PSEUDOPERIODICITY AND THE 3x + 1 CONJUGACY FUNCTION

JONATHAN YAZINSKI

Abstract. The 3x+1 function T : ℕ → ℕ is defined by T (x) = \frac{3x+1}{2} for x odd and T (x) = \frac{x}{2} for x even. The function T has a natural extension to the 2-adic integers ℤ_{2} and there is a continuous function Φ which conjugates T to the 2-adic shift map σ. Bernstein and Lagarias conjectured that −1 and \frac{1}{3} are the only odd fixed points of Φ. In this paper we investigate periodicity associated with Φ, a property of the map which is a natural extention of solenoidality. We use it to show that there are nontrivial infinite families of 2-adics that are not fixed points of Φ. In particular, we prove that three sequences of farPoints of 2-adics are finitely pseudoperiodic, providing more evidence supporting the Φ Fixed Point Conjecture.

1. Introduction

Let ℤ_{2} denote the ring of 2-adic integers. If x ∈ ℤ_{2} with x = ∑^{∞} ; i=0d_{i}2^{i} with d_{i} ∈ {0, 1}, we write

x = d_{0}d_{1}d_{2} · · · . Define the 3x + 1 function T : ℤ_{2} → ℤ_{2} as follows.

T (x) = \{ \begin{matrix}\frac{3x+1}{2} & if x is odd \\ \frac{x}{2} & if x is even \end{matrix}

The famous 3x + 1 conjecture states that for every x ∈ ℕ^{+} there is some k ∈ ℕ^{+} such that the k-th iterate T^{k} (x) = 1, i.e. the conjecture asserts that the T -orbit of every positive integer will eventually enter the cycle {1, 2}. Define the 2-adic shift map σ : ℤ_{2} → ℤ_{2} by

σ (x) = \{ \begin{matrix}\frac{x−1}{2} & if x is odd \\ \frac{x}{2} & if x is even \end{matrix}

so that σ (d_{0}d_{1} ⋯) = d_{1}d_{2} · · · . Hence σ just removes the first digit of a 2-adic integer^{1}. There is a continuous bijective map Φ : ℤ_{2} → ℤ_{2} such that the following diagram commutes:

(1.1)  \begin{matrix}ℤ_{2} & ⟶^{σ} & ℤ_{2} \\ Φ ↓ & & Φ ↓ \\ ℤ_{2} & ⟶^{T} & ℤ_{2} \end{matrix}

so that Φ ∘ σ = T ∘ Φ [2]. The map Φ is solenoidal, that is, x ≡_{2^{n}} y ⇒ Φ (x) ≡_{2^{n}} Φ (y) [1] (where ≡_{2^{n}}

denotes congruence mod 2^{n}). In fact, Φ induces permutations on ℤ⧸2^{n}ℤ.

An explicit formula for Φ was discovered by Bernstein [3], but a convenient one is not known for its inverse. If x = ∑_{i}2^{d_{i}}, with 0 ≤ d_{0} < d_{1} < ⋯, then

(1.2)  Φ (x) = −∑_{i}2^{d_{i}}3^{−i}

Date: April 15, 2003.

1991 Mathematics Subject Classification. 11B75.

Key words and phrases. 3x + 1 problem, conjugacy, fixed points, Collatz problem.

1σ is called S in [1]

It follows from the conjugacy in (1.1) that the inverse map is given by

Φ^{−1} (x) = ∑^{∞} ; i=0 (T^{i} (x) Mod 2) 2^{i}

and we say that Φ^{−1} maps a 2-adic to its parity vector^{2}.

Many of the interesting properties of the 3x + 1 conjugacy function do not lead to an apparent solution to the 3x + 1 problem [1]. The map Φ seems to inherit much of the problematic nature of T, and the authors of [1] have proposed the seemingly equally intractable

Φ Fixed Point Conjecture: The only odd fixed points of Φ are −1 and \frac{1}{3}.

From (1.2), we see that Φ (2^{k}x) = 2^{k}Φ (x) so that every even fixed point of Φ is either 0 or 2^{k}x, where x is an odd fixed point. There is another more general conjecture proposed in [1] stating that for any given 2 power, Φ will have finitely many odd periodic points whose period is that 2 power.

2. Main Results

We now provide evidence supporting the Φ Fixed Point Conjecture by demonstrating a periodicity associated with Φ and a related property which we will call pseudoperiodicity. Solenoidality allows us to study the action of Φ on the first k digits of a 2-adic; however, periodicity will allow us to look at beginning of the infinite “tail” end. First, we define what it means for a sequence to be pseudoperiodic.

Definition 2.1. Let X be a set, and let {a_{n}} be a sequence (where a : ℕ → X). For all n ∈ ℕ we say that the n-th term a_{n} is pseudoperiodic if

∃m ∈ ℕ ∀r∈ ℕ^{+} a_{n+mr} = a_{n}

We say that the sequence {a_{n}} is pseudoperiodic if all of its terms are pseudoperiodic.

We will also say that the sequence {a_{n}}_{n≥k} is pseudoperiodic if we replace “For all n ∈ ℕ” in the above definition with “For all n ≥ k”. It will be convenient in some applications to take X ∪ {∞} , where X ⊆ ℝ to be the codomain of a and say that in this case {a_{n}} is finitely pseudoperiodic when all terms a_{n} ≠ ∞ are pseudoperiodic.

Hence a sequence is pseudoperiodic if for every term in the sequence, there is some period m with which that term will repeat in the sequence. For example, every periodic sequence is pseudoperiodic. For a somewhat less trivial example, consider b : ℕ → ℕ, where b_{n} is defined to be the smallest positive prime dividing n + 2. The pseudoperiodicity of this sequence is reminiscent of the sieve of Eratosthenes.

Because Φ is solenoidal, “the action of Φ on the first k digits of a 2-adic” is well defined. That is, the first k digits of Φ (x) are completely determined by the first k digits of x. Therefore we can classify non-fixed points by their congruence class mod 2^{k}. In fact, we will say that x is a fixed point of Φ mod 2^{k} when Φ (x) ≡_{2^{k}} x. Consequently, whenever x is a fixed point mod 2^{k}, we can ask

how many more digits r are needed so that there is no fixed point mod 2^{k+r} having the same first k digits as x. This motivates the following definition.

2As given in [1], the formula for Φ^{−1} (x) uses mod instead of Mod, but throughout the course of this paper we will keep the convention that for z ∈ ℤ_{2} and k ∈ ℕ, z Mod 2^{k} will be the least m ∈ ℕ such that m ≡_{2^{k}} z.

Definition 2.2. For k ∈ ℕ and x ∈ ℕ ⊆ ℤ_{2} with x < 2^{k}, define

fP (x, k) = min {r ∈ ℕ | ∀z ∈ ℤ_{2}, z ≡_{2^{k}} x ⇒ Φ (z) ≢_{2^{k+r}} z}

when the minimum exists, and ∞ otherwise.

That is, fP (x, k) is the smallest number of digits r needed so that no 2-adic agreeing with x on the first k digits will be a fixed point of Φ mod 2^{k+r}. We call fP (x, k) the farPoint of x on the first k digits.

Example 2.3. If Φ (x) ≢_{2^{k}} x then fP (x, k) = 0. The converse is also true.

Example 2.4. fP (0, k) = ∞ for any k, since Φ (0) = 0.

Example 2.5. Since Φ (1) ≡_{2^{2}} 1 and Φ (1) ≡_{2^{3}} 5 we have that fP (1, 2) ≠ 0 and fP (1, 2) = 1.

For x ∈ ℤ_{2}, denote L_{k} (x) = x Mod 2^{k} and R_{k} (x) = σ^{k} (x) . L_{k} (x) and R_{k} (x) will be called the (k-)left and (k-)right parts of x, respectively. Thus, if x = d_{0}d_{1} ⋯ d_{k−1}d_{k} ⋯, then L_{k} (x) = d_{0}d_{1} ⋯ d_{k−1} and R_{k} (x) = d_{k}d_{k+1} · · · . So, for example, L_{3} (\frac{1}{3}) = 3 and R_{3} (\frac{1}{3}) = −\frac{1}{3}, since \frac{1}{3} = 1101010 ⋯ and −\frac{1}{3} = 101010 · · · . With these definitions we are able to state our first result.

Theorem 2.6. Fix H ≥ 3 and q ∈ ℚ∩ℤ_{2}. Then the sequence {L_{H}R_{n}ΦL_{n} (q)} is eventually periodic.

We call the property of Φ exhibited in this theorem the periodicity of Φ. We can use this property to make progress on the Fixed Point Conjecture by showing that certain sequences of farPoints are pseudoperiodic.

Theorem 2.7. The sequence {fP (2^{n} − 1, n + 1)} is finitely pseudoperiodic.

If the Φ Fixed Point Conjecture is true, then all terms in the above sequence will be finite (and hence pseudoperiodic) except for when n = 0, 2. Any odd x ∈ ℤ_{2} − \{\frac{1}{3}, −1\} that is a fixed point of Φ will agree with either −1 or \frac{1}{3} on a finite number of digits. Direct calculation shows that such a fixed point x must agree with one of these fixed points on at least its first 100 digits. Theorem 2.7 corresponds to those potential fixed points whose initial segments agree with −1 on a finite number of digits. We have an analogous theorem for \frac{1}{3}:

Theorem 2.8. The sequences {fP (1 + ∑^{n} ; i=02^{2i+1}, 2n + 4)} and {fP (1 + (∑^{n} ; i=02^{2i+1}) + 2^{2n+2}, 2n + 3)}

are finitely psuedoperiodic.

Note that \frac{1}{3} = 1+ ∑^{∞} ; i=02^{2i+1}. Knowing that a particular value of farPoint is finite in any of the three

sequences in Theorems 2.7 and 2.8 yields an infinite family of non-fixed points of Φ. In particular, the above theorems imply

Corollary 2.9. If there are no fixed points of the form \overbrace{11 ⋯ 1} 0^{n ones} ⋯ (respectively, 11 \overbrace{010 ⋯ 10} 0^{n ones} ⋯

or 11 \overbrace{010 ⋯ 1} 1^{n ones} ⋯), then there will be some h such that for every r ∈ N, there will be no fixed point

of the form \overbrace{1111 ⋯ 1} 0^{n+rh ones} ⋯ (respectively, 11 \overbrace{010 ⋯ 10}^{n+rh ones}0 ⋯ or 11 \overbrace{010 ⋯ 1}^{n+rh ones}1 ⋯).

Interestingly, the h in Corollary 2.9 turns out to be a 2 power in every case. Some values of farPoint are listed in 1, from which we obtain an immediate example of the pseudoperiodicity from Theorem 2.7.

\begin{matrix}n & fP_{n} \\ 1 & 1 \\ 2 & ∞ \\ 3 & 1 \\ 4 & 7 \\ 5 & 1 \\ 6 & 10 \\ 7 & 1 \\ 8 & 29 \\ 9 & 1 \end{matrix} \begin{matrix}n & fP_{n} \\ 10 & 5 \\ 11 & 1 \\ 12 & 18 \\ 13 & 1 \\ 14 & 11 \\ 15 & 1 \\ 16 & 83 \\ 17 & 1 \\ 18 & 75 \end{matrix} \begin{matrix}n & fP_{n} \\ 19 & 1 \\ 20 & 8 \\ 21 & 1 \\ 22 & 6 \\ 23 & 1 \\ 24 & 11 \\ 25 & 1 \\ 26 & 5 \\ 27 & 1 \end{matrix} \begin{matrix}n & fP_{n} \\ 28 & 6 \\ 29 & 1 \\ 30 & 12 \\ 31 & 1 \\ 32 & 62 \\ 33 & 1 \\ 34 & 13 \\ 35 & 1 \\ 36 & 15 \end{matrix} \begin{matrix}n & fP_{n} \\ 37 & 1 \\ 38 & 11 \\ 39 & 1 \\ 40 & 10 \\ 41 & 1 \\ 42 & 5 \\ 43 & 1 \\ 44 & 10 \\ 45 & 1 \end{matrix} \begin{matrix}n & fP_{n} \\ 46 & 7 \\ 47 & 1 \\ 48 & 13 \\ 49 & 1 \\ 50 & 8 \\ 51 & 1 \\ 52 & 9 \\ 53 & 1 \\ 54 & 6 \end{matrix} \begin{matrix}n & fP_{n} \\ 55 & 1 \\ 56 & 37 \\ 57 & 1 \\ 58 & 5 \\ 59 & 1 \\ 60 & 6 \\ 61 & 1 \\ 62 & 13 \\ 63 & 1 \end{matrix} \begin{matrix}n & fP_{n} \\ 64 & 45 \\ 65 & 1 \\ 66 & 10 \\ 67 & 1 \\ 68 & 7 \\ 69 & 1 \\ 70 & 12 \\ 71 & 1 \\ 72 & 9 \end{matrix}

Table 1. Values of fP_{n} = fP (2^{n} − 1, n + 1) for n from 1 to 72

Example 2.10. We see that we can have no Φ fixed point of the form 1110 ⋯ from Table 1, and in this case we have that the h in Corollary 2.9 will be equal to 2. So there will be no fixed points of

the form 111110 ⋯, 11111110 ⋯, or in general \overbrace{1111 ⋯ 1} 0^{1+2r ones} ⋯ for any r ∈ ℕ, so that there is no fixed point of Φ whose digit expansion will have an odd number of ones followed by a zero.

We will see why h = 2 is the period of this value of farPoint in the proof of Theorem 2.7 in the next section. Continuing the table further would illustrate the pseudoperiodicity of all of these farPoints. For example, fP (2^{10} − 1, 11) is pseudoperiodic with period h = 2^{5−1} = 16, as seen by the farPoint value of 5 for n = 10, 26, 42, 58 in the above table.

3. Pseudohomomorphism and Φ Periodicity

Here we discuss some general properties of Φ that will be used in the proofs of our main results.

If x ∈ ℕ ⊆ ℤ_{2}, then we define α (x) = ∑^{∞} ; i=0d_{i} where x = d_{0}d_{1} · · · . The following theorem shows

that, with sufficient restrictions, Φ acts on the right and left parts of a 2-adic nearly as an additive homomorphism.

Theorem 3.1. Let x ∈ ℤ_{2}, k ∈ ℕ and a ∈ ℕ with a < 2^{k}. Denote m = α (a) . Then

Φ (a + 2^{k}x) = Φ (a) + \frac{Φ (x)}{3^{m}}2^{k}

Proof. If a = 2^{d_{0}} + 2^{d_{1}} + ⋯ + 2^{d_{m−1}} and x = 2^{d_{m}} + 2^{d_{m+1}} + ⋯, with 0 ≤ d_{0} < d_{1} < ⋯ < d_{m−1} and 0 ≤ d_{m} < d_{m+1} < ⋯, then by (1.2),

Φ (a + 2^{k}x) = − ( ∑^{m−1} ; i=02^{d_{i}}3^{−i} + ∑^{∞} ; i=02^{d_{i+m}+k}3^{−(i+m)})

= − ∑^{m−1} ; i=02^{d_{i}}3^{−i} + \frac{2^{k}}{3^{m}} (−∑^{∞} ; i=02^{d_{i+m}}3^{−i})

= Φ (a) + Φ (x) \frac{2^{k}}{3^{m}}
□

Thus, using the (k-)left and (k-)right notation, for any x ∈ ℤ_{2},

(3.1)  Φ (x) = Φ (L_{k} (x)) + \frac{Φ (R_{k} (x))}{3^{m}}2^{k}

for any k, where m = α (L_{k} (x)) . Whenever m is divisible by a positive power of 2, the factor 3^{m} acts as 1 for sufficiently low modulus, so that Φ (a + 2^{k}x) ≡ Φ (a) + Φ (x) 2^{k}, as can be seen in the following Lemma.

Lemma 3.2. Let n ∈ ℕ^{+}. Then 3^{2^{n}} ≡_{2^{n+2}} 1.

Proof. The proof will be by induction. We have that 3^{2} ≡_{2^{3}} 1. For n ∈ ℕ^{+}, assume 3^{2^{n}} ≡_{2^{n+2}} 1. Then

for some k ∈ ℤ, 2^{n+2}k+1 = 3^{2^{n}}, and hence (2^{n+2})^{2} k^{2} +2·2^{n+2}k+1 = 3^{2^{n+1}}. The result follows. □

Recall that ℤ_{2} contains a subring of the rational numbers, namely those with odd denominator when in reduced form. Define ℚ_{odd} = ℚ ∩ ℤ_{2} to be this subring, as in [4]. Then any q ∈ ℚ_{odd} must be of the form q = d_{0}d_{1}d_{2} ⋯ d_{k−1}\overline{d_{k}d_{k+1} ⋯ d_{k+v−1}}. Hence for any q ∈ ℚ_{odd}, there will be some

a, k, b, v ∈ ℕ, with a < 2^{k} and b < 2^{v} such that q = a + 2^{k} (∑^{∞} ; i=0b2^{vi}) . To simplify this, we introduce

the following notation. For b, v, t ∈ ℕ, we denote b̄_{v,t} = b ∑^{t−1} ; i=02^{vi} and b̄_{v,∞} = b∑^{∞} ; i=02^{vi}. In this notation,

q = a + 2^{k}b̄_{v,∞}. There is a strong relationship between the action of Φ on a rational 2-adic and on a 2-adic that results from a truncation after a finite number of its repeating units, as is given by the following theorem.

Theorem 3.3. Let q ∈ ℚ_{odd} and a, k, b, v ∈ ℕ such that a < 2^{k}, b < 2^{v}, and q = a + 2^{k}b̄_{v,∞}. Define m = α (b) . Let t ∈ ℕ^{+}. Then

Φ (a + 2^{k}b̄_{v,t}) = Φ (q) − \frac{Φ \binom{}{b̄_{v,∞}}}{3^{mt+α(a)}}2^{k+tv}

Proof. Clearly L_{k+tv} (q) = a + 2^{k}b̄_{v,t} and R_{k+tv} (q) = b̄_{v,∞}, so by again Theorem 3.1,

Φ (q) = Φ (a + 2^{k}b̄_{v,t} + 2^{k+tv}b̄_{v,∞}) = Φ (a + 2^{k}b̄_{v,t}) + \frac{Φ \binom{}{b̄_{v,∞}}}{3^{mt+α(a)}}2^{k+tv}

□

We also state the analogous theorem for 2-adics whose digits are strictly repeating.

Corollary 3.4. Let v ∈ ℕ^{+}, t ∈ ℕ and let b ∈ ℕ such that b < 2^{k}. Define m = α (b) . Then

Φ \binom{}{b̄_{v,t}} = Φ \binom{}{b̄_{v,∞}} − \frac{Φ \binom{}{b̄_{v,∞}}}{3^{mt}}2^{tv}

Proof. Let q = b̄_{v,∞} in Theorem 3.3 □

Now we present the Φ periodicity result for rational 2-adics. It is well known that Φ (ℚ_{odd}) ⊆ ℚ_{odd}, since if a 2-adic has a rational parity vector, then it is the solution of a linear equation with rational coefficients. Thus Φ of any rational number will have eventually repeating digits. The following result, which does not take into account fixed points, can be used to obtain the desired pseudoperiodicity of the farPoint sequences.

6 JONATHAN YAZINSKI

Theorem 3.5. Let q ∈ ℚ_{odd}, and a, k, b, v ∈ ℕ such that a < 2^{k}, b < 2^{v} and q = a + 2^{k}b̄_{v,∞}. Let

Φ (q) = r_{0}r_{1} ⋯ r_{u−1}\overline{r_{u}r_{u+1} ⋯ r_{u+p−1}}

and choose t such that k + tv ≥ u. Then for all positive integers H,

R_{k+tv}ΦL_{k+tv} (q) ≡_{2^{H+2}} R_{k+(t+p2^{H})v}ΦL_{k+(t+p2^{H})v} (q)

Proof. Define m = α (b) . From Theorem 3.3 we see that

R_{k+tv} (Φ (q Mod 2^{k+tv})) = R_{k+tv} (Φ (a + 2^{k}b̄_{v,t}))
= R_{k+tv} (Φ (q) − \frac{Φ \binom{}{b̄_{v,∞}}}{3^{mt+α(a)}}2^{k+tv})

and also that

R_{k+(t+p2^{H})v} (Φ (q Mod 2^{k+(t+p2^{H})v})) = R_{k+(t+p2^{H})v} (Φ (a + 2^{k}b̄_{v,t+p2^{H}} ))
= R_{k+(t+p2^{H})v} (Φ (q) − \frac{Φ \binom{}{b̄_{v,∞}}}{3^{m(t+p2^{H})+α(a)}} 2^{k+(t+p2^{H})v})

But by Lemma 3.2,

\frac{Φ \binom{}{b̄_{v,∞}}}{3^{mt+α(a)}} ≡_{2^{H+2}} \frac{Φ \binom{}{b̄_{v,∞}}}{3^{mt+α(a)}} \frac{1}{(3^{2^{H}} )^{mp}} = \frac{Φ \binom{}{b̄_{v,∞}}}{3^{m(t+p2^{H})+α(a)}}

Now, since k + tv ≥ u,

R_{k+tv} (Φ (q)) = R_{k+(t+p2^{H})v} (Φ (q))

Since for any y, z ∈ ℤ_{2} and c ∈ ℕ,

(3.2)  R_{c} (y + 2^{c}z) = R_{c} (y) + z

it follows that

R_{k+tv} (Φ (q) − \frac{Φ\binom{}{b̄_{v,∞}}}{3^{mt+α(a)}} 2^{k+tv}) ≡_{2^{H+2}} R_{k+tv}Φ (q) − \frac{Φ\binom{}{b̄_{v,∞}}}{3^{mt+α(a)}}

≡_{2^{H+2}} R_{k+(t+p2^{H})v}Φ (q) − \frac{Φ\binom{}{b̄_{v,∞}}}{3^{m(t+p2^{H})+α(a)}}

≡_{2^{H+2}} R_{k+(t+p2^{H})v} (Φ (q) − \frac{Φ\binom{}{b̄_{v,∞}}}{3^{m(t+p2^{H})+α(a)}} 2^{k+(t+p2^{H})v})

where the first and third lines in particular follow from (3.2), and the result follows. □

There is a similar, simpler, result for strictly repeating 2-adics: Corollary 3.6. Let v ∈ ℕ^{+}, and b ∈ ℕ such that b < 2^{v}. Define m = α (b) . Let

Φ \binom{}{b̄_{v,∞}} = r_{0}r_{1} ⋯ r_{u−1}\overline{r_{u}r_{u+1} ⋯ r_{u+p−1}}

and choose t ∈ ℕ such that tv ≥ u. Then for all positive integers H,

R_{tv} (Φ \binom{}{b̄_{v,t}}) ≡_{2^{H+2}} R_{(t+p2^{H})v} (Φ \binom{}{b̄_{v,t+p2^{H}}})

Proof. Let q = b̄_{v,∞} in Theorem 3.5. □

If q is a fixed point of Φ, then k = u and v = p in Theorem 3.5. We are in a position to prove Theorem 2.6.

4. Proofs of Main Results

Proof of Theorem 2.6. Let q ∈ ℚ_{odd} and a′, k′, b′, v ∈ ℕ such that a′ < 2^{k′}, b′ < 2^{v}, and q = a′ + 2^{k′} \overline{b′}_{v,∞} and let H ≥ 3 be fixed. Let t be the smallest positive natural number such that k′+tv ≥ u, where Φ (q) = r_{0}r_{1} ⋯ r_{u−1}\overline{r_{u}r_{u+1} ⋯ r_{u+p−1}}. Let n ≥ k′+tv, and define l = n−(k′ + tv) . By Theorem 3.5 with k = k′ + l, a = L_{k} (q) , b = L_{v}R_{k} (q) ,

R_{n}ΦL_{n} (q) = R_{k+tv}ΦL_{k+tv} (q)

≡_{2^{H}} R_{k+(t+p2^{H−2})v}ΦL_{k+(t+p2^{H−2})v} (q)

= R_{n+p2^{H−2}v}ΦL_{n+p2^{H−2}v} (q)

Hence L_{H}R_{n}ΦL_{n} (q) = L_{H}R_{n+p2^{H−2}v}ΦL_{n+p2^{H−2}v} (q) . Therefore the sequence {L_{H}R_{n}ΦL_{n} (q)}_{n≥k′+tv} is periodic. □

From Corollary 3.6, the result that {fP (2^{n} − 1, n + 1)} is pseudoperiodic follows. To see this, we will consider 2-adics whose first n digits agree with those of the fixed point −1.

Proof of Theorem 2.7. Let n ∈ ℕ and assume that the farPoint of 2^{n} − 1 on the first n + 1 digits is finite. Let f = fP (2^{n} − 1, n + 1) and H ≥ max {1, f − 1} . So there is no z ∈ ℤ_{2} such that z ≡_{2^{n+1}} 2^{n} − 1 and Φ (z) ≡_{2^{n+1+f}} z, by definition of farPoint. Let y ∈ ℤ_{2} be arbitrary and define

z = 2^{n} − 1 + 2^{n+1}y and z′ = 2^{n+2^{H}} − 1 + 2^{n+1+2^{H}} y

Then z is not a fixed point of Φ mod 2^{n+1+f}, and by Theorem 3.1, Φ (z) = Φ (2^{n} − 1) + \frac{Φ(2y)}{3^{n}}2^{n}.

Similarly, Φ (z′) = Φ (2^{n+2^{H}} − 1) + \frac{Φ(2y)}{3^{n+2^{H}}} 2^{n+2^{H}} . Furthermore, since 3^{2^{H}} ≡_{2^{H+2}} 1 by Lemma 3.2 and

R_{n+2^{H}} Φ (2^{n+2^{H}} − 1) ≡_{2^{H+2}} R_{n}Φ (2^{n} − 1) by Corollary 3.6, letting b = v = 1, again using (3.2),

R_{n+2^{H}} Φ (z′) ≡_{2^{H+2}} R_{n+2^{H}} Φ (2^{n+2^{H}} − 1) + \frac{Φ(2y)}{3^{m+2^{H}}}

≡_{2^{H+2}} R_{n}Φ (2^{n} − 1) + \frac{Φ(2y)}{3^{m}}

≡_{2^{H+2}} R_{n}Φ (z)

Furthermore, it is clear from how we have defined z and z′ that R_{n} (z) = 2y = R_{n+2^{H}} (z′) . Now, by definition of farPoint, R_{n} (Φ (z)) ≢_{2^{f+1}} R_{n} (z) , and hence we have that

R_{n+2^{H}} (Φ (z′)) ≡_{2^{H+2}} R_{n} (Φ (z)) ≢_{2^{f+1}} R_{n} (z) ≡_{2^{H+2}} R_{n+2^{H}} (z′)

Thus fP (2^{n+2^{H}} − 1, n + 1 + 2^{H}) ≤ f.

To show the other inequality, we choose y ∈ ℤ_{2} so that if z = 2^{n} − 1 + 2^{n+1}y, then Φ (z) ≡_{2^{n+f}} z.

We know that such a y exists by definition of farPoint. As before, we will define z′ = 2^{n+2^{H}} − 1 + 2^{n+1+2^{H}} y for this choice of y, and from the above discussion we know that R_{n+2^{H}} Φ (z′) ≡_{2^{f}} R_{n}Φ (z)

and R_{n} (z) ≡_{2^{f}} R_{n+2^{H}} (z′) since f ≤ H + 1. However, since Φ (z) ≡_{2^{n+f}} z, now R_{n} (Φ (z)) ≡_{2^{f}} R_{n} (z) ,

and therefore

R_{n+2^{H}} (Φ (z′)) ≡_{2^{f}} R_{n} (Φ (z)) ≡_{2^{f}} R_{n} (z) ≡_{2^{f}} R_{n+2^{H}} (z′)

Clearly, Φ (z′) ≡_{2^{n+2^{H}}} z′ by solenoidality since Φ (−1) = −1, and therefore fP (2^{n+2^{H}} − 1, n + 1 + 2^{H}) =

fP (2^{n} − 1, n + 1) . This completes the proof. □

The proof of Theorem 2.8 is similar, but relies instead upon Theorem 3.5.

Proof of Theorem 2.8. This time we will work with those 2-adic initial segments agreeing nontrivially with \frac{1}{3} = Φ (\frac{1}{3}) , and so we apply Theorem 3.5 with q = \frac{1}{3}. Once again, for n ∈ ℕ, assume

that f = fP (1 + (∑^{n} ; i=02^{2i+1}) + 2^{2n+2}, 2n + 3) is finite and let H ≥ max {1, f − 1} . Note that

1 + ∑^{n} ; i=02^{2i+1} ≡ \frac{1}{3} Mod 2^{2n+2}, and that there is no z ∈ ℤ_{2} with z ≡_{2^{2n+3}} 1 + (∑^{n} ; i=02^{2i+1}) + 2^{2n+2} and

Φ (z) ≡_{2^{2n+3+f}} z. Let y ∈ ℤ_{2} and define

z = 1 + (∑^{n} ; i=02^{2i+1}) + 2^{2n+2} + 2^{2n+3}y

z′ = 1 + ( ∑^{n+2^{H+1}} ; i=02^{2i+1}) + 2^{2(n+2^{H+1})+2} + 2^{2(n+2^{H+1})+3}y

Here z is not a fixed point of Φ mod 2^{2n+3+f}. By Theorem 3.1,

Φ (z) = Φ (1 + (∑^{n} ; i=02^{2i+1})) + \frac{Φ (1 + 2y)}{3^{n+2}}2^{2n+2}

and also

Φ (z′) = Φ (1 + ( ∑^{n+2^{H+1}} ; i=02^{2i+1})) + \frac{Φ (1 + 2y)}{3^{n+2^{H+1}+2}} 2^{2(n+2^{H+1})+2}

Again, 3^{2^{H+1}} ≡_{2^{H+2}} 1 by Lemma 3.2, and

R_{2+2n+2^{H+2}}Φ (1 + ( ∑^{n+2^{H+1}} ; i=02^{2i+1}) + 2^{2(n+2^{H+1})+2}) ≡_{2^{H+2}} R_{2+2n}Φ (1 + (∑^{n} ; i=02^{2i+1}) + 2^{2n+2})

by Theorem 3.5 with b = k = v = 2 and a = 3. Therefore,

R_{2+2n+2^{H+2}} (Φ (z′)) ≡_{2^{H+2}} R_{2+2n+2^{H+2}}Φ (1 + ( ∑^{n+2^{H+1}} ; i=02^{2i+1}) + 2^{2(n+2^{H+1})+2}) + \frac{Φ(1+2y)}{3^{n+2^{H+1}+2}}

≡_{2^{H+2}} R_{2+2n}Φ (1 + (∑^{n} ; i=02^{2i+1}) + 2^{2n+2}) + \frac{Φ(1+2y)}{3^{n+2}}

≡_{2^{H+2}} Φ (z)

by (3.2). It is again clear from how z and z′ are defined that R_{2+2n} (z) = 1 + 2y = R_{2+2n+2^{H+2}} (z′). By definition of farPoint, R_{2+2n} (Φ (z)) ≢_{2^{f+1}} R_{2+2n} (z) , and hence

R_{2+2n+2^{H+2}} (Φ (z′)) ≡_{2^{H+2}} R_{2+2n} (Φ (z)) ≢_{2^{f+1}} R_{2+2n} (z) ≡_{2^{H+2}} R_{2+2n+2^{H+2}} (z′)

So we have shown that fP (1 + ( ∑^{n+2^{H+1}} ; i=02^{2i+1}) + 2^{2(n+2^{H+1})+2}, 2 (n + 2^{H+1}) + 3) ≤ f. Further-

more we can choose y ∈ ℤ_{2} so that if z = 1 + (∑^{n} ; i=02^{2i+1}) + 2^{2n+2} + 2^{2n+3}y, then Φ (z) ≡_{2^{2n+f+2}} z.

Similarly, we define z′ = 1 + ( ∑^{n+2^{H+1}} ; i=02^{2i+1}) + 2^{2(n+2^{H+1})+2} + 2^{2(n+2^{H+1})+3}y for this same y, and

we can again obtain R_{2+2n+2^{H+2}} (Φ (z′)) ≡_{2^{f}} R_{2+2n} (Φ (z)) and R_{2+2n} (z) ≡_{2^{f}} R_{2+2n+2^{H+2}} (z′) since

f ≤ H + 1. But since Φ (z) ≡_{2^{2n+f+2}} z, we have R_{2+2n} (Φ (z)) ≡_{2^{f}} R_{2+2n} (z) , and so

R_{2+2n+2^{H+2}} (Φ (z′)) ≡_{2^{f}} R_{2+2n} (Φ (z)) ≡_{2^{f}} R_{2+2n} (z) ≡_{2^{f}} R_{2+2n+2^{H+2}} (z′)

And since \frac{1}{3} is a fixed point of Φ, Φ (z′) ≡ z′ (mod 2 + 2n + 2^{H+2}) by solenoidality, and thus we

have shown that {fP (1 + (∑^{n} ; i=02^{2i+1}) + 2^{2n+2}, 2n + 3)} is finitely pseudoperiodic. The other half

of the proof, showing that the sequence {fP (1 + ∑^{n} ; i=02^{2i+1}, 2n + 4)} is finitely pseudoperiodic is

similar, also relying upon Theorem 3.5. □

Using the periodicity of Φ, once we have determined that there is one x ∈ ℤ_{2} that is not a fixed point of Φ mod 2^{k} for some k, we obtain infinite families of 2-adics that are not fixed points of Φ mod 2^{k+mr}. While the applicability of the periodicity of Φ to the Fixed Points Conjecture is clear, it is not clear how it can be used to aid in the solution to the original 3x+1 problem. One potentially interesting area for future study would be to apply this property to the map Ω = Φ ∘ V ∘ Φ^{−1}, where V (x) = −1 − x [4]. This map makes an intimate connection between Φ and the main conjectures associated with the 3x + 1 problem. Such investigations may shed light on the 3x + 1 problem itself.

5. Acknowledgments

This project was funded by a research grant from the University of Scranton. Many thanks to Kenneth Monks for his many helpful comments, and in particular for his contributions which led to simpler proofs of Theorems 3.3 and 3.5.

References

[1] Bernstein, D.J. and Lagarias, J. C., The 3x + 1 Conjugacy Map, Can. J. Math. 48 (1996), 1154-1169

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

[3] Bernstein, D.J., A non-iterative 2-adic statement of the 3x + 1 conjecture, Proc. Amer. Math. Soc. 121 (1994), 405-408

[4] Monks, K. and Yazinski, J., The Autoconjugacy of the 3x + 1 Function, Discrete Math, to appear

Department of Mathematics, University of Scranton, Scranton, PA 18510

   E-mail address: yazinskij2@scranton.edu