Сет Сейлема–Спенсера

Набор чисел без прогрессии

Для набора {1, 2, 4, 5, 10, 11, 13, 14} все средние точки двух элементов (28 желтых точек) оказываются за пределами набора, поэтому никакие три элемента не могут образовать арифметическую прогрессию.

В математике, и в частности в арифметической комбинаторике , множество Салема-Спенсера — это множество чисел, никакие три из которых не образуют арифметическую прогрессию . Множества Салема-Спенсера также называются последовательностями, свободными от 3-AP , или множествами, свободными от прогрессии . Их также называют неусредняющими множествами, ^{[1] [2],} но этот термин также используется для обозначения множества целых чисел, ни одно из которых не может быть получено как среднее значение любого подмножества других чисел. ^[3] Множества Салема-Спенсера названы в честь Рафаэля Салема и Дональда К. Спенсера , которые в 1942 году показали, что множества Салема-Спенсера могут иметь почти линейный размер. Однако более поздняя теорема Клауса Рота показывает, что размер всегда меньше линейного.

Примеры

Для наименьших значений таких, что числа от до имеют -элементное множество Сейлема-Спенсера, равны ${\displaystyle k=1,2,\dots }$ ${\displaystyle n}$ ${\displaystyle 1}$ ${\displaystyle n}$ ${\displaystyle k}$

1, 2, 4, 5, 9, 11, 13, 14, 20, 24, 26, 30, 32, 36, ... (последовательность A065825 в OEIS )

Например, среди чисел от 1 до 14 восемь чисел

{1, 2, 4, 5, 10, 11, 13, 14}

образуют уникальное самое большое множество Сейлема-Спенсера. ^[4]

Этот пример смещен путем добавления единицы к элементам бесконечного множества Сейлема–Спенсера, последовательности Стэнли

0, 1, 3, 4, 9, 10, 12, 13, 27, 28, 30, 31, 36, 37, 39, 40, ... (последовательность A005836 в OEIS )

чисел, которые, будучи записаны как троичные числа , используют только цифры 0 и 1. Эта последовательность является лексикографически первым бесконечным множеством Салема–Спенсера. ^[5] Другое бесконечное множество Салема–Спенсера задается кубами

0, 1, 8, 27, 64, 125, 216, 343, 512, 729, 1000, ... (последовательность A000578 в OEIS )

Теорема Леонарда Эйлера гласит , что никакие три куба не находятся в арифметической прогрессии. ^[6]

Размер

В 1942 году Салем и Спенсер опубликовали доказательство того, что целые числа в диапазоне от до имеют большие множества Салема–Спенсера, размером . ^[7] Знаменатель этого выражения использует большую нотацию O и растет медленнее, чем любая степень , поэтому множества, найденные Салемом и Спенсером, имеют размер, близкий к линейному. Эта граница опровергла гипотезу Пола Эрдёша и Пала Турана о том, что размер такого множества может быть не более для некоторых . ^{[4] [8]} Конструкция Салема и Спенсера была улучшена Феликсом Берендом в 1946 году, который нашел множества размера . ^[9] ${\displaystyle 1}$ ${\displaystyle n}$ ${\displaystyle n/e^{O(\log n/\log \log n)}}$ ${\displaystyle n}$ ${\displaystyle n^{1-\delta }}$ ${\displaystyle \delta >0}$ ${\displaystyle n/e^{O({\sqrt {\log n}})}}$

В 1952 году Клаус Рот доказал теорему Рота , устанавливающую, что размер множества Салема-Спенсера должен быть . ^[10] Следовательно, хотя множества, построенные Салемом, Спенсером и Берендом, имеют размеры, близкие к линейным, их невозможно улучшить и найти множества, размер которых на самом деле линейный. Этот результат стал частным случаем теоремы Семереди о плотности множеств целых чисел, которые избегают более длинных арифметических прогрессий. ^[4] Чтобы отличить границу Рота для множеств Салема-Спенсера от теоремы Рота о диофантовых приближениях алгебраических чисел , этот результат был назван теоремой Рота об арифметических прогрессиях . ^[11] После нескольких дополнительных улучшений теоремы Рота ^{[12] [13] [14] [15]} было доказано, что размер множества Салема-Спенсера равен . ^[16] Еще более точная граница (для некоторых из них , которые не были явно вычислены) была объявлена ​​в 2020 году в препринте. ^[17] В 2023 году новая граница ^{[18] [19] [20]} была найдена учеными-компьютерщиками Келли и Мекой, а вскоре после этого изложение в более привычных математических терминах было дано Блумом и Сисаском ^{[21] [22],} которые с тех пор также улучшили показатель степени Келли-Меки, связанный с (и предположенный ) в препринте. ^[23] ${\displaystyle O(n/\log \log n)}$ ${\displaystyle O{\bigl (}n(\log \log n)^{4}/\log n{\bigr )}}$ ${\displaystyle O{\bigl (}n/(\log n)^{1+\delta }{\bigr )}}$ ${\displaystyle \delta >0}$ ${\displaystyle \exp(-c(\log N)^{1/12})N}$ ${\displaystyle \beta =1/9}$ ${\displaystyle \beta =5/41}$

Строительство

Простая конструкция для множества Сейлема–Спенсера (размером значительно меньшим, чем граница Беренда) заключается в выборе троичных чисел , которые используют только цифры 0 и 1, а не 2. Такое множество должно быть свободным от прогрессии, поскольку если два его элемента и являются первым и вторым членами арифметической прогрессии, третий член должен иметь цифру два на позиции наименее значащей цифры, где и различаются. ^[4] На иллюстрации показан набор этой формы для трехзначных троичных чисел (сдвинутых на единицу, чтобы сделать наименьшим элементом 1 вместо 0). ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle y}$

Конструкция Беренда использует похожую идею для большего нечетного основания . Его набор состоит из чисел, цифры которых ограничены диапазоном от до (так что сложение этих чисел не имеет переносов), с дополнительным ограничением, что сумма квадратов цифр является некоторым выбранным значением . ^[9] Если цифры каждого числа рассматривать как координаты вектора, это ограничение описывает сферу в результирующем векторном пространстве, и в силу выпуклости среднее двух различных значений на этой сфере будет внутренним по отношению к сфере, а не на ней. ^[24] Следовательно, если два элемента набора Беренда являются конечными точками арифметической прогрессии, среднее значение прогрессии (их среднее) не будет в наборе. Таким образом, результирующий набор свободен от прогрессии. ^[9] ${\displaystyle 2d-1}$ ${\displaystyle 0}$ ${\displaystyle d-1}$ ${\displaystyle k}$

При тщательном выборе и выборе в качестве наиболее часто встречающейся суммы квадратов цифр Беренд достигает своей границы. ^[9] В 1953 году Лео Мозер доказал, что существует единственная бесконечная последовательность Салема–Спенсера, достигающая той же асимптотической плотности на каждом префиксе, что и конструкция Беренда. ^[1] Рассматривая выпуклую оболочку точек внутри сферы, а не множество точек на сфере, можно улучшить конструкцию в множитель . ^{[24] [25]} Однако это не влияет на ограничение размера в форме, указанной выше. ${\displaystyle d}$ ${\displaystyle k}$ ${\displaystyle {\sqrt {\log n}}}$

Обобщение

Понятие множеств Салема–Спенсера (3-AP-свободное множество) может быть обобщено до -AP-свободных множеств, в которых элементы образуют арифметическую прогрессию тогда и только тогда, когда они все равны. Ранкин (1961) дал конструкции больших -AP-свободных множеств. ^[26] ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$

Результаты вычислений

Гасарч, Гленн и Крускал провели сравнение различных вычислительных методов для больших подмножеств без арифметической прогрессии. ^[2] Используя эти методы, они нашли точный размер наибольшего такого множества для . Их результаты включают несколько новых границ для различных значений , найденных с помощью алгоритмов ветвей и границ , которые используют линейное программирование и проблемно-специфическую эвристику для ограничения размера, который может быть достигнут в любой ветви дерева поиска. Одной из эвристик, которую они сочли особенно эффективной, был метод третей , в котором две сдвинутые копии множества Салема–Спенсера для помещаются в первую и последнюю трети множества для . ^[2] ${\displaystyle \{1,\dots n\}}$ ${\displaystyle n\leq 187}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle 3n}$

Приложения

Пять ферзей на главной диагонали шахматной доски, атакующие все остальные поля. Свободные поля на диагонали находятся в строках 1, 3 и 7, нечетный набор Салема–Спенсера.

В связи с проблемой Ружи–Семереди множества Салема–Спенсера использовались для построения плотных графов, в которых каждое ребро принадлежит уникальному треугольнику . ^[27]

Множества Сейлема–Спенсера также использовались в теоретической информатике. Они использовались при разработке алгоритма Копперсмита–Винограда для быстрого умножения матриц , ^[28] и при построении эффективных неинтерактивных доказательств с нулевым разглашением . ^[29] Недавно они использовались для демонстрации нижних границ размера для остовов графов , ^[30] и строгой гипотезы экспоненциального времени , основанной на трудностях задачи суммы подмножества . ^[31]

Эти наборы также могут быть применены в развлекательной математике к математической шахматной задаче размещения как можно меньшего количества ферзей на главной диагонали шахматной доски так, чтобы все клетки доски были атакованы. Набор диагональных клеток, которые остаются незанятыми, должен образовывать набор Салема–Спенсера, в котором все значения имеют одинаковую четность (все нечетные или все четные). Наименьший возможный набор ферзей является дополнением к наибольшему подмножеству Салема–Спенсера нечетных чисел в . Это подмножество Салема–Спенсера можно найти, удвоив и вычтя единицу из значений в подмножестве Салема–Спенсера всех чисел в ^[32] ${\displaystyle n\times n}$ ${\displaystyle \{1,\dots n\}}$ ${\displaystyle \{1,\dots n/2\}.}$

Ссылки

1. Moser, Leo (1953), «О неусредняющих множествах целых чисел», Canadian Journal of Mathematics , 5 : 245–252, doi : 10.4153/cjm-1953-027-0 , MR  0053140, S2CID  124488483
2. Гасарч, Уильям ; Гленн, Джеймс; Крускаль, Клайд П. (2008), «Поиск больших 3-свободных множеств. I. Случай малых n» (PDF) , Журнал компьютерных и системных наук , 74 (4): 628–655, doi :10.1016/j.jcss.2007.06.002, MR  2417032
3. Эбботт, HL (1976), «О гипотезе Эрдёша и Штрауса о неусредняющих множествах целых чисел», Труды Пятой Британской комбинаторной конференции (Университет Абердина, Абердин, 1975) , Congressus Numerantium, т. XV, Виннипег, Манитоба: Utilitas Math., стр. 1–4, MR  0406967
4. Dybizbański, Janusz (2012), «Последовательности, не содержащие 3-членных арифметических прогрессий», Electronic Journal of Combinatorics , 19 (2): P15:1–P15:5, doi : 10.37236/2061 , MR  2928630
5. Слоан, Н. Дж. А. (ред.), «Последовательность A005836», Онлайновая энциклопедия целочисленных последовательностей , Фонд OEIS
6. Эрдеш, П .; Лев, В.; Рози, Г.; Шандор, К.; Саркози, А. (1999), «Жадный алгоритм, арифметические прогрессии, суммы подмножеств и делимость», Discrete Mathematics , 200 (1–3): 119–135, doi : 10.1016/S0012-365X(98)00385-9, MR  1692285
7. Салем, Р.; Спенсер , Д.К. (декабрь 1942 г.), «О множествах целых чисел, не содержащих трех членов арифметической прогрессии», Труды Национальной академии наук , 28 (12): 561–563, Bibcode : 1942PNAS...28..561S, doi : 10.1073/pnas.28.12.561 , PMC 1078539 , PMID  16588588 
8. Эрдёш, Пол ; Туран, Пол (1936), «О некоторых последовательностях целых чисел» (PDF) , Журнал Лондонского математического общества , 11 (4): 261–264, doi :10.1112/jlms/s1-11.4.261, MR  1574918
9. Беренд, ФА (декабрь 1946 г.), «О множествах целых чисел, которые не содержат трех членов в арифметической прогрессии», Труды Национальной академии наук , 32 (12): 331–332, Bibcode : 1946PNAS...32..331B, doi : 10.1073/pnas.32.12.331 , PMC 1078964 , PMID  16578230 
10. Рот, Клаус (1952), «Sur quelques ансамбли d'entiers», Comptes rendus de l'Académie des Sciences , 234 : 388–390, MR  0046374
11. Блум, Томас; Сисаск, Олаф (2019), «Логарифмические оценки теоремы Рота с помощью почти периодичности», Дискретный анализ , 2019 (4), arXiv : 1810.12791v2 , doi : 10.19086/da.7884, S2CID  119583263
12. Хит-Браун, DR (1987), «Целочисленные множества, не содержащие арифметических прогрессий», Журнал Лондонского математического общества , Вторая серия, 35 (3): 385–394, doi :10.1112/jlms/s2-35.3.385, MR  0889362
13. Семереди, Э. (1990), «Целочисленные множества, не содержащие арифметических прогрессий», Acta Mathematica Hungarica , 56 (1–2): 155–158, doi :10.1007/BF01903717, MR  1100788
14. Бургейн, Дж. (1999), «О тройках в арифметической прогрессии», Геометрический и функциональный анализ , 9 (5): 968–984, doi :10.1007/s000390050105, MR  1726234, S2CID  392820
15. Сандерс, Том (2011), «О теореме Рота о прогрессиях», Annals of Mathematics , вторая серия, 174 (1): 619–636, arXiv : 1011.0104 , doi : 10.4007/annals.2011.174.1.20, MR  2811612, S2CID  53331882
16. Bloom, TF (2016), «Количественное улучшение теоремы Рота об арифметических прогрессиях», Журнал Лондонского математического общества , Вторая серия, 93 (3): 643–663, arXiv : 1405.5800 , doi : 10.1112/jlms/jdw010, MR  3509957, S2CID  27536138
17. Блум, Томас; Сисаск, Олаф (2020), Преодоление логарифмического барьера в теореме Рота об арифметических прогрессиях , arXiv : 2007.03528; см. также Калай, Джил (8 июля 2020 г.), «Чтобы подбодрить вас в трудные времена 7: Блум и Сисаск только что преодолели логарифмический барьер для теоремы Рота!», Комбинаторика и многое другое
18. Келли, Зандер; Мека, Рагху (2023-11-06). «Сильные границы для 3-прогрессий». 2023 IEEE 64-й ежегодный симпозиум по основам компьютерной науки (FOCS) . IEEE. стр. 933–973. arXiv : 2302.05537 . doi : 10.1109/FOCS57990.2023.00059. ISBN 979-8-3503-1894-4.
19. Келли, Зандер; Мека, Рагху (2023-02-10). «Сильные границы для 3-прогрессий». arXiv : 2302.05537 [math.NT].
20. Сломан, Лейла (21.03.2023). «Неожиданное доказательство компьютерной науки ошеломило математиков». Журнал Quanta .
21. Блум, Томас Ф.; Сисаск, Олоф (2023-12-31). «Границы Келли–Мека для множеств, свободных от трехчленных арифметических прогрессий». Essential Number Theory . 2 (1): 15–44. arXiv : 2302.07211 . doi :10.2140/ent.2023.2.15. ISSN  2834-4634.
22. Блум, Томас Ф.; Сисаск, Олоф (2023-02-14). «Границы Келли–Мека для множеств, свободных от трехчленных арифметических прогрессий». Essential Number Theory . 2 : 15–44. arXiv : 2302.07211 . doi :10.2140/ent.2023.2.15.
23. Блум, Томас Ф.; Сисаск, Олоф (2023-09-05). «Улучшение границ Келли-Мека для трехчленных арифметических прогрессий». arXiv : 2309.02353 [math.NT].
24. Elkin, Michael (2011), «Улучшенная конструкция множеств без прогрессии», Israel Journal of Mathematics , 184 : 93–128, arXiv : 0801.4310 , doi : 10.1007/s11856-011-0061-1 , MR  2823971
25. Грин, Бен ; Вольф, Джулия (2010), «Заметка об улучшении Элкиным конструкции Беренда», в Чудновский, Дэвид ; Чудновский, Грегори (ред.), Аддитивная теория чисел: юбилейный сборник в честь шестидесятилетия Мелвина Б. Натансона , Нью-Йорк: Springer, стр. 141–144, arXiv : 0810.0732 , doi : 10.1007/978-0-387-68361-4_9, ISBN 978-0-387-37029-3, MR  2744752, S2CID  10475217
26. Ранкин, РА (1961), «XXIV: Множества целых чисел, содержащие не более заданного числа членов арифметической прогрессии», Труды Королевского общества Эдинбурга, Раздел A: Математические и физические науки , 65 (4): 332–344, doi :10.1017/S0080454100017726, S2CID  122037820
27. Ружа, ИЗ ; Семереди, Э. (1978), «Тройные системы без шести точек, несущих три треугольника», Комбинаторика (Труды пятого венгерского коллоквиума, Кестхей, 1976), Vol. II , коллок. Математика. Соц. Янош Бояи, том. 18, Амстердам и Нью-Йорк: Северная Голландия, стр. 939–945, MR  0519318.
28. Копперсмит, Дон ; Виноград, Шмуэль (1990), «Умножение матриц с помощью арифметических прогрессий», Журнал символических вычислений , 9 (3): 251–280, doi : 10.1016/S0747-7171(08)80013-2 , MR  1056627
29. Липмаа, Хельгер (2012), «Прогрессионно-свободные множества и неинтерактивные аргументы с нулевым знанием на основе сублинейного спаривания», в Крамер, Рональд (ред.), Теория криптографии: 9-я конференция по теории криптографии, TCC 2012, Таормина, Сицилия, Италия, 19–21 марта 2012 г., Труды , Заметки лекций по информатике, т. 7194, Springer, стр. 169–189, doi : 10.1007/978-3-642-28914-9_10 , ISBN 978-3-642-28913-2
30. Аббуд, Амир; Бодвин, Грег (2017), «4/3 аддитивный показатель степени спаннера является жестким», Журнал ACM , 64 (4): A28:1–A28:20, arXiv : 1511.00700 , doi : 10.1145/3088511, MR  3702458, S2CID  209870748
31. Аббуд, Амир; Брингманн, Карл ; Хермелин, Дэнни; ​​Шабтай, Двир (2019), «Нижние границы на основе SETH для суммы подмножества и пути бикритерия», в Чан, Тимоти М. (ред.), Труды тридцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, SODA 2019, Сан-Диего, Калифорния, США, 6-9 января 2019 г. , Общество промышленной и прикладной математики, стр. 41–57, arXiv : 1704.04546 , doi : 10.1137/1.9781611975482.3, ISBN 978-1-61197-548-2, S2CID  15802062
32. Кокейн, Э. Дж.; Хедетниеми, СТ (1986), «О проблеме доминирования диагональных ферзей», Журнал комбинаторной теории , Серия A, 42 (1): 137–139, doi : 10.1016/0097-3165(86)90012-9, MR  0843468

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

• Поиск неусредняющих множеств, Ярек Вроблевский, Вроцлавский университет