Human proof that completely multiplicative sequences have discrepancy greater than 2

From Polymath1Wiki
Revision as of 16:43, 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. 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
-|

The remaining four question marks are unconstrained other than requiring every block to sum to 0. So this constructs a multiplicative sequence of length 100, at least...