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.

Read the rest of this entry »









Read the rest of this entry »


RSS Google+ feed


Get every new post delivered to your Inbox.

Join 4,725 other followers