The densest packing of a shape that is not a disc

The densest lattice in the plane settles the question for discs, and it settles it completely: every lattice has one reduced form, the reduced forms fill a bounded region with a corner, the density is monotone across the region, and the maximum is at the corner. The proof finishes.

Replace the disc with a pentagon and every step of that argument survives except the last. There is still one reduced form per lattice, the region is still bounded, and the question is still finite — but the density is no longer monotone, the maximum is not at a corner, and there is no closed form waiting at the end of it. What is left is a genuine search, and the honest way to report a search is with its resolution attached.

Two shapes overlap for one reason #

The reduction that makes any of this computable is short and complete.

Two translates of a convex body K, at positions differing by a vector v, overlap exactly when some point of K equals some other point of K shifted by v — which is to say exactly when v can be written as a difference of two points of K. The set of such v is the difference body

D = K − K = { a − b : a, b in K },

and it is convex, and it is centrally symmetric whatever K was, because a − b is in it whenever b − a is.

So a lattice L packs K by translation exactly when L meets the interior of D only at the origin. A lattice with that property is called admissible for D, and the packing question becomes: how small can det L be? That least determinant is D’s critical determinant Δ(D), and the packing density is area(K)/Δ(D).

The difference body is where a shape’s asymmetry goes. A pentagon is not centrally symmetric and its difference body is; a triangle’s difference body is a hexagon; a centrally symmetric shape’s difference body is simply twice itself. Everything after this step is a question about a symmetric convex body, which is why the same machinery answers all of them.

Three pairs, and the one that is easy to lose #

A critical lattice — one achieving the least determinant — has three pairs of points on the boundary of D. That is Minkowski’s, and it is what turns an unbounded minimisation into a search over two angles: take the first basis vector on the boundary, take the second on the boundary, compute the determinant.

That description is wrong in a way that is invisible until it is checked, and getting it wrong cost this file its first set of answers.

The three boundary contacts are at ±u, ±v and ±(u + v). Only two of the three are basis vectors. If v is placed on the boundary and u + v then lands inside D, the lattice is not admissible — and the response is not to discard that direction but to push v outward along its own ray until the lattice becomes admissible. The binding contact is then at u + v rather than at v, and v itself sits strictly outside the body.

A search that takes both basis vectors on the boundary and discards whatever fails admissibility throws away every critical lattice of that shape. The first version of this file did exactly that, and reported the regular pentagon at 0.817 by luck rather than by argument — the right number, reached by a search that could not have found it in general, and which gave visibly wrong answers elsewhere.

The correction is a bisection: admissibility is monotone in how far v is pushed out, because every lattice point containing a v moves outward and the multiples of u are untouched, so the least admissible scale is found by halving an interval.

The checks the search has to pass #

A search has no proof in it, so its credibility is entirely in what it is required to reproduce.

A shape that tiles the plane by translation must reach density one. The square and the regular hexagon do, and the search is not told that they tile — it finds a lattice of determinant exactly their area. That is the single most informative check available, because reaching one is the tightest possible constraint and there is nowhere for a small error to hide.

A density above one would be a packing that overlaps. None occurs.

The circle must come out at π/√12. Approximated by a 180-gon it comes out at 0.906992 against 0.906900, and the two computations have nothing whatever in common — one is a reduction argument over the region of reduced lattices, the other a sweep over boundary angles of a polygon with a hundred and eighty sides.

The triangle must come out at exactly two thirds, and it does, to six places. The reason is worth writing out because it is the one case where the whole chain is visible.

An equilateral triangle of area A has a difference body that is a regular hexagon of area 6A — six copies of the triangle, in the six orientations a hexagon has. A hexagon tiles the plane, and for a centrally symmetric body that tiles, the critical determinant is a quarter of its area: the critical lattice is half the tiling lattice in each direction, which is where the four comes from. So Δ = 6A/4, and the density is A/(6A/4) = 2/3, exactly.

Two of the shapes are one another’s difference bodies, and that makes their answers the same number twice. A pentagon’s difference body is a decagon; a centrally symmetric body’s own difference body is twice itself, so a decagon’s packing density is its area over four times its critical determinant. Taking the pentagon’s answer, rescaling it to circumradius one and running that identity predicts the decagon’s density to six decimal places — 0.913717, against the decagon’s own independently computed 0.913717.

And the regular octagon has a closed form. Its densest lattice packing has density (4 + 4√2)/(5 + 4√2) = 0.906164, and the search returns 0.906160. That is the only check on this page taken from outside the collection, and it is worth having for exactly that reason.

The one place the plane’s own arithmetic gets in #

There is a fact in the census that looks like a coincidence and is a theorem, and it is worth pulling out because it is the only place where the plane’s own crystallography touches this question.

The square and the hexagon reach one, and they are two of the five parallelohedra of the plane — the shapes whose translates tile — of which there are exactly two convex kinds: the parallelogram and the centrally symmetric hexagon. That is why the Wigner–Seitz cell is one of five kinds in space and one of two in the plane, and it is exactly the list of convex shapes for which this essay’s answer is one and the search has nothing to find.

Every other convex shape in the plane packs at density strictly below one, and the amount below is a number with no formula. So the census divides cleanly in two: two rows that are a classification theorem, and six rows that are measurements.

What the answers look like #

The pentagon is the interesting entry and it is interesting because it is the worst. A pentagon has an area 0.817 of the cell it needs, so nearly a fifth of the plane is unavoidably empty — while a heptagon manages 0.860 and an octagon 0.906, and a decagon 0.914, climbing towards the circle’s 0.907 from above and settling.

There is a pattern in the odd entries that is worth noticing and not worth over-reading. A pentagon reaches 0.817, a heptagon 0.860; the even ones sit between 0.906 and one. The gap narrows as the number of sides grows, which it must, since both sequences head for the circle’s 0.907 — the odd ones from below, the even ones from above.

The odd polygons do badly and the even ones well, and the reason is the difference body. An even polygon is centrally symmetric, so its difference body is a scaled copy of itself with the same number of sides. An odd one is not, so its difference body has twice as many sides and a shape the original does not have — a pentagon becomes a decagon, a triangle becomes a hexagon, a heptagon becomes a fourteen-gon. The shape that decides the packing is not the shape being packed.

And a rotation would change everything. Every number here is for translates only. The pentagon’s best packing when copies may be turned is about 0.921, achieved by two orientations differing by a half turn — a double lattice rather than a lattice — and no argument on this page reaches it. That is a real restriction and it is the right one for this collection: a crystal structure is a lattice of translates, and a molecule in a crystal sits at the positions one plane group’s operations put it, not at arbitrary angles.

What “critical” means, and why the answer is attained #

One thing about the definition is worth pausing on, because it is where an infimum quietly becomes a minimum.

The critical determinant is defined as an infimum over admissible lattices, and there is no immediate reason a smallest one should exist rather than being approached. It does exist, and Mahler’s compactness argument is why: the set of lattices with determinant below a bound and no short vectors is compact, so a minimising sequence has a convergent subsequence, and the limit is admissible because admissibility is a closed condition.

That matters here for a practical reason rather than a philosophical one. A search over a grid can only ever report a value it has reached, and if the answer were an infimum not attained, every grid step would return something strictly larger and the refinement would creep downward for ever without settling. The observed behaviour is the opposite — the digits stop moving — and that is the compactness showing through in the only form a computation can see it.

The same argument explains the three boundary contacts. At a minimum, the lattice cannot be deformed in any direction without either raising the determinant or losing admissibility, and a two-dimensional lattice has three degrees of freedom once the determinant is fixed — so three constraints are needed to pin it, and each constraint is a lattice point pressed against the boundary.

The resolution, stated #

Every density on this page is quoted to six decimal places and every one of them is stable across a fourfold change in the grid step, with a local refinement round the answer in each case. The seventh place is not stable and is not reported anywhere.

That is what a numerical answer looks like when it is being honest, and it is a different kind of statement from the rest of this collection. Every count on this site is an enumeration and every enumeration either closes or says at what bound it stopped. A density is neither: it is a real number approached from one side by a search, and the only available claim is this many digits, at this step size, stable under refinement. Saying so is the whole of the difference between a measurement and a result.

Where the exactness stops #

Computed here: the difference body of eight convex polygons as a Minkowski sum of edge lists; the critical determinant of each by a sweep over two boundary angles with the second vector’s scale bisected for admissibility; the admissibility test over a range computed from the body’s circumradius rather than chosen; and the same answers at four grid resolutions.

Nothing here is exact and the file says so throughout. The vertices of a regular polygon are cosines, the boundary intersections are solved by Cramer’s rule in floating point, and the admissibility test uses a tolerance. What is exact is the shape of the answers — a tiling shape must give one, a difference body must be centrally symmetric — and those are the checks.

The admissibility range is computed and that matters more than it sounds. A lattice point inside D has length at most D’s circumradius, so its index along each basis vector is bounded by that radius times the other vector’s length over the determinant. A fixed range instead of a computed one is how a degenerate lattice — two nearly parallel basis vectors, determinant near zero — passes the test: its short combination is outside any fixed window, and the search then reports a rank-one arrangement of vanishing determinant as the densest packing there is. That happened, the reported densities were in the thousands, and the fixed range was the cause.

Lattice packings only, and convex shapes only. A non-convex shape has a difference body that is not convex and the whole reduction fails at the first step; a packing allowing rotations is a different problem with different answers; and a packing by more than one shape is different again. All three are real questions and none of them is this one.

The 180-gon is not a circle. The circle’s row is computed by approximating it with a polygon, so its 0.906992 is a fact about that polygon and not about the circle. It sits four parts in ten thousand above π/√12, which is the right side to be on — a polygon inscribed in a circle packs slightly better than the circle, because it is slightly smaller in the directions that bind — and the agreement is a check on the search rather than a computation of π/√12. The disc’s answer is proved elsewhere and needs no search at all.

Eight shapes is eight shapes. The regular polygons were chosen because their answers can be checked against something, not because they are representative. Nothing here is a statement about convex bodies in general, and the one general statement in the area — that every centrally symmetric convex body packs at density at least 0.892 — is a theorem this file cannot see.

Who asked it, and what they wanted #

Minkowski built the theory of critical determinants in the 1890s, and he was not thinking about packing. He was doing number theory: a lattice point inside a convex body is a solution to a system of inequalities in integers, so a body containing no lattice point but the origin is a system with no non-trivial solution, and the critical determinant is the precise boundary between having solutions and not. His theorem — a symmetric convex body of area more than four times the determinant contains a non-zero lattice point — is the founding result of the geometry of numbers.

Reinhardt asked the packing question in 1934 in the form it takes here, and asked which centrally symmetric convex body packs worst. His conjectured answer is a smoothed octagon at 0.902414, and it is still open — one of the oldest unresolved questions in the subject, about a shape anyone can draw.

The pentagon’s story went the other way. Its best lattice packing is the number computed above; its best packing with turning allowed was conjectured for decades and proved optimal only in 2016, by an argument that runs to hundreds of pages of case analysis. The gap between those two numbers is the price of insisting on translation, and a crystal insists on it.

Where the ladder goes next #

Back, to the case where the argument finishes: the densest lattice in the plane, where reduction turns the question into a bounded region and the answer is at a corner.

Sideways, to the shapes that make the question trivial by tiling: which shapes tile by themselves, where the convex polygons that cover the plane with no gap are grown rather than tabulated.

And to the other extreme of the same measurement: covering and packing want different lattices, where the question is how little can be left over rather than how much can be fitted in — and where, unlike here, the two answers happen to agree.