Теорема Фреймана

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

Заявление

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

Примеры

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

$|A+A|\geq 2|A|-1,$

с равенством именно тогда, когда $A$ представляет собой арифметическую прогрессию.

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

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

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

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

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

Представленное здесь доказательство следует доказательству из конспектов лекций Юфэя Чжао.

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

Основная статья: неравенство Плюнеке – Ружи

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

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

Позволять $A$ и $S$ — конечные подмножества абелевой группы с $S$ непусто, и пусть $K$ быть положительным действительным числом. Тогда, если $|A+S|\leq K|S|$, есть подмножество $T$ из $A$ с максимум $K$ такие элементы, что $A\subseteq T+S-S$.

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

Доказательство: Пусть $T$ быть максимальным подмножеством $A$ такие, что множества $t+S$ для $A$ все непересекающиеся. Затем $|T+S|=|T|\cdot |S|$, а также $|T+S|\leq |A+S|\leq K|S|$, так $|T|\leq K$. Более того, для любого $a\in A$, есть некоторые $t\in T$ такой, что $t+S$ пересекает $a+S$, иначе добавление $a$ к $T$ противоречит максимальности $T$. Таким образом $a\in T+S-S$, так $A\subseteq T+S-S$.

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

Позволять $s\geq 2$ быть положительным целым числом, и $\Gamma$ и $\Gamma '$ быть абелевыми группами. Позволять $A\subseteq \Gamma$ и $B\subseteq \Gamma '$. Карта $\varphi \colon A\to B$ является Фрейманом $s$-гомоморфизм, если

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

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

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

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

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

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

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

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

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

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

Позволять $A\in \mathbb {F} _{2}^{n}$ и пусть $\alpha =|A|/2^{n}$. Затем $4A$ содержит подпространство $\mathbb {F} _{2}^{n}$ размерности по крайней мере $n-\alpha ^{-2}$.

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

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

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

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

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

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

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

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

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

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

Но $P+A\subseteq 3A-2A$, с $P\subseteq 2A-2A$. Таким образом

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

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

Обобщения

Смотрите также: Арифметическая комбинаторика § Брейяра – Грина – Тао_теорема

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

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

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

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

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

Полиномиальная гипотеза Фреймана – Ружи: это обобщение, опубликованное в статье Имре Рузой , но приписан им Каталин Мартон . Он утверждает, что если подмножество группы (степень циклической группы ) $A\subset G$ имеет константу удвоения такую, что $|A+A|\leq K|A|$ то оно покрыто ограниченным числом $K^{C}$смежных классов некоторой подгруппы $H\subset G$ с $|H|\leq |A|$. В 2012 году Томс Сандерс дал почти полиномиальную оценку гипотезы для абелевых групп. В 2023 году решение будет принято $G=\mathbb {F} _{2}^{n}$ поле характеристики 2 было опубликовано в качестве препринта Тимом Гауэрсом , Беном Грином , Фредди Мэннерсом и Терри Тао . Это доказательство было полностью формализовано на языке формальных доказательств Lean 4 — совместном проекте, который стал важной вехой с точки зрения математиков, успешно формализовавших современную математику.

См. также

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

Дальнейшее чтение

• Фрейман, Джорджия (1999). «Структурная теория сложения множеств». Астериск . 258 : 1–33. Збл   0958.11008 .

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