# A combinatorial approach to the prime number theorem

## Introduction:

An interesting thought experiment recently occurred to me. Let’s suppose we are sentient mathematicians from another galaxy *Messier 83* that just recently learned about the existence of prime numbers via a well-funded Search for Extraterrestrial Intelligence programme. If we did not know that the number of primes less than \(N\) was given by:

\begin{equation} \pi(N) \sim \frac{N}{\ln(N)} \end{equation}

we could define the expected value:

\begin{equation} \pi(N) \approx p_N \cdot N \end{equation}

where \(p_N\) is the probability that a randomly chosen integer \(k\) is prime given that \(k \in [1,N]\).

If we received data in the form of the sequence \(\{u_k\}_{k=1}^n\) and know nothing about the arrangement of prime numbers in \(u\) except that \(\pi(n) \geq 1\), how could we best represent the current state of our knowledge of \(p_n\)?

## The investigation begins:

Given our ignorance, there are two extreme propositions which might both be true. The first proposition is that all elements of \(u\) are prime. The second proposition is that at least one element in \(u\) is prime.

If we are to consider the invariants of each proposition, it is sufficient to consider their symmetries with respect to different permutation groups. For such a combinatorial analysis, we may label the elements of \(u\) as follows:

\begin{equation} u_k := k \end{equation}

without loss of generality.

### Counting the symmetries of quantified propositions:

Now, let’s consider the number of symmetries of the first proposition. If each \(k\) is prime the number of permutations \(u' = \sigma \circ u\) where \(u'_k\) is prime for all \(k\) is given by the cardinality of the Symmetric Group:

\begin{equation} \lvert S_n \rvert = n! \end{equation}

On the other hand, if all we know is that \(u_k\) is prime the number of permutations \(u'= \sigma \circ u\), such that \(u'_k\) is certainly prime is given by sub-groups of \(S_n\) with exactly one fixed point:

\begin{equation} \lvert \{ \sigma \in S_n:u’= \sigma \circ u, u’_k = u_k \} \rvert = \frac{n!}{k} \end{equation}

By counting these symmetries we find that for large \(n\):

\begin{equation} \sum_{k=1}^n \frac{n!}{k} = n! \sum_{k=1}^n \frac{1}{k} \sim n! \cdot \ln(n) \end{equation}

### A reasonable estimate of \(p_n\):

So we may quantify the probability that any particular \(u_k\) is prime as follows:

\begin{equation} p_n = \frac{\lvert S_n \rvert}{\sum_{k=1}^n \lvert \{ \sigma \in S_n:u’= \sigma \circ u, u’_k = u_k \} \rvert} \sim \frac{1}{\ln(n)} \end{equation}

If we introduce this approximation into (2), we find:

\begin{equation} \pi(N) \approx p_N \cdot N \sim \frac{N}{\ln(N)} \end{equation}

so the prime number theorem says that, on average, \(\pi(N)\) maximises the number of possible arrangements of the prime numbers in any compact interval \([1,N] \subset \mathbb{N}\).

Meanwhile, after verifying the correctness of this conjecture, a statistical physicist from *Messier 83* might announce that these arrangements are maximally symmetric. Without a contradiction in terms, the same physicist might say that they satisfy the principle of maximum entropy.

## Discussion:

It is fascinating to consider the possibility that mathematicians from a distant civilisation which just recently learned about the existence of prime numbers may know just as much about their distribution as a civilisation which has studied the distribution of prime numbers for more than two thousand years. If this sounds unreasonable, it is worth noting that each step in this thought experiment was both reasonable and elementary. Given what we know about maximum entropy distributions, perhaps this potential discrepancy should be carefully studied by statistical physicists.

On another note, some readers might argue that this scenario is highly implausible as such a civilisation would not have any encrypted communications. On this point, I will make two remarks. First, many important mathematicians and physicists have made important contributions to science without having a professional interest in number theory. Henri Poincaré, Alan Turing, Claude Shannon, Von Neumann, Albert Einstein, Erwin Schrödinger, and Richard Feynman among others. Second, it is possible to imagine civilisations without encrypted communications.

Such civilisations will either have high levels of trust among their members or they have developed intelligent strategies for building diplomatic relations that don’t depend upon keeping secrets.