Ok, hopefully third time’s the charm… (Whoa, simultaneous with @oros post!)
Tao’s Proposition 6 gives a very interesting, sobering reason why the Collatz conjecture is so hard.
Consider:
Proposition A. 2^k - 3^x > x/2, for all integers x and k.
(Let’s restrict to cases where 2^k - 3^x is positive.)
Can you prove Proposition A?
If you can, then you know why 2^{3489238474} - 3^{93849899} \neq 28492791 without having to work out the arithmetic.
Proposition 6. If you can’t prove proposition A, then you can’t prove the Collatz conjecture.
This is sobering, because Proposition A is known to be very hard. It’s a watered-down version of Baker’s theorem showing that 2^k - 3^x grows exponentially in x. But not too watered-down, says Tao – it requires the same transcendental math that won Baker the Fields Medal in the 1960s.
Proposition 6 basically says the Collatz conjecture is “Baker-hard”. The rest of this post justifies it.
Tao’s idea is to show how solving the Collatz conjecture automatically establishes Proposition A … as a side-effect. Meaning, proving Collatz is even harder than proving Proposition A.
Tao does this by taking any claim of the form 2^k - 3^x = n (where n < x/2) and converting it into a Collatz counterexample cycle. Supposing you’ve already proved the Collatz conjecture, that generates a contradiction, and therefore the claim is false. In this way, a proof of the Collatz conjecture establishes Proposition A, by showing all such claims to be false.
Important concepts first:
The way we’ll create a Collatz cycle is to first create a parity sequence v (such as 1001011), a sequence “up” (1) and “down” (0) Collatz steps. Given such a sequence, there’s only one number m that returns to itself after following that sequence of (3n+1)/2 and n/2 operations.
v = a parity sequence
k = the length of v
x = the number of 1s in v
m = \cfrac{\beta(v)}{2^k - 3^x} = number that loops back on itself.
\beta(v) depends on where the 1s lie amongst the 0s in v. It’s a nasty function, but if you master it, you’ll be able to do all kinds of Collatz stuff.
Let p_i be the (zero-based) position of the ith 1.
\beta(v) = \sum_{i=0}^{x-1} 2^{p_i} 3^{x-i-1}
That is, \beta(v) is a sum of products of the form 2^a 3^b, where the a exponents increase as the b exponents decrease.
Some examples:
\beta(11100) = 19
\beta(11010) = 23
\beta(11011010) = 319
If \beta(v) is a multiple of 2^k - 3^x, then m is an integer, and is a member of a Collatz counterexample cycle. (The reason no one has found a Collatz counterexample in real life is that m has always turned out to be a fraction, not an integer.)
That’s it for the preliminaries.
Now suppose we receive a claim of 2^k - 3^x = 5, where 5 < x/2.
We create a Collatz counterexample cycle like this:
If x is even, v = 1^{x} 0^{k-x}.
Otherwise, v = 1^{x-2} 0 1 0 0 0 1 0^{k-x-4}
It can be verified that in all cases, \beta(v) is a multiple of 5. For example, if k=13, x=8, then \beta(1111111100000) = 6305.
(Notice that the legit claim 2^5 - 3^3 = 5, never enters the picture here, because n=5 isn’t less than x/2=1.5.)
We could proceed like this, ruling out claims with n=5, n=7, n=11, and so on, but every v construction would be bespoke. We want a general construction that works no matter what 2^k - 3^x = n claim we are handed.
Empirically, we observe that over all (k,x)-parity sequences, about 1/n of them have \beta(v) divisible by n. For example, 60/210 of the (k=10, x=6) sequences have \beta(v) divisible by 5, and the stats seem to approach 1/n as parity sequences get longer.
But we do math, not physics, so we need an ironclad proof, not a so-called law based on empirical observations.
A couple of quick points:
-
Notice that n must odd, because it’s the difference between an even number and an odd number. It must also be throdd. So it’s coprime with 6.
-
We only have to deal with claims where k = \lceil x \log_2 3 \rceil. If k is larger than that, then having shown 2^{\lceil x \log_2 3 \rceil} - 3^x > x/2 suffices to show 2^k - 3^x > x/2, so refuting claims with this special k is enough for Proposition 6.
Now create parity sequence w from the k and x in the claim:
w = (10)^{k-x} 1^{2x-k}
\beta(w) may very well be a multiple of n, in which case we’re done! It probably isn’t, though.
But it turns out some modification of w (call it v) is guaranteed to have a \beta(v) that’s a multiple of n.
Each of the 10 substrings is a “swap opportunity”, where we can flip the 10 to 01. There are at least x/2 opportunities:
k-x > \lceil x \log_2 3 - x \rceil \approx 0.58x > x/2.
Each swap changes the value of \beta(w). Removing the 1, we subtract some 2^i 3^j from \beta(w), and putting it back in (one position over), we add 2^{i+1} 3^j. The other 1s make their same contributions undisturbed. Therefore, a swap changes \beta(w) by \delta = 3^j (2^{i+1} - 2^i) = 2^i 3^j.
Our goal is to execute a subset of swaps that will render \beta(v) \equiv 0 \mod n. The sum of the \delta values of those swaps just needs to be congruent to -\beta(w).
If the x/2 swap \delta values covered the range of residues (mod n), from 0 to n-1, we’d be golden. Just pick the single swap that “kills” \beta(w).
Unfortunately, we don’t see this kind of diversity. For all we know, all the \delta values are congruent to each other, so maybe none of them individually offset \beta(w).
Enter the key point:
Each \delta is coprime to n, because n is odd and throdd (no factors of 2 or 3), while \delta only has factors of 2 and 3.
Now imagine if we could execute a swap on the first 10 … but multiple times. (We can’t, but bear with me.) Eventually, because of the co-primeness, we’d change \beta(w) by a \cdot \delta \equiv -\beta(w) mod n, so that \beta(v) \equiv 0 mod n.
Now consider swapping the first 10 multiple times, plus swapping the second 10 multiple times. We’d get b \cdot \delta_1 + c \cdot \delta_2. Even if the \delta values were the same, our b and c would each be smaller than a.
Finally, considering swapping the first n instances of 10. We now only have to swap each one at most one time (so: “swap” or “not swap”) to obtain a sum of \delta values that “kill” \beta(w).
That’s the crux of it. Imagine the nightmare case where all n \delta values are congruent to each other mod n. Then there’s still some subset of them whose \delta values offset \beta(w), because \delta is coprime to n. It would just like swapping a single 10 multiple times.
I don’t know what the name of this theorem is, but I convinced myself it must be true: Given a list of n numbers coprime to n, then for any residue r (such as 0), there’s some subset whose sum is congruent to r (mod n).
I can post a working example if useful, e.g., produce a Collatz loop for the claim 2^{65}-3^{41}=19. If the claim is true, then here’s an integer m that loops back to itself after Collatz operations given by parity vector v … a Collatz counterexample loop. A putative proof of the Collatz conjecture would say “Hey, no such loop exists,” automatically falsifying the claim (which, by the way, is false!), and all other claims like it. So as a side effect, that Collatz proof would establish Proposition A.
Note: If we want to strengthen Proposition A to something like 2^k - 3^x > 1.4^x, we might try to manufacture a w where the x/2 swaps modify \beta(w) by adding residues 1, 2, 4, 8, 16, \ldots. From those residues (a “binary basis”), it’s easy to see how any \beta(w) mod n (between 0 and n-1) can be killed by some combination of swaps. Then with x/2 swaps, we would actually cover 2^{x/2} \approx 1.4^x residues, instead of just x/2 residues. It seems hard to do exactly that, but maybe something similar to that.
Interested in any comments/corrections, either on the technical part or the philosophical part …
