Heilbronn Triangle Problem: A Tiny Exponent Overturns Decades of Geometric Belief

Put four dots at the corners of a unit square. Whichever three you join, the triangle covers half the square. With a million dots, how much area can you guarantee for the skinniest triangle? The Heilbronn triangle problem asks how well the best arrangement can do as the number of dots grows. OpenAI’s September 2026 manuscript proves that, for every sufficiently large point count, some arrangement beats the classical inverse-square scale by a fixed positive power. The paper’s explicit exponent is about 3.18×10−2363.18\times 10^{-236}. It stays fixed as the point count grows.

1. What Is the Heilbronn Triangle Problem?

	In the Heilbronn triangle problem, moving one corner to the center drops the minimum area from one-half to zero.
In the Heilbronn triangle problem, moving one corner to the center drops the minimum area from one-half to zero.

Choose a set PP of n≥3n\ge 3 distinct points in the closed unit square. Write Δ(P)\Delta(P) for the least area among all triangles with three different vertices in that set. Now allow the points to move and call the largest attainable value Δ(n)\Delta(n). You choose the arrangement. Someone who sees your choice picks the worst triple.

Each lower bound is a guarantee for every triple in one arrangement.
Key factHeilbronn’s problem in the unit square
QuantityBest achievable minimum triangle area among nn points.
Manuscript resultΔ(n)≥c1n−2+η\Delta(n)\ge c_1n^{-2+\eta} for every sufficiently large nn.
Lean scopeA fixed positive power gain at arbitrarily large sizes.
Open questionThe exact rate at which the optimum shrinks.

Each triangle in the four-corner example has unit base and height, so the minimum is 1/21/2. Move the top right corner to the centre. The centre lies on the diagonal between the two opposite corners. The minimum drops to zero even though all three points on that diagonal are distinct and well separated.

2. The Heilbronn Conjecture and Four Decades of Limited Progress

Heilbronn conjectured an upper bound of O(n−2)O(n^{-2}). Erdős showed why that scale looked plausible. For an odd prime pp, take the points with coordinates xx and the least nonnegative residue of x2x^2 modulo pp, with 0≤x<p0\le x<p. No line meets the finite-field parabola in three distinct points. Back on the integer grid, twice the area is therefore a nonzero integer. Dividing both coordinates by pp gives a minimum area of at least 1/(2p2)1/(2p^2) for pp points.

In 1982, Komlós, Pintz and Szemerédi gained a factor of log⁡n\log n. As in the study of square-difference-free sets, the question became how large a set could avoid a forbidden pattern. They made each small triangle an edge of a hypergraph on the sampled points. Removing short cycles then let them extract a larger independent set, a subset containing no forbidden triple. This disproved the original conjecture. A weaker prediction survived because a logarithm grows more slowly than every fixed positive power.

3. OpenAI’s New Lower Bound: What the Tiny Exponent Changes

	Three lower bounds for the Heilbronn triangle problem show constant, logarithmic, and power gains over n⁻².
Three lower bounds for the Heilbronn triangle problem show constant, logarithmic, and power gains over n⁻².

Theorem 1.1 of the manuscript gives absolute constants c1,η>0c_1,\eta>0 and an integer n0≥3n_0\ge 3 such that, for every integer n≥n0n\ge n_0,

𝚫(𝒏)≥𝒄1𝒏−2+𝜼\boldsymbol{\Delta(n)\ge c_1 n^{-2+\eta}}

Multiply the guaranteed area by n2n^2. On this scale Erdős reaches a constant, Komlós and colleagues reach a logarithm, and OpenAI reaches a power. Squaring the point count doubles the logarithm. For the power, the multiplier is nηn^\eta itself, which eventually exceeds any fixed number.

What changes when the point count is squared?
How the gain above inverse-square changes when the point count is squared At a reference size where the fixed power factor equals four, the gain multiplies by one for the parabola, two for the 1982 logarithmic construction and four for the 2026 power construction. Each bar starts at zero. 0 1 2 3 4 Erdős Parabola 1× 1982 Logarithmic gain 2× 2026 Power gain 4× Multiplier of the gain
Growth of the gain over n−2n^{-2} when the point count is squared. At nη=4n^\eta=4, a constant stays fixed, a logarithm doubles and a power quadruples. Bars compare growth laws, independently of unknown constants.

The relaxed Heilbronn conjecture allowed a different constant CεC_\varepsilon for every ε>0\varepsilon>0 and predicted Δ(n)≤Cεn−2+ε\Delta(n)\le C_\varepsilon n^{-2+\varepsilon} eventually. Choose ε=η/2\varepsilon=\eta/2. The ratio of the new lower bound to that proposed upper bound is (c1/Cε)nη/2(c_1/C_\varepsilon)n^{\eta/2}, which grows without limit. The conjecture required this instance to hold.

4. Inside OpenAI’s Proof: A Six-Stage Roadmap

OpenAI attributes the results in its October release to an internal frontier model. These stages reconstruct the manuscript’s logic. Their order reflects dependencies between lemmas.

  1. Projective representation. Give each planar point three integer coordinates. The third acts as a denominator, letting one integer determinant measure the area of a projected triangle.
  2. Finite-field encoding. Give each column a label. Encode a test for three different labels in the digits of the columns, so a small determinant can occur only when labels repeat.
  3. Lattice counting. For repeated labels, count the lifts, the integer columns with the prescribed residues, that realize each small nonzero determinant, allowing for unequal spacing in different directions.
  4. Auxiliary congruence. At determinant zero, whole planes of possibilities survive. A second modulus excludes short relations among distinct residues and controls the remaining planes.
  5. Random sampling. Combine the two restrictions and sample their integer lifts. A weighted count converts the arithmetic information into a probability for one troublesome triple.
  6. Deletion and normalization. Start with twice the desired number of columns. Delete the violations, project the survivors and translate the determinant threshold back into area.

5. Turning Triangle Areas Into Integer Determinants

	A worked example uses a determinant to compute a triangle area of 3/20 in the Heilbronn triangle problem.
A worked example uses a determinant to compute a triangle area of 3/20 in the Heilbronn triangle problem.

Draw the ray from the origin through the tip of an integer column u=(u1,u2,u3)𝖳u=(u_1,u_2,u_3)^{\mathsf T}. It meets the plane of height one at planar coordinates (u1/u3,u2/u3)(u_1/u_3,u_2/u_3). The construction takes 0≤u1,u2<N0\le u_1,u_2<N and N≤u3<2NN\le u_3<2N, so every projected point lies in the unit square. Proportional columns land at the same point and must be counted separately.

Put three columns in a matrix AA, and call their projected points p1,p2,p3p_1,p_2,p_3. Dividing each column by its last entry makes the bottom row all ones. Subtract the first normalized column from each of the other two. Expanding along the bottom row leaves the planar determinant of two edge vectors, whose absolute value is twice the area. Undoing the divisions gives

Area⁡(𝒑1𝒑2𝒑3)=|det⁡𝑨|2𝑨31𝑨32𝑨33\boldsymbol{\operatorname{Area}(p_1p_2p_3)=\frac{|\det A|}{2A_{31}A_{32}A_{33}}}

For example, use columns (0,0,4)(0,0,4), (3,0,6)(3,0,6) and (0,3,5)(0,3,5). Their determinant is 3636. The projected triangle has base 1/21/2 and height 3/53/5, giving area 3/203/20. The formula returns the same value, 36/(2⋅4⋅6⋅5)36/(2\cdot4\cdot6\cdot5). The bounded heights let one threshold protect every retained triangle.

6. Finite Fields, Field Norms and the Determinant Obstruction

The first restriction borrows Erdős’s parabola but asks more of it. Give each column an independent uniform label ξ\xi in the field K=𝔽rdK=\mathbb F_{r^d}, where rr is a growing odd prime and d=41d=41. For the columns (1,ξ,ξ2)𝖳(1,\xi,\xi^2)^{\mathsf T}, the Vandermonde determinant is the product of the three pairwise label differences, taken in index order. Distinct labels make every factor nonzero.

The field norm multiplies the determinant by its conjugates under the map t↦trt\mapsto t^r. The product lies in the base field and remains nonzero. Exchanging two columns reverses the sign of each conjugate. Because there are an odd number of factors, their product also changes sign. This alternating polynomial can therefore be grouped into a sum of determinants of monomials. Degree 41 supplies an odd number of factors and a collision probability small enough for deletion.

How does a nonzero field element guarantee a large integer? Write each matrix entry in a large prime base BB, using kk digit positions. Positions in the three rows are chosen so that only matched monomial terms contribute modulo rr to the coefficient of Bk−1B^{k-1}. That coefficient recovers the norm modulo rr. Higher powers disappear modulo h=Bkh=B^k, and the sum of all lower terms is too small to cancel the designated term. The paper bounds the entire signed representative below h/2h/2 in absolute value. Thus no representative can fall within distance τ=⌊Bk−1/2⌋\tau=\lfloor B^{k-1}/2\rfloor of zero when the labels are distinct.

7. Lattice Counting and the Exceptional Triple Problem

The probability that at least two labels coincide is at most 3/rd3/r^d. That saving could disappear if colliding labels overwhelmingly produced bad matrices. The digits retain randomness even after the labels are fixed. Each required residue modulo rr admits r9r^9 choices per digit, and separate columns draw afresh.

A common random matrix of determinant one mixes the rows modulo hh. It preserves the determinant and makes the residue matrix uniform over its special-linear orbit, the set of matrices reachable by these row changes. Smith normal form reduces the original digit matrix to diagonal entries 1,D,E1,D,E up to invertible operations. The allowed integer rows form a lattice of index I=DEI=DE. Its successive minima measure the radii at which one, two and finally three independent lattice directions become available.

For a prescribed nonzero determinant, two independent columns fix a plane direction. The determinant equation confines the remaining column to a parallel plane. Separate radii account for thin regions where all available lattice points lie on one line. For rows of length at most 4N4N, the count for each nonzero determinant is O(N6(log⁡(2N))2/I2)O(N^6(\log(2N))^2/I^2). Combining it with the orbit size leaves a factor DD. A large value requires every two-by-two minor to share a large power of the base. Its conditional expectation is at most two even for a fixed triple of repeated labels, once rr is sufficiently large. Averaging therefore preserves the collision saving.

8. The Second Congruence Condition: Eliminating Collinear Triples

Random matrix singularity has a geometric meaning here. A matrix of determinant zero with distinct projected points has rank two. The columns satisfy an integer relation Ax=0Ax=0, where the entries of xx have greatest common divisor one and xx is unique up to sign. All three rows lie in the rank-two lattice cut out by that relation.

At a second prime qq, take a patch of the quadratic surface z=x2−νy2z=x^2-\nu y^2 with ν\nu a nonsquare modulo qq. A nonvertical line meets the full surface at most twice because substitution gives a genuine quadratic. A vertical line meets the surface once. A translated patch in a small box thus supplies a cap, a set with no three distinct points on an affine line.

For three distinct cap points this already excludes short nontrivial relations whose coefficients sum to zero. When the sum is nonzero, translating all three points changes the relation. The proof restricts the translation’s first coordinate so that no short coefficient sum can cancel the patch’s small coordinates. A random invertible linear map mixes the residues while preserving these exclusions. Long relations are counted by grouping primitive vectors by length. When two residues coincide, the equality usually confines the rows to a thinner lattice. The exceptional relations where it fails to do so are counted separately.

9. Combining the Two Modular Constructions

Since hh and qq are coprime, the Chinese remainder theorem combines any two prescriptions into one residue class per coordinate modulo hqhq. With N=(hq)10N=(hq)^{10}, each column has exactly (N/(hq))3(N/(hq))^3 lifts in the sampling box. Columns are sampled independently conditional on the shared transformations. Averaging over those transformations introduces dependence.

The exact lifting identity assigns each admissible matrix a probability proportional to its auxiliary weight, the probability that all three residues belong to the random cap multiplied by (q3/s)3(q^3/s)^3, where ss is the cap’s size. If the digit matrix has orbit 𝒪\mathcal O, a matrix in that orbit modulo hh receives weight W(A)W(A) times h9/(N9|𝒪|)h^9/(N^9|\mathcal O|). Since 2τ<h2\tau<h, at most one integer in the bad interval has the required determinant residue. Applying the counts to that value and averaging over collisions gives Corollary 6.4.

Pr⁡(bad triple)≪𝒉(log⁡(2𝑵))2𝑵3𝒓𝒅\boldsymbol{\Pr(\text{bad triple})\ll\frac{h(\log(2N))^2}{N^3r^d}}

Here “bad” means three distinct projected points with |det⁡A|≤τ|\det A|\le\tau. The inequality hides a constant independent of the growing prime. A label collision supplies the factor r−dr^{-d}.

10. From Random Samples to a Power Improvement

For each large prime rr, set nr=⌊rN3/τ⌋n_r=\lfloor r\sqrt{N^3/\tau}\rfloor and draw 2nr2n_r columns. Count proportional pairs and bad triples. Linearity of expectation allows the counts to be added even when two violations share a point. After division by nrn_r, the triple contribution is bounded by a constant times (log⁡r)2r−9(\log r)^2 r^{-9}. The sample size contributes r2r^2, the ratio h/τh/\tau costs at most a constant times r30r^{30}, and label collisions supply r−41r^{-41}. The pair contribution also tends to zero.

Some sample thus has fewer than nrn_r violations. Mark one index in each and delete the marked indices. Every offending configuration loses a vertex, and removing points cannot create a triple. Let PrP_r consist of the projections of any nrn_r survivors. Their triangles have area at least τ/(16N3)\tau/(16N^3), giving nr2Δ(Pr)≥r2/64n_r^2\Delta(P_r)\ge r^2/64. The size nrn_r lies between fixed positive multiples of r45435k+16r^{45435k+16}, so the gain of r2r^2 becomes a power of the point count with exponent

𝜼=245435𝒌+16\boldsymbol{\eta=\frac{2}{45435k+16}}

Finally, a prime between a sufficiently large integer and its double supplies a constructed size between the desired nn and a fixed multiple of nn. Discarding the surplus preserves the area guarantee and costs only a constant in the bound. This proves the manuscript’s conclusion for every sufficiently large integer.

11. What the Lean Proof Actually Verifies

OpenAI’s formalization notes describe a sequence of point counts tending to infinity. At each count in that sequence, all triangles in a certified configuration meet a power lower bound. The public comparator statement specifies 1/(100000k)1/(100000k), a smaller exponent than the manuscript’s. It also states the failure of the relaxed upper bound at half the formal exponent.

Why does a sequence suffice? Suppose someone proposes a constant and a cutoff for their upper bound. Along the certified sequence, the ratio of the lower bound to the proposed bound grows without limit at that choice of exponent. Eventually a member exceeds the cutoff and defeats the constant. Covering every sufficiently large count is a stronger existence statement, and the original manuscript obtains it through the prime-interval argument.

12. The New Limits of the Heilbronn Triangle Problem

In the opposite direction, Alex Cohen, Cosmin Pohoata and Dmitrii Zakharov proved an upper bound of Oε(n−7/6+ε)O_\varepsilon(n^{-7/6+\varepsilon}) for every ε>0\varepsilon>0. Their incidence bound forces a small triangle in every arrangement. OpenAI builds arrangements that keep every triangle above a smaller threshold. The bounds leave the exact rate of decay undetermined.

The tiny exponent reflects the cost of encoding the norm. There are M=(4d−1d)M=\binom{4d-1}{d} degree-dd monomials in 3d3d variables. Grouping triples gives T=(M3)T=\binom{M}{3} possible terms, and reserving positions takes k=T2+1k=T^2+1. At degree 41, that fixed digit count already has 232 decimal digits. The manuscript makes no attempt to optimize it or to identify the best layout for a particular point count.

The Heilbronn triangle problem now asks how much further a construction can push that power gain before a small triangle becomes unavoidable. For a related question in combinatorial geometry, where the measurement is a distance and the objects are pairs, read Binary Verse AI’s guide to the unit distance problem.

What is the Heilbronn triangle problem?

How can you place nn points in the unit square to make the smallest triangle among all triples as large as possible? The optimum, Δ(n)\Delta(n), is the largest such minimum over all arrangements. Three collinear points give an arrangement a minimum area of zero.

What did OpenAI prove about the Heilbronn triangle problem?

OpenAI’s manuscript proves that there are absolute constants c1,η>0c_1,\eta>0 such that Δ(n)≥c1n−2+η\Delta(n)\ge c_1n^{-2+\eta} for every sufficiently large integer nn. For each such size, some configuration achieves the guarantee simultaneously for every triangle it contains.

Why is the new Heilbronn triangle lower bound significant?

The 1982 lower bound improved the inverse-square scale by a logarithm. The new construction gains a fixed power, nηn^\eta, which eventually outgrows any constant multiple of log⁡n\log n. Taking ε=η/2\varepsilon=\eta/2 therefore contradicts the relaxed conjecture’s proposed upper bound.

What mathematical techniques does OpenAI’s Heilbronn proof use?

The proof represents triangle areas by integer determinants. Finite-field norms and digit expansions rule out small determinants for triples with distinct labels. Lattice counts and a second modular condition control the exceptions, and probabilistic deletion removes the remaining bad pairs and triples.

Has OpenAI’s Heilbronn triangle problem proof been verified in Lean?

OpenAI’s Lean formalization establishes a fixed positive power improvement along a sequence of point counts tending to infinity. This suffices to disprove the relaxed conjecture. The manuscript also covers every sufficiently large point count through a prime-interval argument.

Is the Heilbronn triangle problem completely solved?

No. The proof disproves the relaxed conjecture and improves the lower bound. A gap remains between this construction and the upper bound that applies to every point set. The exact asymptotic size of the best possible minimum triangle area is still unknown.

Leave a Comment