Jump to main content
Circulant Hadamard

Group Ring

Full overview · Group Ring
Show the proof map

Cyclic positions become powers of X, with a unique coefficient list of length n.

Definition

Let and let be the cyclic group of order . Its integer group ring is

The symbol marks one step around the cycle. An element is an integer linear combination of the positions . Addition is coefficientwise; multiplication adds exponents modulo .

Unique polynomial representatives

Proposition. Every element of this group ring has a unique expression

Proof. The relation reduces every nonnegative exponent modulo , giving a representative of degree less than . If two such representatives agree in this group ring, their difference is divisible by . A nonzero multiple of this monic degree- polynomial has degree at least , so the difference must be zero. Thus the coefficients are uniquely determined.

Also is invertible, with . For example, when , , , and .

Output. An ordered coefficient list and a degree-less-than- representative are equivalent descriptions of the same group-ring element. This makes coefficient notation in later nodes unambiguous.

Back to Group-Ring Encoding