A NON-ITERATIVE 2-ADIC STATEMENT

OF THE 3N + 1 CONJECTURE

Daniel J. Bernstein

9/21/92

Abstract. Associated with the 3N + 1 problem is a permutation Φ of the 2-adic integers. The 3N +1 conjecture is equivalent to the conjecture that 3Q is an integer if Φ(Q) is a positive integer. We state a new definition of Φ. To wit: Q and N = Φ(Q) are linked by the equations Q = 2^{d_{0}} + 2^{d_{1}} + ⋯ and N = (−1/3)2^{d_{0}} + (−1/9)2^{d_{1}} + (−1/27)2^{d_{2}} + ⋯ with 0 ≤ d_{0} < d_{1} < · · ·. We list four applications of this definition.

Definition and conjecture

Proceedings of the American Mathematical Society 121 (1994), 405–408. We recall that the 2-adic integers Z_{2} may be defined as binary expansions which are allowed to extend infinitely far to the left [3, Ex. 4.1–31]: for instance, 1/3 = (… 0101011)_{2} ∈ Z_{2}. Fix odd 2-adic integers u_{0}, u_{1}, … ∈ 1 + 2Z_{2}. For any increasing, finite or infinite, sequence 0 ≤ d_{0} < d_{1} < ⋯ of nonnegative integers, the sum ∑ u_{i}2^{d_{i}} converges to some 2-adic integer S. In fact this map from increasing sequences to sums is one-to-one and onto all of Z_{2}. We construct its inverse. Given S ∈ Z_{2} we set d_{0} to the first bit position in S, d_{1} to the first bit position in S − u_{0}2^{d_{0}}, and so on. If at any point S − u_{0}2^{d_{0}} − ⋯ − u_{n}2^{d_{n}} is zero, we stop, and the sequence is finite.

As an example, the expansion

(1)  Q = 2^{d_{0}} + 2^{d_{1}} + ⋯

is a bijection between Q ∈ Z_{2} and increasing sequences d = ⟨d_{0}, d_{1}, … ⟩. Finite sequences d correspond to nonnegative integers Q. (In particular the empty sequence corresponds to Q = 0.) Similarly, the expansion

(2)  N = \frac{−1}{3}2^{d_{0}} + \frac{−1}{9}2^{d_{1}} + \frac{−1}{27}2^{d_{2}} + ⋯

is another bijection. Together (1) and (2) determine a bijection between all N ∈ Z_{2} and all Q ∈ Z_{2}. We write N = Φ(Q). For instance,

(3)  Φ(−\frac{1}{3}) = Φ(2^{0} + 2^{2} + 2^{4} + ⋯) = \frac{−1}{3}2^{0} + \frac{−1}{9}2^{2} + \frac{−1}{27}2^{4} + ⋯ = 1

by elementary geometric series manipulations. So 1 ∈ Φ((1/3)Z).

Conjecture. The set Z^{+} of positive integers is contained in Φ((1/3)Z).

Typeset by AMS-TEX

1991 Mathematics Subject Classification. Primary 11D72.

The author was supported in part by a National Science Foundation Graduate Fellowship. He would also like to thank Bellcore for the use of their facilities in preparing this document.

Connection with the 3N + 1 problem

We define two functions H(Q) and C(N). If Q is even we set H(Q) = Q/2; otherwise we set H(Q) = Q − 1. If N is even we set C(N) = N/2; otherwise we set C(N) = 3N + 1.

Theorem 1. C(Φ(Q)) = Φ(H(Q)).

Proof. We define d as in (1). If Q is even then d_{0} > 0 (or d has length 0) and

C(Φ(Q)) = \frac{−1}{3}2^{d_{0}−1} + \frac{−1}{9}2^{d_{1}−1} + ⋯ = Φ(2^{d_{0}−1} + 2^{d_{1}−1} + ⋯) = Φ(Q/2).

If Q is odd then d_{0} = 0 and

\begin{aligned}C(Φ(Q)) & = 1 + 3(\frac{−1}{3} + \frac{−1}{9}2^{d_{1}} + \frac{−1}{27}2^{d_{2}} ⋯) = \frac{−1}{3}2^{d_{1}} + \frac{−1}{9}2^{d_{2}} + ⋯ \\ & = Φ(2^{d_{1}} + 2^{d_{2}} + ⋯) = Φ(Q − 2^{d_{0}}) = Φ(Q − 1) \end{aligned}

as desired. □

The 3N + 1 conjecture [4] states that, for any positive integer N ∈ Z^{+}, some iterate C^{k}(N) equals 1. This implies our conjecture:

Theorem 2. If C^{k}(N) = 1 then N ∈ Φ((1/3)Z).

Proof. Set Q = Φ^{−1}(N). Now C^{k}(Φ(Q)) = 1 so Φ(H^{k}(Q)) = 1 so H^{k}(Q) = Φ^{−1}(1) = −1/3 ∈ (1/3)Z. If H(x) ∈ (1/3)Z then x ∈ (1/3)Z, so by induction Q ∈ (1/3)Z as desired. □

The converse is also true: our conjecture implies the 3N + 1 conjecture.

Theorem 3. If N ∈ Z^{+} and N ∈ Φ((1/3)Z) then C^{k}(N) = 1 for some k.

Proof. Again set Q = Φ^{−1}(N) and define d by (1) and (2). We have 3Q ∈ Z. Notice first that Q cannot be an integer. For if Q ∈ Z then either Q = 0, in which case N = 0; or Q is positive, in which case d is finite and N is a negative rational number by (2); or Q is negative, in which case d_{i+1} = d_{i} + 1 for all large i and so (2) again converges to a negative rational number.

So Q is 1/3 away from an integer. Thus the d_{i}’s eventually fall into the pattern d_{i+1} = d_{i} + 2, say for i ≥ m. Define a map c on d corresponding to the action of C on N. Notice that c acts on d by subtracting 1 from each element, if d_{0} > 0; or by shifting d to the left, if d_{0} = 0. So

c^{d_{m}+m}(⟨d_{0}, …, d_{m−1}, d_{m}, d_{m} + 2, d_{m} + 4, … ⟩) = ⟨0, 2, 4, … ⟩ ,

and C^{d_{m}+m}(N) = 1. □

Hence our conjecture about the 2-adic expansions (1) and (2) is equivalent to the 3N + 1 conjecture. Does this throw any light on the latter? Our map Φ is exactly the inverse of Q_{∞} in [4]. (This can alternatively be derived from Lemma 4 in [5].) Our Theorem 1, that Φ conjugates H to C, is equivalent to Theorem 1 of [1]. What is new here is the expansion (2). It gives an explicit formula for Φ = Q_{∞}^{−1}. We have therefore answered affirmatively the final question in [4].

Applications

Our result has several immediate applications. First, say Q ∈ Q ∩ Z_{2} is rational. Then either d is finite (say of length μ) or d_{m+λ} = d_{m} + X for all sufficiently large m (say m ≥ μ) and some fixed λ and X. In the first case 3^{μ}N is an integer. In the second case

−3^{μ}(3^{λ} − 2^{X})N = (3^{λ} − 2^{X})(3^{μ−1}2^{d_{0}} + ⋯ + 3^{0}2^{d_{μ−1}}) + (3^{λ−1}2^{d_{μ}} + ⋯ + 3^{0}2^{d_{μ+λ−1}})

by (2). So in either case N is rational.

Corollary 1. Φ(Q ∩ Z_{2}) ⊆ Q ∩ Z_{2}.

The “Periodicity Conjecture” from [4] states that Φ(Q ∩ Z_{2}) = Q ∩ Z_{2}. We have shown half of this.

Second, in our development of Φ we noted that Φ is a bijection from Z_{2} onto itself, i.e., a permutation of Z_{2}. In fact we see from (1) and (2) that Φ is a homeomorphism under the topology induced by the usual 2-adic metric (see [4, section 2.8]). So Theorem L of [4] follows immediately.

Third, from (1) and (2) we see that the function Q_{k}(N) = Φ^{−1}(N) mod 2^{k} depends only on the equivalence class N mod 2^{k}. This is the first half of Theorem B from [4]. The induced function \overline{Q}_{k} on equivalence classes is a permutation because Φ is. By induction the cycles of \overline{Q}_{k} are of length dividing 2^{k}. Indeed, any cycle of \overline{Q}_{k} of length r gives rise to either one cycle of \overline{Q}_{k+1} of length 2r or two cycles of \overline{Q}_{k+1} of length r. This is the second half of Theorem B from [4].

Finally, we give a short proof of the following theorem of Müller [5]:

Corollary 2. Φ is nowhere differentiable.

Proof. If d is infinite then for any k ≥ 0

\frac{Φ(Q) − Φ(Q − 2^{d_{k}})}{2^{d_{k}}} ≡ (−1)^{k} (mod 4)

by routine computation from (2). So as k → ∞ the difference ratio does not converge. If d is finite, say of length m, then for e + f > e > d_{m−1}

\frac{Φ(Q) − Φ(Q + 2^{e} + 2^{e+f})}{2^{e} + 2^{e+f}} = \frac{1}{3^{m+2}} \frac{3 + 2^{f}}{1 + 2^{f}}

again by routine computation; and the latter quantity is different mod 8 for f = 1, 2. So as e → ∞ the difference ratio does not converge. Hence both Φ and its inverse are nowhere differentiable. □

Note that our approach generalizes to the “AN + B problem” [2] [6]. In this generalization A and B are odd, and N = Φ_{A,B}(Q) = ∑(−B/A^{i+1})2^{d_{i}}. This homeomorphism Φ_{A,B} conjugates H to C_{A,B}, where C_{A,B}(N) equals N/2 for N even and AN + B for N odd.

Acknowledgments

The author would like to thank Jeffrey C. Lagarias and an anonymous referee for their helpful suggestions.

References

1. Ethan Akin, 3x + 1, unpublished manuscript.

2. R. E. Crandall, On the 3x + 1 Problem, Math. Comp. 32 (1978), 1281–1292.

3. Donald E. Knuth, The Art of Computer Programming, volume 2: Seminumerical Algorithms, 2nd. ed., Addison-Wesley, Reading, Massachusetts, 1981.

4. Jeffrey C. Lagarias, The 3x + 1 Problem and Its Generalizations, Amer. Math. Monthly 92 (1985), 3–23.

5. Helmut Müller, Das 3n+1 Problem, Mitteilungen der Math. ges. Hamburg 12 (1991), 231–251.

6. Ray P. Steiner, On the Qx + 1 problem, Q odd, II, Fibonacci Quarterly 19 (1981), 293–296.

5 Brewster Lane, Bellport, NY 11713