En teoría de números aditivos y combinatoria , un conjunto de suma restringido tiene la forma
dónde son subconjuntos finitos no vacíos de un campo F yes un polinomio sobre F .
Cuándo , S es la usual sumset que se denota por nA si; Cuándo
S se escribe como que se denota por Si . Tenga en cuenta que | S | > 0 si y solo si existen con .
Teorema de Cauchy-Davenport
El teorema de Cauchy-Davenport que lleva el nombre de Augustin Louis Cauchy y Harold Davenport afirma que para cualquier p primo y subconjuntos no vacíos A y B del grupo cíclico de orden primo Z / p Z tenemos la desigualdad [1] [2]
Podemos usar esto para deducir el teorema de Erdős-Ginzburg-Ziv : dada cualquier secuencia de 2 n -1 elementos en Z / n , hay n elementos que suman cero módulo n . (Aquí n no necesita ser primo.) [3] [4]
Una consecuencia directa del teorema de Cauchy-Davenport es: Dado cualquier conjunto S de p −1 o más elementos distintos de cero, no necesariamente distintos, de Z / p Z , cada elemento de Z / p Z puede escribirse como la suma de los elementos de algún subconjunto (posiblemente vacío) de S . [5]
El teorema de Kneser generaliza esto a grupos abelianos generales. [6]
Conjetura de Erdős-Heilbronn
La conjetura de Erdős-Heilbronn planteada por Paul Erdős y Hans Heilbronn en 1964 establece quesi p es un número primo y A es un subconjunto no vacío del campo Z / p Z . [7] Esto fue confirmado por primera vez por JA Dias da Silva y YO Hamidoune en 1994 [8] quienes demostraron que
donde A es un subconjunto finito no vacío de un campo F , yp ( F ) es un primo p si F es de característica p , yp ( F ) = ∞ si F es de característica 0. Varias extensiones de este resultado fueron dadas por Noga Alon , MB Nathanson e I. Ruzsa en 1996, [9] QH Hou y Zhi-Wei Sun en 2002, [10] y G. Karolyi en 2004. [11]
Nullstellensatz combinatorio
Una herramienta poderosa en el estudio de límites inferiores para cardinalidades de varios conjuntos de sumas restringidos es el siguiente principio fundamental: el combinatorio Nullstellensatz . [12] Dejaser un polinomio sobre un campo F . Supongamos que el coeficiente del monomio en es distinto de cero y es el grado total de. Sison subconjuntos finitos de F con por , entonces hay tal que .
El método que utiliza la combinatoria Nullstellensatz también se denomina método polinomial. Esta herramienta se basó en un artículo de N. Alon y M. Tarsi en 1989, [13] y fue desarrollada por Alon, Nathanson y Ruzsa en 1995-1996, [9] y reformulada por Alon en 1999. [12]
Ver también
Referencias
- ^ Nathanson (1996) p.44
- ^ Geroldinger y Ruzsa (2009) págs. 141-142
- ↑ Nathanson (1996) p.48
- ^ Geroldinger y Ruzsa (2009) p.53
- ^ Wolfram's MathWorld, Cauchy-Davenport Theorem, http://mathworld.wolfram.com/Cauchy-DavenportTheorem.html , consultado el 20 de junio de 2012.
- ^ Geroldinger y Ruzsa (2009) p.143
- ^ Nathanson (1996) p.77
- ^ Dias da Silva, JA; Hamidoune, YO (1994). "Espacios cíclicos para derivados de Grassmann y teoría aditiva". Boletín de la London Mathematical Society . 26 (2): 140-146. doi : 10.1112 / blms / 26.2.140 .
- ^ a b Alon, Noga ; Nathanson, Melvyn B .; Ruzsa, Imre (1996). "El método polinomial y sumas restringidas de clases de congruencia" (PDF) . Revista de teoría de números . 56 (2): 404–417. doi : 10.1006 / jnth.1996.0029 . Señor 1373563 .
- ^ Hou, Qing-Hu; Sun, Zhi-Wei (2002). "Sumas restringidas en un campo" . Acta Arithmetica . 102 (3): 239–249. Código Bibliográfico : 2002AcAri.102..239H . doi : 10.4064 / aa102-3-3 . Señor 1884717 .
- ^ Károlyi, Gyula (2004). "El problema de Erdős-Heilbronn en grupos abelianos". Revista de Matemáticas de Israel . 139 : 349–359. doi : 10.1007 / BF02787556 . Señor 2041798 .
- ^ a b Alon, Noga (1999). "Combinatorial Nullstellensatz" (PDF) . Combinatoria, Probabilidad y Computación . 8 (1–2): 7–29. doi : 10.1017 / S0963548398003411 . Señor 1684621 .
- ^ Alon, Noga ; Tarsi, Michael (1989). "Un punto cero en ninguna parte en las asignaciones lineales". Combinatorica . 9 (4): 393–395. doi : 10.1007 / BF02125351 . Señor 1054015 .
- Geroldinger, Alfred; Ruzsa, Imre Z., eds. (2009). Teoría combinatoria de números y teoría aditiva de grupos . Cursos Avanzados en 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. ISBN 978-3-7643-8961-1. Zbl 1177.11005 .
- 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
- Sun, Zhi-Wei (2006). "Un teorema aditivo y sumas restringidas". Matemáticas. Res. Lett . 15 (6): 1263-1276. arXiv : matemáticas.CO / 0610981 . Bibcode : 2006math ..... 10981S . doi : 10.4310 / MRL.2008.v15.n6.a15 .
- Zhi-Wei Sun : Sobre algunas conjeturas de Erdős-Heilbronn, Lev y Snefully ( PDF ), charla sobre una encuesta.
- Weisstein, Eric W. "Conjetura de Erdős-Heilbronn" . MathWorld .