Erdős problem 1088 — wave w052

Date checked: 2026-07-31 UTC.

Live gate rechecked: 2026-08-12 UTC. The page remains OPEN with 0 claimed proofs, no comments, and no current-worker or collaboration markers.

Claim labels

• [a] elementary-rigorous: a complete proof is given here from elementary facts.
• [b] rigorous-modulo-named-theorem: the claim uses the explicitly named published theorem or primary source.
• [c] plausible/structural-unverified: a search conclusion or proposed route, not a theorem.
• [d] computational-only: an exact finite computation, reproducible by the standalone checker, but not replaced by a hand enumeration.

0. Mandatory live-page gate

I fetched the live page through the Bright Data JavaScript browser, not by datacenter curl. The fetch returned:

• status: OPEN;
• currently working: None;
• interested in collaborating: None;
• claimed proofs: 0;
• comments: 0;
• all other attribution markers: None;
• last page edit: 08 April 2026.

Thus neither stop condition in the task applies.

Verbatim live statement

Let \(f_d(n)\) be the minimal \(m\) such that any set of \(m\) points in \(\mathbb R^d\) contains a set of \(n\) points such that any two determined distances are distinct. Estimate \(f_d(n)\). In particular, is it true that, for fixed \(n\ge3\), \[ > f_d(n)=2^{o(d)}? > \]

Results listed on the live page

The page says that it is easy that \(f_d(n)\le n^{O_d(1)}\). It says Erdős [Er75f] claimed that he and Straus proved \(f_d(n)\le c_n^d\). It also lists:

• \(f_1(n)\asymp n^2\), referring to problem 530;
• Erdős's \(f_2(3)=7\) and Croft's \(f_3(3)=9\);
• the consequence \(f_d(3)=d^2/2+O(d)\), referring to problem 503;
• the fixed-\(d\), \(n\to\infty\) formulation as problem 1208.

These are page/source records, not assumptions inferred from the tracker metadata.

Results obtained

1. A general explicit polynomial obstruction [a]

Put

For \(d+1\ge s\), consider the constant-weight layer

It lies in the affine hyperplane \(\sum x_i=s\), which is isometric to a copy of \(\mathbb R^d\), and

If \(x,y\) have supports \(A,B\), then

Thus the whole configuration determines at most \(s\) distinct distances. An \(n\)-point set whose pairwise distances are all distinct would require \(q=s+1\) distinct distances. No such subset exists in \(X_{d,s}\). Consequently

For example,

The first has the same \(d^2/2\) leading term as the live page's known asymptotic for \(f_d(3)\).

There is also a sharp diagnosis of this construction strategy. The Bannai--Bannai--Stanton absolute bound says that every \(s\)-distance subset of \(\mathbb R^d\) has size at most \(\binom{d+s}{s}\) [b]. Since, for fixed \(s\),

(1) is asymptotically optimal, even in its leading constant, among obstructions whose entire distance set has at most \(\binom n2-1\) values. Any improvement in the order of growth or in the leading constant must therefore allow at least \(\binom n2\) global distance values while forbidding a rainbow \(K_n\); the absolute bound still leaves room for lower-order improvements within the few-distance strategy.

2. An exact computer-assisted small case: \(f_1(4)=7\) [a+d]

This does not resolve the high-dimensional question, but gives an exact finite regime with a from-scratch certificate.

For points on a line, all pairwise distances are distinct exactly when all unordered sums \(a_i+a_j\), allowing \(i=j\), are distinct. Indeed a nontrivial equality of sums rearranges to an equality of positive differences, and conversely. Hence the desired subsets are additive Sidon sets.

Lower bound [a]. Among \(\{0,1,2,3,4,5\}\), any four points produce six positive pairwise distances, all belonging to \(\{1,2,3,4,5\}\). Therefore some distance repeats and \(f_1(4)\ge7\).

Finite upper reduction [a]. Every four distinct real numbers contain a Sidon triple. To see this, write them \(a<b<c<d\). A triple fails to be Sidon exactly when it is a three-term arithmetic progression. If both \((a,b,c)\) and \((b,c,d)\) are progressions, then \((a,b,d)\) is not.

Choose a Sidon triple and normalize it affinely to \(B=\{0,1,r\}\). If \(x\notin B\) and \(B\cup\{x\}\) is not Sidon, the new collision has one of the forms

After removing duplicates, every possible \(x\) is in the following 15-element symbolic universe:

Therefore, if a seven-point counterexample existed, after normalization it would be a subset of \(C(r)\), would contain \(B\), and would have no Sidon four-subset.

Exhaustive exact step [d]. All entries and pair sums in (2) are affine functions \(a+br\) with rational coefficients. Their equality pattern can change only when two entries or two pair sums coincide. The checker:

1. derives all such rational roots rather than using a precomputed list;
2. finds 95 critical roots, of which 90 leave \(B\) Sidon;
3. handles every noncritical real \(r\), including all irrational \(r\), in

one symbolic \(\mathbb Q(r)\) case;

1. enumerates every subset of the at-most-15 distinct candidates containing

\(B\), and rejects a subset if any of its four-subsets is Sidon.

The generic maximum is 5. Among the 90 allowed critical roots, the maxima are 5 for 66 roots and 6 for 24 roots. The global maximum is therefore 6. No seven-point counterexample exists, proving

The conclusion is computer-assisted: the mathematical reduction is [a], while the final finite enumeration is [d].

3. Exact reduction to points on spheres [a]

Let \(\sigma_j(t)\) be the least \(N\) such that every \(N\) points on a round \(j\)-sphere contain \(t\) points with all pairwise distances distinct. Let \(G(m,t)\) be the least \(N\) such that every edge-coloring of \(K_N\) in which each color occurs at most \(m\) times at each vertex contains a rainbow \(K_t\).

A self-contained local rainbow bound

To prove it, take \(N=4mt^3\). The number of unordered same-colored pairs of edges meeting in a vertex is at most \(mN^2/2\): sum \(\binom{\deg_c(v)}2\le m\deg_c(v)/2\) over \(v,c\). A color class has at most \(mN/2\) edges, so the number of disjoint same-colored edge pairs is at most \(mN^3/8\).

Choose a uniformly random \(2t\)-vertex set. A fixed union of \(r\) vertices is selected with probability at most \((2t/N)^r\). Hence the expected number of same-color edge-pair collisions is at most

Some \(2t\)-set has at most \(t\) collisions. Delete one vertex meeting each collision; at least \(t\) vertices remain and their clique is rainbow. This proves (4).

The spherical sandwich

For \(d\ge2\),

The first inequality holds because a \((d-1)\)-sphere is a subset of \(\mathbb R^d\). For the second, color each edge by its distance. For a fixed point \(p\), all neighbors joined to \(p\) by one color lie on a \((d-1)\)-sphere centered at \(p\). If there were \(\sigma_{d-1}(t)\) such neighbors, they themselves would contain the desired \(t\)-set. Otherwise the coloring is locally \((\sigma_{d-1}(t)-1)\)-bounded, so (4) applies.

It follows immediately from (5) that for every fixed \(t\ge3\),

This is an equivalence, not merely a one-way sufficient condition: their logarithms differ by at most an additive \(O_t(1)\).

On a circle, at most two points are at a prescribed distance from a fixed point, so \(\sigma_1(t)\le G(2,t)\le8t^3\). Intersecting an equal-distance neighborhood with a \(j\)-sphere gives a \((j-1)\)-sphere (or a smaller degenerate set), and hence

Together with the analogous line base case, this independently gives the fully explicit known-type exponential estimate

Conlon--Fox--Gasarch--Harris--Ulrich--Zbarsky use this same geometric recursion with the sharper published local anti-Ramsey estimate in their Lemma 3.1 and Proposition 3.2 [b]. Equations (4)--(7) are included because the constants and every logical step have been rederived here from scratch.

What exactly remains

Equation (6) localizes the open high-dimensional question completely to round spheres. General locally bounded colorings do not finish it: Alon--Jiang--Miller--Pritikin prove

up to absolute constants [b]. With \(t\) fixed this is still \(\Theta_t(m)\), so iterating any black-box one-dimension-at-a-time local-color theorem continues to lose a fixed factor per dimension and only yields \(C_t^d\).

The missing ingredient is therefore a genuinely geometric, multilevel lemma coupling equal-distance sections from several centers or several dimension drops. One precise sufficient form would be a block recurrence

uniformly in \(q\), for unbounded block sizes \(r\). Iterating (8) would prove (6). Present incidence bounds and the general local anti-Ramsey theorem supply \(A_t(r)=C_t^r\), not the required \(\exp(o_t(r))\). No argument found in the checked sources controls the dependencies among those successive sphere sections. This identifies the specific uniformity loss, rather than merely saying that the problem is open.

A naive exact attack on even the next planar regime is also infeasible. Enumerating distance-equality patterns for \(N\) labeled points starts with partitions of the \(\binom N2\) edges, before testing Euclidean realizability. The checker independently computes

for \(N=7\), already about 15.0 core-years at the optimistic rate of one million patterns per second. For \(N=8\),

about \(1.952\times10^8\) core-years at the same rate. Geometry-aware canonical augmentation or a new structural lemma would be mandatory; this brute force was not run.

Primary-source audit

• [Erdős, On some problems of elementary and combinatorial geometry

(1975), pp. 99--108](https://www.renyi.hu/~p_erdos/1975-25.pdf): section 3 defines the older notation \(f(n;k)\), records the unpublished Straus--Erdős exponential bound, and asks whether \(\lim_{k\to\infty}f(n;k)^{1/k}=1\). The scan actually contains those claims [b].

• [Avis--Erdős--Pach, *Distinct distances determined by subsets of a point

set in space* (1991)](https://www.cs.umd.edu/~gasarch/TOPICS/points/AEP.pdf), DOI 10.1016/0925-7721(91)90009-4, studies an “almost all \(k\)-subsets” problem for fixed dimension and large ground sets. It does not state a fixed-\(n\), \(d\to\infty\) subexponential bound [b].

• [Alon--Jiang--Miller--Pritikin, *Properly colored subgraphs and rainbow

subgraphs in edge-colorings with local constraints* (2003)](https://web.math.princeton.edu/~nalon/PDFS/ajmp1.pdf) proves the local rainbow estimate quoted above [b].

• [Conlon et al., Distinct volume subsets,

arXiv:1401.6734](https://arxiv.org/abs/1401.6734), SIAM J. Discrete Math. 29 (2015), 472--480, gives the spherical recurrence and the best bound cited by live problem 1208 for the different fixed-dimensional inverse problem [b].

• [Bannai--Bannai--Stanton, *An upper bound for the cardinality of an

\(s\)-distance subset in real Euclidean space, II* (1983)](https://doi.org/10.1007/BF02579288) has, in its publisher abstract, exactly the bound \(|X|\le\binom{d+s}{s}\) used above [b].

• The recent [Clemen--Führer--Roche-Newton, Geometric Sidon Problems,

arXiv:2606.05841](https://arxiv.org/abs/2606.05841) proves that every finite planar point set has a distinct-distance subset of size \(\gg |P|^{1/3}\). This is a June 2026 improvement in the fixed two-dimensional direction, not in the fixed-\(n\), growing-\(d\) direction [b].

Exact-phrase and notation searches for the fixed-\(n\), growing-\(d\) question found no primary source claiming \(2^{o(d)}\), a counterexample, or a sharper high-dimensional result than the live page. This is an honest search miss, not proof that no such paper exists [c].

Reverification

The complete standalone checker is runs/erdos1088_wavew052_verify.py. It uses only the Python standard library and consumes no precomputed certificate (expected totals are asserted only after they are recomputed). It:

• materializes several constant-weight layers and recomputes every squared

distance;

• recomputes the general binomial lower-bound table;
• checks the exact fractions in (4);
• derives the 15 extension candidates, all 95 critical parameters, and

exhaustively checks every relevant subset for (3);

• computes the Bell numbers by their recurrence.

Run:

python -m py_compile runs/erdos1088_wavew052_verify.py
python runs/erdos1088_wavew052_verify.py

The verified headline output is:

CONSTANT-WEIGHT OBSTRUCTIONS
  n=3, d=6, s=2: |X|=21, squared-distance spectrum=(2, 4)
  n=4, d=8, s=5: |X|=126, squared-distance spectrum=(2, 4, 6, 8)

RAINBOW LEMMA
  PASS: the bound at N=4*m*t^3 is 1+t/2 <= t.

EXACT ONE-DIMENSIONAL CASE
  candidate_count: 15
  all_critical_count: 95
  allowed_critical_count: 90
  generic_maximum: 5
  critical_maximum_distribution: {5: 66, 6: 24}
  overall_maximum: 6
  PASS: the exhaustive symbolic reduction proves f_1(4)=7.

NAIVE DISTANCE-EQUALITY PATTERN COST
  Bell(21)=474869816156751 (~15.0 years at 10^6/s)
  Bell(28)=6160539404599934652455 (~195,215,713.6 years at 10^6/s)

ALL CHECKS PASSED

Measured runtime here was 5.21 seconds with peak RSS 13,956 KB. SHA-256: 13e0d9b34a1d881e0de5a7ba05a1ad93b8a08c916d78f0f470f59121f3fdf09c.

PARTIAL: [a+d] Explicitly proved \(f_d(n)\ge\binom{d+1}{\binom n2-1}+1\), certified \(f_1(4)=7\), and reduced the fixed-\(n\) subexponential question equivalently to distinct-distance subsets on \((d-1)\)-spheres; the missing multilevel geometric lemma remains open.