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

p-1 isn't a random integer

Expand Messages
  • Décio Luiz Gazzoni Filho
    For p prime, the integer p-1 is an important quantity in certain analyses (particularly if they involve the group (Z/pZ)*), but as I recall, this integer is
    Message 1 of 3 , Feb 3, 2005
      For p prime, the integer p-1 is an important quantity in certain analyses
      (particularly if they involve the group (Z/pZ)*), but as I recall, this
      integer is usually considered as `a random integer in the vicinity of p' in
      such analyses (except perhaps by considering that it is even).

      However, a neat idea occurred to me: just as the probability that 2 divides
      this integer is skewed in comparison to a random integer (it's 1 in this case
      but 1/2 for a random integer), so is the probability that it is divisible by
      any other prime. Consider for instance the residue class of p mod 3; unless p
      itself is 3, then p == 1 or 2 mod 3, with equal probability for each residue
      class. So p-1 == 0 or 1 mod 3 also with equal probability. Thus, p-1 is
      divisible by 3 with probability 1/2, not 1/3 as expected. Using the same
      argument, p-1 is divisible by a given prime q with probability 1/(q-1), not
      1/q.

      The first implication that occurred to me is that one shouldn't use Mertens'
      theorem in any analyses involving p-1 where p is prime. For instance, I
      computed the probability that primes from 3 to 31337 divide a given integer
      using Mertens' theorem; the result is 0.1085. Using PARI/GP to evaluate the
      product (1 - 1/(p-1)) for primes p from 3 to 31337, I obtained 0.07157. The
      difference is quite real.

      I'll try to work out an estimate, similar to Mertens' theorem, but for the
      product (1 - 1/(p-1)) instead. However, I'm pretty sure David Broadhurst or
      Mike Oakes will beat me to it (:

      I don't know how useful this is (probably not useful at all), but I thought it
      was neat and worth mentioning.

      Also, as I was pondering this, something entirely different (but equally neat)
      occurred to me: by Mertens theorem, the probability that an integer isn't
      divisible by any primes up to x is exp(-gamma)/log x. Now take x = sqrt(n);
      we have that no primes up to sqrt(n) divide a random integer with probability
      exp(-gamma)/log(sqrt(n)) = 2 exp(-gamma)/log n ~ 1.123/log n. On the other
      hand, we have the well-known heuristic using the PNT, which says that a
      random integer in the vicinity of n is prime with probability 1/log n.
      However, we also know that if an integer n isn't divisible by any prime up to
      sqrt(n), then n itself is prime. So, if we're looking for an accurate
      numerical value of the probability that a random integer near n is prime,
      shouldn't we use the heuristic 1.123/log n instead?

      Décio


      [Non-text portions of this message have been removed]
    • mikeoakes2@aol.com
      In a message dated 04/02/2005 01:54:40 GMT Standard Time, decio@decpp.net writes: So, if we re looking for an accurate numerical value of the probability that
      Message 2 of 3 , Feb 4, 2005
        In a message dated 04/02/2005 01:54:40 GMT Standard Time, decio@...
        writes:

        So, if we're looking for an accurate
        numerical value of the probability that a random integer near n is prime,
        shouldn't we use the heuristic 1.123/log n instead?


        No, we shouldn't.

        >by Mertens theorem, the probability that an integer [n] isn't
        >divisible by any primes up to x is exp(-gamma)/log x

        This is true for integers n >> x.
        But fails when x gets as large as sqrt(n).

        -Mike Oakes


        [Non-text portions of this message have been removed]
      • Décio Luiz Gazzoni Filho
        As expected, my idea proposed below is not new. David Broadhurst and Phil Carmody (both missed members of this list, unlike the Goldbach-proving spammers)
        Message 3 of 3 , Feb 4, 2005
          As expected, my idea proposed below is not new. David Broadhurst and Phil
          Carmody (both missed members of this list, unlike the Goldbach-proving
          spammers) pointed me towards the twin-prime constant C2 = 0.660162, which is
          the ratio between Mertens' product and `my' product below. One can use
          Cohen's methods from http://www.math.u-bordeaux.fr/~cohen/hardylw.dvi to
          compute C2 to high-precision, as pointed out by David Broadhurst. Mike Oakes
          also pointed out (off list) an interesting site regarding the twin-prime
          constant, the page by Xavier Gourdon at
          http://numbers.computation.free.fr/Constants/Primes/twin.html. If this isn't
          enough, the owners of Crandall & Pomerance's book can have a look at chapter
          1, who has a derivation of the twin prime conjecture.

          Décio

          On Thursday 03 February 2005 23:49, you wrote:
          > For p prime, the integer p-1 is an important quantity in certain analyses
          > (particularly if they involve the group (Z/pZ)*), but as I recall, this
          > integer is usually considered as `a random integer in the vicinity of p' in
          > such analyses (except perhaps by considering that it is even).
          >
          > However, a neat idea occurred to me: just as the probability that 2 divides
          > this integer is skewed in comparison to a random integer (it's 1 in this
          > case but 1/2 for a random integer), so is the probability that it is
          > divisible by any other prime. Consider for instance the residue class of p
          > mod 3; unless p itself is 3, then p == 1 or 2 mod 3, with equal probability
          > for each residue class. So p-1 == 0 or 1 mod 3 also with equal probability.
          > Thus, p-1 is divisible by 3 with probability 1/2, not 1/3 as expected.
          > Using the same argument, p-1 is divisible by a given prime q with
          > probability 1/(q-1), not 1/q.
          >
          > The first implication that occurred to me is that one shouldn't use
          > Mertens' theorem in any analyses involving p-1 where p is prime. For
          > instance, I computed the probability that primes from 3 to 31337 divide a
          > given integer using Mertens' theorem; the result is 0.1085. Using PARI/GP
          > to evaluate the product (1 - 1/(p-1)) for primes p from 3 to 31337, I
          > obtained 0.07157. The difference is quite real.
          >
          > I'll try to work out an estimate, similar to Mertens' theorem, but for the
          > product (1 - 1/(p-1)) instead. However, I'm pretty sure David Broadhurst or
          > Mike Oakes will beat me to it (:
          >
          > I don't know how useful this is (probably not useful at all), but I thought
          > it was neat and worth mentioning.


          [Non-text portions of this message have been removed]
        Your message has been successfully submitted and would be delivered to recipients shortly.