PaperlayerView exact revision on arXiv

Source-linked AI summary

Two variants of Twisted Reed-Solomon Codes

Haojie Gu, Huiyue Lei, Jun Zhang

arXiv:2609.16188v1cs.ITmath.IT

TL;DR

Constructing MDS codes not equivalent to generalized Reed-Solomon codes is challenging, with the relevant parameter range restricted to 3 ≤ k ≤ n − 3. The paper studies column-twisted and row-column twisted Reed-Solomon codes and derives necessary and sufficient MDS conditions using subset products and elementary symmetric functions. Column-twisted Schur squares have dimension 2k + 1; row-column twisted Schur squares have dimension 2k + 2 for ℓ ∈ {0, k − 1} and 2k + 3 for 1 ≤ ℓ ≤ k − 2; both distinguish from GRS codes, while row-column codes also distinguish from known twisted families.

  • Problem

    Constructing MDS codes not equivalent to generalized Reed-Solomon codes is challenging, with the relevant parameter range restricted to 3 ≤ k ≤ n − 3.

    Source: §1 · p. 2

  • Method

    The paper studies column-twisted and row-column twisted Reed-Solomon codes and derives necessary and sufficient MDS conditions using subset products and elementary symmetric functions.

    Source: §1 · p. 2, §6 · p. 21

  • Results

    Column-twisted Schur squares have dimension 2k + 1; row-column twisted Schur squares have dimension 2k + 2 for ℓ ∈ {0, k − 1} and 2k + 3 for 1 ≤ ℓ ≤ k − 2; both distinguish from GRS codes, while row-column codes also distinguish from known twisted families.

    Source: §4 · p. 13, §6 · p. 21

  • Takeaways & Limitations

    The paper provides explicit parity-check matrices and dual descriptions, and identifies self-orthogonality, hulls, and quantum-code applications as future research directions.

    Source: §6 · p. 21

    More general (L, P)-twist forms and investigations of self-orthogonality, self-duality, hulls, and quantum-code applications remain future research directions.

    Source: §6 · p. 21

Abstract

from arXiv · show

Generalized Reed-Solomon codes and twisted generalized Reed-Solomon codes provide important sources of maximum distance separable codes. In this paper, we study two variants obtained by introducing column twists and simultaneous row-column twists into Reed-Solomon-type evaluation codes. For the column-twisted family, we provide necessary and sufficient conditions for the code to be MDS in terms of explicit subset product conditions. Under the stated parameter assumptions, the Schur square has dimension 2k+1, which leads to MDS codes that are not equivalent to Reed-Solomon codes. For the row-column twisted family, we establish necessary and sufficient conditions for the MDS property in terms of elementary symmetric functions. The larger Schur-square dimension provides a further distinction from both Reed-Solomon codes and known twisted families, thereby yielding new non-RS MDS codes. Finally, explicit parity-check matrices and dual descriptions are obtained for both code families. These results provide a foundation for subsequent studies of self-orthogonality, hull dimensions, and applications to quantum-code constructions.

1 Introduction

Constructing MDS codes inequivalent to generalized Reed-Solomon codes is a challenging problem. This paper studies two twisted variants and develops MDS conditions, non-RS constructions, Schur-square analyses, and dual descriptions.

Motivation

  • Non-RS [n, k]-MDS codes are challenging to construct, and the paper focuses on the range 3 ≤ k ≤ n/2.Any [n, k]-MDS code is equivalent to a Reed-Solomon code when k < 3 or n − k < 3; duality permits focusing on k ≤ n/2.Source: §1 · p. 2

Prior work

  • Beelen et al. introduced Twisted Reed-Solomon codes, and later work developed column-twisted and row-column twisted variants.The paper situates its work after earlier TRS constructions [3] [4] and the CTRS and RCTRS constructions [5] [21].Source: §1 · p. 2

Contributions

  • The paper gives necessary and sufficient MDS conditions for two flexible variants and explicit field-extension and subgroup-based parameter choices that satisfy them.The contribution is framed in comparison with CTRS and RCTRS constructions [5] [21].Source: §1 · p. 2
  • The column-twisted codes have Schur-square dimension 2k + 1, while the row-column family has dimension 2k + 2 or 2k + 3 in the considered ranges.These dimensions distinguish the constructed codes from GRS codes and, in the corresponding ranges, from previously known twisted families.Source: §1 · p. 2
  • The paper derives explicit parity-check matrices and dual descriptions for both families, for possible use in later studies of code properties and quantum-code applications.Suggested directions include self-orthogonality, self-duality, and hulls.Source: §1 · p. 2

2 Preliminaries

The preliminaries set notation and describe twisted evaluation-code variants, then introduce Schur products as a tool for distinguishing MDS codes from generalized Reed-Solomon codes.

Notation

  • The paper fixes conventions for positive and non-negative integers and for indexed subsets of an evaluation set.For a subset U and index set I, it defines U_I and the associated Vandermonde product V(U_I).Source: §2 · p. 3

Twisted codes

  • A twisted generalized Reed-Solomon code evaluates polynomials from a specified function space, and the all-one multiplier case is called a twisted Reed-Solomon code.The paper specializes to L = {0} and P = {ℓ} for its TRS codes.Source: §2 · pp. 3–4
  • The column-twisted and row-column twisted variants replace the final two evaluations with values adjusted by λ₁ and λ₂.CTRS uses polynomials of degree below k; RCTRS uses the specified twisted polynomial space S_{k,ℓ,η}.Source: §2 · p. 4

Schur products

  • The Schur product multiplies codeword coordinates, and the product of a code with itself is its Schur square.For k ≤ n/2, a GRS code has Schur-square dimension 2k − 1; a different dimension for an MDS code signals it is not equivalent to GRS.Source: §2 · pp. 4–5

3 Column twisted Reed-Solomon codes CTRS(A, B, λ)

This section develops column-twisted Reed-Solomon codes, giving an MDS criterion and explicit non-RS MDS constructions. The constructed codes have Schur-square dimension 2k+1, distinguishing them from Reed-Solomon codes and, in the cited construction, RCTRS codes.

3 Column twisted Reed-Solomon codes CTRS(A, B, λ)

  • Theorem 3.1 gives necessary and sufficient conditions for CTRS codes to be MDS, including a determinant test expressed using ΦJ.ΦJ(x, y) = (x − y) times the product of (x − αj)(y − αj) over j in J.Source: §3 · pp. 5–6
  • An example over F17 satisfies the subset test and gives a CTRS MDS code with parameters [5] [7].The subset conditions were checked using Magma.Source: §3 · p. 6
  • Theorem 3.3 constructs MDS CTRS codes under finite-field chain assumptions; pairwise-distinct b values give Schur-square dimension 2k+1.The stated construction also requires its evaluation points and b values to be disjoint.Source: §3 · p. 6
  • A Schur-square dimension of 2k+1 establishes non-RS MDS status and distinguishes the constructed CTRS codes from RCTRS codes in [5].The dimension is established under the stated construction conditions.Source: §3 · pp. 6, 8
  • A field-extension example gives a [12, 4, 9] CTRS code over F13^4 with Schur-square dimension 9, rather than 7.The example therefore has non-RS MDS status.Source: §3 · p. 8
  • Proper multiplicative subgroups yield longer-length non-RS MDS CTRS codes than the construction in Theorem 3.3(ii).The subgroup construction generalizes the use of F∗q0 in Theorem 3.3(ii).Source: §3 · pp. 8–9

4 Row-column twisted Reed-Solomon codes RCTRSℓ,η(A, B, λ)

This section studies row-column twisted Reed–Solomon codes, giving necessary and sufficient conditions for MDS and constructing non-RS MDS codes. It distinguishes the constructed codes using their Schur-square dimensions and presents a subgroup-based construction.

Theorem 4.2

  • Theorem 4.2 characterizes when RCTRS codes are MDS through subset nonvanishing conditions, including a condition involving the elementary symmetric sum S_{k-ℓ}(α_L).One required condition is 1 + (-1)^{k-ℓ-1}ηS_{k-ℓ}(α_L) ≠ 0; the theorem also specifies conditions using Ψ(1) and Ψ(2).Source: §4 · pp. 10–11

Example 4.3

  • A toy construction with n = 11 and k = 7 over F47 is verified as an MDS code with parameters [7] [5].The authors report checking the theorem’s conditions and verifying the generator matrix using Magma.Source: §4 · p. 12

Theorem 4.4

  • Under Theorem 4.4’s assumptions, the constructed RCTRS code is MDS and non-RS, with Schur-square dimension 2k + 2 for ℓ ∈ {0, k − 1} and 2k + 3 for 1 ≤ ℓ ≤ k − 2.The construction uses a subfield chain, evaluation points and twist parameters subject to the theorem’s stated conditions.Source: §4 · pp. 12, 13, 15

Remark 4.5

  • The Schur-square dimensions 2k + 2 or 2k + 3 distinguish these constructed RCTRS codes from the section’s CTRS codes and corresponding previously known families [5] [21].The CTRS construction in Section 3 has Schur-square dimension 2k + 1.Source: §4 · p. 15

Theorem 4.6

  • Theorem 4.6 gives another non-RS MDS RCTRS construction using a multiplicative subgroup H of order n − 1.The preceding passage says the subgroup approach can yield longer lengths than the construction in Theorem 4.4(ii).Source: §4 · p. 15

4 Row-column twisted Reed-Solomon codes RCTRSℓ,η(A, B, λ)

  • For 7 ≤ k < n/2 − 1, RCTRSℓ,η(A, B, λ) is MDS and its Schur-square dimension is at least 2k+2, making it a non-RS MDS code.The MDS property follows from Theorem 4.2; the non-RS conclusion follows from Proposition 2.6.Source: §4 · p. 17

5 The dual codes of CTRS(A, B, λ) and RCTRSℓ,η(A, B, λ)

The section derives parity-check matrices and dual descriptions for the row-column and column-twisted codes. The CTRS matrix follows by setting η = 0 in the RCTRS result.

5 The dual codes of CTRS(A, B, λ) and RCTRSℓ,η(A, B, λ)

  • A parity-check matrix is given for RCTRS codes.The theorem states the matrix under its specified parameter assumptions.Source: §5 · p. 18
  • The matrix derivation uses Lagrange interpolation to obtain coefficients satisfying a system of equations.Source: §5 · pp. 18–19
  • Setting η = 0 in the RCTRS result yields a parity-check matrix for CTRS codes.Source: §5 · pp. 18, 20

6 Conclusion

The conclusion recaps necessary and sufficient MDS conditions and explicit constructions for both twisted code families. Their Schur-square dimensions distinguish the resulting codes from GRS codes, while broader twists and further code properties remain future directions.

6 Conclusion

  • The paper derives necessary and sufficient MDS conditions for both families using subset-product and elementary-symmetric-function conditions.Source: §6 · p. 21
  • The column-twisted family has Schur-square dimension 2k + 1, while the row-column family’s larger dimension distinguishes it from GRS codes and known twisted families.Source: §6 · p. 21
  • The paper derives explicit parity-check matrices and dual descriptions for both families.Source: §6 · p. 21
  • More general (L, P)-twist forms and self-orthogonality, self-duality, hulls, and quantum-code applications are proposed for future study.Source: §6 · p. 21
Loading 2609.16188v1…