(Now that I understand Tao’s argument about Collatz being “Baker-hard”, I can re-explain it in this self-contained post.)
Tao’s Proposition 6 says (roughly), “If you find a case of 2^k - 3^x = n for some small n<x, then I can construct a Collatz counter-example cycle.”
The contrapositive is, “If there are no Collatz cycles (Weak Collatz Conjecture is true), then 2^k - 3^x > x for all (k, x).”
The upshot is, “Anyone who proves the Weak Collatz Conjecture will have proved, as a side effect, the quite hard result 2^k - 3^x > x, which lies in a difficult part of mathematics pioneered by Alan Baker in the 1960s.”
Or, “If you aren’t up to proving things like 2^k - 3^x > x, you aren’t going to solve Collatz.”
Since Proposition 6 is sobering news for a kook, I thought it’s worth understanding.
v = parity vector, such as 11010. This is some series of “up” (1) and “down” (0) moves in a Collatz trajectory.
k = length of v
x = count of 1 s in v
Every parity vector corresponds to some cycle whose first member is
\cfrac{\beta(v)}{2^k-3^x}
where \beta(v) is an interesting sum of 2^i 3^j products, the formula for which is critical to understanding Collatz, but has an unaesthetic form. A concrete example:
\beta(11010) = 2^0 3^2 + 2^1 3^1 + 2^3 3^0 = 23
For every 1 in v, we multiply 2^i (i is the 0-based position of the 1) with 3^j (j is x-m-1 for the first 1, moving down to 0 for the last 1).
One of the biggest problems with Collatz is that these \beta values seem kind of random.
In the case of 11010, the first member of its cycle is
\cfrac{23}{2^5-3^3} = \cfrac{23}{5}
which is not an integer.
It may be surprising that a Collatz cycle can have members that are fractions, but if you consider \frac{23}{5} as odd because 23 is odd, and consider 11010 as a sequence of operations where 1 stands for (3n+1)/2 and 0 stands for n/2, then \frac{23}{5} will return to itself after 5 steps. (Consider a fraction odd if its numerator is odd.)
The Weak Collatz Conjecture posits that no parity vector with k>2 corresponds to a cycle with integer members.
Now suppose I tell you I’ve found k and x such that 2^k - 3^x equals some n < x.
For example:
I say 2^k - 3^x = 2. You can say “not possible”, because 2^k - 3^x is odd.
I say 2^k - 3^x = 3. No, because 2^k - 3^x is throdd.
I say 2^k - 3^x = 5. According to mod-5 tables for 2^a and 3^b, we know 2^k - 3^x isn’t even divisible by 5 unless (at a minimum) k and x are both odd, or both even. If I admit to you, “Actually k is odd and x is even.” Then you say, “Again, not possible”. (Note that I don’t reveal my k and x, and won’t).
2^k - 3^x = 7. Okay, now you’re in a difficult spot. I tell you there’s an infinitude of (k, x) such that 2^k - 3^x is divisible by 7… so who’s to say it never equals 7?
Here, you change tack. Instead of saying “Not possible”, you say “Congratulations, if you are right, then you have also found a Collatz counter-example cycle!”
For the rest, I’m am going to demonstrate using the concrete (false) assertion that 2^{13} - 3^8 = 7, but the argument applies to any 2^k - 3^x = n where n<x.
There are 99 distinct cycles of length 8 with 5 odds, because there are \binom{k}{x} parity vectors with k per cycle .
Considering cycle member
\cfrac{\beta(v)}{2^k - 3^x}
we have 99 “chances” (different \beta values) for this fraction to be an integer. If I’ve claimed 2^{13}-3^8 = 7, then there’s an overwhelming “chance” that at least one of those 99 cycles has integer members. Already, it’s suspicious that 7 is so low.
But \beta values are not, in fact, random. So I can’t knock down your assertion with this probabilistic argument.
Tao’s Proposition 6 actually proves that at least one v of length 13 and weight 8 has a \beta(v) that is divisible by 7. (And more generally for any length k, weight x, and denominator n<x, though I’m going to stick with this concrete example for a while.)
So let’s make the proof sketch.
We start with a particularly-chosen v of length k and weight x, namely
v = 1101101011010
This is the v that distributes the 1s “as evenly as possible” among the 0s. It’s known as the upper Christoffel word, or the parity vector for the Collatz high loop.
The main property we care about is that at least half of the 1s are followed by a 0. This is because the 1-count is at most (2/3)k; otherwise 2^k - 3^x < 0.
So we have at least x/2 places where substring 10 appears in v.
These give us x/2 independent “knobs”, each of which we can decide to locally flip (or not flip), changing some 10 to 01.
Flipping no knobs keeps \beta(1101101011010) = 14501 \equiv 4 \not\equiv 0 \mod 7. So v can’t claim to be a Collatz cycle.
Flipping the first 10 changes v to v^\prime = 1011101011010, which changes \beta(v) by - 3^6 2^1 + 3^6 2^2, which is + 3^6 2^1. Notably, this “plus up” value is coprime to (odd, throdd) 2^k - 3^x.
The plus-up values for all five “knobs” are +1458, +1296, +1728, +1536, and +2048.
Generally speaking, moving from v to v^\prime via an individual flip will not result in \beta(v^\prime) \equiv 0 \mod 7 (though unfortunately for my concrete example, the fourth flip happens to do that, because \beta(v) + 1728 \equiv 0 \mod 7).
But we have at our disposal 32 combinations of flips. Amazingly (or “amusingly”, as Tao puts it), it turns out that one of these combinations is guaranteed to give \beta(v^\prime) \equiv 0 \mod 7, meaning v^\prime will correspond to a Collatz counter-example cycle, thus proving Proposition 6.
The key is that each of the plus-ups is coprime to \beta(v).
The ancient Greeks knew that ax + by = 1 always has a solution in (x, y) if constants a and b are coprime. Somewhere down the line, one of those x multiplies is going to wind up adjacent to one of those y multiples.
In a similar way, 14501 + 1458 y_1 + 1296 y_2 + 1728 y_3 + 1536 y_4 + 2048 y_5 \equiv 0 \mod 7 has a solution in binary y_i (1 = flip, 0 = no flip), provided that:
- each coefficient is coprime to the first constant
- there are enough terms
It turns out that our x/2 available flips are enough.
For better or worse, I’m going to leave it there. I’d be happy to explain ax + by = 1, but expanding “a large enough subset of a finite cyclic group has sum-sets that cover the whole group” into math-kook language isn’t on today’s bingo card.
Intuitively, 7 is so small enough that we can hit it with some combination of y_i. If it were much larger, we might not be able to.
The last thing I want to show is that the other members of the v^\prime cycle are also integers. To get each successive member, we keep rotating v^\prime to the left. If v^\prime starts with 0, then for its left-rotation w, we have
\beta(w) \equiv \beta(v^\prime) 2^{-1} \equiv 0
so \beta(w) \equiv 0. On the other hand, if v^\prime starts with 1, then
\beta(w) \equiv (\beta(v^\prime) - 3^{x-1}) \cdot 3 \cdot 2^{-1} + 2^{k-1}
\equiv - 3^x 2^{-1} + 2^{k-1}
\equiv 2(2^k - 3^x) \equiv 0
And we can continue to rotate by setting v^\prime to w. For this to work, we do need 2^k - 3^x to be divisible by n, though we don’t need 2^k - 3^x = n. In other words, if I claim 2^k - 3^x = 5 for some odd k and even x, you should say “stop right there” rather than attempting to construct a Collatz counter-example cycle.
Final conclusion:
-
The non-trivial separation of powers of 2 and 3 requires advanced math and was difficult to prove even for the Fields Medal-winning mathematicians (like 1960s Alan Baker).
-
If I claim 2^k - 3^x = n for some k, x, and n<x, then you can show me a Collatz counter-example cycle.
-
Therefore, a proof of the Collatz Conjecture will generate, as a by-product, some Fields Medal-worthy knowledge about number theory.
Of course, that “Fields Medal-worthy” knowledge has already been known since the 1960s, so you won’t get a Fields Medal. But, fortunately, this provides an alternate plan: instead of ignoring Baker’s results and winding up having to replicate them (or something even more difficult and powerful), you can use them.
