Axis-parallel square packing with an exact formula for optimal packing of seven squares
summary
The gist
The paper provides exact formulas and proofs for determining the minimum side length required to contain axis-parallel squares of prescribed side lengths…
In short
The research develops exact mathematical formulas for finding the minimum side length required to contain a set of axis-parallel squares. It provides specific expressions for packing up to seven squares, establishes sharp bounds on how many input side lengths define this optimal size, and proves that the best possible Euclidean Lipschitz constant is $\sqrt{n}-3$ for $n\ge 6$.
Key concepts
- L*(s)
- This function represents the smallest overall side length needed to fit a collection of axis-parallel squares with given side lengths. It is a key tool for quantifying the optimal packing size based on the input square dimensions.
- Theorem B
- This theorem states that for packing $n$ squares, the minimum required side length can always be expressed as a sum of at most $n-3$ of the input side lengths. This provides a sharp bound on how many inputs are necessary to define the optimal solution.
- Euclidean Lipschitz Constant
- This measures how much the packing size changes relative to small changes in the input square sizes. The paper proves this constant is exactly $\sqrt{n}-3$ for $n\ge 6$, meaning this value cannot be improved upon.
Terminology used across episodes
This episode discusses
- Axis-parallel square packing with an exact formula for optimal packing of seven squares · Paper Radio
The paper
Axis-parallel square packing with an exact formula for optimal packing of seven squares · Read on arXiv
Transcript
Introduction to the show: ident: Mathematics. The day in mathematics: new theorems, new proofs, and what they open.
Ada: We're looking at the paper: "Axis-parallel square packing with an exact formula for optimal packing of seven squares".
Emmy: Here's the gist of the paper. The paper provides exact formulas and proofs for determining the minimum side length required to contain axis-parallel squares of prescribed side lengths, specifically focusing on cases up to seven squares and establishing sharp bounds on how many input side lengths are needed to define this optimal packing size.
Ada: This research is significant because it moves beyond general area estimates by providing precise, exact mathematical expressions for this geometric optimization problem The Square Packing Function and Basic Properties The function L∗(s) denotes the smallest side length of an axis-parallel square that contains axis-parallel squares of side lengths s0, s1,...
Emmy: with pairwise disjoint interiors The exact formulas for the optimal side through seven squares are given in Theorem A For every n ≥ 6, the optimum for n squares is a sum of at most n − 3 of the prescribed side lengths The function L∗(s) is continuous on l↓2 in the l2 norm and satisfies L∗(s) − L∗ n(t) ≤ √n∥s - t∥2 for all s, t ∈ l↓2 Exact Formulas for Small Numbers of Squares The exact formulas through seven squares are as follows For five and six squares, L∗ 5(1.1)(s) = max(s0 + s1, s2 + s3 + s4), and L∗ 6(1.2)(s) = max(s0 + s1, s2 + s3 + s4, s1 + s4 + s5) For seven squares, L∗ 7(s) = maxL∗ 6(s), min
max(s3 + s4 + s5 + s6, s1 + s2 + s5), max(s0 + s5 + s6, s1 + s3 + s6), and (s1 + s4 + s5) Sharp Bounds on the Number of Sides in a Sum Theorem B states that for every n ≥ 6 and every s ∈ l↓2, there is a set I ⊆ 0,..., n − 1 with I ≤ n − 3 and L∗ n(s) = P i∈I si This bound is sharp on an open set of side lengths and yields the optimal Euclidean Lipschitz constant √n − 3 of the optimum as a function of the n side lengths Theorem 4.2 proves that if a representing set I has I ≥ n − 2, then L∗ n(s) = s0 + s1 Minimality of Convex Representations Lemma 6.1 states that every representation F = min1≤k≤m hk with convex hk on D requires m ≥ N Theorem 6.2 shows that for n = 6, 7, the least numbers m of real-valued convex functions h1,..., hm on l↓2 with L∗ n(s) = mink hk(s) for every s ∈ l↓2 are 1 and 3, respectively Seven Squares Analysis The three strategies for seven squares have costs defined by W = s3 + s4 + s5 + s6, H = s1 + s2 + s5, C0 = s0 + s5 + s6, C3 = s1 + s3 + sn−1, and R = sn−1 Proposition 5.5 proves that for every n ≥ 6 and every vector with positive entries, L∗ n(s) = F7(s) = min[ltop, lcenter, lright: Sharp Euclidean Lipschitz Constants Corollary 4.5 proves that for every n ≥ 6, L∗ n(s) − L∗ n(t) ≤ √n − 3∥s - t∥2 for all s, t ∈ l↓2 This constant √n − 3 cannot be decreased Theorem B Proof Together, Theorem 4.2, Theorem 4.3, and the two corollaries prove Theorem B The lattice representation theorem for continuous piecewise-linear functions on closed convex sets
Ovc02: expresses such a function as a finite maximum of minima of its linear components Acknowledgement of AI assistance This project began in June 2026, when I started actively looking for a formula for L∗ 6, and I obtained a complete proof of the formula for L∗ 7 in July 2026 Throughout this period I used Claude Opus 4.8 (Anthropic) as a research assistant The candidate formulas came from geometric intuition: I proposed arrangements of the squares, such as shelves, columns, and the configurations that became the three strategies in Figure 1.2 The AI system implemented exact solvers and exhaustive searches over integer side vectors that tested these candidates and returned counterexamples, whose optimal packings suggested further arrangements I designed the lower-bound method: assume that a packing has side below the asserted bound, use side sums exceeding that side to exclude chains, and follow the forced overlaps to a contradiction With the assistance of Claude Opus 4.8, this approach was refined into its present form, built from clearing sets, pins, cornering arguments, and a small number of lower bounds combined by arithmetic In preparing this manuscript, I used Claude Opus 5.5 (Anthropic) and GPT-6 Astra Pro to review the mathematical arguments and to improve the exposition Claude Opus 5.5 also assisted with typesetting, figures, and exact-arithmetic checks of the constructions I have checked all proofs and take full responsibility for the content of this paper References
Bad26: Matthew Badger, An exact formula for optimal axis-parallel packing of eight squares, Preprint, 2026
BS25: Matthew Badger and Raanan Schul, Square packings and rectifiable doubling measures, Discrete Analysis (2025), no.
Ada: 3, 40 pp
CKK+17: Josef Cibulka, Miroslav Korbel´aˇr, Jan Kynˇcl, Viola M´esz´aros, Rudolf Stolaˇr, and Pavel Valtr, On three measures of non-convexity, Israel Journal of Mathematics 218 (2017), no.
Title and authors: Ada: So we're looking at this paper now, titled "Axis-parallel square packing with an exact formula for optimal packing of seven squares." We need to talk about what that means in plain terms, beyond just the math.
Emmy: Yeah, I think the big deal here is that they are giving us exact formulas for finding the minimum side length required to fit a set of squares into a bigger square. It moves past just rough area estimates or general bounds.
Kolya: For me, it's interesting because they're focusing on up to seven squares, and the paper states that for any number of squares greater than six, say n greater than six, the optimal size is actually just a sum of at most n minus three of those input side lengths.
Ada: That bound itself is important. It tells us that we don't need to consider every single square when figuring out the best arrangement; we only need a small subset of them.
Emmy: And they even show us exactly which formulas are optimal for five and six squares, like the max of two different sums. But the real focus is on seven squares where things get much more complex, involving three specific strategies.
Kolya: I wonder what this structure implies for larger numbers of squares; if we can only use n minus three sides in our sum, how does that affect the complexity when you're dealing with a very long list of side lengths?
The paper's summary: Ada: So, to summarize what they did here in "Axis-parallel square packing with an exact formula for optimal packing of seven squares," they gave us precise mathematical expressions for the minimum container size. It shows that for seven squares, the optimal side length is determined by taking the minimum of three different types of sums involving those side lengths.
Emmy: Exactly, and they called these three strategies "top," "center," and "right." They give us specific formulas for each strategy, like one example shows a container size of thirty-eight when the input side lengths are twenty-two down to eight.
Kolya: What I find interesting is how they categorize these results. They show that for seven squares, the optimal size is actually just the minimum of three functions, not necessarily a simple maximum of two or three sums in a basic way.
Ada: That's right; they found that for seven squares, you have to check the top sum, and the center sum, and the right sum. They give us those specific costs defined by variables like W, H, C0, C3, and R.
Emmy: The paper also points out that this approach connects to broader ideas in geometry. They mention that for n greater than six squares, the optimum is a sum of at most n minus three side lengths.
Kolya: That relates back to the idea of finding the right structure; they're showing us that for these small numbers, there's a specific set of inputs that defines the best arrangement. It suggests that for seven squares, you can simplify the search space by focusing on these key sums.
The paper's improvements: Ada: The paper suggests a few key improvements to this area of research. First, they provide an exact formula for five and six squares, which is better than just having to rely on general area estimates or loose bounds.
Emmy: And the next big thing is how they establish sharp bounds on the number of sides needed in that sum. They prove there's a set of inputs we can pick from, let's call it I, where the size of that set I is at most n minus three.
Kolya: That bound on the number of sides is what really gives me pause probabilistically. If we know we only need to look at n minus three components, that drastically simplifies how we might approach finding solutions for very large n.
Ada: And they link this to something called the Euclidean Lipschitz constant. They prove that for any number of squares greater than six, the error in our estimate falls with the square root of n minus three times the square of the difference between two input sets.
Emmy: That constant, which is the square root n minus three times a factor related to those differences, is sharp; it cannot be made smaller. They show this constant is achieved on an open set of side lengths.
Kolya: It's interesting because they prove that if you try to use more than n minus two sides in your sum, the optimal size defaults back to just the sum of the first two side lengths, which is a very simple arrangement.
Conclusion: Ada: So, wrapping up on "Axis-parallel square packing with an exact formula for optimal packing of seven squares," we have exact formulas for five and six squares, and a specific structure involving three strategies for seven squares. This gives us concrete tools instead of just approximations.
Emmy: And the biggest structural improvement they offer is proving that the minimum number of side lengths you need to define that optimal size is at most n minus three, which is a very clean result.
Kolya: From a probabilistic view, it means we don't need an exponentially growing number of input constraints to nail down the optimum for seven squares; we have a fixed bound there.
Ada: Exactly. And they show that the error term in their approximation is governed by that square root n minus three term, which is as good as it gets for this problem.
Emmy: It's a solid piece of work because it provides these exact formulas and the structure of those three packing strategies for seven squares.
Kolya: I just think the focus on how the representation complexity scales with n is where it opens up new directions for us to explore, moving beyond just small fixed numbers like seven.
Ada: We'll keep an eye on what they do next, but this paper gives us a very strong foundation for understanding how these packing problems behave as you add more squares.
More episodes
- 2508.20749-Rates of convergence for extremal spacings in Kakutani's random interval-splitting process
- 2509.05860-Concentration Inequalities for Branching Random Walks
- 2509.19309-Small Prime Primitive Roots in Arithmetic Progressions
- 2509.21830-Noncollapsing for Curvature Flows with Inhomogeneous Speeds
- 2510.08346-Separability and Submetrizability in Locally Convex Spaces
- 2510.27290-Borel Combinatorics of Schreier Graphs of Z-actions
- 2511.13500-Sampling Density for Gabor Phase Retrieval
- 2511.19161-Linear dynamics of random products of weighted shifts
- 2511.21548-Metastability of diffusion processes in narrow tubes
- 2512.01536-Abelian approximations for bicrossed products