View source for Human proof that completely multiplicative sequences have discrepancy greater than 2

It is [[multiplicative sequences|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
 -

(could use intermediate diagrams displayed here with text)

f(58) is positive so f(116) is positive

f(13) is positive and f(9) is a square so f(117) is positive

there is a cut between 116 and 117

f(118) is negative since f(59) is negative

f(7) and f(17) are negative so f(119) is positive

f(3) and f(5) are negative and f(2) is positive so 120 is positive

121 is a square so f(121) is positive

so at 116 the sum is zero at because there is a cut between
116 and 117 at 117 the sum is one since f(117) is positive
at 118 the sum is zero since f(118) is negative and since f(119) f(120) and f(121) are positive at 121 the sum is three and we have shown that if a completely multiplicative sequnce has f(2) equal to 1 and f(37) equal to -1 then it reaches discrepancy 3 before 246.

Since we have previously shown that if a completely multiplicative sequence that has f(2) equal to 1 and f(37)equal to 1 reaches discrepancy 3 before 246 we have any completely multiplicative sequence with f(2) equal to one reaches discrepancy 3 before 246 and that finishes case 1.

== Case 2. f(2) = -1 ==

Therefore f(2) = -1. Resetting 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

Adding in multiplicative values:

 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

(Concatenation of various proofs, needs a lot of polish here)

''Assume'' f(5) = 1

Suppose f(11)= 1 

Setting f(2)=-1... Setting f(5)=1... Setting f(11)=1... Deducing... Setting f(3)=-1... Deducing... Setting f(7)=-1... Setting f(241)=1... Deducing... Setting f(23)=-1... Setting f(17)=-1... Setting f(19)=1... Deducing... Setting f(13)=-1... Setting f(47)=-1... Setting f(59)=1... Setting f(67)=-1... Setting f(239)=1... Setting f(251)=1... Setting f(31)=1... Deducing... Setting f(29)=-1... Setting f(53)=-1... Contradiction! f(1) = 1 and f(1) = -1 (from f(58)=-1) 

So f(11)=-1. 

The above part contains references to f(251). We now try to remove such references thereby keeping cases at a minimum. What follows needs a lot of polish.

Here is the output of my prover for the case: f(2)=-1,f(5)=1,f(11)=1 until roughly f(41) is found. From then on we might need some 'human' input to reduce the number of cases. I have added comments on what partial sums lead to the conclusions.

a[1] = 1; a[2] = -1; a[5] = 1; a[11] = 1;
a[7] = -1;(*"s "6" "2*)
a[3] = -1;(*f[5]*)
a[17] = -1;(*"f "32" "35" "-3-a[17]*)
a[19] = 1;(*"f "54" "57" "3-a[19]*)a[23] = -1;(*"f "20" "25" "3+a[23]*)
a[241] = 1;(*"f "240" "243" "-3+a[241]*)
a[47] = -1;(*"f "44" "47" "3+a[47]*)
a[59] = 1;(*"f "118" "121" "3-a[59]*)
a[67] = -1;(*"f "132" "135" "-3-a[67]*)
a[239] = 1;(*"f "238" "243" "-3+a[239]*)

(* from now on we deviate from the so far Wiki *)

a[29] = 1;(*"f "54" "59" "3-a[29]*)a[97] = -1;(*"f "94" "97" "3+a[97]*)

a[13] = -1;(*"f "116" "121" "3+a[13]*)a[31] = -1;(*f[30]*)
a[191] = 1;(*"f "186" "191" "-3+a[191]*)
a[197] = -1;(*"f "194" "197" "3+a[197]*)

(*a[37]=-1; (*assumption*)
a[41]=1;(*f[40]*)a[61]=-1;(*"f "182" "187" "-3-a[61]*)a[223]=-1;(*"f \
"220" "225" "3+a[223]*)
a[43]=1;(*f[42]*)
a[83]=1;(*"f "82" "87" "-3+a[83]*)a[89]=1;(*"f "84" "89" \
"-3+a[89]*)a[107]=1;(*"f "214" "217" "3-a[107]*)a[131]=1;(*"f "128" \
"133" "-3+a[131]*)a[173]=-1;(*"f "168" "173" "3+a[173]*)
a[53]=1;(*"f "104" "107" "3-a[53]*)
(*contradiction f[55]=3*)*)

a[37] = 1; (*because of the above contradiction*)
a[73] = 1;(*"f "72" "75" "-3+a[73]*)
a[79] = 1;(*"f "74" "79" "-3+a[79]*)
a[109] = 1;(*"f "108" "111" "-3+a[109]*)
a[113] = 1;(*"f "110" "113" "-3+a[113]*)
a[223] = -1; (*"f "220" "223" "3+a[223]*)

(*a[41]=-1; (* assumption*)
a[43]=1;(* f[42]*)a[83]=-1;(*"f "78" "83" "3+a[83]*)a[61]=1;(*"f \
"118" "123" "3-a[61]*)a[163]=1;(*"f "160" "165" "-3+a[163]*)
a[89]=1;(*"f "84" "89" "-3+a[89]*)a[107]=1;(*"f "214" "217" \
"3-a[107]*)a[131]=1;(*"f "128" "133" "-3+a[131]*)a[167]=-1;(*"f "166" \
"171" "3+a[167]*)a[173]=-1;(*"f "168" "173" "3+a[173]*)
a[53]=1;(*"f "104" "107" "3-a[53]*)
(*contradiction f[55]=3*)*)

a[41] = 1;(*because of the above contradiction*)

a[43] = -1;(*f[45]*)
a[53] = -1;(*f[55]*)
a[107] = -1;(*"f "104" "107" "3+a[107]*)

So we have f(2) = -1; f(3) = -1; f(5) = 1; f(7) = -1; f(11) = 1; f(13)= -1; f(17)= -1 and f(37) = 1.

From this we get that a f(220)=f(221)=f(222)=f(224)=f(225)=1. This means that there is a cut at 220 and the sum at 220 is zero and the sum at f(225) is at 3 or more which is greater than two thus the discrepancy is greater than 2 and we have dealt with this case. 

[program name] -2 5 -11
Setting f(2)=-1... Setting f(5)=1... Setting f(11)=-1... Deducing... Setting f(3)=-1... Deducing... Setting f(7)=-1... Setting f(13)=1... Setting f(23)=-1... Setting f(241)=1... Deducing... Contradiction! -1 >= f[1,23] >= 1 

So f(5) = -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

If a completely multiplicative sequence with discrepancy 2 or less has length more than 246 then I think there is a human proof that f(2) and f(5) are -1. Given this I can show that if f(3) is 1 f(7) is -1.

Assume that f(3) is 1 and f(7) is 1. We have by the above that f(2) and f(5) are -1. Then this will give the partial sum at 10 the value 2 so f(11) must be -1.

Since f(12) is 1 the sum at 12 must be 2 and f(13) must be -1.

Then f(25), f(26),f(27),f(28) and f(30) must be 1 this forces f(31) to be -1.

Then f(62), f(63),f(64),f(65) and f(66) must be 1 and we have a contradiction.

So if a completely multiplicative sequence with discrepancy 2 or less has length more than 246 and f(3)=1 then f(7)=-1.

So supopse f(3) = 1 and f(7) = -1.

With these assumptions, the partial sum f[18,21]:=f(18)+f(19)+f(20)+f(21) equals -3+f(19). Since f[1,odd] is in {-1,0,1} it follows that f[18,21]>=-2 and thus f(19)=1.

Similarly we get:

f[168,171]=3+f(17) f(17)=-1,

f[34,37]=3+f(37) f(37)=-1 and

f[74,77]=3-f(11) f(11)=1.

Since f(9)=f(10)=f(11)=f(12)=1 it follows that f(13)=-1.

f[50,55]=-5+f(53)>=-2 which cannot be satisfied for f(53) in {-1,1}.

Hence f(7) cannot be -1 and thus f(3)=-1.

It remains to show (by hand) that there is no completely multiplicative sequence with discrepancy 2 and f(2)=f(3)=f(5)=-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

Putting in multiplicative values:

 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
(need to finish filling in)
 ? ? - ? ? ? ? ? ? ?   70-79
 ? + ? ? ? ? ? ? ? ?   80-89
 ? ? ? ? ? ? ? ? - ?   90-99

This is a proof that there is no completely multiplicative sequence with discrepancy 2, f(2)=f(3)=f(5)=-1 and f(7)=1.

I assume f(2)=-1, f(3)=-1 and f(5)=-1. Then

f[242,245]=-3+f(61) implies f(61)=1.

For the sake of contradiction I assume furthermore f(7) = 1. Then f[1,10]=2 and thus f(11)=-1.

We have:

f[18,21]=-3+f(19) implies f(19)=1,

f[168,171]=3+f(17) implies f(17)=-1,

f[22,25]=3+f(23) implies f(23)=-1,

f[60,63]=3-f(31) implies f(31)=1,

f[60,65]=3-f(13) implies f(13)=1,

f[114,117]=3+f(29) implies f(29)=-1,

f[184,187]=3-f(37) implies f(37)=1,

f(85,91) = 5 + f(89) -f(43) implies f(43)=1,

f[40,43]=3+f(41) implies f(41)=-1,

f[50,55]=3+f(53) implies f(53)=-1,

f[58,61]=3+f(59) implies f(59)=-1,

f[92,95]=-3-f(47) implies f(47)=-1 and

f[132,135]=3-f(67) implies f(67)=1.

0: 1 -1 -1 1 -1 1 1 -1 1 1|2

10: -1 -1 1 -1 1 1 -1 -1 1 -1|0

20: -1 1 -1 1 1 -1 -1 1 -1 -1|-2

30: 1 -1 1 1 -1 1 1 -1 -1 1|0

40: -1 1 1 -1 -1 1 -1 -1 1 -1|-2

50: 1 1 -1 1 1 -1 -1 1 -1 1|0

60: 1 -1 1 1 -1 -1 1 -1 1 1|2

70: f(71) -1 f(73) -1 -1 1 -1 1 f(79) -1|-1+f(71)+f(73)+f(79)

Now f[1,70]=2 and thus f(71)=-1. We have

f[72,75]=-3+f(73) implies f(73)=1,

f[88,91]=3+f(89) implies f(89)=-1 

f(98)=f(99) =-1 which means there is a cut at 98 so the sum is 0 at 98. f(100) =1 so the sum is zero at 100. f(110)=f(111)=-1 so there is a cut at 110 so at 110 the sum is zero. This means that the sum of the numbers 101 to 110 is zero which means three of 101,103,107 and 109 must have positive value with the third negative.

If we look at 200 201 202 and 203 we see that 200 and 201 have value -1 which means there is a cut at 200 and if 202 is negative then since 203 is negative the sum at 203 will be negative 3 so 202 must be positive and hence 101 must be negative and 103,107 and 109 must be positive.

Now look at 206 through 215. Since 103 is positive 206 is negative and since 207 is negative there is a cut at 206 but the sum from 207 to 215 is negative 3 and we have a contradiction.

This is a proof that there is no completely multiplicative sequence with discrepancy 2, f(2)=f(3)=f(5)=-1 and f(7)=-1 (which is the last case).

I assume f(2)=-1, f(3)=-1 and f(5)=-1. Then

f[242,245]=-3+f(61) implies f(61)=1.

For the sake of contradiction I assume furthermore f(7) = -1.

We have:

f[14,17]=3+f(17) implies f(17)=-1 and

f[34,37]=3+f(37) implies f(37)=-1.

Sub-case 1: f(11)=-1.

0: 1 -1 -1 1 -1 1 -1 -1 1 1|0

10: -1 -1 f(13) 1 1 1 -1 -1 f(19) -1|-2+f(13)+f(19)

Then f[1,12]=-2 and thus f(13)=1. Now

f[54,57]=3-f(19) implies f(19)=1.

10: -1 -1 1 1 1 1 -1 -1 1 -1|0

20: 1 1 f(23) 1 1 -1 -1 -1 f(29) -1|f(23)+f(29)

f[1,22]=2 implies f(23)=-1 and then f[1,25]=3 is a contradiction. Thus f(11)=1.

Sub-case 2: f(11)=1.

0: 1 -1 -1 1 -1 1 -1 -1 1 1|0

10: 1 -1 f(13) 1 1 1 -1 -1 f(19) -1|f(13)+f(19)

We have f(9)=f(10)=f(11)=f(14)=f(15)=f(16)=1 and f(12)=-1. This implies f(13)=-1.

f[34,39]=3-f(19) implies f(19)=1,

f[30,33]=-3+f(31) implies f(31)=1,

f[28,33]=-3+f(29) implies f(29)=1 and

f[242,247]=-3+f(41) implies f(41)=1.

10: 1 -1 -1 1 1 1 -1 -1 1 -1|0

20: 1 -1 f(23) 1 1 1 -1 -1 1 -1|1+f(23)

30: 1 -1 -1 1 1 1 -1 -1 1 1|3+f(23)

40: 1 -1 f(43) 1 -1 -f(23) f(47) -1 1 -1|2+f(43)+f(47)

Since f[1,41]=4 +f(23) we get a contradiction and thus f(11) is not 1.

Therefore we get a contradiction in the main case (the case f(7)=-1).

Since f(7)=1 is treated in an earlier post, that completes the proof (by hand) that there is no completely multiplicative sequence with discrepancy 2.


Here is a [[computer proof that completely multiplicative sequences have at least 2]], inspired by the above analysis.