# P2990: Existence of dense infinite Sidon sets - ID: `P2990` - Reference: `erdos-problem-39` - Page: https://theoremdb.org/statements/P2990 - Record maturity: Reviewed problem with recorded work ## Problem Erdős Problem 39: A set $A$ of natural numbers is called a Sidon set if all pairwise sums of its elements are distinct, i.e., if $a + b = c + d$ with $a, b, c, d \in A$, then $\{a, b\} = \{c, d\}$. Does there exist an infinite Sidon set $A \subseteq \mathbb{N}$ such that for every real number $\varepsilon > 0$, the counting function satisfies \[ |A \cap \{1, 2, \ldots, N\}| \gg_\varepsilon N^{1/2 - \varepsilon} \] as $N \to \infty$? Here, the notation $f(N) \gg_\varepsilon g(N)$ means that $g(N) = O(f(N))$ with the implied constant depending on $\varepsilon$. ### Context This is a classical problem in additive combinatorics concerning the maximum possible density of infinite Sidon sets. Sidon sets are also known as $B_2$ sets in the literature. The problem asks whether the trivial upper bound of $O(N^{1/2})$ for the size of a Sidon set in $\{1, \ldots, N\}$ can be nearly attained by an infinite set, up to an arbitrarily small polynomial factor $N^{-\varepsilon}$. ### Problem setup - **Definition (A Sidon set).** A Sidon set is a set of natural numbers in which all pairwise sums of (not necessarily distinct) elements are distinct, except for the trivial reordering of terms. - **Definition (For functions $f, g: \mathbb{N} \to \mathbb{R}_{\geq 0}$, the notation $f(N) \gg_\varepsilon g(N)$).** For functions $f, g: \mathbb{N} \to \mathbb{R}_{\geq 0}$, the notation $f(N) \gg_\varepsilon g(N)$ means that there exists a constant $C_\varepsilon > 0$ depending on $\varepsilon$ such that $g(N) \leq C_\varepsilon \cdot f(N)$ for all sufficiently large $N$. - **Definition (The notation $g(N) = O(f(N))$ as $N \to \infty$).** The notation $g(N) = O(f(N))$ as $N \to \infty$ means that there exists a constant $C > 0$ and $N_0 \in \mathbb{N}$ such that $|g(N)| \leq C \cdot |f(N)|$ for all $N \geq N_0$. - **Remark.** This is a classical problem in additive combinatorics concerning the maximum possible density of infinite Sidon sets. Sidon sets are also known as $B_2$ sets in the literature. The problem asks whether the trivial upper bound of $O(N^{1/2})$ for the size of a Sidon set in $\{1, \ldots, N\}$ can be nearly attained by an infinite set, up to an arbitrarily small polynomial factor $N^{-\varepsilon}$. ### What counts as a solution - Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 39: A set $A$ of natural numbers is called a Sidon set if all pairwise sums of its elements are distinct, i.e., if $a + b = c + d$ with $a, b, c, d \in A$, then $\{a, b\} = \{c, d\}$. Does there exist an infinite Sidon set $A \subseteq \mathbb{N}$ such that for every real number $\varepsilon > 0$, the counting function satisfies \[ |A \cap \{1, 2, \ldots, N\}| \gg_\varepsilon N^{1/2 - \varepsilon} \] as $N \to \infty$? Here, the notation $f(N) \gg_\varepsilon g(N)$ means that $g(N) = O(f(N))$ with the implied constant depending on $\varepsilon$. ## Status OPEN as of 2026-07-31. The maintained Erdős Problems database at commit 8138974387d9030542daabe67faaa33eff9356f8 lists Problem 39 as open. The unresolved remainder is the full displayed statement. Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 39: A set $A$ of natural numbers is called a Sidon set if all pairwise sums of its elements are distinct, i.e., if $a + b = c + d$ with $a, b, c, d \in A$, then $\{a, b\} = \{c, d\}$. Does there exist an infinite Sidon set $A \subseteq \mathbb{N}$ such that for every real number $\varepsilon > 0$, the counting function satisfies \[ |A \cap \{1, 2, \ldots, N\}| \gg_\varepsilon N^{1/2 - \varepsilon} \] as $N \to \infty$? Here, the notation $f(N) \gg_\varepsilon g(N)$ means that $g(N) = O(f(N))$ with the implied constant depending on $\varepsilon$. [1](#reference-1) ## Work ### Evidence for the current status **Claim 1 (Current status and unresolved remainder).** OPEN as of 2026-07-31. The maintained Erdős Problems database at commit 8138974387d9030542daabe67faaa33eff9356f8 lists Problem 39 as open. The unresolved remainder is the full displayed statement. Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 39: A set $A$ of natural numbers is called a Sidon set if all pairwise sums of its elements are distinct, i.e., if $a + b = c + d$ with $a, b, c, d \in A$, then $\{a, b\} = \{c, d\}$. Does there exist an infinite Sidon set $A \subseteq \mathbb{N}$ such that for every real number $\varepsilon > 0$, the counting function satisfies \[ |A \cap \{1, 2, \ldots, N\}| \gg_\varepsilon N^{1/2 - \varepsilon} \] as $N \to \infty$? Here, the notation $f(N) \gg_\varepsilon g(N)$ means that $g(N) = O(f(N))$ with the implied constant depending on $\varepsilon$. OPEN as of 2026-07-31. The maintained Erdős Problems database at commit 8138974387d9030542daabe67faaa33eff9356f8 lists Problem 39 as open. The unresolved remainder is the full displayed statement. A complete resolution must satisfy this condition: Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 39: A set $A$ of natural numbers is called a Sidon set if all pairwise sums of its elements are distinct, i.e., if $a + b = c + d$ with $a, b, c, d \in A$, then $\{a, b\} = \{c, d\}$. Does there exist an infinite Sidon set $A \subseteq \mathbb{N}$ such that for every real number $\varepsilon > 0$, the counting function satisfies \[ |A \cap \{1, 2, \ldots, N\}| \gg_\varepsilon N^{1/2 - \varepsilon} \] as $N \to \infty$? Here, the notation $f(N) \gg_\varepsilon g(N)$ means that $g(N) = O(f(N))$ with the implied constant depending on $\varepsilon$. ### Background and intake notes - Original intake status: OPEN as of 2026-07-31. The maintained Erdős Problems database at commit 8138974387d9030542daabe67faaa33eff9356f8 lists Problem 39 as open. The unresolved remainder is the full displayed statement. - The maintained database entry for Erdős Problem 39 was open at commit 8138974387d9030542daabe67faaa33eff9356f8. - The pinned Formal Conjectures declaration was matched by problem number and source locator. - The controlled TheoremDB source corpus was checked for an already published record with the same slug. ### Open directions - **Route 1** (reported): Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 39: A set $A$ of natural numbers is called a Sidon set if all pairwise sums of its elements are distinct, i.e., if $a + b = c + d$ with $a, b, c, d \in A$, then $\{a, b\} = \{c, d\}$. Does there exist an infinite Sidon set $A \subseteq \mathbb{N}$ such that for every real number $\varepsilon > 0$, the counting function satisfies \[ |A \cap \{1, 2, \ldots, N\}| \gg_\varepsilon N^{1/2 - \varepsilon} \] as $N \to \infty$? Here, the notation $f(N) \gg_\varepsilon g(N)$ means that $g(N) = O(f(N))$ with the implied constant depending on $\varepsilon$. [1](#reference-1) ### Working on this Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `erdos-problem-39`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome. ## References 1. Erdős Problems database, Problem 39, maintained status record. Erdős Problems record 39, checked 2026-08-01. Problem 39; status field and linked bibliography https://www.erdosproblems.com/39 - Also cited at Problem 39; status snapshot 8138974387d9030542daabe67faaa33eff9356f8 - Also cited at See dataset.references[0] for the exact external source and locator. - Also cited at Editorial research route recorded 2026-07-31 - reference_database; reference source; commit 8138974387d9030542daabe67faaa33eff9356f8; checked 2026-07-31 - Source use: original_summary - Records the current open status and links the literature attached to this exact numbered problem. - Source used to formulate or check the problem record. - Source used to assess the problem's recorded status. - For Existence of dense infinite Sidon sets: Records the current open status and links the literature attached to this exact numbered problem. - Source named by the research packet. 2. Erdős problem database, data/problems.yaml, commit 8138974387d9030542daabe67faaa33eff9356f8. Problem 39 entry in data/problems.yaml https://github.com/teorth/erdosproblems/blob/8138974387d9030542daabe67faaa33eff9356f8/data/problems.yaml - reference_database; reference source; commit 8138974387d9030542daabe67faaa33eff9356f8; checked 2026-07-31 - Source use: original_summary - Pins the maintained database snapshot used for this release's dated status decision. - Source used to assess the problem's recorded status. - For Existence of dense infinite Sidon sets: Pins the maintained database snapshot used for this release's dated status decision. 3. Google DeepMind, Formal Conjectures, formal statement for Erdős Problem 39. GitHub commit bb1c69dab14ad895ac1ccdb7b0c0e0a67c8eb3e1. FormalConjectures/ErdosProblems/39.lean:L35; theorem erdos_39; commit bb1c69dab14ad895ac1ccdb7b0c0e0a67c8eb3e1 https://github.com/google-deepmind/formal-conjectures/blob/bb1c69dab14ad895ac1ccdb7b0c0e0a67c8eb3e1/FormalConjectures/ErdosProblems/39.lean#L35 - reference_database; primary source; commit bb1c69dab14ad895ac1ccdb7b0c0e0a67c8eb3e1; checked 2026-07-31 - Source use: original_summary - Supplies the pinned formal declaration whose human-readable editorial statement is published here. - Source used to assess the problem's recorded status. - For Existence of dense infinite Sidon sets: Supplies the pinned formal declaration whose human-readable editorial statement is published here.