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

Класс последовательностей натуральных чисел

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

Основная проблема в изучении последовательностей Сидона, поставленная Сидоном, ^[1] заключается в нахождении максимального числа элементов, которые может содержать последовательность Сидона, вплоть до некоторой границы . Несмотря на большой объем исследований, ^[2] вопрос остался нерешенным. ^[3] ${\displaystyle x}$

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

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

В 1994 году Эрдёш предложил 500 долларов за доказательство или опровержение привязки . ^[6] ${\displaystyle {\sqrt {x}}+o(x^{\varepsilon })}$

Плотные наборы Сидона

Подмножество Сидона называется плотным, если где максимум берется по всем подмножествам Сидона . Структура плотных множеств Сидона имеет богатую литературу ^{[7] [8]} и классические конструкции Эрдёша–Турана, ^[9] Зингера, ^[10] Бозе , ^[11] Спенса, ^{[12] [13]} Хьюза ^[14] и Чиллеруэло ^[15] установили, что плотное множество Сидона удовлетворяет . Как заметил Ружа , «каким-то образом все известные конструкции плотных множеств Сидона включают простые числа». ^[16] ${\displaystyle A\subset [n]:=\{1,2,\dots ,n\}}$ ${\displaystyle \left|A\right|=\max \left|S\right|}$ ${\displaystyle [n]}$ ${\displaystyle A}$ ${\displaystyle \left|A\right|\geq \left(1-o(1)\right){\sqrt {n}}}$

Недавний результат Баласубраманьяна и Дутты ^[17] показывает, что если плотное множество Сидона имеет мощность , то ${\displaystyle A=\{a_{1},\dots ,a_{\left|A\right|}\}\subset [n]}$ ${\displaystyle |A|=n^{1/2}-L^{\prime }}$

${\displaystyle a_{m}=m\cdot n^{1/2}+{\mathcal {O}}\left(n^{7/8}\right)+{\mathcal {O}}\left(L^{1/2}\cdot n^{3/4}\right)}$

где . Это напрямую дает некоторые полезные асимптотические результаты, включая ${\displaystyle L=\max\{0,L^{\prime }\}}$

${\displaystyle \sum _{a\in A}a^{\ell }={\frac {1}{\ell +1}}\cdot n^{\frac {2\ell +1}{2}}+{\mathcal {O}}\left(n^{\frac {8\ell +3}{8}}\right)+{\mathcal {O}}\left(L^{1/2}\cdot n^{\frac {4\ell +1}{4}}\right)}$

для любого положительного целого числа . ${\displaystyle \ell }$

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

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

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

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

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

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

Существование последовательностей Сидона, которые образуют асимптотический базис порядка (что означает, что каждое достаточно большое натуральное число может быть записано как сумма чисел из последовательности), было доказано в 2010 году ^[22] , в 2014 году ^[23] (сумма четырех членов с одним меньшим, чем , для произвольно малого положительного ) в 2015 году ^[24] и в 2023 году в качестве препринта ^{[25] [26],} этот последний был поставлен как проблема в статье Эрдёша, Шаркёзи и Шоша в 1994 году. ^[27] ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle m=5}$ ${\displaystyle m=4}$ ${\displaystyle m=3+\varepsilon }$ ${\displaystyle n^{\varepsilon }}$ ${\displaystyle \varepsilon }$ ${\displaystyle m=3}$

Связь с правителями Голомба

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

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

Смотрите также

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

Ссылки

1. Эрдёш, П.; Туран , П. (1941). «О проблеме Сидона в аддитивной теории чисел и о некоторых связанных с ней проблемах» (PDF) . J. London Math. Soc . 16 (4): 212–215. doi :10.1112/jlms/s1-16.4.212.. Приложение, 19 (1944), 208.
2. О'Брайант, К. (2004). «Полная аннотированная библиография работ, связанных с последовательностями Сидона». Электронный журнал комбинаторики . 11 : 39. doi : 10.37236/32 ..
3. Гай, Ричард К. (2004). "C9: Упаковка сумм в пары". Нерешенные проблемы теории чисел (3-е изд.). Springer-Verlag . С. 175–180. ISBN 0-387-20860-7. Збл  1058.11001.
4. Линстрём, Берн (1969). «Неравенство для B2-последовательностей». Журнал комбинаторной теории . 6 (2): 211–212. doi :10.1016/S0021-9800(69)80124-9.
5. Балог, Йожеф; Фюреди, Золтан; Рой, Суктик (28 мая 2023 г.). «Верхняя граница размера сидонских множеств». Американский математический ежемесячник . 130 (5): 437–445. arXiv : 2103.15850 . дои : 10.1080/00029890.2023.2176667. ISSN  0002-9890. S2CID  232417382.
6. Эрдёш, Пол (1994). «Некоторые проблемы теории чисел, комбинаторики и комбинаторной геометрии» (PDF) . Mathematica Pannonica . 5 (2): 261–269.
7. Prendiville, Sean (июль 2022 г.). «Решение уравнений в плотных множествах Сидона». Математические труды Кембриджского философского общества . 173 (1): 25–34. arXiv : 2005.03484 . Bibcode : 2022MPCPS.173...25P. doi : 10.1017/S0305004121000402. ISSN  0305-0041.
8. Эберхард, Шон; Мэннерс, Фредди (2023-02-24). «Кажущаяся структура плотных множеств Сидона». Электронный журнал комбинаторики . 30 : P1.33. arXiv : 2107.05744 . doi : 10.37236/11191. ISSN  1077-8926.
9. Эрдёш, П.; Туран, П. (октябрь 1941 г.). «О проблеме Сидона в аддитивной теории чисел и о некоторых связанных с ней проблемах». Журнал Лондонского математического общества . s1-16 (4): 212–215. doi :10.1112/jlms/s1-16.4.212.
10. Сингер, Джеймс (1938). «Теорема в конечной проективной геометрии и некоторые приложения к теории чисел». Труды Американского математического общества . 43 (3): 377–385. doi :10.1090/S0002-9947-1938-1501951-4. ISSN  0002-9947. S2CID  121112335.
11. Бозе, Р. К. (1942-06-01). «Аффинный аналог теоремы Зингера». Журнал Индийского математического общества . 6 : 1–15.
12. Ganley, Michael J (11.1977). «Наборы прямых разностей произведений». Журнал комбинаторной теории, Серия A. 23 ( 3): 321–332. doi :10.1016/0097-3165(77)90023-1. ISSN  0097-3165.
13. Ruzsa, Imre (1993). «Решение линейного уравнения в наборе целых чисел I». Acta Arithmetica . 65 (3): 259–282. doi :10.4064/aa-65-3-259-282. ISSN  0065-1036.
14. Хьюз, DR (ноябрь 1955 г.). «Планарное деление нео-колец». Труды Американского математического общества . 80 (2): 502–527. doi :10.2307/1993000. ISSN  0002-9947. JSTOR  1993000.
15. Cilleruelo, Javier (2012-05-01). «Комбинаторные проблемы в конечных полях и множествах Сидона». Combinatorica . 32 (5): 497–511. doi :10.1007/s00493-012-2819-4. ISSN  1439-6912.
16. Ружа, Имре З. (1 ноября 1999 г.). «Эрдёш и целые числа». Журнал теории чисел . 79 (1): 115–163. дои : 10.1006/jnth.1999.2395. ISSN  0022-314X.
17. Баласубраманян, Р.; Дутта, Саян (2024-09-08). «$m$-й элемент множества Сидона». arXiv : 2409.01986 [math.NT].
18. Миан, Абдул Маджид; Чоула, С. (1944). «О _{последовательностях} B2 Сидона». Proc. Natl. Acad. Sci. India A. 14 : 3–4. MR  0014114..
19. Аджтай, М .; Комлос, Дж . ; Семереди, Э. (1981). «Плотная бесконечная последовательность Сидона». Европейский журнал комбинаторики . 2 (1): 1–11. дои : 10.1016/s0195-6698(81)80014-5. МР  0611925..
20. Ruzsa, IZ (1998). «Бесконечная последовательность Сидона». Журнал теории чисел . 68 : 63–71. doi : 10.1006/jnth.1997.2192 . MR  1492889..
21. Эрдеш, П .; Реньи, А. (1960). «Аддитивные свойства случайных последовательностей натуральных чисел» (PDF) . Акта Арифметика . 6 : 83–110. дои : 10.4064/aa-6-1-83-110 . МР  0120213..
22. Кисс, СЗ (2010-07-01). «О множествах Сидона, которые являются асимптотическими базисами». Acta Mathematica Hungarica . 128 (1): 46–58. doi :10.1007/s10474-010-9155-1. ISSN  1588-2632. S2CID  96474687.
23. Поцелуй, Шандор З.; Розгоньи, Эстер; Шандор, Чаба (01 декабря 2014 г.). «О множествах Сидона, являющихся асимптотическим базисом порядка $4$». Functiones et Approximatio Commentarii Mathematici . 51 (2). arXiv : 1304.5749 . дои : 10.7169/facm/2014.51.2.10. ISSN  0208-6573. S2CID  119121815.
24. Cilleruelo, Javier (ноябрь 2015 г.). «О множествах Сидона и асимптотических базисах». Труды Лондонского математического общества . 111 (5): 1206–1230. doi :10.1112/plms/pdv050. S2CID  34849568.
25. Пилат, Седрик (2024-05-10). «Решение проблемы Эрдёша–Саркези–Шоша на асимптотических базисах Сидона порядка 3». Compositio Mathematica . 160 (6): 1418–1432. arXiv : 2303.09659 . doi : 10.1112/s0010437x24007140. ISSN  0010-437X.
26. "Выпускник первого года обучения находит парадоксальный набор чисел". Журнал Quanta . 2023-06-05 . Получено 2023-06-13 .
27. Эрдеш, П.; Саркози, А.; Сос, ВТ (31 декабря 1994 г.). «Об аддитивных свойствах общих последовательностей». Дискретная математика . 136 (1): 75–99. дои : 10.1016/0012-365X(94)00108-U. ISSN  0012-365X. S2CID  38168554.