You are currently browsing the tag archive for the ‘generalised arithmetic progressions’ tag.

Let ${\alpha \in {\bf R}/{\bf Z}}$ be an element of the unit circle, let ${N \geq 1}$, and let ${\rho > 0}$. We define the (rank one) Bohr set ${B_N(\alpha;\rho)}$ to be the set

$\displaystyle B_N(\alpha;\rho) := \{ n \in {\bf Z}: -N \leq n \leq N; \|n\alpha\|_{{\bf R}/{\bf Z}} \leq \rho \}$

where ${\|x\|_{{\bf R}/{\bf Z}}}$ is the distance to the origin in the unit circle (or equivalently, the distance to the nearest integer, after lifting up to ${{\bf R}}$). These sets play an important role in additive combinatorics and in additive number theory. For instance, they arise naturally when applying the circle method, because Bohr sets describe the oscillation of exponential phases such as ${n \mapsto e^{2\pi i n \alpha}}$.

Observe that Bohr sets enjoy the doubling property

$\displaystyle B_N(\alpha;\rho) + B_N(\alpha;\rho) \subset B_{2N}(\alpha;2\rho),$

thus doubling the Bohr set doubles both the length parameter ${N}$ and the radius parameter ${\rho}$. As such, these Bohr sets resemble two-dimensional balls (or boxes). Indeed, one can view ${B_N(\alpha;\rho)}$ as the preimage of the two-dimensional box ${[-1,1] \times [-\rho,\rho] \subset {\bf R} \times {\bf R}/{\bf Z}}$ under the homomorphism ${n \mapsto (n/N, \alpha n \hbox{ mod } 1)}$.

Another class of finite set with two-dimensional behaviour is the class of (rank two) generalised arithmetic progressions

$\displaystyle P( a_1,a_2; N_1,N_2 ) := \{ n_1 a_1 + n_2 a_2: n_1,n_2 \in {\bf Z}; |n_1| \leq N_1, |n_2| \leq N_2 \}$

with ${a_1,a_2 \in {\bf Z}}$ and ${N_1,N_2 > 0}$ Indeed, we have

$\displaystyle P( a_1,a_2; N_1,N_2 ) + P( a_1,a_2; N_1,N_2 ) \subset P( a_1,a_2; 2N_1, 2N_2 )$

and so we see, as with the Bohr set, that doubling the generalised arithmetic progressions doubles the two defining parameters of that progression.

More generally, there is an analogy between rank ${r}$ Bohr sets

$\displaystyle B_N(\alpha_1,\ldots,\alpha_r; \rho_1,\ldots,\rho_r) := \{ n \in {\bf Z}: -N \leq n \leq N; \|n\alpha_i\|_{{\bf R}/{\bf Z}} \leq \rho_i$

$\displaystyle \hbox{ for all } 1 \leq i \leq r \}$

and the rank ${r+1}$ generalised arithmetic progressions

$\displaystyle P( a_1,\ldots,a_{r+1}; N_1,\ldots,N_{r+1} ) := \{ n_1 a_1 + \ldots + n_{r+1} a_{r+1}:$

$\displaystyle n_1,\ldots,n_{r+1} \in {\bf Z}; |n_i| \leq N_i \hbox{ for all } 1 \leq i \leq r+1 \}.$

One of the aims of additive combinatorics is to formalise analogies such as the one given above. By using some arguments from the geometry of numbers, for instance, one can show that for any rank ${r}$ Bohr set ${B_N(\alpha_1,\ldots,\alpha_r;\rho_1,\ldots,\rho_r)}$, there is a rank ${r+1}$ generalised arithmetic progression ${P(a_1,\ldots,a_{r+1}; N_1,\ldots,N_{r+1})}$ for which one has the containments

$\displaystyle B_N(\alpha_1,\ldots,\alpha_r;\epsilon \rho_1,\ldots,\epsilon \rho_r) \subset P(a_1,\ldots,a_{r+1}; N_1,\ldots,N_{r+1})$

$\displaystyle \subset B_N(\alpha_1,\ldots,\alpha_r;\rho_1,\ldots,\rho_r)$

for some explicit ${\epsilon>0}$ depending only on ${r}$ (in fact one can take ${\epsilon = (r+1)^{-2(r+1)}}$); this is (a slight modification of) Lemma 4.22 of my book with Van Vu.

In the special case when ${r=1}$, one can make a significantly more detailed description of the link between rank one Bohr sets and rank two generalised arithmetic progressions, by using the classical theory of continued fractions, which among other things gives a fairly precise formula for the generators ${a_1,a_2}$ and lengths ${N_1,N_2}$ of the generalised arithmetic progression associated to a rank one Bohr set ${B_N(\alpha;\rho)}$. While this connection is already implicit in the continued fraction literature (for instance, in the classic text of Hardy and Wright), I thought it would be a good exercise to work it out explicitly and write it up, which I will do below the fold.

It is unfortunate that the theory of continued fractions is restricted to the rank one setting (it relies very heavily on the total ordering of one-dimensional sets such as ${{\bf Z}}$ or ${{\bf R}}$). A higher rank version of the theory could potentially help with questions such as the Littlewood conjecture, which remains open despite a substantial amount of effort and partial progress on the problem. At the end of this post I discuss how one can use the rank one theory to rephrase the Littlewood conjecture as a conjecture about a doubly indexed family of rank four progressions, which can be used to heuristically justify why this conjecture should be true, but does not otherwise seem to shed much light on the problem.

Van Vu and I have just uploaded to the arXiv our preprint “A sharp inverse Littlewood-Offord theorem“, which we have submitted to Random Structures and Algorithms.  This paper gives a solution to the (inverse) Littlewood-Offord problem of understanding when random walks are concentrated in the case when the concentration is of polynomial size in the length $n$ of the walk; our description is sharp up to epsilon powers of $n$.  The theory of inverse Littlewood-Offord problems and related topics has been of importance in recent developments in the spectral theory of discrete random matrices (e.g. a “robust” variant of these theorems was crucial in our work on the circular law).

For simplicity I will restrict attention to the Bernoulli random walk.  Given $n$ real numbers $v_1,\ldots,v_n$, one can form the random variable

$S := \epsilon_1 v_1 + \ldots + \epsilon_n v_n$

where $\epsilon_1,\ldots,\epsilon_n \in \{-1,+1\}$ are iid random signs (with either sign +1, -1 chosen with probability 1/2).  This is a discrete random variable which typically takes $2^n$ values.  However, if there are various arithmetic relations between the step sizes $v_1,\ldots,v_n$, then many of the $2^n$ possible sums collide, and certain values may then arise with much higher probability.  To measure this, define the concentration probability $p(v_1,\ldots,v_n)$ by the formula

$p(v_1,\ldots,v_n) = \sup_x {\Bbb P}(S=x)$.

Intuitively, this probability measures the amount of additive structure present between the $v_1,\ldots,v_n$.  There are two (opposing) problems in the subject:

• (Forward Littlewood-Offord problem) Given some structural assumptions on $v_1,\ldots,v_n$, what bounds can one place on $p(v_1,\ldots,v_n)$?
• (Inverse Littlewood-Offord problem) Given some bounds on $p(v_1,\ldots,v_n)$, what structural assumptions can one then conclude about $v_1,\ldots,v_n$?

Ideally one would like answers to both of these problems which come close to inverting each other, and this is the guiding motivation for our paper.