Re: How hard is this to prove?

On 2 Oct 2005 09:53:01 -0700, "Joubin Houshyar" <Sun_of_27@xxxxxxxxx>
wrote:

>quasi wrote:
>> On 2 Oct 2005 07:01:57 -0700, "Joubin Houshyar" <Sun_of_27@xxxxxxxxx>
>> wrote:
>>
>> >For the problem that I am trying to solve it may actually make more
>> >sense to try and establish the behaviour of phi(n) based on sub-sets of
>> >N. (Lacking a knowledge of the 'accepted terminology') I would like to
>> >get a handle on the behaviour of phi(n) for distinct 'classes' of
>> >integers.
>>
>> Well, if you consider the formula for phi(n) in the form
>>
>> phi(n)=c(n)*n
>>
>> where c(n) is the product of all terms of the form 1-1/p where p
>> ranges over the distinct primes of n,
>>
>> then it's clear that phi(n) is very well behaved if you keep the same
>> distinct prime factors.
>>
>> A few examples:
>>
>> if n=2^a then phi(n)=(1/2)*n
>>
>> if n=2^a*3^b then phi(n)=(1/3)*n
>>
>> if n=3^a*7^b then phi(n)=(4/7)*n
>>
>> if n=3^a*5^b*11^c then phi(n)=(16/33)*n
>>
>> Thus, there are lots of straight lines each of which intersects the
>> graph of phi(n) at infinitely many points.
>
>Thanks for the insight. That is clearly the case. So for these one
>could quickly establish the 'n' where the transition in the relation
>between pi(n) and phi(n) occurs, right?
>
>(Just factor out the n multiple from the pi(n) to phi(n) relation and
>then examine 1/ln(n) in relation to (1-1/p1)*(1-1/p2)..etc, correct?.)

Yes -- for the class of numbers n with a specified set of distinct
primes factors p_1,p_2,p_3,...,p_k, phi(n)=c*n where c is the product
(1-1/p_1)*(1-1/p_2)*...*(1-1/p_k), so phi(n)/pi(n) is asymptotic to a
constant times (c*n)/(n/ln(n)), which, up to a positive constant
multiple, simplifies to ln(n), so for large enough n (keeping the set
of distinct primes fixed), the ratio must exceed 1, and in fact
approaches infinity.

>But how would you make use of this systematically?

I'm not sure, but the basic intuition here is that phi(n) does not
grow asymptotically in just one way. There are classes, each class
following separate linear paths.

>Infinitely many
>such lines can be constructed. (All the unique permutations of the
>distinct primes, correct? (2, 3), (2, 5), (2, 7), .. (3, 5), (3, 7),
>... etc. (But this is countable, right?)

Right.

As an exercise, can you prove that the product
(1-1/p_1)*(1-1/p_2)*...*(1-1/p_k) is unique to a given set of distinct
primes? In other words, if positive integers a, b are such that
phi(a)/a=phi(b)/b then a,b have the same set of distinct prime
factors.

> In terms of the problem I
>was considering, which was establishing some relation between the
>number of primes vs. comps in any given Reduced Residue Set mod n, this
>approach seems to basically reformulate the original problem...)

I'm not sure if I understand what the problem actually is (or was),
but yes, as you get new info, the problems often need to adjust,
sometimes dramatically.

>(& How about using other possible forms of ln(n) as well? Would the
>series form of ln(n) be helpful to use here given the form of phi(n)?
>
>Or perhaps just a simple expansion of 1/ln(n) to 1/((ln(k) + ln(p1) +
>ln(p2) + ... + ln(pn)), where n = k * p_1 * ... * p_n and k is a
>product of some of the p_x's in that list?)

Seems like a good idea, but maybe just stay with square-free numbers
to avoid the extra factor k.

quasi
.

Quantcast