Erdős problem #1082 — wave 8d

Date of live-page audit and computation: 2026-07-28 (UTC).

Claim grades used below:

• (a) elementary-rigorous: proved here from elementary facts.
• (b) rigorous modulo named theorem: the reduction here is rigorous, with the explicitly named published theorem as input.
• (c) plausible/structural-unverified: heuristic or a claim not established here.
• (d) computational-only: exact finite computation, with reproducible code, but not promoted to a uniform theorem beyond the stated finite search space.

0. Mandatory live-page audit

I fetched the live page through the Bright Data browser API, not direct curl. I also opened its discussion thread and read all 21 comments.

Verbatim live statement

> Let \(A \subset \mathbb{R}^2\) be a set of \(n\) points with no three on a line. Does \(A\) determine at least \(\lfloor n/2\rfloor\) distinct distances? In fact, must there exist a single point from which there are at least \(\lfloor n/2\rfloor\) distinct distances?

Stop-condition audit

The page showed:

• status badge: FALSIFIABLE;
• 0 claimed proofs for this problem;
• Currently working on this problem: None;
• Interested in collaborating: None;
• last edited: 11 April 2026.

Thus neither stop condition applied.

Results and comments actually listed on the page

The page says:

1. Szemerédi proved the assertion with \(n/2\) replaced by \(n/3\). More generally, if no \(k\) points are collinear, some point determines \(\gg n/k\) pinned distances. His proof was unpublished but was included by Erdős in [Er75f].

2. The global question is stronger than problem #93; the pinned question is stronger than problem #982.

3. In \(\mathbb R^3\), the corresponding linear bound was proved by Altman for vertices of a convex polyhedron and by Szemerédi under the stronger hypothesis that no four points are coplanar.

4. The second, pinned-distance question is false. There is an 8-point configuration \(H_8\) in which every point sees exactly three distances. The page attributes the configuration to Harborth, its first literature appearance to Erdős–Fishburn, and its detailed study to Fishburn.

5. The discussion records the 2026 rediscovery/formalization of \(H_8\) by a DeepMind prover. Several commenters and the page explicitly emphasize that this refutes only the second clause and that the main global conjecture remains open.

6. The comments also contain a 42-point construction made of two concentric regular 21-gons. With

\[ r_0=\frac12\left(1-\sqrt{5-8\cos(2\pi/7)}\right) =0.4450418679\ldots, \]

a root of \(x^3-x^2-2x+1\), every point sees only 20 distances. Follow-up comments report Maple and Lean checks. Again, this concerns only the pinned clause. The site itself warns that comments are not verified, so none of these comment-only checks is used as a theorem below.

The relevant primary source checks were:

• Erdős, On Some Problems of Elementary and Combinatorial Geometry, Ann. Mat. Pura Appl. 103 (1975), 99–108. Pages 100–101 contain Szemerédi's perpendicular-bisector argument and both conjectures.
• Erdős–Fishburn, Maximum planar sets that determine \(k\) distances00153-N), Discrete Math. 160 (1996), 115–125.
• Shinohara, Uniqueness of maximum planar five-distance sets, Discrete Math. 308 (2008), 3048–3055.
• Wei, A proof of Erdős–Fishburn's conjecture for \(g(6)=13\), Electron. J. Combin. 19(4) (2012), P38. Theorem 19 states \(g(6)=13\).
• Fishburn, A remarkable eight-point planar configuration00134-0), Discrete Math. 252 (2002), 103–122.
• Bao–Yu, Constructions of Large \(m\)-Distance Sets on Triangular Lattice, revised 22 March 2026. It still describes the unrestricted planar \(7\)-distance maximum as unknown and treats 16 as a construction/conjectural maximum, not a theorem.
• Budianto, An Observation on 7-distance Set in Euclidean Plane, master's thesis (2022). It rules out a 17-point 7-distance set for most diameter-hull sizes but leaves sizes 9 through 13 only partially resolved.

I found no primary source claiming a solution of the no-three-collinear global question. That search miss is not itself evidence of openness; the live page is the authority for the status here.

1. Notation and an exact rounding refinement of Szemerédi's bound

Let

Proposition

(b) If \(A\subset\mathbb R^2\), \(|A|=n\ge2\), and no three points of \(A\) are collinear, then

This improves the commonly stated exact global rounding

\(\lceil(n-1)/3\rceil\) by one when \(n\equiv1\pmod3\). It does not improve the pinned bound, because its equality argument uses the set of global distance values.

Proof

For an apex \(x\in A\), partition \(A\setminus\{x\}\) into classes of equal distance from \(x\). If their sizes are \(a_{x,1},\ldots,a_{x,s_x}\), then \(s_x\le D(A)\) and

Let \(I\) count isosceles triangles with a distinguished apex, so an equilateral triangle is counted three times. Then

For a fixed unordered base \(\{u,v\}\), every possible apex lies on the perpendicular bisector of \(uv\). Since no three points of \(A\) are collinear, this line contains at most two points of \(A\). Hence

This part is (a).

For integers \(m,t\), let

Convexity shows that the minimum uses \(t\) parts as equally sized as possible. Suppose

Except when \(n\equiv1\pmod3\), direct division with remainder gives

so summing over the \(n\) apices contradicts (1).

It remains to handle \(n=3k+1\). The only case not already giving a strict contradiction is \(D(A)=k\). Here \(n-1=3k\), and

Consequently equality must hold throughout: every point realizes exactly \(k\) pinned distance classes, and every class has exactly three points. Since there are only \(k\) global distances, every point realizes every global distance exactly three times. In particular, the diameter graph of \(A\) is 3-regular and has \(3n/2\) edges.

The planar diameter-graph theorem says that a diameter graph on \(n\) planar points has at most \(n\) edges. One route is the straight-line Hopf–Pannwitz thrackle theorem; equivalently, Wei's Lemma 5 states the stronger cycle structure from which the edge bound follows. Thus \(3n/2\le n\), a contradiction. This final input is the named theorem responsible for grade (b). Therefore (2) is impossible and the proposition follows.

The arithmetic equality/strict-inequality split is independently checked for \(2\le n\le300\) by the verifier. No finite cutoff is used in the proof.

2. Exact global answer for every \(n\le15\)

Define

The published exact values through six distances are

Here \(g(0)=1\) is elementary; Erdős–Fishburn establish the values through \(5\), Shinohara supplies uniqueness at \(5\), and Wei proves \(g(6)=13\).

Theorem

(b) For every \(1\le n\le15\),

Lower bound

If a set of \(n\) points violated the desired bound, it would have at most

distances. The following implications from (3) are exact:

| \(n\) | \(q\) | maximum size with at most \(q\) distances | conclusion |

|---:|---:|---:|:---|

| 2–3 | 0 | 1 | impossible |

| 4–5 | 1 | 3 | impossible |

| 6–7 | 2 | 5 | impossible |

| 8–9 | 3 | 7 | impossible |

| 10–11 | 4 | 9 | impossible |

| 12 | 5 | 12 | needs the uniqueness argument below |

| 13 | 5 | 12 | impossible |

| 14–15 | 6 | 13 | impossible |

For \(n=12\), a violating set would have exactly five distances and would attain \(g(5)=12\). Shinohara's theorem says that every such set is similar to the unique maximum configuration. One exact triangular-lattice model, in axial coordinates, is

For the lattice basis \((1,0),(1/2,\sqrt3/2)\), squared distance is

The verifier recomputes

Thus \(E\) is a 12-point five-distance set, so uniqueness identifies its similarity class with every extremizer. But \((0,0),(1,0),(2,0)\in E\) are collinear. Similarities preserve collinearity, ruling out the exceptional case.

Upper bound

(a) The vertices of a regular \(n\)-gon have no three collinear, because a line meets its circumcircle in at most two points. Their chord lengths are indexed by cyclic step

and are strictly distinct in that range. They therefore determine exactly

\(\lfloor n/2\rfloor\) distances. This completes the equality.

The verifier treats the published values in (3) and Shinohara's uniqueness as named theorem inputs; it independently checks all finite implications and all coordinate arithmetic.

3. Exact computation against the standard 16-point obstruction

The first unresolved order after the preceding theorem is \(n=16\): one must rule out a no-three-collinear 16-point set with at most seven distances.

The standard unrestricted 16-point seven-distance construction lies in the triangular lattice. Start with the radius-two lattice hexagon

of 19 points and delete the three alternating corners

(a) Direct exact calculation gives the seven squared distances

It also has 42 collinear triples, so it is inadmissible for problem #1082.

I tested not just this 16-point set, but the entire triangular lattice with that distance palette.

Exact finite result

(d) If \(X\) is a subset of the triangular lattice, no three points of \(X\) are collinear, and

then

The bound is attained, for example, by

Its exact squared-distance multiplicities are

whose counts sum to \(\binom92=36\), and an integer-determinant check finds no collinear triple.

Why the computation is exhaustive

Translate one point of \(X\) to the origin. Every other point must then be in

Since

this is an explicitly finite set. The verifier finds \(|V|=54\).

It builds a compatibility graph on \(V\):

1. \(u,v\) are pair-compatible only if \(Q(u-v)\in S_7\);

2. they are also made incompatible if \(0,u,v\) are collinear;

3. when two nonzero points are selected, all possible third points on their line are deleted.

The search is a complete include/exclude maximum-clique recursion. At every node it greedily partitions the remaining compatibility graph into independent color classes. A clique uses at most one vertex per class, so the number of colors is a certified upper bound even after the three-point constraints are relaxed. The search visits 749 recursive nodes and proves that at most eight nonzero vectors can accompany the origin. All norms and determinants are integers.

For comparison, the same code gives the following exact table for nested palettes consisting of the first \(k\) positive triangular-lattice norms:

| \(k\) | palette | shell vectors | exact maximum with no three collinear |

|---:|:---|---:|---:|

| 1 | \(1\) | 6 | 3 |

| 2 | \(1,3\) | 12 | 4 |

| 3 | \(1,3,4\) | 18 | 6 |

| 4 | \(1,3,4,7\) | 30 | 6 |

| 5 | \(1,3,4,7,9\) | 36 | 7 |

| 6 | \(1,3,4,7,9,12\) | 42 | 7 |

| 7 | \(1,3,4,7,9,12,13\) | 54 | 9 |

| 8 | \(1,3,4,7,9,12,13,16\) | 60 | 10 |

This table is deliberately labeled (d). It says nothing about arbitrary seven-element distance palettes, arbitrary scaled sublattices, or off-lattice configurations.

4. Reproduction

The standalone verifier is:

Run:

python runs/erdos1082_wave8d_reverify.py

It uses only the Python standard library. On this VM it completed in 0.10 seconds with peak RSS 11,924 KB and ended with:

ALL EXACT COMPUTATIONAL CHECKS PASSED

The source itself documents the branch invariant and the coloring upper bound. It also clearly identifies which facts are external named-theorem inputs.

5. Exact remaining wall

The next missing statement is now particularly sharp:

Equivalently, if

then the required \(n=16\) lemma is \(g_{\mathrm{no3}}(7)\le15\).

The unrestricted value \(g(7)\) is itself not known in the checked literature. The known 16-point construction and the first-seven-norm lattice family do not threaten (4); the exact computation above leaves a gap of seven points. But it cannot rule out another palette or a non-lattice realization.

A naive semialgebraic search is not a credible next computation. With 16 labeled points there are 120 pairs, each assigned one of seven squared-distance variables, before imposing Euclidean realizability and 560 nonzero collinearity determinants. The raw color assignment space is \(7^{120}\approx10^{101.4}\). Even at an unrealistic \(10^6\) assignments per second this is about \(3\times10^{87}\) years. Diameter-graph and association-scheme reductions are therefore prerequisites, not optional optimization. The 2022 thesis's unresolved diameter-hull cases 9–13 identify one concrete place where such new structure is still missing.

Thus this run does not close the uniform problem. It supplies a proof-level finite frontier through \(n=15\), a small exact rounding refinement of the global lower bound, and a certified elimination of the standard \(n=16\) triangular-lattice palette.

PARTIAL: proved the conjectured exact value for all n<=15 (modulo the published g(k) classifications), proved D(A)>=ceil(n/3) modulo the planar diameter-graph theorem, and exactly ruled out the standard seven-norm triangular-lattice family at n=16 by showing its no-three-collinear maximum is 9.