# Sorting of prime gaps

Let $$gig_i$$ be the $$ithi^{th}$$ prime gap $$pi+1−pi.p_{i+1}-p_i.$$

If we re-arrange the sequence $$(gn,i)ni=1 (g_{n,i})_{i=1}^n$$ so that for any finite $$nn$$ the gaps are arranged from smallest to largest we have a new sequence $$(ˆgn,i)ni=1.(\hat{g}_{n,i})_{i=1}^n.$$

For example, for $$n=10,n = 10,$$

$$(g10,i)10i=1=1,2,2,4,2,4,2,4,6,2;(g_{10,i})_{i=1}^{10} = 1, 2, 2, 4, 2, 4, 2, 4, 6, 2;$$
$$(ˆg10,i)10i=1=1,2,2,2,2,2,4,4,4,6.(\hat{g}_{10,i})_{i=1}^{10} = 1, 2, 2, 2, 2, 2, 4, 4, 4, 6.$$

We can ask about the number of elements of the original sequence which are fixed under the sorting operation. For the example above $$gi=ˆgig_i = \hat{g}_i$$ for $$i=1,2,3,5,8.i = 1,2,3,5,8.$$

The number of elements fixed by sorting appears to grow in a familiar way. Letting $$f(n)f(n)$$ be the number fixed for given $$nn$$ :

$$n50050005000050000010000002000000f(n)8261448433907274195141777\begin{array}{c | c | c | c | c | c | c | c | } n & 500 & 5000 & 50000 & 500000 & 1000000 & 2000000 \\ \hline f(n) & 82 & 614 & 4843 & 39072 & 74195 & 141777 \end{array}$$

For comparison, n and $$π(n)\pi(n)$$ (number of primes not exceeding n) are:

$$n50050005000050000010000002000000π(n)9566951334153878498148933\begin{array}{c | c | c | c | c | c | c | c |} n & 500 & 5000 & 50000 & 500000 & 1000000 & 2000000 \\ \hline \pi(n) & 95 & 669 & 5133 & 41538 & 78498 & 148933 \end{array}$$

and the ratio $$f(n)/π(n)f(n)/\pi(n)$$ at least for the numbers above appears to approach 1.

So my question is whether this might be an indirect consequence of the prime number theorem?

Edit:

This process seems to approximate the number of primes on intervals generally. For example, if we sort the prime gaps from $$g120000g_{120000}$$ to $$g127000g_{127000}$$, 556 are fixed. And $$π(127000)−π(120000)=600.\pi(127000)- \pi(120000) = 600.$$ So maybe a better way of putting the question is, why might it be true that

$$f(gm,gm+1,...,gk)≈π(k)−π(m)? f(g_m,g_{m+1},...,g_k) \approx \pi(k) - \pi(m) ?$$

Some things I have looked at. The prime number theorem gives us that $$(gn)(g_n)$$ is not monotone. I don’t have an idea to support the suggestion that $$f(n)/n∼1/logn.f(n)/n \sim 1/\log n.$$ If the probability (loosely speaking) that $$gk=^gkg_k = \hat{g_k}$$ is $$1/logn1/\log n$$ then maybe this can be explained in terms of the multiplicity, in some average sense, of $$gkg_k$$ in a particular finite sequence of gaps.

It occurs to me that if the number of gaps less than $$nn$$ of size (say) 2 is $$k(n),k(n),$$ it is not possible to understand the probabilities involved without knowing whether $$k(n)k(n)$$ is bounded as $$nn$$ gets large. So maybe the idea can be shown to be incorrect but showing it to be correct might require answering the threshold question about gaps.

Taking the suggestion above as true, assuming infinite gaps of all lengths (a conjecture of Polignac) and letting $$ck(n)c_k(n)$$ be the number of prime gaps of length $$kk$$ for given $$n,n,$$ if we assume also something akin to a well-distributed property in the distribution of gaps of length $$kk$$ (which follows in a qualified way from a conjecture of Hardy-Littlewood$$1^1$$) we have a simplification of notation based on geometry:

$$f(n)≈S=1nn∑k=1ck(n)2≈nlogn. f(n) \approx S = \frac{1}{n}\sum_{k = 1}^{n} c_k(n)^2\approx \frac{n}{\log n}.$$

If nothing else the expression conveys the idea of an average. While it doesn’t seem fortuitous I cannot justify it.

Some numbers:

$$nSπ(n)S/π(n)10021.01250.84041000145.131680.8638100001071.4512290.87181000008562.1795920.8926\begin{array}{c | c | c |c | } n & S & \pi(n) & S/ \pi(n) \\ \hline 100 & 21.01 & 25 &0.8404 \\ \hline 1000 & 145.13 & 168 &0.8638\\ \hline 10000 & 1071.45 & 1229 &0.8718\\ \hline 100000 &8562.17& 9592& 0.8926 \\ \hline \end{array}$$

Edit: Some palaver replaced by an image that shows the distribution of the first million prime gaps in terms of deviation from PNT. The peak is at 0 (the graph is shifted by about 70). The spacing of indices of the 74195 fixed gaps (deviation = 0) is quite prime-like.

$$1^1$$ See Conjectures 3.2, 3.4 of this very readable note by Chris Caldwell.