Desigualdad del triángulo de Ruzsa

En combinatoria aditiva , la desigualdad triangular de Ruzsa , también conocida como desigualdad triangular diferencial de Ruzsa para diferenciarla de algunas de sus variantes, limita el tamaño de la diferencia de dos conjuntos en términos de los tamaños de sus diferencias con un tercer conjunto. Fue demostrada por Imre Ruzsa (1996), ^[1] y se llama así por su semejanza con la desigualdad triangular . Es un lema importante en la demostración de la desigualdad de Plünnecke-Ruzsa .

Declaración

Si y son subconjuntos de un grupo , entonces se utiliza la notación de suma para denotar . De manera similar, denota . Entonces, la desigualdad del triángulo de Ruzsa establece lo siguiente. ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A+B}$ ${\displaystyle \{a+b:a\in A,b\in B\}}$ ${\displaystyle A-B}$ ${\displaystyle \{a-b:a\in A,b\in B\}}$

Teorema  (desigualdad del triángulo de Ruzsa)  :  Si , y son subconjuntos finitos de un grupo, entonces ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle C}$

${\displaystyle |A||B-C|\leq |A-B||A-C|.}$

Una formulación alternativa implica el concepto de distancia de Ruzsa . ^[2]

Definición . Si y son subconjuntos finitos de un grupo, entonces la distancia de Ruzsa entre estos dos conjuntos, denotada , se define como ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle d(A,B)}$

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

Entonces, la desigualdad del triángulo de Ruzsa tiene la siguiente formulación equivalente:

Teorema  (desigualdad del triángulo de Ruzsa)  :  Si , y son subconjuntos finitos de un grupo, entonces ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle C}$

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

Esta formulación se asemeja a la desigualdad triangular para un espacio métrico ; sin embargo, la distancia de Ruzsa no define un espacio métrico ya que no siempre es cero. ${\displaystyle d(A,A)}$

Prueba

Para demostrar el enunciado, basta con construir una inyección del conjunto al conjunto . Definamos una función como sigue. Para cada uno elijamos a y a tales que . Por la definición de , esto siempre se puede hacer. Sea la función que envía a . Para cada punto del conjunto es , debe darse el caso de que y . Por lo tanto, asigna cada punto en a un punto distinto en y es, por tanto, una inyección. En particular, debe haber al menos tantos puntos en como en . Por lo tanto, ${\displaystyle A\times (B-C)}$ ${\displaystyle (A-B)\times (A-C)}$ ${\displaystyle \phi }$ ${\displaystyle x\in B-C}$ ${\displaystyle b(x)\in B}$ ${\displaystyle c(x)\in C}$ ${\displaystyle x=b(x)-c(x)}$ ${\displaystyle B-C}$ ${\displaystyle \phi :A\times (B-C)\rightarrow (A-B)\times (A-C)}$ ${\displaystyle (a,x)}$ ${\displaystyle (a-b(x),a-c(x))}$ ${\displaystyle \phi (a,x)=(y,z)}$ ${\displaystyle (A-B)\times (A-C)}$ ${\displaystyle x=z-y}$ ${\displaystyle a=y+b(x)}$ ${\displaystyle \phi }$ ${\displaystyle A\times (B-C)}$ ${\displaystyle (A-B)\times (A-C)}$ ${\displaystyle (A-B)\times (A-C)}$ ${\displaystyle A\times (B-C)}$

${\displaystyle |A||B-C|=|A\times (B-C)|\leq |(A-B)\times (A-C)|=|A-B||A-C|,}$

Completando la prueba.

Variantes de la desigualdad del triángulo de Ruzsa

La desigualdad del triángulo de la suma de Ruzsa es un corolario de la desigualdad de Plünnecke-Ruzsa (que a su vez se demuestra utilizando la desigualdad del triángulo de Ruzsa ordinaria).

Teorema  (desigualdad de suma de triángulos de Ruzsa)  :  Si , y son subconjuntos finitos de un grupo abeliano, entonces ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle C}$

${\displaystyle |A||B+C|\leq |A+B||A+C|.}$

Demostración . La demostración utiliza el siguiente lema de la demostración de la desigualdad de Plünnecke-Ruzsa .

Lema . Sean y subconjuntos finitos de un grupo abeliano . Si es un subconjunto no vacío que minimiza el valor de , entonces para todos los subconjuntos finitos ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle G}$ ${\displaystyle X\subseteq A}$ ${\displaystyle K'=|X+B|/|X|}$ ${\displaystyle C\subset G,}$

${\displaystyle |X+B+C|\leq K'|X+C|.}$

Si es el conjunto vacío, entonces el lado izquierdo de la desigualdad se convierte en , por lo que la desigualdad es verdadera. De lo contrario, sea un subconjunto de que minimiza . Sea . La definición de implica que Debido a que , al aplicar el lema anterior se obtiene ${\displaystyle A}$ ${\displaystyle 0}$ ${\displaystyle X}$ ${\displaystyle A}$ ${\displaystyle K'=|X+B|/|X|}$ ${\displaystyle K=|A+B|/|A|}$ ${\displaystyle X}$ ${\displaystyle K'\leq K.}$ ${\displaystyle X\subset A}$

${\displaystyle |B+C|\leq |X+B+C|\leq K'|X+C|\leq K'|A+C|\leq K|A+C|={\frac {|A+B||A+C|}{|A|}}.}$

Al reordenar se obtiene la desigualdad triangular de suma de Ruzsa.

Reemplazando y en la desigualdad del triángulo de Ruzsa y la desigualdad del triángulo de la suma de Ruzsa por y según sea necesario, se puede obtener un resultado más general: Si , , y son subconjuntos finitos de un grupo abeliano entonces ${\displaystyle B}$ ${\displaystyle C}$ ${\displaystyle -B}$ ${\displaystyle -C}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle C}$

${\displaystyle |A||B\pm C|\leq |A\pm B||A\pm C|,}$

donde se cumplen las ocho configuraciones posibles de signos. Estos resultados también se conocen a veces colectivamente como desigualdades del triángulo de Ruzsa .

Referencias

1. Ruzsa, I. (1996). "Sumas de conjuntos finitos". Teoría de números: Seminario de Nueva York 1991-1995 .
2. Tao, T.; Vu, V. (2006). Combinatoria aditiva . Cambridge: Cambridge University Press. ISBN 978-0-521-85386-6.