5
$\begingroup$

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

  • 0
    The definition of an [equidistributed sequence](http://en.wikipedia.org/wiki/Equidistributed_sequence) at Wikipedia contains equality instead of inequality and the same definition is given on [p.107](http://books.google.com/books?id=FAOc24bTfGkC&pg=PA107) in Stein's book you mentioned.2012-09-25
  • 0
    @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.2012-09-25
  • 0
    @ShreevatsaR How can we prove that equality holds if inequality holds for every interval $(a,b)$ in $[0,1)$?2016-09-22
  • 1
    @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.)2016-09-22

2 Answers 2

2

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

for $0\le a, $|(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. 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\;.$$

  • 0
    How do we get the other inequality?2016-09-22
  • 0
    @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.2016-09-22
  • 0
    Can you explain why $|(a,b)\cap F_N|\ge \lceil n(b-a)\rceil -1$?2016-09-22
  • 0
    @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)$.2016-09-22
  • 0
    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.2016-09-22
  • 0
    @takecare: The asymptotic density of the sequence in $(0,1)$ is $1$, so the average asymptotic density in the intervals $\left(\frac{k}n,\frac{k+1}n\right)$ is $\frac1n$. If any of these asymptotic densities is greater than $\frac1n$, at least one of the others must then be less than $\frac1n$, and I showed that this is not the case, so each of them must in fact be $\frac1n$. By taking $n$ large enough, you can approximate any open interval in $(0,1)$ arbitrarily closely as a union of intervals of the form $\left(\frac{k}n,\frac{k+1}n\right)$, and so can the one or two intervals that form ...2016-09-24
  • 0
    ... its complement in $(0,1)$. From there it’s plain sailing.2016-09-24
1

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

  • 0
    How do we get the other inequality?2016-09-22