¿Dada una lista de vectores no cero de $2^n$ $GF(2^n)$, hacer algunos $2^{n-1}$ de ellos suma 0?

Question

Deje $G=(\mathbb{Z/2Z})^n$ escrito de forma aditiva, $n>1$. (usted puede pensar en él como $\mathbb{F}_{2^n}$ pero no me pareció que útil... aún)

Deje $v_i$ ser distinto de cero elementos de $G$$i \in \{1 \dots 2^n \}$, de modo que $\sum_{i=1}^{2^n} v_i=0$. Es posible encontrar un subconjunto $J \subset \{1 \dots 2^n \}$, $|J|=2^{n-1}$ de modo que $$\sum_{j \in J} v_j=0?$$ Tenga en cuenta que el $v_i$s no se supone que ser distintos.

La mayoría de los teoremas que he visto de este tipo son prestados trivial por el carácter $2$, a pesar de que yo podría haber perdido algo. Mi primera idea sería aplicar Alon la Combinatoria Nullstellensatz pero no puedo encontrar un adecuado polinomio.

No sé si esto puede ser resuelto en absoluto (sospecho que esta declaración es verdadera), pero tiene una sensación de ser algo bien estudiado ya. Alguna idea? (También estoy considerando la posibilidad de solicitar esta en MathOverflow, ¿crees que es la adecuada?)

ACTUALIZACIÓN 1, basado en algunos comentarios:

1. Equipo de comprobación por joriki muestra el reclamo por $n=3$ y sugiere que para $n=4,5$.
2. Para los casos pequeños, de emparejamiento, también se trabaja, ver Jyrki del comentario de abajo.
3. El papel de la condición de $\sum_i v_i=0$ es claro; creo que en el caso de $\sum_i v_i \neq 0$ es en realidad más fácil de encontrar un adecuado $J$ porque $J$ y su complemento que no tienen las mismas cantidades.

Gracias a todos por su ayuda.

Answer 1

Originalmente mi respuesta reclamado lo siguiente: yo puedo demostrar que podemos encontrar un subconjunto de tamaño de cualquiera de las $2^{n-1}$ o $2^{n-1}+1$ que se suma a cero. IOW, no una solución completa, pero algo que puede ser reparable.

[Edit: Yuval ya dio una respuesta completa. Acabo de arreglar esto.]

Primero quitar el mayor número de duplicados vectores $v_i=v_j, i\neq j$ en pares como sea posible, y los puso a un lado para su uso futuro. Supongamos que nos quitan $k$ pares, y tienen un conjunto $S$ $2^n-2k$ distintos vectores no nulos restantes. Yo el primer reclamo que sin pérdida de generalidad podemos suponer $2k > n$. Esto es así, porque de lo contrario nos estamos perdiendo $<n$ cero vectores de $F_2^n$ desde el set $S$. Deje $U\subset F_2^n$ ser un subespacio de dimensión $n-1$ que contiene el lapso de los desaparecidos vectores. A continuación, el complemento de a $U$ está contenido en $S$, $2^{n-1}$ vectores, y porque (por los comentarios) hemos $n-1\ge2$, que suma igual a cero.

Tenga en cuenta que si $k\ge 2^{n-2}$, entonces hemos terminado, porque podemos construir la necesaria subconjunto de los duplicados de los pares. Por lo tanto podemos suponer que la $|S|> 2^{n-1}$. Observamos además que los vectores en el conjunto $S$ también suma cero, ya que la eliminación de duplicados de los pares de no cambiar esta propiedad (esto no es necesario en lo que sigue, como también se observó por Yuval, y se sospecha por joriki).

Ok. Vamos a iniciar la construcción de más y más grandes subconjuntos $U_j,j=0,1,\ldots,$$S$, que se suma a cero. La clave es la trivial observación de que cualquier conjunto de $n+1$ vectores de $S$ contiene un mínimo subconjunto linealmente dependiente (de tamaño entre el $3$ $n+1$ incluido). Este subconjunto, a continuación, ha de suma cero (maravillas de char 2!). Lo clave es la siguiente

Lema. Entre cualquiera de las $n+2$ vectores no nulos de a $F_2^n$ siempre hay un subconjunto de un número par de vectores tales que su suma es el vector cero.

Prueba. Si los vectores son $u_1,u_2,\ldots,u_{n+2}$, entonces tenemos un mapeo lineal $\phi$ $F_2^{n+2}$ $F_2^n$mediante la asignación de la tupla $(b_1,b_2,\ldots,b_{n+2})$ a la combinación lineal $\sum_i b_iu_i$. Según el rango de nulidad, $\ker\phi$ tiene dimensión, al menos, dos. Por lo tanto, existen al menos 3 distinto de cero combinaciones de $(b_1,b_2,\ldots,b_{n+2})$ dando lugar a una suma cero vector. Si los dos primeros de ellos tienen un peso desigual, entonces su suma tiene un peso. Q. E. D.

Así que vamos a $U_0=\emptyset$, y luego, dado $U_j$, añada una mínima linealmente dependiente de conjunto de un número par de vectores que forman el conjunto $U_{j+1}$. Enjuague. Repita. Porque se supone que $S$ contiene más de la mitad de los elementos de $F_2^n$, en algún momento el conjunto $U_j$ $\le2^{n-1}$ elementos y el conjunto $U_{j+1}$ $>2^{n-1}$ elementos. Debido a $|U_{j+1}\setminus U_j|\le n+2$, vemos que $$ 2^{n-1}-n-1\le |U_j|\le 2^{n-1}. $$ Debido a $|U_j|$ es un número par, el reclamo sigue a continuación, mediante la adición de algunos de los duplicados de los pares que dejamos de lado en el comienzo del set $U_j$. Aquí, en el último paso tenemos que ejercer un poco de atención. Si $n$ es incluso, luego de la paridad nos dice que realmente tenemos $|U_j|\ge 2^{n-1}-n$, y podemos llenar con pares de duplicados. Si $n$ es impar, entonces podemos usar la desigualdad de $|U_{j+1}\setminus U_j|\le n+1$ en lugar de ello, porque este juego también tiene un número de vectores. De nuevo, la frontera "caso" no nos causará problemas.

Answer 2

Aquí es una prueba para $n \geq 4$, inspirado por Jyrki. La prueba de realidad no utilice el hecho de que los vectores de suma cero.

Con avidez extracto de $V = v_1,\ldots,v_{2^n}$ lineal dependencias de mínimo tamaño posible. Este particiones $V$ a $V = S_2 \cup \cdots \cup S_{n+1}$ donde $S_k$ es un discontinuo de la unión lineal de las dependencias de tamaño $k$. Si los vectores no suma cero, no podrían ser algunos de los "restos" de un conjunto de tamaño en la mayoría de las $n$.

Considere la posibilidad de $R = V \setminus (S_2 \cup S_3 \cup S_4)$. Si $x,y \in R$ son distintos, a continuación,$x + y \notin R$; tenga en cuenta que $x,y,x+y \neq 0$. Además, si $x,y,z \in R$ son distintos, a continuación, $x + y \neq x + z$ (desde $y \neq z$), y si $x,y,z,w \in R$ son distintos, a continuación, $x + y \neq z + w$ (ya que de lo contrario $x + y + z + w = 0$). Por lo tanto $$ |R| + \binom{|R|}{2} \leq 2^n-1. $$ Al $n \geq 4$, esto demuestra que $$ |S_2 \cup S_3 \cup S_4| \geq 2^{n-1} + 3. $$ Ya que todos los vectores en $V$ son no-cero, $|S_2| \geq 2$. Por otra parte, si $|S_2| = 2$ $V$ contiene todos los vectores no nulos, y por lo que es fácil encontrar un conjunto de tamaño $2^{n-1}$ sumando a cero. Así que supongamos $|S_2| \geq 4$.

Si $|S_2| + |S_4| \geq 2^{n-1}$, entonces hemos terminado (ya $|S_2| \geq 2$). De lo contrario, existe un subconjunto $T_3 \subset S_3$ sumando a cero tal que $2^{n-1} \leq |S_2| + |S_4| + |T_3| \leq 2^{n-1} + 2$. Si la suma es $2^{n-1}$ o $2^{n-1} + 2$ estamos hecho (de nuevo, con $|S_2| \geq 2$). Si la suma es $2^{n-1}+1$, retire los dos pares de $S_2$. El número total de elementos ahora es $2^{n-1}-3$. Desde $|S_2 \cup S_3 \cup S_4| \geq 2^{n-1} + 3$, debe ser uno más del triple que en $S_3$ que podemos añadir para obtener exactamente $2^{n-1}$ elementos.