# Prove $0, \frac{1}{2}, 0, \frac{1}{3}, \frac{2}{3}, 0, \frac{1}{4}, \frac{2}{4}, …$ equidistributed in $[0, 1)$

Prove

$0, \frac{1}{2}, 0, \frac{1}{3}, \frac{2}{3}, 0, \frac{1}{4}, \frac{2}{4}, ...$

equidistributed in $[0, 1)$.

A sequence of numbers $\xi_1, \xi_2, \xi_3, ...$ in $[0, 1)$ is said to be equidistributed if for every interval $(a, b) \subset [0, 1)$

$$\lim\limits_{N\to\infty} \frac {\bigl|\{1\le n\le N: \xi_n \in (a, b)\}\bigr|} {N} = b-a$$

It's from Chapter 4 in the book Fourier Analysis: An Introduction

-
The definition of an equidistributed sequence at Wikipedia contains equality instead of inequality and the same definition is given on p.107 in Stein's book you mentioned. –  Martin Sleziak Sep 25 '12 at 8:21
@MartinSleziak: Yes I think equality is the more natural definition, but if the inequality holds for every interval $(a,b)$ in $(0,1)$, I think we can prove that equality in fact holds. –  ShreevatsaR Sep 25 '12 at 8:35

For each integer $n>1$ let $$F_n=\left\{\frac{k}n:k=0,\dots,n-1\right\}\;;$$

for $0\le a<b<1$, $|(a,b)\cap F_n|\ge\lceil n(b-a)\rceil-1$.

The first $2$ terms of the sequence are the members of $F_2$; the next $3$ terms are the members of $F_3$, and so on. Thus, the first $\sum_{k=2}^nk=\frac12n(n+1)-1$ terms are the members of blocks $F_2$ through $F_n$ in the obvious order. For $n\ge 2$ let $T_n=\frac12n(n+1)-1$, and suppose that $T_m\le N<T_{m+1}$. Then

\begin{align*} |\{n\le N:\xi_n\in(a,b)\}&\ge\sum_{k=2}^m|(a,b)\cap F_k|\\ &\ge\sum_{k=2}^m\Big(\lceil k(b-a)\rceil-1\Big)\\ &=\sum_{k=2}^m\lceil k(b-a)\rceil-m+1\\ &\ge\sum_{k=2}^mk(b-a)-m+1\\ &=(b-a)T_m-m+1\;, \end{align*}

so

$$\frac{|\{n\le N:\xi_n\in(a,b)\}}N\ge(b-a)\frac{T_m}N-\frac{m-1}N\;.$$

Now $$\frac{T_m}N>\frac{T_m}{T_{m+1}}=\frac{\frac12m(m+1)-1}{\frac12(m+1)(m+2)-1}\to 1\quad\text{ as }\quad m\to\infty\;,$$ and

$$\frac{m-1}N\le\frac{m-1}{T_m}=\frac{m-1}{\frac12m(m+1)-1}\to 0\quad\text{ as }\quad m\to\infty\;,$$

so $$\lim_{N\to\infty}\frac{|\{n\le N:\xi_n\in(a,b)\}}N\ge b-a\;.$$

-

Let $a < b$ be given. We have for $0 \le p < q$ that $\frac pq \in (a,b)$ iff $qa < p < qb$ iff $\lfloor qa\rfloor < p < \lceil qb \rceil$.

For $N \in \mathbb N$, choose the maximal $q$ with $\frac 12q(q+1) < N$, then all fractions with denominator $\le q$ have apperead under $(\xi_n)_{n\le N}$. We have \begin{align*} \left|\{1 \le n \le N: \xi_n \in(a,b)\}\right| &\ge \sum_{r=2}^q \bigl(\lceil rb \rceil - \lfloor ra\rfloor - 1\bigr)\\ &\ge \sum_{r=2}^q \bigl(r(b-a) - 3\bigr)\\ &= \left(\frac 12q(q+1) - 1\right)(b-a) - 3(q-1) \end{align*} But now $\frac 12 q(q+1) < N \le \frac 12 (q+1)(q+2)$ hence $1 \le \frac N{\frac 12q(q+1)} \le \frac{(q+1)(q+2)}{q(q+1)} \to 1, q \to \infty$ So, for $N \to \infty$ \begin{align*} \frac 1N \left|\{1 \le n \le N: \xi_n \in(a,b)\}\right| &\ge \frac 1N\left(\frac 12q(q+1) - 1\right)(b-a) - \frac 3N(q-1)\\ &\to b-a. \end{align*}

-