PaperlayerView exact revision on arXiv

Source-linked AI summary

Chordal Construction of Column-Twisted Reed--Solomon Codes

Anuj Kumar Bhagat, Krishna Kaipa

arXiv:2610.31257v1cs.ITmath.IT

TL;DR

Most known MDS codes are equivalent to GRS codes, and constructing non-GRS MDS codes remains a challenging problem. This paper constructs CTRS codes using points on an imaginary secant and establishes conditions for MDS status. For odd q, it attains length (q + 5)/2 across a stated range of dimensions, while a geometric argument establishes non-GRS status over a broader range than the Schur-square method.

  • Problem

    Most known MDS codes are equivalent to GRS codes, while constructing and classifying non-GRS MDS codes remains challenging.

    Source: §1 · p. 2

  • Method

    The paper constructs codes from points on an RNC together with at most two points on an imaginary secant, deriving necessary and sufficient MDS conditions and explicit constructions.

    Source: §5 · p. 20

  • Results

    For odd q, non-GRS MDS codes of length (q + 5)/2 are constructed for every dimension 3 ≤ k ≤ (q −3)/2.

    Source: §5 · p. 20

  • Takeaways & Limitations

    A geometric argument establishes that every [n, k]q MDS CTRS code is non-GRS for 3 ≤ k ≤ n −4, beyond the range established by the Schur-square technique.

    Source: §5 · p. 20

    The article assumes k < q throughout.

    Source: §2 · p. 5

Abstract

from arXiv · show

A $[n,k]_q$ Generalized Reed--Solomon (GRS) code can be represented, up to monomial equivalence, by a projective system consisting of $n$ points on a degree $(k-1)$ rational normal curve (RNC) $C_{k-1}$ in PG$(k-1,q)$. We use the term \textit{Column-Twisted Reed--Solomon (CTRS)} codes broadly for $[n,k]_q$ codes whose projective system contains at least $(k+2)$ points on a $C_{k-1}$ of PG$(k-1,q)$. By a chord of $C_{k-1}$, we mean a line which is either a tangent, a real secant, or an imaginary secant of $C_{k-1}$. Roth and Lempel constructed non-GRS MDS $[n,k]_q$ codes by considering projective systems consisting of $(n-1)$ points on $C_{k-1}$ together with a point on a tangent line. More recently, Liu et al. obtained non-GRS $[n, k]_q$ MDS codes by considering projective systems consisting of $(n-2)$ points on $C_{k-1}$ together with a pair of points on a real secant. In the case when $q$ is odd, the length of these codes satisfies $k+4 \leq n \leq (q+3)/2$. In this article, we construct non-GRS $[n,k]_q$ MDS codes by considering projective systems consisting of $(n-2)$ points on $C_{k-1}$ together with a pair of Galois conjugate points on an imaginary secant. For odd $q$, these codes have lengths satisfying $k+4 \le n\le (q+5)/2$, thereby improving both the attainable lengths and dimension ranges of previous TRS and CTRS constructions. In particular, our code attains the length $(q+5)/2$ for every $3\le k\le (q-3)/2$. We use a geometric argument to establish the non-GRS property of CTRS codes for the range $3\le k \le n-4$, while the traditional method of comparison with the Schur square of GRS codes proves the non-GRS property only for the narrower range $3\le k \le n/2$. We also determine the structure of the dual of any CTRS code.

1. Introduction

MDS codes are optimal in minimum distance, but most known MDS codes are GRS, leaving non-GRS constructions and classification as challenging problems. This work introduces codes with points on an RNC and an imaginary secant, extending earlier constructions and establishing a broader range for proving non-GRS status.

1. Introduction

  • MDS codes attain the Singleton bound and have optimal error-detection and error-correction capabilities.The dual of an MDS code is also MDS.Source: §1 · p. 1
  • Non-GRS MDS codes are important to construct and classify because most known MDS codes are equivalent to GRS codes.Such codes can occur only for 3 ≤ k ≤ n −3.Source: §1 · p. 2
  • Earlier constructions include Roth–Lempel codes extended by one coordinate and CTRS codes extended by one or two coordinates, with odd-q lengths reaching (q +3)/2 for the latter.Beelen et al. constructed non-GRS MDS codes of length (q + 1)/2 using twisted GRS codes.Source: §1 · p. 2
  • This work places two Galois conjugate points on an imaginary secant and uses geometric arguments to establish non-GRS status for 3 ≤ k ≤ n −4.The Schur-square comparison establishes this property only for 3 ≤ k ≤ n/2; the work also determines that any code in this class has a (row)-twisted GRS dual.Source: §1 · pp. 2–3

2. Preliminaries

The preliminaries connect MDS codes to arcs and GRS codes to rational normal curves, then provide criteria for identifying extended codes and detecting non-GRS structure. They also establish the Schur-square dimension of GRS codes used in a non-GRS test.

2. Preliminaries

  • A chord of an RNC is a tangent, a real secant, or an imaginary secant.An imaginary secant joins the curve points indexed by conjugates α and α^q over Fq².Source: §2 · p. 4
  • A projective system represents the columns of a generator matrix, and GRS codes correspond to systems represented by points on an RNC.Monomial equivalence classes of non-degenerate codes correspond to projective systems up to projective equivalence.Source: §2 · p. 4
  • For k < q, every (k+2)-arc in PG(k−1, q) lies on a unique degree-(k−1) RNC.An n-arc has no k points on a hyperplane, and arcs on an RNC correspond to GRS codes.Source: §2 · p. 5
  • The extended code generated by G(x, u) is non-GRS exactly when u does not represent a point on the RNC.The criterion follows because k+2 points on the arc determine a unique RNC.Source: §2 · p. 5
  • The Schur square of a [n, k]q GRS code is a [n, min{2k −1, n}]q GRS code, supporting a non-GRS test when dim C⋆2 ≥ 2k and 3 ≤ k ≤ n/2.The test applies to an MDS code C under those dimension and range conditions.Source: §2 · p. 6

3. Column-Twisted Reed–Solomon Codes

The section studies CTRS codes formed by adding one or two projective points on a tangent, real secant, or imaginary secant of a rational normal curve. It broadens non-GRS results for real-secant codes and constructs imaginary-secant MDS codes with wider dimension ranges and, for odd q, longer lengths.

3.1. CTRS Codes via Points on Tangent Lines.

  • Tangent-line constructions add one or two points to curve points; listed one-point cases are equivalent to Roth–Lempel codes or their puncturings.For the stated tangent variants, the MDS conditions involve subset sums of evaluation points, and they do not exceed Roth–Lempel maximum lengths.Source: §3.1 · pp. 7–8

3.2. CTRS Codes via Points on Real Secants.

  • Real-secant codes with nonzero twist parameters are non-GRS for 3≤k≤n−2, broader than the previously established ranges.For odd q, non-GRS MDS codes are obtained for N≤(q+3)/2 and 3≤k≤N−4.Source: §3.2 · p. 9

3.3. CTRS Codes via Points on Imaginary Secants.

  • Geometric arguments establish that imaginary-secant codes are non-GRS for 3≤k≤N−4, extending beyond the Schur-square range 3≤k≤N/2.The construction uses projective systems with points on the rational normal curve and up to two points on an imaginary secant.Source: §3.2 · p. 9
  • The imaginary-secant section gives necessary and sufficient MDS conditions and explicit constructions of non-GRS MDS codes.The constructed projective systems use points on the curve together with one or two points on an imaginary secant.Source: §3.2 · p. 9, §3.3 · p. 11
  • For odd q, imaginary-secant constructions give non-GRS MDS codes for lengths up to (q+5)/2, with k+4≤N.This improves on Liu et al.’s (q+3)/2 length ceiling.Source: §3.3 · pp. 13–14

4. Dual of CTRS Codes

The section determines the dual of an arbitrary CTRS code and shows that it is a (row-)twisted GRS code. It gives explicit dual descriptions for the principal generator families and their special cases.

4. Dual of CTRS Codes

  • The dual of any CTRS code is a (row-)twisted GRS code.The section establishes this structure through explicit dual descriptions for the code families considered.Source: §4 · pp. 14, 15, 17
  • For codes generated by G1, the dual has an explicit generator using the original evaluation points and a twist polynomial fu.The construction obtains fu through Lagrange interpolation of the parity-check data.Source: §4 · pp. 15–16
  • For codes generated by G2, the dual uses two twist polynomials, fu and fv, alongside the evaluation-point rows.The description applies the G1 argument to both u and v.Source: §4 · p. 17
  • The corollaries give explicit row-twisted GRS duals for Roth–Lempel codes and other specified CTRS families.These include families with finite-field evaluation points and constructions involving α outside Fq.Source: §4 · pp. 17–18

5. Conclusion

The conclusion summarizes the paper’s MDS constructions, non-GRS results, and dual-code structure. It highlights the attainable length for odd q and the broader dimension range established geometrically.

5. Conclusion

  • The geometric argument establishes that every [n, k]q MDS CTRS code is non-GRS for 3 ≤ k ≤ n −4.This extends the dimension range beyond the Schur-square technique’s stated limitations.Source: §5 · p. 20
  • For odd q, the construction attains length (q + 5)/2 for every dimension 3 ≤ k ≤ (q −3)/2.Source: §5 · p. 20
  • The paper determines the dual of an arbitrary CTRS code and shows it is a (row-)twisted GRS code.Source: §5 · p. 20

Conflict of Interest.

Loading 2610.31257v1…