tag:blogger.com,1999:blog-3722233.post5839218915469004731..comments2023-12-02T04:32:02.323-06:00Comments on Computational Complexity: The Prime Number TheoremLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-3722233.post-24909305870296705632009-05-24T13:09:03.917-05:002009-05-24T13:09:03.917-05:00I believe that Bertrand used it as an unproven ass...I believe that Bertrand used it as an unproven assumption in some work and that is why it is called postulate.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-54367023952017315122009-05-15T11:47:00.000-05:002009-05-15T11:47:00.000-05:00Some information about the history of Bertrand'...Some information about the history of Bertrand's Postulate is given in the following excerpt from "Proofs from THE BOOK", Chapter 2.<br /><br />"A famous bound states that "the gap to the next prime cannot be larger than the number we start our search at." This is known as Bertrand's postulate, since it was conjectured and verified empirically for n < 3 000 000 by Joseph Bertrand. It was first proved for all n by Pafnuty Chebyshev in 1850. A much simpler proof was given by the Indian genius Ramanujan. Our Book Proof is by Paul Erdos: it is taken from Erdos' first published paper, which appeared in 1932, when Erdos was 19."NickHhttps://www.blogger.com/profile/02726467473642434859noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-10814779676556606512009-05-14T15:21:00.000-05:002009-05-14T15:21:00.000-05:00YES, correct that I am
incorrect about
``really sa...YES, correct that I am<br />incorrect about<br />``really said n/ln(n)''<br />Have edited the post to indicate this.bil gasarchnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-7696612815667041612009-05-14T12:49:00.000-05:002009-05-14T12:49:00.000-05:00Recall the Prime Number Theorem (PNT). Let &pi...<I>Recall the Prime Number Theorem (PNT). Let &pi(n) be the number of primes that are &le n. As n goes to infinity &pi(n) approaches n/ln(n). Note that we did not say &theta(n/ln(n)) or n/ln(n) + &theta(1). We really said n/ln(n) </I>The error term is vastly larger than &theta(1), so I'm not sure what it means to say it is "really" n/ln(n) rather than n/ln(n) + &theta(1). All the prime number theorem says is that it is (n/ln(n))(1+o(1)). In fact, the error term is on the order of n/ln(n)^2. Replacing n/ln(n) with the integral from 2 to n of dx/log(x) gives a much better approximation (assuming the Riemann hypothesis, it's within n^(1/2+o(1))).<br /><br /><I>Erdos and Selberg found elementary proofs that question the use of the word elementary since they were quite difficult. It is hard to pin down the term elementary</I>No, it's not. In this context, it has nothing whatsoever to do with difficulty. Rather, it means avoiding complex analysis (and other similarly unexpected branches of mathematics).<br /><br /><I>Erdos and Selberg (ind? not ind?- see this paper for the history)</I>The linked paper is a good reference. Note however that nobody has ever claimed Erdos and Selberg did things independently (which is, I assume, what "ind?" refers to). The story is far more complicated than that.<br /><br /><I>Is PNT, not Weak PNT, ever actually needed?</I>Ever needed for what? If you never care about constant factors, then you are unlikely to start caring here. However, if you like Knuth-style asymptotic analysis of algorithms, where you actually care about constants, then occasionally you'll need the prime number theorem.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-22298852093019570462009-05-14T12:45:00.000-05:002009-05-14T12:45:00.000-05:00"Note that we did not say θ(n/ln(n)) or n/ln(n) + ..."Note that we did not say θ(n/ln(n)) or n/ln(n) + θ(1). We really said n/ln(n)"<br /><br />I donot know what you mean<br />by this. A more precise<br />estimation for \pi(n)<br />is \int_2^n dt/ln t,<br />which is <br /> n/ln n + n/(ln n)^2 + ..<br />so the gap between<br />\pi(n) and n/ln n is much larger than a constant.<br />The gap between \pi(n)<br />and \int_2^n dt/ln t<br />was famously conjectured by<br />Riemann to be <br />\sqrt{n+\epsilon}.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-8079161661738415222009-05-14T12:40:00.000-05:002009-05-14T12:40:00.000-05:00I remember reading the following paper couple of y...I remember reading the following paper couple of years back. It has a cute application of PNT.<br /><br />Valerie King, Garry Sagert: A Fully Dynamic Algorithm for Maintaining the Transitive Closure. J. Comput. Syst. Sci. 65(1): 150-167 (2002)<br /><br />On a related note, I recently <A HREF="http://www.cc.gatech.edu/~kintali/papers/legendre.html" REL="nofollow">generalized Erdos's proof</A>. It is an elementary proof and I believe the bounds in my paper can be tightened. But I don't think it will be anywhere near the best known bounds. The purpose of my paper is to test the limits of elementary techniques. By "elementary", I meant "combinatorial".Shiva Kintalihttps://www.blogger.com/profile/07853545928906483737noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-12114214935449861872009-05-14T12:31:00.000-05:002009-05-14T12:31:00.000-05:00P.S. If you don't care about constants, the p...P.S. If you don't care about constants, the proof that EQ has communication complexity O(log n) does not come close to requiring Bertrand's Postulate. The same proof that <br />(2n choose n) is larger than 2^n and all its prime power factors are ≤ 2n is enough. Instead of using primes, use the prime power factors of (2n choose n).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-56292046349992900962009-05-14T12:16:00.000-05:002009-05-14T12:16:00.000-05:00Do we even have an application that uses the rarit...Do we even have an application that uses the rarity of primes? The weak version of the density lower bound given in the Chebyshev argument below (which is the argument you write without the frills) seems to be sufficient in almost all CS applications:<br /><br />Thm: pi(2n) ≥ n/(1+log_2 n).<br /><br />Proof: Calculate largest power of p dividing m! as<br />floor (m/p) + floor(m/p^2) + ...,<br />and from this write the largest power of p dividing (2n choose n) as<br />floor (2n/p) -2 floor(n/p)<br />+ floor (2n/p^2) -2floor(n/p^2)<br />+...,<br /> observe that each term in this sequence is <=1 and that if there are k non-zero terms then p^k < 2n.<br /><br />Finally, use the trivial property that <br />(2n choose n) > 2^n to derive that <br />pi(2n) > log (2^n)/log (2n) since each distinct prime contributes < 2n to (2n choose n).Anonymousnoreply@blogger.com