# Equidistribution of $\{\xi_n\}$ where $\xi_n = <n\frac{p}{q}>$ $p,q$ rel. prime

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?

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.
• 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? – Lost Feb 26 '14 at 23:55
• 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\}$. – froggie Feb 26 '14 at 23:59
• 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? – Lost Feb 27 '14 at 0:00
• 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$. – froggie Feb 27 '14 at 0:06