7
$\begingroup$

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.

  • 0
    Do you mean $\sum_{i=1}^{2^n} v_i = 0$?2012-02-20
  • 2
    Assuming that's the case, it doesn't work for $n=1$.2012-02-20
  • 0
    Robert Israel: Thanks, that first one was a typo. And yes, I should have noted $n>1$. (I'm interested in Abelian groups where $\sum_{g \in G} g=0$, so $n=1$ is pathological in this respect.)2012-02-20
  • 1
    It doesn't work for $n=2$, either; if you make the $v_i$ all distinct, there's no pair that has an even number of $1$s in both components.2012-02-20
  • 1
    @joriki: I don't follow; if $n=2$, then there are only $4$ elements of $G$, only $3$ nonzero ones. If you have *any* function $f\colon\{1,2,3,4\}\to G-\{0\}$, then $f$ must take the same value for two distinct $i$, $i_1\lt i_2$. Then $J=\{i_1,i_2\}$ has the desired property. It doesn't even matter whether $\sum_{i=1}^4 f(i) = 0$ or not.2012-02-20
  • 0
    @joriki: Note that since it is specified that the $v_i$ are nonzero, you cannot make all $v_i$ pairwise distinct; there *must* be at least one repeat for every $n\gt 1$.2012-02-20
  • 0
    @Arturo: Sorry, I missed the nonzero part.2012-02-20
  • 0
    The case $n=3$ is also relatively easy. If there are at least two repeated pairs, we are done. If there is only a single repeated pair, then after removing that pair, we have six distinct vectors remaining. But this case is impossible! There would be only one non-zero vector missing (out of seven). Because the sum of all seven non-zero vectors is zero, the sum of those six cannot be.2012-02-20
  • 1
    @Jyrki: But we only want $4$ of them to add to $0$. I checked the case $n=3$ by computer (the last one that can easily be checked completely), and if I didn't make a mistake, there's always a solution. I also always found a solution in randomly generated instances for $n=4$ and $n=5$.2012-02-20
  • 0
    @joriki: The contradiction I arrived at in the $n=3$ case was that it is impossible for the sum of all eight non-zero vectors to be zero if there are six distinct vectors and a single repeated pair (that could be one of the six or not). The sum of all eight was assumed to be zero, so it should still be zero after the removal of a repeating pair. This was shown to be impossible. The remaining case is thus that there are at least two repeated pairs, and in that case two such pairs form the required set of four. Sorry about not making that clear.2012-02-20
  • 0
    @Jyrki: I see, thanks for explaining. My computations actually didn't use the fact that the $v_i$ sum to $0$, so I doubt that this condition is necessary.2012-02-20
  • 0
    @joriki: Well, it's quite possible that the zero sum condition is not necessary, I just included that because, for reasons that this comment is too small to hold, that's the subcase I'm really interested in.2012-02-20

2 Answers 2

4

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.

  • 0
    +1, very nice. A minor point: You use set notation in $V = \{v_1,\ldots,v_{2^n}\}$, but I think you need this to be a multiset for the argument to work, e.g. otherwise $S_2$ would be empty.2012-02-21
  • 1
    Just for completeness, the case $n=3$ without the condition $\sum v_j=0$ (Jyrki already proved it in a comment under that condition). If there are at least two pairs of identical vectors, choose those two pairs. Otherwise, all non-zero vectors are present at least once, so we can choose a complete plane not containing the origin, and any plane sums to zero.2012-02-21
5

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 $ 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.

  • 0
    All, sorry about leaving this a bit sketchy for now. I will restructure this, when I have the time. Meanwhile, let's enjoy Yuval's complete answer.2012-02-21