What exactly is meant by "constant" when it is said that Legendre's conjecture implies that the upper bound on the prime gap above n could be bounded by the product of a constant and the square root of n? For example, if $2\sqrt n$ were the upper bound for the prime gap above n, would the 2 here be this constant?


You are correct. Often the Landau "Big O" notation is used. So, in some books, you might see it said that the prime gap is $O(\sqrt{n})$ (read as "order of $\sqrt{n}$" or "big oh of $\sqrt{n}$" if the conjecture is true. There are several equivalent definitions of what this means, but the idea is that a function $g(x)$ is said to be $O(f(x))$ if for there is a constant $c>0$ and point $x_0$ such $\vert g(x) \vert \leq cf(x)$ as soon as $x>x_0.$

  • $\begingroup$ Wait, it was Landau who came up with the big O?! How ironic! The very one who described Legendre's conjecture as "unattackable" is responsible for the big O. It is all clear to me now. $\endgroup$ – Jeffrey Young Oct 2 '14 at 6:02
  • 1
    $\begingroup$ Actually, it was probably Paul Bachmann, but it spread through Landau. At any rate, it first started appearing in number theory articles, but then became popular in applied mathematics (for asymptotic analysis) and computer science (for algorithmic complexity). $\endgroup$ – Philip Hoskins Oct 2 '14 at 6:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.