PaperlayerView exact revision on arXiv

Source-linked AI summary

On the structure of polynomial ideal codes and additive Reed--Solomon codes

Umberto Martínez-Peñas, Rubén Rodríguez-Ballesteros

arXiv:2610.21509v1cs.ITmath.IT

TL;DR

PI codes have unresolved structural questions, including their maximum length, duals, and weight distribution. The paper resolves these questions and connects PI codes to an aRS subfamily, finding that those aRS codes inherit the PI results and asymptotically match PI-code length. It also studies extensions to arbitrary polynomial modules and general aRS codes.

  • Problem

    The structural properties of PI codes—including maximum length, duals, dual QMDS status, and weight distribution—were not fully known.

    Source: §1 · p. 2

  • Method

    The paper analyzes PI codes, relates those with irreducible defining polynomials to aRS codes at pairwise nonconjugate evaluation points, and extends the study to arbitrary polynomial modules and general aRS codes.

    Source: §1 · p. 2

  • Results

    PI codes are dually QMDS with an explicit weight distribution, and the corresponding aRS subfamily inherits PI-code results while asymptotically achieving PI-code maximum length.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The PI-code structural results apply to aRS codes whose evaluation points lie in pairwise distinct Frobenius conjugacy classes of degree r.

    Source: §1 · p. 2

    The polynomial-residue-code analysis assumes k≤deg(L), and duality is taken over Fq because the codes are only Fq-linear.

    Source: §2 · p. 3, §3.3 · p. 11

Abstract

from arXiv · show

We study structural properties of polynomial ideal (PI) codes and additive Reed--Solomon (aRS) codes in the folded Hamming metric (equivalently, the Hamming metric over a larger alphabet). We first determine the maximum possible length of PI codes, prove that the dual of every PI code is a generalized PI code, and deduce that PI codes are dually QMDS together with an explicit formula for their weight distribution. We then show that PI codes defined by irreducible polynomials correspond to aRS codes with pairwise nonconjugate evaluation points. For these aRS codes, the previous results on PI codes apply (duality, QMDS property and weight distribution). We show that, asymptotically, aRS codes with nonconjugate evaluation points achieve the same length as PI codes. We also compute the permutation group of such aRS codes. We also extend the family of PI codes to consider arbitrary polynomial modules (not necessarily pairwise coprime), and study when these and general aRS codes satisfy the QMDS and dually QMDS properties.

1 Introduction

The paper studies PI and additive Reed–Solomon codes in the folded Hamming metric, where codes are linear over a prescribed subfield. It resolves structural questions about PI codes and extends those results to related aRS and polynomial residue codes.

1 Introduction

  • The paper studies codes in the folded Hamming metric, equivalently ordinary Hamming metric over an extension alphabet while retaining linearity over a prescribed subfield.This framework allows dimension over the base field not to be a multiple of the alphabet extension degree.Source: §1 · p. 1
  • PI codes generalize classical Reed–Solomon, folded Reed–Solomon, and multiplicity codes, and the paper adds additive Reed–Solomon codes to this connection.PI codes were introduced in connection with capacity-achieving list decoding.Source: §1 · p. 2
  • PI codes have an established QMDS property, but their maximum length, duals, dual QMDS status, and weight distribution were unresolved; this work determines those structural properties.It also introduces polynomial residue codes, extending PI codes to arbitrary polynomial modules, and studies when they are QMDS or dually QMDS.Source: §1 · p. 2
  • When aRS evaluation points lie in pairwise distinct Frobenius conjugacy classes of degree r, the aRS codes are linearly isometric to PI codes with irreducible defining polynomials.The PI-code results therefore apply to this aRS subfamily; for pairwise nonconjugate points, the paper also gives duals, asymptotic length, and permutation groups.Source: §1 · p. 2

2 Preliminaries

The preliminaries set up the blockwise folded Hamming metric, its Fq-linear isometries, and the Singleton-bound terminology used to define QMDS and dually QMDS codes.

2 Preliminaries

  • The folded Hamming weight counts nonzero blocks, so the folded Hamming distance is ordinary Hamming distance on the n blocks.Each block can be viewed as a symbol over Fqr or, after choosing an Fq-basis, as a vector over Fq.Source: §2 · p. 2
  • Every Fq-linear folded-Hamming isometry consists of a coordinate permutation followed by invertible Fq-linear transformations within each block.This describes the allowed equivalences for the block representation.Source: §2 · p. 3
  • Duality is taken with respect to the Fq-vector-space structure, since the codes are only Fq-linear.The folded Hamming metric can also be viewed as Hamming metric over Fqr, but that alphabet viewpoint does not change the stated duality convention.Source: §2 · p. 3
  • A code is QMDS when its distance attains d = n − ceil(k/r) + 1; it is dually QMDS when both it and its dual are QMDS.The definition extends MDS terminology to dimensions over Fq that need not be divisible by r; a QMDS code with r dividing k is MDS.Source: §2 · pp. 3–4

3 Polynomial ideal codes

This section studies polynomial ideal and generalized polynomial residue codes, establishing length, dimension, and dual-structure results. It characterizes their QMDS and dually QMDS properties and gives their folded weight distributions.

3.1 Maximum length of PI codes

  • For q ≥ 2 and r ≥ 2, Mq(r) denotes the maximum cardinality of a set of pairwise coprime degree-r polynomials in Fq[X], and Mq(r−1) < Mq(r).Source: §3.1 · p. 7

3.2 Duality and weight distribution of PI codes

  • The dual of every PI code is a generalized PI code with invertible block matrices over Fq, establishing that PI and GPI codes are dually QMDS.The dual is computed over Fq itself, rather than only over its algebraic closure.Source: §3.2 · pp. 8, 10
  • The folded weight distribution of PI codes is given explicitly in terms of their parameters n, r, k, and d.The result applies the previously computed folded weight distribution for dually QMDS codes to PI codes.Source: §3.2 · p. 10
  • For PI codes, the folded weight distribution has W0 = 1 and Wj = 0 for 1 ≤ j ≤ d − 1.The supplied passage introduces the weights for j ∈ [d, n] but does not include their formula.Source: §3.2 · p. 10
  • Generalized PI codes retain the corresponding PI code’s weight distribution and are dually QMDS, while their duals are equivalent to PI codes of complementary dimension.These properties are invariant under linear isometry.Source: §3.2 · p. 10

3.3 Polynomial residue codes: Extending PI codes

  • A PR code has dimension min{k, deg(L)}, where L is the least common multiple of its defining polynomials.The defining polynomials are arbitrary nonzero polynomials of degree at most r.Source: §3.3 · p. 11
  • For a code C with k > 0, setting s = ceil(k/r), C is QMDS iff deg(L_J) ≥ k for every J ⊆ [n] of size s; if k > r and C is QMDS, then n ≤ q^r.Source: §3.3 · pp. 11–12
  • The dual minimum distance is 1 if k < r or some polynomial has degree below r, 2 if all have degree r but some pair share a factor, and floor(k/r) + 1 if they are pairwise coprime.In the pairwise-coprime case, k ≥ r; when k = rn, the dual is zero and its distance is n + 1 by convention.Source: §3.3 · p. 12
  • For 2r ≤ k ≤ nr, a PR code is dually QMDS exactly when its polynomials are pairwise coprime and all have degree r, making it a PI code.PR codes with k ∈ [0, r] or k ∈ [(n − 1)r, nr] can be dually QMDS at unrestricted lengths.Source: §3.3 · p. 13

4 Additive Reed–Solomon codes

This section studies the structure of additive Reed–Solomon codes, including their connection to polynomial ideal codes and properties for evaluation points in distinct conjugacy classes. It characterizes dimensions, metric isometries, duals, lengths, coordinate permutations, and QMDS properties for both restricted and arbitrary evaluation points.

4 Additive Reed–Solomon codes

  • An aRS code has dimension min(k, deg(L)), where L is the least common multiple of the evaluation points’ minimal polynomials over Fq.When k ≤ deg(L), its dimension is k; when k > deg(L), its dimension is deg(L).Source: §4 · p. 13

4.1 Linear Hamming and folded isometries

  • The linear isometries between folded-Hamming and Hamming metrics are exactly coordinate permutations combined with independent Fq-linear automorphisms on the extension-field coordinates.The section also defines additive generalized Reed–Solomon codes as codes equivalent to aRS codes.Source: §4.1 · pp. 14–15

4.2 The intersection between the aRS and PI families

  • aRS codes with pairwise nonconjugate evaluation points correspond to PI codes defined by distinct irreducible polynomials of degree r, and the converse also holds.The correspondence extends to generalized codes, so properties invariant under Fq-linear isometries are shared by the two families.Source: §4.2 · pp. 15–16
  • For pairwise distinct conjugacy classes of size r, an aRS code’s dual is an aGRS code with multipliers λ_iQ(α_i), and the aRS and aGRS codes are dually QMDS.The dual code consists of vectors (λ_1Q(α_1), …, λ_nQ(α_n)) for polynomials Q of degree less than nr − k.Source: §4.2 · p. 17
  • Using Corollary 41 and [12, Th. 4], the classical Hamming weight distribution of aRS codes (and thus aGRS codes) has W0 = 1 and Wj = 0 for j ∈ [1, d−1].Source: §4.2 · p. 17
  • The maximum length of an aRS code with pairwise distinct conjugacy classes of size r is N_q(r), and these codes asymptotically attain the maximum possible PI-code length.The maximum is obtained by choosing representatives from all conjugacy classes of size r.Source: §4.2 · p. 17

4.3 The permutation group of aRS codes

  • For 2 ≤ k ≤ nr − 2 and pairwise distinct conjugacy classes of size r, a coordinate permutation preserves an aRS code exactly when ασ(i) = aα_i + b for some a ∈ Fq* and b ∈ Fq.Source: §4.3 · p. 18
  • For 2 ≤ k ≤ nr − 2, any code permutation σ sends evaluation points by ασ(i) = aαi + b, where a ∈ Fq* and b ∈ Fq.The maps preserving A form AGLq(A), defined using these affine transformations on A.Source: §4.3 · p. 19

4.4 Additive Reed–Solomon codes with arbitrary evaluation points

  • For every J ⊆ [n], dim(C_J) = min{k, deg(L_J)} and dim((C⊥)_J) = |J|r − min{k, deg(L_J)}.These formulas give the punctured-code dimensions for arbitrary evaluation points and their trace duals.Source: §4.4 · p. 19
  • For k ≤ r, C is QMDS exactly when every d_i ≥ k; for k > r, this requires pairwise distinct P_i, at most one d_i < r, and any exceptional d_i ≥ k − (⌈k/r⌉ − 1)r.The criteria apply to arbitrary evaluation points, including repeated points and points of degree less than r.Source: §4.4 · p. 20
  • The dual distance is 1 if some d_i < r; if all d_i = r, it is min{2, ⌊k/r⌋ + 1} when some P_i repeat, and ⌊k/r⌋ + 1 when all P_i are distinct.The final case includes the zero-code convention.Source: §4.4 · p. 21
  • For r < k ≤ nr, C is dually QMDS exactly when the P_i are pairwise distinct and each has degree r.Source: §4.4 · p. 21
Loading 2610.21509v1…