Теорема об углах - Corners theorem

На этом рисунке показан

{ displaystyle 6 times 6}

сетка и подмножество с

{ displaystyle { frac {1} {2}}}

точек, отмеченных красным. Этот набор точек содержит всего 2 угла, которые отмечены зеленым и синим цветом соответственно.

В математике теорема углов это результат арифметическая комбинаторика доказано Миклош Айтай и Эндре Семереди. В нем говорится, что для каждого ${ displaystyle varepsilon> 0}$ , для достаточно больших ${ displaystyle N}$ , любой набор не менее ${ displaystyle varepsilon N ^ {2}}$ точки в ${ Displaystyle N раз N}$ сетка ${ Displaystyle {1, ldots, N } times {1, ldots, N }}$ содержит угол, т.е. тройку точек вида ${ Displaystyle {(х, у), (х + ч, у), (х, у + ч) }}$ . Потом, Солимози (2003) дал более простое доказательство, основанное на лемма об удалении треугольника. Из теоремы об углах следует Теорема Рота.

Формулировка и доказательство теоремы об углах

Определение

А угол это подмножество ${ Displaystyle mathbb {Z} ^ {2}}$ формы ${ Displaystyle {(х, у), (х + ч, у), (х, у + ч) }}$ , куда ${ displaystyle x, y, h in mathbb {Z}}$ и ${ displaystyle h> 0}$ .

Формальная формулировка теоремы об углах

Если ${ displaystyle A}$ является подмножеством ${ Displaystyle N раз N}$ сетка ${ Displaystyle {1, ldots, N } times {1, ldots, N }}$ без угла, то размер ${ displaystyle A}$ является ${ displaystyle o (N ^ {2})}$ . Другими словами, для любого ${ displaystyle varepsilon}$ , Существует ${ displaystyle N_ {0}}$ такой, что для любого ${ displaystyle N geq N_ {0}}$ , любое подмножество без углов ${ displaystyle A}$ из ${ Displaystyle {1, ldots, N } times {1, ldots, N }}$ меньше чем ${ displaystyle varepsilon N ^ {2}}$ .

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

Сначала мы хотели бы заменить условие ${ displaystyle h> 0}$ с ${ displaystyle h neq 0}$ . Для этого рассмотрим множество ${ Displaystyle А + А подмножество {1, ldots, 2N } раз {1, ldots, 2N }}$ . Посредством принцип голубятни, существует точка ${ displaystyle c in A + A}$ так что его можно представить как ${ displaystyle c = a + b}$ по крайней мере ${ displaystyle { frac {| A | ^ {2}} {(2N) ^ {2}}}}$ пары ${ displaystyle a, b in A}$ . Выбираем эту точку ${ displaystyle c}$ и построить новый набор ${ displaystyle A ': = A cap (c-A)}$ . Заметьте, что ${ displaystyle | A '| geq { frac {| A | ^ {2}} {(2N) ^ {2}}}}$ , как размер ${ displaystyle A '}$ это количество способов написания ${ displaystyle c = a + b}$ . Далее заметим, что достаточно показать, что ${ Displaystyle | A '| = о (N ^ {2})}$ . Обратите внимание, что ${ displaystyle A '}$ это подмножество ${ displaystyle A}$ , поэтому у него нет угла, то есть нет подмножества формы ${ Displaystyle {(х, у), (х + ч, у), (х, у + ч) }}$ за ${ displaystyle h> 0}$ . Но ${ displaystyle A '}$ также является подмножеством ${ displaystyle c-A}$ , поэтому у него также нет антиугла, т.е. нет подмножества вида ${ Displaystyle {(х, у), (х + ч, у), (х, у + ч) }}$ с ${ displaystyle h <0}$ . Следовательно, ${ displaystyle A '}$ не имеет подмножества формы ${ Displaystyle {(х, у), (х + ч, у), (х, у + ч) }}$ за ${ displaystyle h neq 0}$ , что и является условием, которое мы искали.

Показывать ${ Displaystyle | A '| = о (N ^ {2})}$ , строим вспомогательный трехчастный граф ${ displaystyle G}$ . Первая часть имеет набор вершин ${ Displaystyle U = {u_ {1}, ldots, u_ {N} }}$ , где вершины соответствуют ${ displaystyle N}$ вертикальные линии ${ Displaystyle х = я}$ . Вторая часть имеет набор вершин ${ Displaystyle V = {v_ {1}, ldots, v_ {N} }}$ , где вершины соответствуют ${ displaystyle N}$ горизонтальные линии ${ displaystyle y = j}$ . Третья часть имеет набор вершин ${ Displaystyle W = {w_ {1}, ldots, w_ {2N} },}$ , где вершины соответствуют ${ displaystyle 2N}$ наклонные линии ${ displaystyle y = -x + k}$ с уклоном ${ displaystyle -1}$ . Мы рисуем ребро между двумя вершинами, если соответствующие прямые пересекаются в точке в ${ displaystyle A '}$ .

Давайте теперь подумаем о треугольниках во вспомогательном графе ${ displaystyle G}$ . Обратите внимание, что для каждой точки ${ Displaystyle х в А '}$ , вершины ${ displaystyle G}$ соответствующие горизонтальным, вертикальным и наклонным линиям, проходящим через ${ displaystyle x}$ сформировать треугольник в ${ displaystyle G}$ . Проверка случая показывает, что если ${ displaystyle G}$ содержит любой другой треугольник, тогда будет угол или анти-угол, поэтому ${ displaystyle G}$ не содержит другого треугольника. С этой характеристикой всех треугольников в ${ displaystyle G}$ обратите внимание, что каждый край ${ displaystyle G}$ (соответствует пересечению прямых в некоторой точке ${ Displaystyle х в А '}$ ) содержится ровно в одном треугольнике (а именно в треугольнике с вершинами, соответствующими трем прямым, проходящим через ${ Displaystyle х в А '}$ ). Это хорошо известное следствие лемма об удалении треугольника что график на ${ displaystyle n}$ вершины, в которых каждое ребро находится в уникальном треугольнике, имеют ${ Displaystyle о (п ^ {2})}$ края. Следовательно, ${ displaystyle G}$ имеет ${ displaystyle o (N ^ {2})}$ края. Но обратите внимание, что мы можем посчитать края ${ displaystyle G}$ точно, просто посчитав все пересечения в точках в ${ displaystyle A '}$ - Существуют ${ displaystyle 3 | A '|}$ такие пересечения. Следовательно, ${ Displaystyle 3 | A | '= | E (G) | = о (N ^ {2})}$ , откуда ${ Displaystyle | A '| = о (N ^ {2})}$ . Это завершает доказательство.

Доказательство теоремы Рота из теоремы углов

Теорема Рота - частный случай Теорема Семереди для арифметических прогрессий длины 3.

Теорема Рота. Если ${ Displaystyle А substeq {1,2, ldots, N }}$ не содержит трехчленной арифметической прогрессии, тогда ${ Displaystyle | A | = о (N)}$

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

У нас есть ${ Displaystyle А substeq {1,2, ldots, N }}$ который не содержит 3-членной арифметической прогрессии. Определите следующий набор

${ displaystyle B = {(x, y) in {1,2, ldots, 2N } times {1,2, ldots, 2N } | x-y in A }}$ .

Для каждого ${ displaystyle a in A}$ , есть как минимум ${ displaystyle N}$ пары ${ Displaystyle (х, у) в {1,2, ldots, 2N } раз {1,2, ldots, 2N }}$ такой, что ${ Displaystyle х-у = а}$ . Для разных ${ displaystyle a_ {1}, a_ {2} in A}$ , эти соответствующие пары явно различны. Следовательно, ${ displaystyle | B | geq N | A |}$ .

От противоречия скажем, что ${ displaystyle B}$ содержит угол ${ Displaystyle {(х, у), (х + ч, у), (х, у + ч) }}$ . потом ${ displaystyle A}$ содержит элементы ${ Displaystyle х- (y + h), x-y, (x + h) -y}$ , которые образуют 3-членную арифметическую прогрессию - противоречие. Следовательно, ${ displaystyle B}$ без углов, поэтому по теореме об углах ${ Displaystyle | В | = о (N ^ {2})}$ .