Source-linked AI summary
On sets of vectors of a finite vector space in which every subset of basis size is a basis II
Simeon Ball, Jan De Beule
TL;DR
The MDS conjecture asks how large a set in F_q^k can be if every k-element subset is a basis, with implications for linear MDS-code length. The article develops tangent functions and Segre-product tools to prove the conjectured bound in specified parameter ranges. It proves |S|≤q+1 for non-prime q when k≤2p−2, and for k≤p over all q.
Problem
The MDS conjecture asks whether such a set has size at most q+1, except for the stated even-q cases, and the conjecture bounds linear MDS-code length.
Source: §1 · pp. 1–2Method
The article formulates tangent functions using linear maps whose kernels are hyperplanes through Y containing no other vector of S, alongside a Segre product for subsequences.
Source: §2 · p. 3Results
|S|≤q+1 for non-prime q when k≤2p−2, and for all q when k≤p.
Source: §3 · p. 6, §5 · p. 10Takeaways & Limitations
The conjectured size bound is established for the stated non-prime range k≤2p−2 and for k≤p over all q.
Source: §3 · p. 6, §5 · p. 10The proof assumes t≥1, which the authors state is no restriction for the target bound when k≥4.
Source: §2 · p. 2
Abstract
from arXiv · showhide
This article contains a proof of the MDS conjecture for $k \leq 2p-2$. That is, that if $S$ is a set of vectors of ${\mathbb F}_q^k$ in which every subset of $S$ of size $k$ is a basis, where $q=p^h$, $p$ is prime and $q$ is not and $k \leq 2p-2$, then $|S| \leq q+1$. It also contains a short proof of the same fact for $k\leq p$, for all $q$.
1 Introduction
The MDS conjecture bounds the size of a vector set in which every k-element subset is a basis, with stated exceptions for even q. The article proves the conjecture for non-prime q when k≤2p−2 and also treats prime q.
1 Introduction
- For k≥q, Bush showed |S|≤k+1, attained exactly by a set equivalent to a basis together with the sum of its basis vectors.Source: §1 · p. 1
- The conjecture gives an upper bound of q+1 for such a set, except when q is even and k=3 or k=q−1, where the bound is q+2.Source: §1 · p. 1
- For non-prime q=p^h, the article proves the MDS conjecture for k≤2p−2 and also proves it for prime q, where it was first proved in.Source: §1 · p. 1
- Earlier bounds cited include k<√pq/4+c1p for odd non-square q and k≤√q/2+c2 for q=p^(2h), p≥5.Source: §1 · p. 2
- The conjecture implies that a linear MDS code has length at most q+1, with the same even-q exceptions allowing q+2.Source: §1 · p. 2
- For uniform matroids of rank r with at least r+2 elements, the conjecture characterizes representability over F_q by the corresponding q+1 bound, with the stated even-q exceptions.Source: §1 · p. 2
2 The tangent function and the Segre product
This section introduces tangent functions using linear maps associated with hyperplanes through a chosen subset of S. It also defines the Segre product for subsequences and develops identities by examining how that product changes under swaps.
2 The tangent function and the Segre product
- The argument assumes t≥1, which the authors say is no restriction for the target |S|≤q+1 bound when k≥4.Source: §2 · p. 2
- For each α in φ_Y, its kernel is one of the t hyperplanes containing Y and no other vector of S.The maps in φ_Y are linearly independent, and the tangent function at Y is defined up to a scalar factor.Source: §2 · p. 3
- The Segre product is defined for equal-length subsequences A and B of S with a disjoint base D of size k−n−1.The empty-subsequence product is set to 1.Source: §2 · p. 3
- Interchanging adjacent elements a_j and a_(j+1) in A changes only the Segre-product terms indexed by i=j and i=j+1.Source: §2 · pp. 3–4
3 The main lemma
The section proves |S| ≤ q + 1 when k ≤ p and establishes an inductive lemma used in that result. The lemma’s proof combines subset summation with determinant and Segre-product identities.
3 The main lemma
- σ(B, L) records (t + 1) times the transpositions needed to move B to the end of the ordered set L.Its recursive relation helps track signs as the induction rearranges the subsequences.Source: §3 · pp. 4, 6
- Lemma 3.1 applies to disjoint subsequences A, L, D, and Ω when n ≤ r ≤ n + p − 1 and r ≤ t + 2.The lemma’s stated setting is q = p^h.Source: §3 · p. 5
- The inductive proof fixes an element of L, applies the inductive step, and sums over subsets of Ω before using the induction hypothesis.The argument invokes Lemma 2.2 and rearranges L, tracking the resulting sign with σ.Source: §3 · pp. 5–6
- If k ≤ p, then |S| ≤ q + 1.The proof argues by contradiction from |S| = q + 2.Source: §3 · p. 6
4 The case |S| = q + 2 and q is non-prime.
For |S| = q + 2 with q non-prime, Lemma 4.1 supplies an inductive identity for disjoint subsequences. Its induction compares sums after adjoining elements to L and A and then rearranging determinant and Segre-product terms.
4 The case |S| = q + 2 and q is non-prime.
- Lemma 4.1 states an identity for disjoint subsequences when |S| = q + 2 and n ≥ k − p.Its sets A, L, Ω, X, and Y have the sizes specified in the lemma.Source: §4 · p. 7
- The proof proceeds by induction on m, with the m = 0 case supplied by Lemma 3.1.That application uses r = t + 2 = k − 1 and gives the bound n ≥ k − p.Source: §4 · p. 7
- For the induction step, the proof applies the identity to {y} ∪ L and A ∪ {x}, then splits a sum according to whether B contains y.It subsequently uses the lemmas and the Segre-product definition to rearrange terms.Source: §4 · pp. 7–8
- The comparison applies the induction to a second arrangement and equates the resulting second sums after switching x and y in the determinants.The sign adjustment is (−1)^(t+1), and the argument also uses the stated σ relation for adjoining an element.Source: §4 · pp. 8–9
5 The main theorem
The section proves |S| ≤ q + 1 for non-prime q when k ≤ 2p − 2. It also gives a corollary for q − 2p + 4 ≤ k ≤ q, using duality to reduce to a smaller dimension.
5 The main theorem
- The proof’s induction uses Laplace’s formula for determinants and sums over indexed subsets to establish the required identity.For r = n, all terms vanish except the term with τ = ∅, and the resulting equation yields a contradiction.Source: §5 · p. 10
- If q is non-prime and k ≤ 2p − 2, then |S| ≤ q + 1.The proof reduces to k ≥ p + 1 and assumes |S| = q + 2 to obtain a contradiction using Lemma 4.1.Source: §5 · p. 10
- For non-prime q, when q − 2p + 4 ≤ k ≤ q, Corollary 5.3 gives the bound |S| ≤ q + 1 for S under those conditions.Source: §5 · p. 11
6 Appendix
The appendix gives a short proof of [1, Lemma 4.1], identified as a main tool for the bound and classification in when k ≤ p. It also states Lemma 6.1 and proves it by induction.
6 Appendix
- The appendix gives a short proof of [1, Lemma 4.1], a main tool for proving |S| ≤ q + 1 and classifying |S| = q + 1 for k ≤ p in.The proof uses the Segre product and lemmas from Section 2.Source: §6 · p. 11
- Lemma 6.1 applies to disjoint L, D, and Ω when 1 ≤ r ≤ t + 2 and r ≤ p − 1.The proof is by induction on r; its base case divides the equation from Lemma 2.2 by T_D(ℓ0).Source: §6 · p. 11
- In the inductive step, the proof applies Lemma 2.2 to sets formed from Ω, L, ∆, and D, then sums over subsets ∆ of Ω.It rearranges L and tracks the sign using σ; the second-term ordering is permitted because the sign changes match across the products.Source: §6 · pp. 11–12