Linearly independent subsets

Created at 2023-08-13

The binary words $001$, $010$, $100$ and $111$ have an interesting property: Whenever we choose three of them, the are linearly independent in the $\mathbb{F}_2$-vector space $\mathbb{F}_2^3$ of binary words of length $n$.

I'd like to turn this observation into a more general question: How large can a set $S$ of binary words in $\mathbb{F}_2^n$ be such that any subset with at most $k$ elements is linearly independent? (We will call such a set linearly $k$-independent.)

This problem was proposed a few years ago by a fellow student and I made progress when I applied the techniques from the book Making Up Your Own Mind.

Linearly 2-independent sets

This is easy. Let $S \coloneqq \mathbb{F}_2^n \setminus\{0\}$. This is a $2$-independent set, and it is clearly the largest one!

Linearly 3-independent sets

For $n = 3$, a simple argument suffices to see that a linearly $3$-independent set $S$ cannot have more than four elements. Assume that $S$ contains the three pairwise distinct elements $u, v, w$. If $x \in S$ is another distinct element, then $x$ can uniquely be written as linear combination $\lambda_1 u + \lambda_2 v + \lambda_3 w$ with coefficients $\lambda_i \in \mathbb{F}_2$. Because $u, v, x$ are linearly independent, the coefficient $\lambda_3$ must not be zero. A similar observation holds for $\lambda_1$ and $\lambda_2$. Therefore, $\lambda_1 = \lambda_2 = \lambda_3 = 1$ and $x = u + v + w$. This shows that $S$ cannot contain more elements than $u, v, w, x$.

How about larger $n$? The words in $\mathbb{F}_2^n$ that begin with a $1$ form a linearly $3$-independent set. Indeed, the sum of three such words again begins with a $1$ -- and is therefore nonzero. The linearly $3$-independent set we just found contains $2^{n-1}$ elements, exactly half of all words of length $n$. There is a deeper reason why this works: The words that begin with a $0$ form a subgroup of $\mathbb{F}_2^n$ of index two. Whenever we have a subgroup $G$ of index two, its complement forms a linearly $3$-independent set. Another subgroup I could have used consists of words with an even number of $1$'s.

So we found linearly $3$-independent sets with $2^{n-1}$ elements. Can we find even larger sets? As it turns out, no: Let $S$ be any linearly $3$-independent set and $w \in S$. Then $w + S$ is disjoint to $S$. Because both sets are contained in $\mathbb{F}_2^n$, we obtain $2\left|S\right| \le 2^n$. In other words, $\left|S\right| \le 2^{n-1}$.

A surprising connection

It is not clear how to generalize this argument to $n > 3$, so let us reframe the problem a bit. If we write all $\ell$ vectors in a linearly $k$-independent $S$ as columns into a matrix $A \in \mathbb{F}_2^{n\times \ell}$, then $\ker A \subseteq \mathbb{F}_2^\ell$ is a vector space and all of its nonzero elements have at least $k + 1$ non-zero components. Setting $m \coloneqq \dim\ker A$ and choosing an isomorphism $\mathbb{F}_2^m \cong \ker A$, we obtain a linear block code (see Lineare Blockcodierung) with block length $\ell$, message length $m \ge l - n$, overhead (block length minus message length) at most $n$ and minimum Hamming distance at least $k+1$.

On the other hand, if we are given a linear block code of block length $\ell$, overhead at most $n$ and minimum Hamming distance $k+1$, we can construct a linearly $k$-independent set $S \subseteq \mathbb{F}_2^n$: The space $V \subseteq \mathbb{F}_2^\ell$ of code words has dimension $\ell - n$. If we choose any (rank-$n$) matrix $A \subseteq \mathbb{F}_2^{n\times\ell}$ with $\ker A = V$, then the $\ell$ columns of $A$ form a set $S$ as desired.

There are some immediate implications. Hamming codes give rise to the linearly $2$-independent set $\mathbb{F}_2^n\setminus\{0\}$ from above. SECDED codes, i.e. Hamming codes with an additional parity bit, are linear codes with block length $2^{n-1}$, overhead $n$ and minimum Hamming distance $4$. This confirms our earlier result, this time however as a corollary of an established fact in computer science. Conversely, Richard Hamming might have discovered Hamming codes (which efficiently realize a minimum Hamming distance of $3$) quite naturally by constructing them from the maximal $2$-linearly independent set $S$ from further above (and derive without further calculation that its block size is $\left|\mathbb{F}_2^n\setminus\{0\}\right| = 2^n - 1$ and that it has $n$ bits of overhead).

Linearly 4-independent sets

How about linearly 4-independent sets? There are so-called BCH codes with block length at least $2^{n/2}$, overhead $n$ and minimal Hamming distance $5$. Therefore, there are linearly $4$-independent sets with at least $2^{n/2}$ elements in $\mathbb{F}_2^{n}$. (I quickly derived these numbers from the introduction of this paper by Chen, but I did not do a deep dive into this topic). These codes require a decent amount algebra to derive them, and I find it fascinating that the theory behind these codes can help to find linearly $4$-independent sets.

Can we do better? Probably a bit -- the paper I cite above itself improves on BCH codes, so there seems to be a bit of room for improvement. However, the order of magnitude is as good as it gets. We use an argument similar to the one we used to prove optimality of our linearly $3$-independent sets.

Let $S$ be any linearly $4$-independent set with $\ell$ elements. Then there are $\sum_{i=1}^2\begin{pmatrix}\ell \\ i\end{pmatrix} = 1 + \ell + \frac{\ell(\ell-1)}{2}$ ways to sum up at most two elements of $S$. Because $S$ is linearly $4$-independent, these sums are pairwise distinct elements of $\mathbb{F}_2^n$, and it follows that $\frac{1}{2}\ell^2 + \frac{1}{2}\ell + 1 \le 2^n$. In particular, $\ell \le 2^{(n+1)/2}$, and this bound is quite close to the size of the set we constructed with BCH codes.

(The binomial coefficient formula above is conspicuously similar to the so-called Hamming bound, which produces a similar bound for block codes with minimum Hamming distance $5$.)