The Collatz conjecture, a.k.a. the 3n + 1 problem, a.k.a. the hailstone conjecture, asks whether the following sequence always terminates.
Start with a positive integer n.
- If n is even, set n ← n /2. Otherwise n ← 3n + 1.
- If n = 1, stop. Otherwise go back to step 1.
The Collatz conjecture remains an unsolved problem, though there has been progress toward a proof. Some people, however, are skeptical whether the conjecture is true.
This post will look at a polynomial analog of the Collatz conjecture. Instead of starting with a positive integer, we start with a polynomial with coefficients in the integers mod m.
If the polynomial is divisible by x, then divide by x. Otherwise, multiply by (x + 1) and add 1. Here x is analogous to 2 and (x + 1) is analogous to 3 in the (integer) Collatz conjecture.
Here is Mathematica code to carry out the polynomial Collatz operation.
c[p_, m_] := PolynomialMod[ If[ (p /. x -> 0) == 0, p/x, (x + 1) p + 1 ], m ]
If m = 2, the process always converges. In fact, it converges in at most n² + 2n steps where n is the degree of the polynomial [1].
Here’s an example starting with the polynomial x7 + x3 + 1.
Nest[c[#, 2] &, x^7 + x^3 + 1, 15]
This returns 1, and so in this instance 15 iterations are enough.
If m = 3, however, the conjecture is false. In [1] the authors report that the sequence starting with x² + 1 is periodic with period 6.
The following code produces the sequence of values.
NestList[c[#, 3] &, x^2 + 1, 6]
This returns the sequence
- 1 + x2
- 2 + x + x2 + x3
- 2 x2 + 2 x3 + x4
- 2 x + 2 x2 + x3
- 2 + 2 x + x2
- x + x3
- 1 + x2
Related posts
[1] Kenneth Hicks, Gary L. Mullen, Joseph L. Yucas and Ryan Zavislak. A Polynomial Analogue of the 3n + 1 Problem. The American Mathematical Monthly, Vol. 115, No. 7. pp. 615-622.
August–September 2008
Delightful!
These operations for the first time look to me like cellular automata instructions.
Perhaps Collatz stumbled across the number theory version of Wolfram’s “rule 110” that keeps generating randomness.
Is there a category theorist in the house? There must be functors between 1-D cellular automata and operations on Diophantine equations; maybe some of Wolfram‘s results can be brought over to these spaces?
@Ross: I hadn’t thought of it like that, but the mod 2 case does seem a lot like cellular automata. (You can do cellular automata mod other bases, but that’s less common.)
I hadn’t thought about it until reading your comment, but this algorithm is really nice in low-level bit operations: you shift to the right if the last bit is zero, and you shift to the left and XOR with the original otherwise.