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

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

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

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

История

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

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

Свойства

Размер

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Описание

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

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

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

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

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

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

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

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

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

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

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

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

Distinct distance constant

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

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

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

$2.1600383<{\rm {DDC}}<2.2473$

Обобщения

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

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

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

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

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

Литература

• 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. $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.