Suma restringida

Sumset of a field subject to a specific polynomial restriction

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

${\displaystyle S=\{a_{1}+\cdots +a_{n}:\ a_{1}\in A_{1},\ldots ,a_{n}\in A_{n}\ \mathrm {and} \ P(a_{1},\ldots ,a_{n})\not =0\},}$

donde son subconjuntos finitos no vacíos de un campo F y es un polinomio sobre F . ${\displaystyle A_{1},\ldots ,A_{n}}$ ${\displaystyle P(x_{1},\ldots ,x_{n})}$

Si es una función constante distinta de cero, por ejemplo para cualquier , entonces es el conjunto suma usual que se denota por si ${\displaystyle P}$ ${\displaystyle P(x_{1},\ldots ,x_{n})=1}$ ${\displaystyle x_{1},\ldots ,x_{n}}$ ${\displaystyle S}$ ${\displaystyle A_{1}+\cdots +A_{n}}$ ${\displaystyle nA}$ ${\displaystyle A_{1}=\cdots =A_{n}=A.}$

Cuando

${\displaystyle P(x_{1},\ldots ,x_{n})=\prod _{1\leq i<j\leq n}(x_{j}-x_{i}),}$

S se escribe como lo cual se denota por si ${\displaystyle A_{1}\dotplus \cdots \dotplus A_{n}}$ ${\displaystyle n^{\wedge }A}$ ${\displaystyle A_{1}=\cdots =A_{n}=A.}$

Nótese que | S | > 0 si y sólo si existen con ${\displaystyle a_{1}\in A_{1},\ldots ,a_{n}\in A_{n}}$ ${\displaystyle P(a_{1},\ldots ,a_{n})\not =0.}$

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]} ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$

${\displaystyle |A+B|\geq \min\{p,\,|A|+|B|-1\}}$

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] ${\displaystyle A+B:=\{a+b{\pmod {p}}\mid a\in A,b\in B\}}$ ${\displaystyle A,B}$ ${\displaystyle G}$

${\displaystyle |A+B|\geq \min\{p(G),\,|A|+|B|-1\}}$

donde es el tamaño del subgrupo no trivial más pequeño de (lo establecemos en si no existe tal subgrupo). ${\displaystyle p(G)}$ ${\displaystyle G}$ ${\displaystyle 1}$

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]} ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$

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] ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$ ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$

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 ${\displaystyle |2^{\wedge }A|\geq \min\{p,\,2|A|-3\}}$

${\displaystyle |n^{\wedge }A|\geq \min\{p(F),\ n|A|-n^{2}+1\},}$

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 . ${\displaystyle f(x_{1},\ldots ,x_{n})}$ ${\displaystyle F}$ ${\displaystyle x_{1}^{k_{1}}\cdots x_{n}^{k_{n}}}$ ${\displaystyle f(x_{1},\ldots ,x_{n})}$ ${\displaystyle k_{1}+\cdots +k_{n}}$ ${\displaystyle f(x_{1},\ldots ,x_{n})}$ ${\displaystyle A_{1},\ldots ,A_{n}}$ ${\displaystyle F}$ ${\displaystyle |A_{i}|>k_{i}}$ ${\displaystyle i=1,\ldots ,n}$ ${\displaystyle a_{1}\in A_{1},\ldots ,a_{n}\in A_{n}}$ ${\displaystyle f(a_{1},\ldots ,a_{n})\not =0}$

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

• Método polinomial en combinatoria

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". Números 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. 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 los grupos abelianos". Revista Israelí de Matemáticas . 139 : 349–359. doi :10.1007/BF02787556. SEÑOR  2041798. S2CID  33387005.
14. 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. 

• Geroldinger, Alfred; Ruzsa, Imre Z., eds. (2009). 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. 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 sumatorios . Textos de posgrado en matemáticas . Vol. 165. Springer-Verlag . ISBN. 0-387-94655-1.Zbl 0859.11003  .

Enlaces externos

• Weisstein, Eric W. "Conjetura de Erdős-Heilbronn". MundoMatemático .