I'm looking if there is proof of the infinitude of prime numbers using probabilistic method. I am motivated by the answer of my question here. The answer is based on a relationship between independence of measurable sets and integers coprime.

More precisely ask the following.

QUESTION: There is a proof of the infinitude of primes using the Lovász Local lemma by any of several different versions of the lemma?

  • 2
    $\begingroup$ Why would one want to use LLL here? $\endgroup$ – Did Jul 3 '13 at 19:08
  • $\begingroup$ I put a "comment" after the answer by nullUser calling attention to this question. $\endgroup$ – Will Jagy Jul 3 '13 at 19:15
  • $\begingroup$ Note that, as you both are anonymous, one good choice would be a chat room for the two of you. That would work pretty well if you are in similar time zones. There are instructions on the longest running chat room about how to enable "ChatJax" in order to use Latex. $\endgroup$ – Will Jagy Jul 3 '13 at 19:18
  • 1
    $\begingroup$ @Did The beauty and richness of the proof of this theorem with the LLL would not be a sufficient reason? $\endgroup$ – MathOverview Jul 3 '13 at 19:27
  • 2
    $\begingroup$ This seems to be the stuff some rather nice, innovative papers are made of: somebody wants to prove something using methods and stuff that bear no straightforward, clear conection to that something...Of course, it could perfectly well be that nobody can (at least so far) see any possible conection between things and nothing happens. $\endgroup$ – DonAntonio Jul 3 '13 at 19:53

I don't know how to do it using your proposed lemmas, but if you would like a probabilistic proof, we can work it out from my previous answer. Again take $P(X=n) = n^{-s}/\zeta(s)$ and $E_k := \{X \text{ is divisible by } k\}$. We already showed for $s>1$ $$ \left(\sum_{n=1}^\infty n^{-s}\right)^{-1}=\frac{1}{\zeta(s)} = P(X=1) = P(\cap_{p} E_p^c) = \prod_p(1-P(E_p)) = \prod_p(1-p^{-s}). $$

Assume for contradiction that there are finitely many primes. Now let $s\to 1^+$. Then we get $$ 0 = \prod_p(1-p^{-1}) $$ which cannot be, as the right side is a finite product of strictly positive terms. Thus it must be that there are infinitely many primes.

  • $\begingroup$ Hi, I was confused about one thing. How do you know $n^{-s}/\zeta(s)$ is a real number in $[0,1]$? Or is it okay to have a complex-valued probability? $\endgroup$ – Francis Begbie Jan 11 '16 at 10:36
  • $\begingroup$ While it is true that $\zeta(s)$ is real for $s \in [0,1)$ (not at $s=1$), this is not necessary information to the proof. We consider only real $s>1$, and take the limit from the right, so as to only use $s>1$ throughout. $\endgroup$ – nullUser Jan 15 '16 at 19:03

If your question is whether there exists yet a proof that applies the Lovász/Erdős Local Lemma to prove the prime infinitude. The answer is, no. The Lemma provides a method that helps on existence proofs and gives not a motivation towards infinitude of primes.

If I misunderstood your question then I would need to know the exact motivation behind your inspiration.

  • $\begingroup$ I believe that the proof would be the type to show that for any natural number $N$ the likelihood of a prime greater than $N$ would be positive. $\endgroup$ – MathOverview Jul 3 '13 at 19:31
  • 2
    $\begingroup$ The infinitude of primes is an existence statement - it states that, given any finite set of primes, there exists another prime. $\endgroup$ – Thomas Andrews Jul 3 '13 at 19:33
  • $\begingroup$ @Elias That kind of argument won't work, because primes aren't random. Either there is a prime or there isn't a prime greater than $n$. Look at the proof to the previous question, and you'll see it defines a very specific random variable $X$. $\endgroup$ – Thomas Andrews Jul 3 '13 at 19:36
  • $\begingroup$ @Thomas Andrew His argument (on my coment) seems to make sense to me. But as the use of LLL is a matter of defining a suitable probability space the question is not refuted. $\endgroup$ – MathOverview Jul 3 '13 at 19:42
  • $\begingroup$ @Thomas Andrews your existence statement can not hold in this case because one can clearly show that given any set of primes gives argument that there exists another prime. So the events in this argumentation are not indpendent. This is in harmony also with the fact that primes are not randomly distributed in white noise scheme. $\endgroup$ – al-Hwarizmi Jul 3 '13 at 19:46

Your Answer

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

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