## p-1 isn't a random integer

Expand Messages
• 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]
• 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]
• 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.