Let \(d\ge2\) and \(m_0,\ldots,m_{d-1}\) be positive integers. Also \(r_0,\ldots,r_{d-1}\) are integers satisfying \(r\equiv im_i\pmod{d}\).
Then \(T: \mathbb{Z}\to\mathbb{Z}\) is defined by \(T(x)= \frac{m_ix-r_i}{d}\mbox{ if }x\equiv i \pmod{d}.\)
G.M. Leigh (A Markov process underlying the generalized Syracuse algorithm, ibid. 46 (1986) 125-143 )(Corrections)
For positive integers \(x\), integers \(C(x)\) and \(D(x)\ge1\) 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 \(d_i=D(m_i), c_i=C(m_i).\)
Define \(k_0,k_1,\ldots\) by \[ k_0=1 \mbox{ and } k_{n+1}=\frac{k_nd_{j_n}}{\gcd(k_nd_{j_n}, d)}, \] where \(j_n\) is determined by the congruence \(T^n(x)\equiv j_n\pmod{d}, 0\leq j_n \leq d-1\).
Then \[ \begin{eqnarray*} \mbox{(a) }&Y_0(x)&=B(x,m);\\ \mbox{(b) }&Y_{n+1}(x)&=B(T^{n+1}(x),mk_{n+1}), n\ge0, \end{eqnarray*} \] and \[ \begin{eqnarray*} \mbox{(a) }&X_0(x)&=B(0,1);\\ \mbox{(b) }&X_{n+1}(x)&=B(T^{n+1}(x),\frac{mk_nd_{j_n}}{d}), n\ge0, \end{eqnarray*} \] where \(j_n\) is determined by the congruence \(T^n(x)\equiv j_n\pmod{d}, 0\leq j_n \leq d-1\).
One of Venturini's innovations was to define \(D_n(x)=d_{j_0}\cdots d_{j_{n-1}}\) for all integers \(x\).
Let \(R(d^n)=\{0,\ldots,d^n-1\}\). If \(D_n(x)\) divides \(d^n\) for all \(x\in R(d^n)\), we say that \(T\in G_n(d).\) This implies \(D_n(x)\) divides \(d^n\) for all integers \(x\), as \(x\equiv x_0\pmod{d^n}\implies T(x)\equiv T(x_0)\pmod{d^{n-1}},\ldots.\)
Venturini also defined \(D'_n(x)\) for \(n\ge1\) by \(D'_1(x)=1\) and \(D'_{n+1}(x)=\gcd(D_n(x), dD'_n(x)).\)
I was unable to follow Venturini's proof of Lemma 7 and his proof of Theorem 7, but reproduce the parts that I did understand.
Lemma. (My interpretation of Venturini's Lemma 7, p.196-197)
\[
k_nd_{j_n}=\frac{D_{n+1}(x)}{D'_{n+1}(x)}.\quad (1)
\]
Proof. (By induction.) \(n=0\). \(k_0d_{j_0}=d_{j_0}\). Also \(\frac{D_1(x)}{D'_1(x)}=\frac{d_{j_0}}{1}=d_{j_0}\).
Now assume (1) holds. Then
\[
\begin{align*}
k_{n+1}d_{j_{n+1}}&=\frac{k_nd_{j_n}}{\gcd(k_nd_{j_n},d)}d_{j_{n+1}}\\
&=\frac{\frac{D_{n+1}(x)}{D'_{n+1}(x)}}{\gcd(\frac{D_{n+1}(x)}{D'_{n+1}(x)},d)}d_{j_{n+1}}\\
&=\frac{D_{n+1}(x)}{\gcd(D_{n+1}(x),dD'_{n+1}(x))}d_{j_{n+1}}\\
&=\frac{D_{n+2}(x)}{D'_{n+2}(x)}.
\end{align*}
\]
Corollary.
\[
k_{n+1}=\frac{D_{n+1}(x)}{D'_{n+2}(x)}.
\]
Proof.
\[
\begin{align*}
k_{n+1}&=\frac{k_nd_{j_n}}{\gcd(k_nd_{j_n}, d)}\\
&=\frac{D_{n+1}(x)}{D'_{n+1}(x)}\frac{1}{\gcd(\frac{D_{n+1}(x)}{D'_{n+1}(x)},d)}\\
&=\frac{D_{n+1}(x)}{\gcd(D_{n+1}(x), dD'_{n+1}(x))}\\
&=\frac{D_{n+1}(x)}{D'_{n+2}(x)}.
\end{align*}
\]
By repeated use of the formula \(D'_{n+1}(x)=\gcd(D_n(x), dD'_n(x))\), we have
Lemma. \[ D'_{n+1}(x)=\gcd(D_n(x), dD_{n-1}(x),\ldots,d^{n-1}D_1(x), d^n). \] Corollary. If \(D_n(x)\) divides \(d^n\), then \[ D'_{n+1}(x)=D_1(x)D'_n(T(x)). \] Proof. Since \(D_j(x)=D_1(x)D_{j-1}(T(x))\) for \(j\gt1\), if \(D_n(x)\) divides \(d^n\), we have \[ \begin{align*} D'_{n+1}(x)&=\gcd(D_n(x), dD_{n-1}(x),\ldots,d^{n-1}D_1(x))\\ &=D_1(x)\gcd(D_{n-1}(T(x)), dD_{n-2}(T(x)),\ldots,d^{n-1})\\ &=D_1(x)D'_n(T(x)). \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad(2) \end{align*} \] Corollary. If \(D_n(x)\) divides \(d^n\) and \(M_n(x)=\frac{D_n(x)}{D'_n(x)}, N_n(x)=\frac{D_n(x)}{D'_{n+1}(x)}\), then \[ M_{n+1}(x)=M_n(T(x))\mbox { and }N_{n+1}(x)=N_n(T(x)). \] Proof. \[ M_{n+1}(x)=\frac{D_{n+1}(x)}{D'_{n+1}(x)}=\frac{D_1(x)D_n(T(x))}{D_1(x)D'_n(T(x))}=M_n(T(x)). \] Similarly for \(N_{n+1}(x)=N_n(T(x))\).
At this point, Venturini states that the Markov chain \(X_n(x)\) is finite.
Theorem (Venturini's Theorem 3, \(k=1\)) Let \(a(T|S)=1\). Then
(i) \(m_i=d\) for all \(i\) with \(B(i,d)\in S\);
(ii) If \(S=\{B(i_0,d)\cup\ldots\cup B(i_{L-1},d)\}\), then the \(L\times L\) submatrix of \(Q(d)\) corresponding to \(S\) is periodic;
(iii) Finally, with cyclic relabelling of the classes in \(S\), either there will be infinitely many cycles
\[
dt+i_0\to dt+i_1\to\cdots\to dt+i_{L-1}=dt+i_0, t\in\mathbb{N},
\]
or infinitely many arithmetic progressions
\[
dt+i_0\to dt+i_1\to\cdots\to dt+i_{L-1}\to dt+i_0 +\Delta,\to dt+i_1 +\Delta,\ldots t\in\mathbb{N}, \mbox{ where }\Delta\neq 0.
\]
Proof. Assume \(a(T|S)=1\). Then
\[
\begin{align*}
\left(\frac{c_{i_0}d_{i_0}}{d}\right)^{p_0}\cdots\left(\frac{c_{i_{L-1}}d_{i_{L-1}}}{d}\right)^{p_{L-1}}&=1\\
(c_{i_0}^{p_0}\cdots c_{i_{L-1}}^{p_{L-1}})(d_{i_0}^{p_0}\cdots d_{i_{L-1}}^{p_{L-1}})&=d^{p_0+\cdots p_{L-1}}=d.
\end{align*}
\]
Hence \(c_{i_0}^{p_0}\cdots c_{i_{L-1}}^{p_{L-1}}=1\) as \(gcd(c_{i_j},d)=1\). Also \(d_{i_0}^{p_0}\cdots d_{i_{L-1}}^{p_{L-1}}=d.\)
Hence \(c_{i_0}=1,\ldots,c_{i_{L-1}}=1\).
But \(k_0d_{i_0}=d,\ldots,k_{L-1}d_{i_{L-1}}=d,\) for some positive integers \(k_o,\ldots,k_{L-1}\), so
\(d^{p_0}\cdots d^{p_{L-1}}=d=dk_0^{p_0}\cdots k_{L-1}^{p_{L-1}}\) and \(k_0^{p_0}\cdots k_{L-1}^{p_{L-1}}=1\).
Hence \(k_0=1,\ldots,k_{L-1}=1\), \(d_{i_0}=d,\ldots,d_{i_{L-1}}=d\) and \(m_{i_0}=d,\ldots,m_{i_{L-1}}=d.\)
Let \(Q_S(d)\) be the submatrix of \(Q(d)\) that corresponds to the ergodic set \(S\).
Then \(Q_S(d)\) will be irreducible. Moreover, as
\[
q_{ij}=\left\{
\begin{array}{ll}
\frac{\gcd(m_i,d)}{d} & \mbox{ if \(T(i)\equiv j\pmod{\frac{m}{d}\gcd(m_i,d)}\)}\\
0 & \mbox{ otherwise}
\end{array}
\right.
\]
we have
\[
q_{i,j}=\left\{
\begin{array}{ll}
1 & \mbox{ if \(T(i)\equiv j\pmod{d}\)}\\
0 & \mbox{ otherwise}
\end{array}
\right.
\]
Hence \(Q_S(d)\) has entries \(0\) or \(1\), and with relabelling of states \(i_0,\ldots,i_{L-1}\) in \(S\), has the form
\[
\left[
\begin{array}{ccccc}
0 & 1 & 0 & \cdots & 0\\
0 & 0 & 1 & \cdots & 0\\
\vdots & & & &\vdots\\
0 & 0 & 0 & \cdots & 1\\
1 & 0 & 0 & \cdots & 0
\end{array}
\right].
\]
Hence
\[
\begin{align*}
T(i_0)&\equiv i_1\pmod{d}\\
T(i_1)&\equiv i_2\pmod{d}\\
& \vdots\\
T(i_{L-1})&\equiv i_0\pmod{d}
\end{align*}
\]
and with \(T(x)=x+\Delta_i\) if \(x\equiv i\pmod{d}\), we get mappings of congruence classes in \(S\):
\[
\begin{align*}
T(dt+i_0)&=dt+i_0+\Delta_{i_0}\\
T^2(dt+i_0)&=dt+i_0+\Delta_{i_0}+\Delta_{i_1}\\
&\vdots\\
T^L(dt+i_0)&=dt+i_0+\Delta_{i_0}+\Delta_{i_1}+\cdots+\Delta_{i_{L-1}}.
\end{align*}
\]
Hence if \(\Delta_{i_0}+\Delta_{i_1}+\cdots+\Delta_{i_{L-1}}=0\), we get infinitely many cycles of
length \(L\);
otherwise we get infinitely many arithmetic progressions "cycling" through the congruence classes \(B(i_0),\ldots,B(i_{L-1})\).
Example 1.
\[
T(x)=\left\{\begin{array}{ll}
x+1 &\mbox{if $x\equiv 0\pmod{3}$}\\
x+1 &\mbox{if $x\equiv 1\pmod{3}$}\\
x+2 &\mbox{if $x\equiv 2\pmod{3}$}
\end{array}
\right.
\]
Here \(S=B(1,3)\cup B(2,3)\) and we get "cycling" through residue classes \(B(1,3)\) and \(B(2,3)\) in the form of AP's:
\[
3t+1 \to 3t+2 \to 3t+4 \to 3t+5 \to 3t+7 \cdots
\]
Example 2.
\[
T(x)=\left\{\begin{array}{ll}
x+2 &\mbox{if $x\equiv 0\pmod{3}$}\\
x-1 &\mbox{if $x\equiv 1\pmod{3}$}\\
x-1 &\mbox{if $x\equiv 2\pmod{3}$}
\end{array}
\right.
\]
Here there is one ergodic set \(S=B(0,3)\cup B(1,3)\cup B(2,3)\) and we get infinitely many cycles via residue classes \(B(0,3), B(2,3), B(1,3)\):
\[
3t \to 3t+2 \to 3t+1 \to 3t.
\]
Example 3.
\[
T(x)=\left\{\begin{array}{ll}
x+1 &\mbox{if $x\equiv 0\pmod{10}$}\\
x+2 &\mbox{if $x\equiv 1\pmod{10}$}\\
x+4 &\mbox{if $x\equiv 2\pmod{10}$}\\
x+3 &\mbox{if $x\equiv 3\pmod{10}$}\\
x-3 &\mbox{if $x\equiv 4\pmod{10}$}\\
x-7 &\mbox{if $x\equiv 5\pmod{10}$}\\
x-3 &\mbox{if $x\equiv 6\pmod{10}$}\\
x+6 &\mbox{if $x\equiv 7\pmod{10}$}\\
x+7 &\mbox{if $x\equiv 8\pmod{10}$}\\
x+23 &\mbox{if $x\equiv 9\pmod{10}$}
\end{array}
\right.
\]
Here \(B(0,10)\cup B(6,10)\) and \(B(5,10)\cup B(8,10)\) are the ergodic sets,
and we get two infinite sequences of cycles:
\[
\begin{array}{l}
10t+3\to 10t+6\to 10t+3\\
10t-2\to 10t+5\to 10t-2.
\end{array}
\]
We now briefly discuss Venturini's Theorem 3, p. 190, where T is a mapping of type \(G_\nu(d)\) and S is an ergodic set.
Let \(SR(d^k)=\{x'\in R(d^k)|x'\equiv x\pmod{d^k}, x\in S\}\).
Now suppose \(a(T|S)=1\) and \(T|_S\in G_k'(d^k).\) i.e. \(D_k(x')|d^k\) if \(x'\in SR(d^k)\).
The conclusion is that \(T^k|_S\) has the form
\[
T^k|_S(x)=x+\Delta_i \mbox{ if }x\equiv x'\pmod{d^k}, x'\in SR(d^k).
\]
This follows from the fact that \(T^k(x)=D_k(x)+\Delta_i\) if \(x\in R(d^k)\).
Then we are back to the earlier cyclic cases when \(k=1\).
Venturini gives two examples: 4, where \(T^5(x)=x\) for every \(x\in S\) and 5, where for every class \(B(z,M)\subseteq S\) we have \(T^3(Mq+z)=Mq+M+z\).
Also see another example.
Last modified 28th June 2023