Why so difficult to prove infinitely many restricted primes? - MathOverflow

Why so difficult to prove infinitely many restricted primes?

2011-10-25T19:40:09Z

I wondered whether there were an infinite number of palindromic primes written in binary (11, 101, 111, 10001, 11111, 1001001, 1101011, ...) and quickly discovered that it is unknown (OEIS A117697). Indeed, even though almost all palindromes in any base are composite, whether there are an infinite number of palindromic primes in any base is unknown (Wolfram article).

Earlier (in the MO question, "Why are this operator’s primes the Sophie Germain primes?"), I learned that it is unknown if there are an infinite number of Sophie Germain Primes. In addition, is not known if there are an infinite number of Mersenne primes, Fibonacci primes (OEIS A005478), Wilson primes, Cullen primes, not to mention prime twins, quadruplets, sextuplets, and $k$-tuples. No doubt this list of our ignorance could be extended.

It appears to the naïve (me) that there is no nontrivial restriction on the primes for which we know there remain an infinite number in the restricted sequence.

Q1. Is this superficial perception in fact true?

Q2. If so, is there any high-level reason why it is so difficult to prove these statements? Or is each difficult for its own idiosyncratic reason?

I ask this out of curiosity, without expert knowledge of number theory. Thanks for enlightening me!

Questions Answered. Thanks for the wonderfully rich and informative answers! Essentially both questions have been answered: My superficial perception (Q1) is not in fact accurate, as detailed in the examples provided by quid, Anthony Quas, and Joël, augmented by comments by several. A high-level reason (Q2) explaining the difficulty in the examples I listed was nicely encapsulated by Frank Thorne, enriched by appended comments. Thanks!

Answer by quid for Why so difficult to prove infinitely many restricted primes?

2011-10-25T21:39:58Z

I would say for Q1 the answer is, no. For some of the things mentioned there are relatively close cognates that are known. For example, for Twin Primes there is a result due to Chen that says that there are infinitely many primes at distance $2$ from a number that is a prime or a product of two primes. Noone know how to get rid of the 'or...' and prove Twin Primes but the general type of statement is similar. Or, there are results on small gaps between primes (in particular relatively recent ones by Goldston, Pintz, Yildirim) that prove the existence of primes that are 'exceptionally' close together.

For Q2, many such conjectures are based on the assumption that the primes behave more or less like a random set (of a density one knows by the Prime Number Theorem) and there are some additional 'local' restrictions; mainly congruence conditions. The problem then is to actually prove that the primes behave sufficiently randomly to give a certain result.
Here depending on the precise condition more or less or different types of random-like behavior are needed; and thus sometimes one can solve them sometimes not. A nice overview is given in the following talk by Tao .

For problems that amount to solving systems of linear equations in the primes which contains some of the classical problems mentioned the introduction of the paper Linear equations in Primes by Green and Tao gives a good impression what properties of the system have an effect on the difficulty of the problem.

Answer by Frank Thorne for Why so difficult to prove infinitely many restricted primes?

2011-10-25T23:13:28Z

To give a vague answer, I think these questions are difficult because they mix multiplicative conditions (being prime) and additive conditions (as in the twin prime case).

Basically all results about primes that I can think of come down to unique factorization of the integers. For example, the zeta function is given as

$$\zeta(s) = \sum_n n^{-s} = \prod_p (1 - p^{-s})^{-1}.$$

The right hand side is why the zeta function tells you about prime numbers, but the left hand side is what typically helps you prove theorems. For example, Riemann noticed that the left side looked like something similar to what Poisson summation is good for, and hence proved analytic continuation and the functional equation.

On a simpler level, one nice proof that there are infinitely many primes is to observe that $\sum_n 1/n$ diverges, by elementary calculus, and therefore the right hand side diverges for $s = 1$ as well.

Gerhard Paseman suggested looking at arithmetic progressions, and I think this is an extremely instructive example. Looking at the sum of $n^{-s}$ restricted to an arithmetic progression, you don't have any equation like the above. Conversely, if you take a product over only the primes $p$ in some arithmetic progression, you don't get anything nice like the left side. However, if you let $\chi$ be a Dirichlet character, e.g., a homomorphism from $(\mathbb{Z}/N)^{\times}$ to $\mathbb{C}$, then you get the Dirichlet $L$-function

$$L(s, \chi) = \sum_n \chi(n) n^{-s} = \prod_p (1 - \chi(p) p^{-s})^{-1}.$$

In some way this is forcing a round peg into a square hole: the arithmetic progression condition couldn't be handled directly. But it can be written as a linear combination of Dirichlet characters, and once you force everything to be multiplicative, the machinery (Poisson summation, etc.) all works.

So in other words, IMHO, the question isn't "why is the twin prime conjecture difficult", but "why can we prove anything about the primes at all?" Our toolbox is, in my experience, still pretty limited.

Answer by Anthony Quas for Why so difficult to prove infinitely many restricted primes?

2011-10-25T23:27:11Z

Here is another paper indicating that the answer to Q1 is no:

Mauduit and Rivat, Sur un problème de Gelfond: la somme des chiffres des nombres premiers. (French. English, French summary) [On a problem posed by Gelʹfond: the sum of digits of primes] Ann. of Math. (2) 171 (2010), no. 3, 1591–1646.

They fix $q\ge 2$ and $m$ such that $\gcd(q-1,m)=1$. The paper considers the digit sums of prime numbers written out in base $q$ and reduces that sum modulo $m$. They show that this quantity is equally distributed in residue classes modulo $m$.

I would argue that this gives non-trivial conditions (e.g. binary digit sum is odd) for which there are infinitely many primes.

Answer by Joël for Why so difficult to prove infinitely many restricted primes?

2011-10-26T01:23:27Z

"It appears to the naïve (me) that there is no nontrivial restriction on the primes for which we know there remain an infinite number in the restricted sequence. Q1. Is this superficial perception in fact true?"

No, it is definitely not true. Here are a few examples:

(1) Let $a>0, b$ be two relatively prime integers. Are there infinitely many prime of the form $an+b$? Yes.

(2) Let $P(X)$ be a monic polynomial of degree $n$ with coefficients in $\mathbb{Z}$. Are there infinitely many prime $p$ such that $P(x)$ has $n$ distinct roots mod $p$? Yes.

(3) Let $X$ be a projective smooth variety over $\mathbb{Q}$, $\chi$ the Euler-Poincaré characteristic of the manifold $X(\mathbb{C})$, $n$ an integer. Are there infinitely many prime $p$ such that the the number of points of $X(\mathbb{F}_p)$ is $\chi$ modulo $n$? Yes. Same question with $X(\mathbb{C})$ replaced by $X(\mathbb{R})$? Yes.

(4) Are there infinitely many primes $p$ that can be written $a^2+b^2$? Yes. $a^2+8b^2$ with $b$ odd? Yes...

(5) Let $a,b$ be two integers (such that $4a^3+27b^2 \neq 0$), $a_p$ the number of solutions of $y^2=x^3+ax+b$ modulo $p$, minus $p$. Are there infinitely many primes $p$ such that $a_p=0$? yes. Are there infinitely many primes $p$ such that $a_p \neq 0$? Yes. Let $\alpha$ and $\beta$ be two reals between $-1$ and $1$, and $\alpha$ smaller than $\beta$; are there infinitely many primes $p$ such that $\alpha < a_p/2 \sqrt{p} < \beta$? Yes.

One could multiply those examples. They all belong to algebraic number theory, and a line of thought that has begun with Dirichlet's theorem (example 1), and has developed into the modern theory of algebraic number fields, Galois representations, automorphic forms and the Langlands program. Perhaps the most salient result is Cebotarev's density theorem, of which (1) is a very special case, (2) is a consequence, (3) also a consequence in combination with Grothendieck's étale cohomology, (4) also a consequence. Only (5) lies really beyond this result, due respectively to Noam Elkies, Jean-Pierre Serre, and the long list of people responsible for the proof of Sato-Tate.

Admittedly, there are many natural and interesting sequences of integers in which we can reasonably conjecture that there are infinitely many primes, and to which this line of thought is not supposed to apply (Mersenne's primes, to name one).