I’m actually unsure how nontrivial his argument is (like, does it rely on some heavy artillery indirectly?), but I always wondered if there was an elementary proof.
(Also, assuming this result, I think I have an elementary tile-based proof that the elements of the cycle are also < 3^k, with k the number of odd terms, I will add it to this thread at some point in the future. Note that this answer claims to have both results, and that I’m not claiming that deducing < 3^k once you know < 2^n is hard).
@cosmo thank you for posting these results … they are new to me and probably many others!
Anything with a 13.3 in the proof almost surely uses heavy artillery
Collatz proofs often rely on the exponentially-growing separation between 2^k and 3^x.
There are three that I know about:
Baker’s groundbreaking result was that 2^k - 3^x > 3^x \cfrac{a}{b^{k-1}}, for effective constants a and b that he didn’t supply.
Rhin’s result was that 2^k - 3^x > \cfrac{0.00220823 3^x}{x^{13.3}}. There’s where any 13.3 probably comes from.
Ellison’s result was that 2^k - 3^x > 2.56^x for x > 17.
Ellison’s result is handy for simple jobs, though Rhin’s is better when you need something closer to 3^x. They cross at x=571.
Math kook doesn’t enjoy heavy artillery because he doesn’t understand it. But surely that’s a bad attitude. As von Neumann told a guy who asked a question at a lecture, “Young man, in mathematics you don’t understand things. You just get used to them.”
Thank you for this summary of results that I also… don’t understand (and have tried to avoid because of it, although they seem to give the strongest results we know).
Let me sketch a proof that in a cycle with n terms and k odd terms, all elements are < 3^k. I will rely on the result that all elements are < 2^n. My proof uses the tiles but I think you could easily get it without too.
The result mean that you can always write α within the space of the parity sequence i.e. we’re always in the case below:
The fact that you read T^n(alpha) in ternary on the red line is an instance of Corollary 1.36 in my thesis, illustrated in Figure 1.16.
From there, just rotate the parity vector, this operation preserves k and you will read all the successive iterates of the cycle in ternary on the red vertical line, on k ternary digits, meaning that all elements are < 3^k.
@mathkook or @oros would you have a specific reference for Ellison’s result?
Here the references I have for Baker and Rhin:
@article{Baker1966,
author = {Baker, A.},
title = {Linear forms in the logarithms of algebraic numbers},
journal = {Mathematika},
volume = {13},
number = {2},
pages = {204-216},
doi = {https://doi.org/10.1112/S0025579300003971},
url = {https://londmathsoc.onlinelibrary.wiley.com/doi/abs/10.1112/S0025579300003971},
eprint = {https://londmathsoc.onlinelibrary.wiley.com/doi/pdf/10.1112/S0025579300003971},
year = {1966}
}
@article{Rhin1976,
author = {Georges Rhin},
title = {Minorations de formes linéaires de logarithmes et applications},
journal = {Acta Arithmetica},
volume = {30},
year = {1976},
pages = {325--346},
language = {French},
publisher = {Institute of Mathematics of the Polish Academy of Sciences}
}
My pleasure! That reminds me about maybe making a post about converting between the approximation-of-log-3 (as baker and rhin give) to the difference-between-powers-of-2-and-3 (that we sometimes need)
Someone asked a question on Math exchange yesterday, and I showed in my reply that the smallest element (a_0 ) of a cycle has the property that a_0<(\frac{3}{2})^k (translated to your notation of k and n which are inverted here ,see https://math.stackexchange.com/questions/5085433/explicit-baker-constants-for-collatz-cycle-constraints/5085630#5085630)
This would place the largest element at a_{max}<(\frac{9}{4})^k. If we start using tighter bounds (like for the 2.56^k bound) in the logic, we could even have something like a_0<(\frac{3}{2.5})^k or a_{max}<(\frac{9}{5})^k which would place all elements of the cycle a_i<2^k<3^k<2^n
If you push a little more, you can start with this mathexchange sandbox post showing that \frac{2^n}{3^k}<1+\frac{k}{3a_0} written as \frac{k}{3a_0}>\frac{2^n}{3^k}-1 and, using x-1>\log x, you also have \frac{2^n}{3^k}-1>|n \log 2-k \log 3|>\frac{1}{n^{13.3}} which end up with a_0<\frac{k}{3}n^{13.3}
Now with a_{max}<(a_0+1) (\frac{3}{2})^k (only for 1-cycles which we know do not exists), this puts all elements of a cycle a_i<(\frac{3+\epsilon}{2})^k with \epsilon very small for high n (n is no less than millions in potential cycles).
Note: For these large n, Rhin had even a tighter bound: |n \log 2-k \log 3|>\frac{1}{n^{7.616}} and I think the reality go down as low as one over n square
We know that the maximal element of a circuit with n elements and k odds is 2^{n-k}\frac{3^k-2^k}{2^n-3^k}.
We know that it is also bigger than any element of any non-negative Collatz cycle with n elements and k odds (@mathkook could you confirm this is true and that the proof is simple? Ideally do you have the proof and/or a ref?)
@cosmo For sure, the highest member of the (n,k)-circuit is higher than any member of any other (n,k)-circuit. Every member m of every rational cycle has an (n,k)-parity vector w that returns m to itself. Likewise, every (n,k)-parity vector w corresponds to some cycle member m, which can be computed as m=\beta(w)/(2^n-3^k). The highest member of the circuit has parity vector v=000...111, which maximizes \beta(v) among all such vectors. I realize this suppresses the details of the reviled \beta formula, but for sure the proof is simple and elementary!
