Русская Википедия:Последовательность Сидона
В теории чисел последовательностью Сидона (или множеством Сидона) называется любая последовательность <math>a_1, a_2, \dots</math> такая, что все суммы вида <math>a_i + a_j,\ i \le j</math> различны. Последовательность может быть конечной или бесконечной — от этого существенно зависит подход к изучению свойств таких последовательностей.
Основная проблематика изучения множеств Сидона связана с целыми числами, хотя определение может рассматриваться относительно любой группы.
В данной статье запись <math>A(n)</math> означает число элементов множества <math>A</math>, не превышающих <math>n</math>.
История
Впервые условие, налагаемое на множества Сидона, появилось в примечании к статье Шаблон:Iw 1932 года. Основная тема этой статьи (оценки некоторых рядов Фурье) не касалась свойств множеств Сидона, но полученная там теорема параметризовалась последовательностью, растущей с экспоненциальной скоростью, и могла быть обобщена до аналогичного утверждения о последовательностях Сидона. В связи с этим Сидон отметил (не приводя примеров и доказательств) наличие в натуральном ряду таких последовательностей со свойством <math>a_n = O(n^4)</math>Шаблон:Sfn.
Впоследствии изучение таких множеств как отдельную тему подняли в своей статье Эрдёш и ТуранШаблон:Sfn.
Свойства
Размер
Конечные множества
Очевидно, что размер множества Сидона конечной группы <math>G</math> не может превышать <math>\sqrt{|G|}</math>. Эрдёш и Туран в 1946 году показали, что для кольца вычетов <math>G={\mathbb Z}_N</math> эта оценка достижима с точностью до константыШаблон:Sfn. Их конструкцию легко обобщить на любую группу размера <math>p^{2k}</math>, где <math>k</math> — простое числоШаблон:Sfn.
Известно, что если <math>A</math> — наибольшее множество Сидона целых чисел из интервала <math>[1;N]</math>, то
- <math>\sqrt{N} - N^{0.2625} < |A| < \sqrt{N} + N^{1/4} + 1</math>
Существует гипотеза о том, что для таких множеств при <math>N \to \infty</math> разность <math>|A| - \sqrt{N}</math> должна быть положительна и неограничена[1].
Отношение к линейкам Голомба
Любое конечное множество Сидона является линейкой Голомба, и наоборот.
Предположим, что множество Сидона S не является линейкой Голомба. Так как S не линейка Голомба, существуют <math>a_i-a_j=a_k-a_l</math> из S, и, следовательно, <math>a_i+a_l=a_k+a_j</math>, что противоречит сидоновости S. Так, множество Сидона есть линейка Голомба. По симметричному доказательству, линейка Голомба есть множество Сидона.
Бесконечные множества
Хуже изучен вопрос о размере бесконечных множеств Сидона. Множества Сидона из <math>{\mathbb Z}_N</math> можно интерпретировать как сидоновское подмножество интервала <math>\{ 1, \dots, N \}</math> в рамках группы целых чисел, но такие множества при разных <math>N</math> не будут разными частями единой бесконечной структуры, а каждое будет устроено по-своему. Поэтому актуален следующий вопрос:
Шаблон:Рамка Какую максимальную асимптотику может иметь <math>A(x)</math> если <math>A</math> — бесконечное множество Сидона? Шаблон:Конец рамки
Бесконечные множества можно формировать жадно: перебираются все числа по порядку и если от добавления очередного числа множество не перестаёт быть сидоновским, число добавляется во множество. Такая конструкция даёт результат <math>A(n) \gg n^{1/3}</math>, поскольку для любого конечного <math>A</math> есть лишь <math>|A|^3</math> не подходящих для добавления чисел (тройка <math>a,b,c</math> однозначно определяет число <math>d</math>, для которого <math>a+b=c+d</math>). В 1981 году Шаблон:Iw, Шаблон:Iw и Семереди, используя леммы из теории графов, показали, что, более того, <math>A(n) \gg n^{1/3} (\log n)^{1/3}</math>Шаблон:Sfn[2].
В 1998 году Шаблон:Iw доказал существование множеств Сидона, для которых <math>A(n) > n^{\sqrt{2} - 1 + o(1)}</math>. Его доказательство было вероятностным, то есть не позволяло предъявить конкретное множество, и даже предпосчитать какое-то конечное число его элементовШаблон:Sfn.
Арифметические и комбинаторные свойства
Количество множеств Сидона в интервале <math>[1;N]</math> не превышает <math>2^{cM}</math>, где <math>c</math> — константа, <math>M</math> — размер наибольшего такого множества. По сравнению с тривиальной оценкой <math>M n^{M} = 2^{M \log n (1 + o(1))}</math> это число очень близко к количеству подмножества одного наибольшего множества Сидона <math>2^M</math>[3].
Изучались вопросы о длине и количестве арифметических прогрессий во множествах Сидона <math>A</math> целых чисел из интервала <math>[1;N]</math> и их множествах сумм. В частности, известно, что[4]:
- <math>A+A</math> может содержать интервалы последовательных целых чисел, длины <math>\Omega(N^{1/3})</math>;
- если <math>P_1, \dots, P_k</math> — обобщённые арифметические прогрессии ограниченной размерности, покрывающие <math>A</math>, то <math>k \sum \limits_{i=1}^{k} |P_i| \gg |A|^2</math>. Этот результат верен также для <math>B_2^*[g]</math>-последовательностей (см. раздел об обобщениях).
Distinct distance constant
Distinct distance constant — количественный показатель распределения бесконечных множеств Сидона из <math>{\mathbb N}</math>, равный максимальной сумме ряда, состоящего из чисел, обратных к числам из некоторого множества Сидона:
- <math>{\rm DDC} = \max \limits_{A \subset {\mathbb N}} {\sum \limits_{a \in A} {\frac{1}{a}}},</math>
где максимум берётся по множествам Сидона. Известно, что
- <math>2.1600383 < {\rm DDC} < 2.2473</math>Шаблон:Sfn
Обобщения
Два основных обобщения определения множеств Сидона — по количеству слагаемых и по количеству представлений сумм. Множество <math>A \subset {\mathbb N}</math> называется <math>B_h^*[g]</math>-последовательностью если для всякого <math>x \in {\mathbb N}</math> верно, что
- <math>\# \{ (a_1, \dots, a_h) \in A^h : a_1 + \dots + a_h = x \} \le g</math>
Таким образом, <math>B_2^*[2]</math>-последовательности — это обычные множества Сидона.
Эрдёш и Реньи показали, что существуют бесконечные <math>B_2^*[g]</math>-последовательности такие, что <math>A(n) \gg n^{\frac{1}{2} - \varepsilon(g)}</math>, где <math>\varepsilon(g) \to 0</math> при <math>g \to 0</math>. Чтобы его построить, достаточно взять случайное множество, в котором число <math>n</math> присутствует с вероятностью <math>n^{-\frac{1}{2}-\frac{1}{g+1}}</math> и события присутствия разных чисел независимы. Почти наверное из такого множества достаточно будет удалить конечное число элементов чтобы оно стало <math>B_2^*[g]</math>[5].
Множество результатов об обобщениях систематизировано в обзоре О’БрантаШаблон:Sfn.
Литература
Примечания
- ↑ Шаблон:Sfn0, раздел 4.1
- ↑ Шаблон:OEIS
- ↑ Шаблон:Sfn0, теорема 1.1
- ↑ Шаблон:Sfn0, см. также раздел 6 в Шаблон:Sfn0
- ↑ Шаблон:Sfn0 (теорема 8), описание конструкции приведено по обзору Шаблон:Sfn0 ([13] в списке литературы)
