The Cell Decomposition

The Cell Decomposition

The result the refiner rests on, stated so it can be checked.

Setup

Fix $n$$n$ unit squares. A configuration is

• a centre (xi​,yi​)∈R2$(x_i,y_i)\in {ℝ}^2$ and an angle θi​∈[0,π/2)${\theta }_i\in [0,\pi /2)$ for each square $i$$i$, and
• the container side $s$$s$,

so $3n+1$$3n+1$ real coordinates in all, which is 34 at $n=11$$n=11$.

The four corners of square $i$$i$ are (xi​,yi​)+Ri​⋅(±21​,±21​)$(x_i,y_i)+R_i·(\pm \frac{1}{2},\pm \frac{1}{2})$ where Ri​$R_i$ is rotation by θi​${\theta }_i$. Write oik​∈R2oik​∈R2oik​∈R2$o_{ik}\in {ℝ}^2$ for the four corner offsets, $k=1\dots 4$$k=1\dots 4$. Once θi​${\theta }_i$ is fixed the oik​oik​oik​$o_{ik}$ are constants, and every corner is an affine function of the centre alone.

Two squares have disjoint interiors exactly when some line separates them, and for convex polygons it suffices to test lines parallel to their edges. A square has two distinct edge normals (opposite edges are parallel), so a pair has four candidate axes; these too are functions of the angles alone.

Define a cell of the configuration space to be a choice, for each of the $C(n,2)$$C(n,2)$ pairs, of one candidate axis together with an order (which square lies on the low side). A configuration lies in a cell when that axis genuinely separates that pair in that order.

Statement

T-2. Fix the angle vector $\theta$$\theta$ and fix a cell $C$$C$. Then

minimise   s
subject to  the configuration lies in cell C and inside [0, s]²

is a linear program in the $2n+1$$2n+1$ variables (x1​,…,xn​,y1​,…,yn​,s)$(x_1,\dots ,x_n,y_1,\dots ,y_n,s)$.

Why

Four observations, each immediate once the angles are fixed.

1. Corners are affine in the centres. Corner $k$$k$ of square $i$$i$ is (xi​,yi​)+oik​(xi​,yi​)+oik​(xi​,yi​)+oik​$(x_i,y_i)+o_{ik}$ with oik​oik​oik​$o_{ik}$ constant.
2. Containment is linear. Each corner must satisfy 0≤xi​+oik,x​≤s0≤xi​+oik,x​≤s0≤xi​+oik,x​≤s$0\le x_i+o_{ik,x}\le s$ and 0≤yi​+oik,y​≤s0≤yi​+oik,y​≤s0≤yi​+oik,y​≤s$0\le y_i+o_{ik,y}\le s$. Note that $s$$s$ appears here, and only here, as a variable.
3. Separation along a fixed axis is linear. For axis $\nu$$\nu$ and order (i before j), separation says every corner of $i$$i$ projects at or before every corner of $j$$j$: ⟨ν,(xi​,yi​)+oik​⟩≤⟨ν,(xj​,yj​)+ojl​⟩⟨ν,(xi​,yi​)+oik​⟩≤⟨ν,(xj​,yj​)+ojl​⟩⟨ν,(xi​,yi​)+oik​⟩≤⟨ν,(xj​,yj​)+ojl​⟩$⟨\nu ,(x_i,y_i)+o_{ik}⟩\le ⟨\nu ,(x_j,y_j)+o_{jl}⟩$ for all $k,l$$k,l$. Since $\nu$$\nu$ is a constant vector, each is a linear inequality in four of the variables.
4. The objective is linear, being $s$$s$ itself.

The nonlinearity of the original problem is entirely in two places: the trigonometric dependence of oik​oik​oik​$o_{ik}$ and $\nu$$\nu$ on the angles, and the discrete choice of cell. Neither is present once both are fixed.

Note what the statement does not claim. The LP optimises within one cell. A different cell may have a lower optimum, and finding the best cell is the combinatorial part of the problem, which none of this makes easy.

A cell is not a basin, and this trap has been walked into

The statement above fixes the angles and a cell. A point-basin does not: it is the preimage of a quench endpoint, and the quench moves the angles and may cross cells. So a configuration can sit at exactly its fixed-angle cell optimum and still be far from its quench endpoint, with every remaining unit of gap in the angles and none of it in the centres.

Nor does a point-basin classify a flat terminal component

The section above separates a fixed-angle cell solve from the full quench. There is a second separation, discovered later and the harder of the two: the quench returns a point, while the terminal optimum need not be isolated.

Where the optimum is flat, two quenches into the same connected terminal component can legitimately stop at different places in it. Every symptom then mimics a real discovery—distinct coordinates, distinct geometric keys, two rows in the atlas—while the side agrees exactly and an open stratum can share one contact graph. Neither the key nor that graph alone decides component identity; wall strata can change inside the same connected family. That is D-034, and the shape of the error is the same as the cell/basin trap: an object that fixes more than the mathematics does, mistaken for the mathematics.

The consequence is a reading that looks safe and is not: a fixed-angle solve that stops improving has not converged to a local optimum of the problem—it has run out of things it is allowed to move. Watching it flatten and concluding “wrong basin” is exactly backwards, and it is what the right basin looks like when the residual is angular.

That is not hypothetical. Checking exp-001’s polish/exploration split, an agent built a probe doing one LP solve at fixed angles, called it “the quench”, and retracted a correct finding when it stalled (D-029). On exp-002’s seed 2:

“Quench” names all three stages—solve the cell, re-read the cell to a fixed point, refine the angles. The cell solve alone is one third of it and answers a different question. devtools.check_regressions pins this discrimination under D-029.

Two implementations, on purpose

The row count depends on how separation is written, and this directory now has both forms:

Both are correct formulations of the same feasible set, and neither shares constraint-assembly code with the other. That redundancy is deliberate, and it is the postmortem’s rule R1: a component checked against its own model of correctness is checked against the thing most likely to be wrong. D-014 happened precisely because the quench was validated only against its own constraint rows.

The instance: Trump’s cell

cases.trump11.independent_lp_cell reads the cell off sqpack’s exact certificate—eleven angles and fifty-five axis choices, and nothing else—rebuilds the LP from scratch, and solves it. The centres are never given to the solver. They are what it must reconstruct.

The cell, read off the exact certificate
  distinct angles:  [0.0, 40.18193729] deg
  tilted squares:   [6, 7, 8, 9, 10]
  axis choices:     55 pairs
  LP shape:         23 variables, 1056 constraints  (= 16 x (11 + 55))

Solving it, without telling the solver where the squares go
  LP optimum        s = 3.8770835900228136
  exact value       s = 3.8770835900228140
  |difference|        = 4.441e-16
  worst centre error  = 1.332e-15

sqpack.quench’s single-cell solve at the same angles agrees to the digit—4.441e-16, recorded as a mechanism result of exp-006. The cell containing Trump’s packing, solved as a linear program, is Trump’s packing, through two unrelated constraint sets.

What “exact” does and does not mean here

The formulation is exact; the build is not, and conflating the two caused a critical defect. Three corrections, recorded in the plan spec’s revision note:

• A float LP solver does not deliver the cell optimum. At its default primal feasibility tolerance of 10−7${10}^{-7}$ HiGHS returned a packing violating its own separation constraint by 9.876×10−8$9.876\times {10}^{-8}$, and so a side below Trump’s (D-014). Pinned at the solver’s floor of 10−10${10}^{-10}$, and with every returned solution post-checked against the constraints imposed on it, the residual in the side is about 10−11${10}^{-11}$. That floor is D-021, still open, and eight rounds sit on it.
• The polish step does not produce exact output. R-2 said it produced rational output; HiGHS returns floats. Exact output needs an exact LP over the cell’s certified rational or algebraic coefficients, which is unbuilt and tracked.
• A finite-precision LP endpoint remains a numerical result. Earlier records called this precision stage polished; that local label was retired because it says neither which arithmetic ran nor what precision was achieved. The method is numerical-f64, its actual tolerance and residual must be recorded, and it is only numerically checked. Formal promotion requires a separate exact or rigorous certificate that sqpack can replay.

Thirty-four dimensions become one

Trump’s packing uses two distinct angles: 0∘$0^{\circ }$ on six squares and a∗$a^{*}$ on five. Holding the cell fixed and varying the single free angle gives a function

φ(a) = the LP optimum of Trump's cell with the five tilted squares at angle a

which is the entire problem, restricted to this cell, in one variable.

A 2,001-point scan of [38∘,42∘]$[{38}^{\circ },{42}^{\circ }]$ puts the minimum at 40.182∘${40.182}^{\circ }$, one grid step (0.002∘${0.002}^{\circ }$) from a∗$a^{*}$.

Trump’s angle is not an input to this computation. It is the argument that minimises a one-dimensional function anyone can plot. For this structured cell, the centre coordinates remain LP variables and only one nonlinear angle parameter remains. This demonstrates a useful compression, not a theorem that angle-class count equals the local dimension of the full packing problem; other records already use more classes, and each reduction must be derived from its contact structure.