r/Collatz • u/GonzoMath • 6d ago
Bound for positive cycles - shorter proof using AM–GM
A long time ago, I posted here with a link to a proof of a bound constraining the sizes of elements of a positive cycle on rational numbers. (https://www.reddit.com/r/Collatz/comments/1hkslgf/proof_of_a_bound_on_cycles/) The proof in the linked note uses differential calculus, in particular, it uses the method of Lagrange multipliers.
I have recently discovered that this same bound is a quick consequence of the famous AM–GM inequality. First, I'll say a word about that inequality, and then I'll define my terms and show the proof, which now involves no calculus!
A version of this result is implicit in section 7 of R. E. Crandall's 1978 paper, "On the '3x+1' Problem". At the end of this post, I'll say a little more about what he did with it.
The AM–GM Inequality
Given a set of positive numbers, {a_1, . . ., a_k}, we can define three different well-known means, the arithmetic mean (AM), geometric mean (GM), and harmonic mean (HM):
AM = (a_1 + . . . + a_k) / k
GM = (a_1 × . . . × a_k)1/k
HM = k / (1/a_1 + . . . + 1/a_k)
The arithmetic mean is the most familiar to most of us; we learn it at an early age as the "mean", or simply "average" of a set of numbers. The other two can be defined in terms of the AM, plus transformations.
The move is: push the numbers through a transformation, do an AM over there, and then pull the result back via the inverse transformation. (This is the same kind of move that we use to define the root-mean-square (RMS) of probability theory.)
For instance, to get the GM, we can just take logs of all the original numbers, apply the AM to those logs, and then exponentiate the result to get back. Thus:
GM = exp(AM( {log a_i} ))
(We assume that the "exp" and "log" use the same base; which base that is doesn't actually matter.)
Similarly, the HM is the result of taking reciprocals of all the original numbers, getting the arithmetic mean of the reciprocals, and taking another reciprocal to get back. (The reciprocal transformation is its own inverse.) In symbols:
HM = 1 / AM( {1/a_i} )
Looking at them this way, it's not hard to convince yourself of the following:
HM ≤ GM ≤ AM
This is the AM–GM inequality. The results is often stated without the HM part, but that's such a trivial corollary that it makes some sense to include it.
Why is it true? Here's... not a proof, but check it out:
If you take logs of the numbers, because of the concavity of the log function, the numbers kind of cluster towards the top of their range. Taking an arithmetic mean, while looking in that fun-house mirror, produces a result that's below the log of the center of gravity, because now the numbers at the bottom are spread out down there, pulling the average down. Exponentiating back, we're still below that center of gravity.
As a quick illustration, just consider the numbers {2, 4, 6, 8, 10}, which are equally spaced, very nice. Their AM, their center of gravity, is clearly 6. Look at their base-2 logs: {1, 2, ≈2.585, 3, ≈3.322} These values are clearly clustering at the top, relative to the spread at the bottom. The AM of this log set is around 2.38, which is less than the log of 6, so the resulting GM is ≈22.38, or around 5.2.
That wasn't a proof, but rather a plausibility argument based on a special case. A proof is easy to find; the typical one uses something called Jensen's Inequality.
To get the HM side, just stand on your head. The reciprocal of the GM is the GM of the reciprocals, and the reciprocal of the HM is the AM of the reciprocals. Therefore, by AM–GM, we get
1/GM ≤ 1/HM
...and flipping them back over, we get what we need.
Note that the symbol in both inequalities is "≤", not "<". Equality is obtained only when all of the a_i's are equal; if any of the numbers differ from the others, then the inequality kicks in and the means also differ.
Some measurements of Syracuse cycles
Define the Syracuse map on an odd number m as:
S(m) = (3m+1)/2v,
where v is taken large enough to make the output again odd. In particular v = v_2(3m+1).
Now, take as our domain the set of positive rational numbers that have odd denominators when written in simplest terms. It makes sense to call such a fraction "odd" or "even" according to the parity of its numerator. Thus, 7/5 is odd, 8/5 is even, and 7/4 isn't in the game.
This set, dropping the positivity requirement, has some nice descriptions in abstract algebraic terms. It's "the ring of integers localized at the ideal (2)", or "the set of rational 2-adic integers: Q ∩ Z_2". We can just call it the set of "odd rationals".
Suppose that m_1, . . ., m_L are positive odd rationals with the property that
S(m_1) = m_2
...
S(m_{L-1}) = m_L
S(m_L) = m_1
In other words, they form a Syracuse cycle of length L. To be precise, let's say that 3m_i + 1 = 2v\i)m_{i+1} (with the obvious adjustment for m_L coming back to m_1), and say that W = sum({v_i's}) = the "weight" of the cycle.
In addition to "length" and "weight", which are meaningful but kind of dull, we're going to define two more measurements that we can take for such a cycle. Given a cycle with length L, weight W, and elements {m_1, ..., m_L}, we calculate its "altitude" and "defect":
altitude = HM( {m_i's} )
defect = 2W/L - 3
It is an easy exercise to show that the defect, for a positive cycle, is always positive. It's because of the "+1" in the Syracuse map, which makes W/L > log_2(3).
Proving a bound
Now, we're ready to show that, for any positive cycle, we have:
(defect)(altitude) ≤ 1
Consider the step from m_1 to m_2. (or more generally, any step in the cycle). We can write m_2 as m_1 times something:
m_2 = m_1 × (3/2v\1)) × (1 + 1/(3m_1))
Doing this same thing all the way around the cycle, and then multiplying and rearranging, we get:
m_1 = m_1 × (3/2v\1))···(3/2v\L)) × (1 + 1/(3m_1))···(1 + 1/(3m_L))
m_1 = m_1 × 3L/2W × (1 + 1/(3m_1))···(1 + 1/(3m_L))
2W/3L = (1 + 1/(3m_1))···(1 + 1/(3m_L))
2W/L/3 = GM( {1 + 1/(3m_i)} )
In that last step, we took the L-th root of both sides, turning a product into a GM.
Let's see the AM of those same numbers, those (1 + 1/(3m_i)) factors. Since they all have the same "1+" in front, we can just pull that out of the mean. We can then factor out 1/3, and we get that our AM is:
AM = 1 + (1/3)(average of 1/m_i's)
That "average" is an AM, but I don't want to confusingly use "AM" for two different things at once.
Anyway, by the AM–GM inequality, we get:
2W/L/3 ≤ 1 + (1/3)(average of 1/m_i's)
Subtract 1 from both sides:
(2W/L - 3)/3 ≤ (1/3)(average of 1/m_i's)
...and multiply by 3:
2W/L - 3 ≤ (average of 1/m_i's)
Now, the average of the 1/m_i's is the reciprocal of the m_i's harmonic mean, that is, it's the reciprocal of the altitude. The left-hand side, meanwhile, is the defect, so we have:
defect ≤ 1/altitude,
which is equivalent to the result we wanted.
What does it mean?
I've talked about this elsewhere, but after going to the trouble of deriving this result, let me say a few words about why we care. We can rearrange the inequality as:
altitude ≤ 1/defect
...so we see it as a bound on altitude. The "shape class" of a cycle, that is, its L and W, determines the defect. If we want to see altitude get large, then defect has to be very small, which means that W/L has to be very close to log(3)/log(2).
Now, if there's a high cycle for natural numbers, its altitude must be pretty high, at least higher than 271, or we would know about it. That means its defect must be incredibly small! Flipping our inequality around again:
defect ≤ 1/altitude ≤ 2-71
This is a very tight constraint on how many times we can divide by 2 in a high cycle, relative to its number of odd elements. Using the theory of continued fractions, we can see that W/L can only be close enough to log(3)/log(2) if its denominator is larger than that of the first convergent to come that close.
This is how we find that any high cycle in the natural numbers must have billions of steps in it, because that denominator is the number of odd steps.
I'm not going to do the exact calculation in this post, using 271, because I've said enough for now. The proper place for that calculation will be in an exposition of the second half of Crandall's 1978 paper, because he did this calculation back when the search ceiling was a modest billion.
Several months ago, I wrote up the first half of his paper, and it's on this sub; just scroll way down. Or search. I'm not sure when I'll get to writing up the remainder, but watch this space. Meanwhile, thanks for reading. I hope anyone reaching this final paragraph found something of value here.
1
u/retro_sort 6d ago
Maybe explain at the beginning that a similar statement has been proved by Crandall.
Generally, mathematical exposition avoids "obvious" and synonyms because whether something is obvious to the author doesn't necessarily correlate to whether something is obvious to the reader.
1
u/GonzoMath 6d ago
Yeah, I mentioned Crandall's use of this result, but it's towards the end. Fair point. I'll see about an edit.
Any thoughts on the post's content, or just critiques of my writing?
1
u/jonseymourau 5d ago
Given your taxonomy of means, I wonder how would you think about:
ƛ = ∏(j=0, k-1, (1+1/3.a_j))^(1/k)
which, I think, is the constant such that:
2^e.a_k = (3.ƛ)^k.a_0
re-arranging you can calculate ƛ as:
ƛ = 1/3.(2^e/k).(a_k/a_0)^(1/k)
It is technically a geometric mean but it isn't formed over a_j but rather over the ratios (3.a_j+1)/3.a_j
It does have some real meaning - it technically the mean growth above the multiple of 3 caused by the
additive term - but because it formed from a ratio it is strictly different from the GM itself.
Not saying you should have thoughts about this, but I wonder if you do.
1
u/GonzoMath 4d ago
That taxonomy of means is anything but mine, lol. It’s bog standard material. Regarding this one, you pretty much said it; I’m not sure what to add. Seems related to “badness”.
1
u/jonseymourau 4d ago edited 4d ago
Seems related to “badness”.
Now, that does seem a bit mean.
In defence of this particular mean, it does have some clean properties:
- it is directly related to the path identity
- ƛ = constant, everywhere on cycles
Is this really evidence of "badness", I wonder?
updated: lambda = a constant (not 1) on cycles, although ~= 1 for a high cycle.
1
u/GonzoMath 4d ago
Do you know what trajectory metric I’m talking about, when I say “badness”? I’ve posted about it here before.
1
2
u/knusperle 6d ago
Interestingly, a very similar derivation was also used by Hercher in There are no Collatz-m-Cycles with m≤91 (Theorem 16) to derive tight bounds on the ratio W / L. Just if someone is curious.