Generalized 3x+1 mappings

1. Introduction
2. Mappings of type (a) and (b)
3. Asymptotic behaviour of T^-K(B(j, m))
4. Strongly-mixing property of relatively-prime type mappings
5. The Markov matrix Q_T(m)
6. A simple formula for Q_T(m)
7. Irreducible closed sets of Q_T(m) and ergodic sets of T
8. Transient classes
9. Behaviour of divergent trajectories
10. Conjecture 1
11. Conjecture 2
12. Examples [1], [2], [3], [4], [5], [6] [7] of generalized 3x+1 mappings of relatively prime type
13. Examples [1], [2], [3], [4], [5-prize problem] of mappings satisfying condition (b), but not of relatively prime type
14. BCMATH cycling-finding program.
15. References

Introduction

Starting in 1982, Tony Watts and I investigated the frequencies of occupation of congruence classes mod m of trajectories arising from generalised 3x+1 functions. (See earlier 3x+1 interests)
Experimentally we observed in cases (a) and (b) below, that (apparently) divergent (ie. unbounded) trajectories were attracted to what we called ergodic sets mod m of a Markov matrix Q_T(m), with limiting frequencies that we were later able to predict.

(a) gcd(m_i, d) = 1 for 0 ≤ i ≤ d-1, or

(b) gcd(m_i, d²) = gcd(m_i, d) for 0 ≤ i ≤ d-1 and d divides m.

(See a program for constructing Q_T(m) and finding the ergodic sets and transient classes, using the Fox_Landi algorithm with labels 0,1,...,m-1.)

In the case when neither condition (a) nor (b) holds, it is still possible to get conjectural information using Markov matrices and this was pointed out by George Leigh in 1983.

The asymptotic behaviour of T^-K(B(j, m))

x ≡ i (mod d) and (m_ix - r_i ) ⁄ d ≡ j (mod m)

(m_i(i + dy) - r_i ) ⁄ d ≡ j (mod m), i.e., m_iy ≡ j - M_i (mod m).

This congruence is soluble if and only if gcd(m_i, m) divides j - M_i, in which case there are gcd(m_i, m) solutions for y (mod m) and hence for x (mod md).

Lemma 1. (The Chinese remainder theorem)

x ≡ i (mod d) and x ≡ k (mod m)

Lemma 2. Let p_kj(n, m) be the number of congruence classes mod nd contained in B(k, m) ∩ T^-1(B(j, n)), where m divides n.
Then p_kj(n, m) is given by the following formula:

Let D = gcd(m, d), L = lcm(d, m) and let S_k,D consist of the integers i≡ k (mod D), 0 ≤ i ≤ d-1. Also for i ∈ S_k,D, let x_i denote the solution of

x ≡ i (mod d) and x ≡ k (mod m), 0 ≤ x ≤ L-1.

p_kj(n, m)=∑^' gcd(m_i, n, nd ⁄ m),

Proof. We have

B(k, m) ∩ T^-1(B(j, n)) = {x ∈ ℤ | x ≡ k (mod m) & T(x) ≡ j (mod n)}.

x ≡ i (mod d), x ≡ k (mod m), (m_ix - r_i ) ⁄ d ≡ j (mod n)

(m_i(x_i + Ly) - r_i ) ⁄ d ≡ j (mod n), or (m_im ⁄ D)y ≡ j - M_i (mod n).

gcd(m_im ⁄ D, n) = (m ⁄ D)gcd(m_i, n, nd ⁄ m)

Ln ⁄ t = LDn ⁄ mgcd(m_i, n, nd ⁄ m) = nd ⁄ gcd(m_i, n, nd ⁄ m).

Lemma 3. Under conditions (a) or (b) above, if α ≥ 1,

p_kj(md^α, m) = p_kj(m, m),

p_kj(md^α, m) = ∑^' gcd(m_i, md^α, d^α+1),

(m ⁄ D) gcd(m _i, md^α, d^α+1) divides j - M_i.

gcd(m _i, md^α, d^α+1) = gcd(m_i, d^α gcd(m, d)).

Theorem 1. Write p_kj(m, m)=p_kj(m). Then under conditions (a) or (b) above, the cylinder

B(i₀, m) ∩ T^-1(B(i₁, m)) ∩ ··· ∩ T^-K(B(i_K, m))

Proof. We argue by induction.

B(i₀, m) ∩ T^-1(B(i₁, m)) ∩ ··· ∩ T^-(K+1)(B(i_K+1, m)) = B(i₀, m) ∩ T^-1{B(i₁, m) ∩ ··· ∩ T^-K(B(i_K+1, m))}

p_i0L(md^K, m) = p_i0L(m, m) = p_i0i1(m, m).

Corollary 1. Under conditions (a) or (b), if p_Kjk(m) is the number of congruence classes (mod md^K) contained in B(j, m) ∩ T^-K(B(k, m)), then

[p_Kjk(m)]=[p_jk(m)]^K.

Proof. \[ B(j,m)=B(j,m)\cap\mathbb{Z}=B(j,m)\cap T^{-1}(\mathbb{Z})=\bigcup_{0\leq k\leq m-1}\left\{B(j,m)\cap T^{-1}(B(k,m))\right\}. \] Hence B(j,m) is a disjoint union of \(\displaystyle\sum_{0\leq k\leq m-1}p_{jk}(m)\) congruence classes (mod md).
But B(j,m) is a disjoint union of d congruence classes (mod md), so \[ \sum_{0\leq k\leq m-1}p_{jk}(m)=d. \]

Simplified formula for q_ij(m) when d divides m.

q_ij(m) = gcd(m_i, d) ⁄ d, if j ≡ T(i) (mod (m ⁄ d)gcd(m_i, d)), otherwise q_ij(m) = 0.

q_ij(m) = 1 ⁄ d, if j ≡ T(i) (mod m ⁄ d), otherwise 0.

\[ Q_T(3)=\left[ \begin{array}{ccc}\frac{1}{2} & 0 & \frac{1}{2}\\ 0 & 0 & 1\\ 0 &\frac{1}{2} & \frac{1}{2} \end{array} \right]. \] Under the row/column relabelling (0, 1, 2) → (1, 2, 0),
\[ Q_T(3)\to A=\left[ \begin{array}{ccc} 0 & 1 & 0\\ \frac{1}{2} & \frac{1}{2} & 0\\ 0 &\frac{1}{2} & \frac{1}{2} \end{array} \right]. \]

\[ A^n=\left[ \begin{array}{ccc} (1+(-1)^n/2^{n-1})/3&(2-(-1)^n/2^{n-1})/3 & 0 \\ (1-(-1)^n/2^n)/3&(2+(-1)^n/2^n)/3 & 0 \\ (1+(-1)^n/2^{n+1})/3 -1/2^{n+1} & (2-(-1)^n/2^{n+1})/3 -1/2^{n+1} & 1/2^n \end{array} \right]. \]

Example. (Relatively-prime case)
If A = B(j, d^a) and B = B(k, d^b), then T^-k(A) ∩ B is a disjoint union of d^k-b congruence classes (mod d^k+a) if k ≥ b.
(This fact is the basis of the strongly-mixing property, when the mapping is extended to the d-adic integers.

Proof. Express A and B as cyclinders.

Irreducible closed sets of Q_T(m) and ergodic sets of T

These are in 1-1 correspondence with the T-invariant subsets of ℤ composed of congruence classes (mod m): \[ S=\left\{j_1,\ldots,j_n\right\}\leftrightarrow\Phi(S)=B(j_1,m)\cup\cdots\cup B(j_n,m). \] Proof. Suppose S is closed. We show S' = Φ(S) is T-invariant.
This is equivalent to showing that S' ⊆ T^-1(S'), i.e., T^-1(ℤ - S') ∩ S' = ∅.
So suppose B(j, m) ⊆ S' and B(k, m) ⊆ ℤ - S'. Then j ∈ S and k ∉ S and hence q_jk = 0. Hence B(j, m) ∩ T^-1(B(k, m)) = ∅, as required. The argument is reversible.

We call the minimal T-invariant subsets of ℤ consisting of congruence classes (mod m) ergodic sets (mod m) of T. Clearly these are in 1-1 correspondence with the irreducible closed sets of Q_T(m).

The set {0,...,m-1} decomposes into a disjoint union of t irreducible sets and other elements called transient.
Correspondingly ℤ decomposes into a union of ergodic sets (mod m) and a collection of transient congruence classes.

With a suitable relabelling of the rows and columns, Q_T(m) can be transformed into the following form:

\[ \left[ \begin{array}{ccccc} A_1 & 0 & \cdots & \cdots & 0\\ 0 & A_2 & \cdots & \cdots & 0\\ \cdots & \cdots & \cdots & \cdots & 0\\ 0 & 0 & \cdots & A_t & 0\\ B_1 & B_2 & \cdots & B_t & C \end{array} \right] \]

where matrices A₁,...,A_t and C correspond to the irreducible closed sets and transient classes, respectively.

Theorem 3. If gcd(m_i, m) = 1 for i = 0,...,d-1, then Q_T(m) is doubly stochastic, i.e., each column sum is equal to 1.
Proof. \[ T^{-1}(B(k,m)) =\bigcup_{0\leq j\leq m-1}B(j,m)\cap T^{-1}(B(k, m)). \] Hence T^-1(B(k, m)) is a disjoint union of \(\displaystyle\sum_{0\leq j\leq m-1}p_{jk}(m)\) congruence classes (mod md).
However from Theorem 1, this number is d if gcd(m_i, m) = 1 for i = 0,...,d-1. Hence \[ \sum_{0\leq j\leq m-1}p_{jk}(m)=d. \] Theorem 4. If m divides m_i, where gcd(m, d) = 1, then Q_T(m) has only one irreducible closed set. Moreover if gcd(m_i, d) = 1 for i = 0,...,d-1, then the corresponding submatrix A is primitive, i.e., a suitable power is positive.
Proof. (Tony Watts 1983) Let M_i = (m_ii - r_i) ⁄ d, where m divides m_i. Also let x = amd + bd + i. Then

T(x)= (m_i(amd + bd + i) - r_i) ⁄ d = amm_i + m_ib + M_i ≡ M_i (mod m).

amd + bd + i ≡ j (mod m).

For the second part, assume gcd(m_i, d) = 1 for i = 0,...,d-1. By standard theory, if A is not primitive, it is periodic with period s and A^s has s irreducible closed sets. However it is easy to see from Corollary 1 that

Q_T^s(m) = (Q_T(m))^s.

However T^s has d^s branches and associated "m_i" equal to m_i1 ··· m_is, where 0 ≤ i₁,...,i_s ≤ d-1; also each of these numbers is relatively prime to d^s. Hence by the first part of the proof, Q_T^s(m) has but one irreducible closed set.

Corollary 2. If m divides m_i, where gcd(m_j, d) = 1 for j = 0,...,d-1, then Q(m^k) has only one irreducible closed set. Moreover the corresponding submatrix is primitive.
Proof. Suppose gcd(m_i, d) = 1 for i = 0,...,d-1. Then the d^k cylinders

B(i₀, d) ∩ T^-1(B(i₁, d)) ∩ ··· ∩ T^-(k-1)(B(i_k-1, d))

Now suppose m divides m_i. Then

B(i, d) ∩ T^-1(B(i, d)) ∩ ··· ∩ T^-(k-1)(B(i, d)) = B(j, d^k)

T^h(j) ≡ i (mod d) for h = 0,...,k-1.

However from Corollary 1,

Q_T^k(m^k) = (Q_T(m^k))^k,

Remark. A complete description of the ergodic sets in the relatively-prime case was done in paper [5].

Theorem. Let N₁ be the set of positive integers composed of primes which divide at least one m_i and let N₂ be the set of positive integers which are relatively prime to each m_i. Also let

Δ_i,j = r_j(d-m_i) - r_i(d-m_j) for 0 ≤ i < j ≤ d-1

1. If m ∈ N₂ and gcd(m, Δ) = 1, then ℤ is the only ergodic set (mod m).
2. If m ∈ N₂ and gcd(m, Δ) = δ > 1, then the ergodic sets (mod m) are the ergodic sets (mod δ).
3. If m ∈ N₁, there is only one ergodic set (mod m) with possibly some transient classes.
4. If m = m₁m₂, (m₁ > 1 and m₂ > 1) where m₁ ∈ N₁ and m₂ ∈ N₂, then the ergodic sets (mod m) are the intersections of an ergodic set (mod m₁) with an ergodic set (mod m₂), where m₂ | Δ and m₂ ∈ N₂.

Behaviour of divergent trajectories

It is not difficult to show that if limiting frequencies f₀,...,f_d-1 (mod d) exist, then

|T^k(x)|^1/k → ( |m₀|^f₀···|m_d-1|^f_d-1 ) / d,

\[ T^k(x)=\frac{x}{d^k}\prod_{0\leq i\leq k-1}m_i(x)\prod_{0\leq i\leq k-1}\frac{1-r_i(x)}{m_i(x)T^i(x)}. \] Here (i) we are assuming that Tⁱ(x) ≠ 0 and (ii) if Tⁱ(x) ≡ j (mod d), we let m_i(x) = m_j and r_i(x) = r_j.)

Conjecture 1.
Under the conditions (a) gcd(m_i, d) = 1 for 0 ≤ i ≤ d-1, or (b) gcd(m_i, d²) = gcd(m_i, d) for 0 ≤ i ≤ d-1 and d divides m, a divergent trajectory {T^k(x)} will eventually enter some ergodic set S (mod m).
If B(j, m) ⊆ S, the limiting frequency \[ \lim_{N\rightarrow\infty}\frac{1}{N}\#\left\{k < N \mid T^k(x)\equiv j\pmod{m}\right\}=\mu_S(j,m), \] where μ_S(j, m) is the j (mod m) component of the stationary vector of Q(m) for the irreducible closed set corresponding to S.

A standard result from the theory of Markov matrices tells us that \[ \mu_S(j,m)= \lim_{N\rightarrow\infty}\frac{1}{N}\sum_{k<N}\frac{card_{md^k}(T^{-k}(B(j,m))\cap S)}{card_{md^k}(S)}, \] where t = card_md^k(A) means that A is composed of t congruence classes (mod md^k).
If there are no periodic matrices in the canonical form of Q(m), the Cesàro limit can be replaced by the ordinary limit.

Without the summation sign, this limit is perhaps what one would expect the limiting frequency to be.

Conjecture 2. Let S be an ergodic set (mod d). Then

1. If \[ \prod_{B(i,d)\subseteq S}\mid\frac{m_i}{d}\mid^{\mu_S(i,d)} < 1, \] then all trajectories starting in S will eventually become periodic.
2. If \[ \prod_{B(i,d)\subseteq S}\mid\frac{m_i}{d}\mid^{\mu_S(i,d)} > 1, \] then almost all trajectories starting in S will be divergent. i.e., except for an exceptional set S of integers n satisfying #{n ∈ S | -X ≤ n ≤ X} = o(X).

In the relatively prime case (a), Q(d^a) is doubly-stochastic and ℤ is the only ergodic set (mod d^a). The corresponding stationary vector has all its components equal to 1 ⁄ d^a. Hence we have

Conjecture 3. Suppose gcd(m_i, d) = 1 for 0 ≤ i ≤ d-1. Then

1. There are finitely (≥ 1 - see Lagarias - survey) many cycles.
   The reader can find cycles by using the author's BCMATH program.
2. If |m₀···m_d-1| < d^d, then all trajectories will eventually cycle.
3. If |m₀···m_d-1| > d^d, then almost all trajectories will eventually diverge.
4. If the trajectory {T^k(x)} is divergent, then \[ \lim_{N\rightarrow\infty}\frac{1}{N}\#\left\{k < N \mid T^k(x)\equiv j\pmod{d^a}\right\}=\frac{1}{d^a}. \] Equivalently, since B(j₀, d) ∩ T^-1(B(j₁, d)) ∩ ··· ∩ T^-(a-1)(B(j_a-1, d)) runs over the d^a congruence classes (mod d^a), \[ \lim_{N\rightarrow\infty}\frac{1}{N}\#\left\{k < N \mid T^k(x)\equiv j_0\pmod{d},\ldots, T^{k+a-1}(x)\equiv j_{a-1}\pmod{d}\right\}=\frac{1}{d^a}. \]

Remarks

1. The cycling situation is not so clear if condition (b) holds, though it seems likely that we only get infinitely many cycles for trivial reasons. eg. The mapping T(2n) = 2n+1, T(2n+1) = 2n.
   Also see an example (not of type (a) or (b)) of Chris Smyth.
2. By choosing integers m₀,...,m_d-1 so that the product of their absolute values is close to, but less than d^d, we expect some trajectories may take many iterations to reach a cycle and some cycles to be rather long.

Examples of generalized 3x+1 mappings of relatively prime type

1. (The 3x+1 mapping). Here 1·3 < 2² and so condition (1) is satisfied.
   Hence we expect all trajectories to cycle. In fact there appear to be only five cycles:

   (a) 0, 0;
   (b) 1, 2, 1;
   (c) -1, -1;
   (d) -5, -7, -10, -5;
   (e) -17, -25, -37, -55, -82, -41, -61, -91, -136, -68, -34, -17.

   (The reader is invited to experiment with a BCMATH program.)

   It can be shown that if 3 does not divide m, then ℤ is the only ergodic set S (mod m), whereas is 3 divides m, ℤ-3ℤ is the only ergodic set S (mod m). (The reader can experiment with a BCMATH program.)
   In both cases, the matrix corresponding to S is primitive.

2. (The 3x+k mapping, k odd). Here 1 · 3 < 2² and so condition (1) is satisfied.
   Hence we expect all trajectories to cycle and that there will be finitely many cycles.

   Experimentally, we find that as k varies, the number of cycles is unbounded, as is the greatest length of a cycle.
   In fact, in answer to a question from the author, Alan Jones showed that with k = 2^N - 9, N = 2c + 1, the integers 2^r + 3, 1 ≤ r ≤ c generate c different cycles each of length N.

   The number of cycles for the mappings with k = 5^t appears to grow monotonically, as does the maximum cycle length.

3. More generally, consider the mapping \[ T(x)=\left\{\begin{array}{ccc} \frac{x+a}{2} &\mbox{if $x ≡ 0 \pmod{2}$}\\ \frac{3x+b}{2} &\mbox{if $x ≡ 1 \pmod{d}$}. \end{array} \right. \] where a is even and b is odd. Again we expect all trajectories to eventually cycle. We always get at least the following 5 cycles, which generalize those of the 3x+1 mapping:
   1. a, a;
   2. -b, -b;
   3. b+2a, 2b+3a, b+2a;
   4. -5b-4a, -7b-6a, -10b-9a, -5b-4a;
   5. -17b-16a, -25b-24a, -37b-36a, -55b-54a, -82b-81a, -41b-40a, -61b-60a, -91b-90a, -136b-135a, -68b-67a, -34b-33a, -17b-16a.

4. The 3-branched mapping defined by \[ T(x)=\left\{\begin{array}{ccc} \frac{x}{3} &\mbox{if $x ≡ 0 \pmod{3}$}\\ \frac{2x-2}{3} &\mbox{if $x ≡ 1 \pmod{3}$}\\ \frac{13x-2}{3} &\mbox{if $x ≡ 2 \pmod{3}$} \end{array} \right. \] is of relatively prime type and as 1 · 2 · 13 < 3³, we expect all trajectories to cycle. We have found only seven cycles, with starting values 0, 2, 47, -2, -10, -22 and -265138. The trajectory starting with x = 338 takes 7161 iterations to reach 2. Also the maximum size of an iterate is that of T²⁷²⁶(338), which has 73 digits!
5. The 4-branched mapping \[ T(x)=\left\{\begin{array}{ccc} \frac{x}{4} &\mbox{if $x ≡ 0 \pmod{4}$}\\ \frac{3x-3}{4} &\mbox{if $x ≡ 1 \pmod{4}$}\\ \frac{5x-2}{4} &\mbox{if $x ≡ 2 \pmod{4}$}\\ \frac{17x-3}{4} &\mbox{if $x ≡ 3 \pmod{4}$.} \end{array} \right. \] Here 1 · 3 · 5 · 17 = 255 = 4⁴ - 1.
   We have found 17 cycles, starting at 0, -3, 2, 3, 6 (length 1747), -18, -46, -122, -330, -117, -137, -186, -513 (length 1426), -261, -333, 5127, -5205.
6. (The 5x+1 mapping). Here 1·5 > 2² and so condition (2) is satisfied.
   Hence we expect almost all trajectories to diverge. For such trajectories we expect |T^k(x)|^1/k → √5 ⁄ 2.
   The trajectory starting with x=7 appears to diverge.
   In fact there appear to be only five cycles, with starting values 0, 1, 13, 17 and -1.

   Divergent trajectories appear to occupy the congruence classes (mod 5) with limiting frequencies 0, 1 ⁄ 15, 2 ⁄ 15, 8 ⁄ 15 and 4 ⁄ 15.

   \[ Q(5)=\left[ \begin{array}{ccccc} 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{array} \right]. \] Here 1, 2, 3, 4 form an ergodic set for Q(5) and 0 is the only transient state.

   On relabelling the states as 1, 2, 3, 4, 0, Q(5) transforms to canonical form \[ \left[ \begin{array}{ccccc} 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 & 0\\ 0 & 0 & 1/2 & 0 & 1/2 \end{array} \right] \] and the stationary vector of the submatrix formed by the first 4 rows and columns is \((\frac{1}{15}, \frac{2}{15},\frac{8}{15},\frac{4}{15}\)).

   The zero limiting frequency is easily explained: if x = 2c + 1, then T(x) = 5c + 3, so clearly every trajectory starting from a non-zero integer will eventually reach B(3, 5).

7. (The 5x-3 mapping). Here B(0,3) and B(1,3) ∪ B(2,3) are ergodic sets (mod 3). This may be seen directly or from \[ Q(3)=\left[ \begin{array}{ccc} 1 & 0 & 0\\ 0 & 1/2 & 1/2\\ 0& 1/2 & 1/2 \end{array} \right]. \] The trajectory starting with -7 appears to be divergent.
   There appear to be 10 cycles, with starting numbers 0, -1, 1, -3, 3, -39, -43, -51, -53, -61.