On q-Analogs of the 3x + 1 Dynamical System

Kenneth G. Monks Department of Mathematics University of Scranton Scranton, PA 18510 USA

                      monks@scranton.edu

Abstract

We construct an infinite family of maps on F_{2}[[q]] that are conjugate to the famous 3x + 1 map on the 2-adic integers. We identify one such map that has the further property that the positive integers whose 3x + 1-orbit contains 1 correspond to polynomials via a conjugacy, and whose polynomial orbits all eventually enter the 2-cycle or one of the two fixed points. Proving that every positive integer corresponds to a polynomial via this conjugacy would settle the original 3x + 1 conjecture.

1 Introduction and background

A discrete dynamical system on a set X is obtained by iterating a map f: X → X. For any function f: X → X and any x ∈ X, the f-orbit of x is the set {f^{k}(x) : k ∈ ℕ} where f^{0} is the identity map and f^{k} = f ∘ f^{k−1} for all positive integers k. Two dynamical systems f: X → X and g: Y → Y are conjugate (or isomorphic as dynamical systems) if and only if there exists a bijection h: X → Y such that h ∘ f = g ∘ h. Such a map h is called a conjugacy, and it is easy to see that conjugacies preserve the sizes of orbits as well as other properties of the dynamical system.

The famous 3x + 1 conjecture states that the T -orbit of every positive integer contains 1, where

T (x) = \begin{cases}\frac{x}{2}, & if 2 divides x; \\ \frac{3x+1}{2}, & otherwise. \end{cases}

It has been an open problem in mathematics since the 1930s (see Lagarias [3] and Wirsching [8]).

More recently, several authors have studied a similar dynamical system, T_{q}: F_{2}[q] → F_{2}[q] where F_{2}[q] is the ring of univariate polynomials in q with coefficients in the field with two elements, and for all x ∈ F_{2}[q],

T_{q}(x) = \begin{cases}\frac{x}{q}, & if q divides x; \\ \frac{(1+q)x+1}{q}, & otherwise. \end{cases}

There is a natural bijection ξ: F_{2}[q] → ℤ^{+} that associates a q-polynomial f(q) with the positive integer f(2). Its inverse map sends a positive integer n to the q-polynomial obtained by replacing 2 with q in the base two representation of n. Note that the maps T and T_{q} have the same form if we replace q with 2 in the definition of T_{q}.

It was shown concurrently by Hicks, Mullen, Yucas, and Zavislak [2] and by Snapp and Tracy [7] that the T_{q}-orbit of any polynomial contains 1. The latter concluded that the analog of the 3x + 1 conjecture holds for T_{q} [7, Theorem 2.1]. While the result is analogous if we identify q-polynomials p with their positive integer ξ(p), this does not prove the 3x + 1 conjecture itself, since iterating T_{q} on any polynomial eventually reaches the fixed point 1, but iterating T on infinitely many positive integers eventually reaches the two-cycle {1, 2}. Thus, these two dynamical systems are not conjugate via any correspondence between the positive integers and polynomials.

In this paper, we show that the dynamical systems T and T_{q} actually are conjugate if we extend their domains to the ring of 2-adic integers, ℤ_{2}, and the ring of formal power series in q, F_{2}[[q]], respectively. Both dynamical systems have a unique two-cycle. Thus, to prove the 3x+1 conjecture, it suffices to show for some conjugacy h between T and T_{q} that for any positive integer n, iterating T_{q} on h(n) eventually reaches the unique two-cycle for T_{q}. Using h instead of ξ produces an analogous conjecture whose resolution would settle the original problem.

A similar situation occurs for any function that is conjugate to T. In particular, we will also show that if A, B are elements of F_{2}[[q]] with constant term 1 (i.e., not divisible by q) then the map T_{A,B}: F_{2}[[q]] → F_{2}[[q]] given by

T_{A,B}(x) = \begin{cases}\frac{x}{q}, & if q divides x; \\ \frac{Ax+B}{q} , & otherwise \end{cases}

is conjugate to T and the 3x + 1 conjecture is true if and only if for any conjugacy h: ℤ_{2} → F_{2}[[q]] between T and T_{A,B}, and any positive integer n, the T_{A,B}-orbit of h(n) eventually reaches the unique two-cycle for T_{A,B}. Note that T_{q} is T_{1+q,1} in this notation.

Each element of ℤ_{2} is a formal sum ∑_{i=0}^{∞} x_{i}2^{i} where x_{i} ∈ {0, 1} for all i ∈ ℕ. Thus, we can extend ξ to a bijective correspondence between F_{2}[[q]] and ℤ_{2} by associating a formal power series f(q) ∈ F_{2}[[q]] to the 2-adic integer f(2). We will refer to the elements of F_{2}[[q]] as q-series in what follows for brevity.

The binary representation of either a 2-adic integer x = ∑_{i=0}^{∞} x_{i}2^{i} or a q-series x = ∑_{i=0}^{∞} x_{i}q^{i} is the infinite sequence of zeroes and ones x_{0}x_{1}x_{2} · · ·. By identifying 2-adic integers and q-series with their binary representations, we can consider both T and T_{q} to be dynamical systems from Σ_{2} → Σ_{2}, where Σ_{2} is the set of all infinite binary sequences. We will say that a 2-adic integer or q-series is even if and only if the leading digit of its binary representation is 0 (which implies it is divisible by 2 or q, respectively), and odd otherwise. Similarly, the parity of an element is either 0 or 1 depending on whether the element is even or odd, respectively.

The ordinary rational numbers with odd denominators (when written as reduced fractions) are isomorphic to a subring of ℤ_{2} and correspond to the 2-adic integers with eventually repeating binary representations via the geometric series formula. We can use this as a compact way to represent a q-series whose binary representation is eventually repeating (keeping in mind that ordinary addition and multiplication of rational numbers correspond to addition and multiplication in ℤ_{2}, not in F_{2}[[q]]). Also note that we can express such power series as rational expressions in q with coefficients in F_{2}.

Example 1. Let P_{1} = 1+q+q^{3}+q^{4}+q^{6}+q^{7}+⋯ = \frac{1+q}{1+q^{3}} ∈ F_{2}[[q]]. The binary expansion of P_{1} is 110110110 ⋯ which we can abbreviate as \overline{110}. But \overline{110} is also the binary representation of the 2-adic 1 + 2 + 2^{3} + 2^{4} + 2^{6} + 2^{7} + ⋯ which equals −3/7 by the geometric series formula. Thus, we have the correspondence ξ(P_{1}) = −3/7. Notice that ξ(f) is a positive integer whenever f ∈ F_{2}[[q]] is a polynomial, which is the correspondence assumed by Snapp and Tracy [7, Theorem 2.1] when referring to the analogous conjecture.

Notice that in this situation f is odd if and only if the numerators of both f and ξ(f) are odd when each is written as a reduced fraction. So the parity of f is always the same as the parity of the numerators of the reduced fractions for f and ξ(f).

2 Main results

While the correspondence ξ is a natural one to consider when comparing the dynamical systems T and T_{q}, it is not a conjugacy even when their domains are extended to ℤ_{2} and F_{2}[[q]], respectively. That such conjugacies do exist, however, is the point of our first main result. For the remainder of this paper, we assume that T: ℤ_{2} → ℤ_{2} and T_{A,B}: F_{2}[[q]] → F_{2}[[q]].

Theorem 2. For any odd A, B ∈ F_{2}[[q]], the map T_{A,B} is conjugate to T.

Corollary 3. The map T_{q} is conjugate to T.

Thus, for any conjugacy h between T and T_{A,B}, the power series that correspond to the positive natural numbers are those in h(ℕ^{+}). For T_{q}, this set does not include any polynomials, as all nonzero polynomial orbits end in the fixed point 1 of T_{q}, but no positive integer has a T -orbit that contains the fixed points 0 or −1 of T.

Similarly, any conjugacy between T and T_{q} must map 1 to an element of the unique 2-cycle of T_{q}, namely {P_{1}, qP_{1}} (or equivalently {−3/7, −6/7}). If the conjugacy preserves parity, then for T_{q} it is −3/7 that corresponds to 1 for T, and so the analogous conjecture can be stated as follows:

Conjecture 4. For any conjugacy h: ℤ_{2} → F_{2}[[q]] between T and T_{q} and any positive integer n, the T_{q}-orbit of h(n) contains −3/7.

It follows from the results of Monks and Yazinski [4] that there exists a parity-preserving conjugacy h such that h(1) = −3/7. For any such h and any positive integer n, we can calculate the corresponding power series h(n) for T_{q}. If we can show that all such power series have −3/7 in their T_{q} orbit, then it will prove the 3x + 1 conjecture. We list the first few such values in Table 1.

Given that polynomials do not correspond to positive integers for any conjugacy between T and T_{q}, a natural question to ask is whether such conjugacies might exist for some other maps T_{A,B}. Our second main result answers this in the affirmative.

Theorem 5. The T_{1,1+q^{2}}-orbit of any polynomial contains the 2-cycle {1, q} or one of the two fixed points 0 or 1 + q. Furthermore, T_{1,1+q^{2}}(x) is a polynomial if and only if x is a polynomial.^{1}

Since the only 2-cycle for T is {1, 2} and no positive integer has a T -orbit that contains the fixed points 0 or −1, it follows that for any conjugacy between T and T_{1,1+q^{2}}, the positive integers whose T -orbit contains 1 correspond to polynomials. Thus, to prove the 3x + 1 conjecture, it suffices to prove the following.

Conjecture 6. For any conjugacy H: ℤ_{2} → F_{2}[[q]] between T and T_{1,1+q^{2}} and any positive integer n, the power series H(n) is a polynomial.

Equivalently, the 3x + 1 conjecture is true if and only if ξ(H(n)) is an integer for every positive integer n. We provide the first few such values in Table 2 for any parity-preserving conjugacy, H. Given that Conjecture 6 is equivalent to the original 3x + 1 conjecture, it is not surprising that no integer sequence starting with the first twenty values of ξ(H(n)) appears in the OEIS [6].

Notice that arithmetic in F_{2}[[q]] is somewhat simpler than it is in ℤ_{2}, because addition and multiplication of their binary representations are binary arithmetic without carrying. For example, in F_{2}[[q]] we have 3 + 6 = 5, 3 · 6 = 3 · 4 + 3 · 2 = 10. In this notation, since ξ(1 + q) = 3, ξ(1) = 1, and ξ(q) = 2, the formula for T_{q} becomes

T_{q}(x) = \begin{cases}\frac{x}{2}, & if x is even; \\ \frac{3x+1}{2}, & otherwise \end{cases}

which looks exactly like the formula for T except that the addition and multiplication are the corresponding binary operations without carrying. Similarly, the formula for T_{1,1+q^{2}} becomes

T_{1,1+q^{2}}(x) = \begin{cases}\frac{x}{2}, & if x is even; \\ \frac{x+5}{2}, & otherwise \end{cases}

with the same simpler addition and multiplication.

As the results of Hicks, Mullen, Yucas, and Zavislak [2], Snapp and Tracy [7], and Theorem 5 show, working with these simpler binary operations can allow us to more easily determine the behavior of the orbits. Thus, determining a closed formula for the correspondence shown in either Table 1 or Table 2 could very well lead to a solution to the original conjecture itself.

1A similar theorem holds more generally for any T_{A,B}, where B is a polynomial multiple of A + q^{2}.

2.1 Proof of Theorem 2

It is well known (cf. Lagarias [3]) that T is conjugate to the shift map σ: ℤ_{2} → ℤ_{2}, given by

σ(x) = \begin{cases}\frac{x}{2}, & x is even; \\ \frac{x−1}{2}, & x is odd. \end{cases}

Notice that if x_{0}x_{1}x_{2} ⋯ is the binary representation of x, then σ(x_{0}x_{1}x_{2} ⋯) = x_{1}x_{2}x_{3} ⋯, i.e., σ “shifts” the binary digits by deleting the first one. This makes it very easy to determine, for example, the number of cycles with n elements for a fixed n. In particular, σ has two fixed points \{\overline{0}\} and \{\overline{1}\}, a unique cycle of size two \{\overline{01}, \overline{10}\}, and two cycles of size three \{\overline{110}, \overline{011}, \overline{101}\} and \{\overline{001}, \overline{100}, \overline{010}\}.

Since conjugacy is an isomorphism in the category of discrete dynamical systems, to prove Theorem 2, it suffices to show that T_{A,B} is conjugate to σ. We begin with a few easy lemmas.

Lemma 7. Let n ∈ ℕ and U, V ∈ F_{2}[[q]] with V odd. Then

T_{A,B}(U + q^{n+1}V) = T_{A,B}(U) + q^{n}W

for some odd W ∈ F_{2}[[q]].

Proof. Let n ∈ ℕ and U, V ∈ F_{2}[[q]] with V odd. Either U is even or U is odd. Case 1: Assume U is even. Then U + V q^{n+1} is even as well. So

T_{A,B}(U + q^{n+1}V) = \frac{U + q^{n+1}V}{q}

= \frac{U}{q} + q^{n}V

= T_{A,B}(U) + q^{n}V

and V is odd.

Case 2: Assume U is odd. Then U + V q^{n+1} is odd as well. So

T_{A,B}(U + q^{n+1}V) = \frac{A(U + q^{n+1}V) + B}{q}

= \frac{AU + B}{q} + q^{n}AV

= T_{A,B}(U) + q^{n}AV,

and AV is odd since both A and V are.

So in both cases, the result follows.

Corollary 8. Let n ∈ ℕ and U, V ∈ F_{2}[[q]] with V odd. Then for all k ≤ n + 1

T_{A,B}^{k}(U + q^{n+1}V) = T_{A,B}^{k}(U) + q^{n+1−k}W_{k}

for some odd W_{k} ∈ F_{2}[[q]].

Proof. We proceed by induction on k for arbitrary n. For the base case, we have

T_{A,B}^{0}(U + q^{n+1}V) = U + q^{n+1}V
= T_{A,B}^{0}(U) + q^{n+1−0}V

where V is odd.

For the inductive step, let k ≤ n and assume

T_{A,B}^{k}(U + q^{n+1}V) = T_{A,B}^{k}(U) + q^{n+1−k}W_{k}

for some odd W_{k}. Then

T_{A,B}^{k+1}(U + q^{n+1}V) = T_{A,B}(T_{A,B}^{k}(U + q^{n+1}V))
= T_{A,B}(T_{A,B}^{k}(U) + q^{n+1−k}W_{k})
= T_{A,B}^{k+1}(U) + q^{n−k}W_{k+1}
= T_{A,B}^{k+1}(U) + q^{n+1−(k+1)}W_{k+1}

for some odd W_{k+1} by Lemma 7, which completes the induction.

This gives us the next interesting corollary, which essentially says that changing the coefficient of q^{n} in a q-series changes the parity of its n^{th} iterate. We write ≡_{m} to indicate congruence with modulus m.

Corollary 9. Let n ∈ ℕ and U, V ∈ F_{2}[[q]] with V odd. Then T_{A,B}^{n}(U + q^{n}V) and T_{A,B}^{n}(U) have opposite parity, i.e.,

T_{A,B}^{n}(U + q^{n}V) ≢_{q} T_{A,B}^{n}(U).

Proof. We consider two cases, either n = 0 or n > 0.

If n = 0 then since V is odd, U + V ≢_{q} U, and so

T_{A,B}^{n}(U + q^{n}V) = T_{A,B}^{0}(U + q^{0}V)

= U + V

≢_{q} U

= T_{A,B}^{0}(U).

If n > 0, then by the previous corollary, there exists an odd W ∈ F_{2}[[q]] such that T_{A,B}^{n}(U + q^{n}V) = T_{A,B}^{n}(U) + q^{n−n}W, so

T_{A,B}^{n}(U + q^{n}V) = T_{A,B}^{n}(U) + q^{n−n}W

= T_{A,B}^{n}(U) + W

≢_{q} T_{A,B}^{n}(U).

Definition 10. For x ∈ F_{2}[[q]], define the parity vector PV_{A,B}(x) to be the 2-adic integer whose binary representation is x_{0}x_{1}x_{2} ⋯ where for each k ∈ ℕ, x_{k} ∈ {0, 1} is the parity of T_{A,B}^{k}(x).

We abbreviate PV_{A,B} as PV when the subscripts are clear from the context.

Theorem 11. For n ∈ ℕ and a, b ∈ F_{2}[[q]],

PV(a) ≡_{2^{n+1}} PV(b) ⇔ a ≡_{q^{n+1}} b.

Proof. We proceed by induction on n.

For the base case, if n = 0, then for any a, b ∈ F_{2}[[q]], T_{A,B}^{0}(a) = a and T_{A,B}^{0}(b) = b. So PV(a) ≡_{2^{0+1}} PV(b) if and only if a ≡_{q^{0+1}} b.

For the inductive hypothesis, let k ∈ ℕ and assume for all a, b ∈ F_{2}[[q]],

PV(a) ≡_{2^{k+1}} PV(b) ⇔ a ≡_{q^{k+1}} b.

Let a, b ∈ F_{2}[[q]].

(⇐) Assume a ≡_{q^{k+2}} b. Then a = p + q^{k+1}c and b = p + q^{k+1}d for some p, c, d ∈ F_{2}[[q]] such

that p is a polynomial of degree less than k + 1 and c ≡_{q} d (i.e., they have the same parity).

Clearly,

a = p + q^{k+1}c

≡_{q^{k+1}} p

≡_{q^{k+1}} p + q^{k+1}d

= b,

so by the inductive hypothesis PV(a) ≡_{2^{k+1}} PV(b).

Additionally, by Corollary 8,

T_{A,B}^{k+1}(a) = T_{A,B}^{k+1}(p + q^{k+1}c)

= T_{A,B}^{k+1}(p) + q^{0}c

= T_{A,B}^{k+1}(p) + c

≡_{q} T_{A,B}^{k+1}(p) + d

= T_{A,B}^{k+1}(p) + q^{0}d

= T_{A,B}^{k+1}(p + q^{k+1}d)

= T_{A,B}^{k+1}(b).

Combining these two results shows PV(a) ≡_{2^{k+2}} PV(b) as desired.

(⇒) Now assume PV(a) ≡_{2^{k+2}} PV(b). Then PV(a) ≡_{2^{k+1}} PV(b), so by the induction hy-

pothesis a ≡_{q^{k+1}} b.

Assume a ≢_{q^{k+2}} b. Since a ≡_{q^{k+1}} b, it must be that a = p + q^{k+1}c and b = p + q^{k+1}d for some

p, c, d ∈ F_{2}[[q]] such that p is a polynomial of degree less than k + 1 and c ≢_{q} d (i.e., c, d have

opposite parity). Thus, again by Corollary 8,

T_{A,B}^{k+1}(a) = T_{A,B}^{k+1}(p + q^{k+1}c)

= T_{A,B}^{k+1}(p) + q^{0}c

= T_{A,B}^{k+1}(p) + c

≢_{q} T_{A,B}^{k+1}(p) + d

= T_{A,B}^{k+1}(p) + q^{0}d

= T_{A,B}^{k+1}(p + q^{k+1}d)

= T_{A,B}^{k+1}(b)

so PV(a) ≢_{2^{k+2}} PV(b), which is a contradiction. So a ≡_{q^{k+2}} b as desired.

It follows that P V induces a bijection from F_{2}[[q]]/q^{n} to ℤ_{2}/2^{n} for any positive n.

Corollary 12. Let n ∈ ℕ^{+}. For any a ∈ F_{2}[[q]], define P̂V([a]) = [PV(a)] where [a] is the equivalence class of a in F_{2}[[q]]/q^{n} and [PV(a)] is the equivalence class of PV(a) in ℤ_{2}/2^{n}. Then P̂V: F_{2}[[q]]/q^{n} → ℤ_{2}/2^{n} is a bijection.

Proof. By Theorem 11, P̂V maps to the same equivalence class for all elements in the same equivalence class, so P̂V is a well-defined function.

If [a], [b] ∈ F_{2}[[q]]/q^{n} and P̂V([a]) = P̂V([b]), then

[PV(a)] = P̂V([a])
= P̂V([b])
= [PV(b)].

Thus, PV(a) ≡_{2^{n}} PV(b). Therefore, a ≡_{q^{n}} b by Theorem 11 and thus [a] = [b]. So P̂V is

injective.

Finally, both F_{2}[[q]]/q^{n} and ℤ_{2}/2^{n} are finite sets with 2^{n} elements, so any injective function between them must be bijective as well.

Taking the inverse limit of these maps with respect to n produces the desired conjugacy needed to prove our main result.

Proof (of Theorem 2). We will show that PV: F_{2}[[q]] → ℤ_{2} is a conjugacy between T_{A,B} and the shift map σ.

Let a, b ∈ F_{2}[[q]] and assume PV(a) = PV(b). Then for all positive n, PV(a) ≡_{2^{n}} PV(b) and thus a ≡_{q^{n}} b by Theorem 11. But two elements of F_{2}[[q]] which are congruent mod q^{n} for

all n must be equal. Therefore, a = b and so PV is injective.

To see that PV is surjective, let x ∈ ℤ_{2}. Then by Corollary 12, for each positive integer n there exists a_{n} ∈ F_{2}[[q]] such that PV(a_{n}) ≡_{2^{n}} x. Since s ≡_{2^{n}} x implies s ≡_{2^{m}} x for all m ≤ n, by Theorem 11, a_{n} ≡_{q^{n}} a_{m} for all m ≤ n. So there is a unique a ∈ F_{2}[[q]] such that a ≡_{q^{n}} a_{n}

and PV(a) ≡_{2^{n}} x for all n. Thus, PV(a) = x as desired.

Finally, to see that PV is a conjugacy, let a ∈ F_{2}[[q]]. Then by the definition of parity vector,

(PV ∘T_{A,B})(a) = PV(T_{A,B}(a))
= σ(PV(a))
= (σ ∘ PV)(a).

So T_{A,B} is conjugate to the shift map via conjugacy PV. But it is well known (cf. Lagarias [3]) that the shift map is conjugate to T with conjugacy Φ: ℤ_{2} → ℤ_{2}, and so T_{A,B} is conjugate to T with conjugacy h = Φ ∘ PV.

This proves Theorem 2. Corollary 3 follows immediately as a special case since T_{q} = T_{1+q,1}.

2.2 Proof of Theorem 5

To determine which T_{A,B} are conjugate to T via a conjugacy that maps polynomials to positive integers, we can first ask which T_{A,B} have a polynomial 2-cycle, since such a 2-cycle will be unique and correspond to the unique 2-cycle {1, 2} for T.

Lemma 13. The unique 2-cycle for T_{A,B} is \{\frac{B}{A+q^{2}} , \frac{qB}{A+q^{2}} \}, and its fixed points are 0 and

\frac{B}{A+q}.

Proof. Since T_{A,B} is conjugate to the shift map, it must also have a unique 2-cycle and two fixed points. These elements must all satisfy T_{A,B}(T_{A,B}(x)) = x. If both x and T_{A,B}(x) are even, then x = T_{A,B}(T_{A,B}(x)) = (x/q)/q, so x = 0. If both x and T_{A,B}(x) are odd, then x = T_{A,B}(T_{A,B}(x)) = (A((Ax+B)/q)+B)/q, so x = \frac{B}{A+q}. Finally, if x is even and T_{A,B}(x) is odd, then x = T_{A,B}(T_{A,B}(x)) = (A((x/q) + B)/q, so x = \frac{qB}{A+q^{2}} and T_{A,B}(x) = \frac{B}{A+q^{2}} (reversing the parities just swaps x and T_{A,B}(x)).

Thus, the 2-cycle of T_{A,B} will consist of polynomials whenever \frac{B}{A+q^{2}} is a polynomial, i.e., whenever B is a polynomial multiple of A + q^{2}. The simplest example of this family of dynamical systems is when A = 1 and B = 1 + q^{2}. In that case, the 2-cycle of T_{1,1+q^{2}} is {1, q} and its fixed points are 0 and 1 + q. Thus, to prove Theorem 5 it suffices to show that every polynomial eventually enters either the 2-cycle or one of the two fixed points, and that T_{1,1+q^{2}} maps every polynomial, and only polynomials, to other polynomials.

Proof (of Theorem 5). Let x ∈ F_{2}[[q]] be a polynomial of degree n > 1. If x is even then T_{1,1+q^{2}}(x) = x/q is a polynomial of degree n − 1. If x is odd then x = P + q^{n} for some odd polynomial P of degree less than n (i.e., P = x + q^{n}). So

T_{1,1+q^{2}}(x) = T_{1,1+q^{2}}(P + q^{n})

= \frac{(P + q^{n}) + 1 + q^{2}}{q}

= \frac{1 + P}{q} + q + q^{n−1}.

But (1 + P)/q + q + q^{n−1} is either 0 or is a polynomial of degree less than n because P is odd.

In both cases, the degree of T_{1,1+q^{2}}(x) is strictly less than the degree of x. So the T_{1,1+q^{2}}- orbit of every polynomial of degree greater than 1 is a sequence of polynomials of decreasing degrees and thus must eventually reach 0, 1, q, or 1 + q, which are the two fixed points and the two elements of the 2-cycle as claimed.

For the second part of the theorem, let x ∈ F_{2}[[q]]. If x is an even polynomial, then x = qP for some polynomial P, so T_{A,B}(x) = x/q = qP/q = P is a polynomial. If x is odd then x = 1+qP for some polynomial P, so T_{1,1+q^{2}}(x) = T_{1,1+q^{2}}(1+qP) = (1+qP +1+q^{2})/q = P +q which is also a polynomial.

Conversely, let x ∈ F_{2}[[q]] such that T_{1,1+q^{2}}(x) is a polynomial. If x is even then T_{1,1+q^{2}}(x) = x/q, so x = qT_{1,1+q^{2}}(x) is a polynomial. Similarly, if x is odd then T_{1,1+q^{2}}(x) = (x + 1 + q^{2})/q so x = qT_{1,1+q^{2}}(x) + 1 + q^{2} which, once again, is a polynomial.

This completes the proof.

In conclusion, recent authors have shown that the map T_{q} on F_{2}[q] has the property that the T_{q}-orbit of every polynomial contains 1. This does not prove the original 3x + 1 conjecture, however, because the correspondence ξ between nonzero polynomials and positive integers is not a conjugacy of discrete dynamical systems.

By extending the domains of T_{q} and T to F_{2}[[q]] and ℤ_{2}, respectively, we find that T_{q} and T are actually conjugate as discrete dynamical systems, but not via a conjugacy that maps polynomials to positive integers. This result extends to an infinite family of maps on F_{2}[[q]] which are all conjugate to T, and some of these, such as T_{1,1+q^{2}}, do have the property that the positive integers whose T -orbit contains 1 correspond to polynomials.

By applying the correspondence ξ to the polynomials that correspond to the positive integers whose T -orbit contains 1, we obtain the sequence ξ(H(n)) that starts with

1, 2, 47, 4, 21, 94, 2763, 8, 11049, 42, 1383, 188, 173, 5526, 5427, 16, 689, 22098, 22143, 84, …

Showing that every term in this sequence is an integer, or equivalently, proving that every positive integer corresponds to a polynomial via a conjugacy with T_{1,1+q^{2}}, would resolve the original 3x + 1 conjecture.

\begin{matrix}n & ξ(h(n)) & h(n) \\ 1 & −3/7 & (1 + q) · \frac{1}{(1+q^{3})} \\ 2 & −6/7 & (q + q^{2}) · \frac{1}{(1+q^{3})} \\ 3 & −13/7 & 1 + (1 + q^{2}) · \frac{q^{2}}{(1+q^{3})} \\ 4 & −12/7 & (q + q^{2}) · \frac{q}{(1+q^{3})} \\ 5 & 9/7 & 1 + q + (1 + q) · \frac{q^{2}}{(1+q^{3})} \\ 6 & −26/7 & q + (1 + q^{2}) · \frac{q^{3}}{(1+q^{3})} \\ 7 & −175/9 & 1 + q^{3} + (q^{3} + q^{4} + q^{5}) · \frac{q^{5}}{(1+q^{6})} \\ 8 & −24/7 & (q + q^{2}) · \frac{q^{2}}{(1+q^{3})} \\ 9 & 1187/65 & 1 + q + q^{5} + (1 + q + q^{2} + q^{3} + q^{5} + q^{10}) · \frac{q^{6}}{(1+q^{12})} \\ 10 & 18/7 & q + q^{2} + (1 + q) · \frac{q^{3}}{(1+q^{3})} \\ 11 & −37/7 & 1 + q^{2} + q^{3} + q^{2} · \frac{q^{5}}{(1+q^{3})} \\ 12 & −52/7 & q^{2} + (1 + q^{2}) · \frac{q^{4}}{(1+q^{3})} \\ 13 & −31/7 & 1 + q + q^{2} + (1 + q^{2}) · \frac{q^{4}}{(1+q^{3})} \\ 14 & −350/9 & q + q^{4} + (q^{3} + q^{4} + q^{5}) · \frac{q^{6}}{(1+q^{6})} \\ 15 & −359/9 & 1 + q^{4} + (q^{3} + q^{4} + q^{5}) · \frac{q^{6}}{(1+q^{6})} \\ 16 & −48/7 & (q + q^{2}) · \frac{q^{3}}{(1+q^{3})} \\ 17 & −115/7 & 1 + q + q^{3} + (q + q^{2}) · \frac{q^{5}}{(1+q^{3})} \\ 18 & 2374/65 & q + q^{2} + q^{6} + (1 + q + q^{2} + q^{3} + q^{5} + q^{10}) · \frac{q^{7}}{(1+q^{12})} \\ 19 & 2309/65 & 1 + q^{2} + q^{6} + (1 + q + q^{2} + q^{3} + q^{5} + q^{10}) · \frac{q^{7}}{(1+q^{12})} \\ 20 & 36/7 & q^{2} + q^{3} + (1 + q) · \frac{q^{4}}{(1+q^{3})} \end{matrix}

Table 1: The power series in F_{2}[[q]] that correspond to the first twenty positive integers n via any parity-preserving conjugacy h: ℤ_{2} → F_{2}[[q]] between T and T_{q}.

\begin{matrix}n & ξ(H(n)) & H(n) \\ 1 & 1 & 1 \\ 2 & 2 & q \\ 3 & 47 & q^{5} + q^{3} + q^{2} + q + 1 \\ 4 & 4 & q^{2} \\ 5 & 21 & q^{4} + q^{2} + 1 \\ 6 & 94 & q^{6} + q^{4} + q^{3} + q^{2} + q \\ 7 & 2763 & q^{11} + q^{9} + q^{7} + q^{6} + q^{3} + q + 1 \\ 8 & 8 & q^{3} \\ 9 & 11049 & q^{13} + q^{11} + q^{9} + q^{8} + q^{5} + q^{3} + 1 \\ 10 & 42 & q^{5} + q^{3} + q \\ 11 & 1383 & q^{10} + q^{8} + q^{6} + q^{5} + q^{2} + q + 1 \\ 12 & 188 & q^{7} + q^{5} + q^{4} + q^{3} + q^{2} \\ 13 & 173 & q^{7} + q^{5} + q^{3} + q^{2} + 1 \\ 14 & 5526 & q^{12} + q^{10} + q^{8} + q^{7} + q^{4} + q^{2} + q \\ 15 & 5427 & q^{12} + q^{10} + q^{8} + q^{5} + q^{4} + q + 1 \\ 16 & 16 & q^{4} \\ 17 & 689 & q^{9} + q^{7} + q^{5} + q^{4} + 1 \\ 18 & 22098 & q^{14} + q^{12} + q^{10} + q^{9} + q^{6} + q^{4} + q \\ 19 & 22143 & q^{14} + q^{12} + q^{10} + q^{9} + q^{6} + q^{5} + q^{4} + q^{3} + q^{2} + q + 1 \\ 20 & 84 & q^{6} + q^{4} + q^{2} \end{matrix}

Table 2: The polynomials in F_{2}[[q]] that correspond to the first twenty positive integers n via any parity-preserving conjugacy H: ℤ_{2} → F_{2}[[q]] between T and T_{1,1+q^{2}}.

References

[1] A. Behajaina and E. Paran, The Collatz problem in F_{p}[x] and F_{p}[[x]], Finite Fields Appl.

   91 (2023), https://doi.org/10.1016/j.ffa.2023.102265

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

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

[4] K. G. Monks and J. Yazinski, The autoconjugacy of the 3x + 1 function, Discrete Math. 275 (2004), 219–236.

[5] D. Nichols, Analogues of the 3x + 1 problem in polynomial rings of characteristic 2, Exp. Math. 27 (2018), 100–110.

[6] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2025. Available

   at https://oeis.org.

[7] B. Snapp and M. Tracy, The Collatz problem and analogues, J. Integer Sequences 11 (2008), Article 08.4.7.

[8] G. Wirsching, The Dynamical System Generated by the 3n+1 Function, Springer-Verlag, 1998.

2020 Mathematics Subject Classification: Primary 11B83; Secondary 11B37, 37B10. Keywords: Collatz conjecture, q-series.

Received September 20 2025; revised version received November 17 2025. Published in Journal of Integer Sequences, November 27 2025.

Return to Journal of Integer Sequences home page.