Chinese remainder theorem for cyclotomic polynomials in Z[X]

Abstract: By the Chinese remainder theorem, the canonical map [Psi_n: R[X]/(X^n-1) o oplus_{d|n} R[X]/Phi_d(X)] is an isomorphism when

R

is a field whose characteristic does not divide

n

and

P h i_{d}

is the

d

th cyclotomic polynomial. When

R

is the ring

m a t h b f 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

P s i_{n}

(when

R = m a t h b b Z

) using the prime factorisation of

n

. We also give a pictorial algorithm using Young Tableaux that takes

O (n^{3 + e p s i l o n})

bit operations for any

e p s i l o n > 0

to determine a basis of Smith vectors (see Definition 3.1) for the codomain of

P s i_{n}

. In general when

R

is an integral domain, we prove that the determinant of

written with respect to the standard basis is

p r o d_{1 l e q s l a n t i < j l e q s l a n t n} m a t h c a l R (f_{j}, f_{i})

, where

f_{i}

's are pairwise relatively prime monic polynomials and

m a t h c a l R (f_{j}, f_{i})

is the resultant of

f_{j}

and

f_{i}

.

Recommendations

Cites work

Cited in

(2)

This page was built for publication: Chinese remainder theorem for cyclotomic polynomials in \(\mathbb Z[X]\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2344290)