PaperlayerView exact revision on arXiv

Source-linked AI summary

The permutation and automorphism groups of univariate multiplicity codes

Eduardo Camps Moreno, Hiram H. López, Umberto Martínez-Peñas, Rodrigo San-José

arXiv:2610.31858v1cs.ITmath.IT

TL;DR

The paper addresses the previously unstudied permutation and automorphism groups of multiplicity codes. It characterizes these groups across evaluation sets, multiplicities, dimensions, and metrics, finding projective structure for NRT automorphisms in the main range and distinct permutation groups for multiplicity one and higher multiplicities.

  • Problem

    The permutation and automorphism groups of multiplicity codes had not been investigated, and automorphisms could be considered under either the NRT or folded Hamming metric.

    Source: §1 · p. 2

  • Method

    The paper explicitly characterizes univariate multiplicity-code permutations and linear isometries for arbitrary finite-field evaluation subsets, multiplicities, and dimensions, and gives an algebraic characterization for the folded Hamming metric.

    Source: §1 · p. 2

  • Results

    In the main dimension range, NRT automorphisms are determined by evaluation-set-stabilizing projectivities up to a global nonzero scalar; permutations are affine for multiplicity one and translations for multiplicity at least two.

    Source: §1 · p. 2, §4 · p. 11, §7 · p. 17

  • Takeaways & Limitations

    The NRT automorphism structure extends the classical Reed–Solomon pattern, while multiplicity at least two restricts the permutation group to evaluation-set-preserving translations.

    Source: §1 · p. 2, §7 · p. 17

    When k−1 and q−1 share a common factor, the automorphism group may not be isomorphic to GL(A).

    Source: §6 · p. 17

Abstract

from arXiv · show

We give explicit characterizations of the permutations and linear isometries that leave (univariate) multiplicity codes invariant. We consider any evaluation subset of the finite field, any multiplicity and dimension, and the automorphisms are with respect to the Niederreiter-Rosenblom-Tsfasman (NRT) metric. For multiplicity one, we recover the permutation and automorphism groups of classical Reed--Solomon codes in the classical Hamming metric. In the main dimension range, automorphisms are uniquely determined by a projectivity that permutes the evaluation subset, up to multiplication by a nonzero scalar. For multiplicity one, permutations are given by affine maps that permute the evaluation subset. In contrast, for multiplicity at least two, permutations are only given by translations that permute the evaluation subset. Finally, we give an algebraic characterization of automorphisms of multiplicity codes for the folded Hamming metric.

1 Introduction

The introduction positions multiplicity codes as a derivative-based extension of Reed–Solomon codes and identifies their permutation and automorphism groups as unstudied. It previews characterizations for the NRT and folded Hamming metrics, including a sharp difference between the permutation groups at multiplicities one and at least two.

1 Introduction

  • For multiplicity one, multiplicity-code metrics reduce to the classical Hamming metric, recovering the Reed–Solomon setting.The introduction also notes that univariate multiplicity codes attain the optimal rate-versus-list-decodability tradeoff for the folded Hamming metric and the Singleton bound in both metrics.Source: §1 · pp. 1–2
  • The automorphism-group question had not been investigated for multiplicity codes, and its isometry setting matters: NRT isometries use upper-triangular blocks, while folded-Hamming isometries allow arbitrary invertible blocks.The paper describes the folded-Hamming automorphism group as generally much larger than the NRT group.Source: §1 · p. 2
  • For univariate multiplicity codes over arbitrary finite-field subsets, the paper characterizes NRT automorphisms and permutations and gives an algebraic characterization for folded-Hamming automorphisms.In the main dimension range, NRT automorphisms are tied to projectivities stabilizing the evaluation set, up to a global nonzero scalar.Source: §1 · p. 2
  • For multiplicity one, permutations are affine maps stabilizing the evaluation set; for multiplicity at least two, they are only translations stabilizing it.The permutation groups therefore differ between the Reed–Solomon case and pure multiplicity codes.Source: §1 · p. 2

2 Preliminaries

The preliminaries define multiplicity codes using Hasse-derivative evaluations, set out the NRT metric and its isometries, and recall projective-line facts used in the characterizations.

2.1 Multiplicity codes

  • Hasse derivatives are defined by the coefficients in the expansion of f(x+y), and the zeroth and first derivatives are f and the usual derivative.Vanishing of the first m Hasse derivatives at a point is equivalent to a root of multiplicity at least m, including in positive characteristic.Source: §2.1 · p. 3
  • A multiplicity code evaluates the r-jet—values of a polynomial and its first r−1 Hasse derivatives—at each point of the nonempty set A; its dimension is k.The multiplicity-one case is classical Reed–Solomon.Source: §2.1 · p. 3

2.2 The NRT metric

  • The NRT weight of a block is determined by its first nonzero component, and for multiplicity one the NRT metric is the classical Hamming metric.The NRT metric also has a Singleton bound, which multiplicity codes attain [17, Th. 6].Source: §2.2 · pp. 3–4
  • NRT linear isometries consist of a coordinate permutation and invertible upper-triangular matrices acting on the blocks; automorphisms are such isometries preserving the code.The paper distinguishes this from folded-Hamming isometries, which allow arbitrary invertible block matrices.Source: §2.2 · pp. 4–5

2.3 The projective line

  • Projectivities are bijections of the projective line, and matrices differing by a nonzero scalar induce the same projectivity.A projectivity fixing infinity acts as an affine map on the finite field.Source: §2.3 · p. 6
  • A projectivity is uniquely determined by its images of three distinct projective-line points and preserves cross ratios.Source: §2.3 · p. 6
  • For three fixed distinct finite points, the cross ratio with a fourth point is injective in that fourth point.Source: §2.3 · p. 6

3 Projectivities yield NRT automorphisms

The section shows that a projectivity stabilizing the evaluation set induces an NRT automorphism. Its polynomial-side action is an invertible transformation, and the resulting block action respects the NRT structure.

3 Projectivities yield NRT automorphisms

  • The induced polynomial-space map is a vector-space automorphism, and composing maps associated with matrices M and N corresponds to the map associated with MN.Source: §3 · p. 7
  • The block matrices are upper triangular, and in the affine case their form is independent of the evaluation point and k.The paper says this independence does not hold in general.Source: §3 · pp. 7–8
  • If a projectivity stabilizes A, its induced map gives an NRT automorphism of the multiplicity code, including the stated cases k≥r and k<r.The construction excludes evaluation points that are poles of the projectivity.Source: §3 · pp. 7, 9
  • In most dimensions, these projectivity-induced maps account for all NRT automorphisms apart from multiplication by nonzero scalars.Source: §3 · p. 9

4 The permutation is a projectivity

The section proves that an NRT automorphism’s coordinate permutation must come from a unique projectivity in the stated dimension range. The proof connects the permutation’s action on multiplicity-root subspaces to cross-ratio preservation.

4 The permutation is a projectivity

  • Upper-triangular block actions preserve the relevant vanishing conditions, linking the coordinate permutation to multiplicity-root subspaces.The proof uses these subspaces to derive constraints on the permutation.Source: §4 · pp. 9–10
  • The induced action on selected subspaces yields cross-ratio preservation, the key condition used to identify the permutation as a projectivity.The proof relates four evaluation points through a projectivity between two-dimensional spaces.Source: §4 · pp. 10–11
  • For n≥3 and 2≤k≤rn−r, the permutation of an NRT automorphism is induced by a unique projectivity; when r=1, the theorem also requires k≤n−2.Source: §4 · p. 11
  • For n≥4, fixing the images of three evaluation points determines a projectivity, and cross-ratio injectivity then identifies its action on the remaining points with the permutation.For n=3, any permutation of A extends to a projectivity.Source: §4 · p. 11

5 The (k −1)-degree graph and the scalar λ

For an NRT automorphism whose permutation is the identity, the associated polynomial map is shown to be multiplication by one nonzero scalar. The proof links eigenvalues across a connected graph of bounded-degree exponent vectors, then uses polynomial generators to extend the scalar action to the whole space.

5 The (k −1)-degree graph and the scalar λ

  • An NRT automorphism with identity permutation acts on Vk as multiplication by a single nonzero scalar.The associated map L satisfies L(f) = λf for all f ∈ Vk.Source: §5 · pp. 12, 14
  • The (k−1)-degree graph is connected under the stated dimension assumptions, linking every exponent vector of total degree k−1.Its vertices have total degree k−1, and edges connect vectors sharing a predecessor with at least three components below r.Source: §5 · p. 12
  • Eigenvalues assigned to adjacent graph vertices coincide because three eigenvectors in an invariant plane must share an eigenvalue.Connectivity then makes the eigenvalue the same for every vertex of the graph.Source: §5 · pp. 13–14
  • The polynomials Pe with degree k−1 generate Vk, so their common eigenvalue forces L(f) = λf throughout Vk.The proof establishes generation using induction on degree.Source: §5 · p. 14

6 The automorphism group

In the central dimension range, an NRT automorphism is characterized by a projectivity preserving the evaluation set, together with a nonzero scalar, and the projectivity is unique. The section also describes the associated group structure and the whole-field specialization.

6 The automorphism group

  • The paper treats low and high dimensional ranges in Appendix A and the four boundary cases in Appendix B.The four cases listed are k = 1, k = rn−1, n = 1, and n = 2.Source: §6 · p. 15
  • For n ≥ 3 and the stated central dimension range, an NRT automorphism is determined by a nonzero scalar and a unique projectivity preserving A.The central range is r ≤ k ≤ nr−r, with 2 ≤ k ≤ n−2 also required when r = 1.Source: §6 · p. 15
  • The group in the central range is isomorphic to (Fq* × GL(A))/Hk.The quotient accounts for the non-uniqueness of the representing matrix for a projectivity.Source: §6 · p. 16
  • When k−1 and q−1 share a common factor, the automorphism group need not be isomorphic to GL(A).Thus the quotient description does not always simplify to GL(A).Source: §6 · pp. 16–17
  • When A = Fq, the preserving projectivity is affine, and the automorphism characterization specializes to parameters λ, α ∈ Fq* and β ∈ Fq.For r = 1, this recovers the classical Reed–Solomon automorphism characterization.Source: §6 · pp. 15, 17

7 The permutation group

For evaluation sets of at least three points and the stated dimension range, the permutation group changes sharply with multiplicity. Multiplicity one allows affine maps preserving the set, whereas multiplicity at least two allows only translations preserving it.

7 The permutation group

  • The stated permutation characterization covers 2 ≤ k ≤ rn−2, while the proof treats the central range directly and refers to analogous arguments for other dimensions.For r = 1, the corresponding range is 2 ≤ k ≤ n−2.Source: §7 · pp. 17, 19
  • For n=|A|≥3 and 2≤k≤nr−2, a permutation π:A→A satisfies Pπ∈PAut(MA(r,k)) iff π(a)=αa+β for r=1 (α∈Fq*, β∈Fq), and π(a)=a+β for r≥2 (β∈Fq).Source: §7 · pp. 17–18
  • Translations preserve multiplicity-code membership because Hasse derivatives commute with translations.The argument applies to f(x + β) and its derivatives at points of A.Source: §7 · p. 18
  • For multiplicity at least two, the projectivity associated with a permutation must reduce to a translation preserving A.The proof compares diagonal entries of the induced map to force the projectivity's lower-left parameter to vanish.Source: §7 · p. 18

8 The folded Hamming metric

For multiplicity at least two in the central dimension range, folded-Hamming automorphisms admit an algebraic characterization through the family of polynomial subspaces associated with evaluation points. This automorphism group includes the NRT automorphisms and can be larger.

8 The folded Hamming metric

  • Every NRT automorphism is also a folded-Hamming automorphism, but the folded-Hamming metric admits additional automorphisms.The characterization in this section is for r ≥ 2 and the central dimension range.Source: §8 · pp. 19–20
  • Folded-Hamming automorphisms correspond to linear maps L that permute the family of subspaces {Ka : a ∈ A}.For k > r, these subspaces are distinct, so the criterion is that L stabilize their set.Source: §8 · p. 20
  • When k = r, every Ka is {0}, so the subspace-family condition does not distinguish evaluation-point labels.For k > r, the subspaces are nonzero and distinct.Source: §8 · pp. 20–21
  • For A = F3 and r = k = 2, the identity permutation paired with any L ∈ GL(V2) gives a folded-Hamming automorphism, including one that is not an NRT automorphism.The example's block matrices are neither upper nor lower triangular.Source: §8 · pp. 21–22

Disclosure on AI usage

The authors report that AI was used to fill proof gaps for the general NRT automorphism group, but not to write the article.

Disclosure on AI usage

  • ChatGPT-5.6 Sol helped fill proof gaps for the general NRT automorphism group; the authors say AI was not used to write the article.The authors take responsibility for the correctness of the results.Source: Disclosure on AI usage · p. 22

A The low and high dimensional cases

The low- and high-dimensional ranges have more automorphism freedom than the central range, so their maps are not characterized solely by a projectivity and scalar. In the high range, a projectivity stabilizing the evaluation set and a global scalar occur alongside additional upper-triangular matrix freedom.

Low and high ranges

Low range

  • In the low-dimensional range, arbitrary upper-triangular matrices can act on the last r−k coordinates, which are zero in every codeword.The paper states that any map of this form is also an automorphism.Source: A The low and high dimensional cases · p. 24

High range

B The cases k = 1, k = rn −1, n = 1 and n = 2

The appendix characterizes automorphisms in boundary cases, including dimension one, codimension one, one evaluation point, and two evaluation points. These cases allow arbitrary block permutations and, in some settings, additional local matrix freedom.

Dimension one

Codimension one

  • For codimension one, the automorphisms are obtained from the dimension-one case by complementary-dimension duality.The resulting description includes an arbitrary block permutation and arbitrary upper-triangular matrices of size r−1.Source: B The cases k = 1, k = rn −1, n = 1… · pp. 27–28

One point

Two points

  • The two-point formulas are made explicit only for 1 ≤ k ≤ r; the case r < k ≤ 2r is left to the reader.Source: B The cases k = 1, k = rn −1, n = 1… · p. 28
  • For two evaluation points, either block permutation is allowed, and the induced operator scales each basis polynomial or reverses their order with independent nonzero scalars.When k < r, arbitrary invertible upper-triangular matrices may act on the last r−k coordinates.Source: B The cases k = 1, k = rn −1, n = 1… · p. 28
Loading 2610.31858v1…