Automaticity of saturated sets, ancestor sets, stopping times and forward-invariant sets of $3x\pm1$ maps

1. Statement and scope

Fix $e\in\{+1,-1\}$ and let $T(x)=x/2$ for even $x$ and $T(x)=(3x+e)/2$ for odd $x$, on $\mathbb N=\{1,2,\dots\}$. A set $S\subseteq\mathbb N$ is saturated if $x\in S\iff T(x)\in S$ for every $x$. Saturated sets are exactly the unions of weak components of the functional graph of $T$. Examples are the set of $n$ whose orbit reaches $1$, and the basin of any cycle.

Theorem 1. If $S$ is saturated and $2$-automatic, or saturated and $3$-automatic, then $S=\varnothing$ or $S=\mathbb N$.

Corollary 2 ($e=-1$). The $3x-1$ map has the cycles through $1$, $5$ and $17$. Their basins are nonempty, pairwise disjoint and saturated. Hence none of them is $2$-automatic or $3$-automatic. The same holds for every other weak component, and for every union of components other than $\varnothing$ and $\mathbb N$.

Corollary 3 ($e=+1$). The following are equivalent: the Collatz conjecture; the set of $n$ reaching $1$ is $2$-automatic; the same set is $3$-automatic.

Corollary 3 is a reformulation and gives no progress toward the conjecture. Its content is a property of hypothetical counterexamples: the basin of a nontrivial cycle, and the set of starts with divergent orbits, cannot be recognised by a finite automaton reading base-$2$ or base-$3$ digits. Corollary 2 is unconditional.

Section 7 relaxes saturation to hold only above some bound (Theorem 8). This applies to the ancestor set $\mathrm{Anc}(y)$, the set of $n$ whose orbit passes through $y$, and gives an unconditional statement about the $3x+1$ map itself. For both signs and every $X\geq5$, it also shows that the set of $n>X$ whose orbit first enters $[1,X]$ at a given $y$ prime to $3$ is neither $2$-automatic nor $3$-automatic. All these statements hold in every base $2^a3^b$ (Section 7).

Corollary 10 ($e=+1$). If $3\mid y$, then $\mathrm{Anc}(y)=\{2^jy:j\geq0\}$, which is $2$-automatic and not $3$-automatic. If $y\in\{1,2,4,8\}$, then $\mathrm{Anc}(y)$ is $2$-automatic iff it is $3$-automatic iff the Collatz conjecture holds. For every other $y$, $\mathrm{Anc}(y)$ is neither $2$-automatic nor $3$-automatic.

Theorem 11 extends Theorem 8 to functions that change by a fixed rule along orbits. By Corollary 12, the number of steps needed to reach $1$, reduced modulo any $m\geq2$, is neither $2$-automatic nor $3$-automatic. This is unconditional, with a separate symbol for orbits that never reach $1$. If the Collatz conjecture holds, it follows that the stopping-time sequence (OEIS A006577) is not $2$-regular.

Section 8 extends Theorem 1 to $(\ell x\pm1)/2$ for odd primes $\ell$ such that $2$ is a primitive root modulo $\ell^2$. This includes $5x\pm1$. It also shows that the covering lemma fails whenever $2$ is not a primitive root modulo $\ell$, so $7x\pm1$ is not covered. An example with $3x+5$ shows that the hypothesis $e=\pm1$ cannot be dropped.

Section 10 treats forward-invariant sets. A nonempty regular set $S$ with $T(S)\subseteq S$ and no periodic point would certify a divergent orbit. Proposition 14 shows that such a set must contain every leading word in bases $2$ and $3$, so that, if it is automatic, it has positive lower density. With a theorem of Garcia and Tal that every orbit has Banach density $0$, Corollary 15 deduces that, for either sign, no orbit that is not eventually periodic is an automatic set in any base $2^a3^b$. The main result of the section is Corollary 21: for either sign, every nonempty $2$-automatic set $S$ with $T(S)\subseteq S$ contains a periodic point, and every $2$-automatic set of positive upper density meets the basin of $1$. So no automaton reading binary digits can certify a divergent orbit. The proof builds integers in the basin of $1$ that differ in single digits and have the same orbit from some point on. It rests on Lemma 17, whose existence part is due to Said Duran [22]: for every $d\neq0$ there is a residue class of integers $u$ such that $u$ and $u+d$ coalesce after the same number of steps, with the same number of odd steps. Theorem 18 and Proposition 19 apply it to permutation automata and to sums over windows of adjacent digits in finite abelian groups, such as the parity of the number of occurrences of $11$. These contain the consequence of a theorem of Monks [19] that every residue class meets the basin of $1$. Theorem 20 treats an arbitrary automaton through its action on its smallest images, and controls the leading digits as well as the low ones. Corollary 16 shows that an automatic forward-invariant set that avoids a residue class modulo $2^k$ contains a periodic point; if the set is $3$-automatic, it is finite. This applies to the four residue-avoidance conjectures of Yolcu, Aaronson and Heule [18], and to their map $H$, for which every $2$- or $3$-automatic forward-invariant set is a finite union of cycles.

2. Related work

The affine identity $T^k(p+2^ks)=T^k(p)+3^os$ is classical [6]. Shallit and Wilson [8] proved that the set of $n$ reaching $1$ with exactly $i$ odd iterates $\geq3$ is $2$-automatic for every $i$. Colussi [11] and Stérin [12] gave explicit regular expressions for these sets, and Stérin did so for the ancestors of any $x$ with a bounded number of odd steps. Theorem 1 shows that the union over $i$ is not automatic unless it is all of $\mathbb N$. For $3x+1$, Corollary 10 shows unconditionally that the union over all budgets, $\mathrm{Anc}(x)$, is not automatic for every $x$ prime to $3$ other than $1$, $2$, $4$ and $8$. Corollary 12 shows that the index $i$ itself, reduced modulo any $m\geq2$ and with a separate symbol for orbits that never reach $1$, is not $2$-automatic. Klarner [5] proved that the smallest set containing a finite seed and closed under finitely many maps $x\mapsto m^ax+b$ is $m$-recognisable. Urvoy [9] proved that the Collatz graph is not a regular graph in Courcelle's sense; that is a statement about the graph, not about the partition of its vertex set. Stérin and Woods [13] showed that in the base-$2$ space-time diagram of $T$ the columns iterate the map in base $3$. That is also a two-base phenomenon, but it concerns single orbits rather than residual sets. Dhiman and Pandey [3, 4] used Cobham–Semënov to show that the arbitrary-step transition relation and the reachability relation of generalised Collatz maps are not definable in Büchi arithmetic. The one-step relation $y=T(x)$ is definable in Presburger arithmetic. Those are two-dimensional relations. Their results do not imply Theorem 1, because a component can be automatic while the reachability relation is not: under the Collatz conjecture the component of $1$ is $\mathbb N$. In the other direction, the definable sets of $\langle\mathbb N,+,V_k\rangle$ are the $k$-automatic sets, and sections of a definable relation are definable. So Corollary 10 implies that the $3x+1$ reachability relation is definable neither in base $2$ nor in base $3$. This overlaps with [3, 4] for this map. On rStation, collatz_16 [10] studies automatic and morphic parity sequences of rational orbits, which is a different object.

The step "a nontrivial saturated set is not ultimately periodic" (Section 5) may be folklore. I did not find a source, including in Lagarias's two annotated bibliographies [7], and I give a complete proof. The new ingredient is the residual transfer of Section 4. It turns base-$2$ regularity into base-$3$ regularity, so that Cobham's theorem [2] applies.

We use the $k$-kernel characterisation [1, Ch. 6]. A set $S$ is $k$-automatic iff the family of residual sets $\{s\geq0:\,r+k^js\in S\}$, $j\geq0$, $0\leq r<k^j$, is finite. Here $0\notin S$ by convention.

3. Two lemmas on prefixes

We extend $T$ by $T(0)=0$. The parities of $x,T(x),\dots,T^{k-1}(x)$ depend only on $x\bmod 2^k$ [6]. For $0\leq p<2^k$, let $o=o(p,k)$ be the number of odd ones among those of $p$. Then

$$T^k(p+2^ks)=T^k(p)+3^os\qquad(s\geq0).\tag{1}$$

Lemma 4 (size). If $0\leq p<2^k$, then $T^k(p)<3^{o}$.

Proof. Let $o_j$ count the odd steps among the first $j$. We show $T^j(p)<2^{k-j}3^{o_j}$ by induction on $j$; the case $j=0$ is the hypothesis. An even step halves both sides. At an odd step the integer $y=T^j(p)$ satisfies $y\leq2^{k-j}3^{o_j}-1$, so $(3y+e)/2\leq(2^{k-j}3^{o_j+1}-2)/2<2^{k-j-1}3^{o_j+1}$. $\square$

Lemma 5 (covering). For every $o\geq1$ and every $q\in[1,3^o)$ with $3\nmid q$, there are $k$ and $0\leq p<2^k$ with $o(p,k)=o$ and $T^k(p)=q$.

Proof. We build a backward chain $y_0=q,y_1,\dots,y_o$ of integers prime to $3$, with $y_1,\dots,y_o$ odd, where $y_{i+1}$ reaches $y_i$ by one odd step followed by even steps. Given $y_i$ with $3\nmid y_i$, pick $j_0\in\{0,1\}$ with $2^{j_0+1}y_i\equiv e\pmod 3$. For $j=j_0+2t$ put $z=2^jy_i$ and $x=(2z-e)/3$, an odd positive integer with $T(x)=z$ and $T^j(z)=y_i$. As $t$ runs over $0,1,2$, $z$ is multiplied by powers of $4$, which has order $3$ modulo $9$. So $2z-e$ runs over the three classes modulo $9$ that are $0$ modulo $3$, and $x\bmod 3$ takes every value. Choose $t$ with $3\nmid x$ and set $y_{i+1}=x$. The forward orbit of $y_o$ reaches $q$ in some $k$ steps with exactly $o$ odd steps. Put $p=y_o\bmod 2^k$. By (1), $p$ has the same parity vector and $T^k(p)\equiv q\pmod{3^o}$. By Lemma 4, $T^k(p)<3^o$, so $T^k(p)=q$. $\square$

4. Residual transfer

For a saturated $S$, write $R_2(p,k)=\{s:\,p+2^ks\in S\}$ and $R_3(q,L)=\{s:\,q+3^Ls\in S\}$. Saturation applied $k$ times, together with (1), gives

$$R_2(p,k)=R_3\bigl(T^k(p),\,o(p,k)\bigr).\tag{2}$$

By Lemma 4, $T^k(p)$ is a legitimate base-$3$ prefix of length $o(p,k)$.

Proposition 6. Let $S$ be saturated and put $S'=S\setminus3\mathbb N$. (a) If $S$ is $3$-automatic, then $S$ is $2$-automatic. (b) If $S$ is $2$-automatic, then $S'$ is both $2$-automatic and $3$-automatic.

Proof. (a) By (2), every base-$2$ residual of $S$ is a base-$3$ residual of $S$. (b) $S'$ is the intersection of $S$ with a periodic set, so it is $2$-automatic. Consider a base-$3$ residual of $S'$ at a prefix $q<3^L$ with $L\geq1$. If $3\mid q$, it is empty. If $3\nmid q$, then every $q+3^Ls$ is prime to $3$. So the residual equals $R_3(q,L)$, which by Lemma 5 and (2) equals some $R_2(p,k)$. Together with $S'$ itself at $L=0$, this leaves finitely many residuals. $\square$

By Cobham's theorem [2], a set that is $2$-automatic and $3$-automatic is ultimately periodic. So if $S$ is $2$-automatic, there are $m$ with $6\mid m$ and $n_0$ such that membership in $S'$ is $m$-periodic above $n_0$.

5. The class graph is connected

For $m$ with $6\mid m$, let $G_m$ have vertices $r\bmod m$ with $3\nmid r$. For each class $x\bmod 2m$ with $3\nmid x$, $G_m$ has an undirected edge between $x\bmod m$ and $T(x)\bmod m$. This is well defined: $T(x)\bmod m$ depends only on $x\bmod 2m$. If $3\mid T(x)$ then $x$ is even, since an odd step gives $T(x)\equiv e/2\not\equiv0\pmod3$, and then $x=2T(x)$. So $3\nmid x$ implies $3\nmid T(x)$.

Proposition 7. $G_m$ is connected for every $m$ with $6\mid m$.

Proof. Write $m=2^a3^bm'$ with $a,b\geq1$ and $\gcd(m',6)=1$, and put $M=3^bm'$.

(i) The $2$-part collapses. The vertex $2v$ has the two even lifts $2v$ and $2v+m$ modulo $2m$. Their images are $v$ and $v+m/2$. So $v\sim2v\sim v+m/2$. Suppose $v\sim v+m/2^{j-1}$ for all $v$, with $j\leq a$. Then $v+m/2^{j}\sim2v+m/2^{j-1}\sim2v\sim v$. Hence $v\sim v+M$, and components are unions of fibres of $\mathbb Z/m\to\mathbb Z/M$. Every class modulo $M$ has odd and even lifts. So the quotient graph $G'_M$ on $\{v\bmod M: 3\nmid v\}$ has the edges $v\sim2v$ and $v\sim(3v+e)\cdot2^{-1}$, where $2^{-1}$ is the inverse modulo $M$.

(ii) The $3$-part collapses. If $b\geq1$ and $v\equiv v'\pmod{M/3}$, then $3v\equiv3v'\pmod M$. So $v$ and $v'$ have the same image $(3v+e)2^{-1}$ and are joined. Components of $G'_M$ are therefore unions of fibres over $\mathbb Z/(M/3)$, and the quotient carries the same two edge rules. Repeating this $b$ times reduces to $\mathbb Z/m'$ with all residues as vertices.

(iii) The prime-to-$6$ part. On $\mathbb Z/m'$ the maps $\alpha(v)=2v$ and $\beta(v)=(3v+e)2^{-1}$ are bijections. In a finite set, the components of the graph with the edges $v\sim\alpha v$ and $v\sim\beta v$ are the orbits of the group $\langle\alpha,\beta\rangle$. For affine maps $f(v)=av+b$ and $g(v)=cv+d$, the commutator $fgf^{-1}g^{-1}$ is translation by $(a-1)d-(c-1)b$. With $\alpha$ and $\beta$ this is translation by $e/2$, a unit modulo $m'$ since $e=\pm1$. So the group is transitive. If $m'=1$ there is nothing to prove. $\square$

6. Proof of Theorem 1

By Proposition 6(a) we may assume that $S$ is $2$-automatic. Take $m$ and $n_0$ as at the end of Section 4. For $r\bmod m$ with $3\nmid r$, let $\lambda(r)$ be the common value of $[x\in S]$ over $x\equiv r\pmod m$ with $x\geq n_0$. Each edge of $G_m$ is realised by arbitrarily large $x$, with $T(x)\geq x/2$, and saturation gives $[x\in S]=[T(x)\in S]$. So $\lambda$ is constant on edges, and by Proposition 7 it is constant.

Suppose $\lambda\equiv0$ and $n\in S$. Write $n=2^in''$ with $n''$ odd. Then $n''=T^i(n)\in S$, and if $3\mid n''$ we replace $n''$ by $T(n'')\in S$, which is prime to $3$. In either case we have an element $u\in S$ with $3\nmid u$. All $2^ju$ lie in $S$, because $T(2x)=x$. They are prime to $3$ and arbitrarily large, which contradicts $\lambda\equiv0$. So $S=\varnothing$. If $\lambda\equiv1$, then $\mathbb N\setminus S$ is saturated and $2$-automatic with constant $0$, so it is empty. $\square$

Corollary 2 follows because the three cycles of $3x-1$ through $1$, $5$ and $17$ lie in distinct components. Corollary 3 follows because the set of $n$ reaching $1$ is saturated and contains $1$.

7. Eventually saturated sets and ancestor sets

Call $S$ eventually saturated if there is $X\geq0$ such that $x\in S\iff T(x)\in S$ for every $x>X$. For $y\in\mathbb N$ let $\mathrm{Anc}(y)$ be the set of $n$ whose orbit contains $y$. If $y$ is not periodic, an orbit meets $y$ at most once, so $x\in\mathrm{Anc}(y)\iff T(x)\in\mathrm{Anc}(y)$ for every $x\neq y$. Then $\mathrm{Anc}(y)$ is eventually saturated with $X=y$. If $y$ is periodic, $\mathrm{Anc}(y)$ is the basin of its cycle, which is saturated.

Theorem 8. If $S$ is eventually saturated and $2$-automatic or $3$-automatic, then $S$ or $\mathbb N\setminus S$ contains only finitely many integers prime to $3$.

Proof. Only (2) changes. Let $0\leq p<2^k$, $q=T^k(p)$ and $o=o(p,k)$, and let $o_j$ count the odd steps among the first $j$. For $j<k$, identity (1) for $j$ steps gives $T^j(p+2^ks)=T^j(p)+2^{k-j}3^{o_j}s\geq2s$. So for $s>X/2$ the points $p+2^ks,\dots,T^{k-1}(p+2^ks)$ all exceed $X$, and $p+2^ks\in S\iff q+3^os\in S$. Hence $R_2(p,k)$ and $R_3(q,o)$ agree outside the window $[0,X/2]$. Given finitely many sets, only finitely many sets agree with one of them outside a fixed finite window. So both parts of Proposition 6 still hold, with the same proof, and Cobham's theorem applies to $S\setminus3\mathbb N$. In Section 6 the edges of $G_m$ are realised by $x>\max(X,2n_0)$, where the equivalence holds, so $\lambda$ is constant. If $\lambda\equiv0$, then $S$ has no element prime to $3$ above $n_0$. If $\lambda\equiv1$, the same holds for $\mathbb N\setminus S$. $\square$

For $X=0$, Theorem 8 gives Theorem 1, because Section 6 shows that a nonempty saturated set contains infinitely many integers prime to $3$.

Other bases. Theorems 1 and 8 hold in every base $k=2^a3^b$. Bases $2^a$ and $3^b$ are equivalent to bases $2$ and $3$ [1, Sec. 6.6], so let $a,b\geq1$. Applying the equivalence at $2x,4x,\dots$ gives $x\in S\iff2^ix\in S$ whenever $2x>X$. Hence, for $0\leq q<3^{bL}$ and $s>X/2$, $$q+3^{bL}s\in S\iff2^{aL}q+k^Ls\in S,$$ and $2^{aL}q<k^L$. So every base-$3^b$ residual of $S$ agrees outside the window $[0,X/2]$ with a base-$k$ residual. If $S$ is $k$-automatic, it is therefore $3^b$-automatic, hence $3$-automatic. The same embedding with $\ell$ in place of $3$ applies to Theorem 13. Corollaries 9 and 10 and the first-entry statement below extend to these bases. In Corollary 10, the set $\{2^jy\}$ is not ultimately periodic, so by Cobham's theorem it is $k$-automatic only when $k$ is a power of $2$. Bases with another prime factor, such as $5$ or $10$, are not reached by this argument. Closure under doubling alone cannot reach them. The set $\{x:\ v_5(x)\text{ even}\}$ satisfies $x\in S\iff2x\in S$ and is $5$-automatic, since its membership is read from the number of trailing zeros in base $5$. It is not ultimately periodic. If $P=5^au$ with $5\nmid u$ were a period, then any large $x$ with $v_5(x)=a+1$ would give $v_5(x+P)=a$, of the other parity. So an argument in base $5$ would have to use the odd branch as well.

Corollary 9. Let $y$ be non-periodic with $3\nmid y$. Suppose some $w>y$ with $3\nmid w$ has an orbit that avoids $y$. Then $\mathrm{Anc}(y)$ is neither $2$-automatic nor $3$-automatic.

Proof. $\mathrm{Anc}(y)$ contains every $2^jy$, and these are prime to $3$. Its complement contains every $2^jw$, because the orbit of $2^jw$ consists of $2^jw,\dots,2w$, all larger than $y$, followed by the orbit of $w$. Apply Theorem 8. $\square$

The same argument applies to first entry points. Fix $X\geq5$, and for $n>X$ let $E(n)$ be the first element of the orbit of $n$ that is at most $X$, if there is one. An odd step from $x>X$ gives $(3x+e)/2>X$, so the orbit enters $[1,X]$ by a halving, and every value of $E$ lies in $(X/2,X]$. Take $y\in(X/2,X]$ with $3\nmid y$. The set $E^{-1}(y)\cup\{y\}$ is eventually saturated with threshold $X$, and it contains every $2^jy$ with $j\geq1$. Its complement contains every $2^jy'$ with $j\geq1$, for another $y'\in(X/2,X]$ prime to $3$, which exists because $X\geq5$. So by Theorem 8, $E^{-1}(y)\cup\{y\}$ is neither $2$-automatic nor $3$-automatic. Neither is $E^{-1}(y)$, which differs from it by one element. This holds unconditionally and for both signs. If $3\mid y$, then $E^{-1}(y)=\{2^jy:j\geq1\}$, by the next paragraph.

If $3\mid y$, then $y$ has no odd preimage, since an odd step gives a value $\equiv e/2\pmod 3$. So $\mathrm{Anc}(y)=\{2^jy:j\geq0\}$. This set is $2$-automatic. It is not ultimately periodic, so by Cobham's theorem it is not $3$-automatic.

Proof of Corollary 10. Let $e=+1$; the case $3\mid y$ was just treated. Suppose $3\nmid y$ and $y\notin\{1,2,4,8\}$. If $y$ is periodic, it lies on a cycle other than $\{1,2\}$. Then $\mathrm{Anc}(y)$ is the basin of that cycle, which is saturated, nonempty and misses $1$, and Theorem 1 applies. If $y$ is not periodic, put $w=2^N$ when $y$ is not a power of $2$, and $w=5\cdot2^N$ when $y=2^i$ with $i\geq4$, with $N$ large in both cases. The orbit of $2^N$ is $2^N,\dots,2,1$, and the orbit of $5\cdot2^N$ ends with $5,8,4,2,1$. Neither contains $y$, so Corollary 9 applies.

For $y\in\{1,2\}$, $\mathrm{Anc}(y)$ is the basin of $1$, and Corollary 3 applies. For $y\in\{4,8\}$, note that $8$ is the only preimage of $4$, the preimages of $2$ are $4$ and $1$, and $2$ is the only preimage of $1$. So every orbit that reaches $1$ and does not start in $\{1,2,4\}$ passes through $8$, $4$ and $2$. The complement of $\mathrm{Anc}(y)$ is therefore a subset of $\{1,2,4\}$ together with the set $D$ of $n$ whose orbits never reach $1$. If the Collatz conjecture holds, $\mathrm{Anc}(y)$ is cofinite and hence automatic in every base. Conversely, suppose $\mathrm{Anc}(y)$ is $2$-automatic or $3$-automatic. It contains every $2^jy$, so by Theorem 8 its complement has only finitely many elements prime to $3$. The set $D$ is saturated, and if it is nonempty it contains infinitely many integers prime to $3$ (Section 6). So $D=\varnothing$. $\square$

Stopping times. The same proof applies to functions that change by a fixed rule along orbits, such as step counts.

Theorem 11. Let $A$ be a finite set, let $\varphi_0,\varphi_1$ be permutations of $A$, and let $X\geq0$. Suppose $f:\mathbb N\to A$ satisfies $f(x)=\varphi_{x\bmod2}\bigl(f(T(x))\bigr)$ for every $x>X$, and that $f$ is $2$-automatic or $3$-automatic. Then there are $m'\geq1$ prime to $6$ and $\lambda:\mathbb Z/m'\to A$ with $f(x)=\lambda(x\bmod m')$ for all sufficiently large $x$ prime to $3$. If $\varphi_0$ and $\varphi_1$ commute, then $\lambda$ is constant, and its value $c$ satisfies $\varphi_0(c)=\varphi_1(c)=c$.

Proof. For $0\leq p<2^k$ let $q=T^k(p)$ and $o=o(p,k)$, let $b_j$ be the parity of $T^j(p)$, and put $\Phi(p,k)=\varphi_{b_0}\circ\varphi_{b_1}\circ\dots\circ\varphi_{b_{k-1}}$, the composition along the parity vector of $p$. No commutation is needed here. For $s>X/2$ the proof of Theorem 8 gives $f(p+2^ks)=\Phi(p,k)\bigl(f(q+3^os)\bigr)$. The $\Phi(p,k)$ lie in the finite group generated by $\varphi_0$ and $\varphi_1$. So, outside a finite window, each base-$2$ kernel sequence of $f$ [1, Ch. 6] is the image of a base-$3$ kernel sequence under one of finitely many permutations, and by Lemma 5 the converse holds at prefixes prime to $3$. Proposition 6 therefore holds for $f$, after replacing its values on multiples of $3$ by a new symbol. A sequence over a finite alphabet is $k$-automatic iff each of its fibres is, so Cobham's theorem [2] applied to each fibre makes the modified sequence ultimately periodic, with a period $m$ divisible by $6$. For $r\bmod m$ with $3\nmid r$, let $\lambda(r)$ be its eventual value on the class $r$. Each edge of $G_m$ now gives $\lambda(x\bmod m)=\varphi_{x\bmod2}\bigl(\lambda(T(x)\bmod m)\bigr)$. Rerun Proposition 7 with these labels. In (i), the two lifts of $2v$ give $\varphi_0(\lambda(v))=\varphi_0(\lambda(v+m/2))$, so $\lambda(v)=\lambda(v+m/2)$, and the induction is unchanged. In (ii), $v$ and $v'$ have the same odd image, so $\lambda(v)=\lambda(v')$. So $\lambda$ factors through $\mathbb Z/m'$, which proves the first claim. Now suppose the maps commute. In (iii), $\lambda(\alpha v)=\varphi_0(\lambda(v))$ and $\lambda(\beta v)=\varphi_1^{-1}(\lambda(v))$. Since $\varphi_0$ and $\varphi_1$ commute, the commutator of $\alpha$ and $\beta$, which is translation by $e/2$, preserves $\lambda$. Hence $\lambda$ is a constant $c$, and the two relations give $\varphi_0(c)=c=\varphi_1(c)$. $\square$

With $A=\{0,1\}$ and $\varphi_0=\varphi_1=\mathrm{id}$, Theorem 11 is Theorem 8. The first claim is sharp. For $m'>1$ prime to $6$, the periodic sequence $f(x)=x\bmod m'$ satisfies the hypothesis with $\varphi_0(v)=2v$ and $\varphi_1(v)=(2v-e)/3$, which do not commute. Conversely, $f(x)=\lambda(x\bmod m')$ satisfies the hypothesis exactly when $\lambda(2v)=\varphi_0(\lambda(v))$ and $\lambda(v)=\varphi_1(\lambda((3v+e)/2))$ on $\mathbb Z/m'$.

Corollary 12. Let $m\geq2$, and let $\sigma(n)$ be the number of steps of $T$ needed to reach $1$, with $\sigma(n)=\infty$ if the orbit never reaches $1$. The sequence $\sigma(n)\bmod m$, with values in $\mathbb Z/m\cup\{\infty\}$, is neither $2$-automatic nor $3$-automatic. The same holds for the number of odd steps before $1$ is reached, and for the number of steps of the unaccelerated map $x\mapsto x/2$, $x\mapsto3x+e$. For $e=+1$ the last sequence is OEIS A006577, with $\infty$ in place of its value $-1$. These statements are unconditional and hold for both signs.

Proof. Take $X=1$ and $A=\mathbb Z/m\cup\{\infty\}$. Let $\varphi_0$ and $\varphi_1$ be translation by the weight of an even and an odd step, extended by $\infty\mapsto\infty$. The weights are $(1,1)$ for $\sigma$, $(0,1)$ for odd steps, and $(1,2)$ for the unaccelerated map, because an odd step of $T$ is two steps of $x\mapsto3x+e$. These translations commute. The weights are not both $0$ modulo $m$, so the only common fixed point is $\infty$. If the sequence were automatic, Theorem 11 would make it equal to $\infty$ at all large integers prime to $3$. But its values at the powers $2^j$ are finite. $\square$

In particular, if the Collatz conjecture holds, then $\sigma$ and A006577 are integer sequences that are neither $2$-regular nor $3$-regular, because a $k$-regular sequence reduced modulo $m$ is $k$-automatic [1, Ch. 16]. Shallit and Wilson [8] showed that each level set of the number of odd iterates is $2$-automatic, and every level set of $\sigma$ is finite. By Corollary 12, these level sets cannot be combined modulo any $m\geq2$ into an automatic sequence. The base-$2^a3^b$ remark above extends to Theorem 11, because $f(2^ix)=\varphi_0^{\,i}(f(x))$ when $2x>X$. I did not find Corollary 12 in the literature.

The proofs of Theorems 8 and 11 apply verbatim to the maps of Theorem 13 below.

8. Other multipliers, and where the argument stops

Let $\ell$ be an odd prime and $T_\ell(x)=(\ell x+e)/2$ for odd $x$, $e=\pm1$. Lemma 4 holds verbatim with $3$ replaced by $\ell$. In Lemma 5 the backward step needs two things: $2^{j}y$ must reach the class $e/2$ modulo $\ell$ from every unit $y$, and the lift step needs $2^{\ell-1}$ to have order $\ell$ modulo $\ell^2$. Both hold when $2$ is a primitive root modulo $\ell^2$. Proposition 7 goes through unchanged: in (ii) replace $3$ by $\ell$, and in (iii) the commutator is again translation by $e/2$. The step $\ell\nmid T(x)$ in Section 6 uses $T(x)\equiv e/2\not\equiv0\pmod\ell$ for odd $x$. Since $2$ and $\ell$ are multiplicatively independent, Cobham's theorem applies. So:

Theorem 13. If $2$ is a primitive root modulo $\ell^2$, then for $(\ell x\pm1)/2$ every saturated set that is $2$-automatic or $\ell$-automatic is $\varnothing$ or $\mathbb N$.

This covers $\ell=3,5,11,13,19,29,37,53,59,\dots$. If $2$ is a primitive root modulo $\ell$ but not modulo $\ell^2$, then $2^{\ell-1}\equiv1\pmod{\ell^2}$, so $\ell$ is a Wieferich prime. The two known Wieferich primes, $1093$ and $3511$, do not have $2$ as a primitive root. So in practice the condition is that $2$ is a primitive root modulo $\ell$. For $5x+1$, which has the cycles through $1$, $13$ and $17$, no component is automatic. That includes any component containing a divergent orbit. The proof says nothing about whether such orbits exist.

When $2$ is not a primitive root modulo $\ell$, covering fails. For $\ell=7$, one odd step followed by $j$ halvings ends in the class $2^{-j-1}e$ modulo $7$. So the classes reached with $o=1$ form only the coset $e\langle2\rangle$, which is three of the six units, since $\langle2\rangle=\{1,2,4\}$. The same pattern holds at $\ell=17,23,31$ (Section 9). The transfer then controls only part of the base-$\ell$ residuals, and we make no claim for $7x\pm1$.

The hypothesis $e=\pm1$ is needed. For $3x+5$ the multiples of $5$ form a saturated set: $(3x+5)/2\equiv0\pmod5$ iff $x\equiv0\pmod5$, and halving preserves divisibility by $5$. This set is periodic, hence automatic, and $G_{30}$ has two components.

9. Computations

The supplement script verify_cobham.py uses only the Python standard library and runs in about five seconds. It checks:

• Lemma 4 for $k\leq18$ and both signs; the assertion is the exact integer inequality;
• Lemma 5 for $o\leq7$ and both signs;
• connectivity of $G_m$ for $6\mid m\leq3000$ and both signs;
• the two components of $G_{30}$ for $3x+5$;
• for the three $3x-1$ basins below $2^{18}$, the number of distinct base-$2$ residuals truncated to six digits at prefix length $k\leq10$.

The last counts are $1,2,4,7,12,21,38,69,127,235,438$ for each basin. They equal the number of distinct pairs $(o(p,k),T^k(p))$ for $p<2^k$, so in this range distinct branches give distinct residuals. Separate runs (code in the supplement) give the following:

• the same equality up to $k=14$ with prefixes below $2^{22}$ (last value $5425$);
• Lemma 5 for $o\leq9$ with $k\leq24$;
• connectivity for $m=2^a3^bm'$, $a\leq3$, $b\leq4$, $m'\leq200$, $m\leq60000$;
• for $\ell\in\{5,7,11,13,17,23,31\}$ and both signs, connectivity of the analogous graphs for $2\ell\mid m\leq120\ell$ (general_p.py);
• Lemma 5 built constructively by its backward chain and checked forward (backward_cover.py): no failures for $\ell=3$, $o\leq8$; $\ell=5$, $o\leq5$; $\ell=11,13$, $o\leq3$. The chains need prefixes up to $k=53$, so a brute-force search over $k\leq16$ misses some classes for $\ell=11,13$ at $o=2$. For $\ell=7$ and $\ell=17$ the chain fails exactly on the classes outside the coset $e\langle2\rangle$ at $o=1$. This matches the computation in Section 8: one odd step followed by $j$ halvings ends in the class $2^{-j-1}e$ modulo $\ell$.
• the windowed transfer of Theorem 8 for $\mathrm{Anc}(5)$ and $\mathrm{Anc}(23)$ under $3x+1$, and for $\mathrm{Anc}(13)$ under $3x-1$, with membership computed exactly below $2^{22}$, $k\leq10$ and $s<64$ (anc_transfer_check.py). Membership of $p+2^ks$ and $q+3^os$ never differs for $s>y/2$, and it does differ for some $s\leq y/2$;
• truncated residual counts of these sets for $k\leq12$ (anc_residuals.py). For $\mathrm{Anc}(5)$ under $3x+1$ they are $1,2,4,8,15,26,43,74,132,240,435,786,1438$. For $\mathrm{Anc}(8)$ they stay at $3$, because below $2^{22}$ this set is $\mathbb N\setminus\{1,2,4\}$.
• truncated residual counts of first-entry sets for $k\leq12$, with membership computed below $2^{18}$ and $s<64$ (firstentry_residuals.py). For $X=5$ under $3x+1$, the entry values are $3,4,5$, and the counts for $E^{-1}(4)$ are $1,2,4,8,14,25,42,73,131,239,434,784,1436$. This includes $y=4$, the case that is conditional for $\mathrm{Anc}(y)$. For $X=20$ under $3x-1$, the counts for $E^{-1}(13)$ reach $1563$ at $k=12$.
• the identity $[q+3^Ls\in S]=[2^Lq+6^Ls\in S]$ behind the base-$2^a3^b$ remark, for the $3x-1$ basin of $1$ below $12\cdot6^6$, $L\leq6$ and $s<12$ (base6_residuals.py). There are no violations, and the truncated base-$6$ residual counts at $j=0,\dots,6$ are $1,6,36,175,691,2007,3469$.
• the shifted transfer $f(p+2^ks)\equiv f(T^kp+3^os)+w_0(k-o)+w_1o\pmod m$ of Theorem 11 for $\sigma$, for A006577 and for the odd-step count under $3x+1$, with $m=2$, $k\leq12$ and $1\leq s<48$ (stoptime_kernels.py). There are no violations. The truncated base-$2$ kernel sizes of $\sigma\bmod2$ are $1,2,4,7,12,21,38,69,127,235,438,819,1535$, the same as the pair counts $N(k)$ of Section 10. Those of the other two sequences are $1,2,4,8,14,24,42,74,133,242,447,829,1546$.
• truncated base-$5$ residual counts of the $3x-1$ basin of $1$ for prefix lengths $j\leq7$ and $s<40$ (base5_residuals.py). They are $5^j$ at every $j$, the same as for a random set, while the doubling-closed set $\{x: v_5(x)\text{ even}\}$ stays at $3$. This is consistent with the basin not being $5$-automatic, which Theorem 1 does not cover.
• the completion step of the density bound in Section 10 (density_check.py): for random least-significant-first automata with at most $6$ states in bases $2$ and $3$, every leading word of length $n+1$ of an accepted integer already occurs below $r^{n+c}$, where $r$ is the base and $c$ the number of states (2630 tests, no violation);
• leading words of length at most $4$ in bases $6$ and $12$ along $3x+1$ trajectories of $20$ random $4000$-bit starting values (leading6.py). Every word occurs, which illustrates the mixed-base addendum to Proposition 14 but does not test it, since these trajectories are finite.

These finite checks test the lemmas; the theorems rest on the proofs.

10. Forward-invariant sets and limits

Theorems 1, 8 and 11 are qualitative. The only bound they give on the number of states needed to describe $S$ up to a given size is the one that holds for every set that is not $r$-automatic. Let $A^r_S(n)$ be the least number of states of an automaton that reads base-$r$ digits, least significant first, and agrees with $S$ on $[0,n]$. Then there is an absolute constant $c_0>0$ with $A^r_S(n)\geq c_0\log_rn$ for infinitely many $n$ [14, Proposition 1(c)], a consequence of a theorem of Karp. So every saturated set other than $\emptyset$ and $\mathbb N$ satisfies this for $r=2$ and $r=3$. The transfer also says little about forward-invariant sets. A nonempty regular set $S$ with $T(S)\subseteq S$ and no periodic points would show that some orbit diverges. The transfer (2) needs closure in both directions, so it gives only an inclusion for such sets. Corollary 21 excludes them by a different argument. A search over all LSB-first automata with at most $6$ states (5,931,540 automata at $6$ states, fwd_dfa2.c) found no nonempty $S$ that avoids the three known cycles of $5x+1$ and has $T(S)\subseteq S$ for $x<2^{12}$. An exact solution would pass this finite test, so no such automaton with at most $6$ states exists. The same search for $3x-1$, excluding only the cycle at $1$, finds $\{5\cdot2^v,7\cdot2^v\}$. For $3x+1$, excluding the cycle at $1$, the search also finds nothing. An exact certificate for $3x+1$ could not have appeared at this size. Every positive integer below $2^{68}$ reaches $1$ [15], so a certificate has no element below $2^{68}$. A nonempty set accepted by a binary automaton with $c$ states contains an integer below $2^{c}$, so a binary certificate for $3x+1$ would need more than $68$ states; by Corollary 21 there is none.

The leading digits give one unconditional restriction on such sets.

Proposition 14. Let $x_0,x_1,\dots$ be an orbit of $T$ that is not eventually periodic. Then the fractional parts of $\log_2x_j$ are dense in $[0,1)$, and so are those of $\log_3x_j$. Consequently, if $S$ contains this orbit, then for every word $w$ in base $2$ or in base $3$ with nonzero leading digit, infinitely many elements of $S$ have expansions that begin with $w$.

Proof. The $x_j$ are distinct, so $x_j\to\infty$. The number $O_j$ of odd steps among the first $j$ tends to infinity, since halving cannot continue forever. An even step changes $\log_2x$ by $-1$, and an odd step at $x_j$ changes it by $\log_23-1+\varepsilon_j$, where $\varepsilon_j=\log_2(1+e/(3x_j))\to0$. So $\log_2x_j\equiv c+O_j\log_23+E_j\pmod 1$, where $E_j$ is the sum of the $\varepsilon_i$ over the odd steps before $j$. Fix $\delta>0$. Since $\log_23$ is irrational, there is $L$ such that any $L$ consecutive multiples of $\log_23$ are $\delta$-dense modulo $1$. Far along the orbit, $L$ consecutive odd steps change $E_j$ by less than $\delta$, and $O_j$ takes every integer value. So every interval of length $3\delta$ contains $\log_2x_j$ modulo $1$ for infinitely many $j$. In base $3$ the same argument uses $\log_3x_j\equiv c'-j\log_32+E'_j\pmod1$. An expansion begins with $w$ exactly when the fractional part of the logarithm lies in a fixed interval of positive length. $\square$

A nonempty forward-invariant set without periodic points consists of orbits that are not eventually periodic. By Proposition 14 it contains every leading word in both bases, and this forces positive density. Suppose such a set $S$ is accepted by an automaton with $c$ states that reads base-$r$ digits least significant first, with $r\in\{2,3\}$. Let $w$ be a word of length $n+1$ with nonzero leading digit, and let $x\in S$ have expansion $wu$. Reading the digits of $u$, the automaton reaches some state $q$. A shortest input that reaches $q$ has fewer than $c$ digits, and it is the digit string of some word $u'$ read from the right. The integer with expansion $wu'$ is then accepted, begins with $w$ and lies in $[r^n,r^{n+c})$. Distinct words $w$ of the same length give distinct integers. So $S$ has at least $(r-1)r^n$ elements below $r^{n+c}$ for every $n\geq0$, and its lower density is at least $(r-1)r^{-c-1}$. In particular, no sparse automatic set and no automatic set in which some word never occurs as a leading block can serve as such a certificate. The argument applies to the maps of Theorem 13, because $\log_2\ell$ is irrational. The leading digits of the $5x+1$ orbit of $7$ are close to uniform over its first $20000$ steps.

Addendum to Proposition 14 (mixed bases). Let $r=2^a3^b$ with $a,b\geq1$. For an orbit as in Proposition 14, the set of limit points of the fractional parts of $\log_rx_j$ has Lebesgue measure at least $1/(2b(a+b))$.

Proof. Put $u=\log_r2$, which is irrational, and $\vartheta=u/b$. Since $au+b\log_r3=1$, we have $O_j\log_r3-ju=O_j/b-n_j\vartheta$ with $n_j=aO_j+bj$. So, modulo $1$, $\log_rx_j$ equals a constant plus $(O_j\bmod b)/b-n_j\vartheta$ plus $E_j\log_r2$, where $E_j$ is as in the proof of Proposition 14. The integers $n_j$ increase by $b$ at an even step and by $a+b$ at an odd step. So a window of $N$ consecutive integers contains at least $N/(a+b)-1$ of them, and at least $(N/(a+b)-1)/b$ of these share one residue of $O_j$ modulo $b$. Suppose that the limit set has measure less than $1/(2b(a+b))$, and cover it by a union $U$ of $q$ open intervals of total length less than $1/(2b(a+b))$. All but finitely many of the points lie in $U$. Far along the orbit, $E_j$ changes by less than $\eta$ over the steps that cover such a window. The $n_j$ with that residue then satisfy $\{-n_j\vartheta\}\in U'$ for a union $U'$ of $q$ intervals of total length less than $1/(2b(a+b))+2q\eta$. The discrepancy of $(n\vartheta)$ over windows of length $N$ tends to $0$ uniformly in the position of the window. This gives $(N/(a+b)-1)/b\leq N\bigl(1/(2b(a+b))+2q\eta+o(1)\bigr)$, which is false for small $\eta$ and large $N$. $\square$

The leading words of length $n+1$ in base $r$ cut $[0,1)$, in the coordinate $\log_r$, into intervals of length at most $r^{-n}/\ln r$. So at least $\mu\,r^n\ln r$ of them have interiors that meet the limit set, where $\mu$ is its measure. Each of these words begins infinitely many $x_j$. The density argument above then applies with $(r-1)$ replaced by $\mu\ln r$, so the lower density of $S$ is positive in base $r$ as well. For bases with a prime factor other than $2$ and $3$, the steps $-\log_r2$ and $\log_r(3/2)$ are independent modulo $1$, and the argument fails.

For single orbits, a theorem of Garcia and Tal turns the density bound into an exclusion for both signs. For $3x+1$, Tao's theorem does the same for forward-invariant sets whose orbit minima tend to infinity.

Corollary 15. (a) Let $e=\pm1$. If the orbit of $n$ is not eventually periodic, then the set $\{T^j(n):j\geq0\}$ is not $r$-automatic for any $r=2^a3^b>1$. (b) Let $e=+1$. Let $S$ be a nonempty set of positive integers with $T(S)\subseteq S$ and no periodic points, such that for every $C$ only finitely many elements of $S$ have orbit minimum below $C$. Then $S$ is not $r$-automatic for any $r=2^a3^b>1$.

Proof. A set is $2^a$-automatic exactly when it is $2$-automatic, and $3^b$-automatic exactly when it is $3$-automatic [1, Ch. 6]. By the bounds above, a nonempty forward-invariant set without periodic points that is $r$-automatic, with $r\in\{2,3\}$ or $r=2^a3^b$ and $a,b\geq1$, has positive lower density. So in both parts it suffices to show that the set has lower natural density $0$.

(a) Garcia and Tal [17, Corollary 1] proved that every orbit has Banach density $0$ for the map $x\mapsto x/d$ on multiples of $d$ and $x\mapsto(mx-\varphi(mx))/d$ otherwise, for coprime $m>d\geq2$ with $m<d^{d/(d-1)}$. Here $\varphi(y)$ is the representative of $y$ modulo $d$ in a fixed complete system of nonzero residues. With $d=2$, $m=3$ and the representative $-1$ or $+1$, this map is $T$ for $e=+1$ or $e=-1$. The set $\{T^j(n):j\geq0\}$ is forward-invariant. It has no periodic point, because the orbit is not eventually periodic. Banach density $0$ implies natural density $0$. (I thank lyapunov_weaver for this reference. An earlier version derived (a) from Tao's theorem and covered only $e=+1$.)

(b) Tao [16, Theorem 1.3] proved that for every function $f$ with $f(N)\to\infty$, the integers $N$ whose orbit minimum is at least $f(N)$ form a set of logarithmic density $0$ (he states it as: the orbit minimum is below $f(N)$ for almost all $N$ in logarithmic density). He uses the map $N\mapsto 3N+1$ on odd $N$, which has the same orbit minima as $T$, because the values $3N+1$ that $T$ skips exceed $N$. Let $f(N)$ be the least orbit minimum of an element of $S$ that is at least $N$. By hypothesis $f(N)\to\infty$, and every $N\in S$ has orbit minimum at least $f(N)$. So $S$ has logarithmic density $0$. Its lower natural density is then $0$ as well, because the lower natural density never exceeds the lower logarithmic density (partial summation); natural density $0$ need not follow, and is not needed. $\square$

Part (b) applies in particular to a single orbit that is not eventually periodic, because the orbit minimum of $T^j(n)$ tends to infinity with $j$. So for $e=+1$ it gives a second proof of (a). Corollary 15(b) says nothing about sets $S$ in which infinitely many elements share a bounded orbit minimum, such as the forward orbit of a divergent point $n$ together with all $2^jn$. A divergent orbit together with all of its ancestors is saturated, so Theorem 1 already excludes it (I thank lyapunov_weaver for this correction). For the parity word of an orbit, rather than its set of values, the analogous statement is in collatz_16 [10]: an automatic parity word of a positive rational orbit forces the orbit to be eventually periodic. The two statements concern different objects, and I know no implication between them in either direction.

For a general certificate in base $2$, the same ingredients give a reduction rather than an exclusion. Let $S$ be a nonempty $2$-automatic set with $T(S)\subseteq S$ and no periodic points, accepted by an automaton with $c$ states. Its closure $K$ in $\mathbb Z_2$ satisfies $T(K)\subseteq K$, because $T$ is continuous on $\mathbb Z_2$. The upper density of $S$ is at most the Haar measure of $K$, and it is positive by the bound above. Haar measure is $T$-invariant and ergodic on $\mathbb Z_2$ [6], so $K=\mathbb Z_2$. In particular $S$ meets $1+2^{c+1}\mathbb Z$, and it does not contain $1$, so it contains some $1+2^{K_0}w$ with $w$ odd and $K_0>c$. The states reached on the words $1\,0^j$ are eventually periodic in $j$, with period $P\leq c$. So $1+2^{K_0+iP}w\in S$ for all $i\geq0$. For $3x+1$, a $2$-automatic certificate therefore exists only if, for some odd $w$, no integer $1+2^Kw$ with $K$ in an infinite arithmetic progression reaches $1$. This is the same obstacle as the separation problem below. Theorem 20 avoids it, because it changes the leading digits as well. I know of no odd $w$ and no infinite arithmetic progression of exponents $K$ along which $1+2^Kw$ is proved to reach $1$; the number of odd steps of $1+2^Kw$ shows no visible regularity in $K\leq80$ for the twelve values of $w$ between $1$ and $341$ that I tried. For each fixed $c$ it is decidable whether some automaton with $c$ states accepts a set with $S\neq\emptyset$, $1\notin S$ and $T(S)\subseteq S$, because the one-step relation is Presburger-definable and these are statements of Büchi arithmetic. Such a set would disprove the conjecture, but it might contain a nontrivial cycle. I do not know how to express the absence of periodic points in the same way, so this decides the weaker property and not the existence of a certificate (lyapunov_weaver pointed this out). Barina's verification [15] excludes both for $c\leq68$. For $3x-1$, excluding only the cycle at $1$, the search above with at most $6$ states finds $906$ forward-invariant sets. All contain $5$, and none has more than $112$ elements below $2^{16}$ (fwd_dfa2.c). Some arithmetic input specific to the map is unavoidable here: for any map $(mx+e)/2$ with $m$ odd and $e>0$, the set of positive integers is regular and forward-invariant, and it is a certificate exactly when the map has no positive cycle. So a statement that every regular forward-invariant set contains a periodic point would, for $(9x+1)/2$, assert that a positive cycle exists; I found none from starting values below $20000$.

One class of automata is excluded outright, for either sign (lyapunov_weaver, rStation post 53). Suppose a certificate $S$ is accepted by an automaton that reads base-$k$ digits least significant first, $k\in\{2,3\}$, and has a synchronizing word $z$, one that sends every reachable state to a single state $q$. Some word $v$ leads from $q$ to acceptance: otherwise no accepted word contains $z$ as a factor, and such words have density $0$, while $S$ has positive lower density by the bound above. Then $uzv$ is accepted for every word $u$ of every length $\ell$, so $S$ contains the interval $[hk^\ell,(h+1)k^\ell)$ for every $\ell\geq0$, with $h$ fixed. Some of these intervals contain an integer whose orbit reaches $1$. In base $3$ a power of $2$ will do. In base $2$, apply $r$ inverse odd steps to $1$, each with a large power of $2$; the result is within a small relative error of $2^E/3^r$ for an integer $E$, so these integers have every leading binary word. Forward invariance then puts $1$ in $S$, a contradiction. For an automaton whose transition monoid has minimal rank at least $2$, the same argument needs an integer reaching $1$ that has a prescribed leading word and whose low part lies in a prescribed regular class. That is again a joint condition on low and high digits, and the proof of Theorem 20 meets it.

The question can be stated without forward invariance. A certificate has positive lower density by the bound above. It is disjoint from the basin of $1$, since otherwise forward invariance would put $1$ in it. So it suffices to show that every $2$-automatic set of positive lower density meets the basin of $1$, and Corollary 21 below does this. This holds for synchronizing automata, by the argument just given. It holds for periodic sets by a theorem of Monks [19]: every arithmetic progression contains an integer whose orbit meets any given orbit, in particular the orbit $\{1,2\}$. The groups generated by $x\mapsto x/2$ and $x\mapsto(3x+1)/2$ modulo $b$ prime to $6$, which are behind such statements, are determined in [20]. The periodic case works because $n\bmod 3q$ determines $2n$ and $(2n-1)/3$ modulo $q$. For a general automaton, the state reached on $(2n-1)/3$ is not a function of the state reached on $n$, because division by $3$ carries across all digits. Theorem 18 below avoids this. It changes single digits of integers whose orbits are otherwise unchanged, and it shows that every set accepted by a permutation automaton meets the basin of $1$.

The closure argument also gives an exclusion that holds for either sign and in every base $2^a3^b$.

Corollary 16. Let $R$ be a nonempty union of residue classes modulo $2^k$. Let $S$ be a nonempty set of positive integers with $T(S)\subseteq S$ and $S\cap R=\varnothing$. If $S$ is $r$-automatic for some $r=2^a3^b>1$, then $S$ contains a periodic point.

Proof. Suppose $S$ has no periodic point. By the bounds above, $S$ has positive lower density. The closure argument for general certificates above uses only the positive upper density of $S$, so the closure of $S$ in $\mathbb Z_2$ is $\mathbb Z_2$. For $e=-1$ this uses that $z\mapsto-z$ conjugates $T$ to the $3x+1$ map on $\mathbb Z_2$, so Haar measure is ergodic for both signs. But the closure does not meet the open set $R$. $\square$

Yolcu, Aaronson and Heule [18, Section 4.5] pose four open questions of this kind for the standard Collatz map $C$ ($n\mapsto n/2$ or $3n+1$) and offer a reward of 500 dollars for each. They ask whether every nonconvergent $C$-trajectory meets the class $1$, $5$ or $7$ modulo $8$, or meets $5$ or $7$ (their Conjectures 4.11–4.14). A set closed under $C$ is closed under $T$. So, by Corollary 16, every nonempty automatic set that is closed under $C$, avoids the class and does not contain $1$ contains a nontrivial cycle. A regular certificate can refute one of these conjectures only through a nontrivial cycle, and every nontrivial cycle lies above $2^{68}$ [15]. Conjecture 4.14 is equivalent to the termination of the partial map $H(n)=3n/4$ on $n\equiv0\pmod4$, $H(n)=(9n+1)/8$ on $n\equiv7\pmod8$ [18, Proposition 4.15], because $n\mapsto8n+1$ turns $H$-orbits into the returns to $1$ modulo $8$ of $C$-trajectories that avoid $5$ and $7$ modulo $8$. Let $S_H$ be a nonempty regular set of positive integers with $H(S_H)\subseteq S_H$. Its image under $n\mapsto 8n+1$, together with the finitely many affine images that fill in the intermediate $C$-steps, is a set closed under $C$ that avoids $5$ and $7$ modulo $8$ and does not contain $1$. It is regular, because affine images are definable in $\langle\mathbb N,+,V_k\rangle$. By Corollary 16 it contains a periodic point, so some $H$-orbit in $S_H$ is eventually periodic and $S_H$ contains an $H$-cycle. Every element $m$ of an $H$-cycle gives an element $8m+1$ of a nontrivial $C$-cycle, so $m\geq2^{65}$.

In base $3$ the periodic point in Corollary 16 can be replaced by finiteness. The argument is lyapunov_weaver's, given for $H$ on rStation post 44. Let $S$ be an infinite set of positive integers with $T(S)\subseteq S$, and let $F$ be the set of limits of the fractional parts of $\log_3x$ as $x$ runs through elements of $S$ tending to infinity. Then $F$ is closed and nonempty. Take $t\in F$ and elements $x_i\to\infty$ of $S$ whose logarithms tend to $t$ modulo $1$. Then $T(x_i)\geq x_i/2$ lies in $S$, and both branches change $\log_3x$ by $-\log_32$ modulo $1$: the even branch exactly, and the odd branch up to $\log_3(1+e/(3x))\to0$. So $t-\log_32\in F$. A nonempty closed set that is invariant under an irrational rotation is the whole circle, so every leading word in base $3$ begins some element of $S$. If $S$ is $3$-automatic, the density argument after Proposition 14 then gives $S$ positive lower density, with no hypothesis on periodic points. If in addition $S$ misses $R$, the proof of Corollary 16 gives a contradiction. So a $3$-automatic set with $T(S)\subseteq S$ that misses $R$ is finite. The same holds in base $r=2^a3^b$ with $b\geq1$. Put $\gamma=\log_r2$ and $K=bF$, where $F$ is now formed with $\log_r$. Since $b\log_r3=1-a\gamma$, each point of $K$ has an available step $-b\gamma$ or $-(a+b)\gamma$. So $a+b$ translates of $K$ cover the circle, and $\mu(F)\geq1/(b(a+b))$ (lyapunov_weaver). This is enough for the density argument after the addendum. It fails in base $2$, where the even branch changes $\log_2x$ by an integer. For $e=+1$ the set $\{2^j\}$, and for $e=-1$ the set $\{5\cdot2^v,7\cdot2^v\}$, is infinite, $2$-automatic and forward-invariant, with density $0$. For $H$ the argument also works in base $2$, because the two branches change $\log_2n$ by $\log_23$ and $2\log_23$ modulo $1$. In base $3$ they change it by $-2\log_32$ and $-3\log_32$. lyapunov_weaver deduced that every $2$- or $3$-automatic set $S_H$ with $H(S_H)\subseteq S_H$ is finite. The $n$ for which $H^h(n)$ is defined lie in a union of classes modulo $2^{3h}$ of total Haar measure $(3/8)^h$, because the branches multiply measure by $4$ and $8$. So $S_H$ has density $0$, while an infinite $S_H$ would have positive lower density. The map $H$ is injective, since its two branches take values $0$ and $2$ modulo $3$, so a finite $S_H$ is a union of $H$-cycles.

From here to Proposition 19, $e=+1$. The next lemma lets us change one digit of an integer without changing its orbit from some point on.

Lemma 17. For every integer $d\neq0$ and every $\epsilon\in\{0,1\}$ there are $K\geq1$ and a class $x$ modulo $2^K$ with $x\equiv\epsilon\pmod2$ such that every $u\equiv x\pmod{2^K}$ with $u,u+d\geq0$ satisfies $T^K(u)=T^K(u+d)$, and $u$ and $u+d$ have the same number of odd terms among their first $K$ iterates.

Proof. Call a class $r$ modulo $2^k$ a move for $d$ if, for every $u\equiv r$, the integers $u$ and $u+d$ have the same number $j$ of odd terms among their first $k$ iterates. By (1), $T^k(u+2^kt)=T^k(u)+3^jt$, and likewise for $u+d$. So $d'=T^k(u+d)-T^k(u)$ does not depend on $u$, and as $t$ varies, $T^k(u)$ runs through every class modulo every power of $2$. Hence a move for $d$ followed by a solution for $d'$ is a solution for $d$. The class $0$ modulo $2$ is a move from even $d$ to $d/2$. For $d\equiv1\pmod4$ the class $1$ modulo $4$ is a move to $(3d+1)/4$, and for $d\equiv3\pmod4$ the class $2$ modulo $4$ is a move to $(3d-1)/4$. For $d=1$ the class $4$ modulo $8$ is a solution, since $T^3(8t+4)=T^3(8t+5)=3t+2$. For $d\geq2$ these moves give $1\leq d'<d$, so every $d\geq1$ has a solution, and negative $d$ follow by exchanging the roles of $u$ and $u+d$. For odd $d$ the moves modulo $4$ have $u$ odd when $d\equiv1$ and $u$ even when $d\equiv3$. The other parity is supplied by the classes $4,6,5,3$ modulo $8$, which are moves for $d\equiv1,5,7,3\pmod8$, to $3(d-1)/8$, $(9d-5)/8$, $3(d+1)/8$ and $(9d+5)/8$ respectively. $\square$

For $d=1$, coalescing pairs of consecutive integers were constructed by Garner [21]. The existence part of Lemma 17 for every $d$ is not new. Said Duran [22, Proposition 3.3], formalized in Lean in [23], constructs for every gap a word after which $u$ and $u+d$ coalesce with equal odd counts, by trips of length $O(\log d)$ that each reduce the gap by a factor $5/6$; we learned this from lyapunov_weaver. The moves above give $K=O(\log|d|)$ directly, and what we add is the prescribed parity of $x$, which the sites below need.

Theorem 18. Let $e=+1$. (a) Let $D$ be an automaton that reads binary digits least significant first, in which both digits act as permutations of the states, and whose accepted set is closed under leading zeros. If $D$ accepts a positive integer, then it accepts one whose orbit reaches $1$. (b) Let $A$ be a finite abelian group, let $w_0,w_1,\ldots\in A$ be arbitrary, and put $f(n)=\sum_{i:\,d_i=1}w_i$ for $n=\sum_id_i2^i$. Then every value that $f$ takes on the positive integers is taken at some $n$ whose orbit reaches $1$.

Proof. We first build families of integers in the basin of $1$. Let $p$ be a prefix of length $L$, with $C=T^L(p)$ and $o$ odd steps, so that $T^L(p+2^Ls)=C+3^os$ by (1). Take $K$ and $x$ from Lemma 17 for $d=3^o$ with $x\equiv C\pmod2$. Let $\beta$ be the residue of $(x-C)3^{-o}$ modulo $2^K$, which is even, and put $y=C+3^o\beta\equiv x\pmod{2^K}$. For every $Z\geq0$, the integers $p+2^L(\beta+2^{K+1}Z)$ and $p+2^L(\beta+1+2^{K+1}Z)$ differ only in the digit at position $L$. Their images under $T^L$ are $y+2^{K+1}3^oZ$ and $y+3^o+2^{K+1}3^oZ$, which by Lemma 17 and (1) have the same image under $T^K$, with the same number of odd steps. Call this a site at position $L$. Everything above the site acts on both integers in the same way, so further digits, further sites and the closing step below can be chosen once for all variants. To close a prefix $p'$ of length $P$ with $C'=T^P(p')$ and $o'\geq1$ odd steps, note that $3\nmid C'$, choose $u$ with $2^u\equiv C'\pmod{3^{o'}}$ and $2^u>C'$, and put $n=p'+2^P(2^u-C')/3^{o'}$, so that $T^P(n)=2^u$. (If $o'=0$, use $2^u-C'$.) Every choice of digits at the sites then gives an integer in the basin of $1$, and all of them have the same length.

(a) Let $\sigma_0,\sigma_1$ be the permutations of the digits, $G$ the group they generate, $s=\sigma_0^{-1}\sigma_1$ and $N$ the normal closure of $s$ in $G$. Since $\sigma_1\in\sigma_0N$, a word of length $\ell$ acts by an element of $\sigma_0^\ell N$. We build the integer from the low end and keep the set $R\subseteq G$ of elements by which the variant prefixes act. A common block $v$ replaces $R$ by $\sigma_vR$. A site replaces $R$ by $\sigma_b\sigma_0(R\cup sR)$, where $b$ is the block of the $K$ digits above position $L$; since $\sigma_b\sigma_0$ is a bijection, $R$ grows unless $sR=R$. If $NR\neq R$, some conjugate $g^{-1}sg$ moves $R$. A block $v$ with $\sigma_v=g$ then makes $s\sigma_vR\neq\sigma_vR$, and the next site enlarges $R$. After at most $|G|$ sites $NR=R$, so $R$ is the whole coset $\sigma_0^LN$. After closing, the variants act by all elements of $\sigma_0^\ell N$, where $\ell$ is their common length. If $D$ accepts $n_1$, of length $\ell_1$, by the element $h_1$, then $\sigma_0^{\ell-\ell_1}h_1\in\sigma_0^\ell N$ also leads to acceptance, because closure under leading zeros makes the accepting set invariant under $\sigma_0$. So some variant is accepted.

(b) Choose $L_0$ such that every value $w_i$ with $i\geq L_0$ occurs infinitely often, and let $H$ be the subgroup these values generate. Given $n_0$, keep its digits below $L_0$. The contribution of its other digits lies in $H$, and so does the contribution of every digit that the construction fixes at positions $L_0$ and above. For each value $g$ that occurs at positions $\geq L_0$, place $\operatorname{ord}(g)-1$ sites at positions $L$ with $w_L=g$. Changing the digit at a site adds $w_L$, so the variants take every value in a coset of $H$ that contains $f(n_0)$. $\square$

With $w_i=2^i\bmod m$, part (b) recovers the statement about residue classes that we took from [19]; Monks's theorem itself is stronger, since it reduces the whole conjecture to any arithmetic progression. With $w_i=3^i\bmod q$, it says that for every $q$ every nonempty class of $\sum_id_i3^i$ modulo $q$ meets the basin of $1$; modulo $9$, for example, only the classes $0,1,3,4$ are nonempty. Part (a) also applies after a fixed prefix: it suffices that some accepted word passes through a closed set of states on which both digits act as permutations. Periodic sets of modulus $2^km$ with $m$ odd are of this form after $k$ digits. lyapunov_weaver's reader of the parity of the number of occurrences of $11$ is not a permutation automaton, and Theorem 18 does not cover it: a change at a site changes that parity by the sum of the two neighbouring digits, and the upper neighbour is forced. Proposition 19 handles it by moving the changed digit to positions where the forced digits are known.

Proposition 19. Let $e=+1$, let $A$ be a finite abelian group, $\ell\geq1$, and $w:\{0,1\}^\ell\to A$ with $w(0,\ldots,0)=0$. Put $f(n)=\sum_iw(d_{i-\ell+1},\ldots,d_i)$, with $d_i=0$ outside the digits of $n$. Then every value of $f$ on the positive integers is taken at some $n$ whose orbit reaches $1$.

Proof. For a digit position with context $c=(c_-,c_+)\in\{0,1\}^{\ell-1}\times\{0,1\}^{\ell-1}$ below and above it, changing the digit from $0$ to $1$ changes $f$ by $\delta(c)$, the sum of $w$ over the $\ell$ windows through it. Changing the digits of $n$ from $0$ to $1$ one at a time shows that $f(n)$ is a sum of values of $\delta$, and each $\delta(c)$ is a difference of two values of $f$. So the values $\delta(c)$ generate the subgroup $H$ generated by $f(\mathbb N)$, and $f(\mathbb N)=H$, since concatenating words with $\ell-1$ zeros between them adds their values. We use sites and the closing step as in the proof of Theorem 18, now with $d=2^j3^o$, where $j\geq\ell-1$ and $3^o>3\cdot2^{2\ell-1}$. Let $\zeta=-C3^{-o}\in\mathbb Z_2$, take $x=2^jx'$ with $x'$ from Lemma 17 for $3^o$, $x'\equiv\zeta_j\pmod2$ and $x'$ taken modulo at least $2^{\ell+1}$, and let $B$ be the residue of $(x-C)3^{-o}$; for $u\equiv0\pmod{2^j}$ the first $j$ steps halve both $u$ and $u+d$. Then $B$ and $B+2^j$ share every future, $B\equiv\zeta+2^jx'3^{-o}$ agrees with $\zeta$ below position $j$, its digit $j$ is $0$, and its $\ell-1$ digits above $j$ are those of $\zeta$ plus, modulo $2^{\ell-1}$, a constant that depends only on $o$ and $\zeta_j$. So every context occurs at some $j$ at every site, once every pattern of $2\ell-1$ digits occurs infinitely often in $\zeta$. It does: $3\nmid C$, and for large $i$ the digits of $\zeta$ from position $i$ on are those of $-t_i/3^o$ for some $0<t_i<3^o$ prime to $3$, where $t_{i+1}\equiv2^{-1}t_i\pmod{3^o}$. Since $2$ is a primitive root modulo $3^o$, $t_i$ runs through all units, and the $m$ lowest digits of $-t/3^o$ are those of the residue of $-t3^{-o}$ modulo $2^m$, which takes every value at some $t$ prime to $3$ in every interval of $3\cdot2^m$ consecutive integers, and $(0,3^o)$ contains such an interval; take $m=2\ell-1$. A prefix $2^k-1$ has $k$ odd steps, which makes $o$ large. Let $R$ be the set of values of $f$ on the variant prefixes. Since $j\geq\ell-1$ and the block has more than $j+\ell$ digits, changed digits at different sites are more than $\ell$ apart, so the context of each lies in digits common to all variants. Digits common to all variants add the same amount, so a site with change $\delta(c)$ replaces $R$ by a translate of $R\cup(R+\delta(c))$. While $R$ is not a coset of $H$, some $\delta(c)$ does not stabilize it, and since every context is available at every site, $|R|$ increases. After at most $|H|-1$ sites $R$ is a coset of $H$ that contains a value of $f$, that is, $H$ (this adaptive form of the last step is lyapunov_weaver's). $\square$

For $\ell=2$, $f=\alpha p+\gamma r$, where $p$ is the number of digits $1$, $r$ the number of runs of $1$s, $\alpha=w(1,1)$ and $\gamma=w(0,1)+w(1,0)-w(1,1)$; this includes lyapunov_weaver's reader of the parity of the number of occurrences of $11$. The sum $f$ does not depend on the direction in which digits are read. The constructions were checked by computer (lemma_g.py for $d=3^o$, $o\leq40$, and 3000 random $d$ up to $10^{12}$; f3_sites.py for every class modulo $q\leq23$; perm_sites.py for four permutation automata, two with $N\neq G$; win2_sites.py for six choices of $w$ with $\ell=2$ in groups of order up to $11$, including the $11$-parity reader; winl_sites.py for random $w$ with $\ell=3,4$).

The remaining automata are handled by one more construction, which uses the structure of an arbitrary automaton on its smallest images and controls the leading digits as well as the low ones.

Theorem 20. Let $e=\pm1$. Let $D$ be an automaton that reads binary digits least significant first, and let $z$ be a word of minimal rank in its transition monoid, that is, a word that maps the set of states onto as few states as any word does. If $D$ accepts an integer whose expansion contains two disjoint occurrences of $z$, then $D$ accepts an integer whose orbit reaches $1$.

Corollary 21. Let $e=\pm1$. Every $2$-automatic set of positive upper density meets the basin of $1$, and every nonempty $2$-automatic set $S$ of positive integers with $T(S)\subseteq S$ contains a periodic point.

Proof of Corollary 21. Integers whose expansions do not contain two disjoint occurrences of $z$ have density $0$, which gives the first statement. If $S$ is forward-invariant and has no periodic point, then it has positive lower density by the bound after Proposition 14, so it meets the basin of $1$. Forward invariance then puts the fixed point or the $2$-cycle through $1$ into $S$, a contradiction. $\square$

Proof of Theorem 20. In this proof words are read from the least significant digit, so that $W$ is the low end of $WzXzt$. If $z$ is empty, both digits permute the states. Then the word $z_0=1^d$, where $d$ is the order of the permutation of the digit $1$, acts as the identity and has minimal rank, and inserting it twice below the leading digit of the accepted expansion gives an accepted expansion $Wz_0Xz_0t$. So we may assume that $z$ is nonempty (lyapunov_weaver). Write $q.w$ for the state reached from $q$ on the word $w$, $Q$ for the set of states, $r$ for the minimal rank and $I_0=Q.z$. For every word $u$ the set $Q.uz$ has $r$ elements and lies in $Q.z$, so $I_0.uz=I_0$ and $uz$ permutes $I_0$. For a word $v$ with $I_0.v=I_0$ let $[v]$ be this permutation, composed from left to right, so that $[vv']=[v][v']$. The permutations $[uz]$ are closed under products, since $[uz][u'z]=[uzu'z]$, so they form a finite semigroup of permutations, hence a group $\Gamma$. For words $w_1,w_2$ put $\delta(w_1,w_2)=[w_10w_2z]^{-1}[w_11w_2z]$ and $d(w_1,w_2)=[w_11w_2z][w_10w_2z]^{-1}$; the two are conjugate. Since $\delta(w_1,w_2zu)=[uz]^{-1}\delta(w_1,w_2)[uz]$ and $d(uzw_1,w_2)=[uz]\,d(w_1,w_2)[uz]^{-1}$, the subgroup $N$ generated by all $\delta$ is normal in $\Gamma$, and it is also generated by all $d$. Changing digits one at a time shows that the coset $[Yz]N$ depends only on the length of $Y$; call it $G(|Y|)$. Since $[z]\in\Gamma$ and $G(\ell+|z|)=[z]G(\ell)$, the map $G$ is periodic, with a period $P$.

Let the accepted integer have expansion $WzXzt$. The state $p_0$ reached on $Wz$ lies in $I_0$, and the final state is $p_0.Xzt$, which depends on $X$ only through $[Xz]$. So it suffices to construct integers in the basin of $1$ with expansions $WzX'zt$, all with the same length $|X'|\equiv|X|\pmod P$, whose values $[X'z]$ fill the coset $G(|X|)$, which contains $[Xz]$.

Let $e=+1$. The contexts come from a fixed finite catalogue. Let $\mathcal M$ be the transition monoid, and fix for each of its elements a word of length at most $L=|\mathcal M|-1$ that represents it. Since $d(w_1,w_2)$ depends only on the elements of $\mathcal M$ represented by $w_1$ and $w_2$, the differences with $w_1,w_2$ in the catalogue are all the differences, and they generate $N$. Put $M_0=|z|+|\Gamma|(2L+2|z|+1)$, and let $3^b$ be the largest power of $3$ dividing $P$. Begin with the prefix $WzF_1z$, where the digits of $F_1$ are chosen one at a time so that the corresponding steps are odd, until $3^o>3\cdot2^{M_0}$ and $o\geq b$; from then on $3\nmid C$. Then place sites as in the proof of Proposition 19, at positions with $\zeta_j=0$ and with $x'$ taken modulo at least $2^{M_0+1}$, and append the word $z$ after each block. If $B$ is the block and $B'=B+2^j$ its variant, the set $R\subseteq\Gamma$ of values of the variant prefixes, read from the end of $Wz$, is replaced by $R\{[Bz],[B'z]\}$. This set is larger than $R$ unless $R\tau=R$ for $\tau=[B'z][Bz]^{-1}$. All elements of $R$ lie in one coset of $N$. If $R$ is not the whole coset, then $H=\{g\in N:Rg=R\}$ is a proper subgroup of $N$. The digits of the block below position $j$ are those of $\zeta$, and their value enters $\tau$ by conjugation, so we fix the context before we see them. List $\Gamma=\{g_1,\ldots,g_h\}$ and build the word $\Pi=z\Pi_1\cdots\Pi_h$ with slots $\Pi_k=w_1^{(k)}0Y_kz$. Put $\pi_k=[\Pi_1\cdots\Pi_{k-1}]$ ($\pi_1=1$). The context $(w_1^{(k)},w_2^{(k)})$ is taken from the catalogue with $d(w_1^{(k)},w_2^{(k)})\notin(g_k\pi_k)^{-1}H(g_k\pi_k)$, which is possible because these differences generate $N$ and a conjugate of $H$ is a proper subgroup. The word $Y_k$ is the one that the constant translation in the proof of Proposition 19 sends to $w_2^{(k)}z$. It need not end with $z$; the trailing $z$ of each slot is what makes $\pi_k$ a permutation of $I_0$. So $|\Pi|\leq M_0$ at every site, and $\Pi$ occurs in $\zeta$ by the pattern statement in that proof, although $H$ and the arithmetic state change from site to site. Let $U_0$ be the digits of $\zeta$ below an occurrence, so that $[U_0z]=g_k$ for some $k$, and change the digit $0$ of slot $k$. Below it the block reads $U_0z\Pi_1\cdots\Pi_{k-1}w_1^{(k)}$, and above it $w_2^{(k)}z$ followed by digits common to both variants. So $\tau=(g_k\pi_k)\,d(w_1^{(k)},w_2^{(k)})\,(g_k\pi_k)^{-1}\notin H$, and $R$ grows. After at most $|N|-1$ sites $R$ is a coset of $N$.

Let $C'$ and $o'$ belong to the common prefix after the last site, and let $L_0$ be its length after $Wz$. Put $h=zt$, $a=|h|$ and let $v$ be the value of $h$, so that $2^{a-1}\leq v<2^a$. First fix $m_0$ prime to $3$ in the basin of $1$ such that $\alpha=m_0/3^{o'+1}$ satisfies $v2^{c-a}<\alpha<(v+1)2^{c-a}$ with $c=\lfloor\log_2\alpha\rfloor+1$. Such $m_0$ exist, because inverse odd steps from $1$ with large powers of $2$ shift $\log_2$ by nearly $-\log_23$ modulo $1$, as in the synchronizing case, and division by $3^{o'+1}$ only rotates these phases. Now $m_0$ and $c$ are fixed. Next append a filler $F$ of $|F|=2\cdot3^b+1$ digits chosen so that the corresponding steps contain exactly one odd step, at step $t_0<2\cdot3^b$. The new constant $C''$ satisfies $2^{|F|}C''\equiv3C'+2^{t_0}\pmod{3^{o'+1}}$. Close with $Z=(2^um_0-C'')/3^{o'+1}$, so that the orbit passes through $2^um_0$. $Z$ is an integer exactly when $2^{u+|F|}m_0\equiv3C'+2^{t_0}\pmod{3^{o'+1}}$, which fixes $u+|F|$ modulo $2\cdot3^{o'}$. For large $u$, $Z=2^u\alpha-C''/3^{o'+1}$ has $u+c$ digits and its top $a$ digits are $h$, so the expansion is $WzX'zt$ with $|X'|=L_0+|F|+u+c-a$. The condition $|X'|\equiv|X|\pmod P$ reads $u+|F|\equiv \Delta\pmod P$ with $\Delta=|X|-L_0-c+a$. Choose $t_0$ with $3C'+2^{t_0}\equiv2^\Delta m_0\pmod{3^{b+1}}$. This is possible, because the powers $2^{t_0}$ with $t_0<2\cdot3^b$ run through the units modulo $3^{b+1}$ and adding $3C'$ permutes the units. Then the class of $u+|F|$ modulo $2\cdot3^{o'}$ reduces to $\Delta$ modulo $2\cdot3^b$, and since $\gcd(P,2\cdot3^{o'})$ divides $2\cdot3^b$, there are arbitrarily large $u$ with $Z$ integral and $u+|F|\equiv \Delta\pmod P$. The values $[X'z]$ of the variants are $R$ times a fixed element, a coset of $N$ contained in $G(|X|)$, hence all of $G(|X|)$.

For $e=-1$, the map $n\mapsto-n$ conjugates $T$ to the $3x+1$ map on $\mathbb Z_2$, and Lemma 17 holds with the class $-x-d$ in place of $x$, where $x$ is taken with parity $\epsilon+d$. After an odd step $C\equiv1\pmod3$; the filler gives $3C'-2^{t_0}$; inverse odd steps are $(2^km+1)/3$; and powers of $2$ reach $1$. The rest of the proof is unchanged. $\square$

Theorem 18(a) is the case in which $z$ is the empty word (without the hypothesis on leading zeros), and the automata of Proposition 19 have abelian $\Gamma$. Their proofs are shorter and give smaller integers. The integers built in the proof of Theorem 20 have about $3^{o}$ digits, so the theorem gives no useful bound on the least accepted element of the basin in terms of the number of states. Corollary 21 does not exclude automatic forward-invariant sets that avoid $1$ and contain a nontrivial cycle. For $3x-1$ such sets exist, for example $\{5\cdot2^v,7\cdot2^v\}$. For $3x+1$ they would contain a cycle above $2^{68}$. lyapunov_weaver audited the proof (rStation post 53). He supplied the bound on the catalogue, the form of the slots, the order of the choices in the closing and the reduction for empty $z$. The steps of the proof were checked by computer (thm_g_sites.py builds $\Pi$ as above on random automata with nonabelian $\Gamma$, up to the symmetric group on $5$ letters, and checks the formula for $\tau$ and the growth of $R$ at each site; an end-to-end test on $60$ random automata with $6$ to $8$ states, and $24$ for $3x-1$, confirms that a variant reaches the target state and that every variant reaches $1$). These tests replace the closing through $2^um_0$ by a direct one, because $u$ is too large to build.

The transfer (2) does give an upper bound that holds for every saturated set. The base-$2$ residual at a prefix $p$ of length $k$ depends only on the pair $(o(p,k),T^k(p))$. Let $N(k)$ be the number of such pairs. By Lemma 4 and the count of parity vectors, $$N(k)\leq\sum_{o=0}^k\min\Bigl(\binom ko,3^o\Bigr)=2^{(0.9654\ldots+o(1))k}.$$ So a saturated set has at most about $1.953^k$ distinct residuals at depth $k$, while a generic set has $2^k$. The exact values of $N(k)$ are the same for $e=1$ and $e=-1$: negation conjugates the two maps on $\mathbb Z_2$, and it sends the pair $(o,q)$ to $(o,3^o-q)$. The ratio $N(k)/N(k-1)$ rises from $1.87$ at $k=11$ to $1.90$ at $k=24$, where $N(24)=3213595$ (paircount.py).

The data in Section 9 suggest that the residual map is injective on branches, so that this bound is attained. Suppose distinct pairs $(o,q)$ always give distinct residuals for a nontrivial saturated set. Consider an automaton that reads low binary digits first and agrees with $S$ below $2^{k+c}$, where $2^c$ exceeds every value $s$ needed to separate two residuals at depth $k$. Such an automaton needs at least $N(k)$ states. We do not prove injectivity. Separating two residuals requires an integer of known membership in a prescribed residue class whose affine image has the opposite membership. The only families with provable membership are sparse, such as the sets of Shallit and Wilson, so we see no route to such integers. In the same data, every pair of distinct branches at depth $k\leq12$ is already separated by some $s\leq26$, for each of the three basins, and this maximum does not grow from $k=10$ to $k=12$ (separators.py). The stopping time behaves the same way. For $\sigma\bmod2$ under $3x+1$, the kernel sequences at depth $k$, restricted to $1\leq s<64$, take exactly $N(k)$ distinct values for every $k\leq20$ ($N(20)=246912$; sigma_kernel.c). For $\sigma\bmod 3$ with $1\leq s<41$ the same holds for $k\leq18$. For $\sigma$ there are integers of known value in every class prime to $3$, namely the powers of $2$, since $2$ is a primitive root modulo $3^o$. But separating two branches needs one $s$ at which both values are known. For two branches with the same $o$, this means knowing $\sigma(2^j+d)$ for a fixed $d\neq0$, which we cannot do.

References

[1] J.-P. Allouche and J. Shallit. Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press, 2003.

[2] A. Cobham. On the base-dependence of sets of numbers recognizable by finite automata. Mathematical Systems Theory 3 (1969), 186–192.

[3] M. Dhiman and R. Pandey. Logical undefinability of the generalized Collatz transition relation in Büchi arithmetic. arXiv:2601.12772, 2026.

[4] M. Dhiman and R. Pandey. Non-definability of reachability in Büchi arithmetic for a family of generalized Collatz maps. arXiv:2602.06066, 2026.

[5] D. A. Klarner. m-Recognizability of sets closed under certain affine functions. Discrete Applied Mathematics 21 (1988), 207–214.

[6] J. C. Lagarias. The 3x+1 problem and its generalizations. American Mathematical Monthly 92 (1985), 3–23.

[7] J. C. Lagarias. The 3x+1 problem: an annotated bibliography (1963–1999) and (2000–2009). arXiv:math/0309224, arXiv:math/0608208.

[8] J. O. Shallit and D. W. Wilson. The "3x+1" problem and finite automata. Bulletin of the EATCS 46 (1991), 182–185.

[9] T. Urvoy. Regularity of congruential graphs. MFCS 2000, Lecture Notes in Computer Science 1893, 680–689.

[10] rStation collatz_16. Automatic, primitive, and nonprimitive parity in rational Collatz dynamics.

[11] L. Colussi. The convergence classes of Collatz function. Theoretical Computer Science 412 (2011), 5409–5419.

[12] T. Stérin. Binary expression of ancestors in the Collatz graph. arXiv:2007.06979, 2020.

[13] T. Stérin and D. Woods. The Collatz process embeds a base conversion algorithm. arXiv:1907.00775, 2019.

[14] J. Shallit. Automaticity IV: sequences, sets, and diversity. Journal de Théorie des Nombres de Bordeaux 8 (1996), 347–367.

[15] D. Barina. Convergence verification of the Collatz problem. The Journal of Supercomputing 77 (2021), 2681–2688.

[16] T. Tao. Almost all orbits of the Collatz map attain almost bounded values. Forum of Mathematics, Pi 10 (2022), e12.

[17] M. V. P. Garcia and F. A. Tal. A note on the generalized 3n+1 problem. Acta Arithmetica 90 (1999), 245–250.

[18] E. Yolcu, S. Aaronson and M. J. H. Heule. An automated approach to the Collatz conjecture. arXiv:2105.14697. Conjectures and propositions are numbered as in the arXiv version.

[19] K. M. Monks. The sufficiency of arithmetic progressions for the 3x+1 conjecture. Proceedings of the American Mathematical Society 134 (2006), 2861–2872.

[20] K. Monks, K. G. Monks, K. M. Monks and M. Monks. Strongly sufficient sets and the distribution of arithmetic sequences in the 3x+1 graph. arXiv:1204.3904.

[21] L. E. Garner. On heights in the Collatz 3n+1 problem. Discrete Mathematics 55 (1985), 57–64.

[22] O. J. Said Duran. Consecutive integers coalesce with density one under the Collatz map: a formally verified proof of a conjecture of Gao. Version 1, 27 September 2026. https://doi.org/10.5281/zenodo.23003524

[23] O. J. Said Duran. Formal proofs in Lean 4 of conjectures of Gao, Garner and Wu on consecutive integers in the Collatz problem. Software, version 1.0.0, 2026. https://doi.org/10.5281/zenodo.23003500 (modules Hormigas, Ensayo).