Wanted: A constructive version of a theorem of Furstenberg and Weiss

2010-04-28T15:54:44Z

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$.

Answer by Ben Green for Wanted: A constructive version of a theorem of Furstenberg and Weiss

2010-04-29T00:29:42Z

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.

Wanted: A constructive version of a theorem of Furstenberg and Weiss - MathOverflow

Wanted: A constructive version of a theorem of Furstenberg and Weiss

Answer by Ben Green for Wanted: A constructive version of a theorem of Furstenberg and Weiss