En combinatoria aditiva , la desigualdad del triángulo de Ruzsa , también conocida como desigualdad del triángulo de diferencias 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 ambas diferencias con un tercer conjunto. Fue probado por Imre Ruzsa (1996), [1] y se llama así por su parecido con la desigualdad del triángulo . Es un lema importante en la demostración de la desigualdad de Plünnecke-Ruzsa .
Declaración
Si y son subconjuntos de un grupo abeliano , entonces la notación de suma se usa para denotar . Similar, denota . Entonces, la desigualdad del triángulo de Ruzsa establece lo siguiente.
Teorema (desigualdad del triángulo de Ruzsa) - Si, , y son subconjuntos finitos de un grupo abeliano, entonces
Una formulación alternativa implica la noción de distancia de Ruzsa . [2]
Definición . Si y son subconjuntos finitos de un grupo abeliano, entonces la distancia de Ruzsa entre estos dos conjuntos, denotada, se define como
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 abeliano, entonces
Esta formulación se asemeja a la desigualdad del triángulo para un espacio métrico ; sin embargo, la distancia de Ruzsa no define un espacio métrico ya que no siempre es cero.
Prueba
Para probar el enunciado, basta con construir una inyección a partir del conjunto al set . Definir una funcióncomo sigue. Para cada escoge un y un tal que . Por la definición de, esto siempre se puede hacer. Dejar ser la función que envía a . Por cada punto en el set es , debe ser el caso que y . Por eso, mapea 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,
completando la prueba.
Variantes de la desigualdad del triángulo de Ruzsa
La desigualdad del triángulo de 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 triángulo de suma de Ruzsa) - Si, , y son subconjuntos finitos de un grupo abeliano, entonces
Prueba . La prueba usa el siguiente lema de la prueba de la desigualdad de Plünnecke-Ruzsa .
Lema . Dejar y ser subconjuntos finitos de un grupo abeliano . Si es un subconjunto no vacío que minimiza el valor de , luego para todos los subconjuntos finitos
Si es el conjunto vacío, entonces el lado izquierdo de la desigualdad se convierte en , entonces la desigualdad es verdadera. De lo contrario, deja ser un subconjunto de que minimiza . Dejar. La definición de implica que Porque , la aplicación del lema anterior da
El reordenamiento da la desigualdad del triángulo de suma de Ruzsa.
Por reemplazo y en la desigualdad del triángulo de Ruzsa y la desigualdad del triángulo de suma de Ruzsa con y según sea necesario, se puede obtener un resultado más general: Si , , y son subconjuntos finitos de un grupo abeliano entonces
donde se mantienen las ocho configuraciones posibles de señales. Estos resultados también se conocen a veces colectivamente como las desigualdades del triángulo de Ruzsa .