### 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.