Набор Салема – Спенсера

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

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

Примеры

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

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

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

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

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

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

Обобщение

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

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

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

Приложения

	а	б	с	д	и	ж	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	с	д	и	ж	г	час

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

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

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

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

Ссылки

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

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

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

[m53-1] Перейти обратно: ^а ^б Мозер, Лео (1953), «О неусредняемых множествах целых чисел», Canadian Journal of Mathematics , 5 : 245–252, doi : 10.4153/cjm-1953-027-0 , MR 0053140 , S2CID 124488483

[ggk-2] Перейти обратно: ^а ^б ^с Гасарч, Уильям ; Гленн, Джеймс; Краскал, Клайд П. (2008), «Нахождение больших 3-свободных множеств. I. Случай малого $n$ » (PDF) , Journal of Computer and System Sciences , 74 (4): 628–655, doi : 10.1016/j. jcss.2007.06.002 , МР 2417032

[a76-3] Эбботт, Х.Л. (1976), «О гипотезе Эрдеша и Штрауса о неусредняющих множествах целых чисел», Труды Пятой Британской комбинаторной конференции (Университет Абердина, Абердин, 1975) , Congressus Numerantium, vol. XV, Виннипег, Манитоба: Utilitas Math., стр. 1–4, MR 0406967.

[d12-4] Перейти обратно: ^а ^б ^с ^д Дыбизбанский, Януш (2012), «Последовательности, не содержащие трехчленных арифметических прогрессий» , Электронный журнал комбинаторики , 19 (2): P15:1–P15:5, doi : 10.37236/2061 , MR 2928630

[5] Слоан, Нью-Джерси (редактор), «Последовательность A005836» , Интернет -энциклопедия целочисленных последовательностей , Фонд OEIS

[elrss-6] Эрдеш, П .; Лев, В.; Рози, Г.; Шандор, К.; Саркози, А. (1999), «Жадный алгоритм, арифметические прогрессии, суммы подмножеств и делимость», Discrete Mathematics , 200 (1–3): 119–135, doi : 10.1016/S0012-365X(98)00385-9 , MR 1692285

[ss42-7] Салем, Р. ; Спенсер, округ Колумбия (декабрь 1942 г.), «О наборах целых чисел, которые не содержат трех членов в арифметической прогрессии», Труды Национальной академии наук , 28 (12): 561–563, Bibcode : 1942PNAS...28..561S , дои : 10.1073/pnas.28.12.561 , PMC 1078539 , PMID 16588588

[et36-8] Эрдеш, Пол ; Туран, Пол (1936), «О некоторых последовательностях целых чисел» (PDF) , Журнал Лондонского математического общества , 11 (4): 261–264, doi : 10.1112/jlms/s1-11.4.261 , MR 1574918

[b46-9] Перейти обратно: ^а ^б ^с ^д Беренд, Ф.А. (декабрь 1946 г.), «О множествах целых чисел, которые не содержат трех членов арифметической прогрессии», Proceedings of the National Academy of Sciences , 32 (12): 331–332, Bibcode : 1946PNAS...32..331B , дои : 10.1073/pnas.32.12.331 , ПМК 1078964 , ПМИД 16578230

[r52-10] Рот, Клаус (1952), «О некоторых наборах целых чисел», Études de l'Académie des Sciences , 234 : 388–390, MR 0046374

[bs19-11] Блум, Томас; Сисаск, Олаф (2019), «Логарифмические границы теоремы Рота через почти периодичность», Discrete Analysis , 2019 (4), arXiv : 1810.12791v2 , doi : 10.19086/da.7884 , S2CID 119583263

[hb87-12] Хит-Браун, Д.Р. (1987), «Наборы целых чисел, не содержащие арифметических прогрессий», Журнал Лондонского математического общества , вторая серия, 35 (3): 385–394, doi : 10.1112/jlms/s2-35.3.385 , MR 0889362

[s90-13] Семереди, Э. (1990), «Наборы целых чисел, не содержащие арифметических прогрессий», Acta Mathematica Hungarica , 56 (1–2): 155–158, doi : 10.1007/BF01903717 , MR 1100788

[b99-14] Бургейн, Дж. (1999), «О тройках в арифметической прогрессии», Geometric and Functional Analysis , 9 (5): 968–984, doi : 10.1007/s000390050105 , MR 1726234 , S2CID 392820

[s11-15] Сандерс, Том (2011), «О теореме Рота о прогрессиях», Annals of Mathematics , Second Series, 174 (1): 619–636, arXiv : 1011.0104 , doi : 10.4007/annals.2011.174.1.20 , MR 2811612 , S2CID 53331882

[b16-16] Блум, Т.Ф. (2016), «Количественное улучшение теоремы Рота об арифметических прогрессиях», Журнал Лондонского математического общества , вторая серия, 93 (3): 643–663, arXiv : 1405.5800 , doi : 10.1112/jlms/jdw010 , МР 3509957 , S2CID 27536138

[bs20-17] Блум, Томас; Сисаск, Олаф (2020), Преодоление логарифмического барьера в теореме Рота об арифметических прогрессиях , arXiv : 2007.03528 ; см. также Калаи, Гил (8 июля 2020 г.), «Чтобы подбодрить вас в трудные времена 7: Блум и Сисаск только что преодолели логарифмический барьер для теоремы Рота!» , Комбинаторика и многое другое.

[18] Келли, Зандер; Мека, Рагху (6 ноября 2023 г.). «Сильные границы для 3-прогрессий» . Материалы конференции 64-го ежегодного симпозиума IEEE по основам компьютерных наук (FOCS), 2023 г. ИИЭР: 933–973. arXiv : 2302.05537 . дои : 10.1109/FOCS57990.2023.00059 . ISBN 979-8-3503-1894-4 .

[19] Келли, Зандер; Мека, Рагху (10 февраля 2023 г.). «Сильные границы для 3-прогрессий». arXiv : 2302.05537 [ math.NT ].

[20] Сломан, Лейла (21 марта 2023 г.). «Неожиданное доказательство в области компьютерных наук ошеломило математиков» . Журнал Кванта .

[21] Блум, Томас Ф.; Сисаск, Олоф (31 декабря 2023 г.). «Границы Келли – Меки для множеств, свободных от трехчленных арифметических прогрессий» . Существенная теория чисел . 2 (1): 15–44. arXiv : 2302.07211 . дои : 10.2140/ent.2023.2.15 . ISSN 2834-4634 .

[22] Блум, Томас Ф.; Сисаск, Олоф (14 февраля 2023 г.). «Границы Келли-Меки для множеств, свободных от трехчленных арифметических прогрессий». arXiv : 2302.07211 [ math.NT ].

[23] Блум, Томас Ф.; Сисаск, Олоф (5 сентября 2023 г.). «Улучшение границ Келли-Мека для трехчленных арифметических прогрессий». arXiv : 2309.02353 [ math.NT ].

[e11-24] Перейти обратно: ^а ^б Элкин, Майкл (2011), «Улучшенная конструкция множеств без прогрессий», Israel Journal of Mathematics , 184 : 93–128, arXiv : 0801.4310 , doi : 10.1007/s11856-011-0061-1 , MR 2823971

[gw10-25] Грин, Бен ; Вольф, Джулия (2010), «Заметка об улучшении Элкиным конструкции Беренда», Чудновский, Дэвид ; Чудновский, Грегори (ред.), Аддитивная теория чисел: Festschrift в честь шестидесятилетия Мелвина Б. Натансона , Нью-Йорк: Springer, стр. 141–144, arXiv : 0810.0732 , doi : 10.1007/978-0-387- 68361-4_9 , МР 2744752 , S2CID 10475217

[r61-26] Рэнкин, Р.А. (1961), «XXIV: Наборы целых чисел, содержащие не более заданного числа членов арифметической прогрессии», Труды Королевского общества Эдинбурга, Раздел A: Математические и физические науки , 65 (4): 332– 344, номер документа : 10.1017/S0080454100017726 , S2CID 122037820

[rs78-27] Ружа, Издательство ; Семереди, Э. (1978), «Тройные системы без шести точек, несущих три треугольника», Комбинаторика (Труды пятого венгерского коллоквиума, Кестхей, 1976), Vol. II , коллок. Математика. Соц. Янош Бояи, том. 18, Амстердам и Нью-Йорк: Северная Голландия, стр. 939–945, МР 0519318

[cw90-28] Копперсмит, Дон ; Виноград, Шмуэль (1990), «Умножение матриц посредством арифметических прогрессий», Журнал символических вычислений , 9 (3): 251–280, doi : 10.1016/S0747-7171(08)80013-2 , MR 1056627

[l12-29] Липмаа, Хельгер (2012), «Множества без прогрессии и неинтерактивные аргументы с нулевым разглашением на основе сублинейных пар» , в Крамере, Рональде (ред.), Теория криптографии: 9-я конференция по теории криптографии, TCC 2012, Таормина, Сицилия, Италия, 19–21 марта 2012 г., Труды , Конспекты лекций по информатике, том. 7194, Springer, стр. 169–189, номер документа : 10.1007/978-3-642-28914-9_10.

[ab17-30] Аббуд, Амир; Бодвин, Грег (2017), «Показатель аддитивного гаечного ключа 4/3 плотен», Журнал ACM , 64 (4): A28:1–A28:20, arXiv : 1511.00700 , doi : 10.1145/3088511 , MR 3702458 , S2CID 209870748

[abhs17-31] Аббуд, Амир; Брингманн, Карл ; Гермелин, Дэнни; Шабтай, Двир (2019), «Нижние границы на основе SETH для суммы подмножества и пути бикритериев», в Чан, Тимоти М. (редактор), Труды тридцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, SODA 2019, Сан-Диего , Калифорния, США, 6-9 января 2019 г. , Общество промышленной и прикладной математики, стр. 41–57, arXiv : 1704.04546 , doi : 10.1137/1.9781611975482.3 , S2CID 15802062

[ch-32] Кокейн, Э.Дж.; Хедетниеми, С.Т. (1986), «О проблеме доминирования диагональных ферзей», Журнал комбинаторной теории , серия A, 42 (1): 137–139, doi : 10.1016/0097-3165(86)90012-9 , MR 0843468

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

[ 24 ]

[ 25 ]

[ 26 ]

[ 27 ]

[ 28 ]

[ 29 ]

[ 30 ]

[ 31 ]

[ 32 ]