You are currently browsing the tag archive for the ‘Diophantine approximation’ tag.

I’ve just uploaded to the arXiv my paper “Some remarks on the lonely runner conjecture“, submitted to Contributions to discrete mathematics. I had blogged about the lonely runner conjecture in this previous blog post, and I returned to the problem recently to see if I could obtain anything further. The results obtained were more modest than I had hoped, but they did at least seem to indicate a potential strategy to make further progress on the problem, and also highlight some of the difficulties of the problem.

One can rephrase the lonely runner conjecture as the following covering problem. Given any integer “velocity” ${v}$ and radius ${0 < \delta < 1/2}$, define the Bohr set ${B(v,\delta)}$ to be the subset of the unit circle ${{\bf R}/{\bf Z}}$ given by the formula

$\displaystyle B(v,\delta) := \{ t \in {\bf R}/{\bf Z}: \|vt\| \leq \delta \},$

where ${\|x\|}$ denotes the distance of ${x}$ to the nearest integer. Thus, for ${v}$ positive, ${B(v,\delta)}$ is simply the union of the ${v}$ intervals ${[\frac{a-\delta}{v}, \frac{a+\delta}{v}]}$ for ${a=0,\dots,v-1}$, projected onto the unit circle ${{\bf R}/{\bf Z}}$; in the language of the usual formulation of the lonely runner conjecture, ${B(v,\delta)}$ represents those times in which a runner moving at speed ${v}$ returns to within ${\delta}$ of his or her starting position. For any non-zero integers ${v_1,\dots,v_n}$, let ${\delta(v_1,\dots,v_n)}$ be the smallest radius ${\delta}$ such that the ${n}$ Bohr sets ${B(v_1,\delta),\dots,B(v_n,\delta)}$ cover the unit circle:

$\displaystyle {\bf R}/{\bf Z} = \bigcup_{i=1}^n B(v_i,\delta). \ \ \ \ \ (1)$

Then define ${\delta_n}$ to be the smallest value of ${\delta(v_1,\dots,v_n)}$, as ${v_1,\dots,v_n}$ ranges over tuples of distinct non-zero integers. The Dirichlet approximation theorem quickly gives that

$\displaystyle \delta(1,\dots,n) = \frac{1}{n+1}$

and hence

$\displaystyle \delta_n \leq \frac{1}{n+1}$

for any ${n \geq 1}$. The lonely runner conjecture is equivalent to the assertion that this bound is in fact optimal:

Conjecture 1 (Lonely runner conjecture) For any ${n \geq 1}$, one has ${\delta_n = \frac{1}{n+1}}$.

This conjecture is currently known for ${n \leq 6}$ (see this paper of Barajas and Serra), but remains open for higher ${n}$.

It is natural to try to attack the problem by establishing lower bounds on the quantity ${\delta_n}$. We have the following “trivial” bound, that gets within a factor of two of the conjecture:

Proposition 2 (Trivial bound) For any ${n \geq 1}$, one has ${\delta_n \geq \frac{1}{2n}}$.

Proof: It is not difficult to see that for any non-zero velocity ${v}$ and any ${0 < \delta < 1/2}$, the Bohr set ${B(v,\delta)}$ has Lebesgue measure ${m(B(v,\delta)) = 2\delta}$. In particular, by the union bound

$\displaystyle m(\bigcup_{i=1}^n B(v_i,\delta)) \leq \sum_{i=1}^n m(B(v_i,\delta)) \ \ \ \ \ (2)$

we see that the covering (1) is only possible if ${1 \leq 2 n \delta}$, giving the claim. $\Box$

So, in some sense, all the difficulty is coming from the need to improve upon the trivial union bound (2) by a factor of two.

Despite the crudeness of the union bound (2), it has proven surprisingly hard to make substantial improvements on the trivial bound ${\delta_n \geq \frac{1}{2n}}$. In 1994, Chen obtained the slight improvement

$\displaystyle \delta_n \geq \frac{1}{2n - 1 + \frac{1}{2n-3}}$

which was improved a little by Chen and Cusick in 1999 to

$\displaystyle \delta_n \geq \frac{1}{2n-3}$

when ${2n-3}$ was prime. In a recent paper of Perarnau and Serra, the bound

$\displaystyle \delta_n \geq \frac{1}{2n-2+o(1)}$

was obtained for arbitrary ${n}$. These bounds only improve upon the trivial bound by a multiplicative factor of ${1+O(1/n)}$. Heuristically, one reason for this is as follows. The union bound (2) would of course be sharp if the Bohr sets ${B(v_i,\delta)}$ were all disjoint. Strictly speaking, such disjointness is not possible, because all the Bohr sets ${B(v_i,\delta)}$ have to contain the origin as an interior point. However, it is possible to come up with a large number of Bohr sets ${B(v_i,\delta)}$ which are almost disjoint. For instance, suppose that we had velocities ${v_1,\dots,v_s}$ that were all prime numbers between ${n/4}$ and ${n/2}$, and that ${\delta}$ was equal to ${\delta_n}$ (and in particular was between ${1/2n}$ and ${1/(n+1)}$. Then each set ${B(v_i,\delta)}$ can be split into a “kernel” interval ${[-\frac{\delta}{v_i}, \frac{\delta}{v_i}]}$, together with the “petal” intervals ${\bigcup_{a=1}^{v_i-1} [\frac{a-\delta}{v_i}, \frac{a+\delta}{v_i}]}$. Roughly speaking, as the prime ${v_i}$ varies, the kernel interval stays more or less fixed, but the petal intervals range over disjoint sets, and from this it is not difficult to show that

$\displaystyle m(\bigcup_{i=1}^s B(v_i,\delta)) = (1-O(\frac{1}{n})) \sum_{i=1}^s m(B(v_i,\delta)),$

so that the union bound is within a multiplicative factor of ${1+O(\frac{1}{n})}$ of the truth in this case.

This does not imply that ${\delta_n}$ is within a multiplicative factor of ${1+O(1/n)}$ of ${\frac{1}{2n}}$, though, because there are not enough primes between ${n/4}$ and ${n/2}$ to assign to ${n}$ distinct velocities; indeed, by the prime number theorem, there are only about ${\frac{n}{4\log n}}$ such velocities that could be assigned to a prime. So, while the union bound could be close to tight for up to ${\asymp n/\log n}$ Bohr sets, the above counterexamples don’t exclude improvements to the union bound for larger collections of Bohr sets. Following this train of thought, I was able to obtain a logarithmic improvement to previous lower bounds:

Theorem 3 For sufficiently large ${n}$, one has ${\delta_n \geq \frac{1}{2n} + \frac{c \log n}{n^2 (\log\log n)^2}}$ for some absolute constant ${c>0}$.

The factors of ${\log\log n}$ in the denominator are for technical reasons and might perhaps be removable by a more careful argument. However it seems difficult to adapt the methods to improve the ${\log n}$ in the numerator, basically because of the obstruction provided by the near-counterexample discussed above.

Roughly speaking, the idea of the proof of this theorem is as follows. If we have the covering (1) for ${\delta}$ very close to ${1/2n}$, then the multiplicity function ${\sum_{i=1}^n 1_{B(v_i,\delta)}}$ will then be mostly equal to ${1}$, but occasionally be larger than ${1}$. On the other hand, one can compute that the ${L^2}$ norm of this multiplicity function is significantly larger than ${1}$ (in fact it is at least ${(3/2-o(1))^{1/2}}$). Because of this, the ${L^3}$ norm must be very large, which means that the triple intersections ${B(v_i,\delta) \cap B(v_j,\delta) \cap B(v_k,\delta)}$ must be quite large for many triples ${(i,j,k)}$. Using some basic Fourier analysis and additive combinatorics, one can deduce from this that the velocities ${v_1,\dots,v_n}$ must have a large structured component, in the sense that there exists an arithmetic progression of length ${\asymp n}$ that contains ${\asymp n}$ of these velocities. For simplicity let us take the arithmetic progression to be ${\{1,\dots,n\}}$, thus ${\asymp n}$ of the velocities ${v_1,\dots,v_n}$ lie in ${\{1,\dots,n\}}$. In particular, from the prime number theorem, most of these velocities will not be prime, and will in fact likely have a “medium-sized” prime factor (in the precise form of the argument, “medium-sized” is defined to be “between ${\log^{10} n}$ and ${n^{1/10}}$“). Using these medium-sized prime factors, one can show that many of the ${B(v_i,\delta)}$ will have quite a large overlap with many of the other ${B(v_j,\delta)}$, and this can be used after some elementary arguments to obtain a more noticeable improvement on the union bound (2) than was obtained previously.

A modification of the above argument also allows for the improved estimate

$\displaystyle \delta(v_1,\dots,v_n) \geq \frac{1+c-o(1)}{2n} \ \ \ \ \ (3)$

if one knows that all of the velocities ${v_1,\dots,v_n}$ are of size ${O(n)}$.

In my previous blog post, I showed that in order to prove the lonely runner conjecture, it suffices to do so under the additional assumption that all of the velocities ${v_1,\dots,v_n}$ are of size ${O(n^{O(n^2)})}$; I reproduce this argument (slightly cleaned up for publication) in the current preprint. There is unfortunately a huge gap between ${O(n)}$ and ${O(n^{O(n^2)})}$, so the above bound (3) does not immediately give any new bounds for ${\delta_n}$. However, one could perhaps try to start attacking the lonely runner conjecture by increasing the range ${O(n)}$ for which one has good results, and by decreasing the range ${O(n^{O(n^2)})}$ that one can reduce to. For instance, in the current preprint I give an elementary argument (using a certain amount of case-checking) that shows that the lonely runner bound

$\displaystyle \delta(v_1,\dots,v_n) \geq \frac{1}{n+1} \ \ \ \ \ (4)$

holds if all the velocities ${v_1,\dots,v_n}$ are assumed to lie between ${1}$ and ${1.2 n}$. This upper threshold of ${1.2 n}$ is only a tiny improvement over the trivial threshold of ${n}$, but it seems to be an interesting sub-problem of the lonely runner conjecture to increase this threshold further. One key target would be to get up to ${2n}$, as there are actually a number of ${n}$-tuples ${(v_1,\dots,v_n)}$ in this range for which (4) holds with equality. The Dirichlet approximation theorem of course gives the tuple ${(1,2,\dots,n)}$, but there is also the double ${(2,4,\dots,2n)}$ of this tuple, and furthermore there is an additional construction of Goddyn and Wong that gives some further examples such as ${(1,2,3,4,5,7,12)}$, or more generally one can start with the standard tuple ${(1,\dots,n)}$ and accelerate one of the velocities ${v}$ to ${2v}$; this turns out to work as long as ${v}$ shares a common factor with every integer between ${n-v+1}$ and ${2n-2v+1}$. There are a few more examples of this type in the paper of Goddyn and Wong, but all of them can be placed in an arithmetic progression of length ${O(n \log n)}$ at most, so if one were very optimistic, one could perhaps envision a strategy in which the upper bound of ${O(n^{O(n^2)})}$ mentioned earlier was reduced all the way to something like ${O( n \log n )}$, and then a separate argument deployed to treat this remaining case, perhaps isolating the constructions of Goddyn and Wong (and possible variants thereof) as the only extreme cases.

Klaus Roth, who made fundamental contributions to analytic number theory, died this Tuesday, aged 90.

I never met or communicated with Roth personally, but was certainly influenced by his work; he wrote relatively few papers, but they tended to have outsized impact. For instance, he was one of the key people (together with Bombieri) to work on simplifying and generalising the large sieve, taking it from the technically formidable original formulation of Linnik and Rényi to the clean and general almost orthogonality principle that we have today (discussed for instance in these lecture notes of mine). The paper of Roth that had the most impact on my own personal work was his three-page paper proving what is now known as Roth’s theorem on arithmetic progressions:

Theorem 1 (Roth’s theorem on arithmetic progressions) Let ${A}$ be a set of natural numbers of positive upper density (thus ${\limsup_{N \rightarrow\infty} |A \cap \{1,\dots,N\}|/N > 0}$). Then ${A}$ contains infinitely many arithmetic progressions ${a,a+r,a+2r}$ of length three (with ${r}$ non-zero of course).

At the heart of Roth’s elegant argument was the following (surprising at the time) dichotomy: if ${A}$ had some moderately large density within some arithmetic progression ${P}$, either one could use Fourier-analytic methods to detect the presence of an arithmetic progression of length three inside ${A \cap P}$, or else one could locate a long subprogression ${P'}$ of ${P}$ on which ${A}$ had increased density. Iterating this dichotomy by an argument now known as the density increment argument, one eventually obtains Roth’s theorem, no matter which side of the dichotomy actually holds. This argument (and the many descendants of it), based on various “dichotomies between structure and randomness”, became essential in many other results of this type, most famously perhaps in Szemerédi’s proof of his celebrated theorem on arithmetic progressions that generalised Roth’s theorem to progressions of arbitrary length. More recently, my recent work on the Chowla and Elliott conjectures that was a crucial component of the solution of the Erdös discrepancy problem, relies on an entropy decrement argument which was directly inspired by the density increment argument of Roth.

The Erdös discrepancy problem also is connected with another well known theorem of Roth:

Theorem 2 (Roth’s discrepancy theorem for arithmetic progressions) Let ${f(1),\dots,f(n)}$ be a sequence in ${\{-1,+1\}}$. Then there exists an arithmetic progression ${a+r, a+2r, \dots, a+kr}$ in ${\{1,\dots,n\}}$ with ${r}$ positive such that

$\displaystyle |\sum_{j=1}^k f(a+jr)| \geq c n^{1/4}$

for an absolute constant ${c>0}$.

In fact, Roth proved a stronger estimate regarding mean square discrepancy, which I am not writing down here; as with the Roth theorem in arithmetic progressions, his proof was short and Fourier-analytic in nature (although non-Fourier-analytic proofs have since been found, for instance the semidefinite programming proof of Lovasz). The exponent ${1/4}$ is known to be sharp (a result of Matousek and Spencer).

As a particular corollary of the above theorem, for an infinite sequence ${f(1), f(2), \dots}$ of signs, the sums ${|\sum_{j=1}^k f(a+jr)|}$ are unbounded in ${a,r,k}$. The Erdös discrepancy problem asks whether the same statement holds when ${a}$ is restricted to be zero. (Roth also established discrepancy theorems for other sets, such as rectangles, which will not be discussed here.)

Finally, one has to mention Roth’s most famous result, cited for instance in his Fields medal citation:

Theorem 3 (Roth’s theorem on Diophantine approximation) Let ${\alpha}$ be an irrational algebraic number. Then for any ${\varepsilon > 0}$ there is a quantity ${c_{\alpha,\varepsilon}}$ such that

$\displaystyle |\alpha - \frac{a}{q}| > \frac{c_{\alpha,\varepsilon}}{q^{2+\varepsilon}}.$

From the Dirichlet approximation theorem (or from the theory of continued fractions) we know that the exponent ${2+\varepsilon}$ in the denominator cannot be reduced to ${2}$ or below. A classical and easy theorem of Liouville gives the claim with the exponent ${2+\varepsilon}$ replaced by the degree of the algebraic number ${\alpha}$; work of Thue and Siegel reduced this exponent, but Roth was the one who obtained the near-optimal result. An important point is that the constant ${c_{\alpha,\varepsilon}}$ is ineffective – it is a major open problem in Diophantine approximation to produce any bound significantly stronger than Liouville’s theorem with effective constants. This is because the proof of Roth’s theorem does not exclude any single rational ${a/q}$ from being close to ${\alpha}$, but instead very ingeniously shows that one cannot have two different rationals ${a/q}$, ${a'/q'}$ that are unusually close to ${\alpha}$, even when the denominators ${q,q'}$ are very different in size. (I refer to this sort of argument as a “dueling conspiracies” argument; they are strangely prevalent throughout analytic number theory.)

In his final lecture, Prof. Margulis talked about some of the ideas around the theory of unipotent flows on homogeneous spaces, culminating in the orbit closure, equidsitribution, and measure classification theorems of Ratner in the subject.  Margulis also discussed the application to metric theory of Diophantine approximation which was not covered in the preceding lecture.