1.1 Statement of main result

Let $\mathbb {N} := \{0,1,2,\dots \}$ denote the natural numbers, so that $\mathbb {N}+1 = \{1,2,3,\dots \}$ are the positive integers. The Collatz map ${\operatorname {Col}} \colon \mathbb {N}+1 \to \mathbb {N}+1$ is defined by setting ${\operatorname {Col}}(N) := 3N+1$ when N is odd and ${\operatorname {Col}}(N) := N/2$ when N is even. For any $N \in \mathbb {N}+1$ , let ${\operatorname {Col}}_{\min }(N) := \min {\operatorname {Col}}^{\mathbb {N}}(N) = \inf _{n \in \mathbb {N}} {\operatorname {Col}}^n(N)$ denote the minimal element of the Collatz orbit ${\operatorname {Col}}^{\mathbb {N}}(N) := \{ N, {\operatorname {Col}}(N), {\operatorname {Col}}^2(N), \dots \}$ . We have the infamous Collatz conjecture (also known as the $3x+1$ conjecture):

We refer the reader to [Reference Lagarias14], [Reference Chamberland6] for extensive surveys and historical discussion of this conjecture.

While the full resolution of Conjecture 1.1 remains well beyond the reach of current methods, some partial results are known. Numerical computation has verified ${\operatorname {Col}}_{\min }(N)=1$ for all $N \leq 5.78 \times 10^{18}$ [Reference Oliveira e Silva17], for all $N \leq 10^{20}$ [Reference Roosendaal18], and most recently for all $N \leq 2^{68} \approx 2.95 \times 10^{20}$ [Reference Barina3], while Krasikov and Lagarias [Reference Krasikov and Lagarias13] showed that

$$ \begin{align*}\# \{ N \in \mathbb{N}+1 \cap [1,x]: {\operatorname{Col}}_{\min}(N) = 1 \} \gg x^{0.84}\end{align*} $$

for all sufficiently large x, where $\# E$ denotes the cardinality of a finite set E, and our conventions for asymptotic notation are set out in Section 2. In this paper, we will focus on a different type of partial result, in which one establishes upper bounds on the minimal orbit value ${\operatorname {Col}}_{\min }(N)$ for ‘almost all’ $N \in \mathbb {N}+1$ . For technical reasons, the notion of ‘almost all’ that we will use here is based on logarithmic density, which has better approximate multiplicative invariance properties than the more familiar notion of natural density (see [Reference Tao20] for a related phenomenon in a more number-theoretic context). Due to the highly probabilistic nature of the arguments in this paper, we will define logarithmic density using the language of probability theory.

In Terras [Reference Terras21] (and independently Everett [Reference Everett8]), it was shown that ${\operatorname {Col}}_{\min }(N) < N$ for almost all N. This was improved by Allouche [Reference Allouche1] to ${\operatorname {Col}}_{\min }(N) < N^\theta $ for almost all N, and any fixed constant $\theta>\frac {3}{2} - \frac {\log 3}{\log 2} \approx 0.869$ ; the range of $\theta $ was later extended to $\theta> \frac {\log 3}{\log 4} \approx 0.7924$ by Korec [Reference Korec9]. (Indeed, in these results one can use natural density instead of logarithmic density to define ‘almost all’.) It is tempting to try to iterate these results to lower the value of $\theta $ further. However, one runs into the difficulty that the uniform (or logarithmic) measure does not enjoy any invariance properties with respect to the Collatz map: in particular, even if it is true that ${\operatorname {Col}}_{\min }(N) < x^\theta $ for almost all $N \in [1,x]$ , and ${\operatorname {Col}}_{\min }(N') \leq x^{\theta ^2}$ for almost all $N' \in [1, x^\theta ]$ , the two claims cannot be immediately concatenated to imply that ${\operatorname {Col}}_{\min }(N) \leq x^{\theta ^2}$ for almost all $N \in [1,x]$ , since the Collatz iteration may send almost all of $[1,x]$ into a very sparse subset of $[1,x^\theta ]$ , and in particular into the exceptional set of the latter claim ${\operatorname {Col}}_{\min }(N') \leq x^{\theta ^2}$ .

Nevertheless, in this paper, we show that it is possible to locate an alternate probability measure (or, more precisely, a family of probability measures) on the natural numbers with enough invariance properties that an iterative argument does become fruitful. More precisely, the main result of this paper is the following improvement of these ‘almost all’ results.

Thus, for instance, one has ${\operatorname {Col}}_{\min }(N) < \log \log \log \log N$ for almost all N.

1.2 Syracuse formulation

We now discuss the methods of proof of Theorem 1.3. It is convenient to replace the Collatz map ${\operatorname {Col}} \colon \mathbb {N}+1 \to \mathbb {N}+1$ with a slightly more tractable acceleration $N \mapsto {\operatorname {Col}}^{f(N)}(N)$ of that map. One common instance of such an acceleration in the literature is the map ${\operatorname {Col}}_2 \colon \mathbb {N}+1 \to \mathbb {N}+1$ , defined by setting ${\operatorname {Col}}_2(N) := {\operatorname {Col}}^2(N) = \frac {3N+1}{2}$ when N is odd and ${\operatorname {Col}}_2(N) := \frac {N}{2}$ when N is even. Each iterate of the map ${\operatorname {Col}}_2$ performs exactly one division by $2$ , and for this reason ${\operatorname {Col}}_2$ is a particularly convenient choice of map when performing ‘ $2$ -adic’ analysis of the Collatz iteration. It is easy to see that ${\operatorname {Col}}_{\min }(N) = ({\operatorname {Col}}_2)_{\min }(N)$ for all $N \in \mathbb {N}+1$ , so all the results in this paper concerning ${\operatorname {Col}}$ may be equivalently reformulated using ${\operatorname {Col}}_2$ . The triple iterate ${\operatorname {Col}}^3$ was also recently proposed as an acceleration in [Reference Carletti and Fanelli5]. However, the methods in this paper will rely instead on ‘ $3$ -adic’ analysis, and it will be preferable to use an acceleration of the Collatz map (first appearing to the author’s knowledge in [Reference Crandall7]), which performs exactly one multiplication by $3$ per iteration. More precisely, let $2\mathbb {N}+1 = \{1,3,5,\dots \}$ denote the odd natural numbers, and define the Syracuse map ${\operatorname {Syr}} \colon 2\mathbb {N}+1 \to 2\mathbb {N}+1$ (OEIS A075677) to be the largest odd number dividing $3N+1$ ; thus, for instance,

$$ \begin{align*}{\operatorname{Syr}}(1)=1; \quad {\operatorname{Syr}}(3) = 5; \quad {\operatorname{Syr}}(5) = 1; \quad {\operatorname{Syr}}(7) = 11.\end{align*} $$

Equivalently, one can write

(1.1) $$ \begin{align} {\operatorname{Syr}}(N) = {\operatorname{Col}}^{\nu_2(3N+1)+1}(N) = {\operatorname{Aff}}_{\nu_2(3N+1)}(N), \end{align} $$

where for each positive integer $a \in \mathbb {N}+1$ , ${\operatorname {Aff}}_a\colon \mathbb {R} \to \mathbb {R}$ denotes the affine map

$$ \begin{align*}{\operatorname{Aff}}_a(x) := \frac{3x+1}{2^a}\end{align*} $$

and for each integer M and each prime p, the p-valuation $\nu _p(M)$ of M is defined as the largest natural number a such that $p^a$ divides M (with the convention $\nu _p(0) = +\infty $ ). (Note that $\nu _2(3N+1)$ is always a positive integer when N is odd.) For any $N \in 2\mathbb {N}+1$ , let ${\operatorname {Syr}}_{\min }(N) := \min {\operatorname {Syr}}^{\mathbb {N}}(N)$ be the minimal element of the Syracuse orbit

$$ \begin{align*}{\operatorname{Syr}}^{\mathbb{N}}(N) := \{ N, {\operatorname{Syr}}(N), {\operatorname{Syr}}^2(N), \dots\}.\end{align*} $$

This Syracuse orbit ${\operatorname {Syr}}^{\mathbb {N}}(N)$ is nothing more than the odd elements of the corresponding Collatz orbit ${\operatorname {Col}}^{\mathbb {N}}(N)$ , and from this observation it is easy to verify the identity

(1.2) $$ \begin{align} {\operatorname{Col}}_{\min}(N) = {\operatorname{Syr}}_{\min}( N / 2^{\nu_2(N)} ) \end{align} $$

for any $N \in \mathbb {N}+1$ . Thus, the Collatz conjecture can be equivalently rephrased as

We may similarly reformulate Theorem 1.3 in terms of the Syracuse map. We say that a property $P(N)$ holds for almost all $N \in 2\mathbb {N}+1$ if

$$ \begin{align*}\lim_{x \to \infty} \mathbb{P}( P(\mathbf{Log}( 2\mathbb{N}+1 \cap [1,x] ) ) )= 1,\end{align*} $$

or equivalently if $P(N)$ holds for a set of odd natural numbers of logarithmic density $1/2$ . Theorem 1.3 is then equivalent to

Indeed, if Theorem 1.6 holds and $f\colon \mathbb {N} +1 \to \mathbb {R}$ is such that $\lim _{N \to \infty } f(N) = +\infty $ , then from equation (1.2), we see that for any $a \in \mathbb {N}$ , the set of $N \in \mathbb {N}+1$ with $\nu _2(N) = a$ and ${\operatorname {Col}}_{\min }( N ) = {\operatorname {Syr}}_{\min }(N/2^a) < f(N)$ has logarithmic density $2^{-a}$ . Summing over any finite range $0 \leq a \leq a_0$ , we obtain a set of logarithmic density $1 - 2^{-a_0}$ on which the claim ${\operatorname {Col}}_{\min }(N) < f(N)$ holds, and on sending $a_0$ to infinity one obtains Theorem 1.3. The converse implication (which we will not need) is also straightforward and left to the reader.

The iterates ${\operatorname {Syr}}^n$ of the Syracuse map can be described explicitly as follows. For any finite tuple $\vec a = (a_1,\dots ,a_n) \in (\mathbb {N}+1)^n$ of positive integers, we define the composition ${\operatorname {Aff}}_{\vec a} = {\operatorname {Aff}}_{a_1,\dots ,a_n}\colon \mathbb {R} \to \mathbb {R}$ to be the affine map

$$ \begin{align*}{\operatorname{Aff}}_{a_1,\dots,a_n}(x) := {\operatorname{Aff}}_{a_n}( {\operatorname{Aff}}_{a_{n-1}}( \dots ({\operatorname{Aff}}_{a_1}(x)) \dots )).\end{align*} $$

A brief calculation shows that

(1.3) $$ \begin{align} {\operatorname{Aff}}_{a_1,\dots,a_n}(x) = 3^n 2^{-|\vec a|} x + F_n(\vec a), \end{align} $$

where the size $|\vec a|$ of a tuple $\vec a$ is defined as

(1.4) $$ \begin{align} |\vec a| := a_1 + \dots + a_n, \end{align} $$

and we define the n-Syracuse offset map $F_n\colon (\mathbb {N}+1)^n \to \mathbb {Z}[\frac {1}{2}]$ to be the function

(1.5) $$ \begin{align} F_n(\vec a) &:= \sum_{m=1}^n 3^{n-m} 2^{-a_{[m,n]}} \nonumber\\ &= 3^{n-1} 2^{-a_{[1,n]}} + 3^{n-2} 2^{-a_{[2,n]}} + \dots + 3^1 2^{-a_{[n-1,n]}} + 2^{-a_n}, \end{align} $$

where we adopt the summation notation

(1.6) $$ \begin{align} a_{[j,k]} := \sum_{i=j}^k a_i \end{align} $$

for any $1 \leq j \leq k \leq n$ ; thus, for instance, $|\vec a| = a_{[1,n]}$ . The n-Syracuse offset map $F_n$ takes values in the ring $\mathbb {Z}[\frac {1}{2}] := \{ \frac {M}{2^a}: M \in \mathbb {Z}, a \in \mathbb {N} \}$ formed by adjoining $\frac {1}{2}$ to the integers.

By iterating equation (1.1) and then using equation (1.3), we conclude that

(1.7) $$ \begin{align} {\operatorname{Syr}}^n(N) = {\operatorname{Aff}}_{\vec a^{(n)}(N)}(N) = 3^n 2^{-|\vec a^{(n)}(N)|} N + F_n(\vec a^{(n)}(N)) \end{align} $$

for any $N \in 2\mathbb {N}+1$ and $n \in \mathbb {N}$ , where we define n-Syracuse valuation $\vec a^{(n)}(N) \in (\mathbb {N}+1)^n$ of N to be the tuple

(1.8) $$ \begin{align} \vec a^{(n)}(N) := \left(\nu_2(3N+1), \nu_2(3{\operatorname{Syr}}(N)+1), \dots, \nu_2(3{\operatorname{Syr}}^{n-1}(N)+1)\right). \end{align} $$

This tuple is referred to as the n-path of N in [Reference Kontorovich and Sinai12].

The identity in equation (1.7) asserts that ${\operatorname {Syr}}^n(N)$ is the image of N under a certain affine map ${\operatorname {Aff}}_{\vec a^{(n)}(N)}$ that is determined by the n-Syracuse valuation $\vec a^{(n)}(N)$ of N. This suggests that in order to understand the behaviour of the iterates ${\operatorname {Syr}}^n(N)$ of a typical large number N, one needs to understand the behaviour of n-Syracuse valuation $\vec a^{(n)}(N)$ , as well as the n-Syracuse offset map $F_n$ . For the former, we can gain heuristic insight by observing that for a positive integer a, the set of odd natural numbers $N \in 2\mathbb {N}+1$ with $\nu _2(3N+1)=a$ has (logarithmic) relative density $2^{-a}$ . To model this probabilistically, we introduce the following probability distribution:

In this paper, the only geometric random variables we will actually use are $\mathbf {Geom}(2)$ and $\mathbf {Geom}(4)$ .

We will then be guided by the following heuristic:

We can make this heuristic precise as follows. Given two random variables $\mathbf {X},\mathbf {Y}$ taking values in the same discrete space R, we define the total variation $d_{\operatorname {TV}}(\mathbf {X},\mathbf {Y})$ between the two variables to be the total variation of the difference in the probability measures; thus

(1.9) $$ \begin{align} d_{\operatorname{TV}}(\mathbf{X},\mathbf{Y}) := \sum_{r \in R} |\mathbb{P}( \mathbf{X} = r ) - \mathbb{P}( \mathbf{Y} = r )|. \end{align} $$

Note that

(1.10) $$ \begin{align} \sup_{E \subset R} |\mathbb{P}(\mathbf{X} \in E) - \mathbb{P}(\mathbf{Y} \in E)| \leq d_{\operatorname{TV}}(\mathbf{X},\mathbf{Y}) \leq 2 \sup_{E \subset R} |\mathbb{P}(\mathbf{X} \in E) - \mathbb{P}(\mathbf{Y} \in E)|. \end{align} $$

For any finite non-empty set R, let $\mathbf {Unif}(R)$ denote a uniformly distributed random variable on R. Then we have the following result, proven in Section 4:

Informally, this proposition asserts that Heuristic 1.8 is justified whenever N is expected to be uniformly distributed modulo $2^{n'}$ for some $n'$ slightly larger than $2n$ . The hypothesis in equation (1.11) is somewhat stronger than what is actually needed for the conclusion in equation (1.12) to hold, but this formulation of the implication will suffice for our applications. We will apply this proposition in Section 5, not to the original logarithmic distribution $\mathbf {Log}(2\mathbb {N}+1 \cap [1,x])$ (which has too heavy a tail near $1$ for the hypothesis in equation (1.11) to apply), but to the variant $\mathbf {Log}( 2\mathbb {N}+1 \cap [y,y^\alpha ])$ for some large y and some $\alpha>1$ close to $1$ .

In practice, the offset $F_n(\vec a)$ is fairly small (in an Archimedean sense) when n is not too large; indeed, from equation (1.5), we have

(1.13) $$ \begin{align} 0 \leq F_n(\vec a) \leq 3^n 2^{-a_n} \leq 3^n \end{align} $$

for any $n \in \mathbb {N}$ and $\vec a \in (\mathbb {N}+1)^n$ . For large N, we then conclude from equation (1.7) that we have the heuristic approximation

$$ \begin{align*}{\operatorname{Syr}}^n(N) \approx 3^n 2^{-|\vec a^{(n)}(N)|} N\end{align*} $$

and hence by Heuristic 1.8, we expect ${\operatorname {Syr}}^n(N)$ to behave statistically like

(1.14) $$ \begin{align} {\operatorname{Syr}}^n(N) \approx 3^n 2^{-|\mathbf{Geom}(2)^n|} N = N \exp( n \log 3 - |\mathbf{Geom}(2)^n| \log 2 ) \end{align} $$

if n is much smaller than $\log N$ . One can view the sequence $n \mapsto n \log 3 - |\mathbf {Geom}(2)^n| \log 2$ as a simple random walk on $\mathbb {R}$ with negative drift $\log 3 - 2 \log 2 = \log \frac {3}{4}$ . From the law of large numbers, we expect to have

(1.15) $$ \begin{align} |\mathbf{Geom}(2)^n| \approx 2n \end{align} $$

most of the time; thus we are led to the heuristic prediction

(1.16) $$ \begin{align} {\operatorname{Syr}}^n(N) \approx (3/4)^n N \end{align} $$

for typical N; indeed, from the central limit theorem or the Chernoff bound, we in fact expect the refinement

(1.17) $$ \begin{align} {\operatorname{Syr}}^n(N) = \exp( O(n^{1/2}) ) (3/4)^n N \end{align} $$

for ‘typical’ N. In particular, we expect the Syracuse orbit $N, {\operatorname {Syr}}(N), {\operatorname {Syr}}^2(N), \dots $ to decay geometrically in time for typical N, which underlies the usual heuristic argument supporting the truth of Conjecture 1.1; see [Reference Lagarias and Weiss16], [Reference Kontorovich and Lagarias10] for further discussion. We remark that the multiplicative inaccuracy of $\exp ( O(n^{1/2}) )$ in equation (1.17) is the main reason why we work with logarithmic density instead of natural density in this paper (see also [Reference Kontorovich and Miller11], [Reference Lagarias and Soundararajan15] for a closely related ‘Benford’s law’ phenomenon).

1.3 Reduction to a stabilisation property for first passage locations

Roughly speaking, Proposition 1.9 lets one obtain good control on the Syracuse iterates ${\operatorname {Syr}}^n(N)$ for almost all N and for times n up to $c \log N$ for a small absolute constant c. This already can be used in conjunction with a rigorous version of equation (1.16) or (1.17) to recover the previously mentioned result ${\operatorname {Syr}}_{\min }(N) \leq N^{1-c}$ for almost all N and some absolute constant $c>0$ ; see Section 5 for details. In the language of evolutionary partial differential equations, these types of results can be viewed as analogous to ‘almost sure’ local wellposedness results, in which one has good short-time control on the evolution for almost all choices of initial condition N.

In this analogy, Theorem 1.6 then corresponds to an ‘almost sure’ almost global wellposedness result, where one needs to control the solution for times so large that the evolution gets arbitrary close to the bounded state $N=O(1)$ . To bootstrap from almost sure local wellposedness to almost sure almost global wellposedness, we were inspired by the work of Bourgain [Reference Bourgain4], who demonstrated an almost sure global wellposedness result for a certain nonlinear Schrödinger equation by combining local wellposedness theory with a construction of an invariant probability measure for the dynamics. Roughly speaking, the point was that the invariance of the measure would almost surely keep the solution in a ‘bounded’ region of the state space for arbitrarily long times, allowing one to iterate the local wellposedness theory indefinitely.

In our context, we do not expect to have any useful invariant probability measures for the dynamics due to the geometric decay in equation (1.16) (and indeed Conjecture 1.5 would imply that the only invariant probability measure is the Dirac measure on $\{1\}$ ). Instead, we can construct a family of probability measures $\nu _x$ that are approximately transported to each other by certain iterations of the Syracuse map (by a variable amount of time). More precisely, given a threshold $x \geq 1$ and an odd natural number $N \in 2\mathbb {N}+1$ , define the first passage time

$$ \begin{align*}T_x(N) := \inf \{ n \in \mathbb{N}: {\operatorname{Syr}}^n(N) \leq x \},\end{align*} $$

with the convention that $T_x(N) := +\infty $ if ${\operatorname {Syr}}^n(N)> x$ for all n. (Of course, if Conjecture 1.5 were true, this latter possibility could not occur, but we will not be assuming this conjecture in our arguments.) We then define the first passage location

$$ \begin{align*}{\operatorname{Pass}}_x(N) := {\operatorname{Syr}}^{T_x(N)}(N)\end{align*} $$

with the (somewhat arbitrary and artificial) convention that ${\operatorname {Syr}}^\infty (N) := 1$ ; thus ${\operatorname {Pass}}_x(N)$ is the first location of the Syracuse orbit ${\operatorname {Syr}}^{\mathbb {N}}(N)$ that falls inside $[1,x]$ , or $1$ if no such location exists; if we ignore the latter possibility, then ${\operatorname {Pass}}_x$ can be viewed as a further acceleration of the Collatz and Syracuse maps. We will also need a constant $\alpha> 1$ sufficiently close to one. The precise choice of this parameter is not critical, but for sake of concreteness we will set

(1.18) $$ \begin{align} \alpha := 1.001. \end{align} $$

The key proposition is then

Informally, this theorem asserts that the Syracuse orbits of $ \mathbf {N}_{x^\alpha } $ and $ \mathbf {N}_{x^{\alpha ^2}}$ are almost indistinguishable from each other once they pass x, as long as one synchronises the orbits so that they simultaneously pass x for the first time. In Section 3, we shall see how Theorem 1.6 (and hence Theorem 1.3) follows from Proposition 1.11; basically the point is that equations (1.19) and (1.20) imply that the first passage map ${\operatorname {Pass}}_x$ approximately maps the distribution $\nu _{x^\alpha }$ of ${\operatorname {Pass}}_{x^{\alpha }}( \mathbf {N}_{x^{\alpha ^2}} )$ to the distribution $\nu _x$ of ${\operatorname {Pass}}_{x}( \mathbf {N}_{x^{\alpha }} )$ , and one can then iterate this to map almost all of the probabilistic mass of $\mathbf {N}_y$ for large y to be arbitrarily close to the bounded state $N=O(1)$ . The implication is very general and does not use any particular properties of the Syracuse map beyond equations (1.19) and (1.20).

The estimate in equation (1.19) is easy to establish; it is equation (1.20) that is the most important and difficult conclusion of Proposition 1.11. We remark that the bound of $O(\log ^{-c} x)$ in equation (1.20) is stronger than is needed for this argument; any bound of the form $O((\log \log x)^{-1-c})$ would have sufficed. Conversely, it may be possible to improve the bound in equation (1.20) further, perhaps all the way to $x^{-c}$ .

1.4 Fine-scale mixing of Syracuse random variables

It remains to establish Proposition 1.11. Since the constant $\alpha $ in equation (1.18) is close to $1$ , this proposition falls under the regime of a (refined) ‘local wellposedness’ result, since from the heuristic in equation (1.16) (or equation (1.17)), we expect the first passage time $T_x(\mathbf {N}_y)$ to be comparable to a small multiple of $\log \mathbf {N}_y$ . Inspecting the iteration formula in equation (1.7), the behaviour of the n-Syracuse valuation $\vec a^{(n)}(\mathbf {N}_y)$ for such times n is then well understood thanks to Proposition 1.9; the main remaining difficulty is to understand the behaviour of the n-Syracuse offset map $F_n\colon (\mathbb {N}+1)^n \to \mathbb {Z}[\frac {1}{2}]$ , and more specifically to analyse the distribution of the random variable $F_n(\mathbf {Geom}(2)^n) \bmod 3^k$ for various $n,k$ , where by abuse of notation we use $x \mapsto x \bmod 3^k$ to denote the unique ring homomorphism from $\mathbb {Z}[\frac {1}{2}]$ to $\mathbb {Z}/3^k \mathbb {Z}$ (which in particular maps $\frac {1}{2}$ to the inverse $\frac {3^k+1}{2} \bmod 3^k$ of $2 \bmod 3^k$ ). Indeed, from equation (1.7), one has

(1.21) $$ \begin{align} {\operatorname{Syr}}^n(N) = F_n(\vec a^{(n)}(N)) \bmod 3^k \end{align} $$

whenever $0 \leq k \leq n$ and $N \in 2\mathbb {N}+1$ . Thus, if $n, \mathbf {N}, n', c_0$ obey the hypotheses of Proposition 1.9, one has

$$ \begin{align*}d_{\operatorname{TV}}( {\operatorname{Syr}}^n(\mathbf{N}) \bmod 3^k, F_n( \mathbf{Geom}(2)^n ) \bmod 3^k ) \ll 2^{-c_1 n}\end{align*} $$

for all $0 \leq k \leq n$ . If we now define the Syracuse random variables $\mathbf {Syrac}(\mathbb {Z}/3^n\mathbb {Z})$ for $n \in \mathbb {N}$ to be random variables on the cyclic group $\mathbb {Z}/3^n\mathbb {Z}$ with the distribution

(1.22) $$ \begin{align} \mathbf{Syrac}(\mathbb{Z}/3^n\mathbb{Z}) \equiv F_n( \mathbf{Geom}(2)^n ) \bmod 3^n \end{align} $$

then from equation (1.5), we see that

(1.23) $$ \begin{align} \mathbf{Syrac}(\mathbb{Z}/3^n\mathbb{Z}) \bmod 3^k \equiv \mathbf{Syrac}(\mathbb{Z}/3^k\mathbb{Z}) \end{align} $$

whenever $k \leq n$ , and thus

$$ \begin{align*}d_{\operatorname{TV}}( {\operatorname{Syr}}^n(\mathbf{N}) \bmod 3^k, \mathbf{Syrac}(\mathbb{Z}/3^k\mathbb{Z}) ) \ll 2^{-c_1 n}.\end{align*} $$

We thus see that the $3$ -adic distribution of the Syracuse orbit ${\operatorname {Syr}}^{\mathbb {N}}(\mathbf {N})$ is controlled (initially, at least) by the random variables $\mathbf {Syrac}(\mathbb {Z}/3^n\mathbb {Z})$ . The distribution of these random variables can be computed explicitly for any given n via the following recursive formula:

Thus, for instance, we trivially have $\mathbf {Syrac}(\mathbb {Z}/3^0\mathbb {Z})$ takes the value $0 \bmod 1$ with probability $1$ ; then by the above lemma, $\mathbf {Syrac}(\mathbb {Z}/3\mathbb {Z})$ takes the values $0,1,2 \bmod 3$ with probabilities $0, 1/3, 2/3$ respectively; another application of the above lemma then reveals that $\mathbf {Syrac}(\mathbb {Z}/3^2\mathbb {Z})$ takes the values $0,1,\dots ,8 \bmod 9$ with probabilities

$$ \begin{align*}0, \frac{8}{63}, \frac{16}{63}, 0, \frac{11}{63}, \frac{4}{63}, 0, \frac{2}{63}, \frac{22}{63}\end{align*} $$

respectively; and so forth. More generally, one can numerically compute the distribution of $\mathbf {Syrac}(\mathbb {Z}/3^n\mathbb {Z})$ exactly for small values of n, although the time and space required to do so increases exponentially with n.

While the Syracuse random variables $\mathbf {Syrac}(\mathbb {Z}/3^n\mathbb {Z})$ fail to be uniformly distributed on $\mathbb {Z}/3^n \mathbb {Z}$ , we can show that they do approach uniform distribution $n \to \infty $ at fine scales (as measured in a $3$ -adic sense), and this turns out to be the key ingredient needed to establish Proposition 1.11. More precisely, we will show

Informally, the above proposition asserts that the Syracuse random variable $\mathbf {Syrac}(\mathbb {Z}/3^n\mathbb {Z})$ is approximately uniformly distributed in ‘fine-scale’ or ‘high-frequency’ cosets $Y + 3^m\mathbb {Z}/3^n\mathbb {Z}$ , after conditioning to the event $\mathbf {Syrac}(\mathbb {Z}/3^n\mathbb {Z}) = Y \bmod 3^m$ . Indeed, one could write the left-hand side of equation (1.26) if desired as

$$ \begin{align*}d_{{\operatorname{TV}}}( \mathbf{Syrac}(\mathbb{Z}/3^n\mathbb{Z}), \mathbf{Syrac}(\mathbb{Z}/3^n\mathbb{Z}) + \mathbf{Unif}( 3^m\mathbb{Z}/3^n\mathbb{Z}) )\end{align*} $$

where the random variables $\mathbf {Syrac}(\mathbb {Z}/3^n\mathbb {Z}), \mathbf {Unif}( 3^m\mathbb {Z}/3^n\mathbb {Z})$ are understood to be independent. In Section 5, we show how Proposition 1.11 (and hence Theorem 1.3) follows from Proposition 1.14 and Proposition 1.9.

To prove Proposition 1.14, we use a partial convolution structure present in the n-Syracuse offset map, together with Plancherel’s theorem, to reduce matters to establishing a superpolynomial decay bound for the characteristic function (or Fourier coefficients) of a Syracuse random variable $\mathbf {Syrac}(\mathbb {Z}/3^n\mathbb {Z})$ . More precisely, in Section 6, we derive Proposition 1.14 from

A key point here is that the implied constant in equation (1.28) is uniform in the parameters $n \geq 1$ and $\xi \in \mathbb {Z}/3^n\mathbb {Z}$ (assuming of course that $\xi $ is not divisible by $3$ ), although as indicated, we permit this constant to depend on A.

The remaining task is to establish Proposition 1.17. This turns out to be the most difficult step in the argument, and is carried out in Section 7. From equations (1.5) and (1.22) and reversing the order of the random variables $\mathbf {a}_1,\dots ,\mathbf {a}_n$ (cf. equation (1.24)), we can describe the distribution of the Syracuse random variable by the formula

(1.29) $$ \begin{align} \mathbf{Syrac}(\mathbb{Z}/3^n\mathbb{Z}) \equiv 2^{-\mathbf{a}_1} + 3^1 2^{-\mathbf{a}_{[1,2]}} + \dots + 3^{n-1} 2^{-\mathbf{a}_{[1,n]}} \bmod 3^n, \end{align} $$

with $(\mathbf {a}_1,\dots ,\mathbf {a}_n) \equiv \mathbf {Geom}(2)^n$ ; this also follows from equation (1.25). If this random variable $\mathbf {Syrac}(\mathbb {Z}/3^n\mathbb {Z})$ was the sum of independent random variables, then the characteristic function of $\mathbf {Syrac}(\mathbb {Z}/3^n\mathbb {Z})$ would factor as something like a Riesz product of cosines, and its estimation would be straightforward. Unfortunately, the expression in equation (1.29) does not obviously resolve into such a sum of independent random variables; however, by grouping adjacent terms $3^{2j-2} 2^{-\mathbf {a}_{[1,2j-1]}}, 3^{2j-1} 2^{-\mathbf {a}_{[1,2j]}}$ in equation (1.29) into pairs, one can at least obtain a decomposition into the sum of independent expressions once one conditions on the sums $\mathbf {b}_j := \mathbf {a}_{2j-1}+\mathbf {a}_{2j}$ (which are iid copies of a Pascal distribution $\mathbf {Pascal}$ ). This lets one express the characteristic functions as an average of products of cosines (times a phase), where the average is over trajectories of a certain random walk $\mathbf {v}_1, \mathbf {v}_{[1,2]}, \mathbf {v}_{[1,3]},\dots $ in $\mathbb {Z}^2$ with increments in the first quadrant that we call a two-dimensional renewal process. If we color certain elements of $\mathbb {Z}^2$ ‘white’ when the associated cosines are small, and ‘black’ otherwise, then the problem boils down to ensuring that this renewal process encounters a reasonably large number of white points (see Figure 3 in Section 7).

From some elementary number theory, we will be able to describe the black regions of $\mathbb {Z}^2$ as a union of ‘triangles’ $\Delta $ that are well separated from each other; again, see Figure 3. As a consequence, whenever the renewal process passes through a black triangle, it will very likely also pass through at least one white point after it exits the triangle. This argument is adequate so long as the triangles are not too large in size; however, for very large triangles, it does not produce a sufficient number of white points along the renewal process. However, it turns out that large triangles tend to be fairly well separated from each other (at least in the neighbourhood of even larger triangles), and this geometric observation allows one to close the argument.

As with Proposition 1.14, it is possible that the bound in Proposition 1.17 could be improved, perhaps to as far as $O(\exp (-cn))$ for some $c>0$ . However, we will not need or pursue such a bound here.

Proof. It is clear from equation (1.7) that ${\operatorname {Aff}}_{\vec a^{(n)}(N)} \in 2\mathbb {N}+1$ . It remains to prove uniqueness. The claim is easy for $n=0$ , so suppose inductively that $n \geq 1$ and that uniqueness has already been established for $n-1$ . Suppose that we have found a tuple $\vec a \in (\mathbb {N}+1)^n$ for which ${\operatorname {Aff}}_{\vec a}(N)$ is an odd integer. Then

$$ \begin{align*}{\operatorname{Aff}}_{\vec a}(N) = {\operatorname{Aff}}_{a_n}( {\operatorname{Aff}}_{a_1,\dots,a_{n-1}}(N) ) = \frac{3{\operatorname{Aff}}_{a_1,\dots,a_{n-1}}(N)+1}{2^{a_n}}\end{align*} $$

and thus

(2.1) $$ \begin{align} 2^{a_n} {\operatorname{Aff}}_{\vec a}(N) =3{\operatorname{Aff}}_{a_1,\dots,a_{n-1}}(N)+1. \end{align} $$

This implies that $3{\operatorname {Aff}}_{a_1,\dots ,a_{n-1}}(N)$ is an odd natural number. But from equation (1.3), ${\operatorname {Aff}}_{a_1,\dots ,a_{n-1}}(N)$ also lies in $\mathbb {Z}[\frac {1}{2}]$ . The only way these claims can both be true is if ${\operatorname {Aff}}_{a_1,\dots ,a_{n-1}}(N)$ is also an odd natural number, and then by induction $(a_1,\dots ,a_{n-1}) = \vec a^{(n-1)}(N)$ , which by equation (1.7) implies that

$$ \begin{align*}{\operatorname{Aff}}_{a_1,\dots,a_{n-1}}(N) = {\operatorname{Syr}}^{n-1}(N).\end{align*} $$

Inserting this into equation (2.1) and using the fact that ${\operatorname {Aff}}_{\vec a}(N)$ is odd, we obtain

$$ \begin{align*}a_n = \nu_2( 3{\operatorname{Syr}}^{N-1}(N) + 1 ) \end{align*} $$

and hence by equation (1.8), we have $\vec a = \vec a^{(n)}$ as required.

Lemma 2.2 (Chernoff type bound(

Let $d \in \mathbb {N}+1$ , and let $\mathbf {v}$ be a random variable taking values in $\mathbb {Z}^d$ obeying the exponential tail condition

(2.3) $$ \begin{align} \mathbb{P}( |\mathbf{v}| \geq \lambda ) \ll \exp( -c_0 \lambda ) \end{align} $$

for all $\lambda \geq 0$ and some $c_0>0$ . Assume the non-degeneracy condition that $\mathbf {v}$ is not almost surely concentrated on any coset of any proper subgroup of $\mathbb {Z}^d$ . Let $\vec \mu := \mathbb {E} \mathbf {v} \in \mathbb {R}^d$ denote the mean of $\mathbf {v}$ . In this lemma all implied constants, as well as the constant c, can depend on d, $c_0$ , and the distribution of $\mathbf {v}$ . Let $n \in \mathbb {N}$ , and let $\mathbf {v}_1,\dots ,\mathbf {v}_n$ be n iid copies of $\mathbf {v}$ . Following equation (1.6), we write $\mathbf {v}_{[1,n]} := \mathbf {v}_1 + \dots + \mathbf {v}_n$ .

1. (i) For any $\vec L \in \mathbb {Z}^d$ , one has

   $$ \begin{align*}\mathbb{P}\left( \mathbf{v}_{[1,n]} = \vec L \right) \ll \frac{1}{(n+1)^{d/2}}G_n\left( c \left(\vec L - n \vec \mu\right) \right)\!.\end{align*} $$

2. (ii) For any $\lambda \geq 0$ , one has

   $$ \begin{align*}\mathbb{P}\left( |\mathbf{v}_{[1,n]}- n \vec \mu| \geq \lambda \right) \ll G_n( c \lambda ).\end{align*} $$

Proof. We use the Fourier-analytic (and complex-analytic) method. We may assume that n is positive since the claim is trivial for $n=0$ . We begin with (i). Let S denote the complex strip $S := \{ z \in \mathbb {C}: |\mathrm {Re}(z)| < c_0 \}$ , then we can define the (complexified) moment generating function $M \colon S^d \to \mathbb {C}$ by the formula

$$ \begin{align*}M(z_1,\dots,z_d) := \mathbb{E} \exp( (z_1,\dots,z_d) \cdot \mathbf{v} ),\end{align*} $$

where $\cdot $ is the usual bilinear dot product. From equation (2.3) and Morera’s theorem, one verifies that this is a well-defined holomorphic function of d complex variables on $S^d$ , which is periodic with respect to the lattice $(2\pi i\mathbb {Z})^d$ . By Fourier inversion, we have

$$ \begin{align*}\mathbb{P}( \mathbf{v}_{[1,n]} = \vec L) = \frac{1}{(2\pi)^d} \int_{[-\pi,\pi]^d} M\left( i\vec t \right)^n \exp\left( - i \vec t \cdot \vec L \right)\ d\vec t.\end{align*} $$

By contour shifting, we then have

$$ \begin{align*}\mathbb{P}( \mathbf{v}_{[1,n]} = \vec L) = \frac{1}{(2\pi)^d} \int_{[-\pi,\pi]^d} M\left( i\vec t + \vec \lambda\right)^n \exp\left( - (i\vec t + \lambda) \cdot \vec L \right)\ d\vec t\end{align*} $$

whenever $\vec \lambda = (\lambda _1,\dots ,\lambda _d) \in (-c_0,c_0)^d$ . By the triangle inequality, we thus have

$$ \begin{align*}\mathbb{P}( \mathbf{v}_{[1,n]} = \vec L) \ll \int_{[-\pi,\pi]^d} \left|M\left( i\vec t + \vec \lambda\right)\right|{}^n \exp\left( - \vec \lambda \cdot \vec L \right)\ d\vec t.\end{align*} $$

From Taylor expansion and the non-degeneracy condition we have

$$ \begin{align*}M(\vec z) = \exp\left( \vec z \cdot \vec \mu + \frac{1}{2} \Sigma(\vec z) + O(|\vec z|^3) \right)\end{align*} $$

for all $\vec z \in S^d$ sufficiently close to $0$ , where $\Sigma $ is a positive definite quadratic form (the covariance matrix of $\mathbf {v}$ ). From the non-degeneracy condition we also see that $|M(i\vec t)| < 1$ whenever $\vec t \in [-\pi ,\pi ]^d$ is not identically zero, hence by continuity $|M(i\vec t + \vec \lambda )| \leq 1-c$ whenever $\vec t \in [-\pi ,\pi ]^d$ is bounded away from zero and $\vec \lambda $ is sufficiently small. This implies the estimates

$$ \begin{align*}|M(i\vec t + \vec \lambda )| \leq \exp\left( \vec \lambda \cdot \vec \mu - c |\vec t|^2 + O( |\vec \lambda|^2) \right)\end{align*} $$

for all $\vec t \in [-\pi ,\pi ]^d$ and all sufficiently small $\vec \lambda \in \mathbb {R}^d$ . Thus we have

$$ \begin{align*} \mathbb{P}( \mathbf{v}_{[1,n]} = \vec L) &\ll \int_{[-\pi,\pi]^d} \exp\left( - \vec \lambda \cdot (\vec L-n\vec \mu) - c n|\vec t|^2 + O( n |\vec \lambda|^2 ) \right)\ d\vec t \\ &\ll n^{-1/2} \exp\left( - \vec \lambda \cdot (\vec L-n\vec \mu) + O( n |\vec \lambda|^2 ) \right). \end{align*} $$

If $|\vec L-n\vec \mu | \leq n$ , we can set $\vec \lambda := c(\vec L-n\vec \mu ) / n$ for a sufficiently small c and obtain the claim; otherwise if $|\vec L-n\vec \mu |> n$ , we set $\vec \lambda := c(\vec L-n\vec \mu )/|\vec L-n\vec \mu |$ for a sufficiently small c and again obtain the claim. This gives (i), and the claim (ii) then follows from summing in $\vec L$ and applying the integral test.

Theorem 3.1 (Alternate form of main theorem)

For $N_0 \geq 2$ and $x \geq 2$ , one has

$$ \begin{align*}\frac{1}{\log x} \sum_{N \in 2\mathbb{N}+1 \cap [1,x]: {\operatorname{Syr}}_{\min}(N)> N_0} \frac{1}{N} \ll \frac{1}{\log^c N_0}\end{align*} $$

or equivalently

$$ \begin{align*}\mathbb{P}( {\operatorname{Syr}}_{\min}( \mathbf{Log}(2\mathbb{N}+1 \cap [1,x]) ) \leq N_0 ) \geq 1 - O\left( \frac{1}{\log^c N_0} \right)\!.\end{align*} $$

In particular, by equation (1.2), we have

$$ \begin{align*}\mathbb{P}( {\operatorname{Col}}_{\min}( \mathbf{Log}(\mathbb{N}+1 \cap [1,x]) ) \leq N_0 ) \geq 1 - O\left( \frac{1}{\log^c N_0} \right)\end{align*} $$

for all $x \geq 2$ .

Proof. We may assume that $N_0$ is larger than any given absolute constant, since the claim is trivial for bounded $N_0$ . Let $E_{N_0} \subset 2\mathbb {N}+1$ denote the set

$$ \begin{align*}E_{N_0} := \{ N \in 2\mathbb{N}+1: {\operatorname{Syr}}_{\min}(N) \leq N_0 \}\end{align*} $$

of starting positions N of Syracuse orbits that reach $N_0$ or below. Let $\alpha $ be defined by equation (1.18), let $x \geq 2$ , and let $\mathbf {N}_y$ be the random variables from Proposition 1.11. Let $B_x = B_{x,N_0}$ denote the event that $T_x(\mathbf {N}_{x^\alpha }) < +\infty $ and ${\operatorname {Pass}}_{x}(\mathbf {N}_{x^{\alpha }}) \in E_{N_0}$ . Informally, this is the event that the Syracuse orbit of $\mathbf {N}_{x^\alpha }$ reaches x or below and then reaches $N_0$ or below. (For $x < N_0$ , the latter condition is automatic, while for $x \geq N_0$ , it is the former condition which is redundant.)

Observe that if $T_x( \mathbf {N}_{x^{\alpha ^2}} ) < +\infty $ and ${\operatorname {Pass}}_x(\mathbf {N}_{x^{\alpha ^2}}) \in E_{N_0}$ , then

$$ \begin{align*}T_{x^\alpha}( \mathbf{N}_{x^{\alpha^2}} ) \leq T_x( \mathbf{N}_{x^{\alpha^2}} ) < +\infty\end{align*} $$

and

$$ \begin{align*}{\operatorname{Syr}}^{\mathbb{N}}({\operatorname{Pass}}_x(\mathbf{N}_{x^{\alpha^2}})) \subset {\operatorname{Syr}}^{\mathbb{N}}({\operatorname{Pass}}_{x^\alpha}(\mathbf{N}_{x^{\alpha^2}}))\end{align*} $$

which implies that

$$ \begin{align*}{\operatorname{Syr}}_{\min}( {\operatorname{Pass}}_{x^\alpha}(\mathbf{N}_{x^{\alpha^2}}) ) \leq {\operatorname{Syr}}_{\min}( {\operatorname{Pass}}_x(\mathbf{N}_{x^{\alpha^2}}) ) \leq N_0.\end{align*} $$

In particular, the event $B_{x^\alpha }$ holds in this case. From this and equations (1.19), (1.20) and (1.10), we have

$$ \begin{align*} \mathbb{P}( B_{x^\alpha}) &\geq \mathbb{P}( {\operatorname{Pass}}_{x}(\mathbf{N}_{x^{\alpha^2}}) \in E_{N_0} \wedge T_{x}( \mathbf{N}_{x^{\alpha^2}} ) < +\infty ) \\ &\geq \mathbb{P}( {\operatorname{Pass}}_{x}(\mathbf{N}_{x^{\alpha^2}}) \in E_{N_0} ) - O( x^{-c} ) \\ &\geq \mathbb{P}( {\operatorname{Pass}}_{x}(\mathbf{N}_{x^{\alpha}}) \in E_{N_0} ) - O( \log^{-c} x ) \\ &\geq \mathbb{P}( B_x ) - O( \log^{-c} x ) \end{align*} $$

whenever x is larger than a suitable absolute constant (note that the $O(x^{-c})$ error can be absorbed into the $O(\log ^{-c} x)$ term). In fact, the bound holds for all $x \geq 2$ , since the estimate is trivial for bounded values of x.

Let $J = J(x,N_0)$ be the first natural number such that the quantity $y := x^{\alpha ^{-J}}$ is less than $N_0^{1/\alpha }$ . Since $N_0$ is assumed to be large, we then have (by replacing x with $y^{\alpha ^{j-2}}$ in the preceding estimate) that

$$ \begin{align*}\mathbb{P}( B_{y^{\alpha^{j-1}}} ) \geq \mathbb{P}( B_{y^{\alpha^{j-2}}} ) - O( (\alpha^j \log y)^{-c} ) \end{align*} $$

for all $j=1,\dots ,J$ . The event $B_{y^{\alpha ^{-1}}}$ occurs with probability $1 - O(y^{-c})$ , thanks to equation (1.19) and the fact that $\mathbf {N}_{y} \leq y^\alpha \leq N_0$ . Summing the telescoping series, we conclude that

$$ \begin{align*}\mathbb{P}( B_{y^{\alpha^{J-1}}} ) \geq 1 - O( \log^{-c} y )\end{align*} $$

(note that the $O(y^{-c})$ error can be absorbed into the $O( \log ^{-c} y )$ term). By construction, $y \geq N_0^{1/\alpha ^2}$ and $y^{\alpha ^J} = x$ , so

$$ \begin{align*}\mathbb{P}( B_{x^{1/\alpha}} ) \geq 1 - O( \log^{-c} N_0 ).\end{align*} $$

If $B_{x^{1/\alpha }}$ holds, then ${\operatorname {Pass}}_{x^{1/\alpha }}( \mathbf {N}_x )$ lies in the Syracuse orbit ${\operatorname {Syr}}^{\mathbb {N}}(\mathbf {N}_x)$ , and thus ${\operatorname {Syr}}_{\min }(\mathbf {N}_x) \leq {\operatorname {Syr}}_{\min }({\operatorname {Pass}}_{x^{1/\alpha }}( \mathbf {N}_x )) \leq N_0$ . We conclude that for any $x \geq 2$ , one has

$$ \begin{align*}\mathbb{P}( {\operatorname{Syr}}_{\min}(\mathbf{N}_x)> N_0 ) \ll \log^{-c} N_0.\end{align*} $$

By definition of $\mathbf {N}_x$ (and using the integral test to sum the harmonic series $\sum _{N \in 2\mathbb {N}+1 \cap [x,x^\alpha ]} \frac {1}{N}$ ), we conclude that

(3.1) $$ \begin{align} \sum_{N \in 2\mathbb{N}+1 \cap [x,x^\alpha]: {\operatorname{Syr}}_{\min}(N)> N_0} \frac{1}{N} \ll \frac{1}{\log^c N_0} \log x \end{align} $$

for all $x \geq 2$ . Covering the interval $2\mathbb {N}+1 \cap [1,x]$ by intervals of the form $2\mathbb {N}+1 \cap [y,y^\alpha ]$ for various y, we obtain the claim.

Lemma 4.1 (Tail bound)

We have

$$ \begin{align*}\mathbb{P}( |\vec a^{(n)}(\mathbf{N})| \geq n' ) \ll 2^{-cn}.\end{align*} $$

Proof. Write $\vec a^{(n)}(\mathbf {N}) = (\mathbf {a}_1,\dots ,\mathbf {a}_n)$ , then we may split

$$ \begin{align*}\mathbb{P}( |\vec a^{(n)}(\mathbf{N})| \geq n' ) = \sum_{k=0}^{n-1} \mathbb{P}( \mathbf{a}_{[1,k]} < n' \leq \mathbf{a}_{[1,k+1]} )\end{align*} $$

(using the summation convention in equation (1.6)), and so it suffices to show that

$$ \begin{align*}\mathbb{P}( \mathbf{a}_{[1,k]} < n' \leq \mathbf{a}_{[1,k+1]} ) \ll 2^{-cn}\end{align*} $$

for each $0 \leq k \leq n-1$ .

From Lemma 2.1 and equation (1.3), we see that

$$ \begin{align*}3^{k+1} 2^{- \mathbf{a}_{[1,k+1]}} \mathbf{N} + \sum_{i=1}^{k+1} 3^{k+1-i} 2^{-\mathbf{a}_{[i,k+1]}}\end{align*} $$

is an odd integer, and thus

$$ \begin{align*}3^{k+1} \mathbf{N} + \sum_{i=1}^{k+1} 3^{k+1-i} 2^{\mathbf{a}_{[1,i-1]}}\end{align*} $$

is a multiple of $2^{\mathbf {a}_{[1,k+1]}}$ . In particular, when the event $\mathbf {a}_{[1,k]} < n' \leq \mathbf {a}_{[1,k+1]}$ holds, one has

$$ \begin{align*}3^{k+1} \mathbf{N} + \sum_{i=1}^{k+1} 3^{k+1-i} 2^{\mathbf{a}_{[1,i-1]}} = 0 \bmod 2^{n'}.\end{align*} $$

Thus, if one conditions to the event $\mathbf {a}_j = a_j, j=1,\dots ,k$ for some positive integers $a_1,\dots ,a_k$ , then $\mathbf {N}$ is constrained to a single residue class $b \bmod 2^{n'}$ depending on $a_1,\dots ,a_k$ (because $3^{k+1}$ is invertible in the ring $\mathbb {Z}/2^{n'}\mathbb {Z}$ ). From equations (1.11) and (1.9), we have the quite crude estimate

$$ \begin{align*}\mathbb{P}( \mathbf{N} = b \bmod 2^{n'} ) \ll 2^{-n'}\end{align*} $$

and hence

$$ \begin{align*}\mathbb{P}( \mathbf{a}_{[1,k]} \leq n' < \mathbf{a}_{[1,k+1]} ) \ll \sum_{a_1,\dots,a_k \in \mathbb{N}+1: a_{[1,k]} < n'} 2^{-n'}.\end{align*} $$

The tuples $(a_1,\dots ,a_k)$ in the above sum are in one-to-one correspondence with the k-element subsets $\{ a_1, a_{[1,2]},\dots ,a_{[1,k]}\}$ of $\{1,\dots ,n'-1\}$ , and hence have cardinality $\binom {n'-1}{k}$ ; thus

$$ \begin{align*}\mathbb{P}( \mathbf{a}_{[1,k]} < n' \leq \mathbf{a}_{[1,k+1]} ) \ll 2^{-n'} \binom{n'-1}{k}.\end{align*} $$

Since $k \leq n-1$ and $n' \geq (2+c_0) n$ , the right-hand side is $O(2^{-cn})$ by Stirling’s formula (one can also use the Chernoff inequality for the sum of $n'-1$ Bernoulli random variables $\mathbf {Ber}(\frac {1}{2})$ , or Lemma 2.2). The claim follows.