conjunto de suma restringido

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

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

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

Si${\displaystyle P}$es una función constante distinta de cero, por ejemplo${\displaystyle P(x_{1},\ldots ,x_{n})=1}$para cualquier${\displaystyle x_{1},\ldots ,x_{n}}$, entonces${\displaystyle S}$es el conjunto suma habitual${\displaystyle A_{1}+\cdots +A_{n}}$que se denota por${\displaystyle nA}$si${\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${\displaystyle A_{1}\dotplus \cdots \dotplus A_{n}}$que se denota por${\displaystyle n^{\wedge }A}$si${\displaystyle A_{1}=\cdots =A_{n}=A.}$

Tenga en cuenta que | S | > 0 si y solo si existen${\displaystyle a_{1}\in A_{1},\ldots ,a_{n}\in A_{n}}$con${\displaystyle P(a_{1},\ldots ,a_{n})\not =0.}$

El teorema de Cauchy-Davenport , que recibe su nombre de 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${\displaystyle \mathbb {Z} /p\mathbb {Z} }$tenemos la desigualdad ^{[ 1 ] [ 2 ] [ 3 ]}

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

dónde${\displaystyle A+B:=\{a+b{\pmod {p}}\mid a\in A,b\in B\}}$, es decir, utilizando aritmética modular . Se puede generalizar a grupos arbitrarios (no necesariamente abelianos) utilizando una transformada de Dyson . Si${\displaystyle A,B}$son subconjuntos de un grupo${\displaystyle G}$, entonces ^{[ 4 ]}

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

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

Esto se puede utilizar para deducir el teorema de Erdős–Ginzburg–Ziv : dada cualquier secuencia de 2 n −1 elementos en el grupo cíclico${\displaystyle \mathbb {Z} /n\mathbb {Z} }$, 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 no nulos, no necesariamente distintos, de${\displaystyle \mathbb {Z} /p\mathbb {Z} }$, cada elemento de${\displaystyle \mathbb {Z} /p\mathbb {Z} }$puede escribirse como la suma de los elementos de alguna subsecuencia (posiblemente vacía) de S . ^{[ 7 ]}

El teorema de Kneser generaliza esto a grupos abelianos generales . ^{[ 8 ]}

La conjetura de Erdős-Heilbronn planteada por Paul Erdős y Hans Heilbronn en 1964 afirma que${\displaystyle |2^{\wedge }A|\geq \min\{p,\,2|A|-3\}}$si p es un primo y A es un subconjunto no vacío del campo 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 |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 cotas inferiores para cardinalidades de varios conjuntos suma restringidos es el siguiente principio fundamental: el Nullstellensatz combinatorio . ^{[ 14 ]} Sea${\displaystyle f(x_{1},\ldots ,x_{n})}$sea ​​un polinomio sobre un cuerpo${\displaystyle F}$. Supongamos que el coeficiente del monomio${\displaystyle x_{1}^{k_{1}}\cdots x_{n}^{k_{n}}}$en${\displaystyle f(x_{1},\ldots ,x_{n})}$es distinto de cero y${\displaystyle k_{1}+\cdots +k_{n}}$es el grado total de${\displaystyle f(x_{1},\ldots ,x_{n})}$. Si${\displaystyle A_{1},\ldots ,A_{n}}$son subconjuntos finitos de${\displaystyle F}$con${\displaystyle |A_{i}|>k_{i}}$para${\displaystyle i=1,\ldots ,n}$, entonces hay${\displaystyle a_{1}\in A_{1},\ldots ,a_{n}\in A_{n}}$de tal manera que${\displaystyle f(a_{1},\ldots ,a_{n})\neq 0}$.

Esta herramienta se originó 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 aditiva de números: problemas inversos y geometría de conjuntos suma . 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 .