← All problems

Erdős Problem #773 — What is the size of the largest Sidon subset A⊆{1,22,…,N2}A\subseteq\{1,2^2,\ldots,N^2\}?

41 years old · traced to

For a positive integer NN, let QN={n2:1≤n≤N}Q_N=\{n^2:1\le n\le N\}. A subset A⊆QNA\subseteq Q_N is Sidon if each integer has at most one representation as an unordered sum of two elements of AA, allowing the two elements to be equal; equivalently, a+b=c+da+b=c+d for a,b,c,d∈Aa,b,c,d\in A implies {a,b}={c,d}\{a,b\}=\{c,d\} as multisets. Define

M(N)=max⁡{∣A∣:A⊆QN is Sidon}.M(N)=\max\{|A|:A\subseteq Q_N\text{ is Sidon}\}.

The question is whether M(N)=N1−o(1)M(N)=N^{1-o(1)} as N→∞N\to\infty, meaning that for every ε>0\varepsilon>0, M(N)≥N1−εM(N)\ge N^{1-\varepsilon} for all sufficiently large NN. 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 NN 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 ∣A∣=m|A|=m, the Sidon property gives m(m+1)/2m(m+1)/2 distinct unordered pair-sums. Each is a sum of two squares and is at most 2N22N^2; the Landau–Ramanujan estimate gives O(N2/log⁡N)O(N^2/\sqrt{\log N}) integers of this form up to 2N22N^2. Comparing these counts yields m≪N/(log⁡N)1/4m\ll N/(\log N)^{1/4}. 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

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.