Bertrand's postulate
From Polymath Wiki
Bertrand's postulate asserts that for every positive integer N, there is a prime between N and 2N. Despite its name, it is actually a theorem rather than a postulate.
For large N, the claim is a consequence of the prime number theorem, although more elementary proofs are available.
The relevance of the postulate for the finding primes problem is that it guarantees the existence of a k-digit prime for any k. Brute force search thus yields a k-digit prime after about [math]\displaystyle{ O(10^k) }[/math] steps; this can be considered the "trivial bound" for the problem.
