"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.
>>>> Hm. n(y,P) = o(p(y)) or O(p(y)) ?
>
>>> No: n(y, P) = o(p(y)) means that the limit in the previous
>>> line is 0, and n(y, P) = O(p(y)) means that there is a
>>> positive bound C such that for all sufficiently large y,
>>> n(y, P)/p(y) < C.
>
>>> 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. 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.
* 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.
Cheers.
|
