Erdős Problem #773 — What is the size of the largest Sidon subset ?
For a positive integer , let . A subset is Sidon if each integer has at most one representation as an unordered sum of two elements of , allowing the two elements to be equal; equivalently, for implies as multisets. Define
The question is whether as , meaning that for every , for all sufficiently large . Erdős Problem #773 A combinatorial large sieve for Sidon sets, distances, and norm forms
Background
The problem is associated with Erdős’s 1980 collection of questions and was studied by Alon and Erdős in 1985. It asks how large a Sidon set can be when its elements are restricted to the sparse, highly structured set of the first squares, rather than an interval of integers. Erdős Problem #773 Alon and Erdős (1985)
A basic upper bound follows by counting possible sums. If , the Sidon property gives distinct unordered pair-sums. Each is a sum of two squares and is at most ; the Landau–Ramanujan estimate gives integers of this form up to . Comparing these counts yields . This illustrates the role of the arithmetic sparsity of the sumset, beyond the Sidon condition alone. Erdős Problem #773 A combinatorial large sieve for Sidon sets, distances, and norm forms
References
UnsolvedMath, Erdős Problems set, ULAM AI, licensed CC BY 4.0.
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.