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

Erdős problem #604 — wave w002

Access date: 2026-07-28 (UTC). This is a partial result, not a solution of the asymptotic problem.

Claim labels

[a] elementary-rigorous: proved in this report from elementary facts.
[b] rigorous-modulo-named-theorem: the deduction is rigorous, with the

explicitly named published theorem used as an input.

[c] plausible/structural-unverified: heuristic or a literature-search

miss, not a theorem.

[d] computational-only: established by the supplied exact computation,

without claiming a general proof.

Step 0: authoritative live-page check

I fetched both the live problem page and its discussion thread through the Bright Data browser path, not datacenter curl.

[b/page] Verbatim current statement:

Given $n$ distinct points $A\subset\mathbb R^2$ must there be a point $x\in A$ such that \[ > \#\{d(x,y):y\in A\}\gg n^{1-o(1)}? > \] Or even $\gg n/\sqrt{\log n}$?

[b/page] Eligibility and markers on the live page:

Status: OPEN - $500.
Claimed proofs: 0 claimed proofs for this problem.
Interested in collaborating: None.
Currently working on this problem: None.
The page says it was last edited 23 March 2026.
There is one comment, by Zach Hunter on 8 February 2026:

“if there exists a single point, then by greedily repeating this you will of course get $\gg n$ such points.” The thread says the site was updated to address the comment.

Thus the mandatory stop condition did not trigger.

[b/page] Known-results text recorded from the live page:

This is the pinned-distance problem, stronger than problem #89.
The integer grid shows that $n/\sqrt{\log n}$ would be best possible.
Erdős also conjectured the average bound

\[ \sum_{x\in A}d(x)\gg \frac{n^2}{\sqrt{\log n}}, \] where $d(x)$ is the number of distinct distances from $x$.

The page notes the ambiguity of whether Erdős's $500 offer in [Er97e] was

for one good point or for $\gg n$ good points.

It records that Erdős's stronger initial “overconjecture” was disproved by

Harborth.

It gives the best known lower bound as

\[ \Delta_{\rm pin}(A)\gg n^{c-o(1)},\qquad c=\frac{48-14e}{55-16e}=0.864137\ldots, \] due to Katz and Tardos.

The literal page set includes $d(x,x)=0$. The papers conventionally omit zero. This changes every exact finite count below by $+1$, and changes none of the asymptotics.

Literature audit

[b] Katz–Tardos really proves the quoted pinned bound. Corollary 6 of N. H. Katz and G. Tardos, A new entropy inequality for the Erdős distance problem, Contemporary Mathematics 342 (2004), 119–126, says that for every $\varepsilon>0$, every $n$-point planar set has a point seeing

\Omega\!\left(n^{(48-14e)/(55-16e)-\varepsilon}\right)

distinct distances. The exact paper is available from Tardos's publication page, and its DOI is 10.1090/conm/342/06136. The checker independently recomputes the exponent as 0.86413751027277106375....

[b] Later primary sources still identify this as the real-plane record. Lund and Petridis explicitly call $\Omega(N^{0.864\ldots})$ the best known bound in Bisectors and pinned distances, arXiv:1810.00765, Discrete & Computational Geometry 64 (2020), 995–1012, DOI 10.1007/s00454-019-00122-w. Pham, Senger, and Tran again call Katz–Tardos the “best current record” over $\mathbb R$ in Remark 1.1 of Distribution of pinned distance trees in the plane $\mathbb F_p^2$, Discrete Mathematics 346 (2023), 113613, DOI 10.1016/j.disc.2023.113613. Their results concern finite fields and do not improve the present real-plane problem.

[b] The exact-small-case input is a published locally-distance theorem. Nozaki and Shinohara define a locally $k$-distance set exactly as a set in which every point sees at most $k$ nonzero distances. In On a generalization of distance sets, arXiv:0906.0199, JCTA 117 (2010), 810–826, DOI 10.1016/j.jcta.2009.11.001, they record:

every planar locally two-distance set has at most five points; and
every planar locally three-distance set has at most eight points.

Their eight-point result cites Erdős and Fishburn, Distinct distances in finite planar sets, Discrete Mathematics 175 (1997), 97–132, DOI 10.1016/S0012-365X(96)00145-800145-8). The latter paper's abstract explicitly states the sharp minimum $\sum_x d(x)=24$ for eight points.

[c] Search miss, not a novelty claim. Searches by the exact exponent, “pinned distance”, and “locally four-distance” through 2026 found no later real finite-set exponent and no source for the ten-point construction below. This does not prove that the construction is new.

A clean reformulation

For $n\ge2$, define the nonzero pinned extremal function

f(n)=\min_{\substack{A\subset\mathbb R^2\\|A|=n}} \max_{x\in A}\#\{\lVert x-y\rVert:y\in A,\ y\ne x\}.

Let

L(k)=\max\{|A|:A\subset\mathbb R^2,\ \#\{\lVert x-y\rVert:y\ne x\}\le k\text{ for every }x\in A\}.

[a] Exact inverse relation.

f(n)=\min\{k:n\le L(k)\}.

Indeed, a subset of a locally $k$-distance set is still locally $k$-distance, while $n>L(k-1)$ rules out maximum pin count $k-1$.

[a] An elementary finiteness bound.

L(k)\le 1+k(2k+1).

Fix $x$. The other points lie on at most $k$ circles centered at $x$. If one such circle contains $m$ points of $A$, choose a point $p$ on that circle. A circle centered at $p$ meets the first circle in at most two points, so $p$ sees at least $\lceil(m-1)/2\rceil$ distances within that circle. Hence $m\le2k+1$, and summing the $k$ shells proves the bound.

[a] The requested bounds translate into one uniform missing lemma:

$f(n)\ge n^{1-o(1)}$ is equivalent to $L(k)\le k^{1+o(1)}$.
$f(n)=\Omega(n/\sqrt{\log n})$ is equivalent, up to absolute constants,

to \[ L(k)=O(k\sqrt{\log k}). \]

For the second equivalence, use the elementary quadratic bound above to replace $\log L(k)$ with $O(\log k)$. The Katz–Tardos result currently gives only

L(k)\le k^{1/c+o(1)} =k^{1.157223229\ldots+o(1)}.

[a] Rich line/circle cases are already linear. If a line or circle contains $M$ points of $A$, some point of $A$ sees at least $\lceil(M-1)/2\rceil$ distances just to that subset. For a line one can choose an extreme point and get $M-1$. For a circle, every fixed positive distance has multiplicity at most two. In particular, an all-circular set has at least $\lfloor n/2\rfloor$ pinned distances at every point, and the regular $n$-gon attains equality. Thus the hard regime has no line or circle containing $\Omega(n/\sqrt{\log n})$ points.

Explicit proper locally four-distance set of size 10

[a] Construction. Put

\rho=\frac{3-\sqrt5}{2}=\varphi^{-2}.

Take an outer regular pentagon of circumradius $1$,

O_j=(\cos(2\pi j/5),\sin(2\pi j/5)),\qquad 0\le j<5,

and an inner regular pentagon of circumradius $\rho$, rotated by $36^\circ$,

I_j=\rho\bigl(\cos((2j+1)\pi/5),\sin((2j+1)\pi/5)\bigr), \qquad 0\le j<5.

Write

A=\frac{5-\sqrt5}{2},\quad B=\frac{5+\sqrt5}{2},\quad C=5-2\sqrt5,\quad E=\frac{15-5\sqrt5}{2},\quad F=\frac{25-11\sqrt5}{2}.

These are five distinct positive numbers.

[a] Exact distance calculation. The squared distances from every outer point are exactly

\{C,A,E,B\},

and those from every inner point are exactly

\{F,C,A,E\}.

To see the coincidences, same-ring outer squared distances are $A,B$; same-ring inner squared distances are $\rho^2A,\rho^2B$; and the three cross-ring angular separations are $36^\circ,108^\circ,180^\circ$. Direct simplification gives

d^2_{\rm cross}(108^\circ)=A,\qquad d^2_{\rm cross}(36^\circ)=\rho^2B=C,

d^2_{\rm cross}(180^\circ)=E,\qquad \rho^2A=F.

Consequently all ten points see exactly four nonzero distances, while the whole set determines five distances. It is a proper locally four-distance set, so

L(4)\ge10.

The standalone checker performs this calculation in the exact field $\mathbb Q(\sqrt5)$, with rational coefficient pairs and no numerical tolerance.

Exact pinned values through $n=10$

[a] Matching eight-point construction. The known locally three-distance extremizer can be written as the four vertices $(\pm\frac12,\pm\frac12)$ of a unit square together with

\left(\pm\frac{1+\sqrt3}{2},0\right),\qquad \left(0,\pm\frac{1+\sqrt3}{2}\right).

These are the apices of four outward equilateral triangles. A square vertex has squared-distance set $\{1,2,2+\sqrt3\}$; an apex has $\{1,2+\sqrt3,4+2\sqrt3\}$. Hence every point sees exactly three distances. The checker verifies this exactly in $\mathbb Q(\sqrt3)$.

[b] Exact table. Use the elementary $L(1)=3$, the published $L(2)=5$, the published $L(3)=8$, the eight-point construction above, and the ten-point construction above:

| $n$ | $f(n)$, nonzero convention | literal live-page count $f(n)+1$ | |---:|---:|---:| | 2 | 1 | 2 | | 3 | 1 | 2 | | 4 | 2 | 3 | | 5 | 2 | 3 | | 6 | 3 | 4 | | 7 | 3 | 4 | | 8 | 3 | 4 | | 9 | 4 | 5 | | 10 | 4 | 5 |

In particular,

\boxed{f(10)=4}

is rigorous modulo the named Nozaki–Shinohara theorem $L(3)=8$. The construction proves $f(10)\le4$, and $10>8=L(3)$ proves $f(10)\ge4$.

[b] Precisely the next unresolved finite question under this reduction is

f(11)\in\{4,5\},

and deciding between the two is equivalent to deciding whether a planar locally four-distance set of size 11 exists. The upper value $5$ follows from the regular 11-gon; the lower value $4$ follows from $L(3)=8$.

Exact square-grid obstruction

Let

G_m=\{0,1,\ldots,m-1\}^2,\qquad n=m^2.

[a] Closed exact formula for the maximum pin count:

\Delta_{\rm pin}(G_m) =D_m =\#\{a^2+b^2:0\le a,b\le m-1,\ (a,b)\ne(0,0)\}.

Every difference vector between two grid points has $(|a|,|b|)\in[0,m-1]^2$, so every pin's squared-distance set is contained in the displayed set. A corner realizes every displayed pair, proving equality.

[d] Exact recomputed table:

| $m$ | $n=m^2$ | $D_m$ | |---:|---:|---:| | 2 | 4 | 2 | | 3 | 9 | 5 | | 4 | 16 | 9 | | 5 | 25 | 14 | | 10 | 100 | 50 | | 20 | 400 | 179 | | 50 | 2500 | 992 | | 100 | 10000 | 3663 | | 200 | 40000 | 13647 | | 512 | 262144 | 82489 |

For $2\le m\le12$, the checker also enumerates every pin independently and confirms that its distance set is contained in the corner set and that a corner attains the maximum.

[b] Asymptotic verification modulo the Landau–Ramanujan theorem. If $B(X)$ counts positive integers at most $X$ representable as a sum of two squares, then

B((m-1)^2)\le D_m\le B(2(m-1)^2).

Landau–Ramanujan gives $B(X)=\Theta(X/\sqrt{\log X})$, hence

D_m=\Theta\!\left(\frac{m^2}{\sqrt{\log m}}\right) =\Theta\!\left(\frac{n}{\sqrt{\log n}}\right).

This proves, rather than merely samples, why the grid has the order stated on the live page.

Verification

Run:

python runs/erdos604_wavew002_reverify.py

The checker uses only the Python standard library. It:

computes all squared distances in the eight-point construction exactly in

$\mathbb Q(\sqrt3)$;

computes all squared distances in the ten-point construction exactly in

$\mathbb Q(\sqrt5)$;

verifies the construction half of the exact $f(n)$ table;
recomputes every grid-table entry and independently enumerates all pins for

$m\le12$; and

recomputes the Katz–Tardos decimal to 60-digit working precision.

Observed final line:

ALL CHECKS PASSED

Honest boundary of the result

[a] The ten-point construction and the grid formula are exact, but neither is a uniform lower bound for arbitrary $n$. They do not improve the Katz–Tardos exponent.

[b] The exact missing theorem remains the uniform estimate

L(k)=O(k\sqrt{\log k})

(or $L(k)\le k^{1+o(1)}$ for the weaker question). Existing global Guth–Katz distance machinery does not supply this pinned estimate; the later primary literature above continues to distinguish the two problems.

[c] An unstructured exact search for the next case is not realistic: already $K_{11}$ has 55 edges and $B_{55} =359334085968622831041960188598043661065388726959079837$ unrestricted edge-equality partitions. Local-degree constraints and symmetry would reduce this drastically, so this is not a lower bound on a good algorithm; it explains why a naive semialgebraic enumeration was not run.

PARTIAL: Constructed and exactly checked a 10-point proper locally four-distance set, proving $f(10)=4$ modulo the published sharp theorem $L(3)=8$; the asymptotic Erdős problem remains open.

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