# Density of positive multiples of an irrational number

Let $x$ be irrational. Use $\{r\}$ to denote the fractional part of $r$: $\{r\} = r - \lfloor r \rfloor$. I know how to prove that the following set is dense in $[0,1]$: $$\{\{nx\} : n \in \mathbb{Z}\}.$$ But what about $$\{\{nx\} : n \in \mathbb{N}\}?$$ Any proof that I’ve seen of the first one fails for the second one.

A minor modification of the pigeonhole argument works. Let $m$ be any positive integer. By the pigeonhole principle there must be distinct $i,j\in\{1,\dots,m+1\}$ and $k\in\{0,\dots,m-1\}$ such that $\frac{k}m\le\{ix\},\{jx\}<\frac{k+1}m$; clearly $\{|(j-i)x|\}<\frac1m$. Let $\ell$ be the largest positive integer such that $\ell\{|(j-i)x|\}<1$, let $A_m=\{n|j-i|x:0\le n\le\ell\}$, and let $D_m=\big\{\{y\}:y\in A_m\big\}$.

If $x>0$, every point of $[0,1)$ is clearly within $\frac1m$ of $A_m=D_m$. If $x<0$, then

$$D_m=\{1-|y|:y\in A_m\}\;,$$

so every point of $[0,1)$ is again within $\frac1m$ of the set $D_m$. Since $D_m\subseteq\big\{\{nx\}:n\in\Bbb N\big\}$, we’re done.

• I hope you don't mind how close my answer is to yours, but I had written an answer for someone in chat and was going to post it elsewhere, then saw this question was a better fit.
– robjohn
Jul 20, 2021 at 20:58
• @robjohn: No problem: someone may benefit from the greater detail. Jul 21, 2021 at 2:39
• Can you give more details why if $x>0$ then every ppint of $[0,1)$ is clearly within $1/m$ of $A_m$.
– ZFR
Jul 30, 2021 at 2:29
• @ZFR: Adjacent points of $A_m$ are less than $\frac1m$ apart. Every point of $[0,1)$ is either equal to one of these points, between two adjacent ones, or between $\ell\{|(j-i)x|\}$ and $1$ and hence less than $\frac1m$ from some point of $A_m$. Jul 31, 2021 at 22:00

Here is a proof where the second statement follows from the first with a minor step. I wrote this answer for another question, but then I saw it fit here better, other than being along very similar lines to Brian M. Scott's answer.

Let $$r$$ be irrational. Choose an arbitrary $$n\in\mathbb{N}$$. Partition $$[0,1)$$ into $$n$$ subintervals $$\left\{I_k=\left[\frac{k-1}n,\frac kn\right):1\le k\le n\right\}\tag1$$ Consider the discrete set $$\{\{kr\}:0\le k\le n\}\subset[0,1)$$. There are $$n+1$$ elements in this set, so two of them must lie in the same subinterval. That means that we have $$k_1\ne k_2$$ so that $$\{(k_1-k_2)r\}\in\left(0,\frac1n\right)$$, we leave $$0$$ out of the interval because $$r$$ is irrational.

Let $$m=\left\lfloor\frac1{\{(k_1-k_2)r\}}\right\rfloor$$, then because $$m$$ is the greatest integer not greater than $$\frac1{\{(k_1-k_2)r\}}$$, $$m\{(k_1-k_2)r\}\!\!\overset{\substack{r\not\in\mathbb{Q}\\\downarrow}}{\lt}\!\!1\lt(m+1)\{(k_1-k_2)r\}\tag2$$ which implies that $$\{m(k_1-k_2)r\}=m\{(k_1-k_2)r\}\in\left(\frac{n-1}n,1\right)$$.

Since $$\{(k_1-k_2)r\}\in\left(0,\frac1n\right)$$, if $$j\{(k_1-k_2)r\}\in I_k$$, then $$(j+1)\{(k_1-k_2)r\}\in I_k\cup I_{k+1}$$; that is, $$\{j(k_1-k_2)r\}=j\{(k_1-k_2)r\}$$ cannot skip over any of the $$I_k$$. Therefore, $$\left\{\{j(k_1-k_2)r\}:1\le j\le m\vphantom{\frac12}\right\}\tag3$$ must have at least one element in each $$I_k$$ for $$1\le k\le n$$.

The only problem is that we don't know that $$k_1-k_2\gt0$$. However, this is not a problem since $$\{j(k_1-k_2)r\}\in I_k\iff\{j(k_2-k_1)r\}\in I_{n+1-k}$$. Therefore, $$\left\{\{j(k_2-k_1)r\}:1\le j\le m\vphantom{\frac12}\right\}\tag4$$ must also have at least one element in each $$I_k$$ for $$1\le k\le n$$.

Since $$n$$ was arbitrary, we have shown that $$\left\{\mathbb{N}r\right\}$$ is dense in $$[0,1]$$.

• Thanks a lot professor Robjohn for answering my question. I was having lot of difficulty understanding $k_2\gt k_1$ case. It all makes sense to me now. Many thanks :) I would only like to add this little more detail for statement just before $(3)$ in the hope that it will benefit those who visit this great answer in future: Suppose on the contrary that for some $k<n$, the subinterval $(\frac{k-1}n, \frac kn )$ doesn't contain any element of the set $T=\{ j\{(k_2-k_1)r\}: 1\le j\le m\}$. (Contd.)
– Koro
Jul 21, 2021 at 3:55
• (Contd.) Note that $T_L=\{j: j\{(k_2-k_1)r\}\le \frac{k-1}n\}$ is non-empty and therefore $T_L$ has a maximal element $M\in \mathbb N$ that is $(M+1)\{(k_2-k_1)r\}\ge \frac kn$ and $M\{(k_2-k_1)r\}\le \frac{k-1}n$ and subtracting the two, we get: $\{(k_2-k_1)r\}\ge \frac 1n$, which is a contradiction. Therefore no subinterval $I_k$ can be free of elements from $\{\mathbb N r\}$.
– Koro
Jul 21, 2021 at 3:56
• Really nice answer which helped me to understand the problem. But I think you can assume $r$ to be any real irrational number from the beginning of the solution.
– ZFR
Jul 29, 2021 at 22:25
• @ZFR: You know, I modified this so many times while writing it, and now it seems you are correct; there is no reason for $r\gt0$, so I have removed that constraint.
– robjohn
Jul 30, 2021 at 2:40
• Thanks a lot for your answer! To be honest I've spent on this problem about 2-3 days and eventually your solution helped me to understand it completely. Thanks! +1
– ZFR
Jul 30, 2021 at 15:42

Really? I thought exactly the same proof worked for $\Bbb N$.

Let $k\in\Bbb Z$ with $k\ne 0$ and define $$f(t)=e^{2\pi ikt}.$$

Then $f$ has period $1$, and $$\frac1N\sum_{n=0}^{N-1}f(nx) =\frac1N\sum_{n=0}^{N-1}\left(e^{2\pi ikx}\right)^n=\frac1N \frac{e^{2\pi ikxN}-1}{e^{2\pi ikx}-1}\to0\quad(N\to\infty).$$ So the usual approximation shows that $$\frac1N\sum_{n=0}^{N-1}f(nx)\to\int_0^1 f(t)\,dt$$for $f\in C(\Bbb T)$ and you're done, as usual.

How is this any different from the case $n\in\Bbb Z$?

• How does that imply that $\{ \exp (2\pi i {n x}) :n\in N\}$ is dense in the unit circle in $C$ ? Anyway, a proof from the most elementary method works for N just as well as for Z. Jan 24, 2016 at 5:33
• @user254665 Say those points are not dense. There is then an interval, or arc, $I$ on the circle that contains none of the points. Take $f\in C(\Bbb T)$ such that $f=0$ on the complement of $I$ but $\int f > 0$. Then $\frac1N\sum_0^{N-1}f(nx)=0$ for every $N$, so it does not converge to $\int f$. (Yes, the pigeonhole argument works as well. I really can't think of an argument that works for $n\in\Bbb Z$ but not $\Bbb N$. In any case, ignoring the question of which is simpler, this argument shows more than just that the points are dense, it shows they are asymptotically uniformly distributed.) Jan 24, 2016 at 14:21
• very nice integral proof, which yields extra info (distribution) too. Jan 24, 2016 at 20:10
• @user254665 Yes it is very nice. The equidistribution is Weyl's theorem - I think it's his proof, not sure, in any case it's a standard thing. Jan 24, 2016 at 21:27