tag:blogger.com,1999:blog-3722233.post857373476905734669..comments2023-09-30T21:44:03.907-05:00Comments on Computational Complexity: Kolmogorov Complexity and the PrimesLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-3722233.post-71955769206114737002023-05-02T12:57:32.795-05:002023-05-02T12:57:32.795-05:00There are many proofs, but how many of them are es...There are many proofs, but how many of them are essentially the same, or use the same ideas? For example, Keith Conrad argued in his write-up that Furstenberg&#39;s proof is based on the same idea as Euclid&#39;s proof: https://kconrad.math.uconn.edu/blurbs/ugradnumthy/primestopology.pdfZGnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-68730126721636439872017-12-01T02:19:24.670-06:002017-12-01T02:19:24.670-06:00As said, this shows only the inequality for p_i th...As said, this shows only the inequality for p_i that are factors in random numbers. The previous argument shows that this is true for infinitely many i, but to get this for all large i something else is needed (as Alexey Milovanov, if I remember correctly, pointed out) alexander.shenhttps://www.blogger.com/profile/11475502380398851852noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-33232819888427310312017-11-30T09:53:20.153-06:002017-11-30T09:53:20.153-06:00I like the first simpler proof better because Cheb...I like the first simpler proof better because Chebyshev used something almost as simple as the second proof that gets within a constant factor of the right density. The idea is to look at the prime factorization of N=(2n choose n) = (2n)!/(n!)^2. <br /><br />Consider any prime p and the exponent of p in m!. We get [m/p] terms divisible by p and [m/p^2] divisible by p^2, etc so the exponent of p in m! is just<br />[m/p]+[m/p^2]+[m/p^3]+... where [ ] is the floor function and we can go on forever since the terms become 0 eventually.<br /><br />Therefore the exponent of p dividing (2n choose n) is precisely<br />[2n/p]+[2n/p^2}+[2n/[p^3] +...<br />- 2[n/p]-2[n/p^2}- 2[n/p^3] -...<br />= [2n/p]-2[n/p] + [2n/p^2]-2[n/p^2] +...+ [2n/p^k]-2[n/p^k]<br />where k is the largest power of p smaller than 2n.<br />Now for any number m, 2[n/m] &gt; 2(n/m -1) = 2n/m - 2 so <br />[2n/m]-2[n/m] = 1 since it is &lt;= 2n/m - 2[n/m] &lt; 2.<br />Therefore the exponent of p in (2n choose n) is at most k and hence it contributes a factor at most p^k &lt;= 2n to <br />N=(2n choose n).<br /><br />Trivially N=(2n)!/(n!)^2 is at least 2^n. (I want to keep this elementary so I am willing to lose the near factor of 2 in the exponent.) Each prime dividing N must be at most 2n and its contribution to the product N is at most 2n by the above argument. Therefore the # of primes smaller than 2n must be at least log_{2n} N &gt; n/ log_2 (2n) which gives the right asymptotics.Paul Beamehttps://www.cs.washington.edu/people/faculty/beamenoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-65515448382684573032017-11-30T09:48:39.049-06:002017-11-30T09:48:39.049-06:00It should be mentioned that the bound can be impro...It should be mentioned that the bound can be improved by a better encoding, like first writing down the length of C(pi), so we get log i + log m/pi + log log i + 2 log log log i + c, and I think pi&lt;=O(i log i (log log i)^2) follows. Of course this can be further improved.domhttps://www.blogger.com/profile/05790539025733385232noreply@blogger.com