Known proofs of this result rely on results like Baker’s which is far from being elementary.
An elementary proof of that result would give:
Elementary proof of x < 2^n in a cycle of size n : this is because 2^{n-k} \frac{3^k - 2^k}{2^n - 3^k} is the biggest element of a circuit of size n with k odd integers, which is known to be bigger than the element of any Collatz cycle of size n with k odd integers (@mathkook please correct me if I’m wrong, or if I’m wrong to assume that the proof of this fact is elementary)
In turns, it would give an elementary proof that there are no Collatz cicruits, see this argument
It would be very frustrating to think that there is no elementary proof of this fact because the 2^n bound is not tight at all:
For n=19, we have 2^{19} = 524288 and the following values for \frac{3^k - 2^k}{2^n - 3^k} when 2^n > 3^k:
def f(n,k):
return 2**(n-k) * ((3**k-2**k)/(2**n - 3**k))
for n in range(51):
max_ratio = 0
for k in range(n):
if 2**n <= 3**k:
continue
ratio = f(n,k)/f(n,k+1)
max_ratio = max(max_ratio, ratio)
print(f"n={n}", max_ratio)
Proving this fact (or at least that the ratio is < 2/3) would be enough to get the result.
but Python code was correct and what followed as well, i.e. we have:
f(n,k)/f(n,k+1) < \frac{2}{3}
But it gives only a lowerbound instead of an upperbound on the inverse: i.e. f(n,k+1)/f(n,k) > \frac{3}{2} which is interesting but not super useful, we really need an upperbound to get our result.
Interestingly, in experiments, it is only extremal values of k that are problematic:
You can see that the ratio behaves like 3/2 = 1.5 in the middle but is disturbed for high values of k. But the damage always seems to be contained at the very end (approx 7 or 8 values of k before cutoff), see this example for n=200, I also tried for n=1000 with similar result.
I think it is worth reporting that proving 2^n > 2^{n-k} \frac{3^k - 2^k}{2^n - 3^k} when 2^n > 3^k is implied by the following easier looking inequalities (always assuming 2^n > 3^k):
6^k + 3^k < 2^{n+k} for n \geq 3
6^k + 3^k < 2^{n+k} + 2^k for n \geq 0
2^{n-k} + 3^k < 2^n for n \geq 3 and k \geq 1
2^n \geq 3^k + 2^k for n \geq 9 (implies the second inequality)
2^{n-k} \geq k+2 for n \geq 6
Reason for the last inequality
- Write 3^k via binomial expansion: 3^k = (2 + 1)^k = Σ_{j=0}^k C(k,j) 2^j.
- Then 3^k + 2^k = Σ_{j=0}^{k-1} C(k,j) 2^j + 2·2^k ≤ (k + 2)·2^k, since each C(k,j) ≤ 2^k and there are k terms plus the top 2·2^k.
- So it suffices to show: 2^{n−k} ≥ k + 2.
The following code tests them in Python:
# 6^k + 3^k < 2^{n+k}; n >= 3; 2^n > 3^k
for n in range(3,200):
for k in range(n):
if 2**n <= 3**k:
continue
lhs = 6**k + 3**k
rhs = 2**(n+k)
if not lhs < rhs:
print("oups", n, k)
# 6^k + 3^k < 2^{n+k} + 2^k; n >= 0; 2^n > 3^k
for n in range(0,200):
for k in range(n):
if 2**n <= 3**k:
continue
lhs = 6**k + 3**k
rhs = 2**(n+k)+2**k
if not lhs < rhs:
print("oups", n, k)
# 2^(n-k) + 3^k < 2^n; n >= 3; k >= 1; 2^n > 3^k
for n in range(3,200):
for k in range(1,n):
if 2**n <= 3**k:
continue
lhs = 2**(n-k) + 3**k
rhs = 2**n
if not lhs < rhs:
print("oups", n, k)
Newly released GPT 5 has interesting stuff to say about the first inequality, but not a correct, elementary proof yet. In particular it convinced me that the only hard case of 6^k + 3^k < 2^{n+k} is the case n = \text{ceil}(k\log_2(3)) because otherwise we have 2^{n+k} - 6^k > 6^k > 3^k.
EDIT: GPT-5 knows about Baker and proved the first inequality by using Baker’s result, which we’re trying to avoid (note that I did not tell GPT 5 about Baker but just pointed out at the mistake in its previous proof linked above).
Note that we have 2^{n-k} > (\frac{3}{2})^k by 2^n > 3^k and that because 2^{n-k} is integer we have 2^{n-k} \geq \lceil (\frac{3}{2})^k \rceil. Hence it is enough to prove: \lceil (\frac{3}{2})^k \rceil\geq (\frac{3}{4})^k + (\frac{3}{2})^k, as stated above, which experimentally holds for k\geq 2, which gives the n\geq 3 bound in the initial inequality.
Hi Cosmo, I tried to prove your thesis. I don’t have a degree in mathematics, I’m just a hobbyist from Italy. I hope I haven’t made any mistakes. I’ll upload the JPG files from my PDF created in LaTeX (sorry, the upload reversed the pages).
Yes, I agree. If the falsity of that inequality could be demonstrated in a simple way (by induction?), we would have solved the problem. I also thought it was interesting to point out the connection with Bernoulli’s inequality. I’ll keep trying.
but the goal is to find a proof that does not rely on this super hard stuff!!