# Random pseudoprimes vs. primes

(Edit. What I called "pseudoprimes" are known as "Cramér random primes" in the literature, of which I was unaware.)

Say that a set $S$ of natural numbers is a set of pseudoprimes if they are (a) random in a sense made explicit below, and (b) the number in $S$ less than $n$ grows as $n / \log_e n$. They are, in a sense, random numbers distributed like the primes. To be more specific, $S$ is created by generating random numbers $u_2, u_3, u_4, \ldots$, uniformly distributed in $[0,1]$, and including $n$ in $S$ iff $u_n < 1 / \log_e n$. (This method was suggested by two MSE users in response to an MSE question on prime-like distributions.) Here are the first twenty numbers in various pseudoprime sets generated by this process: $$3, 8, 10, 11, 12, 13, 15, 28, 35, 39, 44, 50, 53, 65, 66, 67, 68, 70, 78, 86$$ $$8, 27, 29, 31, 32, 33, 41, 50, 52, 55, 57, 62, 63, 71, 72, 74, 78, 82, 83, 92$$ $$5, 28, 31, 34, 44, 45, 46, 48, 50, 53, 59, 64, 68, 69, 70, 72, 76, 78, 85, 95$$ One can imagine other ways of defining pseudoprimes, but let me stick to this simple defintion. Here is their cumulative distribution up to $n=10^6$:

My question is:

Which of the many unsolved problems concerning primes could be proved for pseudoprimes?

For example:

One can extend this list indefinitely. I am seeking to understand to what extent the $1/\log n$ distribution determines the properties of the primes. Thanks for insights!

-
This seems to be (or at least it is close to) the Cramér random model of primes. Roughly speaking and oversimplifying a bit, most widely known conjectures on the distribution of primes and existence of primes with certain properties, will hold. If they would not, they'd been discarded as implausible. (Sorry I am short on time; I might say something more detailed later.) – quid Jul 26 '12 at 13:08
@quid: Thanks for the tip; I had not heard of Cramér's model. Here is one (short) explanation: michaelnielsen.org/polymath1/… – Joseph O'Rourke Jul 26 '12 at 13:12
I'd recommend calling these numbers something other than "pseudoprimes", since that already means something (namely, numbers that pass certain necessary but not sufficient tests for primality). – Henry Cohn Jul 26 '12 at 13:55
@Henry Cohn: Very much agree. I think "(Cramér) random primes" is common. – Charles Jul 26 '12 at 20:16

## 2 Answers

The first Hardy-Littlewood conjecture holds, with a different constant term. The reason is because the constant term is determined by the many congruence conditions on primes - e.g., the fact that all primes are odd increases the expected number of twin primes, because the "probability" that any given odd number is prime is $2/\log n$, so if $p$ is an odd prime than the probability that $p+2$ is prime is higher than what you would expect.

In fact, the constant term is $1$. This is because the expected value is

$E(\pi_{m_1,m_2,\dots,m_k}(x))=\sum_{p=2}^{x-m_k} \frac{1}{(\ln p) (\ln p+2m_1) \dots (\ln p+2m_k)} \sim \int_2^x \frac{dt}{\ln^{k+1} t}$

By the law of large numbers, the actual value is almost surely $1+o(1)$ times the actual value, since the events "$x$ is the first number of a $k$-tuple of pseudoprimes" and "$y$ is the first number of a $k$-tuple of pseudoprimes" are independent as long as $|x-y|>2m_k$.

Thus, the twin primes conjecture is true and the second Hardy-Littlewood conjecture is false.

The Sophie-Germain conjecture is true by an identical argument.

I don't know about the infinite walk.

-

This is a bit of a meta-answer; regarding actual facts regarding the specific questions I do not have anything to add to the existing answer; still this or that might be of interest.

As commented the way of studying problems on primes via considering them as random sets with a certain (changing) density is a common tool known as Cramér's model. And, there is also a refinement where one takes 'local' obstructions, that is congruence conditions such as 'almost all primes are odd' into account.

To test a conjecture on the distributions of prime numbers against this 'random model' is quite standard. And, indeeed, if something would not hold for this random model of the primes it typically would be discarded as a plausible conjecture. In some sense this is an oversimplification, since the model in the question is not that precise (not including local obstructions/congruence conditions) and one could imagine (though I do not have a concrete example handy) a conjecture on the primes that would hold in a more refined model but not in the state one; the issue being that with the model in the question one has a density of $1/ \log n$ whereas with more refined models (and for the primes using the so-called W-trick, ie, sieving for small primes) one can push-up the primes to be a subset of about relative density $\log\log n / \log n$ in certain arithmetic progressions. Yet, essentially all the predictions/conjectures on the numer of twin-primes, primes tuples and related things indeed all stem (explicitly or implicitly) from such a refined random model.

Conversely, results on such questions are even (in particular recently) 'almost exactly' proved along these lines. One establishes that the primes are 'sufficiently (pseudo)random' for heuristics based on random models to apply, or one can argue differently. (Needless to say this is infinitely simpler said like this than actually done.)

Two text I can recommend related to this are the following blog post by Tao and, in particular the introduction to, 'Linear equations in primes' by Green and Tao

-
@quid: Thanks for this lucid and informative account! And thanks for the two useful links. – Joseph O'Rourke Jul 27 '12 at 0:30
An interesting thing would be to study whether the multiplicative monoid generated by such a set S contains almost surely "gaps", i.e whether some positive integers, like genuine prime numbers, can't be reached by multiplying elements of S. This might explain the different behaviors you observe considering the plots. In some sense, through fundamental theorem of arithmetics, one can say that the set of prime numbers is some kind of an "optimal" set of (Cramer) random primes. – Sylvain JULIEN Jul 28 '12 at 16:56
@Sylvain Julien: not sure what you mean by gaps, but there should be definitely some missing elements: any prime that is not a pseudo prime and 'surely' one won't hit each and every prime when choosing randomly. I do not think the large discrepancy for twin primes is due to this though. This is mainly a parity issue. Among odd numbers primes are twice as dense then among all numbers; or for the pseudopromes there are also the 'twins' at distance one. – quid Jul 30 '12 at 8:59
A new insight came to my mind: consider some kind of a Shannon-like entropy to determine whether or not prime are randomly distributed. Let A be the set consisting of the first 8 primes and B be the set {3,8,10,11,12,13,15,28} you gave first. As the 8th prime number is roughly n.log n, one can expect the 8th prime number to be 17 (since 8log 8=16.63...). The most "regular" increasing sequence of 8 integers the last term of which is 17 would be an arithmetic sequence, such as 3,5,7,9,11,13,15,17. One can define the "prime entropy" of a sequence of 8 integers as -$\sum_{i=1}^{8}p_i\log(p_i)$... – Sylvain JULIEN Nov 11 '12 at 2:09
...where $p_i$ is $(u_(i+1)-u_i)/(u_8-u_1)$, $(u_n)$ being the sequence we're interested in. Therefore the prime entropy of A is 1.85..., the prime entropy of B is 1,45...and the prime entropy of the arithmetic sequence is the maximal one (all $p_i$ are equal), 1.94...So that in some sense "genuine" primes seem to be be more "regularly" distributed than Cramer random primes. P.S: please replace "8" in the sum by "7" in my previous comment. – Sylvain JULIEN Nov 11 '12 at 2:25