Suma restringida

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.}$

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]

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]

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]

• Método polinomial en combinatoria

• 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  .

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