Rosser's Theorem
   HOME

TheInfoList



Click Here for Items Related To - Rosser's Theorem
OR:
Rosser's Theorem on:   [Wikipedia]   [Google]   [Amazon]

In
number theory Number theory is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic functions. Number theorists study prime numbers as well as the properties of mathematical objects constructed from integers (for example ...
, Rosser's theorem states that the nth
prime number A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime ...
is greater than n \log n , where \log is the
natural logarithm The natural logarithm of a number is its logarithm to the base of a logarithm, base of the e (mathematical constant), mathematical constant , which is an Irrational number, irrational and Transcendental number, transcendental number approxima ...
function. It was published by
J. Barkley Rosser John Barkley Rosser Sr. (December 6, 1907 – September 5, 1989) was an American logician, a student of Alonzo Church, and known for his part in the Church–Rosser theorem in lambda calculus. He also developed what is now called the " Rosser ...
in 1939. Its full statement is: Let p_n be the nth
prime number A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime ...
. Then for n\geq 1 :p_n > n \log n. In 1999, Pierre Dusart proved a tighter lower bound:{{cite journal, authorlink=Pierre Dusart, last=Dusart, first=Pierre, title=The kth prime is greater than k(\log k + \log\log k - 1) for k\geq 2, journal=
Mathematics of Computation ''Mathematics of Computation'' is a bimonthly mathematics journal focused on computational mathematics. It was established in 1943 as ''Mathematical Tables and Other Aids to Computation'', obtaining its current name in 1960. Articles older than f ...
, volume=68, issue=225, year=1999, pages=411–415, mr=1620223, doi=10.1090/S0025-5718-99-01037-6, doi-access=free : p_n > n (\log n + \log \log n - 1).


See also

*
Prime number theorem In mathematics, the prime number theorem (PNT) describes the asymptotic analysis, asymptotic distribution of the prime numbers among the positive integers. It formalizes the intuitive idea that primes become less common as they become larger by p ...


References


External links


Rosser's theorem
article on Wolfram Mathworld. Theorems about prime numbers de:John Barkley Rosser#Satz von Rosser