# P2988: The limit of the minimum overlap quotient

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

## Problem

Erdős Problem 36: For each positive integer $n$, consider all partitions of $\{1, 2, \dots, 2n\}$ into two disjoint $n$-element subsets $A$ and $B$. For integers $a \in A$ and $b \in B$, define the overlap of $A$ and $B$ at difference $k \in \mathbb{Z}$ to be the number of pairs $(a,b)$ with $a - b = k$. Define the maximum overlap $M(A,B)$ to be the largest overlap over all integer differences $k$. Define $M(n)$ to be the minimum of $M(A,B)$ over all such partitions $(A,B)$. Define the minimum overlap quotient by
\[Q(n) = \frac{M(n)}{n}.\]
Does the limit $\displaystyle\lim_{n \to \infty} Q(n)$ exist, and if so, what is its exact value?

### Context

This is Erdős Problem 36, also known as the minimum overlap problem. The problem concerns the asymptotic behavior of the minimum possible maximum overlap when splitting the first $2n$ integers into two equal parts. The limit's existence has been established, with the best known bounds being approximately $0.379005 < \liminf Q(n) \leq \limsup Q(n) \leq 0.3809268534330870$, but the exact value remains unknown.

### Problem setup

- **Definition (For finite sets $A, B \subset \mathbb{Z}$ and $k \in \mathbb{Z}$, the overlap $\operatorname{Overlap}(A,B,k)$).** For finite sets $A, B \subset \mathbb{Z}$ and $k \in \mathbb{Z}$, the overlap $\operatorname{Overlap}(A,B,k)$ is the number of ordered pairs $(a,b) \in A \times B$ such that $a - b = k$.
- **Definition (The maximum overlap $M(A,B)$).** The maximum overlap $M(A,B)$ is $\sup_{k \in \mathbb{Z}} \operatorname{Overlap}(A,B,k)$, which equals the maximum since only finitely many differences occur.
- **Definition (For $n \geq 1$, $M(n)$).** For $n \geq 1$, $M(n)$ is the minimum value of $M(A,B)$ over all partitions of $\{1,2,\dots,2n\}$ into two disjoint $n$-element subsets $A$ and $B$.
- **Definition (The minimum overlap quotient).** The minimum overlap quotient is $Q(n) = M(n)/n$.
- **Remark.** This is Erdős Problem 36, also known as the minimum overlap problem. The problem concerns the asymptotic behavior of the minimum possible maximum overlap when splitting the first $2n$ integers into two equal parts. The limit's existence has been established, with the best known bounds being approximately $0.379005 < \liminf Q(n) \leq \limsup Q(n) \leq 0.3809268534330870$, but the exact value remains unknown.

### What counts as a solution

- Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 36: For each positive integer $n$, consider all partitions of $\{1, 2, \dots, 2n\}$ into two disjoint $n$-element subsets $A$ and $B$. For integers $a \in A$ and $b \in B$, define the overlap of $A$ and $B$ at difference $k \in \mathbb{Z}$ to be the number of pairs $(a,b)$ with $a - b = k$. Define the maximum overlap $M(A,B)$ to be the largest overlap over all integer differences $k$. Define $M(n)$ to be the minimum of $M(A,B)$ over all such partitions $(A,B)$. Define the minimum overlap quotient by
\[Q(n) = \frac{M(n)}{n}.\]
Does the limit $\displaystyle\lim_{n \to \infty} Q(n)$ exist, and if so, what is its exact value?

## Status

OPEN as of 2026-07-31. The maintained Erdős Problems database at commit 8138974387d9030542daabe67faaa33eff9356f8 lists Problem 36 as open. The unresolved remainder is the full displayed statement. Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 36: For each positive integer $n$, consider all partitions of $\{1, 2, \dots, 2n\}$ into two disjoint $n$-element subsets $A$ and $B$. For integers $a \in A$ and $b \in B$, define the overlap of $A$ and $B$ at difference $k \in \mathbb{Z}$ to be the number of pairs $(a,b)$ with $a - b = k$. Define the maximum overlap $M(A,B)$ to be the largest overlap over all integer differences $k$. Define $M(n)$ to be the minimum of $M(A,B)$ over all such partitions $(A,B)$. Define the minimum overlap quotient by
\[Q(n) = \frac{M(n)}{n}.\]
Does the limit $\displaystyle\lim_{n \to \infty} Q(n)$ exist, and if so, what is its exact value? [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 36 as open. The unresolved remainder is the full displayed statement. Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 36: For each positive integer $n$, consider all partitions of $\{1, 2, \dots, 2n\}$ into two disjoint $n$-element subsets $A$ and $B$. For integers $a \in A$ and $b \in B$, define the overlap of $A$ and $B$ at difference $k \in \mathbb{Z}$ to be the number of pairs $(a,b)$ with $a - b = k$. Define the maximum overlap $M(A,B)$ to be the largest overlap over all integer differences $k$. Define $M(n)$ to be the minimum of $M(A,B)$ over all such partitions $(A,B)$. Define the minimum overlap quotient by
\[Q(n) = \frac{M(n)}{n}.\]
Does the limit $\displaystyle\lim_{n \to \infty} Q(n)$ exist, and if so, what is its exact value?

OPEN as of 2026-07-31. The maintained Erdős Problems database at commit 8138974387d9030542daabe67faaa33eff9356f8 lists Problem 36 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 36: For each positive integer $n$, consider all partitions of $\{1, 2, \dots, 2n\}$ into two disjoint $n$-element subsets $A$ and $B$. For integers $a \in A$ and $b \in B$, define the overlap of $A$ and $B$ at difference $k \in \mathbb{Z}$ to be the number of pairs $(a,b)$ with $a - b = k$. Define the maximum overlap $M(A,B)$ to be the largest overlap over all integer differences $k$. Define $M(n)$ to be the minimum of $M(A,B)$ over all such partitions $(A,B)$. Define the minimum overlap quotient by
\[Q(n) = \frac{M(n)}{n}.\]
Does the limit $\displaystyle\lim_{n \to \infty} Q(n)$ exist, and if so, what is its exact value?

### Background and intake notes

- Original intake status: OPEN as of 2026-07-31. The maintained Erdős Problems database at commit 8138974387d9030542daabe67faaa33eff9356f8 lists Problem 36 as open. The unresolved remainder is the full displayed statement.
- The maintained database entry for Erdős Problem 36 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 36: For each positive integer $n$, consider all partitions of $\{1, 2, \dots, 2n\}$ into two disjoint $n$-element subsets $A$ and $B$. For integers $a \in A$ and $b \in B$, define the overlap of $A$ and $B$ at difference $k \in \mathbb{Z}$ to be the number of pairs $(a,b)$ with $a - b = k$. Define the maximum overlap $M(A,B)$ to be the largest overlap over all integer differences $k$. Define $M(n)$ to be the minimum of $M(A,B)$ over all such partitions $(A,B)$. Define the minimum overlap quotient by \[Q(n) = \frac{M(n)}{n}.\] Does the limit $\displaystyle\lim_{n \to \infty} Q(n)$ exist, and if so, what is its exact value? [1](#reference-1)

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `erdos-problem-36`, 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 36, maintained status record. Erdős Problems record 36, checked 2026-08-01. Problem 36; status field and linked bibliography https://www.erdosproblems.com/36
   - Also cited at Problem 36; 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 The limit of the minimum overlap quotient: 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 36 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 The limit of the minimum overlap quotient: 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 36. GitHub commit bb1c69dab14ad895ac1ccdb7b0c0e0a67c8eb3e1. FormalConjectures/ErdosProblems/36.lean:L257; theorem erdos_36; commit bb1c69dab14ad895ac1ccdb7b0c0e0a67c8eb3e1 https://github.com/google-deepmind/formal-conjectures/blob/bb1c69dab14ad895ac1ccdb7b0c0e0a67c8eb3e1/FormalConjectures/ErdosProblems/36.lean#L257
   - 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 The limit of the minimum overlap quotient: Supplies the pinned formal declaration whose human-readable editorial statement is published here.