Friedlander-Iwaniec theorem

From Polymath Wiki
Revision as of 10:08, 8 August 2009 by Teorth (talk | contribs) (New page: The '''Friedlander-Iwaniec theorem''' asserts that there are infinitely many primes of the form <math>a^2+b^4</math>. A more quantitative version of this theorem asserts, among other thin...)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

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

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

Heath-Brown later showed a similar result for primes of the form [math]\displaystyle{ a^3+2b^3 }[/math], which leads to an algorithm of runtime [math]\displaystyle{ O( (10^k)^{2/3} ) }[/math]. 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, [www.mpim-bonn.mpg.de/preprints/send?bid=3552 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.

External links