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