PaperlayerView exact revision on arXiv

Source-linked AI summary

Support periods of polynomials and support-primitive decomposition of constacyclic codes over Galois rings

Li Zhu, Hongfeng Wu

arXiv:2610.29284v1cs.ITmath.ITmath.NT

TL;DR

The paper asks how coefficient compression of constacyclic generators relates to support-primitive code decompositions over Galois rings. It connects polynomial periods, root symmetries, and code interleavings, then derives structural results and coding bounds, alongside explicit trace-factor families with exact periods and distances.

  • Problem

    The paper studies how polynomial support periods and coefficient compression relate to root symmetries and support-primitive decompositions of constacyclic codes over Galois rings.

    Source: §8 · p. 42

  • Method

    It relates coefficient compression to root-set stabilizers and coordinate-projection interleavings, using MED structure and torsion codes to characterize periods and cores.

    Source: §1 · p. 2, §8 · p. 42

  • Results

    At lengths dividing q+1, quadratic trace factors determine hulls explicitly, and opposite-trace pairings at length p + 1 give exact support periods and minimum distances.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Every constacyclic code over a finite commutative ring has a unique maximal interleaving into copies of one support-primitive code, without requiring freeness.

    Source: §1 · p. 2

    At repeated-root lengths over Galois rings, identical residue multiplicities can correspond to different support periods.

    Source: §4.6 · p. 23

Abstract

from arXiv · show

Let \(A=\GR(p^e,r)\) have residue field \(\F_q\), and let \(\lambda\in A^\times\). We relate coefficient compression of monic divisors of \(X^N-\lambda\) to support-primitive decomposition of constacyclic codes. At a simple-root length, the support period of every nonconstant monic divisor is preserved at each coefficient precision and equals the order of the multiplicative stabilizer of its root set. For a cyclic Frobenius-orbit polynomial, the multiple equal-difference structure determines its support period, core degree, and least relative degree of an unramified extension over which all its basic-irreducible factors are binomials. Coordinate projections give every constacyclic code over a finite commutative ring a unique maximal interleaving into copies of one support-primitive code. At simple-root lengths over \(A\), the intrinsic period of a code is the greatest common divisor of the periods of its torsion codes. The decomposition yields distance and duality formulas and the arithmetic Singleton bound for free codes. At every length, a nonzero code over \(A\) has the same minimum Hamming distance as its highest torsion code, which gives a refined bound. At repeated-root lengths, identical torsion filtrations can occur with different intrinsic periods, while a class of nonzero codes obtained by substitution from simple-root generators retains the same core and minimum distance. Trace matrices recover the coefficients of basic-irreducible cores using unit pivots, and local Hensel corrections lift compressed factors directly. For \(X^n-1\) with \(p\nmid n\), lifting and output have quasi-linear bit cost in the compressed representation when the arithmetic data and residue factorizations are given.

1 Introduction

The paper connects polynomial coefficient compression to support-primitive decomposition of constacyclic codes over Galois rings. It characterizes periods and cores at simple-root lengths, extends intrinsic decomposition to arbitrary lengths, and derives coding bounds and explicit families.

1 Introduction

  • For nonconstant monic divisors at simple-root lengths, support period agrees with root-set stabilizer order and is preserved at every coefficient precision.The core has degree deg f/s; local Hensel corrections lift it directly, and a trace matrix with unit determinant recovers basic-irreducible core coefficients.Source: §1 · pp. 1–2
  • For cyclic Frobenius-orbit polynomials, the MED structure determines the core degree and least relative extension degree in which all basic-irreducible factors become binomials.For primitive-order layers, Φd(X) = ΦD(X^µ) gives a factorwise correspondence, and layers with the same reduced order share core factors.Source: §1 · p. 2
  • Coordinate projections give every constacyclic code over a finite commutative ring a unique maximal interleaving into copies of one support-primitive code.For simple-root ideals over A, the intrinsic period is the greatest common divisor of the periods of all torsion codes.Source: §1 · p. 2
  • The interleaving yields distance, weight-enumerator, covering-radius, duality, and hull formulas, while the Singleton bound for the core gives the arithmetic Singleton bound for free codes.At every length, a nonzero code over A has the same minimum distance as its highest torsion code, whose period can exceed the full code's and give a stronger bound.Source: §1 · p. 2
  • At repeated-root lengths, substitution from a simple-root generator preserves the support-primitive core, minimum distance, and arithmetic Singleton value for the resulting nonzero code.Identical residue multiplicities, or even identical full torsion chains, need not determine intrinsic periods over a Galois ring.Source: §1 · p. 2
  • At lengths dividing q+1, quadratic trace factors determine hulls explicitly; pairing factors with opposite traces at length p + 1 yields exact support periods and minimum distances.Source: §1 · p. 2

2 Preliminaries

This section sets notation for Galois rings and constacyclic codes and develops factorization, torsion, and equal-difference tools for studying polynomial root sets and code structure. It also identifies stabilizers relevant to equal-difference parts crossing cosets and recalls a finite-field Singleton bound interpreted through the support-primitive core.

2.1 Galois rings and monic polynomials

  • When p ∤ N, each constacyclic multiplier’s principal-unit part has a unique Nth root, and monic divisors of X^N − λ correspond to divisors of its squarefree reduction.Coprime Hensel lifting gives unique lifted roots and preserves the selected root-orbit products.Source: §2.1 · pp. 3–4

2.2 Cyclotomic cosets and orbit factors

  • Cyclotomic cosets index the basic-irreducible factors of X^n − 1, with root order d_γ and degree ord_dγ(q); extension factors correspond to q^t-orbits within each coset.Equal factor degrees need not mean equal root orders.Source: §2.2 · p. 5

2.3 Constacyclic codes, torsion, and duality

  • In the simple-root case, torsion layers select CRT factors by ideal depth and the torsion chain determines the ideal; every nonzero code has the distance of its highest torsion code.The distance identity holds at every length, not only simple-root lengths.Source: §2.3 · p. 7

2.4 Equal-difference and multiple equal-difference structures

  • For squarefree nonconstant polynomials, the root-set stabilizer determines the coarsest MED representation, and root sets are unions of s-th-root cosets exactly when the polynomial lies in Fq[X^s].Every MED representation is obtained from cosets of a subgroup, with the stabilizer giving the unique coarsest representation.Source: §2.4 · pp. 8–9
  • For unions of cosets, coarsest equal-difference parts can cross between cosets, so the union’s stabilizer—not just individual MED indices—is the relevant datum.The passage identifies this as the datum in Proposition 2.6.Source: §2.4 · p. 10
  • The finite-field arithmetic Singleton bound for a nonzero proper constacyclic code at p∤N is interpreted as the ordinary Singleton bound of its finite-field support-primitive core [15, Section 4] [16, Section 5].The full-space code has distance one, and the ambient-period formulation includes that case.Source: §2.4 · p. 10

3 Coefficient-side description of support periods

Support periods compress monic divisors into support-primitive cores that divide shorter ambient polynomials. The section develops this compression across coefficient precision, coefficient reconstruction, local lifting, and repeated-root factorization.

3.1 Compression by the support period

  • A divisor of support period s has the form h(X^s), where s divides N and h divides Y^(N/s) − λ; coordinate projections characterize code stability by exponent classes modulo s.At simple-root lengths, the core commutes with reduction and Hensel lifting, although individual coefficient positions may change.Source: §3.1 · pp. 10–11, §3.2 · p. 11

3.2 Stability at every precision

  • At simple-root lengths, support periods persist at every coefficient precision, while normalization preserves support and gives a diagonal Hamming isometry.Coefficient positions may change under lifting even though their greatest common divisor remains fixed.Source: §3.2 · pp. 11–12

3.3 Coefficient formulas and trace reconstruction

  • Power traces recover basic-irreducible core coefficients through a linear system with unit determinant, even when Newton identities require division by nonunit multipliers.The system can be solved using only unit pivots at every coefficient precision.Source: §3.3 · pp. 12–13

3.4 A local lifting formula

  • A local correction produces the unique lifted monic divisor from a chosen lower-precision factor, and the same correction works after replacing X^N − λ by X^(kN) − λ^k for p ∤ k.The construction also applies directly to the support-primitive core at its shorter ambient order.Source: §3.4 · pp. 13–14

3.5 Canonical blocks at repeated-root lengths

  • At repeated-root lengths, substitution yields pairwise comaximal local blocks whose factorization is unique up to reordering and remains valid at every coefficient precision.The quotient ring of each block is local; its individual divisors require further data.Source: §3.5 · pp. 14–15

4 Root-side description of support periods

This section describes support periods through root-set symmetries, equal-difference structure, and orbit data, extending the account to single Frobenius orbits, cyclotomic layers, and compatible lengths. It also considers exact-order roots and the limitations of residue multiplicities and unramified roots at repeated-root lengths.

4.1 Unit normalization and multiplicative stabilizers

  • At each coefficient precision, a nonconstant monic divisor’s support period equals the order of its multiplicative root-set stabilizer, and its compressed core is support-primitive.The stabilizer order divides N and determines the greatest common divisor of the divisor’s positive support exponents.Source: §4.1 · pp. 16–17

4.2 Teichmüller defining sets and their coarsest MED representation

  • For Teichmüller defining sets, the additive stabilizer determines the unique coarsest MED partition, and normalization preserves its symmetry and compression exponent for any unit parameter.The resulting core belongs to A[Y], divides Y^(d/ℓ) − λ, and remains support-primitive at every precision.Source: §4.2 · pp. 17–18

4.3 Single-orbit compression and unramified binomial factorization

  • A single Frobenius-orbit factor is binomial exactly when its orbit is ED; its MED structure determines its compressed core, support period at every precision, and least unramified degree for binomial factorization.Over A(t), all basic-irreducible factors are binomials exactly when ω divides t; for X^n − 1, the least such degree is ω(n,q), and admissible degrees are its positive multiples. The core coefficients can be reconstructed by an invertible trace system using unit pivots, and the compressed factor has at most ω + 1 nonzero terms.Source: §4.3 · pp. 18–20
  • Compression preserves the support period under reciprocation and preserves self-reciprocity; a degree-two core yields a three-term orbit factor, self-reciprocal exactly when its root order divides q + 1.For the trace reconstruction, the trace matrix of the compressed-core generator is invertible, and the alternative trace values recover coefficients by division by the unit μ.Source: §4.3 · p. 20

4.4 Primitive-order layers

  • For each primitive-order layer, reduction modulo D_d bijects primitive cyclotomic orbits, and the corresponding cyclotomic polynomial factors are obtained by substituting X^μ_d into their basic-irreducible cores.The same core factors can be used for every layer with a common D_d.Source: §4.4 · p. 21

4.5 Compatible lengths, labels, and primitive seeds

  • Under length scaling from n to n′ = kn, orbit size, root order, primitive form, MED index, support period, and compressed polynomial are preserved.The lengths are required to satisfy p ∤ n′, with the primitive roots chosen compatibly by ξ = (ξ′)^k.Source: §4.5 · p. 22
  • Compatible lengths preserve q-orbits and primitive exponents, while leader selection recovers factors at length n and the primitive-order n layer from length kn.Leaders divisible by k select the length-n factors; leaders with gcd(b, kn) = k select the primitive-order n layer.Source: §4.5 · p. 22
  • An exact-order n-th root indexes every basic-irreducible factor by its Frobenius orbit, with unit reindexing matching labels across splitting rings.A primitive seed of order Nℓ supplies roots in the defining-set fiber for a simple-root constacyclic polynomial with Teichmüller parameter of order ℓ; scaling covers arbitrary unit parameters.Source: §4.5 · pp. 22–23
  • Trace-based coefficient recovery for a basic-irreducible core uses unit pivots, and scaling a Teichmüller root preserves the power-basis property.Applied to αµ, the construction recovers the degree-ω core.Source: §4.5 · p. 23

4.6 Obstructions at repeated-root lengths

  • At repeated-root lengths, identical residue multiplicities can yield different support periods, and identical torsion codes can accompany different projection periods.The finite-field repeated-root formula gives 2 for both reductions, but does not determine the ring support period; invariance under X → −X need not force the odd coefficient to vanish.Source: §4.6 · pp. 23–24
  • When p divides N, unit-parameter normalization and roots in unramified extensions may fail, so residue roots and multiplicities do not capture repeated-root block structure.Over Z/p^2Z, X^p − (1 + p) has no root in any GR(p^2, t); for p = 2, X^2 − 3 has no root in any unramified extension of Z/4Z.Source: §4.6 · p. 24

5 Support-primitive decomposition of constacyclic codes

Coordinate projections define a unique maximal interleaving of any constacyclic code over a finite commutative ring into copies of a support-primitive core. At simple-root lengths, torsion codes and their root labels determine the intrinsic period; repeated-root lengths admit exceptions and a preserved-core substitution family.

5.1 Coordinate projections and an intrinsic period

  • Every constacyclic code has a unique maximal interleaving into copies of one support-primitive core, with its intrinsic period given by the greatest admissible coordinate-projection period.The admissible periods are exactly the divisors of a uniquely determined greatest period.Source: §5 · p. 24, §5.1 · pp. 25–26

5.2 Monic divisors and free codes

  • A free constacyclic ideal over a Galois ring is generated by a unique monic divisor, and its support-primitive core is generated by the corresponding compressed divisor.For a monic-divisor code, a divisor s is admissible exactly when the generator belongs to A[X^s].Source: §5.2 · p. 27

5.3 Simple-root ideals, torsion codes, and root labels

  • At simple-root lengths, the intrinsic period of an ideal is the greatest common divisor of the periods of its torsion codes and is determined by the stabilizer of its CRT exponent function.The exponent function records the CRT exponent assigned to each root and is constant on Frobenius orbits.Source: §5.3 · pp. 28–29

5.4 Repeated-root lengths

  • At repeated-root lengths, identical torsion filtrations can have different intrinsic periods, while substitution from a simple-root generator preserves its support-primitive core and minimum distance.The repeated-root intrinsic decomposition still applies to arbitrary ideals, but their torsion filtrations need not determine their periods.Source: §5.4 · pp. 29–30
  • For λ = 1, products of canonical local blocks from simple-root factors have the same support period as every torsion code.This identifies a repeated-root family whose torsion periods agree with the code period.Source: §5.4 · p. 31

6 Coding-theoretic consequences

The support-primitive interleaving transfers weight, distance, covering-radius, and duality properties to a shorter core. Highest-torsion periods yield a refined Singleton bound, with MED structure estimating bounds for products of cyclic factors.

6 Coding-theoretic consequences

  • The coordinate interleaving identifies a code with repeated copies of its support-primitive core by a weight-preserving coordinate permutation.The resulting formulas apply to nonfree codes unless freeness is explicitly assumed.Source: §6 · p. 31

6.1 Weight distribution and covering radius

  • The interleaving multiplies code cardinality, weight enumerator, covering radius, and each module-type multiplicity by the number of copies; free rank scales likewise.For free cores, a rank K core yields a free code of rank sK.Source: §6.1 · pp. 31–32

6.2 Euclidean duality and the hull

  • The dual code has the same intrinsic period as the original, and its support-primitive core is the dual of the original core.LCD, self-orthogonal, dual-containing, and self-dual properties hold for the code exactly when they hold for its core.Source: §6.2 · p. 32

6.3 Distance and the highest torsion code

  • A nonzero code has the same minimum Hamming distance as its highest torsion code, whose support period can exceed the code’s intrinsic period.This yields a highest-torsion refinement of the arithmetic Singleton bound, including at arbitrary lengths.Source: §6.3 · p. 33, §6.4 · p. 34

6.4 Singleton bounds for the two cores

  • The highest-torsion Singleton bound is a refinement of the arithmetic Singleton bound, while the intrinsic-core bound extends the finite-field arithmetic Singleton value for free codes.The free-code bound is attained exactly when the core, equivalently its residue code, is MDS.Source: §6.4 · p. 34

6.5 Products of cyclic factors and MED estimates

  • MED periods of basic-irreducible factors give upper bounds for cyclic codes generated by their products; the exact product period can yield a smaller bound.For a product of two distinct factors in the stated length-8 example, the exact arithmetic Singleton value is 2, versus 5 from the common-order estimate.Source: §6.5 · pp. 36–37

7 Explicit families and computations

The examples show how support periods and cores persist through lifting and compression, and how these structures determine code decompositions, distances, and duality. The families also exhibit cases attaining the arithmetic Singleton bound.

7.1 A local lift over Z/16Z

  • All four successive lifts of X^3 + X + 1 have support period one, although its X^2 coefficient first becomes nonzero modulo 4.Thus lifting preserves the support period without preserving the individual support positions.Source: §7.1 · p. 37

7.2 Powers of two over GR(3^e, 1)

  • For each fixed j, the last two factors have support period 2j−3 and support-primitive cores; at length 32, each associated cyclic code interleaves four copies of a length-eight code.The arithmetic Singleton bound is 3, compared with the ordinary Singleton bound 9.Source: §7.2 · p. 38

7.3 Lengths dividing q + 1

  • In particular, C is LCD if and only if it is free; a self-dual cyclic code of length n exists if and only if e is even and, when it exists, is uniquely pe/2An.Source: §7.3 · p. 39

7.4 The order p + 1

  • At length p + 1, pairing distinct quadratic factors with opposite traces gives quartic generators with support period two or four.Their arithmetic Singleton-bound equality cases are exactly those whose support-primitive cores are MDS.Source: §7.4 · p. 40

7.5 A free code attaining the arithmetic bound

  • The arithmetic Singleton bound is attained for every e and r, and is strictly sharper than the ordinary Singleton bound s + 1 when s > 1.The exhibited free code has support-primitive core (Y −1) and contains no word of weight one.Source: §7.5 · p. 41

8 Concluding remarks

The concluding results connect support-period decomposition with torsion-code distance and clarify what remains true at repeated-root lengths. They also identify a limitation of torsion data and a class of substitutions that preserves core and distance.

Concluding remarks

  • At simple-root lengths, the intrinsic period of an ideal over A is the greatest common divisor of the periods of its torsion codes.For nonconstant monic divisors, coefficient compression, root-set stabilizers, and code interleaving determine the same support period, preserved through Hensel lifting.Source: §8 · p. 42
  • At every length, a nonzero code over A has the same minimum Hamming distance as its highest torsion code.At repeated-root lengths, pa-power substitutions from simple-root generators preserve the support-primitive core, distance, and arithmetic Singleton value.Source: §8 · p. 42
  • For general repeated-root ideals, even the complete torsion filtration need not determine the intrinsic period.By contrast, coordinate-projection decomposition remains valid at arbitrary lengths.Source: §8 · p. 42

A Construction and bit complexity

This appendix estimates the bit cost of constructing the unordered basic-irreducible factorization of X^n − 1 when p ∤ n. It separates preprocessing, residue-field factorization, lifting, output, and root-label matching costs.

A Construction and bit complexity

A.1 Representation and deterministic lifting

The construction groups divisor layers by reduced order, lifts shared core factors, and substitutes them back into each layer. With arithmetic data and residue factorizations supplied, the fixed-stride lifting and output admit a compressed-size bound.

A.1 Representation and deterministic lifting

  • The construction groups divisors by reduced order, factors each distinct reduced cyclotomic layer over Fq, lifts its factors, then substitutes them into the original layers.Source: §A.1 · p. 43
  • Fixed-stride storage records each core’s nonleading coefficients, including zeros, together with its stride and degree.The stated output sizes charge repeated occurrences separately, even when arrays can be shared.Source: §A.1 · p. 43
  • With arithmetic data and the required residue factorizations supplied, ring lifting and fixed-stride output cost eO(Ure log p) + O(Sstride) = eO(Wre log p + WLn) bit operations.The suppressed logarithmic factors in the coefficient-computation term depend only on compressed sizes and ring parameters.Source: §A.1 · p. 43
  • For schoolbook polynomial arithmetic, the dependence on coefficient precision is quadratic.Source: §A.1 · p. 44

A.2 Finite-field factorization and total cost

The algorithm constructs cyclotomic polynomials over the residue field and splits them into irreducible factors by randomized equal-degree factorization. Its expected total cost includes cyclotomic construction and outputting the chosen exponent representation.

A.2 Finite-field factorization and total cost

  • Randomization is confined to the finite-field factorization, and output can use fixed strides or explicit coefficient–exponent pairs.Source: §A.2 · p. 44
  • The algorithm constructs Φ_D mod p using a Möbius product, then factors it into equal-degree blocks of degree w_D.The blocks have total degree at most s_D in each pass; at termination, each block is irreducible.Source: §A.2 · pp. 44–45
  • The expected number of splitting passes is O(1 + log(s/w)), using a tail bound on pairs of irreducible factors that remain together.For odd p the nonseparation probability is at most 5/9 per pass; for p = 2 it is 1/2.Source: §A.2 · p. 45
  • Summing over D gives expected cost eO(V b^2 + U L n), including cyclotomic construction; explicit exponent output costs O(L n) and is included in W L n.The result combines the factorization cost with Theorem A.2.Source: §A.2 · p. 45

A.3 Certification and simultaneous lifting

The appendix gives a certificate for compressed factors and a simultaneous local-correction procedure for lifting them. The corrections recover the factorwise lifts, while avoiding expansion of the substitutions in the certificate.

A.3 Certification and simultaneous lifting

  • A compressed factorization can be certified from stored core polynomials without expanding the substitutions in (A.7).The certificate uses arithmetic data and residue factorizations as inputs.Source: §A.3 · p. 45
  • The certificate’s divisibility tests establish that the substituted factors form the complete factorization into distinct monic basic-irreducible polynomials.The factors are pairwise comaximal, and their product equals the corresponding cyclotomic polynomial.Source: §A.3 · p. 46
  • For a monic polynomial with squarefree reduction, local corrections are coordinates of one global error under a Chinese remainder isomorphism.The updated factors are independent of the chosen monic lifts.Source: §A.3 · pp. 46–47
  • When p ∤ n, batched corrections recover the factorwise lifts within the same stated bound, given the common inverse (nλ)^−1.Product and remainder trees compute the local errors simultaneously.Source: §A.3 · p. 47

A.4 Dense output, orbit labels, and primary blocks

The appendix compares lifting and output strategies, addresses prescribed cyclotomic labels, and extends simple-root stride construction to primary blocks. Its example contrasts sparse explicit output with dense coefficient output.

A.4 Dense output, orbit labels, and primary blocks

  • Given residue factors, batched lifting is quasi-linear in dense output size, while factorwise lifting has fast cost eO((η(n) + 1)n r e log p).The batched bound is summed over the precision-doubling schedule.Source: §A.4 · pp. 47–48
  • For prescribed cyclotomic labels, leader lists can be scaled and merged for globally ordered output; constructing representatives and matching unordered factors to roots have separate costs.Source: §A.4 · p. 48
  • For N = p^a m with p ∤ m, canonical local blocks are constructed by multiplying each simple-root stride by p^a.Source: §A.4 · p. 48
  • In the stated family, explicit sparse output has size Θ(k e + k^2) bits and takes eO(k e + k^2) bit operations, while dense output requires Ω(2 k e) bits.Every displayed coefficient is nonzero, and exponent lengths summed over the layers are Θ(k^2).Source: §A.4 · p. 48
Loading 2610.29284v1…