0
$\begingroup$

I could not come up with a rigorous proof of the following fact, I'd be thankful if you could help me with this ( elementary) question.

Consider a partition $\Gamma_m$ of $[0,1)$ by sets $P_k=[\frac{k-1}{m},\frac{k}{m})$, $k=1,\ldots,m.$ Suppose $q \in P_k$ be a nonzero irrational number. For each $l\in\{1,\ldots,m\}$, Prove that there exists some $n\in \mathbb{N}$ such that $nq (mod \ 1) \in P_l$.

$\endgroup$
1
$\begingroup$

In fact, more is true: For irrational $q$, the sequence $\{nq\}=nq \bmod 1$ is uniformly distributed on $[0, 1)$, see for example equidistribution theorem here.

The result you wish to show is much weaker, and can easily be achieved with elementary means. Proof below.


Lemma: Let $q$ be irrational. Then $\exists n \in \mathbb{Z}^+$ s.t. either $0<\{nq\}<\frac{1}{m}$ or $1-\frac{1}{m}<\{nq\}<1$.

Proof: Consider the $m+1$ real numbers $0=\{0q\}, \{q\}, \{2q\}, \ldots , \{mq\} \in [0, 1)$. They are pairwise distinct. (otherwise $q$ would be rational, a contradiction) By Pigeonhole Principle applied to $P_0, \ldots P_{m-1}$, $\exists i$ s.t. $P_i$ contains two of them, which we call $\{uq\}$ and $\{vq\}$, $u<v$. Then either $\{vq\}>\{uq\}$, so $0<\{(v-u)q\}<\frac{1}{m}$, or $\{vq\}<\{uq\}$, so $1-\frac{1}{m}<\{(v-u)q\}<1$. In any case we may take $n=v-u$.


We proceed. Pick $n$ as in the lemma. If $0<\{nq\}<\frac{1}{m}$, then $\exists j \in \mathbb{Z}^+$ s.t. $0 \leq \frac{k-1}{m}<j\{nq\}<\frac{k}{m} \leq 1$, i.e. $\{(nj)q\} \in P_k$.

If $1-\frac{1}{m}<\{nq\}<1$, then $0<1-\{nq\}<\frac{1}{m}$, so $\exists j \in \mathbb{Z}^+$ s.t. $0 \leq \frac{m-k}{m}<j(1-\{nq\})<\frac{m-k+1}{m} \leq 1$, i.e. $j-1+\frac{k-1}{m}<j\{nq\}<j-1+\frac{k}{m}$, i.e. $\{(nj)q\} \in P_k$.

Thus we are done.


N.B. The equidistribution theorem may also be proved via elementary means, e.g. by Pigeonhole Principle; see here

$\endgroup$
0
$\begingroup$

I don't think it's true as stated anyway. Let m = 3, so the partition is [0,1/3), [1/3, 2/3), and [2/3, 1), and q = 1/2. It is true if 0 < q <1/m, because then q is less than the length of the intervals of the partition.

$\endgroup$
  • $\begingroup$ sorry, $q$ must be irrational :-/ $\endgroup$ – the8thone May 19 '14 at 3:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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