An "elementary" perspective on Dirichlet's theorem

by t0rajir0u, May 16, 2008, 4:15 AM

In the following discussion, $p$ always denotes a prime. Most of the discussion on convergence is not completely rigorous. Much of (the rigorous part of) this material is taken from this paper.

So we've talked about how to prove special cases of Dirichlet's theorem using polynomials. (The comment I posted contains a generalization). Let's talk about (the easy parts of) the classic proof of the theorem itself.

The Amazing Euler Product: $\zeta(s) = \sum_{n = 1}^{\infty} \frac {1}{n^s} = \prod_{p} \left( \frac {1}{1 - \frac {1}{p^s}} \right)$ . (We can consider this either as a formal identity or as an actual sum equality for $s > 1$ .)

Proof. Write $\frac {1}{1 - \frac {1}{p^s}} = 1 + \frac {1}{p^s} + \frac {1}{p^{2s}} + \frac {1}{p^{3s}} ...$ . The product on the LHS then takes the form $\sum \frac {1}{2^{k_1 s} 3^{k_2 s} 5^{k_3 s} ... }$ where the product is taken over all primes and $k_1, k_2, ... k_3$ are arbitrary non-negative integers. But by the Fundamental Theorem of Algebra the numbers $2^{k_1} 3^{k_2} 5^{k_3}...$ are precisely the natural numbers, once each.

The Euler Product is one of the most beautiful identities I know. It relates the Riemann Zeta function (of Riemann Hypothesis fame) to a product over the primes through prime factorization. Magical. Now we need a lemma.

Lemma: Let $\{ a_n \}$ be a sequence of complex numbers such that $\lim_{n \to \infty} a_n = 0$ . Suppose that $\sum |a_k|^2$ converges. Then $\sum a_k$ converges if and only if $\prod (1 + a_k)$ converges.

Proof. See this thread. (Yes, I cheated.

) I needed to verify this lemma as part of this discussion; the intuitive notion is that $\ln \prod (1 + a_k) \sim \sum a_k$ .

Proposition: There are an infinite number of primes. In fact, $\sum_{p} \frac {1}{p}$ diverges. (The latter implies the former.)

Proof. By our lemma, $\zeta(s) = \prod_{p} \left( 1 + \frac {1}{p^s - 1} \right)$ converges if and only if $\sum_{p} \frac {1}{p^s - 1}$ converges (for $s > \frac {1}{2}$ ), which is asymptotic (by comparison) to $\sum_{p} \frac {1}{p^s}$ .

Now, $\lim_{s \to 1^{ + }} \zeta(s)$ turns out to be just the harmonic series, which diverges. Hence $\lim_{s \to 1^{ + }} \sum_{p} \frac {1}{p}$ also diverges.

N.B. It's more elementary to prove that there are an infinite number of primes alone; as $s \to 1^{ + }$ we know $\zeta(s)$ approaches the harmonic series, so the Euler product must contain an infinite number of factors (or else it is finite).

This is a proof of a quite different flavor than Euclid's proof that there are an infinite number of primes (generalized by the polynomial proof from the other post). It is strangely analytic. Such ideas belong to the fascinating realm of analytic number theory, another example of which is the celebrated Riemann hypothesis.

A short excursion. One of the first successes of analytic number theory was the prime number theorem, which states (in an equivalent form) that the $n^{th}$ prime $p_n$ is asymptotic to $n \ln n$ , and we know that $\sum \frac {1}{n \ln n}$ diverges. The proof is usually done by the integral test, but the more illuminating proof is by Cauchy condensation, which reduces the above to the question of the convergence of the harmonic series.

The substitution required to perform Cauchy condensation is analogous to (the inverse of) our use of the natural log to transform the Euler product into the sum of the reciprocal of the primes. Indeed, the argument we used to prove the divergence of the prime harmonic series suggests that, just as $\sum_{n \le x} \frac {1}{n} \sim \ln x$ , we have $\sum_{p \le x} \frac {1}{p} \sim \ln \ln x$ .

A second short excursion.

Problem: Let $P(x)$ be a polynomial of even degree. Show that the set $\{ P(k) | k \in \mathbb{Z} \}$ cannot contain the primes.

Solution. $\sum_{k = - \infty}^{\infty} \frac {1}{P(k)}$ converges and contains a finite number of negative terms. Its positive terms therefore cannot contain the primes.

Again, this solution has a strange flavor. We have not appealed to any facts intrinsic to polynomials (other than their loose connection to the $p$ -series test). We have not required that the coefficients be integer or even rational. We have not talked about divisibility (which is how we show that an integer polynomial takes on composite values infinitely often).

The above does suggest that there may exist multivariate polynomials (with no terms of degree $1$ ) whose values at integers include the primes. Indeed, by the four-square theorem, such a polynomial is $x^2 + y^2 + z^2 + w^2$ , whose values also contain all the non-negative integers. Amazingly enough, a 26-variable polynomial exists whose positive values at integer inputs is precisely the set of primes.

This is all thanks to the magic of the Euler product. Of course, my use of "the" Euler product is misleading. Let me show you what I mean.

Another Euler Product: $\sum_{n \equiv 1 \bmod 3} \frac {1}{n^s} - \sum_{n \equiv 2 \bmod 3} \frac {1}{n^s} = \prod_{p \equiv 1 \bmod 3} \left( \frac {1}{1 - \frac {1}{p^s}} \right) \prod_{p \equiv 2 \bmod 3} \left( \frac {1}{1 + \frac {1}{p^s}} \right)$ .

Proof. The integers congruent to $2 \bmod 3$ are precisely the integers with an odd number of prime factors congruent to $2 \bmod 3$ (counting multiplicity). The rest follows by a similar argument as the first identity.

Proposition: There are an infinite number of primes congruent to $1 \bmod 3$ and an infinite number of primes congruent to $2 \bmod 3$ . In fact, $\sum_{p \equiv 1 \bmod 3} \frac {1}{p}$ and $\sum_{p \equiv 2 \bmod 3} \frac {1}{p}$ both diverge.

Proof. We are going to call the above sum $L(s, \chi)$ for reasons that will be explained later. Observe that it is essentially an alternating harmonic series and therefore converges as $s \to 1^{ + }$ , and moreover it is nonzero (because we can write it as a sum of positive terms). Now take its natural log. Our lemma allows us to conclude that the sum

$\sum_{p \equiv 1 \bmod 3} \frac {1}{p^s} - \sum_{p \equiv 2 \bmod 3} \frac {1}{p^s}$

converges as $s \to 1^{ + }$ . On the other hand,

$\sum_{p} \frac {1}{p^s} = \frac {1}{3^s} + \sum_{p \equiv 1 \bmod 3} \frac {1}{p^s} + \sum_{p \equiv 2 \bmod 3} \frac {1}{p^s}$

diverges. Adding and then subtracting the two sums, we have our result.

This seems like a rather powerful technique. Here it is motivated; by changing the sign of the part of the product corresponding to primes congruent to $2 \bmod 3$ we simply distinguish the integers congruent to $2 \bmod 3$ . But mod larger numbers we don't have such simple patterns. To generalize this result, we need a more general way to construct Euler products.

The (Fully Multiplicative) Euler product: Let $\chi(a) : \mathbb{N} \to \mathbb{C}$ be a function such that $\chi(ab) = \chi(a) \chi(b)$ . Then

$L(s, \chi) \equiv \sum_{n = 1}^{\infty} \frac {\chi(n)}{n^s} = \prod_{p} \left( \frac {1}{1 - \frac {\chi(p)}{p^s} } \right)$ .

The proof is identical to the proof of the original Euler product. So what function $\chi$ did we choose to create our second Euler product?

It turns out that the only functions $\chi$ we want to look at (for the purposes of Dirichlet's Theorem) are very special functions called Dirichlet characters, and the corresponding series are very special functions called Dirichlet L-functions. A Dirichlet character relative to a positive integer $n$ repeats its values $\bmod n$ and has the following properties:

- Whenever $(a, n) > 1$ , we have $\chi(a) = 0$ .
- $\chi(1) = 1$ .
- For $(a, n) = 1$ we have $ \chi(a)^{\varphi(n)} = \chi(a^{\varphi(n)}}) = 1$. In other words, $\chi(a)$ is a $\varphi(n)^{th}$ root of unity.

The Dirichlet characters relative to a particular $n$ form a group under the multiplication $\chi \psi (a) = \chi(a) \psi(a)$ with the identity element $e(a) = 1, (a, n) = 1$ ; we denote this group $X_n$ . In fact, we can show that this group has order $\varphi(n)$ . We denote the inverse of $\chi$ by $\bar{\chi}$ . Note that $\bar{\chi}(a) = \chi(a^{ - 1})$ .

The character we chose (with respect to $3$ ) was actually the Jacobi symbol (here just the Legendre symbol). The corresponding group has order $2$ , so its only elements are the Jacobi symbol and the identity. (This is also true when $n = 4, 6$ .)

We have the following two related sums (which are left as an exercise):

- $\sum_{a \in \mathbb{Z}_n} \chi(a) = 0$ if $\chi \neq e$ and $\varphi(n)$ otherwise.
- $\sum_{\chi \in X_n} \chi(a) = 0$ if $a \neq 1$ and $\varphi(n)$ otherwise.

We are now somewhat ready to discuss Dirichlet's Theorem.

Dirichlet's Theorem: For $n \in \mathbb{N}$ and $a$ such that $\gcd(a, n) = 1$ , there are an infinite number of primes congruent to $a \bmod n$ .

Sketch. Let $\chi$ be a character relative to $n$ .

The hardest part of the proof of Dirichlet's Theorem is showing that whenever $\chi \neq e$ we know that $L(1, \chi)$ is nonzero and converges. In other words, $1$ is not a zero of the function $L(s, \chi)$ . The natural way to ask this question is within the setting of complex analysis; in fact, the generalized Riemann hypothesis is precisely about the zeroes of Dirichlet L-functions. Details on (one approach to) this step can be found in the paper I linked to initially; we will ignore them, as our focus is on the elementary parts of the proof.

Define $N(s, \chi) \equiv \sum_{p} \frac {\chi(p)}{p^s}$ . Our lemma allows us to conclude that $N(s, \chi)$ converges as $s \to 1^{ + }$ if and only if $L(s, \chi)$ converges and is nonzero, which is whenever $\chi \neq e$ . When $\chi = e$ we recover a sum that is almost the usual zeta function, but the numbers relatively prime to $n$ have been removed. This sum still diverges as $s \to 1^{ + }$ . Now consider the sum

$ \begin{eqnarray*} \sum_{\chi \in X_n} N(s, \chi) \bar{\chi}(a) & = & \sum_{p} \frac {1}{p^s} \left( \sum_{\chi \in X_n} \chi(pa^{ - 1}) \right) \\ & = & \sum_{p \equiv a \bmod n} \frac {\varphi(n)}{p^s}. \\ \end{eqnarray*}$.

The LHS has a single term that diverges (when $\chi = e$ ); the result follows. Notice how this generalizes our argument for $n = 3$ . The Dirichlet characters act as a roots of unity filter, causing the corresponding coefficient to evaluate to $0$ unless $p \equiv a \bmod n$ . QED.

So here we've got two very different approaches to proving that certain congruence classes contain infinitely many primes. One uses divisibility properties of polynomials; this is something solid. Primes relate to divisibility. We can sink our teeth into this method of proof. Unfortunately, it's not enough.

The other proceeds by showing that certain sums are nonzero and therefore certain other sums diverge; this is a very powerful technique, but very far removed from what we usually consider "number theory." Can we strengthen the first technique, then?

Let's return to the main step of the proof from the other post, which is about primes that divide $\Phi_n(a)$ for some integers $a, n$ . We know that such primes either divide $n$ or are congruent to $1 \bmod n$ . Unfortunately, no similar divisibility relations exist for primes congruent to $a \bmod n$ generally. So what do we do?

We saw some interesting consequences of this divisibility when $n = 4, 3$ . When $n = 4$ ,

$p | x^2 + 1 \Leftrightarrow p = 2, p \equiv 1 \bmod 4 \Leftrightarrow p = a^2 + b^2$

and when $n = 3$ ,

$p | x^2 + x + 1 \Leftrightarrow p = 3, p \equiv 1 \bmod 3 \Leftrightarrow p = a^2 + ab + b^2$ .

This viewpoint is generalized by the ring of integers of a cyclotomic field. Now instead of doing analytic number theory, we're doing algebraic number theory. Watch what happens.

When $n = 4$ , the corresponding cyclotomic field is $\mathbb{Q}[\imath]$ , the ring of integers is the Gaussian integers that we know and love, and the primes congruent to $1 \bmod n$ factor into a product of primes $(a + b \imath)(a - b \imath) = a^2 + b^2$ . (These are primes over $\mathbb{Z}[ \imath]$ , rather than primes over $\mathbb{Z}$ .) The primes dividing $n$ (here, just $2$ ) also factor: $2 = (1 + i)(1 - i)$ .

When $n = 3$ , the corresponding cyclotomic field is $\mathbb{Q}[\omega]$ , the ring of integers is the Eisenstein integers, and the primes congruent to $1 \bmod n$ again factor into a product of primes $(a - b \omega)(a - b \omega^2) = a^2 + ab + b^2$ . The primes dividing $n$ (here, just $3$ ) again factor: $3 = (1 - \omega)(1 - \omega^2)$ .

This is interesting. It suggests the following: given $\mathbb{Z}[\zeta_n]$ , we can partition the ordinary (rational) primes into classes depending on whether (and how) they factor any further, and quite possibly those classes correspond to congruence classes $\bmod n$ (with a special class for primes dividing $n$ ). Two special cases:

Case: $p \equiv 1 \bmod n$ : if $p | \Phi_n(a)$ , then

$p | \prod_{\gcd(k, n) = 1} (a - \zeta_n^k)$

over the cyclotomic integers $\mathbb{Z}[\zeta_n]$ . If $p$ is prime over $\mathbb{Z}[\zeta_n]$ , then it must divide one of these factors, which is clearly absurd. Therefore $p$ must be composite. (I believe it's possible to show that, at least when we have prime factorization, $p$ factors into $\varphi(n)$ factors.)

Case: $p | n$ . Because $p | 1^{n - 1} + 1^{n - 2} + ... + 1^0 = \prod_{d | n, d > 1} \Phi_d(1)$ , it divides $\Phi_d(1)$ for some $d$ . But then

$p | \prod_{\gcd(k, d) = 1} (1 - \zeta_d^k)$

and the primitive $d^{th}$ roots are clearly contained in $\mathbb{Z}[\zeta_n]$ , so again $p$ must factor.

These results are easy enough to see explicitly when $n = 3, 4$ because in those cases the degree of $\mathbb{Q}[\zeta_n] : \mathbb{Q}$ (which is $\varphi(n)$ in general) is $2$ , so we can write an arbitrary element as $a + b \imath$ or as $a + b \omega$ , respectively. This is more difficult when $n$ is larger. An example:

$\Phi_5(2) = 31 = 2^4 + 2^3 + 2^2 + 2 + 1 = (2 - \zeta_5)(2 - \zeta_5^2)(2 - \zeta_5^3)(2 - \zeta_5^4)$ ,

so $31$ (a prime) factors into four factors in $\mathbb{Z}[\zeta_5]$ . (The only such primes are $5$ and the primes congruent to $1 \bmod 5$ .)

These notions (divisibility! We like divisibility!) can be generalized to give a proof of Dirichlet's theorem through the magic of Chebotarev's density theorem, of which Dirichlet's theorem is but a small, small subcase.

Practice Problem 1: Prove the Dirichlet character sums.

Practice Problem 2: Factor $11$ in $\mathbb{Z}[\zeta_5]$ . (Try looking at other values of $\Phi_5(a)$ .) How about $41$ ?

Practice Problem 3 (if I recall properly; this is very hard): Show that $\left| \sum_{p \le x} \frac {1}{p} - \ln \ln x \right| < 80$ .

Comment

1 Comment

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Now like always that was an amazing post t0rajir0u, Wow thank you so much!

by sinajackson, May 22, 2008, 5:14 PM

Report

Submit

orz $~~~~$
by clarkculus, Jan 10, 2025, 4:13 PM
Insanely auraful
by centslordm, Jan 1, 2025, 11:17 PM
Fly High
by Siddharthmaybe, Oct 22, 2024, 8:34 PM
Dang it he is gone ( /revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive.
by 799786, Aug 4, 2022, 1:56 PM
annoying precision
by centslordm, May 16, 2021, 7:34 PM
rip t0rajir0u
by OlympusHero, Dec 5, 2020, 9:29 PM
Shoutbox bump xD
by DuoDuoling0, Oct 4, 2020, 2:25 AM
dang hes gone
by OlympusHero, Jul 28, 2020, 3:52 AM
First shout in July
by smartguy888, Jul 20, 2020, 3:08 PM
https://artofproblemsolving.com/community/c2448

has more.

-πφ
by piphi, Jun 12, 2020, 8:20 PM
wait hold up 310,000
people visited this man?!?!??
by srisainandan6, May 29, 2020, 5:16 PM
first shout in 2020
by OlympusHero, Apr 4, 2020, 1:15 AM
in his latest post he says he moved to wordpress
by MelonGirl, Nov 16, 2019, 2:43 AM
Please revive!
by AopsUser101, Oct 30, 2019, 7:10 PM
first shout in october fj9odiais
by bulbasaur., Oct 14, 2019, 1:14 AM
t0rajir0u is beast dude. I bet he'll make IMO this year
by #H34N1, Mar 26, 2008, 2:37 AM
"annoying precision" is somewhat of an understatement, don't you think?
by xscapezaer, Mar 23, 2008, 10:06 PM
Wow. Just by looking at the page--I gained IQ points. That's uncanny. Keep it up!
by The_Scintillator, Mar 21, 2008, 2:20 AM
Mmm t0r... Are you a senior? You're too genius Nice Blog btw... But for the sake of some less advanced people, go about defining some terms...
by resurrection, Jan 31, 2008, 1:08 AM
weird
by Airjohn6, Jan 30, 2008, 11:52 PM
pls help me with integrals i cant private message u b/c i just joined mathlinks, write me back at memena@loyno.edu
by memena, Jan 22, 2008, 2:18 AM
Can you post more problems about number theory? I'd like to suggest you about combinatorial problems!
by ghjk, Jan 10, 2008, 7:03 AM
The article: A Digression is nice
by FOURRIER, Nov 5, 2007, 4:47 PM
Interested in number theory? Mmm... I am bad in number theory but I need to take it. Hope that you can help me.
by ifai, Oct 13, 2007, 7:14 AM
your blog is very useful and i like it.
by lovejrz, Oct 12, 2007, 9:26 AM
madness
by madness, Oct 4, 2007, 4:48 PM
t0r, I recommend you watch out at the RSI-PROMYS frisbee game this weekend. You betrayed both MOP and PROMYS for RSI. I'm not going to be there, but let's just say there's a hitman after you.
by K81o7, Jul 27, 2007, 3:27 AM
hello.
by ajai, Jul 13, 2007, 12:52 AM
just drop by to say hello! and digging for stuffs that I could understand
by jeez123, Jun 30, 2007, 5:02 PM

128 shouts

Annoying precision

An "elementary" perspective on Dirichlet's theorem

by t0rajir0u, May 16, 2008, 4:15 AM

1 Comment