On the size of finite Sidon sets

Kevin O'Bryant

doi:10.3842/umzh.v76i8.7858

Kevin O'Bryant City University of New York, The Graduate Center and the College of Staten Island

DOI: https://doi.org/10.3842/umzh.v76i8.7858

Анотація

УДК 519.1

Про розмір скінченних множин Сідона

Множина Сідона (що також називається лінійкою Голомба) – це послідовність $B_2$, а $1$-тонка множина – це множина цілих чисел, що не містить нетривіальних розв'язків рівняння $a+b=c+d.$ Ми покращуємо нижню межу для діаметра множини Сідона з $k$ елементів, тобто якщо $k$ є достатньо великим, а $\cal A$ є множиною Сідона з $k$ елементами, то ${\rm diam}({\cal A}) \ge k^2-1,99405 k^{3/2}.$ Навпаки, якщо $n$ достатньо велике, то потужність найбільшої підмножини $\{1,2,\dots,n\}$, що є множиною Сідона, не перевищує $n^{1/2}+0.99703 n^ {1/4}.$

Посилання

J. Balogh, Z. Füredi, S. Roy, An upper bound on the size of Sidon sets (2021); available at https://arxiv.org/ abs/2103.15850.

Y. Caicedo, C. A. Martos, A. Trujillo, $g$-Golomb rulers, Rev. Integr. Temas Mat., 33, № 2, 161–172 (2015). DOI: https://doi.org/10.18273/revint.v33n2-2015006

J. Cilleruelo, Sidon sets in $N^d$, J. Combin. Theory Ser. A, 117, № 7, 857–871 (2010); DOI 10.1016/j.jcta.2009.12.003. DOI: https://doi.org/10.1016/j.jcta.2009.12.003

Distributed.net: Completion of OGR-28 project (2022); https://blogs.distributed.net/2022/11/23/03/28/bovine/.

G. Dogon, T. Rokicki, Larger Golomb rulers, gathering 4 gardner 12 (Atlanta, Georgia, April 1) (2016), Exchange Book: Art, Games, Magic, and Math., vol. 1 (2017), p. 155–166; http://cube20.org/golomb/. DOI: https://doi.org/10.14195/2182-8830_4-1_9

P. Erdös, P. Turán, On a problem of Sidon in additive number theory, and on some related problems, J. London Math. Soc., 16, 212–215 (1941); DOI 10.1112/jlms/s1-16.4.212. DOI: https://doi.org/10.1112/jlms/s1-16.4.212

B. Lindström, An inequality for $B_2$-sequences, J. Combin. Theory, 6, 211–212 (1969). DOI: https://doi.org/10.1016/S0021-9800(69)80124-9

K. O'Bryant, A complete annotated bibliography of work related to Sidon sequences, Electron. J. Combin., DS11, 39 (2004). DOI: https://doi.org/10.37236/32

J. Shearer, This webpage is devoted to Golomb rulers (1999); https://web.archive. org/web/20171225101048/http:// www.research.ibm.com/people/s/shearer/grule.html.

S. Sidon, Ein Satz über trigonometrische Polynome und seine Anwendungen in der Theorie der Fourier–Reihen, Math. Ann., 106, 536–539 (1932). DOI: https://doi.org/10.1007/BF01455900

J. Singer, A theorem in finite projective geometry and some applications to number theory, Trans. Amer. Math. Soc., 43, № 3, 377–385 (1938). DOI: https://doi.org/10.1090/S0002-9947-1938-1501951-4