Define the Collatz map {\mathrm{Col}: {\bf N}+1 \rightarrow {\bf N}+1} on the natural numbers {{\bf N}+1 = \{1,2,\dots\}} by setting {\mathrm{Col}(N)} to equal {3N+1} when {N} is odd and {N/2} when {N} is even, and let {\mathrm{Col}^{\bf N}(N) := \{ N, \mathrm{Col}(N), \mathrm{Col}^2(N), \dots \}} denote the forward Collatz orbit of {N}. The notorious Collatz conjecture asserts that {1 \in \mathrm{Col}^{\bf N}(N)} for all {N \in {\bf N}+1}. Equivalently, if we define the backwards Collatz orbit {(\mathrm{Col}^{\bf N})^*(N) := \{ M \in {\bf N}+1: N \in \mathrm{Col}^{\bf N}(M) \}} to be all the natural numbers {M} that encounter {N} in their forward Collatz orbit, then the Collatz conjecture asserts that {(\mathrm{Col}^{\bf N})^*(1) = {\bf N}+1}. As a partial result towards this latter statement, Krasikov and Lagarias in 2003 established the bound

\displaystyle \# \{ N \leq x: N \in (\mathrm{Col}^{\bf N})^*(1) \} \gg x^\gamma \ \ \ \ \ (1)

 

for all {x \geq 1} and {\gamma = 0.84}. (This improved upon previous values of {\gamma = 0.81} obtained by Applegate and Lagarias in 1995, {\gamma = 0.65} by Applegate and Lagarias in 1995 by a different method, {\gamma=0.48} by Wirsching in 1993, {\gamma=0.43} by Krasikov in 1989, {\gamma=0.3} by Sander in 1990, and some {\gamma>0} by Crandall in 1978.) This is still the largest value of {\gamma} for which (1) has been established. Of course, the Collatz conjecture would imply that we can take {\gamma} equal to {1}, which is the assertion that a positive density set of natural numbers obeys the Collatz conjecture. This is not yet established, although the results in my previous paper do at least imply that a positive density set of natural numbers iterates to an (explicitly computable) bounded set, so in principle the {\gamma=1} case of (1) could now be verified by an (enormous) finite computation in which one verifies that every number in this explicit bounded set iterates to {1}. In this post I would like to record a possible alternate route to this problem that depends on the distribution of a certain family of random variables that appeared in my previous paper, that I called Syracuse random variables.

Definition 1 (Syracuse random variables) For any natural number {n}, a Syracuse random variable {\mathbf{Syrac}({\bf Z}/3^n{\bf Z})} on the cyclic group {{\bf Z}/3^n{\bf Z}} is defined as a random variable of the form

\displaystyle \mathbf{Syrac}({\bf Z}/3^n{\bf Z}) = \sum_{m=1}^n 3^{n-m} 2^{-{\mathbf a}_m-\dots-{\mathbf a}_n} \ \ \ \ \ (2)

 

where {\mathbf{a}_1,\dots,\mathbf{a_n}} are independent copies of a geometric random variable {\mathbf{Geom}(2)} on the natural numbers with mean {2}, thus

\displaystyle \mathop{\bf P}( \mathbf{a}_1=a_1,\dots,\mathbf{a}_n=a_n) = 2^{-a_1-\dots-a_n}

} for {a_1,\dots,a_n \in {\bf N}+1}. In (2) the arithmetic is performed in the ring {{\bf Z}/3^n{\bf Z}}.

Thus for instance

\displaystyle \mathrm{Syrac}({\bf Z}/3{\bf Z}) = 2^{-\mathbf{a}_1} \hbox{ mod } 3

\displaystyle \mathrm{Syrac}({\bf Z}/3^2{\bf Z}) = 2^{-\mathbf{a}_1-\mathbf{a}_2} + 3 \times 2^{-\mathbf{a}_2} \hbox{ mod } 3^2

\displaystyle \mathrm{Syrac}({\bf Z}/3^3{\bf Z}) = 2^{-\mathbf{a}_1-\mathbf{a}_2-\mathbf{a}_3} + 3 \times 2^{-\mathbf{a}_2-\mathbf{a}_3} + 3^2 \times 2^{-\mathbf{a}_3} \hbox{ mod } 3^3

and so forth. After reversing the labeling of the {\mathbf{a}_1,\dots,\mathbf{a}_n}, one could also view {\mathrm{Syrac}({\bf Z}/3^n{\bf Z})} as the mod {3^n} reduction of a {3}-adic random variable

\displaystyle \mathbf{Syrac}({\bf Z}_3) = \sum_{m=1}^\infty 3^{m-1} 2^{-{\mathbf a}_1-\dots-{\mathbf a}_m}.

The probability density function {b \mapsto \mathbf{P}( \mathbf{Syrac}({\bf Z}/3^n{\bf Z}) = b )} of the Syracuse random variable can be explicitly computed by a recursive formula (see Lemma 1.12 of my previous paper). For instance, when {n=1}, {\mathbf{P}( \mathbf{Syrac}({\bf Z}/3{\bf Z}) = b )} is equal to {0,1/3,2/3} for {x=b,1,2 \hbox{ mod } 3} respectively, while when {n=2}, {\mathbf{P}( \mathbf{Syrac}({\bf Z}/3^2{\bf Z}) = b )} is equal to

\displaystyle 0, \frac{8}{63}, \frac{16}{63}, 0, \frac{11}{63}, \frac{4}{63}, 0, \frac{2}{63}, \frac{22}{63}

when {b=0,\dots,8 \hbox{ mod } 9} respectively.

The relationship of these random variables to the Collatz problem can be explained as follows. Let {2{\bf N}+1 = \{1,3,5,\dots\}} denote the odd natural numbers, and define the Syracuse map {\mathrm{Syr}: 2{\bf N}+1 \rightarrow 2{\bf N}+1} by

\displaystyle \mathrm{Syr}(N) := \frac{3n+1}{2^{\nu_2(3N+1)}}

where the {2}–valuation {\nu_2(3n+1) \in {\bf N}} is the number of times {2} divides {3N+1}. We can define the forward orbit {\mathrm{Syr}^{\bf N}(n)} and backward orbit {(\mathrm{Syr}^{\bf N})^*(N)} of the Syracuse map as before. It is not difficult to then see that the Collatz conjecture is equivalent to the assertion {(\mathrm{Syr}^{\bf N})^*(1) = 2{\bf N}+1}, and that the assertion (1) for a given {\gamma} is equivalent to the assertion

\displaystyle \# \{ N \leq x: N \in (\mathrm{Syr}^{\bf N})^*(1) \} \gg x^\gamma \ \ \ \ \ (3)

 

for all {x \geq 1}, where {N} is now understood to range over odd natural numbers. A brief calculation then shows that for any odd natural number {N} and natural number {n}, one has

\displaystyle \mathrm{Syr}^n(N) = 3^n 2^{-a_1-\dots-a_n} N + \sum_{m=1}^n 3^{n-m} 2^{-a_m-\dots-a_n}

where the natural numbers {a_1,\dots,a_n} are defined by the formula

\displaystyle a_i := \nu_2( 3 \mathrm{Syr}^{i-1}(N) + 1 ),

so in particular

\displaystyle \mathrm{Syr}^n(N) = \sum_{m=1}^n 3^{n-m} 2^{-a_m-\dots-a_n} \hbox{ mod } 3^n.

Heuristically, one expects the {2}-valuation {a = \nu_2(N)} of a typical odd number {N} to be approximately distributed according to the geometric distribution {\mathbf{Geom}(2)}, so one therefore expects the residue class {\mathrm{Syr}^n(N) \hbox{ mod } 3^n} to be distributed approximately according to the random variable {\mathbf{Syrac}({\bf Z}/3^n{\bf Z})}.

The Syracuse random variables {\mathbf{Syrac}({\bf Z}/3^n{\bf Z})} will always avoid multiples of three (this reflects the fact that {\mathrm{Syr}(N)} is never a multiple of three), but attains any non-multiple of three in {{\bf Z}/3^n{\bf Z}} with positive probability. For any natural number {n}, set

\displaystyle c_n := \inf_{b \in {\bf Z}/3^n{\bf Z}: 3 \nmid b} \mathbf{P}( \mathbf{Syrac}({\bf Z}/3^n{\bf Z}) = b ).

Equivalently, {c_n} is the greatest quantity for which we have the inequality

\displaystyle \sum_{(a_1,\dots,a_n) \in S_{n,N}} 2^{-a_1-\dots-a_m} \geq c_n \ \ \ \ \ (4)

 

for all integers {N} not divisible by three, where {S_{n,N} \subset ({\bf N}+1)^n} is the set of all tuples {(a_1,\dots,a_n)} for which

\displaystyle N = \sum_{m=1}^n 3^{m-1} 2^{-a_1-\dots-a_m} \hbox{ mod } 3^n.

Thus for instance {c_0=1}, {c_1 = 1/3}, and {c_2 = 2/63}. On the other hand, since all the probabilities {\mathbf{P}( \mathbf{Syrac}({\bf Z}/3^n{\bf Z}) = b)} sum to {1} as {b \in {\bf Z}/3^n{\bf Z}} ranges over the non-multiples of {3}, we have the trivial upper bound

\displaystyle c_n \leq \frac{3}{2} 3^{-n}.

There is also an easy submultiplicativity result:

Lemma 2 For any natural numbers {n_1,n_2}, we have

\displaystyle c_{n_1+n_2-1} \geq c_{n_1} c_{n_2}.

Proof: Let {N} be an integer not divisible by {3}, then by (4) we have

\displaystyle \sum_{(a_1,\dots,a_{n_1}) \in S_{n_1,N}} 2^{-a_1-\dots-a_{n_1}} \geq c_{n_1}.

If we let {S'_{n_1,N}} denote the set of tuples {(a_1,\dots,a_{n_1-1})} that can be formed from the tuples in {S_{n_1,N}} by deleting the final component {a_{n_1}} from each tuple, then we have

\displaystyle \sum_{(a_1,\dots,a_{n_1-1}) \in S'_{n_1,N}} 2^{-a_1-\dots-a_{n_1-1}} \geq c_{n_1}. \ \ \ \ \ (5)

 

Next, observe that if {(a_1,\dots,a_{n_1-1}) \in S'_{n_1,N}}, then

\displaystyle N = \sum_{m=1}^{n_1-1} 3^{m-1} 2^{-a_1-\dots-a_m} + 3^{n_1-1} 2^{-a_1-\dots-a_{n_1-1}} M

with {M = M_{N,n_1,a_1,\dots,a_{n_1-1}}} an integer not divisible by three. By definition of {S_{n_2,M}} and a relabeling, we then have

\displaystyle M = \sum_{m=1}^{n_2} 3^{m-1} 2^{-a_{n_1}-\dots-a_{m+n_1-1}} \hbox{ mod } 3^{n_2}

for all {(a_{n_1},\dots,a_{n_1+n_2-1}) \in S_{n_2,M}}. For such tuples we then have

\displaystyle N = \sum_{m=1}^{n_1+n_2-1} 3^{m-1} 2^{-a_1-\dots-a_{n_1+n_2-1}} \hbox{ mod } 3^{n_1+n_2-1}

so that {(a_1,\dots,a_{n_1+n_2-1}) \in S_{n_1+n_2-1,N}}. Since

\displaystyle \sum_{(a_{n_1},\dots,a_{n_1+n_2-1}) \in S_{n_2,M}} 2^{-a_{n_1}-\dots-a_{n_1+n_2-1}} \geq c_{n_2}

for each {M}, the claim follows. \Box

From this lemma we see that {c_n = 3^{-\beta n + o(n)}} for some absolute constant {\beta \geq 1}. Heuristically, we expect the Syracuse random variables to be somewhat approximately equidistributed amongst the multiples of {{\bf Z}/3^n{\bf Z}} (in Proposition 1.4 of my previous paper I prove a fine scale mixing result that supports this heuristic). As a consequence it is natural to conjecture that {\beta=1}. I cannot prove this, but I can show that this conjecture would imply that we can take the exponent {\gamma} in (1), (3) arbitrarily close to one:

Proposition 3 Suppose that {\beta=1} (that is to say, {c_n = 3^{-n+o(n)}} as {n \rightarrow \infty}). Then

\displaystyle \# \{ N \leq x: N \in (\mathrm{Syr}^{\bf N})^*(1) \} \gg x^{1-o(1)}

as {x \rightarrow \infty}, or equivalently

\displaystyle \# \{ N \leq x: N \in (\mathrm{Col}^{\bf N})^*(1) \} \gg x^{1-o(1)}

as {x \rightarrow \infty}. In other words, (1), (3) hold for all {\gamma < 1}.

I prove this proposition below the fold. A variant of the argument shows that for any value of {\beta}, (1), (3) holds whenever {\gamma < f(\beta)}, where {f: [0,1] \rightarrow [0,1]} is an explicitly computable function with {f(\beta) \rightarrow 1} as {\beta \rightarrow 1}. In principle, one could then improve the Krasikov-Lagarias result {\gamma = 0.84} by getting a sufficiently good upper bound on {\beta}, which is in principle achievable numerically (note for instance that Lemma 2 implies the bound {c_n \leq 3^{-\beta(n-1)}} for any {n}, since {c_{kn-k+1} \geq c_n^k} for any {k}).

— 1. Proof of proposition —

Assume {\beta=1}. Let {\varepsilon>0} be sufficiently small, and let {n_0} be sufficiently large depending on {\varepsilon}. We first establish the following proposition, that shows that elements in a certain residue class have a lot of Syracuse preimages:

Proposition 4 There exists a residue class of {{\bf Z}/3^{n_0}{\bf Z}} with the property that for all integers {N} in this class, and all non-negative integers {j}, there exist natural numbers {n_j, L_j} with

\displaystyle (2-\varepsilon^2) n_j \leq L_j \leq (2+\varepsilon^2) n_j

and

\displaystyle (4/3)^{(1-\varepsilon^2) (1+\varepsilon)^j n_0} \leq 3^{-n_j} 2^{L_j} \leq (4/3)^{(1+\varepsilon^2) (1+\varepsilon)^j n_0}

and at least {3^{-n_j - \varepsilon^4 n_j} 2^{L_j}} tuples

\displaystyle (a_1,\dots,a_{n_j-1}) \in S'_{n_j,N}

obeying the additional properties

\displaystyle a_1+\dots+a_{n_j-1} = L_j \ \ \ \ \ (6)

 

and

\displaystyle a_1+\dots+a_i - \frac{\log 3}{\log 2} i \geq - \varepsilon^5 n_0 \ \ \ \ \ (7)

 

for all {1 \leq i \leq n_j-1}.

Proof: We begin with the base case {j=0}. By (4) and the hypothesis {\beta=1}, we see that

\displaystyle \sum_{(a_1,\dots,a_{n_0-1}) \in S'_{n_0,N}} 2^{-a_1-\dots-a_{n_0-1}} \gg 3^{-(1+\varepsilon^6) n_0}

for all integers {N} not divisible by {3}. Let {S''_{n_0,N}} denote the tuples {(a_1,\dots,a_{n_0-1})} in {S'_{n_0,N}} that obey the additional regularity hypotheses

\displaystyle |a_1 + \dots + a_i - 2i| \leq - \varepsilon^5 n_0 \ \ \ \ \ (8)

 

for all {1 \leq i \leq n_0-1},note that this implies in particular the {j=0} case of (7). From the Chernoff inequality (noting that the geometric random variable {\mathrm{Geom}(2)} has mean {2}) and the union bound we have

\displaystyle \sum_{b \in {\bf Z}/3^{n_0}{\bf Z}: 3 \not | b} \sum_{(a_1,\dots,a_{n_0-1}) \in S'_{n_0,b} \backslash S''_{n_0,b}} 2^{-a_1-\dots-a_{n_0-1}} \ll 3^{-c \varepsilon^5 n_0}

for an absolute constant {c>0} (where we use the periodicity of {S'_{n_0,N}, S''_{n_0,N}} in {N} to define {S'_{n_0,b}, S''_{n_0,b}} for {b \in {\bf Z}/3^{n_0}{\bf Z}} by abuse of notation). Hence by the pigeonhole principle we can find a residue class {b} not divisible by {3} such that

\displaystyle \sum_{(a_1,\dots,a_{n_0-1}) \in S'_{n_0,b} \backslash S''_{n_0,b}} 2^{-a_1-\dots-a_{n_0-1}} \ll 3^{-(1+c \varepsilon^5) n_0}

and hence by the triangle inequality we have

\displaystyle \sum_{(a_1,\dots,a_{n_0-1}) \in S''_{n_0,N}} 2^{-a_1-\dots-a_{n_0-1}} \gg 3^{-(1+\varepsilon^6) n_0}

for all {N} in this residue class.

Henceforth {N} is assumed to be an element of this residue class. For {(a_1,\dots,a_{n_0-1}) \in S''_{n_0,N}}, we see from (8)

\displaystyle a_1 + \dots + a_{n_0-1} = (2+O(\varepsilon^5)) n_0,

hence by the pigeonhole principle there exists {L_0 = (2+O(\varepsilon^5)) n_0} (so in particular {3^{-n_0} 2^{L_0} = (4/3)^{(1+O(\varepsilon^5))n_0}}) such that

\displaystyle \sum_{(a_1,\dots,a_{n_0-1}) \in S''_{n_0,N}: a_1+\dots+a_{n_0-1} = L_0} 2^{-L_0} \gg 3^{-(1+\varepsilon^6) n_0}

so the number of summands here is at least {\gg 2^{L_0} 3^{-(1+\varepsilon^6) n_0}}. This establishes the base case {j=0}.

Now suppose inductively that {j \geq 1}, and that the claim has already been proven for {j-1}. By induction hypothesis, there exists natural numbers {n_{j-1}, L_{j-1}} with

\displaystyle (2-\varepsilon^2) n_{j-1} \leq L_{j-1} \leq (2+\varepsilon^2) n_{j-1}

and

\displaystyle (4/3)^{(1-\varepsilon^2) (1+\varepsilon)^{j-1} n_0} \leq 3^{-n_{j-1}} 2^{L_{j-1}} \leq (4/3)^{(1+\varepsilon^2) (1+\varepsilon)^{j-1} n_0} \ \ \ \ \ (9)

 

(which in particular imply that {n_{j-1} = (1+O(\varepsilon^2)) (1+\varepsilon)^{j-1} n_0}) and at least {3^{-n_{j-1} - \varepsilon^4 n_{j-1}} 2^{L_{j-1}}} tuples

\displaystyle (a_1,\dots,a_{n_{j-1}-1}) \in S'_{n_{j-1},N} \ \ \ \ \ (10)

 

obeying the additional properties

\displaystyle a_1+\dots+a_{n_{j-1}-1} = L_{j-1} \ \ \ \ \ (11)

 

and (7) for all {1 \leq i \leq n_{j-1}-1}.

Let {n_{j}} be an integer such that

\displaystyle 3^{-n_{j}} 2^{L_{j-1} + 2(n_{j}-n_{j-1})} \asymp (4/3)^{(1+\varepsilon)^j n_0} N. \ \ \ \ \ (12)

 

One easily checks that

\displaystyle n_{j} = (1+\varepsilon+O(\varepsilon^2)) n_{j-1} = (1+O(\varepsilon^2)) (1+\varepsilon)^{j-1} n_0.

For each tuple (10), we may write (as in the proof of Lemma 2)

\displaystyle N = \sum_{m=1}^{n_{j-1}-1} 3^{m-1} 2^{-a_1-\dots-a_m} + 3^{n_{j-1}-1} 2^{-L_{j-1}} M_{\vec a}

for some integers {M_{\vec a}}. We claim that these integers lie in distinct residue classes modulo {3^k} where

\displaystyle k :=\lfloor \frac{\log 2}{\log 3} L_{j-1} - n_{j-1} + \varepsilon^4 n_{j-1} \rfloor.

Indeed, suppose that {M_{\vec a} = M_{\vec b} \hbox{ mod } 3^k} for two tuples {\vec a = (a_1,\dots,a_{n_{j-1}-1})}, {\vec b = (b_1,\dots,b_{n_{j-1}-1})} of the above form. Then

\displaystyle \sum_{m=1}^{n_{j-1}-1} 3^{m-1} 2^{-a_1-\dots-a_m} = \sum_{m=1}^{n_{j-1}-1} 3^{m-1} 2^{-b_1-\dots-b_m} \hbox{ mod } 3^{n_{j-1}-1+k}

(where we now invert {2} in the ring {{\bf Z}/3^{n_{j-1}-1+k}{\bf Z}}), or equivalently

\displaystyle \sum_{m=1}^{n_{j-1}-1} 3^{m-1} 2^{a_{m+1}+\dots+a_{n_{j-1}-1}} = \sum_{m=1}^{n_{j-1}-1} 3^{m-1} 2^{b_{m+1}+\dots+b_{n_{j-1}-1}} \hbox{ mod } 3^{n_{j-1}-1+k}.

By (11), (7), all the summands on the left-hand side are natural numbers of size {O( 2^{L_{j-1}} 3^{O(\varepsilon^5 n_{j-1})})}, hence the sum also has this size; similarly for the right-hand side. From the estimates of {n_{j-1}, n_{j}}, we thus see that both sides are natural numbers between {1} and {3^{n_{j-1}-1+k}}, by hypothesis on {k}. Thus we may remove the modular constraint and conclude that

\displaystyle \sum_{m=1}^{n_{j-1}-1} 3^{m-1} 2^{a_{m+1}+\dots+a_{n_{j-1}-1}} = \sum_{m=1}^{n_{j-1}-1} 3^{m-1} 2^{b_{m+1}+\dots+b_{n_{j-1}-1}}

and then a routine induction (see Lemma 6.2 of my paper) shows that {(a_1,\dots,a_{n_{j-1}-1}) = (b_1,\dots,b_{n_{j-1}-1})}. This establishes the claim.

As a corollary, we see that every residue class modulo {3^{n_j-n_{j-1}}} contains

\displaystyle O( 3^{k - (n_j-n_{j-1})} ) = O( 2^{L_{j-1}} 3^{-n_j + \varepsilon^4 n_{j-1}} )

of the {M_{\vec a}} at most. Since there were at least {3^{-n_{j-1} - \varepsilon^4 n_{j-1}} 2^{L_{j-1}}} tuples {\vec a} to begin with, we may therefore forbid up to {O(3^{n_j-n_{j-1} - 3 \varepsilon^4 n_{j-1}})} residue classes modulo {3^{n_j-n_{j-1}}}, and still have {\gg 3^{-n_{j-1} - \varepsilon^4 n_{j-1}} 2^{L_{j-1}}} surviving tuples {\vec a} with the property that {M_{\vec a}} avoids all the forbidden classes.

Let {\vec a} be one of the tuples (10). By the hypothesis {\beta = 1}, we have

\displaystyle \sum_{(a_{n_{j-1}},\dots,a_{n_j-1}) \in S'_{n_j-n_{j-1},M_{\vec a}}} 2^{-a_{n_{j-1}}-\dots-a_{n_j-1}} \gg 3^{-(1+\varepsilon^6) (n_j-n_{j-1})}.

Let {S'''_{n_j-n_{j-1},M}} denote the set of tuples {(a_{n_{j-1}},\dots,a_{n_j-1}) \in S'_{n_j-n_{j-1},M}} with the additional property

\displaystyle |a_{n_{j-1}} + \dots + a_i - 2(i-n_{j-1}+1)| \leq - \varepsilon^3 (n_j - n_{j-1})

for all {n_{j-1} \leq i \leq n_j - 1}, then by the Chernoff bound we have

\displaystyle \sum_{b \in {\bf Z}/3^{n_j-n_{j-1}}{\bf Z}} \sum_{(a_{n_{j-1}},\dots,a_{n_j-1}) \in S'_{n_j-n_{j-1},b} \backslash S'''_{n_j-n_{j-1},b}} 2^{-a_{n_{j-1}}-\dots-a_{n_j-1}}

\displaystyle \ll 3^{-c\varepsilon^3 (n_j-n_{j-1})}

for some absolute constant {c>0}. Thus, by the Markov inequality, by forbidding up to {O(3^{n_j-n_{j-1} - 3 \varepsilon^4 n_{j-1}})} classes, we may ensure that

\displaystyle \sum_{(a_{n_{j-1}},\dots,a_{n_j-1}) \in S'_{n_j-n_{j-1},M_{\vec a}} \backslash S'''_{n_j-n_{j-1},M_{\vec a}}} 2^{-a_{n_{j-1}}-\dots-a_{n_j-1}} \ll 3^{-(1+\varepsilon^5) (n_j-n_{j-1})}

and hence

\displaystyle \sum_{(a_{n_{j-1}},\dots,a_{n_j-1}) \in S'''_{n_j-n_{j-1},M_{\vec a}}} 2^{-a_{n_{j-1}}-\dots-a_{n_j-1}} \gg 3^{-(1+\varepsilon^6) (n_j-n_{j-1})}.

We thus have

\displaystyle \sum_{a_1,\dots,a_{n_j-1}} 2^{-a_{n_{j-1}}-\dots-a_{n_j-1}} \gg 3^{-n_{j-1} - \varepsilon^4 n_{j-1}} 2^{L_{j-1}} 3^{-(1+\varepsilon^6) (n_j-n_{j-1})}

where {(a_1,\dots,a_{n_j-1})} run over all tuples with {\vec a = (a_1,\dots,a_{n_{j-1}-1})} being one of the previously surviving tuples, and {(a_{n_{j-1}},\dots,a_{n_j-1}) \in S'''_{n_j-n_{j-1},M_{\vec a}}}. By (11) we may rearrange this a little as

\displaystyle \sum_{a_1,\dots,a_{n_j-1}} 2^{-a_1-\dots-a_{n_j-1}} \gg 3^{-n_{j} - \varepsilon^4 n_{j-1}-\varepsilon^6 (n_j-n_{j-1})}.

By construction, we have

\displaystyle a_1 + \dots + a_{n_j-1} = L_{j-1} + (2 + O(\varepsilon^3)) (n_j - n_{j-1})

for any tuple in the above sum, hence by the pigeonhole principle we may find an integer

\displaystyle L_j = L_{j-1} + (2 + O(\varepsilon^3)) (n_j - n_{j-1}) \ \ \ \ \ (13)

 

for which

\displaystyle \sum_{a_1,\dots,a_{n_j-1}: a_1+\dots+a_{n_j-1}=L_j} 2^{-a_1-\dots-a_{n_j-1}} \geq 3^{-n_{j} - \varepsilon^4 n_j}.

In particular the number of summands is at least {3^{-n_{j} - \varepsilon^4 n_j} 2^{L_j}}. Also observe from (13), (12) that

\displaystyle 3^{-n_j} 2^{L_j} = 3^{-n_{j} + O( \varepsilon^3 (n_j - n_{j-1})} 2^{L_{j-1} + 2(n_j - n_{j-1})}

\displaystyle = (4/3)^{(1+\varepsilon)^j n_0} 3^{( \varepsilon^3 (n_j - n_{j-1})}

so in particular

\displaystyle (4/3)^{(1-\varepsilon^2) (1+\varepsilon)^j n_0} \leq 3^{-n_j} 2^{L_j} \leq (4/3)^{(1+\varepsilon^2) (1+\varepsilon)^j n_0}.

It is a routine matter to verify that all tuples in this sum lie in {S'_{n_j,N}} and obeys the requirements (6), (7), closing the induction hypothesis. \Box

Corollary 5 For all {N} in the residue class from the previous proposition, and all {j \geq 0}, we have

\displaystyle \{ M \in (\mathrm{Syr}^{\bf N})^*(N): M \leq 3 (4/3)^{(1+\varepsilon^2) (1+\varepsilon)^j n_0} N \}

\displaystyle \gg (4/3)^{(1-\varepsilon) (1+\varepsilon)^j n_0}.

In particular, we have

\displaystyle \{ M \in (\mathrm{Syr}^{\bf N})^*(N): M \leq x \} \gg_{\varepsilon,n_0,N} x^{1-\varepsilon}

as {x \rightarrow \infty}.

Proof: For every tuple {(a_1,\dots,a_{n_j-1})} in the previous proposition, we have

\displaystyle N = \sum_{m=1}^{n_{j}-1} 3^{m-1} 2^{-a_1-\dots-a_m} + 3^{n_{j}-1} 2^{-L_{j}} M

for some integer {M}. As before, all these integers {M} are distinct, and have magnitude

\displaystyle M \leq 3^{-n_j+1} 2^{L_j} N \leq \leq 3 (4/3)^{(1+\varepsilon^2) (1+\varepsilon)^j n_0} N.

From construction we also have {\mathrm{Syr}^{n_j}(M) = N}, so that {M \in (\mathrm{Syr}^{\bf N})^*(N)}. The number of tuples is at least

\displaystyle 3^{-n_j - \varepsilon^4 n_j} 2^{L_j}

which can be computed from the properties of {n_j,L_j} to be of size at least {(4/3)^{(1-\varepsilon) (1+\varepsilon)^j n_0}}. This gives the first claim, and the second claim follows by taking {j} to be the first integer for which {3 (4/3)^{(1+\varepsilon^2) (1+\varepsilon)^j n_0} N \geq x}. \Box

To conclude the proof of Proposition 3, it thus suffices to show that

Lemma 6 Every residue class {b \hbox{ mod } 3^{n_0}} has a non-trivial intersection with {(\mathrm{Syr}^{\bf N})^*(1)}.

Indeed, if we let {b \hbox{ mod } 3^{n_0}} be the residue class from the preceding propositions, and use this lemma to produce an element {N} of {(\mathrm{Syr}^{\bf N})^*(1)} that lies in this class, then from the inclusion {(\mathrm{Syr}^{\bf N})^*(N) \subset (\mathrm{Syr}^{\bf N})^*(1)} we obtain (3) with {\gamma = 1-O(\varepsilon)}, and then on sending {\varepsilon} to zero we obtain the claim.

Proof: An easy induction (based on first establishing that {2^{2 \times 3^n} = 1 + 3^{n+1} \hbox{ mod } 3^{n+2}} for all natural numbers {n}) shows that the powers of two modulo {3^{n_0+1}} occupy every residue class not divisible by {3}. From this we can locate an integer {N} in {b \hbox{ mod } 3^{n_0}} of the form {N = \frac{2^n-1}{3}}. Since {\mathrm{Syr}(N)=1}, the claim follows. \Box

We remark that the same argument in fact shows (assuming {\beta=1} of course) that

\displaystyle \# \{ N \leq x: N \in (\mathrm{Col}^{\bf N})^*(N_0) \} \gg_{N_0} x^{1-o(1)}

in the limit {x \rightarrow \infty} for any natural number {N_0} not divisible by three.