Human proof that completely multiplicative sequences have discrepancy greater than 2

From Polymath1Wiki
Revision as of 14:42, 28 January 2010 by Teorth (Talk | contribs)

Jump to: navigation, search

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. 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 two rows, 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

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, and A = -a, B = -b. Then we can fill in more:

0 1 2 3 4 5 6 7 8 9

0 + + - + - - - + +   0-9
- a - b - + + ? + ?   10-19
- + a ? - + b - - ?   20-29
+ ? + A ? + + ? ? B   30-39
- ? + ? a - ? ? - +   40-49
+ ? b ? - A ? ? ? ?   50-59

but it's not clear how to proceed from here.