An infinite Sidon sequence (Q1385264): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
(5 intermediate revisions by 4 users not shown) | |||
Property / author | |||
Property / author: Imre Z. Ruzsa / rank | |||
Property / reviewed by | |||
Property / reviewed by: Mihail N. Kolountzakis / rank | |||
Property / Wikidata QID | |||
Property / Wikidata QID: Q105583199 / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Imre Z. Ruzsa / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Mihail N. Kolountzakis / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1006/jnth.1997.2192 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2046768141 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A dense infinite Sidon sequence / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5515488 / rank | |||
Normal rank |
Latest revision as of 12:21, 28 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An infinite Sidon sequence |
scientific article |
Statements
An infinite Sidon sequence (English)
0 references
12 December 1999
0 references
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.
0 references
infinite Sidon sets of integers
0 references
B2 sets
0 references