Thin boundary faces in Erdős–Oler packings

Use the centre formulation in the research note. Let n=(k+1)(k+2)/2−1n=(k+1)(k+2)/2-1 centres at pairwise distance at least one fit in an equilateral triangle Δ\Delta of side L<kL\lt k. The argument below gives necessary conditions for such a configuration. It uses the area normalisation B(T)=4area(T)/3B(T)=4\operatorname{area}(T)/\sqrt3, so a unit equilateral triangle has B=1B=1.

All three corners can be occupied

A corner cap of size rr is the equilateral triangle of side rr cut off by a line parallel to the opposite side. Let rr be the smallest size of the closed cap containing a centre at a given corner. The convex hull of the centres is contained in the original triangle with the interior of this cap cut off. The perimeter of the truncated triangle is 3L−r3L-r, and its normalised area is L2−r2L^2-r^2. By Oler's inequality,

2n≤L2−r2+3L−r+2.2n\le L^2-r^2+3L-r+2.

As 2n=k2+3k2n=k^2+3k and L<kL\lt k, this gives r+r2<2r+r^2\lt2. In particular there is a centre PP at distance less than one from the corner VV. Any other centre QQ must have |Q−V|≥1|Q-V|\ge1. Indeed, two points at distances strictly less than one from VV and angular separation at most 60∘60^\circ have distance strictly less than one by the cosine rule. Also

|Q−V|2−|Q−P|2=2(P−V)⋅(Q−V)−|P−V|2≥0,|Q-V|^2-|Q-P|^2 =2(P-V)\cdot(Q-V)-|P-V|^2\ge0,

since the angle is at most 60∘60^\circ and |Q−V|≥1>|P−V||Q-V|\ge1\gt |P-V|. Thus PP may be moved to VV without losing separation. Apply the argument successively to the three corners. For k≥2k\ge2 any packing of nn points must have L>1L\gt1, since at most the three vertices can have pairwise distances at least one in side one. The relocations therefore preserve any corner already occupied. The case k=1k=1 cannot give a counterexample by the diameter bound. Henceforth assume all corners are occupied.

Exterior Delaunay faces point to boundary edges

The packing is saturated in Δ\Delta. A point at distance at least one from every centre would give the complete triangular number in side L<kL\lt k, contradicting Oler's bound. Fix a Delaunay triangulation of the centres, including every centre on a straight hull side. Call a face exterior here if its circumradius exceeds one. Its circumcentre lies outside Δ\Delta by saturation, so the face is obtuse. Its longest side is unique, and the circumcentre is on the other side of that edge from the obtuse vertex.

For each exterior face, point across its longest edge, using the adjacent triangle if the edge is interior and stopping otherwise. If the face has largest angle θ>90∘\theta\gt90^\circ, the opposite angle ϕ\phi across this edge obeys ϕ≤180∘−θ\phi\le180^\circ-\theta, by the Delaunay condition. The two circumcentres lie on the same side of the edge, and the new radius is at least the old radius because sinϕ≤sinθ\sin\phi\le\sin\theta. Thus the next face is also exterior and hence obtuse. Its longest edge is strictly longer than the shared edge, because the angle ϕ\phi opposite the shared edge is acute. These arrows cannot form a cycle. Each exterior face reaches a boundary edge.

Let e=ABe=AB be this boundary edge on a given side. The path of circumcentres, with successive centres joined along the dual Voronoi edges, stays in the exterior of Δ\Delta. The distance to the nearest packing centre along each such segment is at least the smaller endpoint radius, since the segment lies on one side of the associated Delaunay edge and moves away from its midpoint. Degenerate dual segments from cocircular faces obey the same statement. Thus every point on the path has at least two nearest centres and distance greater than one from them.

An exterior point whose orthogonal projection on Δ\Delta is an occupied corner has that corner as its unique nearest centre. The same holds for an exterior point that projects to any occupied point of a side. The Voronoi path can therefore exit neither the slab projecting to the relative interior of the given side nor the portion of the slab projecting to the open interval ABAB. The terminal circumcentre is in that portion because it is across an edge of the side and projects to its midpoint. A centre outside the vertical strip over ABAB cannot be tied for nearest to a point in the slab, because AA or BB would be closer. All vertices of every face reaching ee are consequently in that strip. They are also at distance less than one from the side. Indeed, a circumcentre OO at distance hh from its projection on the side has radius R<h+1R\lt h+1 by saturation at the projection, so the part of its circumcircle inside Δ\Delta has height at most R−h<1R-h\lt1.

A bound on total area of deficient faces

For a face with side lengths a,b,ca,b,c where cc is largest, write t=a+b−ct=a+b-c. Heron's formula and a,b,c≥1a,b,c\ge1 imply B(T)2≥tB(T)^2\ge t, since the other factors are a+b+c≥3a+b+c\ge3 and c2−(a−b)2≥abc^2-(a-b)^2\ge ab in the square of the normalised area. The triangle inequality and the same formula also give B(T)≥tB(T)\ge t: the other factors satisfy a+b+c≥3ta+b+c\ge3t and c2−(a−b)2≥ab≥1c^2-(a-b)^2\ge ab\ge1, since t≤min(a,b)t\le\min(a,b). Every face of circumradius at most one has B(T)≥1B(T)\ge1, by the sine-law argument in the research note.

On an exterior face, the edge excesses |e|−1|e|-1 give the identity

1−B(T)=(c−1)−(a−1)−(b−1)−(B(T)−t).1-B(T)=(c-1)-(a-1)-(b-1)-(B(T)-t).

Each positive excess on an outgoing interior edge cancels one negative excess in the next face. The remaining positive excesses occur on distinct hull edges. Write bb for the number of hull edges, P=3LP=3L for the hull perimeter and F=2n−b−2F=2n-b-2 for the number of triangles. The total edge excess on the hull is P−bP-b. Summing gives

∑T exterior(B(T)−t(T))+∑T of radius ≤1(B(T)−1)≤L2+3L+2−2n<2.\sum_{T\text{ exterior}}(B(T)-t(T)) +\sum_{T\text{ of radius }\le1}(B(T)-1) \le L^2+3L+2-2n\lt2.

The cancellation can be performed on each side separately, by assigning each exterior face to the side of its terminal edge. Let bjb_j count the boundary edges on side jj and let DjD_j be the sum of 1−B(T)1-B(T) over the exterior faces assigned to it. Then Dj≤L−bjD_j\le L-b_j. The sum of the three nonnegative quantities L−bj−DjL-b_j-D_j is at most L2+3L+2−2nL^2+3L+2-2n, since every face of radius at most one has nonpositive deficit. A side with no deficient face assigned to it costs at least L−bj≥L−k+1L-b_j\ge L-k+1 in this sum. Writing δ=k−L>0\delta=k-L\gt0, two such sides would cost at least 2−2δ2-2\delta, while the available total is 2−δ(k+L+3)<2−2δ2-\delta(k+L+3)\lt2-2\delta. Thus at least two distinct sides must have deficient faces assigned to them. If there is a side without any, it must have exactly k−1k-1 boundary edges, since a side with bj≤k−2b_j\le k-2 would alone cost more than the available total.

A deficient face has B(T)<1B(T)\lt1 and largest angle θ>120∘\theta\gt120^\circ. The latter follows from B(T)=(2/3)absinθB(T)=(2/\sqrt3)ab\sin\theta, since a,b≥1a,b\ge1 and θ≥60∘\theta\ge60^\circ. For such a face, a+b+c≥2+3a+b+c\ge2+\sqrt3 and c2−(a−b)2=2ab(1−cosθ)≥3abc^2-(a-b)^2=2ab(1-\cos\theta)\ge3ab. Hence

B(T)2≥(2+3)t(T),B(T)−t(T)≥(3−1)B(T).B(T)^2\ge (2+\sqrt3)t(T),\qquad B(T)-t(T)\ge (\sqrt3-1)B(T).

Thus the sum of the normalised areas of all deficient faces is less than 1+31+\sqrt3, uniformly in kk.

A necessary angle and area bound

Set d=3k−bd=3k-b. The hull boundary lemma gives d≥3d\ge3. The aggregate deficit of the Delaunay triangles is

∑T(1−B(T))=2n−b−2−L2>d−2.\sum_T(1-B(T))=2n-b-2-L^2\gt d-2.

For a deficient face, t≤B(T)2/(2+3)<1t\le B(T)^2/(2+\sqrt3)\lt1. For any exterior face with B(T)≥1B(T)\ge1, the inequality 1−B(T)≤κ(1−t)1-B(T)\le\kappa(1-t) holds for every 0≤κ≤10\le\kappa\le1. This is immediate if t≤1t\le1, and follows from B(T)≥tB(T)\ge t if t>1t\gt1. So if κ\kappa bounds the ratios (1−B(T))/(1−t)(1-B(T))/(1-t) on all deficient faces, the outgoing-edge cancellation gives

d−2<∑T(1−B(T))≤κ(P−b)<κd. d-2\lt\sum_T(1-B(T))\le\kappa(P-b)\lt\kappa d.

In particular κ>1−2/d\kappa\gt1-2/d. Each deficient face satisfies

1−B(T)1−t≤1−B(T)1−B(T)2/(2+3)≤1−(3−1)B(T).\frac{1-B(T)}{1-t} \le \frac{1-B(T)}{1-B(T)^2/(2+\sqrt3)} \le 1-(\sqrt3-1)B(T).

Hence some face has normalised area less than (1+3)/d(1+\sqrt3)/d. With the notation above, its longest edge has c=a+b−t≥2−tc=a+b-t\ge2-t, so its terminal hull edge has length greater than 2−(1+3)2/((2+3)d2)=2−2/d22-(1+\sqrt3)^2/((2+\sqrt3)d^2)=2-2/d^2.

For the angle bound, the ratio at largest angle θ\theta is at most

q(θ)=1−(2/3)sinθ2sin(θ/2)−1.q(\theta)=\frac{1-(2/\sqrt3)\sin\theta}{2\sin(\theta/2)-1}.

To see this, put t0=2−2sin(θ/2)t_0=2-2\sin(\theta/2) and B0=(2/3)sinθB_0=(2/\sqrt3)\sin\theta, the values at a=b=1a=b=1. The identity t/(ab)=2(1+cosθ)/(a+b+c)t/(ab)=2(1+\cos\theta)/(a+b+c) gives t/(ab)≤t0t/(ab)\le t_0, since cc is increasing in either side for this obtuse angle. With q=(1−B0)/(1−t0)q=(1-B_0)/(1-t_0), therefore B(T)−qt≥ab(B0−qt0)=ab(1−q)≥1−qB(T)-qt\ge ab(B_0-qt_0)=ab(1-q)\ge1-q. Also q(θ)q(\theta) increases from zero to one on [120∘,180∘][120^\circ,180^\circ]. For fixed 0≤q≤10\le q\le1, the derivative of (2/3)sinθ−q(2−2sin(θ/2))(2/\sqrt3)\sin\theta-q(2-2\sin(\theta/2)) is strictly negative in the interior of that interval. This proves monotonicity by the defining equation B0−qt0=1−qB_0-qt_0=1-q. The largest angle of some face must satisfy q(θ)>1−2/dq(\theta)\gt1-2/d. In particular it exceeds the unique angle solving q(θ)=1/3q(\theta)=1/3, which is between 142∘142^\circ and 143∘143^\circ.

The localisation and area budget leave a geometric obstruction to settle. A boundary edge just shorter than two can support a single deficient triangle of very small area, so the cancellation alone does not rule out several short slivers on different sides.