Let $f(x)$ be a polynomial with real coefficients, and let $||\cdot||$ be the distance-from-the-nearest-integer function. It is known that for any $ \epsilon > 0 $, the set $S$ of positive integer solutions of the inequality $||f(x)|| < \epsilon$ has bounded gaps. This means that if $x\_1 < x\_2 < \ldots$ are the elements of $S$ in increasing order, then the set of differences $x\_{n+1}-x\_n$ is bounded. This is proved in "Simultaneous Diophantine Approximation and IP Sets" by Furstenberg and Weiss, Acta Arith. 1988.


I would like to know how to compute the maximum gap, i.e. the maximum of the values $ x\_{n+1}- x\_n $, given a specific polynomial and a specific value of $\epsilon$. I can do this for linear polynomials, but not for quadratics. The proof of Furstenberg and Weiss appears to be non-constructive. 


To take a particular example, what is the maximum possible gap between successive solutions of the inequality $||2^{1/2}x^2|| < .01$? Can anyone suggest a method, no matter how impractical, that would eventually lead to an answer? Could it be that, even in this particular case, no one knows how to find the maximum gap? 


Note: Experimentation suggests that the maximum gap is 627, which occurs for the first time following the solution $x=1115714$.



Wanted: A constructive version of a theorem of Furstenberg and Weiss
Dear RJS,


I think Tim Gowers is right - the problem seems too hard. Reasonably good bounds are known on (for example) the *least* $n \geq 1$ for which $\Vert n^2 \sqrt{2} \Vert \leq \epsilon$; one can find such an $n$ with $n \leq \epsilon^{-7/4 + o(1)}$. This is a result of Zaharescu [Zaharescu, A; Small values of $n^2\alpha\pmod 1$. Invent. Math. 121 (1995), no. 2, 379--388.] Zaharescu in fact obtains this result for any $\theta$ in place of $\sqrt{2}$. From a cursory glance at the paper I see that he uses the continued fraction expansion for $\theta$ and so it may be that one can slightly improve his bound in the particular case of $\sqrt{2}$.


It is an old conjecture of Heilbronn that the right bound here should be $\epsilon^{-1 + o(1)}$. I don't know off the top of my head whether any more precise conjectures have been made based on sensible heuristics either for this or for your original problem.


To get *an* explicit upper bound for your problem one can proceed quite straightforwardly using arguments due to Weyl. I don't think this is the right place to describe an argument in detail: there are several variants, and I first learnt this from a Tim Gowers course at Cambridge. See Theorem 3.10 of these notes:


<http://www.math.cmu.edu/~af1p/Teaching/AdditiveCombinatorics/notes-acnt.pdf>


If you really had to show that 627 is the answer to your specific problem, probably the best bet would be to inspect all the quadratics $n^2\sqrt{2} + \theta n + \theta'$ for $\theta,\theta'$ in some rather dense finite subset of $[0,1]^2$ and show using a computer that each takes (mod 1) a value less than 0.009999 for some $n \leq 627$. Painful!


The argument of Furstenberg and Weiss uses ergodic theory and so will not directly lead to an effective bound.


There are quite detailed conjectures about the fractional parts of $n^2\sqrt{2}$ (and other similar sequences) due to Rudnick, Sarnak and Zaharescu, essentially encoding the fact that this sequence of fractional parts is expected to behave like a Poisson process. I don't think those conjectures are likely to be helpful in your context since, taken too literally, they would seem to suggest that there are arbitrarily long intervals without a number such that $\Vert n^2 \sqrt{2} \Vert < 0.01$ - contrary to Furstenberg-Weiss.


Nonetheless let me point out a recent paper of Heath-Brown which is very interesting in connection with these matters:


<http://arxiv.org/pdf/0904.0714v1>.


One more point perhaps worthy of mention: sequences with bounded gaps are usually known as *syndetic*.


