Re: How hard is this to prove?

On 1 Oct 2005 21:28:01 -0700, "Joubin Houshyar" <Sun_of_27@xxxxxxxxx>
wrote:

>quasi wrote:
>> On Sat, 01 Oct 2005 23:38:23 -0700, quasi <quasi@xxxxxxxx> wrote:
>>
>> >On 1 Oct 2005 20:17:13 -0700, "Joubin Houshyar" <Sun_of_27@xxxxxxxxx>
>> >wrote:
>> >
>> >>
>> >>Joubin Houshyar wrote:
>> >>> quasi wrote:
>> >>> > On 1 Oct 2005 19:48:37 -0700, "Joubin Houshyar" <Sun_of_27@xxxxxxxxx>
>> >>> > wrote:
>> >>> >
>> >>> > >I am considering the following conjecture:
>> >>> > >
>> >>> > >(i) pi(n) > phi(n) / 2
>> >>> > >
>> >>> > >I have a few questions and would greatly appreciate feedback.
>> >>> > >
>> >>> > >1) Is this known? If it is, then great! (Could you please provide
>> >>> > >reference(s)?)
>> >>> >
>> >>> > It's not known.
>> >>> >
>> >>> > >2) If not known, how hard (do you think) it would be to prove?
>> >>> >
>> >>> > Very hard, since it's also not true.
>> >>>
>> >>> Right you are. A typo:
>> >>>
>> >>> Revised conjecture:
>> >>>
>> >>> (i) pi(n!) > phi(n) / 2
>> >>>
>> >>> For all n > 4, where n is an even number.
>> >>
>> >>(Actually, scratch that -- Simply for all n > 4)
>> >>
>> >>(i) pi(n!) > phi(n) / 2 (where n > 4)
>> >>
>> >>>
>> >>> Could you please reconsider the questions?
>> >>>
>> >>> /R
>> >>>
>> >>> Joubin Houshyar
>> >
>> >Well, now your inequality is obviously true, but much too weak, since
>> >(bypassing small values if n):
>> >
>> >pi(n!)>n!/ln(n!)>n!/ln(n^n)=(n-1)!/ln(n)>(n-2)!>n/2>phi(n)/2
>> >
>> >quasi
>>
>> In other words, phi(n)/2 is tiny compared with pi(n!).
>
>
>[I appreciate your help here. (Amateur hour, so please bear with me.)]
>
>Well, actually you threw me off with your first reply. The original
>was correct, but it clearly doesn't apply to all n.
>
>Basically, I thought that it should hold -- rather I wanted it to hold
><g> -- for n = 2 * k, where k is not prime.
>
>Then we consider pi(n) > phi(n)/2.
>
>I plugged a few numbers in the calculator (haven't programmed it yet.)
>
>1)
>n = 210
>phi(n) = 48
>pi(n) = 36 > 48/2
>
>2)
>n = 120
>phi(n) = 32
>pi(n) = 30 > 32/2
>
>3)
>n = 110
>phi(n) = 40
>pi(n) = 30 > 40/2
>
>4)
>n = 108
>phi(n) = 36
>...
>
>5)
>n = 720
>phi(n) = 48
>pi(n) = 128 > 48/2
>
>5)
>n = 2310
>phi(n) = 480
>pi(n) = 343 > 480 / 2
>
>It definitely seems to hold better for multi-factor (distinct) n's.
>(Ex. primorials and factorials. In fact, it may actually hold for
>these -- I'll have to write a program to check it.)
>
>But cases where n = 2^2 * p definitely seem to break it fairly
>consistently starting with p=31 and it gets worst when p get larger
>(which I guess is obvious once one sees it).
>
>6)
>n = 4 * 31 = 124
>phi(n) = 60
>pi(n) = 30 // broke
>
>7)
>n = 2308
>phi(n) = 1154 (!)
>pi(n) = 343
>
>... and there goes the conjecture ...
>
>I erronuously thought that phi(n) behaved in a relatively smooth/linear
>fashion, but clearly its all over the place! (cf Phi(2308)=1154 and
>phi(2310)=480).
>
>So apparently its not that phi(n) is huge in general, but that it can
>jump to fairly huge numbers.
>
>Anyway, thanks for your help and time.
>
>/R


Yep, phi(n) is all over the place, but relatively big.

Perhaps the right question is this:

What simple function f(n) provides an efficient asymptotic lower bound
for phi(n)? My guess is this ...

There exist positive constants, c1,c2, with c1<c2 such that:
(1) phi(n)>c1*(n/ln(ln(n))) for all sufficiently large n
(2) phi(n)<c2*(n/ln(ln(n))) for infinitely many n.

If the above is true (we only need (1)), then phi(n)/pi(n) approaches
infinity, so phi(n) is a higher order of magnitude than pi(n). Thus,
dividing by 2 or any other constant won't provide the inequality you
conjectured.

As to the places where phi(n) is asymptotically least, instead of the
factorials, I suggest the product of the first k primes:

2
2*3
2*3*5
....
2*3*5*...*p_k.

Try this experiment.

Let n(k) be the product of the first k primes.

Graph n(k)/phi(n(k)) as a function of k for k=1..30.

Compare against the graph of c*ln(k) for various constants c.

quasi
.

Relevant Pages