Source-linked AI summary
MDS codes containing a fixed subcode over finite field extensions
Yangcheng Li, Pingzhi Yuan
TL;DR
The paper asks when a prescribed code can be enlarged to an MDS code and how many completions exist over finite extensions. Using a full-weight correspondence, it gives a distance criterion for completion and relates extension-degree existence to a characteristic polynomial.
Problem
The paper asks when an arbitrary linear code can be extended to an MDS code of dimension one greater, and how many such completions exist over finite field extensions.
Source: §1 · p. 1Method
The paper uses the full-weight correspondence for the Plücker extension code to characterize MDS completions of a fixed subcode.
Source: §5 · p. 16Results
A finite-extension MDS completion exists exactly when d(U) ≥ n − k + 1, and existence over F_q^m is equivalent to χδGM(G)(q^m) > 0.
Source: §1 · p. 2Takeaways & Limitations
Completion counts can distinguish representations of the same column matroid, while identical counts over all finite extensions do not imply monomial equivalence.
Source: §5 · p. 16The results concern extending a fixed (k − 1)-dimensional subcode U to dimension k at fixed length.
Source: §1 · p. 2
Abstract
from arXiv · showhide
Let $2\le k\le n$ and let $U\le\mathbb{F}_q^n$ be a fixed $(k-1)$-dimensional linear code. We study the $[n,k]$ maximum distance separable (MDS) codes over finite extensions of $\mathbb{F}_q$ that contain the scalar extension of $U$. Our approach constructs an auxiliary linear code from \(U\). Its full-weight words characterize the desired MDS completions. We prove that \(U\) admits an \([n,k]\) MDS completion over some finite extension of \(\mathbb{F}_q\) if and only if \(d(U)\ge n-k+1\). When this condition holds, the number of these MDS codes over $\mathbb{F}_{q^m}$ is \[\#\left\{W\le\mathbb{F}_{q^m}^n:U\otimes_{\mathbb{F}_q}\mathbb{F}_{q^m}\subseteq W,\ \dim_{\mathbb{F}_{q^m}} W=k,\ W\text{ is MDS}\right\}=\frac{\chi_{\delta_GM(G)}(q^m)}{q^m-1},\] where $G$ is a generator matrix of $U$, $\delta_GM(G)$ is its represented derived matroid, and $\chi_{\delta_GM(G)}$ is its characteristic polynomial. In particular, the formula determines existence over each extension field and the least extension degree for which such an MDS code exists. Examples show that these counts may distinguish different representations of the same column matroid, while monomially inequivalent codes may have identical counts over every finite extension.
1 Introduction
The paper asks whether a prescribed subcode can be preserved when extending it to an MDS code, and how many such completions exist over finite extensions. It gives a full-weight-word correspondence and derives an exact existence criterion and completion counts.
1 Introduction
- The motivating question comes from whether cyclic shifts of a subspace cover the whole space, and the paper focuses on the one-step completion case.The invariant h_q(n) is the largest codimension of a subspace with that covering property.Source: §1 · p. 1
- The paper counts completions at fixed length while increasing dimension, addressing a different problem from extending an MDS code by adding a coordinate.The cited prior results concern existence or coordinate extension; this work determines exact counts over finite extensions.Source: §1 · pp. 1–2
- The seed is a fixed (k−1)-dimensional code, and the counted completions are actual subspaces rather than monomial-equivalence classes.The admissible extension degrees form a threshold interval m ≥ m0(U).Source: §1 · p. 2
- Full-weight words of the Plücker extension code, modulo nonzero scalars, correspond exactly to the desired MDS completions over each scalar extension.The code is constructed from the maximal minors of a generator matrix with an appended row.Source: §1 · p. 2
- A finite-extension MDS completion exists exactly when d(U) ≥ n−k+1, equivalently when U is MDS or almost MDS.The characteristic-polynomial formula also determines existence over each extension and the least extension degree.Source: §1 · p. 2
2 Preliminaries
The preliminaries establish the coding, geometric, matroidal, and metric language used to represent one-step MDS completions and count them. They connect candidate extensions to projective directions and hyperplane avoidance, while relating the resulting counts to covering radii.
2 Preliminaries
- The preliminaries fix notation and collect the tools used later in the proof.These tools span coding theory, matroids, arrangements, and coset metrics.Source: §2 · p. 2
2.1 Linear codes, MDS codes, and scalar extensions
- For an [n,s] code, the Singleton bound is d(C) ≤ n−s+1; MDS and almost MDS codes have Singleton defect zero and one, respectively.Minimum distance is unchanged under scalar extension because ranks of submatrices do not change.Source: §2.1 · pp. 2–3
2.2 One-step directions and Plücker coordinates
- One-step extensions correspond to projective directions in the quotient by the seed, and an extension is MDS exactly when every maximal minor is nonzero.For the example, there is no completion over F2 but there are two over F4.Source: §2.2 · p. 3
2.3 Matroids, circuits, and represented derived matroids
- The represented derived matroid uses circuit vectors of the seed's column matroid as columns, and different representations of the same abstract matroid can yield different derived matroids.Circuit vectors are minimal dependencies, unique up to nonzero scalar for each circuit.Source: §2.3 · p. 4
2.4 Hyperplane arrangements and characteristic polynomials
- For a loopless represented matroid, its characteristic polynomial evaluated at q^m counts vectors avoiding the associated hyperplanes.A central arrangement is a family of kernels of nonzero linear forms.Source: §2.4 · p. 4
2.5 Coset distances, covering radii, and syndromes
- Every coset of the scalar-extended seed has a representative of weight at most r=n−k+1, the redundancy bound used for coset distance.A parity-check matrix represents quotient vectors as syndrome vectors, and one-step directions become points in the syndrome projective space.Source: §2.5 · p. 5
3 Main results
The section characterizes MDS completions by reducing them to full-weight words in an auxiliary Plücker extension code, and counts completions via the characteristic polynomial of a derived matroid. It studies the first extension degree admitting a completion, gives bounds and monomial-equivalence invariance, and relates the completion condition to coset distances, deep holes, and attaining the redundancy bound on covering radius.
3.1 Statement of the main theorem
- U has an [n, k] MDS completion over some finite extension exactly when d(U) ≥ n − k + 1; over F_(q^m), existence is equivalent to χ_δGM(G)(q^m) > 0.If d(U) < n − k + 1, no scalar extension admits a completion.Source: §3.1 · p. 5, §3.5 · p. 9
3.2 The Plücker extension code and the full-support criterion
- MDS completions of U_K correspond bijectively to one-dimensional subspaces spanned by full-weight words in the Plücker extension code P(U)_K.Its coordinates are the maximal minors of an appended generator row, so a full-weight word means every maximal minor is nonzero.Source: §3.2 · p. 6
3.3 The distance obstruction
- The distance condition d(U) ≥ n − k + 1 holds exactly when U is MDS or almost MDS, and ensures that no coordinate form of P(U) vanishes identically.If the condition fails, an identically zero form prevents completion over every scalar extension; a full-weight word may still require extension.Source: §3.3 · pp. 7–8
3.4 Identification of the derived matroid
- After zero forms are removed and proportional forms identified, the arrangement’s normal matroid is δ_GM(G): its distinct normal lines correspond exactly to circuits of the column matroid.The arrangement has rank n − k + 1.Source: §3.4 · p. 8
3.5 Exact counting of MDS completions
- For each extension F_(q^m), the number of MDS completions is χ_δGM(G)(q^m)/(q^m − 1), with scalar multiples counted as one completion.The auxiliary full-weight-word count yields the formula, and division by q^m − 1 identifies nonzero scalar multiples.Source: §3.5 · p. 9
3.6 First extension degree, bounds, and invariance
- For any nondegenerate linear code C, a full-weight word appears over F_(q^m) for some m exactly when C is nondegenerate, and the least such degree is s₀(C), the minimum number of codeword supports covering all coordinates.The supplied argument also gives s₀(C) ≤ dim(C).Source: §3.6 · p. 10
- U_qm admits a one-step MDS completion exactly when m≥m0(U), equivalently when χδGM(G)(q^m)>0.The first such degree is m0(U)=s0(P(U)).Source: §3.6 · p. 10
- m0(U) is the minimum number of P(U) words whose supports cover every coordinate; completion exists whenever q^m≥s(U), and m0(U)≤r.For every nondegenerate [N,s]_q code, a full-weight word exists over every extension of degree at least s.Source: §3.6 · pp. 10, 12
- U admits an MDS completion over some finite extension exactly when d(U)≥r, and nonzero determinant-coordinate forms suffice after a finite extension.Here r=n−k+1.Source: §3.6 · p. 11
- Completion counts over every finite extension and the first completion degree are invariant under monomial equivalence of U.Source: §3.6 · p. 12
3.7 Coset distances, syndromes, and deep holes
- When d(U)≥r, a one-step MDS completion exists exactly when a coset at distance r exists, equivalently when ρ(UQ)=r and χδGM(G)(Q)>0.The coset distance r is the largest allowed by the redundancy bound.Source: §3.7 · pp. 12–14
- In syndrome coordinates, the obstruction arrangement is formed by spans of (r−1)-subsets of parity-check columns; for Q≥4, there are (Q−1)(Q−2) deep-hole cosets.For Q≥4, NU(Q)=Q−2.Source: §3.7 · pp. 13–14
4 Examples
The examples show both what completion counts distinguish and what they leave unresolved: counts can differ for seeds with the same column matroid, yet agree for monomially inequivalent seeds. The examples count actual completions in fixed coordinate positions.
4 Examples
- The examples illustrate both the information carried by the full-weight count and its limitations; completions are counted in fixed coordinate positions, not up to monomial equivalence.The count is the number of full-weight words in the associated Plücker extension code divided by Q − 1.Source: §4 · p. 14
4.1 Different counts for the same column matroid
- Completion counts distinguish the two seeds with the same column matroid and Hamming weight enumerator: over F7, N_U2(7) = 2 while N_U4(7) = 0, and U4 has completions over F49.Their first completion degrees are m0(U2) = 1 and m0(U4) = 2.Source: §4.1 · p. 15
4.2 Identical counts for inequivalent seeds
- Monomially inequivalent 7 seeds C2 and C3 have identical completion counts over every finite scalar extension.Thus these counts do not determine a seed up to monomial equivalence.Source: §4.2 · p. 15
5 Conclusion
The conclusion characterizes when a fixed code can be completed to an MDS code over a finite extension and gives a formula for counting completions. It also relates the first completion degree to a support-cover size and notes a metric interpretation of the characteristic polynomial.
5 Conclusion
- A fixed (k − 1)-dimensional code U admits an [n, k] MDS completion over some finite extension exactly when d(U) ≥ n − k + 1.When this condition holds, the characteristic-polynomial formula counts completions over F_q^m.Source: §5 · p. 16
- The first extension degree with a full-weight word equals the minimum size of a support cover in P(U) and has explicit upper bounds.Existence at a given degree is equivalent to positivity of the formula's numerator.Source: §5 · p. 16
- The characteristic polynomial counts cosets at the redundancy distance and, when covering radius equals that distance, determines the number of deep-hole words.The examples show that completion counts can distinguish information beyond ordinary code parameters and the column matroid, but equal counts across all finite extensions do not imply monomial equivalence.Source: §5 · p. 16
AI Use Declaration
The authors report using generative AI tools during manuscript preparation and revision.
AI Use Declaration
- Generative AI tools were used for literature searches, comparisons with related work, and finding examples; the authors retain responsibility for the mathematical claims, proofs, and final presentation.The declaration concerns preparation and revision of the manuscript.Source: AI Use Declaration · p. 16