Exploring primes of the form...

A number of deep problems about prime numbers emerge from the simple idea of taking a polynomial and trying to understand which primes appear among its values, and in particular whether there is a finite or an infinite number. We speak then of primes of the form $n^2+1$, etc.

I will walk you through a list of the most important problems of this type, with an invitation to explore them on your own! Even if some of these may be familiar to you, put yourself in the mindset of seeing the problem for the first time, or alternatively try to tweak the problem somehow, so that it becomes a new problem of your own.

The linear case

Take the polynomial $f(n) = 7n+3$, or any other linear polynomial $an+b$, with $a$ and $b$ being positive integers. Are there infinitely many primes in the arithmetic sequence $3, 10, 17, 24, 31, 38$, and so on?

In fact, this problem is the historical origin of the theory of L-functions. Using L-functions, Dirichlet proved in 1837 that indeed there are infinitely many primes in this sequence, and furthermore that the number of such primes up to some bound $X$ follows an asymptotic law similar to the prime number theorem. The theorem is really about the sequence $an+b$, for any pair of coprime integers $a$ and $b$.

Landau's fourth problem

At the fifth International Congress of Mathematicians in 1912, Edmund Landau stated four problems "unattackable at the present state of mathematics". The fourth of these problems (listed as the first in the excellent survey of Pintz) asked if there are infinitely many primes of the form $n^2 + 1$.

Euler's polynomial and other examples

Take any polynomial in one variable and check if the initial values are prime or not. Here is $n^2 + n + 23$, and you can increase the range of $n$ as required.

A famous example studied by Euler is the polynomial $n^2+n+41$, which stays prime for a remarkably long "streak" of $n$-values. Try it with the Sage code above! Another interesting example of higher degree is $3 n ^3 - 183 n ^2 + 3318 n - 18757$.

At the opposite end of the spectrum, consider $n^6 + 1091$. How far do you need to search in order to find its first prime value?

Each of the above examples is expected to generate an infinite list of primes. But this cannot be proven even for a single polynomial of degree 2 or higher! For a wonderful exposition of what's known and how to formulate precise conjectures for polynomials in general, have a look at Keith Conrad's Patterns in primes.

Primes of the form $x^2+ny ^2$

This sentence is the title of one of the most famous number theory textbooks ever written. It is a book by David Cox, which offers a path towards the Langlands program, by analyzing in detail the polynomials $x^2 + n y ^2$, with an increasingly abstract set of tools from algebraic number theory.

Try for yourself to investigate which primes appear among the values of $x^2 + 3y ^2$. This case has a clean and easy answer, related to quadratic reciprocity.

Some other historical examples (of a more complicated nature) studied by Euler are $x^2 + 14 y ^2$ and $x ^2 + 27 y ^2$. Try these on your own!

The openly available book by Hatcher (Topology of numbers) also explores (but in more elementary language) this world of quadratic forms, relying among other things on John Conway's topographs.

Finally, if you haven't seen the legendary one-sentence proof of Don Zagier for the case $x^2+y ^2$, check out this video by vcubingx on what might be one of the most beautiful proofs in all of mathematics.

Two variables, higher degree

A famous result by Friedlander and Iwaniec states that there are infinitely many primes of the form $x ^2+y ^4$. Another similar theorem by Heath-Brown says the same for $x ^3 + 2 y ^3$. These results have been generalized in various ways, and are representative of a kind of very difficult "sparse" problem type in this area.

For a more visual overview of these primes, consider colour-coding an $(x, y)$-grid, something like this:

An open problem is still the case $x^2+y ^3$, although this was resolved in 2025 by Merikoski (with an asymptotic expression for counting such primes), conditional on a certain technical (and unproven) hypothesis. The paper by Merikoski also contains references to the earlier literature on problems of this type.

All primes from a single polynomial

If you ever felt the urge to use the entire alphabet in an algebra problem, this is your lucky break. The set of primes is recursively enumerable (in the sense of computability theory, one definition being that the set is the range of a primitive recursive function). As a consequence, there is a polynomial such that its positive values are precisely all the prime numbers. A polynomial of this kind is described on Wikipedia; it is

\[ (k+2)(1-\alpha_0 ^2 - \alpha_1 ^2 - \ldots - \alpha_{13} ^2) \]

where the auxiliary variables $\alpha_i$ are given by these expressions in the 26 variables $a, b, c, d, \ldots , z$.

Tweaks and twists

Many of the above problems can be tweaked in various ways. For example, in the case of linear polynomials like $7n+3$, we may ask if the sequence contains streaks of consecutive primes. It was Ben Green and Terence Tao who proved in 2004 that the set of primes contains arbitrarily long arithmetic progressions. The current length record is a sequence of 27 primes of the form $224584605939537911+18135696597948930n$, for $n = 0, 1, 2, \ldots 26$.

An interesting "twist" of the Iwaniec-Friedlander problem is to ask for primes of the form $x^2 + y ^4$ where $y$ is also required to be prime. This problem was resolved in 2015 by Heath-Brown and Li.

Refined counting

The basic question for any of the above polynomials is whether it represents finitely or infinitely many primes. In many cases, like for $n^2+1$, even this basic question is completely open.

However, the basic question can be refined, leading to a much richer space of problems about asymptotics and error terms, as seen for example in the paper of Merikoski linked above. The simplest of all polynomials is perhaps $f(n) = n$, where the infinitude of primes is just Euclid's theorem, and the interesting part is about finding an asymptotic formula (like the Prime Number Theorem) and bounds on the error term in this formula (like the Riemann Hypothesis provides).