More generally: Let a_1 < a_2 < … < a_k_1 ≤ n, b_1 < b_2 < … < b_k_2 ≤ n be two Sidon sequences for which a_j - a_i ≠ b_v - b_u for all i < j and u < v. How large can max(binomk_12 + binomk_22) be? I guessed [31] that it is less than binomh(n)2 + O(1). I offer 100 dollars for a proof or disproof. Assume next that k_1 = k_2. I am sure that then binomk_12 + binomk_22 < (1 - c)binomh(n)2.

Erdős Problem #43 — Maximizing total pair counts of two difference-disjoint Sidon sets

About 31 years old · traced to 1995

More generally: Let $a_1 < a_2 < \cdots < a_{k_1} \leq n$ , $b_1 < b_2 < \cdots < b_{k_2} \leq n$ be two Sidon sequences for which $a_j - a_i \neq b_v - b_u$ for all $i < j$ and $u < v$ . How large can

\max\left(\binom{k_1}{2} + \binom{k_2}{2}\right)

be? I guessed [31] that it is less than $\binom{h(n)}{2} + O(1)$ . I offer 100 dollars for a proof or disproof. Assume next that $k_1 = k_2$ . I am sure that then

\binom{k_1}{2} + \binom{k_2}{2} < (1 - c)\binom{h(n)}{2}.

References

Primary source

P. Erdős, Some of my favourite problems in number theory, combinatorics, and geometry, Resenhas IME-USP 2 (1995), 165-186.

Additional references

P. Erdős, Some of my favourite problems in number theory, combinatorics, and geometry, Resenhas IME-USP 2 (1995), 165-186.

InErdős Problems

Posted 2 months ago

Progress summary

Refreshed 1 month ago

Open

Reported constructions now refute both proposed statements, but no retrieved paper confirms the claims.

Erdős offered a prize in 1995 for proving or disproving the first assertion. The problem also asks whether equal-sized sets permit a fixed positive improvement.

Known results

Erdős (1982): $\binom{|A|}{2}+\binom{|B|}{2}\leq(1+o(1))N/2\sim\binom{f(N)}{2}$ , though the $O(1)$ error term may be too optimistic.
Tao: $|A|^2+|B|^2\leq N+O(\sqrt N)$ , hence equal-sized sets satisfy $|A|=|B|\leq N^{1/2}/\sqrt{2}+O(1)$ , without a fixed positive improvement.

Barreto's negative answer (recorded May 2026)

The construction solving Problem #42 gives $|A|=f(N)$ with $|B|\to\infty$ , refuting the first assertion. Barreto is credited with infinitely many equal-sized examples satisfying $\binom{|A|}{2}+\binom{|B|}{2}\geq(1-o(1))\binom{f(N)}{2}$ , refuting any fixed proportional improvement; a finite $N=24$ example even exceeds $\binom{f(N)}{2}$ .

Current status (as of May 2026): negative answers to both questions are recorded, but formal independent corroboration remains absent.

Sources

erdosproblems.com

No solutions have been posted yet.