Erdős Problem #157 — A Sidon set that is an asymptotic basis of order three
Does there exist an infinite set that is both a Sidon set and an asymptotic basis of order ? Here Sidon means that sums of unordered pairs, with repetition allowed, are all distinct: for with and ,
The basis condition means that there is an such that every with admits a representation
where repetitions among the three summands are permitted. Pilatte (2024)
Background
Erdős, Sárközy, and Sós posed this existence question in 1993; Pilatte also records it as an old problem of Nathanson and Erdős. The order three is the first possible order: Erdős, Sárközy, and Sós proved that if a Sidon set is restricted to , its pair-sum set cannot contain consecutive integers, for an absolute constant . Earlier constructions reached weaker basis conclusions, including orders , , and , and Cilleruelo’s order- variant, in which sufficiently large is a sum of four elements with one at most . Kiss and Sándor also constructed a Sidon sequence whose three-fold sumset has lower asymptotic density greater than ; positive lower density does not itself give an asymptotic basis. Pilatte (2024)
A central obstacle in adapting ordinary random-subset constructions is that the sparsity useful for enforcing the Sidon property does not readily provide representations of every sufficiently large integer as three summands. Pilatte instead builds on Ruzsa- and Cilleruelo-type encodings: discrete logarithms of irreducible polynomials over a finite field are placed in a base expansion, with carefully chosen random digits filling positions in the encoding. Congruences control pair-sum collisions, while coverage by triple sums is tied to the distribution of products of three irreducible polynomials in residue classes. Pilatte (2024)
References
P. Erdős, Some problems in number theory, combinatorics and combinatorial geometry, Mathematica Pannonica 5 (1994), no. 2, 261–269.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.