# P3048: Asymptotic formula for the maximum size of a 3-term-AP-free subset of \(\{1,\dots,N\}\)

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

## Problem

Erdős Problem 142: For a positive integer \(N\), let \(r_3(N)\) denote the largest possible cardinality of a subset of \(\{1, 2, \dots, N\}\) that contains no non-trivial 3-term arithmetic progression. A 3-term arithmetic progression is called non-trivial if its terms are distinct. Determine whether there exists a function \(f: \mathbb{N} \to \mathbb{R}\) such that \(r_3(N) = \Theta(f(N))\) as \(N \to \infty\), and if so, identify such a function. That is, find an explicit asymptotic formula for \(r_3(N)\) up to constant factors.

### Context

This problem concerns the quantitative behavior of sets avoiding 3-term arithmetic progressions, a central topic in additive combinatorics. The function \(r_3(N)\) measures how large a subset of the first \(N\) positive integers can be while avoiding any three distinct elements in arithmetic progression.

### Problem setup

- **Definition (For positive integers \(k\) and \(N\), the quantity \(r_k(N)\).** For positive integers \(k\) and \(N\), the quantity \(r_k(N)\) is defined as the maximum cardinality of a subset \(A \subseteq \{1, 2, \dots, N\}\) such that \(A\) contains no non-trivial \(k\)-term arithmetic progression. A \(k\)-term arithmetic progression is a sequence of the form \(a, a+d, a+2d, \dots, a+(k-1)d\), and it is called non-trivial when the common difference \(d\) is non-zero, or equivalently when all \(k\) terms are distinct.
- **Definition (Definition 2).** For functions \(f, g: \mathbb{N} \to \mathbb{R}_{\geq 0}\), we write \(f(N) = \Theta(g(N))\) as \(N \to \infty\) if there exist positive constants \(c_1, c_2\) and a positive integer \(N_0\) such that \(c_1 g(N) \leq f(N) \leq c_2 g(N)\) for all \(N \geq N_0\).
- **Remark.** This problem concerns the quantitative behavior of sets avoiding 3-term arithmetic progressions, a central topic in additive combinatorics. The function \(r_3(N)\) measures how large a subset of the first \(N\) positive integers can be while avoiding any three distinct elements in arithmetic progression.

### What counts as a solution

- Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 142: For a positive integer \(N\), let \(r_3(N)\) denote the largest possible cardinality of a subset of \(\{1, 2, \dots, N\}\) that contains no non-trivial 3-term arithmetic progression. A 3-term arithmetic progression is called non-trivial if its terms are distinct. Determine whether there exists a function \(f: \mathbb{N} \to \mathbb{R}\) such that \(r_3(N) = \Theta(f(N))\) as \(N \to \infty\), and if so, identify such a function. That is, find an explicit asymptotic formula for \(r_3(N)\) up to constant factors.

## Status

OPEN as of 2026-07-31. The maintained Erdős Problems database at commit 8138974387d9030542daabe67faaa33eff9356f8 lists Problem 142 as open. The unresolved remainder is the full displayed statement. Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 142: For a positive integer \(N\), let \(r_3(N)\) denote the largest possible cardinality of a subset of \(\{1, 2, \dots, N\}\) that contains no non-trivial 3-term arithmetic progression. A 3-term arithmetic progression is called non-trivial if its terms are distinct. Determine whether there exists a function \(f: \mathbb{N} \to \mathbb{R}\) such that \(r_3(N) = \Theta(f(N))\) as \(N \to \infty\), and if so, identify such a function. That is, find an explicit asymptotic formula for \(r_3(N)\) up to constant factors. [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 142 as open. The unresolved remainder is the full displayed statement. Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 142: For a positive integer \(N\), let \(r_3(N)\) denote the largest possible cardinality of a subset of \(\{1, 2, \dots, N\}\) that contains no non-trivial 3-term arithmetic progression. A 3-term arithmetic progression is called non-trivial if its terms are distinct. Determine whether there exists a function \(f: \mathbb{N} \to \mathbb{R}\) such that \(r_3(N) = \Theta(f(N))\) as \(N \to \infty\), and if so, identify such a function. That is, find an explicit asymptotic formula for \(r_3(N)\) up to constant factors.

OPEN as of 2026-07-31. The maintained Erdős Problems database at commit 8138974387d9030542daabe67faaa33eff9356f8 lists Problem 142 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 142: For a positive integer \(N\), let \(r_3(N)\) denote the largest possible cardinality of a subset of \(\{1, 2, \dots, N\}\) that contains no non-trivial 3-term arithmetic progression. A 3-term arithmetic progression is called non-trivial if its terms are distinct. Determine whether there exists a function \(f: \mathbb{N} \to \mathbb{R}\) such that \(r_3(N) = \Theta(f(N))\) as \(N \to \infty\), and if so, identify such a function. That is, find an explicit asymptotic formula for \(r_3(N)\) up to constant factors.

### Background and intake notes

- Original intake status: OPEN as of 2026-07-31. The maintained Erdős Problems database at commit 8138974387d9030542daabe67faaa33eff9356f8 lists Problem 142 as open. The unresolved remainder is the full displayed statement.
- The maintained database entry for Erdős Problem 142 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 142: For a positive integer \(N\), let \(r_3(N)\) denote the largest possible cardinality of a subset of \(\{1, 2, \dots, N\}\) that contains no non-trivial 3-term arithmetic progression. A 3-term arithmetic progression is called non-trivial if its terms are distinct. Determine whether there exists a function \(f: \mathbb{N} \to \mathbb{R}\) such that \(r_3(N) = \Theta(f(N))\) as \(N \to \infty\), and if so, identify such a function. That is, find an explicit asymptotic formula for \(r_3(N)\) up to constant factors. [1](#reference-1)

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `erdos-problem-142`, 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 142, maintained status record. Erdős Problems record 142, checked 2026-08-01. Problem 142; status field and linked bibliography https://www.erdosproblems.com/142
   - Also cited at Problem 142; 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 Asymptotic formula for the maximum size of a 3-term-AP-free subset of \(\{1,\dots,N\}\): 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 142 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 Asymptotic formula for the maximum size of a 3-term-AP-free subset of \(\{1,\dots,N\}\): 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 142. GitHub commit bb1c69dab14ad895ac1ccdb7b0c0e0a67c8eb3e1. FormalConjectures/ErdosProblems/142.lean:L67; theorem erdos_142.variants.three; commit bb1c69dab14ad895ac1ccdb7b0c0e0a67c8eb3e1 https://github.com/google-deepmind/formal-conjectures/blob/bb1c69dab14ad895ac1ccdb7b0c0e0a67c8eb3e1/FormalConjectures/ErdosProblems/142.lean#L67
   - 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 Asymptotic formula for the maximum size of a 3-term-AP-free subset of \(\{1,\dots,N\}\): Supplies the pinned formal declaration whose human-readable editorial statement is published here.