I recently came across a solvable variation of the Collatz conjecture due to Farkas. I first read about it in An Automated Approach to the Collatz Conjecture by Emre, Aaronson and Heule. Define (over odd values):
F^\prime(n) = \begin{cases}
\frac{n}{3} & \text{if } n \equiv 0 \pmod{3} \\
\frac{n+1}{2} & \text{if } n \not\equiv 0 \pmod{3} \text{ and } n \equiv 1 \pmod{4} \\
\frac{3n+1}{2} & \text{if } n \not\equiv 0 \pmod{3} \text{ and } n \equiv 3 \pmod{4} \\
\end{cases}
This always maps odd inputs to odd outputs.
Lemma: For all n > 1, there exists k such that (F^\prime)^k(n) < n.
Proof: The non-trivial case is the n \equiv 3 \pmod{4} case.
Note that F^\prime(4k+3) = 6k+5, so the next rule cannot be the n \equiv 0 \pmod{3} rule.
Apply F^\prime repeatedly to n as long as it matches the n \equiv 3 \pmod{4} rule, say j times.
Note that F^\prime(n)+1 = \frac{3}{2} (n+1). So now we have (F^\prime)^j(n) +1 = (\frac{3}{2})^j (n+1).
We now know this must match the n \equiv 1 \pmod{4} case, so (F^\prime)^{j+1}(n) = \frac{3^j}{2^{j+1}} (n+1).
The 2s cannot divide the 3s, so m = \frac{n+1}{2^{j+1}} must be an integer and thus we have: (F^\prime)^{j+1}(n) = 3^j m.
This clearly applies to the n \equiv 0 \pmod{3} rule j times (at least) reaching (F^\prime)^{2j+1}(n) = m = \frac{n+1}{2^{j+1}} < n for all n > 1.
QED
So this is a Collatz-like function which provably always goes to 1 in a non-trivial way which I find very fascinating.
Furthermore, Emre et al show that you can define F(n) = \frac{F^\prime(2n+1) - 1}{2} which has the exact same behavior and looks a lot more like the classic Collatz function:
This is just Collatz, but with a special behavior in the n \equiv 1 \pmod{3} case!
Hershel M. Farkas. Variants of the 3N + 1 conjecture and multiplicative semigroups.
In Geometry, Spectral Theory, Groups, and Dynamics, number 387 in Contemporary
Mathematics, pages 121–127. American Mathematical Society, 2005.
What is it about this variation that makes this proof work? Are there other provable variations like this? Specifically, I want to avoid versions that seem much more “trivially” provable, like f(n) = n+1 (for n odd) where it’s easy to see that all cases decrease in just 2 steps or f(n) = 3n+2 (for n odd) where we can immediately show that this always maps odd to odd and thus diverges. The Farkas map seems more subtle than these.
If n is even: n×1.5
If n is 1 mod4 :(n×3+1)÷4
If n is 3 mod4: (n+1)÷4
These rules track odd to odd movements in the collatz conjecture, with the exception of 3 mod4, which tracks even reductions where the even number could be derived from an (odd×3+1). It looks like the examples you’ve shown here might be able to be leveraged to show why the above rules return to 1.
OK, I have a way to think about this directly in terms of the Collatz function. Consider any odd number n decomposed as n = (2k+1) 2^j - 1. In other words, j is the number of powers of 2 in n+1 and 2k+1 is the remaining odd factor after all 2s have been divided out.
Now we know that T^j(n) = (2k+1) 3^j - 1 and this is even, so then we get T^{j+1}(n) = \frac{(2k+1) 3^j - 1}{2} = k 3^j + \frac{3^j - 1}{2}
Now think of this number in base 3: it has k on the left and on the right: 3^j - 1 = 22\dots2_3 (with j 2s) and so \frac{3^j - 1}{2} = 11\dots1_3 (with j 1s). So we can see that k 3^j + \frac{3^j - 1}{2} \equiv 1 \pmod{3} and F(k 3^j + \frac{3^j - 1}{2}) = k 3^{j-1} + \frac{3^{j-1} - 1}{2} and repeating this we see that F^j(k 3^j + \frac{3^j - 1}{2}) = k.
So F^{2j+1}((2k+1) 2^j - 1) = k which is clearly a decrease.
In other words this seems to be taking advantage of the property of Collatz sequences that if you start with binary number bin(k) 0 1^j (j trailing 1s) this has paritity sequence (1^j, 0) and leads to the value base3(k) 1^j in base 3:
It’s worth noting that Emre et al’s machine-proof system automatically proved that the Farkas rule takes all numbers to 1 (this was years after Farkas’ manual proof, but still).
Although the same machine-proof system was unable to prove the Collatz conjecture.
Understanding that was the first moment I seriously (let’s say) entertained the idea that the Collatz conjecture might be false.
(For anyone not familiar with the Emre et al machine-proof system, it’s awesome, and there’s a summary in the sample chapters from Math Kook, p. 189.)
This tricot is of height 6, but the affine coefficients (3,2,3,9,2,9) aren’t all coprime to 6 (none are actually), so we can’t apply the unicity of trajectories.
EDIT: I changed my mind about what follows, it seems wrong. I leave it as a spoiler for reference to remember it though.
What we can do however, is to “reduce” the same way we can reduce 3n+1 by going from:
2k → k
2k+1 → 6k+4
(not a prime tricot since 6 and 2 aren’t coprime)
to:
2k → k
2k+1 (-> 6k+4) → 3k+2
This reduction will yield to another tricot where all affine coefficients are lesser than the height, and thus it implies the convergence.
Yeah, AFAICT, there is no way to “reduce” this to a “prime tricot”. But it does feel like the non-primeness could be related to why this is reducible. Certainly the fact that it divides by both 2 and 3 in different paths seems really important to this specific proof.
