The generalized 3x + 1 mapping

K.R. Matthews

September 10, 1995

1 Introduction

One of the most tantalizing conjectures in number theory is the so–called 3x + 1 conjecture, attributed to L. Collatz (1937): Let T : ℤ → ℤ be defined by

T (x) = \{ \begin{matrix}x/2 & if x ≡ 0 (mod 2) \\ (3x + 1)/2 & if x ≡ 1 (mod 2). \end{matrix}  (1)

Collatz conjectured that if x ∈ ℕ, then the trajectory

x, T (x), T^{2}(x), …

eventually reaches the cycle 1, 2, 1. If x ∈ −ℕ, it is also conjectured that the trajectory {T^{k}(x)} eventually reaches one of the cycles

(a) −1, −1;

(b) −5, −7, −10, −5;

(c) −17, −25, −37, −55, −82, −41, −61, −91, −136, −68, −34, −17.

There is also the trivial cycle 0, 0.

The 3x + 1 mapping is a special case of a more general class of mappings about which accurate predictions can be made concerning the behaviour of trajectories. Broadly speaking, there are similar conjectures that can be made about such mappings which seem equally unsolvable and tantalizing. Since 1981, in a series of papers [14, 15, 16, 12, 2, 17], the author and collaborators were lead to connections with ergodic theory and Markov chains. It turns out experimentally that divergent trajectories also possess some regularity of distribution of iterates in congruence classes mod m. It is easy to describe the conjectural picture for mappings of relatively prime type which include the 3x + 1 mapping. However the Markov chains are more difficult to describe in the general case.

There are natural generalizations to other rings of interest to number theorists, namely F_{q}[x] and the ring of integers of an algebraic number field. The conjectural picture is not so clear with F_{q}[x]. Also with number fields, it is not just a matter of studying finitely many cycles in the ring of integers in the ring of integers. It seems likely there are in addition to finitely many cycles, finitely many “lower dimensional” T –invariant subsets within which divergent trajectories move in a regular manner. We illustrate with ℤ_{2}[x], ℤ[\sqrt{2}] and ℤ[\sqrt{3}].

For an account of other work on the 3x + 1 problem, we refer the reader to Lagarias’ survey [11] and [8, pages 215–218].

2 The generalized 3x + 1 mapping

Let d ≥ 2 be a positive integer and m_{0}, …, m_{d−1} be non–zero integers. Also for i = 0, …, d − 1, let r_{i} ∈ ℤ satisfy r_{i} ≡ im_{i} (mod d). Then the formula

T (x) = \frac{m_{i}x − r_{i}}{d}  if x ≡ i (mod d)  (2)

defines a mapping T : ℤ → ℤ called the generalized Collatz mapping. (The mapping (1) corresponds to d = 2, m_{0} = 1, m_{1} = 3, r_{0} = 0, r_{1} = −1.) EQUIVALENT FORM: For implementation on a computer, a somewhat simpler form is:

T (x) = ⌊\frac{m_{i}x}{d}⌋ + X_{i} if x ≡ i (mod d),  (3)

where X_{0}, …, X_{d−1} are any given integers and ⌊r⌋ denotes the integer part symbol. EXAMPLE 2.1

T_{k}(x) = \{ \begin{matrix}x/2 & if x ≡ 0 (mod 2) \\ (3x + k)/2 & if x ≡ 1 (mod 2), \end{matrix}

where k is an odd integer. Again, all trajectories appear to reach one of finitely many cycles. Also it seems certain that the number of cycles is unbounded, as k increases in magnitude, as is the maximum cycle length. k # of cycles for T_{5^{k}} max cycle–length

0  5  27
1  10  34
2  13  118
3  17  118
4  19  118
5  21  165
6  23  433

Figure 1: Observed number of cycles for T_{5^{k}}, 0 ≤ k ≤ 6.

In particular, the number of cycles for T_{5^{t}} appears to strictly increase with t. (See Fig. 1.) The only cycles for T_{3^{t}} appear to be 3^{t} times those of T_{1}.

In [14], Matthews and Watts studied the mapping (2) when gcd (d, m_{i}) = 1 for 0 ≤ i ≤ d − 1 (the relatively prime case). The paper contained some conjectures based on computer evidence, the first three corresponding to conjectures of Möller [18], (who studied a special case of mapping (2)):

CONJECTURE 2.1

(i) If |m_{0} ⋯ m_{d−1}| < d^{d}, then all trajectories {T^{K}(n)}, n ∈ ℤ, eventually cycle.

(ii) If |m_{0} ⋯ m_{d−1}| > d^{d}, then almost all trajectories {T^{K}(n)}, n ∈ ℤ are divergent (that is, T^{K}(n) → ±∞, except for an exceptional set S of integers n satisfying #{n ∈ S| − X ≤ n ≤ X} = o(X).)

(iii) The number of cycles is finite.

(iv) If the trajectory {T^{K}(n)}, n ∈ ℤ is not eventually cyclic, then the iterates are uniformly distributed mod d^{α} for each α ≥ 1:

lim_{N→∞} \frac{1}{N+1} card \{K ≤ N|T^{K}(n) ≡ j (mod d^{α})\} = \frac{1}{d^{α}} ,

for 0 ≤ j ≤ d^{α} − 1.

Regarding conjecture 2.1 (i), by choosing m_{0}, …, m_{d−1} so that their product is close to, but less than d^{d} in absolute value, one expects some trajectories to take many iterations to reach a cycle and for some cycles to be rather long. For example:

EXAMPLE 2.2

T (x) = \{ \begin{matrix}x/4 & if x ≡ 0 (mod 4) \\ (3x − 3)/4 & if x ≡ 1 (mod 4) \\ (5x − 2)/4 & if x ≡ 2 (mod 4) \\ (17x − 3)/4 & if x ≡ 3 (mod 4). \end{matrix}

Here 1 · 3 · 5 · 17 = 255 = 4^{4} − 1.

There appear to be 16 cycles starting at 0, −3, 2, 3, 6, (length 1747), −18, −46, −122, −330, −117, −137, −186, −750 (length 1426), −261, −333, 5127.

Regarding conjecture 2.1(ii), the simplest example where things are evident numerically, but defy proof, is the 5x + 1 mapping: EXAMPLE 2.3

T (x) = \{ \begin{matrix}x/2 & if x ≡ 0 (mod 2) \\ (5x + 1)/2 & if x ≡ 1 (mod 2). \end{matrix}

The trajectory {T^{K}(7)} appears to be divergent. Apparently T has 5 cycles, with starting values 0, 1, 13, 17, −1.

The set of generalized 3x + 1 mappings is closed under composition: If T_{1}, T_{2} have d_{1}, d_{2} branches respectively, then T = T_{2}T_{1} has d_{1}d_{2} branches. For example if we take T_{1}, T_{2} to be the 3x + 1, 5x + 1, mappings, then EXAMPLE 2.4

T (x) = \{ \begin{matrix}x/4 & if x ≡ 0 (mod 4) \\ (3x + 1)/4 & if x ≡ 1 (mod 4) \\ (5x + 2)/4 & if x ≡ 2 (mod 4) \\ (15x + 7)/4 & if x ≡ 3 (mod 4). \end{matrix}

Here all trajectories appear to enter one of 7 cycles, with starting values 0, −2, 1, 10, 7, 514, −749.

Whereas for mappings (3) of relatively prime type, the prediction of overall cycling or divergence is independent of the X_{i}, these numbers are of crucial importance in general, as the following two examples show. EXAMPLE 2.5

T (x) = \{ \begin{matrix}x/3 − 1 & if x ≡ 0 (mod 3) \\ (x + 5)/3 & if x ≡ 1 (mod 3) \\ 10x − 5 & if x ≡ 2 (mod 3) \end{matrix}

All trajectories appear to enter one of five cycles, with starting values 0, 5, 17, −1, −4. However this example becomes less mysterious if we consider the related mapping

T′(x) = \{ \begin{matrix}T (x) & if x ≡ 0 or 1 (mod 3) \\ T^{2}(x) = (10x − 8)/3 & if x ≡ 2 (mod 3). \end{matrix}

For T′ is a mapping of relatively prime type and conjecture 2.1 predicts that all trajectories eventually cycle. EXAMPLE 2.6

T (x) = \{ \begin{matrix}7x + 3 & if x ≡ 0 (mod 3) \\ (7x + 2)/3 & if x ≡ 1 (mod 3) \\ (x − 2)/3 & if x ≡ 2 (mod 3) \end{matrix}

We see that 3|x implies 3|T (x). Hence once a trajectory enters the zero residue class mod 3, it remains there. All divergent trajectories starting in the congruence classes x ≡ ±1 (mod 3), appear to eventually enter the zero residue class mod 3. In fact we believe that if T^{k}(x) ≡ ±1 (mod 3) for all k ≥ 0, then the trajectory must eventually enter one of the cycles −1, −1 or −2, −4, −2. The author offers a $100 prize for a proof. The problem seems just as intangible as the 3x + 1 problem and is a simple example of the more general conjecture (6.1) below.

3 Some properties of the general mapping

Let B(j, m) denote the congruence class consisting of integers x ≡ j (mod m). Then

1. T^{−1}(B(j, m)) is a disjoint union of N congruence classes mod md. In particular, if gcd(m_{i}, m) = 1 for i = 0, …, d − 1, then N = d.

2. In the relatively prime case, the d^{α} cylinders

B(i_{0}, d) ∩ T^{−1}(B(i_{1}, d)) ∩ ⋯ ∩ T^{−(α−1)}(B(i_{α−1}, d))  (4)

are the d^{α} congruence classes mod d^{α}. (This observation has been the basis of many of the papers in the subject.)

3. In the relatively prime case, if A = B(j, d^{α}) and B = B(k, d^{β}), then T^{−K}(A) ∩ B is a disjoint union of d^{K−β} congruence classes mod d^{K+α}, if K ≥ β.

(Properties 1 and 2 are proved in [14]. Property 3 then follows from 2 by expressing A and B as cylinders.)

4 Asymptotic growth of |T^{K}(x)|

If T^{K}(x) ≡ i (mod d), 0 ≤ i < d, we let m_{K}(x) = m_{i}, r_{K}(x) = r_{i}. Then

(a) T^{K}(x) = \frac{m_{0}(x) ⋯ m_{K−1}(x)}{d^{K}} (x − ∑_{i=0}^{K−1} \frac{r_{i}(x)d^{i}}{m_{0}(x) ⋯ m_{i}(x)}).

(b) If T^{i}(x) ≠ 0 for all i ≥ 0,

T^{K}(x) = \frac{m_{0} ⋯ m_{K−1}(x)}{d^{K}}x ∏_{i=0}^{K−1} (1 − \frac{r_{i}(x)}{m_{i}(x)T^{i}(x)}).

If T^{K}(x) → ±∞ and the T^{K}(x) are uniformly distributed mod d, the iterates |T^{K}(x)| grow geometrically. For without loss of generality we can assume T^{i}(x) is nonzero for all i. Then taking logarithms in (b) gives

log |T^{K}(x)| = ∑_{i=0}^{K−1} log |m_{i}(x)| + log x − K log d + ∑_{i=0}^{K−1} log |1 − \frac{r_{i}(x)}{m_{i}(x)T^{i}(x)}|.

Then as a_{i} = r_{i}(x)/(m_{i}(x)T^{i}(x)) → 0, we have b_{i} = log |1 − a_{i}| → 0 and hence \frac{1}{K} (b_{0} + ⋯ + b_{K−1}) → 0. Consequently

\frac{1}{K} log |T^{K}(x)| = \frac{1}{K} ∑_{i=0}^{K−1} log |m_{i}(x)| − log d + o(1).

Hence if the T^{K}(x) are uniformly distributed mod d, we deduce

\frac{1}{K} log |T^{K}(x)| → \frac{1}{d} ∑_{i=0}^{d−1} log |m_{i}| − log d,

and hence

|T^{K}(x)|^{1/K} → \frac{(|m_{0} ⋯ m_{d−1}|)^{1/d}}{d} .

More generally, if limiting frequencies f_{0}, …, f_{d−1} exist (mod d) for the trajectory {T^{K}(x)}, then

|T^{K}(x)|^{1/K} → \frac{(|m_{0}|^{f_{0}} ⋯ |m_{d−1}|^{f_{d−1}})}{d}.

5 Ergodic theory

One innovation in [14] was the introduction of ergodic theory (see [1]). The mapping T extends uniquely to a continuous mapping of the d–adic integers ℤ̂_{d} into itself. ℤ̂_{d} can be regarded as a completion, consisting of formal sums

∑_{i=0}^{∞} a_{i}d^{i}, a_{i} ∈ {0, 1, …, d − 1},

with addition and multiplication done as with ordinary positive integers, by “carrying the digit”. (See [10] or [13].)

Let us assume that T is a mapping of relatively prime type. Then by property 1, the inverse image of a congruence class mod d^{α} is the disjoint union of d classes mod d^{α+1} and this shows that T is measure–preserving:

μ(T^{−1}(A)) = μ(A),

where A is a Haar–measurable set in ℤ̂_{d}. (The Haar measure of B(j, d^{α}) is 1/d^{α}.) Property 3 of T implies the strongly–mixing property

lim_{K→∞} μ(T^{−K}(A) ∩ B) = μ(A)μ(B)

for all Haar–measurable sets A and B in ℤ̂_{d}. Consequently T is ergodic i.e. T^{−1}(A) = A ⇒ μ(A) = 0 or 1 and the ergodic theorem [1, page 12] applied to the measurable set B(j, d^{α}) gives

lim_{N→∞} \frac{1}{N+1} card \{K ≤ N|T^{K}(x) ≡ j (mod d^{α})\} = \frac{1}{d^{α}}

for almost all x ∈ ℤ̂_{d}.

Applying the ergodic theorem to the cylinder (4) gives a similar result for the d–adic integers x which satisfy

T^{K}(x) ≡ i_{0} (mod d), …, T^{K+α−1}(x) ≡ i_{α−1} (mod d).

Every d–adic integer possesses an interesting d–adically convergent series noted by Möller:

x = ∑_{i=0}^{∞} \frac{r_{i}(x)d^{i}}{m_{0}(x) ⋯ m_{i}(x)} if x ∈ ℤ̂_{d}.

This tells us that the congruence classes mod d occupied by the iterates of x in fact determine x. A corresponding expansion is later used to advantage later in Section 8 for a mapping T : ℤ_{2}[x] → ℤ_{2}[x]. (See mapping (13) below.)

6 Markov chains: maps of relatively prime

type

Computer experiments indicate that for each m > 1, every divergent trajectory eventually occupies certain congruence classes mod m with positive limiting frequencies. A simple example is the 5x + 1 mapping.

Here divergent trajectories appear to occupy the classes 0, 1, 2, 3, 4 mod 5 with limiting frequencies 0, 1/15, 2/15, 8/15, 4/15. (A trajectory starting from a non–zero integer will eventually enter the class B(3, 5) and subsequently remain in the T –invariant set ℤ − B(0, 5).)

These rational numbers are the limits

ρ_{j} = lim_{K→∞} μ{B(i, 5) ∩ T^{−K}(B(j, 5))}, 0 ≤ j ≤ 4,  (5)

where ρ_{j} is independent of i and μ(S) = r/m if S is a disjoint union of r congruence classes mod m. (μ is a finitely additive measure on ℤ.) Also μ{B(i, 5)∩T^{−K}(B(j, 5))} is the (i, j) element of the K–th power of a Markov matrix Q_{T} (5) defined below. To explain this, let us consider a mapping T of relatively prime type. Then it was implicit in the proof of [15, Lemma 2.8] that if B is the cylinder:

B = B(i_{0}, m) ∩ T^{−1}(B(i_{1}, m)) ∩ ⋯ ∩ T^{−K}(B(i_{K}, m)),

then

μ(B) = q_{i_{0}i_{1}}(m) ⋯ q_{i_{K−1}i_{K}}(m),  (6)

where

q_{ij}(m) = μ(B(i, m) ∩ T^{−1}(B(j, m))) 0 ≤ i, j ≤ m − 1,  (7)

Then (see [15, Lemma 2.9]), the matrix Q_{T} (m) = [q_{ij}(m)] is an m×m Markov matrix, i.e. a matrix whose elements are non–negative and whose rows sum to unity. (For a discussion of Markov matrices, see [9] or [19].) (We are using the transpose of the matrix used in [15].) If d|m, a simple formula exists for q_{ij}(m):

q_{ij}(m) = \{ \begin{matrix}1/d & if T (i) ≡ j (mod m/d) \\ 0 & otherwise. \end{matrix}

However if d does not divide m, the formula is more complicated.

To introduce Markov chains, we need the Prüfer ring ℤ̂. (See [20] or [6, pages 7–11].) Like the d–adic integers, this ring can be defined as a completion of ℤ. ℤ̂ is a metric space in which the closure of a congruence class B(j, m) is the corresponding congruence class {x ∈ ℤ̂|x ≡ j (mod m)}. We also denote this class by B(j, m). Then our finitely additive measure μ on ℤ extends to a probability Haar measure on ℤ̂.

Equation (6) can then be interpreted as showing that the sequence of random set–valued functions Y_{K}(x) = B(T^{K}(x), m), x ∈ ℤ̂, forms a Markov chain with states B(0, m), …, B(m − 1, m), with transition probabilities q_{ij}(m), given by equation (7). For equation (6) can be rewritten as

P r (Y_{0}(x) = B(i_{0}, m), … Y_{K}(x) = B(i_{K}, m)) = q_{i_{0}i_{1}}(m) ⋯ q_{i_{K−1}i_{K}}(m).

Then from an ergodic theorem for Markov chains ([4, Example 2.2, page 299]) we have the following result: Let C be a positive recurrent class and for each B ∈ C, let ρ_{B} be the component of the unique stationary distribution over C. (See [7] for these terms.) Then

P r ( lim_{K→∞} \frac{1}{K+1} card \{n; n ≤ K, Y_{n}(x) = B\} = ρ_{B}|Y_{n}(x) enters C) = 1.

In other words, if S_{C} is the union of the congruence classes of C,

P r ( lim_{K→∞} \frac{1}{K+1} card \{n; n ≤ K, T^{n}(x) ∈ B\} = ρ_{B}|T^{n}(x) enters S_{C}) = 1.

This, together with computer evidence, leads to the following:

CONJECTURE 6.1 Every divergent trajectory will eventually enter some S_{C} and will occupy each class B of C with positive limiting frequency ρ_{B}.

The positive recurrent classes can be determined numerically using an algorithm from [5].

EXAMPLE 6.1 The (5x + 1)/2 mapping with m = 5. The Markov chain formed by states 0, 1, 2, 3, 4 mod 5 has transition matrix

Q_{T}(5) = [ \begin{matrix}1/2 & 0 & 0 & 1/2 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 1/2 & 0 & 1/2 & 0 \\ 0 & 0 & 0 & 1/2 & 1/2 \\ 0 & 0 & 1/2 & 1/2 & 0 \end{matrix} ] .

The states 1, 2, 3, 4 form a positive recurrent class with limiting probabilities 1/15, 2/15, 8/15, 4/15.

EXAMPLE 6.2 The (5x − 3)/2 mapping with m = 15. Here the Markov chain formed by states 0, …, 14 mod 15 has two positive classes C_{1} and C_{2}:

C_{1} : 1, 2, 4, 7, 8, 11, 13, 14; C_{2} : 3, 6, 9, 12,

with limiting probabilites 4/15, 1/30, 1/15, 2/15, 4/15, 2/15, 1/15 and 4/15, 8/15, 2/15, 1/15,

respectively.

In papers [2, 17, 15] the matrices Q_{T} (m) and sets S_{C} were studied in some detail for mappings T of relatively prime type. The structure of these sets can be quite complicated. It seems likely that there are finitely many sets S_{C} as m varies, if and only if T (ℤ) = ℤ.

7 Markov chains: general case

In 1983, George Leigh realized that to predict the frequencies mod m of divergent trajectories for the generalized Collatz mapping (2), we should restrict m to be a multiple of d and allow the states of the Markov chain to be all congruence classes in ℤ̂ of the form mk, where k divides some power of d. The idea is to keep track of how much information we have on the congruence classes that an iterate belongs to. For example, in the mapping of example 7.2 below, if we start off in B(4, 8), then we know T (x) is in B(0, 32)–we neglect factors such as the 5 present in m_{4} that are relatively prime to d = 8. Then B(0, 32) is all the information we have about where T (x) is located. All the information is in the current state, regardless of the previous states of the trajectory.

To define Leigh’s more general chain {Y_{n}}, we need some definitions: Let m_{i} = b_{i}d_{i}, where b_{i} ∈ ℤ, d_{i} ∈ ℕ and gcd (d_{i}, b_{i}) = 1 where d_{i} divides

some power of d, 0 ≤ i < d. Let d|m. We define a sequence of random functions on ℤ̂ : x → Y_{n}(x) ∈ B, where B is the collection of congruence classes of the form B(j, mk), k dividing some power of d:

(a) Y_{0}(x) = B(x, m); (b) Y_{n+1}(x) = B(T^{n+1}(x), mk_{n+1}), where

k_{0} = 1 and k_{n+1} = \frac{d_{j}k_{n}}{gcd (d_{j}k_{n}, d)}  (8)

and where j is determined by T^{n}(x) ≡ j (mod d), 0 ≤ j ≤ d − 1.

Transition probabilities q_{BB′} are defined for B, B′ ∈ B, as follows :

Let B = B(j, mk), B′ = B(j′, mk′). Then

q_{BB′} = \{ \begin{matrix}0 & if B′ ≠ B, \\ kd_{j}/k′d & otherwise. \end{matrix}  (9)

Then (see [12, page 133]) the set–valued functions {Y_{n}(x)} form a Markov chain with transition probabilities q_{BB′}, by virtue of the equation

Pr (Y_{0}(x) = B_{0}, …, Y_{n}(x) = B_{n}) = q_{B_{0}B_{1}}q_{B_{1}B_{2}} ⋯ q_{B_{n−1}B_{n}}.

Now let C be a positive recurrent class and for each B ∈ C, let ρ_{B} be the corresponding limiting probability. Then from the result of [4] mentioned earlier, we have

P r ( lim_{K→∞} \frac{1}{K+1} card \{n; n ≤ K, Y_{n}(x) = B\} = ρ_{B}|Y_{n}(x) enters C) = 1.

To find the limiting frequency p_{i} of occupancy of a particular congruence class B(i, m), we must sum the contributions of each congruence class in C which is contained in B(i, m), obtaining

P r (f_{i} = p_{i}|Y_{n}(x) enters C) = 1,  (10)

where

f_{i} = lim_{K→∞} \frac{1}{K+1} card \{n; n ≤ K, T^{n}(x) ≡ i (mod m)\}  (11)

and

p_{i} = ∑_{\begin{matrix}B ∈ C \\ B ⊆ B(i, m) \end{matrix}} ρ_{B}.  (12)

(See [12, Theorem 5].)

For mappings T of relatively prime type, or when

gcd(m_{i}, d^{2}) = gcd(m_{i}, d) 0 ≤ i < d,

this Markov chain reduces to the one implicitly studied by Matthews and Watts. However in the general case the chain can be infinite. EXAMPLE 7.1

T (x) = \{ \begin{matrix}12x − 1 & if x ≡ 0 (mod 4) \\ 20x & if x ≡ 1 (mod 4) \\ (3x − 6)/4 & if x ≡ 2 (mod 4) \\ (x − 3)/4 & if x ≡ 3 (mod 4). \end{matrix}

To predict the frequency distribution mod 4 of divergent trajectories, we find there are 8 states in the Markov chain:

B(0, 4), B(1, 4), B(2, 4), B(3, 4), B(−1, 16), B(4, 16), B(−17, 64), B(−5, 16)

with transition matrix

[ \begin{matrix}0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 1/4 & 1/4 & 1/4 & 1/4 & 0 & 0 & 0 & 0 \\ 1/4 & 1/4 & 1/4 & 1/4 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \end{matrix} ] .

The Markov matrix is primitive (its 8th power is positive) and the limiting probabilities are ·1, ·1, ·2, ·2, ·1, ·1, ·1, ·1. To find the predicted frequency for the congruence class 0 (mod 4), we must sum the contributions arising from the states B(0, 4) and B(4, 16), namely ·1 + ·1 = ·2. Similarly the other frequencies are ·1, ·2, ·2 + ·1 + ·1 + ·1 = ·5.

We finish this section with some generalizations of conjectures 2.1 (i),(ii) and (iv) due to Leigh. CONJECTURE 7.1 (a) Every divergent trajectory will eventually enter some S_{C} and will occupy each class B of C with limiting frequency ρ_{B}.

(b) Let C be a positive recurrent class for the Markov chain mod d and let p_{i} be defined by (12). Then if

∏_{i=0}^{d−1} |\frac{m_{i}}{d} |^{p_{i}} < 1,

all trajectories starting in S_{C} will eventually cycle.

However if

∏_{i=0}^{d−1} |\frac{m_{i}}{d} |^{p_{i}} > 1,

almost all trajectories starting in S_{C} diverge. Here is an example from [12, page 140]: EXAMPLE 7.2

T (x) = \{ \begin{matrix}x/4 & if x ≡ 0 (mod 8) \\ (x + 1)/2 & if x ≡ 1 (mod 8) \\ 20x − 40 & if x ≡ 2 (mod 8) \\ (x − 3)/8 & if x ≡ 3 (mod 8) \\ 20x + 48 & if x ≡ 4 (mod 8) \\ (3x − 13)/2 & if x ≡ 5 (mod 8) \\ (11x − 2)/4 & if x ≡ 6 (mod 8) \\ (x + 1)/8 & if x ≡ 7 (mod 8) \end{matrix} .

We find there are 9 states in the Markov chain mod 8:

B(0, 8), B(0, 32), B(1, 8), B(2, 8), B(3, 8), B(4, 8), B(5, 8), B(6, 8), B(7, 8).

The transition matrix is

[ \begin{matrix}1/4 & 0 & 0 & 1/4 & 0 & 1/4 & 0 & 1/4 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1/2 & 0 & 0 & 0 & 1/2 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1/8 & 0 & 1/8 & 1/8 & 1/8 & 1/8 & 1/8 & 1/8 & 1/8 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1/2 & 0 & 0 & 0 & 1/2 & 0 & 0 \\ 1/4 & 0 & 0 & 1/4 & 0 & 1/4 & 0 & 1/4 & 0 \\ 1/8 & 0 & 1/8 & 1/8 & 1/8 & 1/8 & 1/8 & 1/8 & 1/8 \end{matrix} ] .

There are two positive recurrent classes: C_{1} : B(1, 8), B(5, 8) and

C_{2} : B(0, 8), B(0, 32), B(2, 8), B(4, 8), B(6, 8).

The limiting probablities are 1/2, 1/2 and 3/8, 1/4, 1/8, 1/8, 1/8, respectively. We have p_{1} = p_{5} = 1/2 and as

(\frac{1}{2})^{1/2} (\frac{3}{2})^{1/2} < 1,

we expect every trajectory starting in S_{C_{1}} = B(1, 8) ∪ B(5, 8) to cycle. Also p_{0} = 3/8 + 1/4 = 5/8 and p_{2} = p_{4} = p_{6} = 1/8. Then as

(\frac{1}{4})^{5/8} 20^{1/8}20^{1/8} (\frac{11}{4})^{1/8} > 1,

we expect most trajectories starting in S_{C_{2}} = B(0, 2) to diverge, displaying frequencies 5/8, 1/8, 1/8, 1/8 in the respective component congruence classes. (Leigh uses another Markov chain X_{n}(x) and arrives at 4/7, 1/7, 1/7, 1/7, which are erroneous, as one discovers on observing the apparently divergent trajectory starting with 46.)

In this example, there appear to be 13 cycles with starting values

0, 1, 10, 13, 61, 158, 205, 3292, 4244, −2, −11, −12, −18.

We finish this section with an example where there are infinitely many states in the Markov chain. The example was suggested by Chris Smyth. EXAMPLE 7.3

T_{k}(x) = \{ \begin{matrix}⌊2x/3⌋ & if x ≡ 0 (mod 2) \\ ⌊3x/2⌋ & if x ≡ 1 (mod 2). \end{matrix}

This can be regarded as a 6–branched mapping. The integer trajectories are much simpler to describe than the Markov chain: Even integers are successively multiplied by 3/2 until one gets an odd integer. Also 6k + 1 → 4k → 6k → 9k → 6k, while 6k+3 → 4k+2 → 6k+3. Finally 6k+5 → 4k+3 and unless we start from −1 (a fixed point), we must eventually reach B(1, 6) or B(3, 6).

8 Other rings: Finite fields

It is natural to investigate analogous mappings T for rings other than ℤ, where division is meaningful, namely the ring of integers of a global field. (See the chapter in [3, page 60]).

We experimented with the ring of polynomials ℤ_{2}[x]. Here the conjectural picture for trajectories is not so clear. In [16] we examined the following mapping:

EXAMPLE 8.1

T (f) = \{ \begin{matrix}f/x & if f ≡ 0 (mod x) \\ \{(x^{2} + 1)f + 1\}/x & if f ≡ 1 (mod x) \end{matrix}  (13)

This is an example of relatively prime type and |m_{0} ⋯ m_{|d|−1}| = |d|^{|d|}, where |f| = 2^{deg f}. Most trajectories appear to cycle. The trajectory starting from 1 + x^{2} + x^{3} exhibits a regularity which enabled its divergence to be proved (see Figure 2). If L_{n} = 5(2^{n} − 1), then

T^{L_{n}}(1 + x^{2} + x^{3}) = \frac{1 + x^{3·2^{n}+1} + x^{3·2^{n}+2}}{1 + x + x^{2}} .

Figure 2 shows the first 92 iterates.

There are infinitely many cycles. In particular, the trajectories starting with g_{n} = (1 + x^{2^{n}−1})/(1 + x) are purely periodic, with period–length 2^{n}. Figure 3 shows the cycle printout for g_{4}.

11001 111101 1001001 01101101 1101101 11011001 110111101 1101001001 11001101101 111111011001 1000010111101 01001001001001 1001001001001 01101101101101 1101101101101 11011011011001 110110110111101 1101101101001001 11011011001101101 110110111111011001 1101101000010111101 11011001001001001001 110111101101101101101 1101001011011011011001 11001100110110110111101 111111111101101101001001 1000000001011011001101101 01000000100110111111011001 1000000100110111111011001 01000010111101000010111101 1000010111101000010111101 01001001001001001001001001 1001001001001001001001001 01101101101101101101101101 1101101101101101101101101 11011011011011011011011001 110110110110110110110111101 1101101101101101101101001001 11011011011011011011001101101 110110110110110110111111011001 1101101101101101101000010111101 11011011011011011001001001001001 110110110110110111101101101101101 1101101101101101001011011011011001 11011011011011001100110110110111101 110110110110111111111101101101001001 1101101101101000000001011011001101101 11011011011001000000100110111111011001 110110110111101000010111101000010111101 1101101101001001001001001001001001001001 11011011001101101101101101101101101101101 110110111111011011011011011011011011011001 1101101000010110110110110110110110110111101 11011001001001101101101101101101101101001001 110111101101111011011011011011011011001101101 1101001011010010110110110110110110111111011001 11001100110011001101101101101101101000010111101 111111111111111111011011011011011001001001001001 1000000000000000010110110110110111101101101101101 01000000000000001001101101101101001011011011011001 1000000000000001001101101101101001011011011011001 01000000000000101111011011011001100110110110111101 1000000000000101111011011011001100110110110111101 01000000000010010010110110111111111101101101001001 1000000000010010010110110111111111101101101001001 01000000001011011001101101000000001011011001101101 1000000001011011001101101000000001011011001101101 01000000100110111111011001000000100110111111011001 1000000100110111111011001000000100110111111011001 01000010111101000010111101000010111101000010111101 1000010111101000010111101000010111101000010111101 01001001001001001001001001001001001001001001001001 1001001001001001001001001001001001001001001001001 01101101101101101101101101101101101101101101101101 1101101101101101101101101101101101101101101101101 11011011011011011011011011011011011011011011011001 110110110110110110110110110110110110110110110111101 1101101101101101101101101101101101101101101101001001 11011011011011011011011011011011011011011011001101101 110110110110110110110110110110110110110110111111011001 1101101101101101101101101101101101101101101000010111101 11011011011011011011011011011011011011011001001001001001 110110110110110110110110110110110110110111101101101101101 1101101101101101101101101101101101101101001011011011011001 11011011011011011011011011011011011011001100110110110111101 110110110110110110110110110110110110111111111101101101001001 1101101101101101101101101101101101101000000001011011001101101 11011011011011011011011011011011011001000000100110111111011001 110110110110110110110110110110110111101000010111101000010111101 1101101101101101101101101101101101001001001001001001001001001001 11011011011011011011011011011011001101101101101101101101101101101

Figure 2: First 92 iterates for example 8.1.

                                    111111111111111
                                    1000000000000011
                                    01000000000001111
                                    1000000000001111
                                    01000000000110011
                                    1000000000110011
                                    01000000011111111
                                    1000000011111111
                                    01000001100000011
                                    1000001100000011
                                    01000111100001111
                                    1000111100001111
                                    01011001100110011
                                    1011001100110011
                                    00111111111111111
                                    0111111111111111
                                    111111111111111

Figure 3: Cycle g_{4}.

9 Other rings: algebraic number fields

Let d be a non–unit in the ring O_{K} of integers of an algebraic number field K. Also let D = |Norm(d)|. Then if m_{0}, …, m_{D−1} ∈ O_{K} satisfy gcd(Norm(m_{i}), Norm(d)) = 1 for all i, a sufficient condition for everywhere cycling appears to be

|Norm(m_{0} ⋯ m_{D−1})| < D^{D}.

Here are three examples. EXAMPLE 9.1 T : ℤ[\sqrt{2}] → ℤ[\sqrt{2}] be defined by

T (α) = \{ \begin{matrix}α/\sqrt{2} & if α ≡ 0 (mod \sqrt{2}) \\ (3α + 1)/\sqrt{2} & if α ≡ 1 (mod \sqrt{2}). \end{matrix}

Writing α = x + y\sqrt{2}, where x, y ∈ ℤ, we have equivalently

T (x, y) = \{ \begin{matrix}(y, x/2) & if x ≡ 0 (mod 2) \\ (3y, (3x + 1)/2) & if x ≡ 1 (mod 2). \end{matrix}

There appear to be finitely many cycles with starting values

0, 1, −1, −5, −17, −2 − 3\sqrt{2}, −3 − 2\sqrt{2}, 9 + 10\sqrt{2}.

An interesting feature is the presence of at least three one–dimensional T –invariant sets S_{1}, S_{2}, S_{3} in ℤ × ℤ:

S_{1} : x = 0 or y = 0, S_{2} : 2x + y + 1 = 0 or x + 4y + 1 = 0,

S_{3} : x + y + 1 = 0 or x + 2y + 1 = 0 or x + 2y + 2 = 0.

Trajectories starting in S_{1} or S_{2} oscillate from one line to the other, while those starting in S_{3} oscillate between the first and either of the second and third. Trajectories starting in S_{1} will cycle, as T^{2}(x, 0) = (C(x), 0), where C denotes the 3x + 1 mapping.

Most divergent trajectories appear to be evenly distributed mod (\sqrt{2})^{α}. However divergent trajectories starting in S_{2} or S_{3} present what at first sight appear to be anomalous frequency distributions mod 2. By considering T^{2}, these are explicable in terms of the predicted “one–dimensional” uniform distribution. For example, if 2x + y + 1 = 0, then

T^{2}(x, y) = \{ \begin{matrix}(\frac{3x}{2}, −3x − 1) & if x ≡ 0 (mod 2) \\ (\frac{9x+3}{2}, −9x − 4) & if x ≡ 1 (mod 2). \end{matrix}

For an example of everywhere cycling, consider:

EXAMPLE 9.2 T : ℤ[\sqrt{3}] → ℤ[\sqrt{3}] is defined by

T (x) = \{ \begin{matrix}x/\sqrt{3} & if x ≡ 0 (mod \sqrt{3}) \\ (x − 1)/\sqrt{3} & if x ≡ 1 (mod \sqrt{3}) \\ (4x + 1)/\sqrt{3} & if x ≡ 2 (mod \sqrt{3}) \end{matrix}

All trajectories appear to enter one of 14 cycles, with starting values 0, −1, −1 + \sqrt{3}, 5 + 2\sqrt{3}, −1 − 2\sqrt{3}, −7 − 4\sqrt{3}, −7 + 8\sqrt{3}, 11 + 11\sqrt{3}, −13 − 16\sqrt{3}, 14 + 8\sqrt{3}, 17 + 10\sqrt{3}, −22 − 7\sqrt{3}, 26 + 35\sqrt{3}, 35 + 41\sqrt{3}.

Finally it should be pointed out that divergent trajectories need not tend to infinity in absolute value:

EXAMPLE 9.3 T : ℤ[\sqrt{2}] → ℤ[\sqrt{2}] be defined by

T (α) = \{ \begin{matrix}(1 − \sqrt{2})α/\sqrt{2} & if α ≡ 0 (mod \sqrt{2}) \\ (3α + 1)/\sqrt{2} & if α ≡ 1 (mod \sqrt{2}). \end{matrix}

If \{T^{K}(x)\} is a divergent trajectory and T^{K}(x) = x_{K} + y_{K} \sqrt{2}, x_{K}, y_{K} ∈ ℤ, then apparently x_{K}/y_{K} → −\sqrt{2} and T^{K}(x) → 0.

Acknowledgement

The author is indebted to George Leigh for several examples, as well as providing a computer program which constructs the transition matrix (9) for the Y_{n}(x) chain. The author also thanks Owen Jones, Richard Pinch and Anthony Quas for helpful conversations when the author was on study leave at the Department of Pure Mathematics, University of Cambridge, July– December 1993.

References

[1] P. Billingsley, Ergodic theory and information, John Wiley, New York 1965.

[2] R.N. Buttsworth and K.R. Matthews, On some Markov matrices arising from the generalized Collatz mapping, Acta Arith. 55 (1990), 43–57.

[3] J.W.S. Cassels and A. Fröhlich, Algebraic Number Theory, Academic Press, London 1967.

[4] R. Durrett, Probability: Theory and Examples , Wadsworth and Brooks/Cole, Berlin 1991.

[5] B.L. Fox and D.M. Landi, An algorithm for identifying the ergodic subchains and transient states of a stochastic matrix, Communications of the ACM, 11 (1968), 619–621.

[6] M.D. Fried and M. Jarden, Field Arithmetic, Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 11, Springer, 1986.

[7] G.R. Grimmett and D.R. Stirzaker, Probability and random processes, Oxford University Press, 1992.

[8] R.K. Guy, Unsolved problems in number theory, Vol. 1, Problem books in Mathematics, Springer, Berlin 1994.

[9] A. Kaufmann and R. Cruon, Dynamic Programming, Academic Press, New York 1967.

[10] N. Koblitz, p–adic numbers, p–adic analysis and zeta–functions, Graduate Text 58, Springer, 1981.

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

[12] G.M. Leigh, A Markov process underlying the generalized Syracuse algorithm, Acta Arith. 46 (1985), 125–143.

[13] K. Mahler, p–adic numbers and their functions, Cambridge University Press, Cambridge, second edition, 1981.

[14] K.R. Matthews and A.M. Watts, A generalization of Hasses’s generalization of the Syracuse algorithm, Acta Arith. 43 (1984), 167–175.

[15] – –, A Markov approach to the generalized Syracuse algorithm, ibid. 45 (1985), 29–42.

[16] K.R. Matthews and G.M. Leigh, A generalization of the Syracuse algorithm in F_{q}[x], J. Number Theory, 25 (1987), 274–278.

[17] K.R. Matthews, Some Borel measures asssociated with the generalized Collatz mapping, Colloquium Math. 63 (1992), 191–202.

[18] H. Möller, Über Hasses Verallgemeinerung des Syracuse-Algorithmus (Kakutanis Problem), ibid. 34 (1978), 219–226.

[19] M. Pearl, Matrix theory and finite mathematics, McGraw–Hill, New York 1973.

[20] A.G. Postnikov. Introduction to analytic number theory, Amer. Math. Soc., Providence R.I. 1988.

Department of Mathematics University of Queensland Brisbane Queensland Australia 4072 krm@axiom.maths.uq.oz.au