The Collatz Problem and Analogues

Bart Snapp and Matt Tracy Department of Mathematics and Statistics Coastal Carolina University Conway, SC 29528-6054 USA

                       snapp@coastal.edu
                      mjtracy@coastal.edu

Abstract

In this paper, we study a polynomial analogue of the Collatz problem. Additionally, we show an additive property of the Collatz graph.

1 Introduction

In the Collatz problem, one starts with any positive integer and repeatedly applies the following function:

C(n) = \begin{cases}3n + 1, & if n is odd; \\ n/2, & if n is even. \end{cases}

Will the iterated application of C always produce the value 1? As an example, consider how C acts on 3:

3 ⟶^{C} 10 ⟶^{C} 5 ⟶^{C} 16 ⟶^{C} 8 ⟶^{C} 4 ⟶^{C} 2 ⟶^{C} 1

This seemingly innocent problem is also known as the 3x + 1 problem, the Hailstone problem, and the Syracuse problem, along with several other names. Despite its simplistic nature, it has remained open since it was suggested by L. Collatz while he was a student in the 1930’s. To some, this problem is a proverbial siren, being seductive yet difficult at the same time. For an in depth discussion of the problem see Lagarias [2].

A condensed version of the traditional Collatz function C(n) can be given:

T (n) = \begin{cases}(3n + 1)/2, & if n is odd; \\ n/2, & if n is even. \end{cases}

We will use the following notation: Let T^{0}(n) = n and inductively define T^{i}(n) = T (T^{i−1}(n)). We can now state the Collatz Conjecture:

Collatz Conjecture. Given any natural number n, there exists a natural number i such that T^{i}(n) = 1.

Since the Collatz problem is notoriously difficult, we do not seek to study it directly. Rather, in Section 2 of this paper, we study a map analogous to T (n), which will act not on the integers, but on a polynomial ring with coefficients in the ring of integers modulo an integer n. In this ring, which we’ll denote by ℤ_{n}[x], we define a map T_{P} (f) which acts on polynomials. The major results of this section are:

Theorem 2.1. Given any polynomial f ∈ ℤ_{2}[x], there exists a natural number i such that T_{P}^{i} (f) = 1. Hence the analogous statement of the Collatz Conjecture is true in ℤ_{2}[x].

Theorem 2.5. If n ≠ 2, then there exists a natural number i and a polynomial f ∈ ℤ_{n}[x] of positive degree such that T_{P}^{i} (f) = f. Hence the analogous statement of the Collatz Conjecture is false in ℤ_{n}[x] when n ≠ 2.

While we find the results above to be interesting in their own right, the study of the analogue to the Collatz problem in ℤ_{2}[x] lead us to a new insight on the problem. In Section 3 of this paper, we show a fascinating arithmetic property of a graph which contains the Collatz graph. Essentially, we have found a meaningful way to combine the graph of the iterates of T (n) on the positive integers with the graph of the iterates of T (n) on the negative integers. It was through our study of the analogous problem in ℤ_{2}[x], where addition looks identical to subtraction, that we were able to see this connection.

During the course of this research, we utilized PARI/GP for aid in intuition and insight, see [3]. The code for the package we wrote for this research can be downloaded from:

                       http://ww2.coastal.edu/snapp/

Finally we would like to mention that our results in Section 2 were concurrent with a publication of Hicks, Mullen, Yucas, and Zavislak, see [1]. We encourage the reader to look into this paper.

2 An analogous question for polynomials

We will first discuss the case of our analogous map in ℤ_{2}[x], then in ℤ_{p}[x] where p is an odd prime, and finally in ℤ_{n}[x] where n is any composite.

2.1 An affirmative result

Given a polynomial f ∈ ℤ_{2}[x], define the following map, which we are viewing as an analogue to T (n):

T_{P} (f) = \begin{cases}((x + 1) · f + 1)/x, & if f is not divisible by x; \\ f/x, & if f is divisible by x. \end{cases}

We are mimicking the relationship between even numbers and odd numbers in the integers. In the integers, 1 added to an odd number will result in an even number. In ℤ_{2}[x], an element is either divisible by x or it is not. To some extent, we are viewing x as 2. Hence when f is not divisible by x, we multiply by x + 1. The product (x + 1) · f will also not be divisible by x. Hence (x + 1) · f + 1 will be divisible by x.

Of particular interest is that deg(T_{P} (f)) ≤ deg(f). In fact, it is easy to see that deg(T_{P} (f)) = deg(f) when x does not divide f. This simple fact is critical in the proof of Theorem 2.1 below. As before, set T_{P}^{0}(f) = f and inductively define T_{P}^{i} (f) = T_{P} (T_{P}^{i−1}(f)).

Theorem 2.1. Given any polynomial f ∈ ℤ_{2}[x], there exists a natural number i such that T_{P}^{i} (f) = 1. Hence the analogous statement of the Collatz Conjecture is true in ℤ_{2}[x].

Proof. Seeking a contradiction, suppose that for some nonconstant polynomial f ∈ ℤ_{2}[x] there does not exist a natural number i such that T_{P}^{i} (f) = 1. Since the function T_{P} does not raise the degree of the polynomial, and since there are only a finite number of polynomials of any fixed degree in ℤ_{2}[x], it must be the case that for some i_{0}, T_{P}^{i_{0}}(f) = f. In this case, for each i, T_{P}^{i} (f) must have a constant term equal to 1. Write

T_{P}^{0}(f) = 1 + ∑_{i=1}^{n} a_{i}x^{i}

So we have that

T_{P}^{1}(f) = 1 + ∑_{i=1}^{n} a_{i}x^{i} + ∑_{i=1}^{n} a_{i}x^{i−1}

In particular, since the constant term of this polynomial must be 1, we see that a_{1} = 0. Repeating this process, starting our indexing at 2, write

T_{P}^{2}(f) = 1 + ∑_{i=2}^{n} a_{i}x^{i} + ∑_{i=2}^{n} a_{i}x^{i−2}

Again, if the constant term of this polynomial must be 1, then we must have that a_{2} = 0. Proceeding inductively, we see that there can be no polynomial of positive degree such that T_{P}^{i} (f) = f. Indeed, we see that f = 1, a contradiction.

2.2 A negative result

One may wonder if the analogous statement of the Collatz Conjecture is true in ℤ_{n}[x] when n > 2. In this case we need to generalize the definition of T_{P} (f) as follows:

T_{P} (f) = \begin{cases}((x + 1) · f − f(0))/x, & if f is not divisible by x; \\ f/x, & if f is divisible by x. \end{cases}

Note, with this new definition of T_{P}, we are not necessarily restricting ourselves to working with polynomial rings over finite fields. Moreover, we should make precise exactly what we mean by an analogue to the Collatz conjecture in this case:

There do not exist nonconstant polynomials f ∈ ℤ_{n}[x] such that T_{P}^{i} (f) = f.

While Theorem 2.1, shows that this statement is true in ℤ_{2}[x], we will now show that this statement is in fact false in ℤ_{n}[x] for all n > 2. We will prove this in steps, starting with ℤ_{p}[x] where p is an odd prime and then move on to the case of ℤ_{n}[x] when n is composite. We will start with a technical lemma:

Lemma 2.2. Given two integers m ≥ n we have the following:

T_{P}^{n}(x^{m} + 1) = \binom{n}{n}x^{m} + \binom{n}{n − 1}x^{m−1} + ⋯ + \binom{n}{0}x^{m−n} + 1

Proof. Proceeding by induction on the iterations of T_{P}. To start, we see that

T_{P} (x^{m} + 1) = \frac{(x + 1)(x^{m} + 1) − 1}{x}

= \frac{x^{m+1} + x^{m} + x}{x}

= x^{m} + x^{m−1} + 1.

Now suppose our theorem is true up to n − 1, that is, assume that:

T_{P}^{n−1}(x^{m} + 1) = \binom{n − 1}{n − 1}x^{m} + \binom{n − 1}{n − 2}x^{m−1} + ⋯ + \binom{n − 1}{0}x^{m−(n−1)} + 1

We now can express T_{P}^{n}(x^{m} + 1) as:

= \frac{(x + 1) (\binom{n−1}{n−1}x^{m} + ⋯ + \binom{n−1}{0}x^{m−(n−1)} + 1) − 1}{x}

= \frac{\binom{n−1}{n−1}x^{m+1} + (\binom{n−1}{n−1} + \binom{n−1}{n−2}) x^{m} + ⋯ + (\binom{n−1}{1} + \binom{n−1}{0}) x^{m−n} + \binom{n}{0}x^{m−(n−1)} + x}{x}

= \frac{\binom{n}{n}x^{m+1} + \binom{n}{n−1}x^{m} + ⋯ + \binom{n}{1}x^{m−n} + \binom{n}{0}x^{m−(n−1)} + x}{x}

= \binom{n}{n}x^{m} + \binom{n}{n − 1}x^{m−1} + ⋯ + \binom{n}{1}x^{m−(n−1)} + \binom{n}{0}x^{m−n} + 1

With the above line holding as long as m ≥ n.

Proposition 2.3. If p is an odd prime, then T_{P}^{p}(x^{p−1} + 1) = x^{p−1} + 1. Hence the analogous statement of the Collatz Conjecture is false in ℤ_{p}[x].

Proof. From Lemma 2.2, we see that:

T_{P}^{p−1}(x^{p−1} + 1) = x^{p−1} + \binom{p − 1}{p − 2}x^{p−2} + ⋯ + \binom{p − 1}{1}x + 2

Hence:

T_{P}^{p}(x^{p−1} + 1) = \frac{x^{p} + (\binom{p−1}{p−2} + 1) x^{p−1} + ⋯ + (\binom{p−1}{1} + 2) x}{x}

= x^{p−1} + \binom{p}{p − 1}x^{p−1} + ⋯ + \binom{p}{1}x + \binom{p}{1} + 1

Examining this expression modulo p, we see that T_{P}^{p}(x^{p−1} + 1) = x^{p−1} + 1.

When working in ℤ_{n}[x] when n is composite, the proof given above may not work as \binom{n}{m} might not be congruent to zero modulo n. Nevertheless, we have the following proposition:

Proposition 2.4. If n is a composite integer with d dividing n, then T_{P}^{n/d}(dx + 1) = dx + 1. Hence the analogous statement of the Collatz Conjecture is false in ℤ_{n}[x].

If n is a composite number, then there exists a natural number i and a polynomial f ∈ ℤ_{n}[x] of positive degree such that T_{P}^{i} (f) = f. Hence the analogous statement of the Collatz Conjecture is false in ℤ_{n}[x] when n is composite.

Proof. Supposing that n is composite and that d divides n. It is easy to see that T_{P} (dx+1) = dx + (d + 1) and that:

T_{P}^{i} (dx + 1) = dx + (di + 1)

Hence we see T_{P}^{n/d}(dx + 1) = dx + (n + 1), which is congruent to dx + 1 modulo n.

Putting the statements of Proposition 2.3 and Proposition 2.4 together, we obtain:

Theorem 2.5. If n ≠ 2, then there exists a natural number i and a polynomial f ∈ ℤ_{n}[x] of positive degree such that T_{P}^{i} (f) = f. Hence the analogous statement of the Collatz Conjecture is false in ℤ_{n}[x] when n ≠ 2.

One may wonder if there exists a polynomial f in ℤ_{p}[x] when p is a prime of such that T_{p}^{i}(f) = f and deg(f) < p − 1. In fact there are many such examples. However, we will leave the classification of such polynomials for future researchers.

3 Connections to the Collatz graph

While we can prove a result analogous to the Collatz Conjecture in ℤ_{2}[x], it is difficult to connect this back to the whole-number case. Nevertheless, we are able to gain insight on the Collatz problem through our study of ℤ_{2}[x]. In particular, in ℤ_{2}[x] there is no distinction between an element and its additive inverse. With this fact in mind, we make the following definitions:

Definition. Call the standard Collatz graph of the iterates of T (n), the positive Collatz graph. This graph generated as follows: Each integer n is associated to a vertex. Vertices n and m are connected by an edge if and only if T (n) = m. We will depict this graph as a directed graph with an arrow from n to m if T (n) = m, see Figure 1.

On the other hand, call the Collatz graph of the iterates of T (n), when n is assumed to be a negative integer, the negative Collatz graph.

Figure 1: A portion of the positive Collatz graph.

We will make a new graph, combining the positive Collatz graph and the negative Collatz graph which we will call the combined Collatz graph. If the Collatz Conjecture is true, then this new graph will have the positive Collatz graph as a subgraph. Moreover, the combined Collatz graph has an additive property between the vertices which we will make clear below. Start with a technical lemma:

Lemma 3.1. Consider any integer n which is not divisible by 3. Then there exist unique x, y ∈ ℕ such that 2n = x + y and exactly one of the following is true:

1. T (x) = n and T (−y) = −2n.

2. T (−x) = −n and T (y) = 2n.

Proof. Since n is an integer which is not divisible by 3,

n = 3k + 1 or n = 3k + 2

for some k ∈ ℤ. A direct calculation will show that in either case exactly one of the following pairs

(x, y) = (\frac{2n − 1}{3}, \frac{4n + 1}{3}) or (x, y) = (\frac{2n + 1}{3}, \frac{4n − 1}{3})

is a pair of odd integers, with the other pair consisting of rational numbers which are not integers.

We will verify our statement in the case where the first pair above consists of odd integers. Set x = (2n − 1)/3 and set y = (4n + 1)/3. It is easy to see that x + y = 2n. Moreover since x and y are odd, a direct calculation shows that T (x) = n and T (−y) = −2n. The fact that these values of x and y are unique is clear from the definition of T. The verification of the second case is similar.

Remark. If n is divisible by 3, then there is no integer x such that (3x + 1)/2 = n.

We are now able to generate a graph as follows: Starting with any integer n which is not divisible by 3, work as in Lemma 3.1 and set

x = \begin{cases}(2n − 1)/3 & if n ≡ 2 (mod 3); \\ (2n + 1)/3 & if n ≡ 1 (mod 3). \end{cases}

Now we may obtain y via subtraction:

y = 2n − x

Since there are two cases for the x and y values we find, there are two cases of subgraphs:

_{\begin{matrix}n≡2 (mod 3) \\ x=(2n−1)/3 \\ y=(4n+1)/3 \end{matrix}}  _{\begin{matrix}n≡1 (mod 3) \\ x=(2n+1)/3 \\ y=(4n−1)/3 \end{matrix}}

The dotted edges above should not be considered part of the graph, they are only depicted to aid the reader in seeing how we produce the next vertex through subtraction.

Corollary 3.2. With x and y as defined above, if n ≡ 2 (mod 3), then we have subgraphs

of the positive Collatz graph, and negative Collatz graph respectively.

If n ≡ 1 (mod 3), then we have subgraphs

of the positive Collatz graph, and negative Collatz graph respectively.

Proof. Follows directly from the statement of Lemma 3.1.

3.1 Construction of the combined Collatz graph

The combined Collatz graph is constructed as follows: Starting with n = 1, repeatedly apply Lemma 3.1 to the powers of 2 to generate the subgraph given in Figure 2.

Figure 2: A start at the combined Collatz graph.

Here the dotted lines show how to produce the next vertex via subtraction. By Corollary 3.2, the solid vertices above correspond to vertices of the positive Collatz graph and hollow vertices above correspond to the vertices of the negative Collatz graph.

Now consider the vertices which are not multiples of 2 which correspond to vertices of the positive Collatz graph. These are either congruent to 0, 1, or 2 modulo 3. Omitting the vertex denoted by 1, apply Lemma 3.1, to generate the next branches of the graph, see see Figure 3.

By repeating this process inductively, we obtain the combined Collatz graph, see Figure 4.

Corollary 3.3. The positive Collatz graph is a subgraph of the combined Collatz graph if and only if the Collatz Conjecture holds.

Proof. If the positive Collatz graph is a subgraph of the combined Collatz graph, then each positive integer must eventually go to 1, as we generated this graph starting at 1.

If the Collatz Conjecture is true, then there is a path to 1 and this construction will find it.

The surprising feature of the combined Collatz graph is that using very simple arithmetic allows for quick and easy generation of the graph. Through this expedient process, we obtain

Figure 3: More of the combined Collatz graph. Figure 4: A portion of the combined Collatz graph. a graph which has the positive Collatz graph as an identifiable subgraph, assuming that the Collatz Conjecture is true. Moreover, note that the construction of the combined Collatz graph is in some sense, fundamentally different from the construction of either the positive Collatz graph or the negative Collatz graph. The insight of looking at both the positive Collatz graph and the negative Collatz graph was gained only through the study of the analogous problem in ℤ_{2}[x].

4 Acknowledgments

We would like to thank Doug Shaw and David Duncan for reading over a preliminary draft of this manuscript and making several helpful comments. We would also like to thank the anonymous referee for his or her comments as well.

References

[1] K. Hicks, G. L. Mullen, J. L. Yucas, and R. Zavislak, A polynomial analogue of the 3n + 1 problem. Amer. Math. Monthly 115 (2008), 615–622.

[2] J. C. Lagarias, The 3x + 1 problem and its generalizations. Amer. Math. Monthly 92 (1985), 3–23.

[3] The PARI Group, Bordeaux. PARI/GP, version 2.3.2, 2005. available from

   http://pari.math.u-bordeaux.fr/.

2000 Mathematics Subject Classification: Primary 11T55; Secondary 11B25. Keywords: Collatz conjecture, polynomial analogue

(Concerned with sequence \underline{A061641}.)

Received May 22 2008; revised version received October 31 2008. Published in Journal of Integer Sequences, November 16 2008.

Return to Journal of Integer Sequences home page.