text: # Uses of Chevalley-Warning
  
  In the recent IMC 2011, the last problem of the 1st day (no. 5, the hardest of that day) was as follows:
  
  We have $4n-1$ vectors in $F_2^{2n-1}$: $\{v_i\}_{i=1}^{4n-1}$. The problem asks : Prove the existence of a subset $A \subseteq [4n-1], |A| = 2n$ such that $\sum_{i \in A} v_i = \vec{0}$.
  
  Is there a solution that uses the Chevalley-Warning theorem about divisibility of number of solutions by the field's characteristic? The statement of the problem seems as a "xor" analog of Erdos-Ginzburg-Ziv, that is usually proved by Chevally-Warning.
  
  My idea is to formulate homogeneous polynomial equations in $a_1,\cdots,a_{4n-1} \in F_2$: $P_j(\vec{a}) = (\sum a_i v_i)_j$ for $1 \le j \le 2n-1$. Let $A(\vec{a}) = \{ i | a_i = 1\}$ and $g(\vec{a}) = |A(\vec{a})|$ (we want to choose $A = A(\vec{a})$ for a solution $a$ of the system).
  
  Ideas for completing the solution:
  
  • We can also create $Q_{k}(\vec{a}) =$ Symmetric polynomial of degree $2^k$ = $a_1 \cdots a_{2^k} + \cdots$. We notice that $Q_k(a) = \binom{g(\vec{a})}{2^k}$. By Lucas's Theorem, mod 2 we have $\binom{m}{2^k} =$ k'th digit of $m$ in base-$2$. So we choose the equations $Q_k(a) = \binom{2n}{2^k}$ mod 2.
  
  The problem is that we get $\sum deg(Q_k) \ge 2n$ (sum over number of digits of $4n-1$). Also, $0$ is not a trivial solution.
  
  • Another idea was to define the equations $R_i(a) = a_{2i-1} + a_{2i} - a_{2i+1} - a_{2i+2} = 0, 1 \le i \le 2n$. A solution implies that $a_{2i-1} + a_{2i}$ is constant. If it is $1$, we get that from each pair of even and odd vector, one is chosen - $2n$ vectors in total. But it has some holes.
  
  • Another idea is to create equations that force $g(\vec{a}) = 0$ mod n, so $\vec{0}$ is a trivial solution, and another solution would imply that a $A$ exists of size $n, 2n$ or $3n$.
  
  A nice observation is that one of the vectors is (wlog) $\vec{0}$ (can be assumed since $2n$ is even, so replacing $v_i$ by $v_i - v_{1}$ is fine).
  
  If you have idea of how to use the theorem, and examples in general of its non-trivial uses - it would be welcome.
  
  -
  I guess $F_2^{2-1}$ should be $F_2^{2n-1}$. (I don't want to edit it yet since it's <6 characters.) – Srivatsan Jul 31 '11 at 17:58
  Ofir: could you please reread your question, there are some obvious typos, but maybe some less obvious ones. – Peter Patzt Jul 31 '11 at 19:12
  I've fixed the typos and added an idea, thanks. – Ofir Aug 1 '11 at 15:41
  (Re: analog of Erdos-Ginzburg-Ziv) a variant of Kemnitz's problem, I'd say... – Grigory M Aug 19 '11 at 11:01
explanation: The document presents a math problem from the IMC 2011 competition, specifically problem 5 from the first day. The problem involves proving the existence of a subset of vectors in a finite field that sums to the zero vector. The author asks if the Chevalley-Warning theorem can be used to solve this problem and provides several ideas and approaches for constructing a solution using polynomial equations and symmetric polynomials. The document contains a question but does not provide a complete answer to the problem.
distilabel_metadata.content: Evaluate the user given text extract and determine if it contains a math question and optionally and answer to this question.
  
  Output rules:
  
  1. Briefly describe the document and mention if it contains a question or a question and answer.
  2. Finalize the output with: Label: no-question,question,question-and-answer,multiple-question,multiple-question-and-answer
distilabel_metadata.role: system
distilabel_metadata.content: # Uses of Chevalley-Warning
  
  In the recent IMC 2011, the last problem of the 1st day (no. 5, the hardest of that day) was as follows:
  
  We have $4n-1$ vectors in $F_2^{2n-1}$: $\{v_i\}_{i=1}^{4n-1}$. The problem asks : Prove the existence of a subset $A \subseteq [4n-1], |A| = 2n$ such that $\sum_{i \in A} v_i = \vec{0}$.
  
  Is there a solution that uses the Chevalley-Warning theorem about divisibility of number of solutions by the field's characteristic? The statement of the problem seems as a "xor" analog of Erdos-Ginzburg-Ziv, that is usually proved by Chevally-Warning.
  
  My idea is to formulate homogeneous polynomial equations in $a_1,\cdots,a_{4n-1} \in F_2$: $P_j(\vec{a}) = (\sum a_i v_i)_j$ for $1 \le j \le 2n-1$. Let $A(\vec{a}) = \{ i | a_i = 1\}$ and $g(\vec{a}) = |A(\vec{a})|$ (we want to choose $A = A(\vec{a})$ for a solution $a$ of the system).
  
  Ideas for completing the solution:
  
  • We can also create $Q_{k}(\vec{a}) =$ Symmetric polynomial of degree $2^k$ = $a_1 \cdots a_{2^k} + \cdots$. We notice that $Q_k(a) = \binom{g(\vec{a})}{2^k}$. By Lucas's Theorem, mod 2 we have $\binom{m}{2^k} =$ k'th digit of $m$ in base-$2$. So we choose the equations $Q_k(a) = \binom{2n}{2^k}$ mod 2.
  
  The problem is that we get $\sum deg(Q_k) \ge 2n$ (sum over number of digits of $4n-1$). Also, $0$ is not a trivial solution.
  
  • Another idea was to define the equations $R_i(a) = a_{2i-1} + a_{2i} - a_{2i+1} - a_{2i+2} = 0, 1 \le i \le 2n$. A solution implies that $a_{2i-1} + a_{2i}$ is constant. If it is $1$, we get that from each pair of even and odd vector, one is chosen - $2n$ vectors in total. But it has some holes.
  
  • Another idea is to create equations that force $g(\vec{a}) = 0$ mod n, so $\vec{0}$ is a trivial solution, and another solution would imply that a $A$ exists of size $n, 2n$ or $3n$.
  
  A nice observation is that one of the vectors is (wlog) $\vec{0}$ (can be assumed since $2n$ is even, so replacing $v_i$ by $v_i - v_{1}$ is fine).
  
  If you have idea of how to use the theorem, and examples in general of its non-trivial uses - it would be welcome.
  
  -
  I guess $F_2^{2-1}$ should be $F_2^{2n-1}$. (I don't want to edit it yet since it's <6 characters.) – Srivatsan Jul 31 '11 at 17:58
  Ofir: could you please reread your question, there are some obvious typos, but maybe some less obvious ones. – Peter Patzt Jul 31 '11 at 19:12
  I've fixed the typos and added an idea, thanks. – Ofir Aug 1 '11 at 15:41
  (Re: analog of Erdos-Ginzburg-Ziv) a variant of Kemnitz's problem, I'd say... – Grigory M Aug 19 '11 at 11:01
distilabel_metadata.role: user
distilabel_metadata.raw_output_q_a_detector_0: The document presents a math problem from the IMC 2011 competition, specifically problem 5 from the first day. The problem involves proving the existence of a subset of vectors in a finite field that sums to the zero vector. The author asks if the Chevalley-Warning theorem can be used to solve this problem and provides several ideas and approaches for constructing a solution using polynomial equations and symmetric polynomials. The document contains a question but does not provide a complete answer to the problem.
  
  Label: question