Proving no cycles is "Baker-hard"

General
1

Tao’s Proposition 6 roughly says:

“If there are no Collatz cycles, then for all k and x, we have 2^k - 3^x > x (for sufficiently large x).”

That is, 2^k can never get super-close to 3^x.

That means a no-cycle proof would imply, as a side benefit, a non-trivial separation result that was historically very hard to prove (as in Fields Medal hard), requiring lots of transcendental math. Another way to say this: “If 2^k did ever get super-close to 3^x, you could manufacture a Collatz cycle.”

Tao’s observation is a kind of converse of Collatz no-circuit proofs, which roughly say:

“Given the separation of 2^k from 3^x that Baker (and Ellison, and Rhin) historically managed to prove, we can conclude that there are no Collatz circuits.”

Note that the Baker/Ellison/Rhin results are much stronger than 2^k - 3^x > x, more like 2^k - 3^x > \frac{3^x}{x^{13}}. But Tao knows of no way to show even the weaker result without heavy artillery.

Summary: Tao is saying proving no cycles is “Baker-hard.”

Unfortunately, I can’t understand (and thus can’t re-explain) the proof of Proposition 6. I feel like I should be able to understand an argument that manufactures a Collatz cycle out of a putative “near collision” of some sufficiently large 2^k and 3^x. Given that the bottom member of a cycle has the form \cfrac{\Sigma 2^i 3^j ...}{2^k - 3^x}, a near collision makes it more likely that this is an integer for some parity sequence of length k with x odds … but given the random-looking numerators, I don’t quite see how it’s a necessity.

1 Like
2

Follow up:

Tao doesn’t say that proving no circuits (vs no cycles) is Baker-hard.

In other words, “no circuits” doesn’t imply “separation of 2^k and 3^x”.

In other other words, if a 2^k ever putatively got super-close to a 3^x, there’s no method for constructing a non-trivial circuit from that putative near-collision.

(That said, to date, all no-circuit proofs invoke Baker’s heavy artillery.)

3

Here’s why I’m interested in “Is the Collatz Conjecture Baker-Hard?”

Tao is basically saying that there’s no way to solve the Collatz Conjecture without creating (or using) Fields-Medal-type math.

In other words, if you were transported to the early 1960s, your resolution of the Collatz Conjecture would incidentally garner you a Fields Medal for establishing that the powers of 2 and 3 grow apart at an exponential rate.

In other words, a math kook isn’t going to solve the Collatz Conjecture without re-developing some very advanced mathematics (or at least knowing about it, and exploiting it).

That’s should be very sobering for a math kook!

At first I thought this was just a feeling that Tao expressed in his blog, but he seems to be saying it’s a provable fact rather than a feeling.

Something akin to, “Don’t work on a polynomial algorithm for solving the Traveling Salesperson problem optimally, because it’s NP-complete. Unless you’re prepared to solve P vs NP (as a side effect!), don’t work on that.”

We used to call a lot of problems “AI hard”. I worked on one of them for many years. Machine translation was called “AI hard” because you could always make up a translation problem that the machine would get wrong unless it knew a particular fact about the world. That didn’t bother us, because we were trying to solve it at 90% (like building a useful, suboptimal Traveling Salesperson algorithm). But what do you know, folks first demonstrated the power of neural sequence modeling on machine translation, then used those techniques to build ChatGPT.

Ok, long preamble to the next post, trying to make technical sense of Tao’s assertion.

1 Like
4

Tao’s idea, as I understand it, is that if someone comes along with an exception to Baker’s separation of 2^k from 3^x, then we can use it to generate a non-trivial Collatz cycle (counter-example to the conjecture).

I’m going to start with a simple case.

Suppose you say:

I have a (k, x) pair such that 2^k - 3^x = 5.

We know from Hershfeld 1936 that this never happens for k>5 (nothing like 32-27=5 is ever seen again).

So if k>5, I know you’re lying.

But suppose I wasn’t aware of Hershfeld or Baker. Instead of calling you a liar, I tell you, “Wow, if that’s true, you’ve disproved the Collatz Conjecture!” which I demonstrate by showing that your 2^k - 3^x = 5 implies the existence of a non-trivial Collatz cycle. You don’t even have to reveal your k and x.

If 2^k -3^x=5, then certainly it’s divisible by 5.

2^k \mod 5 cycles through 2, 4, 3, 1.
3^x \mod 5 cycles through 3, 4, 2, 1.

So, if 5 divides 2^k - 3^x, one of these must be true:

(a) k = 1 \mod 4, and x = 3 \mod 4
(b) k = 2 \mod 4, and x = 2 \mod 4
(c) k = 3 \mod 4, and x = 1 \mod 4
(d) k = 0 \mod 4, and x = 0 \mod 4

We can handle each case in turn.

Starting with (d), let x=4a, k=4b. Then the simple circuit

1^x 0^{k-x}

must be a Collatz cycle, because the bottom member of the circuit

\cfrac{3^{4a}-2^{4a}}{2^k-3^x}

is an integer, because the numerator is a multiple of 5

(via 3^{4a}-2^{4a} = 81^a - 16^a \equiv 1^a - 1^b \equiv 0 \mod 5),

and the denominator is (putatively) 5.

(True but not shown here: the next element of the circuit is also supposedly an integer.)

For case (b), the circuit is also a Collatz cycle.

When x is odd (cases (a) and (c)), the circuit doesn’t work, because 3^x - 2^x isn’t a multiple of 5.

But from (k, x) we can instead construct the parity vector of a Collatz cycle like this:

101 (110)^i \{0001, 001, 01, or 1\} 0^*

We choose i to make x 1s, and we pad with 0* so the total length reaches k. We choose among the “or” alternatives according to i \mod 4.

It took some work, but \ldots the first member of the cycle induced by any such parity vector always has a numerator that’s a multiple of 5.

For example, if k=65, x=39, we have the parity vector

101 (110)^{18} 01 000000

and the first member of the corresponding cycle is

\cfrac{19,289,846,131,800,740,725}{2^k - 3^x}

(Of course, 2^{65}-3^{39} \neq 5. Once we see a particular k and x, we can easily spot the lie.)

So \ldots that’s a tiny case of Tao’s idea that a “near collision” between 2^k and 3^x can be used to construct a Collatz cycle.

At least I feel I get the idea, though it’s still a far cry from covering any putative case of 2^k-3^x < 2.56^x or even just 2^k - 3^x < x.

5

I believe that Tao’s assertion about Collatz being Baker hard is invalid. There is a proof by induction of the Collatz conjecture (a much simpler operation), but I am not a qualified mathematician. I do math as a recreational activity and found a simple proof that proves the Collatz conjecture by showing continuity and completeness of a tree built using Collatz’s two rules. This proof makes no mention of Baker or proposition B. The proof runs to ten theorems and about ten pages. I have also found many hidden structures in the Collatz tree but they are not required for the poof. As this proof is so simple, there must be some element of it that is invalid. How could so many people not have seen such an obvious solution. I can only conclude that there is an error in my proof, but I can’t see it.