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

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

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

Первые результаты

Пол Эрдеш и Пал Туран доказали, что для всех $x>0$, количество элементов меньше $x$ в последовательности Сидона не более ${\sqrt {x}}+O({\sqrt[{4}]{x}})$. Несколькими годами ранее Джеймс Сингер построил последовательности Сидона с помощью ${\sqrt {x}}(1-o(1))$ слагаемые меньше x . Граница была улучшена до ${\sqrt {x}}+{\sqrt[{4}]{x}}+1$ в 1969 году и чтобы ${\sqrt {x}}+0.998{\sqrt[{4}]{x}}$ в 2023 году.

В 1994 году Эрдеш предложил 500 долларов за доказательство или опровержение этой истины. ${\sqrt {x}}+o(x^{\epsilon })$.

Бесконечные последовательности Сидона

Эрдеш также показал, что для любой конкретной бесконечной последовательности Сидона $A$ с $A(x)$ обозначая количество его элементов до $x$, $$\liminf _{x\to \infty }{\frac {A(x){\sqrt {\log x}}}{\sqrt {x}}}\leq 1.$$То есть бесконечные последовательности Сидона тоньше, чем самые плотные конечные последовательности Сидона.

Что касается другого направления, Чоула и Миан заметили, что жадный алгоритм дает бесконечную последовательность Сидона с $A(x)>c{\sqrt[{3}]{x}}$ для каждого $x$. Айтай , Комлос и Семереди улучшили ситуацию, построив последовательности Сидона с $$A(x)>{\sqrt[{3}]{x\log x}}.$$

Наилучшую нижнюю оценку на сегодняшний день дал Имре З. Ружа , доказавший что последовательность Сидона с $$A(x)>x^{{\sqrt {2}}-1-o(1)}$$существует. Эрдеш предположил, что бесконечное множество Сидона $A$ существует, для чего $A(x)>x^{1/2-o(1)}$ держит. Он и Реньи показали существование последовательности $\{a_{0},a_{1},\dots \}$ с предположительной плотностью, но удовлетворяющий только более слабому свойству, заключающемуся в существовании постоянной $k$ такая, что для любого натурального числа $n$ есть максимум $k$ решения уравнения $a_{i}+a_{j}=n$. (Чтобы быть последовательностью Сидона, необходимо, чтобы $k=1$.)

Эрдеш далее предположил, что существует непостоянный целочисленными с коэффициентами полином , значения которого в натуральных числах образуют последовательность Сидона. В частности, он спросил, является ли набор пятых степеней набором Сидона. Ружа приблизился к этому, показав, что существует реальное число. $c$ с $0<c<1$ такая, что область значений функции $f(x)=x^{5}+\lfloor cx^{4}\rfloor$ является последовательностью Сидона, где $\lfloor \ \rfloor$ обозначает целую часть . Как $c$ иррациональна, эта функция $f(x)$ не является полиномом. Утверждение о том, что множество пятых степеней является множеством Сидона, является частным случаем позднейшей гипотезы Ландера, Паркина и Селфриджа .

Последовательности Сидона, являющиеся асимптотическими базисами

Существование последовательностей Сидона, образующих асимптотический базис порядка $m$ (это означает, что каждое достаточно большое натуральное число $n$ можно записать как сумму $m$ чисел из последовательности) доказано для $m=5$ в 2010 году, $m=4$ в 2014 году, $m=3+\epsilon$ (сумма четырех членов, одно из которых меньше $n^{\epsilon }$, для сколь угодно малых положительных $\epsilon$) в 2015 году и $m=3$ в 2023 году в виде препринта, эта более поздняя проблема была представлена ​​​​как проблема в статье Эрдеша, Саркози и Соша в 1994 году.

Отношения с правителями Голомба

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

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

См. также

• Последовательность Мозера – де Брейна
• Шум