Re: How hard is this to prove?

quasi wrote:
> 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.

The original problem, which (effectively) remains the problem (as you
will see), was to explore a tactic of approaching the strong Goldbach
conjecture: Taking the obvious notion that for any number n > 4, the
reduced residue set member pairs form a set of pairwise complements
that add to n. Of course, in a RRS, all members are relatively prime
to the modulus n.

So how to establish that at least one pair is absolute primes?
Obviously a sub-set of RSS(n) will be absolute primes, and the total
number of members given by phi(n).

The naive error happened when I played with a few managable such sets
-- with n being a primorial -- and got the (false) impression that
pi(n) is at least twice as large as phi(n). (Thus the ill-fated
conjecture above.)

Based on that notion, the idea was to assume the worst case in such
pairing -- every prime will be paired with a composite -- and then if
pi(n) > phi(n)/2, that would still leave a few primes which would then
necessarily have to be prime partions of n.

So the whole point of using phi(n) was to use it as a shortcut tool to
do away with the (obviously very hard) problem of dealing with
'structure' of RRSs. But per your very helpful feedback, it seems that
by following that tactic one is merely delegating the hard problem from
the RSS to the much more problematic space of N and classes of numbers
in N and how phi(n) behaves.

Overall though it was educational (which is good) but it has nudged me
a bit from my fence sitting position regarding the provability of
certain matters regarding primes.

So what I got out of this is that some fairly interesting re-alignments
occur when one is dealing with non-primorial modules, with the
composites lining up and forming c <-> c pairs, whereas in RSS's mod
some primorial, they are mostly paired with primes in p <-> c pairs.

Anyway that is the background, and thanks again for your patient hand
holding. I'll consider the suggestions in your last post, but I hope
that at this point it is clear that chasing phi(n) in such a manner
effectively removes its (original) utility as a shortcut tactic.

/Regards

Joubin Houshyar

>
> >(& 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

.

Relevant Pages

  • Re: sum n consecutive primes
    ... primes beginning with p equals the product of ... n distinct primes. ... consecutive primes beginning with p sum to a product of distinct ... primes and ind is the the number of products of distinct primes that ...
    (sci.math)
  • Mystery Permutation
    ... is a permutation of the first 10 integers. ... *ais divisible by the same number of distinct primes as ais. ... your own such puzzle, with preferably as many variables as possible and ...
    (sci.math)
  • Mystery Permutation
    ... is a permutation of the first 10 integers. ... *ais divisible by the same number of distinct primes as ais. ... your own such puzzle, with preferably as many variables as possible and ...
    (rec.puzzles)
  • Re: sum of cubed primes is a square in two ways
    ... >> Do there exist distinct primes A,B,C,D and an integer s ... > So the factors are either relatiively prime squares ... of two cubed odd primes even in one way, ...
    (sci.math)
  • Re: Irreducible polynomials in Z_p
    ... Galois group is the Klein's Four group. ... and there are infinitely many such primes. ... infinitely many distinct primes p such that f is reducible.. ...
    (sci.math)