Suma de $n$ vectores en $(\mathbb Z/n)^k$

Question

Dejemos que $n,k$ sean enteros positivos. ¿Cuál es el valor más pequeño de $N$ tal que para cualquier $N$ vectores (pueden repetirse) en $(\mathbb Z/(n))^k$ se puede elegir $n$ vectores cuya suma es $0$ ?

Mi opinión es $N=2^k(n-1)+1$ . Es ciertamente agudo: uno puede escoger nuestro conjunto para ser $n-1$ copias del conjunto $(a_1,...,a_k)$ con cada $a_i=0$ o $1$ . El caso $k=1$ es alguna pregunta de concurso de matemáticas (creo, pero no recuerdo la referencia exacta). ¿Alguien sabe de alguna referencia? Gracias.

---

Gracias a todos. Me gustaría poder aceptar todas las respuestas, ¡son muy útiles!

Answer 1

Tu suposición es correcta para k=1 y 2, pero cuando k es mayor, las cosas se complican. Por ejemplo, cuando k=n=3, N=19. Para un resumen de algunos resultados conocidos, ver:

http://www.ma.rhul.ac.uk/~elsholtz/WWW/papers/papers08harborth.pdf

Answer 2

El caso k = 1 es el teorema de Erdős-Ginzburg-Ziv. Echa un vistazo a esto Artículo de Wikipedia que tiene enlaces a algunos estudios de la amplia literatura de resultados similares. (Las generalizaciones particulares que conozco piden un conjunto de vectores que suman 0 cuyo tamaño es la cardinalidad del grupo, no su exponente).

El caso k = 2 es la conjetura de Kemnitz, como señaló Kristal, y como mencionó Ricky (y también como se menciona en la página de Wikipedia que enlacé) fue demostrada por Reiher en 2003.

Answer 3

Hubo alguna discusión sobre el caso n=3 en sci.math alrededor de 1994. Hay un juego de cartas llamado Set con una baraja de 81 cartas para que cada carta sea naturalmente un punto en $(\mathbb Z/3)^4$ . Se reparten varias cartas, y tu tarea consiste en identificar los triples de cartas llamados Conjuntos que forman una línea, o lo que es lo mismo, que suman el vector 0. Una pregunta natural es cuántos puntos se pueden repartir sin que exista una línea. No es demasiado difícil construir 9 puntos distintos en el espacio afín 3, o 20 puntos distintos en el espacio afín 4 sobre $\mathbb Z/3$ para que no haya ninguna línea contenida en los puntos, y estos son los máximos. Estos corresponden a $N=19$ para $(n,k) = (3,3)$ y $N=41$ para $(n,k) = (3,4)$ como en la referencia que Ricky Liu enlazó, repitiendo cada punto dos veces.

Las configuraciones máximas son altamente simétricas. Los 9 puntos de la dimensión 3 corresponden a una cónica no degenerada, que es única hasta la simetría. Los 20 puntos de dimensión 4 corresponden en realidad a una cónica no degenerada que contiene 10 puntos en el espacio proyectivo 3 visto como líneas que pasan por el origen en el espacio afín 4.

Por ejemplo, hay 9 puntos en la dimensión 3 que satisfacen $z=x^2 + y^2:$ $\{(0,0,0),(\pm1,0,1),(0,\pm1,1),(\pm1,\pm1,-1)\}$ y este conjunto no contiene líneas.

Answer 4

El caso $k=2$ se maneja (se identifican las secuencias extremas) en este documento de Gao y Goldinger, que se publicó en la revista Números enteros .

Answer 5

Aunque no sé la respuesta a tu pregunta concreta, parece estar relacionada con un problema bien conocido en el que sólo se insiste en que el número de simmands es distinto de cero. Se sabe mucho al respecto y hay interesantes problemas abiertos. Cuando n es un primo se necesitan (n-1)k+1 vectores (y esto es agudo). Este es el "teorema de Olson" y se puede demostrar mediante los teoremas de Chevaley sobre soluciones no nulas para ecuaciones polinómicas cuando el número de variables supera el grado. Quizás técnicas similares (al menos para el caso n=primo) funcionen para tu problema).

La referencia de Olson es: J. E. Olson, A combinatorial problem on nite abelian groups I, J. Number Theory 1 (1969), 8-10.

Para la potencia no prima mira el artículo de R. Meshulam: An uncertainty inequality and zero subsums. Discrete Math. 84 (1990), no. 2, 197--200.

Para un método general relevante: N. Alon, Combinatorial Nullstellensatz. Combin. Probab. Comput. 8 (1999), no. 1-2, 7--29.