Теорема Фреймана - Википедия - Freimans theorem

В аддитивная комбинаторика, Теорема Фреймана - центральный результат, указывающий на приблизительную структуру множеств, сумма маленький. В нем примерно говорится, что если ${ displaystyle | A + A | / | A |}$ маленький, то ${ displaystyle A}$ может содержаться в небольшом обобщенная арифметическая прогрессия.

Заявление

Если ${ displaystyle A}$ конечное подмножество ${ Displaystyle mathbb {Z}}$ с ${ Displaystyle | А + А | leq К | А |}$, тогда ${ displaystyle A}$ содержится в обобщенной арифметической прогрессии размерности не более ${ displaystyle d (K)}$ и размер не больше ${ Displaystyle f (K) | A |}$, куда ${ displaystyle d (K)}$ и ${ displaystyle f (K)}$ константы, зависящие только от ${ displaystyle K}$.

Примеры

Для конечного множества ${ displaystyle A}$ целых чисел, всегда верно, что

${ Displaystyle | А + А | geq 2 | А | -1,}$

с равенством именно тогда, когда ${ displaystyle A}$ это арифметическая прогрессия.

В более общем плане предположим ${ displaystyle A}$ является подмножеством конечной собственной обобщенной арифметической прогрессии ${ displaystyle P}$ измерения ${ displaystyle d}$ такой, что ${ Displaystyle | P | leq C | A |}$ для некоторых настоящих ${ displaystyle C geq 1}$. потом ${ Displaystyle | P + P | leq 2 ^ {d} | P |}$, так что

${ displaystyle | A + A | leq | P + P | leq 2 ^ {d} | P | leq C2 ^ {d} | A |.}$

История теоремы Фреймана

Этот результат обусловлен Грегори Фрейман (1964,1966).^[1] Большой интерес к ней и к приложениям вызван новым доказательством Имре З. Ружа (1994). Мэй-Чу Чанг доказал новые полиномиальные оценки размера арифметических прогрессий, возникающие в теореме 2002 г.^[2] Текущие наилучшие оценки были предоставлены Том Сандерс.^[3]

Инструменты, использованные в доказательстве

Представленное здесь доказательство следует за доказательством из лекций Юфэй Чжао.^[4]

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

Лемма Ружи о покрытии

Лемма Ружи о покрытии утверждает следующее:

Позволять ${ displaystyle A}$ и ${ displaystyle S}$ - конечные подмножества абелевой группы с ${ displaystyle S}$ непустой, и пусть ${ displaystyle K}$ быть положительным действительным числом. Тогда если ${ Displaystyle | А + S | leq К | S |}$, есть подмножество ${ displaystyle T}$ из ${ displaystyle A}$ максимум с ${ displaystyle K}$ такие элементы, что ${ displaystyle A substeq T + S-S}$.

Эта лемма дает оценку количества копий ${ displaystyle S-S}$ нужно прикрыть ${ displaystyle A}$, отсюда и название. Доказательство по сути жадный алгоритм:

Доказательство: Позволять ${ displaystyle T}$ быть максимальным подмножеством ${ displaystyle A}$ такие, что множества ${ displaystyle t + S}$ за ${ displaystyle A}$ все не пересекаются. потом ${ Displaystyle | T + S | = | T | cdot | S |}$, а также ${ Displaystyle | Т + S | Leq | А + S | Leq К | S |}$, так ${ displaystyle | T | leq K}$. Кроме того, для любого ${ displaystyle a in A}$, существует некоторое ${ displaystyle t in T}$ такой, что ${ displaystyle t + S}$ пересекает ${ displaystyle a + S}$, иначе добавление ${ displaystyle a}$ к ${ displaystyle T}$ противоречит максимальности ${ displaystyle T}$. Таким образом ${ displaystyle a in T + S-S}$, так ${ displaystyle A substeq T + S-S}$.

Гомоморфизмы Фреймана и модельная лемма Ружи

Позволять ${ displaystyle s geq 2}$ быть положительным целым числом, и ${ displaystyle Gamma}$ и ${ displaystyle Gamma '}$ быть абелевыми группами. Позволять ${ Displaystyle A substeq Gamma}$ и ${ Displaystyle B substeq Gamma '}$. Карта ${ displaystyle varphi двоеточие от A до B}$ это Фрейман ${ displaystyle s}$-гомоморфизм, если

${ displaystyle varphi (a_ {1}) + cdots + varphi (a_ {s}) = varphi (a_ {1} ') + cdots + varphi (a_ {s}')}$

в любое время ${ displaystyle a_ {1} + cdots + a_ {s} = a_ {1} '+ cdots + a_ {s}'}$ для любого ${ displaystyle a_ {1}, ldots, a_ {s}, a_ {1} ', ldots, a_ {s}' in A}$.

Если вдобавок ${ displaystyle varphi}$ это биекция и ${ displaystyle varphi ^ {- 1} двоеточие от B до A}$ Фрейман ${ displaystyle s}$-гомоморфизм, то ${ displaystyle varphi}$ Фрейман ${ displaystyle s}$-изоморфизм.

Если ${ displaystyle varphi}$ Фрейман ${ displaystyle s}$-гомоморфизм, то ${ displaystyle varphi}$ Фрейман ${ displaystyle t}$-гомоморфизм для любого натурального числа ${ displaystyle t}$ такой, что ${ displaystyle 2 leq t leq s}$.

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

Позволять ${ displaystyle A}$ - конечный набор целых чисел, и пусть ${ displaystyle s geq 2}$ быть положительным целым числом. Позволять ${ displaystyle N}$ - такое натуральное число, что ${ Displaystyle N geq | СА-СА |}$. Тогда существует подмножество ${ displaystyle A '}$ из ${ displaystyle A}$ с мощностью не менее ${ displaystyle | A | / s}$ такой, что ${ displaystyle A '}$ Фрейман ${ displaystyle s}$-изоморфен подмножеству ${ Displaystyle mathbb {Z} / N mathbb {Z}}$.

Последнее утверждение означает, что Фрейман существует. ${ displaystyle s}$-гомоморфизм между двумя подмножествами.

Контрольный эскиз: Выберите прайм ${ displaystyle q}$ достаточно большой, так что по модулю${ displaystyle q}$ карта уменьшения ${ displaystyle pi _ {q} двоеточие mathbb {Z} to mathbb {Z} / q mathbb {Z}}$ Фрейман ${ displaystyle s}$-изоморфизм из ${ displaystyle A}$ к его образу в ${ Displaystyle mathbb {Z} / д mathbb {Z}}$. Позволять ${ displaystyle psi _ {q} двоеточие mathbb {Z} / q mathbb {Z} to mathbb {Z}}$ быть подъемной картой, которая берет каждого члена ${ Displaystyle mathbb {Z} / д mathbb {Z}}$ своему уникальному представителю в ${ Displaystyle {1, ldots, д } substeq mathbb {Z}}$. Для ненулевого ${ displaystyle lambda in mathbb {Z} / q mathbb {Z}}$, позволять ${ Displaystyle cdot лямбда двоеточие mathbb {Z} / q mathbb {Z} to mathbb {Z} / q mathbb {Z}}$ быть умножением на ${ displaystyle lambda}$ карта, которая является Фрейманом ${ displaystyle s}$-изоморфизм. Позволять ${ displaystyle B}$ быть имиджем ${ displaystyle ( cdot lambda circ pi _ {q}) (A)}$. Выберите подходящее подмножество ${ displaystyle B '}$ из ${ displaystyle B}$ с мощностью не менее ${ displaystyle | B | / s}$ так что ограничение ${ displaystyle psi _ {q}}$ к ${ displaystyle B '}$ Фрейман ${ displaystyle s}$-изоморфизм на его образ, и пусть ${ displaystyle A ' substeq A}$ быть прообразом ${ displaystyle B '}$ под ${ displaystyle cdot lambda circ pi _ {q}}$. Тогда ограничение ${ displaystyle psi _ {q} circ cdot lambda circ pi _ {q}}$ к ${ displaystyle A '}$ Фрейман ${ displaystyle s}$-изоморфизм на его образ ${ displaystyle psi _ {q} (B ')}$. Наконец, существует выбор ненулевых ${ displaystyle lambda}$ такой, что ограничение по модулю-${ displaystyle N}$ снижение ${ Displaystyle mathbb {Z} to mathbb {Z} / N mathbb {Z}}$ к ${ displaystyle psi _ {q} (B ')}$ Фрейман ${ displaystyle s}$-изоморфизм на его образ. Результат следует после составления этой карты с более ранним Фрейманом. ${ displaystyle s}$-изоморфизм.

Множества Бора и лемма Боголюбова

Хотя теорема Фреймана применима к наборам целых чисел, лемма Ружи о моделировании позволяет моделировать множества целых чисел как подмножества конечных чисел. циклические группы. Поэтому полезно сначала поработать с настройкой конечное поле, а затем обобщить результаты на целые числа. Боголюбовым доказана следующая лемма:

Позволять ${ displaystyle A in mathbb {F} _ {2} ^ {n}}$ и разреши ${ Displaystyle альфа = | А | / 2 ^ {п}}$. потом ${ displaystyle 4A}$ содержит подпространство ${ displaystyle mathbb {F} _ {2} ^ {n}}$ размером не менее ${ Displaystyle п- альфа ^ {- 2}}$.

Обобщение этой леммы на произвольные циклические группы требует аналогичного понятия «подпространство»: множества Бора. Позволять ${ displaystyle R}$ быть подмножеством ${ Displaystyle mathbb {Z} / N mathbb {Z}}$ куда ${ displaystyle N}$ это простое число. В Набор Бора измерения ${ displaystyle | R |}$ и ширина ${ displaystyle epsilon}$ является

${ displaystyle operatorname {Bohr} (R, epsilon) = {x in mathbb {Z} / N mathbb {Z}: forall r in R, | rx / N | leq epsilon },}$

куда ${ displaystyle | rx / N |}$ это расстояние от ${ displaystyle rx / N}$ до ближайшего целого числа. Следующая лемма обобщает лемму Боголюбова.

Позволять ${ displaystyle A in mathbb {Z} / N mathbb {Z}}$ и ${ Displaystyle альфа = | A | / N}$. потом ${ displaystyle 2A-2A}$ содержит множество Бора размерности не более ${ displaystyle alpha ^ {- 2}}$ и ширина ${ displaystyle 1/4}$.

Здесь размерность множества Бора аналогична размерности коразмерность набора в ${ displaystyle mathbb {F} _ {2} ^ {n}}$. Доказательство леммы включает Фурье-аналитический методы. Следующее предложение связывает установки Бора с обобщенными арифметическими прогрессиями, что в конечном итоге приводит к доказательству теоремы Фреймана.

Позволять ${ displaystyle X}$ быть борцом в ${ Displaystyle mathbb {Z} / N mathbb {Z}}$ измерения ${ displaystyle d}$ и ширина ${ displaystyle epsilon}$. потом ${ displaystyle X}$ содержит правильную обобщенную арифметическую прогрессию размерности не более ${ displaystyle d}$ и размер не менее ${ displaystyle ( epsilon / d) ^ {d} N}$.

Доказательство этого предложения использует Теорема Минковского, фундаментальный результат в геометрия чисел.

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

По неравенству Плюннеке-Ружи ${ Displaystyle | 8A-8A | leq K ^ {16} | A |}$. К Постулат Бертрана, существует простое число ${ displaystyle N}$ такой, что ${ displaystyle | 8A-8A | leq N leq 2K ^ {16} | A |}$. По лемме Ружи о моделировании существует подмножество ${ displaystyle A '}$ из ${ displaystyle A}$ мощности не менее ${ displaystyle | A | / 8}$ такой, что ${ displaystyle A '}$ 8-изоморфно по Фрейману подмножеству ${ Displaystyle B substeq mathbb {Z} / N mathbb {Z}}$.

По обобщению леммы Боголюбова ${ displaystyle 2B-2B}$ содержит правильную обобщенную арифметическую прогрессию размерности ${ displaystyle d}$ в большинстве ${ displaystyle (1 / (8 cdot 2K ^ {16})) ^ {- 2} = 256K ^ {32}}$ и размер не менее ${ Displaystyle (1 / (4d)) ^ {d} N}$. Потому что ${ displaystyle A '}$ и ${ displaystyle B}$ 8-изоморфны Фрейману, ${ displaystyle 2A'-2A '}$ и ${ displaystyle 2B-2B}$ 2-изоморфны Фрейману. Тогда образ при 2-изоморфизме собственной обобщенной арифметической прогрессии в ${ displaystyle 2B-2B}$ является правильной обобщенной арифметической прогрессией в ${ displaystyle 2A'-2A ' substeq 2A-2A}$ называется ${ displaystyle P}$.

Но ${ Displaystyle P + A substeq 3A-2A}$, поскольку ${ Displaystyle P substeq 2A-2A}$. Таким образом

${ Displaystyle | P + A | Leq | 3A-2A | Leq | 8A-8A | Leq N Leq (4d) ^ {d} | P |}$

поэтому по лемме Ружи о покрытии ${ Displaystyle А Subteq X + P-P}$ для некоторых ${ Displaystyle X substeq A}$ мощности не более ${ displaystyle (4d) ^ {d}}$. потом ${ Displaystyle X + P-P}$ содержится в обобщенной арифметической прогрессии размерности ${ displaystyle | X | + d}$ и размер не больше ${ displaystyle 2 ^ {| X |} 2 ^ {d} | P | leq 2 ^ {| X | + d} | 2A-2A | leq 2 ^ {| X | + d} K ^ {4} | A |}$, завершая доказательство.

Обобщения

Результат благодаря Бен Грин а Имре Ружа обобщил теорему Фреймана на произвольные абелевы группы. Они использовали аналогичное понятие для обобщенных арифметических прогрессий, которые они назвали смежными прогрессиями. А прогрессия смежных классов абелевой группы ${ displaystyle G}$ это набор ${ Displaystyle P + H}$ для правильной обобщенной арифметической прогрессии ${ displaystyle P}$ и подгруппа ${ displaystyle H}$ из ${ displaystyle G}$. Размерность этой смежной прогрессии определяется как размерность ${ displaystyle P}$, а его размер определяется как мощность всего множества. Грин и Ружа показали следующее:

Позволять ${ displaystyle A}$ - конечное множество в абелевой группе ${ displaystyle G}$ такой, что ${ Displaystyle | А + А | leq К | А |}$. потом ${ displaystyle A}$ содержится в смежной прогрессии размерности не более ${ displaystyle d (K)}$ и размер не больше ${ Displaystyle f (K) | A |}$, куда ${ displaystyle f (K)}$ и ${ displaystyle d (K)}$ являются функциями ${ displaystyle K}$ которые не зависят от ${ displaystyle G}$.

Грин и Ружа представили верхние границы ${ Displaystyle д (К) = СК ^ {4} журнал (К + 2)}$ и ${ Displaystyle е (К) = е ^ {СК ^ {4} журнал ^ {2} (К + 2)}}$ для некоторой абсолютной постоянной ${ displaystyle C}$.^[5]

Теренс Тао (2010) также обобщили теорему Фреймана на разрешимые группы ограниченной производной длины.^[6]

Распространение теоремы Фреймана на произвольную неабелеву группу все еще открыто. Результаты для ${ displaystyle K <2}$, когда набор имеет очень маленькое удвоение, называются Кнезер теоремы.^[7]

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

• Марковский спектр
• Неравенство Плюннеке-Ружи
• Теорема Кнезера (комбинаторика)

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

• Фрейман, Г.А. (1964). «Сложение конечных множеств». Сов. Матем., Докл.. 5: 1366–1370. Zbl  0163.29501.
• Фрейман, Г.А. (1966). Основы структурной теории сложения множеств (на русском). Казань: Казань Гос. Пед. Inst. п. 140. Zbl  0203.35305.
• Фрейман, Г.А. (1999). «Структурная теория сложения множеств». Astérisque. 258: 1–33. Zbl  0958.11008.
• Натансон, Мелвин Б. (1996). Аддитивная теория чисел: обратные задачи и геометрия сумм. Тексты для выпускников по математике. 165. Springer. ISBN  978-0-387-94655-9. Zbl  0859.11003.
• Ружа, Имре З. (1994). «Обобщенные арифметические прогрессии и суммы». Acta Mathematica Hungarica. 65 (4): 379–388. Дои:10.1007 / bf01876039. Zbl  0816.11008.
• Тао, Теренс (2010). «Теорема Фреймана для разрешимых групп». Contrib. Диск. Математика. 5 (2): 137–184. Дои:10.11575 / cdm.v5i2.62020.

Эта статья включает материал из теоремы Фреймана о PlanetMath, который находится под лицензией Лицензия Creative Commons Attribution / Share-Alike.