The Maximum Number of Bases in a Family of Vectors

Abstract

The proportion of $d$-element subsets of ${\mathbb{F}}_2^d$ that are bases is asymptotic to ${\prod }_{j=1}^{\infty }(1-2^{-j})\approx 0.29$ as $d\to \infty$. It is natural to ask whether there exists a (large) subset $\mathcal{F}$ of ${\mathbb{F}}_2^d$ such that the proportion of $d$-element subsets of $\mathcal{F}$ that are bases is (asymptotically) greater than this number. As well as being a natural question in its own right, this would imply better lower bounds on the Turán densities of certain hypercubes and `daisy' hypergraphs. We give a negative answer to the above question. More generally, we obtain an asymptotically sharp upper bound on the proportion of linearly independent $r$-element subsets of a (large) family of vectors in ${\mathbb{F}}_2^d$, for $r\le d$. This bound follows from an exact result concerning the probability of obtaining a linearly independent sequence when we randomly sample $r$ elements with replacement from our family of vectors: we show that this probability, for any family of vectors, is at most what it is when the family is the whole space ${\mathbb{F}}_2^d\setminus \{0\}$. Our results also go through when ${\mathbb{F}}_2$ is replaced by ${\mathbb{F}}_q$ for any prime power $q$.

It has been brought to our attention that the main result of this preprint had already been proven in [N. Alon, Erasure list-decodable codes and Turan hypercube problems, Finite Fields and Their Applications 100 (2024), 102513]