Сидоновская последовательность

В теории чисел , в последовательности Сидона (или Сидонской набор ), названный в честь венгерский математик Саймон Сидоне , представляет собой последовательность  = { ₀ ,  ₁ ,  ₂ , ...} натуральных чисел , в которых все попарные суммы с _I  +  a _j ( i  ≤  j ) разные. Сидон ввел эту концепцию в свои исследования рядов Фурье .

Основная проблема при изучении последовательностей Сидона, поставленная Сидоном ^[1], состоит в том, чтобы найти наибольшее число элементов, которое может иметь последовательность Сидона A меньше некоторого заданного числа x . Несмотря на большой объем исследований ^[2], вопрос остался нерешенным.

Первые результаты [ править ]

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

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

Эрдеш также показал, что если мы рассматриваем любую конкретную бесконечную последовательность Сидона A и пусть A ( x ) обозначает количество ее элементов до x , то

${\ displaystyle \ liminf _ {x \ to \ infty} {\ frac {A (x) {\ sqrt {\ log x}}} {\ sqrt {x}}} \ leq 1.}$

То есть бесконечные последовательности Сидона тоньше плотнейших конечных последовательностей Сидона.

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

${\ displaystyle A (x)> {\ sqrt [{3}] {x \ log x}}.}$

Наилучшую нижнюю оценку на сегодняшний день дал Имре З. Ружа , который доказал ^[5], что последовательность Сидона с

${\ Displaystyle А (х)> х ^ {{\ sqrt {2}} - 1-о (1)}}$

существуют. Эрдеш предположил, что существует бесконечное множество Сидона A, для которого верно. Он и Реньи показали ^[6] существование последовательности { a ₀ , a ₁ , ...} с предполагаемой плотностью, но удовлетворяющей только более слабому свойству: существует постоянная k такая, что для каждого натурального числа n существует не более k решений уравнения a _i + a _j = n . (Чтобы быть последовательностью Сидона, необходимо, чтобы k = 1.)${\ Displaystyle А (х)> х ^ {1/2-о (1)}}$

Erdős далее высказано предположение , что существует непостоянное целое число - коэффициент многочлен , значение которого в натуральных числах образует последовательность Сидона. В частности, он спросил, является ли набор пятых степеней набором Сидона. Ружа приблизился к этому, показав, что существует действительное число c с 0 < c <1 такое, что диапазон функции f ( x ) = x ⁵ + [ cx ⁴ ] является последовательностью Сидона, где [.] Обозначает целое число часть . Поскольку c иррационально, эта функция f ( x) не является многочленом. Утверждение, что множество пятых степеней является множеством Сидона, является частным случаем более поздней гипотезы Лендера, Паркина и Селфриджа .

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

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

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

См. Также [ править ]

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

Ссылки [ править ]

• Гай, Ричард К. (2004). Нерешенные проблемы теории чисел (3-е изд.). Springer-Verlag . C9. ISBN 0-387-20860-7. Zbl  1058.11001 .