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 sobre las estructuras de $A$ y $B$ ? 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 .

Otro problema típico consiste en hallar una cota inferior para $| A + B |$ en función de $| A |$ y $| B |$ . Esto puede considerarse un problema inverso, dado que $| A + B |$ es suficientemente pequeño, y la conclusión estructural es que $A$ o $B$ es el conjunto vacío. Sin embargo, en la literatura, estos problemas también se consideran a veces problemas directos. 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 estas cuestiones suelen provenir de diversos campos de las matemáticas, como 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 lineales y polinomiales.

Historia de la combinatoria aditiva

Aunque la combinatoria aditiva es una rama relativamente nueva de la combinatoria (el término combinatoria aditiva fue acuñado por Terence Tao y Van H. Vu en su libro homónimo de 2006), un problema mucho más 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 $ℤ / p ℤ$ para un primo $p$ , entonces se cumple la siguiente desigualdad.

|A+B|\geq \min(|A|+|B|-1,p)

Teorema de Vosper

Ahora que tenemos la desigualdad para la cardinalidad del conjunto suma $A + B$ , es natural plantear el problema inverso, es decir, ¿bajo qué condiciones sobre $A$ y $B$ se cumple la igualdad? El teorema de Vosper responde a esta pregunta. Supongamos que $| A |, | B | \geq 2$ (es decir, salvo casos límite) y

|A+B|\leq |A|+|B|-1\leq p-2,

Entonces, $A$ y $B$ son progresiones aritméticas con la misma diferencia. Esto ilustra las estructuras que se estudian frecuentemente en combinatoria aditiva: la estructura combinatoria de $A + B$ en comparación con la estructura algebraica de las progresiones aritméticas.

Desigualdad de Plünnecke-Ruzsa

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

nociones básicas

Operaciones en platós

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

A+B=\{a+b:a\in A,b\in B\}.

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

AB=\{ab:a\in A,b\in B\}.

El conjunto suma $k$ -ésimo del conjunto $A$ consigo mismo se denota por

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

que no debe confundirse con

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. $|A+A|$ se compara con su tamaño original $| A |$ . Definimos la constante de duplicación de $A$ como

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

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

La desigualdad triangular de Ruzsa afirma que la distancia de Ruzsa obedece la desigualdad triangular:

d(B,C)\leq d(A,B)+d(A,C).

Sin embargo, dado que $d (A, A)$ no puede ser cero, la distancia de Ruzsa no es realmente una métrica .

Véase también

Referencias

Citas

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