What is known about the largest set of $k$-wise linearly independent vectors in $\mathbb F\_q^n$? I am especially interested when $q=2$, and in the regime where $k$ is fixed an $n\to\infty$. Here are some partial results:


* The largest pairwise independent set has $\frac{q^n-1}{q-1}$ vectors.
* The largest size of a $3$-wise independent set is at most $$\frac{q^{n-1}-1}{q-1}+1.$$ To see why, if $S$ is $3$-wise independent, and ${\bf v}\_0\in S$, then the set of vectors of the form $a{\bf v}\_0+b{\bf v}$ with $a\in \mathbb F\_q, b\in \mathbb F\_q^{\times}, {\bf v}\in S\setminus\{v\_0\}$ are pairwise distinct. This is achieved when $q=2$ by the set of vectors with an odd number of ones.   
 The next simplest case is $q=3$, where I am stuck. It seems to be that finding a large independent set is related to finding a large cap-set in $\mathbb F\_3^{n-1}$, which is a hard open problem. Specifically, by multiplying all the vectors in $S$ with an appropriate scalar, you can assume their leftmost nonzero coordinate is $1$, and then if $u,v,w$ all have their first coordinate equaling $1$, then $\{u,v,w\}$ being linearly independent is equivalent $\{u',v',w'\}$ being non-colinear, where $u'$ is obtained by deleting the initial $1$ from $u$, and similarly for $v',w'$.
* Any $4$-wise independent set $S$ must satisfy
$$
(q-1)^2\binom{|S|}2\le q^n,
$$
which follows by realizing that the vectors of the form $a{\bf v}\_1+b{\bf v}\_2$, with $a,b\in \mathbb F\_q^\times$ and ${\bf v}\_1,{\bf v}\_2\in S$, are pairwise distinct (for this to work, each pair $\{{\bf v}\_1,{\bf v}\_2\}$ must appear at most once). This gives $|S|\lesssim \sqrt{2}q^{n/2}/(q-1)$. I am not sure if this the true growth rate, even for $q=2$.
* It seems straightforward to generalize these upper bound arguments to show that the size of a $k$-wise independent set is $\mathcal O(q^{n/\lfloor k/2\rfloor})$.


To summarize, I am wondering if the upper bounds I gave are tight, and if any other general constructions are known. (The reason for the [pr.probability](/questions/tagged/pr.probability "show questions tagged 'pr.probability'") is that $k$-wise independent vectors give rise to $k$-wise independent sets of random variables, which is how I came across this problem).



Largest set of $k$-wise linearly independent vectors in $\mathbb F_q^n$?
$\newcommand{\F}{{\mathbb F}}$
Let's focus on the case $q=2$ which you are primarily interested in. Suppose that $v\_1,\dotsc,v\_m\in\F\_2^n$, and let $V$ be the matrix over $\F\_2$ of size $n\times m$ with $v\_1,\dotsc,v\_m$ (written in the standard basis) as its columns. It is readily seen that for $v\_1,\dotsc,v\_m$ to be $k$-wise linearly independent, it is necessary and sufficient that the kernel of $V$ did not contain any vector of weight $k$ or less. You are thus asking how large can the length $m$ of a linear code be given that the minimum distance of the code is at least $k+1$, and that the code has co-dimension $n$. This is essentially equivalent to the central problem of coding theory: what is the largest possible dimension of a linear code of given length and minimum distance ($m$ and $k+1$, respectively, in our case)?


