On strong infinite Sidon and \(B_h\) sets and random sets of integers (Q2037162): Difference between revisions

Let \(h\ge 2\) be an integer. We shall denote by \([n]\) the set \(\{1,\ldots,n\}\). A classically studied class of sets \(B_h\) are defined as follows. A set \(S\subset\mathbb{N}\) is called a \(B_h\) set if for any \(x_1,y_1,\ldots,x_h,y_h\in S\) with \(\max\{x_1,\ldots,x_h\}\ne\max\{y_1,\ldots,y_h\}\) we have \(x_1+\cdots+x_h\ne y_1+\cdots+y_h\). A \(B_2\) set is called a Sidon set (as originally defined and studied by Sidon), and one of the problems of great interest in additive number theory concerns constructing Sidon sets (and more generally \(B_h\) sets for arbitrary \(h\)) which grow reasonably fast, i.e., Sidon sets \(S\) such that the function \(S(n):=|S\cap[n]|\) grows fast as a function of \(n\). It was proved by Erdős that any infinite Sidon set \(S\) satisfies \(\liminf_{n\to\infty} S(n)/\sqrt{n}=0\) and from the study of Sidon subsets of \([n]\) it is easy to show that \(\limsup_{n\to\infty} S(n)/\sqrt{n}\le 1\). At the end of a long line of researchers' efforts, \textit{I. Z. Ruzsa} [J. Number Theory 68, No. 1, 63--71 (1998; Zbl 0927.11005)] showed the existence of a Sidon set with \(S(n)=n^{\sqrt{2}-1+o(1)}\) by probabilistic arguments and then \textit{J. Cilleruelo} [Adv. Math. 255, 474--486 (2014; Zbl 1302.11006)] gave an explicit construction matching this same bound, and this is the best known growth for Sidon sets. More recently, \textit{Y. Kohayakawa} et al. [J. Comb. Theory, Ser. A 183, Article ID 105490, 29 p. (2021; Zbl 1489.11018)] defined a stronger notion for a Sidon set as follows. For \(0\le\alpha<1\) a set \(S\subset \mathbb{N}\) is said to be an \textit{\(\alpha\)-strong Sidon set} if for any \(x,y,z,w\in S\) we have \(|(x+w)-(y+z)|>\max\{x^{\alpha},y^{\alpha},z^{\alpha},w^{\alpha}\}\) whenever \(\max\{x,w\}\ne\max\{y,z\}\). The analogous question that one asks then is: How fast growing an \(\alpha\)-strong Sidon set can one construct? Kohayakawa et al showed the existence of an \(\alpha\)-strong Sidon set \(S\) with \[S(n)\ge n^{\frac{\sqrt{2}-1+o(1)}{1+32\sqrt{\alpha}}}\] for \(0\le \alpha\le 10^{-4}\). They also showed that a simple greedy argument gives a construction with \(S(n)\ge n^{(1-\alpha)/3}\) for any \(0\le \alpha<1\). One of the objectives of Kohayakawa et al was to study the maximal density of Sidon subsets of random subsets of \(\mathbb{N}\). More precisely, for \(0<\delta\le 1\) let \(R_{\delta}\) be a random set where each \(m\in\mathbb{N}\) is picked into \(R_{\delta}\) with probability \(m^{\delta-1}\) and independently; determine the maximum possible \(f(\delta)\) and minimum \(g(\delta)\) such that with probability 1, there is a Sidon set \(S\subset R_{\delta}\) with \(S(n)\ge n^{f(\delta)+o(1)}\), and \textit{any} Sidon subset \(S\subset R_{\delta}\) has \(S(n)\le n^{g(\delta)+o(1)}\). The main results of this paper improve upon the bounds for \(S(n)\) for \(\alpha\)-strong Sidon sets. In fact, the methods allow the authors to give similar bounds for \(S(n)\) for any infinite \(B_h\) subset of \(\mathbb{N}\) as well. More precisely, the authors prove the following: For every \(0\le \alpha<1\) and \(h\ge 2\), there is an \(\alpha\)-strong infinite \(B_h\) subset \(S\subset \mathbb{N}\) such that \[S(n)\ge n^{\sqrt{(h-1+\alpha/2)^2+1-\alpha} - (h-1+\alpha/2)+o(1)}.\] The paper also features an improved bound for the existence, with probability 1, of \(B_h\) subsets of a random \(R_{\delta}\) with the same bound as above, with \(1-\delta\) in place of \(\alpha\). The main idea of the paper -- if we skip over the many details -- and contrast this with the work of Kohayakawa et al is that while the latter build their constructions based on the randomized construction of Ruzsa attaining \(S(n)\ge n^{\sqrt{2}-1+o(1)}\), the authors here use the explicit construction of Cilleruelo as their starting point (at least for the case \(h=2\)). The paper is very well-written and both, the motivation as well as the ideas involved, are delineated very clearly.