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).
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.
Definition. For non-zero integers x, integers C(x) and D(x) ≥ 1, are defined byx = 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. (Leigh was interested in the behaviour of trajectories mod (m) for arbitrary m ≥ 2, and took [m, d] = lcm(m, d).
Define a sequence of congruence classes \(Y_0(x), Y_1(x),\ldots\) by \[ \begin{align*} Y_0(x)&=B(x,m);\\ Y_{n+1}(x)&=B(T^{n+1}(x),mk_{n+1}), n \ge 0, \end{align*} \] where \(k_0=1\) and \(k_{n+1}=\frac{k_nd_j}{\gcd(k_nd_j, d)}\), and where \(j\) is determined by the congruence \(T^n(x)\equiv j\pmod{d}, 0\leq j \leq d-1\).
(Leigh also defined congruence classes \(X_0(x), X_1(x),\ldots\) by
\(X_0(x)=B(0,1)\);
\(X_{n+1}(x)=B(T^{n+1}(x),\frac{mk_nd_j}{d})\) if \(n \ge 0\),
where \(j\) is determined by the congruence \(T^n(x)\equiv j\pmod{d}, 0\leq j \leq d-1\).)
Remark. In the Matthews-Watts case, where dj divides d for all j, we see that Yn(x) = B(Tn(x), m) for all n.
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, thenS = 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 solvex ≡ 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. |
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 \[ p_{Kjk}=\sum_{B\subseteq B(k, m)}p^{(K)}_{B(j, m)B} \] Proof. Then because Kn is a multiple of m, we haveYK(x) ⊆ B(k, m) ⇔ TK(x) ≡ k (mod m).
Hence
\[
\begin{align*}
p_{Kjk}&=\text{card}_{md^K}\{x\in \mathbb{Z} \mid Y_K(x)\subseteq B(k,m), Y_0(x)=B_(j,m)\}\\
&=\sum_{B\subseteq B(k,m)}\text{card}_{md^K}\{x\in \mathbb{Z} \mid Y_K(x)=B, Y_0(x)=B_(j,m)\}\\
&=\sum_{B\subseteq B(k,m)}p^{(K)}_{B(j,m)B}.
\end{align*}
\]
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).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
\[
p_i=\sum_{B\in C, B\subseteq B(i,m)}\rho_B.
\]
Conjecture. Let C be an irreducible closed set of QT(d). Then if
\[
\prod_{\begin{array}{c}0\le i\le d-1\\C\cap B(i,d)\neq\emptyset\end{array}}\biggm|\frac{m_i}{d}\biggm|^{p_i}<1,
\]
all trajectories starting in SC will eventually cycle.
However if
\[
\prod_{\begin{array}{c}0\le i\le d-1\\C\cap B(i,d)\neq\emptyset\end{array}}\biggm|\frac{m_i}{d}\biggm|^{p_i}>1,
\]
almost all trajectories starting in SC will diverge.
If the weighted product equals \(1\), G. Venturini showed that for type (b) mappings and a wider class of mappings, all trajectories starting in \(S_C\) will be cycles or arithmetic progressions.
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 \[ T(x)=\left\{\begin{array}{ccc} 3x-1 &\mbox{if $x ≡ 0 \pmod{3}$}\\ \frac{x-16}{3} &\mbox{if $x ≡ 1 \pmod{3}$}\\ \frac{-4x-7}{3} &\mbox{if $x ≡ 2 \pmod{3}$}. \end{array} \right. \] 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: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 135 → 404 → -541 → 719 → -961 → 1279 → 421 → 135.
Example. (G. Leigh [3], Example 2, pages 140-141.) Let
\[
T(x)=\left\{\begin{array}{ccc}
\frac{x}{4} &\mbox{if $x ≡ 0 \pmod{8}$}\\
\frac{x+1}{2} &\mbox{if $x ≡ 1 \pmod{8}$}\\
20x-40 &\mbox{if $x ≡ 2 \pmod{8}$}\\
\frac{x-3}{8} &\mbox{if $x ≡ 3 \pmod{8}$}\\
20x+48 &\mbox{if $x ≡ 4 \pmod{8}$}\\
\frac{3x-13}{2} &\mbox{if $x ≡ 5 \pmod{8}$}\\
\frac{11x-2}{4} &\mbox{if $x ≡ 6 \pmod{8}$}\\
\frac{x+1}{8} &\mbox{if $x ≡ 7 \pmod{8}$}.
\end{array}
\right.
\]
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(1, 8), B(2, 8), B(3, 8), B(4, 8), B(5, 8), B(6, 8), B(7, 8), B(0, 32) .
We get a transition matrix QT(8) according to the following scheme:B(0,8)→B(0,2)→B(0,8), B(2,8), B(4,8), B(6,8)
B(1,8)→B(1,4)→B(1,8), B(5,8)
B(2,8)→B(0,32)→B(0,32)
B(3,8)→B(0,1)→B(0,8), B(1,8), B(2,8), B(3,8), B(4,8), B(5,8), B(6,8), B(7,8)
B(4,8)→B(0,32)→B(0,32)
B(5,8)→B(1,4)→B(1,8), B(5,8)
B(6,8)→B(0,2)→B(0,8), B(2,8), B(4,8), B(6,8)
B(7,8)→B(0,1)→B(0,8), B(1,8), B(2,8), B(3,8), B(4,8), B(5,8), B(6,8), B(7,8)
B(0,32)→B(0,8)→B(0,8)
\[ Q_T(8)= \left[ \begin{array}{ccccccccc} \frac{1}{4} & 0 & \frac{1}{4} & 0 & \frac{1}{4} & 0 &\frac{1}{4} & 0 & 0\\ 0 & \frac{1}{2} & 0 & 0 & 0 & \frac{1}{2} & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\ \frac{1}{8} &\frac{1}{8} & \frac{1}{8} & \frac{1}{8} & \frac{1}{8} & \frac{1}{8} & \frac{1}{8} & \frac{1}{8} & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\ 0 & \frac{1}{2} & 0 & 0 & 0 & \frac{1}{2} & 0 & 0 & 0\\ \frac{1}{4} & 0 & \frac{1}{4} & 0 & \frac{1}{4} & 0 &\frac{1}{4} & 0 & 0\\ \frac{1}{8} &\frac{1}{8} & \frac{1}{8} & \frac{1}{8} & \frac{1}{8} & \frac{1}{8} & \frac{1}{8} & \frac{1}{8} & 0\\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{array} \right] \] 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 classes B(3,8) and B(7,8) are transient.
The stationary values are ½, ½ and ⅜, ¼, ⅛, ⅛, ⅛.
For C1, we have p1 = p5 = ½ and as \[ \left(\frac{m_1}{8}\right)^{p_1}\left(\frac{m_5}{8}\right)^{p_5}= \left(\frac{4}{8}\right)^{1/2}\left(\frac{12}{8}\right)^{1/2}<1, \] we expect all trajectories starting in SC1 = B(1, 8) ∪ B(5, 8) = B(1, 4) to cycle.
For C2, we have p0 = ⅜ + ¼ = ⅝ and p2 = p4 = p6 = ⅛. Then as \[ \left(\frac{m_0}{8}\right)^{p_0}\left(\frac{m_2}{8}\right)^{p_2}\left(\frac{m_4}{8}\right)^{p_4}\left(\frac{m_6}{8}\right)^{p_6}= \left(\frac{2}{8}\right)^{5/8}\left(\frac{160}{8}\right)^{1/8}\left(\frac{160}{8}\right)^{1/8}\left(\frac{22}{8}\right)^{1/8}>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. See corrections)
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.
Example 1 (G. Venturini [4], 205-206)
\[
T(x)=\left\{\begin{array}{ccc}
\frac{2500x}{6}+1 &\mbox{if $x ≡ 0 \pmod{6}$}\\
\frac{21x-9}{6} &\mbox{if $x ≡ 1 \pmod{6}$}\\
\frac{x+16}{6} &\mbox{if $x ≡ 2 \pmod{6}$}\\
\frac{21x-51}{6} &\mbox{if $x ≡ 3 \pmod{6}$}\\
\frac{21x-72}{6} &\mbox{if $x ≡ 4 \pmod{6}$}\\
\frac{x+13}{6} &\mbox{if $x ≡ 5 \pmod{6}$}.
\end{array}
\right.
\]
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 |
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.There appear to be just two cycles:
(a) 2,3 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.
Experiment with a BCMATH program.
Example 7. (G. Venturini [4], 210-211)
\[
T(x)=\left\{\begin{array}{ccc}
\frac{x}{3} &\mbox{if $x ≡ 0 \pmod{6}$}\\
\frac{2x-2}{3} &\mbox{if $x ≡ 1 \pmod{6}$}\\
\frac{5x-4}{3} &\mbox{if $x ≡ 2 \pmod{6}$}\\
\frac{4x}{3} &\mbox{if $x ≡ 3 \pmod{6}$}\\
\frac{5x-8}{3} &\mbox{if $x ≡ 4 \pmod{6}$}\\
\frac{4x-2}{3} &\mbox{if $x ≡ 5 \pmod{6}$}.
\end{array}
\right.
\]
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:| 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 |
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.
The stationary vectors of the relevant 3×3 and 6×6 submatrices are (⅓,⅓,⅓) and (⅙,⅙,⅙,⅙,⅙) respectively.
The corresponding weighted product for chain[1] is \[ \left(\frac{2}{6}\right)^{1/3}\left(\frac{10}{6}\right)^{1/3}\left(\frac{10}{6}\right)^{1/3}= \frac{25^{1/3}}{3}<1. \] Hence we expect all trajectories starting in the even integers will 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 8. (G. Venturini [4], p. 211-212)
\[
T(x)=\left\{\begin{array}{ccc}
\frac{x}{3} &\mbox{if $x ≡ 0 \pmod{6}$}\\
\frac{x-1}{3} &\mbox{if $x ≡ 1 \pmod{6}$}\\
\frac{5x+5}{3} &\mbox{if $x ≡ 2 \pmod{6}$}\\
\frac{3x+5}{2} &\mbox{if $x ≡ 3 \pmod{6}$}\\
\frac{3x+2}{2} &\mbox{if $x ≡ 4 \pmod{6}$}\\
\frac{3x+1}{2} &\mbox{if $x ≡ 5 \pmod{6}$}.
\end{array}
\right.
\]
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).
Interested viewers can experiment with a BCMATH program.
Example (G. Venturini [4] 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)=\left\{\begin{array}{ccc} 4q+r &\mbox{if \(<p\),}\\ p^2q+r &\mbox{if \(r≥p\)}. \end{array} \right. $$ 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.
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.
where \(\mathcal{S}_{\mathcal{C}_2}=B(5,12)\cup B(45,108)\cup B(33,36)\subseteq\mathcal{S}_{\mathcal{C}_1}=B(5,6)\cup B(45,54)\cup B(15,18)\) and corresponding limiting probabilities \((\frac{1}{3}, \frac{1}{3}, \frac{1}{3})\).
We also have transient states:
B(0,6),B(1,6),B(2,6),B(3,6),B(4,6),B(10,12),B(1,12),B(9,12).
For both \(\mathcal{C}_1\) and \(\mathcal{C}_2\), we have \(p_3=\frac{1}{3}+\frac{1}{3}=\frac{2}{3},\quad p_5=\frac{1}{3}\).
Also \((\frac{7}{3})^{2/3}9^{1/3}>1\). Hence we expect most trajectories starting in \(\mathcal{S}_{\mathcal{C}_2}\) and \(\mathcal{S}_{\mathcal{C}_1}\) to diverge.
The trajectories \(\{T^k(-1)\}\) and \(\{T^k(5)\}\) apparently diverge.
Experimentally, \(\{T^k(-1)\}\) meets each of B(11,12), B(99,108), B(15,36) with limiting
frequencies 1/3 and does not meet \(\mathcal{S}_{\mathcal{C}_2}\).
\(\{T^k(5)\}\) meets each of B(5,12), B(45,108), B(33,36) with limiting frequencies 1/3.
There appears to be one cycle \(-2\to-2\).
Example 5. (G. Venturini [4], 209-210)
\[
T(x)=\left\{\begin{array}{ccc}
\frac{x}{6} &\mbox{if $x ≡ 0 \pmod{6}$}\\
\frac{2x+16}{3} &\mbox{if $x ≡ 1 \pmod{6}$}\\
3x+11 &\mbox{if $x ≡ 2 \pmod{6}$}\\
\frac{x-3}{6} &\mbox{if $x ≡ 3 \pmod{6}$}\\
x-4 &\mbox{if $x ≡ 4 \pmod{6}$}\\
\frac{x+9}{2} &\mbox{if $x ≡ 5 \pmod{6}$}.
\end{array}
\right.
\]
Here
m0 = 1,
m1 = 4,
m2 = 18,
m3 = 1,
m4 = 6,
m5 = 3;
X0 = 0,
X1 = 6,
X2 = 11,
X3 = 0,
X4 = -4,
X5 = 5.
d0 = 1,
d1 = 4,
d2 = 18,
d3 = 1,
d4 = 6,
d5 = 3.
(Contrary to Venturini's statement on line 2, p.210, I cannot find a \(\nu\) such that \(T\in G_\nu(6)\).)
We find 14 states according to the following scheme:
States: 1:B(0,6), 2:B(1,6), 3:B(2,6), 4:B(3,6), 5:B(4,6), 6:B(5,6),
7:B(2,12), 8:B(6,12), 9:B(10,12), 10:B(17,18), 11:B(17,36),
12:B(4,18), 13:B(13,18), 14:B(0,18)
States 7:B(2,12), 11:B(17,36), 13:B(13,18) constitute ergodic chain[1],
and states 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 14 are transient states.
The submatrix of Q(6) corresponding to states 7, 11, 13 is \(\displaystyle \left[\begin{array}{ccc} 0 & 1 & 0\\ 0 & 0 & 1\\ 1 & 0 & 0, \end{array}\right] \) with stationary vector \((1/3, 1/3, 1/3)\).
Note that \[ T^3(x)=\left\{ \begin{array}{ll} x+36 &\mbox{ if } x\equiv17\pmod{36}\\ x+18 &\mbox{ if } x\equiv13\pmod{18}\\ x+12& \mbox{ if } x\equiv2\pmod{12}. \end{array} \right. \] Hence we get trajectories that contain translations going to infinity.
There appear to be two cycles: \(0\to 0\) and \(1\to 6\to 1\).
Trajectories seem certain to either enter the ergodic set and become a translation, or eventually reach one of the two cycles.
This example is one where in terms of ergodic set [1] we have:
\[ \biggm(\frac{m_2}{d}\biggm)^{p_2}\biggm(\frac{m_5}{d}\biggm)^{p_5}\biggm(\frac{m_1}{d}\biggm)^{p_1}=\left(\frac{18}{6}\right)^{1/3}\left(\frac{3}{6}\right)^{1/3}\left(\frac{4}{6}\right)^{1/3}=1. \] Interested viewers can experiment with a BCMATH program.
Note that Venturini had something to say about this phenomenon in his Theorem 3, p.190.
Example 4 (G. Venturini, p. 208 with t = 11) (infinitely many cycles)
$$
T(x)=\left\{\begin{array}{ccc}
9x+1 &\mbox{if $x ≡ 0 \pmod{9}$}\\
\frac{x+32}{3} &\mbox{if $x ≡ 1 \pmod{9}$}\\
\frac{x-2}{3} &\mbox{if $x ≡ 2 \pmod{9}$}\\
x+3 &\mbox{if $x ≡ 3 \pmod{9}$}\\
\frac{100x-364}{9} &\mbox{if $x ≡ 4 \pmod{9}$}\\
\frac{x-5}{3} &\mbox{if $x ≡ 5 \pmod{9}$}\\
x-6 &\mbox{if $x ≡ 6 \pmod{9}$}\\
\frac{100x-637}{9} &\mbox{if $x ≡ 7 \pmod{9}$}\\
\frac{x-8}{3} &\mbox{if $x ≡ 8 \pmod{9}$}.
\end{array}
\right.
$$
Here m[0]=81, m[1]=3, m[2]=3, m[3]=9, m[4]=100, m[5]=3, m[6]=9, m[7]=100, m[8]=3;
Here X[0]=1, X[1]=11, X[2]=0, X[3]=3, X[4]=-40, X[5]=-1, X[6]=-6, X[7]=-70, X[8]=-2.
Here d[0]=81, d[1]=3, d[2]=3, d[3]=9, d[4]=1, d[5]=3, d[6]=9, d[7]=1, d[8]=3.
States: 1:B(0,9), 2:B(1,9), 3:B(2,9), 4:B(3,9), 5:B(4,9), 6:B(5,9), 7:B(6,9), 8:B(7,9), 9:B(8,9), 10:B(1,81), 11:B(11,27)
B(0,9), B(1,81), B(11,27), B(3,9), B(6,9) constitute ergodic chain[1];
B(1,9), B(2,9), B(4,9), B(5,9), B(7,9), B(8,9) are transient states.
The submatrix of Q(9) corresponding to the ergodic chain is \[ A=\left[ \begin{array}{ccccc} 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 1\\ 1 & 0 & 0 & 0 & 0 \end{array} \right]. \] The submatrix is periodic of order 5, and has stationary vector \(\frac{1}{5}(1,1,1,1,1)\).
Also the weighted product is $$ \left(\frac{81}{9}\right)^{1/5} \left(\frac{3}{9}\right)^{1/5} \left(\frac{3}{9}\right)^{1/5} \left(\frac{9}{9}\right)^{1/5} \left(\frac{9}{9}\right)^{1/5}=1. $$ Note that Venturini had something to say about this phenomenon in his Theorem 3, p.190.
There are cycles 4 → 4 and 7 → 7. Also as asserted by Venturini, T5(x) = x for all x in the ergodic chain, so we have infinitely many cycles 9t → 81t+1 → 27t+11 → 9t+3 → 9t+6 → 9t.
I conjecture that all trajectories will eventually enter one of these cycles.
Interested viewers can experiment with a BCMATH program.
Another 6-branched example (infinitely many cycles)
\[
T(x)=\left\{\begin{array}{ccc}
\frac{x}{6} &\mbox{if $x ≡ 0 \pmod{6}$}\\
\frac{7x-1}{2} &\mbox{if $x ≡ 1 \pmod{6}$}\\
\frac{x}{2} &\mbox{if $x ≡ 2 \pmod{6}$}\\
\frac{2x}{3}&\mbox{if $x ≡ 3 \pmod{6}$}\\
2x &\mbox{if $x ≡ 4 \pmod{6}$}\\
\frac{9x-1}{2} &\mbox{if $x ≡ 5 \pmod{6}$}.
\end{array}
\right.
\]
Here
m0 = 1,
m1 = 21,
m2 = 3,
m3 = 4,
m4 = 12,
m5 = 27;
X0 = 0,
X1 = 0,
X2 = 0,
X3 = 0,
X4 = 0,
X5 = 0.
There are 19 states, with three ergodic classes: \(\mathcal{C}_1=\){B(4,6), B(8,12)}, \(\mathcal{C}_2=\){B(22,54), B(44,108)}, \(\mathcal{C}_3=\){B(10,12), B(20,24)},
and transient classes B(0,6), B(1,6), B(2,6), B(3,6), B(5,6), B(2,12), B(6,12), B(49,54), B(9,54), b(36,54), B(6,36), B(6,18), B(15,18).
There are cycles \[ \begin{array}{c} 0\to0\\ 1\to3\to2\to1\\ 11\to49\to171\to114\to19\to66\to11\\ 6k+4\to12k+8\to6k+4, k\in\mathbb{Z}. \end{array} \] The weighted product for \(\mathcal{C}_1\) is \((\frac{1}{2})^{1/2}(\frac{2}{1})^{1/2}=1\). Note that Venturini had something to say about this phenomenon in his Theorem 3, p.190.
I conjecture that every trajectory will eventually enter one of the above cycles.
Interested viewers can experiment with a BCMATH program.
An example of Chris Smyth. 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 one of the 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.
Last modified 29th June 2023