Human proof that completely multiplicative sequences have discrepancy greater than 3
This page will attempt to prove that there are no infinite completely multiplicative sequences of discrepancy 3 using a similar approach to the [1] page. It will move a bit quicker, since there is a lot more to get through. Obviously, this is a project that can't be completed in a reasonable time, as the largest completely multiplicative sequence has length 127645 (See [2]). Another purpose of this discussion is to see if a human can be faster than a computer doing a brute force search. I can now say that a human can be, since they can see where the blocks are generated, whereas the computer is doomed to hit the block thousands (maybe even millions) of times before it finds a way through. I must admit though that I do cheat a little, and use the computer's brute force to find the blocks in the first place.
Case 1: f(2) = 1
First, assume f(2) = 1. The table now looks like this:
0 1 2 3 4 5 6 7 8 9
0|+ + ? + ? ? ? + + 0-9 ? ? ? ? ? ? + ? + ? 10-19 ? ? ? ? ? + ? ? ? ? 20-29 ? ? + ? ? ? + ? ? ? 30-39
Using discrepancy we can get f(3)=-1, thus:
0 1 2 3 4 5 6 7 8 9
0|+ + - + ? - ? + + 0-9 ? ? - ? ? ? + ? + ? 10-19 ? ? ? ? - + ? - ? ? 20-29 ? ? + ? ? ? + ? ? ? 30-39
Now, the discrepancy up to 10 is: 3+2f(5)+f(7). Therefore f(5)=-1. Updating the table, and adding a cut after 6:
0 1 2 3 4 5 6 7 8 9
0|+ + - + - -|? + + 0-9 - ? - ? ? + + ? + ? 10-19 - ? ? ? - + ? - ? ? 20-29 + ? + ? ? ? + ? ? ? 30-39
This seems to be as far as we can get with the assumption f(2) = 1.
Case 1.1: f(2)=f(7)=1
This first attempt will usually make an assumption about the first unknown value. There may be more profitable assumptions to make. Now let us assume f(7)=1. Updating the table:
0 1 2 3 4 5 6 7 8 9
0|+ + - + - -|+ + + 0-9 - ? - ? + + + ? + ? 10-19 - - ? ? - + ? - + ? 20-29 + ? + ? ? - + ? ? ? 30-39
The discrepancy up to 18 is now 5+f(11)+f(13)+f(17). Therefore f(11)=f(13)=f(17)=-1. Updating the table again:
0 1 2 3 4 5 6 7 8 9
0|+ + - + - - + + + 0-9 - - - - +|+ + - + ? 10-19 - - - ? - + - - + ? 20-29 + ? + + - - + ? ? + 30-39
Again, it seems this is as far as we can go with this assumption.
If you assume f(19)=f(23)=f(29)=1 (Case 1.1.1), then Side Proof 1 shows that stops working at 334. If you assume f(29)=-1 and f(19)=f(23)=f(31)=1 (Case 1.1.2), then Side Proof 2 shows that this stops working at 584. Therefore, if f(19)=f(23)=1, then f(29)=f(31)=-1.
Case 1.1.3: f(2)=f(7)=f(19)=f(23)=f(37)=1, f(29)=f(31)=-1
We now assume that f(37)=1. By f[285,290]=5+f(41), we have that f(41)=-1. Updating the table:
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 + ? + ? - + ? ? - ? 100-109 + - + ? - - - - ? - 110-119 + + ? + - - + ? + ? 120-129 + ? + + ? + - ? - ? 130-139
Unfortunately, we don't get any further with this assumption, so we have to make another couple of assumptions
Side Proof 3 shows that the assumption f(43)=1 (Case 1.1.3.1) fails at 726. Therefore, f(43)=-1.
Side Proof 4 shows that the assumption f(43)=-1 (Case 1.1.3.2) fails at 1208. Therefore, f(37)=-1.
Case 1.1.4: f(2)=f(7)=f(19)=f(23)=1, f(29)=f(31)=f(37)=-1
We now assume that f(37)=-1. By f[285,292]=5+f(41)-f(97), we have that f(41)=-1, f(97)=1. Also, s(48)=-4+f(43)+f(47), so f(43)=f(47)=1. Updating the table:
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 + ? + ? - + ? ? - ? 100-109 + + + ? - - - - ? - 110-119 + + ? + - - + ? + - 120-129 + ? + + ? + - ? - ? 130-139
Now, f[183,188] = 5-f(61), so f(61)=1. However, now s(66)=4+f(59)+f(61), so f(53)=f(59)=-1. Updating the table:
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 + ? + ? - + - ? - ? 100-109 + + + ? - - - - - - 110-119 + + + + - - + ? + - 120-129 + ? + + ? + - ? - ? 130-139
As you can see, f[113,118] = -5+f(113), so f(113)=1. Also, f[169,188] = 8+f(89)+f(173)+f(179)+f(181), so f(89)=f(173)=f(179)=f(181)=-1. Updating the table:
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 + ? + ? - + - ? - ? 100-109 + + + + - - - - - - 110-119 + + + + - - + ? + - 120-129 + ? + + ? + - ? - ? 130-139
Now, f[219,226] = 6-f(73)+f(223), so f(73)=1, f(223)=-1. Therefore, f[355,366]=-6-f(71)+f(359), so f(71)=-1, f(359)=1.
If we assume f(67)=1, we have the following: f[121,134] = 6+f(127)+f(131), so f(127)=f(131)=-1. Therefore, f[247,262] = -7-f(83)+f(251)+f(257), so f(83)=-1, f(251)=f(257)=1. Now, s(84)=-3+f(79), so f(79)=1. f[227,238] = -7+f(227)+f(229)+f(233), so f(227)=f(233)=f(239)=1. f[439,454] = 9-f(149)-f(151)+f(439)+f(443)+f(449), so f(149)=f(151)=1, f(439)=f(443)=f(449)=-1. However, now f[143,162]=7+f(157), which is a contradiction.
Therefore, f(67)=-1.
s(84)=-4+f(79)+f(83), so f(79)=f(83)=1. f[227,238] = -7+f(227)+f(229)+f(233), so f(227)=f(233)=f(239)=1. f[439,454] = 9-f(149)-f(151)+f(439)+f(443)+f(449), so f(149)=f(151)=1, f(439)=f(443)=f(449)=-1. However, now f[143,162]=7+f(157), which is a contradiction.
Therefore, f(23)=-1.
The assumptions in Case 1.1.4 fail at 454.
Case 1.1.5: f(2)=f(7)=f(19)=f(29)=1, f(23)=-1
Updating the table:
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 + ? + ? - + ? ? - ? 100-109 + ? + ? - + + - ? - 110-119 + + ? ? ? - + ? + ? 120-129 + ? + + ? + - ? + ? 130-139
f[49,66] = 8+f(31)+f(53)+f(59)+f(61), so f(31)=f(53)=f(59)=f(61)=-1. f[243,250] = -6-f(41)-f(83), so f(41)=f(83)=-1. s(46)=-5+f(37)+f(43)+f(47), so f(37)=f(43)=f(47)=1. f[339,344] = 5-f(113), so f(113)=1. f[527,534] = 5-f(89), so f(89)=1. f[79,92] = -5+f(79), so f(79)=1.
Updating the table:
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 + ? + ? - + - ? - ? 100-109 + - + + - + + - - - 110-119 + + - + - - + ? + - 120-129 + ? + + ? + - ? + ? 130-139
It seems this is as far as we can get with this assumption.
Side Proof 5 shows that the assumption f(67)=1 fails at 688.
Side Proof 6 shows that the assumption f(67)=-1 fails, also at 688.
Therefore, f(29)=-1.
Case 1.1.6: f(2)=f(7)=f(19)=f(31)=1, f(23)=f(29)=-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 + ? + ? - + ? ? - ? 100-109 + ? + ? - + - - - - 110-119 + + - ? + - + ? + ? 120-129 + ? + + ? + - ? + ? 130-139
f[49,66] = 7+f(53)+f(59)+f(61), so f(61)=-1. f[89,96] = -6+f(47)+f(89), so f(47)=f(89)=1. f[169,178] = 6+f(43)+f(173), so f(43)=f(173)=-1. f[83,96] = -5+f(83), so f(83)=1. f[243,250] = -5-f(41), so f(41)=-1. However, then s(46)=-4, contradiction.
Therefore the assumption fails at 250. Therefore, f(31)=-1.
Case 1.1.7: f(2)=f(7)=f(19)=1, f(23)=f(29)=f(31)=-1
s(46) = -6+f(37)+f(41)+f(43)+f(47), so f(37)=f(41)=f(43)=f(47)=1. f[243,248] = -5+f(61), so f(61)=1. s(66)=4+f(53)+f(59), so f(53)=f(59)=-1. However, now f[285,290] = 6, which forces the discrepancy above 3. Therefore, f(19)=-1.
Case 1.1.8: f(2)=f(7)=1, f(19)=-1
s(24)=-3+f(23), so f(23)=1. f[49,66] = 8+f(29)+f(31)+f(53)+f(59)+f(61), so f(29)=f(31)=f(59)=f(61)=-1. s(48) = -6+f(37)+f(41)+f(43)+f(47), so f(37)=f(41)=f(43)+f(47)=1. However, now f[115,124] = -6, which forces the discrepancy above 3.
Therefore, f(7)=-1.
Case 1.2: f(2)=f(11)=f(13)=1, f(7)=-1
Updating the table:
0 1 2 3 4 5 6 7 8 9
0|+ + - + - - - + + 0-9 - + - + -|+ + ? + ? 10-19 - + + ? - + + - - ? 20-29 + ? + - ? - + ? ? - 30-39
s(26)=5+f(17)+f(19)+f(23), so f(17)=f(19)=f(23)=-1. Updating the table:
0 1 2 3 4 5 6 7 8 9
0|+ + - + - - - + + 0-9 - + - + -|+ + - + - 10-19 - + + - - + + - - ? 20-29 + ? + - - - + ? - - 30-39
It seems like we cannot get much further with this assumption.
Case 1.2.1: f(2)=f(11)=f(13)=f(29)=1, f(7)=-1
s(32)=3+f(31), so f(31)=-1. f[115,122] = 6+f(59)+f(61), so f(59)=f(61)=-1.
We have a few equations:
1) f[243,260] = -9-f(37)-f(41)-f(43)-f(83)+f(127)+f(251)+f(257) >= -4
2) f[75,92] = -5+f(41)+f(43)+f(79)+f(83)+f(89) >= -4
3) f[61,78] = -6+f(37)+f(67)+f(71)+f(73) >= -4
4) f[201,210] = -3-f(67)+f(101)+f(103) >= -4
5) f[93,104] = 6+f(47)+f(97)+f(101)+f(103) <= 4
(1)+(2)+(3)+(4)-(5)+29: -f(47)+f(71)+f(73)+f(79)+f(89)-f(97)+f(127)+f(251)+f(257) >= 9
f(47)=f(97)=-1, f(71)=f(73)=f(79)=f(83)=f(127)=f(251)=f(257)=1.
Now, f[69,74] = 5+f(37), so f(37)=-1. s(48)=-4+f(41)+f(43), so f(41)=f(43)=1. However, now f[79,86] = 6, which is a contradiction.
Therefore, f(29)=-1.
Case 1.2.2: f(2)=f(11)=f(13)=1, f(7)=f(29)=-1
Side Proof 7 shows that this assumption fails at 262.
Therefore, f(13)=-1.
Case 1.3: f(2)=f(11)=f(17)=1, f(7)=f(13)=-1
Firstly, s(22) = 3+f(19), so f(19)=-1. f[51,56] = -5+f(53), so f(53)=1.
Unfortunately, that seems to be as far as we can get with this assumption.
Side Proof 8 shows that the assumption f(23)=1 (Case 1.3.1) fails at 586. Therefore, f(23)=-1. f[45,56] = -5+f(47), so f(47)=1.
Side Proof 9 shows that the assumption f(29)=1 (Case 1.3.2) fails at 438. Therefore, f(29)=-1.
Side Proof 10 shows that the assumption f(31)=1 (Case 1.3.3) fails.
