Неравенство Плюннеке – Ружи - Plünnecke–Ruzsa inequality

В аддитивная комбинаторика, то Неравенство Плюннеке-Ружи является неравенством, ограничивающим размер различных суммы набора ${ displaystyle B}$, учитывая, что есть другой набор ${ displaystyle A}$ так что ${ displaystyle A + B}$ не намного больше, чем ${ displaystyle A}$. Немного более слабая версия этого неравенства была первоначально доказана и опубликована Гельмутом Плюннеке (1970).^[1]Имре Ружа (1989)^[2] позже опубликовал более простое доказательство текущего, более общего, варианта неравенства. Неравенство является важным шагом в доказательстве Теорема Фреймана.

Заявление

Следующее сумма обозначение является стандартным в аддитивной комбинаторике. Для подмножеств ${ displaystyle A}$ и ${ displaystyle B}$ из абелева группа и натуральное число ${ displaystyle k}$, определены:

• ${ displaystyle A + B = {a + b: a in A, b in B }}$
• ${ Displaystyle A-B = {a-b: a in A, b in B }}$
• ${ displaystyle kA = underbrace {A + A + cdots + A} _ {k { text {times}}}}$

Набор ${ displaystyle A + B}$ известен как сумма из ${ displaystyle A}$ и ${ displaystyle B}$.

Неравенство Плюннеке-Ружи

Наиболее часто цитируемая версия утверждения неравенства Плюннеке-Ружи заключается в следующем.^[3]

Это часто используется, когда ${ displaystyle A = B}$, в этом случае постоянная ${ Displaystyle K = | 2A | / | A |}$ известен как константа удвоения из ${ displaystyle A}$. В этом случае неравенство Плюннеке-Ружа утверждает, что суммы, сформированные из набора с малой константой удвоения, также должны быть малыми.

Неравенство Плюннеке

Версия этого неравенства, первоначально доказанная Плюннеке (1970)^[1] немного слабее.

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

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

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

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

Следующее простое доказательство неравенства Плюннеке-Ружа принадлежит Петридису (2014).^[4]

Лемма: Позволять ${ displaystyle A}$ и ${ displaystyle B}$ - конечные подмножества абелевой группы ${ displaystyle G}$. Если ${ Displaystyle X substeq A}$ непустое подмножество, которое минимизирует значение ${ Displaystyle K '= | X + B | / | X |}$, то для всех конечных подмножеств ${ Displaystyle C подмножество G}$,

${ Displaystyle | Икс + В + С | leq К '| Х + С |.}$

Доказательство: Это демонстрируется индукцией по размеру ${ displaystyle | C |}$. Для базового случая ${ displaystyle | C | = 1}$, Обратите внимание, что ${ Displaystyle S + C}$ это просто перевод ${ displaystyle S}$ для любого ${ Displaystyle S substeq G}$, так

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

Для индуктивного шага предположим, что неравенство выполнено для всех ${ Displaystyle C substeq G}$ с ${ displaystyle | C | leq n}$ для некоторого положительного целого числа ${ displaystyle n}$. Позволять ${ displaystyle C}$ быть подмножеством ${ displaystyle G}$ с ${ displaystyle | C | = n + 1}$, и разреши ${ Displaystyle С = С ' sqcup { gamma }}$ для некоторых ${ displaystyle gamma in C}$. (В частности, неравенство выполняется для ${ displaystyle C '}$.) Наконец, пусть ${ displaystyle Z = {x in X: x + B + { gamma } substeq X + B + C '}}$. Определение ${ displaystyle Z}$ подразумевает, что ${ Displaystyle Z + B + { gamma } substeq X + B + C '}$. Таким образом, по определению этих множеств,

${ displaystyle X + B + C = (X + B + C ') cup ((X + B + { gamma }) backslash (Z + B + { gamma })).}$

Следовательно, учитывая размеры наборов,

${ displaystyle { begin {align} | X + B + C | & leq | X + B + C '| + | (X + B + { gamma }) обратная косая черта (Z + B + { gamma }) | & = | X + B + C '| + | X + B + { gamma } | - | Z + B + { gamma } | & = | X + B + C '| + | X + B | - | Z + B |. End {выравнивается}}}$

Определение ${ displaystyle Z}$ подразумевает, что ${ Displaystyle Z substeq X substeq A}$, поэтому по определению ${ displaystyle X}$, ${ Displaystyle | Z + B | geq K '| Z |}$. Таким образом, применяя индуктивную гипотезу к ${ displaystyle C '}$ и используя определение ${ displaystyle X}$,

${ displaystyle { begin {align} | X + B + C | & leq | X + B + C '| + | X + B | - | Z + B | & leq K' | X + C '| + | X + B | - | Z + B | & leq K' | X + C '| + K' | X | - | Z + B | & leq K '| X + C '| + K' | X | -K '| Z | & = K' (| X + C '| + | X | - | Z |). End {выравнивается}}}$

Чтобы ограничить правую часть этого неравенства, пусть ${ Displaystyle W = {x in X: x + gamma in X + C '}}$. Предполагать ${ displaystyle y in X + C '}$ и ${ Displaystyle у в Икс + { гамма }}$, то существует ${ displaystyle x in X}$ такой, что ${ Displaystyle х + гамма = у в X + C '}$. Таким образом, по определению ${ displaystyle x in W}$, так ${ Displaystyle у в W + { gamma }}$. Следовательно, множества ${ displaystyle X + C '}$ и ${ Displaystyle (Икс + { gamma }) обратная косая черта (W + { gamma })}$ не пересекаются. Определения ${ displaystyle W}$ и ${ displaystyle C '}$ таким образом подразумевают, что

${ displaystyle X + C = (X + C ') sqcup ((X + { gamma }) backslash (W + { gamma })).}$

Опять же по определению ${ Displaystyle W substeq Z}$, так ${ Displaystyle | W | leq | Z |}$. Следовательно,

${ displaystyle { begin {align} | X + C | & = | X + C '| + | (X + { gamma }) обратная косая черта (W + { gamma }) | & = | X + C '| + | X + { gamma } | - | W + { gamma } | & = | X + C' | + | X | - | W | & geq | X + C '| + | X | - | Z |. End {align}}}$

Объединение двух приведенных выше неравенств дает

${ Displaystyle | Икс + В + С | leq K '(| X + C' | + | X | - | Z |) leq K '| X + C |.}$

Это завершает доказательство леммы.

Чтобы доказать неравенство Плюннеке-Ружи, возьмем ${ displaystyle X}$ и ${ displaystyle K '}$ как в формулировке леммы. Прежде всего необходимо показать, что

${ displaystyle | X + nB | leq K ^ {n} | X |.}$

Это можно доказать по индукции. Для базового случая определения ${ displaystyle K}$ и ${ displaystyle K '}$ подразумевают, что ${ displaystyle K ' leq K}$. Таким образом, определение ${ displaystyle X}$ подразумевает, что ${ Displaystyle | Х + В | leq К | Х |}$. Для индуктивного шага предположим, что это верно для ${ displaystyle n = j}$. Применяя лемму с ${ Displaystyle C = jB}$ и индуктивная гипотеза дает

${ Displaystyle | Икс + (J + 1) B | Leq K '| X + JB | Leq K | X + JB | Leq K ^ {j + 1} | X |.}$

На этом индукция завершена. Наконец, неравенство треугольника Ружи дает

${ Displaystyle | mB-nB | leq { frac {| X + mB || X + nB |} {| X |}} leq { frac {K ^ {m} | X | K ^ {n} | X |} {| X |}} = K ^ {m + n} | X |.}$

Потому что ${ Displaystyle X substeq A}$, должно быть так, что ${ displaystyle | X | leq | A |}$. Следовательно,

${ Displaystyle | mB-nB | leq K ^ {m + n} | A |.}$

Это завершает доказательство неравенства Плюннеке-Ружи.

Графики Плюнеке

И доказательство Плуннеке неравенства Плюннеке, и оригинальное доказательство неравенства Плюннеке-Ружа Ружей используют метод графов Плюннеке. Графы Плюнеке - это способ уловить аддитивную структуру множеств ${ Displaystyle А, А + В, А + 2В, точки}$ теоретически^[5][6] Первым важным для определения графов Плюннеке является понятие коммутативного графа.

Определение. А ориентированный граф ${ displaystyle G}$ называется полукоммутативный если, когда существуют различные ${ displaystyle x, y, z_ {1}, z_ {2}, dots, z_ {k}}$ такой, что ${ Displaystyle (х, у)}$ и ${ Displaystyle (у, z_ {я})}$ края в ${ displaystyle G}$ для каждого ${ displaystyle i}$, то существуют также различные ${ displaystyle y_ {1}, y_ {2}, dots, y_ {k}}$ так что ${ Displaystyle (х, y_ {я})}$ и ${ displaystyle (y_ {i}, z_ {i})}$ края в ${ displaystyle G}$ для каждого ${ displaystyle i}$. ${ displaystyle G}$ называется коммутативный если он полукоммутативен и граф, образованный обращением всех его ребер, также является полукоммутативным.

Теперь граф Плюнеке определяется следующим образом.

Определение. А слоистый граф является (ориентированным) графом ${ displaystyle G}$ чье множество вершин можно разбить ${ Displaystyle V_ {0} чашка V_ {1} чашка точки чашка V_ {m}}$ так что все края в ${ displaystyle G}$ из ${ displaystyle V_ {i}}$ к ${ Displaystyle V_ {я + 1}}$, для некоторых ${ displaystyle i}$. А График Плюнеке является слоистым графом, который коммутативен.

Соответствующий пример графа Плюннеке следующий, показывающий, как структура множеств ${ displaystyle A, A + B, A + 2B, dots, A + mB}$ является случаем графа Плюнеке.

Пример. Позволять ${ displaystyle A, B}$ - подмножества абелевой группы. Тогда пусть ${ displaystyle G}$ быть слоистым графом так, чтобы каждый слой ${ displaystyle V_ {j}}$ это копия ${ displaystyle A + jB}$, так что ${ displaystyle V_ {0} = A}$, ${ Displaystyle V_ {1} = А + В}$, ..., ${ displaystyle V_ {m} = A + mB}$. Создайте край ${ Displaystyle (х, у)}$ (куда ${ Displaystyle х в V_ {я}}$ и ${ Displaystyle у в V_ {я + 1}}$) всякий раз, когда существует ${ displaystyle b in B}$ такой, что ${ displaystyle y = x + b}$. (В частности, если ${ Displaystyle х в V_ {я}}$, тогда ${ Displaystyle х + Ь в V_ {я + 1}}$ по определению, поэтому каждая вершина имеет превосходить равный размеру ${ displaystyle B}$.) Потом ${ displaystyle G}$ является графом Плюнеке. Например, чтобы проверить, что ${ displaystyle G}$ полукоммутативно, если ${ Displaystyle (х, у)}$ и ${ Displaystyle (у, z_ {я})}$ края в ${ displaystyle G}$ для каждого ${ displaystyle i}$, тогда ${ displaystyle y-x, z_ {i} -y in B}$. Тогда пусть ${ displaystyle y_ {i} = x + z_ {i} -y}$, так что ${ displaystyle y_ {i} -x = z_ {i} -y in B}$ и ${ displaystyle z_ {i} -y_ {i} = y-x in B}$. Таким образом, ${ displaystyle G}$ полукоммутативно. Аналогично можно проверить, что граф, образованный обращением всех ребер ${ displaystyle G}$ также полукоммутативен, поэтому ${ displaystyle G}$ является графом Плюнеке.

В графе Плюнеке изображение набора ${ displaystyle X substeq V_ {0}}$ в ${ displaystyle V_ {j}}$, написано ${ displaystyle { text {im}} (X, V_ {j})}$, определяется как множество вершин в ${ displaystyle V_ {j}}$ которого можно достичь путем, начиная с некоторой вершины в ${ displaystyle X}$. В частности, в вышеупомянутом примере ${ displaystyle { text {im}} (X, V_ {j})}$ просто ${ displaystyle X + jB}$.

В коэффициент увеличения между ${ displaystyle V_ {0}}$ и ${ displaystyle V_ {j}}$, обозначенный ${ displaystyle mu _ {j} (G)}$, затем определяется как минимальный коэффициент, на который изображение набора должно превышать размер исходного набора. Формально,

${ displaystyle mu _ {j} (G) = min _ {X substeq V_ {0}, X neq emptyset} { frac {| { text {im}} (X, V_ {j}) ) |} {| X |}}.}$

Теорема Плюнеке - это следующее утверждение о графах Плюнеке.

Доказательство теоремы Плюннеке включает в себя технику, известную как «трюк с тензорным произведением», в дополнение к применению Теорема Менгера.^[5]

Неравенство Плюннеке-Ружи является довольно прямым следствием теоремы Плюнеке и неравенства треугольника Ружи. Применяя теорему Плюннеке к графу, приведенному в примере, на ${ displaystyle j = m}$ и ${ displaystyle j = 1}$, получаем, что если ${ displaystyle | A + B | / | A | = K}$, то существует ${ Displaystyle X substeq A}$ так что ${ Displaystyle | X + mB | / | X | leq K ^ {m}}$. Применяя этот результат еще раз с ${ displaystyle X}$ вместо ${ displaystyle A}$, Существует ${ Displaystyle X ' substeq X}$ так что ${ Displaystyle | X '+ nB | / | X' | leq K ^ {m}}$. Тогда по неравенству треугольника Ружи (на ${ displaystyle -X ', mB, nB}$),

${ displaystyle | mB-nB | leq | X '+ mB || X' + nB || X '| leq K ^ {m + n} | X | leq K ^ {m + n} | X | ,}$

тем самым доказывая неравенство Плюннеке-Ружи.

Смотрите также

• Аддитивная комбинаторика
• Теорема Фреймана
• Неравенство треугольника Ружи

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