Skip to content

Erdős Problem #661

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: geometry, distances.

Read this status correctly

The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.

The question in plain language

Imagine two teams of points, each consisting of \(n\) different positions in the plane. Count only the distances between a member of the first team and a member of the second. Can these cross distances take dramatically fewer different values than ordinary distances among a comparable number of points?

In Erdős Problem #661, the question is whether for every sufficiently large \(n\) there are two labelled planar point sets

\[ X=\{x_1,\ldots,x_n\},\qquad Y=\{y_1,\ldots,y_n\} \]

such that

\[ D(X,Y)=\bigl|\{\lVert x_i-y_j\rVert:1\leq i,j\leq n\}\bigr| =o\left(\frac n{\sqrt{\log n}}\right). \]

For all the concrete examples and the minimization comparison below, we require the two sets to be disjoint, giving \(2n\) different points. The maintained statement does not explicitly specify whether labels across the two sets may coincide. This is an additional historical source-fidelity question, not a new theorem assumption silently imposed on Erdős.

The symbol \(o\) is stronger than \(O\): it asks that the ratio of the number of cross distances to \(n/\sqrt{\log n}\) tend to zero, not merely remain bounded.

The maintained two-dimensional question remains OPEN.

A small example

Put four points equally spaced around the unit circle, and four around a concentric circle of radius \(2\):

\[ x_i=(\cos(2\pi i/4),\sin(2\pi i/4)), \]
\[ y_j=2(\cos(2\pi j/4),\sin(2\pi j/4)), \qquad 0\leq i,j<4. \]

The two sets are disjoint. A direct calculation gives

\[ \lVert x_i-y_j\rVert^2 =1+4-4\cos\left(\frac{2\pi(i-j)}4\right). \]

The cosine takes only the three values \(1,0,-1\). Thus the 16 cross pairs determine only

\[ D(X,Y)=3,\qquad \text{distances }\{1,\sqrt5,3\}. \]

For arbitrary \(n\), two concentric regular \(n\) gons of different radii similarly determine exactly \(\lfloor n/2\rfloor+1\) different cross distances. That is linear in \(n\). It demonstrates the benefit of symmetry but does not achieve the target \(o(n/\sqrt{\log n})\).

What is known

Why bipartite distances are different. Within-team distances do not count in \(D(X,Y)\). This makes it possible to reuse many cross lengths even when the two separate teams each have complex geometry. The cross-distance matrix has \(n^2\) entries, but many can coincide.

Define

\[ F(2n)=\min_{\substack{|X|=|Y|=n\\X\cap Y=\varnothing}} D(X,Y), \quad f(2n)=\min_{|Z|=2n} \bigl|\{\lVert z-z'\rVert:z\ne z'\in Z\}\bigr|. \]

Under the natural interpretation requiring \(2n\) distinct points, if we start with a configuration \(Z\) that minimizes the usual all-pairs distance count and divide its \(2n\) points into two groups of size \(n\), its cross distances are a subset of its complete distance set. Therefore

\[ F(2n)\leq f(2n). \]

The accompanying question is whether the ratio \(F(2n)/f(2n)\) actually tends to zero. Merely proving \(F\leq f\) tells us nothing about that asymptotic improvement.

A 2026 correction in the maintained statement history fixed a reversed comparison: the meaningful question is \(F=o(f)\), not \(f=o(F)\).

A higher-dimensional construction that does not transfer. In four-dimensional Euclidean space, choose \(n\) points on the unit circle inside the coordinate plane spanned by the first two axes and \(n\) on the circle inside the orthogonal plane spanned by the remaining axes. Every first-team vector is orthogonal to every second-team vector, so

\[ \lVert x_i-y_j\rVert^2 =\lVert x_i\rVert^2+\lVert y_j\rVert^2=2. \]

All \(n^2\) cross distances are exactly \(\sqrt2\). This is the Lenz construction mentioned by the catalogue. But two mutually orthogonal two-dimensional linear subspaces require four ambient dimensions. It is not a planar solution and cannot be imported without a new argument.

The scale \(n/\sqrt{\log n}\). Ordinary two-dimensional lattice point sets provide relatively few distinct distances, governed by representation counts for quadratic forms such as \(u^2+v^2\). Splitting a suitably sized finite lattice subset into two groups gives some bipartite configurations with at most \(O(n/\sqrt{\log n})\) cross distances, based on published number-theoretic counting estimates. That explains why the question asks for a little-o improvement. The lattice estimate alone does not deliver one.

GCL's current state

The original authenticated RESULT/1 source return has historical disposition PARTIAL. This status and the original research exceptions are preserved, not silently converted into a theorem verdict. The maintained Erdős source and source-specific mathematical definitions were reviewed, and this article is editorially reviewed as a source-exception-annotated explanation under EC-BULK-005-R10, effective only after the exact-hash protected admission merges.

Source interpretation and unresolved mathematical qualification: Planar cross-distance teams, their disjointness and F(2n)/f(2n) little-o are distinct from a four-dimensional fixture.

The explanation is accepted for publication of established background, examples, and explicitly attributed current claims. It does not establish or formally certify the disputed original theorem, external model-assisted proof, historical interpretation, or any unreplayed Lean kernel file. Original source-fidelity and proof-review research holds remain.

What remains

A useful bounded investigation would choose one explicit pair of planar point-set families and count their distinct cross-distance values using exact arithmetic. The required report must demonstrate that both teams contain \(n\) distinct points, verify that they are disjoint, and give an actual asymptotic ratio.

A result of the form

\[ D(X_n,Y_n)\leq C\frac n{\sqrt{\log n}} \]

for a fixed \(C>0\) is insufficient. A successful affirmative construction must instead give

\[ \frac{D(X_n,Y_n)\sqrt{\log n}}{n}\longrightarrow0. \]

A negative result, in turn, would require a universal lower bound incompatible with that convergence. Finite computations or geometrically elegant higher-dimensional arrangements cannot substitute for a planar asymptotic argument.

The documentary task is to confirm the original [Er97e] reference and the attribution to Lenz, preserving the maintained 2026 correction. Editorial source review, protected publication, browser MathJax verification and exact-hash V2 admission are separate obligations.

Sources and claim boundaries

  • T. F. Bloom, Erdős Problem #661: maintained OPEN statement and the bipartite variant.
  • History of #661: corrected \(F=o(f)\) comparison in January 2026.
  • GCL authenticated original issue return: source identity, exact geometry examples and research boundary.
  • Lenz's four-dimensional orthogonal-circle construction: elementary argument reproduced here; original primary attribution not directly inspected.
  • P. Erdős, Some of my favourite unsolved problems, Math. Japon. (1997) [Er97e]: historical passage not independently read.

Authority boundary: verified elementary finite and four-dimensional constructions, a corrected asymptotic distinction and honest statement of an open planar problem. No o-bound construction, full primary-source lock, novel GCL theorem, Lean certification, protected publication, deployed mathematical rendering or editorial admission.

Qualified editorial critical review: R10 source-exception dossier. The source-semantic exception is visible and its original research hold remains. Publication classification: REVIEWED EXPLANATORY ARTICLE WITH UNRESOLVED SOURCE/PROOF QUALIFICATIONS. Independent theorem proof or Lean certification: NOT CLAIMED.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1932 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: STATEMENT_CAPTURE_REQUIRED.
  • Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
  • External mathematical status: consult current problem page and its dated bibliography.

Back to catalogue · Compendium introduction