Equidistribution of Syracuse random variables and density of Collatz preimages

What's new 2020-01-26

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, 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. 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 ${x \mapsto \mathbf{P}( \mathbf{Syrac}({\bf Z}/3^n{\bf Z}) = x )}$ 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}) = x )}$ is equal to ${0,1/3,2/3}$ for ${x=0,1,2 \hbox{ mod } 3}$ respectively, while when ${n=2}$ , ${\mathbf{P}( \mathbf{Syrac}({\bf Z}/3^2{\bf Z}) = x )}$ 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 ${x=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 \not | b} \mathbf{P}( \mathbf{Syrac}({\bf Z}/3^2{\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 lower bound

$\displaystyle c_n \geq \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 ${0 \leq \beta \leq 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 lower 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)}$

for any natural number ${N_0}$ not divisible by three.