A327818 Square array read by ascending antidiagonals: T(n,m) is the number of irreducible factors in the factorization of the m-th cyclotomic polynomial over GF(k), k = A246655(n) (counted with multiplicity).
1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 2, 2, 2, 2, 1, 1, 1, 1, 4, 2, 1, 4, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 1, 1, 2, 1, 2, 1, 4, 6, 1, 1, 1, 2, 1, 2, 1, 6, 2, 2, 1, 1, 1, 1, 2, 2, 4, 2, 6, 2, 1, 2, 2, 2, 1, 1, 1, 2, 1, 1, 2, 4, 2, 4, 2, 2, 1
Offset: 1
Examples
Table starts n A246655(n) m=1 2 3 4 5 6 7 8 9 10 1 2 1 1 1 2 1 1 2 4 1 1 2 3 1 1 2 1 1 2 1 2 6 1 3 4 1 1 2 2 2 2 2 4 2 2 4 5 1 1 1 2 4 1 1 2 1 4 5 7 1 1 2 1 1 2 6 2 2 1 6 8 1 1 1 2 1 1 6 4 3 1 7 9 1 1 2 2 2 2 2 4 6 2 8 11 1 1 1 1 4 1 2 2 1 4
Links
- Amiram Eldar, Table of n, a(n) for n = 1..10011 (antidiagonals n = 1..141, flattened)
- Jürgen Neukirch, Algebraic_number_theory.
- Jianing Song, My notes on the factorization of cyclotomic polynomials over finite fields.
- Hongfeng Wu, Li Zhu, Rongquan Feng, and Siman Yang, Explicit factorizations of cyclotomic polynomials over finite fields, Des. Codes Cryptogr. 83, 197-217 (2017).
Crossrefs
Programs
-
Mathematica
T[max_] := Module[{pp = Select[Range[max], PrimePowerQ], m, t}, m = Length[pp]; t[i_, j_] := Module[{p = FactorInteger[pp[[j]]][[1, 1]]}, EulerPhi[i] / MultiplicativeOrder[pp[[j]], i/p^IntegerExponent[i, p]]]; Table[t[j, i - j + 1], {i, 1, m}, {j, 1, i}] // Flatten]; T[24] (* Amiram Eldar, Jul 21 2024 *) -
PARI
f(k,m) = if(isprimepower(k), my(p=factor(k)[1,1], s=m/p^valuation(m,p)); eulerphi(m)/znorder(Mod(k,s))) A246655(n) = my(i=0); for(t=1, oo, if(isprimepower(t), i++); if(i==n, return(t))) a(n,m) = f(A246655(n),m)
Formula
Let m = p^e*s, where p is the prime factor of k = A246655(n), gcd(p,s) = 1, then T(n,m) = phi(m)/ord(k,s), where phi = A000010, ord(k,s) is the multiplicative order of k modulo s. Proof:
(a) First consider the case e = 0. Let F be the algebraic closure of GF(k), then Phi_s(x) = 0 has solutions in F, where Phi_s(x) is the s-th cyclotomic polynomial. Let a be any of the solution.
In F, a belongs to GF(k^d) <=> a^(k^d-1) = 1 <=> s|(k^d-1) (note that in F, s is the smallest integer such that a^s = 1). As a result, a belongs to GF(k^ord(k,s)) but not to GF(k^d) for any d < ord(k,s), that is to say, a has algebraic degree ord(k,s) over GF(k). Because a is any of the roots of Phi_s(x) in F, every irreducible factor of Phi_s(x) over GF(k) is of degree ord(k,s), so the number of irreducible factors is phi(s)/ord(k,s);
(b) If e > 0, we can see from the Moebius inversion formula such that Phi_m(x) = (Phi_s(x))^phi(p^e), that the number of irreducible factors is phi(m)/ord(k,s).
The Introduction part in Page 2 and Lemma 1 in Page 3 of Hongfeng Wu's paper (see Links section) also mentions part (a) of this result.
Comments