Теорема Эрдеша – Семереди - Erdős–Szemerédi theorem

В арифметическая комбинаторика, то Теорема Эрдеша – Семереди, доказано Пол Эрдёш и Эндре Семереди в 1983 г.^[1] заявляет, что для каждого конечный набор из действительные числа, либо попарные суммы, либо попарные произведения чисел в наборе образуют значительно больший набор. Точнее, он утверждает существование положительных констант c и ${\displaystyle \varepsilon }$ такой, что

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

в любое время А конечное непустое множество действительных чисел мощности |А|, где ${\displaystyle A+A=\{a+b:a,b\in A\}}$ это сумма-набор из А с собой, и ${\displaystyle A\cdot A=\{ab:a,b\in A\}}$.

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

Эрдёш и Семереди предположили, что можно взять ${\displaystyle \varepsilon }$ как бы близок к 1. Лучший результат в этом направлении на данный момент у Георгия Шакана,^[3] кто показал, что можно взять ${\displaystyle \varepsilon }$ произвольно близко к ${\displaystyle 1/3+5/5277}$. Ранее Миша Руднев, Илья Шкредов и Софи Стивенс показали, что можно ${\displaystyle \varepsilon }$ произвольно близко к ${\displaystyle 1/3+1/1509}$,^[4] улучшение более раннего результата Йожеф Солимоши,^[5] кто показал, что его можно сколь угодно близко к${\displaystyle 1/3}$.

внешняя ссылка

• Как странная сетка выявляет скрытые связи между простыми числами - Журнал Quanta статья о феномене сумм-произведения.

Рекомендации

1. Эрдеш, Пол; Семереди, Эндре (1983), «О суммах и произведениях целых чисел» (PDF), Исследования по чистой математике. Памяти Пауля Турана, Базель: Birkhäuser Verlag, стр. 213–218, Дои:10.1007/978-3-0348-5438-2_19, ISBN  978-3-7643-1288-6, МИСТЕР  0820223.
2. Тао, Теренс (2009), "Явление сумм-произведений в произвольных кольцах", Вклад в дискретную математику, 4 (2): 59–82, arXiv:0806.2497, Bibcode:2008arXiv0806.2497T, HDL:10515 / sy5r78637, МИСТЕР  2592424.
3. Шакан, Джордж (2018). «О разложении высших энергий и феномене суммарного произведения». arXiv:1803.04637 [math.NT ].
4. Руднев, Миша; Шкредов, Илья Д .; Стивенс, Софи (2016). "Об энергетическом варианте гипотезы о суммах произведений". arXiv:1607.05053 [math.CO ].
5. Солимоши, Йожеф (2009), "Ограничение мультипликативной энергии суммой", Успехи в математике, 222 (2): 402–408, arXiv:0806.1040, Дои:10.1016 / j.aim.2009.04.006, МИСТЕР  2538014.