Introduction
The Collatz map
T ( x ) = { ( 3 x + 1 ) / 2 , x odd , x / 2 , x even . T(x) =
\begin{cases}
(3x + 1)/2, & x\ \text{odd},\\
x/2, & x\ \text{even}.
\end{cases} T ( x ) = { ( 3 x + 1 ) /2 , x /2 , x odd , x even .
changes a positive integer by about half of its value at every step: an odd x x x goes up by ( x + 1 ) / 2 (x + 1)/2 ( x + 1 ) /2 , an even x x x goes down by x / 2 x/2 x /2 . The Collatz conjecture states that every orbit eventually reaches the cycle ( 1 , 2 ) (1, 2) ( 1 , 2 ) ; see Lagarias’s surveys and annotated bibliographies [17 , 22 , 21 , 19 , 20 ] and the monograph of Wirsching [31 ] . In this paper we keep the size of the steps and vary their direction: at some numbers we go up where the Collatz map goes down, or down where it goes up. This gives a family of maps that contains the Collatz map, maps whose orbits are expected to diverge, and maps for which the analogue of the conjecture is easy to prove. One can then ask which members are easier than the Collatz map, and whether statements can be transferred from one member to another.
We let the direction depend on the 2-adic valuation of the current number. Write every positive integer uniquely as x = 2 m k x = 2^{m}k x = 2 m k with k k k odd, and let N = { 1 , 2 , 3 , … } \mathbb{N} = \{1, 2, 3, \ldots\} N = { 1 , 2 , 3 , … } .
Definition 1.1. For S ⊆ N S \subseteq\mathbb{N} S ⊆ N let T S , T S − : N → N T_{S}, T_{S}^{-}: \mathbb{N} \to\mathbb{N} T S , T S − : N → N be
T S ( x ) = { ( 3 x + 1 ) / 2 , m = 0 , 3 x / 2 , m ∈ S , k , m ≥ 1 , m ∉ S , T S − ( x ) = { ( x + 1 ) / 2 , m = 0 , 3 x / 2 , m ∈ S , k , m ≥ 1 , m ∉ S , (1) T_{S}(x) =
\begin{cases}
(3x+1)/2, & m=0,\\
3x/2, & m \in S,\\
k, & m \ge1,\ m \notin S,
\end{cases}
\qquad
T_{S}^{-}(x) =
\begin{cases}
(x+1)/2, & m=0,\\
3x/2, & m \in S,\\
k, & m \ge1,\ m \notin S,
\end{cases} \tag*{(1)} T S ( x ) = ⎩ ⎨ ⎧ ( 3 x + 1 ) /2 , 3 x /2 , k , m = 0 , m ∈ S , m ≥ 1 , m ∈ / S , T S − ( x ) = ⎩ ⎨ ⎧ ( x + 1 ) /2 , 3 x /2 , k , m = 0 , m ∈ S , m ≥ 1 , m ∈ / S , (1)
where x = 2 m k x = 2^{m}k x = 2 m k with k k k odd.
Thus S S S is the set of exponents m ≥ 1 m \ge1 m ≥ 1 at which the map goes up, and odd numbers go up under T S T_{S} T S and down under T S − T_{S}^{-} T S − ; equivalently, the two families together are indexed by the set of all exponents m ≥ 0 m \ge0 m ≥ 0 at which the map goes up. A downward step at an even number removes all factors of 2 at once. For the Collatz map this only merges a run of halvings into one step: T ∅ T_{\varnothing} T ∅ sends an even number directly to its odd part, so its orbits are the Collatz orbits with every run of halvings compressed, and T ∅ T_{\varnothing} T ∅ has a divergent or a nontrivial periodic orbit exactly when T T T does. (Theorem 3.5 discusses the variant in which a downward step halves only once.)
For example, for S = { 1 } S = \{1\} S = { 1 } the number 26 = 2 ⋅ 13 26 = 2 \cdot13 26 = 2 ⋅ 13 has m = 1 ∈ S m = 1 \in S m = 1 ∈ S and goes up to 39 39 39 , while 680 = 2 3 ⋅ 85 680 = 2^{3} \cdot85 680 = 2 3 ⋅ 85 has m = 3 ∉ S m = 3 \notin S m = 3 ∈ / S and goes down to 85 85 85 ; under the Collatz map T ∅ T_{\varnothing} T ∅ both would go down to their odd parts 13 13 13 and 85 85 85 .
An orbit of a map f : N → N f : \mathbb{N} \to\mathbb{N} f : N → N is either eventually periodic, in which case it ends in a cycle { x , f ( x ) , … , f p − 1 ( x ) } \{x, f(x), \ldots, f^{p-1}(x)\} { x , f ( x ) , … , f p − 1 ( x )} with f p ( x ) = x f^{p}(x) = x f p ( x ) = x , or it consists of pairwise distinct numbers and then tends to infinity; in the second case we say that the orbit diverges. The analogue of the Collatz conjecture for T S T_{S} T S is the statement that no orbit of T S T_{S} T S diverges. Unlike the Collatz map, most maps T S T_{S} T S have several cycles (see Tables A.2 and 5.1); we write a cycle as a tuple that starts with its smallest element.
The Collatz map appears in the family a second time: T N − ( x ) = T ( x − 1 ) + 1 T_{\mathbb{N}}^{-}(x) = T(x-1)+1 T N − ( x ) = T ( x − 1 ) + 1 (Theorem 6.1). So the family of maps T S T_{S} T S starts at the Collatz map and its downward pull weakens as S S S grows, up to T N ( x ) = ⌈ 3 x / 2 ⌉ > x T_{\mathbb{N}}(x) = \lceil3x/2 \rceil> x T N ( x ) = ⌈ 3 x /2 ⌉ > x , whose orbits all diverge; the family of maps T S − T_{S}^{-} T S − ends at the Collatz map and its pull strengthens as S S S shrinks, down to T ∅ − T_{\varnothing}^{-} T ∅ − , whose orbits all decrease to 1 1 1 . For example,
T { 1 } : 7 , 11 , 17 , 26 , 39 , 59 , 89 , 134 , 201 , 302 , 453 , 680 , 85 , 128 , 1 , 2 , 3 , 5 , 8 , 1 , … T_{\{1\}}:\quad7,\,11,\,17,\,26,\,39,\,59,\,89,\,134,\,201,\,302,\,453,\,680,\,85,\,128,\,1,\,2,\,3,\,5,\,8,\,1,\ldots T { 1 } : 7 , 11 , 17 , 26 , 39 , 59 , 89 , 134 , 201 , 302 , 453 , 680 , 85 , 128 , 1 , 2 , 3 , 5 , 8 , 1 , …
T { 2 , 4 , 6 , … } : 7 , 11 , 17 , 26 , 13 , 20 , 30 , 15 , 23 , 35 , 53 , 80 , 120 , 15 , … T_{\{2,4,6,\ldots\}}:\quad7,\,11,\,17,\,26,\,13,\,20,\,30,\,15,\,23,\,35,\,53,\,80,\,120,\,15,\ldots T { 2 , 4 , 6 , … } : 7 , 11 , 17 , 26 , 13 , 20 , 30 , 15 , 23 , 35 , 53 , 80 , 120 , 15 , …
T { 1 , 2 , 3 } − : 15 , 8 , 12 , 18 , 27 , 14 , 21 , 11 , 6 , 9 , 5 , 3 , 2 , 3 , … T_{\{1,2,3\}}^{-}:\quad15,\,8,\,12,\,18,\,27,\,14,\,21,\,11,\,6,\,9,\,5,\,3,\,2,\,3,\ldots T { 1 , 2 , 3 } − : 15 , 8 , 12 , 18 , 27 , 14 , 21 , 11 , 6 , 9 , 5 , 3 , 2 , 3 , …
T N : 28 , 42 , 63 , 32 , 48 , 72 , 108 , 162 , 243 , 122 , 183 , 92 , … T_{\mathbb{N}}:\quad28,\,42,\,63,\,32,\,48,\,72,\,108,\,162,\,243,\,122,\,183,\,92,\ldots T N : 28 , 42 , 63 , 32 , 48 , 72 , 108 , 162 , 243 , 122 , 183 , 92 , …
The first orbit ends in the cycle ( 1 , 2 , 3 , 5 , 8 ) (1, 2, 3, 5, 8) ( 1 , 2 , 3 , 5 , 8 ) , the second in ( 15 , 23 , 35 , 53 , 80 , 120 ) (15, 23, 35, 53, 80, 120) ( 15 , 23 , 35 , 53 , 80 , 120 ) ; the third and fourth end in ( 2 , 3 ) (2, 3) ( 2 , 3 ) (the fourth is the Collatz orbit of 27 27 27 shifted by one; it takes 71 71 71 steps to first repeat). The questions that motivate this paper are: for which S S S is the analogue of the Collatz conjecture plausible, what do the orbits of the maps near the boundary look like, and can a statement be proved more easily for one map than for another, or be transferred from one map to another?
The heuristic
The following heuristic, standard for the Collatz map [8 , 23 , 13 ] , indicates which maps T S T_S T S should have only eventually periodic orbits. Consider only the odd numbers x 0 , x 1 , x 2 , … x_0, x_1, x_2, \ldots x 0 , x 1 , x 2 , … of an orbit of T S T_S T S . The step from x i x_i x i to x i + 1 x_{i+1} x i + 1 begins with x ↦ 3 x + 1 x \mapsto3x+1 x ↦ 3 x + 1 , which produces M i + 1 = v 2 ( 3 x i + 1 ) ≥ 1 M_i+1 = v_2(3x_i+1) \ge1 M i + 1 = v 2 ( 3 x i + 1 ) ≥ 1 factors 2; the map then trades some of them, say r i r_i r i , for factors 3 by steps x ↦ 3 x / 2 x \mapsto3x/2 x ↦ 3 x /2 , and removes the remaining ones. Thus
x i + 1 ≈ 3 1 + r i 2 M i + 1 x i , that is, log 2 x i + 1 − log 2 x i ≈ ( 1 + r i ) log 2 3 − ( M i + 1 ) . x_{i+1} \approx\frac{3^{1+r_i}}{2^{M_i+1}}x_i,\qquad\text{that is,}\qquad\log_2 x_{i+1}-\log_2 x_i \approx(1+r_i)\log_2 3-(M_i+1). x i + 1 ≈ 2 M i + 1 3 1 + r i x i , that is, log 2 x i + 1 − log 2 x i ≈ ( 1 + r i ) log 2 3 − ( M i + 1 ) .
For a random odd integer x x x the valuation v 2 ( 3 x + 1 ) v_2(3x+1) v 2 ( 3 x + 1 ) equals k k k with probability 2 − k 2^{-k} 2 − k , so P ( M = m ) = 2 − ( m + 1 ) \mathbb{P}(M=m)=2^{-(m+1)} P ( M = m ) = 2 − ( m + 1 ) for m ≥ 0 m\ge0 m ≥ 0 . If the M i M_i M i along an orbit behave like independent random variables with this law (Theorem 3.1 makes this precise in a 2-adic sense), then log 2 x i \log_2 x_i log 2 x i performs a random walk, and the sign of its drift, the expected number of bits gained per odd step, decides whether orbits should come down or go up. For the Collatz map r i = 0 r_i=0 r i = 0 and the drift is log 2 3 − 2 ≈ − 0.415 \log_2 3-2\approx-0.415 log 2 3 − 2 ≈ − 0.415 : each odd step multiplies by 3 and removes two factors 2 on average. For T S T_S T S the number r i r_i r i is a function of M i M_i M i determined by S S S , and the drift is ( 1 + ρ ( S ) ) log 2 3 − 2 (1+\rho(S))\log_2 3-2 ( 1 + ρ ( S )) log 2 3 − 2 , where ρ ( S ) \rho(S) ρ ( S ) is the expected value of r i r_i r i .
Results
(1) Odd-to-odd reduction and a random model (Sections 2 and 3). Between consecutive odd numbers, T S T_S T S acts as x ↦ U S ( x ) = 3 r S ( M ) Syr ( x ) x\mapsto U_S(x)=3^{r_S(M)}\operatorname{Syr}(x) x ↦ U S ( x ) = 3 r S ( M ) Syr ( x ) , where Syr ( x ) = ( 3 x + 1 ) / 2 v 2 ( 3 x + 1 ) \operatorname{Syr}(x)=(3x+1)/2^{v_2(3x+1)} Syr ( x ) = ( 3 x + 1 ) / 2 v 2 ( 3 x + 1 ) is the Syracuse map, M = v 2 ( 3 x + 1 ) − 1 M=v_2(3x+1)-1 M = v 2 ( 3 x + 1 ) − 1 , and r S ( M ) r_S(M) r S ( M ) is the number of consecutive integers M , M − 1 , … M,M-1,\ldots M , M − 1 , … lying in S S S . The valuations along a U S U_S U S -orbit are 2-adically independent and geometric, so log 2 \log_2 log 2 of an orbit behaves like a random walk with drift δ ( S ) = ( 1 + ρ ( S ) ) log 2 3 − 2 \delta(S)=(1+\rho(S))\log_2 3-2 δ ( S ) = ( 1 + ρ ( S )) log 2 3 − 2 , where ρ ( S ) = ∑ m ≥ 1 2 − ( m + 1 ) r S ( m ) \rho(S)=\sum_{m\ge1}2^{-(m+1)}r_S(m) ρ ( S ) = ∑ m ≥ 1 2 − ( m + 1 ) r S ( m ) . The model predicts that almost every orbit is eventually periodic if ρ ( S ) < θ : = log 3 ( 4 / 3 ) ≈ 0.26186 \rho(S)<\theta:=\log_3(4/3)\approx0.26186 ρ ( S ) < θ := log 3 ( 4/3 ) ≈ 0.26186 , and that almost every orbit diverges if ρ ( S ) > θ \rho(S)>\theta ρ ( S ) > θ . For S = { a , … , b } S=\{a,\ldots,b\} S = { a , … , b } the first case occurs exactly when a ≥ 3 a\ge3 a ≥ 3 , or a = 2 a=2 a = 2 and b ≤ 3 b\le3 b ≤ 3 , or a = b = 1 a=b=1 a = b = 1 (Theorem 3.3). The case ρ ( S ) = θ \rho(S)=\theta ρ ( S ) = θ never occurs, although ρ ( S ) \rho(S) ρ ( S ) comes within $2\cdot 10^{-16}o f of o f \theta ({xref}Theorem 3.4`).
(2) Rigorous density results (Section 4). We prove the analogues of the theorems of Terras, Everett and Korec on both sides of the threshold (Theorem 4.1 ), and show that for S ≠ N S\ne\mathbb{N} S = N every odd residue class modulo 2 L 2^L 2 L contains a positive rational number with a periodic orbit (Theorem 4.2 ); hence no argument that uses only residues can prove that the orbits in a residue class diverge.
(3) Numerical evidence (Section 5). For seven contracting maps T S T_S T S , including the three intervals { 1 } \{1\} { 1 } , { 2 , 3 } \{2,3\} { 2 , 3 } and { 3 , 4 , 5 , … } \{3,4,5,\ldots\} { 3 , 4 , 5 , … } with ρ = 1 / 4 \rho=1/4 ρ = 1/4 , we checked every n < 2 34 n<2^{34} n < 2 34 (every n < 16 , 681 , 795 , 584 n<16,681,795,584 n < 16 , 681 , 795 , 584 for S = { 1 } S=\{1\} S = { 1 } ): every orbit reaches one of the one to five cycles listed in Table 5.1 . Drifts and stopping-time distributions agree with the model to three to five digits, and delays, excursion exponents and basin proportions to within a few percent. Three expanding maps behave as predicted as well.
Table 5.1. Cycles of the contracting maps, named as in Section A (C U + ( n ) C_{U}^{+}(n) C U + ( n ) is the cycle of T U T_{U} T U whose smallest element is n n n ): length in steps, number of odd steps, and the share (in percent) of starting values that end in the cycle, among all n ∈ [ 2 25 , 2 26 ) n \in[2^{25},2^{26}) n ∈ [ 2 25 , 2 26 ) and among 400 random odd 4096-bit numbers. No other cycle has smallest element below 2 34 2^{34} 2 34 (below 1.668 ⋅ 10 10 1.668 \cdot10^{10} 1.668 ⋅ 1 0 10 for S = { 1 } S=\{1\} S = { 1 } ).
(4) Going down at odd numbers (Section 6). The drift of T S T_S T S is δ ( S ) − log 2 3 = ρ ( S ) log 2 3 − 2 ≤ log 2 3 − 2 \delta(S)-\log_2 3=\rho(S)\log_2 3-2\le\log_2 3-2 δ ( S ) − log 2 3 = ρ ( S ) log 2 3 − 2 ≤ log 2 3 − 2 , so every T S T_S T S is contracting, with equality only for the Collatz map T N T_{\mathbb{N}} T N . If S S S contains no set [ c , ∞ ) [c,\infty) [ c , ∞ ) and ( 3 / 2 ) L < 2 a (3/2)^L<2^a ( 3/2 ) L < 2 a for every maximal run { a , … , a + L − 1 } \{a,\ldots,a+L-1\} { a , … , a + L − 1 } of consecutive elements of S S S , then no odd step of T S T_S T S increases a number, and every orbit reaches the fixed point 1 or the cycle ( 2 , 3 ) (2,3) ( 2 , 3 ) (Theorem 6.3); this covers, for instance, every S S S without two consecutive elements, and the primes. For every other S S S , a negative rational number, viewed as a 2-adic integer, repeats an increasing odd step forever, and residue arguments cannot prove that all orbits descend. The first members beyond the criterion, such as S = { 1 , 2 } S=\{1,2\} S = { 1 , 2 } , have a much stronger downward pull than the Collatz map; for seven of them we checked all n < 2 34 n<2^{34} n < 2 34 . There is also a partial transfer to the Collatz map (Theorem 6.2).
(5) Branching maps (Section 7). For a family S \mathcal{S} S of sets we let a branch apply any T S T_S T S , S ∈ S S\in\mathcal{S} S ∈ S , at each step, and call S \mathcal{S} S bounded if every n n n reaches only finitely many numbers. Every family is equivalent to a pair S − ⊆ S + S^{-}\subseteq S^{+} S − ⊆ S + (Theorem 7.2); reachable sets grow when S − S^{-} S − shrinks or S + S^{+} S + grows (Theorem 7.4), so boundedness of a family implies eventual periodicity for each member, and boundedness of { ∅ , { 3 } } \{\varnothing,\{3\}\} { ∅ , { 3 }} , for example, would imply that no Collatz orbit diverges. A branching-random-walk heuristic (Section 7.3) predicts that { ∅ , { 3 } } \{\varnothing,\{3\}\} { ∅ , { 3 }} is bounded while { ∅ , { 1 } } \{\varnothing,\{1\}\} { ∅ , { 1 }} and { ∅ , { 2 } } \{\varnothing,\{2\}\} { ∅ , { 2 }} are not. For { ∅ , { 1 } } \{\varnothing,\{1\}\} { ∅ , { 1 }} we prove that a rule depending on x m o d 32 x\bmod32 x mod 32 has positive drift 10 17 log 2 9 8 \frac{10}{17}\log_{2}\frac{9}{8} 17 10 log 2 8 9 almost surely (Theorem 7.7), so that for almost all n n n the reachable set contains numbers larger than n ( 2 / 3 ) log 2 3 − ε n^{(2/3)\log_{2}3-\varepsilon} n ( 2/3 ) l o g 2 3 − ε for every ε > 0 \varepsilon>0 ε > 0 , where ( 2 / 3 ) log 2 3 = 1.0566 … (2/3)\log_{2}3=1.0566\ldots ( 2/3 ) log 2 3 = 1.0566 … (Theorem 7.10); on the other hand, every odd residue class modulo 2 10 2^{10} 2 10 contains a positive rational number whose reachable set is finite, which rules out a proof of unboundedness based only on residues modulo 2 10 2^{10} 2 10 (Theorem 7.11).
(6) Cycles (Section A). A cycle occurs exactly for the sets S S S in an interval determined by the exponents at which it goes up and down, so it can be named by the map of this interval closest to the Collatz map and by its smallest element. A search over all S S S at once finds 53 cycles of maps T S T_S T S with smallest element below 10 5 10^{5} 1 0 5 (and largest below 2 120 2^{120} 2 120 ), and shows that no map T S − T_S^{-} T S − has cycles other than the shifted Collatz cycles (1) and (2, 3) with smallest element below 10 6 10^{6} 1 0 6 .
(7) Unified maps (Section 8). The maps T S o , S e T_{S_o,S_e} T S o , S e go up at an odd x x x if v 2 ( x + 1 ) ∈ S o v_2(x+1)\in S_o v 2 ( x + 1 ) ∈ S o and at an even x x x if v 2 ( x ) ∈ S e v_2(x)\in S_e v 2 ( x ) ∈ S e , so that T S = T N , S T_S=T_{\mathbb{N},S} T S = T N , S and T S − = T ∅ , S T_S^{-}=T_{\varnothing,S} T S − = T ∅ , S . Their orbits split into blocks, each made of steps up at odd numbers, at most one step down at an odd number, and the steps at even numbers that follow, and the random model extends to blocks. If 1 ∉ S o 1\notin S_o 1 ∈ / S o , that is, if the odd x ≡ 1 ( m o d 4 ) x\equiv1\pmod4 x ≡ 1 ( mod 4 ) go down, no block multiplies x + 1 x+1 x + 1 by more than the corresponding block of the Collatz map T N − T_{\mathbb{N}}^{-} T N − , and infinitely many such maps, among them T [ 2 , ∞ ) , S T_{[2,\infty),S} T [ 2 , ∞ ) , S for every S S S , have exactly the block map of T N − T_{\mathbb{N}}^{-} T N − (Theorem 8.5); a census over all these maps finds only the cycles (1), (2, 3) and (3, 5) with smallest element below 10 9 10^{9} 1 0 9 . If 1 ∈ S o 1\in S_o 1 ∈ S o , the census finds thousands of cycles, most of them in maps close to the threshold, but single maps have about as many cycles as maps T S T_S T S with the same drift. So the maps between the two families do not seem to behave in a new way.
Organization
Section 2 reduces T S T_S T S to a map between consecutive odd numbers and extends it to rational numbers with odd denominator and to 2-adic integers. Section 3 develops the random model and the threshold θ \theta θ , Section 4 proves the density results and the obstruction coming from rational cycles, and Section 5 compares the model with computations. Section 6 treats the maps T S − T_S^{-} T S − , Section 7 the branching maps, Section 8 the unified maps, which contain both families, and Section 9 collects conjectures and open problems. Section A explains how cycles are named and lists the cycles found by a search over all maps at once. Sections 5 to 7 can be read largely independently of each other; they use Sections 2 and 3 and the method of proof of Theorem 4.1. Section 8 also uses Sections A and 6.
For the Collatz map itself, Terras [30 ] and Everett [9 ] proved that almost every n n n (in the sense of natural density) has an orbit that falls below n n n ; Korec [15 ] showed that almost every orbit falls below n c n^c n c for every c > log 3 / log 4 c > \log3/\log4 c > log 3/ log 4 , and Tao [29 ] that almost all orbits (in the sense of logarithmic density) attain almost bounded values. The conjecture has been verified for all n < 2 71 n < 2^{71} n < 2 71 [3 ] . The random-walk heuristic described above appears in Crandall’s paper [8 ] ; refined stochastic models are due to Lagarias and Weiss [23 ] and are surveyed in [13 ] .
Generalized Collatz maps that act affinely on the residue classes modulo a fixed integer were introduced by Matthews and Watts [26 ] and studied with Markov-chain methods by Leigh [24 ] and Matthews [25 ] ; for ( d , g , h ) (d,g,h) ( d , g , h ) -maps Kontorovich and Sinai [14 ] proved that trajectories behave like random walks in a precise sense. Conway [7 ] and Kurtz and Simon [16 ] showed that natural questions about such maps are undecidable. The maps T S T_S T S and T S ‾ T_{\overline{S}} T S are of a different kind: the rule depends on the 2-adic valuation m m m of x x x rather than on x x x modulo a fixed number, and the step x ↦ k x \mapsto k x ↦ k removes all factors of 2 at once. Stochastic models of the 3 x + 1 3x+1 3 x + 1 problem are surveyed in [13 ] ; the ones we use for single maps are the basic random-walk models of [8 , 23 ] . Rational numbers with odd denominator, which appear in Theorems 4.2 and 7.11, were used for the 3 x + 1 3x+1 3 x + 1 map by Lagarias [18 ] , who studied its rational cycles. A two-player game in which the moves are 3 n + 1 3n+1 3 n + 1 or 3 n − 1 3n-1 3 n − 1 followed by halving was analysed by Althöfer, Hartisch and Zipproth [1 ] , and Althöfer and Zipproth [2 ] proved divergence of all orbits for a Collatz-type recursion with an irrational multiplier. We have not found the maps T S T_S T S and T S ‾ T_{\overline{S}} T S or the branching maps of § 9 in the literature surveyed in [19 , 20 , 22 ] , and the orbits above are not in the OEIS.
Notation and conventions
For a nonzero integer x x x , v 2 ( x ) v_2(x) v 2 ( x ) is the exponent of the largest power of 2 that divides x x x , and v 2 ( p / q ) = v 2 ( p ) − v 2 ( q ) v_2(p/q)=v_2(p)-v_2(q) v 2 ( p / q ) = v 2 ( p ) − v 2 ( q ) for rational numbers. Z 2 \mathbb{Z}_2 Z 2 is the ring of 2-adic integers. Readers not familiar with it may think of an element of Z 2 \mathbb{Z}_2 Z 2 as an infinite binary expansion ∑ i ≥ 0 a i 2 i \sum_{i\geq0}a_i2^i ∑ i ≥ 0 a i 2 i , a i ∈ { 0 , 1 } a_i \in\{0,1\} a i ∈ { 0 , 1 } , with addition and multiplication carried out with carries as for integers. The integers are contained in Z 2 \mathbb{Z}_2 Z 2 (for instance − 1 = 1 + 2 + 4 + ⋯ -1=1+2+4+\cdots − 1 = 1 + 2 + 4 + ⋯ ), and so are the rational numbers with odd denominator (for instance − 1 / 3 = 1 + 4 + 16 + ⋯ -1/3=1+4+16+\cdots − 1/3 = 1 + 4 + 16 + ⋯ , since 3 ( 1 + 4 + 16 + ⋯ ) = − 1 3(1+4+16+\cdots)=-1 3 ( 1 + 4 + 16 + ⋯ ) = − 1 ). Two elements of Z 2 \mathbb{Z}_2 Z 2 are congruent modulo 2 k 2^k 2 k if their first k k k binary digits agree, and a residue class modulo 2 k 2^k 2 k is the set of elements with prescribed first k k k digits. Z 2 × = 1 + 2 Z 2 \mathbb{Z}_2^\times=1+2\mathbb{Z}_2 Z 2 × = 1 + 2 Z 2 is the set of odd elements, those with a 0 = 1 a_0=1 a 0 = 1 ; they are the units of Z 2 \mathbb{Z}_2 Z 2 . The Haar probability measure μ \mu μ on Z 2 × \mathbb{Z}_2^\times Z 2 × is the law of a random odd 2-adic integer whose digits a 1 , a 2 , … a_1,a_2,\ldots a 1 , a 2 , … are independent fair coin flips, so that every residue class modulo 2 k + 1 2^{k+1} 2 k + 1 inside Z 2 × \mathbb{Z}_2^\times Z 2 × has measure 2 − k 2^{-k} 2 − k . Statements that hold for μ \mu μ -almost every x x x are the 2-adic counterpart of statements about a proportion tending to 1 of the odd integers in long intervals; the passage from one to the other is made in the proof of Theorem 4.1 .
A set A A A of odd positive integers has (natural) density d d d if # { n ∈ A : n ≤ N } / # { n ≤ N : n odd } → d \#\{n \in A:n\leq N\}/\#\{n\leq N:n\text{ odd}\}\to d # { n ∈ A : n ≤ N } /# { n ≤ N : n odd } → d as N → ∞ N\to\infty N → ∞ ; densities are taken among odd integers unless stated otherwise, and almost all n n n means all n n n outside a set of density zero. For a ≤ b a\leq b a ≤ b we write [ a , b ] = { a , a + 1 , … , b } [a,b]=\{a,a+1,\ldots,b\} [ a , b ] = { a , a + 1 , … , b } and [ a , ∞ ) = { a , a + 1 , … } [a,\infty)=\{a,a+1,\ldots\} [ a , ∞ ) = { a , a + 1 , … } ; 2 N 2\mathbb{N} 2 N and 2 N − 1 2\mathbb{N}-1 2 N − 1 are the even and the odd positive integers.
The maps T S T_S T S
Sections 2 to 5 are about the maps T S T_S T S ; the maps T S ‾ T_{\overline{S}} T S are treated in § 8 , where most of the arguments carry over with small changes.
The odd-to-odd map
For odd x x x (an odd integer, or more generally an element of Z 2 × \mathbb{Z}_2^\times Z 2 × other than − 1 / 3 -1/3 − 1/3 ) put
M ( x ) = v 2 ( 3 x + 1 ) − 1 ≥ 0 , Syr ( x ) = 3 x + 1 2 M ( x ) + 1 , M(x)=v_2(3x+1)-1\ge0,\qquad\operatorname{Syr}(x)=\frac{3x+1}{2^{M(x)+1}}, M ( x ) = v 2 ( 3 x + 1 ) − 1 ≥ 0 , Syr ( x ) = 2 M ( x ) + 1 3 x + 1 ,
so that Syr \operatorname{Syr} Syr is the Syracuse map and ( 3 x + 1 ) / 2 = 2 M ( x ) Syr ( x ) (3x+1)/2=2^{M(x)}\operatorname{Syr}(x) ( 3 x + 1 ) /2 = 2 M ( x ) Syr ( x ) . For S ⊆ N S\subseteq\mathbb{N} S ⊆ N and M ≥ 0 M\ge0 M ≥ 0 let
r S ( M ) = max { j ∈ { 0 , … , M } : M , M − 1 , … , M − j + 1 ∈ S } , (2) r_S(M)=\max\{j\in\{0,\ldots,M\}:M,M-1,\ldots,M-j+1\in S\}, \tag*{(2)} r S ( M ) = max { j ∈ { 0 , … , M } : M , M − 1 , … , M − j + 1 ∈ S } , (2)
the length of the run of consecutive elements of S S S that ends at M M M ; equivalently r S ( 0 ) = 0 r_S(0)=0 r S ( 0 ) = 0 , and r S ( M ) = r S ( M − 1 ) + 1 r_S(M)=r_S(M-1)+1 r S ( M ) = r S ( M − 1 ) + 1 if M ∈ S M\in S M ∈ S , r S ( M ) = 0 r_S(M)=0 r S ( M ) = 0 if M ∉ S M\notin S M ∈ / S . Define
U S ( x ) = 3 r S ( M ( x ) ) Syr ( x ) = 3 r S ( M ) ( 3 x + 1 ) 2 M + 1 . (3) U_S(x)=3^{r_S(M(x))}\operatorname{Syr}(x)=\frac{3^{r_S(M)}(3x+1)}{2^{M+1}}. \tag*{(3)} U S ( x ) = 3 r S ( M ( x )) Syr ( x ) = 2 M + 1 3 r S ( M ) ( 3 x + 1 ) . (3)
For example, r { 2 , 3 } ( m ) = 0 , 1 , 2 , 0 , 0 , … r_{\{2,3\}}(m)=0,1,2,0,0,\ldots r { 2 , 3 } ( m ) = 0 , 1 , 2 , 0 , 0 , … for m = 1 , 2 , 3 , 4 , 5 , … m=1,2,3,4,5,\ldots m = 1 , 2 , 3 , 4 , 5 , … ; r 2 N ( m ) r_{2\mathbb{N}}(m) r 2 N ( m ) is 1 for even and 0 for odd m m m ; and r N ( m ) = m r_{\mathbb{N}}(m)=m r N ( m ) = m . The next lemma shows that U S U_S U S maps each odd number of a T S T_S T S -orbit to the next one. After the step x ↦ ( 3 x + 1 ) / 2 x\mapsto(3x+1)/2 x ↦ ( 3 x + 1 ) /2 , the map T S T_S T S trades a factor 2 for a factor 3 as long as the current exponent of 2 lies in S S S , and at the first exponent outside S S S it removes all remaining factors 2; so only the run of consecutive elements of S S S that ends at M M M matters.
Lemma 2.1. Let x x x be odd, M = M ( x ) M=M(x) M = M ( x ) and r = r S ( M ) r=r_S(M) r = r S ( M ) . The T S T_S T S -orbit of x x x is
x , 3 x + 1 2 , 3 2 ⋅ 3 x + 1 2 , … , ( 3 2 ) r 3 x + 1 2 , x,\ \frac{3x+1}{2},\ \frac{3}{2}\cdot\frac{3x+1}{2},\ \ldots,\ \left(\frac{3}{2}\right)^r\frac{3x+1}{2}, x , 2 3 x + 1 , 2 3 ⋅ 2 3 x + 1 , … , ( 2 3 ) r 2 3 x + 1 , and then U S ( x ) U_S(x) U S ( x ) if r < M r<M r < M , while for r = M r=M r = M the last displayed term is already U S ( x ) U_S(x) U S ( x ) . Thus T S T_S T S reaches the odd number U S ( x ) U_S(x) U S ( x ) after exactly
ℓ S ( M ) = 1 + r + [ r < M ] \ell_S(M)=1+r+[r<M] ℓ S ( M ) = 1 + r + [ r < M ] steps, and all intermediate terms are even and larger than x x x . Similarly, an even number 2 m k 2^m k 2 m k (k k k odd) reaches the odd number 3 r S ( m ) k 3^{r_S(m)}k 3 r S ( m ) k after r S ( m ) + [ r S ( m ) < m ] r_S(m)+[r_S(m)<m] r S ( m ) + [ r S ( m ) < m ] steps.
Proof. T S ( x ) = ( 3 x + 1 ) / 2 = 2 M Syr ( x ) T_S(x)=(3x+1)/2=2^M\operatorname{Syr}(x) T S ( x ) = ( 3 x + 1 ) /2 = 2 M Syr ( x ) . A number 3 i 2 e Syr ( x ) 3^i2^e\operatorname{Syr}(x) 3 i 2 e Syr ( x ) with e ≥ 1 e\ge1 e ≥ 1 is multiplied by 3 / 2 3/2 3/2 if e ∈ S e\in S e ∈ S and replaced by its odd part 3 i Syr ( x ) 3^i\operatorname{Syr}(x) 3 i Syr ( x ) otherwise. Starting from e = M e=M e = M , the exponent decreases by one at each multiplication, and by (2.1) exactly r r r multiplications occur before the exponent reaches 0 (if r = M r=M r = M ) or an exponent M − r ∉ S M-r\notin S M − r ∈ / S (if r < M r<M r < M ), which is followed by one division step. The same argument applies to 2 m k 2^m k 2 m k .
For instance, let S = { 1 } S=\{1\} S = { 1 } . For x = 17 x=17 x = 17 we have 3 x + 1 = 52 = 2 2 ⋅ 13 3x+1=52=2^2\cdot13 3 x + 1 = 52 = 2 2 ⋅ 13 , so M = 1 M=1 M = 1 , Syr ( 17 ) = 13 \operatorname{Syr}(17)=13 Syr ( 17 ) = 13 and r = r S ( 1 ) = 1 = M r=r_S(1)=1=M r = r S ( 1 ) = 1 = M : the orbit is 17 , 26 , 39 17,26,39 17 , 26 , 39 , and U S ( 17 ) = 39 U_S(17)=39 U S ( 17 ) = 39 is reached after ℓ S ( 1 ) = 2 \ell_S(1)=2 ℓ S ( 1 ) = 2 steps. For x = 453 x=453 x = 453 we have 3 x + 1 = 2 4 ⋅ 85 3x+1=2^4\cdot85 3 x + 1 = 2 4 ⋅ 85 , so M = 3 M=3 M = 3 and r S ( 3 ) = 0 r_S(3)=0 r S ( 3 ) = 0 : the orbit is 453 , 680 , 85 453,680,85 453 , 680 , 85 , and U S ( 453 ) = Syr ( 453 ) = 85 U_S(453)=\operatorname{Syr}(453)=85 U S ( 453 ) = Syr ( 453 ) = 85 is again reached after ℓ S ( 3 ) = 2 \ell_S(3)=2 ℓ S ( 3 ) = 2 steps. Both pieces occur in the first example orbit of Section 1.
Consequently the T S T_S T S -orbit of any n n n is eventually periodic if and only if the U S U_S U S -orbit of the first odd number in it is, and cycles of T S T_S T S correspond to cycles of U S U_S U S . For S = ∅ S=\varnothing S = ∅ we have U ∅ = Syr U_\varnothing=\operatorname{Syr} U ∅ = Syr , and for S = N S=\mathbb{N} S = N , U N ( x ) = 3 M Syr ( x ) U_{\mathbb{N}}(x)=3^M\operatorname{Syr}(x) U N ( x ) = 3 M Syr ( x ) .
Lemma 2.2 (Monotonicity). If S ⊆ S ′ S\subseteq S' S ⊆ S ′ then r S ≤ r S ′ r_S\le r_{S'} r S ≤ r S ′ , U S ≤ U S ′ U_S\le U_{S'} U S ≤ U S ′ and T S ≤ T S ′ T_S\le T_{S'} T S ≤ T S ′ pointwise.
Proof. Immediate from (2.1), (2.2) and (1.1).
The maps T S T_S T S are not monotone in x x x (for 3 ∉ S 3\notin S 3 ∈ / S , for instance, 7 < 8 7<8 7 < 8 but T S ( 7 ) = 11 > 1 = T S ( 8 ) T_S(7)=11>1=T_S(8) T S ( 7 ) = 11 > 1 = T S ( 8 ) ). So the pointwise inequality T S ≤ T S ′ T_S\le T_{S'} T S ≤ T S ′ does not imply T S t ≤ T S ′ t T_S^t\le T_{S'}^t T S t ≤ T S ′ t , and Theorem 2.2 does not compare orbits; the branching maps of Section 7 are designed to make such comparisons.
Rationals and 2-adic integers
Extending the maps beyond the positive integers serves two purposes. The 2-adic integers carry a natural probability measure, under which the valuations along an orbit become independent random variables (Theorem 3.1). The rational numbers with odd denominator, on the other hand, are 2-adic integers that are not integers: they share all residue information with integers, but their orbits can behave differently, and they show which statements cannot be proved from residues alone.
The formulas (1.1) and (2.2) make sense for every positive rational number with odd denominator: write x = 2 m k x = 2^m k x = 2 m k where k k k has odd numerator and odd denominator. They also define U S U_S U S on Z 2 × ∖ { − 1 / 3 } \mathbb{Z}_2^\times\setminus\{-1/3\} Z 2 × ∖ { − 1/3 } . Every orbit of positive rationals with odd denominator stays in this set, and for odd x x x the identity
U S ( x ) x = 3 1 + r S ( M ) 2 M + 1 ( 1 + 1 3 x ) (4) \frac{U_S(x)}{x} = \frac{3^{1+r_S(M)}}{2^{M+1}}\left(1+\frac{1}{3x}\right) \tag*{(4)} x U S ( x ) = 2 M + 1 3 1 + r S ( M ) ( 1 + 3 x 1 ) (4)
holds for every positive x x x with odd denominator. We use these extensions in Theorems 4.2 and 7.11.
The simplest rational cycles are the following. If m ∉ S m \notin S m ∈ / S , then y = 1 / ( 2 m + 1 − 3 ) y = 1/(2^{m+1}-3) y = 1/ ( 2 m + 1 − 3 ) satisfies 3 y + 1 = 2 m + 1 y 3y+1 = 2^{m+1}y 3 y + 1 = 2 m + 1 y , so T S ( y ) = 2 m y T_S(y) = 2^m y T S ( y ) = 2 m y and T S ( 2 m y ) = y T_S(2^m y) = y T S ( 2 m y ) = y : the pair ( y , 2 m y ) (y,2^m y) ( y , 2 m y ) is a cycle of T S T_S T S . For m = 1 m=1 m = 1 it is the cycle ( 1 , 2 ) (1,2) ( 1 , 2 ) of the Collatz map, for m = 2 m=2 m = 2 the cycle ( 1 / 5 , 4 / 5 ) (1/5,4/5) ( 1/5 , 4/5 ) , and for m = 3 m=3 m = 3 the cycle ( 1 / 13 , 8 / 13 ) (1/13,8/13) ( 1/13 , 8/13 ) .
The random model
The following lemma is the source of all randomness in this paper.
Lemma 3.1 (Independence of valuations). Let x ∈ Z 2 × x \in\mathbb{Z}_2^\times x ∈ Z 2 × be distributed according to μ \mu μ , and let x 0 = x x_0=x x 0 = x , x i + 1 = U S ( x i ) x_{i+1}=U_S(x_i) x i + 1 = U S ( x i ) and M i = M ( x i ) M_i=M(x_i) M i = M ( x i ) (these are defined for all x x x outside a countable set). Then M 0 , M 1 , … M_0,M_1,\ldots M 0 , M 1 , … are independent, and P ( M i = m ) = 2 − ( m + 1 ) \mathbb{P}(M_i=m)=2^{-(m+1)} P ( M i = m ) = 2 − ( m + 1 ) for m ≥ 0 m\ge0 m ≥ 0 . Moreover, for every m 0 , … , m j − 1 ≥ 0 m_0,\ldots,m_{j-1}\ge0 m 0 , … , m j − 1 ≥ 0 the set of x x x with M i = m i M_i=m_i M i = m i for i < j i<j i < j is a single residue class modulo 2 W + 1 2^{W+1} 2 W + 1 , where W = ∑ i < j ( m i + 1 ) W=\sum_{i<j}(m_i+1) W = ∑ i < j ( m i + 1 ) , and U S j U_S^j U S j maps it affinely onto Z 2 × \mathbb{Z}_2^\times Z 2 × .
Proof. For m ≥ 0 m\ge0 m ≥ 0 let D m = { x ∈ Z 2 × : M ( x ) = m } D_m=\{x\in\mathbb{Z}_2^\times:M(x)=m\} D m = { x ∈ Z 2 × : M ( x ) = m } . Since 3 is a unit, D m = { x : 3 x + 1 ≡ 2 m + 1 ( m o d 2 m + 2 ) } D_m=\{x:3x+1\equiv2^{m+1}\pmod{2^{m+2}}\} D m = { x : 3 x + 1 ≡ 2 m + 1 ( mod 2 m + 2 )} is a single residue class a m + 2 m + 2 Z 2 a_m+2^{m+2}\mathbb{Z}_2 a m + 2 m + 2 Z 2 modulo 2 m + 2 2^{m+2} 2 m + 2 , so μ ( D m ) = 2 − ( m + 1 ) \mu(D_m)=2^{-(m+1)} μ ( D m ) = 2 − ( m + 1 ) . With r = r S ( m ) r=r_S(m) r = r S ( m ) we have
U S ( a m + 2 m + 2 z ) = 3 r 3 a m + 1 2 m + 1 + 2 ⋅ 3 r + 1 z ( z ∈ Z 2 ) , U_S(a_m+2^{m+2}z)=3^r\frac{3a_m+1}{2^{m+1}}+2\cdot3^{r+1}z \qquad(z\in\mathbb{Z}_2), U S ( a m + 2 m + 2 z ) = 3 r 2 m + 1 3 a m + 1 + 2 ⋅ 3 r + 1 z ( z ∈ Z 2 ) ,
and ( 3 a m + 1 ) / 2 m + 1 (3a_m+1)/2^{m+1} ( 3 a m + 1 ) / 2 m + 1 is odd. Hence U S U_S U S maps D m D_m D m bijectively and affinely onto Z 2 × \mathbb{Z}_2^\times Z 2 × , and it maps the residue class modulo 2 m + 2 + k 2^{m+2+k} 2 m + 2 + k of a m + 2 m + 2 z a_m+2^{m+2}z a m + 2 m + 2 z onto the residue class modulo 2 k + 1 2^{k+1} 2 k + 1 of its image; so μ ( U S ( E ) ) = 2 m + 1 μ ( E ) \mu(U_S(E))=2^{m+1}\mu(E) μ ( U S ( E )) = 2 m + 1 μ ( E ) for measurable E ⊆ D m E\subseteq D_m E ⊆ D m .
We prove the remaining assertions by induction on j j j , the case j = 0 j=0 j = 0 being trivial. The set E E E of x x x with M i ( x ) = m i M_i(x)=m_i M i ( x ) = m i for i < j i<j i < j is D m 0 ∩ U S − 1 ( E ′ ) D_{m_0}\cap U_S^{-1}(E') D m 0 ∩ U S − 1 ( E ′ ) , where E ′ E' E ′ is the set of y y y with M i ( y ) = m i + 1 M_i(y)=m_{i+1} M i ( y ) = m i + 1 for i < j − 1 i<j-1 i < j − 1 . By the induction hypothesis, E ′ E' E ′ is a residue class modulo 2 W ′ + 1 2^{W'+1} 2 W ′ + 1 , W ′ = ∑ 1 ≤ i < j ( m i + 1 ) W'=\sum_{1\le i<j}(m_i+1) W ′ = ∑ 1 ≤ i < j ( m i + 1 ) , which U S j − 1 U_S^{j-1} U S j − 1 maps affinely onto Z 2 × \mathbb{Z}_2^\times Z 2 × . Its preimage under the affine bijection U S : D m 0 → Z 2 × U_S:D_{m_0}\to\mathbb{Z}_2^\times U S : D m 0 → Z 2 × is a residue class modulo 2 W ′ + 1 + m 0 + 1 = 2 W + 1 2^{W'+1+m_0+1}=2^{W+1} 2 W ′ + 1 + m 0 + 1 = 2 W + 1 , which U S j U_S^j U S j maps affinely onto Z 2 × \mathbb{Z}_2^\times Z 2 × , and its measure is 2 − W = ∏ i < j 2 − ( m i + 1 ) 2^{-W}=\prod_{i<j}2^{-(m_i+1)} 2 − W = ∏ i < j 2 − ( m i + 1 ) . Since this probability is a product of the probabilities 2 − ( m i + 1 ) 2^{-(m_i+1)} 2 − ( m i + 1 ) , the M i M_i M i are independent with the stated law. □ \square □
In terms of binary digits, Theorem 3.1 says the following. If the digits of x x x are independent fair coin flips, then so are the digits of U S ( x ) U_S(x) U S ( x ) , and the valuations read off consecutive disjoint blocks of digits of x x x : M 0 M_0 M 0 is determined by the first M 0 + 2 M_0+2 M 0 + 2 digits, M 1 M_1 M 1 by the next M 1 + 1 M_1+1 M 1 + 1 digits, and so on.
The law of the valuations does not depend on S S S , because the extra factor 3 r 3^r 3 r is a 2-adic unit. Theorem 3.1 is the 2-adic form of Terras’s observation [30 ] that the parity sequence of the first j j j steps of T T T is determined by, and uniformly distributed with, n m o d 2 j n \bmod2^j n mod 2 j . By (4) , for a positive odd integer x x x ,
log 2 U S ( x ) − log 2 x = X S ( M ) + log 2 ( 1 + 1 3 x ) , X S ( M ) = ( 1 + r S ( M ) ) log 2 3 − ( M + 1 ) . (5) \log_2 U_S(x) - \log_2 x = X_S(M) + \log_2\left(1 + \frac{1}{3x}\right), \qquad X_S(M) = (1+r_S(M))\log_2 3 - (M+1). \tag*{(5)} log 2 U S ( x ) − log 2 x = X S ( M ) + log 2 ( 1 + 3 x 1 ) , X S ( M ) = ( 1 + r S ( M )) log 2 3 − ( M + 1 ) . (5)
The random model replaces the valuations along an integer orbit by an i.i.d. sequence M i M_i M i with P ( M i = m ) = 2 − ( m + 1 ) \mathbb{P}(M_i=m)=2^{-(m+1)} P ( M i = m ) = 2 − ( m + 1 ) and ignores the small correction term; then log 2 x t − log 2 x 0 \log_2 x_t-\log_2 x_0 log 2 x t − log 2 x 0 becomes the random walk W t = ∑ i < t X S ( M i ) W_t=\sum_{i<t}X_S(M_i) W t = ∑ i < t X S ( M i ) . Here log 2 \log_2 log 2 measures size in bits: X S ( M ) X_S(M) X S ( M ) is the number of bits gained (or lost, if it is negative) in one odd step, up to the correction term, which is smaller than 1 / ( 3 x ln 2 ) 1/(3x\ln2) 1/ ( 3 x ln 2 ) .
The random model is a heuristic. For an integer x x x all valuations along the orbit are determined by x x x , and Theorem 3.1 shows only that, for a random odd integer from a long interval, the first j j j valuations are distributed like independent geometric variables as long as ∑ i < j ( M i + 1 ) \sum_{i<j}(M_i+1) ∑ i < j ( M i + 1 ) is smaller than the number of binary digits of the integers in question. The rigorous results of § 6 use the model only in this range; the predictions of § 5.2 use it for whole orbits.
Drift and threshold
Since E ( M + 1 ) = 2 \mathbb{E}(M+1)=2 E ( M + 1 ) = 2 , the drift of the model is
δ ( S ) = E X S ( M ) = ( 1 + ρ ( S ) ) log 2 3 − 2 , ρ ( S ) = E r S ( M ) = ∑ m ≥ 1 r S ( m ) 2 m + 1 . (6) \delta(S)=\mathbb{E}X_S(M)=(1+\rho(S))\log_2 3-2,\qquad\rho(S)=\mathbb{E}r_S(M)=\sum_{m\geq1}\frac{r_S(m)}{2^{m+1}}. \tag*{(6)} δ ( S ) = E X S ( M ) = ( 1 + ρ ( S )) log 2 3 − 2 , ρ ( S ) = E r S ( M ) = m ≥ 1 ∑ 2 m + 1 r S ( m ) . (6)
We call S S S contracting if δ ( S ) < 0 \delta(S)<0 δ ( S ) < 0 and expanding if δ ( S ) > 0 \delta(S)>0 δ ( S ) > 0 . In words, δ ( S ) \delta(S) δ ( S ) is the expected number of bits gained per odd step and ρ ( S ) \rho(S) ρ ( S ) the expected number of extra factors 3 per odd step. For instance, for S = { 1 } S=\{1\} S = { 1 } we have r S ( M ) = 1 r_S(M)=1 r S ( M ) = 1 if M = 1 M=1 M = 1 , which has probability 1 / 4 1/4 1/4 , and r S ( M ) = 0 r_S(M)=0 r S ( M ) = 0 otherwise; so ρ ( { 1 } ) = 1 / 4 \rho(\{1\})=1/4 ρ ({ 1 }) = 1/4 and δ ( { 1 } ) = 5 4 log 2 3 − 2 ≈ − 0.0188 \delta(\{1\})=\frac{5}{4}\log_2 3-2\approx-0.0188 δ ({ 1 }) = 4 5 log 2 3 − 2 ≈ − 0.0188 .
Proposition 3.2. (a) S S S is contracting if and only if ρ ( S ) < θ \rho(S)<\theta ρ ( S ) < θ , where θ = 2 log 2 3 − 1 = log 3 4 3 = 0.261859 … \theta=\frac{2}{\log_2 3}-1=\log_3\frac{4}{3}=0.261859\ldots θ = l o g 2 3 2 − 1 = log 3 3 4 = 0.261859 …
(b) 0 = ρ ( ∅ ) ≤ ρ ( S ) ≤ ρ ( N ) = 1 0=\rho(\varnothing)\leq\rho(S)\leq\rho(\mathbb{N})=1 0 = ρ ( ∅ ) ≤ ρ ( S ) ≤ ρ ( N ) = 1 , and ρ \rho ρ is monotone: S ⊆ S ′ S\subseteq S' S ⊆ S ′ implies ρ ( S ) ≤ ρ ( S ′ ) \rho(S)\leq\rho(S') ρ ( S ) ≤ ρ ( S ′ ) .
(c) θ \theta θ is irrational. If S S S is eventually periodic, then ρ ( S ) \rho(S) ρ ( S ) is rational, so δ ( S ) ≠ 0 \delta(S)\ne0 δ ( S ) = 0 .
Proof. (a) and (b) follow from (6) and Theorem 2.2; for S = N S=\mathbb{N} S = N , r N ( m ) = m r_{\mathbb{N}}(m)=m r N ( m ) = m and ρ ( N ) = ∑ m m 2 − ( m + 1 ) = 1 \rho(\mathbb{N})=\sum_m m2^{-(m+1)}=1 ρ ( N ) = ∑ m m 2 − ( m + 1 ) = 1 . (c) If θ = p / q \theta=p/q θ = p / q then 3 p + q = 4 q 3^{p+q}=4^q 3 p + q = 4 q , which is impossible for q ≥ 1 q\geq1 q ≥ 1 . If S S S is eventually periodic, then r S ( m ) r_S(m) r S ( m ) is either eventually periodic or, when S S S contains a tail [ c , ∞ ) [c,\infty) [ c , ∞ ) , eventually equal to m − c + 1 m-c+1 m − c + 1 ; in both cases the series for ρ ( S ) \rho(S) ρ ( S ) is a finite combination of geometric series and their derivatives with rational ratios.
Proposition 3.3 (Intervals). For S = [ a , b ] S=[a,b] S = [ a , b ] with n = b − a + 1 n=b-a+1 n = b − a + 1 elements, ρ ( S ) = 2 − a ( 2 − ( n + 2 ) 2 − n ) \rho(S)=2^{-a}(2-(n+2)2^{-n}) ρ ( S ) = 2 − a ( 2 − ( n + 2 ) 2 − n ) , and ρ ( [ a , ∞ ) ) = 2 1 − a \rho([a,\infty))=2^{1-a} ρ ([ a , ∞ )) = 2 1 − a . Hence [ a , b ] [a,b] [ a , b ] is contracting if and only if a ≥ 3 a\geq3 a ≥ 3 , or a = 2 a=2 a = 2 and b ≤ 3 b\leq3 b ≤ 3 , or a = b = 1 a=b=1 a = b = 1 ; and [ a , ∞ ) [a,\infty) [ a , ∞ ) is contracting if and only if a ≥ 3 a\geq3 a ≥ 3 . The largest value of ρ \rho ρ on contracting intervals is 1 / 4 1/4 1/4 , attained exactly by { 1 } \{1\} { 1 } , { 2 , 3 } \{2,3\} { 2 , 3 } and [ 3 , ∞ ) [3,\infty) [ 3 , ∞ ) .
Proof. Here r S ( m ) = m − a + 1 r_S(m)=m-a+1 r S ( m ) = m − a + 1 for a ≤ m ≤ b a\leq m\leq b a ≤ m ≤ b and 0 otherwise, so ρ ( S ) = ∑ j = 1 n j 2 − ( a + j ) = 2 − a ( 2 − ( n + 2 ) 2 − n ) \rho(S)=\sum_{j=1}^{n}j2^{-(a+j)}=2^{-a}(2-(n+2)2^{-n}) ρ ( S ) = ∑ j = 1 n j 2 − ( a + j ) = 2 − a ( 2 − ( n + 2 ) 2 − n ) . For a ≥ 3 a\geq3 a ≥ 3 we get ρ < 2 1 − a ≤ 1 / 4 < θ \rho<2^{1-a}\leq1/4<\theta ρ < 2 1 − a ≤ 1/4 < θ . For a = 2 a=2 a = 2 the values are 1 / 8 , 1 / 4 , 11 / 32 , … 1/8,1/4,11/32,\ldots 1/8 , 1/4 , 11/32 , … (increasing in n n n ), and 11 / 32 > θ 11/32>\theta 11/32 > θ . For a = 1 a=1 a = 1 they are 1 / 4 , 1 / 2 , … 1/4,1/2,\ldots 1/4 , 1/2 , … . The case b = ∞ b=\infty b = ∞ is the limit n → ∞ n\to\infty n → ∞ .
For example, ρ ( 2 N ) = 1 / 6 \rho(2\mathbb{N}) = 1/6 ρ ( 2 N ) = 1/6 (contracting) while ρ ( 2 N − 1 ) = 1 / 3 \rho(2\mathbb{N} - 1) = 1/3 ρ ( 2 N − 1 ) = 1/3 (expanding). The values of ρ \rho ρ range from ρ ( ∅ ) = 0 \rho(\varnothing) = 0 ρ ( ∅ ) = 0 to ρ ( N ) = 1 \rho(\mathbb{N}) = 1 ρ ( N ) = 1 and come very close to θ \theta θ ; the census of cycles in Section A, for instance, contains the contracting set { 1 , 6 , 8 , 9 } \{1,6,8,9\} { 1 , 6 , 8 , 9 } with ρ = 0.26172 \rho= 0.26172 ρ = 0.26172 . Nevertheless the critical value is never attained.
Proposition 3.4 (No critical sets). Let P = { 1 , 6 , 8 , 9 , 12 , 15 } ∪ [ 19 , 23 ] ∪ [ 25 , 26 ] ∪ [ 31 , 34 ] ∪ [ 36 , 37 ] ∪ [ 39 , 42 ] ∪ [ 44 , 45 ] ∪ [ 47 , 52 ] P = \{1,6,8,9,12,15\} \cup[19,23] \cup[25,26] \cup[31,34] \cup[36,37] \cup[39,42] \cup[44,45] \cup[47,52] P = { 1 , 6 , 8 , 9 , 12 , 15 } ∪ [ 19 , 23 ] ∪ [ 25 , 26 ] ∪ [ 31 , 34 ] ∪ [ 36 , 37 ] ∪ [ 39 , 42 ] ∪ [ 44 , 45 ] ∪ [ 47 , 52 ] , A = P ∪ [ 54 , ∞ ) A = P \cup[54,\infty) A = P ∪ [ 54 , ∞ ) and B = P ∪ { 53 } B = P \cup\{53\} B = P ∪ { 53 } . Then ρ ( A ) < θ < ρ ( B ) \rho(A) < \theta< \rho(B) ρ ( A ) < θ < ρ ( B ) , ρ ( B ) − ρ ( A ) = 5 ⋅ 2 − 54 \rho(B) - \rho(A) = 5 \cdot2^{-54} ρ ( B ) − ρ ( A ) = 5 ⋅ 2 − 54 , and every S ⊆ N S \subseteq\mathbb{N} S ⊆ N satisfies ρ ( S ) ≤ ρ ( A ) \rho(S) \leq\rho(A) ρ ( S ) ≤ ρ ( A ) or ρ ( S ) ≥ ρ ( B ) \rho(S) \geq\rho(B) ρ ( S ) ≥ ρ ( B ) . In particular ρ ( S ) ≠ θ \rho(S) \ne\theta ρ ( S ) = θ , so every S ⊆ N S \subseteq\mathbb{N} S ⊆ N is either contracting or expanding.
Proof. Let m ≥ 0 m \geq0 m ≥ 0 , Q ⊆ [ 1 , m ] Q \subseteq[1,m] Q ⊆ [ 1 , m ] and r = r Q ( m ) r = r_Q(m) r = r Q ( m ) . Every S S S with S ∩ [ 1 , m ] = Q S \cap[1,m] = Q S ∩ [ 1 , m ] = Q satisfies r S ( m + j ) ≤ r + j r_S(m+j) \leq r+j r S ( m + j ) ≤ r + j for j ≥ 1 j \geq1 j ≥ 1 , and therefore
c ( Q ) ≤ ρ ( S ) ≤ c ( Q ) + r + 2 2 m + 1 , c ( Q ) = ∑ k = 1 m r Q ( k ) 2 k + 1 . c(Q) \leq\rho(S) \leq c(Q) + \frac{r+2}{2^{m+1}}, \qquad c(Q) = \sum_{k=1}^{m} \frac{r_Q(k)}{2^{k+1}}. c ( Q ) ≤ ρ ( S ) ≤ c ( Q ) + 2 m + 1 r + 2 , c ( Q ) = k = 1 ∑ m 2 k + 1 r Q ( k ) .
with equality on the left for S = Q S = Q S = Q and on the right for S = Q ∪ [ m + 1 , ∞ ) S = Q \cup[m+1,\infty) S = Q ∪ [ m + 1 , ∞ ) , since ∑ j ≥ 1 ( r + j ) 2 − ( m + 1 + j ) = ( r + 2 ) 2 − ( m + 1 ) \sum_{j\geq1}(r+j)2^{-(m+1+j)} = (r+2)2^{-(m+1)} ∑ j ≥ 1 ( r + j ) 2 − ( m + 1 + j ) = ( r + 2 ) 2 − ( m + 1 ) . Call Q Q Q admissible if this interval contains θ \theta θ . A computation with exact rational arithmetic and a rigorous enclosure of θ \theta θ (ancillary file rho_gap_check.py) lists the admissible sets Q ⊆ [ 1 , m ] Q \subseteq[1,m] Q ⊆ [ 1 , m ] for m = 1 , 2 , … m = 1,2,\ldots m = 1 , 2 , … : there are at most 12 of them for each m ≤ 52 m \leq52 m ≤ 52 , and none for m = 53 m = 53 m = 53 . Hence for every S S S there is a smallest m m m such that S ∩ [ 1 , m ] S \cap[1,m] S ∩ [ 1 , m ] is not admissible, and all sets with this prefix lie on the same side of θ \theta θ ; in particular ρ ( S ) ≠ θ \rho(S) \ne\theta ρ ( S ) = θ . The largest right endpoint among the intervals of these first non-admissible prefixes that lie below θ \theta θ is ρ ( A ) \rho(A) ρ ( A ) , attained by A = P ∪ [ 54 , ∞ ) A = P \cup[54,\infty) A = P ∪ [ 54 , ∞ ) , and the smallest left endpoint among those above θ \theta θ is ρ ( B ) \rho(B) ρ ( B ) , attained by B B B . □
The computation is small: it handles at most twelve intervals at each of the 53 levels and takes a fraction of a second. Numerically θ − ρ ( A ) = 1.47 ⋅ 10 − 16 \theta- \rho(A) = 1.47 \cdot10^{-16} θ − ρ ( A ) = 1.47 ⋅ 1 0 − 16 and ρ ( B ) − θ = 1.30 ⋅ 10 − 16 \rho(B) - \theta= 1.30 \cdot10^{-16} ρ ( B ) − θ = 1.30 ⋅ 1 0 − 16 . The gap reflects a general feature of ρ \rho ρ : if a prefix Q ⊆ [ 1 , m ] Q \subseteq[1,m] Q ⊆ [ 1 , m ] ends with a run of length r ≥ 2 r \geq2 r ≥ 2 , the sets that contain m + 1 m+1 m + 1 have ρ ≥ c ( Q ) + ( r + 1 ) 2 − ( m + 2 ) \rho\geq c(Q) + (r+1)2^{-(m+2)} ρ ≥ c ( Q ) + ( r + 1 ) 2 − ( m + 2 ) , while those that do not have ρ ≤ c ( Q ) + 2 ⋅ 2 − ( m + 2 ) \rho\leq c(Q) + 2 \cdot2^{-(m+2)} ρ ≤ c ( Q ) + 2 ⋅ 2 − ( m + 2 ) . So the set of values of ρ \rho ρ is a compact set with many gaps, and θ \theta θ lies in the one that opens after the run [ 47 , 52 ] [47,52] [ 47 , 52 ] .
Remark 3.5 (Single halvings). If a downward step at an even number only halves it (x ↦ x / 2 x \mapsto x/2 x ↦ x /2 for m ≥ 1 m \geq1 m ≥ 1 , m ∉ S m \notin S m ∈ / S ), the orbit of ( 3 x + 1 ) / 2 = 2 M Syr ( x ) (3x+1)/2 = 2^M \operatorname{Syr}(x) ( 3 x + 1 ) /2 = 2 M Syr ( x ) passes through the exponents M , M − 1 , … , 1 M, M-1,\ldots,1 M , M − 1 , … , 1 and is multiplied by 3 at each exponent in S S S . So r S ( M ) r_S(M) r S ( M ) is replaced by ∣ S ∩ [ 1 , M ] ∣ |S \cap[1,M]| ∣ S ∩ [ 1 , M ] ∣ , and ρ ( S ) \rho(S) ρ ( S ) by ∑ s ∈ S P ( M ≥ s ) = ∑ s ∈ S 2 − s \sum_{s\in S}\mathbb{P}(M \geq s) = \sum_{s\in S}2^{-s} ∑ s ∈ S P ( M ≥ s ) = ∑ s ∈ S 2 − s . The results of this section and of § 6 hold for these changes; for instance, S = { 1 } S = \{1\} S = { 1 } is then expanding (ρ = 1 / 2 \rho= 1/2 ρ = 1/2 ) and S = { 2 } S = \{2\} S = { 2 } contracting (ρ = 1 / 4 \rho= 1/4 ρ = 1/4 ). In this paper we keep the full division, with which the runs of consecutive elements of S S S determine the behaviour.
Further predictions
The model makes several quantitative predictions, which we test in § 7 . Let W t W_t W t be the random walk above, with increments X i = X S ( M i ) X_i = X_S(M_i) X i = X S ( M i ) .
(i) Steps per odd step. By Theorem 2.1 a T S T_S T S -orbit spends on average
ℓ ( S ) = E ℓ S ( M ) = 1 + ρ ( S ) + ∑ m ≥ 1 , r S ( m ) < m 2 − ( m + 1 ) \ell(S) = \mathbb{E}\,\ell_S(M) = 1 + \rho(S) + \sum_{\substack{m \geq1,\, r_S(m)<m}} 2^{-(m+1)} ℓ ( S ) = E ℓ S ( M ) = 1 + ρ ( S ) + m ≥ 1 , r S ( m ) < m ∑ 2 − ( m + 1 )
steps per odd step.
(ii) Glide. The glide of n n n (also called its stopping time) is the number of steps of the orbit before it first drops below n n n . In the model the glide of an odd n n n , counted in odd steps, is
τ = min { t ≥ 1 : W t < 0 } ; \tau=\min\{t\ge1:W_t<0\}; τ = min { t ≥ 1 : W t < 0 } ;
by Theorem 2.1 the orbit can drop below n n n only at the end of an odd step. For contracting S S S , E τ < ∞ \mathbb{E}\tau<\infty E τ < ∞ and P ( τ > t ) \mathbb{P}(\tau>t) P ( τ > t ) decays exponentially; for expanding S S S , p ∞ ( S ) = P ( τ = ∞ ) > 0 p_{\infty}(S)=\mathbb{P}(\tau=\infty)>0 p ∞ ( S ) = P ( τ = ∞ ) > 0 .
(iii) Delay. For contracting S S S , the model predicts that n n n needs about ℓ ( S ) log 2 n / ∣ δ ( S ) ∣ \ell(S)\log_2 n/|\delta(S)| ℓ ( S ) log 2 n /∣ δ ( S ) ∣ steps to reach its cycle. For S = ∅ S=\varnothing S = ∅ , if each halving is counted as a step (as for the map T T T ), this is the classical estimate 2 log n / log ( 4 / 3 ) ≈ 6.95 log n 2\log n/\log(4/3)\approx6.95\log n 2 log n / log ( 4/3 ) ≈ 6.95 log n .
(iv) Excursions. For contracting S S S let λ ( S ) > 0 \lambda(S)>0 λ ( S ) > 0 be the root of E 2 λ X = 1 \mathbb{E}\,2^{\lambda X}=1 E 2 λ X = 1 . (The function λ ↦ E 2 λ X \lambda\mapsto\mathbb{E}\,2^{\lambda X} λ ↦ E 2 λ X is convex, equals 1 1 1 at λ = 0 \lambda=0 λ = 0 and has derivative δ ( S ) ln 2 < 0 \delta(S)\ln2<0 δ ( S ) ln 2 < 0 there; for eventually periodic S S S it tends to ∞ \infty ∞ at the end of the interval on which it is finite, so the positive root exists and is unique.) A random walk with negative drift climbs h h h units above its starting point only with a probability that decays exponentially in h h h , and Cramér’s estimate [10 ] identifies the rate: P ( sup t W t > h ) ∼ C 2 − λ ( S ) h \mathbb{P}(\sup_t W_t>h)\sim C2^{-\lambda(S)h} P ( sup t W t > h ) ∼ C 2 − λ ( S ) h . So the largest value on the orbit of n n n exceeds n 2 h n2^h n 2 h with probability about 2 − λ h 2^{-\lambda h} 2 − λh . Consequently the record values of the orbit maxima should grow like n 1 + 1 / λ ( S ) + o ( 1 ) n^{1+1/\lambda(S)+o(1)} n 1 + 1/ λ ( S ) + o ( 1 ) , and, for 0 < γ < 1 / λ ( S ) 0<\gamma<1/\lambda(S) 0 < γ < 1/ λ ( S ) , the number of n ≤ N n\le N n ≤ N whose orbit exceeds n 1 + γ n^{1+\gamma} n 1 + γ should be N 1 − λ γ + o ( 1 ) N^{1-\lambda\gamma+o(1)} N 1 − λγ + o ( 1 ) . For S = ∅ S=\varnothing S = ∅ , E 2 X = 3 E 2 − ( M + 1 ) = 3 ∑ j ≥ 1 4 − j = 1 \mathbb{E}\,2^X=3\mathbb{E}\,2^{-(M+1)}=3\sum_{j\ge1}4^{-j}=1 E 2 X = 3 E 2 − ( M + 1 ) = 3 ∑ j ≥ 1 4 − j = 1 , so λ ( ∅ ) = 1 \lambda(\varnothing)=1 λ ( ∅ ) = 1 exactly; this recovers the maximum excursion constant 2 2 2 of the random-walk model of Lagarias and Weiss [23 , 13 ] , consistent with the computations of Oliveira e Silva [27 ] .
(v) Expanding maps. For expanding S ≠ N S\ne\mathbb{N} S = N let κ ( S ) > 0 \kappa(S)>0 κ ( S ) > 0 be the root of E 2 − κ X = 1 \mathbb{E}\,2^{-\kappa X}=1 E 2 − κ X = 1 , which exists and is unique by the same convexity argument, since X < 0 X<0 X < 0 with positive probability when S ≠ N S\ne\mathbb{N} S = N . Then P ( inf t W t < − h ) ∼ C 2 − κ X \mathbb{P}(\inf_t W_t<-h)\sim C2^{-\kappa X} P ( inf t W t < − h ) ∼ C 2 − κ X , so the proportion of n ≈ 2 k n\approx2^k n ≈ 2 k whose orbit comes down to a cycle should decay like 2 − κ k = n − κ 2^{-\kappa k}=n^{-\kappa} 2 − κk = n − κ .
Table 3.1 lists these constants. The three maps with ρ = 1 / 4 \rho=1/4 ρ = 1/4 have the same drift − 0.0188 -0.0188 − 0.0188 , about 4.5% of the Collatz drift, but quite different excursion exponents, because λ \lambda λ depends on the whole distribution of r S ( M ) r_S(M) r S ( M ) and not only on its mean. The column ℓ / ∣ δ ∣ \ell/|\delta| ℓ /∣ δ ∣ is the predicted number of steps per bit of the starting value, and 1 + 1 / λ 1 + 1/\lambda 1 + 1/ λ is the predicted exponent of the record peaks (§ 5.2 (iv)); both grow rapidly as ρ ( S ) \rho(S) ρ ( S ) approaches θ \theta θ .
Table 3.1 : Model constants for the ten maps studied numerically: ρ \rho ρ , drift δ \delta δ (bits per odd step), steps per odd step ℓ \ell ℓ , predicted delay per bit ℓ / ∣ δ ∣ \ell/|\delta| ℓ /∣ δ ∣ , excursion exponent λ \lambda λ , model mean glide E τ \mathbb{E}\tau E τ (odd steps), and for expanding maps the return exponent κ \kappa κ and the never-return probability p ∞ p_{\infty} p ∞ . E τ \mathbb{E}\tau E τ and p ∞ p_{\infty} p ∞ are Monte Carlo estimates (at least 1.5 ⋅ 10 8 1.5 \cdot10^{8} 1.5 ⋅ 1 0 8 and 2 ⋅ 10 7 2 \cdot10^{7} 2 ⋅ 1 0 7 walks); the other entries are exact or computed to the digits shown.
Table 3.1.
Rigorous results for single maps
The idea behind the following theorem is that a typical odd integer n n n with k k k binary digits determines, through its residue modulo 2 k 2^k 2 k , about k / 2 k/2 k /2 valuations M 0 , M 1 , … M_0, M_1, \ldots M 0 , M 1 , … of its orbit, since each odd step uses up E ( M + 1 ) = 2 \mathbb{E}(M+1)=2 E ( M + 1 ) = 2 digits on average; by Theorem 3.1, for most residue classes these valuations look like a sample of independent geometric variables. By the law of large numbers the first k / 2 k/2 k /2 odd steps therefore change log 2 n \log_2 n log 2 n by about δ k / 2 \delta k/2 δ k /2 , so the orbit reaches about n 1 + δ / 2 n^{1+\delta/2} n 1 + δ /2 . What happens afterwards is no longer controlled by the residue of n n n .
Theorem 4.1. Let S ⊆ N S \subseteq\mathbb{N} S ⊆ N and δ = δ ( S ) \delta=\delta(S) δ = δ ( S ) .
(a) If δ < 0 \delta<0 δ < 0 , then for every c > 1 + δ / 2 c>1+\delta/2 c > 1 + δ /2 the set of odd n n n whose T S T_S T S -orbit contains a number smaller than n c n^c n c has density one. In particular almost every orbit drops below its starting value.
(b) If δ > 0 \delta>0 δ > 0 , then for every c < 1 + δ / 2 c<1+\delta/2 c < 1 + δ /2 the set of odd n n n whose T S T_S T S -orbit contains a number larger than n c n^c n c has density one.
For S = ∅ S=\varnothing S = ∅ , part (a) is Korec’s theorem [15 ] , since 1 + δ ( ∅ ) / 2 = log 3 / log 4 1+\delta(\varnothing)/2=\log3/\log4 1 + δ ( ∅ ) /2 = log 3/ log 4 , and its last sentence is the theorem of Terras and Everett [30 , 9 ] . The statements extend to all n n n . An even n = 2 m k n=2^m k n = 2 m k reaches the odd number 3 r S ( m ) k 3^{r_S(m)}k 3 r S ( m ) k (Theorem 2.1); for fixed m m m , the odd k k k for which 3 r S ( m ) k 3^{r_S(m)}k 3 r S ( m ) k is exceptional form a set of density zero, because multiplication by 3 r S ( m ) 3^{r_S(m)} 3 r S ( m ) is injective and changes sizes by a bounded factor, and the integers divisible by 2 m + 1 2^{m+1} 2 m + 1 form a set of density 2 − m − 1 2^{-m-1} 2 − m − 1 .
Proof. Fix ε ∈ ( 0 , 1 4 ) \varepsilon\in(0,\frac{1}{4}) ε ∈ ( 0 , 4 1 ) ; it suffices to prove the statements for odd n n n in a dyadic interval ( N / 2 , N ] (N/2,N] ( N /2 , N ] as N → ∞ N\to\infty N → ∞ . Let K = ⌊ ( 1 − ε ) log 2 N ⌋ K=\lfloor(1-\varepsilon)\log_2 N\rfloor K = ⌊( 1 − ε ) log 2 N ⌋ and j = ⌊ K / ( 2 + ε ) ⌋ j=\lfloor K/(2+\varepsilon)\rfloor j = ⌊ K / ( 2 + ε )⌋ . Call a vector ( m 0 , … , m j − 1 ) (m_0,\ldots,m_{j-1}) ( m 0 , … , m j − 1 ) good if ∑ i < j ( m i + 1 ) ≤ K \sum_{i<j}(m_i+1)\le K ∑ i < j ( m i + 1 ) ≤ K and ∣ ∑ i < j X S ( m i ) − j δ ∣ ≤ ε j \left|\sum_{i<j}X_S(m_i)-j\delta\right|\le\varepsilon j ∑ i < j X S ( m i ) − j δ ≤ ε j . By Theorem 3.1 and the law of large numbers (note E ( M + 1 ) = 2 < 2 + ε \mathbb{E}(M+1)=2<2+\varepsilon E ( M + 1 ) = 2 < 2 + ε ), the μ \mu μ -measure p N p_N p N of the set G G G of x ∈ Z 2 ∗ x\in\mathbb{Z}_2^* x ∈ Z 2 ∗ whose first j j j valuations form a good vector tends to 1 1 1 . By Theorem 3.1, G G G is a union of residue classes modulo 2 K + 1 2^{K+1} 2 K + 1 , and each odd residue class modulo 2 K + 1 2^{K+1} 2 K + 1 contains N / 2 K + 2 + O ( 1 ) N/2^{K+2}+O(1) N / 2 K + 2 + O ( 1 ) integers of ( N / 2 , N ] (N/2,N] ( N /2 , N ] . Since there are 2 K = O ( N 1 − ε ) 2^K=O(N^{1-\varepsilon}) 2 K = O ( N 1 − ε ) odd classes, the proportion of odd n ∈ ( N / 2 , N ] n\in(N/2,N] n ∈ ( N /2 , N ] in G G G is p N + O ( N − ε ) → 1 p_N+O(N^{-\varepsilon})\to1 p N + O ( N − ε ) → 1 .
Let n ∈ G n\in G n ∈ G and x i = U S i ( n ) x_i=U_S^i(n) x i = U S i ( n ) . By (5) , log 2 x j = log 2 n + ∑ i < j X S ( M i ) + ∑ i < j log 2 ( 1 + 1 3 x i ) \log_2 x_j=\log_2 n+\sum_{i<j}X_S(M_i)+\sum_{i<j}\log_2\left(1+\frac{1}{3x_i}\right) log 2 x j = log 2 n + ∑ i < j X S ( M i ) + ∑ i < j log 2 ( 1 + 3 x i 1 ) , and j = 1 − ε 2 + ε log 2 n + O ( 1 ) j=\frac{1-\varepsilon}{2+\varepsilon}\log_2 n+O(1) j = 2 + ε 1 − ε log 2 n + O ( 1 ) .
(a) If x i ≥ n c x_i\ge n^c x i ≥ n c for all i < j i<j i < j , the last sum is at most j / ( 3 n c ln 2 ) < 1 j/(3n^c\ln2)<1 j / ( 3 n c ln 2 ) < 1 , so log 2 x j ≤ log 2 n + j ( δ + ε ) + 1 = ( 1 + ( 1 − ε ) ( δ + ε ) 2 + ε ) log 2 n + O ( 1 ) \log_2 x_j\le\log_2 n+j(\delta+\varepsilon)+1=\left(1+\frac{(1-\varepsilon)(\delta+\varepsilon)}{2+\varepsilon}\right)\log_2 n+O(1) log 2 x j ≤ log 2 n + j ( δ + ε ) + 1 = ( 1 + 2 + ε ( 1 − ε ) ( δ + ε ) ) log 2 n + O ( 1 ) . For ε \varepsilon ε small the coefficient is smaller than c c c , so x j < n c x_j<n^c x j < n c for large N N N . Either way the orbit contains a number smaller than n c n^c n c .
(b) The last sum is positive, so log 2 x j ≥ ( 1 + ( 1 − ε ) ( δ − ε ) 2 + ε ) log 2 n − O ( 1 ) \log_2 x_j\ge\left(1+\frac{(1-\varepsilon)(\delta-\varepsilon)}{2+\varepsilon}\right)\log_2 n-O(1) log 2 x j ≥ ( 1 + 2 + ε ( 1 − ε ) ( δ − ε ) ) log 2 n − O ( 1 ) , which exceeds c log 2 n c\log_2 n c log 2 n for small ε \varepsilon ε and large N N N . □
Tao’s much stronger theorem [29 ] for S = ∅ S=\varnothing S = ∅ suggests Theorem 9.9 below. The next proposition explains why a proof of divergence for an expanding map cannot be based on residue classes alone.
Proposition 4.2. Let S ≠ N S\ne\mathbb{N} S = N . For every L ≥ 1 L\ge1 L ≥ 1 and every odd a a a there is a positive rational number y y y with odd denominator such that y ≡ a ( m o d 2 L ) y\equiv a\pmod{2^L} y ≡ a ( mod 2 L ) in Z 2 \mathbb{Z}_2 Z 2 and the T S T_S T S -orbit of y y y is periodic.
Proof. Choose m ∗ ∈ N ∖ S m_*\in\mathbb{N}\setminus S m ∗ ∈ N ∖ S , so that r S ( m ∗ ) = 0 r_S(m_*)=0 r S ( m ∗ ) = 0 . By Theorem 3.1 there are m 0 , … , m j − 1 m_0,\ldots,m_{j-1} m 0 , … , m j − 1 such that every x ∈ Z 2 ∗ x\in\mathbb{Z}_2^* x ∈ Z 2 ∗ whose first j j j valuations are m 0 , … , m j − 1 m_0,\ldots,m_{j-1} m 0 , … , m j − 1 satisfies x ≡ a ( m o d 2 L ) x\equiv a\pmod{2^L} x ≡ a ( mod 2 L ) (take the first valuations of a a a itself until ∑ ( m i + 1 ) ≥ L − 1 \sum(m_i+1)\ge L-1 ∑ ( m i + 1 ) ≥ L − 1 ). For s ≥ 0 s\ge0 s ≥ 0 consider the periodic sequence obtained by repeating the block ( m 0 , … , m j − 1 , m ∗ , … , m ∗ ) (m_0,\ldots,m_{j-1},m_\ast,\ldots,m_\ast) ( m 0 , … , m j − 1 , m ∗ , … , m ∗ ) with s s s copies of m ∗ m_\ast m ∗ . By Theorem 3.1 there is exactly one y ∈ Z 2 × y \in\mathbb{Z}_2^\times y ∈ Z 2 × with this valuation sequence, and then U S j + s ( y ) U_S^{j+s}(y) U S j + s ( y ) has the same sequence, so U S j + s ( y ) = y U_S^{j+s}(y)=y U S j + s ( y ) = y . On the corresponding residue class, U S j + s U_S^{j+s} U S j + s is an affine map x ↦ ( 3 A x + c ) / 2 B x \mapsto(3^A x+c)/2^B x ↦ ( 3 A x + c ) / 2 B with A = ∑ i < j ( 1 + r S ( m i ) ) + s A=\sum_{i<j}(1+r_S(m_i))+s A = ∑ i < j ( 1 + r S ( m i )) + s , B = ∑ i < j ( m i + 1 ) + s ( m ∗ + 1 ) B=\sum_{i<j}(m_i+1)+s(m_\ast+1) B = ∑ i < j ( m i + 1 ) + s ( m ∗ + 1 ) and an integer c > 0 c>0 c > 0 , so y = c / ( 2 B − 3 A ) y=c/(2^B-3^A) y = c / ( 2 B − 3 A ) . Since 2 m ∗ + 1 ≥ 4 > 3 2^{m_\ast+1}\geq4>3 2 m ∗ + 1 ≥ 4 > 3 , we have 2 B > 3 A 2^B>3^A 2 B > 3 A for s s s large, and then y > 0 y>0 y > 0 . All points of the orbit of y y y are positive rationals with odd denominator, and the orbit is periodic.
For example, let S = { 1 , 2 } S=\{1,2\} S = { 1 , 2 } , a = 7 a=7 a = 7 and L = 4 L=4 L = 4 . The U S U_S U S -orbit 7 → 11 → 17 → 39 7\to11\to17\to39 7 → 11 → 17 → 39 has the valuations 0 , 0 , 1 0,0,1 0 , 0 , 1 , which suffice since ∑ ( m i + 1 ) = 4 ≥ L − 1 \sum(m_i+1)=4\geq L-1 ∑ ( m i + 1 ) = 4 ≥ L − 1 , and m ∗ = 3 m_\ast=3 m ∗ = 3 . With s = 0 s=0 s = 0 the fixed point is negative (2 4 < 3 4 2^4<3^4 2 4 < 3 4 ), but with s = 1 s=1 s = 1 the block ( 0 , 0 , 1 , 3 ) (0,0,1,3) ( 0 , 0 , 1 , 3 ) gives A = 5 A=5 A = 5 , B = 8 B=8 B = 8 , 2 B − 3 A = 13 2^B-3^A=13 2 B − 3 A = 13 and y = 187 / 13 y=187/13 y = 187/13 , whose T S T_S T S -orbit is the cycle
187 13 → 287 13 → 437 13 → 662 13 → 993 13 → 1496 13 → 187 13 ; \frac{187}{13}\to\frac{287}{13}\to\frac{437}{13}\to\frac{662}{13}\to\frac{993}{13}\to\frac{1496}{13}\to\frac{187}{13}; 13 187 → 13 287 → 13 437 → 13 662 → 13 993 → 13 1496 → 13 187 ;
indeed y ≡ 7 ( m o d 32 ) y\equiv7\pmod{32} y ≡ 7 ( mod 32 ) , since the first three valuations determine y y y modulo 2 5 2^5 2 5 .
For S = ∅ S=\varnothing S = ∅ this is the classical correspondence between periodic parity sequences and rational cycles of the 3 x + 1 3x+1 3 x + 1 map; see [18 ] . The point of Theorem 4.2 is that the valuations along the orbit of y y y agree with those of the integer a a a for as many steps as we like, so no finite amount of residue information distinguishes the orbit of y y y from integer orbits.
Remark 4.3. Suppose an argument shows that every positive integer in a residue class a m o d 2 L a\bmod2^L a mod 2 L has an unbounded T S T_S T S -orbit, using only the residues of the orbit points and inequalities such as U S ( x ) ≥ 3 1 + r S ( M ) x / 2 M + 1 U_S(x)\geq3^{1+r_S(M)}x/2^{M+1} U S ( x ) ≥ 3 1 + r S ( M ) x / 2 M + 1 that hold for all positive x x x (as in (4) ). The same argument would apply to the rational number y y y of Theorem 4.2 , whose orbit is bounded. So for every S ≠ N S\ne\mathbb{N} S = N , a proof that some orbit diverges must use integrality, or some other information that rational numbers with odd denominators do not share. For S = N S=\mathbb{N} S = N divergence is trivial.
Numerical results
This section compares the predictions of § 5 with computations for ten maps T S T_S T S : the seven contracting maps ∅ \varnothing ∅ , { 3 } \{3\} { 3 } , { 2 } \{2\} { 2 } , 2 N 2\mathbb{N} 2 N , [ 3 , ∞ ) [3,\infty) [ 3 , ∞ ) , { 2 , 3 } \{2,3\} { 2 , 3 } and { 1 } \{1\} { 1 } , listed by increasing ρ ( S ) \rho(S) ρ ( S ) , and three expanding maps. The contracting maps range from the Collatz map to the three maps with ρ = 1 / 4 \rho=1/4 ρ = 1/4 , whose drift is only 4.5% of the Collatz drift, so that their orbits are much longer and climb much higher. The tables are meant to be read against Table 3.1 , which lists the corresponding model constants.
Method
For a given S S S and bound N N N we verify by induction on n n n that every n < N n<N n < N has an eventually periodic T S T_S T S -orbit. For each n n n we iterate T S T_S T S until one of the following happens: (i) the orbit drops below n n n , in which case n n n ends in the same cycle as the smaller number reached; (ii) a cycle is detected (by Brent’s algorithm [6 ] , a cycle-detection method that needs only a bounded amount of memory); since the orbit has not dropped below n n n , all elements of this cycle are at least n n n ; (iii) the orbit exceeds 2 4096 2^{4096} 2 4096 ; (iv) 10 8 10^8 1 0 8 steps are made. Outcomes (iii) and (iv) never occurred. Since an orbit inside a cycle never drops below the smallest element of the cycle, every cycle whose smallest element is below N N N is found. For n < 2 26 n<2^{26} n < 2 26 we also store the cycle reached by n n n and its delay, the number of steps until the orbit first reaches the smallest element of its cycle, computed recursively as delay ( n ) = g ( n ) + delay ( x ) \operatorname{delay}(n)=g(n)+\operatorname{delay}(x) delay ( n ) = g ( n ) + delay ( x ) , where g ( n ) g(n) g ( n ) is the glide of n n n and x < n x<n x < n the first smaller value.
For every odd n n n we record the glide (in steps and in odd steps), the peak (the largest value before the orbit drops below n n n ), and log 2 ( x / n ) \log_2(x/n) log 2 ( x / n ) at the drop. For example, under T ∅ T_{\varnothing} T ∅ the orbit of 7 is 7, 11, 17, 26, 13, 20, 5, 8, 1: the glide of 7 is 6 steps, or 4 odd steps, its peak is 26, the recorded value is log 2 ( 5 / 7 ) \log_2(5/7) log 2 ( 5/7 ) , and the delay of 7 is 8. The measured drift is the sum of log 2 ( x / n ) \log_2(x/n) log 2 ( x / n ) divided by the total number of odd steps, over a block of starting values; by Wald’s identity E W τ = δ ( S ) E τ E W_\tau= \delta(S) E\tau E W τ = δ ( S ) E τ for the walk stopped at the glide τ \tau τ , this ratio estimates δ ( S ) \delta(S) δ ( S ) without bias from the stopping rule. We also sample 400 random odd starting values with B ∈ { 64 , 256 , 1024 , 4096 } B \in\{64,256,1024,4096\} B ∈ { 64 , 256 , 1024 , 4096 } bits for each map, follow them to their cycle (or, for expanding maps, until they exceed 2 2 B + 256 2^{2B+256} 2 2 B + 256 ) and record the delay per bit and the drift up to the first time the orbit has at most B / 2 B/2 B /2 bits.
The program is a Python driver with a C kernel (64-bit arithmetic with an overflow check, then multi-limb integers), with checkpoints so that interrupted runs can be resumed, and a pure-Python twin used for self-tests. The runs were made on free cloud notebooks with 4 CPU cores; the speed ranged from 3.6 ⋅ 10 7 3.6 \cdot10^7 3.6 ⋅ 1 0 7 starting values per second for S = ∅ S=\varnothing S = ∅ to 1.2 ⋅ 10 6 1.2 \cdot10^6 1.2 ⋅ 1 0 6 for S = { 1 } S=\{1\} S = { 1 } , about 10 hours in total. As a check, for S = ∅ S=\varnothing S = ∅ the program reproduces the known path records of the 3 x + 1 3x+1 3 x + 1 problem [27 , 4 ] ; for example the largest peak for n < 2 34 n<2^{34} n < 2 34 is 10,361,199,457,202,525,864, reached from n = 12 , 327 , 829 , 503 n=12,327,829,503 n = 12 , 327 , 829 , 503 . (This is half of the path record 20,722,398,914,405,051,728 of the map x ↦ 3 x + 1 x\mapsto3x+1 x ↦ 3 x + 1 , x ↦ x / 2 x\mapsto x/2 x ↦ x /2 , because T ∅ T_{\varnothing} T ∅ combines the step x ↦ 3 x + 1 x\mapsto3x+1 x ↦ 3 x + 1 with the following halving.)
Contracting maps
We ran seven contracting maps: ∅ \varnothing ∅ , { 3 } \{3\} { 3 } , { 2 } \{2\} { 2 } , $2\mathbb{N}$, and the three maps with ρ = 1 / 4 \rho=1/4 ρ = 1/4 . Every n < 2 34 = 17 , 179 , 869 , 184 n<2^{34}=17,179,869,184 n < 2 34 = 17 , 179 , 869 , 184 was checked, except for S = { 1 } S=\{1\} S = { 1 } , where the run stopped at $n=16,681,795,584; the statistics for S = { 1 } S=\{1\} S = { 1 } below refer to the complete block [ 2 32 , 2 33 ) [2^{32},2^{33}) [ 2 32 , 2 33 ) , and those for the other maps to [ 2 33 , 2 34 ) [2^{33},2^{34}) [ 2 33 , 2 34 ) .
Table 5.1 lists the cycles, named as in Section A: C T + ( n ) C_T^+(n) C T + ( n ) is the cycle with smallest element n n n of the map T U T_U T U , the map closest to the Collatz map in which the cycle occurs. The 20 cycles listed for the seven maps are 11 different cycles; for example, the cycle ( 15 , 23 , 35 , 53 , 80 , 120 ) (15,23,35,53,80,120) ( 15 , 23 , 35 , 53 , 80 , 120 ) of T 2 N T_{2\mathbb{N}} T 2 N is C { 4 } + ( 15 ) C_{\{4\}}^+(15) C { 4 } + ( 15 ) , which occurs for every S S S with 4 ∈ S 4\in S 4 ∈ S and 3 ∉ S 3\notin S 3 ∈ / S . Every cycle has smallest element at most 347, and no new cycle appears beyond that, up to 2 34 2^{34} 2 34 . For S = [ 3 , ∞ ) S=[3,\infty) S = [ 3 , ∞ ) the cycle C ∅ + ( 1 ) = ( 1 , 2 ) C_{\varnothing}^+(1)=(1,2) C ∅ + ( 1 ) = ( 1 , 2 ) is reached only from 1, 2 and 4. The basin shares in [ 2 25 , 2 26 ) [2^{25},2^{26}) [ 2 25 , 2 26 ) and for random 4096-bit numbers agree within the sampling error (about 2.5 percentage points), suggesting that each basin has a natural density (Theorem 9.3).
Table 5.2 and Figure 5.1 compare the data with the model. The measured drifts agree with δ ( S ) \delta(S) δ ( S ) to four or five digits. For every map, the proportion of glides longer than 64 odd steps differs from the exact model value by less than one binomial standard error for the same number of independent samples (∣ z ∣ < 0.8 |z|<0.8 ∣ z ∣ < 0.8 in all seven cases); the mean glides and the far tails agree to about 0.1%, and the fitted excursion exponents are within 2% of λ ( S ) \lambda(S) λ ( S ) . The starting values have only 33 or 34 bits, whereas a glide of 64 odd steps involves about 128 binary digits of valuations and a glide of 512 odd steps about 1000; so the independence of Theorem 3.1 persists, in distribution and to high accuracy, far beyond the range where it is a theorem.
Table 5.2: Model versus data for the contracting maps. Drift in bits per odd step, measured over all odd n n n in the top block (see text) and over 400 random 4096-bit starts (standard error in units of the last digit); delay per bit for the 4096-bit starts; mean glide in odd steps; λ \lambda λ fitted to the tail of the peak excess log 2 ( p e a k / n ) \log_2(\mathrm{peak}/n) log 2 ( peak / n ) for odd n ∈ [ 2 32 , 2 33 ) n \in[2^{32},2^{33}) n ∈ [ 2 32 , 2 33 ) . Model values: P ( g l i d e > 64 ) \mathbb{P}(\mathrm{glide}>64) P ( glide > 64 ) computed exactly by dynamic programming over the walk, the other glide statistics by Monte Carlo (Table 3.1 ).
Table 5.2.
Figure 5.1. Glide length distributions. Dots: proportion of odd n ∈ [ 2 32 , 2 33 ) n \in[2^{32}, 2^{33}) n ∈ [ 2 32 , 2 33 ) whose glide has more than t t t odd steps. Lines: the random-walk model of Section 3 (Monte Carlo with 1.5 ⋅ 10 8 1.5 \cdot10^{8} 1.5 ⋅ 1 0 8 to 2 ⋅ 10 9 2 \cdot10^{9} 2 ⋅ 1 0 9 walks, drawn while at least 25 walks remain). Last panel: the exponent λ \lambda λ fitted to the tail of the peak excess, against the root of E 2 λ X = 1 \mathbb{E}2^{\lambda X}=1 E 2 λ X = 1 .
Table 5.3 shows the records. The near-critical maps have glides of 10 5 10^5 1 0 5 steps and peaks of more than 1000 bits starting from 33-bit numbers. By § 5.2 (iv) the ratio log ( peak ) / log n \log(\operatorname{peak})/\log n log ( peak ) / log n of the record holders should tend to 1 + 1 / λ ( S ) 1+1/\lambda(S) 1 + 1/ λ ( S ) ; the observed ratios (1.88, 1.99, 2.81, 3.22, 8.57, 22.0, 39.2 in the order of the table) are all somewhat below the limits 2, 2.18, 3.13, 3.60, 11.2, 29.4, 45.8, as expected at this size. The three maps with ρ = 1 / 4 \rho=1/4 ρ = 1/4 have the same drift but differ by an order of magnitude in their records, in the order predicted by λ \lambda λ .
Table 5.3: Records among n < 2 34 n<2^{34} n < 2 34 (among n < 1.668 ⋅ 10 10 n<1.668\cdot10^{10} n < 1.668 ⋅ 1 0 10 for S = { 1 } S=\{1\} S = { 1 } ): the longest glide (in steps) and the highest peak (in bits).
Table 5.3.
Expanding maps
For the expanding maps 2 N − 1 2\mathbb{N}-1 2 N − 1 , [ 2 , 4 ] [2,4] [ 2 , 4 ] and { 1 , 2 } \{1,2\} { 1 , 2 } we checked all n < 2 20 n < 2^{20} n < 2 20 , treating an orbit as escaping when it exceeds 2 256 2^{256} 2 256 . The cycles found are C { 3 } + ( 3 ) = ( 3 , 5 , 8 , 12 ) C_{\{3\}}^{+}(3)=(3,5,8,12) C { 3 } + ( 3 ) = ( 3 , 5 , 8 , 12 ) for 2 N − 1 2\mathbb{N}-1 2 N − 1 ; C ∅ + ( 1 ) C_{\varnothing}^{+}(1) C ∅ + ( 1 ) , C { 2 } + ( 19 ) C_{\{2\}}^{+}(19) C { 2 } + ( 19 ) and C { 2 , 3 , 4 } + ( 23 ) C_{\{2,3,4\}}^{+}(23) C { 2 , 3 , 4 } + ( 23 ) for [ 2 , 4 ] [2,4] [ 2 , 4 ] ; and C { 1 } + ( 1 ) = ( 1 , 2 , 3 , 5 , 8 ) C_{\{1\}}^{+}(1)=(1,2,3,5,8) C { 1 } + ( 1 ) = ( 1 , 2 , 3 , 5 , 8 ) for { 1 , 2 } \{1,2\} { 1 , 2 } . The proportion of odd n ∈ [ 2 19 , 2 20 ) n \in[2^{19},2^{20}) n ∈ [ 2 19 , 2 20 ) that never drop below n n n is 0.1644, 0.2686 and 0.4299, against the model values p ∞ = 0.1641 p_{\infty}=0.1641 p ∞ = 0.1641 , 0.2688, 0.4303. The proportion of all n ∈ [ 2 k − 1 , 2 k ) n \in[2^{k-1},2^k) n ∈ [ 2 k − 1 , 2 k ) whose orbit reaches a cycle decreases from 19.9%, 9.3%, 8.1% at k = 15 k=15 k = 15 to 11.6%, 4.3%, 2.6% at k = 20 k=20 k = 20 ; the least-squares slopes of its log 2 \log_{2} log 2 over k = 15 , … , 20 k=15,\ldots,20 k = 15 , … , 20 are − 0.156 -0.156 − 0.156 , − 0.217 -0.217 − 0.217 , − 0.321 -0.321 − 0.321 , against − κ = − 0.156 -\kappa=-0.156 − κ = − 0.156 , − 0.220 -0.220 − 0.220 , − 0.318 -0.318 − 0.318 . All 400 random 4096-bit starting values of each map escaped, with measured drifts + 0.1130 ( 4 ) +0.1130(4) + 0.1130 ( 4 ) , + 0.1302 ( 3 ) +0.1302(3) + 0.1302 ( 3 ) , + 0.3781 ( 7 ) +0.3781(7) + 0.3781 ( 7 ) against δ = + 0.11328 \delta=+0.11328 δ = + 0.11328 , + 0.12979 +0.12979 + 0.12979 , + 0.37744 +0.37744 + 0.37744 .
Going down at odd numbers: the maps T S − T^-_S T S −
For odd x x x , an odd integer or an element of Z 2 × ∖ { − 1 } \mathbb{Z}_2^\times\setminus\{-1\} Z 2 × ∖ { − 1 } , put M − ( x ) = v 2 ( x + 1 ) − 1 M^-(x)=v_2(x+1)-1 M − ( x ) = v 2 ( x + 1 ) − 1 . Exactly as in Theorem 2.1, the T S − T^-_S T S − -orbit of an odd x x x reaches the odd number
U S − ( x ) = 3 r S ( M ) x + 1 2 M + 1 , M = M − ( x ) , (7) U^-_S(x)=3^{r_S(M)}\frac{x+1}{2^{M+1}},\qquad M=M^-(x), \tag*{(7)} U S − ( x ) = 3 r S ( M ) 2 M + 1 x + 1 , M = M − ( x ) , (7)
after ℓ S ( M ) \ell_S(M) ℓ S ( M ) steps, all intermediate terms being even. The set { x ∈ Z 2 × : M − ( x ) = m } \{x\in\mathbb{Z}_2^\times:M^-(x)=m\} { x ∈ Z 2 × : M − ( x ) = m } is again a residue class modulo $2^{m+2}$ that U S − U^-_S U S − maps affinely onto Z 2 × \mathbb{Z}_2^\times Z 2 × , so Theorem 3.1 holds verbatim: the valuations M − M^- M − along a U S − U^-_S U S − -orbit are independent with P ( M − = m ) = 2 − ( m + 1 ) \mathbb{P}(M^-=m)=2^{-(m+1)} P ( M − = m ) = 2 − ( m + 1 ) . Since $\log_2 U^-_S(x)log 2 x = r S ( M ) log 2 3 − ( M + 1 ) + log 2 ( 1 + 1 / x ) \log_{2} x = r_{S}(M) \log_{2} 3 - (M + 1) + \log_{2}(1 + 1/x) log 2 x = r S ( M ) log 2 3 − ( M + 1 ) + log 2 ( 1 + 1/ x ) , the drift of the model is
δ − ( S ) = ρ ( S ) log 2 3 − 2 = δ ( S ) − log 2 3 ≤ log 2 3 − 2 = − 0.41504 … (8) \delta^{-}(S) = \rho(S) \log_{2} 3 - 2 = \delta(S) - \log_{2} 3 \le\log_{2} 3 - 2 = -0.41504\ldots \tag*{(8)} δ − ( S ) = ρ ( S ) log 2 3 − 2 = δ ( S ) − log 2 3 ≤ log 2 3 − 2 = − 0.41504 … (8)
with equality only for S = N S = \mathbb{N} S = N (if m 0 ∉ S m_{0} \notin S m 0 ∈ / S , then r S ( m 0 ) = 0 < m 0 r_{S}(m_{0}) = 0 < m_{0} r S ( m 0 ) = 0 < m 0 and ρ ( S ) < 1 \rho(S) < 1 ρ ( S ) < 1 ). So every S S S is contracting for T S − T^{-}_{S} T S − , and the proof of Theorem 4.1(a) applies with only notational changes (the correction term is now log 2 ( 1 + 1 / x ) \log_{2}(1 + 1/x) log 2 ( 1 + 1/ x ) ): for every S S S and every c > 1 + δ − ( S ) / 2 c > 1 + \delta^{-}(S)/2 c > 1 + δ − ( S ) /2 , almost every odd n n n has a T S − T^{-}_{S} T S − -orbit that contains a number smaller than n c n^{c} n c .
The Collatz map at the top
The maps T S − T^{-}_{S} T S − look rather different from the Collatz map, but the largest of them is the Collatz map in disguise.
Proposition 6.1. For every x ≥ 1 x \ge1 x ≥ 1 , T S − ( x ) = G S ( x − 1 ) + 1 T^{-}_{S}(x) = G_{S}(x-1) + 1 T S − ( x ) = G S ( x − 1 ) + 1 , where G S G_{S} G S is the map of the nonnegative integers
G S ( y ) = { y / 2 , y even , ( 3 y + 1 ) / 2 , y odd and m ∈ S , ⌊ y / 2 m ⌋ , y odd and m ∉ S , m = v 2 ( y + 1 ) . G_{S}(y) =
\begin{cases}
y/2, & y\ \text{even},\\
(3y+1)/2, & y\ \text{odd and }m \in S,\\
\lfloor y/2^{m}\rfloor, & y\ \text{odd and }m \notin S,
\end{cases}
\qquad m = v_{2}(y+1). G S ( y ) = ⎩ ⎨ ⎧ y /2 , ( 3 y + 1 ) /2 , ⌊ y / 2 m ⌋ , y even , y odd and m ∈ S , y odd and m ∈ / S , m = v 2 ( y + 1 ) . In particular G N G_{\mathbb{N}} G N is the Collatz map T T T , and T N − ( x ) = T ( x − 1 ) + 1 T^{-}_{\mathbb{N}}(x) = T(x-1) + 1 T N − ( x ) = T ( x − 1 ) + 1 .
Proof. If x x x is odd, then y = x − 1 y = x - 1 y = x − 1 is even and T S − ( x ) = ( x + 1 ) / 2 = y / 2 + 1 T^{-}_{S}(x) = (x + 1)/2 = y/2 + 1 T S − ( x ) = ( x + 1 ) /2 = y /2 + 1 . If x = 2 m k x = 2^{m}k x = 2 m k with m ≥ 1 m \ge1 m ≥ 1 and k k k odd, then y = x − 1 y = x - 1 y = x − 1 is odd with v 2 ( y + 1 ) = m v_{2}(y + 1) = m v 2 ( y + 1 ) = m ; if m ∈ S m \in S m ∈ S , then T S − ( x ) = 3 x / 2 = ( 3 y + 1 ) / 2 + 1 T^{-}_{S}(x) = 3x/2 = (3y + 1)/2 + 1 T S − ( x ) = 3 x /2 = ( 3 y + 1 ) /2 + 1 , and otherwise T S − ( x ) = k = ( y + 1 ) / 2 m = ⌊ y / 2 m ⌋ + 1 T^{-}_{S}(x) = k = (y + 1)/2^{m} = \lfloor y/2^{m}\rfloor+ 1 T S − ( x ) = k = ( y + 1 ) / 2 m = ⌊ y / 2 m ⌋ + 1 .
For odd y y y , m = v 2 ( y + 1 ) m=v_2(y+1) m = v 2 ( y + 1 ) is the length of the final block of ones in the binary expansion of y y y , and ⌊ y / 2 m ⌋ \lfloor y/2^m\rfloor ⌊ y / 2 m ⌋ deletes this block. For example, y = 23 = 10111 2 y=23=10111_2 y = 23 = 1011 1 2 ends in a block of three ones, so m = 3 m=3 m = 3 ; if 3 ∈ S 3\in S 3 ∈ S then G S ( 23 ) = ( 3 ⋅ 23 + 1 ) / 2 = 35 G_S(23)=(3\cdot23+1)/2=35 G S ( 23 ) = ( 3 ⋅ 23 + 1 ) /2 = 35 , and otherwise G S ( 23 ) = ⌊ 23 / 8 ⌋ = 2 = 10 2 G_S(23)=\lfloor23/8\rfloor=2=10_2 G S ( 23 ) = ⌊ 23/8 ⌋ = 2 = 1 0 2 . Thus T S − T_S^{-} T S − is, up to the shift by one, the Collatz map in which an odd number ending in a block of exactly m m m ones is sent to ( 3 y + 1 ) / 2 (3y+1)/2 ( 3 y + 1 ) /2 only when m ∈ S m\in S m ∈ S , and otherwise loses that block. The fixed point 1 1 1 and the cycle ( 2 , 3 ) (2,3) ( 2 , 3 ) of T N − T_{\mathbb{N}}^{-} T N − are the Collatz cycles ( 0 ) (0) ( 0 ) and ( 1 , 2 ) (1,2) ( 1 , 2 ) , and the Collatz conjecture is equivalent to the statement that every T N − T_{\mathbb{N}}^{-} T N − -orbit of a number x ≥ 2 x\ge2 x ≥ 2 reaches ( 2 , 3 ) (2,3) ( 2 , 3 ) .
Remark 6.2 (A partial transfer). G [ 1 , b ] G_{[1,b]} G [ 1 , b ] agrees with T T T except at the odd numbers that end in at least b + 1 b+1 b + 1 ones, that is, at y ≡ − 1 ( m o d 2 b + 1 ) y\equiv-1\pmod{2^{b+1}} y ≡ − 1 ( mod 2 b + 1 ) . Hence a Collatz orbit that never meets such a number is, after the shift, an orbit of T [ 1 , b ] − T_{[1,b]}^{-} T [ 1 , b ] − . Consequently, if for every b b b every orbit of T [ 1 , b ] − T_{[1,b]}^{-} T [ 1 , b ] − is eventually periodic, then every divergent Collatz orbit contains numbers that end in arbitrarily long blocks of ones.
An elementary criterion
The simplest situation is that no odd step can increase a number. By (7) , an odd step maps x x x to U S − ( x ) = ( 3 r S ( M ) / 2 M + 1 ) ( x + 1 ) U_S^{-}(x)=(3^{r_S(M)}/2^{M+1})(x+1) U S − ( x ) = ( 3 r S ( M ) / 2 M + 1 ) ( x + 1 ) , and the following criterion asks that all these factors be smaller than 1 1 1 .
Proposition 6.3. For S ⊆ N S\subseteq\mathbb{N} S ⊆ N the following are equivalent:
(i) 3 r S ( M ) < 2 M + 1 3^{r_S(M)}<2^{M+1} 3 r S ( M ) < 2 M + 1 for every M ≥ 0 M\ge0 M ≥ 0 ;
(ii) no odd step of T S − T_S^{-} T S − increases a positive integer, that is, U S − ( x ) ≤ x U_S^{-}(x)\le x U S − ( x ) ≤ x for every odd x ≥ 1 x\ge1 x ≥ 1 ;
(iii) S S S contains no set [ c , ∞ ) [c,\infty) [ c , ∞ ) , and ( 3 / 2 ) L < 2 a (3/2)^L<2^a ( 3/2 ) L < 2 a for every maximal run [ a , a + L − 1 ] ⊆ S [a,a+L-1]\subseteq S [ a , a + L − 1 ] ⊆ S of consecutive integers.
If they hold, then U S − ( x ) < x U_S^{-}(x)<x U S − ( x ) < x for every odd x > 3 x>3 x > 3 , and every T S − T_S^{-} T S − -orbit of a positive integer reaches the fixed point 1 1 1 or, if 1 ∈ S 1\in S 1 ∈ S , the cycle ( 2 , 3 ) (2,3) ( 2 , 3 ) . They hold in particular if q ( S ) = sup M ≥ 0 3 r S ( M ) / 2 M + 1 < 1 q(S)=\sup_{M\ge0}3^{r_S(M)}/2^{M+1}<1 q ( S ) = sup M ≥ 0 3 r S ( M ) / 2 M + 1 < 1 .
Proof. For odd x x x write x + 1 = 2 M + 1 k x+1=2^{M+1}k x + 1 = 2 M + 1 k with M = M − ( x ) M=M^{-}(x) M = M − ( x ) and k k k odd, and let r = r S ( M ) r=r_S(M) r = r S ( M ) ; then U S − ( x ) = 3 r k U_S^{-}(x)=3^rk U S − ( x ) = 3 r k . If (i) holds, then 3 r k < 2 M + 1 k = x + 1 3^rk<2^{M+1}k=x+1 3 r k < 2 M + 1 k = x + 1 , which gives (ii). If (i) fails for some M M M , then 3 r > 2 M + 1 3^r>2^{M+1} 3 r > 2 M + 1 , and x = 2 M + 1 − 1 x=2^{M+1}-1 x = 2 M + 1 − 1 satisfies M − ( x ) = M M^{-}(x)=M M − ( x ) = M and U S − ( x ) = 3 r > x U_S^{-}(x)=3^r>x U S − ( x ) = 3 r > x ; so (ii) implies (i).
For the equivalence of (i) and (iii): r S ( M ) = 0 r_S(M)=0 r S ( M ) = 0 for M ∉ S M\notin S M ∈ / S , which gives the factor 2 − ( M + 1 ) ≤ 1 / 2 2^{-(M+1)}\le1/2 2 − ( M + 1 ) ≤ 1/2 ; along a run [ a , a + L − 1 ] [a,a+L-1] [ a , a + L − 1 ] the factor 3 M − a + 1 / 2 M + 1 3^{M-a+1}/2^{M+1} 3 M − a + 1 / 2 M + 1 increases with M M M and is largest at the end of the run, where it equals ( 3 / 2 ) L 2 − a (3/2)^L2^{-a} ( 3/2 ) L 2 − a ; and if [ c , ∞ ) ⊆ S [c,\infty)\subseteq S [ c , ∞ ) ⊆ S , then r S ( M ) ≥ M − c + 1 r_S(M)\ge M-c+1 r S ( M ) ≥ M − c + 1 , so the factor tends to infinity. Now assume (i). Then U S − ( x ) = x U_S^{-}(x)=x U S − ( x ) = x means k ( 2 M + 1 − 3 r ) = 1 k(2^{M+1}-3^r)=1 k ( 2 M + 1 − 3 r ) = 1 , so k = 1 k=1 k = 1 and 2 M + 1 − 1 = 3 r 2^{M+1}-1=3^r 2 M + 1 − 1 = 3 r . For M ≥ 2 M\ge2 M ≥ 2 this is impossible, since 2 M + 1 − 1 ≡ 7 ( m o d 8 ) 2^{M+1}-1\equiv7\pmod8 2 M + 1 − 1 ≡ 7 ( mod 8 ) while 3 r ≡ 1 3^r\equiv1 3 r ≡ 1 or 3 ( m o d 8 ) 3\pmod8 3 ( mod 8 ) . So either M = r = 0 M=r=0 M = r = 0 and x = 1 x=1 x = 1 , or M = r = 1 M=r=1 M = r = 1 , 1 ∈ S 1\in S 1 ∈ S and x = 3 x=3 x = 3 . Hence the odd elements of every orbit decrease strictly until they reach 1 1 1 or 3 3 3 ; and U S − ( 3 ) = 3 r S ( 1 ) U_S^{-}(3)=3^{r_S(1)} U S − ( 3 ) = 3 r S ( 1 ) is 3 3 3 if 1 ∈ S 1\in S 1 ∈ S , when 3 ↦ 2 ↦ 3 3\mapsto2\mapsto3 3 ↦ 2 ↦ 3 , and 1 1 1 otherwise. Finally, q ( S ) < 1 q(S)<1 q ( S ) < 1 clearly implies (i). □
By (iii), a run starting at a a a is allowed if and only if its length is at most ⌊ a / log 2 ( 3 / 2 ) ⌋ = ⌊ 1.7095 … a ⌋ \lfloor a/\log_2(3/2)\rfloor=\lfloor1.7095\ldots a\rfloor ⌊ a / log 2 ( 3/2 )⌋ = ⌊ 1.7095 … a ⌋ . The criterion therefore holds, for instance, for S = ∅ S=\varnothing S = ∅ and S = { 1 } S=\{1\} S = { 1 } ; for every S S S without two consecutive elements, such as the even numbers, the odd numbers and the squares; for the primes, whose only run of length two, { 2 , 3 } \{2,3\} { 2 , 3 } , gives ( 3 / 2 ) 2 < 2 2 (3/2)^2<2^2 ( 3/2 ) 2 < 2 2 ; for the longest allowed runs starting at a = 2 , 3 , 4 , 10 a=2,3,4,10 a = 2 , 3 , 4 , 10 , which are { 2 , 3 , 4 } \{2,3,4\} { 2 , 3 , 4 } , [ 3 , 7 ] [3,7] [ 3 , 7 ] , [ 4 , 9 ] [4,9] [ 4 , 9 ] and [ 10 , 26 ] [10,26] [ 10 , 26 ] ; and for every set made of allowed runs with gaps between them, such as { 2 , 3 , 4 } ∪ [ 6 , 15 ] ∪ { 20 } \{2,3,4\}\cup[6,15]\cup\{20\} { 2 , 3 , 4 } ∪ [ 6 , 15 ] ∪ { 20 } . It fails for { 1 , 2 } \{1,2\} { 1 , 2 } , for every [ 1 , b ] [1,b] [ 1 , b ] with b ≥ 2 b\ge2 b ≥ 2 , for { 2 , 3 , 4 , 5 } \{2,3,4,5\} { 2 , 3 , 4 , 5 } , and for every S S S that contains a set [ c , ∞ ) [c,\infty) [ c , ∞ ) , in particular for N \mathbb{N} N .
When the criterion fails, some odd step increases x x x , and a 2-adic integer repeats that step forever. Indeed, if 3 r > 2 M + 1 3^r > 2^{M+1} 3 r > 2 M + 1 for r = r S ( M ) r = r_S(M) r = r S ( M ) , then the step x ↦ 3 r ( x + 1 ) / 2 M + 1 x \mapsto3^r(x+1)/2^{M+1} x ↦ 3 r ( x + 1 ) / 2 M + 1 , taken on the class M − ( x ) = M M^-(x) = M M − ( x ) = M , has the fixed point x ∗ = − 3 r / ( 3 r − 2 M + 1 ) x^* = -3^r/(3^r - 2^{M+1}) x ∗ = − 3 r / ( 3 r − 2 M + 1 ) , a negative rational number with odd denominator and M − ( x ∗ ) = M M^-(x^*) = M M − ( x ∗ ) = M . For S = { 1 , 2 } S = \{1,2\} S = { 1 , 2 } and M = 2 M = 2 M = 2 this is the step x ↦ 9 ( x + 1 ) / 8 x \mapsto9(x+1)/8 x ↦ 9 ( x + 1 ) /8 , taken at x ≡ 7 ( m o d 16 ) x \equiv7 \pmod{16} x ≡ 7 ( mod 16 ) , with x ∗ = − 9 x^* = -9 x ∗ = − 9 ; for S = { 2 , 3 , 4 , 5 } S = \{2,3,4,5\} S = { 2 , 3 , 4 , 5 } and M = 5 M = 5 M = 5 it is the step x ↦ 81 ( x + 1 ) / 64 x \mapsto81(x+1)/64 x ↦ 81 ( x + 1 ) /64 , with x ∗ = − 81 / 17 x^* = -81/17 x ∗ = − 81/17 . Integers close to x ∗ x^* x ∗ imitate it: under T { 1 , 2 } − T_{\{1,2\}}^- T { 1 , 2 } − the first nine odd steps of 2 30 − 9 2^{30}-9 2 30 − 9 all take the step at M = 2 M = 2 M = 2 and lead to 9 j 2 30 − 3 j − 9 9j2^{30-3j}-9 9 j 2 30 − 3 j − 9 , j ≤ 9 j \le9 j ≤ 9 , so that the number grows from 30 to 31.5 bits. Recall that on a residue class modulo 2 K 2^K 2 K that determines the first j j j valuations, the j j j -th iterate of U S − U_S^- U S − is affine with multiplier 3 a / 2 b 3^a/2^b 3 a / 2 b ; following Terras [30 ] , the class has a coefficient stopping time if 3 a / 2 b < 1 3^a/2^b < 1 3 a / 2 b < 1 for some such j j j , and then all sufficiently large elements of the class eventually decrease. Along the residue classes that contain x ∗ x^* x ∗ every determined step has multiplier 3 r / 2 M + 1 > 1 3^r/2^{M+1} > 1 3 r / 2 M + 1 > 1 , so no residue class modulo 2 K 2^K 2 K that contains x ∗ x^* x ∗ has a coefficient stopping time, for any K K K , just as for the Collatz map and the point − 1 -1 − 1 . Under the criterion, on the other hand, already the first step has multiplier less than 1 on every class. So the criterion holds exactly when every odd 2-adic integer lies in a residue class with a coefficient stopping time; when it fails, the descent of all orbits cannot be proved from residue classes alone. These maps form the part of the family between the elementary cases and the Collatz map.
Numerical results
We checked, with the method of § 7.1 , that for each of the seven sets S S S in Table 6.1 every n < 2 34 n < 2^{34} n < 2 34 has an eventually periodic T S − T_S^- T S − -orbit, and that the only cycles with smallest element below 2 34 2^{34} 2 34 are the fixed point C ∅ − ( 1 ) = ( 1 ) C_\varnothing^-(1) = (1) C ∅ − ( 1 ) = ( 1 ) and, when 1 ∈ S 1 \in S 1 ∈ S , the cycle C ∅ − ( 2 ) = ( 2 , 3 ) C_\varnothing^-(2) = (2,3) C ∅ − ( 2 ) = ( 2 , 3 ) . An odd starting value drops at the first step, so long glides and high peaks come from even starting values 2 m k 2^m k 2 m k with m m m in a long run of S S S ; even so, no glide is longer than 279 steps, and no orbit gets above 2 54 2^{54} 2 54 . The drift measured on random 4096-bit starting values agrees with δ − ( S ) \delta^-(S) δ − ( S ) to two or three digits.
Table 6.1. Maps T S − T_S^- T S − checked for all n < 2 34 n < 2^{34} n < 2 34 : ρ ( S ) \rho(S) ρ ( S ) , the drift δ − ( S ) \delta^-(S) δ − ( S ) and the drift measured on 100 random 4096-bit starting values (followed until they have at most 2048 bits), the quantity q ( S ) q(S) q ( S ) of Theorem 6.3, the longest glide (in steps) and the highest peak (in bits). The only cycles with smallest element below 2 34 2^{34} 2 34 are C ∅ − ( 1 ) = ( 1 ) C_\varnothing^-(1) = (1) C ∅ − ( 1 ) = ( 1 ) and, for 1 ∈ S 1 \in S 1 ∈ S , C ∅ − ( 2 ) = ( 2 , 3 ) C_\varnothing^-(2) = (2,3) C ∅ − ( 2 ) = ( 2 , 3 ) . The last row is the Collatz map, for comparison.
Beyond these seven maps, a search over all sets S S S at once (Section A) shows that for every S ⊆ N S \subseteq\mathbb{N} S ⊆ N the only cycles of T S − T_S^- T S − with smallest element below 10 6 10^6 1 0 6 are C ∅ − ( 1 ) C_\varnothing^-(1) C ∅ − ( 1 ) and C ∅ − ( 2 ) C_\varnothing^-(2) C ∅ − ( 2 ) . So, unlike the maps T S T_S T S (Tables A.2 and 5.1), the maps T S − T_S^- T S − seem to have no cycles besides the shifted cycles of the Collatz map.
Branching maps
Theorem 2.2 compares single maps only pointwise and says nothing about their orbits. To compare orbits we let the map vary along the orbit. One may think of a player who chooses at each step which member of a family to apply (compare the Collatz game of [1 ] ); a family is bounded if no strategy drives any starting value to infinity. Since every orbit of every member is one possible play, boundedness is a statement about all members at once, and it passes from a family to smaller families.
Definitions
Definition 7.1. A branching family is a finite nonempty set S \mathcal{S} S of subsets of N \mathbb{N} N . For x ∈ N x \in\mathbb{N} x ∈ N let N S ( x ) = { T S ( x ) : S ∈ S } N_{\mathcal{S}}(x) = \{T_S(x) : S \in\mathcal{S}\} N S ( x ) = { T S ( x ) : S ∈ S } . A branch from n n n is a sequence n = x 0 , x 1 , x 2 , … n = x_0, x_1, x_2, \ldots n = x 0 , x 1 , x 2 , … with x t + 1 ∈ N S ( x t ) x_{t+1} \in N_{\mathcal{S}}(x_t) x t + 1 ∈ N S ( x t ) , and the reachable set R S ( n ) R_{\mathcal{S}}(n) R S ( n ) is the set of all numbers on branches from n n n . The family is bounded if R S ( n ) R_{\mathcal{S}}(n) R S ( n ) is finite for every n n n , and unbounded otherwise.
The member applied may change at every step, also in the middle of a run of multiplications by 3 / 2 3/2 3/2 . Each T S T_S T S -orbit with S ∈ S S \in\mathcal{S} S ∈ S is a branch, so in a bounded family every member has only eventually periodic orbits. The definition extends verbatim to positive rationals with odd denominators. One could also allow a choice at odd numbers, between ( 3 x + 1 ) / 2 (3x + 1)/2 ( 3 x + 1 ) /2 and ( x + 1 ) / 2 (x + 1)/2 ( x + 1 ) /2 , by admitting maps T S − T_S^- T S − as members; we do not consider such families here.
Lemma 7.2. Let S − = ⋂ S ∈ S S S^- = \bigcap_{S\in\mathcal{S}} S S − = ⋂ S ∈ S S and S + = ⋃ S ∈ S S S^+ = \bigcup_{S\in\mathcal{S}} S S + = ⋃ S ∈ S S . For odd x x x , N S ( x ) = { ( 3 x + 1 ) / 2 } N_{\mathcal{S}}(x) = \{(3x + 1)/2\} N S ( x ) = {( 3 x + 1 ) /2 } ; for x = 2 m k x = 2^m k x = 2 m k with m ≥ 1 m \ge1 m ≥ 1 , N S ( x ) N_{\mathcal{S}}(x) N S ( x ) contains 3 x / 2 3x/2 3 x /2 if and only if m ∈ S + m \in S^+ m ∈ S + , and contains k k k if and only if m ∉ S − m \notin S^- m ∈ / S − . Consequently R S = R { S − , S + } R_{\mathcal{S}} = R_{\{S^-,S^+\}} R S = R { S − , S + } .
Proof. T S ( x ) = 3 x / 2 T_S(x) = 3x/2 T S ( x ) = 3 x /2 for some S ∈ S S \in\mathcal{S} S ∈ S iff m ∈ S + m \in S^+ m ∈ S + , and T S ( x ) = k T_S(x) = k T S ( x ) = k for some S ∈ S S \in\mathcal{S} S ∈ S iff m ∉ S − m \notin S^- m ∈ / S − .
We therefore write ⟨ S − , S + ⟩ \langle S^-, S^+\rangle ⟨ S − , S + ⟩ for the family { S − , S + } \{S^-, S^+\} { S − , S + } , S − ⊆ S + S^- \subseteq S^+ S − ⊆ S + : at an exponent in S − S^- S − the multiplication is forced, at an exponent in S + ∖ S − S^+ \setminus S^- S + ∖ S − there is a choice, and outside S + S^+ S + the division is forced. A single map is ⟨ S , S ⟩ \langle S, S\rangle ⟨ S , S ⟩ , and for example { ∅ , { 2 } , { 3 } } \{\varnothing, \{2\}, \{3\}\} { ∅ , { 2 } , { 3 }} is equivalent to ⟨ ∅ , { 2 , 3 } ⟩ \langle\varnothing, \{2, 3\}\rangle ⟨ ∅ , { 2 , 3 }⟩ . As in Theorem 2.1, the odd numbers reachable from an odd x x x in one odd step are 3 j Syr ( x ) 3^j\operatorname{Syr}(x) 3 j Syr ( x ) with j j j in
J ( M ) = { j ∈ { 0 , … , M } : M − i ∈ S + for 0 ≤ i < j , and j = M or M − j ∉ S − } , M = M ( x ) . (9) J(M) = \{j \in\{0,\ldots,M\}: M-i \in S^+ \text{ for } 0 \le i < j,\text{ and } j=M \text{ or } M-j \notin S^-\}, \quad M=M(x). \tag*{(9)} J ( M ) = { j ∈ { 0 , … , M } : M − i ∈ S + for 0 ≤ i < j , and j = M or M − j ∈ / S − } , M = M ( x ) . (9)
For example, in ⟨ ∅ , { 1 } ⟩ \langle\varnothing, \{1\}\rangle ⟨ ∅ , { 1 }⟩ the odd number x = 17 x=17 x = 17 has M = 1 M=1 M = 1 and J ( 1 ) = { 0 , 1 } J(1)=\{0,1\} J ( 1 ) = { 0 , 1 } , so both 13 = Syr ( 17 ) 13=\operatorname{Syr}(17) 13 = Syr ( 17 ) and 39 = 3 Syr ( 17 ) 39=3\operatorname{Syr}(17) 39 = 3 Syr ( 17 ) are reachable from 17 17 17 in one odd step.
Lemma 7.3. R S ( n ) R_{\mathcal{S}}(n) R S ( n ) is infinite if and only if there is a branch from n n n consisting of pairwise distinct numbers; such a branch tends to infinity.
Proof. Each number has at most two successors. If R S ( n ) R_{\mathcal{S}}(n) R S ( n ) is infinite, the tree obtained by attaching each element of R S ( n ) ∖ { n } R_{\mathcal{S}}(n) \setminus\{n\} R S ( n ) ∖ { n } to the element from which a breadth-first search first reaches it is infinite and locally finite, so by König’s lemma it has an infinite path from n n n , which is a branch with distinct terms. A sequence of distinct positive integers tends to infinity. The converse is clear. □
Transfer
Proposition 7.4 (Transfer principle). If A ′ ⊆ A ⊆ B ⊆ B ′ A' \subseteq A \subseteq B \subseteq B' A ′ ⊆ A ⊆ B ⊆ B ′ , then R ⟨ A , B ⟩ ( n ) ⊆ R ⟨ A ′ , B ′ ⟩ ( n ) R_{\langle A,B\rangle}(n) \subseteq R_{\langle A',B'\rangle}(n) R ⟨ A , B ⟩ ( n ) ⊆ R ⟨ A ′ , B ′ ⟩ ( n ) for every n n n . Hence, if ⟨ A ′ , B ′ ⟩ \langle A',B'\rangle ⟨ A ′ , B ′ ⟩ is bounded, then so is ⟨ A , B ⟩ \langle A,B\rangle ⟨ A , B ⟩ , and every orbit of every T S T_S T S with A ′ ⊆ S ⊆ B ′ A' \subseteq S \subseteq B' A ′ ⊆ S ⊆ B ′ is eventually periodic. Conversely, if some T S T_S T S with A ′ ⊆ S ⊆ B ′ A' \subseteq S \subseteq B' A ′ ⊆ S ⊆ B ′ has an unbounded orbit, then ⟨ A ′ , B ′ ⟩ \langle A',B'\rangle ⟨ A ′ , B ′ ⟩ is unbounded.
Proof. By Theorem 7.2, N ⟨ A , B ⟩ ( x ) ⊆ N ⟨ A ′ , B ′ ⟩ ( x ) N_{\langle A,B\rangle}(x) \subseteq N_{\langle A',B'\rangle}(x) N ⟨ A , B ⟩ ( x ) ⊆ N ⟨ A ′ , B ′ ⟩ ( x ) for every x x x .
Corollary 7.5. If the family ⟨ ∅ , { 3 } ⟩ \langle\varnothing,\{3\}\rangle ⟨ ∅ , { 3 }⟩ is bounded, then no orbit of the Collatz map diverges, and no orbit of T { 3 } T_{\{3\}} T { 3 } diverges.
Thus the branching families form a partially ordered set in which boundedness propagates downwards and unboundedness upwards, and single maps are the minimal elements. A proof that one family ⟨ S − , S + ⟩ \langle S^{-},S^{+}\rangle ⟨ S − , S + ⟩ is bounded would settle the eventual periodicity of all maps T S T_{S} T S with S − ⊆ S ⊆ S + S^{-}\subseteq S\subseteq S^{+} S − ⊆ S ⊆ S + simultaneously; when S + ∖ S − S^{+}\setminus S^{-} S + ∖ S − is infinite, these are uncountably many maps. A statement about a family is in general stronger than the corresponding statements about its members; the families of interest are those that are still plausibly bounded, or those that are unbounded although all their members are contracting.
A branching-random-walk heuristic
Recall that a branching random walk is a system of particles on the real line in which every particle of generation t t t , independently of the others, is replaced in generation t + 1 t+1 t + 1 by a random finite set of children, whose displacements relative to the parent have a fixed joint law. In the random model the odd numbers reachable from x x x form such a walk: a particle at position log 2 x \log_{2}x log 2 x has children at log 2 x + X j ( M ) \log_{2}x+X_{j}(M) log 2 x + X j ( M ) , j ∈ J ( M ) j\in J(M) j ∈ J ( M ) , where X j ( M ) = ( 1 + j ) log 2 3 − ( M + 1 ) X_{j}(M)=(1+j)\log_{2}3-(M+1) X j ( M ) = ( 1 + j ) log 2 3 − ( M + 1 ) and M M M is geometric as before. Let
Λ ( λ ) = E ∑ j ∈ J ( M ) 2 λ X j ( M ) = ∑ M ≥ 0 2 − ( M + 1 ) ∑ j ∈ J ( M ) 3 λ ( 1 + j ) 2 − λ ( M + 1 ) . \Lambda(\lambda)=\mathbb{E}\sum_{j\in J(M)}2^{\lambda X_{j}(M)}=\sum_{M\geq0}2^{-(M+1)}\sum_{j\in J(M)}3^{\lambda(1+j)}2^{-\lambda(M+1)}. Λ ( λ ) = E j ∈ J ( M ) ∑ 2 λ X j ( M ) = M ≥ 0 ∑ 2 − ( M + 1 ) j ∈ J ( M ) ∑ 3 λ ( 1 + j ) 2 − λ ( M + 1 ) .
Thus Λ ( λ ) \Lambda(\lambda) Λ ( λ ) is the expected value of ∑ 2 λ ⋅ ( d i s p l a c e m e n t ) \sum2^{\lambda\cdot(\mathrm{displacement})} ∑ 2 λ ⋅ ( displacement ) over the children of one particle, the analogue of the moment generating function of a single random walk; for a single map, Λ ( λ ) = E 2 λ X \Lambda(\lambda)=\mathbb{E}\,2^{\lambda X} Λ ( λ ) = E 2 λ X . By the theorem of Hammersley, Kingman and Biggins [11 , 12 , 5 ] (see also [28 ] ), the rightmost particle of such a walk moves at speed v = inf λ > 0 λ − 1 log 2 Λ ( λ ) v=\inf_{\lambda>0}\lambda^{-1}\log_{2}\Lambda(\lambda) v = inf λ > 0 λ − 1 log 2 Λ ( λ ) bits per generation (here the process survives forever, since J ( M ) J(M) J ( M ) always contains r S − ( M ) r_{S^{-}}(M) r S − ( M ) ). The heuristic predicts that ⟨ S − , S + ⟩ \langle S^{-},S^{+}\rangle ⟨ S − , S + ⟩ is unbounded if v > 0 v>0 v > 0 and bounded if v < 0 v<0 v < 0 ; equivalently, when v ≠ 0 v\ne0 v = 0 , bounded if and only if Λ ( λ ) < 1 \Lambda(\lambda)<1 Λ ( λ ) < 1 for some λ > 0 \lambda>0 λ > 0 . Within the model, one direction is elementary: the expected value of ∑ 2 λ ⋅ ( h e i g h t ) \sum2^{\lambda\cdot(\mathrm{height})} ∑ 2 λ ⋅ ( height ) over the particles of generation t t t , heights being measured from the starting point, is Λ ( λ ) t \Lambda(\lambda)^{t} Λ ( λ ) t , so by Markov’s inequality the expected number of particles of generation t ≥ 1 t\geq1 t ≥ 1 at height at least 0 is at most Λ ( λ ) t \Lambda(\lambda)^{t} Λ ( λ ) t . If Λ ( λ ) < 1 \Lambda(\lambda)<1 Λ ( λ ) < 1 , the expected total number of descendants that are at least as large as the starting value is at most Λ ( λ ) / ( 1 − Λ ( λ ) ) < ∞ \Lambda(\lambda)/(1-\Lambda(\lambda))<\infty Λ ( λ ) / ( 1 − Λ ( λ )) < ∞ ; this is the property checked numerically in Section 7.5 below. The heuristic treats the subtrees rooted at different children as independent, although the children Syr ( x ) \operatorname{Syr}(x) Syr ( x ) and 3 Syr ( x ) 3\operatorname{Syr}(x) 3 Syr ( x ) of x x x are determined by the same binary digits of x x x .
Table 7.1 shows the prediction for some families ⟨ ∅ , S ⟩ \langle\varnothing,S\rangle ⟨ ∅ , S ⟩ . Every member of these families is contracting, yet the first four families are predicted to be unbounded. The family ⟨ ∅ , { 3 } ⟩ \langle\varnothing,\{3\}\rangle ⟨ ∅ , { 3 }⟩ is predicted to be bounded, but only barely; by Theorem 7.5 its boundedness would imply that no Collatz orbit diverges. Figure 7.1 shows the two functions behind the table: Λ ( λ ) \Lambda(\lambda) Λ ( λ ) , which dips below 1 exactly for the three families predicted to be bounded, and λ − 1 log 2 Λ ( λ ) \lambda^{-1}\log_{2}\Lambda(\lambda) λ − 1 log 2 Λ ( λ ) , whose minimum is v v v .
Table 7.1. Branching-random-walk heuristic for families containing the Collatz map: expected number of children per odd step, Λ min = inf λ > 0 Λ ( λ ) \Lambda_{\min} = \inf_{\lambda> 0}\Lambda(\lambda) Λ m i n = inf λ > 0 Λ ( λ ) , and the speed v v v of the rightmost branch (bits per odd step).
Figure 7.1. The branching-random-walk heuristic for the families of Table 7.1 . Left: Λ ( λ ) \Lambda(\lambda) Λ ( λ ) , with its minimum Λ min \Lambda_{\min} Λ m i n marked; a family is predicted to be bounded if Λ ( λ ) < 1 \Lambda(\lambda) < 1 Λ ( λ ) < 1 for some λ > 0 \lambda> 0 λ > 0 . Right: λ − 1 log 2 Λ ( λ ) \lambda^{-1}\log_2\Lambda(\lambda) λ − 1 log 2 Λ ( λ ) , whose minimum is the speed v v v of the rightmost branch, labelled by S + S^+ S + . The curves on the left start at Λ ( 0 ) = E ∣ J ( M ) ∣ > 1 \Lambda(0) = \mathbb{E}\lvert J(M)\rvert> 1 Λ ( 0 ) = E ∣ J ( M )∣ > 1 , so those on the right tend to + ∞ +\infty + ∞ as λ → 0 \lambda\to0 λ → 0 .
The family ⟨ ∅ , { 1 } ⟩ \langle\varnothing,\{1\}\rangle ⟨ ∅ , { 1 }⟩
Here the choice occurs exactly at the odd numbers x ≡ 1 ( m o d 8 ) x\equiv1\pmod8 x ≡ 1 ( mod 8 ) (where M ( x ) = 1 M(x)=1 M ( x ) = 1 ), whose two successors are ( 3 x + 1 ) / 4 (3x+1)/4 ( 3 x + 1 ) /4 and 3 ( 3 x + 1 ) / 4 3(3x+1)/4 3 ( 3 x + 1 ) /4 ; every other odd x x x has the single successor Syr ( x ) \operatorname{Syr}(x) Syr ( x ) . Both members, the Collatz map and T { 1 } T_{\{1\}} T { 1 } , are contracting.
Numerics. Among n ≤ 2000 n\leq2000 n ≤ 2000 , an exhaustive search shows that 417 have a finite reachable set, and for each of the other 1583 it finds a branch exceeding 2 300 2^{300} 2 300 (so these reachable sets are presumably infinite). Among odd x < 2 16 x < 2^{16} x < 2 16 there are 1345 with a finite reachable set (for each of the others the search found a branch exceeding 2 400 2^{400} 2 400 or more than 3 ⋅ 10 5 3 \cdot10^5 3 ⋅ 1 0 5 reachable numbers). Their number in [ 2 k − 1 , 2 k ) [2^{k-1}, 2^k) [ 2 k − 1 , 2 k ) grows by a factor of about 1.5 per step in k k k , so they appear to have density zero, with roughly N 0.58 N^{0.58} N 0.58 of them below N N N . A beam search that keeps the 10 4 10^4 1 0 4 largest numbers in each generation reaches 1861 bits after 3000 odd steps from 27, that is 0.62 bits per odd step, against v = 0.639 v = 0.639 v = 0.639 .
A positive-drift rule. We now show rigorously that branches of positive drift exist for almost every 2-adic starting point. For D ≥ 3 D \ge3 D ≥ 3 and a set Δ \Delta Δ of residues modulo 2 D 2^D 2 D that are ≡ 1 ( m o d 8 ) \equiv1 \pmod{8} ≡ 1 ( mod 8 ) , let
ψ Δ ( x ) = { ( 3 x + 1 ) / 4 , x ≡ 1 ( m o d 8 ) and x m o d 2 D ∈ Δ , 3 ( 3 x + 1 ) / 4 , x ≡ 1 ( m o d 8 ) and x m o d 2 D ∉ Δ , Syr ( x ) , otherwise. \psi_{\Delta}(x) =
\begin{cases}
(3x+1)/4, & x \equiv1 \pmod{8}\text{ and }x \bmod2^D \in\Delta,\\
3(3x+1)/4, & x \equiv1 \pmod{8}\text{ and }x \bmod2^D \notin\Delta,\\
\operatorname{Syr}(x), & \text{otherwise.}
\end{cases} ψ Δ ( x ) = ⎩ ⎨ ⎧ ( 3 x + 1 ) /4 , 3 ( 3 x + 1 ) /4 , Syr ( x ) , x ≡ 1 ( mod 8 ) and x mod 2 D ∈ Δ , x ≡ 1 ( mod 8 ) and x mod 2 D ∈ / Δ , otherwise.
so that ψ Δ ( x ) = 3 e ( x ) − 1 ( 3 x + 1 ) / 2 b ( x ) \psi_{\Delta}(x) = 3^{e(x)-1}(3x+1)/2^{b(x)} ψ Δ ( x ) = 3 e ( x ) − 1 ( 3 x + 1 ) / 2 b ( x ) with b ( x ) = v 2 ( 3 x + 1 ) b(x) = v_2(3x+1) b ( x ) = v 2 ( 3 x + 1 ) and e ( x ) ∈ { 1 , 2 } e(x) \in\{1,2\} e ( x ) ∈ { 1 , 2 } . Every ψ Δ \psi_{\Delta} ψ Δ -orbit of an odd integer consists of odd numbers on one branch of ⟨ ∅ , { 1 } ⟩ \langle\varnothing, \{1\}\rangle ⟨ ∅ , { 1 }⟩ .
The rule ψ Δ \psi_{\Delta} ψ Δ depends only on x m o d 2 D x \bmod2^D x mod 2 D . The next lemma says that, for a random 2-adic x x x , the
residue of the next odd number is determined by the current residue together with fresh, independent binary digits of x x x , so that the residues form a Markov chain.
Lemma 7.6. Let x x x be μ \mu μ -distributed, x t = ψ Δ t ( x ) x_t = \psi_\Delta^t(x) x t = ψ Δ t ( x ) , s t = x t m o d 2 D s_t = x_t \bmod2^D s t = x t mod 2 D and b t = b ( x t ) b_t = b(x_t) b t = b ( x t ) . Then ( s t ) (s_t) ( s t ) is a Markov chain on the 2 D − 1 2^{D-1} 2 D − 1 odd residues modulo 2 D 2^D 2 D . If v = v 2 ( 3 s + 1 ) < D v = v_2(3s+1) < D v = v 2 ( 3 s + 1 ) < D , then from s s s it moves with probability 2 − v 2^{-v} 2 − v to each of the 2 v 2^v 2 v residues s ′ s' s ′ with s ′ ≡ 3 e ( s ) − 1 ( 3 s + 1 ) / 2 v ( m o d 2 D − v ) s' \equiv3^{e(s)-1}(3s+1)/2^v \pmod{2^{D-v}} s ′ ≡ 3 e ( s ) − 1 ( 3 s + 1 ) / 2 v ( mod 2 D − v ) , and b t = v b_t=v b t = v . If 3 s + 1 ≡ 0 ( m o d 2 D ) 3s+1\equiv0\pmod{2^D} 3 s + 1 ≡ 0 ( mod 2 D ) , then s t + 1 s_{t+1} s t + 1 is uniformly distributed and independent of b t b_t b t , and P ( b t = D + i ) = 2 − ( i + 1 ) \mathbb{P}(b_t=D+i)=2^{-(i+1)} P ( b t = D + i ) = 2 − ( i + 1 ) for i ≥ 0 i\geq0 i ≥ 0 .
Proof. As in Theorem 3.1, by induction on t t t : for every finite history h = ( s 0 , b 0 , … , s t − 1 , b t − 1 , s t ) h=(s_0,b_0,\ldots,s_{t-1},b_{t-1},s_t) h = ( s 0 , b 0 , … , s t − 1 , b t − 1 , s t ) the set of x x x realizing h h h is a residue class modulo 2 D + b 0 + ⋯ + b t − 1 2^{D+b_0+\cdots+b_{t-1}} 2 D + b 0 + ⋯ + b t − 1 that ψ Δ t \psi_\Delta^t ψ Δ t maps affinely onto the class s t m o d 2 D s_t\bmod2^D s t mod 2 D , multiplying μ \mu μ by 2 b 0 + ⋯ + b t − 1 2^{b_0+\cdots+b_{t-1}} 2 b 0 + ⋯ + b t − 1 . Hence P ( h ) = 2 − ( D − 1 ) 2 − ( b 0 + ⋯ + b t − 1 ) \mathbb{P}(h)=2^{-(D-1)}2^{-(b_0+\cdots+b_{t-1})} P ( h ) = 2 − ( D − 1 ) 2 − ( b 0 + ⋯ + b t − 1 ) , and the conditional probability of each continuation ( b t , s t + 1 ) (b_t,s_{t+1}) ( b t , s t + 1 ) compatible with s t s_t s t is 2 − b t 2^{-b_t} 2 − b t , which depends only on s t s_t s t .
Theorem 7.7. Let ψ = ψ Δ \psi=\psi_\Delta ψ = ψ Δ with D = 5 D=5 D = 5 and Δ = { 9 } \Delta=\{9\} Δ = { 9 } , that is: at x ≡ 1 ( m o d 8 ) x\equiv1\pmod8 x ≡ 1 ( mod 8 ) take ( 3 x + 1 ) / 4 (3x+1)/4 ( 3 x + 1 ) /4 if x ≡ 9 ( m o d 32 ) x\equiv9\pmod{32} x ≡ 9 ( mod 32 ) and 3 ( 3 x + 1 ) / 4 3(3x+1)/4 3 ( 3 x + 1 ) /4 otherwise. For μ \mu μ -almost every x x x ,
1 t ∑ i < t e ( x i ) → 20 17 , 1 t ∑ i < t b ( x i ) → 30 17 . \frac{1}{t}\sum_{i<t}e(x_i)\to\frac{20}{17},\qquad\frac{1}{t}\sum_{i<t}b(x_i)\to\frac{30}{17}. t 1 i < t ∑ e ( x i ) → 17 20 , t 1 i < t ∑ b ( x i ) → 17 30 . so that 1 t ∑ i < t ( e ( x i ) log 2 3 − b ( x i ) ) → 10 17 log 2 9 8 = 0.09995 … > 0 \frac{1}{t}\sum_{i<t}(e(x_i)\log_2 3-b(x_i))\to\frac{10}{17}\log_2\frac{9}{8}=0.09995\ldots>0 t 1 ∑ i < t ( e ( x i ) log 2 3 − b ( x i )) → 17 10 log 2 8 9 = 0.09995 … > 0 .
Proof. By Theorem 7.6, ( s t ) (s_t) ( s t ) is a Markov chain on the 16 odd residues modulo 32, with the transitions listed in Table 7.2 . It is irreducible (from every state one reaches 5, and from 5 every state) and aperiodic (5 → \to → 5). (To read the table: from s = 3 s=3 s = 3 we have 3 s + 1 = 10 3s+1=10 3 s + 1 = 10 , so b = 1 b=1 b = 1 and the next residue is congruent to 5 modulo 16, that is, 5 or 21, each with probability 1 / 2 1/2 1/2 ; from s = 1 s=1 s = 1 , where e = 2 e=2 e = 2 , the next residue is congruent to 3 ( 3 s + 1 ) / 4 = 3 3(3s+1)/4=3 3 ( 3 s + 1 ) /4 = 3 modulo 8.) One checks directly that its stationary distribution is π ( s ) = 8 / 136 , 9 / 136 , 6 / 136 , 11 / 136 \pi(s)=8/136,9/136,6/136,11/136 π ( s ) = 8/136 , 9/136 , 6/136 , 11/136 for s ≡ 1 , 3 , 5 , 7 ( m o d 8 ) s\equiv1,3,5,7\pmod8 s ≡ 1 , 3 , 5 , 7 ( mod 8 ) respectively. The process ( s t , b t ) (s_t,b_t) ( s t , b t ) is a positive recurrent Markov chain on a countable set (by Theorem 7.6, the conditional law of ( b t , s t + 1 ) (b_t,s_{t+1}) ( b t , s t + 1 ) given the past depends only on s t s_t s t ), so by the ergodic theorem the averages converge almost surely to
Table 7.2. The Markov chain of Theorem 7.7 : state s s s (odd residue modulo 32), exponent e e e , valuation b = v 2 ( 3 s + 1 ) b=v_{2}(3s+1) b = v 2 ( 3 s + 1 ) , the states reached (each with probability 2 − b 2^{-b} 2 − b ; “all” means all 16 states with probability 1 / 16 1/16 1/16 each), and 136 π ( s ) 136\pi(s) 136 π ( s ) .
∑ s π ( s ) e ( s ) = 1 + 3 ⋅ 8 136 = 20 17 (the residues 1, 17, 25 have e = 2 ), \sum_s\pi(s)e(s)=1+3\cdot\frac{8}{136}=\frac{20}{17}\qquad\text{(the residues 1, 17, 25 have }e=2\text{),} s ∑ π ( s ) e ( s ) = 1 + 3 ⋅ 136 8 = 17 20 (the residues 1, 17, 25 have e = 2 ),
∑ s π ( s ) E ( b t ∣ s t = s ) = 80 136 ⋅ 1 + 32 136 ⋅ 2 + 12 136 ⋅ 3 + 6 136 ⋅ 4 + 6 136 ⋅ 6 = 240 136 = 30 17 . \sum_s\pi(s)\mathbb{E}(b_t\mid s_t=s)=\frac{80}{136}\cdot1+\frac{32}{136}\cdot2+\frac{12}{136}\cdot3+\frac{6}{136}\cdot4+\frac{6}{136}\cdot6=\frac{240}{136}=\frac{30}{17}. s ∑ π ( s ) E ( b t ∣ s t = s ) = 136 80 ⋅ 1 + 136 32 ⋅ 2 + 136 12 ⋅ 3 + 136 6 ⋅ 4 + 136 6 ⋅ 6 = 136 240 = 17 30 .
Finally 20 17 log 2 3 − 30 17 = 10 17 ( 2 log 2 3 − 3 ) = 10 17 log 2 9 8 \frac{20}{17}\log_2 3-\frac{30}{17}=\frac{10}{17}(2\log_2 3-3)=\frac{10}{17}\log_2\frac{9}{8} 17 20 log 2 3 − 17 30 = 17 10 ( 2 log 2 3 − 3 ) = 17 10 log 2 8 9 .
The rule is easy to understand from Table 7.2 . At x ≡ 9 ( m o d 32 ) x\equiv9\pmod{32} x ≡ 9 ( mod 32 ) the step up would lead to a number ≡ 5 ( m o d 8 ) \equiv5\pmod8 ≡ 5 ( mod 8 ) , whose next odd step removes at least three factors 2 (b ≥ 3 b\geq3 b ≥ 3 ), while the step down leads to a number ≡ 7 ( m o d 8 ) \equiv7\pmod8 ≡ 7 ( mod 8 ) , which loses only one factor 2. At x ≡ 17 ( m o d 32 ) x\equiv17\pmod{32} x ≡ 17 ( mod 32 ) the situation is reversed: the step down leads to a number ≡ 5 ( m o d 8 ) \equiv5\pmod8 ≡ 5 ( mod 8 ) and the step up to a number ≡ 7 ( m o d 8 ) \equiv7\pmod8 ≡ 7 ( mod 8 ) . So the rule uses the choice to steer the orbit away from residues with large valuations, at the price of giving up a factor 3 at x ≡ 9 ( m o d 32 ) x\equiv9\pmod{32} x ≡ 9 ( mod 32 ) . For example, from 41 ≡ 9 ( m o d 32 ) 41\equiv9\pmod{32} 41 ≡ 9 ( mod 32 ) the step down leads to 31 and then to 47, the step up to 93 and then to 35. Figure 7.2 follows the rule and the two members of the family from one starting value.
Figure 7.2. Three branches of ⟨ ∅ , { 1 } ⟩ \langle\varnothing,\{1\}\rangle ⟨ ∅ , { 1 }⟩ from the same random odd 256-bit starting value: the Collatz map (always the step down), T { 1 } T_{\{1\}} T { 1 } (always the step up) and the rule ψ \psi ψ of Theorem 7.7 . Dashed: lines with slopes log 2 3 − 2 \log_{2}3-2 log 2 3 − 2 , 5 4 log 2 3 − 2 \frac{5}{4}\log_{2}3-2 4 5 log 2 3 − 2 and 10 17 log 2 9 8 \frac{10}{17}\log_{2}\frac{9}{8} 17 10 log 2 8 9 . The Collatz orbit reaches 1 after 746 odd steps; after 3000 odd steps T { 1 } T_{\{1\}} T { 1 } has lost 22 bits and ψ \psi ψ has gained 198, against 56 and 300 predicted (over 300 random 256-bit starting values the gain of ψ \psi ψ has mean 297 and standard deviation 82 bits).
Remark 7.8. The rule of Theorem 7.7 was found by solving the average-reward Markov decision problem in which the choice may depend on x m o d 2 D x\bmod2^D x mod 2 D . The optimal drifts are − 0.0188 -0.0188 − 0.0188 for D = 4 D=4 D = 4 (always choosing 3 ( 3 x + 1 ) / 4 3(3x+1)/4 3 ( 3 x + 1 ) /4 , i.e. the map T { 1 } T_{\{1\}} T { 1 } , is optimal), and + 0.1000 , + 0.1784 , + 0.1901 , + 0.2156 , +0.1000,+0.1784,+0.1901,+0.2156, + 0.1000 , + 0.1784 , + 0.1901 , + 0.2156 ,
+ 0.2613 +0.2613 + 0.2613 , + 0.2928 +0.2928 + 0.2928 , + 0.3185 +0.3185 + 0.3185 , + 0.3414 +0.3414 + 0.3414 , + 0.3602 +0.3602 + 0.3602 , + 0.3773 +0.3773 + 0.3773 for D = 5 , … , 14 D=5,\ldots,14 D = 5 , … , 14 . Thus five bits of the current number suffice for positive drift, and four do not. For D = 6 D=6 D = 6 the optimal rule takes ( 3 x + 1 ) / 4 (3x+1)/4 ( 3 x + 1 ) /4 exactly when x m o d 64 ∈ { 1 , 9 , 41 } x\bmod64\in\{1,9,41\} x mod 64 ∈ { 1 , 9 , 41 } ; the same proof, with a chain on 32 states, gives the stationary averages 20 17 \frac{20}{17} 17 20 and 86 51 \frac{86}{51} 51 86 and the drift ( 60 log 2 3 − 86 ) / 51 = 0.1784 … (60\log_{2}3-86)/51=0.1784\ldots ( 60 log 2 3 − 86 ) /51 = 0.1784 … .
Remark 7.9. Taking the step up whenever some member of the family allows it gives the single map T S + T_{S+} T S + , and taking the step down whenever possible gives T S − T_{S-} T S − (Theorem 7.2). Neither decides whether the family is bounded: for ⟨ ∅ , { 1 } ⟩ \langle\varnothing,\{1\}\rangle ⟨ ∅ , { 1 }⟩ both T { 1 } T_{\{1\}} T { 1 } and the Collatz map are contracting, while the rule of Theorem 7.7 , which sometimes takes the step down, has positive drift. A step up changes which steps follow, so the greedy choice is not the one that grows fastest.
Theorem 7.10. For every ε > 0 \varepsilon>0 ε > 0 , the set of odd n n n for which R ⟨ ∅ , { 1 } ⟩ ( n ) R_{\langle\varnothing,\{1\}\rangle}(n) R ⟨ ∅ , { 1 }⟩ ( n ) contains a number larger than n ( 2 / 3 ) log 2 3 − ε n^{(2/3)\log_{2}3-\varepsilon} n ( 2/3 ) l o g 2 3 − ε has density one; here ( 2 / 3 ) log 2 3 = log 8 9 = 1.0566 … (2/3)\log_{2}3=\log_{8}9=1.0566\ldots ( 2/3 ) log 2 3 = log 8 9 = 1.0566 … With the 6-bit rule of
Theorem 7.8 the exponent improves to ( 30 / 43 ) log 2 3 = 1.1057 … (30/43)\log_{2} 3 = 1.1057\ldots ( 30/43 ) log 2 3 = 1.1057 … ; a numerical computation of the stationary averages of the optimal 14-bit rule gives about 1.233.
The exponent has the following origin. The residue of n n n modulo 2 K 2^{K} 2 K determines about K / b ˉ K/\bar{b} K / b ˉ steps of the rule, where b ˉ = 30 / 17 \bar{b}=30/17 b ˉ = 30/17 is the average number of factors 2 removed per step; during these steps the factors 2 removed use up the roughly log 2 n \log_{2}n log 2 n bits of n n n , while the factors 3 gained contribute about e ˉ log 2 3 \bar{e}\log_{2}3 e ˉ log 2 3 bits per step, e ˉ = 20 / 17 \bar{e}=20/17 e ˉ = 20/17 . With K ≈ log 2 n K\approx\log_{2}n K ≈ log 2 n this gives about ( e ˉ / b ˉ ) log 2 3 ⋅ log 2 n (\bar{e}/\bar{b})\log_{2}3\cdot\log_{2}n ( e ˉ / b ˉ ) log 2 3 ⋅ log 2 n bits.
Proof. Let e ˉ = 20 / 17 \bar{e}=20/17 e ˉ = 20/17 and b ˉ = 30 / 17 \bar{b}=30/17 b ˉ = 30/17 be the limits in Theorem 7.7 , fix ε > 0 \varepsilon>0 ε > 0 and consider odd n ∈ ( N / 2 , N ] n\in(N/2,N] n ∈ ( N /2 , N ] . Let t = ⌊ ( 1 − 2 ε ) log 2 N / ( b ˉ + ε ) ⌋ t=\lfloor(1-2\varepsilon)\log_{2}N/(\bar{b}+\varepsilon)\rfloor t = ⌊( 1 − 2 ε ) log 2 N / ( b ˉ + ε )⌋ , and let G G G be the set of x ∈ Z 2 × x\in\mathbb{Z}_{2}^{\times} x ∈ Z 2 × with ∣ ∑ i < t e ( x i ) − t e ˉ ∣ ≤ ε t \left|\sum_{i<t}e(x_i)-t\bar{e}\right|\leq\varepsilon t ∑ i < t e ( x i ) − t e ˉ ≤ εt and ∣ ∑ i < t b ( x i ) − t b ˉ ∣ ≤ ε t \left|\sum_{i<t}b(x_i)-t\bar{b}\right|\leq\varepsilon t ∑ i < t b ( x i ) − t b ˉ ≤ εt . By Theorem 7.7 , μ ( G ) → 1 \mu(G)\to1 μ ( G ) → 1 . By the proof of Theorem 7.6, G G G is a union of residue classes modulo 2 D + ∑ i < t b ( x i ) 2^{D+\sum_{i<t}b(x_i)} 2 D + ∑ i < t b ( x i ) , hence modulo 2 D + ( 1 − 2 ε ) log 2 N 2^{D+(1-2\varepsilon)\log_{2}N} 2 D + ( 1 − 2 ε ) l o g 2 N , and as in the proof of Theorem 4.1 the proportion of odd n ∈ ( N / 2 , N ] n\in(N/2,N] n ∈ ( N /2 , N ] lying in G G G tends to 1. For such n n n , by (4) applied to each step,
x t ≥ n 3 ∑ e ( x i ) 2 ∑ b ( x i ) ≥ 3 t ( e ˉ − ε ) x_t \geq n\frac{3^{\sum e(x_i)}}{2^{\sum b(x_i)}} \geq3^{t(\bar{e}-\varepsilon)} x t ≥ n 2 ∑ b ( x i ) 3 ∑ e ( x i ) ≥ 3 t ( e ˉ − ε )
for N N N large, because 2 ∑ b ( x i ) ≤ 2 ( 1 − 2 ε ) log 2 N < n 2^{\sum b(x_i)}\leq2^{(1-2\varepsilon)\log_{2}N}<n 2 ∑ b ( x i ) ≤ 2 ( 1 − 2 ε ) l o g 2 N < n . Since t ≥ ( 1 − 3 ε ) log 2 n / ( b ˉ + ε ) t\geq(1-3\varepsilon)\log_{2}n/(\bar{b}+\varepsilon) t ≥ ( 1 − 3 ε ) log 2 n / ( b ˉ + ε ) for large N N N , we get log 2 x t ≥ ( 1 − 3 ε ) ( e ˉ − ε ) b ˉ + ε log 2 3 ⋅ log 2 n \log_{2}x_t\geq\frac{(1-3\varepsilon)(\bar{e}-\varepsilon)}{\bar{b}+\varepsilon}\log_{2}3\cdot\log_{2}n log 2 x t ≥ b ˉ + ε ( 1 − 3 ε ) ( e ˉ − ε ) log 2 3 ⋅ log 2 n , and e ˉ / b ˉ = 2 / 3 \bar{e}/\bar{b}=2/3 e ˉ / b ˉ = 2/3 . The number x t x_t x t lies on a branch from n n n . The other exponents are obtained in the same way from the stationary averages of the corresponding rules.
Theorem 7.10 does not show that ⟨ ∅ , { 1 } ⟩ \langle\varnothing,\{1\}\rangle ⟨ ∅ , { 1 }⟩ is unbounded: the large numbers it produces might all belong to the exceptional set of density zero. The following computation shows that residue classes alone cannot settle the question.
Proposition 7.11. Every odd residue class modulo 2 10 2^{10} 2 10 , and hence every odd residue class modulo 2 L 2^{L} 2 L for L ≤ 10 L\leq10 L ≤ 10 , contains a positive rational number y = p / q y=p/q y = p / q , q q q odd, whose reachable set under ⟨ ∅ , { 1 } ⟩ \langle\varnothing,\{1\}\rangle ⟨ ∅ , { 1 }⟩ is finite. The denominators can be chosen at most 2187 and the reachable sets have at most 73 odd elements. For example, 41 / 9 ≡ 33 ( m o d 256 ) 41/9\equiv33\pmod{256} 41/9 ≡ 33 ( mod 256 ) , and
41 9 ↦ 11 3 or 11 , 11 3 ↦ 3 or 9. \frac{41}{9}\mapsto\frac{11}{3}\text{ or }11,\qquad\frac{11}{3}\mapsto3\text{ or }9. 9 41 ↦ 3 11 or 11 , 3 11 ↦ 3 or 9. where 3, 9 and 11 have finite reachable sets; R ( 41 / 9 ) R(41/9) R ( 41/9 ) has 24 odd elements. Explicitly, the odd elements of R ( 41 / 9 ) R(41/9) R ( 41/9 ) are 41 / 9 41/9 41/9 , 11 / 3 11/3 11/3 and the 22 integers 1, 3, 5, 7, 9, 11, 13, 17, 19, 21, 29, 39, 59, 67, 85, 89, 101, 151, 201, 227, 341, 453. Thus 41 / 9 41/9 41/9 lies in the residue class of 33 modulo 2 8 2^{8} 2 8 but has a finite reachable set, while integers with a finite reachable set appear to be rare.
Proof. For a rational y = p / q y=p/q y = p / q the odd-to-odd steps of the family act on the numerator as p ↦ ( 3 p + q ) / 2 ν 2 ( 3 p + q ) p\mapsto(3p+q)/2^{\nu_{2}(3p+q)} p ↦ ( 3 p + q ) / 2 ν 2 ( 3 p + q ) , with the extra choice p ↦ 3 ( 3 p + q ) / 4 p\mapsto3(3p+q)/4 p ↦ 3 ( 3 p + q ) /4 when ν 2 ( 3 p + q ) = 2 \nu_{2}(3p+q)=2 ν 2 ( 3 p + q ) = 2 . For each class we found p , q p,q p , q by a computer search and then enumerated the reachable set with exact rational arithmetic. The lists of witnesses are in the ancillary files.
To state the consequence, call a nonempty set C C C of odd residue classes modulo 2 L 2^{L} 2 L a growth certificate if there are γ > 1 \gamma>1 γ > 1 and, for every c ∈ C c\in C c ∈ C , a finite decision tree that reads further binary digits of x ∈ c x\in c x ∈ c and chooses moves of the family, such that every x ∈ c x\in c x ∈ c is led along a branch to a number x ′ x' x ′ with x ′ m o d 2 L ∈ C x'\bmod2^{L}\in C x ′ mod 2 L ∈ C and x ′ ≥ γ x x'\geq\gamma x x ′ ≥ γ x , where the last inequality is derived from the multipliers 3 e / 2 b 3^{e}/2^{b} 3 e / 2 b and (4) , so that it holds for all positive x x x in c c c . A growth certificate would show that every positive integer in a class of C C C has an unbounded branch. In other words, a growth certificate is a finite strategy, based on residues, that guarantees growth by the factor γ \gamma γ from every number in a class of C C C .
Corollary 7.12. There is no growth certificate for ⟨ ∅ , { 1 } ⟩ \langle\varnothing, \{1\}\rangle ⟨ ∅ , { 1 }⟩ modulo 2 L 2^{L} 2 L with L ≤ 10 L \le10 L ≤ 10 .
Proof. A certificate modulo 2 L 2^{L} 2 L with L ≤ 10 L \le10 L ≤ 10 is also one modulo 2 10 2^{10} 2 10 . Applied to the rational y y y of Theorem 7.11 in a class of C C C , it would produce numbers ≥ γ k y \ge\gamma^{k}y ≥ γ k y in R ( y ) R(y) R ( y ) for every k k k , contradicting finiteness.
For L = 12 L=12 L = 12 we found such rational witnesses in 501 of the 512 classes ≡ 1 ( m o d 8 ) \equiv1 \pmod{8} ≡ 1 ( mod 8 ) . A direct search for certificates in which the trees read at most 8 extra digits and make at most 40 odd steps, landing on classes ≡ 1 ( m o d 8 ) \equiv1 \pmod{8} ≡ 1 ( mod 8 ) , found none for L = 12 L=12 L = 12 and L = 14 L=14 L = 14 : the largest self-sustaining set of classes is empty. Within these bounds the search is exhaustive; in particular it never reached its limit on the number of nodes (2 ⋅ 10 6 2 \cdot10^{6} 2 ⋅ 1 0 6 per class).
The family ⟨ ∅ , { 3 } ⟩ ⟩ \langle\varnothing, \{3\}\rangle\rangle ⟨ ∅ , { 3 }⟩⟩
Here the choice occurs at odd x x x with M ( x ) = 3 M(x)=3 M ( x ) = 3 , i.e. x ≡ 5 ( m o d 32 ) x \equiv5 \pmod{32} x ≡ 5 ( mod 32 ) , between Syr ( x ) \operatorname{Syr}(x) Syr ( x ) and 3 Syr ( x ) 3\operatorname{Syr}(x) 3 Syr ( x ) . We checked by induction that every n < 10 8 n<10^{8} n < 1 0 8 has a finite reachable set: for every odd n n n , the set of numbers ≥ n \ge n ≥ n reachable from n n n without passing below n n n is finite. This suffices: by induction on n n n , every branch from n n n either stays in this finite set or passes below n n n , and every branch from an even number passes below it within two steps. The largest such set has 2431 elements (for n = 37,537,407 n=37{,}537{,}407 n = 37 , 537 , 407 ), and the largest climb is 31 bits (from n = 4,196,607 n=4{,}196{,}607 n = 4 , 196 , 607 ). In a simulation of the branching random walk of § 9.3 , the probability that the maximum climbs at least 30 bits before all branches fall below the start is about 10 − 7 10^{-7} 1 0 − 7 , so for 5 ⋅ 10 7 5 \cdot10^{7} 5 ⋅ 1 0 7 odd starting values one expects a largest climb of 30 to 34 bits, in agreement with the data.
Unified maps
The maps T S T_S T S and T ‾ S \overline{T}_S T S agree at even numbers and differ at odd numbers, which all go up under T S T_S T S and all go down under T ‾ S \overline{T}_S T S . We now let the direction at odd numbers depend on a 2-adic valuation as well. For odd x x x we use v 2 ( x + 1 ) v_2(x+1) v 2 ( x + 1 ) , the number of binary digits 1 at the end of x x x ; it is the exponent M − ( x ) + 1 M^{-}(x)+1 M − ( x ) + 1 of § 8 . The question is whether the maps between the two families behave in a new way. The computations below suggest that they do not, and that a single exponent decides: if the odd numbers x ≡ 1 ( m o d 4 ) x \equiv1 \pmod{4} x ≡ 1 ( mod 4 ) , those with v 2 ( x + 1 ) = 1 v_2(x+1)=1 v 2 ( x + 1 ) = 1 , go down, a map behaves like the maps (Section 8.4), and if they go up, like the maps T S T_S T S (§ 10.5 ).
Definition 8.1. For S o , S e ⊆ N S_o,S_e \subseteq\mathbb{N} S o , S e ⊆ N let T S o , S e : N → N T_{S_o,S_e}\colon\mathbb{N}\to\mathbb{N} T S o , S e : N → N be
T S o , S e ( x ) = { ( 3 x + 1 ) / 2 , x odd , m ∈ S o , ( x + 1 ) / 2 , x odd , m ∉ S o , 3 x / 2 , x even , m ∈ S e , k , x even , m ∉ S e , (10) T_{S_o,S_e}(x)=
\begin{cases}
(3x+1)/2, & x\ \text{odd},\ m\in S_o,\\
(x+1)/2, & x\ \text{odd},\ m\notin S_o,\\
3x/2, & x\ \text{even},\ m\in S_e,\\
k, & x\ \text{even},\ m\notin S_e,
\end{cases} \tag*{(10)} T S o , S e ( x ) = ⎩ ⎨ ⎧ ( 3 x + 1 ) /2 , ( x + 1 ) /2 , 3 x /2 , k , x odd , m ∈ S o , x odd , m ∈ / S o , x even , m ∈ S e , x even , m ∈ / S e , (10)
where x + 1 = 2 m k x+1=2^{m}k x + 1 = 2 m k if x x x is odd and x = 2 m k x=2^{m}k x = 2 m k if x x x is even, with m ≥ 1 m\ge1 m ≥ 1 and k k k odd.
Thus S o S_o S o is the set of exponents at which odd numbers go up and S e S_e S e the set of exponents at which even numbers go up, and
T S = T N , S , T ‾ S = T ∅ , S . T_S=T_{\mathbb{N},S},\qquad\overline{T}_S=T_{\varnothing,S}. T S = T N , S , T S = T ∅ , S .
We call T S o , S e T_{S_o,S_e} T S o , S e mixed if S o ≠ ∅ S_o\ne\varnothing S o = ∅ and S o ≠ N S_o\ne\mathbb{N} S o = N ; the mixed maps belong to neither family. Since ( 3 x + 1 ) / 2 > ( x + 1 ) / 2 (3x+1)/2>(x+1)/2 ( 3 x + 1 ) /2 > ( x + 1 ) /2 and 3 x / 2 > k 3x/2>k 3 x /2 > k , Theorem 2.2 extends: T S o , S e ≤ T S o ′ , S e ′ T_{S_o,S_e}\le T_{S'_o,S'_e} T S o , S e ≤ T S o ′ , S e ′ pointwise if S o ⊆ S o ′ S_o\subseteq S'_o S o ⊆ S o ′ and S e ⊆ S e ′ S_e \subseteq S'_e S e ⊆ S e ′ . The family runs from T ∅ , ∅ = T ∅ T_{\varnothing,\varnothing}=T_{\varnothing} T ∅ , ∅ = T ∅ , whose orbits all decrease to 1, to T N , N = T N T_{N,N}=T_N T N , N = T N , whose orbits all diverge, and it contains the Collatz map twice: as T N , ∅ = T ∅ T_{N,\varnothing}=T_{\varnothing} T N , ∅ = T ∅ and, after the shift by one of Theorem 6.1, as T ∅ , N = T N T_{\varnothing,N}=T_N T ∅ , N = T N . For example,
T { 2 } , ∅ T_{\{2\},\varnothing} T { 2 } , ∅ : 27, 41, 21, 11, 17, 9, 5, 3, 5, . . .
T { 1 } , [ 1 , 3 ] T_{\{1\},[1,3]} T { 1 } , [ 1 , 3 ] : 37, 56, 84, 126, 189, 284, 426, 639, 320, 5, 8, 12, 18, 27, 14, 21, 32, 1, 2, 3, 2, . . .
The first orbit ends in the cycle (3, 5), in which 3 goes up (v 2 ( 4 ) = 2 ∈ S o v_2(4)=2\in S_o v 2 ( 4 ) = 2 ∈ S o ) and 5 goes down (v 2 ( 6 ) = 1 ∉ S o v_2(6)=1\notin S_o v 2 ( 6 ) = 1 ∈ / S o ); so (3, 5) is a cycle of no map T S T_S T S and of no map T S − T^-_S T S − . The second orbit ends in the cycle (2, 3) of Section 6. Theorem 8.3 below explains why the two cycles are closely related.
The block map
Since ( 3 x + 1 ) / 2 + 1 = 3 2 ( x + 1 ) (3x+1)/2+1=\frac{3}{2}(x+1) ( 3 x + 1 ) /2 + 1 = 2 3 ( x + 1 ) , a step up acts in the same way at odd and at even numbers: in the notation of Theorem 8.1 it replaces 2 m k 2^m k 2 m k by 2 m − 1 ⋅ 3 k 2^{m-1}\cdot3k 2 m − 1 ⋅ 3 k , and the parity of the number is kept as long as m ≥ 2 m\geq2 m ≥ 2 (for m = 1 m=1 m = 1 an odd x x x goes up to the even number 3 k − 1 3k-1 3 k − 1 , and an even x x x to the odd number 3 k 3k 3 k ). So at odd numbers, too, a run of steps up passes through the exponents m , m − 1 , … m,m-1,\ldots m , m − 1 , … , and the run of consecutive elements of S o S_o S o that ends at m m m decides how many steps up are taken. Under T S T_S T S every odd x x x goes up, and x x x is followed by m − 1 m-1 m − 1 further odd numbers. A step down at an odd x x x gives ( x + 1 ) / 2 = 2 m − 1 k (x+1)/2=2^{m-1}k ( x + 1 ) /2 = 2 m − 1 k : it lowers the exponent by one, as a step up does, and for m ≥ 2 m\geq2 m ≥ 2 hands the even number 2 m − 1 k 2^{m-1}k 2 m − 1 k over to the rules for even numbers. A step down at an even number gives its odd part at once.
Lemma 8.2. Let x x x be odd, x + 1 = 2 m k x+1=2^m k x + 1 = 2 m k with k k k odd, and r = r S o ( m ) r=r_{S_o}(m) r = r S o ( m ) . The T S o , S e T_{S_o,S_e} T S o , S e -orbit of x x x begins with the r r r steps up x i ↦ x i + 1 x_i\mapsto x_{i+1} x i ↦ x i + 1 , 0 ≤ i < r 0\leq i<r 0 ≤ i < r , where x i = 2 m − i 3 i k − 1 x_i=2^{m-i}3^i k-1 x i = 2 m − i 3 i k − 1 . Let
y = { ( x r + 1 ) / 2 = 2 m − r − 1 3 r k , r < m , x r = 3 m k − 1 , r = m , y=\begin{cases}
(x_r+1)/2=2^{m-r-1}3^r k, & r<m,\\
x_r=3^m k-1, & r=m,
\end{cases} y = { ( x r + 1 ) /2 = 2 m − r − 1 3 r k , x r = 3 m k − 1 , r < m , r = m , which is the next term of the orbit if r < m r<m r < m and equal to x r x_r x r if r = m r=m r = m , and write y = 2 M k ′ y=2^M k' y = 2 M k ′ with M ≥ 0 M\geq0 M ≥ 0 and k ′ k' k ′ odd. Then the orbit of x x x reaches the odd number
U S o , S e ( x ) = 3 r S e ( M ) k ′ (11) U_{S_o,S_e}(x)=3^{r_{S_e}(M)}k' \tag*{(11)} U S o , S e ( x ) = 3 r S e ( M ) k ′ (11) after ℓ = r + [ r < m ] + r S e ( M ) + [ r S e ( M ) < M ] \ell=r+[r<m]+r_{S_e}(M)+[r_{S_e}(M)<M] ℓ = r + [ r < m ] + r S e ( M ) + [ r S e ( M ) < M ] steps; all terms after x r x_r x r and before U S o , S e ( x ) U_{S_o,S_e}(x) U S o , S e ( x ) are even. Explicitly,
U S o , S e ( x ) = { 3 r + r S e ( m − r − 1 ) ( x + 1 ) / 2 m , r < m , 3 r S e ( M ) ( 3 m ( x + 1 ) / 2 m − 1 ) / 2 M , r = m . U_{S_o,S_e}(x)=\begin{cases}
3^{r+r_{S_e}(m-r-1)}(x+1)/2^m, & r<m,\\
3^{r_{S_e}(M)}(3^m(x+1)/2^m-1)/2^M, & r=m.
\end{cases} U S o , S e ( x ) = { 3 r + r S e ( m − r − 1 ) ( x + 1 ) / 2 m , 3 r S e ( M ) ( 3 m ( x + 1 ) / 2 m − 1 ) / 2 M , r < m , r = m . Proof. By the rule above, the step up at x i x_i x i is taken if m − i ∈ S o m-i\in S_o m − i ∈ S o , and it leads to x i + 1 x_{i+1} x i + 1 . By (2.1), exactly r r r steps up are taken before the exponent reaches m − r m-r m − r , which is 0 if r = m r=m r = m and not in S o S_o S o if r < m r<m r < m ; in the second case x r x_r x r is odd and goes down to y y y . If M = 0 M=0 M = 0 , then y = k ′ y=k' y = k ′ is odd and ℓ = r + 1 \ell=r+1 ℓ = r + 1 . If M ≥ 1 M\geq1 M ≥ 1 , then by the last sentence of Theorem 2.1 the even number y = 2 M k ′ y=2^M k' y = 2 M k ′ reaches the odd number 3 r S e ( M ) k ′ 3^{r_{S_e}(M)}k' 3 r S e ( M ) k ′ after r S e ( M ) + [ r S e ( M ) < M ] r_{S_e}(M)+[r_{S_e}(M)<M] r S e ( M ) + [ r S e ( M ) < M ] steps, through even numbers. □
We call U S o , S e U_{S_o,S_e} U S o , S e the block map, and the part of an orbit from an odd number x x x to U S o , S e ( x ) U_{S_o,S_e}(x) U S o , S e ( x ) a block. For S o = ∅ S_o=\varnothing S o = ∅ we have r = 0 r=0 r = 0 , y = ( x + 1 ) / 2 y=(x+1)/2 y = ( x + 1 ) /2 and M = M − ( x ) M=M^-(x) M = M − ( x ) , so U ∅ , S e = U S − U_{\varnothing,S_e}=U^-_{S} U ∅ , S e = U S − by (6.1). For S o = N S_o=N S o = N we have r = m r=m r = m , and x 0 , … , x m − 1 x_0,\ldots,x_{m-1} x 0 , … , x m − 1 are consecutive odd numbers of the T S T_S T S -orbit, with M ( x i ) = 0 M(x_i)=0 M ( x i ) = 0 for i < m − 1 i<m-1 i < m − 1 and ( 3 x m − 1 + 1 ) / 2 = y = 2 M k ′ (3x_{m-1}+1)/2=y=2^M k' ( 3 x m − 1 + 1 ) /2 = y = 2 M k ′ , so that M ( x m − 1 ) = M M(x_{m-1})=M M ( x m − 1 ) = M and U N , S ( x ) = U S m ( x ) U_{N,S}(x)=U^m_S(x) U N , S ( x ) = U S m ( x ) : a block
of T S o , S e T_{S_o,S_e} T S o , S e consists of v 2 ( x + 1 ) v_2(x+1) v 2 ( x + 1 ) odd steps. In general y = 2 M k ′ y=2^M k' y = 2 M k ′ is the number at which the rules for even numbers take over; in the two families it is ( 3 x m − 1 + 1 ) / 2 = 2 M Syr ( x m − 1 ) (3x_{m-1}+1)/2=2^M\operatorname{Syr}(x_{m-1}) ( 3 x m − 1 + 1 ) /2 = 2 M Syr ( x m − 1 ) , as in § 4 , and ( x + 1 ) / 2 (x+1)/2 ( x + 1 ) /2 , as in § 8 . As in § 4.2 , (8.1) and (8.2) also make sense for positive rational numbers with odd denominator, and (8.2) for all x ∈ Z 2 x\in\mathbb{Z}_2 x ∈ Z 2 outside a countable set.
Remark 8.3 (Switching). In the case r < m r<m r < m , a block consists of r r r steps up at odd numbers, one step down at an odd number, and the steps at even numbers that follow: b = r S e ( M ) b=rS_e(M) b = r S e ( M ) steps up and, if b < M b<M b < M , a step down to the odd part. Every step up multiplies x i + 1 x_i+1 x i + 1 , or the even number, by 3 3 3 and the step down at the odd number x r x_r x r halves x r + 1 x_r+1 x r + 1 . So the block multiplies x + 1 x+1 x + 1 by 3 a / 2 2 m 3^a/2^{2m} 3 a / 2 2 m , where a = r + b a=r+b a = r + b is the number of steps up: for a given a a a , it does not matter where the step down at an odd number is taken. Moving this step within the block, by trading steps up at odd numbers for steps up at even numbers or conversely, changes neither the end of the block nor its number of steps, but only the numbers passed through, which are of the form 2 i 3 h k − 1 2^i3^{h}k-1 2 i 3 h k − 1 before the step down and 2 i 3 h k 2^i3^{h}k 2 i 3 h k after it. For example, x = 3 x=3 x = 3 has m = 2 m=2 m = 2 , and its block with a = 1 a=1 a = 1 is 3 → 5 → 3 3\to5\to3 3 → 5 → 3 if 2 ∈ S o 2\in S_o 2 ∈ S o and 1 ∉ S o 1\notin S_o 1 ∈ / S o , and 3 → 2 → 3 3\to2\to3 3 → 2 → 3 if 2 ∉ S o 2\notin S_o 2 ∈ / S o and 1 ∈ S e 1\in S_e 1 ∈ S e : these are the cycles ( 3 , 5 ) (3,5) ( 3 , 5 ) and ( 2 , 3 ) (2,3) ( 2 , 3 ) . Consequently, different pairs ( S o , S e ) (S_o,S_e) ( S o , S e ) can have the same block map; ( { 1 } , [ 1 , 3 ] ) \bigl(\{1\},[1,3]\bigr) ( { 1 } , [ 1 , 3 ] ) and ( { 1 , 3 } , [ 1 , 3 ] ) \bigl(\{1,3\},[1,3]\bigr) ( { 1 , 3 } , [ 1 , 3 ] ) are an example. We say that two cycles are in the same class if they differ only by such moves.
Cycles and a census
A cycle C C C of a map T S o , S e T_{S_o,S_e} T S o , S e determines four finite sets of exponents: the sets U o ( C ) U_o(C) U o ( C ) and D o ( C ) D_o(C) D o ( C ) of the exponents v 2 ( x + 1 ) v_2(x+1) v 2 ( x + 1 ) of the odd elements x ∈ C x\in C x ∈ C that go up and down, and the sets U e ( C ) U_e(C) U e ( C ) and D e ( C ) D_e(C) D e ( C ) of the exponents v 2 ( x ) v_2(x) v 2 ( x ) of the even elements that go up and down. As in Theorem A.1, C C C is a cycle of T S o , S e T_{S_o,S_e} T S o , S e if and only if
U o ( C ) ⊆ S o ⊆ N ∖ D o ( C ) and U e ( C ) ⊆ S e ⊆ N ∖ D e ( C ) . U_o(C)\subseteq S_o\subseteq\mathbb{N}\setminus D_o(C)\quad\text{and}\quad U_e(C)\subseteq S_e\subseteq\mathbb{N}\setminus D_e(C). U o ( C ) ⊆ S o ⊆ N ∖ D o ( C ) and U e ( C ) ⊆ S e ⊆ N ∖ D e ( C ) .
The + + + cycles of Section A are the cycles with D o ( C ) = ∅ D_o(C)=\varnothing D o ( C ) = ∅ , with U ( C ) = U e ( C ) U(C)=U_e(C) U ( C ) = U e ( C ) and D ( C ) = D e ( C ) D(C)=D_e(C) D ( C ) = D e ( C ) , and the − - − cycles are those with U o ( C ) = ∅ U_o(C)=\varnothing U o ( C ) = ∅ . Both kinds also occur in mixed maps: ( 1 , 2 ) (1,2) ( 1 , 2 ) , for instance, is a cycle of T S o , S e T_{S_o,S_e} T S o , S e whenever 1 ∈ S o 1\in S_o 1 ∈ S o and 1 ∉ S e 1\notin S_e 1 ∈ / S e , and ( 1 ) (1) ( 1 ) whenever 1 ∉ S o 1\notin S_o 1 ∈ / S o . We call C C C mixed if U o ( C ) U_o(C) U o ( C ) and D o ( C ) D_o(C) D o ( C ) are both nonempty; mixed cycles occur only in mixed maps. The simplest one is ( 3 , 5 ) (3,5) ( 3 , 5 ) , with U o = { 2 } U_o=\{2\} U o = { 2 } , D o = { 1 } D_o=\{1\} D o = { 1 } and no even elements, a cycle of T S o , S e T_{S_o,S_e} T S o , S e whenever 2 ∈ S o 2\in S_o 2 ∈ S o and 1 ∉ S o 1\notin S_o 1 ∈ / S o ; by Theorem 8.3 it is in the class of the − - − cycle ( 2 , 3 ) (2,3) ( 2 , 3 ) .
To find the cycles of all unified maps at once we extend the search of Section A. For each n n n we follow the orbits from n n n in which every exponent v 2 ( x + 1 ) v_2(x+1) v 2 ( x + 1 ) of an odd number and every exponent v 2 ( x ) v_2(x) v 2 ( x ) of an even number is assigned the step up or the step down when it first occurs, following both assignments; a branch is abandoned when it drops below n n n , when it exceeds a fixed bound (2 120 2^{120} 2 120 or 2 64 2^{64} 2 64 below), or when it enters a loop that does not contain n n n . This finds, exactly once, every cycle of every map T S o , S e T_{S_o,S_e} T S o , S e whose smallest element is n n n and whose largest element is below the bound. We searched the pairs with 1 ∉ S o 1\notin S_o 1 ∈ / S o and those with 1 ∈ S o 1\in S_o 1 ∈ S o separately; a cycle that does not meet the exponent 1 at an odd number, such as ( 2 , 3 ) (2,3) ( 2 , 3 ) , is found in both searches. As a check, the + + + cycles found are exactly those of Table A.2 below the same bounds, the − - − cycles are ( 1 ) (1) ( 1 ) and ( 2 , 3 ) (2,3) ( 2 , 3 ) , and every cycle was verified again, with its four sets, by an independent program. For counting, we also group the cycles into classes: two cycles are in the same class if and only if they start their blocks at the same odd numbers, in the same order and with the same case of Theorem 8.2 in each block.
The random model
The blocks of a random 2-adic integer are independent, as the odd steps are in Theorem 3.1. The odd x x x with v 2 ( x + 1 ) = m v_2(x+1)=m v 2 ( x + 1 ) = m form the residue class of 2 m − 1 2^m-1 2 m − 1 modulo 2 m + 1 2^{m+1} 2 m + 1 , of measure 2 − m 2^{-m} 2 − m . If r < m r<m r < m , the block map x ↦ 3 a ( x + 1 ) / 2 m x \mapsto3^{a}(x+1)/2^{m} x ↦ 3 a ( x + 1 ) / 2 m maps this class affinely onto Z 2 ∗ \mathbb{Z}_2^* Z 2 ∗ . If r = m r=m r = m , then k = ( x + 1 ) / 2 m k=(x+1)/2^m k = ( x + 1 ) / 2 m is uniformly distributed in Z 2 ∗ \mathbb{Z}_2^* Z 2 ∗ and y = 3 m k − 1 y=3^m k-1 y = 3 m k − 1 in 2 Z 2 2\mathbb{Z}_2 2 Z 2 , so the exponent M = v 2 ( y ) M=v_2(y) M = v 2 ( y ) is new, with P ( M = i ) = 2 − i \mathbb{P}(M=i)=2^{-i} P ( M = i ) = 2 − i for i ≥ 1 i\ge1 i ≥ 1 ; each set { v 2 ( x + 1 ) = m , v 2 ( y ) = M } \{v_2(x+1)=m,\ v_2(y)=M\} { v 2 ( x + 1 ) = m , v 2 ( y ) = M } is a residue class modulo 2 m + M + 1 2^{m+M+1} 2 m + M + 1 , which U S o , S e U_{S_o,S_e} U S o , S e maps affinely onto Z 2 ∗ \mathbb{Z}_2^* Z 2 ∗ . The induction in the proof of Theorem 3.1 then shows that for μ \mu μ -distributed x x x the exponents m i = v 2 ( x i + 1 ) m_i=v_2(x_i+1) m i = v 2 ( x i + 1 ) along the orbit x i + 1 = U S o , S e ( x i ) x_{i+1}=U_{S_o,S_e}(x_i) x i + 1 = U S o , S e ( x i ) are independent, with P ( m i = m ) = 2 − m \mathbb{P}(m_i=m)=2^{-m} P ( m i = m ) = 2 − m , and that the exponents M M M of the blocks with r = m r=m r = m are independent of them and of each other, with P ( M = i ) = 2 − i \mathbb{P}(M=i)=2^{-i} P ( M = i ) = 2 − i .
A block takes u = r + r S e ( M ) u=r+r_{S_e}(M) u = r + r S e ( M ) steps up and removes h h h factors 2, where h = m h=m h = m if r < m r<m r < m and h = m + M h=m+M h = m + M if r = m r=m r = m ; up to a correction of order 1 / x 1/x 1/ x , it changes log 2 x \log_2 x log 2 x by u log 2 3 − h u\log_2 3-h u log 2 3 − h . Since the blocks have different lengths, we count time in halvings, each of which uses up one binary digit of x x x (the set of x x x with a given block has measure 2 − h 2^{-h} 2 − h ), and measure the drift in bits per two halvings, the average number of halvings in an odd step of T S o T_{S_o} T S o and of T S e − T_{S_e}^{-} T S e − :
δ ( S o , S e ) = 2 ( σ log 2 3 − 1 ) , σ = σ ( S o , S e ) = E u E h . (12) \delta(S_o,S_e)=2(\sigma\log_2 3-1),\qquad\sigma=\sigma(S_o,S_e)=\frac{\mathbb{E}u}{\mathbb{E}h}. \tag*{(12)} δ ( S o , S e ) = 2 ( σ log 2 3 − 1 ) , σ = σ ( S o , S e ) = E h E u . (12)
Here E h = 2 + 2 π \mathbb{E}h=2+2\pi E h = 2 + 2 π , where π = ∑ m : [ 1 , m ] ⊆ S o 2 − m \pi=\sum_{m:[1,m]\subseteq S_o}2^{-m} π = ∑ m : [ 1 , m ] ⊆ S o 2 − m is the probability of the case r = m r=m r = m , and E u = ∑ m ≥ 1 2 − m u ˉ ( m ) \mathbb{E}u=\sum_{m\ge1}2^{-m}\bar{u}(m) E u = ∑ m ≥ 1 2 − m u ˉ ( m ) , where u ˉ ( m ) = r + r S e ( m − r − 1 ) \bar{u}(m)=r+r_{S_e}(m-r-1) u ˉ ( m ) = r + r S e ( m − r − 1 ) if r = r S o ( m ) < m r=r_{S_o}(m)<m r = r S o ( m ) < m , and u ˉ ( m ) = m + 2 ρ ( S e ) \bar{u}(m)=m+2\rho(S_e) u ˉ ( m ) = m + 2 ρ ( S e ) if r = m r=m r = m . For S o = N S_o=\mathbb{N} S o = N we get E h = 4 \mathbb{E}h=4 E h = 4 and E u = 2 + 2 ρ ( S e ) \mathbb{E}u=2+2\rho(S_e) E u = 2 + 2 ρ ( S e ) , and for S o = ∅ S_o=\varnothing S o = ∅ we get E h = 2 \mathbb{E}h=2 E h = 2 and E u = ρ ( S e ) \mathbb{E}u=\rho(S_e) E u = ρ ( S e ) ; so δ ( N , S ) = δ ( S ) \delta(\mathbb{N},S)=\delta(S) δ ( N , S ) = δ ( S ) and δ ( ∅ , S ) = δ − ( S ) \delta(\varnothing,S)=\delta^{-}(S) δ ( ∅ , S ) = δ − ( S ) . The sign of δ \delta δ is the sign of the drift per block, E u log 2 3 − E h \mathbb{E}u\log_2 3-\mathbb{E}h E u log 2 3 − E h , so T S o , S e T_{S_o,S_e} T S o , S e is contracting if and only if σ < log 3 2 = 0.6309 … \sigma<\log_3 2=0.6309\ldots σ < log 3 2 = 0.6309 … , that is, if a block takes on average fewer than 0.6309 steps up per halving. For example, σ ( { 1 } , [ 1 , 3 ] ) = 5 / 8 = σ ( N , { 1 } ) \sigma(\{1\},[1,3])=5/8=\sigma(\mathbb{N},\{1\}) σ ({ 1 } , [ 1 , 3 ]) = 5/8 = σ ( N , { 1 }) , so T { 1 } , [ 1 , 3 ] T_{\{1\},[1,3]} T { 1 } , [ 1 , 3 ] has the drift − 0.0188 -0.0188 − 0.0188 of T { 1 } T_{\{1\}} T { 1 } .
Proposition 8.4. If S o ⊆ S o ′ S_o\subseteq S'_o S o ⊆ S o ′ and S e ⊆ S e ′ S_e\subseteq S'_e S e ⊆ S e ′ , then σ ( S o , S e ) ≤ σ ( S o ′ , S e ′ ) \sigma(S_o,S_e)\le\sigma(S'_o,S'_e) σ ( S o , S e ) ≤ σ ( S o ′ , S e ′ ) . In particular, among all maps that contain a given cycle C C C , the map T U o ( C ) , U e ( C ) T_{U_o(C),U_e(C)} T U o ( C ) , U e ( C ) has the smallest drift.
Proof. It suffices to add one element s s s to one of the sets. If s s s is added to S e S_e S e , then no u ˉ ( m ) \bar{u}(m) u ˉ ( m ) decreases and E h \mathbb{E}h E h does not change. Let s s s be added to S o S_o S o , and let c c c be the smallest positive integer not in S o S_o S o , so that s ≥ c s\ge c s ≥ c . In the blocks with r = r S o ( m ) < m r=r_{S_o}(m)<m r = r S o ( m ) < m that remain in this case, r r r can only grow, and u ˉ ( m ) = r + r S e ( m − r − 1 ) \bar{u}(m)=r+r_{S_e}(m-r-1) u ˉ ( m ) = r + r S e ( m − r − 1 ) does not decrease when r r r grows, because r S e ( i ) ≤ r S e ( i − d ) + d r_{S_e}(i)\le r_{S_e}(i-d)+d r S e ( i ) ≤ r S e ( i − d ) + d for 0 ≤ d ≤ i 0\le d\le i 0 ≤ d ≤ i ; if s > c s>c s > c , these are the only changes, and E h \mathbb{E}h E h does not change. If s = c s=c s = c , the blocks with c ≤ m < c ′ c\le m<c' c ≤ m < c ′ , where c ′ > c c'>c c ′ > c is the next integer not in S o S_o S o (c ′ = ∞ c'=\infty c ′ = ∞ if there is none), pass from the case r < m r<m r < m , with u ˉ ( m ) ≤ m − 1 \bar{u}(m)\le m-1 u ˉ ( m ) ≤ m − 1 and h = m h=m h = m , to the case r = m r=m r = m , with u ˉ ( m ) = m + 2 ρ ( S e ) \bar{u}(m)=m+2\rho(S_e) u ˉ ( m ) = m + 2 ρ ( S e ) and on average m + 2 m+2 m + 2 halvings. So E u \mathbb{E}u E u and E h \mathbb{E}h E h grow by amounts whose ratio is at least 1 2 + ρ ( S e ) \frac{1}{2}+\rho(S_e) 2 1 + ρ ( S e ) . Before the change, u ˉ ( m ) ≤ m − 1 \bar{u}(m)\le m-1 u ˉ ( m ) ≤ m − 1 for m ≥ c m\ge c m ≥ c gives E u ≤ 1 + W + 2 ρ ( S e ) W \mathbb{E}u\le1+W+2\rho(S_e)W E u ≤ 1 + W + 2 ρ ( S e ) W with W = 1 − 2 1 − c W=1-2^{1-c} W = 1 − 2 1 − c , while E h = 2 + 2 W \mathbb{E}h=2+2W E h = 2 + 2 W , so that σ ≤ 1 2 + ρ ( S e ) W 1 + W ≤ 1 2 + ρ ( S e ) \sigma\le\frac{\frac{1}{2}+\rho(S_e)W}{1+W}\le\frac{1}{2}+\rho(S_e) σ ≤ 1 + W 2 1 + ρ ( S e ) W ≤ 2 1 + ρ ( S e ) . Adding to the numerator and the denominator of a fraction amounts whose ratio is at least the fraction does not decrease it. □ \square □
The drift per block, on the other hand, is not monotone: it is − 2 -2 − 2 for T ∅ , ∅ T_{\varnothing,\varnothing} T ∅ , ∅ and 1 2 log 2 3 − 3 = − 2.21 \frac{1}{2}\log_2 3-3=-2.21 2 1 log 2 3 − 3 = − 2.21 for T { 1 } , ∅ T_{\{1\},\varnothing} T { 1 } , ∅ , whose blocks with m = 1 m=1 m = 1 are longer.
Odd numbers x ≡ 1 ( m o d 4 ) x\equiv1\pmod4 x ≡ 1 ( mod 4 ) going down
If 1 ∉ S o 1\notin S_o 1 ∈ / S o , the odd numbers x ≡ 1 ( m o d 4 ) x\equiv1\pmod4 x ≡ 1 ( mod 4 ) go down to ( x + 1 ) / 2 (x+1)/2 ( x + 1 ) /2 . Then [ 1 , m ] ⊈ S o [1,m]\not\subseteq S_o [ 1 , m ] ⊆ S o for every m m m , so every block is of the case r < m r<m r < m of Theorem 8.2, as for the maps T S − T_S^{-} T S − , and the block map has the form of (6.1), with a more general exponent of 3.
Proposition 8.5. Let 1 ∉ S o 1\notin S_o 1 ∈ / S o , and for m ≥ 1 m\ge1 m ≥ 1 let a ( m ) = r S o ( m ) + r S e ( m − r S o ( m ) − 1 ) a(m)=r_{S_o}(m)+r_{S_e}(m-r_{S_o}(m)-1) a ( m ) = r S o ( m ) + r S e ( m − r S o ( m ) − 1 ) . (a) For odd x x x with v 2 ( x + 1 ) = m v_2(x+1)=m v 2 ( x + 1 ) = m we have U S o , S e ( x ) = 3 a ( m ) ( x + 1 ) / 2 m U_{S_o,S_e}(x)=3^{a(m)}(x+1)/2^m U S o , S e ( x ) = 3 a ( m ) ( x + 1 ) / 2 m and a ( m ) ≤ m − 1 a(m)\le m-1 a ( m ) ≤ m − 1 . Hence U S o , S e ( x ) ≤ U N − ( x ) U_{S_o,S_e}(x)\le U_{\mathbb{N}}^{-}(x) U S o , S e ( x ) ≤ U N − ( x ) for every odd x x x , and δ ( S o , S e ) ≤ log 2 3 − 2 \delta(S_o,S_e)\le\log_2 3-2 δ ( S o , S e ) ≤ log 2 3 − 2 .
(b) a ( m ) = m − 1 a(m)=m-1 a ( m ) = m − 1 for every m m m if and only if [ 1 , g − 1 ] ⊆ S e [1,g-1]\subseteq S_e [ 1 , g − 1 ] ⊆ S e for every g ∈ N ∖ S o g\in\mathbb{N}\setminus S_o g ∈ N ∖ S o . In this case U S o , S e = U N − U_{S_o,S_e}=U_{\mathbb{N}}^{-} U S o , S e = U N − , so every T S o , S e T_{S_o,S_e} T S o , S e -orbit is eventually periodic if and only if no Collatz orbit diverges, and every cycle of T S o , S e T_{S_o,S_e} T S o , S e is in the class of a cycle of T N − T_{\mathbb{N}}^{-} T N − , that is, of a Collatz cycle shifted by one.
(c) If 3 a ( m ) < 2 m 3^{a(m)}<2^m 3 a ( m ) < 2 m for every m m m , then every T S o , S e T_{S_o,S_e} T S o , S e -orbit of a positive integer reaches the fixed point 1 1 1 or a cycle through 3 3 3 , which is ( 3 , 5 ) (3,5) ( 3 , 5 ) if 2 ∈ S o 2\in S_o 2 ∈ S o , and ( 2 , 3 ) (2,3) ( 2 , 3 ) if 2 ∉ S o 2\notin S_o 2 ∈ / S o and 1 ∈ S e 1\in S_e 1 ∈ S e .
Proof. (a) Since 1 ∉ S o 1\notin S_o 1 ∈ / S o , we have r = r S o ( m ) < m r=r_{S_o}(m)<m r = r S o ( m ) < m , so Theorem 8.2 gives the formula, and r S e ( m − r − 1 ) ≤ m − r − 1 r_{S_e}(m-r-1)\le m-r-1 r S e ( m − r − 1 ) ≤ m − r − 1 . For ( S o , S e ) = ( ∅ , N ) (S_o,S_e)=(\varnothing,\mathbb{N}) ( S o , S e ) = ( ∅ , N ) we get a ( m ) = m − 1 a(m)=m-1 a ( m ) = m − 1 , that is, U N − ( x ) = 3 m − 1 ( x + 1 ) / 2 m U_{\mathbb{N}}^{-}(x)=3^{m-1}(x+1)/2^m U N − ( x ) = 3 m − 1 ( x + 1 ) / 2 m . Finally E h = 2 E_h=2 E h = 2 and E u − ∑ m 2 − m a ( m ) ≤ ∑ m 2 − m ( m − 1 ) = 1 E_u-\sum_m 2^{-m}a(m)\le\sum_m 2^{-m}(m-1)=1 E u − ∑ m 2 − m a ( m ) ≤ ∑ m 2 − m ( m − 1 ) = 1 .
(b) Let g = m − r S o ( m ) g=m-r_{S_o}(m) g = m − r S o ( m ) , the largest element of [ 1 , m ] [1,m] [ 1 , m ] not in S o S_o S o . Then a ( m ) = m − g + r S e ( g − 1 ) a(m)=m-g+r_{S_e}(g-1) a ( m ) = m − g + r S e ( g − 1 ) , which equals m − 1 m-1 m − 1 if and only if r S e ( g − 1 ) = g − 1 r_{S_e}(g-1)=g-1 r S e ( g − 1 ) = g − 1 , that is, [ 1 , g − 1 ] ⊆ S e [1,g-1]\subseteq S_e [ 1 , g − 1 ] ⊆ S e ; and every g ∉ S o g\notin S_o g ∈ / S o occurs, for m = g m=g m = g . If the block maps agree, the orbits of T S o , S e T_{S_o,S_e} T S o , S e and T N − T_{\mathbb{N}}^{-} T N − through an odd number start their blocks at the same odd numbers, and corresponding blocks differ only by the moves of Theorem 8.3. A block has finitely many steps, so an orbit is eventually periodic if and only if the sequence of its block starts is; and by Theorem 6.1, T N − T_{\mathbb{N}}^{-} T N − is the Collatz map shifted by one.
(c) Write x + 1 = 2 m k x+1=2^m k x + 1 = 2 m k . Then U S o , S e ( x ) = 3 a ( m ) k < 2 m k = x + 1 U_{S_o,S_e}(x)=3^{a(m)}k<2^m k=x+1 U S o , S e ( x ) = 3 a ( m ) k < 2 m k = x + 1 , so U S o , S e ( x ) ≤ x U_{S_o,S_e}(x)\le x U S o , S e ( x ) ≤ x , with equality if and only if k ( 2 m − 3 a ( m ) ) = 1 k(2^m-3^{a(m)})=1 k ( 2 m − 3 a ( m ) ) = 1 , that is, k = 1 k=1 k = 1 and 2 m − 3 a ( m ) = 1 2^m-3^{a(m)}=1 2 m − 3 a ( m ) = 1 . For m ≥ 3 m\ge3 m ≥ 3 this is impossible, since 2 m − 1 ≡ 7 ( m o d 8 ) 2^m-1\equiv7\pmod8 2 m − 1 ≡ 7 ( mod 8 ) while 3 a ≡ 1 3^a\equiv1 3 a ≡ 1 or 3 ( m o d 8 ) 3\pmod8 3 ( mod 8 ) . So either m = 1 m=1 m = 1 , a ( 1 ) = 0 a(1)=0 a ( 1 ) = 0 and x = 1 x=1 x = 1 , or m = 2 m=2 m = 2 , a ( 2 ) = 1 a(2)=1 a ( 2 ) = 1 and x = 3 x=3 x = 3 . Hence the odd numbers at which blocks start decrease strictly until they reach 1 1 1 or 3 3 3 . The block of 1 1 1 is 1 → 1 1\to1 1 → 1 , and the block of 3 3 3 is 3 → 5 → 3 3\to5\to3 3 → 5 → 3 if 2 ∈ S o 2\in S_o 2 ∈ S o , 3 → 2 → 3 3\to2\to3 3 → 2 → 3 if 2 ∉ S o 2\notin S_o 2 ∈ / S o and 1 ∈ S e 1\in S_e 1 ∈ S e , and 3 → 2 → 1 3\to2\to1 3 → 2 → 1 otherwise.
Part (a) says that without the step up at the exponent 1, no block multiplies x + 1 x+1 x + 1 by more than the corresponding block of the Collatz map T N − T_{\mathbb{N}}^{-} T N − , which goes down once and then up at every exponent of the even numbers that follow, the largest possible number m − 1 m-1 m − 1 of steps up. So every map with 1 ∉ S o 1\notin S_o 1 ∈ / S o is at least as contracting as the Collatz map; its drift lies between δ ( ∅ , ∅ ) = − 2 \delta(\varnothing,\varnothing)=-2 δ ( ∅ , ∅ ) = − 2 and log 2 3 − 2 = − 0.415 \log_2 3-2=-0.415 log 2 3 − 2 = − 0.415 .
Part (b) gives infinitely many maps that are the Collatz map in disguise, in a different way than in Theorem 6.1: for instance T [ 2 , ∞ ) , S T_{[2,\infty),S} T [ 2 , ∞ ) , S for every S S S , and T [ 3 , ∞ ) , S T_{[3,\infty),S} T [ 3 , ∞ ) , S for every S S S with 1 ∈ S 1\in S 1 ∈ S . Under T [ 2 , ∞ ) , S T_{[2,\infty),S} T [ 2 , ∞ ) , S , an odd x x x with x + 1 = 2 m k x+1=2^m k x + 1 = 2 m k , m ≥ 2 m\ge2 m ≥ 2 , goes up through the odd numbers 2 m − i 3 i k − 1 2^{m-i}3^i k-1 2 m − i 3 i k − 1 and down at the exponent 1, to 3 m − 1 k 3^{m-1}k 3 m − 1 k ; under T N − T_{\mathbb{N}}^{-} T N − it goes down first, to 2 m − 1 k 2^{m-1}k 2 m − 1 k , and then up through even numbers, to the same odd number 3 m − 1 k 3^{m-1}k 3 m − 1 k . The cycle ( 3 , 5 ) (3,5) ( 3 , 5 ) of T [ 2 , ∞ ) , S T_{[2,\infty),S} T [ 2 , ∞ ) , S thus corresponds to the cycle ( 2 , 3 ) (2,3) ( 2 , 3 ) of T N − T_{\mathbb{N}}^{-} T N − .
Part (c) contains Theorem 6.3, the case S o = ∅ S_o=\varnothing S o = ∅ . It applies, for instance, to the first example of this section, T { 2 } , ∅ T_{\{2\},\varnothing} T { 2 } , ∅ , for which a ( 2 ) = 1 a(2)=1 a ( 2 ) = 1 and a ( m ) = 0 a(m)=0 a ( m ) = 0 for m ≠ 2 m\ne2 m = 2 : every orbit ends in ( 1 ) (1) ( 1 ) or in ( 3 , 5 ) (3,5) ( 3 , 5 ) . When the criterion fails, 3 a ( m ) > 2 m 3^{a(m)}>2^m 3 a ( m ) > 2 m for some m m m , and as in Section 6.2 the negative rational number x ∗ = − 3 a ( m ) / ( 3 a ( m ) − 2 m ) x^*=-3^{a(m)}/(3^{a(m)}-2^m) x ∗ = − 3 a ( m ) / ( 3 a ( m ) − 2 m ) , which satisfies v 2 ( x ∗ + 1 ) = m v_2(x^*+1)=m v 2 ( x ∗ + 1 ) = m , repeats this increasing block forever; so the descent of all orbits cannot be proved from residue classes alone.
The census of Section 8.2, run over all pairs with 1 ∉ S o 1\notin S_o 1 ∈ / S o and all n < 10 9 n<10^9 n < 1 0 9 , never reached the bound 2 120 2^{120} 2 120 and found only the cycles ( 1 ) (1) ( 1 ) , ( 2 , 3 ) (2,3) ( 2 , 3 ) and ( 3 , 5 ) (3,5) ( 3 , 5 ) . So for every S o S_o S o with 1 ∉ S o 1\notin S_o 1 ∈ / S o and every S e S_e S e , these are the only cycles of T S o , S e T_{S_o,S_e} T S o , S e with smallest element below 10 9 10^9 1 0 9 ; up to switching, they are the two shifted Collatz cycles. This includes the maps T S − T_S^{-} T S − , for which Section A went up to 10 6 10^6 1 0 6 . In this respect, too, the maps with 1 ∉ S o 1\notin S_o 1 ∈ / S o , mixed or not, behave like the maps T S − T_S^{-} T S − .
Odd numbers x ≡ 1 ( m o d 4 ) x \equiv1 \pmod{4} x ≡ 1 ( mod 4 ) going up
If 1 ∈ S o 1 \in S_o 1 ∈ S o , let c ≥ 2 c \ge2 c ≥ 2 be the smallest positive integer not in S o S_o S o (c = ∞ c = \infty c = ∞ if S o = N S_o = \mathbb{N} S o = N ). The blocks with m < c m < c m < c are of the case r = m r = m r = m : they go up at all the odd exponents m , m − 1 , … , 1 m, m-1, \ldots, 1 m , m − 1 , … , 1 and reach the even number 3 m ( x + 1 ) / 2 m − 1 3^m(x+1)/2^m - 1 3 m ( x + 1 ) / 2 m − 1 , whose exponent M M M is new, as after the step x ↦ 3 x + 1 x \mapsto3x+1 x ↦ 3 x + 1 of the Collatz map. Such a block multiplies x + 1 x+1 x + 1 by about 3 m + r S e ( M ) / 2 m + M 3^{m+r_{S_e}(M)}/2^{m+M} 3 m + r S e ( M ) / 2 m + M , which for M = 1 M=1 M = 1 is larger than the factor 3 m − 1 / 2 m 3^{m-1}/2^m 3 m − 1 / 2 m of the corresponding block of the Collatz map T N T_{\mathbb{N}} T N . So these maps can be expanding: by Theorem 8.4 the drift of the maps with 1 ∈ S o 1 \in S_o 1 ∈ S o ranges from δ ( { 1 } , ∅ ) = 1 3 log 2 3 − 2 = − 1.47 \delta(\{1\}, \varnothing) = \frac{1}{3}\log_2 3 - 2 = -1.47 δ ({ 1 } , ∅ ) = 3 1 log 2 3 − 2 = − 1.47 to δ ( N , N ) = 2 log 2 3 − 2 = 1.17 \delta(\mathbb{N}, \mathbb{N}) = 2\log_2 3 - 2 = 1.17 δ ( N , N ) = 2 log 2 3 − 2 = 1.17 , and the maps T S T_S T S are among them.
Here the census finds many cycles. Below 1000 (with largest element below 2 120 2^{120} 2 120 ) it finds the 43 + cycles of Table A.2, the cycle ( 2 , 3 ) (2, 3) ( 2 , 3 ) , which does not meet the exponent 1 at an odd number, and 17,200 mixed cycles, which form 2,436 classes. Their number grows with the bound on the smallest element, but slowly, like that of the + cycles: with largest element below 2 64 2^{64} 2 64 there are 217, 650 and 845 classes of mixed cycles with smallest element below 10 2 10^2 1 0 2 , 10 3 10^3 1 0 3 and 10 4 10^4 1 0 4 , against 24, 37 and 45 + cycles.
Figure 8.1 plots the classes against the drift of the most contracting map that contains them. The mixed classes crowd around the threshold: for 2,253 of the 2,436 (92%) this most contracting map has ∣ δ ∣ < 0.1 |\delta| < 0.1 ∣ δ ∣ < 0.1 ; these classes have a median length of about 3200 steps, and 93% of them have elements above 2 40 2^{40} 2 40 . This is the picture of Fig. A.1, much amplified. Near the threshold orbits make long excursions (§ 5.2 ), so that long cycles with large elements can close up, and the unified maps, with two sets as parameters, include far more maps near the threshold than the family T S T_S T S .
Figure 8.1. The classes of cycles found by the census of § 10.2 : all cycles with smallest element below 1000 and largest element below 2 120 2^{120} 2 120 of the maps with 1 ∈ S o 1 \in S_o 1 ∈ S o , and the three cycles of the maps with 1 ∉ S o 1 \notin S_o 1 ∈ / S o . Length (left) and log 2 \log_2 log 2 of the largest element (right), against the drift of the most contracting map that contains the class (Theorem 8.4 ). Orange: classes of mixed cycles; blue: + cycles; green: the classes of (1) and of (2, 3) and (3, 5). The vertical line is the threshold δ = 0 \delta= 0 δ = 0 , the horizontal line on the right the bound 2 120 2^{120} 2 120 of the search.
So the large number of mixed cycles reflects the size of the family rather than the behaviour of single maps. To compare single maps, we read off from the census the cycles of 512 maps T S T_S T S and of 32,512 mixed maps with 1 ∈ S o 1 \in S_o 1 ∈ S o and compare them at equal drift (Table 8.1 ). A mixed map has about as many cycles as a map T S T_S T S with the same drift, two or three with smallest element below 1000 near the threshold. At drifts below − 0.5 -0.5 − 0.5 , which no map T S T_S T S has, the mixed maps have one to three cycles each, all small (with at most ten elements, the largest at most 120), but not only the shifted Collatz cycles: besides (1, 2), (2, 3) and (1, 2, 3, 5, 8) they include, for example, C { 3 } + ( 3 ) = ( 3 , 5 , 8 , 12 ) C^{+}_{\{3\}}(3) = (3, 5, 8, 12) C { 3 } + ( 3 ) = ( 3 , 5 , 8 , 12 ) , C { 2 } + ( 19 ) C^{+}_{\{2\}}(19) C { 2 } + ( 19 ) and the mixed cycle ( 17 , 26 , 39 , 59 , 30 , 45 , 68 ) (17, 26, 39, 59, 30, 45, 68) ( 17 , 26 , 39 , 59 , 30 , 45 , 68 ) , which occurs in maps with drift down to − 0.68 -0.68 − 0.68 . The maps with 1 ∉ S o 1 \notin S_o 1 ∈ / S o have no such cycles at any drift. We also checked 22 mixed maps with drifts between − 1.47 -1.47 − 1.47 and − 0.019 -0.019 − 0.019 directly, by the method of § 7.1 , for all n < 10 6 n < 10^6 n < 1 0 6 : every orbit is eventually periodic, and each map has one to five cycles with smallest element below 10 6 10^6 1 0 6 , as the maps of Table 5.1 . For instance, under T { 1 } , [ 1 , 3 ] T_{\{1\},[1,3]} T { 1 } , [ 1 , 3 ] , which has the drift of T { 1 } T_{\{1\}} T { 1 } , every n < 10 6 n < 10^6 n < 1 0 6 ends in ( 2 , 3 ) (2, 3) ( 2 , 3 ) , and the longest glide (114,654 steps) and the highest peak (851 bits) are of the same size as those of T { 1 } T_{\{1\}} T { 1 } for n < 10 6 n < 10^6 n < 1 0 6 (86,626 steps and 602 bits).
Table 8.1. Cycles of single maps, read off from the census of Section 8.2: for the contracting maps with drift δ \delta δ in the given range, the number of maps and the mean number of cycles with smallest element below 1000 and largest element below 2 120 2^{120} 2 120 . Maps T S T_S T S : all S S S for which S ∩ [ 9 , ∞ ) S \cap[9,\infty) S ∩ [ 9 , ∞ ) is empty or equal to [ 9 , ∞ ) [9,\infty) [ 9 , ∞ ) . Mixed maps: all pairs with 1 ∈ S o ≠ N 1 \in S_o \ne\mathbb{N} 1 ∈ S o = N for which S o ∩ [ 8 , ∞ ) S_o \cap[8,\infty) S o ∩ [ 8 , ∞ ) and S e ∩ [ 8 , ∞ ) S_e \cap[8,\infty) S e ∩ [ 8 , ∞ ) are empty or equal to [ 8 , ∞ ) [8,\infty) [ 8 , ∞ ) .
Mixed cycles do have one feature that + + + cycles lack. Under T S T_S T S an even number x x x is reached only from ( 2 x − 1 ) / 3 (2x-1)/3 ( 2 x − 1 ) /3 or from 2 x / 3 2x/3 2 x /3 , both smaller than x x x , so the smallest element of a + + + cycle is odd. In a mixed map an even x x x can also be reached from the larger odd number 2 x − 1 2x-1 2 x − 1 , and some mixed cycles have an even smallest element, for instance ( 16 , 24 , 36 , 54 , 27 , 41 , 62 , 31 ) (16, 24, 36, 54, 27, 41, 62, 31) ( 16 , 24 , 36 , 54 , 27 , 41 , 62 , 31 ) of T { 1 , 2 } , [ 2 , 4 ] T_{\{1,2\},[2,4]} T { 1 , 2 } , [ 2 , 4 ] , in which 31 goes down to 16.
To sum up, the mixed maps do not seem to form a new kind. The direction at the odd numbers x ≡ 1 ( m o d 4 ) x \equiv1 \pmod{4} x ≡ 1 ( mod 4 ) decides: if they go down, the map is dominated block by block by the Collatz map and, as far as the census reaches, has only the two shifted Collatz cycles, up to switching; if they go up, the map behaves like the maps T S T_S T S .
Conjectures and open problems
Conjecture 9.1. If S S S is eventually periodic and contracting, then every T S T_S T S -orbit is eventually periodic, and T S T_S T S has finitely many cycles. For the seven maps of Table 5.1 , the cycles listed there are all the cycles.
For S = ∅ S = \varnothing S = ∅ the first statement is the part of the Collatz conjecture that excludes divergent orbits. For every S S S the 2-adic integer − 1 -1 − 1 is a fixed point of U S U_S U S (with M ( − 1 ) = 0 M(-1) = 0 M ( − 1 ) = 0 ), and on the residue classes that contain − 1 -1 − 1 every determined odd step multiplies by 3 / 2 3/2 3/2 . So, as for the Collatz map, these classes have no coefficient stopping time in the sense recalled in § 8 , and Theorem 9.1 cannot be proved from residue classes alone.
Conjecture 9.2. If S ≠ N S \ne\mathbb{N} S = N is expanding, then almost every T S T_S T S -orbit diverges. If moreover κ ( S ) < 1 \kappa(S) < 1 κ ( S ) < 1 , the number of n ≤ N n \le N n ≤ N with an eventually periodic orbit is N 1 − κ ( S ) + o ( 1 ) N^{1-\kappa(S)+o(1)} N 1 − κ ( S ) + o ( 1 ) .
The condition κ ( S ) < 1 \kappa(S)<1 κ ( S ) < 1 fails only for the sets S = N ∖ { c } S=\mathbb{N}\setminus\{c\} S = N ∖ { c } . Indeed, E 2 − X = 1 3 ∑ m ≥ 0 3 − r S ( m ) \mathbb{E}2^{-X}=\frac{1}{3}\sum_{m\geq0}3^{-r_S(m)} E 2 − X = 3 1 ∑ m ≥ 0 3 − r S ( m ) , and every m ∉ S m\notin S m ∈ / S , including m = 0 m=0 m = 0 , contributes 1 to the sum. So if S S S is expanding and misses at least two positive integers, then E 2 − X > 1 \mathbb{E}2^{-X}>1 E 2 − X > 1 , and κ ( S ) < 1 \kappa(S)<1 κ ( S ) < 1 by convexity; for S = N ∖ { c } S=\mathbb{N}\setminus\{c\} S = N ∖ { c } , on the other hand, E 2 − X = 1 − 3 1 − c / 6 < 1 \mathbb{E}2^{-X}=1-3^{1-c}/6<1 E 2 − X = 1 − 3 1 − c /6 < 1 and κ ( S ) > 1 \kappa(S)>1 κ ( S ) > 1 . For these sets the heuristic of § 5.2 predicts that only finitely many n n n have an eventually periodic orbit; for S = N ∖ { 1 } S=\mathbb{N}\setminus\{1\} S = N ∖ { 1 } , for example, the cycle ( 1 , 2 ) (1,2) ( 1 , 2 ) attracts only the numbers 1 and 2.
Conjecture 9.3. If S S S is contracting, the basin of every cycle of T S T_S T S has a natural density.
Conjecture 9.4. ⟨ ∅ , { 1 } ⟩ \langle\varnothing,\{1\}\rangle ⟨ ∅ , { 1 }⟩ is unbounded, and ⟨ ∅ , { 3 } ⟩ \langle\varnothing,\{3\}\rangle ⟨ ∅ , { 3 }⟩ is bounded. More generally, a family with v ≠ 0 v\ne0 v = 0 is bounded if and only if v < 0 v<0 v < 0 , that is, if Λ ( λ ) < 1 \Lambda(\lambda)<1 Λ ( λ ) < 1 for some λ > 0 \lambda>0 λ > 0 (§ 9.3 ), at least when S − S^- S − and S + S^+ S + are eventually periodic.
Problem 9.5. Prove that some T S T_S T S with S ≠ N S\ne\mathbb{N} S = N has a divergent orbit, for instance S = { 1 , 2 } S=\{1,2\} S = { 1 , 2 } , where δ = + 0.377 \delta=+0.377 δ = + 0.377 and almost every orbit exceeds n 1.18 n^{1.18} n 1.18 (Theorem 4.1 ). By Theorem 4.2 this requires arithmetic information beyond residue classes.
Problem 9.6. Prove that every orbit of T { 1 , 2 } − T_{\{1,2\}}^- T { 1 , 2 } − is eventually periodic. This is perhaps the simplest map in the family that is not covered by Theorem 6.3: its drift − 1.21 -1.21 − 1.21 is about three times that of the Collatz map, and only the steps at x ≡ 7 ( m o d 16 ) x\equiv7\pmod{16} x ≡ 7 ( mod 16 ) go up, by a factor of about 9 / 8 9/8 9/8 . More generally, for which S S S is every T S − T_S^- T S − -orbit eventually periodic?
Problem 9.7. Are C ∅ − ( 1 ) C_{\varnothing}^-(1) C ∅ − ( 1 ) and C ∅ − ( 2 ) C_{\varnothing}^-(2) C ∅ − ( 2 ) the only − - − cycles, that is, does every map T S − T_S^- T S − have only the shifted cycles of the Collatz map? For S = N S=\mathbb{N} S = N this includes the statement that the Collatz map has no cycle other than ( 1 , 2 ) (1,2) ( 1 , 2 ) . (By Theorem 6.3 the answer is yes for every S S S that satisfies its criterion, and by Section 8.4 it is yes for cycles with smallest element below 10 9 10^9 1 0 9 .) More generally, are ( 1 ) (1) ( 1 ) , ( 2 , 3 ) (2,3) ( 2 , 3 ) and ( 3 , 5 ) (3,5) ( 3 , 5 ) the only cycles of the unified maps T S o , S e T_{S_o,S_e} T S o , S e with 1 ∉ S o 1\notin S_o 1 ∈ / S o ? Is the set of + + + cycles infinite?
Problem 9.8. Prove that ⟨ ∅ , { 1 } ⟩ \langle\varnothing,\{1\}\rangle ⟨ ∅ , { 1 }⟩ is unbounded, that is, that some positive integer has a divergent branch. By Theorem 7.12, residue classes modulo 2 10 2^{10} 2 10 do not suffice.
Problem 9.9. Extend Tao’s theorem [29 ] to contracting T S T_S T S : is it true that for every function f f f with f ( n ) → ∞ f(n)\to\infty f ( n ) → ∞ almost every T S T_S T S -orbit, in the sense of logarithmic density, attains a value below f ( n ) f(n) f ( n ) ? A similar question can be asked for a family with v < 0 v<0 v < 0 : for almost every n n n , does every branch from n n n attain a value below f ( n ) f(n) f ( n ) ? (The weaker statement that some branch from n n n does so would follow from the first question, applied to T S − T_{S^-} T S − , which is contracting since δ ( S − ) ≤ v \delta(S^-)\leq v δ ( S − ) ≤ v .)
Problem 9.10. By Theorem 3.4 no map T S T_S T S is critical. In the single-halving variant of Theorem 3.5, where ρ ( S ) \rho(S) ρ ( S ) is replaced by ∑ s ∈ S 2 − s \sum_{s\in S}2^{-s} ∑ s ∈ S 2 − s , the critical case does occur, for the set S S S of positions of the binary digits 1 of θ \theta θ . Describe the orbits of this map.
Problem 9.11. Find other ways to transfer statements between maps. Theorem 7.4 only compares families ordered by inclusion, and Theorem 6.2 gives a partial transfer from the maps T [ 1 , b ] T_{[1,b]} T [ 1 , b ] to the Collatz map. Is there, for example, a single map T S T_S T S or T S − T_S^- T S − , other than T ∅ T_{\varnothing} T ∅ and T N − T_{\mathbb{N}}^- T N − , whose eventual periodicity would imply that of the Collatz map? (Among the unified maps there are such maps, for instance T [ 2 , ∞ ) , S T_{[2,\infty),S} T [ 2 , ∞ ) , S for every S S S , by Theorem 8.5(b); but they have the same block map as T N − T_{\mathbb{N}}^- T N − .)
Data and code
The program (a Python driver with a C kernel), the JSON files with all statistics, the lists of rational witnesses of Theorem 7.11, the script for the computation in the proof of Theorem 3.4, the census programs and the lists of cycles of Section A and Section 8, and scripts that recompute the constants, tables and the figures are available as ancillary files of this paper on arXiv, linked from its abstract page; the file README.txt among them describes them and how to run them.
Acknowledgments
The computations were done on Kaggle notebooks. This work was carried out with the assistance of Claude Opus 5.5 (Anthropic), an AI system, which helped with the literature search, the derivations, the code and the drafting of the text. The author has checked the results and takes full responsibility for the content.
Cycles across the family
A cycle is a finite set of numbers that a map permutes cyclically, and the same cycle can occur in many maps of the family; here we name cycles independently of the maps. Every cycle contains odd numbers, since a run of steps at even numbers ends at an odd number, and all odd elements of a cycle are treated by the same rule. So a cycle is either a + + + cycle, whose odd elements go up to ( 3 x + 1 ) / 2 (3x+1)/2 ( 3 x + 1 ) /2 , or a − - − cycle, whose odd elements go down to ( x + 1 ) / 2 (x+1)/2 ( x + 1 ) /2 ; the former occur only for maps T S T_S T S , the latter only for maps T S − T_S^- T S − . For a cycle C C C let U ( C ) U(C) U ( C ) , respectively D ( C ) D(C) D ( C ) , be the set of exponents m ≥ 1 m \ge1 m ≥ 1 such that some element x = 2 m k x = 2^m k x = 2 m k of C C C is mapped to 3 x / 2 3x/2 3 x /2 , respectively to k k k . These are disjoint finite sets.
Proposition A.1. A + + + cycle C C C is a cycle of T S T_S T S if and only if U ( C ) ⊆ S U(C) \subseteq S U ( C ) ⊆ S and S ∩ D ( C ) = ∅ S \cap D(C) = \varnothing S ∩ D ( C ) = ∅ , and a − - − cycle C C C is a cycle of T S − T_S^- T S − under the same condition.
Proof. C C C is a cycle of a map exactly when the map sends every element of C C C to its successor in C C C , that is, when at every exponent occurring in C C C the map follows the same rule.
So the maps that contain a cycle C C C form an interval U ( C ) ⊆ S ⊆ N ∖ D ( C ) U(C) \subseteq S \subseteq\mathbb{N} \setminus D(C) U ( C ) ⊆ S ⊆ N ∖ D ( C ) , and this interval contains a unique map closest to the Collatz map of the same family: T U ( C ) T_{U(C)} T U ( C ) for a + + + cycle, which differs from the Collatz map T ∅ T_{\varnothing} T ∅ exactly at the exponents in U ( C ) U(C) U ( C ) , and T N ∖ D ( C ) T_{\mathbb{N}\setminus D(C)} T N ∖ D ( C ) for a − - − cycle, which differs from the Collatz map T N T_{\mathbb{N}} T N exactly at the exponents in D ( C ) D(C) D ( C ) . By Theorem 3.2(b), T U ( C ) T_{U(C)} T U ( C ) is also the most contracting map that contains C C C . We name a cycle by its family, by the set of exponents at which it deviates from the Collatz rule, and by its smallest element n n n :
C U + ( n ) C_U^+(n) C U + ( n ) : the + + + cycle with U ( C ) = U U(C) = U U ( C ) = U and smallest element n n n , a cycle of T U T_U T U ,
C D − ( n ) C_D^-(n) C D − ( n ) : the − - − cycle with D ( C ) = D D(C) = D D ( C ) = D and smallest element n n n , a cycle of T N ∖ D T_{\mathbb{N}\setminus D} T N ∖ D .
Since C U + ( n ) C_U^+(n) C U + ( n ) is the cycle of T U T_U T U through n n n , and C D − ( n ) C_D^-(n) C D − ( n ) the cycle of T N ∖ D T_{\mathbb{N}\setminus D} T N ∖ D through $n, the name determines the cycle. An empty index marks a cycle of the Collatz map: C ∅ + ( 1 ) = ( 1 , 2 ) C_{\varnothing}^+(1) = (1,2) C ∅ + ( 1 ) = ( 1 , 2 ) is a cycle of T ∅ T_{\varnothing} T ∅ , and C ∅ − ( 1 ) = ( 1 ) C_{\varnothing}^-(1) = (1) C ∅ − ( 1 ) = ( 1 ) and C ∅ − ( 2 ) = ( 2 , 3 ) C_{\varnothing}^-(2) = (2,3) C ∅ − ( 2 ) = ( 2 , 3 ) are the Collatz cycles ( 0 ) (0) ( 0 ) and ( 1 , 2 ) (1,2) ( 1 , 2 ) , shifted by one, as cycles of T N − T_{\mathbb{N}}^- T N − (Theorem 6.1). Table A.1 lists the cycles of all maps studied in Sections 5 and 6.
A census of cycles. To find all cycles with small elements, we search, for each n n n , the orbits starting at n n n in which every exponent m ≥ 1 m \ge1 m ≥ 1 is assigned the step up or the step down when it first occurs, following both assignments; this is the branching family ⟨ ∅ , N ⟩ \langle\varnothing,\mathbb{N}\rangle ⟨ ∅ , N ⟩ of Section 7 (and its analogue with odd numbers going down), restricted to branches that treat each exponent in the same way every time it occurs. A branch is abandoned when it drops below n n n , when it exceeds 2 120 2^{120} 2 120 , or when it enters a loop that does not contain n n n . This finds every cycle, of every map T S T_S T S or T S − T_S^- T S − , whose smallest element is n n n and whose largest element is below 2 120 2^{120} 2 120 ; every cycle found was checked again independently. For example, from n = 1 n = 1 n = 1 the search finds C ∅ + ( 1 ) C_{\varnothing}^+(1) C ∅ + ( 1 ) (down at the exponent 1) and C { 1 } + ( 1 ) C_{\{1\}}^+(1) C { 1 } + ( 1 ) (up at 1, down at 3), and it abandons the branch that goes up at 1 and 3 and down at 2 when it enters the loop ( 3 , 5 , 8 , 12 ) (3,5,8,12) ( 3 , 5 , 8 , 12 ) , which the search from n = 3 n = 3 n = 3 finds as C { 3 } + ( 3 ) C_{\{3\}}^+(3) C { 3 } + ( 3 ) .
For − - − cycles the bound 2 120 2^{120} 2 120 was never reached, so the result is complete: for every S ⊆ N S \subseteq\mathbb{N} S ⊆ N , the only cycles of T S − T_S^- T S − with smallest element below 10 6 10^6 1 0 6 are C ∅ − ( 1 ) C_{\varnothing}^-(1) C ∅ − ( 1 ) and C ∅ − ( 2 ) C_{\varnothing}^-(2) C ∅ − ( 2 ) . (Section 8.4 extends this to 10 9 10^9 1 0 9 .) For + + + cycles there are exactly 53 with smallest element below 10 5 10^5 1 0 5 and largest element below 2 120 2^{120} 2 120 ; they are listed in Table A.2. Their number grows slowly with the smallest element: 25 of them have smallest element below 100, 43 below 1000, and all of them at most 6757. Exactly 21 of them occur in a contracting map, that is, have ρ ( U ( C ) ) < θ \rho(U(C)) < \theta ρ ( U ( C )) < θ . Cycles with larger elements exist: with the bound 2 125 2^{125} 2 125 the search finds one more cycle with smallest element below 10 4 10^{4} 1 0 4 , C { 1 , 5 , 9 , 10 , 11 , 12 , 13 , 14 } + ( 4033 ) C_{\{1,5,9,10,11,12,13,14\}}^{+}(4033) C { 1 , 5 , 9 , 10 , 11 , 12 , 13 , 14 } + ( 4033 ) , of length 4371.
Table A.1. Table A.1: The cycles of the maps studied in Sections 5 and 6: name, the sets U ( C ) U(C) U ( C ) and D ( C ) D(C) D ( C ) , length in steps, number of odd steps, largest element, and the maps of Section 5 (for + cycles) or of Section 6 (for − cycles) that contain the cycle; by Theorem A.1, C C C occurs exactly for the sets S S S with U ( C ) ⊆ S U(C) \subseteq S U ( C ) ⊆ S and S ∩ D ( C ) = ∅ S \cap D(C) = \varnothing S ∩ D ( C ) = ∅ .
Figure A.1 plots the 53 cycles against ρ ( U ) \rho(U) ρ ( U ) . The 11 cycles with more than 1000 steps and the 12 cycles with largest element above 2 40 2^{40} 2 40 all have 0.25 < ρ ( U ) < 0.34 0.25 < \rho(U) < 0.34 0.25 < ρ ( U ) < 0.34 , close to θ \theta θ on either side, and several of them come close to the bound 2 120 2^{120} 2 120 . This fits the random model, in which the drift is small near θ \theta θ and the orbits make long excursions (Table 3.1 ), and it suggests that a larger bound would reveal more cycles of this kind.
To read Table A.2, recall from Theorem A.1 that C U + ( n ) C_{U}^{+}(n) C U + ( n ) is a cycle of T S T_{S} T S exactly when U ⊆ S U \subseteq S U ⊆ S and S ∩ D = ∅ S \cap D = \varnothing S ∩ D = ∅ . For example, the cycle C { 1 , 6 , 8 , 9 } + ( 43 ) C_{\{1,6,8,9\}}^{+}(43) C { 1 , 6 , 8 , 9 } + ( 43 ) occurs for every S S S that contains 1, 6, 8, 9 and none of 2, 3, 4, 5, 7; the most contracting of these maps, T { 1 , 6 , 8 , 9 } T_{\{1,6,8,9\}} T { 1 , 6 , 8 , 9 } , has ρ = 0.2617 \rho= 0.2617 ρ = 0.2617 , just below θ = 0.2619 \theta= 0.2619 θ = 0.2619 .
Table A.2. Table A.2: All + cycles C U + ( n ) C_{U}^{+}(n) C U + ( n ) with smallest element n < 10 5 n < 10^{5} n < 1 0 5 and largest element below 2 120 2^{120} 2 120 : n n n (with * if the cycle occurs in a map of Section 5), U = U ( C ) U = U(C) U = U ( C ) , D = D ( C ) D = D(C) D = D ( C ) , length, number of odd steps, log 2 \log_{2} log 2 of the largest element, and ρ ( U ) \rho(U) ρ ( U ) ; the map T U T_{U} T U is contracting if and only if ρ ( U ) < θ = 0.2619 \rho(U) < \theta= 0.2619 ρ ( U ) < θ = 0.2619 .
Figure A.1. The 53 + cycles of Table A.2: length (left) and log 2 \log_{2} log 2 of the largest element (right) against ρ ( U ) \rho(U) ρ ( U ) . Blue: cycles that occur in a contracting map (ρ ( U ) < θ \rho(U) < \theta ρ ( U ) < θ ); orange: cycles that occur only in expanding maps. The vertical line is θ \theta θ , the horizontal line on the right the bound 2 120 2^{120} 2 120 of the search.