tag:blogger.com,1999:blog-3722233.post857373476905734669..comments2018-12-10T20:52:53.733-05:00Comments on Computational Complexity: Kolmogorov Complexity and the PrimesLance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-3722233.post-68730126721636439872017-12-01T03:19:24.670-05:002017-12-01T03:19:24.670-05: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-30T10:53:20.153-05:002017-11-30T10:53:20.153-05: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] > 2(n/m -1) = 2n/m - 2 so <br />[2n/m]-2[n/m] = 1 since it is <= 2n/m - 2[n/m] < 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 <= 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 > 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-30T10:48:39.049-05:002017-11-30T10:48:39.049-05: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<=O(i log i (log log i)^2) follows. Of course this can be further improved.domhttps://www.blogger.com/profile/05790539025733385232noreply@blogger.com