Combinatoria aditiva

Área de combinatoria en matemáticas

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 . ${\displaystyle A}$ ${\displaystyle 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 . ${\displaystyle |A+B|}$ ${\displaystyle |A|}$ ${\displaystyle |B|}$ ${\displaystyle |A+B|}$ ${\displaystyle A}$ ${\displaystyle B}$

Historia de la combinatoria aditiva

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.

Teorema de Cauchy-Davenport

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} }$ ${\displaystyle p}$

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

Teorema de Vosper

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 ${\displaystyle A+B}$ ${\displaystyle A}$ ${\displaystyle 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. ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A+B}$

Desigualdad de Plünnecke-Ruzsa

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|}$ ${\displaystyle A}$

Nociones básicas

Operaciones sobre conjuntos

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

${\displaystyle A+B=\{a+b:a\in A,b\in 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 A-B=\{a-b:a\in A,b\in B\}.}$

Aquí proporcionamos otras notaciones útiles.

${\displaystyle kA=\underbrace {A+A+\cdots +A} _{k{\text{ terms }}}=\{a_{1}+\cdots +a_{k}:a_{1}\in A,\dots ,a_{k}\in A\}.}$

No debe confundirse con

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

Constante de duplicación

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 ${\displaystyle |A+A|}$

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

Distancia de Ruzsa

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 {|A-B|}{\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)}$

Véase también

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

Referencias

Citas

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