I'm working from Stein's An Introduction to Fourier Analysis, and there's a question (chapter 4 number 6):

Let $\theta = \frac{p}{q} \in \mathbb{Q}$ where $\operatorname{gcd}(p,q) = 1$. Assume WLOG $q > 0$.

Define the sequence $(\xi_n)$ by $\xi_n = <n\theta>$ where $<>$ denotes the fractional part. Show that this sequence is equidistributed on the points of the form $0, \frac{1}{q},..., \frac{q-1}{q}$

In fact, show that $\forall 0 \leq a < q$,

$\frac{\operatorname{card}\{n: 1 \leq n \leq N, <n\theta> = \frac{a}{q}\}}{N} = \frac{1}{q} + O(\frac{1}{N})$

($\operatorname{card}$ is cardinality)

My problem is that I don't know what I should be doing. The course is Fourier analysis, and this topic (Weyl's equidistribution theorem) is covered in only a few pages in this chapter. I don't see how I can work with the definition of equidistribuition: for every $(a,b) \subset [0,1)$, $(\xi_n)$ is equidistributed in $[0,1)$ if $\operatorname{lim}_{N \to \infty} \frac{\operatorname{card}\{n: 1 \leq n \leq N, \xi_n \in (a,b) \}}{N} = b-a$

I don't have much intuition to work with; I was able to prove that the sequence $(<n\phi>)$ where $\phi$ is the golden ratio was not equidistributed in $[0,1)$ by showing that it tended to either $0$ or $1$, so I see how a sequence might not be equidistributed and how I might be able to show it.

Proving equidistributivity seems far more difficult. Could anyone help me understand how I should work with this definition and steer me into the right direction for the proof?


1 Answer 1


This question seems very algebraic to me, no Fourier theory necessary. The key observation (which you should prove!) is that if $\langle n\frac{p}{q}\rangle = \frac{a}{q}$, then $np\equiv a\pmod{q}$. Therefore, for any $n\geq 1$, the value of $a = 0,\ldots, q-1$ such that $n\frac{p}{q} = \frac{a}{q}$ corresponds exactly to the residue class of $np$ modulo $q$.

Since $p$ and $q$ are relatively prime, $p$ is a generator of $\mathbb{Z}/q\mathbb{Z}$. It follows that the sequence of residue classes $\{[np]\}_{n=1}^\infty$ in $\mathbb{Z}/q\mathbb{Z}$ takes on all of the possible residue classes of $\mathbb{Z}/q\mathbb{Z}$, and in a cyclic manner.

Perhaps with this in mind, you can finish the exercise? I hope this helped!

  • $\begingroup$ I thought so as well, as Fourier series only appear in Stein's proof of Weyl's theorem. The hint in the book is very similar to what you're saying (albeit not quite as formally), so I think I can proceed that way now, thanks. My question is, would the $\frac{1}{q} + O(\frac{1}{N})$ bound imply that the sequence is equidistributed, or are these two distinct proofs? $\endgroup$
    – Lost
    Feb 26, 2014 at 23:55
  • $\begingroup$ This is distinct from Weyl's equidistribution theorem, because the equidistribution theorem applies to $\langle n\theta\rangle$ when $\theta$ is irrational. When $\theta$ is rational, like in this problem, the sequence $\langle n\theta\rangle$ is not equidistributed on $[0,1]$. But the point of this problem is to say that, even though you aren't equidistributed on $[0,1]$, you're are at least equidistributed on the set $\{0, 1/q, \ldots, (q-1)/q\}$. $\endgroup$
    – froggie
    Feb 26, 2014 at 23:59
  • $\begingroup$ I meant to ask that, if I'm able to show that $(<n\theta>)$ is $\frac{1}{q} + O(\frac{1}{N})$ in the sense as in the question, would equidistribution follow? Or do I have to prove these two facts separately? $\endgroup$
    – Lost
    Feb 27, 2014 at 0:00
  • $\begingroup$ Equidistribution follows easily once you get $\frac{1}{q} + O(1/N)$. Equidistribution means that in the limit as $N\to \infty$, the fraction tends to $\frac{1}{q}$. But this is clear, because the error term is of order $\frac{1}{N}$, which goes to $0$ as $N\to \infty$. $\endgroup$
    – froggie
    Feb 27, 2014 at 0:06
  • 1
    $\begingroup$ Alright, thanks. That was the part that I had an issue with; the concept of equidistribution wasn't explained that rigorously in the book so, while I could see what it means intuitively, I had trouble actually proving it. Let me work it out, see where I go. $\endgroup$
    – Lost
    Feb 27, 2014 at 0:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .