2020 Mathematics Subject Classification: Primary 11B83; Secondary 05C20, 11J71, 11Y55, 60J10.
Introduction
Up or down at every integer
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: odd numbers go up and even numbers go down. The Collatz conjecture states that every orbit reaches the cycle ( 1 , 2 ) (1,2) ( 1 , 2 ) ; see the surveys and bibliographies of Lagarias [9 , 12 , 10 , 11 ] . In [24 ] we kept the size of the steps and let the 2-adic valuation of the current number decide their direction. Here the direction is decided at every integer separately, by an arbitrary set. Let N = { 1 , 2 , 3 , … } \mathbb{N} = \{1,2,3,\ldots\} N = { 1 , 2 , 3 , … } .
Definition 1.1. For x ∈ N x \in\mathbb{N} x ∈ N let U ( x ) = ⌈ 3 x / 2 ⌉ U(x)=\lceil3x/2\rceil U ( x ) = ⌈ 3 x /2 ⌉ and D ( x ) = ⌈ x / 2 ⌉ D(x)=\lceil x/2\rceil D ( x ) = ⌈ x /2 ⌉ , and for S ⊆ N S\subseteq\mathbb{N} S ⊆ N let T S : N → N T_S:\mathbb{N}\to\mathbb{N} T S : N → N be
T S ( x ) = { U ( x ) , x ∈ S , D ( x ) , x ∉ S . (1) T_S(x)=
\begin{cases}
U(x), & x\in S,\\
D(x), & x\notin S.
\end{cases} \tag*{(1)} T S ( x ) = { U ( x ) , D ( x ) , x ∈ S , x ∈ / S . (1)
So U ( x ) = ( 3 x + 1 ) / 2 U(x)=(3x+1)/2 U ( x ) = ( 3 x + 1 ) /2 and D ( x ) = ( x + 1 ) / 2 D(x)=(x+1)/2 D ( x ) = ( x + 1 ) /2 for odd x x x , and U ( x ) = 3 x / 2 U(x)=3x/2 U ( x ) = 3 x /2 and D ( x ) = x / 2 D(x)=x/2 D ( x ) = x /2 for even x x x . A step up adds ⌊ x / 2 ⌋ \lfloor x/2\rfloor ⌊ x /2 ⌋ to x x x , a step down subtracts ⌊ x / 2 ⌋ \lfloor x/2\rfloor ⌊ x /2 ⌋ , and a step down at an even number halves it only once, rather than removing all factors 2 at once. These are exactly the two steps of the Collatz map, together with the step x ↦ ( x + 1 ) / 2 x\mapsto(x+1)/2 x ↦ ( x + 1 ) /2 at odd numbers that was used by the maps T S T_S T S of [24 ] . Since U ( x ) > x U(x)>x U ( x ) > x for all x x x and D ( x ) < x D(x)<x D ( x ) < x for all x ≥ 2 x\ge2 x ≥ 2 , while D ( 1 ) = 1 D(1)=1 D ( 1 ) = 1 , an orbit of T S T_S T S goes up exactly at the elements of S S S that it visits.
Maps as subgraphs of one graph
All maps T S T_S T S are built from the same two steps, so they all reside in one graph. The up-down graph G G G has the vertex set N \mathbb{N} N and, at every vertex x x x , the two edges x → U ( x ) x \to U(x) x → U ( x ) and x → D ( x ) x \to D(x) x → D ( x ) (Theorem 2.2, Figure 2.1 ). A map T S T_S T S is the subgraph G S G_S G S that keeps one of the two edges at every vertex, the up-edge at the elements of S S S and the down-edge elsewhere. A family of maps, in which the step up is forced on a set A A A , the step down is forced outside a set B ⊇ A B \supseteq A B ⊇ A , and both are allowed in between, is the subgraph G ⟨ A , B ⟩ G_{\langle A,B\rangle} G ⟨ A , B ⟩ that keeps one or two edges at every vertex, and the family of all maps is G G G itself.
Figure 2.1. The up-down graph G G G on [ 1 , 12 ] [1,12] [ 1 , 12 ] . Solid arcs above the line are up-edges x → ⌈ 3 x / 2 ⌉ x \to\lceil3x/2\rceil x → ⌈ 3 x /2 ⌉ (those leaving [ 1 , 12 ] [1,12] [ 1 , 12 ] are short arrows marked with their targets), dashed arcs below the line are down-edges x → ⌊ x / 2 ⌋ x \to\lfloor x/2\rfloor x → ⌊ x /2 ⌋ , and the loop is the down-edge at 1. A map T S T_S T S keeps the solid edge at the elements of S S S and the dashed edge elsewhere.
This gives a correspondence between maps and subgraphs (Theorem 2.3): the cycles of the maps of a family are exactly the simple cycles of its subgraph, any set of pairwise disjoint simple cycles occurs in a single map, the divergent orbits are exactly the rays (infinite simple paths), and all maps of the family are bounded if and only if the subgraph has no ray. So a classification of maps is the same as a classification of subgraphs of G G G , and statements about all maps at once are statements about G G G . Boundedness depends only on S S S “at infinity”: changing S S S at finitely many numbers does not change whether the map has a divergent orbit (Theorem 2.4).
The simplest classification
The first distinction is between sets that obviously give bounded maps and the others. If S S S has no element in an interval ( 2 B / 3 , B ] (2B/3,B] ( 2 B /3 , B ] , then no step leads from [ 1 , B ] [1,B] [ 1 , B ] above B B B , so T S T_S T S maps [ 1 , B ] [1,B] [ 1 , B ] into itself; we call such a B B B a barrier . A set with infinitely many barriers is trivially bounded : every orbit is trapped below some barrier. This happens exactly when S S S is finite or, writing S = { s 1 < s 2 < ⋯ } S=\{s_1<s_2<\cdots\} S = { s 1 < s 2 < ⋯ } , when infinitely often the next element s i + 1 s_{i+1} s i + 1 is out of reach of a step up from s i s_i s i , that is, s i + 1 > U ( s i ) s_{i+1}>U(s_i) s i + 1 > U ( s i ) (Theorem 3.2). Every other set has at least log 3 / 2 N − O ( 1 ) \log_{3/2}N-O(1) log 3/2 N − O ( 1 ) elements below N N N , and this is sharp.
For the remaining sets the important structure is that of the step up alone. The map U U U is injective, and N \mathbb{N} N splits into the chains { c , U ( c ) , U 2 ( c ) , … } \{c,U(c),U^2(c),\ldots\} { c , U ( c ) , U 2 ( c ) , … } , one for each c ≡ 1 ( m o d 3 ) c\equiv1\pmod{3} c ≡ 1 ( mod 3 ) ; the chains are the orbits of T N T_{\mathbb{N}} T N . An orbit of T S T_S T S makes several steps up in a row exactly when S S S contains several consecutive elements of a chain; in particular, it goes up at every step (we call such an orbit increasing ) exactly when S S S contains all elements of a chain from the starting number on. If no element of S S S goes up to another element of S S S , every number above 3 3 3 falls below itself within two steps, and T S T_S T S is bounded with one or two of the cycles ( 1 ) (1) ( 1 ) , ( 1 , 2 ) (1,2) ( 1 , 2 ) , ( 2 , 3 ) (2,3) ( 2 , 3 ) , ( 3 , 5 ) (3,5) ( 3 , 5 ) ; this holds for the squares and for a set of density 3 / 5 3/5 3/5 . Two steps up in a row already allow divergent orbits (Theorem 3.3).
The density of S S S turns out to say very little about T S T_S T S . A single chain has density zero and gives an increasing orbit; even periodic sets of arbitrarily small density can give increasing orbits (Theorem 3.5). In the other direction, if the complement of S S S is closed under the step down, then an orbit that leaves S S S never returns to it and falls to 1 1 1 . This “one-way door” gives sets of density one whose maps send every orbit to the fixed point 1 1 1 (Theorem 3.8 ). Table 3.1 in Section 3 collects these classes.
Table 3.1. The simplest classes of sets S S S . The classes overlap; for instance, sets whose complement is closed under D D D can be trivially bounded.
Cycles across all maps
By definition, the cycles of all maps together are the simple cycles of G G G . There are infinitely many of them: G G G is strongly connected, and every positive integer is the least element of a cycle of some map, even of a cycle with a single run of steps up (Theorem 4.1 ). On the other hand there are only finitely many cycles of each length, because a cycle of length ℓ \ell ℓ with a a a steps up satisfies 3 a < 2 ℓ 3^a<2^\ell 3 a < 2 ℓ with a gap controlled by its least element. Any set of disjoint cycles is the set of cycles of a single map (Theorem 4.3), so the cycles of single maps carry no further restriction. Table 4.1 lists all cycles of length at most 30; every one of them has a = ⌊ log 3 2 ⌋ a=\lfloor\log_3 2\rfloor a = ⌊ log 3 2 ⌋ , and we ask whether this always holds.
Table 4.1: All simple cycles of G G G , that is, all cycles of all maps T S T_S T S , of length ℓ ≤ 30 \ell\le30 ℓ ≤ 30 . There are none of the lengths 3, 4, 6, 7, 9, 11, 12, 14, 17–20, 22, 23, 25, 28, 30. Every cycle found has a = ⌊ ℓ log 3 2 ⌋ a = \lfloor\ell\log_3 2 \rfloor a = ⌊ ℓ log 3 2 ⌋ steps up.
Table 4.1.
Near the threshold
Which sets are, intuitively, the most expanding ones whose maps can still be proved to be bounded, and which are the least expanding ones whose maps can be proved to be unbounded? Since density is not the right yardstick, we measure how often an orbit goes up. A step up multiplies by about $3/2$ and a step down by about 1 / 2 1/2 1/2 , so the critical proportion of steps up is log 3 2 = 0.6309 … \log_{3} 2 = 0.6309\ldots log 3 2 = 0.6309 … , the solution of ( 3 / 2 ) p ( 1 / 2 ) 1 − p = 1 (3/2)^p(1/2)^{1-p}=1 ( 3/2 ) p ( 1/2 ) 1 − p = 1 . It is sharp from both sides (§ 7 ): every cycle has a proportion a / ℓ < log 3 2 a/\ell< \log_{3} 2 a / ℓ < log 3 2 of steps up, and these proportions come arbitrarily close to log 3 2 \log_{3} 2 log 3 2 ; every divergent orbit has a proportion of steps up that is asymptotically at least log 3 2 \log_{3} 2 log 3 2 , and there are divergent orbits whose proportion is arbitrarily close to $\log_{3} 2 ({xref}Theorem 5.2`).
For sets that are periodic modulo a power of 2 2 2 the proportion of steps up of a typical orbit can be computed. Following an orbit modulo 2 k 2^k 2 k , each step reveals one new binary digit of the starting number, and the residues form a Markov chain with transition probabilities 1 / 2 1/2 1/2 (Theorem 5.5). Its stationary distribution gives an effective up-frequency π \pi π , which is 1 / 2 1/2 1/2 for the Collatz map. It is π \pi π , not the density of S S S , that decides on which side of the threshold a typical orbit lies: if π < log 3 2 \pi< \log_{3} 2 π < log 3 2 , then almost every number eventually falls below itself, as Terras and Everett proved for the Collatz map [23 , 6 ] (Theorem 5.9), and π \pi π and the density can lie on opposite sides of log 3 2 \log_{3} 2 log 3 2 (Table 5.2 ). A stronger, uniform version of descent can be decided by a finite computation on the residue graph, and when it holds it yields a complete proof that every orbit reaches one of finitely many cycles, with a certificate that can be checked by hand (Theorem 5.11 ). Finally, Mahler’s question whether Z Z Z -numbers exist [13 ] would be answered by a statement about one periodic map of the family, with π = 5 / 6 \pi= 5/6 π = 5/6 (Theorem 5.13).
Table 5.2. Density and effective up-frequency π \pi π of some periodic sets; each of these residue graphs has a single closed class. Residues are taken modulo the given modulus, and 0 stands for the multiples of the modulus. In the last four rows 0.438 = 7/16, 0.786 = 11/14, 0.688 = 11/16, 0.303 = 10/33 and 0.420 = 73/174; the last set has the largest π \pi π among the uniformly descending sets modulo 16 (Table 5.3 ), and the one before it is the set of Theorem 6.4 .
How far is the Collatz map from provable behaviour?
The Collatz map is T S T_S T S for the odd numbers. Which modifications of this set make the behaviour of the map provable, either that all orbits reach ( 1 , 2 ) (1,2) ( 1 , 2 ) or that some orbit diverges, and how small can such a modification be? Table 1.1 summarizes the answers of Section 6.
Table 1.1. Modifications of the Collatz set 2 N − 1 2\mathbb{N}-1 2 N − 1 and what they make provable (Section 6). The middle column counts the modified numbers below N N N .
So a logarithmically thin addition already gives a provably divergent orbit, while the smallest periodic removal that we found to give provable convergence changes 4.3 % 4.3\% 4.3% of all integers. Its proof is a finite certificate of the same kind as above, and finding the smallest such removal modulo 2 k 2^k 2 k is a hitting-set problem for the cycles of the residue graph that expand, which are the shadows of the cycles of the Collatz map at negative rational numbers, such as − 1 -1 − 1 and − 5 → − 7 → − 10 → − 5 -5 \to-7 \to-10 \to-5 − 5 → − 7 → − 10 → − 5 (Theorem 6.5). We do not know whether the proportion of changed numbers can be made arbitrarily small, or whether removing odd numbers alone can ever produce a divergent orbit.
The map T N = U T_N = U T N = U appears in Mahler’s work on Z Z Z -numbers [13 ] , its orbit of 1 in Odlyzko and Wilf’s study of the Josephus problem [19 ] , the fractional parts of ξ ( 3 / 2 ) n \xi(3/2)^n ξ ( 3/2 ) n in the work of Flatto, Lagarias and Pollington [7 ] , and related questions in the number systems with rational base of Akiyama, Frougny and Sakarovitch [1 ] . Mignosi [15 ] replaced the multiplier 3 / 2 3/2 3/2 at odd numbers by an arbitrary β > 1 \beta> 1 β > 1 . Steiner [22 ] and Simons and de Weger [21 ] bounded the Collatz cycles with few runs of odd steps, and the fact that almost all orbits of the Collatz map fall below their starting value is due to Terras [23 ] and Everett [6 ] . Applegate and Lagarias [3 ] proved Farkas’s weak 3 x + 1 3x+1 3 x + 1 conjecture, a statement that steps combined freely reach every positive integer; Theorem 4.1 (a) is a statement of the same kind for G G G . Generalized Collatz maps [5 , 14 , 8 ] contain T S T_S T S for every periodic S S S , and questions about them are undecidable in general [5 , 8 ] . The counting argument behind our Theorem 5.5, that every step reveals one new binary digit, goes back to Terras [23 ] ; see [9 ] . Yolcu, Aaronson and Heule [25 ] encoded the Collatz map and some of its variants as string rewriting systems and proved termination for several variants automatically; the weight certificates of Sections 5.4 and 6 are proofs of a much simpler kind. Monks, Monks, Monks and Monks [16 ] used the cycles of the residue graphs of the Collatz map to show that every divergent Collatz orbit must meet certain residue classes, among them the classes 9, 15 (mod 16) of Theorem 6.4 ; see Theorem 6.6. Choices between steps appear in a two-player game of Althöfer, Hartisch and Zipproth [2 ] and in the branching maps of [24 Section 7] . We have not found the maps T S T_S T S for arbitrary S S S , or the graph G G G , in the literature surveyed in [10 , 11 ] .
Organization and notation
Section 2 introduces the graph G G G and the dictionary, Section 3 the simplest classes of sets, and Section 4 the cycles of all maps. Section 5 is about the threshold log 3 2 \log_3 2 log 3 2 and periodic sets, Section 6 about modifications of the Collatz set, and Section 7 collects open questions. Section A describes the computations.
For integers a ≤ b a \le b a ≤ b we write [ a , b ] = { a , … , b } [a,b] = \{a,\ldots,b\} [ a , b ] = { a , … , b } and [ a , ∞ ) = { a , a + 1 , … } [a,\infty) = \{a,a+1,\ldots\} [ a , ∞ ) = { a , a + 1 , … } ; for real numbers u < v u < v u < v , ( u , v ] (u,v] ( u , v ] denotes the set of integers x x x with u < x ≤ v u < x \le v u < x ≤ v . We write # A \#A # A for the number of elements of a finite set A A A , N 0 = { 0 , 1 , 2 , … } \mathbb{N}_0 = \{0,1,2,\ldots\} N 0 = { 0 , 1 , 2 , … } , 2 N 2\mathbb{N} 2 N and 2 N − 1 2\mathbb{N}-1 2 N − 1 for the even and the odd positive integers, and similarly 4 N = { 4 , 8 , … } 4\mathbb{N} = \{4,8,\ldots\} 4 N = { 4 , 8 , … } , 4 N − 2 = { 2 , 6 , 10 , … } 4\mathbb{N}-2 = \{2,6,10,\ldots\} 4 N − 2 = { 2 , 6 , 10 , … } , 4 N − 3 = { 1 , 5 , 9 , … } 4\mathbb{N}-3 = \{1,5,9,\ldots\} 4 N − 3 = { 1 , 5 , 9 , … } and 4 N − 1 = { 3 , 7 , 11 , … } 4\mathbb{N}-1 = \{3,7,11,\ldots\} 4 N − 1 = { 3 , 7 , 11 , … } . A set S S S has (natural) density δ \delta δ if # ( S ∩ [ 1 , N ] ) / N → δ \#(S \cap[1,N])/N \to\delta # ( S ∩ [ 1 , N ]) / N → δ , and lower and upper density are the lim inf \liminf lim inf and the lim sup \limsup lim sup of this ratio. We write { t } = t − ⌊ t ⌋ \{t\} = t - \lfloor t \rfloor { t } = t − ⌊ t ⌋ for the fractional part of a real number t t t , and x m o d m x \bmod m x mod m for the least nonnegative residue. A set S S S is periodic modulo m m m if whether x ∈ S x \in S x ∈ S depends only on x m o d m x \bmod m x mod m .
The maps and the up-down graph
The two steps
We collect the elementary properties of the two steps that are used throughout. The only non-obvious one is (d): iterating the step up behaves like multiplying by 3 / 2 3/2 3/2 , up to a bounded error that is fixed once and for all by the starting number.
Lemma 2.1. Let x , y ∈ N x,y \in\mathbb{N} x , y ∈ N and e = x m o d 2 e=x \bmod2 e = x mod 2 .
(a) U ( x ) = ( 3 x + e ) / 2 U(x)=(3x+e)/2 U ( x ) = ( 3 x + e ) /2 and D ( x ) = ( x + e ) / 2 D(x)=(x+e)/2 D ( x ) = ( x + e ) /2 . The map U U U is strictly increasing and D D D is non-decreasing; U ( x ) > x U(x)>x U ( x ) > x , and D ( x ) < x D(x)<x D ( x ) < x for x ≥ 2 x\ge2 x ≥ 2 .
(b) D s ( y ) = ⌈ y / 2 s ⌉ D^{s}(y)=\lceil y/2^{s}\rceil D s ( y ) = ⌈ y / 2 s ⌉ for s ≥ 0 s\ge0 s ≥ 0 . In particular every orbit of D D D reaches 1 1 1 .
(c) For an integer B B B , U ( y ) > B U(y)>B U ( y ) > B if and only if y > 2 B / 3 y>2B/3 y > 2 B /3 .
(d) 3 y / 2 ≤ U ( y ) 3y/2\le U(y) 3 y /2 ≤ U ( y ) and U ( y ) + 1 ≤ 3 2 ( y + 1 ) U(y)+1\le\frac{3}{2}(y+1) U ( y ) + 1 ≤ 2 3 ( y + 1 ) . Hence for every x x x there is a number K x ∈ ( x , x + 1 ) K_x\in(x,x+1) K x ∈ ( x , x + 1 ) with K x ( 3 / 2 ) r − 1 < U r ( x ) < K x ( 3 / 2 ) r K_x(3/2)^r-1<U^r(x)<K_x(3/2)^r K x ( 3/2 ) r − 1 < U r ( x ) < K x ( 3/2 ) r , that is, U r ( x ) = ⌊ K x ( 3 / 2 ) r ⌋ U^r(x)=\lfloor K_x(3/2)^r\rfloor U r ( x ) = ⌊ K x ( 3/2 ) r ⌋ , for all r ≥ 0 r\ge0 r ≥ 0 .
(e) The image of U U U is { y ≥ 2 : y ≢ 1 ( m o d 3 ) } \{y\ge2:y\not\equiv1\pmod3\} { y ≥ 2 : y ≡ 1 ( mod 3 )} .
(f) U ( x + 2 m ) = U ( x ) + 3 m U(x+2m)=U(x)+3m U ( x + 2 m ) = U ( x ) + 3 m and D ( x + 2 m ) = D ( x ) + m D(x+2m)=D(x)+m D ( x + 2 m ) = D ( x ) + m for all m ∈ N 0 m\in\mathbb{N}_0 m ∈ N 0 .
Proof. (a) is immediate. (b) follows from ⌈ ⌈ y / a ⌉ / b ⌉ = ⌈ y / ( a b ) ⌉ \lceil\lceil y/a\rceil/b\rceil=\lceil y/(ab)\rceil ⌈⌈ y / a ⌉ / b ⌉ = ⌈ y / ( ab )⌉ for integers y y y and a , b ≥ 1 a,b\ge1 a , b ≥ 1 . (c) ⌈ 3 y / 2 ⌉ ≥ B + 1 \lceil3y/2\rceil\ge B+1 ⌈ 3 y /2 ⌉ ≥ B + 1 if and only if 3 y / 2 > B 3y/2>B 3 y /2 > B . (d) The first inequality is clear, and U ( y ) + 1 ≤ ( 3 y + 1 ) / 2 + 1 = 3 2 ( y + 1 ) U(y)+1\le(3y+1)/2+1=\frac{3}{2}(y+1) U ( y ) + 1 ≤ ( 3 y + 1 ) /2 + 1 = 2 3 ( y + 1 ) . So a r = ( 2 / 3 ) r U r ( x ) a_r=(2/3)^rU^r(x) a r = ( 2/3 ) r U r ( x ) is non-decreasing in r r r , b r = ( 2 / 3 ) r ( U r ( x ) + 1 ) b_r=(2/3)^r(U^r(x)+1) b r = ( 2/3 ) r ( U r ( x ) + 1 ) is non-increasing, and b r − a r = ( 2 / 3 ) r b_r-a_r=(2/3)^r b r − a r = ( 2/3 ) r tends to 0 0 0 ; both converge to some K x K_x K x with a r ≤ K x ≤ b r a_r\le K_x\le b_r a r ≤ K x ≤ b r . If a r = K x a_r=K_x a r = K x for some r r r , then a r ′ = a r a_{r'}=a_r a r ′ = a r for all r ′ ≥ r r'\ge r r ′ ≥ r , so U r ′ ( x ) = ( 3 / 2 ) r ′ − r U r ( x ) U^{r'}(x)=(3/2)^{r'-r}U^r(x) U r ′ ( x ) = ( 3/2 ) r ′ − r U r ( x ) would be an integer for all r ′ ≥ r r'\ge r r ′ ≥ r , which is impossible. Similarly b r = K x b_r=K_x b r = K x would make ( 3 / 2 ) r ′ − r ( U r ( x ) + 1 ) (3/2)^{r'-r}(U^r(x)+1) ( 3/2 ) r ′ − r ( U r ( x ) + 1 ) an integer for all r ′ ≥ r r'\ge r r ′ ≥ r . So a r < K x < b r a_r<K_x<b_r a r < K x < b r for all r r r , which is the claim; for r = 0 r=0 r = 0 it gives x < K x < x + 1 x<K_x<x+1 x < K x < x + 1 . (e) U ( 2 k ) = 3 k U(2k)=3k U ( 2 k ) = 3 k and U ( 2 k − 1 ) = 3 k − 1 U(2k-1)=3k-1 U ( 2 k − 1 ) = 3 k − 1 . (f) x x x and x + 2 m x+2m x + 2 m have the same parity.
For example, K 1 = 1.6222705 … K_1=1.6222705\ldots K 1 = 1.6222705 … is the constant of Odlyzko and Wilf [19 ] , and U r ( 1 ) = ⌊ K 1 ( 3 / 2 ) r ⌋ U^r(1)=\lfloor K_1(3/2)^r\rfloor U r ( 1 ) = ⌊ K 1 ( 3/2 ) r ⌋ for all r r r .
The up-down graph
Definition 2.2. The up-down graph G G G is the directed graph with vertex set N \mathbb{N} N and, at every vertex x x x , an up-edge x → U ( x ) x\to U(x) x → U ( x ) and a down-edge x → D ( x ) x\to D(x) x → D ( x ) (a loop at x = 1 x=1 x = 1 ). For A ⊆ B ⊆ N A\subseteq B\subseteq\mathbb{N} A ⊆ B ⊆ N let G ⟨ A , B ⟩ G_{\langle A,B\rangle} G ⟨ A , B ⟩ be the spanning subgraph that keeps the up-edge at x x x if and only if x ∈ B x\in B x ∈ B and the down-edge if and only if x ∉ A x\notin A x ∈ / A , and let G S = G ⟨ S , S ⟩ G_S=G_{\langle S,S\rangle} G S = G ⟨ S , S ⟩ . We also write ⟨ A , B ⟩ \langle A,B\rangle ⟨ A , B ⟩ for the family of the maps T S T_S T S with A ⊆ S ⊆ B A\subseteq S\subseteq B A ⊆ S ⊆ B .
For example, G ⟨ ∅ , 2 N ⟩ G_{\langle\varnothing,2\mathbb{N}\rangle} G ⟨ ∅ , 2 N ⟩ keeps all down-edges and the up-edges at the even numbers; it is the union of the graphs of all maps T S T_S T S with S ⊆ 2 N S\subseteq2\mathbb{N} S ⊆ 2 N , that is, of all maps obtained from the shifted Collatz map T 2 N T_{2\mathbb{N}} T 2 N by turning some of its steps up into steps down. Similarly G ⟨ 2 N − 1 , N ⟩ G_{\langle2\mathbb{N}-1,\mathbb{N}\rangle} G ⟨ 2 N − 1 , N ⟩ belongs to the maps that go up at every odd number and are free at the even numbers.
Thus G S G_S G S is the graph of T S T_S T S , with one out-edge at every vertex, and G ⟨ A , B ⟩ = ⋃ A ⊆ S ⊆ B G S G_{\langle A,B\rangle}=\bigcup_{A\subseteq S\subseteq B}G_S G ⟨ A , B ⟩ = ⋃ A ⊆ S ⊆ B G S : on A A A the step up is forced, outside B B B the step down is forced, and on B ∖ A B\setminus A B ∖ A both steps are allowed. Every spanning subgraph of G G G in which each vertex keeps at least one of its two out-edges is G ⟨ A , B ⟩ G_{\langle A,B\rangle} G ⟨ A , B ⟩ for exactly one pair A ⊆ B A\subseteq B A ⊆ B , and G = G ⟨ ∅ , N ⟩ G=G_{\langle\varnothing,\mathbb{N}\rangle} G = G ⟨ ∅ , N ⟩ . So
the sets S S S correspond to the subgraphs with all out-degrees 1,
the families ⟨ A , B ⟩ \langle A, B\rangle ⟨ A , B ⟩ correspond to the subgraphs with all out-degrees at least 1, and
the family of all maps corresponds to G G G .
As in [24 Lemma 7.2] , any collection S S S of sets gives the same subgraph ⋃ S ∈ S G S \bigcup_{S\in\mathcal{S}}G_S ⋃ S ∈ S G S as the family ⟨ ⋂ S , ⋃ S ⟩ \langle\bigcap\mathcal{S},\bigcup\mathcal{S}\rangle ⟨ ⋂ S , ⋃ S ⟩ , so the branching families of [24 Section 7] correspond to these subgraphs as well.
Two subgraphs are worth keeping in mind. The edges of G ∅ G_{\varnothing} G ∅ lead from 2 y − 1 2y-1 2 y − 1 and 2 y 2y 2 y to y y y , so G ∅ G_{\varnothing} G ∅ is a binary tree with root 1 (and a loop at 1); in binary, the step down sends x − 1 x-1 x − 1 to ⌊ ( x − 1 ) / 2 ⌋ \lfloor(x-1)/2\rfloor ⌊( x − 1 ) /2 ⌋ , that is, it deletes the last binary digit of x − 1 x-1 x − 1 . The graph G N G_{\mathbb{N}} G N is a disjoint union of rays, the chains of § 5.2 . A path is simple if its vertices are distinct, a ray is an infinite simple path, and a simple cycle is a closed path whose vertices are distinct.
The dictionary
Proposition 2.3 (Dictionary). Let A ⊆ B ⊆ N A \subseteq B \subseteq\mathbb{N} A ⊆ B ⊆ N and H = G ⟨ A , B ⟩ H=G_{\langle A,B\rangle} H = G ⟨ A , B ⟩ .
(a) The cycles of the maps in ⟨ A , B ⟩ \langle A,B\rangle ⟨ A , B ⟩ are exactly the simple cycles of H H H . A set of simple cycles of H H H consists of cycles of a single map in ⟨ A , B ⟩ \langle A,B\rangle ⟨ A , B ⟩ if and only if the cycles are pairwise vertex-disjoint.
(b) The divergent orbits of the maps in ⟨ A , B ⟩ \langle A,B\rangle ⟨ A , B ⟩ are exactly the rays of H H H .
(c) All maps in ⟨ A , B ⟩ \langle A,B\rangle ⟨ A , B ⟩ are bounded if and only if H H H has no ray, if and only if from every x x x only finitely many vertices can be reached in $H.
The point of the proof is that a simple cycle or a ray visits every vertex at most once, so that the choices it makes between the two edges never conflict and can be made by a single set S S S . For example, in Figure 2.1 the closed path 2 → 3 → 5 → 8 → 4 → 2 2\to3\to5\to8\to4\to2 2 → 3 → 5 → 8 → 4 → 2 is a simple cycle of G G G : it uses the up-edges at 2, 3, 5 and the down-edges at 8 and 4. So ( 2 , 3 , 5 , 8 , 4 ) (2,3,5,8,4) ( 2 , 3 , 5 , 8 , 4 ) is a cycle of T S T_S T S for every set S S S that contains 2, 3, 5 and does not contain 4, 8, such as the set of primes, and of no other map. By contrast, the closed path 2 → 3 → 2 → 1 → 2 2\to3\to2\to1\to2 2 → 3 → 2 → 1 → 2 is not simple: it would need both edges at 2, and no single map follows it.
Proof. (a) A cycle of T S T_S T S uses edges of G S ⊆ H G_S\subseteq H G S ⊆ H and visits distinct numbers. Conversely, let C \mathcal{C} C be a set of pairwise disjoint simple cycles of H H H , let V V V be the union of their vertex sets, and let V ↑ ⊆ V V^{\uparrow}\subseteq V V ↑ ⊆ V be the set of vertices at which they use the up-edge. Put S = ( A ∖ V ) ∪ V ↑ S=(A\setminus V)\cup V^{\uparrow} S = ( A ∖ V ) ∪ V ↑ . Every edge of a cycle is an edge of H H H , so V ↑ ⊆ B V^{\uparrow}\subseteq B V ↑ ⊆ B , and a vertex of V ∩ A V\cap A V ∩ A has no down-edge in H H H and lies in V ↑ V^{\uparrow} V ↑ . Hence A ⊆ S ⊆ B A\subseteq S\subseteq B A ⊆ S ⊆ B , and T S T_S T S follows every cycle of C \mathcal{C} C . Two cycles of one map are equal or disjoint, since G S G_S G S has one out-edge at every vertex. (b) A divergent orbit consists of distinct numbers, so it is a ray of G S ⊆ H G_S \subseteq H G S ⊆ H . Conversely, for a ray of H H H the construction of (a), with V V V the vertex set of the ray, gives S S S with A ⊆ S ⊆ B A \subseteq S \subseteq B A ⊆ S ⊆ B such that the orbit of the first vertex follows the ray; this orbit consists of distinct numbers, so it diverges. (c) The first equivalence follows from (b). If infinitely many vertices can be reached from x x x , the tree in which every reachable vertex other than x x x is attached to the vertex from which a breadth-first search first reaches it is infinite and has finite degrees, so by König’s lemma it has an infinite path from x x x , which is a ray of H H H ; compare [24 Lemma 7.3] . Conversely, a ray from x x x reaches infinitely many vertices.
In [24 Proposition 7.4] boundedness passed from a family to its members but not back, because there a single exponent decided the direction at infinitely many numbers; here (c) is an equivalence. Table 2.1 summarizes the correspondence. It is a duality between classes of maps and classes of subgraphs of G G G : statements about all maps at once are statements about G G G , and statements about all maps of a family are statements about a subgraph of G G G .
Table 2.1. Maps and subgraphs of the up-down graph G G G (Theorem 2.3).
Two kinds of families will appear in questions. We call a set B B B force-bounded if it forces boundedness on every map that goes up only inside B B B : T S T_S T S is bounded for every S ⊆ B S \subseteq B S ⊆ B , that is, G ⟨ ∅ , B ⟩ G_{\langle\varnothing,B\rangle} G ⟨ ∅ , B ⟩ has no ray. Dually, we call a set A A A force-divergent if it forces a divergent orbit on every map that goes up on A A A : T S T_S T S is unbounded for every S ⊇ A S \supseteq A S ⊇ A , whatever happens outside A A A . Every subset of a force-bounded set is force-bounded, and every set that contains a force-divergent set is force-divergent. For example, a set A A A that contains all the numbers x , U ( x ) , U 2 ( x ) , … x, U(x), U^2(x), \ldots x , U ( x ) , U 2 ( x ) , … for some x x x is force-divergent, since then the orbit of x x x is x , U ( x ) , U 2 ( x ) , … x, U(x), U^2(x), \ldots x , U ( x ) , U 2 ( x ) , … under every T S T_S T S with S ⊇ A S \supseteq A S ⊇ A .
Finite changes
The next lemma says that boundedness is a property of S S S at infinity. It is simple, but it is the first answer to the question of Section 6: no finite modification of the Collatz set can decide whether the Collatz map has divergent orbits.
Lemma 2.4. Let S , S ′ ⊆ N S,S' \subseteq\mathbb{N} S , S ′ ⊆ N agree on ( m , ∞ ) (m,\infty) ( m , ∞ ) for some m m m .
(a) Every divergent orbit of T S T_S T S is, from some point on, an orbit of T S ′ T_{S'} T S ′ . In particular, T S T_S T S is bounded if and only if T S ′ T_{S'} T S ′ is bounded.
(b) The cycles of T S T_S T S that lie in ( m , ∞ ) (m,\infty) ( m , ∞ ) are cycles of T S ′ T_{S'} T S ′ .
Proof. (a) A divergent orbit x 0 , x 1 , … x_0,x_1,\ldots x 0 , x 1 , … tends to infinity, so x t > m x_t>m x t > m for all t ≥ t 0 t \ge t_0 t ≥ t 0 , and then x t + 1 = T S ( x t ) = T S ′ ( x t ) x_{t+1}=T_S(x_t)=T_{S'}(x_t) x t + 1 = T S ( x t ) = T S ′ ( x t ) for t ≥ t 0 t \ge t_0 t ≥ t 0 . So x t 0 , x t 0 + 1 , … x_{t_0},x_{t_0+1},\ldots x t 0 , x t 0 + 1 , … is a divergent orbit of T S ′ T_{S'} T S ′ . The statement is symmetric in S S S and S ′ S' S ′ . (b) T S T_S T S and T S ′ T_{S'} T S ′ agree on ( m , ∞ ) (m,\infty) ( m , ∞ ) .
Finite changes can create or destroy cycles below m m m , and so they can change whether all orbits reach a given cycle; but they cannot make a bounded map out of an unbounded one, or the other way round.
The simplest classification
Barriers and trivially bounded sets
Consider an infinite set S = { s 1 < s 2 < ⋯ } S=\{s_1<s_2<\cdots\} S = { s 1 < s 2 < ⋯ } . If the next element s i + 1 s_{i+1} s i + 1 is out of reach of a step up from s i s_i s i , that is, if s i + 1 > U ( s i ) s_{i+1}>U(s_i) s i + 1 > U ( s i ) , then T S T_S T S maps [ 1 , s i + 1 − 1 ] [1,s_{i+1}-1] [ 1 , s i + 1 − 1 ] into itself: the elements of S S S in this interval are at most s i s_i s i and go up to at most U ( s i ) U(s_i) U ( s i ) , and all other numbers go down. This means that every orbit that starts below s i + 1 s_{i+1} s i + 1 stays below s i + 1 s_{i+1} s i + 1 forever. The following definition captures exactly this situation. It is based on a simple fact (Theorem 2.1(c)): the numbers x ≤ B x\le B x ≤ B whose step up leads above B B B are exactly the numbers in the interval ( 2 B / 3 , B ] (2B/3,B] ( 2 B /3 , B ] . If none of them is in S S S , nothing can cross B B B from below.
Definition 3.1. A barrier of S ⊆ N S\subseteq\mathbb{N} S ⊆ N is an integer B ≥ 1 B\ge1 B ≥ 1 such that S S S has no element in the interval ( 2 B / 3 , B ] (2B/3,B] ( 2 B /3 , B ] . The set S S S is trivially bounded if it has infinitely many barriers.
For example, let S = { 1 , 2 , 4 , 8 , 16 , … } S=\{1,2,4,8,16,\ldots\} S = { 1 , 2 , 4 , 8 , 16 , … } be the set of powers of 2 2 2 . Then B = 6 B=6 B = 6 is a barrier, since the interval ( 4 , 6 ] = { 5 , 6 } (4,6]=\{5,6\} ( 4 , 6 ] = { 5 , 6 } contains no power of 2 2 2 ; indeed the only steps up from [ 1 , 6 ] [1,6] [ 1 , 6 ] are 1 → 2 1\to2 1 → 2 , 2 → 3 2\to3 2 → 3 and 4 → 6 4\to6 4 → 6 , and none of them leaves [ 1 , 6 ] [1,6] [ 1 , 6 ] . In the same way B = 3 ⋅ 2 k − 1 B=3\cdot2^{k-1} B = 3 ⋅ 2 k − 1 is a barrier for every k ≥ 1 k\ge1 k ≥ 1 , because the largest power of 2 2 2 below it, 2 k 2^k 2 k , goes up exactly to 3 ⋅ 2 k − 1 3\cdot2^{k-1} 3 ⋅ 2 k − 1 . So the powers of 2 2 2 are trivially bounded: every orbit of their map is trapped below one of these barriers.
Proposition 3.2. Let S ⊆ N S\subseteq\mathbb{N} S ⊆ N .
(a) B B B is a barrier of S S S if and only if T S T_S T S maps [ 1 , B ] [1,B] [ 1 , B ] into itself, if and only if G S G_S G S has no edge from [ 1 , B ] [1,B] [ 1 , B ] to ( B , ∞ ) (B,\infty) ( B , ∞ ) . In G G G these edges are the up-edges at the vertices in ( 2 B / 3 , B ] (2B/3,B] ( 2 B /3 , B ] .
(b) S S S is trivially bounded if and only if S S S is finite or s i + 1 > U ( s i ) s_{i+1}>U(s_i) s i + 1 > U ( s i ) for infinitely many i i i . The barriers B ≥ s 1 B\ge s_1 B ≥ s 1 are the integers with U ( s i ) ≤ B < s i + 1 U(s_i)\le B<s_{i+1} U ( s i ) ≤ B < s i + 1 for some i i i (where s i + 1 = ∞ s_{i+1}=\infty s i + 1 = ∞ if s i s_i s i is the largest element of S S S ).
(c) If S S S is trivially bounded, then so is every subset of S S S , and T S T_S T S is bounded. Thus trivially bounded sets are force-bounded.
(d) If S S S is not trivially bounded, then # ( S ∩ [ 1 , N ] ) ≥ log 3 / 2 N − C \#(S\cap[1,N])\ge\log_{3/2}N-C # ( S ∩ [ 1 , N ]) ≥ log 3/2 N − C for some C = C ( S ) C=C(S) C = C ( S ) and all $N\ge1.
Proof. (a) Let x ≤ B x\le B x ≤ B . Then D ( x ) ≤ B D(x)\le B D ( x ) ≤ B , and U ( x ) > B U(x)>B U ( x ) > B if and only if x > 2 B / 3 x>2B/3 x > 2 B /3 by Theorem 2.1(c). So some x ≤ B x\le B x ≤ B has T S ( x ) > B T_S(x)>B T S ( x ) > B if and only if S S S meets ( 2 B / 3 , B ] (2B/3,B] ( 2 B /3 , B ] .
(b) Every B < s 1 B<s_1 B < s 1 is a barrier. For B ≥ s 1 B\ge s_1 B ≥ s 1 let s i = max ( S ∩ [ 1 , B ] ) s_i=\max(S\cap[1,B]) s i = max ( S ∩ [ 1 , B ]) , so that s i ≤ B < s i + 1 s_i\le B<s_{i+1} s i ≤ B < s i + 1 . Then B B B is a barrier if and only if s i ≤ 2 B / 3 s_i\le2B/3 s i ≤ 2 B /3 , that is, if and only if U ( s i ) ≤ B U(s_i)\le B U ( s i ) ≤ B by Theorem 2.1(c). This proves the second statement. If S S S is finite, every B ≥ U ( max S ) B\ge U(\max S) B ≥ U ( max S ) is a barrier. If S S S is infinite, the barriers B ≥ s 1 B\ge s_1 B ≥ s 1 are the integers in the finite intervals [ U ( s i ) , s i + 1 − 1 ] [U(s_i),s_{i+1}-1] [ U ( s i ) , s i + 1 − 1 ] , and there are infinitely many of them if and only if infinitely many of these intervals are nonempty, that is, s i + 1 > U ( s i ) s_{i+1}>U(s_i) s i + 1 > U ( s i ) for infinitely many i i i .
(c) A barrier of S S S is a barrier of every subset. Every x x x lies below some barrier B B B , and by (a) its orbit stays in [ 1 , B ] [1,B] [ 1 , B ] . (d) The idea is that a set without large barriers must have an element in every interval ( 2 B / 3 , B ] (2B/3, B] ( 2 B /3 , B ] with B B B large, and about log 3 / 2 N \log_{3/2} N log 3/2 N such intervals fit disjointly below N N N . Let B 0 B_0 B 0 be larger than all barriers of S S S , and put B k + 1 = U ( B k ) B_{k+1}=U(B_k) B k + 1 = U ( B k ) . Since 2 B k + 1 / 3 ≥ B k 2B_{k+1}/3 \ge B_k 2 B k + 1 /3 ≥ B k , the intervals ( 2 B k / 3 , B k ] (2B_k/3, B_k] ( 2 B k /3 , B k ] are pairwise disjoint, and each contains an element of S S S , because B k B_k B k is not a barrier; so # ( S ∩ [ 1 , B k ] ) ≥ k \#(S \cap[1, B_k]) \ge k # ( S ∩ [ 1 , B k ]) ≥ k . By Theorem 2.1(d), B k + 1 ≤ ( 3 / 2 ) k ( B 0 + 1 ) B_k+1 \le(3/2)^k(B_0+1) B k + 1 ≤ ( 3/2 ) k ( B 0 + 1 ) . For B k ≤ N < B k + 1 B_k \le N < B_{k+1} B k ≤ N < B k + 1 this gives # ( S ∩ [ 1 , N ] ) ≥ k ≥ log 3 / 2 ( ( N + 1 ) / ( B 0 + 1 ) ) − 1 \#(S \cap[1,N]) \ge k \ge\log_{3/2}((N+1)/(B_0+1))-1 # ( S ∩ [ 1 , N ]) ≥ k ≥ log 3/2 (( N + 1 ) / ( B 0 + 1 )) − 1 .
For a trivially bounded S S S with barriers B 1 < B 2 < ⋯ B_1<B_2<\cdots B 1 < B 2 < ⋯ , the map T S T_S T S restricts to self-maps of the nested finite sets [ 1 , B k ] [1,B_k] [ 1 , B k ] , and all questions about T S T_S T S are finite questions. Finite sets, the powers of 2 2 2 and the factorials are trivially bounded, and so are unions of intervals [ a k , b k ] [a_k,b_k] [ a k , b k ] with a k + 1 > U ( b k ) a_{k+1}>U(b_k) a k + 1 > U ( b k ) , which can have upper density 1 1 1 . So it is the gaps of S S S , not its density, that matter here.
Most natural infinite sets are not trivially bounded. If S S S has density δ > 0 \delta>0 δ > 0 , then # ( S ∩ ( 2 B / 3 , B ] ) = δ B / 3 + o ( B ) \#(S \cap(2B/3,B])=\delta B/3+o(B) # ( S ∩ ( 2 B /3 , B ]) = δ B /3 + o ( B ) , so S S S has only finitely many barriers. The odd numbers have the single barrier 2 2 2 , the even numbers the barriers 1 1 1 and 3 3 3 , and the squares the barriers 2 , 3 , 6 , 7 , 8 , 14 , 15 , 24 2,3,6,7,8,14,15,24 2 , 3 , 6 , 7 , 8 , 14 , 15 , 24 . For the primes, Nagura’s theorem [18 ] gives a prime in ( x , 6 x / 5 ] (x,6x/5] ( x , 6 x /5 ] for every x ≥ 25 x \ge25 x ≥ 25 , so for B ≥ 38 B \ge38 B ≥ 38 there is a prime in ( 2 B / 3 , 4 B / 5 ] ⊆ ( 2 B / 3 , B ] (2B/3,4B/5] \subseteq(2B/3,B] ( 2 B /3 , 4 B /5 ] ⊆ ( 2 B /3 , B ] , and a check of B ≤ 37 B \le37 B ≤ 37 leaves only the barrier B = 1 B=1 B = 1 .
The bound in (d) is sharp up to the constant. The chain of 1 1 1 , the set { U r ( 1 ) : r ≥ 0 } = { 1 , 2 , 3 , 5 , 8 , 12 , 18 , 27 , … } \{U^r(1):r \ge0\}=\{1,2,3,5,8,12,18,27,\ldots\} { U r ( 1 ) : r ≥ 0 } = { 1 , 2 , 3 , 5 , 8 , 12 , 18 , 27 , … } , has s i + 1 = U ( s i ) s_{i+1}=U(s_i) s i + 1 = U ( s i ) for all i i i , so it is not trivially bounded, and it has log 3 / 2 N + O ( 1 ) \log_{3/2}N+O(1) log 3/2 N + O ( 1 ) elements below N N N . Under its map every orbit diverges: a number outside the set goes down, so its orbit decreases until it meets the set (at the latest at 1 1 1 ), and from then on it goes up forever.
Chains and runs
If S S S is not trivially bounded, every large B B B is jumped over: some element of S S S in ( 2 B / 3 , B ] (2B/3,B] ( 2 B /3 , B ] goes up to a number above B B B . To describe these sets we use the structure of the step up alone. By Theorem 2.1(a) and (e), the map U U U is strictly increasing and its image is the set of y ≥ 2 y \ge2 y ≥ 2 with y ≢ 1 ( m o d 3 ) y \not\equiv1 \pmod{3} y ≡ 1 ( mod 3 ) . Hence N \mathbb{N} N is the disjoint union of the chains
Γ c = { c , U ( c ) , U 2 ( c ) , … } , c ≡ 1 ( m o d 3 ) , \Gamma_c=\{c,U(c),U^2(c),\ldots\},\qquad c\equiv1\pmod{3}, Γ c = { c , U ( c ) , U 2 ( c ) , … } , c ≡ 1 ( mod 3 ) ,
which are the orbits of T N T_{\mathbb{N}} T N and the rays of G N G_{\mathbb{N}} G N . For example,
Γ 1 = { 1 , 2 , 3 , 5 , 8 , 12 , 18 , 27 , … } , Γ 4 = { 4 , 6 , 9 , 14 , 21 , 32 , … } , Γ 7 = { 7 , 11 , 17 , 26 , 39 , … } . \Gamma_1=\{1,2,3,5,8,12,18,27,\ldots\},\qquad\Gamma_4=\{4,6,9,14,21,32,\ldots\},\qquad\Gamma_7=\{7,11,17,26,39,\ldots\}. Γ 1 = { 1 , 2 , 3 , 5 , 8 , 12 , 18 , 27 , … } , Γ 4 = { 4 , 6 , 9 , 14 , 21 , 32 , … } , Γ 7 = { 7 , 11 , 17 , 26 , 39 , … } .
Every x x x is U d ( c ) U^d(c) U d ( c ) for a unique root c ≡ 1 ( m o d 3 ) c\equiv1\pmod{3} c ≡ 1 ( mod 3 ) and a unique depth d = d ( x ) d=d(x) d = d ( x ) : the depth is the number of times that U − 1 U^{-1} U − 1 can be applied to x x x . For instance 21 = U 4 ( 4 ) 21=U^4(4) 21 = U 4 ( 4 ) has root 4 4 4 and depth 4 4 4 . For any x x x , the set { x , U ( x ) , U 2 ( x ) , … } \{x,U(x),U^2(x),\ldots\} { x , U ( x ) , U 2 ( x ) , … } is the part of the chain of x x x from x x x on; we call this a tail of the chain.
An orbit of T S T_S T S that arrives at an element x x x of S S S goes up to U ( x ) U(x) U ( x ) , and it goes up again exactly if U ( x ) ∈ S U(x)\in S U ( x ) ∈ S . So the steps up of an orbit come in runs, and a run is a segment of a chain that lies in S S S . For x ∈ S x\in S x ∈ S let λ S ( x ) ∈ { 1 , 2 , … , ∞ } \lambda_S(x)\in\{1,2,\ldots,\infty\} λ S ( x ) ∈ { 1 , 2 , … , ∞ } be the largest λ \lambda λ such that x , U ( x ) , … , U λ − 1 ( x ) x,U(x),\ldots,U^{\lambda-1}(x) x , U ( x ) , … , U λ − 1 ( x ) all lie in S S S ; we call this number the run of x x x in S S S . An orbit that arrives at x ∈ S x\in S x ∈ S makes exactly λ S ( x ) \lambda_S(x) λ S ( x ) steps up before its next step down. Let λ ( S ) = sup x ∈ S λ S ( x ) \lambda(S)=\sup_{x\in S}\lambda_S(x) λ ( S ) = sup x ∈ S λ S ( x ) , with λ ( ∅ ) = 0 \lambda(\varnothing)=0 λ ( ∅ ) = 0 .
For example, let S = 2 N − 1 S=2\mathbb{N}-1 S = 2 N − 1 , so that T S T_S T S is the Collatz map. From 7 7 7 the orbit goes up three times, 7 → 11 → 17 → 26 7\to11\to17\to26 7 → 11 → 17 → 26 , and then down, because 7 , 11 , 17 7,11,17 7 , 11 , 17 are odd and 26 26 26 is even. So λ S ( 7 ) = 3 \lambda_S(7)=3 λ S ( 7 ) = 3 , λ S ( 11 ) = 2 \lambda_S(11)=2 λ S ( 11 ) = 2 and λ S ( 17 ) = 1 \lambda_S(17)=1 λ S ( 17 ) = 1 . In general, for odd x x x the run λ 2 N − 1 ( x ) \lambda_{2\mathbb{N}-1}(x) λ 2 N − 1 ( x ) is the exponent of 2 2 2 in x + 1 x+1 x + 1 , since U ( x ) + 1 = 3 2 ( x + 1 ) U(x)+1=\frac{3}{2}(x+1) U ( x ) + 1 = 2 3 ( x + 1 ) for odd x x x . All these runs are finite, but they are not bounded: λ ( 2 N − 1 ) = ∞ \lambda(2\mathbb{N}-1)=\infty λ ( 2 N − 1 ) = ∞ .
We call an orbit x 0 , x 1 , x 2 , … x_0,x_1,x_2,\ldots x 0 , x 1 , x 2 , … increasing if it goes up at every step, x 0 < x 1 < x 2 < ⋯ x_0<x_1<x_2<\cdots x 0 < x 1 < x 2 < ⋯ . An increasing orbit diverges, and it is the simplest kind of divergent orbit. The first part of the next proposition says when it occurs: an orbit that always goes up is an orbit of U U U , so all of its elements must lie in S S S .
Proposition 3.3 (Runs). Let S ⊆ N S \subseteq\mathbb{N} S ⊆ N .
(a) The orbit of x x x under T S T_S T S is increasing if and only if all the numbers x , U ( x ) , U 2 ( x ) , … x,U(x),U^2(x),\ldots x , U ( x ) , U 2 ( x ) , … lie in S S S , that is, if and only if x ∈ S x \in S x ∈ S and λ S ( x ) = ∞ \lambda_S(x)=\infty λ S ( x ) = ∞ . Consequently, T S T_S T S has an increasing orbit if and only if S S S contains a tail of a chain.
(b) If λ ( S ) ≤ 1 \lambda(S) \le1 λ ( S ) ≤ 1 , that is, if U ( x ) ∉ S U(x) \notin S U ( x ) ∈ / S for every x ∈ S x \in S x ∈ S , then for every x ≥ 4 x \ge4 x ≥ 4 either T S ( x ) < x T_S(x)<x T S ( x ) < x or T S 2 ( x ) = ⌈ 3 x / 4 ⌉ < x T_S^2(x)=\lceil3x/4\rceil<x T S 2 ( x ) = ⌈ 3 x /4 ⌉ < x . Hence T S T_S T S is bounded, and every orbit ends in one of the cycles ( 1 ) (1) ( 1 ) , ( 1 , 2 ) (1,2) ( 1 , 2 ) , ( 2 , 3 ) (2,3) ( 2 , 3 ) , ( 3 , 5 ) (3,5) ( 3 , 5 ) ; these are cycles of T S T_S T S if and only if 1 ∉ S 1 \notin S 1 ∈ / S , 1 ∈ S 1 \in S 1 ∈ S , 2 ∈ S 2 \in S 2 ∈ S and 3 ∈ S 3 \in S 3 ∈ S , respectively. In particular, T S T_S T S has one or two cycles.
(c) For every y ≥ 51 y \ge51 y ≥ 51 , the path from y y y that repeats the steps up, up, down is a ray of G G G . The set S S S of the vertices at which it goes up has λ ( S ) = 2 \lambda(S)=2 λ ( S ) = 2 , and the orbit of y y y under T S T_S T S diverges.
Here is what the three parts say. For (a), take the chain Γ 4 = { 4 , 6 , 9 , 14 , 21 , 32 , … } \Gamma_4=\{4,6,9,14,21,32,\ldots\} Γ 4 = { 4 , 6 , 9 , 14 , 21 , 32 , … } . The orbit of 4 4 4 under T S T_S T S is 4 , 6 , 9 , 14 , 21 , 32 , … 4,6,9,14,21,32,\ldots 4 , 6 , 9 , 14 , 21 , 32 , … if and only if S S S contains all these numbers. If S S S contains only the tail 9 , 14 , 21 , 32 , … 9,14,21,32,\ldots 9 , 14 , 21 , 32 , … of this chain, then the orbit of 9 9 9 is increasing, and so is, from 9 9 9 on, every orbit that reaches 9 9 9 . If S S S misses infinitely many elements of every chain, as the odd numbers do, then all runs are finite and no orbit is increasing. Such a map can still have divergent orbits, which go down infinitely often but go up more: (c) gives the simplest example, in which all runs have length 2. Part (b) says that runs of length 1 are not enough for this. So the threshold lies between runs of length one and two: a step up followed by a step down multiplies a number by about 3 / 4 3/4 3/4 , while two steps up and one step down multiply it by about 9 / 8 9/8 9/8 . We return to this threshold in Section 5.
Proof. (a) If the orbit of x x x is increasing, then each of its steps is a step up, so the orbit is x , U ( x ) , U 2 ( x ) , … x,U(x),U^2(x),\ldots x , U ( x ) , U 2 ( x ) , … , and each of these numbers lies in S S S , because T S T_S T S goes up only at elements of S S S . Conversely, if all U j ( x ) U^j(x) U j ( x ) lie in S S S , then T S ( U j ( x ) ) = U j + 1 ( x ) T_S(U^j(x))=U^{j+1}(x) T S ( U j ( x )) = U j + 1 ( x ) for all j ≥ 0 j \ge0 j ≥ 0 , so the orbit of x x x is x , U ( x ) , U 2 ( x ) , … x,U(x),U^2(x),\ldots x , U ( x ) , U 2 ( x ) , … , which is increasing. The last statement follows, since the set { x , U ( x ) , U 2 ( x ) , … } \{x,U(x),U^2(x),\ldots\} { x , U ( x ) , U 2 ( x ) , … } is a tail of a chain.
(b) Let x ≥ 4 x \ge4 x ≥ 4 . If x ∉ S x \notin S x ∈ / S , then T S ( x ) = D ( x ) < x T_S(x)=D(x)<x T S ( x ) = D ( x ) < x . If x ∈ S x \in S x ∈ S , then U ( x ) ∉ S U(x) \notin S U ( x ) ∈ / S , so T S 2 ( x ) = D ( U ( x ) ) = ⌈ 3 x / 4 ⌉ T_S^2(x)=D(U(x))=\lceil3x/4\rceil T S 2 ( x ) = D ( U ( x )) = ⌈ 3 x /4 ⌉ by Theorem 2.1(b), and ⌈ 3 x / 4 ⌉ ≤ x − 1 \lceil3x/4\rceil\le x-1 ⌈ 3 x /4 ⌉ ≤ x − 1 for x ≥ 4 x \ge4 x ≥ 4 . So from every x ≥ 4 x \ge4 x ≥ 4 the orbit reaches a smaller number in one or two steps, passing at most through U ( x ) U(x) U ( x ) . Hence every orbit is bounded and reaches [ 1 , 3 ] [1,3] [ 1 , 3 ] , and every cycle has its least element in [ 1 , 3 ] [1,3] [ 1 , 3 ] . If 1 ∉ S 1 \notin S 1 ∈ / S , then 1 is fixed; if 1 ∈ S 1 \in S 1 ∈ S , then 2 = U ( 1 ) ∉ S 2=U(1) \notin S 2 = U ( 1 ) ∈ / S and the orbit of 1 is ( 1 , 2 ) (1,2) ( 1 , 2 ) . If 2 ∈ S 2 \in S 2 ∈ S , then 3 ∉ S 3 \notin S 3 ∈ / S and ( 2 , 3 ) (2,3) ( 2 , 3 ) is a cycle; if 2 ∉ S 2 \notin S 2 ∈ / S , then 2 goes to 1. If 3 ∈ S 3 \in S 3 ∈ S , then 5 ∉ S 5 \notin S 5 ∈ / S and ( 3 , 5 ) (3,5) ( 3 , 5 ) is a cycle; if 3 ∉ S 3 \notin S 3 ∈ / S , then 3 goes to 2. So every orbit ends in one of the four cycles, and the conditions are as stated. Exactly one of (1) and (1,2) occurs. Of the other two cycles at most one occurs, since 2 ∈ S 2 \in S 2 ∈ S excludes 3 = U ( 2 ) ∈ S 3=U(2) \in S 3 = U ( 2 ) ∈ S , and (2,3) does not occur together with (1,2), since 1 ∈ S 1 \in S 1 ∈ S excludes 2 = U ( 1 ) ∈ S 2=U(1) \in S 2 = U ( 1 ) ∈ S . So T S T_S T S has one or two cycles.
(c) We have to show that the path never visits a number twice; then it is a ray, and by Theorem 2.3(b) it is a divergent orbit of the map that goes up exactly at its up-vertices. Let y 0 = y y_0=y y 0 = y and y k + 1 = F ( y k ) y_{k+1}=F(y_k) y k + 1 = F ( y k ) , where F = D ∘ U ∘ U F=D\circ U\circ U F = D ∘ U ∘ U , so that the path is y 0 , U ( y 0 ) , U 2 ( y 0 ) , y 1 , U ( y 1 ) , U 2 ( y 1 ) , … y_0,U(y_0),U^2(y_0),y_1,U(y_1),U^2(y_1),\ldots y 0 , U ( y 0 ) , U 2 ( y 0 ) , y 1 , U ( y 1 ) , U 2 ( y 1 ) , … . By Theorem 2.1(a), 3 2 z ≤ U ( z ) ≤ 3 2 z + 1 2 \frac{3}{2}z\le U(z)\le\frac{3}{2}z+\frac{1}{2} 2 3 z ≤ U ( z ) ≤ 2 3 z + 2 1 , hence 9 4 z ≤ U 2 ( z ) ≤ 9 4 z + 5 4 \frac{9}{4}z\le U^2(z)\le\frac{9}{4}z+\frac{5}{4} 4 9 z ≤ U 2 ( z ) ≤ 4 9 z + 4 5 and 9 8 z ≤ F ( z ) ≤ 9 8 z + 9 8 \frac{9}{8}z\le F(z)\le\frac{9}{8}z+\frac{9}{8} 8 9 z ≤ F ( z ) ≤ 8 9 z + 8 9 . By induction,
( 9 8 ) j y k ≤ y k + j ≤ ( 9 8 ) j ( y k + 9 ) − 9 ( j ≥ 0 ) , (2) \left(\frac{9}{8}\right)^j y_k\le y_{k+j}\le\left(\frac{9}{8}\right)^j(y_k+9)-9 \qquad(j\ge0), \tag*{(2)} ( 8 9 ) j y k ≤ y k + j ≤ ( 8 9 ) j ( y k + 9 ) − 9 ( j ≥ 0 ) , (2)
and the three sequences ( y k ) (y_k) ( y k ) , ( U ( y k ) ) (U(y_k)) ( U ( y k )) , ( U 2 ( y k ) ) (U^2(y_k)) ( U 2 ( y k )) are strictly increasing. Within a block y k < U ( y k ) < U 2 ( y k ) y_k<U(y_k)<U^2(y_k) y k < U ( y k ) < U 2 ( y k ) . So a repetition can only be of the form y k + j = U ( y k ) y_{k+j}=U(y_k) y k + j = U ( y k ) , y k + j = U 2 ( y k ) y_{k+j}=U^2(y_k) y k + j = U 2 ( y k ) or U ( y k + j ) = U 2 ( y k ) U(y_{k+j})=U^2(y_k) U ( y k + j ) = U 2 ( y k ) with j ≥ 1 j \ge1 j ≥ 1 , and the third is the first, as U U U is injective. Let z = y k ≥ y 0 ≥ 51 z=y_k \ge y_0 \ge51 z = y k ≥ y 0 ≥ 51 . For j ≤ 3 j \le3 j ≤ 3 , (2) gives y k + j ≤ ( 9 / 8 ) 3 ( z + 9 ) − 9 < 1.4239 z + 3.82 < 3 2 z ≤ U ( z ) y_{k+j} \le(9/8)^3(z+9)-9 < 1.4239z+3.82 < \frac{3}{2}z \le U(z) y k + j ≤ ( 9/8 ) 3 ( z + 9 ) − 9 < 1.4239 z + 3.82 < 2 3 z ≤ U ( z ) , and for j ≥ 4 j \ge4 j ≥ 4 it gives y k + j ≥ ( 9 / 8 ) 4 z > 1.6018 z > 3 2 z + 1 2 ≥ U 2 ( z ) y_{k+j} \ge(9/8)^4z > 1.6018z > \frac{3}{2}z+\frac{1}{2} \ge U^2(z) y k + j ≥ ( 9/8 ) 4 z > 1.6018 z > 2 3 z + 2 1 ≥ U 2 ( z ) . Similarly, for j ≤ 6 j \le6 j ≤ 6 , y k + j ≤ ( 9 / 8 ) 6 ( z + 9 ) − 9 < 2.0273 z + 9.25 < 9 4 z ≤ U 2 ( z ) y_{k+j} \le(9/8)^6(z+9)-9 < 2.0273z+9.25 < \frac{9}{4}z \le U^2(z) y k + j ≤ ( 9/8 ) 6 ( z + 9 ) − 9 < 2.0273 z + 9.25 < 4 9 z ≤ U 2 ( z ) , and for j ≥ 7 j \ge7 j ≥ 7 , y k + j ≥ ( 9 / 8 ) 7 z > 2.2806 z > 9 4 z + 3 4 ≥ U 3 ( z ) y_{k+j} \ge(9/8)^7z > 2.2806z > \frac{9}{4}z+\frac{3}{4} \ge U^3(z) y k + j ≥ ( 9/8 ) 7 z > 2.2806 z > 4 9 z + 4 3 ≥ U 3 ( z ) . So the path is a ray. Its up-vertices are the y k y_k y k and U ( y k ) U(y_k) U ( y k ) . Since the ray is simple, U 2 ( y k ) U^2(y_k) U 2 ( y k ) is not one of them, and y k y_k y k is not U U U of one of them. So the runs of S S S are the pairs { y k , U ( y k ) } \{y_k,U(y_k)\} { y k , U ( y k )} , and the orbit of y y y under T S T_S T S is the ray.
A computation shows that the path of Theorem 3.3(c) is simple for every y ≥ 37 y \ge37 y ≥ 37 , but repeats a number for y ≤ 36 y \le36 y ≤ 36 unless y ∈ { 29 , 33 , 35 } y \in\{29,33,35\} y ∈ { 29 , 33 , 35 } .
The condition in (b) is easy to check for many sets. For the squares, U ( k 2 ) U(k^2) U ( k 2 ) is either 3 k 2 / 2 3k^2/2 3 k 2 /2 or ( 3 k 2 + 1 ) / 2 (3k^2+1)/2 ( 3 k 2 + 1 ) /2 , and neither is a square, since 3 k 2 = 2 j 2 3k^2=2j^2 3 k 2 = 2 j 2 and 3 k 2 + 1 = 2 j 2 3k^2+1=2j^2 3 k 2 + 1 = 2 j 2 is impossible modulo 3. So T { squares } T_{\{\text{squares}\}} T { squares } has the single cycle ( 1 , 2 ) (1,2) ( 1 , 2 ) , which every orbit reaches. The same holds for 4 N − 3 = { 1 , 5 , 9 , 13 , … } 4\mathbb{N}-3=\{1,5,9,13,\ldots\} 4 N − 3 = { 1 , 5 , 9 , 13 , … } , since U ( 4 k + 1 ) = 6 k + 2 U(4k+1)=6k+2 U ( 4 k + 1 ) = 6 k + 2 is even, and also for { 3 } ∪ ( 4 N − 3 ) \{3\}\cup(4\mathbb{N}-3) { 3 } ∪ ( 4 N − 3 ) , which has the run 3 , 5 3,5 3 , 5 of length 2: the argument of (b) only needs U ( x ) ∉ S U(x)\notin S U ( x ) ∈ / S for the elements x ≥ 4 x\ge4 x ≥ 4 of S S S . The condition does not make S S S sparse:
Lemma 3.4. Let E = { x ∈ N : d ( x ) even } E=\{x\in\mathbb{N}:d(x)\text{ even}\} E = { x ∈ N : d ( x ) even } . Every S ⊆ N S\subseteq\mathbb{N} S ⊆ N with λ ( S ) ≤ 1 \lambda(S)\le1 λ ( S ) ≤ 1 satisfies # ( S ∩ [ 1 , N ] ) ≤ # ( E ∩ [ 1 , N ] ) \#(S\cap[1,N])\le\#(E\cap[1,N]) # ( S ∩ [ 1 , N ]) ≤ # ( E ∩ [ 1 , N ]) for all N N N , and E E E has density 3 / 5 3/5 3/5 . More generally, the numbers of depth d d d have density 1 3 ( 2 3 ) d \frac{1}{3}\left(\frac{2}{3}\right)^d 3 1 ( 3 2 ) d , and the numbers of depth at least d d d have density ( 2 3 ) d \left(\frac{2}{3}\right)^d ( 3 2 ) d .
Proof. On a chain Γ c = { c 0 < c 1 < ⋯ } \Gamma_c=\{c_0<c_1<\cdots\} Γ c = { c 0 < c 1 < ⋯ } , with c i = U i ( c ) c_i=U^i(c) c i = U i ( c ) , a set S S S with λ ( S ) ≤ 1 \lambda(S)\le1 λ ( S ) ≤ 1 contains no two consecutive elements c i , c i + 1 c_i,c_{i+1} c i , c i + 1 . The elements of Γ c \Gamma_c Γ c in [ 1 , N ] [1,N] [ 1 , N ] are c 0 , … , c q − 1 c_0,\ldots,c_{q-1} c 0 , … , c q − 1 for some q q q , of which S S S contains at most ⌈ q / 2 ⌉ \lceil q/2\rceil ⌈ q /2 ⌉ and E E E contains exactly ⌈ q / 2 ⌉ \lceil q/2\rceil ⌈ q /2 ⌉ . Summing over c c c gives the inequality. The numbers of depth d d d form the set U d ( R ) U^d(R) U d ( R ) , where R = { c : c ≡ 1 ( m o d 3 ) } R=\{c:c\equiv1\pmod3\} R = { c : c ≡ 1 ( mod 3 )} . By Theorem 2.1(d), U d ( z ) ≤ N U^d(z)\le N U d ( z ) ≤ N if z + 1 ≤ ( 2 / 3 ) d N z+1\le(2/3)^dN z + 1 ≤ ( 2/3 ) d N , and U d ( z ) > N U^d(z)>N U d ( z ) > N if z > ( 2 / 3 ) d N z>(2/3)^dN z > ( 2/3 ) d N . Since U d U^d U d is increasing, the number of elements of U d ( R ) U^d(R) U d ( R ) in [ 1 , N ] [1,N] [ 1 , N ] is ( 1 / 3 ) ( 2 / 3 ) d N + O ( 1 ) (1/3)(2/3)^dN+O(1) ( 1/3 ) ( 2/3 ) d N + O ( 1 ) , and the number of elements of depth at least d d d is at most ( 2 / 3 ) d N + 1 (2/3)^dN+1 ( 2/3 ) d N + 1 . Hence the densities are as claimed, and E E E has density ∑ d even 1 3 ( 2 3 ) d = 1 3 ⋅ 9 5 = 3 5 \sum_{d\text{ even}}\frac{1}{3}\left(\frac{2}{3}\right)^d=\frac{1}{3}\cdot\frac{9}{5}=\frac{3}{5} ∑ d even 3 1 ( 3 2 ) d = 3 1 ⋅ 5 9 = 5 3 .
In words: E E E takes every second element of every chain, starting with the root, and no set without two steps up in a row can do better. Since d ( 1 ) = 0 d(1)=0 d ( 1 ) = 0 , d ( 2 ) = 1 d(2)=1 d ( 2 ) = 1 and d ( 3 ) = 2 d(3)=2 d ( 3 ) = 2 , we have 1 , 3 ∈ E 1,3\in E 1 , 3 ∈ E and 2 ∉ E 2\notin E 2 ∈ / E , and Theorem 3.3(b) gives the cycles ( 1 , 2 ) (1,2) ( 1 , 2 ) and ( 3 , 5 ) (3,5) ( 3 , 5 ) for T E T_E T E . For comparison, the odd numbers have the smaller density 1 / 2 1/2 1/2 , but their runs are unbounded: U j ( 2 k − 1 ) = 3 j 2 k − j − 1 U^j(2^k-1)=3^j2^{k-j}-1 U j ( 2 k − 1 ) = 3 j 2 k − j − 1 is odd for j < k j<k j < k , so λ 2 N − 1 ( 2 k − 1 ) = k \lambda_{2N-1}(2^k-1)=k λ 2 N − 1 ( 2 k − 1 ) = k . The same holds for the even numbers, with 2 k 2^k 2 k in place of 2 k − 1 2^k-1 2 k − 1 .
Increasing orbits from sparse periodic sets
A chain has density zero and gives an increasing orbit. Remarkably, the set of all numbers of large depth is periodic, so even periodic sets of small density can contain chain tails.
Proposition 3.5. Let j ≥ 1 j\ge1 j ≥ 1 , let D j = U j ( N ) D_j=U^j(\mathbb{N}) D j = U j ( N ) be the set of numbers of depth at least j j j , and let A j = { U j ( r ) m o d 3 j : 1 ≤ r ≤ 2 j } A_j=\{U^j(r)\bmod3^j:1\le r\le2^j\} A j = { U j ( r ) mod 3 j : 1 ≤ r ≤ 2 j } . Then # A j = 2 j \#A_j=2^j # A j = 2 j and
D j = { x ∈ N : x m o d 3 j ∈ A j } , D_j=\{x\in\mathbb{N}:x\bmod3^j\in A_j\}, D j = { x ∈ N : x mod 3 j ∈ A j } ,
so D j D_j D j is periodic modulo 3 j 3^j 3 j and has density ( 2 / 3 ) j (2/3)^j ( 2/3 ) j . Under T D j T_{D_j} T D j , every orbit that meets D j D_j D j increases from then on, and every other orbit decreases to the fixed point 1. For example, D 1 = { x : x ≢ 1 ( m o d 3 ) } D_1=\{x:x\not\equiv1\pmod{3}\} D 1 = { x : x ≡ 1 ( mod 3 )} is the image of U U U . A number in D 1 D_1 D 1 goes up to a number in the image of U U U , that is, again to a number in D 1 D_1 D 1 , so it goes up forever; a number x ≡ 1 ( m o d 3 ) x\equiv1\pmod{3} x ≡ 1 ( mod 3 ) goes down, and continues to go down until it meets D 1 D_1 D 1 or arrives at 1. The next case is D 2 = { x : x ≡ 0 , 3 , 5 , 8 ( m o d 9 ) } D_2=\{x:x\equiv0,3,5,8\pmod{9}\} D 2 = { x : x ≡ 0 , 3 , 5 , 8 ( mod 9 )} , of density 4 / 9 4/9 4/9 . The reason for the periodicity is that adding 2 j 2^j 2 j to x x x adds 3 j 3^j 3 j to U j ( x ) U^j(x) U j ( x ) .
Proof. By Theorem 2.1(f) and induction on i i i , U i ( x + 2 j ) = U i ( x ) + 3 i 2 j − i U^i(x+2^j)=U^i(x)+3^i2^{j-i} U i ( x + 2 j ) = U i ( x ) + 3 i 2 j − i for 0 ≤ i ≤ j 0\le i\le j 0 ≤ i ≤ j , so U j ( x + 2 j ) = U j ( x ) + 3 j U^j(x+2^j)=U^j(x)+3^j U j ( x + 2 j ) = U j ( x ) + 3 j . Since U j U^j U j is strictly increasing, D j D_j D j is the union of the progressions U j ( r ) + 3 j N 0 U^j(r)+3^j\mathbb{N}_0 U j ( r ) + 3 j N 0 , 1 ≤ r ≤ 2 j 1\le r\le2^j 1 ≤ r ≤ 2 j . The numbers U j ( 1 ) < ⋯ < U j ( 2 j ) U^j(1)<\cdots<U^j(2^j) U j ( 1 ) < ⋯ < U j ( 2 j ) lie in [ 1 , 3 j ] [1,3^j] [ 1 , 3 j ] , as U j ( 2 j ) = 3 j U^j(2^j)=3^j U j ( 2 j ) = 3 j , so they are distinct modulo 3 j 3^j 3 j and # A j = 2 j \#A_j=2^j # A j = 2 j . If x ≡ U j ( r ) ( m o d 3 j ) x\equiv U^j(r)\pmod{3^j} x ≡ U j ( r ) ( mod 3 j ) with x ≥ 1 x\ge1 x ≥ 1 , then x ≥ U j ( r ) x\ge U^j(r) x ≥ U j ( r ) , since x < U j ( r ) − 3 j ≤ 0 x<U^j(r)-3^j\le0 x < U j ( r ) − 3 j ≤ 0 otherwise; so x ∈ D j x\in D_j x ∈ D j . This proves the description of D j D_j D j , and its density is 2 j / 3 j 2^j/3^j 2 j / 3 j .
If x ∈ D j x\in D_j x ∈ D j , then U ( x ) ∈ D j + 1 ⊆ D j U(x)\in D_{j+1}\subseteq D_j U ( x ) ∈ D j + 1 ⊆ D j , so an orbit that meets D j D_j D j stays in D j D_j D j and increases. An orbit outside D j D_j D j goes down until it meets D j D_j D j or reaches 1, which has depth 0 and is fixed.
One-way doors
In the other direction, there is a simple mechanism that makes T S T_S T S bounded even when S S S is very large. If the complement W = N ∖ S W=\mathbb{N}\setminus S W = N ∖ S is closed under the step down, then an orbit that enters W W W goes down and stays in W W W forever, so it falls to 1. The only way for an orbit to escape this trap is to avoid W W W altogether, and then it goes up at every step. So W W W works like a one-way door: orbits can pass from S S S into W W W , but not back.
Proposition 3.6. Let W ⊆ N W\subseteq\mathbb{N} W ⊆ N be nonempty with D ( W ) ⊆ W D(W)\subseteq W D ( W ) ⊆ W , and let S = N ∖ W S=\mathbb{N}\setminus W S = N ∖ W .
(a) 1 ∈ W 1\in W 1 ∈ W , and S S S is closed under x ↦ 2 x − 1 x\mapsto2x-1 x ↦ 2 x − 1 and x ↦ 2 x x\mapsto2x x ↦ 2 x . In binary, a nonempty set W W W is closed under D D D if and only if the set { x − 1 : x ∈ W } \{x-1:x\in W\} { x − 1 : x ∈ W } is closed under deleting the last binary digit.
(b) Every orbit of T S T_S T S that meets W W W stays in W W W and reaches the fixed point 1.
(c) T S T_S T S is bounded if and only if S S S contains no tail of a chain, that is, if and only if every chain has infinitely many elements in W W W . In that case every orbit of T S T_S T S reaches 1.
Proof. (a) D s ( x ) = 1 D^s(x)=1 D s ( x ) = 1 for large s s s , by Theorem 2.1(b). The numbers 2 x − 1 2x-1 2 x − 1 and 2 x 2x 2 x are the two preimages of x x x under D D D , so D ( W ) ⊆ W D(W)\subseteq W D ( W ) ⊆ W is equivalent to the closure of S S S under them. Finally D ( x ) − 1 = ⌊ ( x − 1 ) / 2 ⌋ D(x)-1=\lfloor(x-1)/2\rfloor D ( x ) − 1 = ⌊( x − 1 ) /2 ⌋ . (b) On W W W the map T S T_S T S is D D D , which maps W W W into itself, and every orbit of D D D reaches 1. (c) An orbit that never meets W W W lies in S S S , so it goes up at every step: it is a tail of a chain contained in S S S . Conversely, a chain tail in S S S is an increasing orbit. Together with (b) this proves (c).
Example 3.7. For m ≥ 1 m\ge1 m ≥ 1 let
W m = [ 1 , 2 m ] ∪ ⋃ n ≥ m ( 2 n , 2 n + 2 n − m ] , W_m=[1,2^m]\cup\bigcup_{n\ge m}(2^n,2^n+2^{n-m}], W m = [ 1 , 2 m ] ∪ n ≥ m ⋃ ( 2 n , 2 n + 2 n − m ] , that is, x ∈ W m x\in W_m x ∈ W m if and only if x − 1 < 2 m x-1<2^m x − 1 < 2 m or the binary expansion of x − 1 x-1 x − 1 begins with a 1 followed by m m m zeros. Then W m W_m W m is closed under D D D : if 2 n < x ≤ 2 n + 2 n − m 2^n<x\le2^n+2^{n-m} 2 n < x ≤ 2 n + 2 n − m with n > m n>m n > m , then 2 n − 1 < D ( x ) ≤ 2 n − 1 + 2 n − 1 − m 2^{n-1}<D(x)\le2^{n-1}+2^{n-1-m} 2 n − 1 < D ( x ) ≤ 2 n − 1 + 2 n − 1 − m , and D D D maps ( 2 m , 2 m + 1 ] (2^m,2^m+1] ( 2 m , 2 m + 1 ] into [ 1 , 2 m ] [1,2^m] [ 1 , 2 m ] . Every chain meets W m W_m W m infinitely often: x ∈ ( 2 n , 2 n ( 1 + 2 − m ) ] x\in(2^n,2^n(1+2^{-m})] x ∈ ( 2 n , 2 n ( 1 + 2 − m )] means that { log 2 x } \{\log_2x\} { log 2 x } lies in the interval ( 0 , log 2 ( 1 + 2 − m ) ] (0,\log_2(1+2^{-m})] ( 0 , log 2 ( 1 + 2 − m )] , and by Theorem 2.1(d) the numbers log 2 U j ( c ) \log_2 U^j(c) log 2 U j ( c ) differ from log 2 K c + j log 2 3 2 \log_2 K_c+j\log_2\frac{3}{2} log 2 K c + j log 2 2 3 by less than 3 ( 2 / 3 ) j 3(2/3)^j 3 ( 2/3 ) j for j ≥ 2 j\ge2 j ≥ 2 , and the fractional parts of the latter are dense, since log 2 3 2 \log_2\frac{3}{2} log 2 2 3 is irrational. So for S m = N ∖ W m S_m=\mathbb{N}\setminus W_m S m = N ∖ W m the map T S m T_{S_m} T S m is bounded, and every orbit reaches 1. A short count shows that S m S_m S m has lower density ( 2 m − 1 ) / ( 2 m + 1 ) (2^m-1)/(2^m+1) ( 2 m − 1 ) / ( 2 m + 1 ) and upper density 1 − 2 − m 1-2^{-m} 1 − 2 − m ; for instance S 1 = ⋃ n ≥ 1 ( 3 ⋅ 2 n − 1 , 2 n + 1 ] S_1=\bigcup_{n\ge1}(3\cdot2^{n-1},2^{n+1}] S 1 = ⋃ n ≥ 1 ( 3 ⋅ 2 n − 1 , 2 n + 1 ] , the set of x x x for which x − 1 x-1 x − 1 begins with 11 in binary, has lower density 1 / 3 1/3 1/3 and upper density 1 / 2 1/2 1/2 .
In this example the door W m W_m W m occupies the proportion 2 − m 2^{-m} 2 − m of every interval ( 2 n , 2 n + 1 ] (2^n,2^{n+1}] ( 2 n , 2 n + 1 ] , and a chain cannot avoid it, because the numbers U j ( c ) U^j(c) U j ( c ) grow like K c ( 3 / 2 ) j K_c(3/2)^j K c ( 3/2 ) j and their positions within the intervals ( 2 n , 2 n + 1 ] (2^n,2^{n+1}] ( 2 n , 2 n + 1 ] are spread out evenly. Letting the number m m m of zeros grow slowly with n n n makes the door thinner and thinner, and gives a set S S S of density one.
Theorem 3.8. There is a set W ⊆ N W \subseteq\mathbb{N} W ⊆ N of density zero that is closed under D D D and contains infinitely many elements of every chain. Consequently S = N ∖ W S = \mathbb{N} \setminus W S = N ∖ W has density one, T S T_S T S is bounded, and every orbit of T S T_S T S ends at the fixed point 1 1 1 .
Proof. For a non-decreasing function h : N 0 → N 0 h\colon\mathbb{N}_0 \to\mathbb{N}_0 h : N 0 → N 0 with h ( n ) ≤ n h(n) \leq n h ( n ) ≤ n let
W h = { 1 } ∪ ⋃ n ≥ 0 ( 2 n , 2 n + 2 n − h ( n ) ] . W_h = \{1\} \cup\bigcup_{n \geq0} (2^n, 2^n + 2^{n-h(n)}]. W h = { 1 } ∪ n ≥ 0 ⋃ ( 2 n , 2 n + 2 n − h ( n ) ] . W h W_h W h is closed under D D D . We have D ( 1 ) = D ( 2 ) = 1 D(1) = D(2) = 1 D ( 1 ) = D ( 2 ) = 1 . Let n ≥ 1 n \geq1 n ≥ 1 and 2 n < x ≤ 2 n + 2 n − h ( n ) 2^n < x \leq2^n + 2^{n-h(n)} 2 n < x ≤ 2 n + 2 n − h ( n ) . Then D ( x ) > 2 n − 1 D(x) > 2^{n-1} D ( x ) > 2 n − 1 and D ( x ) ≤ 2 n − 1 + ⌈ 2 n − 1 − h ( n ) ⌉ ≤ 2 n − 1 + 2 n − 1 − h ( n − 1 ) D(x) \leq2^{n-1} + \lceil2^{n-1-h(n)}\rceil\leq2^{n-1} + 2^{n-1-h(n-1)} D ( x ) ≤ 2 n − 1 + ⌈ 2 n − 1 − h ( n ) ⌉ ≤ 2 n − 1 + 2 n − 1 − h ( n − 1 ) , since h ( n − 1 ) ≤ h ( n ) h(n-1) \leq h(n) h ( n − 1 ) ≤ h ( n ) and h ( n − 1 ) ≤ n − 1 h(n-1) \leq n-1 h ( n − 1 ) ≤ n − 1 . So D ( x ) ∈ W h D(x) \in W_h D ( x ) ∈ W h .
If h ( n ) → ∞ h(n) \to\infty h ( n ) → ∞ , then W h W_h W h has density zero. The interval ( 2 n , 2 n + 1 ] (2^n,2^{n+1}] ( 2 n , 2 n + 1 ] contains 2 n − h ( n ) 2^{n-h(n)} 2 n − h ( n ) elements of W h W_h W h . For 2 n < N ≤ 2 n + 1 2^n < N \leq2^{n+1} 2 n < N ≤ 2 n + 1 and every L ≤ n L \leq n L ≤ n , splitting the sum at n − L n-L n − L gives
# ( W h ∩ [ 1 , N ] ) ≤ 2 + ∑ i ≤ n − L 2 i + ∑ n − L < i ≤ n 2 i − h ( n − L ) ≤ 2 + 2 n − L + 1 + 2 n + 1 − h ( n − L ) . \#(W_h \cap[1,N]) \leq2 + \sum_{i \leq n-L} 2^i + \sum_{n-L < i \leq n} 2^{i-h(n-L)} \leq2 + 2^{n-L+1} + 2^{n+1-h(n-L)}. # ( W h ∩ [ 1 , N ]) ≤ 2 + i ≤ n − L ∑ 2 i + n − L < i ≤ n ∑ 2 i − h ( n − L ) ≤ 2 + 2 n − L + 1 + 2 n + 1 − h ( n − L ) . so lim sup N # ( W h ∩ [ 1 , N ] ) / N ≤ 2 1 − L \limsup_{N} \#(W_h \cap[1,N])/N \leq2^{1-L} lim sup N # ( W h ∩ [ 1 , N ]) / N ≤ 2 1 − L for every L L L .
Choice of h h h . Let α = log 2 3 2 \alpha= \log_2 \frac{3}{2} α = log 2 2 3 , which is irrational, and let c 1 , c 2 , … c_1,c_2,\ldots c 1 , c 2 , … be a sequence of numbers ≡ 1 ( m o d 3 ) \equiv1 \pmod3 ≡ 1 ( mod 3 ) in which every such number appears infinitely often. We choose 0 = L 0 < L 1 < L 2 < ⋯ 0 = L_0 < L_1 < L_2 < \cdots 0 = L 0 < L 1 < L 2 < ⋯ and elements x i ∈ Γ c i x_i \in\Gamma_{c_i} x i ∈ Γ c i with
2 L i < x i < 2 L i + 2 L i − i , L i > L i − 1 + i , 2^{L_i} < x_i < 2^{L_i} + 2^{L_i-i}, \qquad L_i > L_{i-1} + i, 2 L i < x i < 2 L i + 2 L i − i , L i > L i − 1 + i , as follows. Let ε = log 2 ( 1 + 2 − i ) \varepsilon= \log_2(1 + 2^{-i}) ε = log 2 ( 1 + 2 − i ) and β = log 2 K c i \beta= \log_2 K_{c_i} β = log 2 K c i . By Theorem 2.1(d), log 2 U j ( c i ) = β + j α + η j \log_2 U^j(c_i) = \beta+ j\alpha+ \eta_j log 2 U j ( c i ) = β + j α + η j with log 2 ( 1 − ( 2 / 3 ) j ) < η j < 0 \log_2(1 - (2/3)^j) < \eta_j < 0 log 2 ( 1 − ( 2/3 ) j ) < η j < 0 . By Kronecker’s theorem the fractional part of β + j α \beta+ j\alpha β + j α lies in ( ε / 3 , 2 ε / 3 ) (\varepsilon/3,2\varepsilon/3) ( ε /3 , 2 ε /3 ) for infinitely many j j j ; choose such a j j j with ∣ η j ∣ < ε / 3 |\eta_j| < \varepsilon/3 ∣ η j ∣ < ε /3 and U j ( c i ) > 2 L i − 1 + i + 1 U^j(c_i) > 2^{L_{i-1}+i+1} U j ( c i ) > 2 L i − 1 + i + 1 , and put x i = U j ( c i ) x_i = U^j(c_i) x i = U j ( c i ) and L i = ⌊ log 2 x i ⌋ L_i = \lfloor\log_2 x_i \rfloor L i = ⌊ log 2 x i ⌋ . Then { log 2 x i } ∈ ( 0 , ε ) \{\log_2 x_i\} \in(0,\varepsilon) { log 2 x i } ∈ ( 0 , ε ) , which is the displayed condition. Now let h ( 0 ) = 0 h(0) = 0 h ( 0 ) = 0 and h ( n ) = i h(n) = i h ( n ) = i for L i − 1 < n ≤ L i L_{i-1} < n \leq L_i L i − 1 < n ≤ L i . This function is non-decreasing, tends to infinity, and satisfies h ( n ) ≤ n h(n) \leq n h ( n ) ≤ n because L i − 1 ≥ i − 1 L_{i-1} \geq i-1 L i − 1 ≥ i − 1 . Since h ( L i ) = i h(L_i) = i h ( L i ) = i , every x i x_i x i lies in W h W_h W h . Every chain is Γ c i \Gamma_{c_i} Γ c i for infinitely many i i i , and the x i x_i x i are distinct, so every chain has infinitely many elements in W = W h W = W_h W = W h . The rest follows from Theorem 3.6.
The function h h h in the proof grows very slowly, and it could be made explicit with an effective irrationality measure for log 2 3 \log_2 3 log 2 3 ; we do not need this.
Density is not the measure
The examples of this section show that the density of S S S does not determine, even roughly, whether T S T_S T S is bounded:
density zero is compatible with divergence: a single chain gives an increasing orbit, and so do the periodic sets D j D_j D j of density ( 2 / 3 ) j (2/3)^j ( 2/3 ) j (Theorem 3.5);
density one is compatible with convergence of every orbit to 1 1 1 (Theorem 3.8 ), and upper density one even with trivial boundedness;
in between, the set E E E of density 3 / 5 3/5 3/5 gives a bounded map with two small cycles (Theorem 3.4), while the odd and the even numbers, of density 1 / 2 1/2 1/2 , give the Collatz map.
What matters is how often an orbit actually visits S S S , and an orbit visits S S S in a very biased way: chains are the only routes upward, and a set can be dense but avoid them often enough, or sparse but contain one. We take this up in § 7 . Table 3.1 collects the classes found so far; they are not exclusive.
Typical sets
Two natural notions of a typical set give opposite answers. The second is that of a random set. The first is topological, and we recall the terms. A set S ⊆ N S \subseteq\mathbb{N} S ⊆ N is the same thing as a point of the product { 0 , 1 } N \{0,1\}^{\mathbb{N}} { 0 , 1 } N , and we use the product topology on the collection of all sets: a family U \mathcal{U} U of sets is open if for every S ∈ U S \in\mathcal{U} S ∈ U there is an n n n such that U \mathcal{U} U contains every set S ′ S' S ′ with S ′ ∩ [ 1 , n ] = S ∩ [ 1 , n ] S' \cap[1,n] = S \cap[1,n] S ′ ∩ [ 1 , n ] = S ∩ [ 1 , n ] . In other words, membership in an open family is always witnessed by finitely many elements and non-elements of the set. A family is dense if it meets every nonempty open family, that is, if every prescription of finitely many elements and non-elements is satisfied by one of its members. A G δ G_\delta G δ is an intersection of countably many open families. By the Baire category theorem, an intersection of countably many dense open families is dense; these intersections are the dense G δ G_\delta G δ families. A family is comeager if it contains a dense G δ G_\delta G δ . Comeager families are dense, in particular nonempty, and an intersection of countably many comeager families is comeager; see [20 ] . So the comeager families play the role of “almost all sets” in the topological sense, as the families of probability one do for random sets, and a property is called generic if the sets that have it form a comeager family.
Proposition 3.9 (Typical sets).
(a) In the product topology on the collection of all sets S ⊆ N S \subseteq\mathbb{N} S ⊆ N , the trivially bounded sets form a dense G δ G_\delta G δ , and so do the sets S S S for which T S T_S T S has infinitely many cycles. So for a comeager family of sets S S S the map T S T_S T S is trivially bounded and has infinitely many cycles.
(b) If every x x x belongs to S S S independently with probability p ∈ ( 0 , 1 ) p \in(0,1) p ∈ ( 0 , 1 ) , then almost surely S S S is not trivially bounded, all its runs are finite, and λ ( S ) = ∞ \lambda(S)=\infty λ ( S ) = ∞ . If p < log 3 2 p < \log_3 2 p < log 3 2 , then T S T_S T S is almost surely bounded.
In (b) the logarithm of an orbit behaves, until the orbit returns to a number it has visited, like a random walk with steps log ( 3 / 2 ) \log(3/2) log ( 3/2 ) and − log 2 -\log2 − log 2 , which has negative drift for p < log 3 2 p < \log_3 2 p < log 3 2 . We expect that T S T_S T S almost surely has divergent orbits if p > log 3 2 p > \log_3 2 p > log 3 2 (Theorem 7.8). The proof of (a) uses Theorem 4.1 (b) from the next section.
Proof. (a) The set { S : S ∩ ( 2 B / 3 , B ] = ∅ } \{S:S\cap(2B/3,B]=\varnothing\} { S : S ∩ ( 2 B /3 , B ] = ∅ } is closed and open, and for every n n n the union of these sets over B ≥ n B\ge n B ≥ n is open and dense: a condition on finitely many elements can be met by a set that has no element in ( 2 B / 3 , B ] (2B/3,B] ( 2 B /3 , B ] for some large B B B . So the trivially bounded sets form a dense G δ G_\delta G δ . The set of S S S for which T S T_S T S has at least k k k cycles is open, since a cycle depends only on S S S at its elements, and dense, since by Theorem 4.1 (b) we can add k k k cycles whose least elements exceed the largest prescribed number and the largest element of the previously added cycle. Intersecting over k k k gives the second dense G δ G_\delta G δ .
(b) A given B B B is a barrier with probability ( 1 − p ) # ( 2 B / 3 , B ] ≤ ( 1 − p ) B / 3 (1-p)^{\#(2B/3,B]} \le(1-p)^{B/3} ( 1 − p ) # ( 2 B /3 , B ] ≤ ( 1 − p ) B /3 , which is summable, so by the Borel–Cantelli lemma S S S has only finitely many barriers. A given chain tail lies in S S S with probability 0, and there are countably many; and for every λ \lambda λ , disjoint segments of length λ \lambda λ of chains lie in S S S independently with probability p λ p^\lambda p λ , so infinitely many of them do. For the last claim fix x 0 x_0 x 0 , and let ξ 1 , ξ 2 , … \xi_1,\xi_2,\ldots ξ 1 , ξ 2 , … be independent with P ( ξ t = 1 ) = p = 1 − P ( ξ t = 0 ) P(\xi_t=1)=p=1-P(\xi_t=0) P ( ξ t = 1 ) = p = 1 − P ( ξ t = 0 ) . We may assume that the membership of the t t t -th new number visited by the orbit of x 0 x_0 x 0 is decided by ξ t \xi_t ξ t , so that until the first repetition the orbit makes a step up at time t t t if and only if ξ t = 1 \xi_t=1 ξ t = 1 . Suppose that the orbit never repeats a number. Then x t → ∞ x_t\to\infty x t → ∞ , and since U ( z ) ≤ 3 2 z ( 1 + 1 3 z ) U(z)\le\frac{3}{2}z(1+\frac{1}{3z}) U ( z ) ≤ 2 3 z ( 1 + 3 z 1 ) and D ( z ) ≤ 1 2 ( 1 + 1 z ) D(z)\le\frac{1}{2}(1+\frac{1}{z}) D ( z ) ≤ 2 1 ( 1 + z 1 ) ,
log x t ≤ log x 0 + ∑ i = 1 t ( ξ i log 3 2 − ( 1 − ξ i ) log 2 ) + ∑ i < t log ( 1 + 1 x i ) . \log x_t \le\log x_0+\sum_{i=1}^{t}\left(\xi_i\log\frac{3}{2}-(1-\xi_i)\log2\right)+\sum_{i<t}\log\left(1+\frac{1}{x_i}\right). log x t ≤ log x 0 + i = 1 ∑ t ( ξ i log 2 3 − ( 1 − ξ i ) log 2 ) + i < t ∑ log ( 1 + x i 1 ) .
The last sum is o ( t ) o(t) o ( t ) , and by the strong law of large numbers the first sum is t ( p log 3 − log 2 ) + o ( t ) t(p\log3-\log2)+o(t) t ( p log 3 − log 2 ) + o ( t ) almost surely, which tends to − ∞ -\infty − ∞ for p < log 3 2 p<\log_3 2 p < log 3 2 . This contradicts x t → ∞ x_t\to\infty x t → ∞ . So almost surely the orbit of x 0 x_0 x 0 repeats a number, for every x 0 x_0 x 0 .
Cycles across all maps
By Theorem 2.3, the cycles of all maps T S T_S T S together are the simple cycles of G G G , and a set of simple cycles of G G G occurs in a single map if and only if its members are pairwise disjoint. So the question whether there are infinitely many cycles across all maps is the question whether G G G has infinitely many simple cycles.
Theorem 4.1.
(a) G G G is strongly connected. More precisely, for all x ≥ 1 x\ge1 x ≥ 1 and y ≥ 2 y\ge2 y ≥ 2 there are r , s ≥ 1 r,s\ge1 r , s ≥ 1 with D s ( U r ( x ) ) = y D^{s}(U^{r}(x))=y D s ( U r ( x )) = y .
(b) Every n ∈ N n\in\mathbb{N} n ∈ N is the least element of a cycle of some map T S T_S T S , and for n ≥ 2 n\ge2 n ≥ 2 the cycle can be chosen with a single run of steps up. In particular, there are infinitely many cycles across all maps.
(c) Let a cycle have length ℓ \ell ℓ , a a a steps up and least element m m m . Then 1 < 2 ℓ / 3 a ≤ ( 1 + 1 / m ) ℓ 1<2^{\ell}/3^{a}\le(1+1/m)^\ell 1 < 2 ℓ / 3 a ≤ ( 1 + 1/ m ) ℓ . Hence there are only finitely many cycles of each length.
(d) If p 1 , … , p k ≥ 2 p_1,\ldots,p_k \ge2 p 1 , … , p k ≥ 2 are the numbers at which the runs of steps up of a cycle other than (1) start, then
3 a 2 ℓ > ∏ j = 1 k p j − 1 p j + 1 . \frac{3^a}{2^\ell} > \prod_{j=1}^{k}\frac{p_j-1}{p_j+1}. 2 ℓ 3 a > j = 1 ∏ k p j + 1 p j − 1 .
In particular, every cycle with a single run of steps up has 3 a < 2 ℓ < 3 a + 1 3^a < 2^\ell< 3^{a+1} 3 a < 2 ℓ < 3 a + 1 , that is, a = ⌊ ℓ log 3 2 ⌋ a = \lfloor\ell\log_3 2\rfloor a = ⌊ ℓ log 3 2 ⌋ .
The idea behind (a) and (b) is that a run of steps up multiplies by almost exactly ( 3 / 2 ) r (3/2)^r ( 3/2 ) r and a run of steps down divides by almost exactly 2 s 2^s 2 s , and since log 3 / log 2 \log3/\log2 log 3/ log 2 is irrational, ( 3 / 2 ) r / 2 s (3/2)^r/2^s ( 3/2 ) r / 2 s can be made as close to any given ratio as we like. Going up from n n n and coming back down to n n n closes a cycle. For example, from n = 4 n=4 n = 4 the steps up give 4 , 6 , 9 , 14 , 21 , … 4,6,9,14,21,\ldots 4 , 6 , 9 , 14 , 21 , … , and we look for an element of this chain that the steps down bring back to 4 4 4 , that is, an element u u u with ⌈ u / 2 s ⌉ = 4 \lceil u/2^s\rceil=4 ⌈ u / 2 s ⌉ = 4 for some s s s . The number 6 6 6 fails (6 → 3 6\to3 6 → 3 ), and so does 9 9 9 (9 → 5 → 3 9\to5\to3 9 → 5 → 3 ), but 14 → 7 → 4 14\to7\to4 14 → 7 → 4 works. This gives the cycle ( 4 , 6 , 9 , 14 , 7 ) (4,6,9,14,7) ( 4 , 6 , 9 , 14 , 7 ) of length ℓ = 5 \ell=5 ℓ = 5 with a = 3 a=3 a = 3 steps up, which is a cycle of T S T_S T S exactly for the sets S S S that contain 4 , 6 , 9 4,6,9 4 , 6 , 9 and do not contain 7 , 14 7,14 7 , 14 .
Part (c) is the identity that every cycle of every map must satisfy, the analogue of the well-known product formula for Collatz cycles: the steps multiply by 3 / 2 3/2 3/2 and 1 / 2 1/2 1/2 exactly at even numbers and by slightly more at odd numbers, and around a cycle the total factor is 1 1 1 . For the cycle ( 4 , 6 , 9 , 14 , 7 ) (4,6,9,14,7) ( 4 , 6 , 9 , 14 , 7 ) the odd elements are 9 9 9 , which goes up, and 7 7 7 , which goes down, and indeed 2 5 / 3 3 = 32 / 27 = ( 1 + 1 / 27 ) ( 1 + 1 / 7 ) 2^5/3^3 = 32/27 = (1+1/27)(1+1/7) 2 5 / 3 3 = 32/27 = ( 1 + 1/27 ) ( 1 + 1/7 ) . Part (d) is a relation of Steiner’s type [22 ] that holds for all maps at once.
Lemma 4.2. For all x ≥ 1 x\ge1 x ≥ 1 and y ≥ 2 y\ge2 y ≥ 2 there are infinitely many pairs r , s ≥ 1 r,s\ge1 r , s ≥ 1 with D s ( U r ( x ) ) = y D^s(U^r(x))=y D s ( U r ( x )) = y .
Proof. By Theorem 2.1(b), D s ( U r ( x ) ) = y D^s(U^r(x))=y D s ( U r ( x )) = y if and only if y − 1 < U r ( x ) / 2 s ≤ y y-1<U^r(x)/2^s\le y y − 1 < U r ( x ) / 2 s ≤ y . Let J = ( log 2 ( y − 1 2 ) , log 2 y ) J=(\log_2(y-\frac{1}{2}),\log_2 y) J = ( log 2 ( y − 2 1 ) , log 2 y ) and λ r = log 2 K x + r log 2 3 2 \lambda_r=\log_2 K_x+r\log_2\frac{3}{2} λ r = log 2 K x + r log 2 2 3 , with K x K_x K x as in Theorem 2.1(d). If λ r − s ∈ J \lambda_r-s\in J λ r − s ∈ J and s ≥ 1 s\ge1 s ≥ 1 , then K x ( 3 / 2 ) r / 2 s ∈ ( y − 1 2 , y ) K_x(3/2)^r/2^s\in(y-\frac{1}{2},y) K x ( 3/2 ) r / 2 s ∈ ( y − 2 1 , y ) , so U r ( x ) / 2 s ∈ ( y − 1 2 − 2 − s , y ) ⊆ ( y − 1 , y ) U^r(x)/2^s\in(y-\frac{1}{2}-2^{-s},y)\subseteq(y-1,y) U r ( x ) / 2 s ∈ ( y − 2 1 − 2 − s , y ) ⊆ ( y − 1 , y ) . The interval J J J has length less than 1 1 1 and contains no integer, since no power of 2 2 2 lies in ( y − 1 2 , y ) (y-\frac{1}{2},y) ( y − 2 1 , y ) ; so J ⊆ ( j , j + 1 ) J\subseteq(j,j+1) J ⊆ ( j , j + 1 ) for j = ⌊ log 2 ( y − 1 2 ) ⌋ j=\lfloor\log_2(y-\frac{1}{2})\rfloor j = ⌊ log 2 ( y − 2 1 )⌋ . Since log 2 3 2 \log_2\frac{3}{2} log 2 2 3 is irrational, the fractional part of λ r \lambda_r λ r lies in J − j J-j J − j for infinitely many r r r , by Kronecker’s theorem, and for each of them s = ⌊ λ r ⌋ − j s=\lfloor\lambda_r\rfloor-j s = ⌊ λ r ⌋ − j satisfies λ r − s ∈ J \lambda_r-s\in J λ r − s ∈ J , and s ≥ 1 s\ge1 s ≥ 1 when r r r is large.
Proof of Theorem 4.1. (a) Every x x x reaches 1 1 1 by steps down, since D s ( x ) = ⌈ x / 2 s ⌉ D^s(x)=\lceil x/2^s\rceil D s ( x ) = ⌈ x / 2 s ⌉ , and 1 1 1 reaches every y ≥ 2 y\ge2 y ≥ 2 by Theorem 4.2 .
(b) For n = 1 n=1 n = 1 take the fixed point (1). Let n ≥ 2 n\ge2 n ≥ 2 and choose r , s ≥ 1 r,s\ge1 r , s ≥ 1 with D s ( U r ( n ) ) = n D^s(U^r(n))=n D s ( U r ( n )) = n . Put u i = U i ( n ) u_i=U^i(n) u i = U i ( n ) for 0 ≤ i ≤ r 0\le i\le r 0 ≤ i ≤ r and v j = D j ( u r ) v_j=D^j(u_r) v j = D j ( u r ) for 0 ≤ j ≤ s 0\le j\le s 0 ≤ j ≤ s . Then n = u 0 < u 1 < ⋯ < u r = v 0 > v 1 > ⋯ > v s = n n=u_0<u_1<\cdots<u_r=v_0>v_1>\cdots>v_s=n n = u 0 < u 1 < ⋯ < u r = v 0 > v 1 > ⋯ > v s = n , and v j > n v_j>n v j > n for j < s j<s j < s , since D ( v s − 1 ) = n D(v_{s-1})=n D ( v s − 1 ) = n gives v s − 1 ≥ 2 n − 1 > n v_{s-1}\ge2n-1>n v s − 1 ≥ 2 n − 1 > n . So the walk goes up from n n n to u r u_r u r and comes down to n n n again; the only way in which it can fail to be a simple cycle is that on the way down it meets a number that it visited on the way up, and then we take a shortcut. If no v j v_j v j with 1 ≤ j < s 1\le j<s 1 ≤ j < s is one of u 1 , … , u r u_1,\ldots,u_r u 1 , … , u r , the closed walk u 0 , … , u r , v 1 , … , v s − 1 u_0,\ldots,u_r,v_1,\ldots,v_{s-1} u 0 , … , u r , v 1 , … , v s − 1 is a simple cycle. Otherwise let j ∗ < s j^*<s j ∗ < s be the largest j j j for which it is, say v j ∗ = u i ∗ v_{j^*}=u_{i^*} v j ∗ = u i ∗ with i ∗ ≥ 1 i^*\ge1 i ∗ ≥ 1 ; then u 0 , … , u i ∗ , v j ∗ + 1 , … , v s − 1 u_0,\ldots,u_{i^*},v_{j^*+1},\ldots,v_{s-1} u 0 , … , u i ∗ , v j ∗ + 1 , … , v s − 1 is a simple cycle. In both cases the cycle has least element n n n and a single run of steps up, and by Theorem 2.3(a) it is a cycle of a map T S T_S T S . Since every cycle is finite and every n n n lies on one, there are infinitely many cycles.
(c) Let x 0 , … , x ℓ − 1 x_0,\ldots,x_{\ell-1} x 0 , … , x ℓ − 1 be the cycle, with indices modulo ℓ \ell ℓ . By Theorem 2.1(a), x i + 1 = ( c i x i + e i ) / 2 x_{i+1}=(c_i x_i+e_i)/2 x i + 1 = ( c i x i + e i ) /2 with c i ∈ { 1 , 3 } c_i\in\{1,3\} c i ∈ { 1 , 3 } and e i = x i m o d 2 e_i=x_i\bmod2 e i = x i mod 2 . Multiplying the ratios x i + 1 / x i x_{i+1}/x_i x i + 1 / x i around the cycle gives
2 ℓ 3 a = ∏ i = 0 ℓ − 1 ( 1 + e i c i x i ) . (3) \frac{2^\ell}{3^a}=\prod_{i=0}^{\ell-1}\left(1+\frac{e_i}{c_i x_i}\right). \tag*{(3)} 3 a 2 ℓ = i = 0 ∏ ℓ − 1 ( 1 + c i x i e i ) . (3)
Not all x i x_i x i are even, since both steps divide an even number by 2 exactly once, so that otherwise the exponent of 2 in x i x_i x i would decrease by 1 at every step around the cycle. So the product is larger than 1, and every factor is at most 1 + 1 / m 1+1/m 1 + 1/ m . For fixed ℓ \ell ℓ there are finitely many a < ℓ log 3 2 a<\ell\log_3 2 a < ℓ log 3 2 , so 2 ℓ / 3 a 2^\ell/3^a 2 ℓ / 3 a stays above some constant larger than 1; then the inequality 2 ℓ / 3 a ≤ ( 1 + 1 / m ) ℓ 2^\ell/3^a\leq(1+1/m)^\ell 2 ℓ / 3 a ≤ ( 1 + 1/ m ) ℓ bounds m m m , and a cycle is determined by m m m and its ℓ \ell ℓ steps.
(d) Write the cycle as runs of steps up p j → q j = U r j ( p j ) p_j\to q_j=U^{r_j}(p_j) p j → q j = U r j ( p j ) and runs of steps down q j → p j + 1 = D s j ( q j ) q_j\to p_{j+1}=D^{s_j}(q_j) q j → p j + 1 = D s j ( q j ) , j = 1 , … , k j=1,\ldots,k j = 1 , … , k , with p k + 1 = p 1 p_{k+1}=p_1 p k + 1 = p 1 , ∑ r j = a \sum r_j=a ∑ r j = a and ∑ ( r j + s j ) = ℓ \sum(r_j+s_j)=\ell ∑ ( r j + s j ) = ℓ . By Theorem 2.1(d), q j + 1 ≤ ( 3 / 2 ) r j ( p j + 1 ) q_j+1\leq(3/2)^{r_j}(p_j+1) q j + 1 ≤ ( 3/2 ) r j ( p j + 1 ) , and by Theorem 2.1(b), p j + 1 < q j / 2 s j + 1 p_{j+1}<q_j/2^{s_j}+1 p j + 1 < q j / 2 s j + 1 . Hence p j + 1 − 1 < ( 3 / 2 ) r j ( p j + 1 ) / 2 s j p_{j+1}-1<(3/2)^{r_j}(p_j+1)/2^{s_j} p j + 1 − 1 < ( 3/2 ) r j ( p j + 1 ) / 2 s j , and multiplying over j j j gives ∏ j ( p j − 1 ) < ( 3 a / 2 ℓ ) ∏ j ( p j + 1 ) \prod_j(p_j-1)<(3^a/2^\ell)\prod_j(p_j+1) ∏ j ( p j − 1 ) < ( 3 a / 2 ℓ ) ∏ j ( p j + 1 ) . If k = 1 k=1 k = 1 and p 1 ≥ 2 p_1\geq2 p 1 ≥ 2 , this gives 3 a / 2 ℓ > ( p 1 − 1 ) / ( p 1 + 1 ) ≥ 1 / 3 3^a/2^\ell>(p_1-1)/(p_1+1)\geq1/3 3 a / 2 ℓ > ( p 1 − 1 ) / ( p 1 + 1 ) ≥ 1/3 . If k = 1 k=1 k = 1 and p 1 = 1 p_1=1 p 1 = 1 , the cycle is ( 1 , 2 ) (1,2) ( 1 , 2 ) , since the only edges into 1 come from 1 and 2; and 4 < 9 4<9 4 < 9 . Together with (c), 3 a < 2 ℓ < 3 a + 1 3^a<2^\ell<3^{a+1} 3 a < 2 ℓ < 3 a + 1 .
Part (b) contrasts with Steiner’s theorem that the only Collatz cycle with a single run of odd steps is ( 1 , 2 ) (1,2) ( 1 , 2 ) [22 ] , extended by Simons and de Weger to cycles with up to 75 runs [21 ] . The cycles of (b) are long, since ( 3 / 2 ) r / 2 s (3/2)^r/2^s ( 3/2 ) r / 2 s has to be within about 1 / n 1/n 1/ n of 1; for n = 32 n=32 n = 32 the construction gives a cycle of length 46 with largest element 4,102,266. Cycles with several runs are much shorter: for 88% of the numbers n n n between 9 ⋅ 10 4 9\cdot10^4 9 ⋅ 1 0 4 and 10 5 10^5 1 0 5 there is a cycle through n n n of length at most 65 inside [ 1 , 3 n ] [1,3n] [ 1 , 3 n ] .
Since a single map can have any set of disjoint cycles, the cycles of single maps carry no further restriction:
Proposition 4.3 (Prescribed cycles). Let C C C be a nonempty set, finite or infinite, of pairwise vertex-disjoint simple cycles of G G G . Then there is a set S S S such that the cycles of T S T_S T S are exactly the members of C C C and every orbit of T S T_S T S ends in one of them.
Proof. The idea is to let every number outside the given cycles go down. Then every orbit decreases until it meets one of the cycles or arrives at 1, and we only have to take care of 1. Let V V V be the union of the vertex sets of the members of C C C , and V ↑ V^\uparrow V ↑ the set of vertices at which they go up. If 1 ∈ V 1\in V 1 ∈ V , let S = V ↑ S=V^\uparrow S = V ↑ . Otherwise, let P P P be a shortest path from 2 to V V V , which exists by Theorem 4.1 (a). It does not pass through 1, since from 1 one can only go to 1 or 2, and only its last vertex lies in V V V . Let S S S consist of V ↑ V^\uparrow V ↑ , the number 1, and the vertices at which P P P goes up. Then T S T_S T S follows the cycles of C C C on V V V , sends 1 to 2 and then along P P P into V V V , and sends every other number x x x down to D ( x ) < x D(x)<x D ( x ) < x . So every orbit decreases until it meets V V V , P P P or 1, and then ends in a member of C C C .
So for every k ∈ { 1 , 2 , … , ∞ } k\in\{1,2,\ldots,\infty\} k ∈ { 1 , 2 , … , ∞ } there are bounded maps with exactly k k k cycles, and T N T_{\mathbb{N}} T N has none. The classification of single maps by their cycles is therefore the classification of sets of pairwise disjoint simple cycles of G G G , and what remains is the structure of G G G and of natural classes of sets. Table 4.1 lists the cycles of G G G of length at most 30.
The three cycles of length 2 are ( 1 , 2 ) (1,2) ( 1 , 2 ) , ( 2 , 3 ) (2,3) ( 2 , 3 ) and ( 3 , 5 ) (3,5) ( 3 , 5 ) , which appeared in Theorem 3.3(b). The table suggests that cycles exist for the lengths ℓ \ell ℓ for which 2 ℓ / 3 ⌊ ℓ log 3 2 ⌋ 2^\ell/3^{\lfloor\ell\log_3 2\rfloor} 2 ℓ / 3 ⌊ ℓ l o g 3 2 ⌋ is small, but not in a monotone way (Theorem 7.2).
Remark 4.4 (Cycles and divergent orbits together). Call two divergent orbits of T S T_S T S equivalent if they eventually coincide, and let k k k and l l l be the numbers of cycles and of classes of divergent orbits of T S T_S T S ; always k + l ≥ 1 k+l\geq1 k + l ≥ 1 , since the orbit of 1 is periodic or diverges. Every pair ( k , l ) (k,l) ( k , l ) with k < ∞ k<\infty k < ∞ and k + l ≥ 1 k+l\geq1 k + l ≥ 1 occurs: take k k k disjoint cycles below some K K K , one of them ( 1 ) (1) ( 1 ) , and l l l chains with roots above K K K (or Γ 1 \Gamma_1 Γ 1 together with l − 1 l-1 l − 1 such chains if k = 0 k=0 k = 0 ), and let all other numbers go down. In this construction the chains, the cycles and the number 1 are disjoint, every number that lies on none of them goes down, and so its orbit decreases until it meets one of them; distinct chains are disjoint and are never left, so they give distinct classes of divergent orbits. Theorem 4.3 gives k = ∞ k = \infty k = ∞ , l = 0 l = 0 l = 0 . We do not know whether a map can have infinitely many cycles and a divergent orbit (Theorem 7.3).
Near the threshold
Which sets are, intuitively, the most expanding sets whose maps can still be proved to be bounded, and which are the least expanding sets whose maps can be proved to be unbounded? Since the density of S S S is not a measure of expansion (§ 5 ), we first need a better yardstick. The natural one is how often an orbit actually goes up. In this section we show that the critical proportion of steps up is log 3 2 \log_3 2 log 3 2 , sharp from both sides, and that for sets that are periodic modulo a power of 2 the proportion of steps up of a typical orbit can be computed from a finite Markov chain. This leads to a simple test, uniform descent, that proves boundedness for many periodic sets, and it places Mahler’s Z Z Z -number problem inside our family.
The critical proportion of steps up
Along an orbit, a step up multiplies by 3 / 2 3/2 3/2 and a step down by 1 / 2 1/2 1/2 , up to a relative error of order 1 / x 1/x 1/ x . So after t t t steps, of which a a a go up, an orbit has been multiplied by about 3 a / 2 t 3^a/2^t 3 a / 2 t , and it grows or shrinks according to whether a / t a/t a / t is above or below log 3 2 = 0.6309 … \log_3 2 = 0.6309\ldots log 3 2 = 0.6309 … .
Proposition 5.1. Let x 0 , x 1 , … x_0, x_1, \ldots x 0 , x 1 , … be an orbit of a map T S T_S T S , and let a ( t ) a(t) a ( t ) be the number of steps up among its first t t t steps.
(a)
x 0 3 a ( t ) 2 t ≤ x t ≤ x 0 ( 3 a ( t ) 2 t ) ∏ i < t ( 1 + 1 x i ) . x_0 \frac{3^{a(t)}}{2^t} \le x_t \le x_0 \left(\frac{3^{a(t)}}{2^t}\right) \prod_{i<t}\left(1+\frac{1}{x_i}\right). x 0 2 t 3 a ( t ) ≤ x t ≤ x 0 ( 2 t 3 a ( t ) ) i < t ∏ ( 1 + x i 1 ) . (b) If the orbit diverges, then lim inf t → ∞ a ( t ) / t ≥ log 3 2 \liminf_{t\to\infty} a(t)/t \ge\log_3 2 lim inf t → ∞ a ( t ) / t ≥ log 3 2 .
(c) If lim inf t → ∞ a ( t ) / t > log 3 2 \liminf_{t\to\infty} a(t)/t > \log_3 2 lim inf t → ∞ a ( t ) / t > log 3 2 , then the orbit diverges.
(d) Every cycle has a proportion a / ℓ < log 3 2 a/\ell< \log_{3} 2 a / ℓ < log 3 2 of steps up, and there are cycles with proportions arbitrarily close to log 3 2 \log_{3} 2 log 3 2 .
Proof. (a) For every z z z , 3 2 z ≤ U ( z ) ≤ 3 2 z ( 1 + 1 z ) \frac{3}{2}z \le U(z) \le\frac{3}{2}z\left(1+\frac{1}{z}\right) 2 3 z ≤ U ( z ) ≤ 2 3 z ( 1 + z 1 ) and 1 2 z ≤ D ( z ) ≤ 1 2 z ( 1 + 1 z ) \frac{1}{2}z \le D(z) \le\frac{1}{2}z\left(1+\frac{1}{z}\right) 2 1 z ≤ D ( z ) ≤ 2 1 z ( 1 + z 1 ) ; multiply over the first t t t steps. (b) If the orbit diverges, then x i → ∞ x_i \to\infty x i → ∞ , so ∑ i < t log ( 1 + 1 x i ) = o ( t ) \sum_{i<t}\log\left(1+\frac{1}{x_i}\right)=o(t) ∑ i < t log ( 1 + x i 1 ) = o ( t ) , and by (a) log x t ≤ log x 0 + a ( t ) log 3 − t log 2 + o ( t ) \log x_t \le\log x_0+a(t)\log3-t\log2+o(t) log x t ≤ log x 0 + a ( t ) log 3 − t log 2 + o ( t ) . If a ( t ) ≤ ( log 3 2 − ε ) t a(t)\le(\log_{3}2-\varepsilon)t a ( t ) ≤ ( log 3 2 − ε ) t for infinitely many t t t , then log x t → − ∞ \log x_t\to-\infty log x t → − ∞ along these t t t , which is impossible. (c) By (a), x t ≥ x 0 exp ( t ( a ( t ) t log 3 − log 2 ) ) → ∞ x_t\ge x_0\exp\left(t\left(\frac{a(t)}{t}\log3-\log2\right)\right)\to\infty x t ≥ x 0 exp ( t ( t a ( t ) log 3 − log 2 ) ) → ∞ . (d) The first claim is Theorem 4.1 (c). By Theorem 4.1 (b), for every n ≥ 2 n\ge2 n ≥ 2 there is a cycle with least element n n n and one run of steps up, and by Theorem 4.1 (d) it has a = ⌊ ℓ log 3 2 ⌋ a=\lfloor\ell\log_{3}2\rfloor a = ⌊ ℓ log 3 2 ⌋ . Since there are only finitely many cycles of each length, ℓ → ∞ \ell\to\infty ℓ → ∞ as n → ∞ n\to\infty n → ∞ , and ⌊ ℓ log 3 2 ⌋ / ℓ → log 3 2 \lfloor\ell\log_{3}2\rfloor/\ell\to\log_{3}2 ⌊ ℓ log 3 2 ⌋ / ℓ → log 3 2 .
So no set S S S can produce a divergent orbit that goes up less often than a proportion log 3 2 \log_{3}2 log 3 2 of the time, in the long run. The next theorem shows that this bound is sharp: there are divergent orbits that go up only very slightly more often. For the Collatz map, (b) is the familiar observation that a divergent orbit would have to consist of odd numbers at least a proportion log 3 2 \log_{3}2 log 3 2 of the time.
Theorem 5.2 (Barely divergent orbits). Let r , s ≥ 1 r,s\ge1 r , s ≥ 1 with 3 r > 2 r + s 3^r>2^{r+s} 3 r > 2 r + s , that is, r / ( r + s ) > log 3 2 r/(r+s)>\log_{3}2 r / ( r + s ) > log 3 2 . There is y 0 y_0 y 0 such that for every y ≥ y 0 y\ge y_0 y ≥ y 0 the path from y y y in G G G that repeats r r r steps up followed by s s s steps down is a ray. If S S S is the set of its up-vertices, then the orbit of y y y under T S T_S T S is this ray: it diverges, and its proportion of steps up is r / ( r + s ) r/(r+s) r / ( r + s ) . In particular, there are divergent orbits whose proportion of steps up is arbitrarily close to log 3 2 \log_{3}2 log 3 2 .
Theorem 3.3(c) is the case r = 2 r=2 r = 2 , s = 1 s=1 s = 1 . The best choices of ( r , s ) (r,s) ( r , s ) come from the continued fraction of log 3 2 = [ 0 ; 1 , 1 , 1 , 2 , 2 , 3 , 1 , 5 , 2 , 23 , … ] \log_{3}2=[0;1,1,1,2,2,3,1,5,2,23,\ldots] log 3 2 = [ 0 ; 1 , 1 , 1 , 2 , 2 , 3 , 1 , 5 , 2 , 23 , … ] , whose convergents above log 3 2 \log_{3}2 log 3 2 are 2 / 3 2/3 2/3 , 12 / 19 12/19 12/19 , 53 / 84 53/84 53/84 , 665 / 1054 , … 665/1054,\ldots 665/1054 , … ; see Table 5.1 .
Table 5.1. Barely divergent rays (Theorem 5.2 ): the pattern U r D s U^rD^s U r D s repeated forever. The growth per block is ρ = 3 r / 2 r + s \rho=3^r/2^{r+s} ρ = 3 r / 2 r + s , and y 0 y_0 y 0 is the threshold given by the proof.
The path of the theorem grows by the factor ρ = 3 r / 2 r + s > 1 \rho=3^r/2^{r+s}>1 ρ = 3 r / 2 r + s > 1 in every block of r + s r+s r + s steps, so it tends to infinity. We have to prove that it never visits a number twice, because only then is it the orbit of a single map (Theorem 2.3). The idea is this: Any two numbers on the path differ by a factor 3 X / 2 Y 3^X/2^Y 3 X / 2 Y , up to a relative error of order 1 / y 1/y 1/ y that comes from the rounding at odd numbers. A power of 3 is never a power of 2, so 3 X / 2 Y ≠ 1 3^X/2^Y\ne1 3 X / 2 Y = 1 ; and only finitely many exponents X , Y X,Y X , Y have to be considered, because after many blocks the path has grown too much to return. So all these factors stay away from 1 by a fixed amount, and for large y y y the rounding errors are too small to make two numbers of the path equal.
Proof. Let L = r + s L=r+s L = r + s , ρ = 3 r / 2 L > 1 \rho=3^r/2^L>1 ρ = 3 r / 2 L > 1 , and let z 0 = y , z 1 , z 2 , … z_0=y,z_1,z_2,\ldots z 0 = y , z 1 , z 2 , … be the path, so that the t t t -th step goes up if and only if t m o d L < r t\bmod L<r t mod L < r . Let a ( t ) a(t) a ( t ) be the number of steps up among the first t t t steps. Since the steps up come first in every block, 3 a ( p ) / 2 p ≥ 1 3^{a(p)}/2^p\ge1 3 a ( p ) / 2 p ≥ 1 for 0 ≤ p ≤ L 0\le p\le L 0 ≤ p ≤ L , and so 3 a ( t ) / 2 t ≥ ρ ⌊ t / L ⌋ 3^{a(t)}/2^t\ge\rho^{\lfloor t/L\rfloor} 3 a ( t ) / 2 t ≥ ρ ⌊ t / L ⌋ for all t t t . By the bounds in the proof of Theorem 5.1(a), z t ≥ y ρ ⌊ t / L ⌋ z_t \ge y\rho^{\lfloor t/L\rfloor} z t ≥ y ρ ⌊ t / L ⌋ , and therefore
z t = y 3 a ( t ) 2 t ( 1 + ϑ t ) , 0 ≤ ϑ t ≤ exp ( ∑ i ≥ 0 1 z i ) − 1 ≤ e C 1 / y − 1 , C 1 = L ρ ρ − 1 . z_t = y\frac{3^{a(t)}}{2^t}(1+\vartheta_t), \qquad0 \le\vartheta_t \le\exp\left(\sum_{i\ge0}\frac{1}{z_i}\right)-1 \le e^{C_1/y}-1, \qquad C_1=\frac{L\rho}{\rho-1}. z t = y 2 t 3 a ( t ) ( 1 + ϑ t ) , 0 ≤ ϑ t ≤ exp ( i ≥ 0 ∑ z i 1 ) − 1 ≤ e C 1 / y − 1 , C 1 = ρ − 1 L ρ .
Suppose that z t = z t ′ z_t=z_{t'} z t = z t ′ with t < t ′ t<t' t < t ′ , and write t ′ − t = q L + e t'-t=qL+e t ′ − t = q L + e with 0 ≤ e < L 0\le e<L 0 ≤ e < L . Then a ( t ′ ) − a ( t ) = q r + A a(t')-a(t)=qr+A a ( t ′ ) − a ( t ) = q r + A , where 0 ≤ A ≤ e 0\le A\le e 0 ≤ A ≤ e is the number of steps up among e e e consecutive positions of the periodic pattern, and
Q : = 3 a ( t ′ ) − a ( t ) 2 t ′ − t = ρ q 3 A 2 e = 1 + ϑ t 1 + ϑ t ′ ∈ [ e − C 1 / y , e C 1 / y ] . Q:=\frac{3^{a(t')-a(t)}}{2^{t'-t}}=\rho^q\frac{3^A}{2^e}=\frac{1+\vartheta_t}{1+\vartheta_{t'}}\in\left[e^{-C_1/y},e^{C_1/y}\right]. Q := 2 t ′ − t 3 a ( t ′ ) − a ( t ) = ρ q 2 e 3 A = 1 + ϑ t ′ 1 + ϑ t ∈ [ e − C 1 / y , e C 1 / y ] .
Since 3 A / 2 e ≥ 2 − L 3^A/2^e\ge2^{-L} 3 A / 2 e ≥ 2 − L , we have Q > 2 Q>2 Q > 2 as soon as q > q 0 = ( L + 1 ) / log 2 ρ q>q_0=(L+1)/\log_2\rho q > q 0 = ( L + 1 ) / log 2 ρ . For q ≤ q 0 q\le q_0 q ≤ q 0 there are only finitely many possible values of Q Q Q , all of the form 3 X / 2 Y 3^X/2^Y 3 X / 2 Y with Y = q L + e ≥ 1 Y=qL+e\ge1 Y = q L + e ≥ 1 , so all different from 1 1 1 . Let c > 0 c>0 c > 0 be the smallest of the numbers ∣ log Q ∣ |\log Q| ∣ log Q ∣ over these finitely many values. Then for y > y 0 = C 1 / c y>y_0=C_1/c y > y 0 = C 1 / c (and y ≥ C 1 / log 2 y\ge C_1/\log2 y ≥ C 1 / log 2 , so that e C 1 / y ≤ 2 e^{C_1/y}\le2 e C 1 / y ≤ 2 ) no repetition is possible, and the path is a ray. Its up-vertices are visited once each, so by Theorem 2.3(b) the orbit of y y y under T S T_S T S follows the ray.
Periodic sets and fresh binary digits
For a general set S S S the sequence of steps of an orbit can be anything. For a set that is periodic modulo a power of 2 2 2 , it is governed by a finite graph.
Definition 5.3. Let k ≥ 1 k\ge1 k ≥ 1 , M = 2 k M=2^k M = 2 k , and let S S S be periodic modulo M M M ; we also regard S S S as a set of residues modulo M M M . For a residue r r r let r ^ ∈ [ 1 , M ] \hat r\in[1,M] r ^ ∈ [ 1 , M ] be its representative, and let g ( r ) = U ( r ^ ) m o d M g(r)=U(\hat r)\bmod M g ( r ) = U ( r ^ ) mod M if r ∈ S r\in S r ∈ S and g ( r ) = D ( r ^ ) m o d M g(r)=D(\hat r)\bmod M g ( r ) = D ( r ^ ) mod M otherwise. The residue graph R k ( S ) R_k(S) R k ( S ) is the directed graph on Z / M \mathbb{Z}/M Z / M with the two edges r → g ( r ) r\to g(r) r → g ( r ) and r → g ( r ) + M / 2 r\to g(r)+M/2 r → g ( r ) + M /2 at every r r r . We give the vertex r r r the factor f ( r ) = 3 / 2 f(r)=3/2 f ( r ) = 3/2 if r ∈ S r\in S r ∈ S and f ( r ) = 1 / 2 f(r)=1/2 f ( r ) = 1/2 otherwise. The residue chain is the random walk on R k ( S ) R_k(S) R k ( S ) that takes each of the two edges with probability 1 / 2 1/2 1/2 .
The two edges at r r r are always different, since M / 2 ≢ 0 ( m o d M ) M/2\not\equiv0\pmod M M /2 ≡ 0 ( mod M ) . They lead to the two possible residues of T S ( x ) T_S(x) T S ( x ) for the numbers x ≡ r ( m o d M ) x\equiv r\pmod M x ≡ r ( mod M ) . Indeed, by Theorem 2.1(f), adding M M M to x x x adds 3 M / 2 3M/2 3 M /2 to a step up and M / 2 M/2 M /2 to a step down, and both are congruent to M / 2 M/2 M /2 modulo M M M ; so the images of r ^ , r ^ + M , r ^ + 2 M , … \hat r,\hat r+M,\hat r+2M,\ldots r ^ , r ^ + M , r ^ + 2 M , … have the residues g ( r ) g(r) g ( r ) and g ( r ) + M / 2 g(r)+M/2 g ( r ) + M /2 alternately (Theorem 5.5(a)). In binary terms, a step ends with a division by 2 2 2 , so the last k k k binary digits of x x x determine only the last k − 1 k-1 k − 1 digits of T S ( x ) T_S(x) T S ( x ) .
Example 5.4. For the Collatz set S = 2 N − 1 S=2\mathbb{N}-1 S = 2 N − 1 and k = 2 k=2 k = 2 , the residue graph on { 0 , 1 , 2 , 3 } \{0,1,2,3\} { 0 , 1 , 2 , 3 } has the edges
0 → 0 , 2 ; 1 → 0 , 2 ; 2 → 1 , 3 ; 3 → 1 , 3 , 0\to0,2;\qquad1\to0,2;\qquad2\to1,3;\qquad3\to1,3, 0 → 0 , 2 ; 1 → 0 , 2 ; 2 → 1 , 3 ; 3 → 1 , 3 ,
with steps up at 1 1 1 and 3 3 3 ; for instance U ( 3 ) = 5 ≡ 1 U(3)=5\equiv1 U ( 3 ) = 5 ≡ 1 , so 3 → 1 3\to1 3 → 1 and 3 → 1 + 2 = 3 3\to1+2=3 3 → 1 + 2 = 3 . The loop 3 → 3 3\to3 3 → 3 has one step up in one step, and 3 > 2 3>2 3 > 2 ; it reflects the fact that the numbers x ≡ − 1 ( m o d 2 j ) x\equiv-1\pmod{2^j} x ≡ − 1 ( mod 2 j ) go up j j j times in a row. The cycle 1 → 2 → 1 1\to2\to1 1 → 2 → 1 is the residue pattern of the cycle ( 1 , 2 ) (1,2) ( 1 , 2 ) , with 3 < 4 3<4 3 < 4 , and the cycle 2 → 3 → 1 → 2 2\to3\to1\to2 2 → 3 → 1 → 2 has 9 > 8 9>8 9 > 8 . Every vertex has two incoming edges, so the uniform distribution is stationary and π = 1 / 2 \pi=1/2 π = 1/2 . For S = 4 N − 3 S=4\mathbb{N}-3 S = 4 N − 3 , the only change is that 3 3 3 goes down, D ( 3 ) = 2 D(3)=2 D ( 3 ) = 2 , so 3 → 0 , 2 3\to0,2 3 → 0 , 2 ; now every cycle has at most half of its vertices in S S S , and the stationary distribution ( 1 / 3 , 1 / 6 , 1 / 3 , 1 / 6 ) (1/3,1/6,1/3,1/6) ( 1/3 , 1/6 , 1/3 , 1/6 ) gives π = 1 / 6 \pi=1/6 π = 1/6 .
The next lemma says that the residues of an orbit move along this graph, and that the choice between the two edges is made by a new binary digit of the starting number at every step.
Lemma 5.5 (Fresh binary digits). Let S S S be periodic modulo M = 2 k M = 2^k M = 2 k .
(a) If x ≡ r ( m o d M ) x \equiv r \pmod{M} x ≡ r ( mod M ) , then T S ( x ) m o d M T_S(x) \bmod M T S ( x ) mod M is one of the two successors of r r r in R k ( S ) \mathcal{R}_k(S) R k ( S ) , and T S ( x ) = f ( r ) x + O ( 1 ) T_S(x) = f(r)x + O(1) T S ( x ) = f ( r ) x + O ( 1 ) ; precisely, x = r ^ + M u x = \hat{r} + Mu x = r ^ + M u gives T S ( x ) = T S ( r ^ ) + 2 f ( r ) ⋅ M 2 u ≡ g ( r ) + M 2 u ( m o d M ) T_S(x) = T_S(\hat{r}) + 2f(r) \cdot\frac{M}{2}u \equiv g(r) + \frac{M}{2}u \pmod{M} T S ( x ) = T S ( r ^ ) + 2 f ( r ) ⋅ 2 M u ≡ g ( r ) + 2 M u ( mod M ) .
(b) Let t ≥ 0 t \ge0 t ≥ 0 and r 0 ∈ Z / M r_0 \in\mathbb{Z}/M r 0 ∈ Z / M . The sequence of residues ( T S i ( x ) m o d M ) 0 ≤ i ≤ t (T_S^i(x) \bmod M)_{0 \le i \le t} ( T S i ( x ) mod M ) 0 ≤ i ≤ t depends only on x m o d 2 k + t x \bmod2^{k+t} x mod 2 k + t , and as x x x runs through the 2 t 2^t 2 t classes modulo 2 k + t 2^{k+t} 2 k + t that are ≡ r 0 ( m o d M ) \equiv r_0 \pmod M ≡ r 0 ( mod M ) , this sequence runs through all 2 t 2^t 2 t paths of length t t t in R k ( S ) \mathcal{R}_k(S) R k ( S ) that start at r 0 r_0 r 0 , each exactly once.
(c) Consequently, for every path P P P of length t t t in R k ( S ) \mathcal{R}_k(S) R k ( S ) the set of x ∈ N x \in\mathbb{N} x ∈ N whose residue sequence begins with P P P is a single residue class modulo 2 k + t 2^{k+t} 2 k + t , of density 2 − k − t 2^{-k-t} 2 − k − t . In other words, the residues of the orbit of a number x x x chosen uniformly at random from [ 1 , 2 k + t ] [1,2^{k+t}] [ 1 , 2 k + t ] form the first t t t steps of the residue chain started from the uniform distribution.
For the Collatz map (S = 2 N − 1 S = 2\mathbb{N}-1 S = 2 N − 1 , k = 1 k = 1 k = 1 ) this is Terras’s observation that the sequence of parities of the first t t t terms of an orbit is a bijective function of x x x modulo 2 t 2^t 2 t [23 , 9 ] .
Here is what the lemma says in the graph of Theorem 5.4. A number x ≡ 3 ( m o d 4 ) x \equiv3 \pmod4 x ≡ 3 ( mod 4 ) goes up to ( 3 x + 1 ) / 2 (3x + 1)/2 ( 3 x + 1 ) /2 , and its residue moves along one of the edges 3 → 1 3 \to1 3 → 1 and 3 → 3 3 \to3 3 → 3 . Which one is decided by the next binary digit of x x x : the numbers x ≡ 3 ( m o d 8 ) x \equiv3 \pmod8 x ≡ 3 ( mod 8 ) , such as 3 → 5 3 \to5 3 → 5 and 11 → 17 11 \to17 11 → 17 , arrive at the residue 1 1 1 , and the numbers x ≡ 7 ( m o d 8 ) x \equiv7 \pmod8 x ≡ 7 ( mod 8 ) , such as 7 → 11 7 \to11 7 → 11 and 15 → 23 15 \to23 15 → 23 , arrive at the residue 3 3 3 . So each edge is used by exactly half of the numbers, and the digit that decides was not used before. At the next step the fourth binary digit of x x x decides, and so on. For a number taken at random, the residues therefore perform a random walk on the residue graph, with a fair coin tossed at every step, for as many steps as the number has binary digits. This is why the properties of the map T S T_S T S for typical numbers can be read off a finite Markov chain.
Proof. (a) If r ∈ S r \in S r ∈ S , then U ( r ^ + M u ) = U ( r ^ ) + 3 2 M u U(\hat{r} + Mu) = U(\hat{r}) + \frac{3}{2}Mu U ( r ^ + M u ) = U ( r ^ ) + 2 3 M u by Theorem 2.1(f), and if r ∉ S r \notin S r ∈ / S , then D ( r ^ + M u ) = D ( r ^ ) + 1 2 M u D(\hat{r} + Mu) = D(\hat{r}) + \frac{1}{2}Mu D ( r ^ + M u ) = D ( r ^ ) + 2 1 M u ; and 3 2 M u ≡ 1 2 M u ≡ M 2 u ( m o d M ) \frac{3}{2}Mu \equiv\frac{1}{2}Mu \equiv\frac{M}{2}u \pmod M 2 3 M u ≡ 2 1 M u ≡ 2 M u ( mod M ) .
(b) If x ≡ x ′ ( m o d 2 j ) x \equiv x' \pmod{2^j} x ≡ x ′ ( mod 2 j ) with j ≥ k + 1 j \ge k + 1 j ≥ k + 1 , then x x x and x ′ x' x ′ have the same residue r r r modulo M M M and the same parity, so the same step is applied to both, and T S ( x ) − T S ( x ′ ) = f ( r ) ( x − x ′ ) ≡ 0 ( m o d 2 j − 1 ) T_S(x) - T_S(x') = f(r)(x - x') \equiv0 \pmod{2^{j-1}} T S ( x ) − T S ( x ′ ) = f ( r ) ( x − x ′ ) ≡ 0 ( mod 2 j − 1 ) . By induction, T S i ( x ) ≡ T S i ( x ′ ) ( m o d 2 k + t − i ) T_S^i(x) \equiv T_S^i(x') \pmod{2^{k+t-i}} T S i ( x ) ≡ T S i ( x ′ ) ( mod 2 k + t − i ) , and in particular modulo M M M , for i ≤ t i \le t i ≤ t if x ≡ x ′ ( m o d 2 k + t ) x \equiv x' \pmod{2^{k+t}} x ≡ x ′ ( mod 2 k + t ) . So the residue sequence depends only on x x x modulo 2 k + t 2^{k+t} 2 k + t . Now let x ≡ x ′ ≡ r 0 ( m o d M ) x \equiv x' \equiv r_0 \pmod M x ≡ x ′ ≡ r 0 ( mod M ) with x ≢ x ′ ( m o d 2 k + t ) x \not\equiv x' \pmod{2^{k+t}} x ≡ x ′ ( mod 2 k + t ) , and let k + i k+i k + i , with 0 ≤ i < t 0 \le i < t 0 ≤ i < t , be the exact power of 2 2 2 that divides x − x ′ x-x' x − x ′ . As before, the residue sequences agree up to index i i i , the first i i i steps are the same, and T S i ( x ) − T S i ( x ′ ) = 3 b ( x − x ′ ) / 2 i T_S^i(x)-T_S^i(x') = 3^b(x-x')/2^i T S i ( x ) − T S i ( x ′ ) = 3 b ( x − x ′ ) / 2 i for some b b b ; this difference is divisible by M M M but not by 2 M 2M 2 M . The same step is applied once more, so T S i + 1 ( x ) − T S i + 1 ( x ′ ) T_S^{i+1}(x)-T_S^{i+1}(x') T S i + 1 ( x ) − T S i + 1 ( x ′ ) is divisible by M / 2 M/2 M /2 but not by M M M , and the residues at index i + 1 i+1 i + 1 differ. So distinct classes give distinct sequences. By (a) every sequence is a path in R k ( S ) \mathcal{R}_k(S) R k ( S ) , and there are exactly 2 t 2^t 2 t paths of length t t t from r 0 r_0 r 0 , so the correspondence is a bijection.
(c) follows from (b).
:::
The lemma has a consequence that explains why residues alone can prove convergence, as we shall see, but never divergence.
Lemma 5.6. Let S S S be periodic modulo 2 k 2^k 2 k . If the orbit of x x x under T S T_S T S diverges, then the sequence of its residues modulo 2 k 2^k 2 k is not eventually periodic.
Proof. Suppose that the residues of x t = T S t ( x ) x_t = T_S^t(x) x t = T S t ( x ) are periodic with period ℓ \ell ℓ from t 0 t_0 t 0 on, and let y = x t 0 y = x_{t_0} y = x t 0 and y ′ = x t 0 + ℓ = T S ℓ ( y ) y' = x_{t_0+\ell} = T_S^\ell(y) y ′ = x t 0 + ℓ = T S ℓ ( y ) . Then y y y and y ′ y' y ′ have the same residue sequence, so by Theorem 5.5(b) they are congruent modulo 2 k + t 2^{k+t} 2 k + t for every t t t , and y = y ′ y = y' y = y ′ . So the orbit is eventually periodic.
Remark 5.7 (Cycles of the residue graph as 2-adic cycles). The formulas x ↦ ( 3 x + e ) / 2 x \mapsto(3x+e)/2 x ↦ ( 3 x + e ) /2 and x ↦ ( x + e ) / 2 x \mapsto(x+e)/2 x ↦ ( x + e ) /2 , with e = x m o d 2 e=x\bmod2 e = x mod 2 , also make sense for 2-adic integers x x x , and Theorem 5.5 holds for the resulting extension of T S T_S T S to Z 2 \mathbb{Z}_2 Z 2 . Hence an infinite path in R k ( S ) \mathcal{R}_k(S) R k ( S ) is the residue sequence of exactly one 2-adic integer. If the path goes around a cycle of length ℓ \ell ℓ with a a a vertices in S S S forever, this 2-adic integer x x x satisfies T S ℓ ( x ) = x T_S^\ell(x)=x T S ℓ ( x ) = x . On the numbers that follow the cycle for ℓ \ell ℓ steps, T S ℓ T_S^\ell T S ℓ is the affine map y ↦ ( 3 a y + d ) / 2 ℓ y \mapsto(3^a y+d)/2^\ell y ↦ ( 3 a y + d ) / 2 ℓ for a nonnegative integer d d d , so x = d / ( 2 ℓ − 3 a ) x=d/(2^\ell-3^a) x = d / ( 2 ℓ − 3 a ) is a rational number. In particular, the cycles with 3 a > 2 ℓ 3^a>2^\ell 3 a > 2 ℓ are the residues of periodic orbits of the extended map that consist of rational numbers x ≤ 0 x\leq0 x ≤ 0 , and x < 0 x<0 x < 0 unless all vertices of the cycle are even residues. We use this in Section 6.
The effective up-frequency
Definition 5.8. Let S S S be periodic modulo 2 k 2^k 2 k . A closed class of R k ( S ) \mathcal{R}_k(S) R k ( S ) is a strongly connected set of vertices that no edge leaves. On a closed class C C C the residue chain is irreducible and has a unique stationary distribution μ C \mu_C μ C . The effective up-frequency of S S S on C C C is
π C ( S ) = ∑ r ∈ C ∩ S μ C ( r ) . \pi_C(S)=\sum_{r\in C\cap S}\mu_C(r). π C ( S ) = r ∈ C ∩ S ∑ μ C ( r ) .
If R k ( S ) \mathcal{R}_k(S) R k ( S ) has a single closed class we write π ( S ) \pi(S) π ( S ) .
In words: a closed class is a set of residues that the residue chain cannot leave once it has entered it, and inside which it can get from every residue to every other one. The residues outside all closed classes are visited only finitely often by the chain. The number π C ( S ) \pi_C(S) π C ( S ) is the proportion of time that the chain spends at residues where the map goes up, once it has settled in C C C .
By the ergodic theorem for finite Markov chains, the residue chain enters some closed class C C C after finitely many steps almost surely, and then the proportion of its steps taken at vertices in S S S converges to π C ( S ) \pi_C(S) π C ( S ) . By Theorem 5.5(c), π C ( S ) \pi_C(S) π C ( S ) is therefore the proportion of steps up of the orbit of a typical number whose residues end up in C C C , over any fixed number of steps that is large compared with the time needed to enter C C C . The numbers π C ( S ) \pi_C(S) π C ( S ) are rational, so they are never equal to log 3 2 \log_3 2 log 3 2 .
For the two copies of the Collatz map the uniform distribution is stationary, since every residue has exactly two incoming edges, and π ( 2 N − 1 ) = π ( 2 N ) = 1 / 2 \pi(2\mathbb{N}-1)=\pi(2\mathbb{N})=1/2 π ( 2 N − 1 ) = π ( 2 N ) = 1/2 , the density. In general π \pi π and the density are unrelated, and they can lie on opposite sides of log 3 2 \log_3 2 log 3 2 ; see Table 5.2 . The reason is the same as for arbitrary sets: what matters is not how many residues lie in S S S , but how often the orbits visit them.
The two middle examples of Table 5.2 are the extreme cases modulo 16: among all sets that are periodic modulo 16, they maximize π − \pi- π − density subject to density < log 3 2 < π <\log_3 2<\pi < log 3 2 < π , and density − π -\pi − π subject to π < log 3 2 < \pi<\log_3 2< π < log 3 2 < density. The effective up-frequency decides, as in the theorem of Terras and Everett for the Collatz map [23 , 6 ] , whether a typical orbit eventually falls below its starting value:
Theorem 5.9. Let S S S be periodic modulo 2 k 2^k 2 k .
(a) If π C ( S ) < log 3 2 \pi_C(S)<\log_3 2 π C ( S ) < log 3 2 for every closed class C C C of R k ( S ) \mathcal{R}_k(S) R k ( S ) , then the set of x x x with T S t ( x ) < x T_S^t(x)<x T S t ( x ) < x for some t ≥ 1 t\geq1 t ≥ 1 has density 1.
(b) If π C ( S ) > log 3 2 \pi_C(S)>\log_3 2 π C ( S ) > log 3 2 for some closed class C C C , then there are c > 0 c>0 c > 0 and λ > 1 \lambda>1 λ > 1 such that for every large t t t the set of x x x with T S t ( x ) ≥ λ t x T_S^t(x)\geq\lambda^t x T S t ( x ) ≥ λ t x has lower density at least c c c .
Proof. Let a t a_t a t be the number of steps up among the first t t t steps of the residue chain started from the uniform distribution, that is, the number of the first t t t vertices of its path that lie in S S S . By the ergodic theorem, a t / t a_t/t a t / t converges almost surely to π C ( S ) \pi_C(S) π C ( S ) , where C C C is the closed class that the chain enters.
(a) Choose ε > 0 \varepsilon> 0 ε > 0 with π C ( S ) < log 3 2 − 2 ε \pi_C(S) < \log_3 2 - 2\varepsilon π C ( S ) < log 3 2 − 2 ε for all C C C . Then P ( a t ≥ ( log 3 2 − ε ) t ) → 0 P(a_t \ge(\log_3 2-\varepsilon)t) \to0 P ( a t ≥ ( log 3 2 − ε ) t ) → 0 . Let t t t be so large that e 3 − ε t < 1 e\,3^{-\varepsilon t} < 1 e 3 − εt < 1 , and let x ≥ t x \ge t x ≥ t be a number whose residue sequence of length t t t has fewer than ( log 3 2 − ε ) t (\log_3 2-\varepsilon)t ( log 3 2 − ε ) t vertices in S S S . If T S i ( x ) ≥ x T_S^i(x) \ge x T S i ( x ) ≥ x for all i < t i < t i < t , then by Theorem 5.1(a)
T S t ( x ) ≤ x 3 a 2 t ( 1 + 1 x ) t < x ⋅ 3 − ε t ⋅ e < x . T_S^t(x) \le x\frac{3^a}{2^t}\left(1+\frac{1}{x}\right)^t < x\cdot3^{-\varepsilon t}\cdot e < x. T S t ( x ) ≤ x 2 t 3 a ( 1 + x 1 ) t < x ⋅ 3 − εt ⋅ e < x .
So every such x x x falls below itself within t t t steps. By Theorem 5.5(c), the set of the other numbers x ≥ t x \ge t x ≥ t has upper density at most P ( a t ≥ ( log 3 2 − ε ) t ) P(a_t \ge(\log_3 2-\varepsilon)t) P ( a t ≥ ( log 3 2 − ε ) t ) , which tends to 0 as t → ∞ t \to\infty t → ∞ .
(b) Choose ε > 0 \varepsilon> 0 ε > 0 with π C ( S ) > log 3 2 + 2 ε \pi_C(S) > \log_3 2+2\varepsilon π C ( S ) > log 3 2 + 2 ε . Started from the uniform distribution on C C C , the chain stays in C C C , so P ( a t ≥ ( log 3 2 + ε ) t ∣ r 0 ∈ C ) → 1 P(a_t \ge(\log_3 2+\varepsilon)t \mid r_0 \in C) \to1 P ( a t ≥ ( log 3 2 + ε ) t ∣ r 0 ∈ C ) → 1 . For every x x x whose residue sequence of length t t t has at least ( log 3 2 + ε ) t (\log_3 2+\varepsilon)t ( log 3 2 + ε ) t vertices in S S S , Theorem 5.1(a) gives T S t ( x ) ≥ x 3 a / 2 t ≥ 3 ε t x T_S^t(x) \ge x\,3^{a/2^t} \ge3^{\varepsilon t}x T S t ( x ) ≥ x 3 a / 2 t ≥ 3 εt x . By Theorem 5.5(c), these x x x form a union of residue classes of density at least # C 2 k P ( a t ≥ ( log 3 2 + ε ) t ∣ r 0 ∈ C ) \frac{\#C}{2^k}P(a_t \ge(\log_3 2+\varepsilon)t \mid r_0 \in C) 2 k # C P ( a t ≥ ( log 3 2 + ε ) t ∣ r 0 ∈ C ) , which is at least c = # C / 2 k + 1 c=\#C/2^{k+1} c = # C / 2 k + 1 for large t t t . Take λ = 3 ε \lambda=3^\varepsilon λ = 3 ε .
Part (b) does not prove that T S T_S T S is unbounded: an orbit may grow for a long time and still come down. For the “sparse but expanding” set of Table 5.2 , of density 7/16, the residue graph has a single closed class, and the proof of (b) shows that for every ε > 0 \varepsilon> 0 ε > 0 and every large t t t all numbers x x x outside a set of upper density ε \varepsilon ε satisfy T S t ( x ) ≥ 1.18 t x T_S^t(x) \ge1.18^t x T S t ( x ) ≥ 1.1 8 t x , since 3 11 / 14 / 2 > 1.18 3^{11/14}/2 > 1.18 3 11/14 /2 > 1.18 ; but we cannot prove that a single orbit diverges. By Theorem 5.6, any divergent orbit would have to visit the residues in an aperiodic way.
Uniform descent
Theorem 5.9 (a) only says that almost every number falls below itself. A much stronger property can follow from the residue graph directly: that every long path in it descends.
Definition 5.10. A set S S S that is periodic modulo 2 k 2^k 2 k is uniformly descending if every cycle of R k ( S ) R_k(S) R k ( S ) of length ℓ \ell ℓ with a a a vertices in S S S satisfies 3 a < 2 ℓ 3^a < 2^\ell 3 a < 2 ℓ .
Equivalently, the cycles of R k ( S ) R_k(S) R k ( S ) all have a proportion a / ℓ < log 3 2 a/\ell< \log_3 2 a / ℓ < log 3 2 of vertices in S S S . Since a closed walk is made of simple cycles, it suffices to check the simple cycles, and this can be done in time polynomial in 2 k 2^k 2 k by computing the maximum mean weight of a cycle with weights log f ( r ) \log f(r) log f ( r ) (Karp’s algorithm). The definition does not depend on k k k : a set that is periodic modulo 2 k 2^k 2 k is also periodic modulo 2 k + 1 2^{k+1} 2 k + 1 , reduction modulo 2 k 2^k 2 k maps the cycles of R k + 1 ( S ) R_{k+1}(S) R k + 1 ( S ) to closed walks of R k ( S ) R_k(S) R k ( S ) with the same steps, and conversely every cycle of R k ( S ) R_k(S) R k ( S ) is the reduction of the closed walk of R k + 1 ( S ) R_{k+1}(S) R k + 1 ( S ) formed by the residues of the corresponding 2-adic periodic orbit (Theorem 5.7). A uniformly descending set has π C ( S ) < log 3 2 \pi_C(S)<\log_3 2 π C ( S ) < log 3 2 for all closed classes C C C : the stationary chain uses the edges of C C C with frequencies that form a circulation, a circulation is a positive combination of simple cycles, and on each of these the proportion of vertices in S S S is less than log 3 2 \log_3 2 log 3 2 . The converse is false. The effective up-frequency is an average over typical paths, while uniform descent is a condition on the worst path: the Collatz set has π = 1 / 2 < log 3 2 \pi=1/2<\log_3 2 π = 1/2 < log 3 2 , but it is not uniformly descending, because of the loop at the residue − 1 -1 − 1 (Theorem 5.4). The set 4 N − 3 4\mathbb{N}-3 4 N − 3 of the same example is uniformly descending, since at most half of the vertices of any of its cycles lie in S S S .
Theorem 5.11. Let S S S be periodic modulo M = 2 k M=2^k M = 2 k . The following are equivalent.
(i) S S S is uniformly descending.
(ii) There are weights c : Z / M → N c:\mathbb{Z}/M\to\mathbb{N} c : Z / M → N and a number θ < 1 \theta<1 θ < 1 such that f ( r ) c ( s ) ≤ θ c ( r ) f(r)c(s)\leq\theta c(r) f ( r ) c ( s ) ≤ θ c ( r ) for every edge r → s r\to s r → s of R k ( S ) R_k(S) R k ( S ) .
(iii) There is t ≥ 1 t\geq1 t ≥ 1 such that 3 a < 2 t 3^a<2^t 3 a < 2 t for every path of length t t t in R k ( S ) R_k(S) R k ( S ) with a a a vertices in S S S (not counting its last vertex).
(iv) There is t ≥ 1 t\geq1 t ≥ 1 such that T S t ( x ) < x T_S^t(x)<x T S t ( x ) < x for all sufficiently large x x x .
Corollary 5.12 (Certificates). Let c c c and θ \theta θ be as in (ii), let x 1 x_1 x 1 be the least integer with θ ( 1 + 1 / x 1 ) < 1 \theta(1+1/x_1)<1 θ ( 1 + 1/ x 1 ) < 1 , and let B = ⌊ c max U ( x 1 ) / c min ⌋ + 1 B=\lfloor c_{\max}U(x_1)/c_{\min}\rfloor+1 B = ⌊ c m a x U ( x 1 ) / c m i n ⌋ + 1 , where c max c_{\max} c m a x and c min c_{\min} c m i n are the largest and the smallest weight. Then every orbit of T S T_S T S is eventually smaller than B B B . In particular T S T_S T S is bounded, all its cycles lie in [ 1 , B ] [1,B] [ 1 , B ] , and if the orbits of all x < B x<B x < B end in a given set of cycles, then so do all orbits.
Thus a uniformly descending set comes with a proof that can be checked by hand: a table of 2 k 2^k 2 k weights, the inequalities on the 2 k + 1 2^{k+1} 2 k + 1 edges, and a finite computation below B B B . The weights play the role of a Lyapunov function Φ ( x ) = c ( x m o d M ) x \Phi(x)=c(x\bmod M)x Φ ( x ) = c ( x mod M ) x that decreases at every step. The size x x x itself does not decrease at every step, of course. But a residue from which steps up are still to come gets a larger weight, so that the weighted size Φ \Phi Φ has already “paid” for these steps, and each single step makes it smaller.
Here is the smallest example, for S = 4 N − 3 S=4\mathbb{N}-3 S = 4 N − 3 and the modulus 4 4 4 . Let Φ ( x ) = 7 x \Phi(x)=7x Φ ( x ) = 7 x if x ≡ 1 ( m o d 4 ) x\equiv1\pmod4 x ≡ 1 ( mod 4 ) and Φ ( x ) = 4 x \Phi(x)=4x Φ ( x ) = 4 x otherwise. A number x ≡ 1 ( m o d 4 ) x\equiv1\pmod4 x ≡ 1 ( mod 4 ) goes up to the even number ( 3 x + 1 ) / 2 (3x+1)/2 ( 3 x + 1 ) /2 , so Φ \Phi Φ changes from 7 x 7x 7 x to 6 x + 2 6x+2 6 x + 2 , which is smaller for x > 2 x>2 x > 2 . Any other number x x x goes down to at most ( x + 1 ) / 2 (x+1)/2 ( x + 1 ) /2 , so Φ \Phi Φ changes from 4 x 4x 4 x to at most 7 2 ( x + 1 ) \frac{7}{2}(x+1) 2 7 ( x + 1 ) , which is smaller for x > 7 x>7 x > 7 . So Φ \Phi Φ decreases at every step from a number x ≥ 8 x\geq8 x ≥ 8 , and every orbit comes below 8 8 8 . From there it cannot climb back above U ( 5 ) = 8 U(5)=8 U ( 5 ) = 8 , and the numbers up to 8 8 8 all reach the cycle ( 1 , 2 ) (1,2) ( 1 , 2 ) . This proves that every orbit of T 4 N − 3 T_{4\mathbb{N}-3} T 4 N − 3 reaches ( 1 , 2 ) (1,2) ( 1 , 2 ) . In the notation of Theorem 5.11(ii) the weights are c = ( 4 , 7 , 4 , 4 ) c=(4,7,4,4) c = ( 4 , 7 , 4 , 4 ) at the residues 0 , 1 , 2 , 3 0,1,2,3 0 , 1 , 2 , 3 , and θ = 7 / 8 \theta=7/8 θ = 7/8 . (For this set the result also follows from Theorem 3.3(b); the point is that the same kind of proof works for sets with longer runs, such as the set of Theorem 6.4.)
Proof of Theorem 5.11. Let w ( r ) = log f ( r ) w(r)=\log f(r) w ( r ) = log f ( r ) , and define the weight of a path as the sum of w w w over its vertices other than the last one; a path of length t t t with a a a such vertices in S S S has weight log ( 3 a / 2 t ) \log(3^a/2^t) log ( 3 a / 2 t ) . (i)⇒ \Rightarrow ⇒ (iii). Every closed walk splits into simple cycles, and there are finitely many simple cycles, each of negative weight; let − γ < 0 -\gamma<0 − γ < 0 be the largest of their weights divided by their lengths. A path of length t t t splits into a simple path of length less than M M M and simple cycles of total length more than t − M t-M t − M , so its weight is less than M log 3 2 − γ ( t − M ) M\log\frac{3}{2}-\gamma(t-M) M log 2 3 − γ ( t − M ) , which is negative for large t t t . (iii)⇒ \Rightarrow ⇒ (iv). Let η < 1 \eta< 1 η < 1 be the largest value of 3 a / 2 t 3^a/2^t 3 a / 2 t over all paths of length t t t . By Theorem 5.5(a), the residues of an orbit form a path, and T S t ( x ) ≥ x / 2 t T_S^t(x) \ge x/2^t T S t ( x ) ≥ x / 2 t , since every step at least halves. So Theorem 5.1(a) gives T S t ( x ) ≤ x η ( 1 + 2 t / x ) T_S^t(x) \le x\eta(1+2^t/x) T S t ( x ) ≤ x η ( 1 + 2 t / x ) , which is less than x x x for large x x x .
(iv)⇒ \Rightarrow ⇒ (i). Suppose that a cycle r 0 → r 1 → ⋯ → r ℓ = r 0 r_0 \to r_1 \to\cdots\to r_\ell= r_0 r 0 → r 1 → ⋯ → r ℓ = r 0 has 3 a > 2 ℓ 3^a > 2^\ell 3 a > 2 ℓ . Its weights w ( r 0 ) , … , w ( r ℓ − 1 ) w(r_0),\ldots,w(r_{\ell-1}) w ( r 0 ) , … , w ( r ℓ − 1 ) have a positive sum, so for a suitable rotation all partial sums are nonnegative: start at a vertex r m r_m r m , 0 ≤ m < ℓ 0 \le m < \ell 0 ≤ m < ℓ , for which the partial sum ∑ i < m w ( r i ) \sum_{i<m} w(r_i) ∑ i < m w ( r i ) is smallest. We may therefore assume that the path P P P that goes around the cycle from r 0 r_0 r 0 repeatedly has weight at least 0 0 0 after any number of steps. Given t t t , by Theorem 5.5(b) there are arbitrarily large x x x whose residue sequence begins with the first t t t steps of P P P , and for them T S t ( x ) ≥ x 3 a / 2 t ≥ x T_S^t(x) \ge x\,3^a/2^t \ge x T S t ( x ) ≥ x 3 a / 2 t ≥ x by Theorem 5.1(a), where a a a now counts the steps up among the first t t t . So (iv) fails for every t t t .
(i)⇒ \Rightarrow ⇒ (ii). Let μ ∗ < 0 \mu^* < 0 μ ∗ < 0 be the largest mean weight of a simple cycle, choose μ ∈ ( μ ∗ , 0 ) \mu\in(\mu^*,0) μ ∈ ( μ ∗ , 0 ) , and let ψ ( r ) \psi(r) ψ ( r ) be the supremum of ∑ i < j ( w ( r i ) − μ ) \sum_{i<j}(w(r_i)-\mu) ∑ i < j ( w ( r i ) − μ ) over all paths r = r 0 → ⋯ → r j r=r_0\to\cdots\to r_j r = r 0 → ⋯ → r j , j ≥ 0 j\ge0 j ≥ 0 . Every cycle has negative weight for the weights w − μ w-\mu w − μ , so 0 ≤ ψ ( r ) ≤ M max r ∣ w ( r ) − μ ∣ 0\le\psi(r)\le M\max_r|w(r)-\mu| 0 ≤ ψ ( r ) ≤ M max r ∣ w ( r ) − μ ∣ , and ψ ( r ) ≥ w ( r ) − μ + ψ ( s ) \psi(r)\ge w(r)-\mu+\psi(s) ψ ( r ) ≥ w ( r ) − μ + ψ ( s ) for every edge r → s r\to s r → s . With c ( r ) = e ψ ( r ) c(r)=e^{\psi(r)} c ( r ) = e ψ ( r ) and θ = e μ \theta=e^\mu θ = e μ this is f ( r ) c ( s ) ≤ θ c ( r ) f(r)c(s)\le\theta c(r) f ( r ) c ( s ) ≤ θ c ( r ) . Replacing θ \theta θ by a slightly larger number below 1 1 1 , we may perturb the weights to rational numbers and then multiply them by a common denominator.
(ii)⇒ \Rightarrow ⇒ (i). Along a cycle, 3 a / 2 ℓ = ∏ i f ( r i ) ≤ ∏ i θ c ( r i ) / c ( r i + 1 ) = θ ℓ < 1 3^a/2^\ell=\prod_i f(r_i)\le\prod_i\theta c(r_i)/c(r_{i+1})=\theta^\ell<1 3 a / 2 ℓ = ∏ i f ( r i ) ≤ ∏ i θ c ( r i ) / c ( r i + 1 ) = θ ℓ < 1 .
Proof of Theorem 5.12. Let Φ ( x ) = c ( x m o d M ) x \Phi(x)=c(x\bmod M)x Φ ( x ) = c ( x mod M ) x , a positive integer. For x ≡ r ( m o d M ) x\equiv r\pmod M x ≡ r ( mod M ) we have T S ( x ) ≤ f ( r ) x ( 1 + 1 / x ) T_S(x)\le f(r)x(1+1/x) T S ( x ) ≤ f ( r ) x ( 1 + 1/ x ) , and T S ( x ) m o d M T_S(x)\bmod M T S ( x ) mod M is a successor s s s of r r r , so
Φ ( T S ( x ) ) = c ( s ) T S ( x ) ≤ θ c ( r ) f ( r ) f ( r ) x ( 1 + 1 x ) = θ ( 1 + 1 x ) Φ ( x ) . \Phi(T_S(x))=c(s)T_S(x)\le\frac{\theta c(r)}{f(r)}f(r)x\left(1+\frac{1}{x}\right)=\theta\left(1+\frac{1}{x}\right)\Phi(x). Φ ( T S ( x )) = c ( s ) T S ( x ) ≤ f ( r ) θ c ( r ) f ( r ) x ( 1 + x 1 ) = θ ( 1 + x 1 ) Φ ( x ) .
Hence Φ ( T S ( x ) ) < Φ ( x ) \Phi(T_S(x))<\Phi(x) Φ ( T S ( x )) < Φ ( x ) for x ≥ x 1 x\ge x_1 x ≥ x 1 . Since Φ \Phi Φ takes positive integer values, no orbit stays in [ x 1 , ∞ ) [x_1,\infty) [ x 1 , ∞ ) forever. Whenever an orbit passes from [ 1 , x 1 ) [1,x_1) [ 1 , x 1 ) to [ x 1 , ∞ ) [x_1,\infty) [ x 1 , ∞ ) , it arrives at a number y ≤ U ( x 1 ) y\le U(x_1) y ≤ U ( x 1 ) , and from then on, as long as it stays in [ x 1 , ∞ ) [x_1,\infty) [ x 1 , ∞ ) , its elements z z z satisfy c min z ≤ Φ ( z ) ≤ Φ ( y ) ≤ c max U ( x 1 ) c_{\min}z\le\Phi(z)\le\Phi(y)\le c_{\max}U(x_1) c m i n z ≤ Φ ( z ) ≤ Φ ( y ) ≤ c m a x U ( x 1 ) , so z < B z<B z < B . So after its first visit to [ 1 , x 1 ) [1,x_1) [ 1 , x 1 ) the orbit stays below B B B . The remaining claims follow.
We checked all sets that are periodic modulo 4 4 4 , 8 8 8 and 16 16 16 ; Table 5.3 lists how many of them are uniformly descending, and the largest effective up-frequency and density among these. Uniform descent forces π \pi π well below log 3 2 \log_3 2 log 3 2 , at least for small moduli. We do not know whether uniformly descending sets with π \pi π arbitrarily close to log 3 2 \log_3 2 log 3 2 exist for larger moduli (Theorem 7.10).
Table 5.3. The numbers of all sets and of the uniformly descending sets that are periodic modulo 2 k 2^k 2 k , k ≤ 4 k\le4 k ≤ 4 , and the largest effective up-frequency and density among the latter.
Mahler’s Z-numbers
Mahler [13 ] called a real number ξ > 0 \xi>0 ξ > 0 a Z Z Z -number if 0 ≤ { ξ ( 3 / 2 ) n } < 1 / 2 0\le\{\xi(3/2)^n\}<1/2 0 ≤ { ξ ( 3/2 ) n } < 1/2 for all n ≥ 0 n\ge0 n ≥ 0 , and asked whether Z Z Z -numbers exist; he proved that there is at most one in every interval [ m , m + 1 ) [m,m+1) [ m , m + 1 ) , and that the number of m ≤ X m\le X m ≤ X for which there is one is O ( X 0.7 ) O(X^{0.7}) O ( X 0.7 ) . The question is still open; see also Flatto, Lagarias and Pollington [7 ] . It turns out to be a question about one map of our family, or more precisely, it is implied by a question about one map.
Proposition 5.13. Let ξ \xi ξ be a Z Z Z -number and g n = ⌊ ξ ( 3 / 2 ) n ⌋ g_n = \lfloor\xi(3/2)^n \rfloor g n = ⌊ ξ ( 3/2 ) n ⌋ . Then g n + 1 = U ( g n ) g_{n+1} = U(g_n) g n + 1 = U ( g n ) and g n ≢ 3 ( m o d 4 ) g_n \not\equiv3 \pmod{4} g n ≡ 3 ( mod 4 ) for all n n n with g n ≥ 1 g_n \ge1 g n ≥ 1 . Consequently, the set S = N ∖ ( 4 N − 1 ) S = \mathbb{N} \setminus(4\mathbb{N}-1) S = N ∖ ( 4 N − 1 ) contains a tail of a chain, and T S T_S T S has an increasing orbit.
Proof. Write ξ ( 3 / 2 ) n = g n + f n \xi(3/2)^n = g_n + f_n ξ ( 3/2 ) n = g n + f n with 0 ≤ f n < 1 / 2 0 \le f_n < 1/2 0 ≤ f n < 1/2 . If g n g_n g n is even, then ξ ( 3 / 2 ) n + 1 = 3 2 g n + 3 2 f n \xi(3/2)^{n+1} = \frac{3}{2}g_n + \frac{3}{2}f_n ξ ( 3/2 ) n + 1 = 2 3 g n + 2 3 f n with 3 2 g n ∈ Z \frac{3}{2}g_n \in\mathbb{Z} 2 3 g n ∈ Z and 3 2 f n < 3 4 \frac{3}{2}f_n < \frac{3}{4} 2 3 f n < 4 3 , so g n + 1 = 3 2 g n = U ( g n ) g_{n+1} = \frac{3}{2}g_n = U(g_n) g n + 1 = 2 3 g n = U ( g n ) . If g n g_n g n is odd, then ξ ( 3 / 2 ) n + 1 = 3 g n + 1 2 + 3 f n − 1 2 \xi(3/2)^{n+1} = \frac{3g_n+1}{2} + \frac{3f_n-1}{2} ξ ( 3/2 ) n + 1 = 2 3 g n + 1 + 2 3 f n − 1 , and − 1 2 ≤ 3 f n − 1 2 < 1 4 -\frac{1}{2} \le\frac{3f_n-1}{2} < \frac{1}{4} − 2 1 ≤ 2 3 f n − 1 < 4 1 . If 3 f n < 1 3f_n < 1 3 f n < 1 , the fractional part f n + 1 = 3 f n + 1 2 f_{n+1} = \frac{3f_n+1}{2} f n + 1 = 2 3 f n + 1 would be at least 1 2 \frac{1}{2} 2 1 ; so 3 f n ≥ 1 3f_n \ge1 3 f n ≥ 1 , g n + 1 = 3 g n + 1 2 = U ( g n ) g_{n+1} = \frac{3g_n+1}{2} = U(g_n) g n + 1 = 2 3 g n + 1 = U ( g n ) , and f n + 1 = 3 f n − 1 2 < 1 4 f_{n+1} = \frac{3f_n-1}{2} < \frac{1}{4} f n + 1 = 2 3 f n − 1 < 4 1 . Since f n + 1 < 1 3 f_{n+1} < \frac{1}{3} f n + 1 < 3 1 , the same argument applied to n + 1 n+1 n + 1 shows that g n + 1 g_{n+1} g n + 1 cannot be odd. So every odd g n g_n g n has 3 g n + 1 2 \frac{3g_n+1}{2} 2 3 g n + 1 even, that is, g n ≡ 1 ( m o d 4 ) g_n \equiv1 \pmod{4} g n ≡ 1 ( mod 4 ) . As g n → ∞ g_n \to\infty g n → ∞ , the numbers g n ≥ 1 g_n \ge1 g n ≥ 1 form a tail of a chain that avoids 4 N − 1 4\mathbb{N}-1 4 N − 1 , and under T S T_S T S the orbit of its first element increases.
Corollary 5.14. If every chain contains infinitely many numbers ≡ 3 ( m o d 4 ) \equiv3 \pmod{4} ≡ 3 ( mod 4 ) , that is, if T S T_S T S has no increasing orbit for S = N ∖ ( 4 N − 1 ) S = \mathbb{N} \setminus(4\mathbb{N}-1) S = N ∖ ( 4 N − 1 ) , then there are no Z Z Z -numbers.
The set N ∖ ( 4 N − 1 ) \mathbb{N} \setminus(4\mathbb{N}-1) N ∖ ( 4 N − 1 ) is periodic modulo 4 4 4 with π = 5 / 6 > log 3 2 \pi= 5/6 > \log_3 2 π = 5/6 > log 3 2 (Table 5.2 ), so by Theorem 5.9 (b) a positive proportion of all orbits grows exponentially for a long time, and we expect T S T_S T S to have many divergent orbits. The corollary asks for much less than boundedness: only that no orbit avoids the residue class 3 3 3 modulo 4 4 4 forever while going up at every step. In the other direction, let e m e_m e m be the parity of U m ( c ) U^m(c) U m ( c ) . Since ( 2 / 3 ) m + 1 U m + 1 ( c ) = ( 2 / 3 ) m U m ( c ) + 1 3 ( 2 / 3 ) m e m (2/3)^{m+1}U^{m+1}(c) = (2/3)^mU^m(c) + \frac{1}{3}(2/3)^m e_m ( 2/3 ) m + 1 U m + 1 ( c ) = ( 2/3 ) m U m ( c ) + 3 1 ( 2/3 ) m e m , summing over m ≥ n m \ge n m ≥ n gives K c ( 3 / 2 ) n = U n ( c ) + 1 3 ∑ j ≥ 0 ( 2 / 3 ) j e n + j K_c(3/2)^n = U^n(c) + \frac{1}{3}\sum_{j \ge0}(2/3)^j e_{n+j} K c ( 3/2 ) n = U n ( c ) + 3 1 ∑ j ≥ 0 ( 2/3 ) j e n + j , so a chain tail from c c c that avoids 4 N − 1 4\mathbb{N}-1 4 N − 1 , and hence has no two consecutive odd elements, gives a number ξ = K c \xi= K_c ξ = K c with 0 < { ξ ( 3 / 2 ) n } ≤ 1 3 ( 1 + 4 9 + 16 81 + ⋯ ) = 3 5 0 < \{\xi(3/2)^n\} \le\frac{1}{3}(1 + \frac{4}{9} + \frac{16}{81} + \cdots) = \frac{3}{5} 0 < { ξ ( 3/2 ) n } ≤ 3 1 ( 1 + 9 4 + 81 16 + ⋯ ) = 5 3 for all n ≥ 0 n \ge0 n ≥ 0 , but not necessarily a Z Z Z -number. So the question of Theorem 5.14 lies between Mahler’s question and the same question for the interval ( 0 , 3 / 5 ] (0,3/5] ( 0 , 3/5 ] in place of [ 0 , 1 / 2 ) [0,1/2) [ 0 , 1/2 ) .
How far is the Collatz map from provable behaviour?
The Collatz map is T S T_S T S for S = 2 N − 1 S = 2\mathbb{N}-1 S = 2 N − 1 . We now ask which modifications of this set make the behaviour of the map provable, in either direction: that every orbit reaches the cycle ( 1 , 2 ) (1,2) ( 1 , 2 ) , or that some orbit diverges. A modification is described by the set S △ ( 2 N − 1 ) S \mathbin{\triangle} (2\mathbb{N}-1) S △ ( 2 N − 1 ) of changed numbers, which consists of the removed odd numbers ( 2 N − 1 ) ∖ S (2\mathbb{N}-1) \setminus S ( 2 N − 1 ) ∖ S and the added even numbers S ∩ 2 N S \cap2\mathbb{N} S ∩ 2 N , and we measure its size by the number of changed numbers below N N N , or by its density. This gives a notion of distance between the Collatz map and the maps whose behaviour we can prove. The answers are very different in the two directions (Table 1.1 ).
Finite changes
By Theorem 2.4, changing 2 N − 1 2\mathbb{N}-1 2 N − 1 at finitely many numbers does not change whether there are divergent orbits.
Corollary 6.1. If S △ ( 2 N − 1 ) S \mathbin{\triangle} (2\mathbb{N}-1) S △ ( 2 N − 1 ) is finite, then T S T_S T S has a divergent orbit if and only if the Collatz map has one.
So every modification that makes the existence or the absence of divergent orbits provable must be infinite, unless it settles the same question for the Collatz map itself. We look for infinite modifications that are as thin as possible.
Divergence from a logarithmically thin addition
The cheapest way to create a divergent orbit is to complete a chain: an orbit goes up forever if and only if it runs along a chain inside S S S (Theorem 3.3(a)), and the odd elements of every chain are already in 2 N − 1 2\mathbb{N}-1 2 N − 1 .
Proposition 6.2. Let A A A be the set of even elements of the chain Γ 1 = { U r ( 1 ) : r ≥ 0 } \Gamma_1=\{U^r(1):r\ge0\} Γ 1 = { U r ( 1 ) : r ≥ 0 } ,
A = { 2 , 8 , 12 , 18 , 62 , 140 , 210 , 710 , 1598 , 3596 , 5394 , 18206 , 40964 , 61446 , … } . A=\{2,8,12,18,62,140,210,710,1598,3596,5394,18206,40964,61446,\ldots\}. A = { 2 , 8 , 12 , 18 , 62 , 140 , 210 , 710 , 1598 , 3596 , 5394 , 18206 , 40964 , 61446 , … } . Then the orbit of 1 1 1 under T ( 2 N − 1 ) ∪ A T_{(2\mathbb{N}-1)\cup A} T ( 2 N − 1 ) ∪ A is Γ 1 \Gamma_1 Γ 1 and increases, and # ( A ∩ [ 1 , N ] ) ≤ log 3 / 2 N \#(A\cap[1,N])\le\log_{3/2}N # ( A ∩ [ 1 , N ]) ≤ log 3/2 N for all N ≥ 1 N\ge1 N ≥ 1 . The same holds for the even elements of any chain.
Proof. Every element of Γ 1 \Gamma_1 Γ 1 is odd or lies in A A A , so Γ 1 ⊆ ( 2 N − 1 ) ∪ A \Gamma_1\subseteq(2\mathbb{N}-1)\cup A Γ 1 ⊆ ( 2 N − 1 ) ∪ A , and the orbit of 1 1 1 goes up at every step. By Theorem 2.1(d), U r ( 1 ) > K 1 ( 3 / 2 ) r − 1 ≥ ( 3 / 2 ) r U^r(1)>K_1(3/2)^r-1\ge(3/2)^r U r ( 1 ) > K 1 ( 3/2 ) r − 1 ≥ ( 3/2 ) r for r ≥ 2 r\ge2 r ≥ 2 , and also for r = 0 , 1 r=0,1 r = 0 , 1 , so Γ 1 \Gamma_1 Γ 1 has at most log 3 / 2 N + 1 \log_{3/2}N+1 log 3/2 N + 1 elements in [ 1 , N ] [1,N] [ 1 , N ] , one of which is the odd number 1 1 1 .
Up to 10 60 10^{60} 1 0 60 the chain Γ 1 \Gamma_1 Γ 1 has 340 elements, of which 173 are even, so the added set has about 1 2 log 3 / 2 N \frac{1}{2}\log_{3/2}N 2 1 log 3/2 N elements below N N N . The parities of the numbers ⌊ K 1 ( 3 / 2 ) n ⌋ \lfloor K_1(3/2)^n\rfloor ⌊ K 1 ( 3/2 ) n ⌋ are the subject of Mahler’s problem and are not understood, but they look random, and this count is what one expects. For instance, only 18 even numbers below 10 6 10^6 1 0 6 are added.
The effect of this thin addition is drastic. Under the modified map every element of Γ 1 \Gamma_1 Γ 1 goes up, so an orbit that meets Γ 1 \Gamma_1 Γ 1 increases from then on. An orbit of the modified map agrees with the Collatz orbit of the same number until that orbit first meets Γ 1 \Gamma_1 Γ 1 , and a Collatz orbit that reaches 1 1 1 meets Γ 1 \Gamma_1 Γ 1 , since 1 ∈ Γ 1 1\in\Gamma_1 1 ∈ Γ 1 . Hence, if the Collatz conjecture is true, then every orbit of T ( 2 N − 1 ) ∪ A T_{(2\mathbb{N}-1)\cup A} T ( 2 N − 1 ) ∪ A diverges.
Could fewer additions suffice, say o ( log N ) o(\log N) o ( log N ) below N N N ? By Theorem 5.1(b) a divergent orbit goes up a proportion at least log 3 2 > 1 / 2 \log_3 2>1/2 log 3 2 > 1/2 of the time, while the steps up of a typical orbit at odd numbers make up only about half of its steps; so if the orbit is typical, it needs steps up at added even numbers at a positive proportion of its steps, and since it grows exponentially, this means order log N \log N log N added numbers below N N N . An atypical orbit that visits odd numbers unusually often might need fewer.
Remark 6.3 (A first-moment heuristic). Model the parities of the numbers visited by the paths from a given number by independent fair coins, and count the paths of length t t t in G ⟨ 2 N − 1 , N ⟩ G_{\langle2\mathbb{N}-1,N\rangle} G ⟨ 2 N − 1 , N ⟩ (up at odd numbers, free at even numbers) that visit about o t ot o t odd numbers and go up at about κ t \kappa t κ t even numbers. Their expected number is exp ( t ( H ( o ) + ( 1 − o ) H ( κ 1 − o ) − log 2 ) + o ( t ) ) \exp(t(H(o)+(1-o)H(\frac{\kappa}{1-o})-\log2)+o(t)) exp ( t ( H ( o ) + ( 1 − o ) H ( 1 − o κ ) − log 2 ) + o ( t )) , where H H H is the entropy function in natural logarithms, and such a path grows by the factor exp ( t ( ( o + κ ) log 3 − log 2 ) ) \exp(t((o+\kappa)\log3-\log2)) exp ( t (( o + κ ) log 3 − log 2 )) . Minimizing the number of additions per unit of logarithmic growth, κ / ( ( o + κ ) log 3 − log 2 ) \kappa/((o+\kappa)\log3-\log2) κ / (( o + κ ) log 3 − log 2 ) , subject to a nonnegative first exponent gives about 0.23 0.23 0.23 , at o ≈ 0.69 o\approx0.69 o ≈ 0.69 and κ ≈ 0.021 \kappa\approx0.021 κ ≈ 0.021 , compared with 1 / log 9 4 ≈ 1.23 1/\log\frac{9}{4}\approx1.23 1/ log 4 9 ≈ 1.23 for the even elements of a chain. So the model suggests that order log N \log N log N additions below N N N are needed, but with a smaller constant than in Theorem 6.2: as κ → 0 \kappa\to0 κ → 0 the constraint forces o → 1 / 2 o\to1/2 o → 1/2 and negative growth.
Convergence from removing residue classes
In order to prove that every orbit converges, we must control all orbits at once; the tool is uniform descent (§ 7.4 ). The Collatz set itself is not uniformly descending: its residue graph modulo 2 k 2^k 2 k has the loop 2 k − 1 → 2 k − 1 2^k-1\to2^k-1 2 k − 1 → 2 k − 1 at a vertex in S S S , the shadow of the fixed point − 1 -1 − 1 of the Collatz map on the 2-adic integers, since U ( 2 k − 1 ) = 3 ⋅ 2 k − 1 − 1 ≡ − 1 + 2 k − 1 U(2^k-1)=3\cdot2^{k-1}-1\equiv-1+2^{k-1} U ( 2 k − 1 ) = 3 ⋅ 2 k − 1 − 1 ≡ − 1 + 2 k − 1 . Removing residue classes from 2 N − 1 2\mathbb{N}-1 2 N − 1 can break such cycles. The smallest modulus at which a removal of density less than 1 / 4 1/4 1/4 works is 16:
Theorem 6.4. Let S S S be the set of odd numbers x x x with x ≢ 9 , 15 ( m o d 16 ) x \not\equiv9, 15 \pmod{16} x ≡ 9 , 15 ( mod 16 ) . Then every orbit of T S T_S T S reaches the cycle ( 1 , 2 ) (1,2) ( 1 , 2 ) .
Explicitly, the map of the theorem is
x ↦ { x / 2 , x even , ( x + 1 ) / 2 , x ≡ 9 or 15 ( m o d 16 ) , ( 3 x + 1 ) / 2 , all other odd x . x \mapsto
\begin{cases}
x/2, & x\ \text{even},\\
(x+1)/2, & x \equiv9\ \text{or}\ 15 \pmod{16},\\
(3x+1)/2, & \text{all other odd }x.
\end{cases} x ↦ ⎩ ⎨ ⎧ x /2 , ( x + 1 ) /2 , ( 3 x + 1 ) /2 , x even , x ≡ 9 or 15 ( mod 16 ) , all other odd x .
So turning the steps at the odd numbers ≡ 9 \equiv9 ≡ 9 and ≡ 15 ( m o d 16 ) \equiv15 \pmod{16} ≡ 15 ( mod 16 ) , an eighth of all positive integers, from up into down gives a Collatz-type map whose convergence can be proved in a few lines. For example, the Collatz orbit of 27 needs 70 steps to reach 1 and climbs to 4616 on the way; under the modified map the orbit is 27, 41, 21, 32, 16, 8, 4, 2, 1, because 41 ≡ 9 ( m o d 16 ) \equiv9 \pmod{16} ≡ 9 ( mod 16 ) goes down to 21 instead of up to 62.
Proof. The proof is an instance of Theorem 5.12 : a weighted size Φ ( x ) = c ( x m o d 16 ) x \Phi(x) = c(x \bmod16)x Φ ( x ) = c ( x mod 16 ) x decreases at every step from every large enough x x x , and the remaining small numbers are checked directly. S S S is periodic modulo 16, and Table 6.1 lists its residue graph: for instance 7 ∈ S 7 \in S 7 ∈ S goes up to U ( 7 ) = 11 U(7) = 11 U ( 7 ) = 11 , so its successors are 11 and 11 + 8 ≡ 3 11 + 8 \equiv3 11 + 8 ≡ 3 , while 9 ∉ S 9 \notin S 9 ∈ / S goes down to D ( 9 ) = 5 D(9) = 5 D ( 9 ) = 5 , with successors 5 and 13. The weights satisfy f ( r ) c ( s ) ≤ 75 76 c ( r ) f(r)c(s) \le\frac{75}{76}c(r) f ( r ) c ( s ) ≤ 76 75 c ( r ) on all 32 edges, as the last column shows. In Theorem 5.12 we have θ = 75 / 76 \theta= 75/76 θ = 75/76 , so x 1 = 76 x_1 = 76 x 1 = 76 , U ( 76 ) = 114 U(76) = 114 U ( 76 ) = 114 , and B = ⌊ 58 ⋅ 114 / 16 ⌋ + 1 = 414 B = \lfloor58 \cdot114/16 \rfloor+ 1 = 414 B = ⌊ 58 ⋅ 114/16 ⌋ + 1 = 414 . Concretely, Φ ( x ) = c ( x m o d 16 ) x \Phi(x) = c(x \bmod16)x Φ ( x ) = c ( x mod 16 ) x decreases at every step from a number x ≥ 76 x \ge76 x ≥ 76 , and every orbit eventually stays below 414. A computation shows that every x x x with 2 ≤ x ≤ 414 2 \le x \le414 2 ≤ x ≤ 414 falls below itself within at most 8 steps, so by induction on x x x every x ≤ 414 x \le414 x ≤ 414 reaches 1. Since 1 ∈ S 1 \in S 1 ∈ S , the orbit of 1 is the cycle ( 1 , 2 ) (1,2) ( 1 , 2 ) .
Table 6.1. A certificate for Theorem 6.4: the residue graph of S S S modulo 16 with weights c ( r ) c(r) c ( r ) . The last column is the largest ratio f ( r ) c ( s ) / c ( r ) f(r)c(s)/c(r) f ( r ) c ( s ) / c ( r ) over the two successors s s s ; all are at most θ = 75 / 76 \theta= 75/76 θ = 75/76 .
Why the classes 9 and 15? Call a cycle of a residue graph expanding if 3 a > 2 ℓ 3^a > 2^\ell 3 a > 2 ℓ , that is, if going around it multiplies a number by more than 1; a set is uniformly descending exactly when its residue graph has no expanding cycle. The residue graph of 2 N − 1 2\mathbb{N}-1 2 N − 1 modulo 16 has exactly eleven expanding simple cycles. The shortest are the loop at 15, the cycle 6 → 11 → 9 → 6 6 \to11 \to9 \to6 6 → 11 → 9 → 6 and the cycle 7 → 11 → 9 → 14 → 7 7 \to11 \to9 \to14 \to7 7 → 11 → 9 → 14 → 7 . A modification can make the residue graph uniformly descending only if it changes the step at some residue on each of these eleven cycles. Nine of them pass through the residue 9, and the same nine pass through the residue 11; the other two, among them the loop, pass through 15. So with two residues there are exactly two candidates, { 9 , 15 } \{9,15\} { 9 , 15 } and { 11 , 15 } \{11,15\} { 11 , 15 } , and both work: the second choice gives a theorem like Theorem 6.4 as well, with π = 13 / 48 \pi= 13/48 π = 13/48 . Changing the steps at even residues gives no further possibilities with two residues.
Remark 6.5 (Shadows of negative cycles). By Theorem 5.7, the cycles of the residue graph of 2 N − 1 2\mathbb{N}-1 2 N − 1 with 3 a > 2 ℓ 3^a > 2^\ell 3 a > 2 ℓ are the residues of periodic orbits of the Collatz map T T T , extended to the 2 2 2 -adic integers, that consist of negative rational numbers. Modulo 16, the loop at 15 is the fixed point − 1 -1 − 1 , the cycle 6 → 11 → 9 → 6 6 \to11 \to9 \to6 6 → 11 → 9 → 6 is the cycle − 10 → − 5 → − 7 → − 10 -10 \to-5 \to-7 \to-10 − 10 → − 5 → − 7 → − 10 of T T T on the negative integers, and the cycle 7 → 11 → 9 → 14 → 7 7 \to11 \to9 \to14 \to7 7 → 11 → 9 → 14 → 7 is the cycle − 19 11 → − 23 11 → − 29 11 → − 38 11 → − 19 11 -\frac{19}{11} \to-\frac{23}{11} \to-\frac{29}{11} \to-\frac{38}{11} \to-\frac{19}{11} − 11 19 → − 11 23 → − 11 29 → − 11 38 → − 11 19 . Of the three known cycles of T T T on the negative integers, the third, of length 11 through − 17 -17 − 17 , passes through − 17 ≡ 15 -17 \equiv15 − 17 ≡ 15 as well. So to make a periodic modification of the Collatz map uniformly descending, one has to destroy all the negative rational cycles of the extended map that are visible modulo 2 k 2^k 2 k . Finding the smallest such removal is a hitting-set problem for the cycles of a finite graph.
For every k k k let δ k \delta_k δ k be the smallest density of S △ ( 2 N − 1 ) S \mathbin{\triangle} (2\mathbb{N}-1) S △ ( 2 N − 1 ) over all sets S S S that are periodic modulo 2 k 2^k 2 k and uniformly descending, and let δ k − ≥ δ k \delta_k^- \ge\delta_k δ k − ≥ δ k be the same minimum over such sets S ⊆ 2 N − 1 S \subseteq2\mathbb{N}-1 S ⊆ 2 N − 1 , that is, over removals only. Both sequences are non-increasing in k k k , since uniform descent does not depend on the modulus. A modification has to change at least one residue on every cycle of R k ( 2 N − 1 ) \mathcal{R}_k(2\mathbb{N}-1) R k ( 2 N − 1 ) with 3 a > 2 ℓ 3^a > 2^\ell 3 a > 2 ℓ , so p p p pairwise disjoint such cycles give δ k ≥ p / 2 k \delta_k \ge p/2^k δ k ≥ p / 2 k . On the other side, every removal for which the residue graph is uniformly descending gives an upper bound, which becomes a theorem like Theorem 6.4 once a certificate has been computed and the orbits below the bound B B B of Theorem 5.12 have been checked. Table 6.2 shows what we found.
Table 6.2. Smallest periodic modifications of 2 N − 1 2\mathbb{N}-1 2 N − 1 that are uniformly descending. Bold entries are exact. R k R_k R k is a set of removed odd residues of density # R k / 2 k \#R_k/2^k # R k / 2 k that attains the upper bound (listed in Section A); for it, π \pi π is the effective up-frequency of ( 2 N − 1 ) ∖ R k (2\mathbb{N}-1)\setminus R_k ( 2 N − 1 ) ∖ R k , “worst cycle” the largest proportion a / ℓ a/\ell a / ℓ over the cycles of its residue graph, and θ \theta θ and B B B describe the certificate. An entry [ p , q ] / 2 k [p,q]/2^k [ p , q ] / 2 k means that the value lies between p / 2 k p/2^k p / 2 k and q / 2 k q/2^k q / 2 k . For every R k R_k R k , all orbits reach ( 1 , 2 ) (1,2) ( 1 , 2 ) .
For k = 2 k=2 k = 2 and k = 3 k=3 k = 3 the best removal is the class 3 (mod 4), which leaves 4 N − 3 4\mathbb{N}-3 4 N − 3 and is covered by Theorem 3.3(b) as well. The proportion of changed numbers decreases slowly: 1 / 4 1/4 1/4 , 1 / 4 1/4 1/4 , 1 / 8 1/8 1/8 , 1 / 8 1/8 1/8 , 5 / 64 5/64 5/64 , 1 / 16 1/16 1/16 , and then at most 0.047, 0.043 and 0.043. As the modulus grows, the surviving cycles come closer to the threshold (a / ℓ = 3 / 5 a/\ell= 3/5 a / ℓ = 3/5 , 5 / 8 5/8 5/8 , 17 / 27 17/27 17/27 , three fractions just below log 3 2 \log_3 2 log 3 2 ), the certificates get tighter (θ → 1 \theta\to1 θ → 1 ), and the bounds B B B for the finite checks tend to grow. Two features are worth noting. First, for k ≥ 4 k \ge4 k ≥ 4 removing classes lowers the effective up-frequency from 1 / 2 1/2 1/2 to between 0.29 and 0.38, far below log 3 2 \log_3 2 log 3 2 , although only a few percent of all numbers are changed: the removed classes are exactly the ones through which orbits climb. Second, for k ≤ 7 k \le7 k ≤ 7 allowing changes at even residues as well does not help, δ k = δ k − \delta_k=\delta_k^- δ k = δ k − ; we do not know whether this persists.
Remark 6.6 (Consequences for the Collatz map). Let R R R be the set of numbers removed in Theorem 6.4 or in a row of Table 6.2 , and let S = ( 2 N − 1 ) ∖ R S=(2\mathbb{N}-1)\setminus R S = ( 2 N − 1 ) ∖ R . The maps T S T_S T S and T T T differ only at the numbers of R R R , so an orbit of the Collatz map T T T is an orbit of T S T_S T S until it meets R R R . Since every orbit of T S T_S T S reaches 1, every orbit of the Collatz map reaches 1 or contains a number of R R R . Applied to the tails of an orbit, this shows that a divergent orbit of T T T would contain infinitely many numbers of R R R , and that a cycle of T T T other than ( 1 , 2 ) (1, 2) ( 1 , 2 ) would contain at least one. So the Collatz conjecture is equivalent to the statement that every x = 9 x = 9 x = 9 or 15 (mod 16) reaches 1, and equally to the same statement for the 22 classes of R 9 R_9 R 9 modulo 512, which contain 4.3% of all numbers.
Reductions of this kind are known. A set is called sufficient if the orbit of every positive integer meets the orbit of some element of the set, and Monks [17 ] proved that every arithmetic progression is sufficient. The property above is stronger, because the orbit itself has to pass through the set. Monks, Monks, Monks and Monks [16 ] call a set forward sufficient if every divergent orbit of T T T contains an element of it. They prove that a set of residues modulo d d d is forward sufficient if every cycle of the residue graph of T T T that avoids these residues has a proportion of steps up below log 3 2 \log_3 2 log 3 2 , and their examples, found by computer, include the pairs { 9 , 15 } \{9, 15\} { 9 , 15 } and { 11 , 15 } \{11, 15\} { 11 , 15 } modulo 16 of this section. Their criterion asks less than uniform descent of T S T_S T S : only the cycles that avoid the chosen residues matter, and the residues may be even. For k ≤ 7 k \le7 k ≤ 7 it still does not give smaller sets, because no set of fewer than 2 k δ k 2^k\delta_k 2 k δ k residues modulo 2 k 2^k 2 k meets every expanding cycle of R k ( 2 N − 1 ) R_k(2\mathbb{N}-1) R k ( 2 N − 1 ) (Section A). What Theorem 6.4 and Table 6.2 add is the statement for cycles, which comes from the same finite check, the minimality for k ≤ 7 k \le7 k ≤ 7 , and the sets for the moduli up to 1024.
None of this is a shortcut for the numerical verification of the Collatz conjecture. The first number of R R R on the orbit of x x x can be larger than x x x : from 27 the orbit goes to 41, and from 39 it reaches 89 before any other number of R R R . A certificate only shows that this number is less than x c max / c min x\,c_{\max}/c_{\min} x c m a x / c m i n for x ≥ x 1 x \ge x_1 x ≥ x 1 . So in order to verify the conjecture for all x ≤ N x \le N x ≤ N one would have to follow the numbers of R R R up to a multiple of N N N , each of them all the way to 1. The sieves used in practice [4 ] discard the residue classes modulo 2 k 2^k 2 k whose numbers fall below themselves within k k k steps. The classes that are kept also meet every orbit that does not reach 1, a kept number has to be followed only until it falls below itself, and k k k can be taken large. At equal modulus the sets R k R_k R k are smaller, with 2, 4, 5, 8, 12, 22, 44 classes for k = 4 , … , 10 k = 4, \ldots, 10 k = 4 , … , 10 against 3, 4, 8, 13, 19, 38, 64 kept classes, but this does not outweigh the two disadvantages.
Boundedness from barriers
If we only ask for boundedness, and not for convergence to ( 1 , 2 ) (1, 2) ( 1 , 2 ) , there is a cheaper but irregular way: create barriers.
Proposition 6.7. Let B 1 < B 2 < ⋯ B_1 < B_2 < \cdots B 1 < B 2 < ⋯ be integers with B i + 1 ≥ 2 B i B_{i+1} \ge2^{B_i} B i + 1 ≥ 2 B i , and let R R R be the set of odd numbers in ⋃ i ( 2 B i / 3 , B i ] \bigcup_i(2B_i/3,B_i] ⋃ i ( 2 B i /3 , B i ] . Then T S T_S T S is bounded for S = ( 2 N − 1 ) ∖ R S=(2\mathbb{N}-1)\setminus R S = ( 2 N − 1 ) ∖ R , and R R R has lower density 0. On the other hand, every R ⊆ 2 N − 1 R \subseteq2\mathbb{N}-1 R ⊆ 2 N − 1 for which ( 2 N − 1 ) ∖ R (2\mathbb{N}-1)\setminus R ( 2 N − 1 ) ∖ R is trivially bounded has upper density at least 1 / 6 1/6 1/6 .
Proof. Every B i B_i B i is a barrier of S S S , so S S S is trivially bounded. For N = ⌊ 2 B i + 1 / 3 ⌋ N=\lfloor2B_{i+1}/3\rfloor N = ⌊ 2 B i + 1 /3 ⌋ we have R ∩ [ 1 , N ] ⊆ [ 1 , B i ] R\cap[1,N]\subseteq[1,B_i] R ∩ [ 1 , N ] ⊆ [ 1 , B i ] , so # ( R ∩ [ 1 , N ] ) / N ≤ B i / N → 0 \#(R\cap[1,N])/N\le B_i/N\to0 # ( R ∩ [ 1 , N ]) / N ≤ B i / N → 0 . Conversely, if B B B is a barrier of ( 2 N − 1 ) ∖ R (2\mathbb{N}-1)\setminus R ( 2 N − 1 ) ∖ R , then R R R contains all odd numbers in ( 2 B / 3 , B ] (2B/3,B] ( 2 B /3 , B ] , at least B / 6 − 1 B/6-1 B /6 − 1 of them, so # ( R ∩ [ 1 , B ] ) ≥ B / 6 − 1 \#(R\cap[1,B])\ge B/6-1 # ( R ∩ [ 1 , B ]) ≥ B /6 − 1 for infinitely many B B B . □ \square □
Such a map is bounded, but we cannot say which cycles it has: below each barrier it is still a Collatz map with some steps changed. Barriers also need a positive upper density, so in terms of density they are no better than the periodic removals of Table 6.2 .
The asymmetry
The two directions behave very differently. A divergent orbit is a single path that never comes down, and a set that contains it can be extremely thin: it only has to supply the steps up that the Collatz map does not already make, and along a chain these are the even elements. A proof of convergence must control every orbit, and for a periodic modification this means breaking every expanding cycle of the residue graph, that is, every negative rational cycle of the extended map that is visible modulo 2 k 2^k 2 k (Theorem 6.5). Conversely, residues can never prove divergence for a periodic set: by Theorem 5.6 a divergent orbit has aperiodic residues, so a proof of divergence has to use the archimedean size of the numbers, as the chains of Theorem 6.2 and the rays of Theorem 5.2 do.
Measured by counting functions, the Collatz set is therefore within O ( log N ) O(\log N) O ( log N ) of a provably divergent map, and within 0.043 N 0.043N 0.043 N of a map that provably converges. We do not know whether the second distance can be made o ( N ) o(N) o ( N ) , whether removals alone, without additions, can produce a divergent orbit, or whether o ( log N ) o(\log N) o ( log N ) additions can (Theorems 7.6, 7.12 and 7.13).
Questions
Some of the questions that arose, roughly in the order of the sections.
Cycles
Question 7.1. Does every cycle satisfy 2 ℓ < 3 a + 1 2^\ell< 3^{a+1} 2 ℓ < 3 a + 1 , that is, a = ⌊ ℓ log 3 2 ⌋ a = \lfloor\ell\log_3 2 \rfloor a = ⌊ ℓ log 3 2 ⌋ ? This holds for cycles with a single run of steps up (Theorem 4.1 (d)), for all cycles of length ℓ ≤ 30 \ell\le30 ℓ ≤ 30 , and for all 1,133,265,572 cycles whose elements are all at most 160; among the latter, the largest ratio 2 ℓ / 3 a 2^\ell/3^a 2 ℓ / 3 a is 2.398, for ℓ = 71 \ell= 71 ℓ = 71 . If the answer is negative, what is the supremum of 2 ℓ / 3 a 2^\ell/3^a 2 ℓ / 3 a ?
Question 7.2. Which lengths occur? Up to 30 they are 1, 2, 5, 8, 10, 13, 15, 16, 21, 24, 26, 27, 29, and occurrence is not monotone in 2 ℓ / 3 ⌊ ℓ log 3 2 ⌋ 2^\ell/3^{\lfloor\ell\log_3 2 \rfloor} 2 ℓ / 3 ⌊ ℓ l o g 3 2 ⌋ : there is no cycle of length 7, with ratio 1.580, but there are 12 of length 15, with ratio 1.665. Is every large ℓ \ell ℓ a cycle length, and how fast does the number of cycles of length ℓ \ell ℓ grow?
Question 7.3. Is there a map with infinitely many cycles and a divergent orbit (Theorem 4.4)?
Question 7.4. Is there a set S S S such that the orbit of 1 under T S T_S T S contains every positive integer, that is, does G G G have a ray through all vertices? Such a ray has to start at 1, since the only edges into 1 come from 1 and 2, and it has to continue with 2, 3, 5, 8, since D ( 2 ) = 1 D(2) = 1 D ( 2 ) = 1 , D ( 3 ) = 2 D(3) = 2 D ( 3 ) = 2 and D ( 5 ) = 3 D(5) = 3 D ( 5 ) = 3 have already been visited.
Families
Question 7.5. Which sets B B B are force-bounded, that is, for which B B B has G ⟨ ∅ , B ⟩ G_{\langle\varnothing,B\rangle} G ⟨ ∅ , B ⟩ no ray? Trivially bounded sets and sets with λ ( B ) ≤ 1 \lambda(B) \le1 λ ( B ) ≤ 1 are, and sets that contain a tail of a chain are not. The two copies of the Collatz map behave very differently here. For B = 2 N B = 2N B = 2 N , every x ≤ 20,000 x \le20{,}000 x ≤ 20 , 000 reaches at most 2,466 vertices of G ⟨ ∅ , 2 N ⟩ G_{\langle\varnothing,2N\rangle} G ⟨ ∅ , 2 N ⟩ , and every cycle of a map T S T_S T S with S ⊆ 2 N S \subseteq2N S ⊆ 2 N and all elements below 4 ⋅ 10 6 4 \cdot10^6 4 ⋅ 1 0 6 lies in { 1 } \{1\} { 1 } , in { 2 , 3 } \{2,3\} { 2 , 3 } , or in one strongly connected set of 74 vertices between 28 and 4617; this set contains the Collatz orbit of 27, shifted by one, up to its maximum. (For instance, following the Collatz orbit of 27 up to 445, and then taking ( y − 1 ) / 2 (y - 1)/2 ( y − 1 ) /2 instead of ( 3 y + 1 ) / 2 (3y + 1)/2 ( 3 y + 1 ) /2 at y = 445 y = 445 y = 445 , 111 and 55, returns to 27.) For B = 2 N − 1 B = 2N - 1 B = 2 N − 1 , the strongly connected component of 15 in the subgraph of G ⟨ ∅ , 2 N − 1 ⟩ G_{\langle\varnothing,2N-1\rangle} G ⟨ ∅ , 2 N − 1 ⟩ induced by [ 1 , 2 28 ] [1,2^{28}] [ 1 , 2 28 ] contains 19.6% of all numbers in this interval. Is 2 N 2N 2 N force-bounded? This would imply that no Collatz orbit diverges.
Question 7.6. Is there a set S S S of odd numbers for which T S T_S T S has a divergent orbit? In other words, can removing odd numbers from the Collatz set, without adding even ones, produce divergence?
Question 7.7. Does every force-divergent set, that is, every A A A such that T S T_S T S is unbounded for all S ⊇ A S \supseteq A S ⊇ A , contain a tail of a chain?
Typical and periodic sets
Question 7.8. For the random sets of Theorem 3.9(b) with p > log 3 2 p > \log_3 2 p > log 3 2 , does T S T_S T S almost surely have a divergent orbit?
Question 7.9. Let S S S be periodic modulo a power of 2.
(a) If π C ( S ) < log 3 2 \pi_C(S) < \log_3 2 π C ( S ) < log 3 2 for every closed class C C C , is T S T_S T S bounded? For S = 2 N − 1 S = 2\mathbb{N} - 1 S = 2 N − 1 this includes the statement that no Collatz orbit diverges.
(b) If π C ( S ) > log 3 2 \pi_C(S) > \log_3 2 π C ( S ) > log 3 2 for some closed class, is T S T_S T S unbounded? Is there any set S S S that is periodic modulo a power of 2, misses at least one residue class, and for which T S T_S T S provably has a divergent orbit? By Theorem 5.6 its residues would have to be aperiodic.
(c) Is it decidable whether T S T_S T S is bounded, or whether all its orbits reach a given cycle? Compare [5 , 8 ] ; uniform descent (Theorem 5.11 ) is decidable.
Question 7.10. Is the supremum of π C ( S ) \pi_C(S) π C ( S ) over all uniformly descending periodic sets S S S equal to log 3 2 \log_3 2 log 3 2 ? Modulo 16 the largest value is 73 / 174 = 0.420 73/174 = 0.420 73/174 = 0.420 (Table 5.3 ).
Question 7.11. Does N ∖ ( 4 N − 1 ) \mathbb{N} \setminus(4\mathbb{N} - 1) N ∖ ( 4 N − 1 ) contain a tail of a chain? A negative answer would show that there are no Z Z Z -numbers (Theorem 5.14).
The distance of the Collatz map from provable behaviour
Question 7.12. Does δ k → 0 \delta_k \to0 δ k → 0 (Table 6.2 )? More generally, is there a set R R R of density zero such that every orbit of T S T_S T S , S = ( 2 N − 1 ) △ R S = (2\mathbb{N} - 1)\triangle R S = ( 2 N − 1 ) △ R , provably reaches ( 1 , 2 ) (1,2) ( 1 , 2 ) , or at least such that T S T_S T S is provably bounded?
Question 7.13. Is there a set A A A of even numbers with # ( A ∩ [ 1 , N ] ) = o ( log N ) \#(A \cap[1,N]) = o(\log N) # ( A ∩ [ 1 , N ]) = o ( log N ) such that T ( 2 N − 1 ) ∪ A T_{(2\mathbb{N}-1)\cup A} T ( 2 N − 1 ) ∪ A has a divergent orbit? Theorem 6.3 suggests not; what is the smallest constant c c c for which c log N c\log N c log N added numbers below N N N suffice?
Question 7.14. Find further classes of sets that are not trivially bounded and whose maps can be analysed. Others than the periodic ones are sets defined by binary digits, Beatty sets and the primes. For the primes, every n ≤ 10 7 n \le10^7 n ≤ 1 0 7 reaches one of the cycles ( 1 ) (1) ( 1 ) , ( 2 , 3 , 5 , 8 , 4 ) (2, 3, 5, 8, 4) ( 2 , 3 , 5 , 8 , 4 ) and ( 31 , 47 , 71 , 107 , 161 , 81 , 41 , 62 ) (31, 47, 71, 107, 161, 81, 41, 62) ( 31 , 47 , 71 , 107 , 161 , 81 , 41 , 62 ) , the last one from 12.8% of them.
Acknowledgments
This work was carried out with the assistance of the AI models Claude Opus 5.5 and Claude Fable 5.2 (Anthropic), which helped with the literature search, the derivations and computations, and with the drafting of the text. The author has checked the results and takes full responsibility for the content.
Computations
The ancillary files of the paper contain the C and Python scripts and the outputs of the runs (see README.txt).
All computations use exact integer or rational arithmetic, except where floating point is mentioned. Floating point serves only to search (for uniformly descending sets, for the weights of certificates, for extremal sets) and for values that are given as decimals. Every statement about uniform descent, every certificate and every extremal set was then confirmed in exact arithmetic, as described below. The programs are among the ancillary files (see Data and code above), and the file names below refer to them.
Cycles of G G G by length (Table 4.1 ). For each length ℓ \ell ℓ and each least element m m m allowed by Theorem 4.1 (c), a depth-first search over paths through vertices larger than m m m , pruned by the fact that the lowest number reachable from z z z in k k k steps is ⌈ z / 2 k ⌉ \lceil z/2^k\rceil ⌈ z / 2 k ⌉ . The run for ℓ ≤ 30 \ell\le30 ℓ ≤ 30 takes about 20 seconds; for ℓ ≤ 21 \ell\le21 ℓ ≤ 21 the 4,723 cycles were also checked against Theorem 4.1 (c) and (d) in exact arithmetic.
Cycles of G G G with all elements at most N N N (Theorem 7.1). The numbers of such cycles are 947, 1,020, 878,612, 13,745,028 and 1,133,265,572 for $N = 100, 115, 117, 130, 160; the jump at N = 116 N = 116 N = 116 is the merger of the two nontrivial strongly connected components of the subgraph of G G G induced by [ 1 , N ] [1,N] [ 1 , N ] , of 54 and 20 vertices at N = 115 N = 115 N = 115 .
Short cycles (§ 6 ). A breadth-first search finds the shortest cycle through n n n inside [ 1 , 3 n ] [1,3n] [ 1 , 3 n ] for all but 7,403 of the n ≤ 10 5 n \le10^5 n ≤ 1 0 5 . For the 10,001 numbers n ∈ [ 9 ⋅ 10 4 , 10 5 ] n \in[9 \cdot10^4,10^5] n ∈ [ 9 ⋅ 1 0 4 , 1 0 5 ] there is no such cycle for 742 of them, and its length is 46, 54, 62 or 65 for 8,773 and at most 65 for 8,809 of them.
Subgraphs G ⟨ ∅ , B ⟩ G_{\langle\varnothing,B\rangle} G ⟨ ∅ , B ⟩ (Theorem 7.5). Reachable sets by depth-first search with a cap of 10 6 10^6 1 0 6 vertices; strongly connected components of the induced subgraphs by Tarjan’s algorithm and, for B = 2 N − 1 B = 2N - 1 B = 2 N − 1 , by intersecting the sets of vertices of [ 1 , 2 28 ] [1,2^{28}] [ 1 , 2 28 ] reachable from 15 and reaching 15 (52,719,985 vertices).
Primes (Theorem 7.14). Every orbit of n ≤ 10 7 n \le10^7 n ≤ 1 0 7 was followed until it fell below n n n or met one of the three cycles, with a deterministic Miller–Rabin test; the largest number reached is 106,780,274.
Barely divergent paths (Theorem 3.3(c)), Table 5.1 . For ( r , s ) = ( 2 , 1 ) (r,s) = (2,1) ( r , s ) = ( 2 , 1 ) the path from every y < 2000 y < 2000 y < 2000 was followed for 400 blocks with a hash set of visited numbers; repetitions occur exactly for y ≤ 36 y \le36 y ≤ 36 , y ∉ { 29 , 33 , 35 } y \notin\{29,33,35\} y ∈ / { 29 , 33 , 35 } , and for y ≥ 1993 y \ge1993 y ≥ 1993 the proof of Theorem 5.2 applies. The thresholds y 0 = C 1 / c y_0 = C_1/c y 0 = C 1 / c of the table were computed as in that proof, in floating point, by minimizing ∣ X log 3 − Y log 2 ∣ |X \log3 - Y \log2| ∣ X log 3 − Y log 2∣ over all q ≤ q 0 q \le q_0 q ≤ q 0 , 0 ≤ e < L 0 \le e < L 0 ≤ e < L and all starting positions in the pattern.
Effective up-frequencies (Table 5.2 and Table 6.2 ). Closed classes by reachability, and stationary distributions by Gaussian elimination over Q \mathbb{Q} Q for moduli up to 64 and in floating point for larger moduli. The two “straddling” sets of Table 5.2 were found by running over all 2 16 2^{16} 2 16 sets periodic modulo 16 and all closed classes of their residue graphs in floating point; every pair within 10 − 9 10^{-9} 1 0 − 9 of an optimum was then recomputed over Q \mathbb{Q} Q . Both optima, 39 / 112 39/112 39/112 and 23 / 80 23/80 23/80 , are attained only by these sets (straddle-exact.py). The “worst cycle” of Table 6.2 is the largest mean weight of a cycle when the residues in S S S have weight 1 and the others weight 0, by Karp’s algorithm with rational numbers.
Expanding cycles in integer arithmetic. Whether a cycle of a residue graph with a a a of its ℓ \ell ℓ vertices in S S S is expanding, 3 a > 2 ℓ 3^a > 2^\ell 3 a > 2 ℓ , can be tested with small integers. We have 971 / 1539 < log 3 2 < 665 / 1054 971/1539 < \log_3 2 < 665/1054 971/1539 < log 3 2 < 665/1054 and 665 ⋅ 1539 − 971 ⋅ 1054 = 1 665 \cdot1539 - 971 \cdot1054 = 1 665 ⋅ 1539 − 971 ⋅ 1054 = 1 , so no fraction with denominator at most 2592 lies strictly between these two fractions; hence, for ℓ ≤ 2592 \ell\le2592 ℓ ≤ 2592 , 3 a > 2 ℓ 3^a > 2^\ell 3 a > 2 ℓ holds if and only if 1539 a > 971 ℓ 1539a > 971\ell 1539 a > 971 ℓ . Give the weight 568 to every residue in S S S and the weight − 971 -971 − 971 to every other residue. A cycle then has weight 1539 a − 971 ℓ 1539a - 971\ell 1539 a − 971 ℓ , and if its length is at most 2592, this is positive exactly when the cycle is expanding. A closed walk of positive weight contains a simple cycle of positive weight, and the simple cycles of R k ( S ) \mathcal{R}_k(S) R k ( S ) have length at most 2 k 2^k 2 k . So for k ≤ 11 k \le11 k ≤ 11 the Bellman–Ford algorithm with these integer weights decides whether S S S is uniformly descending, and if it is not, it produces an expanding simple cycle.
Uniform descent (Table 5.3 ). For all sets periodic modulo 4, 8 and 16, a first pass in floating point: the maximum mean weight of a cycle of the residue graph by Karp’s algorithm, with weights log 3 2 \log\frac{3}{2} log 2 3 and − log 2 -\log2 − log 2 (unifdesc.c). The counts and the extremal sets of the table come from a second pass in exact arithmetic (unifdesc_exact.py): uniform descent with the integer weights above, and stationary distributions over Q \mathbb{Q} Q .
Smallest modifications (Table 6.2 ). Exact values by branch and bound (modsearch.c): find an expanding simple cycle with the integer weights above; a uniformly descending modification must change the step at one of its residues, and we branch on the first residue of the cycle that is changed. For removals this finishes up to k = 7 k = 7 k = 7 , in about a second for k = 7 k = 7 k = 7 . For arbitrary changes it finishes up to k = 6 k = 6 k = 6 , and for k = 7 k = 7 k = 7 it shows within a few seconds that no change of fewer than 8 residues is uniformly descending, so δ 7 = δ ‾ 7 = 8 / 128 \delta_7 = \overline{\delta}_7 = 8/128 δ 7 = δ 7 = 8/128 . For k ≤ 6 k \le6 k ≤ 6 a plain enumeration of all changes of fewer residues confirms the lower bounds (679,121 sets for k = 6 k = 6 k = 6 ; bruteforce.c). The same search with residues deleted from R k ( 2 N − 1 ) \mathcal{R}_k(2N - 1) R k ( 2 N − 1 ) instead of changed shows that for k ≤ 7 k \le7 k ≤ 7 no set of fewer than 2 k δ k 2^k\delta_k 2 k δ k residues, odd or even, meets every expanding cycle (Theorem 6.6). For removals with k = 8 k = 8 k = 8 the search for a removal of fewer than 12 residues did not finish within 15 minutes. Upper bounds for k = 8 , 9 , 10 k = 8, 9, 10 k = 8 , 9 , 10 by a randomized greedy choice in floating point (remove a random up-vertex of an expanding cycle until none is left, then try to put back the removed residues in random order), with 5000, 1200 and 1000 trials; the sets found are confirmed by their certificates. Lower bounds for k = 8 , 9 , 10 k = 8, 9, 10 k = 8 , 9 , 10 by a greedy packing of pairwise disjoint expanding simple cycles of length at most 2 k + 2 2k + 2 2 k + 2 (up to 22), of which there are 2,831, 12,481 and 44,980; the packings consist of 10, 14 and 23 cycles. The sets found are
R 2 = { 3 } , R 3 = { 3 , 7 } , R 4 = { 9 , 15 } , R 5 = { 7 , 19 , 25 , 31 } , R 6 = { 7 , 15 , 39 , 57 , 63 } , R_2 = \{3\},\quad R_3 = \{3,7\},\quad R_4 = \{9,15\},\quad R_5 = \{7,19,25,31\},\quad R_6 = \{7,15,39,57,63\}, R 2 = { 3 } , R 3 = { 3 , 7 } , R 4 = { 9 , 15 } , R 5 = { 7 , 19 , 25 , 31 } , R 6 = { 7 , 15 , 39 , 57 , 63 } ,
R 7 = { 9 , 27 , 47 , 55 , 95 , 111 , 121 , 127 } , R_7 = \{9,27,47,55,95,111,121,127\}, R 7 = { 9 , 27 , 47 , 55 , 95 , 111 , 121 , 127 } ,
R 8 = { 31 , 91 , 95 , 97 , 105 , 125 , 159 , 219 , 223 , 233 , 251 , 255 } , R_8 = \{31,91,95,97,105,125,159,219,223,233,251,255\}, R 8 = { 31 , 91 , 95 , 97 , 105 , 125 , 159 , 219 , 223 , 233 , 251 , 255 } ,
R 9 = { 31 , 63 , 91 , 125 , 143 , 159 , 207 , 219 , 223 , 233 , 287 , 297 , 311 , 347 , 353 , 415 , 457 , 463 , 489 , 503 , 507 , 511 } , R_9 = \{31,63,91,125,143,159,207,219,223,233,287,297,311,347,353,415,457,463,489,503,507,511\}, R 9 = { 31 , 63 , 91 , 125 , 143 , 159 , 207 , 219 , 223 , 233 , 287 , 297 , 311 , 347 , 353 , 415 , 457 , 463 , 489 , 503 , 507 , 511 } ,
R 10 = { 31 , 55 , 63 , 71 , 121 , 123 , 155 , 191 , 207 , 215 , 219 , 223 , 231 , 251 , 275 , 359 , 367 , 411 , 415 , 479 , 481 , 491 , 543 , 575 , 655 , 667 , 671 , 679 , 731 , 743 , 751 , 793 , 799 , 831 , 839 , 871 , 879 , 935 , 967 , 987 , 991 , 993 , 1019 , 1023 } . \begin{aligned}
R_{10} = \{&31,55,63,71,121,123,155,191,207,215,219,223,231,251,275,359,367,411,415,479,481,\\
&491,543,575,655,667,671,679,731,743,751,793,799,831,839,871,879,935,967,987,991,\\
&993,1019,1023\}.
\end{aligned} R 10 = { 31 , 55 , 63 , 71 , 121 , 123 , 155 , 191 , 207 , 215 , 219 , 223 , 231 , 251 , 275 , 359 , 367 , 411 , 415 , 479 , 481 , 491 , 543 , 575 , 655 , 667 , 671 , 679 , 731 , 743 , 751 , 793 , 799 , 831 , 839 , 871 , 879 , 935 , 967 , 987 , 991 , 993 , 1019 , 1023 } .
Certificates (Theorem 6.4 and Table 6.2 ). For each R k R_k R k , in floating point: the maximum mean cycle weight μ ∗ \mu^* μ ∗ by Karp’s algorithm, the potential ψ \psi ψ of the proof of Theorem 5.11 for μ = μ ∗ / 2 \mu= \mu^*/2 μ = μ ∗ /2 (and a few other fractions of μ ∗ \mu^* μ ∗ ), integer weights by scaling e ψ e^\psi e ψ by 10 3 10^3 1 0 3 to 10 5 10^5 1 0 5 and rounding. Then, exactly: a check of all edge inequalities with rational numbers, which gives θ \theta θ , and a check that every x x x with 2 ≤ x ≤ B 2 \le x \le B 2 ≤ x ≤ B falls below itself (by induction, then every such x x x reaches 1). The integer weights are among the ancillary files, together with a separate program that repeats the exact part (check_certificate.py). The largest stopping times in these checks are between 2 and 20. The hand-made weights of Table 6.1 were found by rounding and then adjusting by hand; the program finds slightly better ones (θ = 0.9717 \theta= 0.9717 θ = 0.9717 , B = 196 B = 196 B = 196 ).
The chain of 1 (Theorem 6.2). The 340 elements of Γ 1 \Gamma_1 Γ 1 below 10 60 10^{60} 1 0 60 , of which 173 are even; below 10 3 10^3 1 0 3 , 10 6 10^6 1 0 6 , 10 12 10^{12} 1 0 12 and 10 30 10^{30} 1 0 30 there are 8, 18, 36 and 82 even ones.
The heuristic (Theorem 6.3). For each o o o on a grid of step 1.25 ⋅ 10 − 4 1.25 \cdot10^{-4} 1.25 ⋅ 1 0 − 4 in ( 1 / 2 , 3 / 4 ) (1/2,3/4) ( 1/2 , 3/4 ) , the smallest κ \kappa κ with a nonnegative first exponent by bisection, and the minimum of κ / ( ( o + κ ) log 3 − log 2 ) \kappa/((o+\kappa)\log3-\log2) κ / (( o + κ ) log 3 − log 2 ) over the grid.
References