# Friedlander-Iwaniec theorem

Jump to: navigation, search

The Friedlander-Iwaniec theorem asserts that there are infinitely many primes of the form $a^2+b^4$. A more quantitative version of this theorem asserts, among other things, that there exists a k-digit prime of the form $a^2+b^4$ for every k.

The relevance of this result to the finding primes project is that the set of k-digit numbers of the form $a^2+b^4$ is relatively sparse, having cardinality $O( (10^k)^{3/4} )$, and is easy to enumerate. This allows for a deterministic prime-searching algorithm with runtime $O( (10^k)^{3/4} )$.

Heath-Brown later showed a similar result for primes of the form $a^3+2b^3$, which leads to an algorithm of runtime $O( (10^k)^{2/3} )$. Related results for other binary cubic forms exist, see the survey of Moroz; but this is the sparsest set of polynomial forms currently known to capture primes.

1. J. Friedlander, H. Iwaniec, Using a parity-sensitive sieve to count prime values of a polynomial, PNAS 1997 94:1054-1058
2. D.R. Heath-Brown, Primes represented by x3 +2y3; Acta Mathematica, 186 (2001), 1-84.
3. B. Z. Moroz, On the representation of primes by polynomials (a survey of some recent results), Proceedings of the Mathematical Institute of the Belarussian Academy of Sciences, 13 (2005), no. 1, pp. 114-119.