The generalized 3x+1 mapping: George Leigh's approach

  1. Introduction
  2. The generalized 3x+1 function
  3. The motivating example
  4. Definitions
  5. The crucial lemma
  6. The main theorem
  7. The Markov matrix QT(m)
  8. An example from paper [3]
  9. A finiteness theorem of G. Venturini
  10. A BCMATH program for constructing QT(m) and finding its irreducible closed sets
  11. Some examples of G. Venturini: Example 1, Example 2, Example 3, Example 4,
  12. Example of Chris Smyth.
  13. BCMATH cycling-finding program
  14. References
Introduction

This online paper is based on a paper of George Leigh which generalized papers [1,2] by Tony Watts and myself.

George came up with his approach in the course of doing an honours thesis in 1983. He had in the previous year done a course in Markov chains with Barry Quinn and amazed me by coming up with a Markov chain explanation of the behaviour of 3x+1 type mappings that could not be dealt with by the Matthews-Watts heuristics. George worked over the l-adic integers, where l = lcm(d, m) (see below). This is because of the need to work in a probability space.

However, in my account, I am avoiding the language of Markov chains and we can avoid l-adic integers and work with ordinary congruence classes of integers. Also it seemed simpler to assume that d divides m, so that l = m.

My proof of the main theorem is different from his and is modelled on the one given in my online generalized 3x+1 paper. I have left out details. The reader may prefer Leigh's proof.

The only person who seems to have followed up on George's paper was G. Venturini who clearly had great insights into George's work. (See paper [4] below.) His paper contains a number of interesting examples and deals only with the important case of m = d. Also he came up with a sufficient condition for the chains to be finite. He defines on page 187 g-ergodic sets, which seem to be our SC below. Also he had an example where unexpectedly SC ⊆ SC'.
(I did not find his papers easy reading.)
Venturini's paper is based on Leigh's Markov chain Xn(x), rather than Yn(x) and like Leigh, his matrix examples are given for the Xn(x) chain.

The transition matrix for the Xn(x) chain is smaller in general than that of the Yn(x) chain. However I prefer the latter, as it generalises the Matthews-Watts QT(m), in the case where d divides m.

I have written an online BCMATH version of Leigh's fortran program for the Yn(x) Markov matrix QT(m).


Let d ≥ 2 and m0,...,md-1 be non-zero integers. Also r0,...,rd-1 are integers satisfying r ≡ imi (mod d). Then T: ℤ → ℤ is defined by

T(x) = (mix - ri) ⁄ d if x ≡ i (mod d).

Our aim is to predict the limiting frequency of occupancy of a congruence class B(j, m) = {x ∈ ℤ | x ≡ j (mod m)} by a divergent trajectory x, T(x), T2(x),... and also to predict cycling and divergence of trajectories.

Paper [1] assumes (a) gcd(mi, d) = 1 for 0 ≤ i ≤ d-1, while paper [2] assumes either (a) holds or (b) gcd(mi, d2) = gcd(mi, d) for 0 ≤ i ≤ d-1 and d divides m.

Motivating example.

12x - 1 if x ≡ 0 (mod 4)
T(x) = 20x if x ≡ 1 (mod 4)
(3x - 6) ⁄ 4 if x ≡ 2 (mod 4)
(x - 3) ⁄ 4 if x ≡ 3 (mod 4).

Here m0 = 48, m1 = 80, m2 = 3, m3 = 1 and r0 = 4, r1 = 0, r2 = 6, r3 = 3.
Also gcd(m0, d2) = gcd(48, 16) = 16, whereas gcd(m0, d) = gcd(48, 4) = 4.

Next observe: if x ≡ 0 (mod 4) (state 0)

while if x ≡ 1 (mod 4) (state 1) Leigh then writes down a transition matrix A which is to be interpreted as representing the probability of being in state j,
starting in state i, for 0 ≤ i, j ≤ 7:

00 0 0  1  0   0   0 
0 0 0 0 0 1 00
¼¼¼¼0 0 0 0
¼ ¼ ¼ ¼ 0 00 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

A is primitive (A8 is a positive matrix) and its stationary vector is (·1, ·1, ·2, ·2, ·1, ·1, ·1, ·1).

Notice that as sets,

So the limiting frequencies of occupation of congruence classes B(0, 4), B(1, 4), B(2, 4) and B(3, 4) by divergent trajectories can be expected to be

(·1 + ·1, ·1, ·2, ·2 + ·1 + ·1 + ·1) = (·2, ·1, ·2, ·5).

An can be interpreted as giving the probability that Tn(x) is in state j, given that x is in state i.

We will eventually see how A allows us to calculate card4n+1{B(i, 4) ∩ T-n(B(j, 4))} where t = cardm(A) means that A is composed of t congruence classes (mod m).

The trajectory starting with 21 appears to be divergent.
We note that there appear to be 6 cycles, with starting numbers (and lengths) -1 (1), 5(81), -19(86), -4(3), -6(1), 19133(342).

Definition. For non-zero integers x, integers C(x) and D(x) ≥ 1, are defined by

x = C(x)D(x), where gcd(C(x), d) = 1 and D(x) is a divisor of some power of d.

Also let di = D(mi ) and extend the definition to arbitrary i by di = di (mod d).

As George Leigh pointed out in his paper, the condition gcd(mi,d2)=gcd(mi,d) is equivalent to di divides d.

From now on we assume that d divides m. Also [a, b] denotes lcm(a, b).

Define a sequence of congruence classes Y0(x),Y1(x),... recursively by Yn(x) = B(Tn(x), Kn), where

M0 = 1, K0 = m and Tn(x) ≡ jn (mod d), Kn = [Mn, m], Mn+1 = Kndjn ⁄ d.

In particular, Y0(x)=B(x,m).

(Leigh also defines congruence classes X0(x),X1(x),... recursively by Xn(x) = B(Tn(x), Mn).)

Remark. In the Matthews-Watts case, where dj divides d for all j, we see that Kn = m for all n.

Lemma. For n ≥ 0, Kn = mkn and Mn+1 = (m ⁄ d)M'n+1, where kn and M'n+1 divide some power of d.

Proof. True when n = 0, as K0 = m.
Now assume Kn = m kn, where kn divides some power of d. Then

Kn+1 = [Mn+1, m] = [Kndjn ⁄ d, m]
= (Kndjnm ⁄ d)/gcd(Kndjn ⁄ d, m)
= m(kndjn)/gcd(kndjn, d)

and the induction goes through.

The result for M'n then follows.

Definition. Let Θ denote the set of congruence classes of the form B(y, mK), where K divides some power of d.

Then Yn(x) ∈ Θ for all integers n ≥ 0 and x.

Lemma. Let Bn=B(jn, mLn) ∈ Θ for 0 ≤ n ≤ K and let S = {x ∈ ℤ | Y0(x) = B0,...,YK(x) = BK}.
Then if S is non-empty, we have

Ln+1 = (Lndjn)/gcd(Lndjn, d) for 0 ≤ n ≤ K-1.

Conversely, if this condition holds, then

S = B0 ∩ T-1(B1)∩ ··· ∩ T-K(BK).

Consequently S is either empty, or a disjoint union of congruence classes (mod mdKL0).

Theorem. As in the previous lemma, let S = {x ∈ ℤ | Y0(x) = B0,...,YK(x) = BK}. Then S is a disjoint union of pB0,...,BK congruence classes (mod mdKL0) where

pB0,...,BK = pB0,B1 ··· pBK-1,BK,

and pBi-1,Bi = cardmdLi-1 Bi-1 ∩ T-1(Bi).

Leigh's proof depends on the following result (equation (42), p. 132): There exists U, w, gcd(w,d)=1, such that for all integers a,

Tn(x+aU)=Tn(x)+awM_n.

For our proof we need the following result.

Lemma. Suppose M = (Ldj)/gcd(Ldj, d), where L and M divide some power of d.
Then B(j, mL) ∩ T-1(B(k, mdnM)) is a disjoint union of pjk(mdnM, mL) congruence classes (mod mdn+1L), where

pjk(mdnM, mL) = gcd(Ldj, d) if mLdj ⁄ d divides k - T(j) and 0 otherwise.

Proof. We have to solve

x ≡ j (mod mL) & (mjx-rj) ⁄ d ≡ k (mod mdnM).

Let x = j + tmL. Then we have to solve

(mjx-rj) ⁄ d = T(j) + (tmLmj) ⁄ d ≡ k (mod mdnM).

This is soluble if and only if gcd((mmjL) ⁄ d, mdnM) divides k - T(j).

Now

gcd((mmjL) ⁄ d, mdnM) = (m ⁄ d)gcd(mjL, dn+1M)
= (m ⁄ d)gcd(djL, dn+1M)
= (m ⁄ d)gcd(Mgcd(Ldj, d), dn+1M)
= (mM ⁄ d)gcd(gcd(Ldj, d), dn+1)
= (mM ⁄ d)gcd(Ldj, d, dn+1)
= (mM ⁄ d)gcd(Ldj, d)
= (mLdj) ⁄ d.

If soluble, the solution t is unique (mod mdnM/(mLdj ⁄ d)) ie. mod (dn+1M/Ldj).
Hence the solution for x is unique (mod (dn+1M/Ldj)mL) ie. (mod mdn+1M ⁄ dj). But

mdn+1M ⁄ dj = mdn+1Ldj/gcd(Ldj, d).

Consequently there are gcd(Ldj, d) solutions mod (mdn+1L).

Proof of Theorem. (Added 9th April 2010). We use induction on K. It's clearly true when K=1.
Let S = {x ∈ ℤ | Y0(x) = B0,...,YK+1(x) = BK+1}.
If S is non-empty, it can be written as S = B0 ∩ T-1(B1∩⋯∩ T-K(BK+1)).
By the induction hypothesis, B1(x) ∩⋯∩ T-K(BK+1) is a disjoint union of pB1B2⋯pBKBK+1 congruence classes mod mdKL1 of the form B(u, mdKL1) say.
Then u ≡ j1 (mod mL1) and j1 ≡ T(j0) (mod mL1). Hence u ≡ T(j0) (mod mL1). Hence u ≡ T(j0) (mod mL0dj0/gcd(L0dj0, d)) and hence (mod mL0dj0/d).
Then by the Lemma, B0 ∩ T-1(B(u, mdKL1)) is a disjoint union of gcd(L0dj0, d) = pBoB1 congruence classes (mod mdK+1L0). This gives a total of pB0B1⋯pBKBK+1 congruence classes (mod mdK+1L0) and the induction goes through.

Assumption. From now on we assume that the set ΘT formed by the congruence classes Yn(x), is finite.

Corollary. Let P = [pBB'], where B, B' ∈ ΘT. Then

cardmd^K{x ∈ ℤ | Y0(x) = B0, YK(x) = B1} = p(K)B0B1, where PK = [p(K)BB'].

The following result generalises Corollary 1 of Matthews-Watts:

Corollary. Assuming as usual, that d divides m, let

pKjk = cardmdK{x ∈ ℤ | x ≡ j (mod m), TK(x) ≡ k (mod m)}.

Then

pKjk = ∑B ⊆ B(k, m)p(K)B(j, m)B

Proof. Then because Kn is a multiple of m, we have

YK(x) ⊆ B(k, m) ⇔ TK(x) ≡ k (mod m).

Hence

pKjk = cardmdK{x ∈ ℤ | YK(x) ⊆ B(k, m), Y0(x) = B(j, m)}
= B ⊆ B(k, m)cardmdK{x ∈ ℤ | YK(x) = B, Y0(x) = B(j, m)}
= B ⊆ B(k, m)p(K)B(j, m)B.

Lemma. QT(m) = [pBB' ⁄ d] is a Markov matrix.
Proof. Let B ∈ ΘT, B = B(j, mL). Then

B = {x ∈ ℤ | Y0(x) = B} = ∪B' ∈ ΘT {x ∈ ℤ | Y0(x) = B, Y1(x) = B'}.

Hence B is a disjoint union of ∑B' ∈ ΘT pBB' congruence classes (mod mLd).
However B is also a disjoint union of d congruence classes (mod mLd). Hence

B' ∈ ΘT pBB' = d.

Theorem. Let C be an irreducible closed set of QT(m) and SC = ∪B ∈ CB. Then SC is a T-invariant set.
Proof. Suppose x∈SC. Then x∈B, B∈C. Now B=B(Tn(y), Kn)=B(x, Kn).

Now using an earlier-mentioned result of Leigh, the congruence classes B'=B(T(x)+tMn+1, Kn+1) belong to Ω and satisfy qBB'>0 and hence belong to C. The desired result then follows on taking t=0.

Conjecture. Every divergent trajectory will eventually enter some SC and will occupy each congruence class B of C with limiting frequency ρB, where ρB is the stationary value of QT(m) corresponding to B. Then the limiting frequency of occupancy of B(i, m) will be given by

pi = ∑B ∈C, B ⊆ B(i, m)ρB.

Conjecture. Let C be an irreducible closed set of QT(d). Then if

0≤i≤d-1|mi ⁄ d|pi < 1,

all trajectories starting in SC will eventually cycle.
However if

0≤i≤d-1|mi ⁄ d|pi > 1,

almost all trajectories starting in SC will diverge.

Here is a link to a BCMATH program for constructing the matrix QT(m). It is based on one provided by George Leigh to the author in March 1995.

Example. (G. Leigh [3], Example 1, page 139.) Let

3x - 1if x ≡ 0 (mod 3)
T(x) = (x - 16) ⁄ 3if x ≡ 1 (mod 3)
(-4x - 7) ⁄ 3if x ≡ 2 (mod 3)

Here m0 = 9, m1 = 1, m2 = -4; X0 = -1, X1 = -5, X2 = -2; d0 = 9, d1 = 1, d2 = 1.

The program finds 4 states and transition matrix QT(3) according to the following scheme:

B(0,3)→B(8,9)→B(8,9)

B(1,3)→B(0,1)→B(0,3)
              →B(1,3)
              →B(2,3)

B(2,3)→B(0,1)→B(0,3)
              →B(1,3)
              →B(2,3)

B(8,9)→B(2,3)→B(2,3)
States:
1:B(0,3), 2:B(1,3), 3:B(2,3), 4:B(8,9),

QT(3)
(0,3)(1,3)(2,3)(8,9)
(0,3)0 0 0 1
(1,3)0
(2,3)0
(8,9)0 0 1 0

(QT(3))4 > 0, so B(0,3), B(1,3), B(2,3) and B(8,9) form an ergodic chain, with stationary vector (1/5,1/5,2/5,1/5).
Now B(8,9) ⊆ B(2,3). Consequently p0 = 1/5, p1 = 1/5, p2 = 2/5 + 1/5 = 3/5.
Hence the weighted product ∏0≤i≤d-1|mi ⁄ d|pi = (9/3)1/5(1/3)1/5(4/3)3/5 = (4/3)3/5 > 1.

Hence we expect most trajectories to diverge.

The trajectory starting with x = 1 appears to diverge.

There appear to be 3 cycles: -1 → -1, -8 → -8 and 421 → 135 → 404 → -541 → 719 → -961 → 1279 → 421.

Leigh does the case m = 6. We get states B(0,6), B(1,6), B(2,6), B(3,6), B(4,6), B(5,6), B(17,18), B(8,18), with ergodic chain B(1,6),B(3,6),B(5,6),B(8,18).

The stationary vector is (1/5,1/5,2/5,1/5).

Example. (G. Leigh [3], Example 2, pages 140-141.) Let

x / 4if x ≡ 0 (mod 8)
(x+1) / 2if x ≡ 1 (mod 8)
20x - 40if x ≡ 2 (mod 8)
T(x) = (x - 3) / 8if x ≡ 3 (mod 8)
20x + 48if x ≡ 4 (mod 8)
(3x - 13) / 2if x ≡ 5 (mod 8)
(11x - 2) / 4if x ≡ 6 (mod 8)
(x + 1) / 8if x ≡ 7 (mod 8)

Here m0=2, m1=4, m2=160, m3=1, m4=160, m5=12, m6=22, m7=1;
X0=0, X1=1, X2=-40, X3=0, X4=48, X5=-6, X6=0, X7=1.

We find there are 9 classes in ΘT:

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 Markov matrix QT(8) =

¼00¼0¼0¼0
1  0  0000000
00½000½00
010000000
0
010000000
00½000½00
¼00¼0¼0¼0
0

There are two irreducible closed sets: C1 = {B(1, 8), B(5, 8)} and C2 = {B(0, 8), B(0, 32), B(2, 8), B(4, 8), B(6, 8)}.

The stationary values are ½, ½ and ⅜, ¼, ⅛, ⅛, ⅛.

For C1, we have p1 = p2 = ½ and as

(½)½(3/2)½ < 1,

we expect all trajectories starting in SC1 = B(1, 8) ∪ B(5, 8) to cycle.

For C2, we have p0 = ⅜ + ¼ = ⅝ and p2 = p4 = p6 = ⅛. Then as

(¼)2020(11/4) > 1,

we expect most trajectories starting in SC2 = B(0, 2) to diverge.

(Leigh uses another Markov chain Xn(x) and arrives at limiting frequencies 4/7, 1/7, 1/7, 1/7, which are erroneous, as one soon discovers on observing the apparently divergent trajectory starting at 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.

Theorem. (G. Venturini - Theorem 7, p. 196). Let

Dν(x)= dj0 ··· djν-1, where Ti(x) ≡ ji (mod d) for 0 ≤ i ≤ ν-1.

Suppose Dν(x) divides dν for all x, 0 ≤ x < dν. Then Kn(x) = mkn(x) and Mn(x) = (m ⁄ d)M'n(x), where kn(x) divides dν-1 and M'n(x) divide dν for all n ≥ 0.

Remarks.
  1. Venturini defines T to be of type Gν if T has the property of the last theorem and ν is minimal. Otherwise T is of type G.
  2. Venturini gives two examples (6 and 7, pp. 210-211) of mappings T which belong to G but for which ΘT has only finitely many states.
We need some lemmas of Venturini:

Lemma.

kn(x) = Dn(x)/D'n(x), M'n(x) = (m ⁄ d) Dn(x)/D'n-1(x),

where D0(x) = 1 = D'0(x) and D'n+1(x) = gcd(Dn+1(x), dD'n(x).)

Corollary.

D'n(x) = gcd(Dn(x), dDn-1(x),...,dn-1D1(x), dn).

Corollary. If Dν(x) divides dν, then

M'ν+1(x) = M'ν(T(x)).

Proof. Using the result Dν(x) = D1(x)Dν-1(T(x)), we have

D'ν(x) = gcd(Dν(x), dDν-1(x),...,dν-1D1(x), dν)
= gcd(Dν(x), dDν-1(x),...,dν-1D1(x))
= D1(x)gcd(Dν-1(T(x)), dDν-2T((x)),...,dν-1)
=D1(x)D'ν-1(T(x)).

Hence

M'ν+1(x) = Dν+1(x)/D'ν(x) = D1(x)Dν(T(x))/D1(x)D'ν-1(T(x)) = Dν(T(x))/D'ν-1(T(x)) = M'ν(T(x)).

The theorem now follows.

Example 1. (G. Venturini [4] Example 1, 205-206)

T(x) = :
(2500x ⁄ 6) + 1 if x ≡ 0 (mod 6)
(21x - 9) ⁄ 6 if x ≡ 1 (mod 6)
(x + 16) ⁄ 6 if x ≡ 2 (mod 6)
(21x - 51) ⁄ 6 if x ≡ 3 (mod 6)
(21x - 72) ⁄ 6 if x ≡ 4 (mod 6)
(x + 13) ⁄ 6 if x ≡ 5 (mod 6).

Here
m0 = 2500, m1 = 21, m2 = 1, m3 = 21, m4 = 21, m5 = 1;
X0 = 1, X1 = -1, X2 = 3, X3 = -8, X4 = -12, X5 = 3.
Also
d0 = 4, d1 = 3, d2 = 1, d3 = 3, d4 = 3, d5 = 1.

We find 9 states according to the following scheme:

B(0,6)→B(1,4)→B(1,12)
              →B(5,12)
              →B(9,12)

B(1,6)→B(2,3)→B(2,6)
              →B(5,6)

B(2,6)→B(0,1)→B(0,6)
              →B(1,6)
              →B(2,6)
              →B(3,6)
              →B(4,6)
              →B(5,6)

B(3,6)→B(2,3)→B(2,6)
              →B(5,6)

B(4,6)→B(2,3)→B(2,6)
              →B(5,6)

B(5,6)→B(0,1)→B(0,6)
              →B(1,6)
              →B(2,6)
              →B(3,6)
              →B(4,6)
              →B(5,6)
  
B(1,12)→B(2,6)→B(2,6)

B(5,12)→B(1,2)→B(1,6)
               →B(3,6)
               →B(5,6)

B(9,12)→B(5,6)→B(5,6)

QT(6)
(0,6)(1,6)(2,6)(3,6)(4,6)(5,6)(1,12)(5,12)(9,12)
(0,6)0 0 0 0 0 0
(1,6)0 0 ½ 0 0 ½ 0 0 0
(2,6)0 0 0
(3,6)0 0 ½ 0 0 ½ 0 0 0
(4,6)0 0 ½ 0 0 ½ 0 0 0
(5,6)0 0 0
(1,12)0 0 1 0 0 0 0 0 0
(5,12)0 0 0 0 0 0
(9,12)0 0 0 0 0 1 0 0 0

States 1, 7, 3, 2, 4, 5, 6, 8, 9 constitute an ergodic chain.

The stationary vector of QT(6) is (1 ⁄ 202)(18, 20, 53, 20, 18, 55, 6, 6, 6).
Noting that B(1,12) ⊆ B(1,6), B(5,12) ⊆ B(5,6), B(9,12) ⊆ B(3,6), we calculate expected frequencies

p0=9/101, p1=13/101, p2=53/202, p3=13/101, p4=9/101, p5=61/202.

Also

0≤i≤5(mi ⁄ d)pi = (2500 ⁄ 6)9/101(21 ⁄ 6)13/101(1 ⁄ 6)53/202(21 ⁄ 6)13/101(21 ⁄ 6)9/101(1 ⁄ 6)61/202 = (536735 ⁄ 283366)1/101 < 1.

Hence we expect all trajectories to eventually cycle.

In fact there appear to be just two cycles:

(a) 2,3,2 and
(b) 6, 2501, 419, 72, 30001, 105002, 17503, 61259, 10212, 4255001, 709169, 118197, 413681, 68949, 241313, 40221, 140765, 23463, 82112, 13688, 2284, 7982, 1333, 4664, 780, 325001, 54169, 189590, 31601, 5269, 18440, 3076, 10754, 1795, 6281, 1049, 177, 611, 104, 20, 6.

Interested viewers can experiment with a BCMATH program.

Example 2. (G. Venturini [4] Example 7, 210-211)

T(x) = :
x ⁄ 3 if x ≡ 0 (mod 6)
(2x - 2) ⁄ 3 if x ≡ 1 (mod 6)
(5x - 4) ⁄ 3 if x ≡ 2 (mod 6)
4x ⁄ 3 if x ≡ 3 (mod 6)
(5x - 8) ⁄ 3 if x ≡ 4 (mod 6)
(4x - 2) ⁄ 3 if x ≡ 5 (mod 6).

Here
m0 = 2, m1 = 4, m2 = 10, m3 = 8, m4 = 10, m5 = 8;
X0 = 0, X1 = 0, X2 = -1, X3 = 0, X4 = -2, X5 = 0.
d0 = 2, d1 = 4, d2 = 2, d3 = 8, d4 = 2, d5 = 8.

We find 21 states according to the following scheme:

B(0,6)→B(0,2)→B(0,6)
              →B(2,6)
              →B(4,6)

B(1,6)→B(0,4)→B(0,12)
              →B(4,12)
              →B(8,12)

B(2,6)→B(0,2)→B(0,6)
              →B(2,6)
              →B(4,6)

B(3,6)→B(4,8)→B(4,24)
              →B(12,24)
              →B(20,24)

B(4,6)→B(0,2)→B(0,6)
              →B(2,6)
              →B(4,6)

B(5,6)→B(6,8)→B(6,24)
              →B(14,24)
              →B(22,24)

B(0,12)→B(0,4)→B(0,12)
               →B(4,12)
               →B(8,12)

B(4,12)→B(0,4)→B(0,12)
               →B(4,12)
               →B(8,12)

B(8,12)→B(0,4)→B(0,12)
               →B(4,12)
               →B(8,12)

B(4,24)→B(4,8)→B(4,24)
               →B(12,24)
               →B(20,24)

B(12,24)→B(4,8)→B(4,24)
                →B(12,24)
                →B(20,24)

B(20,24)→B(0,8)→B(0,24)
                →B(8,24)
                →B(16,24)

B(6,24)→B(2,8)→B(2,24)
               →B(10,24)
               →B(18,24)

B(14,24)→B(6,8)→B(6,24)
                →B(14,24)
                →B(22,24)

B(22,24)→B(2,8)→B(2,24)
                →B(10,24)
                →B(18,24)

B(0,24)→B(0,8)→B(0,24)
               →B(8,24)
               →B(16,24)

B(8,24)→B(4,8)→B(4,24)
               →B(12,24)
               →B(20,24)

B(16,24)→B(0,8)→B(0,24)
                →B(8,24)
                →B(16,24)

B(2,24)→B(2,8)→B(2,24)
               →B(10,24)
               →B(18,24)

B(10,24)→B(6,8)→B(6,24)
                →B(14,24)
                →B(22,24)

B(18,24)→B(6,8)→B(6,24)
                →B(14,24)
                →B(22,24)
States:
1:(0,6), 2:(1,6), 3:(2,6), 4:(3,6), 5:(4,6), 6:(5,6), 7:(0,12), 8:(4,12), 9:(8,12), 10:(4,24), 11:(12,24), 12:(20,24), 13:(6,24), 14:(14,24), 15:(22,24), 16:(0,24), 17:(8,24), 18:(16,24), 19:(2,24), 20:(10,24), 21:(18,24),
QT(6)
 (0,6) (1,6) (2,6) (3,6) (4,6) (5,6)(0,12)(4,12)(8,12)(4,24)(12,24)(20,24)(6,24)(14,24)(22,24)(0,24)(8,24)(16,24)(2,24)(10,24)(18,24)
(0,6)0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
(1,6)0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
(2,6)0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
(3,6)0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
(4,6)0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
(5,6)0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
(0,12)0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
(4,12)0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
(8,12)0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
(4,24)0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
(12,24)0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
(20,24)0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
(6,24)0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
(14,24)0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
(22,24)0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
(0,24)0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
(8,24)0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
(16,24)0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
(2,24)0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
(10,24)0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
(18,24)0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

1, 3, 5, constitute ergodic chain[1] ie. B(0,6), B(2,6), B(4,6);
7, 8, 9, constitute ergodic chain[2] ie. B(0,12), B(4,12), B(8,12);
10, 11, 12, 16, 17, 18, constitute ergodic chain[3] ie. B(4,24), B(12,24), B(20,24), B(0,24), B(8,24), B(16,24);
13, 19, 20, 14, 15, 21, constitute ergodic chain[4] ie. B(6,24), B(2,24), B(10,24), B(14,24), B(22,24), B(18,24);
2, 4, 6 are the transient states ie. B(1,6), B(3,6), B(5,6).

row/column permutation:
(1, 3, 5, 7, 8, 9, 10, 11, 12, 16, 17, 18, 13, 19, 20, 14, 15, 21, 2, 4, 6)
canonical form of QT(6)=
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0  0  0  0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Let Si be the union of the congruence classes that make up chain[i].
This example is curious, as S3=S2=B(0,4) ⊆ S1=B(0,2) and S4=B(2,4) ⊆ S1. Also S1=S2∪S4.

QT(6) is a doubly-stochastic matrix.
So the stationary vectors of the relevant 3×3 and 6×6 submatrices are (⅓,⅓,⅓) and (⅙,⅙,⅙,⅙,⅙) respectively.

The corresponding weighted product for chain[1] and chain[2] is

0≤i≤d-1|mi ⁄ d|pi = (2 ⁄ 6)(10 ⁄ 6)(10 ⁄ 6) = 25 ⁄ 3 < 1.

Hence we expect all trajectories starting in the even integers to eventually cycle. Note that T(B(1,2)) ⊆ B(0,2).

We believe that there are 9 cycles:

cycle 1: 0, 0
cycle 2: -6, -2, -6
cycle 3: 2, 2
cycle 4: -16, -28, -48, -16
cycle 5: 4, 4
cycle 6: -78, -26, -46, -78
cycle 7: -22, -38, -66, -22
cycle 8: -32, -56, -96, -32
cycle 9: 2454, 818, 1362, 454, 754, 1254, 418, 694, 1154, 1922, 3202, 5334, 1778, 2962, 4934, 8222, 13702, 22834, 38054, 63422, 105702, 35234, 58722, 19574, 32622, 10874, 18122, 30202, 50334, 16778, 27962, 46602, 15534, 5178, 1726, 2874, 958, 1594, 2654, 4422, 1474, 2454.
(length of cycle 9 is 41)

Interested viewers can experiment with a BCMATH program.

Venturini gave two examples of mappings where the chain {Yn} is infinite. In his Example 8, p. 211, heuristic reasoning implied that all trajectories eventually cycle. There appear to be 8 cycles. In his Example, section 7.4, p. 212, he could prove that all trajectories eventually cycle into specified cycles.

Example 3. (G. Venturini [4] Example 8, p. 211-212)

T(x) = :
x ⁄ 3 if x ≡ 0 (mod 6)
(x - 1) ⁄ 3 if x ≡ 1 (mod 6)
(5x + 5) ⁄ 3 if x ≡ 2 (mod 6)
(3x + 5) ⁄ 2 if x ≡ 3 (mod 6)
(3x + 2) ⁄ 2 if x ≡ 4 (mod 6)
(3x - 1) ⁄ 2 if x ≡ 5 (mod 6).

Here
m0 = 2, m1 = 2, m2 = 10, m3 = 9, m4 = 9, m5 = 9;
X0 = 0, X1 = 0, X2 = 2, X3 = 3, X4 = 1, X5 = 0.
d0 = 2, d1 = 2, d2 = 2, d3 = 9, d4 = 9, d5 = 9.

Y0(3)=B(3,6), Y1(3)=B(16,18), Y2(3)=B(52,54), Y3(3)=B(160,162), etc.

There appear to be 8 cycles: 0 (1), -2 (1), 2, (3), 8, (3), -10 (4), -82 (7), -52 (7), 6038 (52).

Example 4. (G. Venturini [4] Example section 7.4, p. 212) This is a 2p-branched map, where p > 1 is odd. As pointed out by G. Venturini, the chain has infinitely many states and the behaviour of the iterates can be established directly.

T(2pq + r)=4q + r if r < p,
T(2pq + r)=p2q + r if r ≥ p.

Venturini points out that if x=2k(2y+1)p+r, k ≥ 0 and 0 ≤ r < 2p where |x| ≥ 2p, there is an n ∈ {1, 2k + 1, 2k + 3, 2k + 5} such that |Tn(x)| < |x| and consequently every trajectory meets a fixed point T(r)=r, or one of the two cycles with T5(-1) = -1, or T5(-2) = -2. If p = 3, there is only the one cycle, starting with -2, as T(-1) = T4(-2).

cycle 1: -1, -p2 + p - 1, -p + 1, -p2 + p + 1, -2p + 3, -1.
cycle 2: -2, -p2 + 2p - 2, -p, -p2 + p, -2p + 2, -2.

For the mapping

T(2pq + r)=p2q + r if r < p
T(2pq + r)=4q + r if r ≥ p,

Venturini remarks that the above two cycles are replaced by similar ones starting with 2p and 2p + 1, with only one cycle when p = 3, starting with 7.

cycle 1: 2p, p2, 3p - 2, p2 + p - 2, 4p - 4, 2p.
cycle 2: 2p + 1, p2+1, 3p - 1, p2 + p - 1, 4p - 3, 2p+1.

Example 5

T(x)=
int(7x/6) if x ≡ 0 (mod 6)
int(21x/6) if x ≡ 1 (mod 6)
3x if x ≡ 2 (mod 6)
int(4x/6) if x ≡ 3 (mod 6)
2x if x ≡ 4 (mod 6)
int(27x/6) if x ≡ 5 (mod 6).

There are three positive recurrent classes:

C1={B(4,6), B(8,12), B(24,36)
C2={B(22,54), etc}
C3={B(10,12), B(20,24), B(60,72).

SC2 and SC3 intersect non-trivially. The trajectory starting with x=-1 appears to be divergent and inhabits the intersection. There appears to be one cycle 0, 0.

Example 6. T(x) = 3x ⁄ 2 if x is even, int(2x ⁄ 3) if x is odd, was suggested by Chris Smyth when the author visited Edinburgh in 1993. Here all trajectories eventually enter a cycle, namely cycles 6n → 9n → 6n (n nonzero) and 6n+3 → 4n+2 → 6n+3, or the fixed points 0 and -1. This was pointed out by George Leigh in an email of 14th December 1993.
The chain {Yn} is infinite, as Yn(0) = B(0, 2·3n+1) for n ≥ 0.

References

  1. K.R. Matthews and A.M. Watts, A generalization of Hasse's generalization of the Syracuse algorithm, Acta Arith. 43 (1984) 167-175.
  2. - -, A Markov approach to the generalized Syracuse algorithm, ibid. 45 (1985) 29-42.
  3. G.M. Leigh, A Markov process underlying the generalized Syracuse algorithm, ibid. 46 (1986) 125-143.
  4. G. Venturini, Iterates of number-theoretic functions with periodic rational coefficients (generalization of the 3x+1 problem), Stud. Appl. Math. 86 (1992), no.3, 185-218.
Top of page

Last modified 7th April 2016