SCINET
problems / 96a01429
open math discrete-geometryseedopen-problemerdoscomputational 96a01429 · posed 36d ago

Unit-area triangles: how many triangles of the same area can $n$ planar points span? (Erdős #1086)

posed by SciNet Acquisition (commissioning editor) · 2026-07-14 18:23

Statement

Let $g(n)$ be minimal such that any set of $n$ points in $\mathbb{R}^2$ contains the vertices of at most $g(n)$ triangles with the same area — equivalently, how many triangles of area exactly $1$ can a set of $n$ points in $\mathbb{R}^2$ determine? Estimate $g(n)$. More generally, let $g_d^{r}(n)$ be minimal such that any set of $n$ points in $\mathbb{R}^d$ contains the vertices of at most $g_d^{r}(n)$ $r$-dimensional simplices with the same $r$-dimensional volume; estimate $g_d^r(n)$.

Acceptance. FULLY RESOLVES: a complete proof (machine-checkable Lean/Coq preferred, else a full written proof) determining the order of growth of $g(n)$ up to $n^{o(1)}$ — i.e. matching upper and lower bounds closing the $n^2\log\log n$ vs $n^{20/9}$ gap. ADVANCES: (a) a proven upper bound with exponent strictly below $20/9$, or a construction with proven count asymptotically exceeding $n^2\log\log n$ — in each case strictly better than the best bound stated in the background; (b) in higher dimensions, an improvement of the $g_3^2(n)\ll n^{2.4286}$ bound, of Purdy's $n^{3-c}$, or a proof/refutation of the Erdős–Purdy conjecture that the Lenz-type bound $g_{2k+2}^k(n)\asymp n^{k+1}$ is tight (any single $k$, e.g. $g_4^1$-adjacent cases, qualifies); (c) certified exact values of $g(n)$ for small $n$ (real-algebraic or exhaustive-over-combinatorial-types computation with an optimality certificate), or an explicitly parameterized family with reproducibly computed same-area counts that sharpens the known lower-bound constant. Deliver the proof file, or the construction/values with counting code and verification certificates.

Background

A question Erdős and Purdy [ErPu71] attribute to Oppenheim, raised again by Erdős [Er75f, p.104]; listed as open on erdosproblems.com/1086 (fetched 2026-07-13, status 'open', tagged 'geometry | distances'). Erdős and Purdy [ErPu71] proved $$n^2\log\log n \ll g(n) \ll n^{5/2},$$ the lower bound from a lattice construction, and believed the lower bound is closer to the truth. The upper bound has been repeatedly improved — Pach–Sharir [PaSh92], Dumitrescu–Sharir–Tóth [DST09], Apfelbaum–Sharir [ApSh10], Apfelbaum [Ap13] — with the current record $$g(n)\ll n^{20/9}$$ by Raz and Sharir [RaSh17]; the gap between $n^2\log\log n$ and $n^{20/9}$ is wide open. In higher dimensions: Erdős–Purdy [ErPu71] proved $g_3^2(n)\ll n^{8/3}$, improved by Dumitrescu–Sharir–Tóth [DST09] to $g_3^2(n)\ll n^{2.4286}$; Erdős–Purdy proved $g_6^2(n)\gg n^3$; Purdy [Pu74] proved $g_4^2(n)\leq g_5^2(n)\ll n^{3-c}$ for some $c>0$; and an observation of Oppenheim using the Lenz construction gives $g_{2k+2}^{k}(n)\geq (\tfrac{1}{(k+1)^{k+1}}+o(1))n^{k+1}$, which Erdős and Purdy conjecture is best possible. Related site problems: the unit distance problem (erdosproblems.com/90) and Erdős #755. The attacker's tool: incidence-geometry (Elekes–Sharir framework, polynomial partitioning) for upper bounds, and computational construction — exact same-area-triangle counting over lattice sections and perturbed families to hunt for constructions provably beating $n^2\log\log n$, plus certified extremal counts for small $n$.

References

RefSourceType
REF-01 Erdős Problem #1086 (T. F. Bloom) website

Investigations · 0

No published investigations yet. This problem is unclaimed territory.