Теорема Эрдеша–Семереди

В арифметической комбинаторике теорема Эрдёша –Семереди утверждает, что для любого конечного множества $A$ целых чисел по крайней мере одно из множеств $A + A$ и $A \cdot A$ (множества попарных сумм и попарных произведений соответственно) образуют значительно большее множество. Точнее, теорема Эрдёша–Семереди утверждает, что существуют положительные константы $c$ и $ε$ такие, что для любого непустого множества $A \subset ℕ$ ,

\max(|A+A|,|A\cdot A|)\geq c|A|^{1+\varepsilon }

Это было доказано Полом Эрдёшем и Эндре Семереди в 1983 году. ^[1] Обозначение $| A |$ обозначает мощность множества $A$ .

Множество попарных сумм равно $A + A = {a + b : a, b \in A}$ и называется множеством сумм $A.$

Множество попарных произведений имеет вид $A \cdot A = {a \cdot b : a, b \in A}$ и называется множеством произведений $A$ ; оно также обозначается как $AA$ .

Теорема является версией максимы, что аддитивная структура и мультипликативная структура не могут сосуществовать. Ее также можно рассматривать как утверждение, что вещественная прямая не содержит никакого множества, напоминающего конечное подкольцо или конечное подполе ; это первый пример того, что теперь известно как явление суммы-произведения , которое, как теперь известно, выполняется в широком спектре колец и полей, включая конечные поля. ^[2]

Гипотеза суммы-произведения

Гипотеза суммы-произведения неформально утверждает, что одно из множеств суммы или произведения любого множества должно быть почти как можно больше. Первоначально она была выдвинута Эрдёшем в 1974 году для того, чтобы установить, является ли $A$ множеством целых, действительных или комплексных чисел. ^[3] Точнее, она предполагает, что для любого множества $A \subset ℂ$ , мы имеем

$\max(|A+A|,|AA|)\geq |A|^{2-o(1)}.$

Асимптотический параметр в записи $o (1)$ равен $| A |$ .

Примеры

Если $A = {1, 2, 3, \dots, n}$ , то $| A + A | = 2| A | - 1 = O (| A |)$ с использованием асимптотической записи , где $| A |$ асимптотический параметр. Неформально это говорит о том, что множество сумм $A$ не растет. С другой стороны, множество произведений $A$ удовлетворяет ограничению вида $| A \cdot A | \geq | A | 2 - ε$ для всех $ε > 0$ . Это связано с задачей таблицы умножения Эрдёша . ^[4] Лучшая нижняя граница для $| A \cdot A |$ для этого множества принадлежит Кевину Форду . ^[5]

Этот пример является примером версии «Несколько сумм, много произведений ^{» [6]} задачи суммы-произведения Дьёрдя Элекеша и Имре З. Ружи . Следствием их результата является то, что любое множество с малым аддитивным удвоением (такое как арифметическая прогрессия ) имеет нижнюю границу на множестве произведений $| AA | = Ω(| A | 2 log -1 (| A |))$ . Сюй и Чжоу доказали ^[7] , что $| AA | = Ω(| A | 2 log 1-2log(2)- o (1) (| A |))$ для любого плотного подмножества $A$ арифметической прогрессии в целых числах, которое является точным с точностью до $o (1)$ в показателе степени.

Наоборот, набор $B = {2, 4, 8, \dots, 2 n}$ удовлетворяет $| BB | = 2| B | - 1$ , но имеет много сумм: . Эта граница получается из рассмотрения двоичного представления числа. Набор $B$ является примером геометрической прогрессии . $|B+B|={\binom {|B|+1}{2}}$

Для случайного набора из $n$ чисел как множество произведений, так и множество сумм имеют мощность ; то есть с высокой вероятностью ни множество сумм, ни множество произведений не генерируют повторяющихся элементов. ${\binom {n+1}{2}}$

Острота предположения

Эрдёш и Семереди приводят пример достаточно гладкого множества целых чисел $A$ с границей

$\max\{|A+A|,|A\cdot A|\}\leq |A|^{2}e^{-{\frac {c\log |A|}{\log \log |A|}}}$ . ^[1]

Это показывает, что член $o (1)$ в гипотезе необходим.

Экстремальные случаи

Часто изучаются крайние случаи гипотезы:

мало сумм, много произведений (FSMP) : если $| A + A | ≪ | A |$ , то $| AA | \geq | A | 2- o (1)$ , ^[6] и
мало произведений, много сумм (FPMS) : если $| AA | ≪ | A |$ , то $| A + A | \geq | A | 2- o (1)$ . ^[8]

История и текущие результаты

Следующая таблица суммирует прогресс в решении проблемы суммы-произведения над вещественными числами. Показатели 1/4 Дьёрдя Элекеша и 1/3 Йожефа Шоймоши считаются важными результатами в цитируемой литературе. Все улучшения после 2009 года имеют вид $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}⁠1/3⁠ + c$ , и представляют собой уточнения аргументов Конягина и Шкредова.^[9]

Комплексные числа

Методы доказательства, включающие только теорему Семереди–Троттера, автоматически распространяются на комплексные числа, поскольку теорема Семереди–Троттера верна для $ℂ 2$ по теореме Тота. ^[20] Конягин и Руднев ^[21] сопоставили показатель степени 4/3 с комплексными числами. Результаты с показателями вида $⁠$ $4 / 3 ⁠ + c$ не были сопоставлены по комплексным числам.

Над конечными полями

Проблема суммы-произведения особенно хорошо изучена над конечными полями . Мотивированный гипотезой Какея о конечном поле , Вольф предположил, что для каждого подмножества $A \subseteq 𝔽 p$ , где $p$ — (большое) простое число, $max(| A + A |, | AA |) \geq min(p, | A | 1+ ε)$ для абсолютной константы $ε > 0$ . Эта гипотеза также была сформулирована в 1990-х годах Вигдерсоном ^[22], мотивированным экстракторами случайности .

Обратите внимание, что задача суммы-произведения не может выполняться в конечных полях безусловно из-за следующего примера:

Пример: Пусть $𝔽$ — конечное поле и возьмём $A = 𝔽$ . Тогда, поскольку $𝔽$ замкнуто относительно сложения и умножения, $A + A = AA = 𝔽$ , и поэтому $| A + A | = | AA | = | 𝔽 |$ . Этот патологический пример распространяется на то, чтобы взять $A$ как любое подполе рассматриваемого поля.

Качественно задача суммы-произведения решена над конечными полями:

Теорема (Бурген, Кац, Тао (2004)): ^[23] Пусть $p$ — простое число и пусть $A \subset 𝔽 p$ с $p δ < | A | < p 1- δ$ для некоторого $0 < δ < 1.$ Тогда $max(| A + A |, | AA |) \geq c δ | A | 1+ ε$ для некоторого $ε = ε (δ) > 0$ .

Бургейн , Кац и Тао распространили эту теорему на произвольные поля. Неформально следующая теорема гласит, что если достаточно большое множество не растет ни при сложении, ни при умножении, то оно в основном содержится в дилате подполя.

Теорема (Бурген, Кац, Тао (2004)): ^[23] Пусть $A$ — подмножество конечного поля $𝔽$ , такое что $| A | > | 𝔽 | δ$ для некоторого $0 < δ < 1$ , и предположим, что $| A + A |, | AA | \leq K | A |$ . Тогда существует подполе $G \subset 𝔽$ с $| G | \leq K C δ | A |$ , элемент $x ∈ 𝔽 \ {0}$ и множество $X \subset 𝔽$ с $| X | \leq K C δ$ , такое что $A \subseteq xG \cup X$ .

Они предполагают, что константа $C δ$ может не зависеть от $δ$ .

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

Маленькие наборы

В этом режиме пусть $𝔽$ будет полем характеристики $p$ . Обратите внимание, что поле не всегда конечно. Когда это так, и характеристика $𝔽$ равна нулю, то $p$ -ограничение опускается.

В полях с не простым порядком $p$ -ограничение на $A \subset 𝔽$ можно заменить предположением, что $A$ не имеет слишком большого пересечения с любым подполем. Лучшая работа в этом направлении принадлежит Ли и Роше-Ньютону ^[30], которые достигли показателя $δ = ⁠ 1 / 19 ⁠$ в обозначениях приведенной выше таблицы.

Большие наборы

Когда $𝔽 = 𝔽 p$ для $p$ простого числа, проблема суммы-произведения считается решенной благодаря следующему результату Гараева: ^[31]

Теорема (Гараев (2007)): Пусть $A \subset 𝔽 p$ . Тогда $max(| A + A |, | AA |) ≫ min(p 1/2 | A | 1/2, | A | 2 p -1/2)$ .

Это оптимально в диапазоне $| A | \geq p 2/3$ .

Этот результат был распространен на конечные поля не простого порядка Винем ^[32] в 2011 году.

Варианты и обобщения

Другие комбинации операторов

Бургейн и Чанг доказали безусловный рост для множеств $A \subseteq ℤ$ , если рассмотреть достаточно много сумм или произведений:

Теорема (Бурген, Чанг (2003)): ^[33] Пусть $b \in ℕ$ . Тогда существует $k \in ℕ$ такой, что для всех $A \subseteq ℤ$ , имеем $max(| kA |, | A (k) |) = max(| A + A + \dots + A |, | A \cdot A \cdot \dots \cdot A |) \geq | A | b$ .

Во многих работах сложение и умножение объединены в одном выражении. С девизом сложение и умножение не могут сосуществовать, можно ожидать, что любая нетривиальная комбинация сложения и умножения множества должна гарантировать рост. Обратите внимание, что в конечных условиях или в полях с нетривиальными подполями такое утверждение требует дополнительных ограничений.

Интересующие нас наборы включают (результаты для $A \subset ℝ$ ):

$AA + A$ : Стивенс и Уоррен^[34] показывают, что $| AA + A | ≫ | A | ⁠ 3 / 2 ⁠ + ⁠ 3 / 170 ⁠ - о (1)$
$A (A + A)$ : Мерфи, Рош-Ньютон и Шкредов^[35] показывают, что $| A (A + A) | ≫ | A | ⁠ 3 / 2 ⁠ + ⁠ 5 / 242 ⁠ - о (1)$
$A (A + 1)$ : Стивенс и Уоррен^[34] показывают, что $| A (A + 1) | ≫ | A | ⁠ 49 / 38 ⁠ - о (1)$
$AA + AA$ : Стивенс и Руднев^[19] показывают, что $| AA + AA | ≫ | A | ⁠ 127 / 80 ⁠ - о (1)$

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

Ссылки

^ Аб Эрдеш, Пол ; Семереди, Эндре (1983), «О суммах и произведениях целых чисел», Исследования по чистой математике. Памяти Пауля Турана , Базель: Birkhäuser Verlag, стр. 213–218, CiteSeerX 10.1.1.210.6957 , doi : 10.1007/978-3-0348-5438-2_19, ISBN 978-3-7643-1288-6, МР 0820223.
^ Тао, Теренс (2009), «Явление суммы-произведения в произвольных кольцах», Вклад в дискретную математику , 4 (2): 59–82, arXiv : 0806.2497 , Bibcode : 2008arXiv0806.2497T, doi : 10.11575/cdm.v4i2.61994 , hdl : 10515/sy5r78637, MR 2592424.
^ П. Эрдёш: Некоторые недавние проблемы и результаты в теории графов, комбинаторике и теории чисел, Труды Седьмой юго-восточной конференции по комбинаторике, теории графов и вычислениям (Университет штата Луизиана, Батон-Руж, Луизиана, 1976), Конгресс. Номер. XVII, стр. 3--14, Utilitas Math., Виннипег, Ман., 1976 MR54 #10023; Zentralblatt 352.05024.
^ Эрдёш, Пауль (1960). «Асимптотическое неравенство в теории чисел». Вестник Ленинградского ун-та . 15 : 41–49. MR 0126424.
^ Форд, Кевин (1998), «Суммы и произведения из конечного набора действительных чисел», Аналитическая и элементарная теория чисел , Развитие математики, т. 1, Бостон, Массачусетс: Springer US, стр. 59–66, doi :10.1007/978-1-4757-4507-8_7, ISBN 978-1-4419-5058-1, S2CID 117873720 , получено 2021-07-09
^ аб Элекеш Дь., Дьёрдь; Ружа, Имре З. (1 августа 2003 г.). «Мало сумм, много продуктов». Studia Scientiarum Mathematicarum Hungarica . 40 (3): 301–308. дои : 10.1556/sscmath.40.2003.3.4. ISSN 0081-6906.
^ Сюй, Макс Вэньцян; Чжоу, Юнкунь (2022). «О множествах произведений арифметических прогрессий». arXiv : 2201.00104 [math.NT].
^ Мерфи, Брендан; Руднев, Миша; Шкредов Илья; Штейников, Юрий (2019). «Немногие продукты — проблема многих сумм». Journal de Théorie des Nombres de Bordeaux . 31 (3): 573–602. arXiv : 1712.00410 . дои : 10.5802/jtnb.1095. S2CID 119665080.
^ ab Конягин, СВ; Шкредов, ИД (август 2015). «О суммах множеств, имеющих малые произведения». Труды Математического института им. В.А. Стеклова РАН . 290 (1): 288–299. arXiv : 1503.05771 . doi :10.1134/s0081543815060255. ISSN 0081-5438. S2CID 117359454.
^ Эрдеш, П.; Семереди, Э. (1983), «О суммах и произведениях целых чисел», Исследования по чистой математике , Базель: Birkhäuser Basel, стр. 213–218, doi : 10.1007/978-3-0348-5438-2_19, ISBN 978-3-7643-1288-6, получено 2021-07-09
^ Натансон, Мелвин Б. (1997). «О суммах и произведениях целых чисел». Труды Американского математического общества . 125 (1): 9–16. doi : 10.1090/s0002-9939-97-03510-7 . ISSN 0002-9939.
^ Форд, Кевин (1998). «Суммы и произведения конечного набора действительных чисел». The Ramanujan Journal . 2 (1/2): 59–66. doi :10.1023/a:1009709908223. ISSN 1382-4090. S2CID 195302784.
^ Элекеш, Дьёрдь (1997). «О числе сумм и произведений». Акта Арифметика . 81 (4): 365–367. дои : 10.4064/aa-81-4-365-367 . ISSN 0065-1036.
^ Шоймоши, Йожеф (август 2005 г.). «О числе сумм и произведений». Бюллетень Лондонского математического общества . 37 (4): 491–494. doi :10.1112/s0024609305004261. ISSN 0024-6093. S2CID 56432429.
^ Солимоси, Йожеф (октябрь 2009 г.). «Ограничение мультипликативной энергии суммой». Достижения в математике . 222 (2): 402–408. arXiv : 0806.1040 . дои : 10.1016/j.aim.2009.04.006 . ISSN 0001-8708.
^ Конягин, С. В.; Шкредов, ИД (август 2016 г.). «Новые результаты о суммах и произведениях в ℝ». Труды Математического института им. В. А. Стеклова РАН . 294 (1): 78–88. doi :10.1134/s0081543816060055. ISSN 0081-5438. S2CID 126099880.
^ Руднев, Миша; Шкредов, Илья; Стивенс, Софи (2019-09-10). «Об энергетическом варианте гипотезы суммы-произведения». Revista Matemática Iberoamericana . 36 (1): 207–232. arXiv : 1607.05053 . doi : 10.4171/rmi/1126. ISSN 0213-2230. S2CID 119122310.
^ Шакан, Джордж (2018-07-03). «О разложениях высших энергий и явлении суммы–произведения». Математические труды Кембриджского философского общества . 167 (3): 599–617. arXiv : 1803.04637 . doi : 10.1017/s0305004118000506. ISSN 0305-0041. S2CID 119693920.
^ ab Руднев, Миша; Стивенс, Софи (2020). «Обновление проблемы суммы-произведения». arXiv : 2005.11145 [math.CO].
^ Тот, Чаба Д. (февраль 2015 г.). «Теорема Семереди-Троттера в комплексной плоскости». Комбинаторика . 35 (1): 95–126. arXiv : math/0305283 . дои : 10.1007/s00493-014-2686-2. ISSN 0209-9683. S2CID 13237229.
^ Конягин, Сергей В.; Руднев, Миша (январь 2013 г.). «О новых оценках типа суммы произведения». SIAM Journal по дискретной математике . 27 (2): 973–990. arXiv : 1111.4977 . дои : 10.1137/120886418. ISSN 0895-4801. S2CID 207065775.
^ Тревизан, Лука (2009-06-20). "Гостевая колонка". ACM SIGACT News . 40 (2): 50–66. doi :10.1145/1556154.1556170. ISSN 0163-5700. S2CID 12566158.
^ abc Бургейн, Жан; Кац, Нетс; Тао, Теренс (2004-02-01). "Оценка суммы-произведения в конечных полях и ее применение". Геометрический и функциональный анализ . 14 (1): 27–57. arXiv : math/0301343 . doi :10.1007/s00039-004-0451-1. ISSN 1016-443X. S2CID 14097626.
^ Гараев, МЗ (2010-07-08). "Явная оценка суммы-произведения в Fp". Международные уведомления по математическим исследованиям . arXiv : math/0702780 . doi :10.1093/imrn/rnm035. ISSN 1073-7928.
^ Бургейн, Гараев (2008). «О варианте оценок сумм-произведений и явных границах экспоненциальных сумм в простых полях». Math. Proc. Cambridge Philosophical Society . 146 (1): 1. Bibcode :2008MPCPS.146....1B. doi :10.1017/S0305004108001230. S2CID 120185078.
^ Ли, Лянпань (2011). «Немного улучшены оценки суммы произведений в полях простого порядка». Акта Арифметика . 147 (2): 153–160. arXiv : 0907.2051 . дои : 10.4064/aa147-2-4. ISSN 0065-1036. S2CID 15954935.
^ Руднев, Миша (2011-08-25). «Улучшенное неравенство суммы–произведения в полях простого порядка». International Mathematics Research Notices . 2012 (16): 3693–3705. arXiv : 1011.2738 . doi : 10.1093/imrn/rnr158. ISSN 1687-0247.
^ Рош-Ньютон, Оливер; Руднев, Миша; Шкредов, Илья Д. (2016). «Новые оценки типа суммы-произведения над конечными полями». Успехи математики . 293 : 589–605. arXiv : 1408.0542 . doi : 10.1016/j.aim.2016.02.019 .
^ Мохаммади, Стивенс (2021). «Достижение показателя 5/4 для задачи суммы-произведения в конечных полях». arXiv : 2103.08252 [math.CO].
^ Ли, Лянпань; Рош-Ньютон, Оливер (январь 2011 г.). «Улучшенная оценка суммы-произведения для общих конечных полей». SIAM Journal on Discrete Mathematics . 25 (3): 1285–1296. arXiv : 1101.5348 . doi : 10.1137/110823122. ISSN 0895-4801. S2CID 7024012.
^ Гараев, МЗ (2008-04-14). "Оценка суммы-произведения для больших подмножеств простых полей". Труды Американского математического общества . 136 (8): 2735–2739. arXiv : 0706.0702 . doi :10.1090/s0002-9939-08-09386-6. ISSN 0002-9939. S2CID 16064726.
^ Винь, Ле Ань (ноябрь 2011 г.). «Теорема типа Семереди–Троттера и оценка суммы-произведения в конечных полях». European Journal of Combinatorics . 32 (8): 1177–1181. arXiv : 0711.4427 . doi : 10.1016/j.ejc.2011.06.008 . ISSN 0195-6698.
^ Бургейн, Жан; Чанг, Мей-Чу (2003-11-25). «О размере $k$-кратной суммы и произведения множеств целых чисел». Журнал Американского математического общества . 17 (2): 473–497. arXiv : math/0309055 . Bibcode :2003math......9055B. doi :10.1090/s0894-0347-03-00446-6. ISSN 0894-0347. S2CID 15154515.
^ ab Стивенс, Уоррен (2021). «О суммах множеств выпуклых функций». arXiv : 2102.05446 [math.CO].
^ Мерфи, Брендан; Рош-Ньютон, Оливер; Шкредов, Илья Д. (январь 2017 г.). «Вариации на тему суммы-произведения II». Журнал SIAM по дискретной математике . 31 (3): 1878–1894. arXiv : 1703.09549 . doi :10.1137/17M112316X. ISSN 0895-4801. S2CID 207074281.

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

Хартнетт, Кевин (6 февраля 2019 г.). «Как странная сетка раскрывает скрытые связи между простыми числами». Журнал Quanta .