Difference between revisions of "Human proof that completely multiplicative sequences have discrepancy greater than 2"

From Polymath1Wiki
Jump to: navigation, search
(Case 1.b f(2)=1, f(37)=-1)
Line 242: Line 242:
 
  - + ? ? + C ? F a ?  80-89
 
  - + ? ? + C ? F a ?  80-89
 
  - B C ? ? + - ? + a  90-99
 
  - B C ? ? + - ? + a  90-99
  -
+
  +
This seems to be about as far as one can get just from the assumption f(2)=+1.
+
  
 
So we assume f(37)=-1
 
So we assume f(37)=-1
Line 251: Line 250:
 
  0 + + - + - - - + +  0-9
 
  0 + + - + - - - + +  0-9
 
  -|a - b - + + c + -  10-19
 
  -|a - b - + + c + -  10-19
- + a e - + b - - f  20-29
 
+ ? + A c + + - - B  30-39
 
- ? + ? a - e ? - +  40-49
 
+ C b ? - A - + f ?  50-59
 
+ ? ? - + B A ? c E  60-69
 
+ ? + ? - - - A B ?  70-79
 
- + ? ? + C ? F a ?  80-89
 
- B C ? ? + - ? + a  90-99
 
-
 
 
a and b can't both be - (five -s starting at 10).
 
 
A,B can't both be - (five -s starting at 74)
 
 
Also note that there must be a cut between 74 and 75 due to the rule that when f(2n)=f(2n+1) there is a cut between.
 
 
Therefore a and b can't both be +, so a and b are alternating, so there is a cut before 17.
 
 
0 1 2 3 4 5 6 7 8 9
 
 
0 + + - + - - - + +  0-9
 
-|a - b - + +|c + -  10-19
 
 
  - + a e - + b - - f  20-29
 
  - + a e - + b - - f  20-29
 
  + ? + A c + + - - B  30-39
 
  + ? + A c + + - - B  30-39
Line 283: Line 260:
 
  -
 
  -
  
A must be + (otherwise the sum reaches -3 at 76) and since A and B are also alternating, B must be - also forcing 79 to be +.
+
From f[75,77] we have A=+1, then from f[11,13] we have b=-1, and then from f[75,79] we have f(79)=+1:
 
+
A = +1 and B = -1 so a = -1 and b = +1.
+
  
 
  0 1 2 3 4 5 6 7 8 9
 
  0 1 2 3 4 5 6 7 8 9
Line 292: Line 267:
 
  -|- - + - + +|c + -  10-19
 
  -|- - + - + +|c + -  10-19
 
  - + - e - + + - - f  20-29
 
  - + - e - + + - - f  20-29
  + ? + + c|+ + - - -  30-39
+
  + ? +|+ c|+ + - -|-  30-39
  - + + ? - - e ? - +  40-49
+
  - ? + ? - - e ? - +  40-49
 
  + C + ? - + - + f ?  50-59
 
  + C + ? - + - + f ?  50-59
 
  + ? ? - + - + ? c E  60-69
 
  + ? ? - + - + ? c E  60-69
Line 299: Line 274:
 
  - + ? ? + C ? F - ?  80-89
 
  - + ? ? + C ? F - ?  80-89
 
  - - C ? ? + - ? + -  90-99
 
  - - C ? ? + - ? + -  90-99
  -
+
  +
  
+ + - - - - forces cut before the start of the sequence, so the only way for sum to be 0 with + + ? | is if ? = -1, so c = -1.
+
From f[33,34] we have c=-1, and from f[39,41] we have f(41)=+1;
  
 
  0 1 2 3 4 5 6 7 8 9
 
  0 1 2 3 4 5 6 7 8 9
Line 315: Line 290:
 
  - + ? ? + + ? F - ?  80-89
 
  - + ? ? + + ? F - ?  80-89
 
  - - + ? ? + - ? + -  90-99
 
  - - + ? ? + - ? + -  90-99
  -
+
  +
  
So sums force e = +
+
From f[19,23] we have e = +
  
 
  0 1 2 3 4 5 6 7 8 9
 
  0 1 2 3 4 5 6 7 8 9
Line 331: Line 306:
 
  - + ? ? + + ? F - ?  80-89
 
  - + ? ? + + ? F - ?  80-89
 
  - - + ? ? + - ? + -  90-99
 
  - - + ? ? + - ? + -  90-99
  -
+
  +
  
So f = +, so 31 = -, and sums and multiplicity force
+
From f[27,29] we have f = +, so from f[27,34] we have f(31) = -, and sums and multiplicity force
  
 
  0 1 2 3 4 5 6 7 8 9
 
  0 1 2 3 4 5 6 7 8 9
Line 347: Line 322:
 
  - + + ? + + + - - ?  80-89
 
  - + + ? + + + - - ?  80-89
 
  - - + + - + - ? + -  90-99
 
  - - + + - + - ? + -  90-99
  -
+
  +
  
 
The smallest sum before 70 is -1, so 71 must be -1. This forces 67 = -1, otherwise the sum at 73 is 3.
 
The smallest sum before 70 is -1, so 71 must be -1. This forces 67 = -1, otherwise the sum at 73 is 3.
Line 363: Line 338:
 
  - + +|? + + + - - ?  80-89
 
  - + +|? + + + - - ?  80-89
 
  - - + + - + - ? + -  90-99
 
  - - + + - + - ? + -  90-99
  -
+
  +
  
 
83 must be -, otherwise the sum is 3 at 85.
 
83 must be -, otherwise the sum is 3 at 85.
Line 379: Line 354:
 
  - + +|- +|+ + - -|?  80-89
 
  - + +|- +|+ + - -|?  80-89
 
  - - + + - + - ? + -  90-99
 
  - - + + - + - ? + -  90-99
  -
+
  +
  
 
So 89 is + (otherwise the sum is -3 at 91)
 
So 89 is + (otherwise the sum is -3 at 91)

Revision as of 15:43, 1 February 2010

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.

The notions of a cut and a block will be useful. A cut occurs between n and n+1 whenever it can be proved that f[1,n] sums to 0; these can only occur when n is even. We indicate a cut by a bar | between n and n+1. Thus for instance we begin with just one cut:

0 1 2 3 4 5 6 7 8 9

0|+ ? ? + ? ? ? ? +   0-9
? ? ? ? ? ? + ? ? ?   10-19
? ? ? ? ? + ? ? ? ?   20-29
? ? ? ? ? ? + ? ? ?   30-39

A block is any interval between two cuts; thus inside each block one must sum to zero, and the discrepancy inside each block is at most 2. Thus we can "localise" the analysis to each block, though multiplicativity relates the blocks together.

A block is solved if all values are assigned in it. Solved blocks are uninteresting (other than for the values they provide by multiplicativity), so we shall adopt the convention of concatenating solved blocks with adjacent blocks to reduce clutter.

More notation: we use f[a,b] as short for f(a)+...+f(b). Note that

f[a,b] = -4,-2,0,2,4 if a is odd and b is even;
f[a,b] = -3,-1,1,3 if a and b are both odd or both even;
f[a,b] = -2,0,2 if a is even and b is odd.

Also if [a,b] starts or ends at a cut, then f[a,b] has magnitude at most 2.

A key observation is that if f(2n)=f(2n+1) then there must be a cut between 2n and 2n+1.

Case 1. f(2)=1

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

As f(8)=f(9) we can now cut at 8=9. 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 and adding cuts where obvious extends to

0 1 2 3 4 5 6 7 8 9

0 + + - + - -|? +|+   0-9
-|? - ? ? + + ? + ?   10-19
- ? ? ? - + ? - ? ?   20-29
+ ? + ? ? ? + ? ? ?   30-39

Looking at the 7-8 block 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
+

Note that

f[15,19] = 3 + f(17) + f(19)

cannot exceed 3, and

f[168,171] = 2 - f(17) + f(19)

cannot exceed 2. Thus f(19) = -1. We use this information to update the board:

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
+

Let's write f(11)=a, f(13)=b, f(17)=c, f(23)=e, f(29)=f and A = -a, B = -b, C = -c, 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 + -   10-19
- + a e - + b - - f   20-29
+ ? + A c + + ? - B   30-39
- ? + ? a - e ? - +   40-49
+ C b ? - A - + f ?   50-59
+ ? ? - + B A ? c E   60-69
+ ? + ? ? - - A B ?   70-79
- + ? ? + C ? F a ?   80-89
- B C ? ? + - ? + a   90-99
+

This seems to be about as far as one can get just from the assumption f(2)=+1.

Case 1.a f(2)=f(37)=1

The most profitable assumption here seems to be f(37)=+1. This creates a cut at 36-37, which then forces f(34)=-1 and then f(33)=-1 also. Filling in these values and adding in cuts, and extending a row gives

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 e ? ? + - ? +|+   90-99
+ ? + ? b - ? ? - ?   100-109

looking at f[30,32] we thus have f(31)=-1, while from f[99,103] we have f(101)=f(103)=-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 e + ? + - ? +|+   90-99
+ - + - b - ? ? - ?   100-109

From the [51,54] block we have f(53) = B, which then forces f[90,106]=0, so there is a cut at 106-107:

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 B -|- - + f ?   50-59
+ ? - - + B - ? - E   60-69
+ ? + ? + - -|- B ?   70-79
- + ? ? +|+ ? F + ?   80-89
- B e + ? + - ? +|+   90-99
+ - + - b - B|? - ?   100-109
-|- - ? + E f b ? +   110-119
+|+ ? ? -|- - ? + ?   120-129

From f[118-120] we have f(59)=-1; from f[111,113] we have f(113)=+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 B -|- - + f -   50-59
+ ? - - + B - ? - E   60-69
+ ? + ? + - -|- B ?   70-79
- + ? ? +|+ ? F + ?   80-89
- B e + ? + - ? +|+   90-99
+ - + - b - B|? - ?   100-109
-|- - + +|E f b - +   110-119
+|+ ? ? -|- - ? + ?   120-129

From f[13,30] we have 2b+e+f=0 while from f[115,120] we have -e+f+b=-1. This forces b=-1, e=f=1:

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

From the 60-69 row we then get f(61)=+1, f(67)=+1; from f[85,92] we get f(43)=f(89)=-1; from f[93,98] we have f(47)=f(97)=-1; from f[125,127] one has f(127)=+1; from f[107,110] one gets f(107)=f(109)=+1:

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

From f[41,50] one has f(41)=-1; but then f[121,125]=2, a contradiction. Hence this case is not possible.

Case 1.b f(2)=1, f(37)=-1

This takes us back to case 1.b f(2)=1, f(37)=-1, which begins here:

Let's write f(11)=a, f(13)=b, f(17)=c, f(23)=e, f(29)=f and A = -a, B = -b, C = -c, 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 + -   10-19
- + a e - + b - - f   20-29
+ ? + A c + + ? - B   30-39
- ? + ? a - e ? - +   40-49
+ C b ? - A - + f ?   50-59
+ ? ? - + B A ? c E   60-69
+ ? + ? ? - - A B ?   70-79
- + ? ? + C ? F a ?   80-89
- B C ? ? + - ? + a   90-99
+

So we assume f(37)=-1

0 1 2 3 4 5 6 7 8 9

0 + + - + - - - + +   0-9
-|a - b - + + c + -   10-19
- + a e - + b - - f   20-29
+ ? + A c + + - - B   30-39
- ? + ? a - e ? - +   40-49
+ C b ? - A - + f ?   50-59
+ ? ? - + B A ? c E   60-69
+ ? + ? -|- - A B ?   70-79
- + ? ? + C ? F a ?   80-89
- B C ? ? + - ? + a   90-99
-

From f[75,77] we have A=+1, then from f[11,13] we have b=-1, and then from f[75,79] we have f(79)=+1:

0 1 2 3 4 5 6 7 8 9
0 + + - + - - - + +   0-9
-|- - + - + +|c + -   10-19
- + - e - + + - - f   20-29
+ ? +|+ c|+ + - -|-   30-39
- ? + ? - - e ? - +   40-49
+ C + ? - + - + f ?   50-59
+ ? ? - + - + ? c E   60-69
+ ? + + - - - + - +   70-79
- + ? ? + C ? F - ?   80-89
- - C ? ? + - ? + -   90-99
+

From f[33,34] we have c=-1, and from f[39,41] we have f(41)=+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[19,23] we have e = +

0 1 2 3 4 5 6 7 8 9
0 + + - + - - - + +   0-9
-|- - + - + +|- +|-   10-19
- + - + - + +|- - f   20-29
+ ? + + -|+ + - - -   30-39
- + + ? - - + ? - +   40-49
+ + + ? - + - + f ?   50-59
+ ? ? - + - + ? + -   60-69
+ ? + + - - - + - +   70-79
- + ? ? + + ? F - ?   80-89
- - + ? ? + - ? + -   90-99
+

From f[27,29] we have f = +, so from f[27,34] we have f(31) = -, and sums and multiplicity force

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 smallest sum before 70 is -1, so 71 must be -1. This forces 67 = -1, otherwise the sum at 73 is 3.

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
+

83 must be -, otherwise the sum is 3 at 85.

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
+

So 89 is + (otherwise the sum is -3 at 91)

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
-