We formulate an Algebraic-Coding Equivalence to the Maximum Distance Separable Conjecture. Specifically, we present novel proofs of the following equivalent statements. Let $(q,k)$ be a fixed pair of integers satisfying $q$ is a prime power and $2leq k leq q$. We denote by $mathcal{P}_q$ the vector space of functions from a finite field $mathbb{F}_q$ to itself, which can be represented as the space $mathcal{P}_q := mathbb{F}_q[x]/(x^q-x)$ of polynomial functions. We denote by $mathcal{O}_n subset mathcal{P}_q$ the set of polynomials that are either the zero polynomial, or have at most $n$ distinct roots in $mathbb{F}_q$. Given two subspaces $Y,Z$ of $mathcal{P}_q$, we denote by $langle Y,Z rangle$ their span. We prove that the following are equivalent. [A] Suppose that either: 1. $q$ is odd 2. $q$ is even and $k otin {3, q-1}$. Then there do not exist distinct subspaces $Y$ and $Z$ of $mathcal{P}_q$ such that: 3. $dim(langle Y, Z rangle) = k$ 4. $dim(Y) = dim(Z) = k-1$. 5. $langle Y, Z rangle subset mathcal{O}_{k-1}$ 6. $Y, Z subset mathcal{O}_{k-2}$ 7. $Ycap Z subset mathcal{O}_{k-3}$. [B] Suppose $q$ is odd, or, if $q$ is even, $k otin {3, q-1}$. There is no integer $s$ with $q geq s > k$ such that the Reed-Solomon code $mathcal{R}$ over $mathbb{F}_q$ of dimension $s$ can have $s-k+2$ columns $mathcal{B} = {b_1,ldots,b_{s-k+2}}$ added to it, such that: 8. Any $s times s$ submatrix of $mathcal{R} cup mathcal{B}$ containing the first $s-k$ columns of $mathcal{B}$ is independent. 9. $mathcal{B} cup {[0,0,ldots,0,1]}$ is independent. [C] The MDS conjecture is true for the given $(q,k)$.
Download