Difference between revisions of "Friedlander-Iwaniec theorem"

From Polymath1Wiki
Jump to: navigation, search
(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...)
 
 
Line 7: Line 7:
 
# J. Friedlander, H. Iwaniec, [http://www.pnas.org/content/94/4/1054.abstract Using a parity-sensitive sieve to count prime values of a polynomial], PNAS 1997 94:1054-1058
 
# J. Friedlander, H. Iwaniec, [http://www.pnas.org/content/94/4/1054.abstract Using a parity-sensitive sieve to count prime values of a polynomial], PNAS 1997 94:1054-1058
 
# D.R. Heath-Brown, Primes represented by x3 +2y3; Acta Mathematica, 186 (2001), 1-84.
 
# D.R. Heath-Brown, Primes represented by x3 +2y3; Acta Mathematica, 186 (2001), 1-84.
# 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.
+
# B. Z. Moroz, [http://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 ==
 
== External links ==
  
 
* [http://en.wikipedia.org/wiki/Friedlander%E2%80%93Iwaniec_theorem The Wikipedia page for this theorem]
 
* [http://en.wikipedia.org/wiki/Friedlander%E2%80%93Iwaniec_theorem The Wikipedia page for this theorem]

Latest revision as of 09:08, 8 August 2009

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 things, that there exists a k-digit prime of the form [math]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]a^2+b^4[/math] is relatively sparse, having cardinality [math]O( (10^k)^{3/4} )[/math], and is easy to enumerate. This allows for a deterministic prime-searching algorithm with runtime [math]O( (10^k)^{3/4} )[/math].

Heath-Brown later showed a similar result for primes of the form [math]a^3+2b^3[/math], which leads to an algorithm of runtime [math]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, 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