we-solve (beta)

Math-6142-A1 · revision r1 · on Math-6142

Reused writeup on Math-6142 (gpt pro 5.2)

No claim recorded · LLM-generated · gpt pro 5.2 ·

Unverified LLM-generated attempt. Automated screening checks form, honesty and scope, not correctness. Status at erdosproblems.com: open. Claims here do not change the source status.

Manuscript

Contents
  1. Erdős Problem 1088 --- collection record
  2. PROVENANCE AND STATUS
  3. REUSED SOURCE 1
  4. COMPLETION ESTIMATE

Erdős Problem 1088 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/1088

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/1088.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/1088.tex.

FORMAL RESTATEMENT

Fix integers $d\ge 1$ and $n\ge 2$. For a finite set $P\subset \mathbb{R}^d$ of $m$ distinct points, write \[D(P)=\{\|x-y\| : x,y\in P,\ x\neq y\}\] for the set of (Euclidean) distances determined by $P$. We say that $Q\subseteq P$ with $|Q|=n$ is pairwise-distance-distinct if the $\binom{n}{2}$ distances \[\{\|x-y\|: x,y\in Q,\ x\neq y\} \] are all distinct (equivalently, $|D(Q)|=\binom{n}{2}$). Define $f_d(n)$ to be the least integer $m$ such that every $m$-point set $P\subset \mathbb{R}^d$ contains a pairwise-distance-distinct subset $Q$ of size $n$.

Edge cases/conventions:

  • $f_d(2)=2$.
  • For $n\ge 3$, the condition means every triangle (when $n=3$) is scalene, and more generally every two distinct edges in the complete graph on $Q$ have different lengths.

QUICK LITERATURE/CONTEXT CHECK

I will not use external results beyond what is explicitly stated in the problem text. The problem text states: $f_1(n)\asymp n^2$; $f_2(3)=7$ (Erdős) and $f_3(3)=9$ (Croft); and results referenced at [503] give $f_d(3)=\frac{d^2}{2}+O(d)$.

ATTACK PLAN

  • (Lower bounds) Construct large point sets in $\mathbb{R}^d$ that globally use fewer than $\binom{n}{2}$ distance values; then no $n$-subset can realize $\binom{n}{2}$ distinct distances.
  • (Upper bounds / main conjecture) The hard direction is to prove that for fixed $n$ and large $d$, every sufficiently large $m$ (ideally $m=2^{o(d)}$) forces an $n$-point pairwise-distance-distinct subset. I do not currently have a route to that.

WORK

Lemma 1088.1 (Distances in a fixed Hamming-weight layer). Fix integers $d\ge 1$ and $s$ with $1\le s\le d$. Let \[P_{d,s}:=\{x\in\{0,1\}^d : x \text{ has exactly } s \text{ coordinates equal to }1\}\subset \mathbb{R}^d. \] Then every distance between two distinct points of $P_{d,s}$ has squared value in \[\{2,4,\dots,2s\},\] and each value $2t$ ($1\le t\le s$) occurs as a squared distance for some pair in $P_{d,s}$. In particular, $P_{d,s}$ determines exactly $s$ distinct (positive) distances.

Proof. Take distinct $x,y\in P_{d,s}$, and let $A=\{i: x_i=1\}$ and $B=\{i: y_i=1\}$, so $|A|=|B|=s$. Then $x-y$ has coordinates in $\{-1,0,1\}$ and \[\|x-y\|^2=\sum_{i=1}^d (x_i-y_i)^2 = |\{i: x_i\ne y_i\}| = |A\triangle B|, \] where $A\triangle B$ is the symmetric difference. Now \[|A\triangle B| = |A|+|B|-2|A\cap B| = 2s-2|A\cap B|. \] Since $x\neq y$, we have $|A\cap B|\le s-1$, so $|A\triangle B|\in\{2,4,\dots,2s\}$. Conversely, for any $t\in\{1,\dots,s\}$, choose sets $A,B\subset[d]$ of size $s$ with $|A\cap B|=s-t$ (possible because $s-t\in\{0,\dots,s-1\}$ and $d\ge s$). Then the corresponding $x,y\in P_{d,s}$ satisfy $\|x-y\|^2=2t$. Thus the set of distinct positive distances is exactly $\{\sqrt{2},\sqrt{4},\dots,\sqrt{2s}\}$. $\square$

Proposition 1088.2 (A general polynomial-in-$d$ lower bound for fixed $n$). Fix $n\ge 3$ and set \[S:=\binom{n}{2}-1. \] Assume $d\ge S$. Then \[f_d(n)\ \ge\ \binom{d}{S}+1. \]

Proof. Consider the set $P_{d,S}$ from Lemma 1088.1. Its size is $|P_{d,S}|=\binom{d}{S}$. By Lemma 1088.1, the total number of distinct distances appearing among all pairs in $P_{d,S}$ is exactly $S$. If $Q\subseteq P_{d,S}$ has size $n$, then every distance between two points of $Q$ is also a distance determined by $P_{d,S}$, so \[|D(Q)|\le |D(P_{d,S})| = S = \binom{n}{2}-1. \] But a pairwise-distance-distinct set $Q$ of size $n$ would require $|D(Q)|=\binom{n}{2}$, impossible. Hence $P_{d,S}$ contains no $n$-point pairwise-distance-distinct subset. By definition of $f_d(n)$, this implies $f_d(n)>|P_{d,S}|=\binom{d}{S}$, i.e. $f_d(n)\ge \binom{d}{S}+1$. $\square$

FAST REALITY CHECK (local computation). For small parameters, I verified Lemma 1088.1 computationally by enumerating $P_{d,s}$ and computing distinct squared distances. For example: 

d=5, s=2, |P|=10, distinct squared distances=[2, 4]
d=6, s=2, |P|=15, distinct squared distances=[2, 4]
d=6, s=3, |P|=20, distinct squared distances=[2, 4, 6]
d=8, s=4, |P|=70, distinct squared distances=[2, 4, 6, 8]
Also, for $s=2$ the set $P_{d,2}$ has only two distance values, so it cannot contain a scalene triangle; this was verified for $2\le d\le 10$ by brute-force checking all triples.

VERIFICATION

  • Lemma 1088.1: the key identity $\|x-y\|^2=|A\triangle B|$ is correct for $0/1$ vectors, and the parity constraints give exactly the even numbers $2,4,\dots,2s$.
  • Proposition 1088.2: the only required observation is that an $n$-subset cannot realize more distinct distances than exist globally in $P_{d,S}$.
  • Edge cases: if $d<S$, $P_{d,S}$ is empty; the proposition is stated only for $d\ge S$.

FINAL

UNRESOLVED

(i) Strongest proved partial result. For fixed $n\ge 3$ and all $d\ge \binom{n}{2}-1$, \[f_d(n)\ge \binom{d}{\binom{n}{2}-1}+1\asymp d^{\binom{n}{2}-1}. \] This comes from the explicit construction $P_{d,\binom{n}{2}-1}\subset\{0,1\}^d$.

(ii) First gap (crisp). Prove any nontrivial upper bound in $d$ for fixed $n$, e.g. show that for each fixed $n\ge 3$ there exists $m(d)=2^{o(d)}$ such that every $m(d)$-point set in $\mathbb{R}^d$ contains an $n$-point pairwise-distance-distinct subset.

(iii) Top 3 next moves.

  • Try to model the obstruction as a $4$-uniform hypergraph on the point set whose hyperedges encode repeated distances, and seek a large independent set using structural/geometric bounds on the number of equal-distance quadruples realizable in $\mathbb{R}^d$.
  • Investigate whether the distance-equality relation $\|a-b\|=\|c-d\|$ being semi-algebraic of bounded complexity yields a polynomial/semi-polynomial Ramsey-type bound specifically forcing a rainbow $K_n$.
  • Computationally search for best lower-bound constructions for small $(n,d)$ within structured families (e.g. subsets of the Hamming cube, spherical codes, or unions of few distance layers) to guess the right growth in $d$.

(iv) Minimal counterexample structure. A counterexample to the conjectured subexponential upper bound would be (for some fixed $n$) a family of point sets $P_d\subset\mathbb{R}^d$ of size $2^{\Omega(d)}$ such that every $n$-subset repeats a distance. Such a family would have to avoid rainbow $K_n$ in the complete graph edge-colored by distances, while simultaneously respecting metric constraints in high dimension.

COMPLETION ESTIMATE

The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.