Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
Why would one want to use LLL here? –  Did Jul 3 '13 at 19:08
    
I put a "comment" after the answer by nullUser calling attention to this question. –  Will Jagy Jul 3 '13 at 19:15
    
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. –  Will Jagy Jul 3 '13 at 19:18
1  
@Did The beauty and richness of the proof of this theorem with the LLL would not be a sufficient reason? –  Elias Jul 3 '13 at 19:27
2  
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. –  DonAntonio Jul 3 '13 at 19:53
show 2 more comments

2 Answers 2

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.

share|improve this answer
add comment

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.

share|improve this answer
    
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. –  Elias Jul 3 '13 at 19:31
2  
The infinitude of primes is an existence statement - it states that, given any finite set of primes, there exists another prime. –  Thomas Andrews Jul 3 '13 at 19:33
    
@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$. –  Thomas Andrews Jul 3 '13 at 19:36
    
@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. –  Elias Jul 3 '13 at 19:42
    
@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. –  al-Hwarizmi Jul 3 '13 at 19:46
show 3 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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