Loading ...
Sorry, an error occurred while loading the content.

Better Euclid proofs for infinite # primes?

Expand Messages
  • WarrenS
    Ron Maimon asks an interesting question here http://mathoverflow.net/questions/72451/how-many-primes-does-euclids-prime-generating-algorithm-really-produce His
    Message 1 of 1 , Jan 17, 2013
    • 0 Attachment
      Ron Maimon asks an interesting question here

      http://mathoverflow.net/questions/72451/how-many-primes-does-euclids-prime-generating-algorithm-really-produce

      His simplest version:
      If you have a set of k primes p1,p2,...,pk, then you can partition them into
      2 disjoint nonempty subsets, compute the products of each subset, and
      then add or subtract the two results. That yields 2^k-2 numbers,
      each of which is coprime to all of your k primes so far.

      Maimon's point is, this seems to generate a heck of a lot more primes than Euclid's original proof. Does it generate enough to see that the prime number theorem is true (or true up to a multiplicative constant)?

      I suspect the answer is "yes."
      Here is a crude argument for this one version of Maimon-Euclid:
      you find all 2^k-2 numbers, factor them all, and find the least prime that you get in this way. Then you adjoin it to your set of k primes (now k+1) and continue on.

      The point is that with 2^k-2 "fairly random" numbers, it seems highly likely that
      at least one of them is going to be divisible by the (k+1)th prime.
      Exceptions to this ought to be extremely rare, in fact so rare that the total
      expected number of exceptions summed over every k=1,2,3,... seems likely to
      be finite. (You can easily prove this in usual bogus statistical models.)

      So therefore, I suspect that the Maimon-Euclid algorithm, starting from some suitable small set of primes, will generate every prime except for a finite set of exceptions.
      Indeed, if you can keep going for a longish time with none missed, then it will get probable that there are no exceptions.

      If I start with {2,3} and work manually, I find:
      2, 3, 5=2+3, 7=2*5-3, 11=3*7-2*5, 13=5*11-2*3*7, etc.
      (not even any factoring required, so far).
    Your message has been successfully submitted and would be delivered to recipients shortly.