Набор Салема – Спенсера - Salem–Spencer set

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

В 1952 г. Клаус Рот доказано Теорема Рота установление того, что размер набора Салема-Спенсера должен быть ${\displaystyle O(n/\log \log n)}$.^[10] Это частный случай Теорема Семереди от плотности наборов целых чисел, чтобы избежать более длинных арифметических прогрессий.^[4]Чтобы отличить этот результат от Теорема Рота на Диофантово приближение из алгебраические числа, этот результат был назван Теорема Рота об арифметических прогрессиях.^[11]После нескольких дополнительных улучшений теоремы Рота^{[12][13][14][15]} размер набора Салема – Спенсера оказался ${\displaystyle O{\bigl (}n(\log \log n)^{4}/\log n{\bigr )}}$.^[16]

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

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

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

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

Результаты расчетов

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

Приложения

	а	б	c	d	е	ж	грамм	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	c	d	е	ж	грамм	час

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

В связи с Проблема Ружи – Семереди, Множества Салема – Спенсера использовались для построения плотных графов, в которых каждое ребро принадлежит уникальному треугольнику.^[19] Они также были использованы в дизайне Алгоритм Копперсмита – Винограда для быстрого матричное умножение,^[20] и в построении эффективных неинтерактивные доказательства с нулевым разглашением.^[21]

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

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

1. Мозер, Лев (1953), «О множествах целых чисел без усреднения», Канадский математический журнал, 5: 245–252, Дои:10.4153 / cjm-1953-027-0, МИСТЕР  0053140
2. Гасарх, Уильям; Гленн, Джеймс; Крускал, Клайд П. (2008), "Поиск больших наборов из трех свободных предметов. I. Маленькие п дело" (PDF), Журнал компьютерных и системных наук, 74 (4): 628–655, Дои:10.1016 / j.jcss.2007.06.002, МИСТЕР  2417032
3. Эбботт, Х. Л. (1976), "Об одной гипотезе Эрдеша и Штрауса о неусредняющих множествах целых чисел", Труды Пятой Британской комбинаторной конференции (Абердинский университет, Абердин, 1975 г.), Congressus Numerantium, XV, Виннипег, Манитоба: Utilitas Math., Стр. 1–4, МИСТЕР  0406967
4. Дибизбанский, Януш (2012), «Последовательности, не содержащие трехчленных арифметических прогрессий», Электронный журнал комбинаторики, 19 (2): P15: 1 – P15: 5, МИСТЕР  2928630
5. Слоан, Н. Дж. А. (ред.). «Последовательность A005836». В Он-лайн энциклопедия целочисленных последовательностей. Фонд OEIS.
6. Эрдеш, П.; Лев, В .; Rauzy, G .; Sándor, C .; Шаркози, А. (1999), "Жадный алгоритм, арифметические прогрессии, суммы подмножеств и делимость", Дискретная математика, 200 (1–3): 119–135, Дои:10.1016 / S0012-365X (98) 00385-9, МИСТЕР  1692285
7. Салем, Р.; Спенсер, Д. (Декабрь 1942 г.), «О наборах целых чисел, не содержащих трех членов в арифметической прогрессии», Труды Национальной академии наук, 28 (12): 561–563, Дои:10.1073 / pnas.28.12.561, ЧВК  1078539, PMID  16588588
8. Эрдеш, Пол; Туран, Пол (1936), «О некоторых последовательностях целых чисел» (PDF), Журнал Лондонского математического общества, 11 (4): 261–264, Дои:10.1112 / jlms / s1-11.4.261, МИСТЕР  1574918
9. Беренд, Ф.А. (Декабрь 1946 г.), «О наборах целых чисел, не содержащих трех членов в арифметической прогрессии», Труды Национальной академии наук, 32 (12): 331–332, Дои:10.1073 / pnas.32.12.331, ЧВК  1078964, PMID  16578230
10. Рот, Клаус (1952), "Sur quelques ensembles d'entiers", Comptes rendus de l'Académie des Sciences, 234: 388–390, МИСТЕР  0046374
11. Блум, Томас; Сисаск, Олаф (2019), "Логарифмические оценки теоремы Рота через почти периодичность", Дискретный анализ, 2019 (4), arXiv:1810.12791v2, Дои:10.19086 / da.7884
12. Хит-Браун, Д. (1987), «Целочисленные множества, не содержащие арифметических прогрессий», Журнал Лондонского математического общества, Вторая серия, 35 (3): 385–394, Дои:10.1112 / jlms / s2-35.3.385, МИСТЕР  0889362
13. Семереди, Э. (1990), «Целочисленные множества, не содержащие арифметических прогрессий», Acta Mathematica Hungarica, 56 (1–2): 155–158, Дои:10.1007 / BF01903717, МИСТЕР  1100788
14. Бургейн, Дж. (1999), «О троек в арифметической прогрессии», Геометрический и функциональный анализ, 9 (5): 968–984, Дои:10.1007 / с000390050105, МИСТЕР  1726234
15. Сандерс, Том (2011), «О теореме Рота о прогрессиях», Анналы математики, Вторая серия, 174 (1): 619–636, arXiv:1011.0104, Дои:10.4007 / летопись.2011.174.1.20, МИСТЕР  2811612
16. Блум, Т. Ф. (2016), "Количественное улучшение теоремы Рота об арифметических прогрессиях", Журнал Лондонского математического общества, Вторая серия, 93 (3): 643–663, arXiv:1405.5800, Дои:10.1112 / jlms / jdw010, МИСТЕР  3509957
17. Элькин, Майкл (2011), "Улучшенная конструкция наборов без прогрессии", Израильский математический журнал, 184: 93–128, arXiv:0801.4310, Дои:10.1007 / s11856-011-0061-1, МИСТЕР  2823971
18. Грин, Бен; Волк, Юля (2010), «Заметка об усовершенствовании Элькиным конструкции Беренда», в Чудновский, Давид; Чудновский Григорий (ред.), Аддитивная теория чисел: Festschrift в честь шестидесятилетия Мелвина Б. Натансона, Нью-Йорк: Springer, стр. 141–144, arXiv:0810.0732, Дои:10.1007/978-0-387-68361-4_9, МИСТЕР  2744752
19. Ружа, И.З.; Семереди, Э. (1978), «Тройные системы без шести точек, несущие три треугольника», Комбинаторика (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II, Коллок. Математика. Soc. Янош Бойяи, 18, Амстердам и Нью-Йорк: Северная Голландия, стр. 939–945, МИСТЕР  0519318
20. Медник, Дон; Виноград, Шмуэль (1990), "Умножение матриц через арифметические прогрессии", Журнал символических вычислений, 9 (3): 251–280, Дои:10.1016 / S0747-7171 (08) 80013-2, МИСТЕР  1056627
21. Липмаа, Хельгер (2012), «Наборы без прогрессии и неинтерактивные аргументы с нулевым разглашением на основе сублинейных пар», в Крамер, Рональд (ред.), Теория криптографии: 9-я конференция по теории криптографии, TCC 2012, Таормина, Сицилия, Италия, 19–21 марта 2012 г., Труды, Конспект лекций по информатике, 7194, Springer, стр. 169–189, Дои:10.1007/978-3-642-28914-9_10
22. Cockayne, E.J .; Хедетниеми, С. Т. (1986), "О проблеме доминирования диагональных ферзей", Журнал комбинаторной теории, Серия А, 42 (1): 137–139, Дои:10.1016/0097-3165(86)90012-9, МИСТЕР  0843468

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

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