login
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).
8
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,9
COMMENTS
T(n,m) = 1 if and only if (let k = A246655(n)):
(a) gcd(m,k) = 1, and k is a primitive root modulo m;
(b) k is a power of 2, m == 2 (mod 4), and k is a primitive root modulo m/2.
As a result, T(n,m) > 1 if at least one of the following holds:
(i) There is no primitive root modulo m, that is, m is in A033949;
(ii) k is a square number and m > 2.
If p = A246655(n) is prime, then T(n,m) is also the number of irreducible factors in the factorization of the ideal (p) in Z[zeta_m], zeta_m = exp(2*Pi*i/m). Actually, if the m-th cyclotomic polynomial factors as Product_{i=1..T(n,m)} F_i(x) over GF(p), then the factorization of (p) in Z[zeta_m] is (p) = Product_{i=1..T(n,m)} (p,F_i(zeta_m)). As a result, p remains inert in Q(zeta_m) <=> T(n,m) = 1. See Page 47-48, Proposition 8.3 and Page 61-62, Proposition 10.3 of the Neukirch link for a proof. - Jianing Song, Sep 13 2022
LINKS
Amiram Eldar, Table of n, a(n) for n = 1..10011 (antidiagonals n = 1..141, flattened)
Jürgen Neukirch, Algebraic_number_theory.
Hongfeng Wu, Li Zhu, Rongquan Feng, and Siman Yang, Explicit factorizations of cyclotomic polynomials over finite fields, Des. Codes Cryptogr. 83, 197-217 (2017).
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.
EXAMPLE
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
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 *)
PROG
(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)
CROSSREFS
KEYWORD
nonn,easy,tabl
AUTHOR
Jianing Song, Sep 26 2019
STATUS
approved