Human proof that completely multiplicative sequences have discrepancy greater than 2

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

It is known from computer search that the longest completely multiplicative sequence $f: [N] \to \{-1,+1\}$ 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?