# Square packing in a square Unsolved problem in mathematics:What is the asymptotic growth rate of wasted space for square packing in a half-integer square?(more unsolved problems in mathematics)

Square packing in a square is a packing problem where the objective is to determine how many squares of side one (unit squares) can be packed into a square of side $a$ . If $a$ is an integer, the answer is $a^{2}$ , but the precise, or even asymptotic, amount of wasted space for non-integer $a$ is an open question.

## Small numbers of squares

5 unit squares in a square of side length $2+1/{\sqrt {2}}\approx 2.707$
10 unit squares in a square of side length $3+1/{\sqrt {2}}\approx 3.707$

The smallest value of $a$  that allows the packing of $n$  unit squares is known when $n$  is a perfect square (in which case it is ${\sqrt {n}}$ ), as well as for $n={}$ 2, 3, 5, 6, 7, 8, 10, 13, 14, 15, 24, 34, 35, 46, 47, and 48. For most of these numbers (with the exceptions only of 5 and 10), the packing is the natural one with axis-aligned squares, and $a$  is $\lceil {\sqrt {n}}\rceil$ . The figure shows the optimal packings for 5 and 10 squares, the two smallest numbers of squares for which the optimal packing involves tilted squares.

The smallest unresolved case involves packing 11 unit squares into a larger square. 11 unit squares cannot be packed in a square of side less than $\textstyle 2+2{\sqrt {4/5}}\approx 3.789$ . By contrast, the tightest known packing of 11 squares is inside a square of side length approximately 3.877084, slightly improving a similar packing found earlier by Walter Trump.

## Asymptotic results

For larger values of the side length $a$ , the exact number of unit squares that can pack an $a\times a$  square remains unknown. It is always possible to pack a $\lfloor a\rfloor \times \lfloor a\rfloor$  grid of axis-aligned unit squares, but this may leave a large area, approximately $2a(a-\lfloor a\rfloor )$ , uncovered and wasted. Instead, Paul Erdős and Ronald Graham showed that for a different packing by tilted unit squares, the wasted space could be significantly reduced to $o(a^{7/11})$  (here written in little o notation). In an unpublished manuscript, Graham and Fan Chung further reduced the wasted space, to $O(a^{3/5})$ . However, as Klaus Roth and Bob Vaughan proved, all solutions must waste space at least $\Omega {\bigl (}a^{1/2}(a-\lfloor a\rfloor ){\bigr )}$ . In particular, when $a$  is a half-integer, the wasted space is at least proportional to its square root. The precise asymptotic growth rate of the wasted space, even for half-integer side lengths, remains an open problem.

Some numbers of unit squares are never the optimal number in a packing. In particular, if a square of size $a\times a$  allows the packing of $n^{2}-2$  unit squares, then it must be the case that $a\geq n$  and that a packing of $n^{2}$  unit squares is also possible.