PaperlayerView exact revision on arXiv

Source-linked AI summary

On the maximum length of cyclic MDS codes

Gaojun Luo, Xiwang Cao, Shitao Li, Yang Li

arXiv:2610.29810v1cs.ITmath.IT

TL;DR

The paper studies how long nontrivial simple-root cyclic MDS codes over Fq can be, a problem whose general maximum remains undetermined. It combines Fourier-support and arithmetic arguments with field descent to establish n≤q+1 for several classes of lengths, while leaving other cases open.

  • Problem

    The maximum length of a nontrivial simple-root cyclic MDS code over Fq remains undetermined in general.

    Source: §1 · p. 2

  • Method

    The proofs use Fourier-support constraints, dimension reduction, field descent, and arithmetic restrictions on multiplicative orders and valuations.

    Source: §2.1 · p. 4, §3.2 · p. 10, §4.1 · p. 16

  • Results

    For nontrivial simple-root cyclic MDS codes, n≤q+1 holds when gcd(n,q^2−1)>2, when k is even and gcd(n,q^2−1)>1, and for several additional length classes.

    Source: §5 · p. 16

  • Takeaways & Limitations

    The established n≤q+1 cases cover lengths with prime factors in {2,3,5,7} and further cases involving primes ℓ≥11 with (ℓ−1)/2 prime.

    Source: §5 · p. 16

    The arithmetic restrictions leave many cyclic lengths untreated, and the full MDS conjecture also covers codes without cyclic symmetry.

    Source: §5 · pp. 16–17

Abstract

from arXiv · show

We study the maximum length of nontrivial simple-root cyclic maximum distance separable (MDS) codes over ${\mathbb F}_q$. We prove $n\le q+1$ if $\gcd(n,q^2-1)>2$, or if the dimension is even and $\gcd(n,q^2-1)>1$. The bound also holds for all lengths whose prime factors lie in $\{2,3,5,7\}$. We obtain further cases involving primes $\ell\ge11$ with $(\ell-1)/2$ prime, under conditions on the exponents and the characteristic. The proofs combine Fourier supports, locality bounds and field descent with arithmetic restrictions on multiplicative orders and prime-adic valuations.

1. Introduction

The maximum length of nontrivial simple-root cyclic MDS codes remains undetermined in general. This paper gives conditions under which such codes satisfy n≤q+1, within the broader MDS length problem.

1. Introduction

  • The general linear MDS length problem is the search for the largest n for fixed k and q, equivalent to finding the maximum size of an arc in PG(k−1,q).The MDS conjecture predicts n≤q+1 except when q is even and k∈{3,q−1}, where it predicts n≤q+2.Source: §1 · p. 1
  • The paper addresses the unresolved general problem of maximum length for nontrivial simple-root cyclic MDS codes over Fq.The introduction identifies this prescribed-dimension question as undetermined in general.Source: §1 · p. 2
  • For nontrivial cyclic MDS codes, n≤q+1 when k is even and gcd(n,q^2−1)>1.This is one of the conditions in Theorem 1.1.Source: §1 · p. 2
  • For nontrivial cyclic MDS codes, n≤q+1 when 3|n, 4|n, or n has distinct odd prime divisors ℓ1, ℓ2 with gcd(ℓ1−1,ℓ2−1)=2.These are the two cases stated in Theorem 1.2.Source: §1 · p. 2

2. Preliminaries

The preliminaries establish the linear MDS bounds and cyclic-code tools used later: Fourier supports are balanced, and lengths above q + 1 impose arithmetic restrictions on multiplicative orders.

2.1. Linear MDS codes.

  • The preliminaries recall that every nontrivial MDS code over a prime field has length at most p + 1 and state a locality-based Singleton-like bound.Locality r means each coordinate can be recovered from r other coordinates.Source: §2.1 · p. 3, §2.3 · p. 6
  • If a nontrivial [n, k]q MDS code has n > q + 1, shortening yields n ≤ 2q − 4p + 6 for q = p^f with odd p and f ≥ 2.The proof shortens a code or its dual to dimension 2p − 2, then applies the bound n ≤ q + 1.Source: §2.1 · pp. 3–4

2.2. Cyclic codes.

  • Lifting a cyclic code to a splitting field identifies it with the span of vectors indexed by its Fourier support.This gives the Fourier-support representation used to analyze cyclic MDS codes.Source: §2.2 · pp. 4–5
  • A nontrivial cyclic MDS code has a Fourier support balanced modulo every divisor of its length.Each residue class contains either floor(k/t) or ceiling(k/t) support elements for each divisor t of n.Source: §2.2 · pp. 5–6
  • For a nontrivial cyclic MDS code with n > q + 1, writing q = p^f and t = ord_n(p) gives f | t and ord_n(q) = t/f.The result supplies necessary arithmetic conditions for lengths exceeding q + 1.Source: §2.2 · p. 6

3. Proof of Theorems 1.1 and 1.2

The proof bounds multipliers preserving a cyclic MDS code’s Fourier support using locality, then combines that bound with order restrictions. This yields n ≤ q + 1 under the stated gcd and length conditions.

3.1. Auxiliary lemmas.

  • For n satisfying uD = D and u ≠ 1, gcd(u−1, n) ≤ 2; the proof combines a subcode argument with a similar technique on the complement.The constructed subcode is D = (P − I)CE; its punctured code has locality r − 1, and the bound gives f − a ≤ 1 before the complement argument yields a ≤ 1.Source: §3.1 · pp. 7–8
  • For every divisor m | n with m ≥ 3, the multiplicative orders satisfy ord_n(q) = ord_m(q).Reduction of support-preserving multipliers modulo m is injective, giving the equality.Source: §3.1 · pp. 8–9

3.2. Proof of Theorem 1.1.

  • Because q² ≢ 1 (mod n) would imply f ≤ 2 by Lemma 3.1, contradicting the assumed f > 2, the proof concludes n | q² − 1 and hence n ≤ q + 1.Source: §3.2 · p. 10

3.3. Proof of Theorem 1.2.

  • For lengths divisible by 3 or 4, and for lengths divisible by two odd primes, the order restrictions imply ord_n(q) | 2 and hence n ≤ q + 1.The two-prime case uses that the gcd of the primes’ predecessor values is 2.Source: §3.3 · p. 10

4. Proof of Theorem 1.3

This section proves Theorem 1.3 by reducing length cases through auxiliary order, valuation, and Fourier-support arguments. It establishes bounds for several prime-power families and lengths with prime factors in {2, 3, 5, 7}, and in Case (2) restricts possible odd prime divisors under the assumption n>q+1 before ruling out the remaining cases.

4.1. Auxiliary lemmas.

  • Every nontrivial cyclic MDS code of length ε5^e or ε7^e, for ε ∈ {1, 2}, satisfies n ≤ q + 1.These auxiliary bounds rule out the remaining 5- and 7-power cases in the proof of Theorem 1.3.Source: §4.1 · pp. 11–12
  • Any counterexample of length εℓ^e, where ℓ = 2r + 1 and r, ℓ are odd primes, must be defined over a quadratic extension of the prime field.For n = 2ℓ², the lemmas nevertheless establish n ≤ q + 1.Source: §4.1 · pp. 11, 15
  • For a cyclic MDS code of length 2h and dimension h, 2h divides q² − 1.The proof obtains the stronger alternative 2h | q − 1 or 2h | q + 1.Source: §4.1 · pp. 13–14
  • The zero residue class of a cyclic MDS code’s Fourier support yields a shorter cyclic MDS code, with dimension ⌊k/h⌋ or ⌈k/h⌉.The shorter code has length N = n/h; if its dimension is zero, it is the zero code.Source: §4.1 · p. 14
  • For ℓ ≥ 11 with r = (ℓ − 1)/2 prime and e ≥ 3, n = εℓ^e satisfies n ≤ q + 1 when ℓ ≥ ⌈p/2⌉.A counterexample would force q = p² with p odd; the length bound then yields a contradiction under the stated condition.Source: §4.1 · p. 16

4.2. Proof of Theorem 1.3.

  • n = 2^α3^β5^γ7^δ ≤ q + 1: Theorem 1.2 reduces this case to lengths ε5^e or ε7^e, which the auxiliary lemmas exclude as counterexamples.The reduction uses β = 0, α ≤ 1, and the exclusion of simultaneous factors 5 and 7.Source: §4.1 · pp. 11–12, §4.2 · p. 16
  • Theorem 1.2 forces α=1, β=0, and exactly one odd prime in A={5, 7, ℓ1, . . . , ℓs} can divide n.Source: §4.2 · p. 16
  • If that prime is 5 or 7, then n=2·5^e or n=2·7^e, and Lemmas 4.3 and 4.5 yield n≤q+1.Source: §4.2 · p. 16
  • For ℓ_i cases, Lemmas 4.8–4.10 yield n≤q+1 when e_i=1 or 2, or when e_i≥3 and ℓ_i≥⌈p/2⌉, contradicting n>q+1.Source: §4.2 · p. 16

5. Conclusion

The paper proves n ≤ q+1 for several classes of nontrivial simple-root cyclic MDS codes, with additional cases for certain primes ℓ ≥ 11. Its arithmetic restrictions leave many cyclic lengths untreated, while the full MDS conjecture also covers codes without cyclic symmetry.

5. Conclusion

  • n ≤ q+1 when gcd(n, q^2−1) > 2, or when k is even and gcd(n, q^2−1) > 1.Source: §5 · p. 16
  • The same bound holds when 3 divides n or 4 divides n, and for lengths with distinct odd prime divisors ℓ1, ℓ2 satisfying gcd(ℓ1−1, ℓ2−1) = 2.Source: §5 · p. 16
  • The bound also holds for all lengths whose prime factors lie in {2, 3, 5, 7}.Source: §5 · p. 16
  • Further cases cover primes ℓ ≥ 11 for which (ℓ−1)/2 is prime, subject to conditions in Theorem 1.3.Source: §5 · p. 16
  • The proofs combine Fourier supports, locality bounds, multiplicative orders, field descent, and valuation estimates, but arithmetic restrictions leave many cyclic lengths untreated.Source: §5 · p. 16
  • The full MDS conjecture also concerns codes without cyclic symmetry, and the authors expect new techniques will be needed for remaining cases.Source: §5 · p. 17

Related papers

Loading 2610.29810v1…