# P3030: Erdős's distinct distances diameter problem

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

## Problem

Erdős Problem 100: Let a finite set of points in the plane be called distance-separated if whenever two distances determined by pairs of its points are unequal, they differ by at least 1. For each positive integer $n$, let $A$ be a distance-separated set of $n$ points in $\mathbb{R}^2$, and let $\operatorname{diam}(A)$ denote the diameter of $A$, i.e., the maximum Euclidean distance between any two points of $A$. Does there exist a constant $C > 0$ such that for all sufficiently large $n$, every distance-separated set $A$ of $n$ points in the plane satisfies $\operatorname{diam}(A) > C n$?

### Context

This problem originates from Paul Erdős's collection of open problems in discrete geometry. It concerns the relationship between the combinatorial condition of separated distances and the geometric size of a point set. Related results include: Kanold proved a lower bound of order $n^{3/4}$; Guth and Katz improved this to order $n / \log n$ using their solution to the Erdős distinct distances problem; and Piepmeyer constructed a 9-point example with diameter less than 5. A stronger conjecture asserts that $\operatorname{diam}(A) \geq n - 1$ for all sufficiently large $n$.

### Problem setup

- **Definition (A finite set $A \subset \mathbb{R}^2$).** A finite set $A \subset \mathbb{R}^2$ is distance-separated if for all points $p_1, q_1, p_2, q_2 \in A$, whenever $\operatorname{dist}(p_1, q_1) \neq \operatorname{dist}(p_2, q_2)$, we have $|\operatorname{dist}(p_1, q_1) - \operatorname{dist}(p_2, q_2)| \geq 1$, where $\operatorname{dist}$ denotes the Euclidean distance.
- **Definition (The diameter of a set $A \subset \mathbb{R}^2$, denoted $\operatorname{diam}(A)$).** The diameter of a set $A \subset \mathbb{R}^2$, denoted $\operatorname{diam}(A)$, is the supremum of Euclidean distances between pairs of points in $A$, i.e., $\operatorname{diam}(A) = \sup\{\operatorname{dist}(p,q) : p, q \in A\}$.
- **Remark.** This problem originates from Paul Erdős's collection of open problems in discrete geometry. It concerns the relationship between the combinatorial condition of separated distances and the geometric size of a point set. Related results include: Kanold proved a lower bound of order $n^{3/4}$; Guth and Katz improved this to order $n / \log n$ using their solution to the Erdős distinct distances problem; and Piepmeyer constructed a 9-point example with diameter less than 5. A stronger conjecture asserts that $\operatorname{diam}(A) \geq n - 1$ for all sufficiently large $n$.

### What counts as a solution

- Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 100: Let a finite set of points in the plane be called distance-separated if whenever two distances determined by pairs of its points are unequal, they differ by at least 1. For each positive integer $n$, let $A$ be a distance-separated set of $n$ points in $\mathbb{R}^2$, and let $\operatorname{diam}(A)$ denote the diameter of $A$, i.e., the maximum Euclidean distance between any two points of $A$. Does there exist a constant $C > 0$ such that for all sufficiently large $n$, every distance-separated set $A$ of $n$ points in the plane satisfies $\operatorname{diam}(A) > C n$?

## Status

OPEN as of 2026-07-31. The maintained Erdős Problems database at commit 8138974387d9030542daabe67faaa33eff9356f8 lists Problem 100 as open. The unresolved remainder is the full displayed statement. Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 100: Let a finite set of points in the plane be called distance-separated if whenever two distances determined by pairs of its points are unequal, they differ by at least 1. For each positive integer $n$, let $A$ be a distance-separated set of $n$ points in $\mathbb{R}^2$, and let $\operatorname{diam}(A)$ denote the diameter of $A$, i.e., the maximum Euclidean distance between any two points of $A$. Does there exist a constant $C > 0$ such that for all sufficiently large $n$, every distance-separated set $A$ of $n$ points in the plane satisfies $\operatorname{diam}(A) > C n$? [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 100 as open. The unresolved remainder is the full displayed statement. Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 100: Let a finite set of points in the plane be called distance-separated if whenever two distances determined by pairs of its points are unequal, they differ by at least 1. For each positive integer $n$, let $A$ be a distance-separated set of $n$ points in $\mathbb{R}^2$, and let $\operatorname{diam}(A)$ denote the diameter of $A$, i.e., the maximum Euclidean distance between any two points of $A$. Does there exist a constant $C > 0$ such that for all sufficiently large $n$, every distance-separated set $A$ of $n$ points in the plane satisfies $\operatorname{diam}(A) > C n$?

OPEN as of 2026-07-31. The maintained Erdős Problems database at commit 8138974387d9030542daabe67faaa33eff9356f8 lists Problem 100 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 100: Let a finite set of points in the plane be called distance-separated if whenever two distances determined by pairs of its points are unequal, they differ by at least 1. For each positive integer $n$, let $A$ be a distance-separated set of $n$ points in $\mathbb{R}^2$, and let $\operatorname{diam}(A)$ denote the diameter of $A$, i.e., the maximum Euclidean distance between any two points of $A$. Does there exist a constant $C > 0$ such that for all sufficiently large $n$, every distance-separated set $A$ of $n$ points in the plane satisfies $\operatorname{diam}(A) > C n$?

### Background and intake notes

- Original intake status: OPEN as of 2026-07-31. The maintained Erdős Problems database at commit 8138974387d9030542daabe67faaa33eff9356f8 lists Problem 100 as open. The unresolved remainder is the full displayed statement.
- The maintained database entry for Erdős Problem 100 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 100: Let a finite set of points in the plane be called distance-separated if whenever two distances determined by pairs of its points are unequal, they differ by at least 1. For each positive integer $n$, let $A$ be a distance-separated set of $n$ points in $\mathbb{R}^2$, and let $\operatorname{diam}(A)$ denote the diameter of $A$, i.e., the maximum Euclidean distance between any two points of $A$. Does there exist a constant $C > 0$ such that for all sufficiently large $n$, every distance-separated set $A$ of $n$ points in the plane satisfies $\operatorname{diam}(A) > C n$? [1](#reference-1)

### Working on this

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