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

From Polymath1Wiki
Jump to: navigation, search
m (New page: 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 w...)
 
Line 34: Line 34:
 
  0 + + - + - - ? + +  0-9
 
  0 + + - + - - ? + +  0-9
 
  - ? - ? ? + + ? + ?  10-19
 
  - ? - ? ? + + ? + ?  10-19
  ? ? ? ? - + ? - ? ?  20-29
+
  - ? ? ? - + ? - ? ?  20-29
 
  + ? + ? ? ? + ? ? ?  30-39
 
  + ? + ? ? ? + ? ? ?  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
+
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 1 2 3 4 5 6 7 8 9
Line 43: Line 43:
 
  0 + + - + - - - + +  0-9
 
  0 + + - + - - - + +  0-9
 
  - ? - ? - + + ? + ?  10-19
 
  - ? - ? - + + ? + ?  10-19
  ? + ? ? - + ? - - ?  20-29
+
  - + ? ? - + ? - - ?  20-29
 
  + ? + ? ? + + ? ? ?  30-39
 
  + ? + ? ? + + ? ? ?  30-39
 
  - ? + ? ? - ? ? - +  40-49
 
  - ? + ? ? - ? ? - +  40-49
 +
+ ? ? ? - ? ? ? ? ?  50-59
  
This seems to be about as far as one can get just from the assumption f(2)=+1.  What's the next step?
+
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.

Revision as of 14:42, 28 January 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.

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.