Largest set of $k$-wise linearly independent vectors in $\mathbb F_q^n$?

Question

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 is that $k$-wise independent vectors give rise to $k$-wise independent sets of random variables, which is how I came across this problem).

Answer 1

For q = 2, this question was actually answer by Bose in his paper on $t$-error correcting group codes. This question is equivalent to the existence of $k$-fold Sidon sets in $F_2^n$. Here is a link to another Math overflow which essentially gives Bose's construction.:

Maximum size of $k$-Sidon set over $\mathbb{F}_2^n.$

To be clear, for $q = 2$, the answer is in the affirmative. There exist $k$-wise independent sets in $F_2^n$ of size $2^{n/m}$ where $m = \lfloor \frac{k}{2}\rfloor$.

Answer 2

$\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)?