# P2992: Erdős Problem 40 on additive bases with slow growth

- ID: `P2992`
- Reference: `erdos-problem-40`
- Page: https://theoremdb.org/statements/P2992
- Record maturity: Reviewed problem with recorded work

## Problem

Erdős Problem 40: For a set $A \subseteq \mathbb{N}$ and a positive integer $N$, let $|A \cap \{1, \ldots, N\}|$ denote the cardinality of the intersection. For $n \in \mathbb{N}$, define the representation function $(1_A * 1_A)(n)$ as the number of ordered pairs $(a, b) \in A \times A$ such that $a + b = n$. We say that a property holds for sets $A$ satisfying $|A \cap \{1, \ldots, N\}| \gg \frac{\sqrt{N}}{g(N)}$ if there exists a positive constant $C$ such that $|A \cap \{1, \ldots, N\}| \geq C \cdot \frac{\sqrt{N}}{g(N)}$ for all sufficiently large $N$. A function $g: \mathbb{N} \to \mathbb{R}$ tends to infinity if for every $M > 0$, there exists $N_0$ such that $g(N) > M$ for all $N \geq N_0$. Determine the set of all functions $g: \mathbb{N} \to \mathbb{R}$ tending to infinity such that for every set $A \subseteq \mathbb{N}$ satisfying $|A \cap \{1, \ldots, N\}| \gg \frac{\sqrt{N}}{g(N)}$, we have $\limsup_{n \to \infty} (1_A * 1_A)(n) = \infty$.

### Context

This problem originates from Erdős and concerns additive bases. The Erdős–Turán conjecture on additive bases (Erdős Problem 28) asserts that if $A$ is an asymptotic basis of order 2 (meaning every sufficiently large integer is a sum of two elements of $A$), then the representation function is unbounded. Problem 40 asks for a refinement: how slowly can the counting function $|A \cap \{1, \ldots, N\}|$ grow, relative to $\sqrt{N}$, while still guaranteeing that the representation function has unbounded limsup?

### Problem setup

- **Definition (For a set $A \subseteq \mathbb{N}$ and $n \in \mathbb{N}$, the representation function $(1_A * 1_A)(n)$).** For a set $A \subseteq \mathbb{N}$ and $n \in \mathbb{N}$, the representation function $(1_A * 1_A)(n)$ is defined as $\sum_{a + b = n} 1_A(a) \cdot 1_A(b)$, which counts ordered pairs $(a, b) \in A \times A$ with $a + b = n$.
- **Definition (For functions $f, h: \mathbb{N} \to \mathbb{R}$, we write $f(N) =O h(N)$ as $N \to \infty$ if there exists a positive constant $C$ and $N_0 \in \mathbb{N}$ such that $|f(N)| \leq C \cdot |h(N)|$ for all $N \geq N_0$).** For functions $f, h: \mathbb{N} \to \mathbb{R}$, we write $f(N) =O h(N)$ as $N \to \infty$ if there exists a positive constant $C$ and $N_0 \in \mathbb{N}$ such that $|f(N)| \leq C \cdot |h(N)|$ for all $N \geq N_0$.
- **Definition (For a set $A \subseteq \mathbb{N}$ and a function $g: \mathbb{N} \to \mathbb{R}$, the condition $|A \cap \{1, \ldots, N\}| \gg \frac{\sqrt{N}}{g(N)}$).** For a set $A \subseteq \mathbb{N}$ and a function $g: \mathbb{N} \to \mathbb{R}$, the condition $|A \cap \{1, \ldots, N\}| \gg \frac{\sqrt{N}}{g(N)}$ means that the function $N \mapsto \frac{\sqrt{N}}{g(N)}$ is $O$-big-oh of the function $N \mapsto |A \cap \{1, \ldots, N\}|$ as $N \to \infty$.
- **Remark.** This problem originates from Erdős and concerns additive bases. The Erdős–Turán conjecture on additive bases (Erdős Problem 28) asserts that if $A$ is an asymptotic basis of order 2 (meaning every sufficiently large integer is a sum of two elements of $A$), then the representation function is unbounded. Problem 40 asks for a refinement: how slowly can the counting function $|A \cap \{1, \ldots, N\}|$ grow, relative to $\sqrt{N}$, while still guaranteeing that the representation function has unbounded limsup?

### What counts as a solution

- Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 40: For a set $A \subseteq \mathbb{N}$ and a positive integer $N$, let $|A \cap \{1, \ldots, N\}|$ denote the cardinality of the intersection. For $n \in \mathbb{N}$, define the representation function $(1_A * 1_A)(n)$ as the number of ordered pairs $(a, b) \in A \times A$ such that $a + b = n$. We say that a property holds for sets $A$ satisfying $|A \cap \{1, \ldots, N\}| \gg \frac{\sqrt{N}}{g(N)}$ if there exists a positive constant $C$ such that $|A \cap \{1, \ldots, N\}| \geq C \cdot \frac{\sqrt{N}}{g(N)}$ for all sufficiently large $N$. A function $g: \mathbb{N} \to \mathbb{R}$ tends to infinity if for every $M > 0$, there exists $N_0$ such that $g(N) > M$ for all $N \geq N_0$. Determine the set of all functions $g: \mathbb{N} \to \mathbb{R}$ tending to infinity such that for every set $A \subseteq \mathbb{N}$ satisfying $|A \cap \{1, \ldots, N\}| \gg \frac{\sqrt{N}}{g(N)}$, we have $\limsup_{n \to \infty} (1_A * 1_A)(n) = \infty$.

## Status

OPEN as of 2026-07-31. The maintained Erdős Problems database at commit 8138974387d9030542daabe67faaa33eff9356f8 lists Problem 40 as open. The unresolved remainder is the full displayed statement. Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 40: For a set $A \subseteq \mathbb{N}$ and a positive integer $N$, let $|A \cap \{1, \ldots, N\}|$ denote the cardinality of the intersection. For $n \in \mathbb{N}$, define the representation function $(1_A * 1_A)(n)$ as the number of ordered pairs $(a, b) \in A \times A$ such that $a + b = n$. We say that a property holds for sets $A$ satisfying $|A \cap \{1, \ldots, N\}| \gg \frac{\sqrt{N}}{g(N)}$ if there exists a positive constant $C$ such that $|A \cap \{1, \ldots, N\}| \geq C \cdot \frac{\sqrt{N}}{g(N)}$ for all sufficiently large $N$. A function $g: \mathbb{N} \to \mathbb{R}$ tends to infinity if for every $M > 0$, there exists $N_0$ such that $g(N) > M$ for all $N \geq N_0$. Determine the set of all functions $g: \mathbb{N} \to \mathbb{R}$ tending to infinity such that for every set $A \subseteq \mathbb{N}$ satisfying $|A \cap \{1, \ldots, N\}| \gg \frac{\sqrt{N}}{g(N)}$, we have $\limsup_{n \to \infty} (1_A * 1_A)(n) = \infty$. [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 40 as open. The unresolved remainder is the full displayed statement. Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 40: For a set $A \subseteq \mathbb{N}$ and a positive integer $N$, let $|A \cap \{1, \ldots, N\}|$ denote the cardinality of the intersection. For $n \in \mathbb{N}$, define the representation function $(1_A * 1_A)(n)$ as the number of ordered pairs $(a, b) \in A \times A$ such that $a + b = n$. We say that a property holds for sets $A$ satisfying $|A \cap \{1, \ldots, N\}| \gg \frac{\sqrt{N}}{g(N)}$ if there exists a positive constant $C$ such that $|A \cap \{1, \ldots, N\}| \geq C \cdot \frac{\sqrt{N}}{g(N)}$ for all sufficiently large $N$. A function $g: \mathbb{N} \to \mathbb{R}$ tends to infinity if for every $M > 0$, there exists $N_0$ such that $g(N) > M$ for all $N \geq N_0$. Determine the set of all functions $g: \mathbb{N} \to \mathbb{R}$ tending to infinity such that for every set $A \subseteq \mathbb{N}$ satisfying $|A \cap \{1, \ldots, N\}| \gg \frac{\sqrt{N}}{g(N)}$, we have $\limsup_{n \to \infty} (1_A * 1_A)(n) = \infty$.

OPEN as of 2026-07-31. The maintained Erdős Problems database at commit 8138974387d9030542daabe67faaa33eff9356f8 lists Problem 40 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 40: For a set $A \subseteq \mathbb{N}$ and a positive integer $N$, let $|A \cap \{1, \ldots, N\}|$ denote the cardinality of the intersection. For $n \in \mathbb{N}$, define the representation function $(1_A * 1_A)(n)$ as the number of ordered pairs $(a, b) \in A \times A$ such that $a + b = n$. We say that a property holds for sets $A$ satisfying $|A \cap \{1, \ldots, N\}| \gg \frac{\sqrt{N}}{g(N)}$ if there exists a positive constant $C$ such that $|A \cap \{1, \ldots, N\}| \geq C \cdot \frac{\sqrt{N}}{g(N)}$ for all sufficiently large $N$. A function $g: \mathbb{N} \to \mathbb{R}$ tends to infinity if for every $M > 0$, there exists $N_0$ such that $g(N) > M$ for all $N \geq N_0$. Determine the set of all functions $g: \mathbb{N} \to \mathbb{R}$ tending to infinity such that for every set $A \subseteq \mathbb{N}$ satisfying $|A \cap \{1, \ldots, N\}| \gg \frac{\sqrt{N}}{g(N)}$, we have $\limsup_{n \to \infty} (1_A * 1_A)(n) = \infty$.

### Background and intake notes

- Original intake status: OPEN as of 2026-07-31. The maintained Erdős Problems database at commit 8138974387d9030542daabe67faaa33eff9356f8 lists Problem 40 as open. The unresolved remainder is the full displayed statement.
- The maintained database entry for Erdős Problem 40 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 40: For a set $A \subseteq \mathbb{N}$ and a positive integer $N$, let $|A \cap \{1, \ldots, N\}|$ denote the cardinality of the intersection. For $n \in \mathbb{N}$, define the representation function $(1_A * 1_A)(n)$ as the number of ordered pairs $(a, b) \in A \times A$ such that $a + b = n$. We say that a property holds for sets $A$ satisfying $|A \cap \{1, \ldots, N\}| \gg \frac{\sqrt{N}}{g(N)}$ if there exists a positive constant $C$ such that $|A \cap \{1, \ldots, N\}| \geq C \cdot \frac{\sqrt{N}}{g(N)}$ for all sufficiently large $N$. A function $g: \mathbb{N} \to \mathbb{R}$ tends to infinity if for every $M > 0$, there exists $N_0$ such that $g(N) > M$ for all $N \geq N_0$. Determine the set of all functions $g: \mathbb{N} \to \mathbb{R}$ tending to infinity such that for every set $A \subseteq \mathbb{N}$ satisfying $|A \cap \{1, \ldots, N\}| \gg \frac{\sqrt{N}}{g(N)}$, we have $\limsup_{n \to \infty} (1_A * 1_A)(n) = \infty$. [1](#reference-1)

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `erdos-problem-40`, 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. <a id="reference-1"></a>Erdős Problems database, Problem 40, maintained status record. Erdős Problems record 40, checked 2026-08-01. Problem 40; status field and linked bibliography https://www.erdosproblems.com/40
   - Also cited at Problem 40; 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 Erdős Problem 40 on additive bases with slow growth: Records the current open status and links the literature attached to this exact numbered problem.
   - Source named by the research packet.
2. <a id="reference-2"></a>Erdős problem database, data/problems.yaml, commit 8138974387d9030542daabe67faaa33eff9356f8. Problem 40 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 Erdős Problem 40 on additive bases with slow growth: Pins the maintained database snapshot used for this release's dated status decision.
3. <a id="reference-3"></a>Google DeepMind, Formal Conjectures, formal statement for Erdős Problem 40. GitHub commit bb1c69dab14ad895ac1ccdb7b0c0e0a67c8eb3e1. FormalConjectures/ErdosProblems/40.lean:L55; theorem erdos_40; commit bb1c69dab14ad895ac1ccdb7b0c0e0a67c8eb3e1 https://github.com/google-deepmind/formal-conjectures/blob/bb1c69dab14ad895ac1ccdb7b0c0e0a67c8eb3e1/FormalConjectures/ErdosProblems/40.lean#L55
   - 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 Erdős Problem 40 on additive bases with slow growth: Supplies the pinned formal declaration whose human-readable editorial statement is published here.