Polynomial analog of the Collatz conjecture

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.

1. If n is even, set n n /2. Otherwise n 3n + 1.
2. 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^2 + 2n steps where n is the degree of the polynomial [1].

Here's an example starting with the polynomial x⁷ + x³ + 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^2 + 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 + x²
• 2 + x + x² + x³
• 2 x² + 2 x³ + x⁴
• 2 x + 2 x² + x³
• 2 + 2 x + x²
• x + x³
• 1 + x²

Related posts

• The iterated aliquot problem
• What is a polynomial in abstract algebra?

[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.

The post Polynomial analog of the Collatz conjecture first appeared on John D. Cook.