Chinese Remainder Theorem for Cyclotomic Polynomials in Z[X]

Original · EN

By the Chinese remainder theorem, the canonical map Ψₙ: R[X]/(Xⁿ-1)→ ⊕d|ₙ R[X]/Φd(X) is an isomorphism when R is a field whose characteristic does not divide n and Φd is the dth cyclotomic polynomial. When R is the ring Z of rational integers, this map is injective but not surjective. In this paper, we give an explicit formula for the elementary divisors of the cokernel of Ψₙ(when R=Z) using the prime factorisation of n. We also give a pictorial algorithm using Young Tableaux that takes O(n³⁺ε) bit operations for any ε> 0 to determine a basis of Smith vectors (see Definition 3.1) for the codomain of Ψₙ. In general when R is an integral domain, we prove that the determinant of Ψ: R[X]/(∏ⱼ fⱼ) → ⱼ R[X]/(fⱼ) written with respect to the standard basis is ∏1 i < j n R(fⱼ, fᵢ), where fᵢ's are pairwise relatively prime monic polynomials and R(fⱼ, fᵢ) is the resultant of fⱼ and fᵢ.