4
$\begingroup$

As most others are, so am I fascinated by primes.

By the theorem of Euclid and the sieve of Eratosthenes the $ k \ge 2$ - th prime is given by:

$$ p_k = \min_{x>1,\gcd(x,p_1 \cdots p_{k-1})=1} x $$

which might be seen as one definition of the $k$-th prime.

Thank God this process is deterministic, so that each time we apply it, with $p_1=2$ we get the same prime numbers.

Suppose now that we add some randomness to this process:

$$y = \min_{x_i > 1, \gcd(n, x_i)=1} (x_1, \ldots, x_k)$$

where we draw each $x_i$ with replacement and independent of each other from $1,\cdots,n$.

I read that the extreme value theory is concerned with $\min, \max$ of iid random variables as $k$ goes to infinity.

Another hint might be the Gumbel distribution which shows values $\zeta(2), \zeta(3)$ in variance and mean where $\zeta$ is the Riemann zeta function.

Yet another hint comes from empirical connection of primes to extreme value theory:

https://arxiv.org/abs/1301.2242

My question is, if one can make this heuristic more precise, if this is not asked too much. (So maybe there is a way to think of a random process where one can apply the extreme value theory? )

Thanks for your help!

Reference:

https://arxiv.org/abs/1301.2242

https://en.wikipedia.org/wiki/Gumbel_distribution

https://stats.stackexchange.com/questions/220/how-is-the-minimum-of-a-set-of-random-variables-distributed

https://en.wikipedia.org/wiki/Extreme_value_theory

Edit:

I did some computations based on the following model:

Given $N$, choose with replacement $y_1,\cdots,y_m$ from the set $\{ x | \gcd(x,N)=1, N \ge x>1\}$ which has $\phi(N)-1$ elements.

The probability that $Y$ is the least prime $p$ not dividing $N$ is:

$$P(Y=p) = \frac{1}{\phi(N)-1}$$

The probability $P(Y_{\min}=y)$ is:

$$P(Y_{\min}=y)=(1-F(y-1))^m - (1-F(y))^m$$

where $$F(y) = \sum_{a \le y} P(Y=a) = \frac{1}{\phi(N)-1} \cdot \chi(N,y)$$

and

$$\chi(N,y) = |\{a | a \le y, a > 1, \gcd(a,N)=1 \}|$$.

Hence the expected value of $Y^{(N,m)}_{\min}$ is given by:

$$E(Y^{(N,m)}_{\min}) = \sum_{k=1,k>1,\gcd(k,N)=1}^N k \cdot P(Y_{\min}=k)$$

For $m \rightarrow \infty$ we "should" have:

$$\lim_{m \rightarrow \infty} E(Y^{(P_k,m)}_{\min})=p_{k+1}$$

where $P_k$ is the $k$-th primorial.

It would be nice, if someone with more experience in probability theory and number theory can have a look at this computation.

I also did some computations with SAGEMATH to this theoretical consideration:

def PK(k):
    return prod(primes(nth_prime(k)))

def FF(N,m,k):
    return 1/(euler_phi(N)-1)*len([ a for a in range(1,k+1) if gcd(a,N)==1 and a > 1])

def EE(N,m):
    EN = euler_phi(N)
    return sum([k*((1-FF(N,m,k-1))**m-(1-FF(N,m,k))**m) for k in range(1,N+1) if gcd(k,N)==1 and k>1])


for n in range(3,6+1):
    print nth_prime(n),EE(PK(n),PK(n)).n()

5 5.00000000000000
7 7.03931627655029
11 11.0222933198474
13 13.0321521439774

Thanks for your help.

$\endgroup$
3
  • 3
    $\begingroup$ I am a bit doubtful about random models for primes, as what makes them deterministic and finally so mysterious is precisely the fundamental theorem of arithmetic. Both the existence and the unicity of the decomposition of any integer as a product of primes are crucial. $\endgroup$ – Sylvain JULIEN Apr 21 '20 at 19:45
  • $\begingroup$ @SylvainJULIEN You are right, but there are random models which are useful in some sense, that they shed some light about natural numbers. $\endgroup$ – user6671 Apr 22 '20 at 6:08
  • $\begingroup$ I couldn't follow so I cannot comment but in case you didn't know there exist the cramér random model +, and $\lim_{m \rightarrow \infty} E(Y^{(P_k,m)}_{\min})=p_{k+1}$ sounds similar to the fact that $\ln(p_n\#)\approx p_n$+ $\endgroup$ – Daniel D. Apr 26 '20 at 17:22
0
$\begingroup$

I don't know nothing about extreme value theory, and I didn't know Gumbel distribution (and to this date my probability isn't good). But I add a reference if you want to study it in your home, since the only thing/bridge that I can glimpse to be potentially useful, in my view, is the reference [1]. This is from my belief by inspection of the definitions of certain probability/statistical distributions. This is the only contribution that I can to do as an attempt to create a connection of prime numbers and extreme value theory.

I hope it can to help you. In other case please feel free (you or a professor) to add a comment with your feedback, that I'm going to delete this answer as soon as possible, many thanks.

References:

[1] Dennis P. Walsh, A curious Way to Test for Primes, Mathematics Magazine, Vol. 80, No. 4 (Oct., 2007), pp. 302-303.

$\endgroup$
4
  • $\begingroup$ One can go through the proof of [1] to create a slightly different primality criterion built on the function $$-\log F(x),$$ where $F(x)$ denotes the cumulative distribution function of the standard Gumbel function. If you try it in your home, you'll need a proof by cases to get the mentioned slightly different primality criterion. $\endgroup$ – user142929 May 6 '20 at 16:14
  • $\begingroup$ thanks for your answer $\endgroup$ – user6671 May 6 '20 at 18:17
  • 1
    $\begingroup$ please do not delete the answer $\endgroup$ – user6671 May 6 '20 at 18:18
  • $\begingroup$ Thanks to you, for your posts @orgesleka . Other formula is $\frac{1}{f(x)}\cdot F(x)$ where $F(x)$ denotes the cumulative distribution function of the standard Gumbel distribution, and $f(x)$ its corresponding density function, but I don''t know if this has a specific meaning in the probability theory. I known the article from JSTOR, I can read online it for free since I have an account (they are very generous). $\endgroup$ – user142929 May 6 '20 at 18:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy