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

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.

1. Is there a connection between prefix free codes and multiplicative number Theory? Both try to characterize unique representation in some manner.
• This argument can also give a bound of $i(\log i)(\log \log i)^2$, if you bound $\log m$ using the second equation from p 3 instead of the first. Aug 8, 2019 at 2:26
• By the way, the Prime Number Theorem is equivalent to an asymptotic formula $p_i \sim i \log i$. This is much stronger than just saying $p_i = O(i \log i)$. Aug 8, 2019 at 8:59
• $\sim$ means the proportionality constant is 1, so $f(x)\sim g(x)$ if $\lim_{x\infty} f(x)/g(x)=1.$ Aug 8, 2019 at 10:59
• I have rolled back an edit from the user who seems determined to enforce their standards and customs for punctuation of headings, to very very very little benefit Aug 8, 2019 at 14:53
• Btw the $O(i\log i)$ upper bound is due to Chebyshev around 1850 much before PNT was proved in its usual form.
– YCor
Aug 8, 2019 at 15:57

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!

• 'at least not without further effort' indicates $p_n=O(n(\log n)^2)$ possible to state in complexity language? Aug 8, 2019 at 17:37
• This proof of $\sum 1/p=\infty$ resembles Erdős's proof of this fact (cf. proof of Theorem 19 in Hardy-Wright). Aug 9, 2019 at 10:15
• @GHfromMO: Well spotted! Aug 9, 2019 at 13:55
• Concerning the last observation in the answer, I believe this is due to the fact that the concatenation schemes work by encoding $\langle a,b\rangle$ as $a^*b$ where $a^*$ is a prefix-free encoding of $a$. Now, prefix-free codes have to obey Kraft’s inequality, and conversely, given a sequence of numbers that obeys Kraft’s inequality, one can construct a corresponding prefix-free code. (I’m not sure how to make the argument for general concatenation schemes that do not have to have this form.) Aug 27, 2019 at 10:14
• That is, to be more precise: (1) $C(\langle x,y\rangle)\le K(x)+C(y)+O(1)$, and (2) if $f\colon\mathbb N\to\mathbb N$ is a nondecreasing computable function, then $K(x)\le f(C(x))+O(1)$ for all $x$ if and only if $\sum_n2^{n-f(n)}<+\infty$. Aug 27, 2019 at 16:04

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.

• I was just interested in whether such wood pushing arguments get to PNT. Perhaps I will add a note. Aug 10, 2019 at 0:39
• This paper says it uses information theory to rigorously show (*). "Some information-theoretic computations related to the distribution of prime numbers", Ioannis Kontoyiannis, 2007. arxiv.org/abs/0710.4076
– usul
Feb 17, 2021 at 5:34