[References to Euler totient function phi(n) for integers n appear below] ============================================================================== From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: number of lower degree poly. primative to poly degree n Date: 13 Jun 1999 06:43:58 GMT In article , Xuming Chen wrote: >Suppose f(x) is a polynomial with degree n and f(x) \in F_q[x], >where F_q is a finite field. Define \Phi(f) to be the number of >polynomials with degree less than n and relatively prime to f(x). This is a good chance to exploit the parallels between the rings Z and F[x] with F a field. We can check that Phi has some of the properties usually proved for phi, using some of the same proofs. Prop. 1: Phi(f) is the number of invertible elements in the ring F_q[x]/( f ) Prop. 2: If gcd(f,g)=1 then Phi(fg)=Phi(f) Phi(g) Proof: F[x]/( fg ) is isomorphic to F[x]/(f) tensor F[x]/(g). Prop. 3: If f is irreducible, Phi(c f^m) = (q^n - 1)*(q^n)^(m-1) for any nonzero constant c. >Define \Phi_q(n) to be the sum of all such \Phi(f), where >f run through all possible cases. I found a general formula >for \Phi_q(n), which I can only prove few cases when n is small. Me too, I guess. For Phi_q(1) are we then to add the (q^1-1) for each of q^2-q polynomials of degree 1? (I don't see what Phi(f) means for constant polynomials). This gives q*(q-1). For Phi_q(2) I see (q^3-q^2) polynomials of degree 2; our count will be greater by a factor of q-1 than the sum over all q^2 _monic_ quadratic polynomials. Of these, q are perfect squares (Phi(f)=(q-1)*q), and (q choose 2) are products of distinct linear factors (Phi(f)=(q-1)^2), leaving (q^2-q)/2 irreducible quadratics (Phi(f)=q^2-1) for a grand total of q^3*(q-1). I didn't track the combinatorics for n greater than 2. Off-topic a bit: Trying to pursue the analogy I thought about the sum S of phi(n) for n=1, 2, ..., N. Empirically, I get great agreement estimating this sum S as (3/pi^2)*N^2, but I can't recall this as one of the known "pi^2/6" results (this estimate may be stated as "phi(n) is roughly (6/pi^2)*n"). I also noticed that S/N was integral for a few N (I looked up to N=10000) and found only these: N S S/N 1 1 1 2 2 1 5 10 2 6 12 2 16 80 5 25 200 8 36 396 11 249 18924 76 617 115996 188 1296 510624 394 Are there any others? Is there a "reason" there are so many squares among the values of N? dave ============================================================================== [This sequence now included in Sloane's sequence server, sequence #A048290] ============================================================================== Date: Tue, 15 Jun 1999 14:06:12 -0700 (PDT) From: Oren Patashnik To: rusin@vesuvius.math.niu.edu Subject: Asypmtotics of Phi(N) [was: Re: number of lower degree poly...] Hi Dave-- > Trying to pursue the analogy I thought about the sum S of phi(n) for > n=1, 2, ..., N. Empirically, I get great agreement estimating this sum S > as (3/pi^2)*N^2, but I can't recall this as one of the known "pi^2/6" > results (this estimate may be stated as "phi(n) is roughly (6/pi^2)*n"). Yes; the leading term (3/pi^2)*N^2 of the sum was due to Dirichlet in 1849. A simple derivation appears at the end of section 9.3 of Concrete Math, Graham et al., Addison-Wesley, 2nd ed., 1994. (Due to a recently discovered bug in a 1960 paper, the upper bound for the error term for that sum mentioned in the margin of that book is not quite right---O(N (log N)^2/3 (loglog N)^4/3) is the best that's known now.) Once upon a time I investigated this sum, and I gave a brief history of it in a Monthly paper "Pizza Slicing, Phi's, and the Riemann Hypothesis", Bender et al., 101(4):307--317, April 1994. > I also noticed that S/N was integral for a few N (I looked up to N=10000) > and found only these: > N S S/N > 1 1 1 > 2 2 1 > 5 10 2 > 6 12 2 > 16 80 5 > 25 200 8 > 36 396 11 > 249 18924 76 > 617 115996 188 > 1296 510624 394 > > Are there any others? Is there a "reason" there are so many squares among > the values of N? I guess the obvious heuristics would suggest that this should be an integer about ln N times among the first N values, and ln 10000 is about 9.2, so 10 occurrences is about right. Thus I'd guess that this happens infinitely often. The squares observation is interesting, but I don't offhand see a reason for it. In any case, if you learn of anything else about this, I'd appreciate your emailing me anything you don't post. Thanks. -- Oren ============================================================================== Date: Tue, 15 Jun 1999 22:39:39 -0700 (PDT) From: Oren Patashnik To: rusin@math.niu.edu Subject: Re: Asypmtotics of Phi(N) [was: Re: number of lower degree poly...] > Thanks for your response. I hadn't bothered to check Sloane's server until > you wrote back, but I see now this sequence isn't there. I submitted it and > included your monthly article as a reference. I'll keep a file on the > sequence at my site in case anyone collects more information. Can I append > your letter to the file? (With or without your email address as you prefer) Sure, no problem, and feel free to include my name, but please don't include my email address. And in case you don't already have the full author names for the Monthly article, they are: Edward A. Bender, Oren Patashnik, and Howard Rumsey, Jr. -- Oren ============================================================================== From: Dean Hickerson Newsgroups: sci.math Subject: Re: number of lower degree poly. primative to poly degree n Date: 18 Jun 1999 13:22:52 GMT Dave Rusin (rusin@vesuvius.math.niu.edu) wrote: > Off-topic a bit: > > Trying to pursue the analogy I thought about the sum S of phi(n) for > n=1, 2, ..., N. Empirically, I get great agreement estimating this sum S > as (3/pi^2)*N^2, but I can't recall this as one of the known "pi^2/6" > results (this estimate may be stated as "phi(n) is roughly (6/pi^2)*n"). It's proved in Hardy and Wright. > I also noticed that S/N was integral for a few N (I looked up to > N=10000) and found only these: > N S S/N > 1 1 1 > 2 2 1 > 5 10 2 > 6 12 2 > 16 80 5 > 25 200 8 > 36 396 11 > 249 18924 76 > 617 115996 188 > 1296 510624 394 > > Are there any others? Up to 38000000, there are 10 more: N S S/N 13763 57584392 4184 76268 1768121044 23183 189074 10866460928 57472 783665 186673704990 238206 1102394 369399000672 335088 3258466 3227363942030 990455 3808854 4409712145062 1157753 7971034 19313050162736 2422904 15748051 75383305960534 4786834 27746990 234020166937260 8434074 Assuming that S mod N is randomly distributed among the values from 0 to N-1, except that S is even for all N>1, we'd expect about log(M) even values and about log(M)/2 odd values on the list up to M. The data above seems to agree with that fairly well. > Is there a "reason" there are so many squares among the values of N? I think it's just coincidence. There are no more squares among the new values; in particular, 6^8 = 1679616 isn't in the list. Dean Hickerson dean@math.ucdavis.edu ============================================================================== Date: Sat, 19 Jun 1999 04:30:27 -0700 From: Dean Hickerson To: njas@research.att.com Subject: Sequence A048290 Cc: rusin@vesuvius.math.niu.edu I understand that Dave Rusin recently submitted sequence A048290, which contains the numbers n for which n divides the sum from k=1 to n of phi(k). In response to his sci.math article about this, I extended the search up to 38000000, and can add 10 more terms to the sequence: %S A048290 1,2,5,6,16,25,36,249,617,1296,13763,76268,189074,783665,1102394, %T A048290 3258466,3808854,7971034,15748051,27746990 The comment line should be changed to: %C A048290 There are no other values with n < 38000000. Note that half of the first 10 values are squares; significance unknown. The Euler-sum to n is about (3/pi^2)*n^2. The heuristics can be improved slightly: %F A048290 Not obviously infinite; rough heuristics predict about 3/2 log(N) such n's less than N, log(N) even ones and log(N)/2 odd ones. (The heuristic argument is simple: The sum of phi(k) up to n is always even for n>1, but otherwise seems to be uniformly distributed mod n. So an odd n is in the sequence with probability 1/n, an even n has probability 2/n. Hence the number of odd ones up to N should be about 1 + 1/3 + 1/5 + ... + 1/N ~ log(N)/2. The number of even ones should be about 2(1/2 + 1/4 + 1/6 + ... + 1/N) ~ log(N).) Dean Hickerson dean@math.ucdavis.edu ============================================================================== From: Dave Rusin Date: Sat, 19 Jun 1999 14:52:45 -0500 (CDT) To: dean@math.ucdavis.edu Subject: Re: Sequence A048290 Cc: rusin@math.niu.edu Thanks, Dean. Neal, I don't know if you need me to initiate the changes to the sequence since I submitted it, but these changes are AOK with me. dave