Human proof that completely multiplicative sequences have discrepancy greater than 2

It is known from computer search that the longest completely multiplicative sequence [math]\displaystyle{ 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