Elementary proof of no circuits?

[mathkook]

It’s known that no counter-example Collatz cycle can be a circuit, one whose trajectory starts with an odd positive integer m > 1, proceeds (exclusively) through odd numbers, then (exclusively) through even numbers, landing back at m.

The proof uses Alan Baker’s “big gun” that 2^k - 3^x rises exponentially in x. The big gun involves a lot of transcendental math.

Can we make an elementary no-circuit proof without the big gun?

The lowest member of a circuit has the value \cfrac{3^x-2^x}{2^k-3^x}, where k is the length of the circuit, and x is the number of odds. So the question boils down to:

Are there integers k and x for which \cfrac{3^x-2^x}{2^k-3^x} is a positive integer > 1?

When k and x have a common factor > 1, there actually is an elementary proof that “no”.

When k and x are co-prime, people bring out the big gun.

But maybe there’s a divisibility trick, or some kind of restriction?

For example, if 2^k-3^x always had a prime factor not shared by 3^x-2^x, that would do it.

When k and x are co-prime, the only time those two expressions do share a common prime factor p is when it’s a Kershaw prime, defined by:

\{p: \exists y: 2^y \equiv 3^y \equiv 2 \mod{p}\}

For co-prime (k, x), the first time it happens is k=41,x=11,p=331. Namely 2^{41}-3^{11} = 331 \cdot 5 \cdot 1328714851 and 3^{11}-2^{11} = 331 \cdot 23^2.

So we might want to show that 2^k-3^x never equals a product of Kershaw primes, i.e., it always has some other factor that 3^x-2^x doesn’t share.

For example, 2^k - 3^x will always have another factor besides 331, because
331 \equiv 3 \mod{8}, while 2^k - 3^x never has a remainder of 3 mod 8.

The known Kershaw primes are
p = 331, 1210483, 45661129, 107889071, 13220372117, 452802040997, 2381120538437, 5836609770097, 6196278645943, 8322368214791
with their corresponding certificates being
y = 121, 379107, 86668, 30855641, 7850019689, 172800778897,
969305705913, 1574816965408, 783190158058, 12363639911
(credit to youtubers @DLG03, @peepzorz, and @Perryman1138).

Any thoughts?

[mathkook]

Let A be the set of all numbers representable as the product of Kershaw primes.

Let B be the set of all numbers representable as 2^k - 3^x for positive x and k>x.

Are A and B disjoint?

Both sets are presumably infinite, but both are so sparse that we don’t “expect” there to be any overlap, much like we don’t “expect” any 2^n to be adjacent to any 3^m.

But unlike that adjacency question, it seems hard to prove A and B are disjoint, because their definitions don’t seem related.

In other words, maybe A and B are disjoint, but there’s no reason for it … it just happens to be? (This is a paraphrase of Lagarias’ comment about the whole Collatz conjecture.)

But we’re not so easily derailed, right? Just food for thought.

PS. Proving that A and B are disjoint is actually stronger that what we need here. We only need to show that gcd(3^x-2^x,2^{k-x}-1) \neq 2^k-3^x, for all x and k>x. But the stronger thing might be easier to prove.

[stargazer07817]

Cool question. Let’s take a shot at sketching:

First, we’ll define a “circuit.” If we have x odd-type steps (of the form (3n+1)/2, each yielding an odd result) and k total divisions by 2, the starting member m_1 is given by:

m_1 = \frac{3^x - 2^x}{2^k - 3^x}

Hopefully I got that right, because everything that follows will depend on it.

If we let N = 3^x - 2^x (numerator) and D = 2^k - 3^x (denominator), then for m_1 to be an integer greater than 1, we have to satisfy three things:

• 2^k > 3^x (which implies D > 0 and k > x).
• D must exactly divide N.
• D > 1. And we hit our first interesting finding, because if D=1, then k=2, x=1, which leads to m_1 = (3^1-2^1)/1 = 1. This is the trivial cycle, not a counter-example.

Let’s check divisibility:
Assuming m_1 > 1, we have D > 1 and D \mid N.

• Since D \mid N, it follows that D \mid (N+D).
• Calculating the sum: N+D = (3^x - 2^x) + (2^k - 3^x) = 2^k - 2^x.
• So, D \mid (2^k - 2^x). That can be factored as D \mid 2^x(2^{k-x}-1).
• The denominator D = 2^k - 3^x is always an odd number (since 2^k is even and 3^x is odd, for k \ge 2, x \ge 1).
• Because D is odd and D \mid 2^x(2^{k-x}-1), D cannot share any prime factors with 2^x. Enter our old buddy Euclid: D must divide the other factor: D \mid (2^{k-x}-1).

The Sticky Part (An Inequality)
Since D > 1 and D \mid (2^{k-x}-1), and also k-x \ge 1 (so 2^{k-x}-1 \ge 1), it must be that D is less than or equal to 2^{k-x}-1:

2^k - 3^x \le 2^{k-x}-1

Simply rearranging gives:
2^{k-x}(2^x-1)+1 \le 3^x

The Interval for 2^y
Let y = k-x. Since k>x, y is a positive integer (y \ge 1). The inequality becomes 2^y(2^x-1)+1 \le 3^x, which implies 2^y \le \frac{3^x-1}{2^x-1}.

We started with the initial condition 2^k > 3^x (meaning 2^{x+y} > 3^x), we get 2^y > (3/2)^x.
So, we’re looking for an integer y \ge 1 that must satisfy:
\left(\frac{3}{2}\right)^x < 2^y \le \frac{3^x - 1}{2^x - 1}

Now we have to look at the interval itself, because we need to figure out possible integer values of y:

• If x=1: The interval becomes 1.5 < 2^y \le 2. The only integer solution is 2^y=2, so y=1. This implies k-x=1 \Rightarrow k-1=1 \Rightarrow k=2. This is the (k,x)=(2,1) case, which yields D=1 and m_1=1, not an m_1 > 1 cycle.
• If x \ge 2: There’s a well-established “proof” in Collatz cycle analysis that for x \ge 2, the interval \left( (\frac{3}{2})^x, \frac{3^x-1}{2^x-1} \right] contains no integer power of 2. I’m not proving this here (and it should be checked in this context) but this is usually shown by verifying for small values of x directly and then using more advanced arguments for larger x, proving that the first power of 2 greater than (3/2)^x already exceeds (3^x-1)/(2^x-1).

So, the conditions necessary for m_1 to be an integer greater than 1 (i.e. for a non-trivial circuit, as we’ve defined it, to exist) mean:

• For x=1, the only possibility is m_1=1.
• For x \ge 2, an integer y=k-x would have to exist such that 2^y falls into an interval that contains no powers of 2. That’s the sticking point - it seems impossible.

Since both cases appear to lead to a contradiction with the assumption of m_1 > 1 no such Collatz “circuit” can exist with a starting number m_1 > 1?

[mathkook]

Makes total sense! Everything is right.

Now, I guess the advanced arguments you mention are not elementary, involving some version of Baker’s heavy artillery, linear forms in logarithms, etc. … which addresses the possible magnitudes of these expressions rather than their divisibility properties. Another heavy artillery proof uses Ellison’s theorem that 2^k-3^x > 2.56^x for x > 27.

You can say a lot about divisibility of things like 2^y - 1. Such as, if y is prime, then 2^y -1 is congruent to 1 (mod y), and amazingly, so are each of its prime factors. Likewise for 3^x - 2^x.

But there’s nothing obvious to say about 2^k - 3^x (say, when k and x are co-prime). The values seem all over the place, and that seems like the hard part.

[cosmo]

I love this question!

Olivier Rozier has a simpler proof than Steiner’s, but it is only in French as far I know: https://www.probleme-syracuse.fr/cargo/Singularit�_1_3.pdf.

I actually have been looking for a proof using the tiles

For fun, here is the tiling for x = 17, k = x + (x-3), gcd(x,k) = 1:

As generated by coreli:

import coreli
x = 17
k = x + (x-3)
pv = coreli.ParityVector([1]*x+[0]*(k-x))
tiling = pv.to_tiling()
tiling.all_steps()
tiling.draw_svg()

It is easy/known that the x odd terms will yield ternary number 2...2 x times, (i.e. 3^x - 1). Then, successive columns give (3^x - 1)/ 2^i in the multiplicative group of \mathbb{Z}/3^x\mathbb{Z}, with 0 \leq i < k-x , which starts enumerating all the members of that group in a weird order. However, discrete logarithm is not hard in that group (i.e. there is a fast algo) hence, the order is not too weird (see Remark 1.75), i.e. it is not too hard (in terms of computational complexity) to predict the ternary expansion of the last column, (3^x - 1)/ 2^{k-x-1}.

But then chaos seem to fully take over; for fun, here are 4 repetitions of this parity vector concatenated to get a (small) idea of the cyclic solution:

[mathkook]

Fantastic! These visualizations are unbelievable.

And great – it’s a high bar to try making a no-circuit proof without transcendental math, though it seems possible. I feel it would open up new avenues.

As a run-up, it might also be interesting to attack the high cycle (whose parity sequence spreads the 1s as evenly as possible throughout the 0s, unlike the circuit, which pushes all the 1s to the beginning). A no-high-cycle proof can be done without the deep stuff.

For general cycles, the situation might be different. Terence Tao’s 2011 blog post informally sketches a proof saying that transcendental math is actually required: “… any proposed proof of the Collatz conjecture must either use transcendence theory, or introduce new techniques that are powerful enough to create exponential separation between powers of 2 and powers of 3,” which is some food for thought.

[cosmo]

Unless I’m Collatz-hallucinating (OK, I think it was an hallucination), I believe I have found an extremely simple proof of no circuits using the tiles.

I just found the proof and writing it well is a small bit of work, but here is examplified for the case of 4 even terms and 5 odd terms.

In case of a positive integer cycle with circuit parity vector 0^4 1^5, you would see the following pattern at some point in the assembly (anything north and west to it is 0s for ever):

(Magenta points identify points that are the same because of cycle)

Now, consider the following tile lemma:

The lemma says that in the situation on top, out of the two only possibilities (tile 0 and 1), we are forced to choose tile 0 for the green position if we want to avoid a future black hole (position where no tile can fit). Note that this happens because tile 2 is the only one with (1,0) north-west corner.

Hence, avoiding the black hole (justification at the end), we deduce that:

And… nothing ahah, sorry for hallucinating (I was wrong in my first lemma, off by one tile, which destructed the argument).

EDIT:

Well, in that case you actually get two partial reconstructions, both with very early black holes (lacking an argument as of why the blacl hole on the right would not be Collatz feasible).

I need to see if this generalisable.

[mathkook]

You definitely would have more odds than evens in a positive, non-trivial circuit.

k = length of circuit
x = number of odds in circuit
k-x = number of evens in circuit

If the bottom member of the circuit is greater than 1, then

\cfrac{3^x - 2^x}{2^k - 3^x} > 1

3^x - 2^x > 2^k - 3^x

2 \cdot 3^x > 2^k - 2^x

2 \cdot 3^x > 2^x(2^{k-x}-1)

2 \cdot \frac{3}{2}^x > 2^{k-x}-1

x > 0.631 k - 1.27

x > 0.6 k (… for all k \geq 41)

Interested to look at the rest

[cosmo]

Cool thank you for the proof of that result which I always took for granted without knowing the reason for it being true

I’m not 100% sure that the tiling argument actually depends on it but I had the intuitive feeling that I used it.

I’m really excited because I’ve been searching for ages a nontrivial result for which the tiles would give a simple proof.

Next step: I want to formalise the proof in Rocq to increase consensus. Unless my proof is wrong, of course (which I should discover on the way to formalising it).

[cosmo]

Ok… I hallucinated… Sorry

[mathkook]

Been there so many times!

[mathkook]

Since the bottom member of a k length circuit with x odds is

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

An elementary Collatz no-circuit proof has to show (either directly, or as a side-benefit) that there are no positive integer solutions to the equation

3^x-2^x = m(2^k-3^x)

which would of course be of interest to mathematicians, who know of no such elementary proof.

[cosmo]

Thank you for this nice motivating reformulation!

[cosmo]

Ok, I think I have an elementary proof of no circuits using the fact that for all iterate x in a positive integer cycle with k odd terms we have x < 3^k (see this thread), for which we do not have an elementary proof (yet).

Notations:

• k: number of odd terms
• l: number of even terms
• n = k+l

We know that to get a positive integer cycle, you need both:

• Bound 1. 2^n > 3^k
• Bound 2. k > l

Both bounds have elementary proofs.

Now consider, the circuit 0^l 1^k, using the result I mentioned at the top, we know that the first/last iterate of the circuit in this rotation is exactly 3^k - 1 (and not just congruent to 3^k - 1 modulo 3^k).

Now, because of rotation 1^k 0^l you know that this is asking 3^k - 1 to end with l bits 0 in base 2. Now, look at the first k such that 3^k-1 ends with l bits 0 in base 2:

l	First k such that 3^k - 1 ends with l bits 0 in base 2
1	1
2	None
3	2
4	4
5	8
6	16
7	32
8	64

^ you can reproduce the above using your favorite programming language, here’s my Python code.

This is no coincidence, excluding l \in \{1,2\}, we get k = 2^{l-2}, and I believe it can be proved without too much effort using what is known about the multiplicative group of \mathbb{Z}/2^l\mathbb{Z} because we are basically asking for the multiplicative order of 3 in multiplicative group \mathbb{Z}/2^l\mathbb{Z}, i.e. smallest k > 0 such that 3^k = 1 \text{ mod } 2^l. I’m waiting on my number theorist friend to give me the proof, but meanwhile, ChatGPT’s proof of this 2^{l-2} lemma seems correct/promising.

The nice thing is that it requires k to be way too big, i.e. way too many odd numbers in the circuit!!

Indeed, you need to satisfy Bound 1, i.e. 2^n > 3^k, which becomes at least:

2^{2^{l-2} + l} > 3^{2^{l-2}}

And, according to Wolfram Alpha, this is possible only for l \in \{1,2,3,4,5\} which for us becomes l \in \{1,3,4,5\}. (ChatGPT reasoning on this does not seem bad).

This only gives a finite number of (k,l) couples to check given our two bounds (see above).

QED

[cosmo]

I’d be interested in any questions or thoughts about this argument, don’t hesitate to shoot especially if there is something you don’t understand in my argument

Also let me know if your main source of unsatisfaction is that I did not prove the k = 2^{l-2} result and only used empirical evidence. In that case, I’ll ask my number theorist friend for a proof.

If correct, I like the argument because it focuses the hardness on what seems to be a more fundamental result about general Collatz cycle bounds, instead of being specific to circuits.

[mathkook]

For myself, looking forward to studying it. It’s a great idea to flesh out any unproven parts. In the proofs and sketches by Steiner, Rozier, me, and @stargazer07817 , there always comes a step where some non-elementary result gets invoked (“Baker”, “Rhin”, “linear forms in logarithms”, etc). Versus a proof that could have been written in, say, 1960 (pre-Baker).

[cosmo]

Please note that, in the first sentence, I invoke the x < 3^k result which relies on x < 2^n, for which we need Baker/Rhin etc…

The above proof of no circuits relies on that result to say that parity vector 0^l 1^k ends in exactly 3^k - 1 and not just in some number congruent to it modulo 3^k.

The point of the proof is only to rely on this more general bound rather than developing a complex argument specific to circuits.

[mathkook]

Ah ok, I also got my variables confounded. Thanks, thanks

[cosmo]

Yeah, I’m sorry!! I know that you use x and k in a different way, unfortunately my brain has been wired for years with the notations I used above…

I hope it won’t be too much of a bother to read!

Also, I edited and fleshed out a bit the k = 2^{l-2} argument.

[mathkook]

great – it’s no problem – i agree with you that it is to error prone to try converting a whole argument even if you want to