Prime gap: Difference between revisions

Revision as of 00:59, 9 February 2010

Definition

The prime gap between a prime $p$ and its successor prime $q$ is the difference $q - p$ . In other words, a prime gap is a gap between two successive primes.

Facts

Basic facts

A prime gap of $1$ occurs between $2$ and $3$ , and never again. All other prime gaps are even, and at least $2$ .
There exist arbitrarily large prime gaps: This is because there exist arbitrarily large sequences of consecutive composite integer. For instance, for any $n > 1$ , the sequence $n! + 2, n! + 3, \dots, n! + n$ is a sequence of composite integers.

Conjectures and advanced facts on minimum prime gaps

Name of conjecture/fact	Statement	Status
twin primes conjecture	there exist arbitrarily large pairs of twin primes -- successive primes with a gap of two.	open

Conjectures and advanced facts on maximum prime gaps

Name of conjecture/fact	Statement	Function (big-O)	Status
Cramér's prime gap conjecture	For any prime $p$ , the prime gap between $p$ and the next prime is at most $c (\log p)^{2}$ , $c$ fixed	$O ((\log p)^{2})$	open
Prime-between-squares conjecture	There exists a prime between any two successive squares. Puts upper bound of $1 + 2 \sqrt{p}$ on prime gap	$O (\sqrt{p})$	open
(corollary of) Generalized Riemann hypothesis	The prime gap between a prime $p$ and the next prime is $O (\sqrt{p} (\log p))$	$O (\sqrt{p} \log p)$	open
exponent bound for prime gap of 0.535	The prime gap between $p$ and the next prime is $O (p^{0.535})$	$O (p^{0.535})$	proved
(corollary of) prime number theorem	there exists a prime between $n$ and $α n$ for any $α > 1$ , for $n$ large enough (dependent on $α$ )	$O (n)$	proved
Bertrand's postulate	there exists a prime between $n$ and $2 n$	$O (n)$	proved

@@ Line 23: / Line 23: @@
 ! Name of conjecture/fact !! Statement !! Function (big-O) !! Status
 |-
-| [[Cramér's prime gap conjecture]] || For any prime <math>p</math>, the prime gap between <math>p</math> and the next prime is at most <math>c(\log p)^2</math>, <math>c</math> fixed || <math>O((\log p)^2)</math> open
+| [[Cramér's prime gap conjecture]] || For any prime <math>p</math>, the prime gap between <math>p</math> and the next prime is at most <math>c(\log p)^2</math>, <math>c</math> fixed || <math>O((\log p)^2)</math> || open
 |-
 | [[Prime-between-squares conjecture]] || There exists a prime between any two successive squares. Puts upper bound of <math>1 + 2\sqrt{p}</math> on prime gap || <math>O(\sqrt{p})</math> ||open
@@ Line 33: / Line 33: @@
 | (corollary of) [[prime number theorem]] || there exists a prime between <math>n</math> and <math>\alpha n</math> for any <math>\alpha > 1</math>, for <math>n</math> large enough (dependent on <math>\alpha</math>) || <math>O(n)</math> || proved
 |-
-| [[Bertrand's postulate]] || there exists a prime between <math>n</math> and <math>2n</math> ||<math>O(n)</math> proved
+| [[Bertrand's postulate]] || there exists a prime between <math>n</math> and <math>2n</math> ||<math>O(n)</math> || proved
 |}