An infinite Sidon sequence (Q1385264): Difference between revisions

The author proves the existence of a ``large'' infinite Sidon set of integers. A Sidon set of integers is one for which the equation \(x+y=z+w\), for elements of the set, implies \(\{x,y\} = \{z,w\}\). Suppose that \(A\) is such a sequence and write \(A(x)\) for the number of elements of \(A\) up to \(x\). It is trivial that \(A(x) \leq C x^{1/2}\) and one can give an easy ``greedy'' construction of a set \(A\) with \(A(x) \geq C x^{1/3}\). Many years ago Erdős proved that \(A(x) \leq C x^{1/2} \log^{-1/2} x\) for infinitely many \(x\). In the way of constructions, the only significant step up to now was the result of \textit{M. Ajtai, J. Komlós} and \textit{E. Szemerédi} [Eur. J. Comb. 2, 1-11 (1981; Zbl 0474.10038)], who proved, almost 20 years ago, a very slight improvement over the greedy construction, that such a set \(A\) exists for which \(A(x) \geq C (x \log x)^{1/3}\). The author's result, the construction of such an \(A\) with \(A(x) = C x^{\sqrt 2 - 1 + o(1)} \geq C x^{0.4142\cdots}\), represents thus a major step forward in the direction of proving the conjecture of Erdős that Sidon sets exist with at least \(x^{1/2-\varepsilon}\) elements up to \(x\), for all \(\varepsilon>0\). It is also important that the construction is almost completely deterministic and explicit, apart from the random choice of a single random real number \(\alpha \in [1,2]\). The starting point is that the set \(\{\alpha\log p:\;p\text{\;a\;prime}\}\) is a Sidon set of \textit{reals}. To make from this a Sidon set of integers (1) only a finite number of binary digits (which increases linearly in \(\log p\)) of \(\alpha \log p\) is kept, and (2) an integer is constructed from the remaining binary digits in such a way that, for the resulting set of integers, the number of coincidences of the sums \(x+y\) is small and the set can be made Sidon with few deletions, leaving behind a large Sidon set.