MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Can please someone help me with the following problem.

Say we have a sequence $nx \; \mathrm{mod} \; 1$, where $n$ is a whole number and $x$ is irrational.

Now I need to solve the inequality $nx \; \mathrm{mod} \; 1 < v$ with respect to $n$, for some given small $v$.

According to Equidistribution Theorem, this sequence is uniformly distributed on (0,1). And thus we definitely know that there is an infinite number of those $n$'s. But what can we say about these solutions themselves? In particular, I need to know if the distance between two consequtive solutions is limited or not.

It seems to be true to me, but maybe I'm missing something... and can't figure out a hard proof.

share|cite|improve this question
Try applying pigeonhole principle you should be able to get what you are looking for. Its also called Dirichlet's Box Principle. – Vagabond Dec 6 '11 at 8:39
up vote 1 down vote accepted

Here is a quick solution to your problem. Fix a positive integer $q$ such that $\{ qx \} <v $, and then fix a positive integer $s$ such that $1<s\{qx\}$. Now assume that $n$ is any integer satisfying $\{nx\}<v$. Let $r$ be the smallest positive integer such that $1<\{nx\}+r\{qx\}$. Clearly, $r\leq s$. In addition, $\{nx\}+r\{qx\}<1+\{qx\}<1+v$, hence in fact $\{(n+rq)x\}<v$. We showed that the gaps between the solutions of $\{nx\}<v$ is at most $sq$.

share|cite|improve this answer

Basically you don't need the Weyl's Equi. theorem, it's enough to use Kronecker's lemma about density.

If you want to use measure theory, then your question follows from any ergodic theorem you would like + the fact that the system is uniquely ergodic.

If you want, you can use the theory of continued fractions to explicitly compute such a return time rate.

In the Furstenberg terminology, you want to say that the topological dynamical system of the rotation by $x$ is uniformly recurrent.

If you add nx to itself about ~ 1/(nx) times, you will end up being roughly close to your original nx (this can be made more precise using continued fractions). It is even almost periodic, you always miss the interval (0,v) by at-most one rotation. Hence the set of return times of the orbit of $0$ under the rotation by $x$ map is so-called syndethic set, means it has bounded gaps.

share|cite|improve this answer
Thank you very much for your answer! Kronecker's theorem seems very related and thanks for other useful keywords as well. I should go through it in detail to be sure, but it seems the problem is solved. – Sasha Dec 6 '11 at 8:31

The sequence of fractional parts $\{ nx \}$ with $n \in \mathbb{Z}$ is dense in the reals. First we can divide $[0,1]$ into intervals $[0,1/n]\cup [1/n,2/n]\cup \dots \cup [1-1/n,1]$.

Two numbers are in the same interval $n\alpha, n\beta \in [k/n, k/n+1/n]$ for some $0 < a < b < n+2$ and we get $n(b-a) \in [0,1/n]$. We get evenly spaced values of $\{ n x\}$ for arbitrarily small spacing.

This is more or less Kronecker Approximation Theorem with a hint of why Weyl Equidistribution might be true.

When is $0 < \{ nx \} < x$, for $0 < x < 1$? This happens when $n = \lfloor 1/x \rfloor$. Then $$ 0 < \{ nx \} = \lfloor 1/x \rfloor x - \lfloor \lfloor 1/x \rfloor x \rfloor < x $$ But the floor-functions do simplify $ \lfloor \lfloor 1/x \rfloor x \rfloor = 1$. Dividing both sides by $x$, the rotation is rescaled: $$ 0 < \frac{\{ nx \}}{x } = \{ 1/x \} < 1 $$

This is the ``renormalization" of the Euclidean algorithm in dynamics/number theory.

share|cite|improve this answer

Your question is a special case of the question that I answered in complete detail here, where I gave an explicit fast algorithm that can be used to compute the return times to any interval. Your problem is essentially the case of $\alpha =0$, which is especially easy to compute. The integers you are asking for are very evenly spaced- a generalized arithmetic progression with two alternating moduli. So yes, the distance between consecutive integers that do what you want is bounded.

share|cite|improve this answer
@Alan, one should be a bit more careful playing with the Ostrowski expansion as you mentioned it (or the cutting sequence for the rotation, as dynamicist will call it). The cutting sequence alternates between the sides of the zero in the torus, and therefore you get estimation for the absolute value of nx. If you would like to get only estimation about the return times to the positive side, one should add one to every second element in the cutting sequence. – Asaf Dec 6 '11 at 19:56
@Asaf This requires no significant modification to the post that I already made. If you want a one sided approximation then you use the pieces of the Ostrowski expansion corresponding to either the odd or even convergents. – Alan Haynes Dec 7 '11 at 8:17

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.