A linear-in-q range of dimensions for the MDS conjecture over F_q in odd characteristic

Abstract

Let q be a power of an odd prime p. We prove the MDS conjecture over F_q in dimension k whenever 2 ≤ k ≤ B(p,q) or q + 2 − B(p,q) ≤ k ≤ q, where B(p,q) = ⌊((p − 2)q + 6p − 10)/(2p − 3)⌋. For fixed p, this gives a range of dimensions linear in q, in contrast with the square-root scale of the previously known general unconditional ranges over proper extension fields, and proves the conjecture in an asymptotic proportion 1 − 1/(2p − 3) of all dimensions.