On Sun, 20 Jul 2008 18:31:21 +0100, Jack <jj@[EMAIL PROTECTED]
>
wrote in <news:qDKgk.44993$7B3.563@[EMAIL PROTECTED]
> in
alt.algebra.help:
> "Brian M. Scott" <b.scott@[EMAIL PROTECTED]
> wrote in message
> news:1ln1u6xp4ff3a.ok9hy602kjlf$.dlg@[EMAIL PROTECTED]
>> On Sun, 20 Jul 2008 17:55:17 +0100, Jack <jj@[EMAIL PROTECTED]
>
>> wrote in <news:U5Kgk.59080$GO7.37014@[EMAIL PROTECTED]
> in
>> alt.algebra.help:
>>> "Brian M. Scott" <b.scott@[EMAIL PROTECTED]
> wrote in message
>>> news:83moctyfxgbp.wjxllm2oemie.dlg@[EMAIL PROTECTED]
>>>> On Sat, 19 Jul 2008 23:58:32 -0700, William Elliot
>>>> <marsh@[EMAIL PROTECTED]
> wrote in
>>>> <news:Pine.BSI.4.58.0807192335480.2040@[EMAIL PROTECTED]
> in
>>>> alt.algebra.help:
>>>> [...]
>>>>> Never mind. I'll guess what you're trying to say.
>>>>> Let P be a set of primes.
>>>>> Let n(y,P) be the number of integers n, in [1,y]
>>>>> with for all p in P and p <= sqr y, p not divide n.
>>>>> Then n(y,P) converges on being negligibly different from
>>>>> the number of primes found in that interval. Hm. Mostly
>>>>> gibberish. Let's see.
>>>>> Let p(y) be the number of primes in [1,y]
>>>>> Then lim(y->oo) n(y,P)/p(y) = 1.
[...]
>>>> There is a notation abbreviating the statement that
>>>> lim_{y --> oo} {n(y, P)/p(y)} = 1: n(y, P) ~ p(y).
>>>> The claim is obviously false. Take P = {2}. For all
>>>> y >= 4, n(y, P) is simply the number of odd integers in the
>>>> interval [1, y], which is ceil(y/2) ~ y/2. By the prime
>>>> number theorem, however, p(y) ~ y/ln(y) Thus,
>>>> n(y, {2})/p(y) = ~ (y/2)/(y/ln(y)) = ln(y)/2 --> oo as
>>>> y --> oo.
>>>> More generally, let P be any finite set of primes, and let
>>>> m = prod(P). From basic properties of Euler's phi function
>>>> we know that n(m, P) = phi(m) = prod{p - 1 : p in P}. It's
>>>> also clear that for any k in N, the number of integers in
>>>> the interval [km + 1, (k+1)m] that are divisible by none of
>>>> the primes in P is also phi(m). Thus, for any y in Z+ we
>>>> have n(km, P) = k * phi(m). But p(km) ~ km/ln(km), so
>>>> n(km, P)/p(km) ~ k * phi(m)/[km/ln(km)] =
>>>> [phi(m)/m] * ln(km), which increases without bound as k
>>>> increases, since phi(m)/m is constant. In particular, the
>>>> limit isn't 1.
>>>> This shows that Jack's claim is false, assuming that your
>>>> translation of it is correct.
>>> But if you look at the graph here:
>>> http://mathworld.wolfram.com/PrimeNumberTheorem.html
>>> are you denying that the lines defining the bounds Li(n) and L/Ln(n)
do
>>> not
>>> serve also as bounds within which the pro****tion of integers n in any
>>> interval [1,y] for which p in P does not divide n diverges from the
value
>>> found by your formula n(m, P) = phi(m) = prod{p - 1 : p inP}?
>> I'm not going to waste my time trying to disentangle all of
>> those negatives. If you can recast that in a more
>> intelligible form, I'll look at it. But whatever you're
>> trying to say, the fact is that if William's translation of
>> your claim is, as you say, accurate, then the claim is
>> false. What's more, it's false *because of* the prime
>> number theorem.
> I made the claim not because of any hare-brained idea I
> had, but because I was informed of it by a competent
> number theorist.
It's pretty clear that either you misunderstood him, he
misunderstood you, or he made a mistake.
> If you observe the limits defining, as by the PNT, the
> number of primes that will be found in any interval
> [1,y], by illustrated the graph in the link I referenced,
> then I would be interested to know how the number of n,
> found by phi(m) \times (y-x/(prod{p : p inP}))* can
> possibly fail to fall within the same bounds, or at least
> fall within limits that converge on on or other of the
> values found by either of the two functions defining
> such bounds.
I don't know what x is.
I showed above that n(km, P) = k * phi(m). From the
Mathworld page that you cite, p(n)/(n/ln(n)) < 1.105 for
large n, and hence p(n) < 1.105n/ln(n) for large n. Thus,
for large k we have p(km) < 1.105km/ln(km).
But then since n(km, P) = k * phi(m),
n(km, P)/p(km) > k * phi(m)/[1.105km/ln(km)],
n(km, P)/p(km) > phi(m) * ln(km)/(1.105m),
and hence, setting c(m) = phi(m)/(1.105m),
n(km, P)/p(km) > c(m) * ln(km)
for large k. Since ln(km) grows without bound as k
increases, and c(m) > 0, the ratio n(km, P)/p(km) also grows
without bound as k increases.
> * If I understand correctly, phi(m) is the number of n for
> which no p in P divides n for n in an interval of length
> equal to the product of all p in P.
By definition it's the number of integers in the interval
[1, m] that are relatively prime to m. In this case that's
the number of integers in [1, m] that are not divisible by
any member of P. If k is any integer, it can easily be
shown that it's also the number of integers in the interval
[k, k + m - 1] that are not divisible by any member of P.
|
