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

В теории чисел последовательностью Сидона (или множеством Сидона) называется любая последовательность ${\displaystyle a_{1},a_{2},\dots }$ такая, что все суммы вида ${\displaystyle a_{i}+a_{j},\ i\leq j}$ различны. Последовательность может быть конечной или бесконечной — от этого существенно зависит подход к изучению свойств таких последовательностей.

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

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

История

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

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

Свойства

Размер

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

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

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

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

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

${\displaystyle {\sqrt {N}}-N^{0.2625}<|A|<{\sqrt {N}}+N^{1/4}+1}$

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

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

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

Предположим, что множество Сидона S не является линейкой Голомба. Так как S не линейка Голомба, существуют ${\displaystyle a_{i}-a_{j}=a_{k}-a_{l}}$ из S, и, следовательно, ${\displaystyle a_{i}+a_{l}=a_{k}+a_{j}}$, что противоречит сидоновости S. Так, множество Сидона есть линейка Голомба. По симметричному доказательству, линейка Голомба есть множество Сидона.

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

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

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

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

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

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

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

Описание

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

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

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

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

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

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

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

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

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

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

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

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

Distinct distance constant

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

${\displaystyle {\rm {DDC}}=\max \limits _{A\subset {\mathbb {N} }}{\sum \limits _{a\in A}{\frac {1}{a}}},}$

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

${\displaystyle 2.1600383<{\rm {DDC}}<2.2473}$^[10]

Обобщения

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

${\displaystyle \#\{(a_{1},\dots ,a_{h})\in A^{h}:a_{1}+\dots +a_{h}=x\}\leq g}$

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

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

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

Литература

• 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. ${\displaystyle B_{2}}$-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.

Примечания

1. Sidon, 1932.
2. Erdos, Turan, 1941.
3. Babai, Sos, 1985.
4. O’Bryant, 2004, раздел 4.1
5. Ajtai, Komlós, Szemerédi, 1981.
6. последовательность A005282 в OEIS
7. Ruzsa, 1998.
8. Kohayakawa, Lee, Rödl, Samotij, 2015, теорема 1.1
9. Erdős, Sárközy, Sós, 1995, см. также раздел 6 в O’Bryant, 2004
10. Yovanof, Taylor, 2000.
11. Erdös, Rényi, 1960 (теорема 8), описание конструкции приведено по обзору O’Bryant, 2004 ([13] в списке литературы)
12. O’Bryant, 2004.