Теорема об углах

Высказывание в арифметической комбинаторике

В арифметической комбинаторике теорема об углах утверждает, что для любого , для достаточно большого , любой набор из по крайней мере точек в сетке содержит угол, т. е. тройку точек вида с . Впервые это было доказано Миклошем Айтаем и Эндре Семереди в 1974 году с использованием теоремы Семереди . ^[1] В 2003 году Йожеф Шоймоши дал короткое доказательство с использованием леммы об удалении треугольника . ^[2] ${\displaystyle \varepsilon >0}$ ${\displaystyle N}$ ${\displaystyle \varepsilon N^{2}}$ ${\displaystyle N\times N}$ ${\displaystyle \{1,\ldots ,N\}^{2}}$ ${\displaystyle \{(x,y),(x+h,y),(x,y+h)\}}$ ${\displaystyle h\neq 0}$

Заявление

Определим угол как подмножество вида , где и . Для каждого существует положительное целое число такое, что для любого , любое подмножество с размером не менее содержит угол. ${\displaystyle \mathbb {Z} ^{2}}$ ${\displaystyle \{(x,y),(x+h,y),(x,y+h)\}}$ ${\displaystyle x,y,h\in \mathbb {Z} }$ ${\displaystyle h\neq 0}$ ${\displaystyle \varepsilon >0}$ ${\displaystyle N(\varepsilon )}$ ${\displaystyle N\geq N(\varepsilon )}$ ${\displaystyle A\subseteq \{1,\ldots ,N\}^{2}}$ ${\displaystyle \varepsilon N^{2}}$

Условие можно смягчить, показав, что если является плотным, то у него есть некоторое плотное подмножество, которое является центрально-симметричным. ${\displaystyle h\neq 0}$ ${\displaystyle h>0}$ ${\displaystyle A}$

Обзор доказательств

Ниже приводится набросок аргументации Солимоси.

Предположим, что не имеет углов. Постройте вспомогательный трехдольный граф с частями , и , где соответствует прямой , соответствует прямой , а соответствует прямой . Соедините две вершины, если пересечение их соответствующих прямых лежит в . ${\displaystyle A\subset \{1,\ldots ,N\}^{2}}$ ${\displaystyle G}$ ${\displaystyle X=\{x_{1},\ldots ,x_{N}\}}$ ${\displaystyle Y=\{y_{1},\ldots ,y_{N}\}}$ ${\displaystyle Z=\{z_{1},\ldots ,z_{2N}\}}$ ${\displaystyle x_{i}}$ ${\displaystyle x=i}$ ${\displaystyle y_{j}}$ ${\displaystyle y=j}$ ${\displaystyle z_{k}}$ ${\displaystyle x+y=k}$ ${\displaystyle A}$

Обратите внимание, что треугольник в соответствует углу в , за исключением тривиального случая, когда линии, соответствующие вершинам треугольника, пересекаются в точке в . Отсюда следует, что каждое ребро из находится ровно в одном треугольнике, поэтому по лемме об удалении треугольников , имеет ребра, поэтому , что и требовалось. ${\displaystyle G}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle o(|V(G)|^{2})}$ ${\displaystyle |A|=o(N^{2})}$

Количественные границы

Пусть будет размером наибольшего подмножества , которое не содержит ни одного угла. Наиболее известные границы: ${\displaystyle r_{\angle }(N)}$ ${\displaystyle [N]^{2}}$

${\displaystyle {\frac {N^{2}}{2^{(c_{1}+o(1)){\sqrt {\log _{2}N}}}}}\leq r_{\angle }(N)\leq {\frac {N^{2}}{(\log \log N)^{c_{2}}}},}$

где и . Нижняя граница принадлежит Грину, ^[3] основанному на работе Линиала и Шрайбмана. ^[4] Верхняя граница принадлежит Шкредову. ^[5] ${\displaystyle c_{1}\approx 1.822}$ ${\displaystyle c_{2}\approx 0.0137}$

Многомерное расширение

Угол в — это множество точек вида , где — стандартный базис , и . Естественное расширение теоремы об углах для этого случая можно показать с помощью леммы об удалении гиперграфа , в духе доказательства Солимози. Лемма об удалении гиперграфа была показана независимо Гауэрсом ^[6] и Наглом, Рёдлем, Шахтом и Скоканом. ^[7] ${\displaystyle \mathbb {Z} ^{d}}$ ${\displaystyle \{a\}\cup \{a+he_{i}:1\leq i\leq d\}}$ ${\displaystyle e_{1},\ldots ,e_{d}}$ ${\displaystyle \mathbb {R} ^{d}}$ ${\displaystyle h\neq 0}$

Многомерная теорема Семереди.

Многомерная теорема Семереди утверждает, что для любого фиксированного конечного подмножества и для каждого существует положительное целое число такое, что для любого любое подмножество с размером по крайней мере содержит подмножество вида . Эта теорема следует из теоремы о многомерных углах с помощью простого проекционного аргумента. ^[6] В частности, теорема Рота об арифметических прогрессиях напрямую следует из теоремы об обычных углах. ${\displaystyle S\subseteq \mathbb {Z} ^{d}}$ ${\displaystyle \varepsilon >0}$ ${\displaystyle N(S,\varepsilon )}$ ${\displaystyle N\geq N(S,\varepsilon )}$ ${\displaystyle A\subseteq \{1,\ldots ,N\}^{d}}$ ${\displaystyle \varepsilon N^{d}}$ ${\displaystyle a\cdot S+h}$

Ссылки

1. Айтай, Миклош ; Семереди, Эндре (1974). «Наборы точек решетки, не образующие квадратов». Стад. наук. Математика. Венгрия . 9 : 9–11. МР  0369299..
2. Solymosi, József (2003). «Заметка об обобщении теоремы Рота». В Aronov, Борис; Basu, Saugata; Pach, János; и др. (ред.). Дискретная и вычислительная геометрия . Алгоритмы и комбинаторика. Т. 25. Берлин: Springer-Verlag. С. 825–827. doi :10.1007/978-3-642-55566-4_39. ISBN 3-540-00371-1. МР  2038505.
3. Грин, Бен (2021). «Нижние оценки для множеств без углов». Новозеландский журнал математики . 51. arXiv : 2102.11702 . doi : 10.53733/86.
4. Linial, Nati ; Shraibman, Adi (2021). "Большие свободные от углов наборы из лучших протоколов NOF Exactly-N". Дискретный анализ . 2021 . arXiv : 2102.00421 . doi :10.19086/da.28933. S2CID  231740736.
5. Шкредов, ИД (2006). «Об обобщении теоремы Семереди». Труды Лондонского математического общества . 93 (3): 723–760. arXiv : math/0503639 . doi :10.1017/S0024611506015991. S2CID  55252774.
6. Gowers, Timothy (2007). «Регулярность гиперграфа и многомерная теорема Семереди». Annals of Mathematics . 166 (3): 897–946. arXiv : 0710.3032 . doi : 10.4007/annals.2007.166.897. MR  2373376. S2CID  56118006.
7. Rodl, V.; Nagle, B.; Skokan, J.; Schacht, M.; Kohayakawa, Y. (2005-05-26). "From The Cover: The hypergraph regularity method and its applications". Труды Национальной академии наук . 102 (23): 8109–8113. Bibcode : 2005PNAS..102.8109R. doi : 10.1073/pnas.0502771102 . ISSN  0027-8424. PMC 1149431. PMID 15919821  . 

Внешние ссылки

• Доказательство теоремы об углах на полимате.