# Prime number density vs. connectedness threshold: coincidence?

(1) $\pi(n)$, the number of primes at most $n$, is asymptotic to $n / \ln n$.

(2) In the Erdős-Rényi random graph model, $p = \ln n / n$ is a sharp threshold for the connectedness of the graph $G(n,p)$ on $n$ vertices with edge-probability $p$.

Is there any connection between these two, or is the ratio $n / \ln n$ natural enough to arise in several unrelated circumstances by happenstance?

(I ask as neither an expert in random graphs nor in number theory.)

-
It'd pretty natural, I have no reason to expect a connection. –  Charles Sep 18 '11 at 22:31
@Charles: I thought perhaps that was a pun :-). You are likely correct, but it would be more interesting if there were a connection. However, desiring will not make it so. –  Joseph O'Rourke Sep 18 '11 at 23:21
I imagine the relationship is much like the one offered in this answer mathoverflow.net/questions/53122/mathematical-urban-legends/… . Gerhard "Ask Me About Symbolic Relationships" Paseman, 2011.09.18 –  Gerhard Paseman Sep 18 '11 at 23:29

## 1 Answer

I'd lean towards "coincidence", for a number of reasons:

1. $\pi(n)$ is a cardinality, whereas $p$ is a density; one is comparing apples and oranges. The density of the primes is $1/\log n$, which is quite different from $\log n/n$. (It is true that the average number of divisors $\tau(n)$ of a natural number $n$ is $\log n$, which at first glance seems to match the average degree of a Erdos-Renyi graph of density $\log n/n$, but $\tau(n)$ is very irregularly distributed (its variance is comparable to $\log^3 n$, for instance), in contrast to the Erdos-Renyi degree which obeys a central limit theorem, so this does not seem to be a good match.)
2. For Erdos-Renyi graphs there is a second threshold at 1/n, which is where the giant component begins to emerge. There doesn't seem to be anything analogous for primes.
3. In an Erdos-Renyi graph, n is fixed, and all vertices are given equal weight. For the primes, it is much more natural to work on all the natural numbers at once, and give each natural number n a different weight ($1/n^s$ being a particularly good choice). This pulls the numerology of the two settings even further apart.

Note that there certainly are useful probabilistic models of the primes, such as the Cramer model. However, there appears to be little relation between the Cramer model and the Erdos-Renyi model, other than that they are both random models with a density parameter that involves a logarithm in either the numerator or denominator.

-