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

В теории чисел последовательностью Сидона (или множеством Сидона) называется любая последовательность такая, что все суммы вида различны. Последовательность может быть конечной или бесконечной — от этого существенно зависит подход к изучению свойств таких последовательностей.

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

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

История Впервые условие, налагаемое на множества Сидона, появилось в примечании к статье 1932 года. Основная тема этой статьи (оценки некоторых рядов Фурье) не касалась свойств множеств Сидона, но полученная там теорема параметризовалась последовательностью, растущей с экспоненциальной скоростью, и могла быть обобщена до аналогичного утверждения о последовательностях Сидона. В связи с этим Сидон отметил (не приводя примеров и доказательств) наличие в натуральном ряду таких последовательностей со свойством .

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

Свойства

Размер

Конечные множества Очевидно, что размер множества Сидона конечной группы не может превышать . Эрдёш и Туран в 1946 году показали, что для кольца вычетов эта оценка достижима с точностью до константы. Их конструкцию легко обобщить на любую группу размера , где  — простое число.

Известно, что если  — наибольшее множество Сидона целых чисел из интервала , то

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

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

Предположим, что множество Сидона S не является линейкой Голомба. Так как S не линейка Голомба, существуют из S, и, следовательно, , что противоречит сидоновости S. Так, множество Сидона есть линейка Голомба. По симметричному доказательству, линейка Голомба есть множество Сидона.

Бесконечные множества Хуже изучен вопрос о размере бесконечных множеств Сидона. Множества Сидона из можно интерпретировать как сидоновское подмножество интервала в рамках группы целых чисел, но такие множества при разных не будут разными частями единой бесконечной структуры, а каждое будет устроено по-своему. Поэтому актуален следующий вопрос:

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

Бесконечные множества можно формировать жадно: перебираются все числа по порядку и если от добавления очередного числа множество не перестаёт быть сидоновским, число добавляется во множество. Такая конструкция даёт результат , поскольку для любого конечного есть лишь не подходящих для добавления чисел (тройка однозначно определяет число , для которого ). В 1981 году , и Семереди, используя леммы из теории графов, показали, что, более того, .

В 1998 году доказал существование множеств Сидона, для которых . Его доказательство было вероятностным, то есть не позволяло предъявить конкретное множество, и даже предпосчитать какое-то конечное число его элементов.

Арифметические и комбинаторные свойства Количество множеств Сидона в интервале не превышает , где  — константа,  — размер наибольшего такого множества. По сравнению с тривиальной оценкой это число очень близко к количеству подмножества одного наибольшего множества Сидона , теорема 1.1.

Изучались вопросы о длине и количестве арифметических прогрессий во множествах Сидона целых чисел из интервала и их множествах сумм. В частности, известно, что, см. также раздел 6 в :

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

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

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

Обобщения

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

Таким образом, -последовательности — это обычные множества Сидона.

Эрдёш и Реньи показали, что существуют бесконечные -последовательности такие, что , где при . Чтобы его построить, достаточно взять случайное множество, в котором число присутствует с вероятностью и события присутствия разных чисел независимы. Почти наверное из такого множества достаточно будет удалить конечное число элементов чтобы оно стало (теорема 8), описание конструкции приведено по обзору ( в списке литературы).

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

Литература

Примечания

Категория:Аддитивная теория чисел Категория:Комбинаторика