Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
add comment

2 Answers

up vote 2 down vote accepted

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

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

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.