Complex architecture of primes and natural numbers

Natural numbers can be divided in two nonoverlapping infinite sets, primes and composites, with composites factorizing into primes. Despite their apparent simplicity, the elucidation of the architecture of natural numbers with primes as building blocks remains elusive. Here, we propose a new approach to decoding the architecture of natural numbers based on complex networks and stochastic processes theory. We introduce a parameter-free non-Markovian dynamical model that naturally generates random primes and their relation with composite numbers with remarkable accuracy. Our model satisfies the prime number theorem as an emerging property and a refined version of Cramér's conjecture about the statistics of gaps between consecutive primes that seems closer to reality than the original Cramér's version. Regarding composites, the model helps us to derive the prime factors counting function, giving the probability of distinct prime factors for any integer. Probabilistic models like ours can help to get deeper insights about primes and the complex architecture of natural numbers.

Figure 1

Example of the bipartite network of natural numbers grown up to size 20. Orange circles represent composite numbers and green squares prime numbers. The degree of a prime, $k_p$, is the number of distinct composites to which it is connected, whereas its strength, $s_p$, is the sum of its weighted connections. Similarly, the degree of a composite, $k_c$, is its number of distinct prime factors and its strength, $s_c$, the total number of prime factors.

Figure 2

Comparison of the prime counting function $\pi \left(N\right)$, the prime number theorem Eq. (2), and the prime counting function of our random model $\Pi \left(N\right)$, averaged over 1000 realizations. The inset shows the corresponding relative errors. The relative error of the random model is one order of magnitude smaller than the one of Eq. (2).

Figure 3

Average relative error $\epsilon \left(N\right)=1-\langle x\rangle$ between a composite number and its factorization in the network as a function of the system size $N$ and the standard deviation of the ratio $x$, ${\sigma }_x\left(N\right)$.

Figure 4

Comparison between the complementary cumulative distribution functions of the real bipartite network of natural numbers of size $N={10}^6$ and the network generated by our model averaged over 1000 realizations. The left column shows the unweighted properties and the right column the weighted ones. The legend explaining line types applies to the four plots.

Figure 5

Gaps between primes. Top. Series of largest gaps between real primes in intervals between perfect squares. Top inset: The same series normalized by using Eq. (12). In both plots, primes are considered up to ${10}^{11}$. Bottom: Complementary cumulative distribution function of the normalized largest gaps for real primes and the model in the range $[9\times {10}^{10},{10}^{11}]$. To make evident the slow convergence of the distribution, we also show extrapolations from Eq. (13) for $N={10}^{15}$ and $N={10}^{25}$.

Figure 6

Number of gaps with ${\overline{G}}_m>\alpha$ for different values of $\alpha$ as a function of $N$ rescaled by the factor ${ln}^{\alpha -1}N$. According our estimates, this should behave as a power law of the form $N^{1-\alpha /2}$. Dashed lines are power law fits, which exponents are shown in the inset plot and compared to the theoretical prediction $1-\alpha /2$.

Figure 7

One-mode projection for $N=289$. Primes greater than $N/2$ do not appear in the picture since they are all unconnected. Self-loops are not depicted either. Primes $\{2,3,5,7,11,13,17\}$ form a clique, and there are no links between nodes not belonging to it.

Figure 8

Complementary cumulative degree distribution $P_c\left(k\right)$ of the one-mode projection graph for both the real and the stochastic model networks.

Figure 9

Clustering coefficient as a function of the degree $C\left(k\right)$.