Axis-parallel square packing with an exact formula for optimal packing of seven squares

arXiv:2610.22622 · math.MG, math.CO · Submitted 2026-10-15 · Read on arXiv

Listen

Radio episode about this paper

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.

math.MG, math.CO

Submitted: 2026-10-15

Updated: 2026-11-10

Comments: v1: 24 pages, 6 figures (v2: strengthened Lemma 2.1 and Equation (2.5), streamlined several proofs)

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 92/100

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…

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

Summary

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. p. 0 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,... 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. p. 12)(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. p. 02 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. p. 72 shows that for n = 6, 7, the least numbers m of real-valued convex functions h1,. p. 0.., 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. p. 0 p. 03, 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. p. 22 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. p. 35 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. 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. 1, 331–369

[CLMM06] Alberto Caprara, Andrea Lodi, Silvano Martello, and Michele Monaci, Packing into the smallest square: Worst-case analysis of lower bounds, Discrete Optimization 3 (2006), 317–326

[Fri09] Erich Friedman, Packing unit squares in squares: A survey and new results, Electronic Journal of Combinatorics (2009), Dynamic Survey DS7, version of August 14, 2009

[Hou11] Stefan Hougardy, On packing squares into a rectangle, Computational Geometry 44 (2011), no. 8, 456–463

[LDH+13] Yan Lan, Gy¨orgy D´osa, Xin Han, Chenyang Zhou, and Attila Benk˝o, 2D knapsack: Packing squares, Theoretical Computer Science 508 (2013), 35–40

[LTW+90] Joseph Y.-T. Leung, Tommy W. Tam, C. S. Wong, Gilbert H. Young, and Francis Y. L. Chin, Packing squares into a square, Journal of Parallel and Distributed Computing 10 (1990), no. p. 0 3, 271–275

[MFNK96] Hiroshi Murata, Kunihiro Fujiyoshi, Shigetoshi Nakatake, and Yoji Kajitani, VLSI module placement based on rectangle-packing by the sequence-pair, IEEE Transactions on ComputerAided Design of Integrated Circuits and Systems 15 (1996), no. 12, 1518–1524

[MM67] J. W. Moon and L. p. 0 Moser, Some packing and covering theorems, Colloquium Mathematicum 17 (1967), 103–110

[MM68] A. Meir and L. p. 3 Moser, On packing of squares and cubes, Journal of Combinatorial Theory 5 (1968), 126–134

[Ovc02] Sergei Ovchinnikov, Max-min representation of piecewise linear functions, Beitr¨age zur Algebra und Geometrie 43 (2002), no. 1, 297–302

[SV20] Jannik Silvanus and Jens Vygen, Few sequence pairs suffice: Representing all rectangle placements, SIAM Journal on Discrete Mathematics 34 (2020), no. 4, 2017–2032

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 The components are the short sums just identified

Corollary 6.3 (Unit-container parameter sets)

The set X6 = s ∈ l↓2: L∗ 6(s) ≤ 1 is convex, whereas X7 = s ∈ l↓2: L∗ 7(s) ≤ 1 is a union of three convex subsets and is not a union of two convex subsets The convexity number of X7 is three

Corollary 4.5 (Sharp Euclidean Lipschitz constants)

Since finite minima and maxima preserve a common Lipschitz constant, Corollary 4.4 gives L∗ n(s) − L∗ n(t) ≤ √n − 3 X i<n(s i - t i) squared 1/2 ≤ √n − 3 s - t squared The constant √n − 3 cannot be decreased

Theorem 4.3 (Sharpness)

For every n ≥ 6, there is a nonempty open set U of strictly decreasing positive n-tuples such that, for all s ∈ l↓2 with (s0,..., sn−1) ∈ U, L∗ n(s) = Pn(s) = s1 + Xn−1 i=4 si and qn(s) = n − 3

Corollary 4.4 (Minimum-of-maxima formulas with at most n − 3 sides per sum)

For n ≥ 6, every linear component is a subset sum with at most n − 3 entries There is a finite minimum-of-maxima formula for L∗ n(s) in s0,..., sn−1 whose constituent sums all have that cardinality bound

For every n ≥ 6, L∗ n(s) − L∗ n(t) ≤ √n − 3 X i<n(s i - t i) squared 1/2 ≤ √n − 3 s - t squared The constant √n − 3 cannot be decreased

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 The components are the short sums just identified

Since finite minima and maxima preserve a common Lipschitz constant, Corollary 4.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Precise calculation of optimal square side lengths: The system can now compute exact formulas for axis-parallel square packing for any number of squares up to seven, using Theorem A from Section 1.1, which provides explicit constructions and geometric lower-bound proofs.

  2. Determination of the minimum number of side lengths required: The AI can find the minimum size of a strategy family attaining the optimum by identifying a set I such that |I| <= n - 3, as guaranteed by Theorem B in Section 1.2.

  3. Verification of Lipschitz constants: The system can calculate the optimal Euclidean Lipschitz constant for axis-parallel square packing as √n - 3 for n >= 6, based on Corollary 4.5, which proves that this constant cannot be decreased.

  4. Derivation of lower bounds via clearing sets: The AI can prove lower bounds by assuming a packing side L is less than a threshold Σ and using the property that every triple among the four largest squares clears Σ to force contradictions through geometric arguments in Lemma 3.5.

  5. Identification of optimal packing strategies: For seven squares, the system can determine which of the three strategies (top, center, or right) yields the minimum cost by calculating min(ltop, lcenter, lright) as per Proposition 5.1 and Theorem 5.5.

  6. Recognition of representation complexity: The AI can identify when a linear component is a subset sum with at most n - 3 entries and use this to rule out representations using fewer than n - 3 sides for L∗n(s).

Related papers