Problema de suma cero

Problema matemático

En teoría de números , los problemas de suma cero son ciertos tipos de problemas combinatorios sobre la estructura de un grupo abeliano finito . Concretamente, dado un grupo abeliano finito G y un entero positivo n , se busca el valor más pequeño de k tal que cada secuencia de elementos de G de tamaño k contenga n términos que sumen .

El resultado clásico en esta área es el teorema de 1961 de Paul Erdős , Abraham Ginzburg y Abraham Ziv . ^[1] Demostraron que para el grupo de números enteros módulo n , ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$

$${\displaystyle k=2n-1.}$$

Explícitamente, esto dice que cualquier multiconjunto de 2 n − 1 enteros tiene un subconjunto de tamaño n cuya suma de elementos es un múltiplo de n , pero que lo mismo no es cierto para los multiconjuntos de tamaño 2 n − 2. (De hecho, el límite inferior es fácil de ver: el multiconjunto que contiene n − 1 copias de 0 y n − 1 copias de 1 no contiene ningún n -subconjunto que sume un múltiplo de n .) Este resultado se conoce como el teorema de Erdős–Ginzburg–Ziv en honor a sus descubridores. También puede deducirse del teorema de Cauchy–Davenport . ^[2]

Existen resultados más generales que este teorema, como el teorema de Olson, la conjetura de Kemnitz (demostrada por Christian Reiher en 2003 ^[3] ) y el teorema EGZ ponderado (demostrado por David J. Grynkiewicz en 2005 ^[4] ).

Véase también

• Constante de Davenport
• Problema de suma de subconjuntos
• Teoría de Ramsey de suma cero

Referencias

1. Erdős, Paul; Ginzburg, A.; Ziv, A. (1961). "Teorema en la teoría de números aditivos". Bull. Res. Council Israel . 10F : 41–43. Zbl  0063.00009.
2. Nathanson (1996) pág. 48
3. Reiher, Christian (2007), "Sobre la conjetura de Kemnitz respecto de los puntos reticulares en el plano", The Ramanujan Journal , 13 (1–3): 333–337, arXiv : 1603.06161 , doi :10.1007/s11139-006-0256-y, S2CID  119600313, Zbl  1126.11011.
4. Grynkiewicz, DJ (2006), "Un teorema ponderado de Erdős-Ginzburg-Ziv" (PDF) , Combinatorica , 26 (4): 445–453, doi :10.1007/s00493-006-0025-y, S2CID  33448594, Zbl  1121.11018.

• Geroldinger, Alfred (2009). "Teoría de grupos aditivos y factorizaciones no únicas". En Geroldinger, Alfred; Ruzsa, Imre Z. (eds.). Teoría combinatoria de números y teoría aditiva de grupos . Cursos Avanzados de Matemáticas CRM Barcelona. Elsholtz, C.; Freiman, G.; Hamidoune, YO; Hegyvári, N.; Károlyi, G.; Nathanson, M.; Solymosi, J .; Stanchescu, Y. Con prólogo de Javier Cilleruelo, Marc Noy y Oriol Serra (Coordinadores del DocCourse). Basilea: Birkhäuser. pp. 1–86. ISBN 978-3-7643-8961-1.Zbl 1221.20045  .
• Nathanson, Melvyn B. (1996). Teoría de números aditivos: problemas inversos y geometría de conjuntos sumatorios . Textos de posgrado en matemáticas . Vol. 165. Springer-Verlag . ISBN. 0-387-94655-1.Zbl 0859.11003  .

Enlaces externos

• "Teorema de Erdös-Ginzburg-Ziv", Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
• PlanetMath Erdős, Ginzburg, Teorema de Ziv
• Sun, Zhi-Wei , "Sistemas de cobertura, conjuntos de suma restringidos, problemas de suma cero y su unificación"

Lectura adicional

• Problemas de suma cero: una encuesta (artículo de revista de acceso abierto)
• Teoría de Ramsey de suma cero: gráficos, secuencias y más (página de inicio del taller)
• Arie Bialostocki , "Árboles de suma cero: un estudio de resultados y problemas abiertos" NW Sauer (ed.) RE Woodrow (ed.) B. Sands (ed.), Combinatoria finita e infinita en conjuntos y lógica , Nato ASI Ser. , Kluwer Acad. Publ. (1993) págs. 19-29
• Y. Caro, "Problemas de suma cero: una revisión" Discrete Math. , 152 (1996) pp. 93–113