Неравенство треугольника Ружи - Ruzsa triangle inequality - Wikipedia

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

Заявление

Если ${\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\}}$. Тогда неравенство треугольника Ружи утверждает следующее.

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

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

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

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

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

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

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

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

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

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

Для доказательства утверждения достаточно построить инъекцию по множеству ${\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|,}$

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

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

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

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

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

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

Лемма. Позволять ${\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|.}$

Если ${\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|}}.}$

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

Заменив ${\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|,}$

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

Рекомендации

1. Ружа, И. (1996). «Суммы конечных множеств». Теория чисел: Нью-Йоркский семинар 1991-1995 гг..
2. Тао, Т .; Ву В. (2006). Аддитивная комбинаторика. Кембридж: Издательство Кембриджского университета. ISBN  978-0-521-85386-6.