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!
Best Answer
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.