Теорема Фреймана - Freimans theorem - Wikipedia

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

Заявление

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

Примеры

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

${\displaystyle |A+A|\geq 2|A|-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 |A+S|\leq K|S|}$, есть подмножество ${\displaystyle T}$ из ${\displaystyle A}$ максимум с ${\displaystyle K}$ такие элементы, что ${\displaystyle A\subseteq T+S-S}$.

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

Доказательство: Позволять ${\displaystyle T}$ быть максимальным подмножеством ${\displaystyle A}$ такие, что множества ${\displaystyle t+S}$ за ${\displaystyle A}$ все не пересекаются. потом ${\displaystyle |T+S|=|T|\cdot |S|}$, а также ${\displaystyle |T+S|\leq |A+S|\leq K|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\subseteq T+S-S}$.

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

Позволять ${\displaystyle s\geq 2}$ быть положительным целым числом, и ${\displaystyle \Gamma }$ и ${\displaystyle \Gamma '}$ быть абелевыми группами. Позволять ${\displaystyle A\subseteq \Gamma }$ и ${\displaystyle B\subseteq \Gamma '}$. Карта ${\displaystyle \varphi \colon A\to 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}\colon B\to 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 |sA-sA|}$. Тогда существует подмножество ${\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}\colon \mathbb {Z} \to \mathbb {Z} /q\mathbb {Z} }$ Фрейман ${\displaystyle s}$-изоморфизм из ${\displaystyle A}$ к его образу в ${\displaystyle \mathbb {Z} /q\mathbb {Z} }$. Позволять ${\displaystyle \psi _{q}\colon \mathbb {Z} /q\mathbb {Z} \to \mathbb {Z} }$ быть подъемной картой, которая берет каждого члена ${\displaystyle \mathbb {Z} /q\mathbb {Z} }$ своему уникальному представителю в ${\displaystyle \{1,\ldots ,q\}\subseteq \mathbb {Z} }$. Для ненулевого ${\displaystyle \lambda \in \mathbb {Z} /q\mathbb {Z} }$, позволять ${\displaystyle \cdot \lambda \colon \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'\subseteq 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 \alpha =|A|/2^{n}}$. потом ${\displaystyle 4A}$ содержит подпространство ${\displaystyle \mathbb {F} _{2}^{n}}$ размером не менее ${\displaystyle n-\alpha ^{-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 \alpha =|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\subseteq \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'\subseteq 2A-2A}$ называется ${\displaystyle P}$.

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

${\displaystyle |P+A|\leq |3A-2A|\leq |8A-8A|\leq N\leq (4d)^{d}|P|}$

поэтому по лемме Ружи о покрытии ${\displaystyle A\subseteq X+P-P}$ для некоторых ${\displaystyle X\subseteq 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 |A+A|\leq K|A|}$. потом ${\displaystyle A}$ содержится в смежной прогрессии размерности не более ${\displaystyle d(K)}$ и размер не больше ${\displaystyle f(K)|A|}$, куда ${\displaystyle f(K)}$ и ${\displaystyle d(K)}$ являются функциями ${\displaystyle K}$ которые не зависят от ${\displaystyle G}$.

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

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

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

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

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

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

1. Натансон (1996) стр.252
2. Чанг, Мэй-Чу (2002). «Полиномиальная оценка в теореме Фреймана». Duke Math. J. 113 (3): 399–419. CiteSeerX  10.1.1.207.3090. Дои:10.1215 / s0012-7094-02-11331-3. МИСТЕР  1909605.
3. Сандерс, Том (2013). «Пересмотр структурной теории сложения множеств». Бык. Амер. Математика. Soc. 50: 93–127. Дои:10.1090 / S0273-0979-2012-01392-7.
4. Чжао, Юфэй. «Теория графов и аддитивная комбинаторика» (PDF).
5. Ружа, Имре З.; Грин, Бен (2007). «Теорема Фреймана в произвольной абелевой группе». Журнал Лондонского математического общества. 75 (1): 163–175. arXiv:математика / 0505198. Дои:10.1112 / jlms / jdl021.
6. Тао, Теренс (2010). «Теорема Фреймана для разрешимых групп». Contrib. Диск. Математика. 5 (2): 137–184. Дои:10.11575 / cdm.v5i2.62020.
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.