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

## (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"
• For the record, the answers below have been converted to Community Wiki answers for easier editing. Commented Sep 1, 2022 at 23:11
• One small point is with your unanswerable questions section where you wrote "Or any other order-2 or higher polynomial". We do know the answer to any, for example, order-$2$ polynomials in $n$ of the form $(n+j)(n+k)=n^2+(j+k)n+jk$, where $j$ and $k$ are any integer constants, with this being that there are not infinitely many primes of this form. I believe you meant only irreducible polynomials, such as the $n^2+1$ one you explicitly mentioned. Thus, I suggest changing "higher polynomial" to "higher irreducible polynomial". Commented Sep 2, 2022 at 0:35
• Regarding my comment above, even just limiting higher order polynomials to irreducible polynomials over the integers is not sufficient. For example, $n^2+n+2$ is irreducible, but it's also always even, so it has a prime value only of $2$ for $n = 0$. For more details about this, please see this answer (in particular, the Bunyakovsky conjecture that it references). Commented Sep 2, 2022 at 6:32
• To summarize it : We know much about the distribution of the prime numbers (thank to the powerful prime number theorem and its refinements) , but we know very little about concrete prime numbers. In particular we are unable to construct easily any new huge prime number. This is the reason for the prime hunt. There would be no record prime if we had a method to produce ever larger primes directly. Commented Sep 2, 2022 at 8:08
• Mills constant gives an expression prime for every positive integer $n$, but the catch is that we cannot calculate the constant efficiently precise enough to get more and more primes. Commented Sep 2, 2022 at 8:11

# 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.

## 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}$$

• Certainly worth mentioning the prime number theorem here, and (with suitable error terms) its corollary that generalizes Bertrand's postulate: for any $\epsilon > 0$ there exists $N$ such that for all $n \ge N$ there's a prime between $n$ and $(1 + \epsilon) n$. Then maybe a mention of Legendre's conjecture and related results: en.wikipedia.org/wiki/Legendre%27s_conjecture Commented Sep 2, 2022 at 6:26
• Nevertheless an excellent overview (+1) Commented Sep 2, 2022 at 8:03
• I upvoted the comment suggesting that the prime number theorem shouuld be mentioned here, but Legendre's conjecture doesn't belong in this answer. Commented Feb 7 at 1:13
• Added the PNT. Note that as this is set up as a Wiki, so anyone can edit! Commented Feb 9 at 2:03

# 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.

• 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.

• Hugely valuable! Small points: a conjecture is a statement, not a question - but you have written the Conjectures as questions. The same applies to hypotheses. Commented Sep 2, 2022 at 5:43
• You say that $n^2-n+41$ has only finitely many prime values. Is this really true? I hadn’t heard of it, and it sounds significant enough to deserve a reference if that is what you mean by “none of these expressions produce infinitely many primes.” Or do you mean something like “none of these expressions produce nothing but primes”? Commented Sep 2, 2022 at 5:50
• @MartinKochanski Technivally it should be "none of these expressions is *known to8 produce infinitely many primes. I'll clarify. Commented Sep 2, 2022 at 6:16
• That edit definitely helps! But I do still find that paragraph confusing - it says 'Note that some expressions are known to be "prime-generating functions" ' but it doesn't say what a "prime-generating function" is. Does the phrase 'some expressions are "prime-generating functions" ' have any technical meaning? (Could it say something more like: 'some expressions are famous for generating long sequences of primes'?) Commented Sep 2, 2022 at 6:27
• I think, we can safely assume that the WEAK Goldbach conjecture is solved. Commented Sep 2, 2022 at 8:16

# 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$$

• "An integer of the form $p=4k+1$ is prime if and only if it can be expressed as $p=a^2+b^2$". No, the "if" is wrong. For example, $65 = 4 \cdot 16 + 1 = 1^2 + 8^2$ but $65$ is not prime. Commented Sep 1, 2022 at 23:07