Re: [math-fun] cyclotomic factorization
From: rwg@sdf.lonestar.org
I thought the appearance of 2s (or 3s ...) in the coefficients of factor(x^n-1) was equivalent to >= three (or four ...) distinct primes dividing n, but it seems they can't all be 3 mod 4 since n=231 fails.
What's "failure"? There are cyclotomic polynomials Phi(pqr) with maximum height 1 where p,q,r == 1 (mod 4) and cyclotomic polynomials with huge maximum height where p,q,r == 3 (mod 4), such as pqr=79.131.199 with height 41. Phil
From: rwg@sdf.lonestar.org
I thought the appearance of 2s (or 3s ...) in the coefficients of factor(x^n-1) was equivalent to >= three (or four ...)� distinct primes dividing n, but it seems they can't all be 3 mod 4 since n=231 fails.
Phil Carmody> What's "failure"? Height+1 < # distinct odd prime factors of n.
There are cyclotomic polynomials Phi(pqr) with maximum height 1 where p,q,r == 1 (mod 4)
E.g.?
and cyclotomic polynomials with huge maximum height where p,q,r == 3 (mod 4), such as pqr=79.131.199 with height 41.
Phil
Mma 7.0 seems to disagree: Max@@Abs/@CoefficientList[#,x]&/@List@@Factor[x^(79*13*199)-1] {1, 1, 1, 1, 1, 1, 1, 2} (with >10^5 terms in that last factor), whereas Max@@Abs/@CoefficientList[#,x]&/@List@@Factor[x^(3*5*7*11)-1] {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 3, 3} --rwg HETEROPYCNOSIS HYPOSECRETIONS
From: rwg@sdf.lonestar.org
I thought the appearance of 2s (or 3s ...) in the coefficients of factor(x^n-1) was equivalent to >= three (or four ...)� distinct primes dividing n, but it seems they can't all be 3 mod 4 since n=231 fails.
Phil Carmody> What's "failure"? Height+1 < # distinct odd prime factors of n.
There are cyclotomic polynomials Phi(pqr) with maximum height 1 where p,q,r == 1 (mod 4)
E.g.?
and cyclotomic polynomials with huge maximum height where p,q,r == 3 (mod 4), such as pqr=79.131.199 with height 41.
Phil
Mma 7.0 seems to disagree: Max@@Abs/@CoefficientList[#,x]&/@List@@Factor[x^(79*13*199)-1] {1, 1, 1, 1, 1, 1, 1, 2} (with >10^5 terms in that last factor), whereas Max@@Abs/@CoefficientList[#,x]&/@List@@Factor[x^(3*5*7*11)-1] {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 3, 3} --rwg HETEROPYCNOSIS HYPOSECRETIONS
From: rwg@sdf.lonestar.org
I thought the appearance of 2s (or 3s ...) in the coefficients of factor(x^n-1) was equivalent to >= three (or four ...)� distinct primes dividing n, but it seems they can't all be 3 mod 4 since n=231 fails.
Phil Carmody> What's "failure"?
Height+1 < # distinct odd prime factors of n.
There are cyclotomic polynomials Phi(pqr) with maximum height 1 where p,q,r == 1 (mod 4)
E.g.?
and cyclotomic polynomials with huge maximum height where p,q,r == 3 (mod 4), such as pqr=79.131.199 with height 41.
Phil
Mma 7.0 seems to disagree: Max@@Abs/@CoefficientList[#,x]&/@List@@Factor[x^(79*13*199)-1] {1, 1, 1, 1, 1, 1, 1, 2} (with >10^5 terms in that last factor), whereas Max@@Abs/@CoefficientList[#,x]&/@List@@Factor[x^(3*5*7*11)-1] {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 3, 3} --rwg HETEROPYCNOSIS HYPOSECRETIONS Eek, sorry, I botched the input! Goddam Adobe Flash is bogging my machine so badly that when I click to move the cursor, the next several edits happen back at the former location! It looks like 79*131*99 may be beyond Mma 7.0 on a 2G machine, but Aha, height(x^(3*7*47)-1) = 2 (thus cooking my 3mod4 theory), and height(x^(41*43*53)-1) = 17 ! --rwg CAMPHOR TREE PERCHROMATE DISCREETER CIDER TREES
If a sequence of integers is periodic modulo every positive integer, then it obeys a linear or bilinear recurrence with constant coefficients. E.g., if s(n):= somos4(n)^2, then - 4 s(n - 6) s(n - 1) + 29 s(n - 5) s(n - 2) + 116 s(n - 4) s(n - 3) s(n) = -------------------------------------------------------------------- s(n - 7) --rwg IN REALITY LINEARITY IMPERIALIST PRIMALITIES
No, probably. I think there are more sequences that are periodic mod-every-N, than sequences that obey a recurrence, with one possible glitch. a) The sequences periodic mod every N are non-denumerable, "aleph 1". Make a list of the primes & prime powers. These are the N for which the value of LCM(1,...,N) increases, and for which "mod N" has new information. We build a sequence whose period length doubles each time a new such N appears. Copy the sequence-so-far. Read the next bit of our non-denumerable random bit string; if it's a 1, add N! to each element of the copy. Proceed to the next prime-or-prime-power. b) The sequences that obey a recurrence are denumerable. We can list the recurrences, and each recurrence's starting values are a finite set of integers. This gives an enumeration of the sequences. This works as long as the sequence is determined by enough initial values of the recurrence, which is my guess at your intention. However, we can manipulate sequences from (a) to obey useless bilinear recurrences: Take any (a) sequence, insert a 0 after every term. The periodic-mod-every-N property is preserved; the periods are all doubled. The new sequence obeys the dubious recurrence s(n) s(n+1) = 0, along with your somos4^2 rule. Rich ------------- Quoting rwg@sdf.lonestar.org:
If a sequence of integers is periodic modulo every positive integer, then it obeys a linear or bilinear recurrence with constant coefficients. E.g., if s(n):= somos4(n)^2, then
- 4 s(n - 6) s(n - 1) + 29 s(n - 5) s(n - 2) + 116 s(n - 4) s(n - 3) s(n) = -------------------------------------------------------------------- s(n - 7) --rwg IN REALITY LINEARITY IMPERIALIST PRIMALITIES
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (3)
-
Phil Carmody -
rcs＠xmission.com -
rwg＠sdf.lonestar.org