11
$\begingroup$

On p.177 of Number Theory Revealed: A Masterclass by Andrew Granville, the author states that "One can ask for prime values of polynomials in two or more variables." (though he later mentions Landau's $n^2+1$ conjecture so I'm not sure why single-variable polynomials are omitted). For example, there are some classical results, like Fermat's Christmas theorem and Euler's $6n+1$ theorem. More recent results include the Friedlander-Iwaniec theorem, which states that there are infinitely many prime numbers of the form $a^2+b^4$ for integers $a$ an $b,$ and the result of Heath-Brown on the infinitude of primes of the form $x^3+2y^3$ for integers $x$ and $y.$ Granville's book mentions other recent advances by Maynard and collaborators of Heath-Brown and Iwaniec.

Initially, I wondered why the Friedlander-Iwaniec theorem is considered to be a breakthrough, so I asked Why does the infinitude of primes of a certain form matter? on math.stackexchange, but it was closed for being "opinion-based". Granville's book cleared up a part of this question for me because it states that the Friedlander-Iwaniec theorem was the first example in which the polynomial is "sparse" in taking on integer values, and that later results of the same type based on norm forms were inspired by Friedlander-Iwaniec (although I don't know to what extent the proofs of the former are related to the proof of the latter).

My question is this: is the area of exploration quoted at the beginning of this post an island in that it is considered to be an inherently interesting question requiring no further justification, or are there external motivations for pursuing it? Some satisfactory motivations (this list is by no means exhaustive) might be that other problems reduce to it, that the techniques developed in the course of solving these problems are widely applicable elsewhere, real world applications (e.g., cryptography), or maybe these are instances of much more general problems for which "Mathematics is not yet ripe" in the words of Erdős.

$\endgroup$
14
$\begingroup$

I think questions about prime values of polynomials are considered inherently interesting.

All these questions are special cases of Bunyakovsky's conjecture, or, if you want, the Bateman-Horn conjecture. Certainly mathematics is not yet ripe for such problems.

You can also view them as special cases of the general problem of when special sequences of numbers are prime. One generally expects to see transfers of techniques from one special case of this problem to another, but not as much with other areas of number theory and mathematics. So to a large extent I think the results on primes-of-a-special-type problems that are considered most interesting are those that point to way to further solution of primes-of-a-special-type problems.

One could also note that primes of the form $a^2+b^4$ is a special case (in some sense) of primes of the form $a^2 +1$, since infinitely many primes of the form $a^2+1$ implies infinitely many primes of the form $a^2+b^4$. (Of course this is the reverse of the special case direction between the numbers themselves.)

I don't think many who work on these problems are motivated by applications to cryptography. As Ben Smith points out in the comments, there are some applications of Bateman-Horn to cryptography, where we would like to find primes represented by special polynomials for use in certain cryptographic algorithms. Conditional on not just the existence of such primes but the Bateman-Horn conjecture predicting how many there are in a large interval, we can generate such primes in polynomial time by randomly sampling values of the polynomial and primality testing.

However, since these conjectures are very very hard to prove, but we have very strong reasons to believe that they are true, working on them might not help with cryptography very much.

$\endgroup$
2
  • 1
    $\begingroup$ We might want to avoid these special primes for RSA, but primes represented by polynomials do have cryptographic applications, especially in pairing-based cryptography. See e.g. eprint.iacr.org/2006/372 for a survey of constructions: you'll see (univariate) polynomial-value primes appearing in several places to get efficient cryptographic parameters, and Bateman-Horn used to (conditionally) prove heuristic algorithmic running times. $\endgroup$ – Ben Smith Jun 22 '20 at 7:05
  • $\begingroup$ @BenSmith Thanks! I edited my answer to account for this. $\endgroup$ – Will Sawin Jun 22 '20 at 11:49
10
$\begingroup$

Suppose you suspect that among some subset $\mathcal{S}$ of the natural numbers, there ought to be infinitely many primes. How would you confirm that this is indeed the case?

Clearly, the "bigger" $\mathcal{S}$ is (measured in terms of natural density), the easier the question should be. The biggest set is of course $\mathbb{N}$ itself, and it was a highly non-trivial theorem of Euclid that confirmed this. What about the next most obvious "big" sets, the arithmetic progressions? Indeed, consider the set $\mathcal{S}(a; q)$ by

$$\displaystyle \mathcal{S}(a; q) = \{qx + a : x \in \mathbb{N}\}.$$

In the special case $q = 4, a = 3$ one can use Euclid's argument again to show that there are infinitely many primes in the set (but far from the correct density). A much more difficult argument shows that the case $q = 4, a = 1$ also gives infinitely many primes. But we expect that there are infinitely many primes in $\mathcal{S}(a; q)$ whenever $\gcd(a,q) = 1$. This is not known until the work of Dirichlet, almost 2000 years after Euclid!

The most extensive generalization of the theorem of Dirichlet known is the Chebotarev density theorem, which shows that in any number field there are infinitely many primes which split completely (over simplifying here).

So far, all of the sets considered have log density one. If we put $\mathcal{S}(X) = \# \{n \leq X : n \in \mathcal{S} \}$ then the log density is the infimum among all non-negative real numbers $\delta$ such that $\mathcal{S}(X) < X^{\delta}$ for all $X$ sufficiently large. Log density one sets can still be very very hard to count primes in: indeed, we expect the set of primes $p$ such that $p + 2$ is also prime to be infinite, and this set (if infinite) is expected to have log density one.

Thus, producing an infinite set of primes which have log density less than one is a formidable task. Both the Friedlander-Iwaniec theorem and Heath-Brown's theorem are examples where this can be achieved. These should be considered highly exceptional in the sense that similar, perhaps even easier looking polynomials are not amenable to their methods! Perhaps the most infamous is the polynomial $F(x,y) = 4x^3 - y^2$, which counts discriminants of elliptic curves in short Weierstrass form.

$\endgroup$
3
  • 4
    $\begingroup$ Describing Euclid's proof of the infinitude of the primes as "highly nontrivial" is rather excessive. By that measure, all proofs that involve a noncomputational idea are highly nontrivial. $\endgroup$ – KConrad Jun 17 '20 at 22:55
  • $\begingroup$ @KConrad would you accept "highly nontrivial at the time"? $\endgroup$ – Gerry Myerson Jun 18 '20 at 7:01
  • 1
    $\begingroup$ @Gerry Myerson I think it would be better not to use such a label in the answer. I’d call the work by Archimedes nontrivial (especially considering the nature of his results achieved without a good algebraic notation). Once I looked at the proof of infinitude of the primes in a copy of Euclid and was disappointed: it treats three primes as the “general case”. I understand their lack of good notation made it hard to describe the general case with general notation, but it was still disappointing. $\endgroup$ – KConrad Jun 18 '20 at 7:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.