Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

(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.)

share|cite|improve this question
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… . Gerhard "Ask Me About Symbolic Relationships" Paseman, 2011.09.18 – Gerhard Paseman Sep 18 '11 at 23:29

1 Answer 1

up vote 11 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.