Are there infinitely many primes of the form [X]? We probably don't know.

Question

Are there infinitely many primes of the form [expression]?

(We probably don't know. Sorry.)

This question appears pretty often, with any number of various expressions. The sad reality is that the answer, more likely than not, is that we don't know. What we don't know about the prime numbers vastly outnumbers what we do know. Related questions regarding gaps between primes are common as well. For instance:

---

• Common unanswerable questions posted to M.SE
  • Are there infinitely many primes of the form $n^2+1$ ? Or any other order-2 or higher polynomial. We think there probably are, but it's unproven, and going to be hard to prove.
  • Are there infinitely many primes of the form $2^k + a$ ? Or any other exponential expression.
  • Are there infinitely many prime gaps of the form [expression]?
  • Does [this formula] generate all the prime numbers? (Though this is often "No.")

Note: There are other questions that ask "What do we know about primes of the form [expression]?" This is a very different question, and can generate good discussion! They're also rarer.

---

I felt we could use an article that could be pointed to, edited, referenced, and the like, for questions of this type. Hopefully the community will find this useful.

This post will organize some answers--both positive and negative--to the question for various expressions, and provide informative links and proofs where proofs are available. Please edit in more information if you think it's useful! Note that the questions and answers here are not intended to deal with error terms, sieve bounds, asymptotics, etc. We're just keeping it nice and simple. Even the Prime Number Theorem is outside the scope here.

---

Terminology used below:

• The gap function, $g(p)$, is the difference between two consecutive primes. That is, $g(p_i) = p_{i+1} - p_i$.
• The prime-counting function, $\pi(x)$, counts the number of primes equal to or less than $x$.
• "ATIM": "Are There Infinitely Many"

Answer 1

Theorems About Primes: Things We Know

A theorem is a proven mathematical statement. These statements are true, and their truth is accepted by the mathematical community at large.

---

Forms of Prime Numbers

Theorems or results showing the infinitude of primes of certain forms.

---

• Euclid's Theorem

  There are infinitely many prime numbers. This is the most basic and important proven result. Sometimes noted as Euclid's second theorem.

---

• Lemmata About a Lack of Primes AKA "Nothing to See Here, Move Along"

  Examples of expressions that are known to generate no primes or almost no primes.

  There are almost no primes of the form $n^2-1$, or $n^3-1$, or any other factorable polynomial. If it can be factored as a polynomial, it can be factored as an integer. When they do produce primes, it's because $n$ is very small. For instance, $n^2-1 = (n+1)(n-1)$ and $n^3-1 = (n-1)(n^2+n+1)$. These expressions produce primes for $n=2$, because one of the factors is $1$.

  There are almost no primes of the form $n^2+n+2$, or $n^3-n^2+8$, or any other expression that is always even. These can be tricky to spot, but remember that the parities of $n, n^2, \cdots, n^k$ are all the same: they're all even, or all odd. Since two odd numbers and two even numbers both add to an even number, both of the expressions here must produce even numbers.

  There are almost no tuples of primes of the form $(n, n+2, n+4)$, or $(n, n+4, n+8)$, or any other tuple that must include a multiple of $3$, or $5$, or some other divisor. The single exception, only true for the first example, is $(3,5,7)$.

---

• Dirichlet's Theorem [Primes in arithmetic progression]

  If $a$ and $d$ are positive coprime integers, there are infinitely many primes in the arithmetic progression $an+d$, where $n$ is a positive integer.

---

• Sum of Two Squares Theorem [Fermat]

  A prime can be expressed as $p = a^2 + b^2$ if and only if it is of the form $p = 4k+1$. As Dirichlet's theorem tells us there are infinitely many primes of the form $4k+1$, it follows that there are infinitely many primes of the form $a^2+b^2$. These are sometimes called the Pythagorean primes, as each is square of the hypotenuse of a primitive right triangle.

---

• Friedlander-Iwaniec Theorem

  There are infinitely many primes of the form $a^2+b^4$.

---

Prime Gaps

Theorems or results about the distances between prime numbers, especially consecutive prime numbers.

---

• Lemma [Name?]

  The gap function grows arbitrarily large. Or stated differently: for any integer, there is a gap between consecutive primes at least as large as that integer.

---

• Bertrand's Postulate [AKA Chebyshev's Theorem]

  For all $n > 3$, there is at least one prime number $p$ such that $n < p < 2n-2$.

---

• Bounded Gaps [Zhang, Maynard, Tao, Polymath]

  There are infinitely many prime gaps of length $246$ or shorter. Assuming the Riemann Hypothesis and the Elliot-Halberstam Conjecture, this number is instead $6$. (Link is to a very high-level paper.)

---

Distribution of Prime Numbers

• Prime Number Theorem

  The prime number theorem states that the prime-counting function $\pi(x)$, the number of primes less than or equal to $x$, asymptotically behaves as:

$$\pi(x) \sim \frac{x}{\log x}$$

Answer 2

Conjectures About Primes: Things We Don't Know

In general, a conjecture is a statement that is unproven, but believed by many mathematicians, perhaps even a vast majority of them, to be true--though this is not always the case. In some cases, disproving one of these conjectures would disrupt a lot of other math in many, many fields, though such disruptions are often welcomed as paradigm-breakers.

Any list of conjectures about primes is much longer than the list of theorems about primes. One could reasonably suggest there are infinitely many possible conjectures about primes. (This list is therefore incomplete.)

These conjectures are presented as questions, rather than statements. This is partially to be certain they can't be interpreted as true, and partly to help direct search engines. Note that some related theorems are included near the conjectures to which they are related--that is, where a conjecture has been partly confirmed.

---

Forms of Prime Numbers

---

• Schinzel's Hypothesis H

  Briefly: for any finite set of irreducible polynomials $\{P_1(n), P_2(n), \cdots\}$ that do not have a common prime divisor, are there infinitely many integers $n$ where all of these polynomials have prime values?

  Hypothesis H, in some senses, includes many of the conjectures below.

  The Bateman-Horn conjecture predicts the asymptotic frequency of the values of $n$ that give primes for all of the polynomials.

  • Note that some expressions are known to be "prime-generating functions," perhaps the best known of which was presented by Euler: $n^2-n+41$, which generates primes for $1 \le n \le 40$. However, it is unknown whether any of these expressions generate infinitely many primes.

---

• Twin Prime Conjecture

  Are there infinitely many primes $p$ for which $p+2$ is also prime? This may be the best-known unsolved problem in mathematics. So simple, yet unproven.

  • Related Theorem: Chen's Theorem

    While we're still uncertain about twin primes, Chen showed that there are infinitely many primes such that $p+2$ is either a prime or a semiprime (a product of two primes).

---

• Goldbach's Conjecture

  Can every even integer greater than $2$ be expressed as the sum of two prime numbers? Note that Chen's Theorem applies to the Goldbach conjecture as well; that is, every even number is the sum of two primes or a prime and a semiprime.

  • Related: Helfgott's Theorem (previously Goldbach's Weak Conjecture)

    Can every odd number greater than $5$ be expressed as the sum of $3$ prime numbers? This is generally considered proven, though many references still mention it as a conjecture. Proof was presented in 2013, and the mathematical community has widely accepted the proof. While the proof hasn't been published in a journal, the fact that it's about 250 pages long makes that harder. (Link to discussion on MSE from Dr Helfgott himself. His book is here, but if you can understand it, you likely don't need this page.)

  • Related Theorem: Chen's Theorem

    On the same paper that proves the approximate version of twin prime conjecture, Chen shows that every large even integer $N$ there exists a prime $p$ such that $N-p$ is a prime or a semiprime.

---

• Hardy and Littlewood's Conjectures

  Hardy and Littlewood presented two conjectures, and it has since been proved that neither can survive while the other lives. The first is an extension of the twin prime conjecture regarding larger groups of primes ($k$-tuples).

  The second asks: Is the following statement about the prime counting function true? $$\pi(x+y) \le \pi(x) + \pi(y)$$

  As of now, neither conjecture has been answered positively or negatively.

---

• Unnamed, unanswered questions about primes of form [X]

  • Are there more than five Fermat primes (form $2^{2^n} + 1$), which is prime for $0 \le n \le 4$?
  • Are there infinitely many Mersenne primes (form $M_p = 2^p - 1$)?
  • ATIM Sophie Germain Primes and Safe Primes? If $p_b = 2p_a +1$ and both $p_a, p_b$ are prime, $p_a$ is a Sophie Germain Prime, and $p_b$ is a Safe Prime.
  • ATIM Fibonacci or Lucas primes, primes appearing in those sequences?
  • ATIM Euclid primes (or primorial primes) (form $p_n\# \pm 1$)?
  • ATIM factorial primes (form $p = n! \pm 1$)?
  • And many, many more on Wikipedia.

• Common unaswerable questions posted to M.SE

  • ATIM primes of the form $n^2+1$ ? Or any other order-$2$ or higher irreducible polynomial, in particular those that meet the conditions of the Bunyakovsky conjecture? We think there probably are, but it's unproven, and going to be hard to prove.
  • ATIM primes of the form $2^k + a$ ? Or any other exponential expression?
  • ATIM prime gaps of the form [expression]?

---

Prime Gaps

• Legendre's Conjecture

  For all natural numbers $n$, is there a prime number such that $n^2 < p < (n+1)^2$?

  • Oppermann's Conjecture

    Going a step further than Legendre: for all natural numbers $n$, are there two prime numbers such that $n^2 < p_1 < n(n+1) < p_2 < (n+1)^2$

  • Note: It has been proven that for all $n$, some prime exists such that $n^\mathbf{3} < p < (n+1)^\mathbf{3}$.

  • Andrica's Conjecture

    Is the following statement about the prime gap function true? $$g(p_i) \le \sqrt{p_i} + 1$$

---

• Cramér's conjecture

  There are several variants of this conjecture and no standardized terminology, but it is reasonable to refer to the conjectures as follows:

  • Weak Cramér conjecture

    Are $g(p_i)$ bounded by a constant multiple of $(\log p_i)^2$? In other words, is $\limsup_{i \to \infty} \frac{g(p_i)}{(\log p_i)^2}$ finite?

  • Strong Cramér conjecture

    Does $\limsup_{i \to \infty} \frac{g(p_i)}{(\log p_i)^2} =1$? The answer is believed to be negative as modern probabilistic models favor the Cramér-Granville conjecture.

  • Cramér-Granville conjecture

    Does $\limsup_{i \to \infty} \frac{g(p_i)}{(\log p_i)^2} = 2e^{-\gamma} \approx 1.1229$ (where $\gamma$ is the Euler-Mascheroni constant)?

  • Firoozbakht's conjecture

    Does $p_j^{1/j} \lt p_i^{1/i}$ whenever $i \lt j$? The answer is believed to be negative as a positive answer implies the strong Cramér conjecture.

Answer 3

Simple Proofs of Theorems

To be posted below: simple proofs of the simple theorems discussed.

---

Euclid's Theorem: No finite set of prime contains all the prime numbers.

Proof Consider a finite set of $n$ prime numbers $P = \{p_1, p_2, \cdots p_n\}$. Calculate $Q = p_1p_2p_3 \cdots p_{n-1}p_n + 1$. $Q$ must be prime or composite. If it is prime, then $P$ does not contain all the prime numbers, and the proposition is true. If $Q$ is composite, it must be divisible by at least two prime numbers. However, it is indivisible by $p_1, p_2$, and all other elements of $P$. Therefore at least two primes numbers are absent from $Q$, and the proposition is proven.

---

Proof (after Filip Saidak (2005)) Let $n$ be a positive integer greater than $1$. Since $n$ and $n+1$ are coprime, $n(n+1)$ must have at least two distinct prime factors. Similarly, $n(n+1)$ and $n(n+1)+1$ are coprime, so $n(n+1)(n(n+1) + 1)$ must contain at least three distinct prime factors. This process can be extended infinitely. $\square$