Skip to main content

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:
  1. We start with estimating logn by using a comparison between the sum and integral of a monotone function.
  2. Next, we rewrite this as a sum involving the Von Mangoldt function, Λ(d)xd, by rewriting the previous sum as a double sum indexed over lattice points under a hyperbola.
  3. This in turn lets us estimate Λ(n)n, where we can control the error term thanks to Chebyshev’s estimate for the Chebyshev ψ function.
  4. We check that the terms logppk with powers k2 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 logpp 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 1p. 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. 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 nth root of unity is a complex number ξ (the Greek letter xi) such that ξn=1. There are n such numbers, forming the vertices of a regular n-gon inscribed in the unit circle. The nth roots of unity are exp(2πk1/n) for 0k<n. 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 xn1 factors,
(7.1.1)xn1=k=0n1(xξk).
The coefficient of xn1 is zero on the left hand side, and is (ξ0++ξn1) on the right hand side.

Remark 7.1.2.

Likewise, 1i<j<nξiξj=0, and similar statements hold for the sum of products of 3,4,,n1 of the ξk’s.

Proof.

If ξ=1 then every ξk=1 and the sum, having n terms, is equal to n.
Otherwise, suppose that ξ1. Let d be the order of ξ, the smallest positive integer such that ξd=1. The assumption ξ1 means d>1.
Note that d must be a divisor of n. (This follows from Lagrange’s theorem in group theory. Alternatively, if n=dq+r with 0r<d, then ξr=ξn(ξd)q. Since ξn=ξd=1, then ξr=1as well. The fact that r<d contradicts that d is the smallest positive integer such that ξd=1, unless, of course, r is not positive. And this must be the case: r=0, so d divides n.)
Then the values ξ0,ξ1,,ξd1 are dth roots of unity, and they are pairwise distinct (why? exercise). So they are in fact all of the dth roots of unity. By the previous proposition, k=0d1ξk=0.
Finally, the full sum k=0n1ξk is simply equal to the sum of the first d terms, repeated n/d times. This is because ξk+d=ξk, 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+ξ+ξ2++ξn1 is a (finite) geometric series. If ξ1, the value of the sum is
(7.1.3)S=1ξn1ξ=01ξ=0,
where the numerator 1ξn=0 because ξ is an nth root of unity, and the denominator 1ξ0 since ξ1.
So, our strategy for Dirichlet’s theorem is to consider sums
(7.1.4)pxlogppξp
where, for each p, ξp is a root of unity chosen in some way. Specifically, we will choose them so that if pa(modq), then ξp=1, but otherwise, the ξ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 pa(modq) will add up, but the other terms will cancel out (add up to zero).

Example 7.1.5.

Let q=3. For every prime p, define
(7.1.5)α(p)={1,p1(mod3)1,p2(mod3)0,p0(mod3)(p=3)
and
(7.1.6)β(p)={1,p1(mod3)1,p2(mod3)0,p0(mod3)(p=3).
Other than p=3, these are 2nd roots of unity.
Consider the sums
(7.1.7)A(x)=pxlogppα(p)=log22+log55+log77+log1111+log1313+
(here the root of unity is ξp=1 for all p other than 3) and
(7.1.8)B(x)=pxlogppβ(p)=log22log55+log77log1111+log1313+.
Then
(7.1.9)A(x)+B(x)=2(log77+log1313+)=2p1(mod3),pxlogpp
and
(7.1.10)A(x)B(x)=2(log22+log55+)=2p2(mod3),pxlogpp.
We will have to figure out how to choose the roots of unity ξ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!