Теорема Фреймана
О приближенной структуре множеств, сумма которых мала

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

Заявление

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

Примеры

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

| А + А | ≥ 2 | А | − 1 , {\displaystyle |A+A|\geq 2|A|-1,}

с равенством именно тогда, когда является арифметической прогрессией. А {\displaystyle А}

В более общем случае предположим, что есть подмножество конечной собственной обобщенной арифметической прогрессии размерности такой, что для некоторого действительного . Тогда , так что А {\displaystyle А} П {\displaystyle P} г {\displaystyle д} | П | ≤ С | А | {\displaystyle |P|\leq C|A|} С ≥ 1 {\displaystyle C\geq 1} | П + П | ≤ 2 г | П | {\displaystyle |P+P|\leq 2^{d}|P|}

| А + А | ≤ | П + П | ≤ 2 г | П | ≤ С 2 г | А | . {\displaystyle |A+A|\leq |P+P|\leq 2^{d}|P|\leq C2^{d}|A|.}

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

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

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

Представленное здесь доказательство следует доказательству из лекционных заметок Юфэя Чжао. [8]

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

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

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

Пусть и — конечные подмножества абелевой группы с непустотой, и пусть — положительное действительное число. Тогда если , существует подмножество с не более чем элементами такое, что . А {\displaystyle А} С {\displaystyle S} С {\displaystyle S} К {\displaystyle К} | А + С | ≤ К | С | {\displaystyle |A+S|\leq K|S|} Т {\displaystyle Т} А {\displaystyle А} К {\displaystyle К} А ⊆ Т + С − С {\displaystyle A\subseteq T+SS}

Эта лемма дает ограничение на то, сколько копий одного нужно покрыть , отсюда и название. Доказательство по сути является жадным алгоритмом : С − С {\displaystyle СС} А {\displaystyle А}

Доказательство: Пусть будет максимальным подмножеством из , таким, что множества для все не пересекаются. Тогда , а также , поэтому . Более того, для любого существует такое , что пересекает , так как в противном случае добавление к противоречит максимальности . Таким образом , поэтому . Т {\displaystyle Т} А {\displaystyle А} т + С {\displaystyle т+С} А {\displaystyle А} | Т + С | = | Т | ⋅ | С | {\displaystyle |T+S|=|T|\cdot |S|} | Т + С | ≤ | А + С | ≤ К | С | {\displaystyle |T+S|\leq |A+S|\leq K|S|} | Т | ≤ К {\displaystyle |T|\leq K} а ∈ А {\displaystyle а\в А} т ∈ Т {\displaystyle t\in T} т + С {\displaystyle т+С} а + С {\displaystyle а+S} а {\displaystyle а} Т {\displaystyle Т} Т {\displaystyle Т} а ∈ Т + С − С {\displaystyle a\in T+SS} А ⊆ Т + С − С {\displaystyle A\subseteq T+SS}

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

Пусть — положительное целое число, а и — абелевы группы. Пусть и . Отображение является гомоморфизмом Фреймана, если с ≥ 2 {\displaystyle s\geq 2} Г {\displaystyle \Гамма} Г ′ {\displaystyle \Гамма '} А ⊆ Г {\displaystyle A\subseteq \Гамма} Б ⊆ Г ′ {\displaystyle B\subseteq \Gamma '} φ : A → B {\displaystyle \varphi \colon A\to B} s {\displaystyle s}

φ ( a 1 ) + ⋯ + φ ( a s ) = φ ( a 1 ′ ) + ⋯ + φ ( a s ′ ) {\displaystyle \varphi (a_{1})+\cdots +\varphi (a_{s})=\varphi (a_{1}')+\cdots +\varphi (a_{s}')}

когда бы то ни было для любого . a 1 + ⋯ + a s = a 1 ′ + ⋯ + a s ′ {\displaystyle a_{1}+\cdots +a_{s}=a_{1}'+\cdots +a_{s}'} a 1 , … , a s , a 1 ′ , … , a s ′ ∈ A {\displaystyle a_{1},\ldots ,a_{s},a_{1}',\ldots ,a_{s}'\in A}

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

Если — гомоморфизм Фреймана , то — гомоморфизм Фреймана для любого положительного целого числа, такого что . φ {\displaystyle \varphi } s {\displaystyle s} φ {\displaystyle \varphi } t {\displaystyle t} t {\displaystyle t} 2 ≤ t ≤ s {\displaystyle 2\leq t\leq s}

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

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

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

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

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

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

Пусть и пусть . Тогда содержит подпространство размерности не менее . A ⊆ F 2 n {\displaystyle A\subseteq \mathbb {F} _{2}^{n}} α = | A | / 2 n {\displaystyle \alpha =|A|/2^{n}} 4 A {\displaystyle 4A} F 2 n {\displaystyle \mathbb {F} _{2}^{n}} n − α − 2 {\displaystyle n-\alpha ^{-2}}

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

Bohr ⁡ ( R , ε ) = { x ∈ Z / N Z : ∀ r ∈ R , | r x / N | ≤ ε } , {\displaystyle \operatorname {Bohr} (R,\varepsilon )=\{x\in \mathbb {Z} /N\mathbb {Z} :\forall r\in R,|rx/N|\leq \varepsilon \},}

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

Пусть и . Тогда содержит множество Бора размерности не более и ширины . A ⊆ Z / N Z {\displaystyle A\subseteq \mathbb {Z} /N\mathbb {Z} } α = | A | / N {\displaystyle \alpha =|A|/N} 2 A − 2 A {\displaystyle 2A-2A} α − 2 {\displaystyle \alpha ^{-2}} 1 / 4 {\displaystyle 1/4}

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

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

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

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

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

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

Но , так как . Таким образом P + A ⊆ 3 A − 2 A {\displaystyle P+A\subseteq 3A-2A} P ⊆ 2 A − 2 A {\displaystyle P\subseteq 2A-2A}

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

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

Обобщения

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

Пусть — конечное множество в абелевой группе, такое что . Тогда содержится в смежной прогрессии размерности не более и размера не более , где и — функции от , не зависящие от . A {\displaystyle A} G {\displaystyle G} | A + A | ≤ K | A | {\displaystyle |A+A|\leq K|A|} A {\displaystyle A} d ( K ) {\displaystyle d(K)} f ( K ) | A | {\displaystyle f(K)|A|} f ( K ) {\displaystyle f(K)} d ( K ) {\displaystyle d(K)} K {\displaystyle K} G {\displaystyle G}

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

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

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

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

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

Ссылки

  1. ^ Фрейман, Г. А. (1964). «Сложение конечных множеств». Советская математика. Доклады . 5 : 1366–1370. Zbl  0163.29501.
  2. ^ Фрейман, Г. А. (1966). Основы структурной теории сложения множеств . Казань: Казанский гос. пед. ин-т. С. 140. Збл  0203.35305.
  3. ^ Натансон, Мелвин Б. (1996). Аддитивная теория чисел: обратные задачи и геометрия сумм . Graduate Texts in Mathematics . Vol. 165. Springer. ISBN 978-0-387-94655-9. Збл  0859.11003.стр. 252.
  4. ^ Ruzsa, IZ (август 1992). «Арифметические прогрессии и число сумм». Periodica Mathematica Hungarica . 25 (1): 105–111. doi :10.1007/BF02454387. ISSN  0031-5303.
  5. ^ Ruzsa, Imre Z. (1994). «Обобщенные арифметические прогрессии и суммы множеств». Acta Mathematica Hungarica . 65 (4): 379–388. doi : 10.1007/bf01876039 . Zbl  0816.11008.
  6. ^ Чанг, Мэй-Чу (2002). «Многочленная оценка в теореме Фреймана». Математический журнал Дьюка . 113 (3): 399–419. CiteSeerX 10.1.1.207.3090 . дои : 10.1215/s0012-7094-02-11331-3. МР  1909605. 
  7. ^ Сандерс, Том (2013). «Возвращение к структурной теории сложения множеств». Бюллетень Американского математического общества . 50 : 93–127. arXiv : 1212.0458 . doi : 10.1090/S0273-0979-2012-01392-7. S2CID  42609470.
  8. ^ Чжао, Юфэй. "Теория графов и аддитивная комбинаторика" (PDF) . Архивировано из оригинала (PDF) 2019-11-23 . Получено 2019-12-02 .
  9. ^ Ruzsa, Imre Z. ; Green, Ben (2007). «Теорема Фреймана в произвольной абелевой группе». Журнал Лондонского математического общества . 75 (1): 163–175. arXiv : math/0505198 . doi :10.1112/jlms/jdl021. S2CID  15115236.
  10. ^ Тао, Теренс (2010). «Теорема Фреймана для разрешимых групп». Вклад в дискретную математику . 5 (2): 137–184. doi : 10.11575/cdm.v5i2.62020 .
  11. ↑ Тао, Теренс (10 ноября 2009 г.). «Элементарная некоммутативная теорема Фреймана». Блог Теренса Тао .
  12. ^ "(Бен Грин) Полиномиальная гипотеза Фреймана–Ружи". Что нового . 2007-03-11 . Получено 2023-11-14 .
  13. ^ Ruzsa, I. (1999). «Аналог теоремы Фреймана в группах» (PDF) . Astérisque . 258 : 323–326.
  14. ^ Сандерс, Том (15 октября 2012 г.). «О лемме Боголюбова – Ружи». Анализ и PDE . 5 (3): 627–655. arXiv : 1011.0107 . дои : 10.2140/apde.2012.5.627 . ISSN  1948-206Х.
  15. ^ Брубейкер, Бен (2023-12-04). «Простая на первый взгляд задача дает слишком большие числа для нашей Вселенной». Журнал Quanta . Получено 2023-12-11 .
  16. ^ Гауэрс, У. Т.; Грин, Бен; Мэннерс, Фредди; Тао, Теренс (2023). «О гипотезе Мартона». arXiv : 2311.05762 [math.NT].
  17. ^ "О гипотезе Мартона". Что нового . 2023-11-13 . Получено 2023-11-14 .
  18. ^ Сломан, Лейла (6 декабря 2023 г.). «Команда математиков «А» доказывает критическую связь между сложением и множествами». Журнал Quanta . Получено 16 декабря 2023 г.
  19. ^ "Полиномиальная гипотеза Фреймана-Ружи". Домашняя страница проекта PFR .

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


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

Retrieved from "https://en.wikipedia.org/w/index.php?title=Freiman%27s_theorem&oldid=1253754825"