random networks and prime numbers

Question

I have been studying networks recently and accidentally came up with an heuristic approach towards the distribution of prime numbers. The prime number theorem states that $\pi(n)\sim n/log(n)$ for large $n$, where $\pi(n)$ is the number of prime numbers up to a quantity $n$. Consider a finite set of natural numbers $ S_n={1,2,..,n}$. Partition this set into the set of composite numbers and denote it by $C_n$ and the set of prime numbers $P_n$. Consequently $|P_n|=\pi(n)$ and $|C_n|=n-\pi(n)$, where $|S|$ denotes the cardinality of the set $|S|$. Now randomly pick an element from $C_n$ and also randomly pick an element from $P_n$. We say that this two elements are linked together iff the prime number picked from the set $P_n$ divides the composite number picked from the set $C_n$. Any prime number from the set $P_n$ has an equal probability of being picked and that is $\frac{1}{\pi(n)}$. Without loss of generality assume that $p_i$ is drawn from $P_n$, then we can say that there are $[\frac{n}{p_i}]$ numbers between $1$ and $n$ divisible by $p_i$ where square brackets stand for the greatest integer less than or equal to $\frac{n}{p_i}$. Thus the probability that our randomly composite number chosen from the set $C_n$ is divisible by $p_i$ is $\frac {[\frac {n}{p_i}]-1}{n-\pi(n)}$. Now we can say that the chances that the two elements chosen are linked is probability of prime number $p_i$ being chosen times the probability of our composite number being divisible by it. Denote this event by $L$ for the sake of link then we can state it as: $Pr(L)=\frac{1}{\pi(n)}\cdot\frac {[\frac {n}{p_i}]-1}{n-\pi(n)}$. Set $x(n)=\frac{\pi(n)}{n}$ and noting that $\frac{n}{p_i}=[\frac {n}{p_i}]+\{\frac{n}{p_i}\}$ where $\{\frac{n}{p_i}\}$ is the decimal part of $\frac{n}{p_i}$ then we can rewrite the probability of $L$ as $$ Pr(L)=\frac{1}{x(n)\cdot n}\cdot \frac {\frac{1}{p_i}-\frac{\{\frac{n}{p_i}\}}{n}-\frac{1}{n}}{(1-x(n))}$$ Now we let the size of $S_n$ grow very large and investigate what happens as $n\rightarrow \infty$. Eventually as the size of $S_n$ grows so does the size of $C_n$ and $P_n$. For very large values of $n$ the probability of the event $L$ is roughly $$Pr(L)=\frac{1}{x(n)\cdot n}\cdot\frac{c}{(1-x(n))}$$ where $c=\frac{1}{p_i}$. Given the randomness nature of the problem we can view it as a random graph from the set $C_n$ into the set $P_n$ where probability of an element from the former set being linked to an element from the later set is given by $Pr(L)$. As $n\rightarrow \infty$, $S_n$ becomes the set of all natural numbers, $C_n$ becomes the set of all composite numbers and $P_n$ the set of all prime numbers. Because every natural number is expressed as a product of prime numbers up to a multiplicity then it must be the case that $C_n$ and $P_n$ must be totally connected in other words there is no isolated point in $C_n$ or $P_n$. However in random graph theory there is a result due to Erdos and Renyi which states the threshold probability of a node being connected to other nodes so that the graph is totally connected. Let $p(n)$ denote the probability of a node being connected to other nodes in a network of $n$ nodes and let $n\rightarrow \infty$ then for the network to be totally connected the threshold for $p(n)$ must be $\frac {log(n)}{n}$, i.e. as $n\rightarrow \infty$ then $p(n)\sim\frac{log(n}{n}$. Therefore it is natural to conjecture that $Pr(L)\sim \frac{log(n)}{n}$ which would imply $$\frac{1}{x(n)\cdot n}\cdot\frac{c}{(1-x(n))}\sim \frac{log(n)}{n}$$ Since $x(n)<1$ one could approximate $\frac{1}{(1-x(n))}$ by $1+x(n)$, i.e. $\frac{1}{(1-x(n))}\simeq 1+x(n)$. Therefore we get $$\frac{1}{x(n)\cdot n}\cdot c(1+x(n))\sim \frac{log(n)}{n}$$ or roughly $$ 1+\frac{1}{x(n)}\sim log(n)$$ which is to say $$x(n)\sim \frac{1}{log(n)}$$ Given that $x(n)=\frac{\pi(n)}{n}$ one obtains the result $$\pi(n)\sim\frac{n}{log(n)}$$ which coincides with the one from prime number theorem. I am wondering if this heuristic approach is valid not for the sake of only showing a result that has been proven in many different other ways, but moreover for a new perspective in looking at connectedness between graph theory and number theory. Any suggestions or comments would be highly appreciated.

Answer 1

There is something lacking in this heuristic, even after glossing over the "probabilistic" steps. Since you plan to use the fact that connectivity in a random graph appears above the threshold $\frac{\log n}{n}$, you can conclude that your probabilities will be at least of that order. Then you can conclude that $\pi(n)\leq O\left(\frac{n}{\log n}\right)$. This is an estimate that is much more elementary than the prime number theorem (and which can be explained heuristically with simpler probabilistic estimates). If you want to turn that into an equality $\pi(n)=O\left(\frac{n}{\log n}\right)$, then you would have to explain why the connectivity of your prime-composite graph would have to be a threshold connectivity. I don't see any immediate reasons to expect that to be the case.

Answer 2

The original proof by Chebyshev or Dirichlet wasn't very rigorous either...

---

In my own personal reading, I have been reading about similarities between random integers and random permutations, but it is still quite speculative

• The Poisson-Dirichlet process, and large prime factors of a random number
• The Anatomy of Integers and Permutations

The Granville paper compares two observations and says $N \sim \log x$ where:

• the prime number theorem says $\frac{1}{\log x}$ numbers up to $x$ are prime, where $x \to \infty$.
  $\log x$ is basically the number of digits of $x$.
• $\frac{1}{N}$ permutations of $\{ 1,2,3,\dots, N\}$ is an $N$-cycle.

---

One you partition your graph $\{ 1, 2, \dots, n\} = P_n \cup C_n$, you have defined a bipartite graph.

Can you modify Erdos-Renyi to get bipartite graphs?
For each $p \in P$ we can create an edge $(p,c)$ with probability $\mathbb{P} = \frac{1}{p}$ independently at random.

For an Erdos-Renyi $\mathbb{P} = \frac{\log n}{n}$, I don't know what the threshhold for connectivity is for the graph outlined.

Maybe you can show there are $\log x $ primes in $[x,2x]$ by constructing a graph between $P(x) = \{ primes \} \cap [1, x]$ and $C(x) = [x,2x]$. For large enough $x$ we would like to say that divisibility by these primes are "independent". Then your graph becomes the Erdos-Renyi independent-edges model you are talking about. However the edges connected to each $p \in P(x)$ appear with probability $\frac{1}{p}$.

By unique factorization, every vertex in $C(x)$ is connected to something in $P(x)$. And you can calculate the threshhold probability for such an even to happen in the Erdos-Renyi case.

Then you can ask why the primes hit this thresshold exactly?