The EMS Publishing House is now EMS Press and has its new home at ems.press.

Please find all EMS Press journals and articles on the new platform.

Journal of the European Mathematical Society


Full-Text PDF (191 KB) | Metadata | Table of Contents | JEMS summary
Volume 14, Issue 3, 2012, pp. 733–748
DOI: 10.4171/JEMS/316

Published online: 2012-03-07

On sets of vectors of a finite vector space in which every subset of basis size is a basis

Simeon Ball[1]

(1) Universitat Politécnica de Catalunya, Barcelona, Spain

It is shown that the maximum size of a set ${ S}$ of vectors of a $k$-dimensional vector space over ${\mathbb F}_q$, with the property that every subset of size $k$ is a basis, is at most $q+1$, if $k \leq p$, and at most $q+k-p$, if $q \geq k \geq p+1 \geq 4$, where $q=p^h$ and $p$ is prime. Moreover, for $k\leq p$, the sets $S$ of maximum size are classified, generalising Beniamino Segre's “arc is a conic'' theorem.

These results have various implications. One such implication is that a $k\times (p+2)$ matrix, with $k \leq p$ and entries from ${\mathbb F}_p$, has $k$ columns which are linearly dependent. Another is that the uniform matroid of rank $r$ that has a base set of size $n \geq r+2$ is representable over ${\mathbb F}_p$ if and only if $n \leq p+1$. It also implies that the main conjecture for maximum distance separable codes is true for prime fields; that there are no maximum distance separable linear codes over ${\mathbb F}_p$, of dimension at most $p$, longer than the longest Reed-Solomon codes. The classification implies that the longest maximum distance separable linear codes, whose dimension is bounded above by the characteristic of the field, are Reed–Solomon codes.

Keywords: Arcs, Maximum Distance Separable Codes (MDS codes), uniform matroids

Ball Simeon: On sets of vectors of a finite vector space in which every subset of basis size is a basis. J. Eur. Math. Soc. 14 (2012), 733-748. doi: 10.4171/JEMS/316