Chinese Remainder Theorem for Cyclotomic Polynomials in $\mathbf{Z}[X]$

Abstract

By the Chinese remainder theorem, the canonical map \[Ψ_n: R[X]/(X^n-1)\to \oplus_{d|n} R[X]/Φ_d(X)\] is an isomorphism when $R$ is a field whose characteristic does not divide $n$ and ${\Phi }_d$ is the $d$th cyclotomic polynomial. When $R$ is the ring $\mathbf{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 ${\Psi }_n$(when $R=\mathbb{Z}$) using the prime factorisation of $n$. We also give a pictorial algorithm using Young Tableaux that takes $O(n^{3+\epsilon })$ bit operations for any $\epsilon >0$ to determine a basis of Smith vectors (see Definition 3.1) for the codomain of ${\Psi }_n$. In general when $R$ is an integral domain, we prove that the determinant of $\Psi :R[X]/({\prod }_j{f}_j)\to {⨁}_{j}R[X]/(f_j)$ written with respect to the standard basis is ${\prod }_{1⩽i<j⩽n}\mathcal{R}(f_j,f_i)$, where $f_i$'s are pairwise relatively prime monic polynomials and $\mathcal{R}(f_j,f_i)$ is the resultant of $f_j$ and $f_i$.

arXiv comment33 pages, 7 figures

Cited by in corpus (1)

• Measure Theoretic Aspects Of Error Terms