Human proof that completely multiplicative sequences have discrepancy greater than 3

From Polymath1Wiki
Jump to: navigation, search

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.