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 número entero positivo n , se pide el valor más pequeño de k tal que toda secuencia de elementos de G de tamaño k contenga n términos que sumen 0 .
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 grupode enteros módulo n ,
Explícitamente, esto dice que cualquier conjunto múltiple 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 conjuntos múltiples de tamaño 2 n - 2 (de hecho, el menor El límite es fácil de ver: el conjunto múltiple que contiene n - 1 copias de 0 y n - 1 copias de 1 no contiene n- subconjuntos que sumen a un múltiplo de n .) Este resultado se conoce como el teorema de Erdős-Ginzburg-Ziv por sus descubridores . También se puede deducir del teorema de Cauchy-Davenport . [2]
Existen resultados más generales que este teorema, como el teorema de Olson , la conjetura de Kemnitz (probada por Christian Reiher en 2003 [3] ) y el teorema EGZ ponderado (probado por David J. Grynkiewicz en 2005 [4] ).
Ver también
Referencias
- ^ Erdős, Paul; Ginzburg, A .; Ziv, A. (1961). "Un teorema en teoría de números aditivos". Toro. Res. Consejo de Israel . 10F : 41–43. Zbl 0063.00009 .
- ^ Nathanson (1996) p.48
- ^ Reiher, Christian (2007), "Sobre la conjetura de Kemnitz sobre los puntos de celosía en el plano", The Ramanujan Journal , 13 (1-3): 333-337, arXiv : 1603.06161 , doi : 10.1007 / s11139-006-0256- y , Zbl 1126.11011.
- ^ Grynkiewicz, DJ (2006), "A Weighted Erdős-Ginzburg-Ziv Theorem" (PDF) , Combinatorica , 26 (4): 445–453, doi : 10.1007 / s00493-006-0025-y , 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ática 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 . Textos de Posgrado en Matemáticas . 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, sumas restringidas, problemas de suma cero y su unificación"