Is there a Kolmogorov complexity proof of the prime number theorem?

Question

Lance Fortnow uses Kolmorogov complexity to prove an Almost Prime Number Theorem (https://lance.fortnow.com/papers/files/kaikoura.pdf, after theorem $2.1$): the $i$th prime is at most $i(\log i)^2$. This differs from the bound in the Prime Number Theorem only by a factor of $\log i$.

1. Is there a way to sharpen this proof to a bound of $O(i\log i)$, making good use of complexity theory (Matt. F comment gives a smaller $O((\log\log i)^2)$ factor)?

added: If 1. is not possible what additional information do we need to get to the Prime Number Theorem?

The only limitation seems to be the creativity needed in prefix free codes. Perhaps there are asymptotically efficient coding or some other reasoning getting to needed.

2. Is there a connection between prefix free codes and multiplicative number Theory? Both try to characterize unique representation in some manner.

Answer 1

Firstly, the proof given there doesn't really show that $p_n = O(n(\log n)^2)$ (at least not without further effort). Instead what it shows is that there are $n$ for which $p_n = O(n(\log n)^2)$, and with a small effort that this holds for arbitrarily large $n$. As noted in the comments, the argument also gives that there are $n$ with $p_n = O(n (\log n) (\log \log n)^2)$ etc.

In fact, all that is going on in this proof is that the sum of the reciprocals of the primes diverges, which also immediately gives that there must be large $n$ with $p_n \le n (\log n)^2$ etc (else the sum of reciprocals would converge). So let me reformulate this ``new proof" in more usual language: the proof is nice, but there aren't really any new ideas here, only less familiar language (which is interesting and suggestive).

Consider integers $n$ below $x$ (which is large), and sort them according to their largest prime factor $p=P(n)$. If $z$ is any fixed number, then there are at most $(\log x)^z$ numbers below $x$ all of whose prime factors are less than $z$. Therefore $$ x \le (\log x)^z + \sum_{\substack{ n\le x \\ P(n) >z}} 1 \le (\log x)^z + \sum_{p>z } \frac{x}{p}, $$ since there are at most $x/p$ integers below $x$ whose largest prime factor is $p$. This shows that for any fixed $z$ $$ \sum_{p> z} \frac 1p >1, $$ which amounts to the divergence of the sum of reciprocals of primes. This is the content of the proof in the linked notes.

There is one fact that I find intriguing. The complexity argument of how to concatenate ``programs" given there seems to dovetail exactly with how a sequence must grow in order to have a divergent sum (that $1/n(\log n)^2$ converges, $1/(n(\log n)(\log \log n)^2)$ converges, etc) --- curious!

Answer 2

I think it’s not uncommon for arguments in elementary number theory to be “philosophically” information-theoretic in nature. But this is not a very deep fact - at the end of the day it all comes down to the well-known heuristic principle that the events of a “random integer” being divisible by different primes are approximately independent events. It’s making that heuristic notion precise that always requires considerably more subtle arguments involving complex analysis etc, in which information theoretic thinking plays no apparent role. So I‘m reasonably sure the answer to your title question about the prime number theorem is “no”.

Nonetheless, one can do some cute things with this idea. Here is an example I noticed many years ago, related to the standard estimate $$ \textrm{(*)} \qquad \sum_{p \le n} \frac{\log p}{p} = \log(n) + O(1) \qquad (n\to \infty) $$ (summation over primes) — a series that is very much related to the sum of the reciprocals of the primes and to estimates of $p_n$ which you and others were discussing here. I will give (*) the following information-theoretic interpretation (which will give a rigorous proof of a bound in one direction):

Take a random variable $X$ that is chosen uniformly at random from the numbers $1,\ldots,n$. For each prime $p\le n$, let $V_p$ be the $p$-valuation of X (the exponent of $p$ dividing $X$). A key observation is that knowing all the $V_p$’s, one can recover $X$. That means that there is an inequality of Shannon entropies: $$ \log_2(n) = H(X) \le H(\{V_p, p\le n\}) \le \sum_{p\le n} H(V_p), $$ by well-known properties of the entropy function $H(\cdot)$ (subadditivity and monotonicity with respect to the $\sigma$-field, precisely analogous to the properties of Kolmogorov complexity that Fortnow uses in his notes).

Now, what is the entropy $H(V_p)$ of the random variable $V_p$? It’s the expression $$ - \sum_{k\ge 0} \operatorname{Pr}(V_p=k) \log \operatorname{Pr}(V_p=k), $$ which can be bounded from above by the $k=1$ term $$ -\operatorname{Pr}(V_p=1) \log \operatorname{Pr}(V_p=1) = -\left( \frac{1}{n} \lfloor n/p \rfloor \right) \log \left( \frac{1}{n} \lfloor n/p \rfloor \right), $$ plus all the other parts (which I’ll leave as an exercise to show is $O(1)$). And this last quantity is approximately equal to $\frac{\log p}{p}$ as long as $p$ is smaller in order of magnitude than $n$. Thus after some more simple estimates one gets essentially the “$\ge$” side of (*), together with the added insight that the error term in approximations such as (*) says something about the extent to which divisibility properties of a typical number by different primes are correlated with each other.

As I was saying at the beginning, this is kind of interesting at a philosophical level, but I’m not aware that anyone has found a way to make these sorts of arguments precise enough to prove something as strong as the prime number theorem, or indeed anything stronger than the most elementary sorts of estimates that already have very short and direct proofs.