Последовательность Сидона

В теории чисел последовательностью Сидона (или множеством Сидона) называется любая последовательность [math]\displaystyle{ a_1, a_2, \dots }[/math] такая, что все суммы вида [math]\displaystyle{ a_i + a_j,\ i \le j }[/math] различны. Последовательность может быть конечной или бесконечной — от этого существенно зависит подход к изучению свойств таких последовательностей.

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

В данной статье запись [math]\displaystyle{ A(n) }[/math] означает число элементов множества [math]\displaystyle{ A }[/math], не превышающих [math]\displaystyle{ n }[/math].

История

Впервые условие, налагаемое на множества Сидона, появилось в примечании к статье Симона Сидона 1932 года. Основная тема этой статьи (оценки некоторых рядов Фурье) не касалась свойств множеств Сидона, но полученная там теорема параметризовалась последовательностью, растущей с экспоненциальной скоростью, и могла быть обобщена до аналогичного утверждения о последовательностях Сидона. В связи с этим Сидон отметил (не приводя примеров и доказательств) наличие в натуральном ряду таких последовательностей со свойством [math]\displaystyle{ a_n = O(n^4) }[/math].

Впоследствии изучение таких множеств как отдельную тему подняли в своей статье Эрдёш и Туран.

Свойства

Размер

Конечные множества

Очевидно, что размер множества Сидона конечной группы [math]\displaystyle{ G }[/math] не может превышать [math]\displaystyle{ \sqrt{|G|} }[/math]. Эрдёш и Туран в 1946 году показали, что для кольца вычетов [math]\displaystyle{ G={\mathbb Z}_N }[/math] эта оценка достижима с точностью до константы. Их конструкцию легко обобщить на любую группу размера [math]\displaystyle{ p^{2k} }[/math], где [math]\displaystyle{ k }[/math] — простое число.

Конструкция Эрдёша-Турана

Пусть [math]\displaystyle{ p \lt \sqrt{G} }[/math] и [math]\displaystyle{ s_k }[/math] - число от [math]\displaystyle{ 0 }[/math] до [math]\displaystyle{ N-1 }[/math], соответствующее квадратичному вычету [math]\displaystyle{ s_k \equiv k^2 \pmod p }[/math]. Тогда множество [math]\displaystyle{ \{ k p + s_k : k=1,\dots,N \} }[/math] является множеством Сидона.

Известно, что если [math]\displaystyle{ A }[/math] — наибольшее множество Сидона целых чисел из интервала [math]\displaystyle{ [1;N] }[/math], то

[math]\displaystyle{ \sqrt{N} - N^{0.2625} \lt |A| \lt \sqrt{N} + N^{1/4} + 1 }[/math]

Существует гипотеза о том, что для таких множеств при [math]\displaystyle{ N \to \infty }[/math] разность [math]\displaystyle{ |A| - \sqrt{N} }[/math] должна быть положительна и неограничена.

Отношение к линейкам Голомба

Любое конечное множество Сидона является линейкой Голомба, и наоборот.

Предположим, что множество Сидона S не является линейкой Голомба. Так как S не линейка Голомба, существуют [math]\displaystyle{ a_i-a_j=a_k-a_l }[/math] из S, и, следовательно, [math]\displaystyle{ a_i+a_l=a_k+a_j }[/math], что противоречит сидоновости S. Так, множество Сидона есть линейка Голомба. По симметричному доказательству, линейка Голомба есть множество Сидона.

Бесконечные множества

Хуже изучен вопрос о размере бесконечных множеств Сидона. Множества Сидона из [math]\displaystyle{ {\mathbb Z}_N }[/math] можно интерпретировать как сидоновское подмножество интервала [math]\displaystyle{ \{ 1, \dots, N \} }[/math] в рамках группы целых чисел, но такие множества при разных [math]\displaystyle{ N }[/math] не будут разными частями единой бесконечной структуры, а каждое будет устроено по-своему. Поэтому актуален следующий вопрос:

Какую максимальную асимптотику может иметь [math]\displaystyle{ A(x) }[/math] если [math]\displaystyle{ A }[/math] — бесконечное множество Сидона?

Бесконечные множества можно формировать жадно: перебираются все числа по порядку и если от добавления очередного числа множество не перестаёт быть сидоновским, число добавляется во множество. Такая конструкция даёт результат [math]\displaystyle{ A(n) \gg n^{1/3} }[/math], поскольку для любого конечного [math]\displaystyle{ A }[/math] есть лишь [math]\displaystyle{ |A|^3 }[/math] не подходящих для добавления чисел (тройка [math]\displaystyle{ a,b,c }[/math] однозначно определяет число [math]\displaystyle{ d }[/math], для которого [math]\displaystyle{ a+b=c+d }[/math]). В 1981 году Ajtai, Янош Комлош и Семереди, используя леммы из теории графов, показали, что, более того, [math]\displaystyle{ A(n) \gg n^{1/3} (\log n)^{1/3} }[/math].

В 1998 году Ружа доказал существование множеств Сидона, для которых [math]\displaystyle{ A(n) \gt n^{\sqrt{2} - 1 + o(1)} }[/math]. Его доказательство было вероятностным, то есть не позволяло предъявить конкретное множество, и даже предпосчитать какое-то конечное число его элементов.

Описание конструкции Ружа

Схема построения элемента множества.

Описание

Конструкция зависит от параметра [math]\displaystyle{ \alpha \in [1;2] }[/math]. Точное значение [math]\displaystyle{ \alpha }[/math], при котором конструкция будет корректной, неизвестно, но можно доказать его существование.

Для фиксированного [math]\displaystyle{ \alpha }[/math] рассматриваются двоичные представления числа [math]\displaystyle{ \alpha \log p }[/math], где [math]\displaystyle{ p }[/math] — простое число, округлённые с достаточно большой точностью (зависящей от величины этого числа). После этого знаки из дробной части разбиваются на неравные блоки и переставляются в обратном порядке. Чтобы получить число [math]\displaystyle{ b_p }[/math] (кандидата во множество Сидона) между ними и после последней из них (в порядке возрастания разрядов, то есть слева направо) вставляются области из пяти цифр, среди которых:

• первая, третья и пятая — нули;
• вторая соответствует очередной цифре из части логарифма до запятой (цифры заполняются справа налево, в том же порядке, что и в числе)
• четвёртая равна единице только для самого старшего такого блока

Ружа показал существование [math]\displaystyle{ \alpha \in [1;2] }[/math], при котором количество решений уравнения [math]\displaystyle{ a+b=c+d }[/math] (противоречащего определению сидоновости) в таком множестве пренебрежимо мало по сравнению с общим количеством элементов, так что для получения множества Сидона можно просто удалить элементы, участвующие в этих решениях, и размер множества не изменится. Показатель степени размера множества [math]\displaystyle{ \sqrt{2} - 1 }[/math] соответствует решению (в терминах [math]\displaystyle{ \frac{1}{\beta} }[/math]) уравнения [math]\displaystyle{ \frac{2}{\beta - 1} - 1 = \frac{1}{\beta} }[/math], где левая часть как раз соответствует показателю степени количества решений уравнений [math]\displaystyle{ a+b=c+d }[/math].

Мотивация к выбору конструкции

Изменение порядка блоков, на которые разбита дробная часть, позволяет сравнивать числа [math]\displaystyle{ b_p }[/math] по некоторому модулю несмотря на разницу в округлении больших и малых значений [math]\displaystyle{ \alpha \log p }[/math]. Нули в промежуточных областях нужны чтобы разделить влияние сложения на разные основные блоки (чтобы из равенства суммы [math]\displaystyle{ b_p }[/math] можно было заключить равенство сумм блоков из каждой отдельной позиции). Единица в последней промежуточной области фиксирует порядок роста чисел [math]\displaystyle{ b_p }[/math], это важно для оценки их количества в отрезке.

Ружа замечает, что отправной точкой для создания конструкции стало то, что множество вещественных чисел [math]\displaystyle{ \log p }[/math] (без округления) явлояется сидоновским. Это напрямую вытекает из основной теоремы арифметики, потому что решение [math]\displaystyle{ \log p + \log r = \log q + \log s }[/math], где все числа — простые, означало бы, что [math]\displaystyle{ pr=qs }[/math]. Неравенство [math]\displaystyle{ |pr-qs| \ge 2 }[/math] действительно существенно используется в ходе доказательства чтобы показать, что при равенстве [math]\displaystyle{ b_p+b_r=b_q+b_s }[/math] порядок роста [math]\displaystyle{ b_p }[/math] и [math]\displaystyle{ b_r }[/math] будет сильно отличаться.

В статье Ружи дробная часть [math]\displaystyle{ \alpha \log p }[/math] разбивается на блоки в позициях, соответствующих квадратам. Фактически это используется только для того, чтобы общий размер промежуточных областей (по пять цифр), вставляемых между блоками, при растущем [math]\displaystyle{ p }[/math] становился сколь угодно мал по сравнению с общим количеством цифр в [math]\displaystyle{ b_p }[/math]. Поэтому вместо возведения номера блока в квадрат можно использовать любую функцию, возрастающую быстрее, чем линейная.

Арифметические и комбинаторные свойства

Количество множеств Сидона в интервале [math]\displaystyle{ [1;N] }[/math] не превышает [math]\displaystyle{ 2^{cM} }[/math], где [math]\displaystyle{ c }[/math] — константа, [math]\displaystyle{ M }[/math] — размер наибольшего такого множества. По сравнению с тривиальной оценкой [math]\displaystyle{ M n^{M} = 2^{M \log n (1 + o(1))} }[/math] это число очень близко к количеству подмножества одного наибольшего множества Сидона [math]\displaystyle{ 2^M }[/math].

Изучались вопросы о длине и количестве арифметических прогрессий во множествах Сидона [math]\displaystyle{ A }[/math] целых чисел из интервала [math]\displaystyle{ [1;N] }[/math] и их множествах сумм. В частности, известно, что:

• [math]\displaystyle{ A+A }[/math] может содержать интервалы последовательных целых чисел, длины [math]\displaystyle{ \Omega(N^{1/3}) }[/math];
• если [math]\displaystyle{ P_1, \dots, P_k }[/math] — обобщённые арифметические прогрессии ограниченной размерности, покрывающие [math]\displaystyle{ A }[/math], то [math]\displaystyle{ k \sum \limits_{i=1}^{k} |P_i| \gg |A|^2 }[/math]. Этот результат верен также для [math]\displaystyle{ B_2^*[g] }[/math]-последовательностей (см. раздел об обобщениях).

Distinct distance constant

Distinct distance constant — количественный показатель распределения бесконечных множеств Сидона из [math]\displaystyle{ {\mathbb N} }[/math], равный максимальной сумме ряда, состоящего из чисел, обратных к числам из некоторого множества Сидона:

[math]\displaystyle{ {\rm DDC} = \max \limits_{A \subset {\mathbb N}} {\sum \limits_{a \in A} {\frac{1}{a}}}, }[/math]

где максимум берётся по множествам Сидона. Известно, что

[math]\displaystyle{ 2.1600383 \lt {\rm DDC} \lt 2.2473 }[/math]

Обобщения

Два основных обобщения определения множеств Сидона — по количеству слагаемых и по количеству представлений сумм. Множество [math]\displaystyle{ A \subset {\mathbb N} }[/math] называется [math]\displaystyle{ B_h^*[g] }[/math]-последовательностью если для всякого [math]\displaystyle{ x \in {\mathbb N} }[/math] верно, что

[math]\displaystyle{ \# \{ (a_1, \dots, a_h) \in A^h : a_1 + \dots + a_h = x \} \le g }[/math]

Таким образом, [math]\displaystyle{ B_2^*[2] }[/math]-последовательности — это обычные множества Сидона.

Эрдёш и Реньи показали, что существуют бесконечные [math]\displaystyle{ B_2^*[g] }[/math]-последовательности такие, что [math]\displaystyle{ A(n) \gg n^{\frac{1}{2} - \varepsilon(g)} }[/math], где [math]\displaystyle{ \varepsilon(g) \to 0 }[/math] при [math]\displaystyle{ g \to 0 }[/math]. Чтобы его построить, достаточно взять случайное множество, в котором число [math]\displaystyle{ n }[/math] присутствует с вероятностью [math]\displaystyle{ n^{-\frac{1}{2}-\frac{1}{g+1}} }[/math] и события присутствия разных чисел независимы. Почти наверное из такого множества достаточно будет удалить конечное число элементов чтобы оно стало [math]\displaystyle{ B_2^*[g] }[/math].

Множество результатов об обобщениях систематизировано в обзоре О’Бранта.

Литература

• S. Sidon. Ein Satz über trigonometrische Polynome und seine Anwendung in der Theorie der Fourier-Reihen (нем.) // Ein Satz über trigonometrische Polynome und seine Anwendung in der Theorie der Fourier-Reihen. — 1932. — Bd. 106. — S. 536--539.

• P. Erdos, P. Turán. On a problem of Sidon in additive number theory, and on some related problems (англ.) // Journal of the London Mathematical Society. — 1941. — Vol. 16. — P. 212--215.

• László Babai, Vera T.Sós. Sidon Sets in Groups and Induced Subgraphs of Cayley Graphs (англ.) // European Journal of Combinatorics. — 1985. — Vol. 6, iss. 2. — P. 101--114.

• Miklós Ajtai, János Komlós, Endre Szemerédi. A Dense Infinite Sidon Sequence (англ.) // European Journal of Combinatorics. — 1981. — Vol. 2, iss. 1. — P. 1--11.

• Imre Z. Ruzsa. An Infinite Sidon Sequence (англ.) // Journal of Number Theory. — 1998. — Vol. 68, iss. 1. — P. 63--71.

• G. S. Yovanof, H. Taylor. [math]\displaystyle{ B_2 }[/math]-sequences and the distinct distance constant (англ.) // Computers & Mathematics with Applications. — 2000. — Vol. 39, iss. 11. — P. 37--42.

• Kevin O’Bryant. A Complete Annotated Bibliography of Work Related to Sidon Sequences (англ.). — 2004. — arXiv:math/0407117v1.

• P. Erdös, A Rényi. Additive properties of random sequences of positive integers (англ.) // Acta Arithmetica. — 1960. — Vol. 6, iss. 1. — P. 83--110.

• P. Erdős, A. Sárközy, V. T. Sós. On sum sets of sidon sets, II (англ.) // Israel Journal of Mathematics. — 1995. — Vol. 90. — P. 221--233.

• Yoshiharu Kohayakawa, Sang June Lee, Vojtěch Rödl, Wojciech Samotij. The Number of Sidon Sets and the Maximum Size of Sidon Sets Contained in a Sparse Random Set of Integers (англ.) // Random Structures and Algorithms. — 2015. — Vol. 46.