← All problems

Erdős Problem #157 — A Sidon set that is an asymptotic basis of order three

32 years old · traced to

Does there exist an infinite set A⊆NA\subseteq\mathbb{N} that is both a Sidon set and an asymptotic basis of order 33? Here Sidon means that sums of unordered pairs, with repetition allowed, are all distinct: for a,b,c,d∈Aa,b,c,d\in A with a≤ba\le b and c≤dc\le d,

a+b=c+d⟹a=c and b=d.a+b=c+d\quad\Longrightarrow\quad a=c\text{ and }b=d.

The basis condition means that there is an n0n_0 such that every n∈Nn\in\mathbb{N} with n≥n0n\ge n_0 admits a representation

n=a1+a2+a3,a1,a2,a3∈A,n=a_1+a_2+a_3,\qquad a_1,a_2,a_3\in A,

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 {1,…,n}\{1,\ldots,n\}, its pair-sum set cannot contain Cn1/2C n^{1/2} consecutive integers, for an absolute constant C>0C>0. Earlier constructions reached weaker basis conclusions, including orders 77, 55, and 44, and Cilleruelo’s order-3+ε3+\varepsilon variant, in which sufficiently large nn is a sum of four elements with one at most nεn^\varepsilon. Kiss and Sándor also constructed a Sidon sequence whose three-fold sumset has lower asymptotic density greater than 0.00640.0064; 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.

Source: P. Erdős, Some problems in number theory, combinatorics and combinatorial geometry, Mathematica Pannonica 5 (1994), no. 2, 261–269.

Progress summary

Never refreshed

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.