Erdoes #661 - working report - Erdős Problem a Day

Erdős problem 661 — wave w007

Access/search date: 2026-07-28 UTC.

Claim labels

(a) elementary-rigorous: proved here from definitions.
(b) rigorous-modulo-named-theorem: the deduction is rigorous assuming the cited theorem.
(c) plausible/structural-unverified: interpretation or a search miss, not a theorem.
(d) computational-only: exact integer computation in the stated finite search space.

No line labelled (c) or (d) is used as a theorem about unrestricted planar configurations.

0. Mandatory live-page gate

(a; direct live-page observation) I fetched the live page through the Bright Data browser path, not datacenter curl: Erdős problem 661. At access time it said OPEN - $50, 0 claimed proofs for this problem, Currently working on this problem: None, and Interested in collaborating: None. The page said it was last edited 11 January 2026. Thus none of the mandatory stop conditions fired.

Verbatim current statement

Are there, for all large $n$, some points $x_1,\ldots,x_n,y_1,\ldots,y_n\in \mathbb{R}^2$ such that the number of distinct distances $d(x_i,y_j)$ is \[o\left(\frac{n}{\sqrt{\log n}}\right)?\]

(a; direct live-page observation) The page's listed remarks are:

The analogous question can be asked in $\mathbb R^3$.
In $\mathbb R^4$, Lenz's two orthogonal-circle construction makes every cross-distance equal to $1$.
If $F(2n)$ is the minimum cross-distance count and $f(2n)$ is the usual minimum distance count for $2n$ planar points, the page also asks whether $F=o(f)$.
It links problem 89.

(a; direct comment-thread observation) The sole comment, by Adenwalla on 7 January 2026, asks, “Shouldn't the last line be $F=o(f)$?” The thread says the page was updated to address it. It contains no claimed result.

(a; bibliographic transcription) Clicking all four live-page citation widgets returned:

[ErPa90] P. Erdős and J. Pach, Variations on the theme of repeated distances, Combinatorica 10 (1990), 261–269, MR 1092543.
[Er92e] P. Erdős, Some Unsolved problems in Geometry, Number Theory and Combinatorics, Eureka (1992), 44–48.
[Er97e] P. Erdős, Some of my favourite unsolved problems, Math. Japon. (1997), 527–537, MR 1487304.
[Er97f] P. Erdős, Some unsolved problems, in Combinatorics, Geometry and Probability (1997), 1–10, MR 1476428.

1. What the primary literature currently gives

Write

D(P,Q)=|\{|p-q|:p\in P,\ q\in Q\}|,\qquad D(m,n)=\min_{\substack{|P|=m\\|Q|=n}}D(P,Q).

(a; notation) Under the page's notation, the equal-size case is $F(2n)=D(n,n)$.

(a; source verification) I inspected the scan of [Er97f], internal page 6, Problem 18, in Combinatorics, Geometry and Probability. It defines the same $F(2n)$, asks how $f/F$ behaves in dimensions 2 and 3, and explicitly asks whether $f/F\to\infty$ or remains bounded. This verifies that the cited source exists and contains the problem, rather than merely sharing keywords.

(b; Mathialagan 2021, Theorem 3 and Corollary 8) The directly relevant modern paper is Surya Mathialagan, On Bipartite Distinct Distances in the Plane, Electronic Journal of Combinatorics 28(4) (2021), P4.33, DOI 10.37236/9687; the matching preprint is arXiv:1912.01883. It proves, for $n^{1/3}\le m\le n$,

D(m,n)=\Omega\!\left(\frac{\sqrt{mn}}{\log n}\right),

and records the ordinary lattice upper bound

D(m,n)=O\!\left(\frac{n}{\sqrt{\log n}}\right)

in the large-$m$ range. Consequently, at $m=n$,

\boxed{\quad \Omega\!\left(\frac{n}{\log n}\right) \le D(n,n)\le O\!\left(\frac{n}{\sqrt{\log n}}\right). \quad}

The paper's Question 5 says the asymptotic value in the range $n^{1/3}\le m\le n$ remains open. This is exactly the factor-$\sqrt{\log n}$ gap in problem 661.

(b; Mathialagan 2021, Remark 17) If all points of one equal-size part lie on a line, then $D(P,Q)=\Omega(n)$. A one-line/circle-grid extrapolation therefore cannot meet even the known lattice upper order, let alone little-$o$ of it.

(b; Pach–de Zeeuw 2017) For points constrained to two fixed irreducible bounded-degree algebraic curves, the theorem in arXiv:1308.0177 gives

\Omega\!\bigl(\min(m^{2/3}n^{2/3},m^2,n^2)\bigr)

cross-distances unless the curves are parallel lines, orthogonal lines, or concentric circles. Thus a solution cannot come from two generic fixed-degree curves.

(a/b) The exceptional pairs do not yield the requested scale either. The line cases are covered by Mathialagan's $\Omega(n)$ theorem above. For concentric circles, fix $x$ on the first circle: any circle centered at $x$ meets the second circle in at most two points, so the $n$ points of the second part already give at least $n/2$ distances from $x$.

(c; search report, not an absence theorem) Exact-title, exact-formula, arXiv, journal, citation-trail, and author-publication searches found no post-2021 unrestricted equal-size upper bound improving $O(n/\sqrt{\log n})$. I did find later work on curve-restricted bipartite distances, but it does not provide a construction for the unrestricted equal-size problem. A literature search cannot prove that no unindexed result exists.

2. An exact disjoint construction and reduction

For an integer $m\ge1$, put $n=m^2$ and define two disjoint $n$-point sets

X_m=\{(2i,2j):0\le i,j<m\},\qquad Y_m=\{(2k+1,2\ell+1):0\le k,\ell<m\}.

Proposition 1: exact distance set

(a) The squared cross-distance set is exactly

\mathcal H_m = \{a^2+b^2:\ a,b\in\{1,3,\ldots,2m-1\}\}. \tag{1}

Proof. For $x=(2i,2j)\in X_m$ and $y=(2k+1,2\ell+1)\in Y_m$,

|x-y|^2=(2(i-k)-1)^2+(2(j-\ell)-1)^2.

As $i-k$ ranges from $-(m-1)$ through $m-1$, the absolute values of $2(i-k)-1$ are precisely $1,3,\ldots,2m-1$. The same holds in the second coordinate, proving both inclusions in (1). $\square$

(a) This reduces an apparent $n^2=m^4$ pair enumeration to $m^2=n$ exact integer sums.

Proposition 2: this family cannot solve problem 661

(b; Landau–Ramanujan theorem) Let

B(T)=|\{r\le T:r=u^2+v^2\text{ for some }u,v\in\mathbb Z\}|.

The Landau–Ramanujan theorem says

B(T)\sim K\,\frac{T}{\sqrt{\log T}}

for a fixed $K>0$. Then

|\mathcal H_m| =\Theta\!\left(\frac{m^2}{\sqrt{\log m}}\right) =\Theta\!\left(\frac{n}{\sqrt{\log n}}\right). \tag{2}

Proof.

(b), upper bound. Every member of $\mathcal H_m$ is a sum of two squares at most

$2(2m-1)^2<8m^2$. Hence \[ |\mathcal H_m|\le B(8m^2) =O(m^2/\sqrt{\log m}). \]

(a), parity identity. An even integer $N$ is a sum of two squares if and only if $N/2$ is. One direction uses

$2(c^2+d^2)=(c+d)^2+(c-d)^2$; the reverse direction applies the same rotation after observing that a representation of even $N$ has coordinates of the same parity. Therefore the number of odd represented integers at most $T$ is exactly $B(T)-B(T/2)$.

(b), odd represented integers. Landau–Ramanujan now gives

\[ B(T)-B(T/2)\sim \frac K2\,\frac{T}{\sqrt{\log T}}. \]

(a), injection into $\mathcal H_m$. Let $M=c^2+d^2$ be odd and

$M\le(2m-1)^2/2$. Then $c,d$ have opposite parity, \[ 2M=(c+d)^2+(c-d)^2, \] and both $|c+d|$ and $|c-d|$ are positive odd integers at most $\sqrt{2M}\le2m-1$. Thus $M\mapsto2M$ injects all such odd represented integers into $\mathcal H_m$, yielding the matching lower bound in (2).

$\square$

(a) Taking subsets of the next larger $X_m,Y_m$ extends the upper bound to arbitrary $n$, but (2) shows that the full periodic half-shift construction has the same asymptotic order as the classical lattice construction. It does not give the requested little-$o$.

3. Exact finite search in a larger arithmetic-lattice family

Search space

Let

Q_{a,b,c}(u,v)=au^2+buv+cv^2

with

1\le a\le c\le8,\quad |b|\le a,\quad b^2<4ac,\quad \gcd(a,b,c)=1. \tag{3}

(d) There are exactly 212 triples satisfying (3), as independently enumerated by the checker.

(a) Every form in (3) is a Euclidean squared norm. One realization is

v_1=(\sqrt a,0),\qquad v_2=\left(\frac{b}{2\sqrt a}, \sqrt{c-\frac{b^2}{4a}}\right),

for which

|uv_1+vv_2|^2=Q_{a,b,c}(u,v).

For each form, take the coefficient window

P_m=\{iv_1+jv_2:0\le i,j<m\}

and compare it with

P_m+\frac{hv_1+kv_2}{2},\qquad(h,k)\in\{0,1\}^2.

(a) The zero shift is retained as a control; its literal cross-distance set includes zero. The three nonzero shifts give disjoint sets.

(a) Four times the exact squared cross-distance set is

\mathcal S_m(a,b,c;h,k)= \{Q_{a,b,c}(2r-h,2s-k):-(m-1)\le r,s\le m-1\}. \tag{4}

Thus all comparisons can be done with integers, without numerical geometry or tolerance choices.

Exhaustive result

(d) Exhausting the 212 forms and four shifts—848 candidates—found that for every integer

4\le m\le64,

the unique minimum in this explicitly finite family is

\[ (a,b,c;h,k)=(1,0,1;1,1), \]

namely the construction in Proposition 1.

(d) Selected exact minima are:

| $m$ | $n=m^2$ | minimum in the 848-candidate family | |---:|---:|---:| | 4 | 16 | 9 | | 8 | 64 | 32 | | 16 | 256 | 109 | | 32 | 1024 | 398 | | 64 | 4096 | 1464 |

(d; scope) This is a sharp statement only for (3), the four half-period shifts, square coefficient windows, and $4\le m\le64$. It says nothing by itself about forms of larger height, other rational shifts, non-window subsets, non-arithmetic lattices, or arbitrary planar sets.

Larger exact counts for the winning construction

(d) The following table was recomputed from (1). The “co-located grid” column is only an arithmetic reference $\{a^2+b^2:0\le a,b<m\}$, including zero; it is not asserted to be the optimal disjoint construction.

| $m$ | $n=m^2$ | co-located grid | $|\mathcal H_m|$ | ratio | |---:|---:|---:|---:|---:| | 4 | 16 | 10 | 9 | 0.900000000 | | 8 | 64 | 34 | 32 | 0.941176471 | | 16 | 256 | 120 | 109 | 0.908333333 | | 32 | 1024 | 431 | 398 | 0.923433875 | | 64 | 4096 | 1576 | 1464 | 0.928934010 | | 128 | 16384 | 5839 | 5473 | 0.937318034 | | 256 | 65536 | 21860 | 20604 | 0.942543458 | | 512 | 262144 | 82490 | 78229 | 0.948345254 | | 1024 | 1048576 | 313260 | 298694 | 0.953501883 |

(d) For $m=4,64,1024$, the verifier also checks SHA-256 digests of the complete sorted distance sets, not just their cardinalities. For $m\le6$, it independently enumerates every point pair and checks equality with both (1) and (4).

4. What exactly remains

(b) Three standard regimes now have explicit obstructions:

A collinear part forces $\Omega(n)$ cross-distances (Mathialagan).
Two generic fixed bounded-degree curves force $\Omega(n^{4/3})$ cross-distances (Pach–de Zeeuw).
The most symmetric disjoint square-lattice half-shift has

$\Theta(n/\sqrt{\log n})$ cross-distances (Proposition 2).

(c; structural diagnosis) These results point away from one-dimensional/circle-grid constructions and away from any fixed periodic parity trick. They do not exclude a construction whose lattice/form/coset varies with $n$, a sparse non-window subset, or a genuinely nonperiodic two-dimensional configuration.

(c; exact missing construction/lemma) The arithmetic-lattice route would require one of the following genuinely new inputs:

an explicit sequence of normalized forms/cosets/windows for which the number of represented cross-norms is

$o(n/\sqrt{\log n})$; or

a uniform lower theorem for inhomogeneous binary quadratic forms/lattice cosets with discriminant and local data allowed to grow with $n$, proving that no such sequence works.

Classical Landau–Ramanujan/Bernays asymptotics are for a fixed form and do not supply that uniformity. A fixed-form asymptotic constant, however small, cannot establish little-$o$.

(d; measured computational cost) The completed finite scan makes

848(2\cdot64-1)^2=13{,}677{,}392

exact candidate-vector evaluations and took 5.9 seconds with about 63 MB peak RSS on this VM. Naively extending both coefficient bound and window size costs $\Theta(A^3m^2)$ hash insertions. At $A=100,m=1000$, this is on the order of $10^{12}$–$10^{13}$ insertions, realistically hundreds of core-hours even in optimized compiled code; it was not run. More importantly, any finite cutoff still lacks the uniformity step needed for problem 661.

5. Reproduction

Standalone checker:

python3 runs/erdos661_wavew007_reverify.py

Expected final output:

forms=212, shifts=4, candidates=848
PASS: unique minimizer for every 4 <= m <= 64 is
      Q(u,v)=u^2+v^2 with shift (v1+v2)/2
anchor minima: {4: 9, 8: 32, 16: 109, 32: 398, 64: 1464}

ALL CHECKS PASSED

The core exact enumeration used by the standalone checker is:

def quadratic(form, u, v):
    a, b, c = form
    return a*u*u + b*u*v + c*v*v

def distance_set(m, form, shift):
    h, k = shift
    R = range(-(m-1), m)
    return {
        quadratic(form, 2*r-h, 2*s-k)
        for r in R for s in R
    }

def odd_square_sums(m):
    O = range(1, 2*m, 2)
    return {a*a+b*b for a in O for b in O}

for m in range(1, 7):
    assert distance_set(m, (1,0,1), (1,1)) == odd_square_sums(m)

(a; file description) The full script additionally contains the direct $m^4$ point-pair cross-checks, incremental exhaustive scan, hard-coded regression counts, and full-set hashes.

PARTIAL: The disjoint diagonal half-shift has an exact odd-square-sum distance set and is the unique finite-family minimizer in 848 arithmetic candidates for every $4\le m\le64$, but Landau–Ramanujan rigorously keeps it at $\Theta(n/\sqrt{\log n})$; the unrestricted problem remains open between $\Omega(n/\log n)$ and $O(n/\sqrt{\log n})$.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger