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

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

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

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

История

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

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

Свойства

Размер

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

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

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

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

Существует гипотеза о том, что для таких множеств при $N\to \mathrm{\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 году Шаблон:Iw, Шаблон:Iw и Семереди, используя леммы из теории графов, показали, что, более того, $A(n)\gg n^{1/3}(\log n{)}^{1/3}$Шаблон:Sfn.

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

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

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

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

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

Distinct distance constant

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

$\mathrm{D}\mathrm{D}\mathrm{C}=\max {\mathrm{\backslash limits}}_{A\subset \mathbb{N}}\sum _{a\in A}\frac{1}{a},$

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

$2.1600383<\mathrm{D}\mathrm{D}\mathrm{C}<2.2473$Шаблон:Sfn

Шаблон:Якорь Обобщения

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

$\mathrm{\#}\{(a_1,\dots ,a_h)\in A^h:a_1+\dots +a_h=x\}\le g$

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

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

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

Литература

• Шаблон:Статья

• Шаблон:Статья

• Шаблон:Статья

• Шаблон:Статья

• Шаблон:Статья

• Шаблон:Статья

• Шаблон:Статья

• Шаблон:Статья

• Шаблон:Статья

• Шаблон:Статья