Wanted: A constructive version of a theorem of Furstenberg and Weiss - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T05:54:12Z http://mathoverflow.net/feeds/question/22868 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/22868/wanted-a-constructive-version-of-a-theorem-of-furstenberg-and-weiss Wanted: A constructive version of a theorem of Furstenberg and Weiss SJR 2010-04-28T15:54:44Z 2010-04-29T00:29:42Z <p>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 <code>$\epsilon &gt; 0$</code>, the set $S$ of positive integer solutions of the inequality <code>$||f(x)|| &lt; \epsilon$</code> has bounded gaps. This means that if $x_1 &lt; x_2 &lt; \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.</p> <p>I would like to know how to compute the maximum gap, i.e. the maximum of the values <code>$x_{n+1}- x_n$</code>, 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. </p> <p>To take a particular example, what is the maximum possible gap between successive solutions of the inequality $||2^{1/2}x^2|| &lt; .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? </p> <p>Note: Experimentation suggests that the maximum gap is 627, which occurs for the first time following the solution $x=1115714$.</p> http://mathoverflow.net/questions/22868/wanted-a-constructive-version-of-a-theorem-of-furstenberg-and-weiss/22913#22913 Answer by Ben Green for Wanted: A constructive version of a theorem of Furstenberg and Weiss Ben Green 2010-04-29T00:29:42Z 2010-04-29T00:29:42Z <p>Dear RJS,</p> <p>I think Tim Gowers is right - the problem seems too hard. Reasonably good bounds are known on (for example) the <em>least</em> $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}$.</p> <p>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.</p> <p>To get <em>an</em> 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:</p> <p><a href="http://www.math.cmu.edu/~af1p/Teaching/AdditiveCombinatorics/notes-acnt.pdf" rel="nofollow">http://www.math.cmu.edu/~af1p/Teaching/AdditiveCombinatorics/notes-acnt.pdf</a></p> <p>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!</p> <p>The argument of Furstenberg and Weiss uses ergodic theory and so will not directly lead to an effective bound.</p> <p>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 &lt; 0.01$ - contrary to Furstenberg-Weiss.</p> <p>Nonetheless let me point out a recent paper of Heath-Brown which is very interesting in connection with these matters:</p> <p><a href="http://arxiv.org/pdf/0904.0714v1" rel="nofollow">http://arxiv.org/pdf/0904.0714v1</a>.</p> <p>One more point perhaps worthy of mention: sequences with bounded gaps are usually known as <em>syndetic</em>.</p>