Given a list of $2^n$ nonzero vectors in $GF(2^n)$, do some $2^{n-1}$ of them sum to 0?

Question

Let $G=(\mathbb{Z/2Z})^n$ written additively, $n>1$. (you can think of it as $\mathbb{F}_{2^n}$ but I didn't find that useful... yet)

Let $v_i$ be nonzero elements of $G$ for $i \in \{1 \dots 2^n \}$ so that $\sum_{i=1}^{2^n} v_i=0$. Is it possible to find a subset $J \subset \{1 \dots 2^n \}$, $|J|=2^{n-1}$ so that $$\sum_{j \in J} v_j=0?$$ Note that the $v_i$s are not assumed to be distinct.

Most theorems I've seen of this kind are rendered trivial by the characteristic $2$, although I might have missed something. My first idea would be to apply Alon's Combinatorial Nullstellensatz but I can't find a suitable polynomial.

I don't know if this can be solved at all (I suspect this statement is true), but it has a feel of being somewhat well-studied already. Any ideas? (I'm also considering asking this on MathOverflow, do you think it's appropriate?)

UPDATE 1, based on some comments:

1. Computer checking by joriki shows the claim for $n=3$ and suggests it for $n=4,5$.
2. For small cases, pairing also works, see Jyrki's comment below.
3. The role of the condition $\sum_i v_i=0$ is unclear; I think in the case $\sum_i v_i \neq 0$ it's actually easier to find a suitable $J$ because then $J$ and its complement don't have the same sums.

Thank you all for your help.

Answer 1

Here is a proof for $n \geq 4$, inspired by Jyrki's. The proof doesn't really use the fact that the vectors sum to zero.

Greedily extract from $V = v_1,\ldots,v_{2^n}$ linear dependencies of minimal possible size. This partitions $V$ into $V = S_2 \cup \cdots \cup S_{n+1}$, where $S_k$ is a disjoint union of linear dependencies of size $k$. If the vectors don't sum to zero, there might be some "leftover" set of size at most $n$.

Consider $R = V \setminus (S_2 \cup S_3 \cup S_4)$. If $x,y \in R$ are distinct then $x + y \notin R$; note that $x,y,x+y \neq 0$. Furthermore, if $x,y,z \in R$ are distinct then $x + y \neq x + z$ (since $y \neq z$), and if $x,y,z,w \in R$ are distinct then $x + y \neq z + w$ (since otherwise $x + y + z + w = 0$). Therefore $$ |R| + \binom{|R|}{2} \leq 2^n-1. $$ When $n \geq 4$, this shows that $$ |S_2 \cup S_3 \cup S_4| \geq 2^{n-1} + 3. $$ Since all vectors in $V$ are non-zero, $|S_2| \geq 2$. Moreover, if $|S_2| = 2$ then $V$ contains all non-zero vectors, and so it is easy to find a set of size $2^{n-1}$ summing to zero. So assume $|S_2| \geq 4$.

If $|S_2| + |S_4| \geq 2^{n-1}$ then we are done (since $|S_2| \geq 2$). Otherwise, there is a subset $T_3 \subset S_3$ summing to zero such that $2^{n-1} \leq |S_2| + |S_4| + |T_3| \leq 2^{n-1} + 2$. If the sum is $2^{n-1}$ or $2^{n-1} + 2$ we're done (again using $|S_2| \geq 2$). If the sum is $2^{n-1}+1$, remove two pairs from $S_2$. The total number of elements now is $2^{n-1}-3$. Since $|S_2 \cup S_3 \cup S_4| \geq 2^{n-1} + 3$, there must be one more triple in $S_3$ that we can add in to get exactly $2^{n-1}$ elements.

Answer 2

Originally my answer claimed the following: I can show that we can find a subset of size either $2^{n-1}$ or $2^{n-1}+1$ summing up to zero. IOW, not a full solution, but something that may be fixable.

[Edit: Yuval already gave a complete answer. I just fix this.]

First remove as many duplicate vectors $v_i=v_j, i\neq j$ in pairs as possible, and set them aside for future use. Let's say that we removed $k$ pairs, and have a set $S$ of $2^n-2k$ distinct non-zero vectors remaining. I first claim that without loss of generality we can assume $2k > n$. This is so, because otherwise we are missing $<n$ nonzero vectors of $F_2^n$ from the set $S$. Let $U\subset F_2^n$ be a subspace of dimension $n-1$ containing the span of those missing vectors. Then the complement of $U$ is contained in $S$, has $2^{n-1}$ vectors, and because (by the comments) we have $n-1\ge2$, they sum up to zero.

Note that if $k\ge 2^{n-2}$, then we are done, because we can build the required subset from the duplicate pairs. Thus we may assume that $|S|> 2^{n-1}$. We further observe that the vectors in the set $S$ also sum up to zero, because removal of duplicate pairs did not change this property (this isn't actually needed in what follows, as also observed by Yuval, and suspected by joriki).

Ok. Let's start building bigger and bigger subsets $U_j,j=0,1,\ldots,$ of $S$ that sum up to zero. The key is the trivial observation that any set of $n+1$ vectors from $S$ contains a minimal linearly dependent subset (of size between $3$ and $n+1$ inclusive). This subset then has zero sum (wonders of char 2!). They key is the following

Lemma. Among any $n+2$ non-zero vectors of $F_2^n$ there is always a subset of an even number of vectors such that their sum is the zero vector.

Proof. If the vectors are $u_1,u_2,\ldots,u_{n+2}$, then we get a linear mapping $\phi$ from $F_2^{n+2}$ to $F_2^n$ by mapping the tuple $(b_1,b_2,\ldots,b_{n+2})$ to the linear combination $\sum_i b_iu_i$. By rank-nullity, $\ker\phi$ has dimension at least two. Therefore there are at least 3 distinct non-zero combinations of $(b_1,b_2,\ldots,b_{n+2})$ giving rise to a zero sum vector. If the first two of them have an odd weight, then their sum has an even weight. Q.E.D.

So let $U_0=\emptyset$, and then, given $U_j$, add a minimal linearly dependent set of an even number of vectors to it to form the set $U_{j+1}$. Rinse. Repeat. Because we assumed that $S$ contains more than half the elements of $F_2^n$, at some point the set $U_j$ has $\le2^{n-1}$ elements and the set $U_{j+1}$ has $>2^{n-1}$ elements. Because $|U_{j+1}\setminus U_j|\le n+2$, we see that $$ 2^{n-1}-n-1\le |U_j|\le 2^{n-1}. $$ Because $|U_j|$ is an even number, the claim then follows by adding a few of those duplicate pairs that we set aside in the beginning to the set $U_j$. Here in the last step we need to exercise a modicum of care. If $n$ is even, then parity tells us that we really have $|U_j|\ge 2^{n-1}-n$, and we can fill it with pairs of duplicates. If $n$ is odd, then we can use the inequality $|U_{j+1}\setminus U_j|\le n+1$ instead, because this set also has an even number of vectors. Again, the "border case" won't cause us any problems.