Why so difficult to prove infinitely many restricted primes?

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!

-
I have no comment on why these questions are difficult, but you can make a naive prediction about the number of palindromic primes. Between $2^n$ and $2^{n+1}$, there are approximately $2^{n/2}$ palindromes. In the range $[2^n,2^{n+1})$, the density of primes is essentially $1/n$ by the prime number theorem. So you would expect to see $c2^{n/2}/n$ palindromic primes in the range. So you should conjecture that there's an infinite number of them - and that the number of palindromic primes up to $N$ should be $\sim \sqrt{N}/\log N$. –  Anthony Quas Oct 25 '11 at 20:00
You might also be interested in Schinzel's hypothesis H, which generalizes several of these observations. You might also ask an expert how hard it is to prove a result like Dirichlet's theorem on arithmetic progressions, or Heath-Brown's result (x^2 + y^4?). Gerhard "Ask Me About System Design" Paseman, 2011.10.25 –  Gerhard Paseman Oct 25 '11 at 20:15
Not to quibble, but the x^2 + y^4 result is due to Friedlander and Iwaniec. –  Micah Milinovich Oct 26 '11 at 0:39
Re: palindromic primes, I might add that Sylvain Col has made great strides in understanding the distribution of palindromes in arithmetic progressions. This allowed him to use sieve methods to show that in base 10, there are infinitely many palindromes which have at most 372 prime factors (counted with multiplicity). –  Anonymous Oct 26 '11 at 2:43
I tried to ask around to see if there are cases where infinitely maint primes are knowm for sets with upper densities (for length n intervals) smaller than n^{-1/2}. I am not aware of any result of this kind. Elkies' result is conjecturally of density n^{-1/2} (and provably n^{-1/4}. People certainly did try to prove infinitely many primes for sets of density n^{-2/3} that appear naturally. But there is no sucess. I also asked around if such n^{-1/2} density is a reasonable barrier to expect (I had some vague reasons for that), but people dont think so. (n^{-1+o(1) looks beyond reach.) –  Gil Kalai Dec 8 '11 at 15:26

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.

-
@Frank: Insightful point that difficulty is produced by mixing multiplicative with additive conditions! –  Joseph O'Rourke Oct 26 '11 at 0:49
Sometimes, we can mix additive and multiplicative structure by showing that the additive structure is somehow "multiplicatively dispersed". For instance, if $\alpha$ is an irrational, then the bilinear form $\sum_n \sum_m a_n b_m e(\alpha nm)$ has a lot of cancellation, which (by the work of Vinogradov, Vaughan, etc.) can be combined with the multiplicative structure of the primes to show that $\sum_p e(\alpha p)$ has a lot of cancellation also. In particular, one can say things like "there are infinitely many primes $p$ for which $\sqrt{2} p$ is within $10^{-10}$ of an integer". –  Terry Tao Oct 26 '11 at 3:26
The first sentence of Frank's answer is right to the point. Another example of a very hard problem connecting multiplicative and additive properties of numbers is Catalan's conjecture. –  Péter Komjáth Oct 26 '11 at 14:20

"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).

-
An erudite and convincing answer! –  Joseph O'Rourke Oct 26 '11 at 1:37
(In 5 you are using x and y for two different things) –  Mariano Suárez-Alvarez Oct 26 '11 at 2:41
Thanks Mariano, I changed it. –  Joël Oct 26 '11 at 3:39
@Gil: This might not be sparse enough for you, but Friedlander and Iwaniec showed that there are infinitely many primes of the form $a^2 + b^4$. –  Timothy Chow Oct 26 '11 at 14:40
Indeed the a^2 +b^4 result is very miraculous as the density is n^{1/4}. (There are roughly n^{3/4} elements in the sequence in the interbal [1,n]. Naively I would regard such a result for sequences of density below n^{-1/2} as a huge miracle. (E.g. if the number of elements in [1,n] is say n^{1/3}.) This is because i thing (perhaps also naively) that results about infinitely many primes in sequences of density larger than n^{-1/2+epsilon} can sometimes be derived from GRH. But maybe I am wrong and there is no essential difference (beside technicalities) between a^2+b^4 and say a^5+b^7+c^8. –  Gil Kalai Oct 27 '11 at 22:22

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.

-
@Anthony: Excellent example, and clearly a nontrivial restriction. Thanks! –  Joseph O'Rourke Oct 26 '11 at 0:46
Maybe the result or proof of Green about the AC0 orime number theorem from here mathoverflow.net/questions/57543/… can be used to show that if f(n) is a boolean function described by an AC0 circuit depending on the digits of n and if the set of integers so that f(1)=1 is not of very low density then there are infinitely many primes for which f(n)=1. (Of course we cannot expect it when f has low density because being binary-palidromic as well as being a Mersenne prime or a Fermat prime are expressible by such circuits. –  Gil Kalai Oct 26 '11 at 11:12
A similar remark is that recent results of Bourgain may apply (using GRH and perhaps even unconditionally) to the question "are there infinitely many primes so that in their binary expansion the number of '1's is at least 51% of the digits. (Or at most 49% of the digits). so instead e.g. of showing that the sum of all powers of 2 from 0 to m is infinitly often prime you show something like that for the sum of some sum of "many" distint powers of 2. –  Gil Kalai Oct 28 '11 at 4:57

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.

-
Thanks for the reference to Chen primes, of which I was ignorant: en.wikipedia.org/wiki/Chen_prime –  Joseph O'Rourke Oct 25 '11 at 21:46
You are welcome! –  quid Oct 25 '11 at 23:34