← All problems

Heilbronn triangle problem

76 years old · traced to

For a compact set D⊆R2D\subseteq\mathbb{R}^2, an integer n≥3n\ge 3, and points p1,…,pn∈Dp_1,\dots,p_n\in D, let

m(p1,…,pn)=min⁡1≤i<j<k≤narea⁡(pipjpk),m(p_1,\dots,p_n)=\min_{1\le i<j<k\le n}\operatorname{area}(p_ip_jp_k),

where area⁡(pipjpk)\operatorname{area}(p_ip_jp_k) denotes the area of the triangle with vertices pi,pj,pkp_i,p_j,p_k, taken to be 00 when the three points are collinear. Define

ΔD(n)=max⁡p1,…,pn∈Dm(p1,…,pn),\Delta_D(n)=\max_{p_1,\dots,p_n\in D} m(p_1,\dots,p_n),

the maximum being attained because DD is compact and mm is continuous.

If DD and D′D' are compact convex sets of nonzero area, then there are constants 0<c≤C0<c\le C depending on DD and D′D' but not on nn such that

c ΔD′(n)≤ΔD(n)≤C ΔD′(n)for all n≥3,c\,\Delta_{D'}(n)\le\Delta_D(n)\le C\,\Delta_{D'}(n)\qquad\text{for all }n\ge 3,

since some affine image of D′D' is contained in DD and an affine map multiplies all triangle areas by a fixed factor. Consequently the growth rate of ΔD(n)\Delta_D(n), up to constant factors, does not depend on the choice of compact convex DD of nonzero area; write Δ(n)\Delta(n) for this common growth rate, and write Δ□(n)\Delta_\square(n) when DD is the unit square [0,1]2[0,1]^2.

Determine the asymptotic behaviour of Δ(n)\Delta(n) as n→∞n\to\infty: exhibit an explicit function ff with Δ(n)=Θ(f(n))\Delta(n)=\Theta\bigl(f(n)\bigr). In particular, determine whether the limit

α=lim⁡n→∞log⁡(1/Δ□(n))log⁡n\alpha=\lim_{n\to\infty}\frac{\log\bigl(1/\Delta_\square(n)\bigr)}{\log n}

exists, and determine its value, i.e. determine the least exponent α\alpha such that Δ(n)=n−α+o(1)\Delta(n)=n^{-\alpha+o(1)}.

References
  1. Wikipedia, Heilbronn triangle problem, the article this problem comes from.

Source: Wikipedia

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 1

Claimed by OpenAI. For absolute constants eta>0 and c>0 and every sufficiently large n, the manuscript claims n points in the unit square for which every triangle has area at least c*n^(-2+eta). This gives a lower bound for the page’s extremal triangle area and rules out an exponent of two if its requested limit exists. It does not determine the exact asymptotic order or establish that the exponent limit exists.See full solutionHide full solution