Square packing

For larger values of the side length ${\displaystyle a}$, the exact number of unit squares that can pack an ${\displaystyle a\times a}$ square remains unknown. It is always possible to pack a ${\displaystyle \lfloor a\rfloor \!\times \!\lfloor a\rfloor }$ grid of axis-aligned unit squares, but this may leave a large area, approximately ${\displaystyle 2a(a-\lfloor a\rfloor )}$, uncovered and wasted.[4] 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 ${\displaystyle o(a^{7/11})}$ (here written in little o notation).[7] Later, Graham and Fan Chung further reduced the wasted space to ${\displaystyle O(a^{3/5})}$.[8] However, as Klaus Roth and Bob Vaughan proved, all solutions must waste space at least ${\displaystyle \Omega {\bigl (}a^{1/2}(a-\lfloor a\rfloor ){\bigr )}}$. In particular, when ${\displaystyle a}$ is a half-integer, the wasted space is at least proportional to its square root.[9] The precise asymptotic growth rate of the wasted space, even for half-integer side lengths, remains an open problem.[1]

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