gpt pro 5.2 attempt on Math-6141
mathematicsErdős problemscontributionManuscript
Contents
Erdős Problem 1087 ("degenerate" 4-sets with a repeated distance)
FORMAL RESTATEMENT
Let $P\subset\mathbb{R}^2$ be a set of $n$ points. Call a 4-element subset $Q\subset P$ degenerate if among the $\binom{4}{2}=6$ pairwise distances $\{\|x-y\|: x,y\in Q, x\ne y\}$ there exist two distinct unordered pairs $\{x,y\}\ne\{u,v\}$ with $\|x-y\|=\|u-v\|$. Let \[ f(n):=\max\{\,\#\{Q\subset P: |Q|=4,\ Q\text{ degenerate}\}: P\subset\mathbb{R}^2,\ |P|=n\,\}. \] Equivalently, $f(n)$ is the smallest number such that every $n$-point set has at most $f(n)$ degenerate 4-subsets. The problem asks for estimates of $f(n)$, in particular whether $f(n)\le n^{3+o(1)}$.QUICK LITERATURE/CONTEXT CHECK
The problem statement records bounds of Erdős--Purdy: $n^3\log n \ll f(n) \ll n^{7/2}$. I do not use further external results.ATTACK PLAN
- Proof track (partial). Provide a clean combinatorial upper bound on the number of degenerate 4-sets in terms of distance multiplicities (counts of equal-length pairs). Provide an explicit construction (regular $n$-gon) yielding $\Omega(n^3)$ degenerate 4-sets.
- Disproof track. Not applicable.
WORK
Fast reality check.
For $P$ the vertices of a regular $n$-gon, brute-force computation shows: for $n=6,7,8,9,10,11$, every 4-subset is degenerate (so the count equals $\binom{n}{4}$); for $n=12$, there are $447$ degenerate 4-subsets out of $\binom{12}{4}=495$.Lemma (Degenerate 4-sets controlled by distance multiplicities): For a finite set $P\subset\mathbb{R}^2$, and each distance value $r>0$, let $a_r$ be the number of unordered pairs $\{x,y\}\subset P$ with $\|x-y\|=r$. Then the number $D(P)$ of degenerate 4-subsets of $P$ satisfies \[
D(P)\le \sum_{r} \binom{a_r}{2}.
\]
Proof: For each distance value $r$, form the graph $G_r$ on vertex set $P$ whose edges are exactly the pairs at distance $r$. Then $|E(G_r)|=a_r$. If $Q\subset P$ is a degenerate 4-set, by definition there exist two distinct unordered pairs $e_1,e_2\subset Q$ with $|e_1|=|e_2|=2$ and $\mathrm{dist}(e_1)=\mathrm{dist}(e_2)=r$ for some $r$. In particular, $e_1$ and $e_2$ are two distinct edges of $G_r$. Thus each degenerate 4-set contributes at least one unordered pair of edges from some $G_r$. For each fixed $r$, the total number of unordered edge-pairs in $G_r$ is $\binom{a_r}{2}$, and the number of degenerate 4-sets that can be "certified" by distance $r$ is at most that. Summing over $r$ gives $D(P)\le \sum_r \binom{a_r}{2}$. ∎
Lemma (Regular $n$-gon gives $\Omega(n^3)$ degenerate 4-sets): Let $P$ be the vertex set of a regular $n$-gon in $\mathbb{R}^2$, with $n\ge 6$. Then \[
f(n)\ge D(P)\ge c\,n^3
\] for an absolute constant $c>0$ (e.g. $c=1/48$ works for all sufficiently large $n$).
Proof: In a regular $n$-gon, for each step size $k\in\{1,2,\dots,\lfloor n/2\rfloor\}$, all chords connecting vertices with cyclic separation $k$ have the same length; denote this length by $\ell_k$. For each fixed $k$ (with $1\le k< n/2$), there are exactly $n$ edges of length $\ell_k$: namely $\{i,i+k\}$ for $i\in\mathbb{Z}/n\mathbb{Z}$. Among these $n$ edges, at most $2n$ unordered pairs of edges share a vertex (each edge shares a vertex with at most $2$ other edges of the same step size at each endpoint), so the number of unordered disjoint edge pairs of length $\ell_k$ is at least \[
\binom{n}{2}-2n = \frac{n(n-1)}{2}-2n \ge \frac{n^2}{3}
\] for all $n\ge 6$. Each disjoint pair of edges $\{a,b\}$ and $\{c,d\}$ of the same length determines a 4-set $\{a,b,c,d\}$ which is degenerate (it contains two equal distances).
Let $T$ be the number of pairs $(k,\{e_1,e_2\})$ where $1\le k\le \lfloor n/3\rfloor$ and $e_1,e_2$ are disjoint edges of length $\ell_k$. By the bound above, for each such $k$ there are at least $n^2/3$ choices of $\{e_1,e_2\}$, so \[ T \ge \left\lfloor\frac{n}{3}\right\rfloor\cdot \frac{n^2}{3} \ge \frac{n^3}{12}-\frac{n^2}{9}. \] On the other hand, a fixed 4-set $Q$ can contribute to at most $3$ such pairs $(k,\{e_1,e_2\})$, because a 4-set has exactly $3$ ways to partition its vertices into two disjoint unordered pairs. Therefore $T\le 3D(P)$, hence \[ D(P)\ge \frac{T}{3} \ge \frac{n^3}{36}-\frac{n^2}{27}. \] Taking $c=1/48$ works for all sufficiently large $n$, and in any case this proves $D(P)=\Omega(n^3)$. Since $f(n)$ is the maximum possible number of degenerate 4-sets over all $n$-point sets, $f(n)\ge D(P)$. ∎
VERIFICATION
- In Lemma 1, the injection "degenerate 4-set $\to$ some distance class edge-pair" may have multiplicities (a 4-set can be certified by multiple distances), but that only strengthens the inequality in the correct direction.
- In Lemma 2, the disjoint-edge-pair count is a lower bound; even if the constant $2n$ is loose, it suffices to obtain $\Omega(n^3)$.
- Computation for regular $n$-gons: for $n\le 11$ all $\binom{n}{4}$ quadruples are degenerate; for $n=12$ the exact number of degenerate quadruples is $447$ (out of $495$).
FINAL
UNRESOLVED.- (i) Strongest proved partial result here: explicit construction shows $f(n)\ge c n^3$. Also, for any point set $P$, the number of degenerate 4-sets is at most $\sum_r \binom{a_r}{2}$ where $a_r$ are multiplicities of each realized distance.
- (ii) First gap: prove a universal upper bound $f(n)\le n^{3+o(1)}$ (or construct configurations with $\gg n^{3+\varepsilon}$ degenerate 4-sets).
- (iii) Top 3 next moves: $1$ bound $\sum_r \binom{a_r}{2}$ sharply using incidence geometry to control distance multiplicities $a_r$; $2$ look for configurations (e.g. integer lattices) where many distances repeat and estimate the resulting degenerate-4 count computationally; $3$ attempt to count non-degenerate 4-sets (all 6 distances distinct) from below to deduce upper bounds on $f(n)$.
- (iv) Minimal counterexample structure (to $f(n)\le n^{3+o(1)}$): sets with many distance classes each containing $\Theta(n)$ pairs, and with many of those pairs disjoint so that $\sum_r \binom{a_r}{2}$ is $\gg n^{3+\varepsilon}$.