stringtranslate.com

Suma restringida

En la teoría de números aditivos y combinatoria , un conjunto sumatorio restringido tiene la forma

donde son subconjuntos finitos no vacíos de un campo F y es un polinomio sobre F .

Si es una función constante distinta de cero, por ejemplo para cualquier , entonces es el conjunto suma usual que se denota por si

Cuando

S se escribe como lo cual se denota por si

Nótese que | S | > 0 si y sólo si existen con

Teorema de Cauchy-Davenport

El teorema de Cauchy-Davenport , llamado así por Augustin Louis Cauchy y Harold Davenport , afirma que para cualquier primo p y subconjuntos no vacíos A y B del grupo cíclico de orden primo tenemos la desigualdad [1] [2] [3]

donde , es decir, estamos usando aritmética modular . Se puede generalizar a grupos arbitrarios (no necesariamente abelianos) usando una transformada de Dyson . Si son subconjuntos de un grupo , entonces [4]

donde es el tamaño del subgrupo no trivial más pequeño de (lo establecemos en si no existe tal subgrupo).

Podemos usar esto para deducir el teorema de Erdős–Ginzburg–Ziv : dada cualquier secuencia de 2 n −1 elementos en el grupo cíclico , hay n elementos que suman cero módulo n . (Aquí n no necesita ser primo.) [5] [6]

Una consecuencia directa del teorema de Cauchy-Davenport es: Dada cualquier secuencia S de p −1 o más elementos distintos de cero, no necesariamente distintos, de , cada elemento de puede escribirse como la suma de los elementos de alguna subsecuencia (posiblemente vacía) de S . [7]

El teorema de Kneser generaliza esto a los grupos abelianos generales . [8]

Conjetura de Erdös-Heilbronn

La conjetura de Erdős-Heilbronn planteada por Paul Erdős y Hans Heilbronn en 1964 establece que si p es un primo y A es un subconjunto no vacío del cuerpo Z / p Z . [9] Esto fue confirmado por primera vez por JA Dias da Silva y YO Hamidoune en 1994 [10] quienes demostraron que

donde A es un subconjunto finito no vacío de un cuerpo F , y p ( F ) es un primo p si F es de característica p , y p ( 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, [11] QH Hou y Zhi-Wei Sun en 2002, [12] y G. Karolyi en 2004. [13]

Sentido nulo combinatorio

Una herramienta poderosa en el estudio de límites inferiores para cardinalidades de varios conjuntos suma restringidos es el siguiente principio fundamental: el Nullstellensatz combinatorio . [14] Sea un polinomio sobre un cuerpo . Supóngase que el coeficiente del monomio en es distinto de cero y es el grado total de . Si son subconjuntos finitos de con para , entonces hay tales que .

Esta herramienta se basó en un artículo de N. Alon y M. Tarsi en 1989, [15] y fue desarrollada por Alon, Nathanson y Ruzsa en 1995-1996, [11] y reformulada por Alon en 1999. [14]

Véase también

Referencias

  1. ^ Nathanson (1996) pág. 44
  2. ^ Geroldinger y Ruzsa (2009) págs. 141-142
  3. ^ Jeffrey Paul Wheeler (2012). "El teorema de Cauchy-Davenport para grupos finitos". arXiv : 1202.1816 [math.CO].
  4. ^ DeVos, Matt (2016). "Sobre una generalización del teorema de Cauchy-Davenport". Enteros . 16 .
  5. ^ Nathanson (1996) pág. 48
  6. ^ Geroldinger y Ruzsa (2009) p.53
  7. ^ Wolfram's MathWorld, Teorema de Cauchy-Davenport, http://mathworld.wolfram.com/Cauchy-DavenportTheorem.html, consultado el 20 de junio de 2012.
  8. ^ Geroldinger y Ruzsa (2009) p.143
  9. ^ Nathanson (1996) pág. 77
  10. ^ Dias da Silva, JA; Hamidoune, YO (1994). "Espacios cíclicos para derivadas de Grassmann y teoría aditiva". Boletín de la Sociedad Matemática de Londres . 26 (2): 140–146. doi :10.1112/blms/26.2.140.
  11. ^ ab Alon, Noga ; Nathanson, Melvyn B.; Ruzsa, Imre (1996). "El método polinomial y las sumas restringidas de clases de congruencia" (PDF) . Journal of Number Theory . 56 (2): 404–417. doi :10.1006/jnth.1996.0029. MR  1373563.
  12. ^ Hou, Qing-Hu; Sol, Zhi-Wei (2002). "Sumas restringidas en un campo". Acta Aritmética . 102 (3): 239–249. Código Bib : 2002AcAri.102..239H. doi : 10.4064/aa102-3-3 . SEÑOR  1884717.
  13. ^ Károlyi, Gyula (2004). "El problema de Erdős-Heilbronn en grupos abelianos". Revista Israelí de Matemáticas . 139 : 349–359. doi :10.1007/BF02787556. SEÑOR  2041798. S2CID  33387005.
  14. ^ ab Alon, Noga (1999). "Combinatorial Nullstellensatz" (PDF) . Combinatoria, probabilidad y computación . 8 (1–2): 7–29. doi :10.1017/S0963548398003411. MR  1684621. S2CID  209877602.
  15. ^ Alon, Noga ; Tarsi, Michael (1989). "Un punto cero en ninguna parte en aplicaciones lineales". Combinatorica . 9 (4): 393–395. CiteSeerX 10.1.1.163.2348 . doi :10.1007/BF02125351. MR  1054015. S2CID  8208350. 

Enlaces externos