we-solve (beta)

Math-672-A3 · revision r1 · on Math-672

gpt pro 5.2 attempt on Math-672

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 #98
  2. (A) Tiny cases (exact).
  3. (B) General bounds from the literature.

Erdős Problem #98

  1. Formal Restatement.

    For a finite set $P\subset\mathbb{R}^2$, write \[ \Delta(P):=\{\|p-q\|:p,q\in P,\ p\ne q\} \] for the set of (nonzero) Euclidean distances determined by pairs of points. Let $\mathcal{G}_n$ be the family of all $n$-point sets $P\subset\mathbb{R}^2$ in general position in the sense:

    • no three points of $P$ are collinear;
    • no four points of $P$ are concyclic.
    Define \[ h(n):=\min\{\,|\Delta(P)|: P\in\mathcal{G}_n\,\}. \]

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

  2. Quick literature/context check.

    The Erdős Problems page lists this as open (last edited 15 Oct 2025).[ErdosProblems98] It records that Erdős could not even prove $h(n)\ge n$, and that Pach proved an upper bound $h(n)<n^{\log_2 3}$.[ErdosProblems98] It also records a stronger upper bound by Erdős--Füredi--Pach--Ruzsa $1993$: \[ h(n) < n\exp\left(c\sqrt{\log n}\right)\quad\text{for some constant }c>0. \] [ErdosProblems98,EFPR93]

    Independently, for arbitrary $n$-point sets (with no general-position hypotheses), Guth and Katz proved that the number of distinct distances is at least on the order of $n/\log n$.[GK15] Since $\mathcal{G}_n$ is a subset of all $n$-point sets, this lower bound applies to $h(n)$ as well.

  3. Attack plan.

    Proof track (toward $h(n)/n\to\infty$). Seek a superlinear lower bound on $|\Delta(P)|$ under the combined restrictions "no three collinear" and "no four concyclic." Natural approaches:

    • strengthen incidence-based distinct distance arguments by ruling out rich lines and rich circles;
    • "pinned distance" methods: show some point determines $\omega(n)$ distinct distances, then $|\Delta(P)|\ge \omega(n)$.

    Disproof track (construct $P\in\mathcal{G}_n$ with $|\Delta(P)|=O(n)$). Try to build a highly structured configuration with many repeated distances while avoiding collinear triples and concyclic quadruples. A key obstacle is that small perturbations typically destroy distance multiplicities.

    Phase 1 small cases. Compute/construct $h(n)$ for the smallest $n$ to sanity-check the definition and the general-position constraints.

  4. Work.

    (A) Tiny cases (exact).

    Claim 1: $h(3)=1$. Take an equilateral triangle; then $|\Delta(P)|=1$, and clearly no three collinear. Hence $h(3)\le 1$. On the other hand, any three non-collinear points determine at least one distance, so $h(3)=1$.

    Claim 2: $h(4)=2$. Upper bound. Let $A,B,C$ be an equilateral triangle of side length $1$, and let $O$ be its circumcenter (which coincides with centroid). Then \[ \|A-B\|=\|B-C\|=\|C-A\|=1,\qquad \|O-A\|=\|O-B\|=\|O-C\|=\frac{1}{\sqrt{3}}. \] Thus $\Delta(\{A,B,C,O\})=\{1,1/\sqrt{3}\}$ has size $2$. The four points are in general position: no three are collinear, and they are not concyclic because the unique circle through $A,B,C$ is the circumcircle centered at $O$, which does not contain $O$. So $h(4)\le 2$.

    Lower bound. A set of four planar points cannot have all six pairwise distances equal (the largest equidistant set in $\mathbb{R}^2$ has size $3$), so $h(4)\ne 1$. Therefore $h(4)=2$.

    (B) General bounds from the literature.

    Lower bound (all $n$). Guth--Katz proved that for any $n$ points in $\mathbb{R}^2$, \[ |\Delta(P)| \ge c\,\frac{n}{\log n} \] for some absolute constant $c>0$.[GK15] Since $\mathcal{G}_n$ is a subset of all $n$-point sets, \[ h(n)=\min_{P\in\mathcal{G}_n}|\Delta(P)| \ge c\,\frac{n}{\log n}. \] This is far from the desired superlinear growth, but it is a rigorous baseline.

    Upper bound (general position). Erdős--Füredi--Pach--Ruzsa constructed (for all sufficiently large $n$) $n$-point sets in general position with \[ |\Delta(P)| < n\exp\left(c\sqrt{\log n}\right) \] for some constant $c>0$.[EFPR93,ErdosProblems98] Hence \[ h(n) \le n\exp\left(c\sqrt{\log n}\right). \]

    Current gap. To answer "$h(n)/n\to\infty$?" one needs either:

    • a lower bound $h(n)\ge n\cdot\omega(1)$ (even $h(n)\ge n\log\log n$ would suffice), or
    • a construction showing $h(n)=O(n)$.
    Neither is currently achieved by the bounds above.

  5. Verification.

    The computations for $h(3)$ and $h(4)$ are explicit and verify the general-position constraints. For the general bounds:

    • Guth--Katz applies to all point sets, so it applies to $\mathcal{G}_n$ without extra hypotheses.
    • EFPR93 is explicitly a construction in general position as quoted on the Erdős Problems page, and thus gives an upper bound on $h(n)$.
    No claim here asserts the limit $h(n)/n\to\infty$; rather, these bounds delineate what is known.

  6. FINAL: UNRESOLVED.

    • (i) Strongest fully proved partial result: For all $n$, $h(n)\ge c\,n/\log n$ (Guth--Katz), and there exist general-position sets with $h(n)\le n\exp(c\sqrt{\log n})$ (EFPR93). Also $h(3)=1$ and $h(4)=2$ exactly.
    • (ii) Most plausible route forward: Either (a) prove a substantially improved lower bound in general position by combining incidence geometry with the prohibition of 4-point cocircularities, or (b) construct a genuinely linear-distance construction $|\Delta(P)|=O(n)$ while certifying no 3 collinear and no 4 concyclic.
    • (iii) First place the proof attempt breaks: Known distinct-distance lower bounds (even with modern polynomial/incidence methods) are essentially linear up to polylog factors; current techniques do not yield superlinear lower bounds from these general-position constraints.
    • (iv) What a counterexample would have to look like: An infinite family $P_n\in\mathcal{G}_n$ with $|\Delta(P_n)|\le Cn$ for a constant $C$ independent of $n$.

  7. Completion estimate.

    COMPLETION: 15%.