# 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. Commented Sep 25, 2012 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. Commented Sep 25, 2012 at 8:35
• @ShreevatsaR How can we prove that equality holds if inequality holds for every interval $(a,b)$ in $[0,1)$? Commented Sep 22, 2016 at 16:35
• @takecare All the numbers in the sequence have to go somewhere. If some interval has more than it should, then its complement (one or two intervals) will have fewer than it should. (Needs some work to make it precise, and to account for the endpoints of the intervals.) Commented Sep 22, 2016 at 16:42

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\;.$$

• How do we get the other inequality? Commented Sep 22, 2016 at 16:32
• @takecare: When I wrote the answer, the definition of equidistributed in the question used only this inequality. However, ShreevatsaR’s comment under the question gives you a workable approach. Divide the unit interval into intervals of length $\frac1n$; the inequality proved here implies equality for these intervals by the argument that he indicated. Any interval can be approximated arbitrarily closely by a union of intervals $\left(\frac{k}n,\frac{k+1}n\right)$ for sufficiently large $n$, so we get equality for arbitrary intervals. Commented Sep 22, 2016 at 17:52
• Can you explain why $|(a,b)\cap F_N|\ge \lceil n(b-a)\rceil -1$? Commented Sep 22, 2016 at 19:26
• @takecare: The worst case is when $a$ and $b$ are multiples of $\frac1n$, say $b=\frac{k}n$ and $a=\frac{\ell}n$; then there are $k-\ell-1=n(b-a)-1$ multiples of $\frac1n$ in $(a,b)$. Commented Sep 22, 2016 at 19:45
• Okay, but I'm having a hard time understanding your previous comment. First, how does ShreevatsaR's comment imply equality for intervals of length $1/n$. And even if I accept that, I can't figure out how to use an approximation argument here. I'd greatly appreciate it if you can explain these to me. Commented Sep 22, 2016 at 23:07

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

• How do we get the other inequality? Commented Sep 22, 2016 at 16:33