How many binary vectors of weight 3 can you have before their span contains one of weight 2?

376 Views Asked by At

In other words, I am looking for the smallest $k$ for which the following is always true:
Let $v_i \in \mathbb{F}_2^n$ for $i = 1\ldots k$ be distinct vectors of Hamming weight 3, that is, vectors with 3 non-zero entries. Then there exists some $u\in \mbox{span}(v_1,\ldots,v_k)$ which has Hamming weight 2.

I know $k \leq \binom{n}{2}$, as otherwise two $v_i$ overlap in two positions. Moreover, I can construct $\frac{n^3}{27}$ vectors without their span containing a vector of weight one (any 3-partite 3-uniform hypergraph). Can I hope for something better than what I already know for this 2 case?

1

There are 1 best solutions below

2
On BEST ANSWER

Actually you cannot get higher than $u_n=n(n-1)/6$. This is because every triple of positions cover ${3\choose 2}=3$ pairs of positions. If there were more than $u_n$ words of weight three, than some pair would be covered twice, and your argument kicks in.

This upper bound can also be achieved - at least for some values of $n$. For example when $n=2^m-1$ for some integer $m>1$. This is because the single error correcting Hamming code has covering radius one meaning that any bitvector $x$ is at Hamming distance $\le1$ from a codeword $w$. If $x$ is of weight two, then $w$ can only be of weight three, so every pair of bit positions is covered in the sense of the first paragraph, and hence that bound is attained.

It is easy to also calculate the number of words of weight three of that Hamming code directly. Their supports consist of the non-trivial points of 2-dimensional subspace $W$ of an $m$-dimensional vector space $V$ over $GF(2)$. The formula for the number of such subspaces has been derived on our site many times. For the sake of completeness here it is one more time. The first non-zero vector, $v_1\in W$, can be selected in $2^m-1$ ways. After that a second non-zero vector, $v_2\in W$, can be chosen in $2^m-2$ ways. The sum of the two chosen vectors is the third one $v_3=v_1+v_2$. By selecting any of $v_1,v_2,v_3$ first and then one of the remaining two as the second choice we end up with the same subspace $W$, so this process yields $W$ in exactly six different ways. Therefore the number of such subspaces $W$ is $$ \frac{(2^m-1)(2^m-2)}6=\frac{n(n-1)}6. $$

Another related concept is that of a Steiner system $S(2,3,n)$. Such a Steiner system consists of subsets of 3 elements of a given $n$ element set $V$ such that any subset of size two is contained in exactly one triple of the system. The number of triples is then necessarily $n(n-1)/6$. However, in general it is not clear whether the triples of a Steiner system come from words of weight three of a code with minimum Hamming distance three. This type of relations between sets of low weight words of a code and Steiner systems (or, more generally, combinatorial designs) has been studied extensively, most notably by Ed Assmus and Skip Mattson. Google Assmus-Mattson theorem for more information.