Proposition 7.1.1.
Let \(n \geq 2\) and let \(\xi_0,\dotsc,\xi_{n-1}\) be the \(n\)th roots of unity. Then \(\sum_{k=0}^{n-1} \xi_k = 0\text{.}\)
Section 7.1 Overview of Proof of Dirichlet’s Theorem
I will add to this overview as I continue to work through the proof.
Subsection 7.1.1 Repeating the proof of Mertens’s theorems
To some extent the proof is a reprise of the proof of Mertens’s theorems:
- We start with estimating \(\sum \log n\) by using a comparison between the sum and integral of a monotone function.
- Next, we rewrite this as a sum involving the Von Mangoldt function, \(\sum \Lambda(d) \left\lfloor \frac{x}{d} \right\rfloor\text{,}\) by rewriting the previous sum as a double sum indexed over lattice points under a hyperbola.
- This in turn lets us estimate \(\sum \frac{\Lambda(n)}{n}\text{,}\) where we can control the error term thanks to Chebyshev’s estimate for the Chebyshev \(\psi\) function.
- We check that the terms \(\frac{\log p}{p^k}\) with powers \(k \geq 2\) have a convergent sum, so they contribute a bounded amount to the total, in other words an \(O(1)\) amount. Dropping these terms leaves the sum \(\sum \frac{\log p}{p}\) and only makes an \(O(1)\) difference.
(For Mertens’s theorems our next step was to use Riemann-Stieltjes integration and integration by parts to change the sum to \(\sum \frac{1}{p}\text{.}\) However we will not take this step in our study of Dirichlet’s theorem.)
Our plan is basically to repeat all the same ideas, with the added restriction of summing over a congruence class modulo \(q\text{.}\) How will we do this? The basic idea is to use complex roots of unity.
Subsection 7.1.2 Complex roots of unity
A complex \(n\)th root of unity is a complex number \(\xi\) (the Greek letter xi) such that \(\xi^n = 1\text{.}\) There are \(n\) such numbers, forming the vertices of a regular \(n\)-gon inscribed in the unit circle. The \(n\)th roots of unity are \(\exp(2\pi k \sqrt{-1}/n)\) for \(0 \leq k \lt n\text{.}\) They form a group under multiplication. This group is cyclic.
A fundamental fact about roots of unity concerns the sum of roots of unity, or of powers of a root of unity.
Proof.
Geometrically, the points are equally spaced around the origin, so their average or center of gravity is at the origin.
Algebraically, the polynomial \(x^n-1\) factors,
\begin{equation}
x^n-1 = \prod_{k=0}^{n-1} (x - \xi_k)\text{.}\tag{7.1.1}
\end{equation}
The coefficient of \(x^{n-1}\) is zero on the left hand side, and is \(-(\xi_0+\dotsb+\xi_{n-1})\) on the right hand side.
Remark 7.1.2.
Likewise, \(\sum_{1 \leq i \lt j \lt n} \xi_i \xi_j = 0\text{,}\) and similar statements hold for the sum of products of \(3, 4, \dotsc, n-1\) of the \(\xi_k\)’s.
Proposition 7.1.3.
Let \(\xi\) be an \(n\)th root of unity. Then
\begin{equation}
\sum_{k=0}^{n-1} \xi^k =
\begin{cases}
n, \amp \xi = 1 \\
0, \amp \xi \neq 1
\end{cases}\tag{7.1.2}
\end{equation}
Proof.
If \(\xi=1\) then every \(\xi^k=1\) and the sum, having \(n\) terms, is equal to \(n\text{.}\)
Otherwise, suppose that \(\xi \neq 1\text{.}\) Let \(d\) be the order of \(\xi\text{,}\) the smallest positive integer such that \(\xi^d = 1\text{.}\) The assumption \(\xi \neq 1\) means \(d \gt 1\text{.}\)
Note that \(d\) must be a divisor of \(n\text{.}\) (This follows from Lagrange’s theorem in group theory. Alternatively, if \(n = dq+r\) with \(0 \leq r \lt d\text{,}\) then \(\xi^r = \xi^n (\xi^d)^{-q}\text{.}\) Since \(\xi^n=\xi^d=1\text{,}\) then \(\xi^r=1\)as well. The fact that \(r \lt d\) contradicts that \(d\) is the smallest positive integer such that \(\xi^d=1\text{,}\) unless, of course, \(r\) is not positive. And this must be the case: \(r=0\text{,}\) so \(d\) divides \(n\text{.}\))
Then the values \(\xi^0,\xi^1,\dotsc,\xi^{d-1}\) are \(d\)th roots of unity, and they are pairwise distinct (why? exercise). So they are in fact all of the \(d\)th roots of unity. By the previous proposition, \(\sum_{k=0}^{d-1} \xi^k = 0\text{.}\)
Finally, the full sum \(\sum_{k=0}^{n-1} \xi^k\) is simply equal to the sum of the first \(d\) terms, repeated \(n/d\) times. This is because \(\xi^{k+d} = \xi^k\text{,}\) so that each term in the sum is simply a repetition of the term \(d\) steps earlier. Therefore the full sum is \(n/d\) times zero, which is simply zero.
Remark 7.1.4.
After presenting the above proof, I realized there’s a much quicker idea: the sum \(S = 1 + \xi + \xi^2 + \dotsb + \xi^{n-1}\) is a (finite) geometric series. If \(\xi \neq 1\text{,}\) the value of the sum is
\begin{equation}
S = \frac{1-\xi^n}{1-\xi} = \frac{0}{1-\xi} = 0,\tag{7.1.3}
\end{equation}
where the numerator \(1-\xi^n=0\) because \(\xi\) is an \(n\)th root of unity, and the denominator \(1-\xi \neq 0\) since \(\xi \neq 1\text{.}\)
So, our strategy for Dirichlet’s theorem is to consider sums
\begin{equation}
\sum_{p \leq x} \frac{\log p}{p} \xi_p\tag{7.1.4}
\end{equation}
where, for each \(p\text{,}\) \(\xi_p\) is a root of unity chosen in some way. Specifically, we will choose them so that if \(p \equiv a \pmod{q}\text{,}\) then \(\xi_p = 1\text{,}\) but otherwise, the \(\xi_p\) will cycle among all the roots of unity. Then we will add together all of these sums, with the result that the terms with \(p \equiv a \pmod{q}\) will add up, but the other terms will cancel out (add up to zero).
Example 7.1.5.
Let \(q = 3\text{.}\) For every prime \(p\text{,}\) define
\begin{equation}
\alpha(p) =
\begin{cases}
1, \amp p \equiv 1 \pmod{3} \\
1, \amp p \equiv 2 \pmod{3} \\
0, \amp p \equiv 0 \pmod{3} (p=3)
\end{cases}\tag{7.1.5}
\end{equation}
and
\begin{equation}
\beta(p) =
\begin{cases}
1, \amp p \equiv 1 \pmod{3} \\
-1, \amp p \equiv 2 \pmod{3} \\
0, \amp p \equiv 0 \pmod{3} (p=3)
\end{cases}\text{.}\tag{7.1.6}
\end{equation}
Other than \(p=3\text{,}\) these are \(2\)nd roots of unity.
Consider the sums
\begin{equation}
A(x) = \sum_{p \leq x} \frac{\log p}{p} \alpha(p)
= \frac{\log 2}{2} + \frac{\log 5}{5} + \frac{\log 7}{7}
+ \frac{\log 11}{11} + \frac{\log 13}{13} + \dotsb\tag{7.1.7}
\end{equation}
(here the root of unity is \(\xi_p = 1\) for all \(p\) other than \(3\)) and
\begin{equation}
B(x) = \sum_{p \leq x} \frac{\log p}{p} \beta(p)
= - \frac{\log 2}{2} - \frac{\log 5}{5}
+ \frac{\log 7}{7} - \frac{\log 11}{11} + \frac{\log 13}{13} + \dotsb\text{.}\tag{7.1.8}
\end{equation}
Then
\begin{equation}
A(x) + B(x) = 2\left( \frac{\log 7}{7} + \frac{\log 13}{13} + \dotsb \right)
= 2 \sum_{p \equiv 1 \pmod{3}, p \leq x} \frac{\log p}{p}\tag{7.1.9}
\end{equation}
and
\begin{equation}
A(x) - B(x) = 2\left( \frac{\log 2}{2} + \frac{\log 5}{5} + \dotsb \right)
= 2 \sum_{p \equiv 2 \pmod{3}, p \leq x} \frac{\log p}{p}\text{.}\tag{7.1.10}
\end{equation}
We will have to figure out how to choose the roots of unity \(\xi_p\) in general in order to get the cancellation we seek. And we will have to estimate the order of growth of these sums involving the roots of unity. This is our plan!
