Difference between revisions of "Human proof that completely multiplicative sequences have discrepancy greater than 2"
| Line 414: | Line 414: | ||
+ - - + + - -|? - ? 130-139 | + - - + + - -|? - ? 130-139 | ||
+|+ ? - + - ? - + ? 140-149 | +|+ ? - + - ? - + ? 140-149 | ||
| + | |||
| + | Extending through multiplicative knowledge ... | ||
| + | |||
| + | 0 1 2 3 4 5 6 7 8 9 | ||
| + | |||
| + | 0 + + - + - - - + + 0-9 | ||
| + | - + - - - + + - + - 10-19 | ||
| + | - + + + - + - - - + 20-29 | ||
| + | + - + - - + + + - + 30-39 | ||
| + | - - + - + - + - - + 40-49 | ||
| + | + + - + - - - + +|- 50-59 | ||
| + | + ? -|- + + - + - - 60-69 | ||
| + | +|? + ? + - -|- + - 70-79 | ||
| + | - + + - + + - - + - 80-89 | ||
| + | - + + + - + - - + + 90-99 | ||
| + | -|? + ? -|- +|+ - + 100-109 | ||
| + | - - - + +|- +|- - + 110-119 | ||
| + | + + + - - - - + + + 120-129 | ||
| + | + - - + + - -|? - ? 130-139 | ||
| + | +|+ ? - + - ? - + ? 140-149 | ||
| + | - ? - - - + + ? - - 150-159 | ||
| + | |||
| + | We know 71 and 73 must be alternate signs, so by multiplicative properties 142 (2 * 71) and 146 2 * 73) must have alternate signs, so the sum is zero immediately before 147 and 149. Now extendind the list to 159: | ||
| + | |||
| + | 0 1 2 3 4 5 6 7 8 9 | ||
| + | |||
| + | 0 + + - + - - - + + 0-9 | ||
| + | - + - - - + + - + - 10-19 | ||
| + | - + + + - + - - - + 20-29 | ||
| + | + - + - - + + + - + 30-39 | ||
| + | - - + - + - + - - + 40-49 | ||
| + | + + - + - - - + +|- 50-59 | ||
| + | + ? -|- + + - + - - 60-69 | ||
| + | +|? + ? + - -|- + - 70-79 | ||
| + | - + + - + + - - + - 80-89 | ||
| + | - + + + - + - - + + 90-99 | ||
| + | -|? + ? -|- +|+ - + 100-109 | ||
| + | - - - + +|- +|- - + 110-119 | ||
| + | + + + - - - - + + + 120-129 | ||
| + | + - - + + - -|? - ? 130-139 | ||
| + | +|+ ? - + - ?|- +|? 140-149 | ||
| + | - ? - - - + + ? - - 150-159 | ||
| + | |||
| + | 151 must be + because otherwise we have 5 -s in a row, and 149 must be + because otherwise the sum will be -3 at 153, so immediately before 157 the sum is 0: | ||
| + | |||
| + | 0 1 2 3 4 5 6 7 8 9 | ||
| + | |||
| + | 0 + + - + - - - + + 0-9 | ||
| + | - + - - - + + - + - 10-19 | ||
| + | - + + + - + - - - + 20-29 | ||
| + | + - + - - + + + - + 30-39 | ||
| + | - - + - + - + - - + 40-49 | ||
| + | + + - + - - - + +|- 50-59 | ||
| + | + ? -|- + + - + - - 60-69 | ||
| + | +|? + ? + - -|- + - 70-79 | ||
| + | - + + - + + - - + - 80-89 | ||
| + | - + + + - + - - + + 90-99 | ||
| + | -|? + ? -|- +|+ - + 100-109 | ||
| + | - - - + +|- +|- - + 110-119 | ||
| + | + + + - - - - + + + 120-129 | ||
| + | + - - + + - -|? - ? 130-139 | ||
| + | +|+ ? - + - ?|- +|+ 140-149 | ||
| + | - + - - - + +|? - - 150-159 | ||
Revision as of 07:43, 29 January 2010
It is known from computer search that the longest completely multiplicative sequence [math]f: [N] \to \{-1,+1\}[/math] of discrepancy 2 has length 246. Here we record the attempts to prove this by hand. Notation: we display our function in rows of 10, starting with 0. We use the notation that + and - denote values which are known to equal +1 or -1 respectively, and ? for unknown values. I'll also put a bar | after the last place where it is known that f(1)+...f(n) sums to 0; these can only occur after an even number, and will be automatic in the middle of any ++++ or ---- string. Thus, initially our array looks like this:
0 1 2 3 4 5 6 7 8 9 0|+ ? ? + ? ? ? ? + 0-9 ? ? ? ? ? ? + ? ? ? 10-19 ? ? ? ? ? + ? ? ? ? 20-29 ? ? ? ? ? ? + ? ? ? 30-39
since f(n^2) = 1 for all square numbers.
Now, let us assume f(2)=1 and that the discrepancy is at most 2 and see what happens. From multiplicativity we obtain f(2n^2)=1, thus
0 1 2 3 4 5 6 7 8 9 0|+ + ? + ? ? ? + + 0-9 ? ? ? ? ? ? + ? + ? 10-19 ? ? ? ? ? + ? ? ? ? 20-29 ? ? + ? ? ? + ? ? ? 30-39
and then by using discrepancy we get f(3)=f(5)=-1, thus
0 1 2 3 4 5 6 7 8 9 0|+ + - + - ? ? + + 0-9 ? ? ? ? ? ? + ? + ? 10-19 ? ? ? ? ? + ? ? ? ? 20-29 ? ? + ? ? ? + ? ? ? 30-39
which then by multiplicativity extends to
0 1 2 3 4 5 6 7 8 9 0 + + - + - -|? + + 0-9 - ? - ? ? + + ? + ? 10-19 - ? ? ? - + ? - ? ? 20-29 + ? + ? ? ? + ? ? ? 30-39
Looking at f(1)+...+f(9) we see that f(7) is forced to be -1; from this and multiplicativity, and showing rows up to 100, we arrive at
0 1 2 3 4 5 6 7 8 9 0 + + - + - - - + + 0-9 -|? - ? - + + ? + ? 10-19 - + ? ? - + ? - - ? 20-29 + ? + ? ? + + ? ? ? 30-39 - ? + ? ? - ? ? - + 40-49 + ? ? ? - ? - ? ? ? 50-59 + ? ? ? + ? ? ? ? ? 60-69 + ? + ? ? - ? ? ? ? 70-79 - + ? ? ? ? ? ? ? ? 80-89 - ? ? ? ? ? - ? + ? 90-99 -
This seems to be about as far as one can get just from the assumption f(2)=+1.
Let's write f(11)=a, f(13)=b, f(17)=c, f(19)=d, f(23)=e, f(29)=f and A = -a, B = -b, C = -c, D=-d, E=-e, F=-f. Then we can fill in more:
0 1 2 3 4 5 6 7 8 9 0 + + - + - - - + + 0-9 -|a - b - + + c + d 10-19 - + a e - + b - - f 20-29 + ? + A c + + ? d B 30-39 - ? + ? a - e ? - + 40-49 + C b ? - A - D f ? 50-59 + ? ? - + B A ? c E 60-69 + ? + ? ? - d A B ? 70-79 - + ? ? + C ? F a ? 80-89 - B C ? ? D - ? + a 90-99 -
The most profitable assumption here seems to be f(37)=+1. This forces f(1)+...+f(37) to equal +1, which then forces f(34)=-1 and then f(33)=-1 also. Filling in these values gives
0 1 2 3 4 5 6 7 8 9 0 + + - + - - - + + 0-9 - + -|b - + + - + d 10-19 - + + e - + b - - f 20-29 + ? + - - + + + d B 30-39 - ? + ? + - e ? - + 40-49 + + b ? - - - D f ? 50-59 + ? ? - + B - ? - E 60-69 + ? + ? + - d - B ? 70-79 - + ? ? + + ? F + ? 80-89 - B + ? ? D - ? + + 90-99 -
looking at f(30)+...+f(37) we thus have f(31)=-1,
0 1 2 3 4 5 6 7 8 9 0 + + - + - - - + + 0-9 - + -|b - + + - + d 10-19 - + + e - + b - - f 20-29 + - + - - + + + d B 30-39 - ? + ? + - e ? - + 40-49 + + b ? - - - D f ? 50-59 + ? - - + B - ? - E 60-69 + ? + ? + - d - B ? 70-79 - + ? ? + + ? F + ? 80-89 - B + + ? D - ? + + 90-99 -
from f(1)+...+f(19) we have b+d <= 0, while from f(35)+...+f(39) we have d-b <= 0. Thus d must be -1:
0 1 2 3 4 5 6 7 8 9
0 + + - + - - - + + 0-9 - + -|b - + + - + - 10-19 - + + e - + b - - f 20-29 + - + - - + + + - B 30-39 - ? + ? + - e ? - + 40-49 + + b ? - - - + f ? 50-59 + ? - - + B - ? - E 60-69 + ? + ? + - - - B ? 70-79 - + ? ? + + ? F + ? 80-89 - B + + ? + - ? + + 90-99 -
Now suppose we assume b=+1. Then by looking at f(1)+...+f(23) we have e=-1, and by looking at f(1)+...+f(37) we then have f=-1, leaving us with
0 1 2 3 4 5 6 7 8 9
0 + + - + - - - + + 0-9 - + - + - + + - + - 10-19 - + + - - + + - - - 20-29 + - + - - + + + -|- 30-39 - ? + ? + - - ? - + 40-49 + + + ? - - - + - ? 50-59 + ? - - + - - ? - + 60-69 + ? + ? + - -|- - ? 70-79 - + ? ? + + ? + + ? 80-89 - - + + ? + - ? + + 90-99 -
from f(1)+...+f(41) we have f(41)=+1, and from f(75)+...+f(79) we have f(79)=+1, and from f(84)+...+f(88) we have f(86)=-1, hence f(43)=-1:
0 1 2 3 4 5 6 7 8 9
0 + + - + - - - + + 0-9 - + - + - + + - + - 10-19 - + + - - + + - - - 20-29 + - + - - + + + - - 30-39 - + + - +|- - ? - + 40-49 + + + ? - - - + - ? 50-59 + ? - - + - - ? - + 60-69 + ? + ? + - -|- - + 70-79 - + +|? + + - + + ? 80-89 - - + + ? + - ? + + 90-99 -
from f(81)+...+f(85) we must have f(83)=-1, and from f(81)+...+f(89) we must have f(89)=-1, and from f(1)+...+f(47) we have f(47)=+1, hence f(94)=-1:
0 1 2 3 4 5 6 7 8 9
0 + + - + - - - + + 0-9 - + - + - + + - + - 10-19 - + + - - + + - - - 20-29 + - + - - + + + - - 30-39 - + + - + - - + - + 40-49 +|+ + ? - - - + - ? 50-59 + ? - - + - - ? - + 60-69 + ? + ? + - -|- - + 70-79 - + + - + + - + + - 80-89 - - +|+ + + - ? + + 90-99 -
But this creates a contradiction at 95, we cannot have three +++ after a |. So we conclude (under the assumptions f(2)=+1 and f(37)=+1) that b=-1:
0 1 2 3 4 5 6 7 8 9
0 + + - + - - - + + 0-9 - + - - - + + - + - 10-19 - + +|e - + - - - f 20-29 + - + - - + + + - + 30-39 - ? + ? + - e ? - + 40-49 + + - ? - - - + f ? 50-59 + ? - - + + - ? - E 60-69 + ? + ? + - - - + ? 70-79 - + ? ? + + ? F + ? 80-89 - + + + ? + - ? + + 90-99 -
From f(1)+...+f(29) we have e=+1 and f=+1. Looking at f(91)+...+f(95) we see that f(94)=-1 hence f(47)=+1, and we have a cut at 92-93, hence also at 96-97:
0 1 2 3 4 5 6 7 8 9
0 + + - + - - - + + 0-9 - + - - - + + - + - 10-19 - + + + - + - - - + 20-29 + - + - - + + + - + 30-39 -|? + ? + - + - - + 40-49 + + - ? - - - + + ? 50-59 + ? - - + + - ? - - 60-69 + ? + ? + - - - + ? 70-79 - + ? ? + + ? - + ? 80-89 - + +|+ - + -|? + + 90-99 -
from f(91)+...+f(99) we have f(97)=-1. From the f(75)+...+f(77) chain we must have a cut at 76-77, hence also at 78-79:
0 1 2 3 4 5 6 7 8 9
0 + + - + - - - + + 0-9 - + - - - + + - + - 10-19 - + + + - + - - - + 20-29 + - + - - + + + - + 30-39 -|? + ? + - + - - + 40-49 + + - ? - - - + + ? 50-59 + ? - - + + - ? - - 60-69 + ? + ? + - -|- +|? 70-79 - + ? ? + + ? - + ? 80-89 - + +|+ - + - - + + 90-99 -|
Any time we have two repeated signs at an even number followed by an odd number, there must be a cut in between, so we have a few more cuts to put in here:
0 1 2 3 4 5 6 7 8 9
0 + + - + - - - + + 0-9 - + - - - + + - + - 10-19 - + + + - + - - - + 20-29 + - + - - + + + - + 30-39 -|? + ? + - + - - + 40-49 +|+ - ? - - - + + ? 50-59 + ? -|- +|+ - ? -|- 60-69 +|? + ? + - -|- +|? 70-79 - + ? ? +|+ ? - + ? 80-89 - + +|+ - + - - + + 90-99 -|
Using the cuts we can fill in f(67)=+1 and f(86)=f(89)=-1, hence f(43)=-1:
0 1 2 3 4 5 6 7 8 9
0 + + - + - - - + + 0-9 - + - - - + + - + - 10-19 - + + + - + - - - + 20-29 + - + - - + + + - + 30-39 -|? + - + - + - - + 40-49 +|+ - ? - - - + + ? 50-59 + ? -|- + + - + - - 60-69 +|? + ? + - -|- +|? 70-79 - + ? ? +|+ - - + - 80-89 - + +|+ - + - - + + 90-99 -|
The 41-50 block then forces f(41)=-1, hence f(82)=+1:
0 1 2 3 4 5 6 7 8 9
0 + + - + - - - + + 0-9 - + - - - + + - + - 10-19 - + + + - + - - - + 20-29 + - + - - + + + - + 30-39 - - + - + - + - - + 40-49 + + -|? - - - + + ? 50-59 + ? -|- + + - + - - 60-69 +|? + ? + - -|- +|? 70-79 - + + ? +|+ - - + - 80-89 - + + + - + - - + + 90-99 -|
The 79-84 block then forces f(79)=f(83)=-1:
0 1 2 3 4 5 6 7 8 9
0 + + - + - - - + + 0-9 - + - - - + + - + - 10-19 - + + + - + - - - + 20-29 + - + - - + + + - + 30-39 - - + - + - + - - + 40-49 + + -|? - - - + + ? 50-59 + ? -|- + + - + - - 60-69 +|? + ? + - -|- + - 70-79 - + + - + + - - + - 80-89 - + + + - + - - + + 90-99 -|
Looking at 53-56 we see that f(53)=+1:
0 1 2 3 4 5 6 7 8 9
0 + + - + - - - + + 0-9 - + - - - + + - + - 10-19 - + + + - + - - - + 20-29 + - + - - + + + - + 30-39 - - + - + - + - - + 40-49 + + - + - - - + +|? 50-59 + ? -|- + + - + - - 60-69 +|? + ? + - -|- + - 70-79 - + + - + + - - + - 80-89 - + + + - + - - + + 90-99 -|
Suppose f(59)=+1. Then f(118)=f(120)=f(121)=1 and f(119)=-f(17), so f(17)=+1. Also, f(57)=f(59)=f(60)=1 and f(58)=f(29), hence f(29)=-1. Next, f(15)+…+f(22) = f(11)+2, hence f(11)=-1; and then f(1)+…+f(13) = f(13)-2, so f(13)=+1. But then f(1)+…+f(23)=f(23)+2, so f(23)=-1. But then f(1)+…+f(29)=-3, contradiction.
Thus we must also have f(59)=-1, so f(61)=+1.
0 1 2 3 4 5 6 7 8 9
0 + + - + - - - + + 0-9 - + - - - + + - + - 10-19 - + + + - + - - - + 20-29 + - + - - + + + - + 30-39 - - + - + - + - - + 40-49 + + - + - - - + +|- 50-59 + + -|- + + - + - - 60-69 +|? + ? + - -|- + - 70-79 - + + - + + - - + - 80-89 - + + + - + - - + + 90-99 -|
The remaining three question marks are unconstrained other than requiring every block to sum to 0. Now consider the sequence up to 119, with the multiplicative values filled in:
0 1 2 3 4 5 6 7 8 9
0 + + - + - - - + + 0-9 - + - - - + + - + - 10-19 - + + + - + - - - + 20-29 + - + - - + + + - + 30-39 - - + - + - + - - + 40-49 + + - + - - - + +|- 50-59 + + -|- + + - + - - 60-69 +|? + ? + - -|- + - 70-79 - + + - + + - - + - 80-89 - + + + - + - - + + 90-99 -|? + ? - - + ? - ? 100-109 - - - ? + - + - - + 110-119
109 is clearly + (otherwise there’s a sequence of 5 -s).
Consider 101 and 103.
Both can’t be + because the sum at 103 would reach 3.
Both can’t be – because then at 105 the sum would reach -3.
Therefore one has to be + and the other -, so the sum is 0 immediately before 105 and 0 immediately before 107.
0 1 2 3 4 5 6 7 8 9
0 + + - + - - - + + 0-9 - + - - - + + - + - 10-19 - + + + - + - - - + 20-29 + - + - - + + + - + 30-39 - - + - + - + - - + 40-49 + + - + - - - + +|- 50-59 + + -|- + + - + - - 60-69 +|? + ? + - -|- + - 70-79 - + + - + + - - + - 80-89 - + + + - + - - + + 90-99 -|? + ? -|- +|? - + 100-109 - - - ? + - + - - + 110-119
Since the sum is 0 before 107, 107 must be + (otherwise the sum is -3 at 111).
Also, the sum is -2 before 103, so 103 is +.
0 1 2 3 4 5 6 7 8 9
0 + + - + - - - + + 0-9 - + - - - + + - + - 10-19 - + + + - + - - - + 20-29 + - + - - + + + - + 30-39 - - + - + - + - - + 40-49 + + - + - - - + +|- 50-59 + + -|- + + - + - - 60-69 +|? + ? + - -|- + - 70-79 - + + - + + - - + - 80-89 - + + + - + - - + + 90-99 -|? + ? -|- +|+ - + 100-109 - - - + +|- +|- - + 110-119
Continuing with known multiplicative values and values set by the sum being 2 or -2 up to 149:
0 1 2 3 4 5 6 7 8 9
0 + + - + - - - + + 0-9 - + - - - + + - + - 10-19 - + + + - + - - - + 20-29 + - + - - + + + - + 30-39 - - + - + - + - - + 40-49 + + - + - - - + +|- 50-59 + ? -|- + + - + - - 60-69 +|? + ? + - -|- + - 70-79 - + + - + + - - + - 80-89 - + + + - + - - + + 90-99 -|? + ? -|- +|+ - + 100-109 - - - + +|- +|- - + 110-119 + + + - - - - + + + 120-129 + - - + + - -|? - ? 130-139 + + ? - + - ? - + ? 140-149
107 and 109 can't both be + (sum reaches 3 at 141) and can't both be - (5 -s in a row) so before 141 the sum must be 0:
0 1 2 3 4 5 6 7 8 9
0 + + - + - - - + + 0-9 - + - - - + + - + - 10-19 - + + + - + - - - + 20-29 + - + - - + + + - + 30-39 - - + - + - + - - + 40-49 + + - + - - - + +|- 50-59 + ? -|- + + - + - - 60-69 +|? + ? + - -|- + - 70-79 - + + - + + - - + - 80-89 - + + + - + - - + + 90-99 -|? + ? -|- +|+ - + 100-109 - - - + +|- +|- - + 110-119 + + + - - - - + + + 120-129 + - - + + - -|? - ? 130-139 +|+ ? - + - ? - + ? 140-149
Extending through multiplicative knowledge ...
0 1 2 3 4 5 6 7 8 9
0 + + - + - - - + + 0-9 - + - - - + + - + - 10-19 - + + + - + - - - + 20-29 + - + - - + + + - + 30-39 - - + - + - + - - + 40-49 + + - + - - - + +|- 50-59 + ? -|- + + - + - - 60-69 +|? + ? + - -|- + - 70-79 - + + - + + - - + - 80-89 - + + + - + - - + + 90-99 -|? + ? -|- +|+ - + 100-109 - - - + +|- +|- - + 110-119 + + + - - - - + + + 120-129 + - - + + - -|? - ? 130-139 +|+ ? - + - ? - + ? 140-149 - ? - - - + + ? - - 150-159
We know 71 and 73 must be alternate signs, so by multiplicative properties 142 (2 * 71) and 146 2 * 73) must have alternate signs, so the sum is zero immediately before 147 and 149. Now extendind the list to 159:
0 1 2 3 4 5 6 7 8 9
0 + + - + - - - + + 0-9 - + - - - + + - + - 10-19 - + + + - + - - - + 20-29 + - + - - + + + - + 30-39 - - + - + - + - - + 40-49 + + - + - - - + +|- 50-59 + ? -|- + + - + - - 60-69 +|? + ? + - -|- + - 70-79 - + + - + + - - + - 80-89 - + + + - + - - + + 90-99 -|? + ? -|- +|+ - + 100-109 - - - + +|- +|- - + 110-119 + + + - - - - + + + 120-129 + - - + + - -|? - ? 130-139 +|+ ? - + - ?|- +|? 140-149 - ? - - - + + ? - - 150-159
151 must be + because otherwise we have 5 -s in a row, and 149 must be + because otherwise the sum will be -3 at 153, so immediately before 157 the sum is 0:
0 1 2 3 4 5 6 7 8 9
0 + + - + - - - + + 0-9 - + - - - + + - + - 10-19 - + + + - + - - - + 20-29 + - + - - + + + - + 30-39 - - + - + - + - - + 40-49 + + - + - - - + +|- 50-59 + ? -|- + + - + - - 60-69 +|? + ? + - -|- + - 70-79 - + + - + + - - + - 80-89 - + + + - + - - + + 90-99 -|? + ? -|- +|+ - + 100-109 - - - + +|- +|- - + 110-119 + + + - - - - + + + 120-129 + - - + + - -|? - ? 130-139 +|+ ? - + - ?|- +|+ 140-149 - + - - - + +|? - - 150-159
