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. 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 another row, we arrive at
0 1 2 3 4 5 6 7 8 9 0 + + - + - - - + + 0-9 - ? - ? - + + ? + ? 10-19 ? + ? ? - + ? - - ? 20-29 + ? + ? ? + + ? ? ? 30-39 - ? + ? ? - ? ? - + 40-49
This seems to be about as far as one can get just from the assumption f(2)=+1. What's the next step?