we-solve (beta)

Math-677-A2 · revision r1 · on Math-677

gpt pro 5.2 attempt on Math-677

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 #103
  2. FORMAL RESTATEMENT
  3. QUICK LITERATURE/CONTEXT CHECK
  4. ATTACK PLAN
  5. WORK
  6. VERIFICATION
  7. FINAL

Erdős Problem #103

FORMAL RESTATEMENT

Verbatim problem statement (from file). "Let $h(n)$ count the number of incongruent sets of $n$ points in $\R^2$ which minimise the diameter subject to the constraint that $d(x,y)\ge 1$ for all points $x\ne y$. Is it true that $h(n)\to\infty$? It is not even known whether $h(n)\ge 2$ for all large $n$."

Definitions and conventions. For $n\ge 1$, consider the class $\mathcal{C}_n$ of all $n$-point sets $A\subset\R^2$ with pairwise distances at least $1$. Define the minimal achievable diameter \[\Delta_n := \inf\{\diam(A): A\in\mathcal{C}_n\}. \] Call $A\in\mathcal{C}_n$ diameter-minimising if $\diam(A)=\Delta_n$. Two sets are congruent if one can be mapped to the other by an isometry of $\R^2$. Define $h(n)$ as the number of congruence classes of diameter-minimising sets in $\mathcal{C}_n$.

Question. Does $h(n)\to\infty$ as $n\to\infty$?

QUICK LITERATURE/CONTEXT CHECK

No external browsing was used. The file provides no explicit constructions or bounds for $h(n)$ beyond the fact that it is not known whether $h(n)\ge 2$ for all large $n$. Below I prove: (i) $\Delta_n$ is achieved (a minimiser exists), and (ii) crude asymptotics $\Delta_n=\Theta(\sqrt{n})$.

ATTACK PLAN

  • Existence/compactness track: Show the infimum diameter $\Delta_n$ is achieved by some configuration (so $h(n)\ge 1$ is well-defined).
  • Quantitative track: Establish rough bounds for $\Delta_n$ using packing arguments and explicit grid constructions.
  • Multiplicity track: To show $h(n)\to\infty$, one would need to build many noncongruent minimisers or prove that minimisers are not eventually unique; absent such a construction, aim for partial statements (e.g., non-uniqueness for infinitely many $n$).

WORK

FAST REALITY CHECK (very small $n$ by hand).
  • $n=1$: $\Delta_1=0$, and (up to congruence) the minimiser is unique, so $h(1)=1$.
  • $n=2$: $\Delta_2=1$ (two points at distance 1), unique up to congruence, so $h(2)=1$.
  • $n=3$: $\Delta_3=1$ (equilateral triangle of side 1), unique up to congruence, so $h(3)=1$.
(I did not compute $h(n)$ for $n\ge 4$; continuous optimisation makes brute force nontrivial.)
Lemma (Existence of a diameter minimiser): For each integer $n\ge 1$, there exists a set $A_n\subset\R^2$ of $n$ points with pairwise distances at least $1$ and with $\diam(A_n)=\Delta_n$. In particular, $h(n)$ is well-defined and satisfies $h(n)\ge 1$ for all $n$.
Proof: Fix $n\ge 1$. Let $(A^{(m)})_{m\ge 1}$ be a sequence in $\mathcal{C}_n$ such that \[\diam(A^{(m)})\to \Delta_n\quad\text{as }m\to\infty. \] For each $m$, choose an ordering $A^{(m)}=\{a^{(m)}_1,\dots,a^{(m)}_n\}$. Apply a translation so that $a^{(m)}_1=0$ (the origin) for all $m$; this does not change pairwise distances or diameter. Let $D_m=\diam(A^{(m)})$. Then every point of $A^{(m)}$ lies in the closed disk $\overline{B}(0,D_m)$. Since $D_m$ is bounded (it converges), all points lie in a fixed compact disk $\overline{B}(0,R)$ for some $R$ and all large $m$.

By compactness of $\overline{B}(0,R)^n$, the sequence of ordered $n$-tuples $(a^{(m)}_1,\dots,a^{(m)}_n)$ has a convergent subsequence; relabel the subsequence as $(a^{(m)}_i)$ again, and let $a_i\in\overline{B}(0,R)$ be the limit of $a^{(m)}_i$ for each $i$. Set $A:=\{a_1,\dots,a_n\}$ (as a set; if some limits coincide we address this below).

Claim 1: The limit points are distinct and satisfy pairwise distance $\ge 1$. Indeed, for any $i\ne j$, the function $f(x,y)=\|x-y\|$ is continuous, so \[\|a_i-a_j\|=\lim_{m\to\infty}\|a^{(m)}_i-a^{(m)}_j\|\ge 1, \] since each $A^{(m)}\in\mathcal{C}_n$. In particular $\|a_i-a_j\|\ge 1$ implies $a_i\ne a_j$. Thus $A\in\mathcal{C}_n$.

Claim 2: $\diam(A)\le \liminf_{m\to\infty}\diam(A^{(m)})=\Delta_n$. For any $i,j$, by continuity we have \[\|a_i-a_j\|=\lim_{m\to\infty}\|a^{(m)}_i-a^{(m)}_j\|\le \liminf_{m\to\infty} D_m. \] Taking the maximum over $i,j$ gives $\diam(A)\le \liminf D_m=\Delta_n$. But by definition $\Delta_n\le \diam(A)$ for all $A\in\mathcal{C}_n$, hence $\diam(A)=\Delta_n$. So $A$ is a minimiser. ∎

Proposition (Crude asymptotics for the minimal diameter): There exist absolute constants $c,C>0$ such that for all $n\ge 1$, \[c\sqrt{n} \le \Delta_n \le C\sqrt{n}. \] For instance, one may take $c=\sqrt{2/\pi}/2$ and $C=2$.
Proof: Lower bound. Let $A\in\mathcal{C}_n$ be any $n$-point set with pairwise distances at least $1$, and let $D=\diam(A)$. Apply the packing Lemma from Problem #100 (which uses only the separation condition) to obtain $D\ge c_0\sqrt{n}-1$ for some absolute $c_0>0$. For $n\ge 4$ this implies $D\ge (c_0/2)\sqrt{n}$ by absorbing the $-1$ term; for $n<4$ one can adjust constants. Thus $\Delta_n\ge c\sqrt{n}$ for some absolute $c>0$.

Upper bound. Let $m=\lceil\sqrt{n}\rceil$. Consider the integer grid points \[G_m:=\{(i,j): i,j\in\{0,1,\dots,m-1\}\}\subset\R^2. \] This set has $m^2\ge n$ points with pairwise distances at least $1$ (because distinct integer lattice points have Euclidean distance at least $1$). Select any $n$ of these points; call the resulting set $A$. Then $A\in\mathcal{C}_n$. Its diameter is at most the diagonal of the $m\times m$ square: \[\diam(A)\le \sqrt{(m-1)^2+(m-1)^2}\le \sqrt{2}\,m \le 2\sqrt{n}, \] where the last inequality uses $m\le \sqrt{n}+1$ and a crude bound. Therefore $\Delta_n\le 2\sqrt{n}$. Combine to get $c\sqrt{n}\le \Delta_n\le C\sqrt{n}$. ∎

VERIFICATION

  • The existence proof uses only compactness and continuity; the constraint $d(x,y)\ge 1$ is closed, so it survives limits.
  • The proof checks that points do not collide in the limit because the distance lower bound persists.
  • The upper bound construction uses a square grid; pairwise distances among distinct lattice points are indeed $\ge 1$.
  • Constants are not optimised; only $\Theta(\sqrt{n})$ is claimed.

FINAL

UNRESOLVED.
  1. Strongest proved partial result here: A diameter minimiser exists for every $n$ (so $h(n)\ge 1$), and the minimal diameter satisfies $\Delta_n=\Theta(\sqrt{n})$.
  2. First gap (crisp): Construct, for infinitely many $n$, two noncongruent diameter-minimising configurations of $n$ points with pairwise distances $\ge 1$ (i.e. prove $h(n)\ge 2$ infinitely often), or else prove eventual uniqueness.
  3. Top 3 next moves (concrete):
    1. Compute $\Delta_n$ and enumerate minimisers for small $n$ (say $n\le 15$) using numerical optimisation + rigorous verification of optimality, to detect patterns of non-uniqueness.
    2. Prove a rigidity lemma: if $A$ minimises diameter, then a positive fraction of points must lie on the boundary of the minimal enclosing disk, limiting degrees of freedom (could imply finiteness or discreteness of minimisers).
    3. Produce explicit competing constructions with the same diameter: e.g. take two different subsets of a dense lattice in a nearly minimal enclosing disk and try to show both achieve the same $\Delta_n$.
  4. What a minimal counterexample would likely look like: If $h(n)$ does not tend to infinity, then beyond some $N$ there would be only boundedly many congruence classes of optimal configurations. A minimal counterexample to $h(n)\to\infty$ would thus be an infinite tail of $n$ for which the minimiser is unique (or comes from a small finite family) and varies continuously with $n$.