MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Sorry if the question is too vague or if the examples I look for are too boringly well-known: my knowledge of analytic number theory is rather primitive......

So, here it goes: suppose that you want to prove that the set $\Sigma$ of primes satisfying a certain condition $C$ is infinite. Then you may attempt to compute the density $$ \delta(C)=\lim_{x\to\infty}\frac{|\text{$p\leq x$ such that $C(p)$ holds}|}{|p\leq x|}. $$ If $\delta$ turns out to be positive, you're done. But it could as well be that $\delta=0$ and yet $\Sigma$ be infinite.

My questions are: (1) what are the main known examples of this occurrence? (2) in these examples, if any, the proofs of the infiniteness of $\Sigma$ did use ad hoc case-by-case "tricks" or there are somewhat standard techniques than can be employed with the situation? (3) is there a standard reference?

share|cite|improve this question
My understanding is that the Dirichlet density is defined more often than the asymptotic density, so maybe that would be worth a try. Although I think that really only works for very "structured" sets of primes. – Qiaochu Yuan Mar 2 '10 at 13:59
up vote 4 down vote accepted

If you can prove any reasonable lower bound for the set of primes which are at most $x$ then it's trivial to find infinite sets of primes with density 0. For example using completely elementary methods one can check that there's always a prime between $n$ and $2n$ (Bertrand's postulate), and hence the number of primes between 1 and $x$ is at least $log_2(x)$ for $x\geq2$ an integer. So now just build an infinite set $C$ of primes by letting the $n$th element be the smallest prime greater than $2^{2^n}$ (or any function that grows much faster than $2^n$). Does this answer your question or did I misunderstand it?

Edit: it appears that the questioner doesn't want arbitrary constructions, but explicit examples of infinite sets of density 0. In this case I would say that there is no "standard technique" (known to me, at least), other than the obvious one of "take a finite set of primes with the property, and construct another one". This is, for example, the technique used by Elkies to prove that there are infinitely many supersingular primes for an elliptic curve over the rationals.

I think that in general if you want to prove that a set of primes is infinite, often you try and compute the rate of growth, or come up with heuristics estimating what its growth should be under suitable "independence hypotheses". I guess that would be another technique. Having positive density is a super-strong condition on a set of primes. Heuristic arguments based on Sato-Tate, for example, tell you that the set of supersingular primes for a non-CM elliptic curve over Q is probably growing something like $O(x^{1/2}/log(x))$. The truth of that statement establishes both that the set is infinite and has density zero all in one stroke. Elkies didn't prove this though, he just took the more naive approach above.

share|cite|improve this answer
Kevin, I believe you're answering to the problem of constructing an "explicit" infinite set of primes of density 0. My admittedly vague question goes a bit in the other direction: suppose you start with some set of primes (defined by some conditions) and suppose that you can establish that its density is 0. What can you do next if you insist on proving that the set is infinite? It's just a case-by-case situation or there are some standard techniques you can try to apply? Are there interesting examples in the literature where a set of primes is shown to be infinite although its density is 0? – Andrea Mori Mar 2 '10 at 13:40
I think what he wants are "natural" sets of primes with density 0, such as twin primes or primes of the form n^2+1. The set of primes of the form x^2 + y^4 is infinite - does it have positive density? – Franz Lemmermeyer Mar 2 '10 at 13:42
@Andrea: OK, I added some comments on an explicit example---infinitude of supersingular primes. – Kevin Buzzard Mar 2 '10 at 13:55
@Franz: In some sense my example of a set of density 0 is no more or less natural than the n^2+1 example! For the set of numbers of the form n^2+1 is growing a lot more slowly than the primes: there are only about sqrt(x) of these less than x, but there are x/log(x) primes! So in some sense the two examples are "the same". – Kevin Buzzard Mar 2 '10 at 14:26

A neat way to show that a set of primes has zero density (within the primes) is to use the following form of the Green-Tao theorem:

Any set of positive density within the primes has arbitrarily long arithmetic progressions.

In particular, any set of primes which does not contain three (say) elements in arithmetic progression must have zero density.

If a set $P$ of primes has the property that $p_1,p_2\in P$ implies that $(p_1+p_2)/2\not\in P$, then the set $P$ has zero density in the primes.

As an immediate corollary, we get the (unconditional) result that the Mersenne primes (ones of the form $2^p-1$) have zero density.

This trick seems like it could be applied to many other natural sets of primes.

EDIT: Zero density for Mersenne primes is easy to get anyway, as Ben Weiss points out, and so is zero density for primes of form $n^2+1$, which would also follow from this method.

share|cite|improve this answer
+1 post, but as an aside, we already know the Mersenne primes have zero density; there are at most log(x) of them up to x (as they are powers of 2). – Ben Weiss Mar 2 '10 at 21:40
Ah, of course. Still, this method seems like it should be able to show some non-trivial results, if I could just think of them. – Thomas Bloom Mar 2 '10 at 21:47

There is a general strategy, which unfortunately is a failure because the information needed for success is scarcely ever available.

Let $A$ denote a set of primes, and $B$ the set of all products of powers of the primes in $A$. Then

$$ \prod_{p \in A}(1 - p^{-s})^{-1} = \sum_{n \in B}n^{-s} $$

by the Euler product formula. The Dirichlet series on the right hand side has nonnegative coefficients, so by a theorem of Landau, the point where the line of convergence crosses the real axis is a singularity of the sum function. If $A$ is finite, this singularity is at the origin. Thus if it can be established that the line of convergence is to the right of the imaginary axis, $A$ must be infinite (The only reason to invoke the theorem of Landau is to guarantee that there always is a singularity on the line of convergence). Of course, existence of a singularity of the sum function somewhere in the open right hand half plane would also work, even if we do not know the line of convergence.

This tends to fail because we can't get a good grip on $B$. Suppose $A$ is the set of twin primes (primes $p$ such that $p+2$ is also prime). Nothing really useful is known about the set $B$ of integers that are products of powers of twin primes. But if the accepted conjecture about the distribution of twin primes holds, there will be a singularity at $s = 1$, so $B$ cannot be really sparse.

As an example, there are infinitely many primes $p \equiv 1\pmod{4}$. Letting these primes, together with $2$, constitute $A$, we see that $B$ contains the values of the polynomial $n^2 + 1$, since the latter is never divisible by any prime $q \equiv 3\pmod{4}$. Then

$$ \sum_{n \in B}n^{-\sigma} \geq \sum_{m = 1}^{\infty}(m^2 + 1)^{-\sigma} $$

and thus the Dirichlet series over $B$ has a singularity in the half plane $\sigma \geq 1/2$. So $A$ has to be infinite.

Admittedly, this example is not that interesting.

share|cite|improve this answer

This is essentially a comment on Kevin Buzzard's answer, but because of its length and (I feel) importance, I am leaving it separately.

It is a consequence of Serre's open image theorem that the set of primes of supersingular reduction for a non-CM elliptic curve $E_{/ \mathbb{Q}}$ has density zero. (Conversely, for a CM elliptic curve, the set of such primes has density $\frac{1}{2}$.) Therefore, when Elkies showed -- by a method of proof strongly reminiscent of Euclid's argument, as you say! -- that there are infinitely many supersingular primes for every $E$, he was in particular giving a very interesting and natural example of an infinite set of primes of density zero.

It is interesting to try to generalize this example to analogous cases. For instance, Barry Mazur (my thesis advisor) asked me once if I could prove infinitude of primes of supersingular reduction for abelian surfaces $A_{/\mathbb{Q}}$ with quaternionic multiplication. (I had previously proven the analogue of Serre's open image theorem in this case, or rather reproven it, since Ohta had done it many years before.) I had no idea how to do this. My roommate, David Jao, ended up writing a thesis on generalizations of Elkies' proof to elliptic curves corresponding to $\mathbb{Q}$-rational points on Atkin-Lehner quotients of genus $0$ modular curves $X_0(N)$, in particular giving new examples of infinitude of supersingular primes for certain elliptic curves over quadratic imaginary fields. He tried the QM case (in which $X_0(N)$ is replaced by a Shimura curve) but couldn't make the argument work for a funny reason: although a QM abelian surface is much like a non-CM elliptic curve in its reduction behavior at most primes, it is like a CM elliptic curve in that it has some primes of guaranteed supersingular reduction, namely those primes dividing the discriminant of the quaternion algebra. He was able to set up a Euclid-Elkies style argument where you use the supersingular primes you already have to get another one, but he couldn't show that this "other one" wasn't one of the finitely many primes dividing the quaternionic discriminant! More recently, Baba and Granath established this result for QM surfaces of quaternionic discriminant $6$ and $10$.

(There is an analogous problem for Drinfeld modules in the function field case, but Bjorn Poonen famously gave an example of a Drinfeld module with no primes of supersingular reduction.)

I seem to vaguely remember that Serre's 1981 paper on applications of the Cebotarev density theorem and/or his 1997 JAMS paper on equidistribution contains further examples of this general type, but I wouldn't swear to it.

share|cite|improve this answer

This is very similar to the $n^2 + 1$ idea.

Friedlander–Iwaniec theorem

Up to some bound $M$ there are at most about $M^{3/4}$ values of $a^2 + b^4,$ only some of those are prime, and $ M^{3/4} / (M / (\log M)) = \frac{ \log M }{M^{1/4}} $

share|cite|improve this answer
Yes, this is a good example. It is much better to use a known theorem in place of a conjecture, and I was not very conversant in analytic number theory. Thanks for coming up with this. – Regenbogen Mar 3 '10 at 1:02

Here is a simple example of how one can use Dirichlet's theorem on primes in arithmetic progressions to find infinite families of primes with zero density:

Let $P$ be a set of primes {$p_1,\ldots,p_n,\ldots$} recursively defined such that $p_n\equiv 1 \bmod p_i$ for all $ i \lt n$.

1) The set $P$ is infinite by Dirichlet's theorem in arithmetic progressions, because if $p_1,\ldots, p_n$ are the first $n$ primes in $P$, then there is always a prime $p \equiv 1 \bmod p_1\cdots p_n$, and therefore $p\equiv 1 \bmod p_i$ for all $i=1,\ldots, n$.

2) The density of $P$ must be zero, because, if we fix $N>0$

$$\limsup_{x\to\infty}\frac{|\text{$p\leq x$ such that $p\in P$}|}{|p\leq x|} \leq \lim_{x\to\infty}\frac{|p\leq p_1\cdots p_N| + |\text{$p$ such that $p\equiv 1 \bmod p_1\cdots p_N$}|}{|p\leq x|}$$ $$\leq \lim_{x\to\infty}\frac{|p\leq p_1\cdots p_N|}{|p\leq x|} + \frac{|\text{$p$ such that $p\equiv 1 \bmod p_1\cdots p_N$}|}{|p\leq x|} = 0 + \frac{1}{\varphi(p_1\cdots p_N)} \to 0 \text{ as $N\to \infty$.}$$ Hence $\delta(P)=\lim_{x\to\infty}\frac{|p\leq x \text{ such that } p\in P|}{|p\leq x|}$ exists and it is zero.

share|cite|improve this answer
Hm, I don't think part (1) is correct -- certainly a $p$ such that $p = 1 mod p_1p_2...p_n$ exists, but there are likely new primes in between $p_n$ and $p$. In fact, unless I'm seriously misunderstanding you, (1) is false by Bertrand's postulate. – Harrison Brown Mar 2 '10 at 16:43
@Harrison, thanks! I guess I didn't need to define $P$ in that way, so I edited the definition, and I think it now should make sense. – Álvaro Lozano-Robledo Mar 2 '10 at 16:54
This is an ad-hoc construction. You could have just required that $p_n$ is the first prime after $n!$, or the prime just before $10^n$, and you would have got a set of density zero primes. – Regenbogen Mar 2 '10 at 17:09
Yes, this is a somewhat ad-hoc construction, but it's simply an example of a standard technique, as the poster asked, of how one can use Dirichlet's theorem to find sets of density zero. – Álvaro Lozano-Robledo Mar 2 '10 at 17:25

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.