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

Keywords: Sidon Set, Golomb Ruler, Bh set

Abstract

UDC 519.1

A Sidon set (also called a Golomb ruler) is a $B_2$ sequence and a $1$-thin set is a set of integers containing no nontrivial solutions to the equation $a+b=c+d.$ We improve the lower bound for the diameter of a Sidon set with $k$ elements, namely, if $k$ is sufficiently large and $\mathcal A$ is a Sidon set with $k$ elements, then ${\rm diam}({\mathcal A})\ge k^2-1.99405 k^{3/2}.$ Alternatively, if $n$ is sufficiently large, then the cardinality of the largest subset of $\{1,2,\dots,n\},$ which is a Sidon set, does not exceed $n^{1/2}+0.99703 n^{1/4}.$

References

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