we-solve (beta)

Math-5426-A2 · revision r1 · on Math-5426

gpt pro 5.2 attempt on Math-5426

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

Erdős Problem #100

FORMAL RESTATEMENT

Verbatim problem statement (from file). "Let $A$ be a set of $n$ points in $\R^2$ such that all pairwise distances are at least $1$ and if two distinct distances differ then they differ by at least $1$. Is the diameter of $A$ $\gg n$? Perhaps the diameter is even $\ge n-1$ for sufficiently large $n$."

Definitions and conventions.

  • $n\in\N$ with $n\ge 1$.
  • $A\subset\R^2$ with $|A|=n$.
  • For distinct $x,y\in\R^2$, the Euclidean distance is $d(x,y)=\|x-y\|_2$.
  • The diameter of $A$ is $\diam(A)=\max\{d(x,y):x,y\in A\}$.
  • The set of pairwise distances is $D(A)=\{d(x,y):x,y\in A,\ x\ne y\}$.
  • The hypothesis "all pairwise distances are at least $1$" means $\min D(A)\ge 1$.
  • The hypothesis "if two distinct distances differ then they differ by at least $1$" means: \[\forall r,s\in D(A)\ (r\ne s\ \Rightarrow\ |r-s|\ge 1).\] Equivalently, $D(A)$ is a $1$-separated subset of $\R$.

Question. Does there exist an absolute constant $c>0$ such that for every such $A$ one has \[\diam(A)\ge c\,n\ ?\] A stronger possibility mentioned is: for all sufficiently large $n$, must $\diam(A)\ge n-1$?

QUICK LITERATURE/CONTEXT CHECK

No external browsing was used. The file notes (i) an example with $n=9$ and $\diam(A)<5$, (ii) a bound of Kanold: $\diam(A)\ge n^{3/4}$, and (iii) that the Guth--Katz distinct distances bounds imply $\diam(A)\gg n/\log n$. I do not re-prove these literature bounds here; below I prove only elementary bounds and an implication from a distinct-distance lower bound to a diameter lower bound.

ATTACK PLAN

  • Proof track (lower bounds). Relate diameter to the number of distinct distances: the distance-separation condition forces at most $O(\diam(A))$ distinct distances, so any nontrivial lower bound on distinct distances yields a diameter lower bound.
  • Geometric packing track. Independently of the distance-separation condition, the minimum distance $\ge 1$ forces $\diam(A)\gtrsim \sqrt{n}$ by area/packing.
  • Disproof track (constructions). Try to construct large $n$ sets satisfying the separation hypothesis with $\diam(A)=o(n)$ (e.g. variants of lattice constructions). The file indicates such constructions exist at least for $n=9$.

WORK

FAST REALITY CHECK (small cases).
  • $n=1$: any single point has $\diam(A)=0$ and vacuously satisfies the distance conditions.
  • $n=2$: any two points at distance $\ge 1$ satisfy the condition; $\diam(A)=d(x,y)$.
  • Collinear integer-spaced example: $A=\{(0,0),(1,0),\dots,(n-1,0)\}$ has pairwise distances in $\{1,2,\dots,n-1\}$, hence distinct distances differ by at least $1$, and $\diam(A)=n-1$.
  • A minimal brute-force sanity search over lattice points in $[-3,3]^2$ (checked by code) found, for $n=4$, the smallest diameter among such lattice configurations satisfying the constraints is $3$ (achieved by 4 collinear points), and for $n=5$ it is $4$ (achieved by 5 collinear points).
Lemma (Packing lower bound): Let $A\subset\R^2$ be a set of $n\ge 1$ points with pairwise distances at least $1$. Then \[\diam(A)\ge \frac{\sqrt{n}}{2}-\frac12.\] In particular $\diam(A)=\Omega(\sqrt{n})$.
Proof: Let $D=\diam(A)$ and fix an arbitrary point $a_0\in A$. For each $a\in A$ consider the closed Euclidean disk $\overline{B}(a,\tfrac12)$ of radius $1/2$ about $a$. Because pairwise distances in $A$ are at least $1$, these disks have disjoint interiors. Hence the area of their union is the sum of their areas: \[\text{area}\Big(\bigcup_{a\in A}\overline{B}(a,\tfrac12)\Big)= n\cdot \pi\left(\tfrac12\right)^2 = \frac{\pi n}{4}.\]

For any $a\in A$ and any $x\in \overline{B}(a,\tfrac12)$ we have \[d(x,a_0)\le d(x,a)+d(a,a_0)\le \tfrac12 + D,\] where $d(a,a_0)\le D$ follows from the definition of diameter. So $\overline{B}(a,\tfrac12)\subseteq \overline{B}(a_0,D+\tfrac12)$ for every $a\in A$. Therefore \[\bigcup_{a\in A}\overline{B}(a,\tfrac12)\subseteq \overline{B}(a_0,D+\tfrac12).\] Comparing areas gives \[\frac{\pi n}{4}\le \pi\left(D+\tfrac12\right)^2.\] Cancel $\pi$ and take square roots: \[\frac{\sqrt{n}}{2}\le D+\tfrac12\quad\Rightarrow\quad D\ge \frac{\sqrt{n}}{2}-\frac12.\] ∎

Proposition (Distance separation bounds the number of distinct distances): Let $A\subset\R^2$ satisfy the hypotheses of Problem #100, and set $D=\diam(A)$. Let $m=|D(A)|$ be the number of distinct pairwise distances realized by $A$. Then \[m\le \lfloor D\rfloor\quad\text{and in particular}\quad m\le D. \] More generally, without integrality assumptions one always has $m\le \lceil D\rceil$.
Proof: By hypothesis, every distance in $D(A)$ lies in the interval $[1,D]$. Also by hypothesis, $D(A)$ is $1$-separated: if $r\ne s$ are in $D(A)$ then $|r-s|\ge 1$. Let $r_1<r_2<\cdots<r_m$ list the elements of $D(A)$ in increasing order. Then $r_{i+1}-r_i\ge 1$ for all $i$, so by telescoping \[r_m-r_1\ge (m-1)\cdot 1 = m-1. \] But $r_1\ge 1$ and $r_m\le D$, hence $r_m-r_1\le D-1$. Combining gives $m-1\le D-1$, i.e. $m\le D$. Since $m$ is an integer, $m\le \lfloor D\rfloor$. Equivalently $m\le \lceil D\rceil$ also holds. ∎
Corollary (Distinct-distance lower bounds imply diameter lower bounds): Suppose there is a function $L(n)$ such that every $n$-point subset of $\R^2$ determines at least $L(n)$ distinct distances. Then any set $A$ satisfying the hypotheses of Problem #100 obeys \[\diam(A)\ge L(n).\] In particular, using the file's statement that Guth--Katz implies $L(n)\gg n/\log n$, one obtains $\diam(A)\gg n/\log n$.
Proof: Let $m$ be the number of distinct distances determined by $A$. By assumption $m\ge L(n)$. By Proposition above, $m\le \diam(A)$. Therefore $\diam(A)\ge L(n)$. The final sentence is the specialization $L(n)\gg n/\log n$ as already stated in the problem file. ∎

VERIFICATION

  • Quantifiers: Lemma 1 uses only the $d(x,y)\ge 1$ assumption, so it is valid for all sets in the problem.
  • Edge cases: For $n=1$, Lemma 1 gives $\diam(A)\ge \sqrt{2/\pi}-1<0$, which is vacuous but consistent (lower bounds can be negative). For $n\ge 2$ it yields a nontrivial bound.
  • Proposition: The separation argument uses only that all distances lie in $[1,D]$ and differ by $\ge 1$; no hidden geometry.
  • Consistency with known examples: The collinear example has $m=n-1$ and $D=n-1$, saturating Proposition. The file's mention of $n=9$ with $D<5$ is consistent with Proposition only if $m\le 4$, i.e. such configurations must realize very few distinct distances.

FINAL

UNRESOLVED.
  1. Strongest proved partial result here: For any admissible $A$, $\diam(A)\ge \Omega(\sqrt{n})$ (Lemma 1). Also $|D(A)|\le \diam(A)$ (Proposition), so any distinct-distance lower bound $L(n)$ implies $\diam(A)\ge L(n)$.
  2. First gap (crisp): Prove or disprove the existence of an absolute $c>0$ such that every admissible $A$ satisfies $\diam(A)\ge c n$.
  3. Top 3 next moves (concrete):
    1. Attempt a purely elementary distinct-distance lower bound for these special sets (using the distance separation and $d\ge 1$) that beats $\sqrt{n}$.
    2. Search for explicit constructions (beyond $n=9$) with $\diam(A)=o(n)$, e.g. via computer search in bounded grids but allowing non-lattice coordinates (parametrized families).
    3. Try to prove a structural lemma: admissible sets with small diameter must have many repeated distances, forcing many isosceles triangles/circle incidences, and then leverage incidence bounds.
  4. What a minimal counterexample would likely look like: A sequence $A_n$ with $|A_n|=n$, $\diam(A_n)=o(n)$, and a very small set of distinct distances (by Proposition). Such a counterexample must force extremely high multiplicities of a few distance values.