You are currently browsing the tag archive for the ‘generalised arithmetic progressions’ tag.
Let be an element of the unit circle, let , and let . We define the (rank one) Bohr set to be the set
where is the distance to the origin in the unit circle (or equivalently, the distance to the nearest integer, after lifting up to ). 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 .
Observe that Bohr sets enjoy the doubling property
thus doubling the Bohr set doubles both the length parameter and the radius parameter . As such, these Bohr sets resemble two-dimensional balls (or boxes). Indeed, one can view as the preimage of the two-dimensional box under the homomorphism .
Another class of finite set with two-dimensional behaviour is the class of (rank two) generalised arithmetic progressions
with and Indeed, we have
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 Bohr sets
and the rank generalised arithmetic progressions
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 Bohr set , there is a rank generalised arithmetic progression for which one has the containments
for some explicit depending only on (in fact one can take ); this is (a slight modification of) Lemma 4.22 of my book with Van Vu.
In the special case when , 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 and lengths of the generalised arithmetic progression associated to a rank one Bohr set . 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 or ). 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 of the walk; our description is sharp up to epsilon powers of . 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 real numbers , one can form the random variable
where are iid random signs (with either sign +1, -1 chosen with probability 1/2). This is a discrete random variable which typically takes values. However, if there are various arithmetic relations between the step sizes , then many of the possible sums collide, and certain values may then arise with much higher probability. To measure this, define the concentration probability by the formula
Intuitively, this probability measures the amount of additive structure present between the . There are two (opposing) problems in the subject:
- (Forward Littlewood-Offord problem) Given some structural assumptions on , what bounds can one place on ?
- (Inverse Littlewood-Offord problem) Given some bounds on , what structural assumptions can one then conclude about ?
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.