Powered by MathJax

Two theorems of G. Venturini

In this note, we discuss two innovations of G. Venturini, from his paper Iterates of number-theoretic functions with periodic rational coefficients (generalization of the 3x+1 problem), Stud. Appl. Math. 86 (1992), no.3, 185-218.
The first is his Theorem 7, p. 196, which gives a sufficient condition for the Markov chains of George Leigh to be finite, while his Theorem 3 fills a gap in Conjecture 1 in the Matthews-Watts paper A Markov approach to the generalized Syracuse algorithm, ibid. 45 (1985) 29-42.

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)
defined two sequences of congruence classes \(Y_n(x)\) and \(X_n(x), x\in\mathbb{Z}\), as follows:

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).\)

Then the type (b) mapping condition \(\gcd(m_i,d^2)=\gcd(m_i,d)\) for \(0\le i\le d-1\) is equivalent to \(d_i\mid d\) for \(0\le i\le d-1\).

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.

We now discuss Venturini's Theorem 3, p. 190, where \(T\) is a mapping of type (b) i.e. \(d_j\) divides \(d\) for \(0\le j \le d-1\).
Also if \(S\) is an ergodic set (mod \(d)\), let \[ a(T|S)=\prod_{B(i,d)\subseteq S}\left(\frac{m_i}{d}\right)^{p_i}, \] where \(p_i=\mu_S(i,d)\).

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