Неравенство треугольника Ружи

В аддитивной комбинаторике неравенство треугольника Рузсы , также известное как неравенство разностного треугольника Рузсы , чтобы отличать его от некоторых его вариантов, ограничивает размер разницы двух наборов с точки зрения размеров обоих их различий с третьим набором. Это было доказано Имре Рузой (1996), и названо так из-за сходства с неравенством треугольника . Это важная лемма в доказательстве неравенства Плюнеке-Рузы .

Заявление

Если $A$ и $B$ являются подмножествами группы , то суммы обозначение $A+B$ используется для обозначения $\{a+b:a\in A,b\in B\}$. Сходным образом, $A-B$ обозначает $\{a-b:a\in A,b\in B\}$. Тогда неравенство треугольника Рузсы утверждает следующее.

Теорема   (неравенство треугольника Рузсы) — Если $A$, $B$, и $C$ являются конечными подмножествами группы, то

$|A||B-C|\leq |A-B||A-C|.$

Альтернативная формулировка включает понятие расстояния Ружи .

Определение . Если $A$ и $B$ являются конечными подмножествами группы, то расстояние Ружи между этими двумя множествами обозначается $d(A,B)$, определяется как

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

Тогда неравенство треугольника Рузсы имеет следующую эквивалентную формулировку:

Теорема   (неравенство треугольника Рузсы) — Если $A$, $B$, и $C$ являются конечными подмножествами группы, то

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

Эта формулировка напоминает неравенство треугольника для метрического пространства ; однако расстояние Ружи не определяет метрическое пространство, поскольку $d(A,A)$ не всегда равен нулю.

Доказательство

Для доказательства утверждения достаточно построить инъекцию из множества $A\times (B-C)$ на съемочную площадку $(A-B)\times (A-C)$. Определить функцию $\phi$ следующее. Для каждого $x\in B-C$ выбрать $b(x)\in B$ и $c(x)\in C$ такой, что $x=b(x)-c(x)$. По определению $B-C$, это всегда можно сделать. Позволять $\phi :A\times (B-C)\rightarrow (A-B)\times (A-C)$ быть функцией, которая отправляет $(a,x)$ к $(a-b(x),a-c(x))$. Для каждой точки $\phi (a,x)=(y,z)$ в наборе есть $(A-B)\times (A-C)$, должно быть так, что $x=z-y$ и $a=y+b(x)$. Следовательно, $\phi$ отображает каждую точку в $A\times (B-C)$ в определенную точку в $(A-B)\times (A-C)$ и, таким образом, является инъекцией. В частности, должно быть как минимум столько же точек в $(A-B)\times (A-C)$ как в $A\times (B-C)$. Поэтому,

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

завершение доказательства.

Варианты неравенства треугольника Рузсы

Неравенство треугольника суммы Ружи является следствием неравенства Плюннеке-Ружи (которое, в свою очередь, доказывается с помощью обычного неравенства треугольника Ружи).

Теорема   (неравенство треугольника суммы Рузсы) — Если $A$, $B$, и $C$ являются конечными подмножествами абелевой группы, то

$|A||B+C|\leq |A+B||A+C|.$

Доказательство . В доказательстве используется следующая лемма из доказательства неравенства Плюннеке-Ружи .

Лемма . Позволять $A$ и $B$ — конечные подмножества абелевой группы $G$. Если $X\subseteq A$ является непустым подмножеством, которое минимизирует значение $K'=|X+B|/|X|$, то для всех конечных подмножеств $C\subset G,$

$|X+B+C|\leq K'|X+C|.$

Если $A$ — пустое множество, то левая часть неравенства принимает вид $0$, поэтому неравенство верно. В противном случае, пусть $X$ быть подмножеством $A$ что сводит к минимуму $K'=|X+B|/|X|$. Позволять $K=|A+B|/|A|$. Определение $X$ подразумевает, что $K'\leq K.$ Потому что $X\subset A$, применение приведенной выше леммы дает

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

Перестановка дает неравенство треугольника суммы Рузсы.

Заменив $B$ и $C$ в неравенстве треугольника Рузсы и неравенстве треугольника суммы Рузсы с $-B$ и $-C$ при необходимости можно получить более общий результат: если $A$, $B$, и $C$ являются конечными подмножествами абелевой группы, то

$|A||B\pm C|\leq |A\pm B||A\pm C|,$

где выполняются все восемь возможных конфигураций знаков. Эти результаты также иногда известны под общим названием « неравенства треугольника Рузсы» .