Random pseudoprimes vs. primes

Question

(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:

• Are there almost surely an infinite number of twin pseudoprimes in any pseuodprime set $S$? (See the graph below for the cumulative distribution.)

• Are there almost surely an infinite number of Sophie Germain pseudoprimes?

• Can you walk to infinity via a pseudoprime Ulam-spiral? (This was my original motivation.)

• Do the Hardy–Littlewood conjectures hold for pseudoprimes?

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!

          

Answer 1

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.

Answer 2

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