Nerovnost trojúhelníku Ruzsa - Ruzsa triangle inequality - Wikipedia

v aditivní kombinatorika, Nerovnost trojúhelníku Ruzsa, také známý jako Neruznost rozdílu trojúhelník nerovnost odlišit to od některých jeho variant, ohraničuje velikost rozdílu dvou sad z hlediska velikostí obou jejich rozdílů s třetí sadou. Bylo prokázáno Imre Ruzsa (1996),^[1] a je tak pojmenován pro svou podobnost s nerovnost trojúhelníku. Je to důležité lemma v důkazu Nerovnost Plünnecke-Ruzsa.

Prohlášení

Li ${ displaystyle A}$ a ${ displaystyle B}$ jsou podmnožiny souboru abelianská skupina, pak souprava notace ${ displaystyle A + B}$ se používá k označení ${ displaystyle {a + b: a v A, b v B }}$. Podobně, ${ displaystyle A-B}$ označuje ${ displaystyle {a-b: a v A, b v B }}$. Potom nerovnost trojúhelníku Ruzsa uvádí následující.

Alternativní formulace zahrnuje pojem Ruzsova vzdálenost.^[2]

Definice. Li ${ displaystyle A}$ a ${ displaystyle B}$ jsou konečné podmnožiny abelianské skupiny, pak Ruzsova vzdálenost mezi těmito dvěma sadami, označené ${ displaystyle d (A, B)}$, je definován jako

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

Potom má nerovnost trojúhelníku Ruzsa následující ekvivalentní formulaci:

Tato formulace připomíná nerovnost trojúhelníku pro a metrický prostor; vzdálenost Ruzsa však od té doby nedefinuje metrický prostor ${ displaystyle d (A, A)}$ není vždy nula.

Důkaz

K prokázání tvrzení stačí postavit injekci ze sady ${ displaystyle A krát (B-C)}$ do sady ${ displaystyle (A-B) krát (A-C)}$. Definujte funkci ${ displaystyle phi}$ jak následuje. Pro každého ${ displaystyle x v B-C}$ vyber ${ displaystyle b (x) v B}$ a a ${ displaystyle c (x) v C}$ takhle ${ displaystyle x = b (x) -c (x)}$. Podle definice ${ displaystyle B-C}$, to lze vždy udělat. Nechat ${ displaystyle phi: A krát (B-C) pravá šipka (A-B) krát (A-C)}$ být funkce, která odesílá ${ displaystyle (a, x)}$ na ${ displaystyle (a-b (x), a-c (x))}$. Za každý bod ${ displaystyle phi (a, x) = (y, z)}$ v sadě je ${ displaystyle (A-B) krát (A-C)}$, musí tomu tak být ${ displaystyle x = z-y}$ a ${ displaystyle a = y + b (x)}$. Proto, ${ displaystyle phi}$ mapuje každý bod ${ displaystyle A krát (B-C)}$ do odlišného bodu v ${ displaystyle (A-B) krát (A-C)}$ a je tedy injekcí. Zejména musí být alespoň tolik bodů v ${ displaystyle (A-B) krát (A-C)}$ jako v ${ displaystyle A krát (B-C)}$. Proto,

${ displaystyle | A || B-C | = | A krát (B-C) | leq | (A-B) krát (A-C) | = | A-B || A-C |,}$

vyplňování důkazu.

Varianty nerovnosti trojúhelníku Ruzsa

The Nerovnost součtu trojúhelníku Ruzsa je důsledkem nerovnosti Plünnecke-Ruzsa (což je zase prokázáno pomocí běžné nerovnosti trojúhelníku Ruzsa).

Důkaz. Důkaz používá následující lemma z důkaz nerovnosti Plünnecke-Ruzsa.

Lemma. Nechat ${ displaystyle A}$ a ${ displaystyle B}$ být konečné podmnožiny abelianské skupiny ${ displaystyle G}$. Li ${ displaystyle X subseteq A}$ je neprázdná podmnožina, která minimalizuje hodnotu ${ displaystyle K '= | X + B | / | X |}$, pak pro všechny konečné podmnožiny ${ displaystyle C podmnožina G,}$

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

Li ${ displaystyle A}$ je prázdná množina, pak se stane levá strana nerovnosti ${ displaystyle 0}$, takže nerovnost je pravdivá. Jinak nechte ${ displaystyle X}$ být podmnožinou ${ displaystyle A}$ který minimalizuje ${ displaystyle K '= | X + B | / | X |}$. Nechat ${ displaystyle K = | A + B | / | A |}$. Definice ${ displaystyle X}$ to naznačuje ${ displaystyle K ' leq K.}$ Protože ${ displaystyle X podmnožina A}$, použití výše uvedeného lematu dává

${ 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 |}}.}$

Přeskupení dává nerovnost součtu trojúhelníku Ruzsa.

Výměnou ${ displaystyle B}$ a ${ displaystyle C}$ v nerovnosti trojúhelníku Ruzsa a nerovnosti trojúhelníku Ruzsa s ${ displaystyle -B}$ a ${ displaystyle -C}$ podle potřeby lze dosáhnout obecnějšího výsledku: Pokud ${ displaystyle A}$, ${ displaystyle B}$, a ${ displaystyle C}$ jsou tedy konečné podmnožiny abelianské skupiny

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

kde drží všech osm možných konfigurací značek. Tyto výsledky jsou také někdy souhrnně označovány jako Nerovnosti trojúhelníku Ruzsa.

Reference