###### Abstract

The main result of this paper is a decomposition theorem for a measure on the
one-dimensional torus. Given a ”sufficiently large” subset $S$ of the positive
integers, an arbitrary measure on the torus is decomposed as the sum of two
measures. The first one $\mu_{1}$ has the property that the random walk with
initial distribution $\mu_{1}$ evolved by the action of $S$ equidistributes
very fast. The second measure $\mu_{2}$ in the decomposition is concentrated
on very small neighborhoods of a small number of points.

title = Decomposition of Random Walk Measures on the One-Dimensional Torus,
author = Tom Gilat, plaintextauthor = Tom Gilat, year=2020, number=3,
received=17 September 2019, published=4 March 2020, doi=10.19086/da.11888,

[classification=text]

##  1 Introduction

This paper is concerned with the dynamics of subsemigroups of the positive
integers acting on the one-dimensional torus $\mathbb{R}/\mathbb{Z}$. This
extensive line of research goes back to Furstenberg, who described the minimal
sets of the action of the semigroup generated by two multiplicatively
independent integers. They are finite periodic orbits and the whole torus.

Furstenberg also made several conjectures about such actions, which had an
enormous impact on the field. Perhaps the most prominent of these asks for a
classification of invariant measures on the torus under the action of the
semigroup generated by 2 and 3 (or any other pair of multiplicatively
independent integers). There has been some remarkable progress on this
problem, but the conjecture is still wide open.

These problems become more manageable if one considers the action of ”larger”
semigroups. For example, Einsiedler and Fish gave a classification of
invariant measures under the action of a semigroup with positive logarithmic
density.

The main result of this paper is a decomposition theorem for a measure on the
torus. Given a ”sufficiently large” subset $S$ of the positive integers, an
arbitrary measure on the torus is decomposed as the sum of two measures. The
first one $\mu_{1}$ has the property that the random walk with initial
distribution $\mu_{1}$ evolved by the action of $S$ equidistributes very fast.
The second measure $\mu_{2}$ in the decomposition is concentrated on very
small neighborhoods of a small number of points.

The proof of the main result uses tools from additive combinatorics and builds
on the work of Bourgain, Furman, Lindenstrauss and Mozes on the classification
of stationary measures under the action of non-commuting toral automorphisms.

We define the general setting as follows: for $L>0$, let $S\subset[L,2L]$ be a
set of natural numbers, $|S|>L^{\beta}$ for $0<\beta<1$, with $S$ being
$(\widetilde{C},\lambda)$-regular (definition follows). The variables
$L,\beta$ and $\widetilde{C},\lambda>0$ should be considered as global
parameters and are referred to in the different theorems, propositions and
lemmas, typically by giving thresholds on their values in the conditions of
the statements. All the measures in this paper are Borel measures, with the
topology of the measure space clear from the context. For countable spaces
such as $\mathbb{N}$ the topology is the discrete one. In a minor abuse of
terminology we refer to the Haar measure on $\mathbb{T}$ as the Lebesgue
measure on $\mathbb{T}$.

For a non-empty set $S\subset\mathbb{N}$ we let

$\nu_{S}=\frac{1}{|S|}\sum_{s\in S}\delta_{s}$ (1.1)

be the measure that averages over $S$. The set $S$ acts on the torus in the
following standard way: $s.x=sx\ (\mathrm{mod}\ 1)$ for $s\in S$. For $s\in
S$, let $T_{s}:\mathbb{T}\rightarrow\mathbb{T}$ be the mapping:
$T_{s}(x):x\mapsto s.x$ .

We denote by $\mathcal{P}(\cdot)$ the space of Borel probability measures on a
topological space. For $\mu\in\mathcal{P}(\mathbb{T}),\nu\in\mathcal{P}(S)$,
define the measure $\nu*\mu\in\mathcal{P}(\mathbb{T})$ as follows:

$\nu*\mu=\sum_{s\in S}\nu(s)T_{s*}\mu,$ (1.2)

where $T_{s*}\mu(E)=\mu(T_{s}^{-1}(E))$ for a Borel set $E\subset\mathbb{T}$.

The following definition says what it means for a set $S$ to be
$(\widetilde{C},\lambda$)-regular.

######  Definition 1.

Let $\widetilde{C},\lambda>0$. We say that a set
$S\subset[L,2L]\subset\mathbb{N}$ is $(\widetilde{C},\lambda)$-_regular at
scale_ $r$, where $r$ is a positive real number, if

$|I\cap S|\leq\widetilde{C}\cdot\left(\frac{|I|}{L}\right)^{\lambda}|S|$ (1.3)

for any interval $I\subset[L,2L]\subset\mathbb{R}$ with $|I|\geq r$. By
$|\cdot|$, we denote cardinality or the Lebesgue measure according to context.

If we say that a set is $(\widetilde{C},\lambda)$-regular, we mean that it is
$(\widetilde{C},\lambda)$-regular at scale $1$.

We are ready to state the main theorem of this work, which is a decomposition
theorem for a measure on the torus. In the statement, $\mu_{1},\mu_{2}$ are
non-negative Borel measures on $\mathbb{T}$, and $\mathsf{B}_{x,r}$ denotes an
open ball in $\mathbb{T}$ with center at $x$ and radius $r$. A finite set
$X\subset\mathbb{T}$ is $\delta$-_separated_ if for any $x,y\in
X,d(x,y)>\delta$, where $d(\cdot,\cdot)$ is the usual metric on $\mathbb{T}$.

######  Theorem 2.

Let $\mu$ be a probability measure on $\mathbb{T}$. For every
$\lambda,\beta>0$ there exist $L_{1},\kappa,C,U,\tau_{0}>0,k\in\mathbb{N}$,
such that if $L>L_{1}$, $S\subset[L,2L]$ is a
$(\widetilde{C},\lambda)$-regular set for some $\widetilde{C}<L^{\tau_{0}}$,
and $0<\tau<\tau_{0}$ with $|S|>L^{\beta}$, then there is a decomposition
$\mu=\mu_{1}+\mu_{2}$ such that

$\left|\widehat{\nu_{S}^{*k}*\mu_{1}}(n)\right|\leq L^{-\tau}\qquad\forall
0\neq|n|<L^{\tau},$ (1.4)

and there are finite subsets $X_{1},X_{2},...,X_{l}$ of $\mathbb{T}$, where
$l<L^{C\tau}$, such that each $X_{i}$ is $\frac{1}{M}$-separated, $\mu_{2}$ is
supported on $\bigcup_{i=1}^{l}\bigcup_{x\in
X_{i}}\mathsf{B}_{x,\frac{1}{N}}$, where $N=L^{U}$ and $M=N^{1-\kappa}$, and
$\mu_{1}$ is supported on the complement of the support of $\mu_{2}$.

The usefulness of this theorem is due to the fact that $M<N$ in a well
controlled manner. This implies a granulation phenomenon on the support of
$\mu_{2}$, meaning that $\mu_{2}(\mathbb{T})$ is larger, in a controlled
manner, than the Lebesgue measure of the support of $\mu_{2}$. In addition,
1.4 effectively describes $\mu_{1}$ as being ”close to uniform” over its
support.

In a follow-up paper we intend to show how Theorem 2 can be used to prove
effective equidistribution results in this context.

##  2 Preliminaries from additive combinatorics

The following inequality is due to Ruzsa. It is surprisingly useful, given how
simple it is to prove.

######  Lemma 3 ([14, Lemma 2.6] – Ruzsa triangle inequality).

Let $A,B,C\subset G$ with $G$ any additive group and $C\neq\emptyset$. Then

$|A-B|\leq\frac{|A-C||B-C|}{|C|}$

We will need the following graph-theoretic result, closely connected to the
Balog-Szemerédi-Gowers Theorem, due to Sudakov B., Szemerédi E. and Vu V. H. .

######  Theorem 4 ([13], Lemma 4.2).

Let n and K be positive numbers, and let $\mathcal{G}=\mathcal{G}(A,B,E)$ be a
(finite) bipartite graph, where $|B|\leq|A|=n$ and $|E|=n^{2}/K$. Then one can
find $A^{\prime}\subset A$ and $B^{\prime}\subset B$ such that

  1. 1.

$|A^{\prime}|\geq n/(16K^{2})$ and $|B^{\prime}|\geq n/(4K)$,

  2. 2.

$|(A^{\prime}\times B^{\prime})\cap E|\geq|A^{\prime}||B^{\prime}|/(4K)$

  3. 3.

for each $a\in A^{\prime}$ and $b\in B^{\prime}$, there are
$n^{2}/(2^{12}K^{5})$ paths of length 3 whose two endpoints are a and b.

We need two pieces of notation for the statement of the next lemma. They will
be used throughout the paper.

######  Definition 5.

Given a set $A\subset\mathbb{R}$ and $M\in\mathbb{R}$, let $\mathcal{N}(A;M)$
be the minimal number of open balls with radius $M>0$ (the center of a ball is
any point in $\mathbb{R}$) that cover the set $A$.

######  Definition 6.

Given $\mu\in\mathcal{P}(\mathbb{T})$ and a real number $\delta\geq 0$, let

$\mathcal{F}(\mu,\delta)=\left\\{a\in\mathbb{Z}\backslash\\{0\\}:|\widehat{\mu}(a)|>\delta\right\\}$
(2.1)

The following lemma allows us to extract from an initial set of high Fourier
coefficients a set of relatively large Fourier coefficients that is stable
with respect to subtraction. The sets are in a window around 0 and are viewed
at some resolution $M$. The proof uses a counting argument which involves the
graph-theoretic Lemma 4 as well as the algebraic nature of the ring of
integers.

######  Lemma 7.

For positive integer numbers $N,M$ and a probability measure $\mu$ on
$\mathbb{T}$; let $A_{0}$ be an $M$-separated subset of
$\mathcal{F}\left(\mu,\delta\right)\cap[-N,N]$. Let $R$ be a positive real
number, and assume that

$\mathcal{N}(\mathcal{F}\left(\mu,\delta^{2}/8\right)\cap[-2N,2N];M)\leq
R|A_{0}|.$

Then there exists a subset $A_{1}\subset A_{0}$ such that

  1. 1.

$\left|\frac{1}{|A_{1}|}\sum_{a\in
A_{1}}\widehat{\mu}(a)\right|\geq\frac{\delta}{2}$

  2. 2.

$|A_{1}|\gg|A_{0}|\delta^{2}$

  3. 3.

$\mathcal{N}(A_{1}-A_{1};M)\ll|A_{0}|R^{6}\delta^{-8}$

###### Proof.

By passing to a subset $A\subset A_{0}$ of size $|A|\geq\frac{|A_{0}|}{4}$ we
may assume that
$\mathrm{Re}(e^{i\theta}\cdot\widehat{\mu}(a))>\frac{\delta}{2}$, for some
fixed $\theta\in[0,2\pi)$ and for every $a\in A$. Therefore

$\left|\frac{1}{|A|}\sum_{a\in A}\widehat{\mu}(a)\right|>\frac{\delta}{2}.$
(2.2)

Let

$\phi(x)=\sum_{a\in A}e_{a}(x),$ (2.3)

where $e_{a}(x)$ stands for $e^{-2\pi axi}$. Note that

$|\phi(x)|^{2}=(\sum_{a\in A}e_{a}(x))\cdot\overline{(\sum_{b\in
A}e_{b}(x))}=\sum_{a,b\in A}e_{a-b}(x).$ (2.4)

We have that

$\begin{split}\sum_{a,b\in A}\widehat{\mu}(a-b)&=\int_{\mathbb{T}}\sum_{a,b\in
A}e_{a-b}(x)d\mu(x)\\\ &=\int_{\mathbb{T}}|\phi(x)|^{2}d\mu(x)\\\
&\geq\left|\int_{\mathbb{T}}\phi(x)d\mu(x)\right|^{2}\\\ &=\left|\sum_{a\in
A}\widehat{\mu}(a)\right|^{2}\end{split}$ (2.5)

where the inequality is due to the Cauchy-Schwarz inequality. Therefore

$\frac{1}{|A|^{2}}\sum_{a,b\in
A}\widehat{\mu}(a-b)\geq\left|\frac{1}{|A|}\sum_{a\in
A}\widehat{\mu}(a)\right|^{2}\geq\frac{\delta^{2}}{4}$ (2.6)

Let

$\begin{split}E&=\left\\{(a,b)\in A\times
A:\widehat{\mu}(a-b)>\frac{\delta^{2}}{8}\right\\}\\\ &=\left\\{(a,b)\in
A\times
A:a-b\in\mathcal{F}(\mu,\frac{\delta^{2}}{8})\cap[-2N,2N]\right\\}\end{split}$
(2.7)

By Lemma 14 we have that

$|E|\geq\frac{\delta^{2}}{8}|A|^{2}$ (2.8)

Define

$\bar{A}=\left\\{\left\lfloor\frac{a}{M}\right\rfloor\cdot M:a\in
A\right\\}+\\{0,M\\}$ (2.9)

Note that (recalling that $A$ is $M$-separated)

$|A|\leq|\bar{A}|\leq 2|A|$ (2.10)

Define

$H=\left\\{\left\lfloor\frac{h}{M}\right\rfloor\cdot
M:h\in\mathcal{F}(\mu,\frac{\delta^{2}}{8})\cap[-2N,2N]\right\\}+\\{0,M\\}$
(2.11)

Note that

$|H|\leq
4\mathcal{N}(\mathcal{F}\left(\mu,\delta^{2}/8\right)\cap[-2N,2N];M)\leq
4R|A_{0}|\leq 16R|\bar{A}|$ (2.12)

Next, we define

$\bar{E}=\left\\{(a,b)\in\bar{A}\times\bar{A}:a-b\in H\right\\}$ (2.13)

Note that

$|\bar{E}|\geq|E|$ (2.14)

By 2.8, 2.10, 2.14 we have that

$|\bar{E}|\geq\frac{\delta^{2}}{32}|\bar{A}|^{2}$ (2.15)

We choose subsets $A^{\prime},B^{\prime}\subset\bar{A}$ using Theorem 4, such
that

$|A^{\prime}|\geq\frac{\delta^{2}}{2^{7}}|\bar{A}|\quad,\quad|B^{\prime}|\geq\frac{\delta^{4}}{2^{14}}|\bar{A}|$
(2.16)

Let $a\in A^{\prime},b\in B^{\prime}$. Then $a-b$ can be written as

$a-b=(a-b_{1})+(b_{1}-a_{1})+(a_{1}-b)$ (2.17)

in at least $\frac{|\bar{A}|^{2}\delta^{2}}{2^{37}}$ ways with all
$a-b_{1},a_{1}-b_{1},a_{1}-b\in H$, and so by (2.12)

$\frac{|\bar{A}|^{2}\delta^{2}}{2^{37}}|A^{\prime}-B^{\prime}|\leq(16R|\bar{A}|)^{3}$
(2.18)

or

$|A^{\prime}-B^{\prime}|\leq 2^{49}R^{3}\delta^{-2}|\bar{A}|$ (2.19)

By Lemma 3 we have that

$|A^{\prime}-A^{\prime}|\leq 2^{102}R^{6}\delta^{-8}|\bar{A}|$ (2.20)

Define

$A_{1}=\left\\{a\in A:\exists a^{\prime}\in A^{\prime}\quad
s.t.\quad\left\lfloor\frac{a}{M}\right\rfloor\cdot M=a^{\prime}\right\\}$
(2.21)

And so (using 2.10)

$\mathcal{N}(A_{1}-A_{1};M)<2^{105}R^{6}\delta^{-8}|A_{0}|$ (2.22)

∎

######  Definition 8.

We denote by $V(\overline{y},\rho)$ the $\rho$-neighborhood of
$\overline{y}\in\mathbb{P}^{1}$. Formally it is:

$V(\overline{y},\rho)=\left\\{\overline{x}\in\mathbb{P}^{1}:\frac{|\langle
x,y\rangle|}{|x||y|}<\rho\ \text{\ for some\ representatives\
}x,y\in\mathbb{R}^{2},[x]=\overline{x},[y]=\overline{y}\right\\}.$ (2.23)

The following theorem is a projection theorem by Bourgain, which can be found
in [3].

######  Theorem 9 ([3], Thm. 5).

For any $\alpha_{0},\kappa>0$ there are
$\alpha_{\Delta},\epsilon_{0},r_{0},\tau_{0}>0$ such that the following holds
for $0<r<r_{0}$ and $\alpha_{0}<\alpha<2-\alpha_{0}$: let $\eta$ be a
probability measure on $\mathbb{P}^{1}$ s.t.

$\max_{\overline{y}\in\mathbb{P}^{1}}\eta\left(V\left(\overline{y},\rho\right)\right)<\rho^{\kappa}\qquad\textnormal{if}\quad
r<\rho<r^{\tau_{0}}.$ (2.24)

Let $E\subset[0,1]^{2}$ be an r-separated set with $|E|>r^{-\alpha}$ and a
non-concentration property

$\max_{x}|E\cap\mathtt{B}_{x,\rho}|<\rho^{\kappa}|E|\qquad\textnormal{if}\quad
r<\rho<r^{\tau_{0}}.$ (2.25)

Then there exist $D\subset\mathbb{P}^{1}$ and $E^{\prime}\subset E$ with

$\eta(D)>1-r^{\epsilon_{0}},\qquad|E^{\prime}|>r^{\epsilon_{0}}|E|$

so that

$\mathcal{N}\left(\pi_{\overline{\theta}}(E^{\prime\prime});r\right)>r^{-(\alpha+\alpha_{\Delta})/2}$

whenever $\overline{\theta}\in D$ and $E^{\prime\prime}\subset E^{\prime}$
satisfies $|E^{\prime\prime}|>r^{2\epsilon_{0}}|E|$. Here,
$\pi_{\overline{\theta}}(U)$ is the orthogonal projection of $U$ on the
subspace of $R^{2}$ spanned by some representative of $\overline{\theta}$.

##  3 Regularity of sets

######  Definition 10 ([4], Def. 5.1).

A Borel probability measure $\rho$ on a Borel set $B\subset\mathbb{R}^{d}$ is
said to be $(C,\alpha)$-_regular at scale $r$ on_ $B$ if for any $x\in B$,
$s\geq r$

$\rho(\mathsf{B}_{x,s})<C\left(\frac{s}{\mathrm{diam}\ B}\right)^{\alpha}.$
(3.1)

A set $B$ is said to be $(C,\alpha)$-_regular at scale_ $r$ if the
corresponding uniform measure $\rho=\frac{1}{|B|}\sum_{x\in B}\delta_{x}$ is
$(C,\alpha)$-regular at scale $r$.

The following lemma [4, Lemma 5.2] relates the defined notion of regularity of
a set to the expression of dimension via covering numbers.

######  Lemma 11 ([4], Lemma 5.2).

For any $\epsilon>0$ there are constants
$C_{\epsilon},C^{\prime}_{\epsilon}>0$ such that for every $s,\alpha$ with
$2\epsilon<s<\alpha$ and $r<1$, if
$\tilde{A}\subset\mathsf{B}_{\mathbf{0},1}\subset\mathbb{R}^{d}$ satisfies

$\mathcal{N}\left(\tilde{A};r\right)\geq r^{-\alpha},$ (3.2)

then there is a point $x\in\mathsf{B}_{\mathbf{0},1}$ and a probability
measure $\rho$ supported on $\tilde{A}\cap\mathsf{B}_{x,r^{\beta}}$ which is
$\left(C_{\epsilon},\alpha-s\right)$-regular on
$\mathsf{B}_{x,C^{\prime}_{\epsilon}r^{\beta}}$ at scale $r$ for
$\beta=\frac{1-\alpha+\epsilon}{1-\alpha+s-\epsilon}$

Lemma 5.3 in [4] is the following

######  Lemma 12.

Let $\rho$ be a $\left(C,\alpha\right)$-regular probability measure at scale
$r$ on $B\subset\mathbb{R}^{d}$. Then for any $\epsilon>0$ there is an
$r$-separated subset $A\subset\mathrm{supp}(\rho)$ and $C_{\epsilon}>0$ such
that the uniform measure on $A$ is
$\left(C_{\epsilon},\alpha-\epsilon\right)$-regular at scale $r$ on $B$.

We will be using the following lemma. Lemmas 11, 12 are used in its proof.

######  Lemma 13 ([4, Lemma 6.7], one dimensional torus).

For any $\epsilon>0$, there is a $C_{\epsilon}$ so that the following holds.
Let $\mu$ be a probability measure on $\mathbb{T}$. Assume that for some
$N>M,t,\alpha$

$\mathcal{N}(\mathcal{F}(\mu,t)\cap[-N,N];M)\geq\left(\frac{N}{M}\right)^{\alpha}.$
(3.3)

Then there is an $M<N_{1}<N$ with

$\log\frac{N_{1}}{M}>\left(\frac{1-\alpha+\epsilon}{1-\alpha+8\epsilon}\right)\log\frac{N}{M}$
(3.4)

such that $\mathcal{F}(\mu,t^{2}/4)\cap[-N_{1},N_{1}]$ contains a subset which
is $\left(C_{\epsilon}t^{-2},\alpha-10\epsilon\right)$-regular at scale $M$.

##  4 Main Bootstrapping Lemma

The following lemma is very simple but it is employed over and over again in
the main lemmas, making its explicit statement and proof worthwhile.

######  Lemma 14.

Let $\\{a_{i}\\}_{i=1}^{n}$ be a set of real numbers in $[0,1]$ for which

$\sum_{i=1}^{n}a_{i}\geq\alpha n.$ (4.1)

for $\alpha\in[0,1]$. Then

$\left|\left\\{i:a_{i}\geq\alpha/2\right\\}\right|\geq\frac{\alpha}{2}n$ (4.2)

###### Proof.

Suppose that

$\left|\left\\{i:a_{i}\geq\alpha/2\right\\}\right|<\frac{\alpha}{2}n$ (4.3)

Since each $a_{i}$ can be at most 1, we have that

$\sum_{i=1}^{n}a_{i}<\frac{\alpha}{2}n\cdot
1+\frac{2-\alpha}{2}n\cdot\frac{\alpha}{2}<\alpha n$ (4.4)

This is a contradiction. ∎

We prove the following lemma which is the extraction of the initial set of
large Fourier coefficients, using the information of having one single large
Fourier coefficient of the random walk measure.

######  Lemma 15 (Initial dimension).

For any probability measure $\mu$ on $\mathbb{T}$ for $n\geq 1$, if for some
$a\in\mathbb{Z}$

$|\widehat{\mu}_{n}(a)|>\delta_{0}$ (4.5)

for $\delta_{0}\in(0,1)$, then

$\mathcal{N}\left(\mathcal{F}(\mu_{n-1},\frac{\delta_{0}}{2})\cap[-N,N];M\right)\geq\frac{\delta_{0}}{2}\left(\frac{N}{M}\right)^{\alpha_{ini}}$
(4.6)

where $N=L|a|,M=|a|,\alpha_{ini}=\beta$ ($|S|=L^{\beta}$).

###### Proof.

Note the equality

$\widehat{\mu}_{n}(\xi)=\frac{1}{|S|}\sum_{s\in S}\widehat{\mu}_{n-1}(s\xi).$
(4.7)

By the above, we have that

$\delta_{0}<|\widehat{\mu}_{n}(a)|=\left|\frac{1}{|S|}\sum_{s\in
S}\widehat{\mu}_{n-1}(sa)\right|\leq\frac{1}{|S|}\sum_{s\in
S}\left|\widehat{\mu}_{n-1}(sa)\right|.$ (4.8)

By Lemma 14

$\left|\left\\{s\in
S:|\widehat{\mu}_{n-1}(sa)|>\frac{\delta_{0}}{2}\right\\}\right|\geq\frac{|S|\delta_{0}}{2}$
(4.9)

and so

$\mathcal{N}\left(\mathcal{F}(\mu_{n-1},\frac{\delta_{0}}{2})\cap\left[-L|a|,L|a|\right];|a|\right)\geq|S|\frac{\delta_{0}}{2}$
(4.10)

∎

For the next lemma we need the following simple definition.

######  Definition 16.

For a set $A\subset\mathbb{Z}$ and a positive real $M$, let
$B_{M}(A)=\bigcup_{a\in A}\mathsf{B}_{a,M}$.

The following is the main technical tool of the proof of our main
decomposition theorem, Theorem 2. We either find a large set of Fourier
coefficients by regarding a smaller value of the threshold on the coefficients
as being ”large”, or we look at the previous generation random walk measure;
the assumption of non-existence of a set that meets our terms is employed with
the additive structure of the Fourier coefficients to show two contradicting
inequalities.

######  Lemma 17 (Bootstrap lemma).

Given $\lambda,\tau>0$ and $0<\alpha_{ini}<\alpha_{high}<1$, there exist
$C^{*},\alpha_{inc}>0$ and $L_{1}$ such that if $L>L_{1}$,
$\alpha_{high}\geq\alpha\geq\alpha_{ini}$, $S\subset[L,2L]$ is a
$(\widetilde{C},\lambda)$-regular set for some $\widetilde{C}<L^{C^{*}}$, and
$N,M,\delta$ satisfy

$L^{\tau}<\frac{N}{M}<L\quad\text{and}\quad L^{-C^{*}}<\delta,$ (4.11)

and if

$\mathcal{N}\left(\mathcal{F}(\mu_{n},\delta)\cap[-N,N];M\right)\geq\left(\frac{N}{M}\right)^{\alpha}$

for some $n\geq 1$, then

$\mathcal{N}\left(\mathcal{F}(\mu_{n-1},\delta^{4}/256)\cap[-N^{\prime},N^{\prime}];M^{\prime}\right)\geq\left(\frac{N^{\prime}}{M^{\prime}}\right)^{\alpha+\alpha_{inc}}$

where $N^{\prime}=LN_{0},M^{\prime}=LM$, and $N_{0}$ is such that $M<N_{0}\leq
2N$ with

$\log\frac{N_{0}}{M}>\frac{1}{8}\cdot\log\frac{N}{M}.$ (4.12)

###### Proof.

Let $\alpha_{\Delta}$ be as in Theorem 9 for
$\alpha_{0}=\min(\alpha_{ini},1-\alpha_{high})/2$, and for
$\kappa=\frac{\lambda}{10}$.

Let

$E_{0}\subset\mathcal{F}\left(\mu_{n},\delta\right)\cap[-N,N]$ (4.13)

be an $M$-separated set of maximal cardinality. Let
$\epsilon<\frac{\alpha_{\Delta}}{640\cdot 20}$ be a constant to be determined
when we explain how to apply the projection theorem (Theorem 17) later in this
proof. Note that the proof may end without actually applying the projection
theorem. Apply Lemma 13 with respect to $\mu_{n},\delta$ (in the roles of
$\mu,t$) to obtain

$E^{\prime}_{0}\subset\mathcal{F}\left(\mu_{n},\delta^{2}/4\right)\cap[-N_{1},N_{1}],$
(4.14)

an $M$-separated set which is
$\left(C\delta^{-2},\alpha-10\epsilon\right)$-regular at scale $M$ ($C$
depends on $\epsilon$). $N_{1}$ is as obtained in the conclusion of Lemma 13.
Let

$E_{1}\subset\mathcal{F}\left(\mu_{n},\delta^{4}/32\right)\cap[-2N_{1},2N_{1}]$
(4.15)

be an $M$-separated set of maximal cardinality. And let

$\rho=\frac{|E_{1}|}{|E^{\prime}_{0}|}.$ (4.16)

We first deal with the case that

$\rho\geq 1024C\left(\frac{N_{1}}{M}\right)^{\alpha_{\Delta}/640}\delta^{-6}.$
(4.17)

We will use the relation

$\widehat{\mu}_{n}(\xi)=\frac{1}{|S|}\sum_{s\in S}\widehat{\mu}_{n-1}(s\xi).$
(4.18)

By passing to a subset $E_{1}^{\prime}\subset E_{1}$ of size
$|E_{1}^{\prime}|>\frac{|E_{1}|}{4}$ we may assume that for some fixed
$\theta\in[0,2\pi)$, for all $\xi\in E_{1}^{\prime}$,
$\mathrm{Re}(e^{i\theta}\cdot\widehat{\mu}(\xi))>\frac{\delta^{4}}{128}$.
Therefore,

$\left|\frac{1}{|E^{\prime}_{1}|}\sum_{\xi\in
E^{\prime}_{1}}\widehat{\mu}_{n}(\xi)\right|\geq\frac{\delta^{4}}{128}.$
(4.19)

Then by the relation (4.18) we have the inequality

$\frac{1}{|S||E_{1}^{\prime}|}\sum_{s\in S}\sum_{\xi\in
E_{1}^{\prime}}|\widehat{\mu}_{n-1}(s\xi)|\geq\frac{\delta^{4}}{128}.$ (4.20)

In particular there exists $s_{0}\in S$ such that

$\frac{1}{|E_{1}^{\prime}|}\sum_{\xi\in
E^{\prime}_{1}}|\widehat{\mu}_{n-1}(s_{0}\xi)|\geq\frac{\delta^{4}}{128}.$
(4.21)

Let

$E_{2}\subset\mathcal{F}\left(\mu_{n-1},\delta^{4}/256\right)\cap[-2LN_{1},2LN_{1}]$
(4.22)

be an $(LM)$-separated set of maximal cardinality. By Lemma 14 we have that

$\begin{split}\left|E_{2}\right|&\geq\left|\left\\{\xi\in
E^{\prime}_{1}:|\widehat{\mu}_{n-1}(s_{0}\xi)|\geq\frac{\delta^{4}}{256}\right\\}\right|\\\
&\geq\frac{\delta^{4}}{256}|E^{\prime}_{1}|\\\
&\geq\rho\frac{\delta^{4}}{1024}|E^{\prime}_{0}|.\end{split}$ (4.23)

If the inequality (4.17) holds then we are done (as long as we choose
$\alpha_{inc}\leq\frac{\alpha_{\Delta}}{1280}$, and for $N_{0}=2N_{1}$) as

$\left|E_{2}\right|\leq\mathcal{N}\left(\mathcal{F}(\mu_{n-1},\delta^{4}/256)\cap[-2LN_{1},2LN_{1}];LM\right)$

and $\epsilon<\frac{\alpha_{\Delta}}{640\cdot 20}$.

We now turn to the harder case where (4.17) fails. Define
$\delta^{\prime}=\frac{\delta^{2}}{4}$. By Lemma 7 there exists a set
$E\subset E^{\prime}_{0}$ such that

  1. (E.1)

$\left|\frac{1}{|E|}\sum_{e\in
E}\widehat{\mu}_{n}(e)\right|\geq\frac{\delta^{\prime}}{2}$ .

  2. (E.2)

$|E|>c^{\prime}|E^{\prime}_{0}|\delta^{\prime 2}$.

  3. (E.3)

$\mathcal{N}(E-E;M)<|E^{\prime}_{0}|c\rho^{6}\delta^{\prime-8}$.

Where $c,c^{\prime}$ are absolute constants. Set
$\rho^{\prime}=1024C\left(\frac{N}{M}\right)^{\alpha_{\Delta}/640}\delta^{-6}$
(this is the value in the bound in (4.17)). By (4.18) we have the inequality

$\left|\frac{1}{|S|}\frac{1}{|E|}\sum_{s\in S}\sum_{e\in
E}\widehat{\mu}_{n-1}(se)\right|\geq\frac{\delta^{\prime}}{2}.$ (4.24)

By Lemma 14 we have that

$\\#\left\\{(s,e)\in S\times
E:|\widehat{\mu}_{n-1}(se)|\geq\frac{\delta^{\prime}}{4}\right\\}\geq\frac{\delta^{\prime}}{4}|S||E|.$
(4.25)

Assume that for $\alpha_{inc}$ small to be determined later (but certainly
$\leq\frac{\alpha_{\Delta}}{1280}$), the following holds:

${}\mathcal{N}\left(\mathcal{F}(\mu_{n-1},\frac{\delta^{\prime}}{4})\cap[-LN_{1},LN_{1}];LM\right)<\left(\frac{N_{1}}{M}\right)^{\alpha+\alpha_{inc}}.$
(4.26)

Let

$M^{\prime}=LM,\qquad N^{\prime}=LN_{1}.$ (4.27)

Let

$E_{3}\subset\mathcal{F}(\mu_{n-1},\frac{\delta^{\prime}}{4})\cap[-N^{{}^{\prime}},N^{{}^{\prime}}]$
(4.28)

be an $M^{\prime}$-separated set of maximal cardinality. By inequality (4.25)
we have that

$\frac{2}{M^{\prime}}\sum_{s\in S}m\left(B_{M^{\prime}}(sE)\cap
B_{M^{\prime}}(E_{3})\right)\geq\frac{\delta^{\prime}}{4}|S||E|.$ (4.29)

Therefore,

$\int_{B_{M^{\prime}}(E_{3})}\sum_{s\in S}\mathbf{1}_{B_{M^{\prime}}(sE)\cap
B_{M^{\prime}}(E_{3})}(x)dm(x)\geq\frac{\delta^{\prime}}{8}M^{\prime}|S||E|.$
(4.30)

By the Cauchy-Schwarz inequality we have that

$2M^{\prime}|E_{3}|\int_{B_{M^{\prime}}(E_{3})}\left(\sum_{s\in
S}\mathbf{1}_{B_{M^{\prime}}(sE)\cap
B_{M^{\prime}}(E_{3})}(x)\right)^{2}dm(x)\geq\frac{\delta^{\prime
2}}{64}M^{\prime 2}|S|^{2}|E|^{2}.$ (4.31)

Writing inequality (4.31) in the following way

$\frac{1}{|S|^{2}}\sum_{(s_{1},s_{2})\in S\times
S}\frac{m\left(B_{M^{\prime}}(s_{1}E)\cap
B_{M^{\prime}}(s_{2}E)\right)}{M^{\prime}|E|}\geq\frac{\delta^{\prime
2}|E|}{128|E_{3}|},$ (4.32)

we see (using Lemma 14) that

$\\#\left\\{(s_{1},s_{2})\in S\times S:m(B_{M^{\prime}}(s_{1}E)\cap
B_{M^{\prime}}(s_{2}E))\geq\frac{M^{\prime}\delta^{\prime
2}|E|^{2}}{256|E_{3}|}\right\\}\geq\frac{\delta^{\prime
2}|E|}{256|E_{3}|}|S|^{2}.$ (4.33)

For a specific $s_{1}\in S$ we define the set $B$ as follows:

$B=\left\\{s_{2}\in S:m\left(B_{M^{\prime}}(s_{1}E)\cap
B_{M^{\prime}}(s_{2}E)\right)\geq\frac{M^{\prime}\delta^{\prime
2}|E|^{2}}{256|E_{3}|}\right\\}.$ (4.34)

By the pigeonhole principle there exists $s_{1}\in S$ so that

$|B|\geq\frac{\delta^{\prime 2}|E|}{512|E_{3}|}|S|.$ (4.35)

By assumption $S$ is $(\widetilde{C},\lambda)$-regular, and
$|E_{3}|<\left(\frac{N_{1}}{M}\right)^{\alpha+\alpha_{inc}}$. By (E.2) and the
$(C\delta^{-2},\alpha-10\epsilon)$ regularity of $E_{0}^{\prime}$ we have

$|E|>C^{-1}\delta^{4}\left(\frac{N_{1}}{M}\right)^{\alpha-10\epsilon}$ (4.36)

(recall that $\delta^{\prime}=\delta^{2}/4$), Hence, we may conclude that

$\frac{|E|}{|E_{3}|}\geq\frac{c^{\prime\prime}\delta^{6}(N_{1}/M)^{\alpha-10\epsilon}}{(N_{1}/M)^{\alpha+\alpha_{inc}}},$

from which it follows that $B$ is $(\widetilde{C_{1}},\lambda)$-regular, where

$\widetilde{C_{1}}=C^{\prime\prime}L^{10C_{*}}(N_{1}/M)^{\alpha_{inc}+10\epsilon}\widetilde{C}$

for some $c^{\prime\prime},C^{\prime\prime}$ independent of $N,M,L$.

Using Rusza’s triangle inequality (Lemma 3) we have the following, for fixed
$s_{1}$ and for all $s_{2}\in B$:

$\begin{aligned}
\left|B_{M^{\prime}}(s_{1}E)-B_{M^{\prime}}(s_{2}E)\right|\leq&\frac{\left|B_{M^{\prime}}(s_{1}E)-B_{M^{\prime}}(s_{1}E)\cap
B_{M^{\prime}}(s_{2}E)\right|\left|B_{M^{\prime}}(s_{2}E)-B_{M^{\prime}}(s_{1}E)\cap
B_{M^{\prime}}(s_{2}E)\right|}{\left|B_{M^{\prime}}(s_{1}E)\cap
B_{M^{\prime}}(s_{2}E)\right|}\\\
\leq&\frac{\left|B_{M^{\prime}}(s_{1}E)-B_{M^{\prime}}(s_{1}E)\right|\left|B_{M^{\prime}}(s_{2}E)-B_{M^{\prime}}(s_{2}E)\right|}{\left|B_{M^{\prime}}(s_{1}E)\cap
B_{M^{\prime}}(s_{2}E)\right|}\\\ \leq&\frac{25\mathcal{N}(E-E;M)^{2}M^{\prime
2}}{|B_{M^{\prime}}(s_{1}E)\cap B_{M^{\prime}}(s_{2}E)|}.\end{aligned}$

This can be summarized by the inequality

$\left|B_{M^{\prime}}(s_{1}E)-B_{M^{\prime}}(s_{2}E)\right|\leq\frac{25\mathcal{N}(E-E;M)^{2}M^{\prime
2}}{|B_{M^{\prime}}(s_{1}E)\cap B_{M^{\prime}}(s_{2}E)|}$ (4.37)

By (E.2), (E.3) and by (4.34),(4.26), for $s_{2}\in B$ ($s_{1}$ fixed before),
we have

$\begin{split}\left|B_{M^{\prime}}(s_{1}E)-B_{M^{\prime}}(s_{2}E)\right|&\leq
c\rho^{12}\delta^{\prime-22}M^{\prime}|E_{3}|\\\
&<c_{1}\rho^{12}\delta^{-44}M^{\prime}\left(\frac{N_{1}}{M}\right)^{\alpha+\alpha_{inc}}\\\
&<c_{2}\delta^{-116}M^{\prime}\left(\frac{N_{1}}{M}\right)^{\alpha+\alpha_{inc+3\alpha_{\Delta}/16}}.\end{split}$
(4.38)

Define the set $\widetilde{E}=N_{1}^{-1}E\times N_{1}^{-1}E$. By (4.36),

$|\widetilde{E}|>C^{-2}\delta^{8}\left(\frac{N_{1}}{M}\right)^{2\alpha-20\epsilon}>\left(\frac{N_{1}}{M}\right)^{2\alpha-21\epsilon}$
(4.39)

by (4.11) and (4.12), the second inequality holding if
$C^{*}<2^{-6}\tau\epsilon$ and $L_{1}$ is large enough.

The set $\widetilde{E}$ is $\frac{M}{N_{1}}$-separated and
$(C^{2}\delta^{-8},2\alpha-20\epsilon)$-regular at scale $M/N_{1}$. We apply
the projection theorem, Theorem 9, to the set $\widetilde{E}\subset[-1,1]^{2}$
with respect to the measure $\eta$ on the set of directions in
$\mathbb{P}^{1}$ corresponding to uniform choice of direction from the
projection of the set $\\{-s_{1}\\}\times B$ to $\mathbb{P}^{1}$. This measure
$\eta$ will satisfy (2.24) for any $\kappa<\lambda$ as long as the $\tau_{0}$
from Theorem 9 satisfies that
$\left(\frac{N_{1}}{M}\right)^{\tau_{0}(\lambda-\kappa)}>\widetilde{C_{1}}$,
which holds for suitable choice of $C^{*},\epsilon,\alpha_{inc}$ once $L_{1}$
is large enough. Similarly, $\widetilde{E}$ will satisfy (2.25) once
$\kappa<\alpha_{ini}$ if $C^{*},\epsilon$ are small enough and $L_{1}$ large
enough.

Theorem 9 gives us a set $\Theta\subset\mathbb{P}^{1}$ with
$\eta(\Theta)>1-\left(\frac{M}{N_{1}}\right)^{\epsilon_{0}}$ so that for
$\overline{(-s_{1},s_{2})}\in\Theta$:

$\begin{split}\mathcal{N}&\left(\frac{s_{2}E/N_{1}-s_{1}E/N_{1}}{\sqrt{s_{1}^{2}+s_{2}^{2}}};\frac{M}{N_{1}}\right)\geq\left(\frac{N_{1}}{M}\right)^{\alpha+\alpha_{\Delta}-11\epsilon}\\\
\end{split}$ (4.40)

Since $\eta(\Theta)$ is positive, there is at least one $s_{2}\in B\subset S$,
for which the inequality 4.40 holds. Let $s_{2}$ be any such number.

Using the fact that $\sqrt{s_{1}^{2}+s_{2}^{2}}\geq L$ and by $M^{\prime}=LM$,
we have (if $\epsilon$ is $<\alpha_{\Delta}/100$) the inequality

$\mathcal{N}\left(s_{2}E-s_{1}E;M^{\prime}\right)\geq\left(\frac{N_{1}}{M}\right)^{\alpha+\alpha_{\Delta}/2}.$
(4.41)

Therefore,

$\left|B_{M^{\prime}}(s_{1}E)-B_{M^{\prime}}(s_{2}E)\right|\geq
25\mathcal{N}\left(s_{2}E-s_{1}E;M^{\prime}\right)M^{\prime}\geq
M^{\prime}\left(\frac{N_{1}}{M}\right)^{\alpha+\alpha_{\Delta}/2}.$ (4.42)

Recalling that $\alpha_{inc}$ was chosen to be $\leq\alpha_{\Delta}/1280$, we
get a contradiction between (4.38) and (4.42) if $C^{*}$ is small enough and
$L_{1}$ large enough. This completes the proof (with $N_{0}=N_{1}$).

∎

##  5 Dimensions of Projections

This section contains background material for a final bootstrapping lemma,
which is stated and proved the end. The following part is adapted from [4].
Closely related to the notion of $(C,\alpha)$-regular measure introduced in
Definition 10 is the notion of $\alpha$-energy of a measure $\rho$, denoted by
$\mathcal{E}_{\alpha}(\rho)$, which we define for a compactly supported
measure $\rho$ on $\mathbb{R}^{d}$ and $\alpha<d$.

######  Definition 18.

The $\alpha$-_energy_ of a compactly supported measure $\rho$ on
$\mathbb{R}^{d}$ and $\alpha<d$, denoted by $\mathcal{E}_{\alpha}(\rho)$, is
defined by

$\mathcal{E}_{\alpha}(\rho)=\int_{\mathbb{R}^{d}}\int_{\mathbb{R}^{d}}\frac{d\rho(x)d\rho(y)}{|x-y|^{\alpha}}.$
(5.1)

If $\rho$ is $(C,\alpha+\epsilon)$-regular on a set $B$ at all scales, then

$\mathcal{E}_{\alpha}(\rho)=\alpha\int\int\frac{\rho(\mathsf{B}_{x,r})}{r^{\alpha+1}}d\rho(x)dr\leq
C(\mathrm{diam}\ B)^{-\alpha}\alpha\epsilon^{-1}.$ (5.2)

The energy $\mathcal{E}_{\alpha}(\rho)$ can also be expressed in terms of the
Fourier transform of $\rho$, up to an implicit constant that tends to $\infty$
as $\alpha\rightarrow 1$ (see [11], Lemma 12.12):

$\mathcal{E}_{\alpha}(\rho)\asymp\int_{\mathbb{R}^{d}}|\widehat{\rho}(\xi)|^{2}(1+|\xi|)^{\alpha-d}d\xi.$
(5.3)

If $\mathcal{E}_{\alpha}(\rho)<\infty$, then any set of positive $\rho$
measure has Hausdorff dimension at least $\alpha$ (for this and further
information about $\alpha$-energy, see [11]).

A simple way to adapt this notion to our ”coarse” setup, where we do not care
about the details of how $\rho$ behaves at scales smaller than $r$, is to
smooth it by convolving with an appropriate kernel. Let $\Phi$ be a fixed
radially symmetric nonnegative smooth function on $\mathbb{R}^{d}$ with
$\left\|\Phi\right\|_{1}=1$ supported on $\mathsf{B}_{\mathbf{0},1}$ and for
$r>0$ set

$\Phi_{r}(x)=r^{-d}\Phi(r^{-1}x).$ (5.4)

Then instead of using the possibly atomic measure $\rho$, we can consider its
smoothed version $\rho^{\prime}=\rho*\Phi_{r}$. In particular, if $\rho$ is
$(C,\alpha+\epsilon)$-regular at scale $r$ on a subset
$B\subset\mathbb{R}^{d}$, then

$\mathcal{E}_{\alpha}(\rho*\Phi_{r})\ll C(\mathrm{diam}\
B)^{-\alpha}\alpha\epsilon^{-1}$ (5.5)

with the implicit parameter depending only on $d$ and the choice of $\Phi$.

See [4], subsection 6.C. for more details. Let
$\Psi:\mathbb{R}\rightarrow\mathbb{R}^{+}$ be the smooth compactly supported
function

$\Psi(x_{1})=\int dx_{2}...\int dx_{d}\Phi(x_{1},x_{2},...,x_{d}),$ (5.6)

and define $\Psi_{r}$ analogously to (5.4)

######  Lemma 19 ([4], Lemma 6.10).

Let $\rho$ be a probability measure on $\mathbb{R}$, and let $\phi$ be the
Radon-Nikodym derivative $\phi=\frac{d(\rho*\Psi_{r})}{dx}$. Then for every
$0<r<r_{1}<1$

$\mathcal{N}(\mathrm{supp}\
\rho;r_{1})\geq(4r_{1}\left\|\phi\right\|_{2}^{2})^{-1}.$ (5.7)

Moreover, for any subset $X\subset\mathrm{supp}\ \rho$,

$\mathcal{N}(X;r_{1})\geq\frac{\rho(X)^{2}}{4r_{1}\left\|\phi\right\|^{2}_{2}}.$
(5.8)

For the next proposition we need a further definition.

######  Definition 20.

Let $\rho$ be a probability measure supported on the unit ball
$\mathsf{B}_{0,1}$ of $\mathbb{R}^{d}$ and let $\rho_{\theta}$ be the
orthogonal projection of the measure $\rho$ in the direction
$\theta\in\mathbb{P}^{d-1}$. Then $\widehat{\rho_{\theta}}(t)$ is defined by

$\widehat{\rho_{\theta}}(t)=\int_{-\infty}^{\infty}e^{-2\pi
itz}d\rho_{\theta}(z).$ (5.9)

######  Proposition 21 ([4], Prop. 6.11).

Let $\rho$ be a probability measure supported on the unit ball
$\mathsf{B}_{0,1}$ of $\mathbb{R}^{d}$ so that
$\mathcal{E}_{\alpha}(\rho)<\infty$ for some $0<\alpha<d$, $0<r<1$, and let
$\eta$ be a measure on $S^{d-1}$ such that for some $c_{\eta},\beta>0$

$\eta(\mathsf{B}_{\theta,\epsilon})\leq
c_{\eta}\epsilon^{\beta}\qquad\mathnormal{for\ every\ }\epsilon>r\ and\
\theta\in S^{d-1}.$ (5.10)

Then for any $\beta^{\prime}<\beta$

$\begin{split}\int_{\theta}\int_{t}|\widehat{\rho_{\theta}}&(t)|^{2}\left|\widehat{\Psi_{r}}(t)\right|^{2}(1+|t|)^{\beta^{\prime}+\alpha-d}dtd\eta(\theta)\\\
&\leq
c_{\eta}C_{d}\int_{\mathbb{R}^{d}}|\widehat{\rho}(x)|^{2}\left|\widehat{\Phi_{r}}(x)\right|^{2}(1+|x|)^{\alpha-d}dx+c_{\eta}C(\alpha,\beta,\beta^{\prime},d).\end{split}$
(5.11)

We shall use Proposition 21 with $d=2$. Almost quoting from [4], note that if
$\alpha+\beta^{\prime}>d$ and $\rho$ is $(C,\alpha^{\prime})$-regular at scale
$r$ for $\alpha^{\prime}>\alpha$, then by (5.2) the right-hand side of (5.11)
is bounded from above by a constant (depending on
$\alpha,\alpha^{\prime},\beta,\beta^{\prime},C,...$) while the left hand side
is at least

$\int_{\theta}\left\|\frac{d(\rho_{\theta}*\Psi_{r})}{dx}\right\|^{2}_{2}d\eta(\theta).$
(5.12)

In view of Lemma 19, this in particular implies that for $\eta$-many choices
of $\theta$, the covering number of supp($\rho_{\theta}$) by $r$-intervals is
large.

The next lemma will be used as a final step after the application of a number
of iterations of Lemma 17.

######  Lemma 22 (High dimension to positive density).

For any $\lambda>0$ there exist $\epsilon_{0}>0$ and $L_{1},C^{*}>0$ such that
if $L>L_{1}$, $\delta>L^{-C^{*}}$, $S\subset[L,2L]$ is
$(\widetilde{C},\lambda)$-regular, $N\leq LM$ and

$\mathcal{N}\left(\mathcal{F}(\mu_{n},\delta)\cap[-N,N];M\right)>\left(\frac{N}{M}\right)^{1-\epsilon_{0}},$
(5.13)

then there exists $N_{1}$ such that

$\mathcal{N}\left(\mathcal{F}(\mu_{n-1},\delta^{4}/128)\cap[-N_{1},N_{1}];M\right)>\frac{c\delta^{10}}{\widetilde{C}}\frac{N_{1}}{M},$
(5.14)

where $c$ is a constant and $N_{1}$ is such that

$\log\frac{N_{1}}{M}>\frac{1}{2}\log\frac{N}{M}.$ (5.15)

###### Proof.

(Parts of this Lemma are adapted from [4, Lemma 6.12]). Set
$\epsilon_{0}=\lambda/60$. Assume that for $N,M,n,\delta$ the inequality 5.13
holds. Let

$E_{0}\subset\mathcal{F}\left(\mu_{n},\delta\right)\cap[-N,N]$ (5.16)

be an $M$-separated set of maximal cardinality.

Set $\delta^{\prime}=\delta^{2}/4$. By Lemma 13 applied with
$\epsilon=\lambda/6$, there exists $N_{1}\in(M,N)$ with
$\log(N_{1}/M)>\frac{1}{2}\log(N/M)$ such that
$\mathcal{F}(\mu_{n},\delta^{\prime})\cap[-N_{1},N_{1}]$ contains a subset $E$
which is $(C\delta^{\prime-2},1-2\lambda/6)$-regular at scale $M$, where $C$
depends only on $\lambda$. We may assume that

$\frac{1}{E}\left|\sum_{b\in
E}\widehat{\mu}_{n}(b)\right|\geq\frac{\delta^{\prime}}{2},$ (5.17)

since we may always choose a subset $E_{1}\subset E$ of cardinality $\geq$
$|E|/4$ on which the above inequality holds which is
$(C\delta^{\prime-2},1-2\lambda/6)$-regular (possibly for a slightly different
$C$).

Set $\phi(x)=\sum_{s\in S}\sum_{\xi\in E}e_{s\xi}(x)$. Then by the Cauchy-
Schwarz inequality we have

$\begin{split}\sum_{s_{1},s_{2}\in S}\sum_{\xi_{1},\xi_{2}\in
E}\widehat{\mu}_{n-1}(s_{1}\xi_{1}-s_{2}\xi_{2})&=\int_{\mathbb{T}}\sum_{s_{1},s_{2}\in
S}\sum_{\xi_{1},\xi_{2}\in E}e_{s_{1}\xi_{1}-s_{2}\xi_{2}}(x)d\mu_{n-1}(x)\\\
&=\int_{\mathbb{T}}|\phi(x)|^{2}d\mu_{n-1}(x)\\\
&\geq\left|\int_{\mathbb{T}}\phi(x)d\mu_{n-1}(x)\right|^{2}\\\
&=\left|\sum_{s\in S}\sum_{\xi\in E}\widehat{\mu}_{n-1}(s\xi)\right|^{2}\\\
&=\left|\ |S|\sum_{\xi\in E}\widehat{\mu}_{n}(\xi)\right|^{2}.\end{split}$
(5.18)

We then obtain,

$\frac{1}{|S|^{2}}\sum_{s_{1},s_{2}\in S}\sum_{\xi_{1},\xi_{2}\in
E}\widehat{\mu}_{n-1}(s_{1}\xi_{1}-s_{2}\xi_{2})\geq\left|\sum_{\xi\in
E}\widehat{\mu}_{n}(\xi)\right|^{2},$ (5.19)

and so

$\begin{split}\frac{1}{|E|^{2}}\frac{1}{|S|^{2}}\sum_{s_{1},s_{2}\in
S}\sum_{\xi_{1},\xi_{2}\in
E}\widehat{\mu}_{n-1}(s_{1}\xi_{1}-s_{2}\xi_{2})&\geq\left|\frac{1}{E}\sum_{\xi\in
E}\widehat{\mu}_{n}(\xi)\right|^{2}\\\ &\geq\frac{\delta^{\prime
2}}{4}.\end{split}$ (5.20)

Fix $s_{2}$ to be an element in $S$ such that the term corresponding to it in
the above sum is the largest. Then

$\frac{1}{|S|}\frac{1}{|E|^{2}}\sum_{s_{1},s_{2}\in S}\sum_{\xi_{1},\xi_{2}\in
E}\widehat{\mu}_{n-1}(s_{1}\xi_{1}-s_{2}\xi_{2})\geq\frac{\delta^{\prime
2}}{4}.$ (5.21)

By Lemma 14 we have that

$\\#\left\\{(s_{1},\xi_{1},\xi_{2})\in S\times E\times
E:|\widehat{\mu}_{n-1}(s_{1}\xi_{1}-s_{2}\xi_{2})|\geq\frac{\delta^{\prime
2}}{8}\right\\}\geq\frac{\delta^{\prime 2}}{8}|S||E|^{2}.$ (5.22)

Let

$Q=\left\\{(s_{1},\xi_{1},\xi_{2})\in S\times E\times
E:|\widehat{\mu}_{n-1}(s_{1}\xi_{1}-s_{2}\xi_{2})|\geq\frac{\delta^{\prime
2}}{8}\right\\}.$ (5.23)

Next, we define a set $S^{\prime}$ by

$S^{\prime}=\left\\{s_{1}\in S:\left|Q\cap\left(\\{s_{1}\\}\times E\times
E\right)\right|\geq\frac{\delta^{\prime 2}|E|^{2}}{16}\right\\}.$ (5.24)

By Lemma 14 we have that $|S^{\prime}|\geq\frac{\delta^{\prime 2}}{16}|S|$.

Let $\eta$ be the uniform measure on the set of directions in $\mathbb{P}^{1}$
corresponding to the set $\\{-s_{2}\\}\times S^{\prime}$. The
$(\widetilde{C},\lambda)$-regularity of $S$ ensures that for any
$\xi\in\mathrm{supp}(\eta)\subset\mathbb{P}^{1}$ we have the inequality

$\eta\left(V(\xi,r)\right)\leq u\widetilde{C}\delta^{\prime-2}r^{\lambda}$
(5.25)

for any positive real number $r\geq M/N$ and some absolute constant $u$.
Applying Proposition 21 with $\beta=\lambda$,
$\beta^{\prime}=\frac{5\lambda}{6}$, $\alpha=1-\frac{5\lambda}{6}$ and

$\rho=\frac{1}{|E|^{2}}\sum_{b\in E^{\prime\prime}\times
E^{\prime}}\delta_{b/N_{1}}$

we get that

$\int_{\xi}\left\|\frac{d(\rho_{\xi}*\Phi_{r})}{dx}\right\|^{2}_{2}d\eta\leq\widetilde{C}\delta^{\prime-2}\left[C_{2}\int_{\mathbb{R}^{2}}|\widehat{\rho}(x)|^{2}\left|\widehat{\Phi_{r}}(x)\right|^{2}(1+|x|)^{\alpha-2}dx+C(\alpha,\beta,\beta^{\prime})\right],$
(5.26)

for $r=M/N_{1}$. Recall that $\rho$ is $(C\delta^{-2},2-2\lambda/3)$-regular
at scale $M/N_{1}$ (by adjusting $C$ if needed). It follows that

$\begin{split}\int_{\mathbb{R}^{2}}|\widehat{\rho}(x)|^{2}\left|\widehat{\Phi_{r}}(x)\right|^{2}(1+|x|)^{\alpha-2}dx&\asymp\mathcal{E}_{\alpha}(\rho*\Phi_{r})\leq\qquad\qquad\
(\mathrm{by}\ \ref{EnergyAsym2})\\\ &\leq
c^{\prime\prime}\delta^{-2}=8c^{\prime\prime}\delta^{\prime-1}\qquad(\mathrm{since}\
\alpha<2-2\lambda/3)\end{split}$ (5.27)

with $C^{\prime},c^{\prime\prime}$ depending on $\lambda$. Substituting into
5.26, we get

$\int_{\xi}\left\|\frac{d(\rho_{\xi}*\Phi_{r})}{dx}\right\|^{2}_{2}d\eta(\xi)\leq\widetilde{C}c_{*}\delta^{\prime-3}.$
(5.28)

We conclude that there is a subset $S^{\prime\prime}\subset S^{\prime}$ with
$|S^{\prime}|>(1-\frac{\delta^{\prime 2}}{16})|S|$ for which if $s_{1}\in
S^{\prime\prime}$ and $\xi_{0}=\overline{(-s_{2},s_{1})}\in\mathbb{P}^{1}$,
then

$\left\|\frac{d(\rho_{\xi_{0}}*\Phi_{r})}{dx}\right\|^{2}_{2}\leq\widetilde{C}c_{*}\delta^{\prime-3}\cdot\frac{16}{\delta^{\prime
2}}.$ (5.29)

For any such direction $\xi_{0}\in\mathbb{P}^{1}$, let $\pi_{\xi_{0}}$ denote
the orthogonal projection on to the subspace spanned by $\xi_{0}$ (considered
as a map $\mathbb{R}^{2}\rightarrow\mathbb{R}$). By Lemma 19 and 5.29 it
follows that

$\mathcal{N}\left(\pi_{\xi_{0}}(\frac{E^{\prime\prime}\times
E^{\prime}}{N_{1}};\frac{M}{N_{1}})\right)\geq 4\delta^{\prime
3}\cdot\frac{\delta^{\prime 2}}{16\widetilde{C}c_{*}}\cdot\frac{N_{1}}{M}\ .$
(5.30)

This yields the conclusion of our lemma. ∎

##  6 The Main Granulation Estimate

We state and prove two key propositions . The first is a general statement
which is stated and proved in [4]. The second is the main granulation
estimate, which is used in the proof of the main theorem, Theorem 2.

The following proposition and its proof are adapted from Bourgain, Furman,
Lindenstrauss and Mozes, [4]. The statement and its proof are harmonic
analytic in nature.

######  Proposition 23 ([4, Proposition 7.5]).

There exists $c>0$ such that if $t>0$ and a probability measure $\mu$ on
$\mathbb{T}^{d}$ satisfies

$\mathcal{N}\left(\left\\{a\in\mathbb{Z}^{d}\cap\mathsf{B}_{0,N}:|\widehat{\mu}(a)|>t\right\\};M\right)>s\cdot\left(\frac{N}{M}\right)^{d}$
(6.1)

with $M<\mathrm{const}_{d}\cdot N$, then there exists an
$\frac{1}{M}$-separated set $X\subset\mathbb{T}$ with

$\mu\left(\bigcup_{x\in X}\mathsf{B}_{x,\frac{1}{N}}\right)>c\cdot(ts)^{3}.$
(6.2)

###### Proof.

We shall need an auxiliary smooth function $F$ on the torus such that

$0\leq F\leq C_{1}\cdot
N^{d},\qquad\mathrm{supp}(F)\subset\mathsf{B}_{0,\frac{1}{N}}\qquad\int_{\mathbb{T}^{d}}Fdx=1$
(6.3)

and

$\widehat{F}(a)\geq
0,\qquad\widehat{F}(a)\geq\frac{1}{2}\quad\mathrm{for}\quad
a\in\mathbb{Z}^{d}\cap\mathsf{B}_{0,N}$ (6.4)

where $C_{1}$ is a constant depending on $d$ only. To construct such a
function, consider the step function
$F_{1}(x)=m\left(\mathsf{B}_{0,r}^{-1}\right)\cdot\mathbf{1}_{\mathsf{B}_{0,r}}(x)$,
where $r=\epsilon/N$ for some fixed small $\epsilon>0$. Then
$\widehat{F_{1}}(a)$ is close to 1 for
$a\in\mathbb{Z}^{d}\cap\mathsf{B}_{0,N}$. If $F_{2}$ is a smooth symmetric
approximation of $F_{1}$, then the convolution $F=F_{2}*\check{F_{2}}$ has the
desired properties.

Let $\tilde{A}$ be an $M$-separated set of size $|\tilde{A}|>s(N/M)^{d}$
consisting of coefficients $a\in\mathbb{Z}^{d}\cap\mathsf{B}_{0,N}$ with
$|\widehat{\mu}(a)|>t$. Upon passing to a subset $A\subset\tilde{A}$ of size

$|A|\geq\frac{|\tilde{A}|}{4}>\frac{s}{4}\left(\frac{N}{M}\right)^{d},$ (6.5)

we may assume that $\mathrm{Re}(e^{i\theta}\cdot\widehat{\mu}(a))>\frac{t}{2}$
for some fixed $\theta\in[0,2\pi]$. Let

$\phi(x)=\sum_{a\in A}e_{a}(x).$ (6.6)

As usual, $e_{a}=e^{-2\pi ixa}$. Note that

$|\phi(x)|^{2}=(\sum_{a\in A}e_{a}(x))\cdot\overline{(\sum_{b\in
A}e_{b}(x))}=\sum_{a,b\in A}e_{a-b}(x).$ (6.7)

The probability measure $\lambda=\mu*F$ has a smooth density
$g:\mathbb{T}^{d}\rightarrow[0,\infty)$ with
$\widehat{g}(b)=\widehat{\mu}(b)\cdot\widehat{F}(b)$. On $A$ we have
$\widehat{F}\geq 1/2$ and $\mathrm{Re}(e^{i\theta}\widehat{\mu}(a))>t/2$.
Therefore

$\left|\int_{\mathbb{T}^{d}}\phi d\lambda\right|\geq\sum_{a\in
A}\mathrm{Re}(e^{i\theta}\cdot\widehat{g}(a))>\frac{t}{4}\cdot|A|>\frac{ts}{2^{4}}\cdot\left(\frac{N}{M}\right)^{d}.$
(6.8)

We shall see that the right-hand side is close to an a priori upper estimate
for the left-hand side. Partition $\mathbb{T}^{d}$ into $M^{d}$ ”cubes”
$Q_{i}$ with side length $\frac{1}{M}$ and centers $c_{i}\in\mathbb{T}^{d}$.
By the Cauchy-Schwarz inequality,

$\left|\int_{\mathbb{T}^{d}}\phi
d\lambda\right|\leq\sum_{i}\left|\int_{\mathbb{T}^{d}}\mathbf{1}_{Q_{i}}\cdot\phi
d\lambda\right|\leq\sum_{i}\lambda(Q_{i})^{\frac{1}{2}}\cdot\left(\int_{Q_{i}}|\phi|^{2}d\lambda\right)^{\frac{1}{2}}$
(6.9)

Let $r=\frac{1}{M}$ which is assumed to be at least $\frac{1}{N}$. Then
$Q_{i}\subset\mathsf{B}_{c_{i},r/2}$ and $y+Q_{i}\subset\mathsf{B}_{c_{i},r}$
for any $y\in\mathrm{supp}(F)\subset\mathsf{B}_{0,\frac{1}{N}}$. Thus,

$\lambda(Q_{i})=\int_{\mathbb{T}^{d}}F(y)\cdot\mu(y+Q_{i})dy\leq\mu(\mathsf{B}_{c_{i},r}).$
(6.10)

Since $d\lambda(x)=g(x)dx$, we have

$\int_{Q_{i}}|\phi|^{2}d\lambda\leq
G_{i}\cdot\int_{Q_{i}}|\phi|^{2}dx,\qquad\mathrm{where}\qquad G_{i}=\max_{x\in
Q_{i}}g(x).$ (6.11)

We shall estimate $\int_{Q_{i}}|\phi|^{2}dx$ using an auxiliary function $f$
on $\mathbb{T}^{d}$: we take $f$ to be the product
$f(x)=\prod_{i=1}^{d}h_{M}(x_{i})$ of one-dimensional Fejér kernels

$h_{n}(u)=\frac{1}{n}\sum_{k=1}^{n}\sum_{j=-k}^{k}e^{2\pi
jui}=\frac{1}{n}\left(\frac{\sin\frac{nu}{2}}{\sin\frac{u}{2}}\right)^{2}.$
(6.12)

Note that $f$ is a nonnegative function, with $f(x)>10^{-d}\cdot M^{d}$ on the
$\frac{1}{M}$-cube
$Q_{0}=\left[-\frac{1}{2M},\frac{1}{2M}\right]^{d}+\mathbb{Z}^{d}$ around
$0\in\mathbb{T}^{d}$. The Fourier coefficients $\widehat{f}$ take values in
$[0,1]$ and vanish outside the $[-M,M]^{d}\cap\mathbb{Z}^{d}$ cube. Thus

$\begin{split}\int_{Q_{i}}&|\phi(x)|^{2}dx=\int_{Q_{0}}|\phi(x_{i}+y)|^{2}dy\leq\frac{10^{d}}{M^{d}}\int_{Q_{0}}|\phi(c_{i}+y)|^{2}f(y)dy\\\
&\leq\frac{10^{d}}{M^{d}}\int_{\mathbb{T}^{d}}|\phi(c_{i}+y)|^{2}f(y)dy=\frac{10^{d}}{M^{d}}\int_{\mathbb{T}^{d}}\sum_{a,b\in
A}e_{a-b}(c_{i}+y)\cdot f(y)dy\\\ &=\frac{10^{d}}{M^{d}}\left(\sum_{a,b\in
A}e_{a-b}(c_{i})\widehat{f}(a-b)\right)\leq\frac{10^{d}}{M^{d}}\cdot\sum_{a,b\in
A}|\widehat{f}(a-b)|.\end{split}$ (6.13)

Let $C_{2}$ denote the constant which is $10^{d}$ times the maximal
cardinality of a $1$-separated set in $[-1,1]^{-d}$. Since $A$ is
$M$-separated and $0\leq\widehat{f}\leq 1$, we have

$\frac{10^{d}}{M^{d}}\cdot\sum_{a,b\in
A}|\widehat{f}(a-b)|\leq\frac{C_{2}\cdot|A|}{M^{d}}\leq\frac{C_{2}\cdot
N^{d}}{M^{2d}}.$ (6.14)

The density $g$ of $\lambda=\mu*F$ has the following upper bound:

$g(x)=\int_{\mathbb{T}^{d}}F(x-y)d\mu(y)\leq C_{1}\cdot
N^{d}\cdot\mu(\mathsf{B}_{x,\frac{1}{N}}).$ (6.15)

Since $\mathsf{Nbd}_{\frac{1}{N}}(Q_{i})\subset\mathsf{B}_{c_{i},r}$, it
follows that

$G_{i}=\max_{x\in Q_{i}}g(x)\leq C_{1}N^{d}\mu(\mathsf{B}_{c_{i},r}).$ (6.16)

Let $0\leq H_{i}\leq 1$ denote the ratio, so $G_{i}=H_{i}\cdot
C_{1}N^{d}\mu(\mathsf{B}_{c_{i},r})$. By 6.8 and 6.9,

$\begin{split}\frac{ts}{2^{4}}\left(\frac{N}{M}\right)^{d}&\leq\sum_{i}\mu(\mathsf{B}_{c_{i},r})^{\frac{1}{2}}\cdot
G_{i}^{\frac{1}{2}}\cdot\frac{\sqrt{C_{2}}N^{\frac{d}{2}}}{M^{d}}\\\
&\leq\sum_{i}\mu(\mathsf{B}_{c_{i},r})\cdot
H_{i}^{\frac{1}{2}}\cdot\sqrt{C_{1}\cdot
C_{2}}\cdot\left(\frac{N}{M}\right)^{d}.\end{split}$ (6.17)

Let $C_{3}=\sqrt{C_{1}\cdot C_{2}}$. We have

$\sum_{i}\mu(\mathsf{B}_{c_{i},r})\cdot
H_{i}^{\frac{1}{2}}>\frac{ts}{2^{4}C_{3}}.$ (6.18)

Therefore,

$\sum_{i\in
I}\mu(\mathsf{B}_{c_{i},r})>\frac{ts}{2^{5}C_{3}}\qquad\mathrm{where}\qquad
I=\left\\{i:H_{i}^{\frac{1}{2}}>\frac{ts}{2^{5}C_{3}}\right\\}.$ (6.19)

For each $i\in I$ choose $x_{i}\in Q_{i}$ such that

$g(x_{i})>\left(\frac{ts}{2^{5}C_{3}}\right)^{2}\cdot
C_{1}N^{d}\cdot\mu(\mathsf{B}_{c_{i},r}).$ (6.20)

Then 6.15 gives

$\mu(\mathsf{B}_{x_{i},\frac{1}{N}})>\frac{g(x_{i})}{C_{1}N^{d}}>\frac{(ts)^{2}}{2^{10}C_{3}^{2}}\cdot\mu(\mathsf{B}_{c_{i},r}),$
(6.21)

and using 6.19,

$\sum_{i\in
I}\mu(\mathsf{B}_{x_{i},\frac{1}{N}})>\frac{(ts)^{3}}{2^{15}C_{3}^{3}}.$
(6.22)

The set $\tilde{X}={x_{i}:i\in I}$ visits each of the cubes $Q_{j}$ at most
once. Thus it may be separated into $2^{d}$ subsets each of which never visits
any neighboring $Q_{j}$ and is therefore $\frac{1}{M}$-separated. At least one
of the $2^{d}$ subsets $X\subset\tilde{X}$ has

$\mu(\bigcup_{x\in X}\mathsf{B}_{x,r})=\sum_{x\in
X}\mu(\mathsf{B}_{x,\frac{1}{N}})>2^{-d}\sum_{i\in
I}\mu(\mathsf{B}_{x_{i},\frac{1}{N}})>\frac{(ts)^{3}}{2^{d+15}\cdot
C_{3}^{3}}$ (6.23)

This completes the proof of the proposition. ∎

######  Proposition 24.

For $\lambda,\beta>0$ there exist $k\in\mathbb{N},C_{1},C^{\prime},L_{lb}>0$,
such that if $L>L_{lb}$, $n\geq k$, and $S\subset[L,2L]$ is a
$(\widetilde{C},\lambda)$-regular set for some $\widetilde{C}<L^{C_{1}}$ with
$|S|>L^{\beta}$, and if the measure $\mu_{n}=\nu_{S}^{*n}*\mu$ satisfies that
for some $a\in\mathbb{Z}\backslash\\{0\\}$ and $t>L^{-C_{1}}$ that

$|\widehat{\mu}_{n}(a)|>t>0,$ (6.24)

then there exists a $\frac{1}{M}$-separated set $X\subset\mathbb{T}$ with

$\mu_{n-k}\left(\bigcup_{x\in
X}\mathsf{B}_{x,\frac{1}{N}}\right)>C^{\prime}\cdot t^{33\cdot 2^{k}},$ (6.25)

where $M=L^{k}|a|$ and $N=L^{k+\frac{1}{8^{k}}}|a|$.

###### Proof.

Let $\epsilon_{0}$ be as in Lemma 22. Set $\alpha_{ini}=0.99\beta$ and
$\alpha_{high}=1-\epsilon_{0}$. Let $L_{lb}$ be the maximum of the value
$L_{{}_{1}}$ as in Lemma 17 and the value $L_{1}$ as in Lemma 22. Let $C^{*}$
be such that the conditions of both lemmas, Lemma 17 and Lemma 22, hold. We
shall determine $C_{1}$ later in the proof.

By Lemma 15 we have that for $\mu_{n}$

$\mathcal{N}\left(\mathcal{F}(\mu_{n-1},\frac{t}{2})\cap[-N,N];M\right)\geq\frac{t}{2}\left(\frac{N}{M}\right)^{\beta}$
(6.26)

where $N=L|a|,M=|a|$. Since $t$ is bounded from below by $L^{-C_{1}}$ which
will depend only on $\alpha_{ini}$ (and formally also on $\alpha_{high}$) then
we can modify $L_{lb}$, if necessary, to be large enough such that the
following holds,

$\mathcal{N}\left(\mathcal{F}(\mu_{n-1},\frac{t}{2})\cap[-N,N];M\right)\geq\left(\frac{N}{M}\right)^{0.99\beta}.$
(6.27)

We now use our bootstrapping lemma, Lemma 17, to obtain denser and denser sets
of large Fourier coefficients. We finish by applying the Final Bootstrapping
Lemma, 22. The first step is actually checking if we can reach the conclusion
of this lemma by applying once Lemma 22.

If $\alpha_{ini}>1-\epsilon_{0}$ then apply Lemma 22 and Proposition 23 to
complete the proof. If $\alpha_{ini}\leq 1-\epsilon_{0}$ then we do the
following. Let $\alpha_{inc}$ be as in Lemma 17 for the chosen values of
$\alpha_{ini},\alpha_{high}$. Let
$k^{\prime}=\left\lfloor(1-\epsilon_{0}-\alpha_{ini})/\alpha_{inc}\right\rfloor$
and $k=k^{\prime}+1$. Let $C_{1}$ be such that if $L_{lb}^{-C^{*}}<t$ then
$L_{lb}^{-C_{1}}<(t^{2^{k}}/4^{6^{k}})^{4}/128$.

Apply Lemma 17 $k^{\prime}$ times to obtain

$\mathcal{N}\left(\mathcal{F}(\mu_{n-k^{\prime}},t^{2^{k}}/4^{6^{k}})\cap[-N^{\prime},N^{\prime}];M^{\prime}\right)>\left(\frac{N^{\prime}}{M^{\prime}}\right)^{1-\epsilon_{0}}.$
(6.28)

Apply Lemma 22 to obtain

$\mathcal{N}\left(\mathcal{F}(\mu_{n-k^{\prime}},(t^{2^{k}}/4^{6^{k}})^{4}/128)\cap[-N^{\prime\prime},N^{\prime\prime}];M^{\prime}\right)>c\cdot\left(\frac{t^{2^{k}}}{4^{6^{k}}}\right)^{10}\left(\frac{N^{\prime}}{M^{\prime}}\right),$
(6.29)

where $c$ is the constant in the conclusion of Lemma 22. Apply Proposition 23
to complete the proof. ∎

##  7 Proof of Theorem 2

###### Proof of Theorem 2.

For $\lambda,\beta>0$, let $k,L_{lb},C_{1},C^{\prime}$ be as in the conclusion
of Proposition 24; we will set $L_{1}$ later to be greater than $L_{lb}$. Let
$\tau_{0}=\min\\{C_{1},\frac{1}{10\cdot 8^{k}}\\}$.

For $\tau<\tau_{0}$, let $a\in\mathbb{Z}\backslash\\{0\\}$ be such that
$|a|<L^{\tau}$ and such that $|\widehat{\nu_{S}^{*k}*\mu}(a)|>L^{-\tau}$.
Apply Proposition 24 to the measure $\nu_{S}^{*k}*\mu$ to obtain a set $X_{1}$
which is $\frac{1}{M}$-separated and $\mu(\bigcup_{x\in
X_{1}}\mathsf{B}_{x,\frac{1}{N}})>C^{\prime}\cdot L^{-\tau\cdot 33\cdot
2^{k}}$ for some constant $C^{\prime}$, where $M=L^{k+\frac{1}{10\cdot
8^{k}}}$, $N=L^{k+\frac{1}{8^{k}}}$ (the proposition gives the slightly
stronger statement that $X_{1}$ is $\frac{1}{L^{k}|a|}$ separated and that
$\mu(\bigcup_{x\in X_{1}}\mathsf{B}_{x,\frac{1}{N^{\prime}}})>C^{\prime}\cdot
L^{-33\cdot 2^{k}\tau}$ for $N^{\prime}=L^{k+\frac{1}{8^{k}}}|a|$; this
clearly implies what we use here). Let $\overline{X}_{1}=\bigcup_{x\in
X_{1}}\mathsf{B}_{x,\frac{1}{N}}$. Set

$\mu^{(1)}_{1}=\mu\bigr{|}_{\mathbb{T}\backslash\overline{X}_{1}}\qquad\text{and}\qquad\mu^{(1)}_{2}=\mu\bigr{|}_{\overline{X}_{1}}.$

As long as there are large Fourier coefficients of the measure $\mu^{(1)}_{1}$
in the relevant range, we continue in a similar manner: for
$a\in\mathbb{Z}\backslash\\{0\\}$ in the range $|a|<L^{\tau}$ such that
$|\widehat{\nu_{S}^{k}*\mu^{(1)}_{1}}(a)|>L^{-\tau}$ obtain $X_{2}$ using
Proposition 24; in order to apply Proposition 24, the measure $\mu^{(1)}_{1}$
is normalized so that the input is a probability measure
${\bar{\mu}}^{(1)}_{1}$, which only increases the Fourier coefficient, so

$|\widehat{\nu_{S}^{k}*{\bar{\mu}}^{(1)}_{1}}(a)|>|\widehat{\nu_{S}^{k}*\mu^{(1)}_{1}}(a)|>L^{-\tau}.$

We obtain a set $X_{2}$ which is $\frac{1}{M}$-separated and has the property
that

$\mu^{(1)}_{1}(\bigcup_{x\in X_{2}}\mathsf{B}_{x,\frac{1}{N}})>C^{\prime}\cdot
L^{-33\cdot 2^{k}\tau}\mu^{(1)}_{1}(\mathbb{T}).$

Let $\overline{X}_{2}=\bigcup_{x\in X_{2}}\mathsf{B}_{x,\frac{1}{N}}$. Set
$\mu^{(2)}_{1},\mu^{(2)}_{2}$ to be the following new measures:

$\displaystyle\mu^{(2)}_{1}$
$\displaystyle=\mu\bigr{|}_{\mathbb{T}\backslash(\overline{X}_{1}\cup\overline{X}_{2})}$
$\displaystyle\mu_{2}^{(2)}$
$\displaystyle=\mu\bigr{|}_{\overline{X}_{1}\cup\overline{X}_{2}}.$

We repeat this step in an analogous manner, as long there is an $|a|<L^{\tau}$
for which $\bigl{|}\widehat{\mu_{1}^{(\ell)}}(a)\bigr{|}>L^{-\tau}$, obtaining
a (finite, as we shall soon see) sequence of measures
$\mu^{(\ell)}_{1},\mu^{(\ell)}_{2}$ for $\ell=0,\dots,\ell_{max}$. Note that
for every $\ell\leq\ell_{max}$

$\mu^{(\ell)}_{1}(\mathbb{T})\leq(1-C^{\prime}\cdot L^{-33\cdot
2^{k}\tau})^{\ell}\leq e^{-C^{\prime}\cdot L^{-33\cdot 2^{k}\tau}\ell}$

which in particular shows that $\ell_{max}<\infty$ as
$\bigl{|}\widehat{\mu^{(\ell)}_{1}}(a)\bigr{|}\leq\mu^{(\ell)}_{1}(\mathbb{T})$
for all $\ell$. Indeed, this shows that

$e^{-C^{\prime}\cdot L^{-33\cdot 2^{k}\tau}\ell_{max}}\geq L^{-\tau}$

hence $\ell_{max}<{C^{\prime}}^{-1}(\log L)\cdot L^{33\cdot
2^{k}\tau}\tau<L^{34\cdot 2^{k}\tau}$ if $L_{1}$ is large enough. ∎

## Acknowledgments

The work presented in this paper comprises most of my PhD dissertation written
at the Hebrew University. I wish to thank my advisor, Prof. Elon
Lindenstrauss, for having me as a student, acquainting me with the techniques
and ideas which consist of this work, guiding me and more. I am deeply
grateful for that.

I would also like to thank Prof. Barak Weiss and Prof. Tamar Ziegler, who
served on my PhD committee, for following the process of the work and asking
important questions. I would like to thank Prof. Mike Hochman for his remarks
and help. In addition, I wish to thank the Hebrew University and the Einstein
Institute for being such a pleasant home. Lastly, I wish to thank the
anonymous referees who meticulously read my thesis. One of the referees
summarized the work so well that I could not avoid using his descriptions in
the introduction of this paper.

## References

  * [1] Michael D. Boshernitzan.  Elementary proof of Furstenberg’s Diophantine result.  Proc. Amer. Math. Soc., 122(1):67–70, 1994.
  * [2] J. Bourgain, A. A. Glibichuk, and S. V. Konyagin.  Estimates for the number of sums and products and for exponential sums in fields of prime order.  J. London Math. Soc. (2), 73(2):380–398, 2006.
  * [3] Jean Bourgain.  The discretized sum-product and projection theorems.  J. Anal. Math., 112:193–236, 2010.
  * [4] Jean Bourgain, Alex Furman, Elon Lindenstrauss, and Shahar Mozes.  Stationary measures and equidistribution for orbits of nonabelian semigroups on the torus.  J. Amer. Math. Soc., 24(1):231–280, 2011.
  * [5] Jean Bourgain, Elon Lindenstrauss, Philippe Michel, and Akshay Venkatesh.  Some effective results for $\times a\times b$.  Ergodic Theory Dynam. Systems, 29(6):1705–1722, 2009.
  * [6] Manfred Einsiedler and Alexander Fish.  Rigidity of measures invariant under the action of a multiplicative semigroup of polynomial growth on $\mathbb{T}$.  Ergodic Theory Dynam. Systems, 30(1):151–157, 2010.
  * [7] Harry Furstenberg.  Noncommuting random products.  Trans. Amer. Math. Soc., 108:377–428, 1963.
  * [8] Harry Furstenberg.  Disjointness in ergodic theory, minimal sets, and a problem in Diophantine approximation.  Math. Systems Theory, 1:1–49, 1967.
  * [9] Aimee S. A. Johnson.  Measures on the circle invariant under multiplication by a nonlacunary subsemigroup of the integers.  Israel J. Math., 77(1-2):211–240, 1992.
  * [10] Elon Lindenstrauss.  Dynamical Aspects of Arithmetic Combinatorics - Course Lecture Notes, Spring Semester 2013, Hebrew University.
  * [11] P. Mattila.  Geometry of Sets and Measures in Euclidean Spaces: Fractals and Rectifiability.  Cambridge Studies in Advanced Mathematics. Cambridge University Press, 1999.
  * [12] Daniel J. Rudolph.  $\times 2$ and $\times 3$ invariant measures and entropy.  Ergodic Theory Dynam. Systems, 10(2):395–406, 1990.
  * [13] B. Sudakov, E. Szemerédi, and V. H. Vu.  On a question of Erdős and Moser.  Duke Math. J., 129(1):129–155, 2005.
  * [14] Terence Tao and Van H. Vu.  Additive Combinatorics.  Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2006.

[tomg] Tom Gilat
Postdoctoral Fellow
Faculty of Engineering
Bar-Ilan University
Ramat Gan, Israel
tom.gilatbiuacil