Combinatoria aditiva

La combinatoria aditiva es un área de la combinatoria en matemáticas. Un área importante de estudio en la combinatoria aditiva son los problemas inversos : dado que el tamaño del conjunto suma A  +  B es pequeño, ¿qué podemos decir acerca de las estructuras de y ? En el caso de los números enteros, el teorema clásico de Freiman proporciona una respuesta parcial a esta pregunta en términos de progresiones aritméticas multidimensionales . ${\estilo de visualización A}$${\estilo de visualización B}$

Otro problema típico es encontrar un límite inferior para en términos de y . Esto puede verse como un problema inverso con la información dada que es suficientemente pequeña y la conclusión estructural es entonces de la forma que o es el conjunto vacío; sin embargo, en la literatura, tales problemas a veces también se consideran problemas directos. Los ejemplos de este tipo incluyen la conjetura de Erdős-Heilbronn (para un conjunto suma restringido ) y el teorema de Cauchy-Davenport . Los métodos utilizados para abordar tales preguntas a menudo provienen de muchos campos diferentes de las matemáticas, incluyendo la combinatoria , la teoría ergódica , el análisis , la teoría de grafos , la teoría de grupos y los métodos algebraicos y polinómicos lineales . ${\estilo de visualización |A+B|}$${\displaystyle |A|}$${\estilo de visualización |B|}$${\estilo de visualización |A+B|}$${\estilo de visualización A}$${\estilo de visualización B}$

Aunque la combinatoria aditiva es una rama bastante nueva de la combinatoria (de hecho, el término combinatoria aditiva fue acuñado por Terence Tao y Van H. Vu en su libro en la década de 2000), un problema extremadamente antiguo, el teorema de Cauchy-Davenport, es uno de los resultados más fundamentales en este campo.

Supongamos que A y B son subconjuntos finitos del grupo cíclico para un primo , entonces se cumple la siguiente desigualdad. ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$${\estilo de visualización p}$

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

Ahora que tenemos la desigualdad para la cardinalidad del conjunto suma , es natural plantear el problema inverso, es decir, ¿bajo qué condiciones en y se cumple la igualdad? El teorema de Vosper responde a esta pregunta. Supongamos que (es decir, salvo casos extremos) y $Estilo de visualización A+B$${\estilo de visualización A}$${\estilo de visualización B}$${\displaystyle |A|,|B|\geq 2}$

${\displaystyle |A+B|\leq |A|+|B|-1\leq p-2,}$

Entonces y son progresiones aritméticas con la misma diferencia. Esto ilustra las estructuras que se estudian a menudo en combinatoria aditiva: la estructura combinatoria de en comparación con la estructura algebraica de las progresiones aritméticas. ${\estilo de visualización A}$${\estilo de visualización B}$$Estilo de visualización A+B$

Un teorema útil en combinatoria aditiva es la desigualdad de Plünnecke-Ruzsa . Este teorema proporciona un límite superior para la cardinalidad de en términos de la constante de duplicación de . Por ejemplo, utilizando la desigualdad de Plünnecke-Ruzsa, podemos demostrar una versión del teorema de Freiman en cuerpos finitos. ${\displaystyle |nA-mA|}$${\estilo de visualización A}$

Sean A y B subconjuntos finitos de un grupo abeliano, entonces el conjunto suma se define como

${\displaystyle A+B=\{a+b:a\en A,b\en B\}.}$

Por ejemplo, podemos escribir . De manera similar, podemos definir el conjunto de diferencias de A y B como ${\displaystyle \{1,2,3,4\}+\{1,2,3\}=\{2,3,4,5,6,7\}}$

${\displaystyle AB=\{ab:a\en A,b\en B\}.}$

Aquí proporcionamos otras notaciones útiles.

${\displaystyle kA=\underbrace {A+A+\cdots +A} _{k{\text{ términos }}}=\{a_{1}+\cdots +a_{k}:a_{1}\en A,\dots ,a_{k}\en A\}.}$

No debe confundirse con

${\displaystyle k\cdot A=\{ka:a\en A\}}$

Sea A un subconjunto de un grupo abeliano. La constante de duplicación mide cuán grande es el conjunto suma en comparación con su tamaño original | A |. Definimos la constante de duplicación de A como ${\estilo de visualización |A+A|}$

${\displaystyle K={\dfrac {|A+A|}{|A|}}.}$

Sean A y B dos subconjuntos de un grupo abeliano. Definimos la distancia de Ruzsa entre estos dos conjuntos como la cantidad

${\displaystyle d(A,B)=\log {\dfrac {|AB|}{\sqrt {|A||B|}}}.}$

La desigualdad triangular de Ruzsa nos dice que la distancia de Ruzsa obedece a la desigualdad triangular:

${\displaystyle d(B,C)\leq d(A,B)+d(A,C).}$

Sin embargo, como no puede ser cero, tenga en cuenta que la distancia de Ruzsa no es en realidad una métrica. ${\displaystyle d(A,A)}$

• Combinatoria aritmética
• Teoría de números aditivos

• Tao, T., y Vu, V. (2012). Combinatoria aditiva . Cambridge: Cambridge University Press.
• Green, B. (15 de enero de 2009). Reseña del libro Combinatoria Aditiva. Recuperado de https://www.ams.org/journals/bull/2009-46-03/S0273-0979-09-01231-2/S0273-0979-09-01231-2.pdf.