26

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!

Community
  • 1
Joseph O'Rourke
  • 149,182
  • 34
  • 342
  • 933
  • It's not clear to me what you mean by "restrictions" on primes, but this survey "Equidistribution and Primes" by Peter Sarnak might be interesting to you http://www.math.princeton.edu/sarnak/EquidPrimes.pdf – j.c. Oct 25 '11 at 19:46
  • @jc: I am not clear myself on what should constitute a nontrivial restriction! Thanks for the reference. Interesting that he touches on integral Apollonian packings... – Joseph O'Rourke Oct 25 '11 at 20:00
  • 4
    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
  • 2
    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
  • 5
    Not to quibble, but the x^2 + y^4 result is due to Friedlander and Iwaniec. – Micah Milinovich Oct 26 '11 at 00:39
  • 2
    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 02:43
  • Micah, thanks for the clarification. Is there not also some later work building on that of F and I by Heath-Brown, possibly involving a cubic polynomial representing many primes? Gerhard "Ask Me About System Design" Paseman, 2011.10.26 – Gerhard Paseman Oct 26 '11 at 18:35
  • @GP: I think you are referring to this paper of Heath-Brown, http://www.springerlink.com/content/rv25938237376nk8/ – Micah Milinovich Nov 06 '11 at 19:35
  • 1
    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 08 '11 at 15:26

4 Answers4

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 Thorne
  • 7,199
  • 1
    @Frank: Insightful point that difficulty is produced by mixing multiplicative with additive conditions! – Joseph O'Rourke Oct 26 '11 at 00:49
  • 10
    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 03:26
  • 1
    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
23

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

Joël
  • 25,755
  • An erudite and convincing answer! – Joseph O'Rourke Oct 26 '11 at 01:37
  • (In 5 you are using x and y for two different things) – Mariano Suárez-Álvarez Oct 26 '11 at 02:41
  • Daer Joel, are there examples where you can guarantee infinitely many primes among a sequence with very low density? – Gil Kalai Oct 26 '11 at 10:45
  • 3
    @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
  • Dear Gil, among the examples given above, only Noam Elkies's result (5.1) concerns a list of primes with density (conjecturally) 0: all others have positive density, so you're right to insist on that, because that's a clear separation between the results obtained by "algebraic number theory" (as in my example), and the conjectures concerning the list of Mersenne primes or Fermat primes which, even if they are proven infinite, will have density 0. This suggests me a lazy question: is it known that the number of primes p of the form n^2+1 has density 0? – Joël Oct 26 '11 at 14:43
  • @Timothy: and those primes have density 0? – Joël Oct 26 '11 at 14:46
  • In a sense, one could say that all results in my answer (except Elkies' which is an UFO) are based on one simple idea from analytic number theory, discovered by Dirichlet (namely that sometimes L-function's have a pole at $s=1$, and that this forces their number of Euler factors to be infinite, as explain in Franke's answer), based with a lot of deep work in algebraic number theory and algebraic geometry to make the most of this single idea. Indeed (i) is that idea + the formalism of Dirichlet character, Cebotarev and (ii) are that idea plus quite a bit of tricky Galois theory, etc. – Joël Oct 26 '11 at 14:51
  • @Joël: regarding your density $0$ question. The number of all numbers of the form $n^2 + 1$ up to $x$ is about $\sqrt(x)$. So even if every single of these number were prime these are still much less then the $x / \log x$ primes up to $x$, so their relative denisty in the primes is guaranteed to be $0$, without any specific information on primes of that form. Likewise, for the Friedlander-Iwaniec result; there are only about $x^{3/4}$ numbers of that form at all below $x$, and so the relative denisity is again $0$. –  Oct 26 '11 at 19:02
  • Thanks Quid, and shame on me! That was really a stupid question. In my head I thought: "there are at most $\log \log n$ Mersenne primes less than $n$, and $\sqrt{n}$ primes of the form $a^2+1$, so since the number of primes less than $n$ is roughly in $\log n$ (!!!!), it is clear that the density (in the primes) of Mersenne primes is 0, but that's not clear for primes of the form $a^2+1$. Let's ask the question." :-) – Joël Oct 26 '11 at 19:30
  • Perhaps $a^2+p^2$ (Fouvry/Iwaniec) is also of interest, where they truly handle $\sum_{a,b}\rho(b)\Lambda(a^2+b^2)$ for suitable weights $\rho$ getting an asymptotic, and $\rho=\Lambda$ is suitable. http://matwbn.icm.edu.pl/ksiazki/aa/aa79/aa7935.pdf One idea, also in Fried/Iw $(a^2+b^4)$ is that roots of $x^2+1$ mod $d$ are spaced at $1/D$ for $d\sim D$, not $1/D^2$ as might guess. Fried/Iw is delicate, using lacunarity of the squares in bilinear estimate, but the broad idea is already in Fou/Iw. For $x^3+y^3$ Heath-Brown, rather uses a multi-dimensional large-sieve for a bilinear estimate. – Junkie Oct 26 '11 at 20:56
  • 2
    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
7

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 Quas
  • 22,470
  • @Anthony: Excellent example, and clearly a nontrivial restriction. Thanks! – Joseph O'Rourke Oct 26 '11 at 00:46
  • 1
    Maybe the result or proof of Green about the AC0 orime number theorem from here http://mathoverflow.net/questions/57543/walsh-fourier-transform-of-the-mobius-function 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
  • 1
    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 04:57
3

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.