0
$\begingroup$

Many conjectures about primes seem to revolve around the idea of "primes are random". So I thought about how this "randomness" may be formally defined, and came up with the following outline:

  1. Describe an algorithm that generates a random sequence "similar" to the primes. A simple example would be Cramer's random model, which selects each integer $n>1$ independently with probability $\frac{1}{\log n}$, but such a sequence may not be "similar" enough to the primes, as it does not accurately describe the distribution of primes mod $n$.

  2. Describe a way to build statements about some sequence $\{a_n\}$ of positive integers. An example may be to build statements using only equality, addition, the universal and existential quantifiers, and taking a term from $\{a_n\}$ (this seems similar to Presburger arithmetic).

  3. Show that, for any statement built from step 2, if it hold with probability $1$ for a random sequence generated from step 1, then it must hold for the sequence of primes. In other words, the statements of step 2 cannot distinguish the primes from a random sequence from step 1. This is similar to the definition of algorithmic randomness.

Clearly step 2 must not allow statements involving divisibility, as then it would be possible to construct the primes. But even if we only use addition, it is still possible to state important conjectures such as the Goldbach conjecture ($\forall n\exists x\exists y(a_x+a_y=n+n)$).

Has such a thing been attempted? Could step 3 even be true for any useful choice of steps 1 and 2?

Improve this question
$\endgroup$
4
  • $\begingroup$ This question is very similar to mathoverflow.net/questions/468260/… $\endgroup$
    – Daniel Weber
    Commented Sep 20 at 11:55
  • $\begingroup$ It's definitely an interesting proposal and I'm sure some people have thought about it. To my knowledge, there is no remotely successful approach of this form, not even conjecturally. $\endgroup$
    – Wojowu
    Commented Sep 20 at 11:55
  • $\begingroup$ @Wojowu I see that proving such a result is probably well beyond current mathematics, so I am more interested in seeing what sort of counterexamples there are that limit the strength of such an approach. $\endgroup$
    – XM73
    Commented Sep 20 at 14:36
  • 1
    $\begingroup$ (1) Maier's theorem is the main example of a "serious" failure of Cramer. But probably it's not possible to express the statement of this theorem in such a limited language. (2) In function fields, we can prove more prime randomness statements, but not up to the level of existence of infinitely many prime tuples, so even a weak version is not provable there. $\endgroup$
    – Will Sawin
    Commented Sep 20 at 18:00

0

Reset to default

You must log in to answer this question.