ASYMPTOTIC SQUARE PACKING PROBLEMS

by
Rory McClenagan
B.Sc., University of Northern British Columbia, 2021

THESIS SUBMITTED IN PARTIAL FULFILLMENT OF
THE REQUIREMENTS FOR THE DEGREE OF
MASTER OF SCIENCE

IN
MATHEMATICS

UNIVERSITY OF NORTHERN BRITISH COLUMBIA

August 2024
© Rory McClenagan, 2024

Abstract
In this thesis, we study two problems that belong to the family of infinite square

packing problems. Our first result establishes a multidimensional generalization
of a result of Terrance Tao that proved a weak form of the Meir-Moser packing

problem. More precisely, we show that if

,

< t < d' , and no is sufficiently large

depending on t, then the d-dimensional cubes of sidelength n-t for n
fectly pack a d-dimensional cube of volume

no can per¬

qk Our second result proves
•

that the wasted space generated when packing a square of sidelength x by unit

squares is bounded by O(x3/5).

ii

TABLE OF CONTENTS

Abstract

ii

Table of Contents

iii

List of Figures

iii

Acknowledgements

vi

1 Introduction
1.1 Some History and Overview of Existing Literature
1.2 Main Results
1.3 Organization of the Thesis
1.4 Conventions and Notation

1

2

3

An Overview of the Meir-Moser Problem and its Variants
2.1 Imperfect Packing Variants
2.2
Perfect Packing Variants for t<1
2.3 Extensions and Generalizations

Perfectly Packing a Cube by Cubes of Nearly Harmonic Sidelength
3.1 Preliminary Lemmas and Notation
3.2
3.3

4

Initial Reductions
Efficient Brick-Packing Algorithm

An Overview of the Unit Square Packing Problem
4.1 Bounding the Wasted Space by Ofx7/11)
4.2
Issues Around Improved Upper and Lower Bounds

1
5
5
6
7
8

11
18
19
21
24
28
33

34
39

5 Efficient Packing of Unit Squares
5.1 Packing S(x) Using Stacks of Unit Squares
5.2 The First Packing Algorithm
5.3 The Second Packing Algorithm
5.4 Proof of Theorem 1.2

49
55
61

Bibliography

64

iii

47
48

LIST OF FIGURES

1.1
1.2
1.3
2.1
2.2

2.3
2.4
2.5
3.1

3.2
4.1

4.2

4.3
4.4
4.5

4.6

A comparison of a packing with higher packing density (left) and
lower packing density (right)
2
One of the classic square-packing problem posed by Meir and Moser. 3
The trivial packing of S (x) by squares of unit sidelength. The wasted
4
space W(x) is O(x) if {x} = x — [xj is bounded away from 0
An example of Paulhus' first-phase algorithm
Grzegorek and Januszewski's "birow" packing method used to cor¬
rect the error in the proof of Paulhus's lemma
Packing S by squares Sni with nj = n0 + 4. The remaining space has
been partitioned into a collection of rectangles 5? = {Ro, Ri , . . . , R4}. .
A simplistic packing algorithm
A lower quality (left) and higher quality (right) packing algorithm.

The packing of the cubes Q in S. Here, d = 2, M] = 3, M2 = 4,
M* = 1 2, and ij = i2 = 1 . Note that the diagram is not to scale. ...
The simple solid K is constructed from B and 6

We pack S (x) in a trivial manner leaving rectangles of width h at
the top and left portion of S(x). We call one of these unpacked
rectangles R
We pack R by n-length parallel stacks of unit squares inclined at an
angle 0 such that each stack touches both the top and the bottom
of R. We call one of the unpacked trapezoids formed T
We partition T into x 0h sub-trapezoids T , . . . , Tk
We pack each T trivially, except for the sub-trapezoid T/ of width
W; ~ w, which we then pack by angled near-horizontal stacks. ...
Constant-width packing algorithms are straightforward since they
can be packed by stacks with a single inclination which ensures
there are no gaps between the stacks. The algorithm shown here
generates a wasted space of O(x/yh)
Variable-width packing algorithms are more difficult because of
the changing angle required if we want the stacks to touch both
walls simultaneously. If we ignored this and used the trivial pack¬
ing algorithm pictured above, we will generate a wasted space of
0(h)

9

11
13
15
16
30
31

35

36
37
38

40

42
iv

4.9

If we rotate each successive stack and choose w ~ h1/4, then the
total wasted space generated will be O(h7/8)
If we "shear" the stacks instead of "tilt" the stacks, the triangles
of wasted space generated are no longer long "sliver" triangles.
Unfortunately, there are small rectangular regions generated in this
packing regimen as indicated by the circled regions
Packing the majority of S(x) introducing wasted space 0(\/k)-

5.1
5.2
5.3
5.4

The first packing algorithm
The second packing algorithm
Demonstrating that 0' < 0
Packing the trapezoid T

4.7
4.8

•

•

43

•

44
45
50
56
57
62

v

Acknowledgements
I would like thank my supervisor. Dr. Alia Hamieh, for supporting me so con¬

sistently through both my undergraduate and graduate studies. I am continually
amazed at how she is always there for me to encourage me and provide guidance
both academically and personally. Dr. Hamieh has been willing to meet anytime

that I needed help or someone to bounce ideas off. Her commitment to my mathe¬
matical pursuits has been stronger than my own and is truly what has carried me

through to this point.
I would also like to express my appreciation for my committee members, Dr. Ed¬
ward Dobrowolski, Dr. Mohammad El Smaily, and Dr. George Jones. Dr. Dobrowolski has been a wonderful guide to me throughout my mathematical pur¬
suits. Ever since he introduced me to the world of higher mathematics in gifting

me Rosen's Elementary Number Theory and Its Application back in high school,

he has provided me with an engaging introduction to many beautiful areas of
mathematics. Dr. El Smaily is an amazing instructor who has exposed me to a

lot of ideas in analysis in an engrossing manner, and I appreciate both him and
Dr. Jones for helping me so much on my mathematics journey.

In writing [10], I would like to thank Professor Terence Tao for the discussion
on his blog post describing his work in [14] and for answering my many questions.

I would also like to thank Professor Tao's research team members Jaume de Dios,
Dr. Rachel Greenfeld, and Dr. Jose Madrid for helpful comments.
Indeed, Professor Tao has often been my source for mathematical inspiration

over nearly a decade. His ability to express complex and deep ideas in a beautiful

and elegant manner is hard to match and is one of the key reasons why I love

mathematics so much to this day.

Finally, I would like to thank my family. My parents' encouragement and exam¬

ples of hard work and my brother's willingness to listen to my latest mathematical
vi

idea have been invaluable.

vii

Chapter 1
Introduction
1.1 Some History and Overview of Existing Literature
Packing problems are concerned with configuring a collection of packing shapes
into some larger container such that the interiors of the packing shapes do not

overlap. In general, the goal is to maximize the proportion of the container that is
packed.
For instance, consider the problem of arranging circles inside of a larger con¬
tainer (see Figure 1.1). We can see that the "hexagonal" packing on the left is more

dense than the packing on the right. If we define the packing density of a particular

packing as the ratio of the packed area to the total area of the container, then we
could say that the hexagonal packing pictured in Figure 1.1 has a higher packing

density than the packing on the right.
Indeed, a classical finite packing problem is to determine the smallest circle that
can still contain a fixed number n of unit circles and estimate the corresponding

packing density of such a configuration. These problems tend to be surprisingly
difficult, especially for larger fixed n. Natural extensions to differently shaped

packing containers (e.g., squares or equilateral triangles) have also been studied.

1

Figure 1.1: A comparison of a packing with higher packing density (left) and lower
packing density (right).
See [6] for a review of this topic.

We are not necessarily restrained to instances where the number of packing

objects is finite. For instance, in the above example, we can consider the asymptotic
behaviour of the packing density when packing circles into asymptotically larger
containers in R2. In this scenario, one can compute that the "hexagonal" packing

depicted on the left-hand side of Figure 1.1 would have an asymptotic packing

density of

« 0.9, while the packing arrangement on the right would have an

asymptotic packing density of J % 0.8.
This introduces the question of whether or not the "hexagonal" packing has the

highest packing density for any configuration of congruent circles. This question
can be answered in the affirmative, and is known as Thue's theorem. If only lattice

configurations were considered (where the center points of the circles are arranged
in a lattice), the hexagonal packing can easily be shown to be the densest packing, a

result that is usually attributed to Lagrange (see [1]) all the way back in 1773. Thue

claimed to have proven the general result in 1890, but his proof was considered

incomplete. It was not until 1940 that Fejes Toth proved that the hexagonal packing
was the densest of all possible packings [15].

We can also consider cases where the the packing objects are unequally sized.
In these situations we are often concerned with attaining a perfect packing, one in
which the packing shapes completely cover the container and include no gaps

2

Figure 1.2: One of the classic square-packing problem posed by Meir and Moser.
(namely, the packing density is 1). Let us take a look at a concrete example.
In [11], Meir and Moser introduced two closely related packing problems that
remain open to this day. The first asked whether rectangles of dimensions

1 can perfectly pack a square of area 1 . The second asked whether squares

for n

of dimensions
-

x

x

for n

2 can perfectly pack a square (or rectangle) of area

1 (see Figure 1.2).

Currently, no solution to either conjecture exists. However, we can instead try
to perfectly pack the squares of sidelength 1 /n1 for n
and t > 1/2, into a square of area ^,^no

no, with some fixed n0

2

For reasons that are not immediately

obvious, this becomes harder as t -> 1 “, and is obviously equivalent to the original

problem when t = 1 and n0 = 2. Januszewski and Zielonka [7] verified this for
1 /2 < t

2/3 and no = 1 . In 2022, Tao [14] proved that one could extend the range

for t to the open interval 1 /2 < t < 1 for some large n0 that only depends on t.

We can also consider the multidimensional generalization of this problem, where
we are attempting to pack d-dimensional bricks of sidelength n-t for n

for

no and

< t < y’q into a d-dimensional cube of volume Hn=nQ /dt a result which we
/

will prove in this thesis (see Theorem 1.1, which was published in [10]).

We can also consider an imperfect infinite packing problem where we try to
optimize the packing density. Consider a large square S(x) of sidelength x. Pack
3

Figure 1.3: The trivial packing of S(x) by squares of unit sidelength. The wasted
space W(x) is 0(x) if {x} = x — |_xj is bounded away from 0.
S(x) by non-overlapping unit squares, and let W(x) represent the remaining un¬

packed area, or wasted space, of S (x). Our goal is to pack S (x) in such a way that
we minimize this wasted space and determine the optimal bound for W(x).

If we pack S(x) in the trivial manner where all of the unit squares have parallel

sides (see Figure 1.3), then W(x) < x{x}, where {x} represents the fractional part of
x. This bound is only O(x) when {x} is bounded away from 0.

If one instead packs the squares at slight angles, the wasted space can be de¬
creased. Indeed, determining the right order of magnitude of W(x) (when x is

bounded away from an integer) remains an open problem. It was first attacked by
Erdos and Graham in 1975 (see [4]), in which they proved W(x) < x7/11. While

Chung and Graham in [3] introduced a new packing algorithm that they claimed
reduced the wasted space bound to O(x3/5), we found that their proof contains
an error, and it only reproves the original bound O(x7/11). We introduce a more

sophisticated algorithm that allows us to attain the bound O(x3/5) (see Theorem
1.2).

4

1.2 Main Results
In this thesis, we will extend Tao's work in [14] to its multidimensional setting to
demonstrate the perfect packing of cubes of nearly harmonic sidelengths (note that

this result is published in [10]):

Theorem 1.1. If

<t<

of sidelength n-t for n

and n0 is sufficiently large depending on t, then the cubes

n0 can perfectly pack a cube of volume

•

In addition, we will improve the state of the art bound on the wasted space

generated when packing a large square by unit squares in the following result:
Theorem 1.2. The wasted space in packing the square S(x) by unit squares is bounded by

WM = O(x3/5).

1.3

Organization of the Thesis

This thesis is organized as follows. In Chapter 2, we give a detailed overview of

the progress that has been made towards the Meir-Moser problem. We discuss the

methodologies used in these results including a detailed look at Tao's argument
in [14]. We end by summarizing some of the difficulties that arise when extend¬

ing Tao's result to its multidimensional setting. We prove this multidimensional

analogue, Theorem 1.1, in Chapter 3.
In Chapter 4, we give a history of the upper and lower bounds on the wasted

space generated in the unit square packing problem. We end by discussing the

techniques that have been used to date, their intuitions, and shortcomings, includ¬
ing an explanation of where the mistake was made in [3]. This sets us up for the

proof of Theorem 1.2 in Chapter 5.

5

1.4 Conventions and Notation
Throughout this work, we will use the standard asymptotic notation X = O(Y),
X < Y, and Y » X to refer to the relation X

C|Y|. In a specific section we will

note if we are allowing the constant C to depend on auxiliary parameters. We will

explicitly use the notation X = Om[Y) or X <m Y to signify that the corresponding
constant C is allowed to depend on the parameter M. We use X x Y if X < Y and
Y < X. We use X

— Q( Y) to refer to the case when sup |X/Y| > 0. Finally, we use

the notation X = o(Y) ifX/Y —» 0. All of these notations hold with respect to some

explicit or implicit limiting behaviour defined in context.

6

Chapter 2
An Overview of the Meir-Moser

Problem and its Variants
In this chapter we will focus on the square version of the Meir-Moser problem (see

[11]), as most of the methods will generalize in a straightforward manner to the

rectangular version. Recall that this problem asked whether squares of dimensions

£ x 1 for n

2 can perfectly pack a square (or rectangle) of area

— 1 (see Figure

1.2). By perfectly pack, we mean that the squares are packed in such a way that

there is no wasted space, and the packing density is 1 .
While there is still no complete solution to the Meir-Moser problem, various

partial results have been established. In Section 2.1, we will discuss progress that
has been made towards the weaker, imperfect packing, version of the problem
where we are trying to pack the same squares into a rectangle that has slightly

larger area. In Section 2.2, we look at a different way of weakening the prob¬
lem, where we perfectly pack squares of sidelength 1 /n1 for some t < 1 instead

of squares of sidelength 1 /n. We focus on the result [14] of Tao, explaining some of

the motivation behind his work. We end in Section 2.3 by discussing the difficul¬
ties behind extending to the t = 1 case and the problems that arise when we try to

7

generalize Tao's result to higher dimensions.

2.1

Imperfect Packing Variants

We will begin by discussing the problem of trying to pack the same squares of

sidelength 1 /n for n

2 into a a rectangle R of area

— 1 + e for some e > 0, a

weaker "imperfect" version of the original problem.

In 1997, Paulhus [12] claimed that one could take e = !244918662- While this

proof did contain an error, this error was later fixed. Since the basic structure of the
corrected proof remains the same, we still discuss some of the ideas that Paulhus
used. Paulhus followed a three stage packing method in his proof to pack the

squares into a rectangle R£ with dimensions|x2( j-1 + 2e). First, he developed
an efficient first-phase packing algorithm that allowed him to pack a large number
of squares into the rectangle R (of dimensions

x2( j-1)) testable via computer

simulations up to some large N]. For some large N2 > Nj, the squares of width

£ for n G {N], . . . , N2} were packed into a small sliver of a rectangle adjoined to
R of width 2e using a second-phase packing algorithm, and the infinite number

of squares of width 1 for n larger than N2 were packed into one of the remaining

rectangles in this packing using a third-phase algorithm (that had to be proven

mathematically since it concerned an infinite number of squares).
The first-phase packing algorithm Paulhus used was a greedy algorithm that

packed one square at a time from largest to smallest, which we now describe. Let
S], S2, ... be the squares we are packing into R, ordered such that their widths are

in descending order. Suppose that at some point we have packed R by S], . . . , Sn.

Subdivide the remaining space R \ {Si , ... , Sn} into a collection of rectangles 3?. Let

Ro G ft be the smallest width rectangle that fits Sn+i . Place this next smallest square

Sn+i inside Ro such that the corner of Sn+i aligns with one of the corners of Ro.
8

R

R2

cut to longer side

Ro
Ri

5n+l

5i

Figure 2.1: An example of Paulhus' first-phase algorithm.
Partition Ro into two new rectangles Ri and R2 by cutting from the free corner of

Sn+i to the longer side of R. We can then iterate this algorithm by replacing 3? with
0? \ {Ro} U {R] , R2} This packing algorithm is pictured in Figure 2.1.

Paulhus applied his algorithm to pack the first 1 09 squares. The second phase

algorithm explicitly describes the packing of the squares from 109 to 2761408695,
and can be verified directly. The third-phase of the algorithm necessitates packing

the infinite number of remaining squares. Paulhus appeals to a lemma that states
that all of the squares from n to oo can be packed in a rectangle Ro of width w and

height h, as long as
n

b+1
——
.
wh

To get a heuristic sense of this lemma, consider the case when h is much larger than
w. Then

« 1, and so the lemma would claim that as long as n was significantly

9

larger than

we could pack the squares of width 1,

.... In other words,

rearranging the inequality, as long as Ro was long and narrow, the lemma would

only require that the rectangle Ro be a little wider than the very first square we
would pack of width 1.

On the other hand, if Ro is sufficiently small and it is not too narrow, we would

have h + 1 « 1 and the lemma would only require n to be a little larger than 1 /wh.
Since the squares we are packing have total area

this lemma would

roughly be saying that we would only need the area of Ro to be a little larger than
the area of all of the squares we were packing.

After applying the first phase of the Paulhus' algorithm computationally, Paulhus confirmed that there was an empty space with dimensions w = h = 0.00001 903,
which allowed him to pack the squares with n

2761408695 by this lemma.

Paulhus proved the lemma by performing a naive packing, placing the squares

along the long-edge of Ro in rows. However, it was pointed out in 2017 (see [8])
that this proof contained an obvious error. The naive packing method that Paulhus

used does not actually yield the necessary lemma.
Two years later, Grzegorek and Januszewski showed in [5] that if the lemma
was constrained to the particular case in which Paulhus actually applied it, the

result was still true, provided the underlying packing method and proof in the
lemma was changed to a more sophisticated one, thus providing a final rigorous

proof of the following result:
Theorem 2.1. The squares of sidelength 1 /nfor n

2 can be packed into a square of area

^-1 +1/1244918662.
Grzegorek and Januszewski relied on packing along the length of Ro, but per¬
formed this packing more efficiently by packing in "birows" instead of rows. Each
birow consisted of a row of squares with widths descending from left to right and

then a row of squares with widths descending from right to left. This pattern was
10

then replicated over all of Ro. This packing configuration is illustrated in Figure
2.2.

To date, [5] still holds the best result for the smallest e in this particular variant

of the Meir-Moser packing problem.

2.2

Perfect Packing Variants for t < 1

Another way of weakening the Meir-Moser conjecture is to instead try to perfectly

pack the squares of sidelength 1 /nl for n
into a square of area

no, with some fixed no

This becomes harder as t

2 and t > 1 /2,

1“, and is obviously

equivalent to the original problem when t — 1 and n0 = 2. We will touch upon this
issue later in the section.

Januszewski and Zielonka [7] verified this for 1/2 < t
11

2/3 and n0 = 1. In

2022, Tao [14] proved that one could extend the range for t to the open interval

1 /2 < t < 1 for some large n0 that only depends on t. More precisely, Tao proved

the following theorem.

Theorem 2.2. Let 1 /2 < t < 1, and suppose that n0 is a natural number that is sufficiently

large depending on t. Then squares of sidelength nr1 for n

n0 can perfectly pack a square

of area Xn=n0
Let us take a closer look at the ideas behind Tao's proof of Theorem 2.2. Fix
1 /2 < t < 1 . We are trying to pack the squares Sn of sidelength 1 /rd for n

a square S of area

n0 into

Suppose that we already packed SU1 = {Sno, ... , Sn]_i}

^n^no

into S. Partition the remaining space we have to pack, namely S \ Sni , into a col¬

lection of rectangles ft (see Figure 2.3). A sufficient condition to be able to pack the
next square Sni is the existence of a rectangle Re ft with width w(R)

.

Now, Tao's innovation was to develop an "efficient" packing algorithm that

kept the perimeter of ft small. This works because as long as the total perime¬
ter of ft is small enough there must be a rectangle Reft that is wide enough to

pack the next square Sni . More concretely, define the perimeter of the collection of
rectangles ft by
2 (w(R) + h(R)) ,

perim(ft) =
Rg3?

where w(R) is the width of R and h(R) is the height of R. Define the area of ft by

area(ft) =

w(R)h(R),
RcJ?

and observe that it is bounded by

area(ft)

sup w(R]
RgK

h(R)

|( sup w(R] j perim(ft).
\ReK

Rgir

12

/

R3
R^
SnQ+2

Ro

Ri

^no+3

R2

^«0

^no+l

Figure 2.3: Packing S by squares Sni with n] = no + 4. The remaining space has
been partitioned into a collection of rectangles tR = {Ro, R] , .. . , R4}.
Thus, there always exists a rectangle R G CR satisfying

w(R)

2

area(CR) \

(2-1)

perim(!R) /

How large of a rectangle R do we want to find? Well, at worse, we would want
to find a rectangle R e S such that w(R)

To satisfy this condition, we would

need the perimeter of J? to be bounded by n,area(^}. Observe that

area(K) =

£
n>n0

1

2t — 1

no<n<ni

1

—

as n] > 00.

Thus, for large ni, to ensure the existence of a rectangle with width at least 2^ it

13

would suffice to require that

perim(ft)
Thus, we can only increase the perimeter of 5? at a rate of about p(t)(ni )-t, where

Note that p ft) is decreasing for t > 1 /2, tends to infinity as t —> 1 /2+ and p ( 1 ) =0.
The next step would be to come up with some sort of packing algorithm such

that for each square of width ny1 that we packed, the perimeter of ft only increased

by about pltlnyT This immediately illustrates the critical nature of the point t = 1,
since that scenario would require the perimeter of ft not to increase at all, and

to remain bounded. However, as we move t towards 1 /2, this problem becomes
easier since p(t) gets larger. This, in turn, allows us to pack a little less efficiently
since we have a larger perimeter allotment to play with.

If we are only packing a single square in our rectangle R, then the best case
scenario is to place the square so it is aligned with the corner of the rectangle (see

Figure 2.4). This means that R is replaced by two rectangles, which have total

perimeter perim(R) + 2(w(R) —

t). Now, unless w(R) happens to be very close to

there is no particular reason that this quantity would be bounded by p(t)n^t,
at least when t is close to 1 (if t was sufficiently close to 1 /2, then p (t) tends to

infinity, making this bound much easier to attain).
If we wish to push the range of t up to 1, we would need a more sophisticated

technique. The solution is to require our rectangle to be wider so that we can pack
batches of squares at the same time in an efficient manner, instead of packing a

single square at a time. For some large fixed M, let us instead require that w(R)

14

o

> n, ‘

Figure 2.4: A simplistic packing algorithm.

Mn1 1. This would replace the perimeter bound (2.2) with
Perim™

Kt

(zWt)

(2-3)

and the maximal rate of increase for the perimeter of 3? to be ^pAlrq \ where

Our rectangle R now has width at least

and M2 =

|_y=vj then clearly M2

Mn^. In fact, if we define M] =

Mi

M, and we should easily be able to

pack R with Mi M2 squares of sidelengths n^, (ni + 1 )-t, .. . , (n2 - 1 )-t where n2 =
ni + MiM2. If we, for now, enforce that Mi x M2 x M, then ni x n2, and this

means that we are allowed to increase the perimeter of 1R by at most pftJMn^. We
now have to find such a packing algorithm.

A comparison of two packing algorithms when Mi = 3 and M2 = 4 is given in

Figure 2.5. A naive packing algorithm is attempted on the left-hand side. Due to
the "slivers" in between the squares, the perimeter of 1R is increased by an amount

approximately equal to the total perimeter of the Mi M2 squares, namely about

M2?!^, which is clearly not good enough for our purposes. However, on the right¬
hand side of Figure 2.5, we have arranged the squares in a near-lattice type struc¬

ture. Here, the only substantial increase in perimeter is due to the rectangles that
will be formed against the Mi + M2

— 1 boundary squares (in red). Thus, the perime15

w(R)
Figure 2.5: A lower quality (left) and higher quality (right) packing algorithm.
ter is only increased by about Mnp1, as desired.
Now, even though we have found an efficient packing algorithm that allows

us to only increase the perimeter of 5? at a rate of

this is not quite sufficient,

since our maximum allotted rate of increase is actually

Although p(t) is

going to be fixed for a particular t, this still makes the induction challenging espe¬

cially as t -> 1“.
The solution is to introduce a somewhat artifical concept of weighted perimeter
of a collection of rectangles J?:

perim6(^) = \ w(R)sh(R),
ReK

for some 5 > 0. Clearly, this definition coincides with the definition of unweighted

perimeter (up to an order of magnitude) when 6 = 0. Then, since
area(ft) =

w(R)h(R)
ReK

( supw(R)1-6 | perimJK),
\Re;R

16

/

we can say that there always exists a rectangle R e !R satisfying

w(R)

area(3?) \

(2-4)

perimJlR)/

Why does this help us? Well, now, to ensure there is a rectangle of width Mn1 \ we
only need

(zT^r) (n,)' "+6’''

perimJX)

(2.5)

replacing the old perimeter bound (2.3). This allows for a rate of increase in the
weighted perimeter of 3? amounting to ^4=5Pd(t)n^1+5)t, where
Ps(t) = -

~(1+6)t
2t 1

—

Now, the weighted perimeter of a single rectangle with sidelength x

n^L is going

to be n^(1+5)t, which means for each square we add in the packing algorithm de¬

picted in Figure 2.5, the weighted perimeter is only going to increase by an average
amount of

However, this is less than our allowed weighted perimeter

rate of increase by a multiplicative factor of M6p§(t). If we choose 6 = 1

— t, then

6 > 0 while (1 + 5 ) t < 1 . Thus, since t is fixed and M. can be chosen large, the factor

M5p5(t) can be made large enough so that the desired inequality is satisfied.
The intuition behind weighted perimeter is that smaller rectangles are weighted
a little less than larger rectangles. This means that even though the unweighted

perimeter of the little rectangles formed after packing R is approximately the same
or a little larger than unweighted perimeter of R itself, the weighted perimeter is

smaller.

17

2.3

Extensions and Generalizations

The major obstacle preventing us from extending the arguments in Section 2.2 to
t = 1 is the fact that the allowable perimeter of the rectangles 5?, computed in

(2.2), would now have to remain bounded throughout the entire packing algo¬
rithm. This is in contrast to the case when t < 1 , where for each square of width

that we pack, we can increase the total perimeter of ft by about O (^ ). For t = 1,
our current packing algorithm would still increase the perimeter of ft by about

most Om(1

for each square of width 1 that we pack. This would mean that the

perimeter of ft would grow in an unbounded manner. Thus, extending to t = 1
would require a much more subtle approach.

Extending Tao's ideas to higher dimensions is feasible. However, while the
packing arrangement in Figure 2.5 itself is generalizable to higher dimensions,
Tao's method of explicitly verifying that this packing is legal and efficient becomes

much more difficult in three dimensions or more. Our contribution is to introduce
the notion of "snugness"; this allows us to perform this portion of the argument in
an elegant fashion which does not become too complex in the higher-dimensional

setting. This is the content of Chapter 3 in which we extend Theorem 2.2 to the
d-dimensional setting.

18

Chapter 3
Perfectly Packing a Cube by Cubes of

Nearly Harmonic Sidelength
Let d be an integer greater than 1 . We define a brick to be a closed d-dimensional

hyperrectangle and use the term cube to refer to a brick with equal sidelengths.
We define a packing of a finite or infinite collection of bricks 13 to be a particular

configuration of the bricks in Rd such that the interior of the bricks are disjoint and
the facets of the bricks are parallel to the coordinate hyperplanes. A packing of 13

in a solid £1 c Rd is a packing of 13 such that every brick is contained in £1. The
packing is perfect if the measure m(£l \ 13} is 0. In this case the sum of the volumes
of the bricks must be equal to m(O).

In this chapter, we extend Tao's work [14] in the 2-dimensional case to the d-

dimensional case of cubes:

Theorem 1.1. If|< t <

of sidelength n-t for n

and n0 is sufficiently large depending on t, then the cubes

no can perfectly pack a cube of volume

.

The reader is reminded that the content of this chapter appears in [10]. To prove
Theorem 1.1, we apply an inductive-type argument similar to that used by Tao in

[14], Initially, we suppose that we can pack a finite set of cubes C of sidelength
19

n f for no

n <

into our single cube S. As long as S \ C can be partitioned

into bricks 2 with small enough total surface area, then we can find a brick Be®

which is wide enough to pack the next cube of sidelength
cubes 6' of sidelength n-t for n^

We pack B by

in some efficient manner. By efficient,

n<

we mean that the remaining space B \ 6' can be partitioned into bricks 23' with

small enough total surface area. In the next iteration, we choose a wide brick from
13 \ {B} U 13' and pack it efficiently. We proceed recursively until we have packed
an arbitrarily large finite number of cubes into S. Theorem 1.1 would then follow

from a compactness argument.
This type of argument reduces the problem to finding a general technique for

packing cubes efficiently into some brick, in essence, forming the inductive step
in the above argument. Up until now, we have followed Tao's argument in [14]

closely. However, while it is fairly straightforward to generalize the standard twodimensional packing algorithm used in [14] to the higher-dimensional case, Tao's
method of explicitly verifying that this packing is legal and efficient becomes much
more difficult in three dimensions or more. Our innovation is to introduce the
notion of "snugness" (see Section 3.1); this allows us to perform this portion of the

argument in an elegant fashion which does not become too complex in the higher¬
dimensional setting.

In Section 3.1, we introduce our notation and prove some simple lemmas. In
Section 3.2, we reduce the proof of Theorem 1.1 to a more general result, Proposi¬
tion 3.4, which can be proved via induction. The inductive step of this argument
is furnished by Theorem 3.5 which provides a general and efficient method for

packing a brick by cubes. This result is proved in Section 3.3.

20

3.1 Preliminary Lemmas and Notation
Note that we are using standard asymptotic notation, although we will implicitly
assume that all of our constants are allowed to depend upon the dimension d. Note

that we also use some non-standard asymptotic notation. If x = (xi,x2, .. .,xd) e

Rd, then we use x + 0(X) to refer to a vector (xi + O(X), ... ,xd + 0(X)), and analo¬
gously for little-o notation. Similarly, if B = [B^B,'] x

• • •

x [Bd, B^J is a brick posi¬

tioned in Rd, then we use B + 0(X) to refer to a brick [Bi + O(X), Bj + O (X)] x • • • x
[Bd + O(X), B^ + O(X)], and analogously for little-o notation.

Let i, j e {1,2, ... , d}. Given a brick B, we will denote its sidelengths by w^B),
ordered so that wJB)

wj(B) for any i

j. We say that the width of B is the

smallest sidelength, and denote it by w(B) := wj(B). Clearly, wdB) = Wj(B) for

every i and j if and only if B is a cube. We define the volume of a single brick B to
be
vol(B) := W] (B)w2(B) . .. wd{B).

We define the eccentricity of a brick as

Note that ecc(B] = 1 if and only if B is a cube.
Let $ be a collection of bricks. Define the volume of £ to be

wt (B)w2(B) . . . wd(B).

vol(B] :=
Be®

21

Define the unweighted surface area of 3 to be

surf(B) := 2

£ ≤^1 £

Be® 1

x

<i2<-<id_1 ≤d

(B)wi2(B) . . . w^ (B)

£ w2(B)w3(B) . . . wd(B).

Be®

For 0

S < 1, define the weighted surface area of 23 to be

surf6(®) :=

£

W]

(B)5w2(B) .. . wd(B).

Be®

Clearly, surfo(B) x surf(B). Weighted surface area is roughly speaking a version
of unweighted surface area which weights high eccentricity bricks a little less than
low eccentricity bricks. We can use the inequality w(B)

(w2(B)w3(B) . . . wd(B))

for any brick B, to derive the crude bound
surf5(£) < (surf(B))1+dx/

(3.1)

for a finite collection of bricks 23.

A solid S c Rd is called simple if it is connected and can be formed as a union
of a finite collection of bricks. A packing of a finite collection of bricks 23 in a

simple solid S is called c-snug for some e > 0 if, for every brick Be®, the portion
of SB which does not intersect the boundary of another brick or the boundary of
S has surface area < (w£)d-1 and the portion of SS which does not intersect the

boundary of any brick in ® also has surface area C (w£)d-1 . Here w is the width of
the widest brick in ®. The size discrepancy of a finite collection of bricks 3 is

maxBa»g)_1
mmBe® w(B)
The following lemma gives a criterion for the existence of a brick of a certain
22

minimum width in terms of an elegant relationship between volume and weighted

surface area.
Lemma 3.1. Let 0

6 < 1. For any finite collection of bricks B, there exists a brick with

width at least

Proof. By definition,
vol(B) =

W]

. wd(B)

( sup w(B]] 6^surf5(B).
Be®

Be®

This implies that (supBeBw(B))1-6

giving the desired result.

This illustrates the principle behind using weighted surface area. If we were to
use unweighted surface area, namely setting 5 = 0, then to guarantee the existence

of a brick of width w, we would need an upper bound on the surface area of the
form w-1vol(B). However, if 6 > 0, then we only need a weaker bound of the form

w-^voUB).
The following result follows from a compactness argument (see, for example,
[9])-

Lemma 3.2. Let T be an, at most, countable collection of bricks and let £1 c JRd be

compact. Suppose that an arbitrarily large, but finite, number of bricks from B can be
packed into £1. Then B in its entirety can be packed into £1. Furthermore, if vol(B) =
m(£l), then this packing is perfect.

The following lemma states that if a packing of bricks is sufficiently snug, then
the region between the bricks has negligible surface area.

Lemma 3.3. Suppose that a finite collection of bricks B, where the widest brick has width
w, has a c-snug packing in a brick B,for some s > 0. Then, B \ B can be partitioned into

bricks with weighted surface area c C|S|Vwd-1+6, where C|B| is a constant that depends

on |B| and y -4- 0 as e -4- 0.
23

Proof. Partition B \ B into a finite number of bricks B'. The maximum number of
bricks in B' can be bounded by a constant dependent upon |B|. By the definition

of snugness, we know that the true surface area, A, (in the sense of the (d — 1)dimensional Lebesgue measure) of the solid UB' could not exceed (Ew)d-1 (|B| + 1 ).

The result follows from the crude bound surf(B') < A|B'| and (3.1).

3.2

Initial Reductions

In this section we prove the higher-dimensional analogue of Proposition 2.1 in [14]
which will allow us to deduce Theorem 1.1.

Proposition 3.4. Fix
(d

and 6 depending on t, such that 0 < 6 < 1 and

< t <

— 1)t + 6t < 1. Choose a scale M sufficiently large and choose No sufficiently large

depending on M. Let nmax

No, and suppose that B is a family of bricks with

n0

volume

vokbi =

L

<3-2>

n=n0

weighted surface area bound

surf6 (B) <

n° 1

1

H

1

(3’3)

mi-5/2 n=1 n(d-i)t+st'

and height bound
(3-4)

sup wd(B) < 1.
Be®

Then one can pack Ubg® $

cubes of sidelength n 1 for n0

n < nmax.

First we see how we can derive our main result from Proposition 3.4.

Proof of Theorem 1.1. Fix 6 =

- 1,

and note that it easily satisfies the necessary

conditions. Take B — {C} where C is the cube of volume Xnn0

24

/

having side-

length <

1

(since t > 1 /d). Observe that (3.3) is satisfied, since

surf5(®) « n.Q /d-t^d_1+6) « nj“dt «

1
1

1i

y

Mi-5/2 lo

n=1

1i

n^-bt+st'

recalling that (d — 1 )t + St < 1 and 0 < 6 < 1 . We also have used the fact that
n+ m
m1q_s/2 » 1 since n0 No, which is sufficiently large depending upon M. Since
(3.2) and (3.4) are trivially satisfied, we can then apply Proposition 3.4 to conclude

that C can be packed by cubes of sidelength n 1 for no

n < nmaX/ and the result

follows from Lemma 3.2.
The inductive step in the proof of Proposition 3.4 requires us to pack a brick

by a collection of cubes. We isolate this result as a corollary to the following more

general theorem:
Theorem 3.5. Fix 0

8 < 1 . Let M = Mi

M2

•

Md be natural numbers,

and 6 be a family of M, = M] M2 . . . Md cubes with maximum width w and with size

discrepancy e,for some e > 0. Let Sbea brick with dimensions Si x S2 x

MiW

Si

•

•

x Sd satisfying

MiW + O (w) for i E {1, 2, . . . , d}. Then, there exists a packing of 6 in S such

that S \ 6 can be partitioned into bricks T satisfying
surf6(®) < —wd 1+6 + CMvwd 1+6,

where CM is some constant dependent upon M and y

0 as e

0.

We will prove this theorem in Section 3.3. For now, we use it to derive the

corollary we need in the proof of Proposition 3.4:
Corollary 3.5.1. Fix d < t <

5 depending on t, such that 0 < 8 < 1 and

(d — 1)t + St < 1. Choose a scale M sufficiently large and choose No sufficiently large

depending on M. Suppose that S is a brick satisfying the width bound Mnj1
25

w(S)

Mn^ + O(ngt) for some no
Then zve can find n{

No and satisfying the eccentricity bound ecc(S) = o(no).

n0 with

-n0 x ecc(S)Md, such that S can be perfectly packed

by cubes of sidelength n-t for n0

and a collection of bricks B satisfying the

n <

weighted surface area bound

sur«®> «

1

0

1

L nlJ-Wf

Proof Let the parameters be chosen as in the corollary, and use the notation S =

Si x S2 x

• • •

x Sd such that Si

Define Mt = LSt/n0

S2

Sd. Thus,

• • •

Si

Mn/ + Olng1).

for i G {1,2, ... , d}, so that Mi x M. Choose

= n0 + M*.

Note that

M* x ecc(S)Md,

(3-5)

as required. Let 6 be the collection of cubes of sidelength n f for no

The size discrepancy is

n/t

n <

n^.

— 1 . This can be made arbitrarily small as long as No is

chosen to be sufficiently large compared with M. This makes the second term in
the bound of Theorem 3.5 negligible with respect to the first. Thus, we can apply

Theorem 3.5 to get a packing of 6 in S such that S \ 6 can be partitioned into bricks
B satisfying

surf6m «

CH^dfen^^
« M*
M (n^^-bt+st
v 07

J_

1

m 2_ ^d-pt+st'
n=n0

since sd(C) —> 0. This completes the proof.

Observe that the power of M in the weighted surface area bound of the corol¬

lary is independent of 6. This fact allows us to loosen our weighted surface area
bound (3.3) by a factor of M5/2, which is enough to let us complete the inductive

step of the proof of Proposition 3.4, illustrating the advantage of working with

weighted surface area (see also the discussion after Lemma 3.1).
26

We now use this corollary to prove Proposition 3.4. Our proof closely mirrors
the proof of Proposition 2.1 in [14] except for higher dimensions. However, for the

reader's convenience, we include it here.

Proof of Proposition 3.4. We prove this via downward induction on n0. Fix nmax

No. Clearly, the result holds if n0 = nmax. Fix some n0

nmax, and assume the

result holds with n0 replaced by any strictly larger integer up to nmax. We show

that the result will then hold for n0.
Since t > 1/d, (3.2) implies that vol(®) x

nJ dt. Furthermore, since (d— 1)t +
Thus, Lemma 3.1 implies the

5t < 1, we have surfs]®) C
existence of a brick B ' G ® satisfying

W

,

B' »

nj-dt

/

°

1U

1

_

... \

= M 1-6 n/.

Since 1]~^2 > 1 for 0 < 6 < 1 , then as long as we take M sufficiently large, we can

drop the implied constant and conclude that w(B')
bricks B and B' \ B, so that

Mn^

Mn^L Partition B' into two

+ Oln^). By the height bound,

w(B)

= o(no), which means that we can apply Corollary
3.5.1 to pack B by cubes of sidelengths n-t for n0 n < nJ with nJ — n0 » Md and
(3.4), ecc(B) <

a collection of bricks ®o satisfying
ri',— 1

surf6(®0) «

£ n(dJ)t+5t-

(3.6)

n=n0

Now, if nJ

nmax, then we are done, as we have packed every cube of sidelengths

n-t for no

n < nmax. Otherwise, suppose that

nJ < nmax. Since nJ is strictly

larger than no, it makes sense to now apply our inductive hypothesis, replacing n0
by nJ (which is strictly larger than no), and replacing ® by ® ’ = (® \ {B '}) U {B ' \ B} U

®o- First, however we have to check to assure that the conditions of the proposition
27

are met. Observe,
oo

X

n'-1

1

L

n=no

n=no

oo

=

L

^=^0

and so S' has the required total volume (3.2). Clearly, S' satisfies the height bound
(3.4). Finally, by (3.6), (3.3), and the fact that surfj{B' \ B}

surf6(B')

surfs{B'}, we have

surfjfSuSo)
1

m1
1

1

1

n(d-1)t+St

n^-Bt+st

n'-1
n=l

1

T^ld— 1 )t+6t '

and thus S' satisfies the weighted surface bound (3.3). Thus, we can apply the

inductive hypothesis for

n-t for ng

and pack UbgB' b by the remaining cubes of sidelength

n < nmax, which in turn implies that we can pack UBgS b by cubes of

sidelength n 1 for n0

n < nmax.

All that remains is proving Theorem 3.5 which provides a general and efficient

brick-packing algorithm.

3.3

Efficient Brick-Packing Algorithm

Proof of Theorem 3.5. Note that, without loss of generality, we can assume that St =

MiW for i G {1,2, ... , d}. To see this, suppose that S' is a cube that contains S and
instead satisfies Mpv

S(

MjW + O (w) . Then, S ' \ S can be partitioned into a 0(1)

bricks, each of which contributes an allowable weighted surface area <

28

^wd-1+6.

To explicitly define our packing, we position S in ]Rd as

[0, M.1 w] x [0, M.2w] x

•

x [0, M.dw],

Index C as {Crd^-1 from largest width to smallest width. We use the notation

wn := w(Cn). By construction, wn

wm if and only if n

n = 0, 1, ... , M* — 1 by m =

where

'n-ilzt2z.-,id := h + CMi + 13^1 M2 H

m. We further index

FidM1M2 ... Md_],

for ik = 0, .. ., Mk — 1 (with k = 1,2, . . . , d). We use the notation Q := Cn;. and
S as
wrI := wn_
Position each Gin
I
i

Q := [xl, xl + Wr] X [x|,x| + Wr] X

X

[xd, Xr + Wr],

where for any k G {1, 2, .. . , d}, we define
Mk—1

Xf = E Wb

Mk-1
0-

tk=°

E

(see Figure 3.1).

We will verify that this is a legal packing shortly. Note that each (xj,x|, ...,x^
is asymptotically fixed at a lattice point as sd(C)

e, namely

(xl,x|, .. .,xd) = (wii,wi2, . . . , wid) + Om(ew).
Collect the subset of cubes from 6 which form its exterior "shell":

6 = {G G e : ik = 0 or ik = Mk — 1 , for some k G {1, 2, ... , d}}.

29

(3.7)

S

£2,3

- 4w
a. ,

Co,o
W

= WOfi

3w
Figure 3.1: The packing of the cubes Q in S. Here, d = 2, M] = 3, M2 = 4, M* = 12,
and ii = i2 = 1 . Note that the diagram is not to scale.
Let B be the smallest brick containing 6 \ 6. By (3.7), B has dimensions
[w, (Mi — 1 )w] x [w, (M2 — 1 )w] x •

x [w, (Mj — 1 )w] + o(1 ).

Define the simple solid K = BuC = Bue (see Figure 3.2). Observe that

S\K = (S \B) \ e.
Observe that S \ B can be partitioned into O ( M*/M) bricks ® 1 each with dimensions

30

K = BUC

C

Figure 3.2: The simple solid K is constructed from B and 6.
0(w). Each brick Bz G B' intersects at most 0(1) cubes in C. This means that we

can partition B' \ 6 into 0(1) bricks, each with weighted surface area less than

that of B', which is < wd-1+6. Thus, S \ K can be partitioned into bricks with
allowable weighted surface area <

^wd-1+6. It then suffices to show that K \ C

can be partitioned into bricks with weighted surface area <

By Lemma 3.3, it suffices to show that C is a packing that is 0M(e)-snug in K.
First, observe that all of the cubes are inside of S. This follows from the bound

w. Thus, we have to check that none of the cubes' interiors overlap, and that

wr

every cube in C \ C is touching the 2d adjacent cubes (the cubes in 6 are already
touching K by construction).
Define 7Tk to be the projection operator onto the xk axis for every k G {1, 2, ... , d}.
Let E be the collection of 2d
but e

— 1 vectors e = (e], ej, .. ., ed) such that every ek G {0, 1}

0. Let ek be the kth unit vector, namely (0, . . . , 0, 1 , 0, . . . , 0), with a 1 in the

kth component and let E c E be the collection of such d unit vectors. Define I be
31

the collection of i = (ij,12, • • , id) such that ik G {0, 1, ... , M.k

— 2} for k G {1, 2, . . . , d}.

By symmetry and the asymptotic positioning of the cubes (3.7), we only have to
worry about checking overlap on "adjacent" cubes, reducing the proof to showing
the following two claims:
(i) Let e G E and i e I. Then for at least one k G {1 , 2, . . . , d} we have that %k( Q) n
is exactly one point.

(ii) Let e G E \ E and i G I. Then for at least one k G {1,2, . . . , d}, we have that

7tk(Q) n 7tk ( Cr

is at most one point.

To see why this is sufficient to complete the proof, observe that as long as the

boundary of the cubes are touching, the asymptotic positioning of the cubes (3.7)
ensures that the non-overlapping boundary will have area Om(ew), meaning that

(i) will imply that the packing is Ojvi(E)-snug. Clearly, (ii) implies that none of the

cubes' interiors overlap, and thus our packing of 6 is valid.
To see (i), note that the construction of the Ci immediately implies that for every
k G {1, 2, . . . , d], we have

nk(CrL^ek
+ wr}.
? ) n 7tk(Cr) = {xj
1
I

L

Now we show (ii). Fix some e = (ei, e2, . . . , ed) G E \ E. Let k be the smallest
index such that the component ek is nonzero. Clearly, k G {1,2, . . . , d

— 1}. Recall

that
Mk— 1

Mk-1

C=0

ik=L

= E wb C-iaLO 0- E wii L-iALL+E.-idBy
ordering
we have that w-1+e
y the
o of vw,
i'

shows that 7rk(Cr

w^,

- . Thus, x^,t+C

s

This
L
T
+Ck = x^+w^.

x^,
b 3

n 7tk(Cr) is at most a singleton, as desired. This completes the

proof.

32

Chapter 4
An Overview of the Unit Square

Packing Problem
We now discuss the second type of packing problems that is studied in this thesis.
Consider a large square S(x) of sidelength x. Pack S(x) by non-overlapping unit

squares, and let W(x) represent the remaining unpacked area, or wasted space, of
S(x). Our goal is to pack S(x) in such a way that we minimize this wasted space

and determine the optimal bound for W(x).

There are a few differences between this style of packing problems and the
Meir-Moser type problems. While both problems are "asymptotic" in nature (in

the sense that they are concerned with packing an infinite number of squares), in

this style of problem, the squares we are packing are all the same size. Conse¬

quently, we are no longer interested in finding a perfect packing, and so the con¬

cept of the perimeter of the wasted space is lost. Instead we are more concerned
about packing squares at very slight inclines that will allow us to minimize the
total wasted space.

Recall that Erdos and Graham studied this problem in 1975 (see [4]) and proved
that you could bound W(x) as low as O(x7/11 ). We will give a version of their proof

33

in Section 4.1, since it introduces many important ideas.

Erdos and Graham were unable to prove any asymptotic lower bound on W(x),
and stated that they could not even rule out the possibility that W(x) = 0(1 ). They
did state that perhaps the proper correct bound was Olx1/2). This prompted Roth

and Vaughan to analyze the problem, and in 1978 (see [13]), they showed that
W(x) > 1O-1oVx(x- [xj).

Thus, we know that upper bound for W(x) can be no better than 0(x1/2).

In the other direction, Montgomery improved the upper bound to W(x) =

Olx1^), according to personal communication (see, for example, [3]). In 2009,
Chung and Graham [2] improved it further to W(x) =

Olx5^ logx). Recently,

in 2020, they published a result that states that W(x) = O(x3/5) (see [3]). Unfortu¬

nately, while studying their paper, we found an error in their work, which brings
the best known bound back to W(x) =

Ofx2^ logx). We will discuss this error

later in this chapter.

In Section 4.1, we give an overview of the proof in [4] bounding W(x) = 0 (x7/11 ) .

In Section 4.2, we discuss the difficulties that arise when attempting to improve the

upper bound on W(x) beyond O(x7//11), and the intuition behind the ideas in our
proof. We also discuss heuristics for what the proper order of asymptotic growth
of W(x) might be.

4.1

Bounding the Wasted Space by O(x711 )

We will now give an overview of Erdos and Graham's proof in [4] that W(x) =

O(x7//11 ). We begin by packing S(x) in the trivial manner starting from the lower
right-hand corner of S (x) . We will leave rectangles of width h unpacked at the top
and left-hand sides of S(x) (see Figure 4.1).

34

Figure 4.1: We pack S(x] in a trivial manner leaving rectangles of width h at the
top and left portion of S(x). We call one of these unpacked rectangles R.
Without loss of generality, we will pack only one of the rectangles, which we

call R. We will assume that the short h-length side of R is aligned with the vertical
coordinate axis (see Figure 4.1). We then pack R by near-vertical stacks of unit

squares of length n inclined so that they touch both sides of R (see Figure 4.2).
Choose n G Z+ so that 1 < n — h < 1 . If 0 is the angle of inclination of these stacks,
observe that
,n.
sec(0)
=

n + tan0

-

n.

Taylor series expansion then gives

Thus, when n

— h x 1,
(4-1)

35

Figure 4.2: We pack R by n-length parallel stacks of unit squares inclined at an
angle 0 such that each stack touches both the top and the bottom of R. We call one
of the unpacked trapezoids formed T.
This allows us to bound the error term by 0(^2), which gives a more precise

expression for 0:

Pack all of R in such a manner except for a narrow trapezoid on each end of height
h. Without loss of generality, we will pack only one such trapezoid, which we call

T. Note that we can fix the width of T (namely, the width of its smaller side), which

we call w, to the nearest 0(1 ) by changing the number of n-length stacks that we

pack during this stage, and will do so at a later time. We will assume that the hlength side of T is aligned with the vertical coordinates axis. We will call this the
vertical wall of T. We will call the opposing side the inclined wall of T.

We begin by partitioning T into a collection of sub-trapezoids. Let m = [0“1 J .
Partition T into trapezoids T , . . . , Tk of width m starting at the lower end of T, and

working our way up to the upper end (see Figure 4.3). Naturally, there will be a

36

w

Figure 4.3: We partition T into x 0h sub-trapezoids T] , . . . , Tk.
left-over trapezoid T* of width 0(m) at the top of T, which we will just pack in the
trivial manner.
Now, for each of the k x 0h sub-trapezoids, we will pack the left-hand side of

the given h with vertical stacks of length m, leaving an unpacked trapezoid T/ on
the right-hand side of h that has lower width Wj and upper width w< (see Figure

4.4). Pack the h by vertical stacks so that

is within a distance 1 of w.

We then pack T/ by near-horizontal stacks of length n^, where

is some integer

greater than Wt such that Tg — Wt x 1 . We will place the stacks so that they are

touching both of the opposing sides of T/ and are touching each other on the right37

Figure 4.4: We pack each L trivially, except for the sub-trapezoid T/ of width Wi
w, which we then pack by angled near-horizontal stacks.
hand side, starting as close as we can to the top of T/ and continuing until we reach
its bottom (see Figure 4.4). Observe that the angles at which we place the stacks

will depend upon how wide T/ is in that location, and will vary between some <p(

and cpi. However, recall that from (4.1), we have

(4-3)

Now, since 0 1 ~ m, we have Wj
wiz Wt

- 1 . By construction, we also have that

—

~ w. Combining these observation with (4.2) gives
(4-4)

This completes the packing algorithm. We now have to determine the wasted

space that has been generated. Let us first focus on a particular T/ (see Figure
4.4). The wasted space at the top and bottom of T/ is O(w3/2) due to (4.3). The
total wasted space generated by the "sliver" triangles between the near-horizontal
stacks is also O(w3/2) from (4.4). There are also small triangles on the right and left

38

side of each near-horizontal stack which have area O(g^) courtesy of (4.3) and
our definition of m.
Now, recall that there are a total of 0h such sub-trapezoids Tiz and so the total

wasted space generated by packing T] , ... , Tk is

< vw + ehw3^2.
Since 0

-4=, the wasted space becomes bounded by
< -i + w3/2\/h.
a/W

Note that if we pack T, trivially, we will generate an additional waste of O ( a/R + w),
which is clearly absorbed into the above terms. Now, if we equalize these two

expressions, it motivates the choice of w

- h1"'4, which gives an upper bound on

the wasted space generated when packing T of O(h7/8j.
Now, we also have to account for the wasted space generated by packing R

with the ©-inclined vertical stacks (see Figure 4.2). Once again, from (4.1), this is

just O(^). Thus, the total wasted space is
W(x) < h7/8 +

Vh

-

This motivates the choice of h x8/11, and gives the desired result W(x) = O(x7/11 ).

4.2

Issues Around Improved Upper and Lower Bounds

The above proof demonstrates the basic form that general solutions of this prob¬
lem must adhere to. There are two main sources of wasted space generated by
a "constant-width packing algorithm" and a "variable-width packing algorithm".

39

oojjh}
Figure 4.5: Constant-width packing algorithms are straightforward since they can
be packed by stacks with a single inclination which ensures there are no gaps be¬
tween the stacks. The algorithm shown here generates a wasted space of O(x/\/h).
At first, we need some sort of packing algorithm to fill the distance between op¬

posing sides of a rectangle R of width h and height x x (see Figure 4.2). Of course,
h is a parameter that we can optimize for in the proof.

The packing methods we can use in this situation seem fairly straightforward
since the distance between the opposing walls is obviously constant (we will refer

to this a "constant-width packing algorithm"). Thus, a simple packing of near¬

vertical stacks inclined at an angle 0(1 / \/h) is natural and will only generate wasted

space at the top and bottom of the stacks and not between them (see Figure 4.5).
The larger h becomes, the less wasted space that will be generated by the constant¬
width packing algorithm as the angle of the near-vertical stacks becomes slighter.
Second, no matter what variation on the above algorithm that we use, we are

generally going to generate a trapezoid T whose width can be chosen arbitrarily
and whose height in the above example would be h. We then need some sort of

packing algorithm that can pack the region between the inclined and vertical wall.
Note that any attempted optimization where we pack between the top and bottom

parallel walls during any step tends to only add additional redundancy since any

40

such optimization could generally be performed when we fixed the width of T.
What distinguishes the required algorithm in this setting to the constant-width

packing algorithm is that the distance between the two walls is no longer constant.
Thus, we refer to this as a "variable-width packing algorithm". We need some way

of increasing the width covered by each "stack" of squares as we move down T.
This is a hard problem because each stack is going to consist of an integer number
of unit squares, which will need to be rotated by some small amount in order to
cover a non-integer width.

Now, the larger h becomes the slighter the angle of the stacks in the constant¬

width packing algorithm (and the smaller the wasted space). However, larger
h means that the length of the inclined wall will also increase, leading to more

wasted space generated during the variable-width packing algorithm.

What are some natural candidates for a variable-width packing algorithm? Let
us focus on a single near-horizontal slice of T with height about Vh, meaning the

width between the vertical wall and the inclined wall would change by about 1

moving from top to bottom over this slice (see Figure 4.6). Naturally, there would
be about

such slices that we would need to pack. While in practice, we would

need a method to deal with transitions between the slices as well as the top and
bottom of T, we will ignore these concerns for now and isolate just the variable¬

space packing algorithm element by analyzing how we would pack a single such
slice.
If we try to pack this slice in the trivial manner without modifying the angles

of each successive stack, we would generate a lot of wasted space due to the large

triangle created against the inclined wall (see Figure 4.6). Over one slice this area is

0(^1, and so the total wasted space generated over T would be O(h). Assuming a
wasted space of O(x/\/h) generated during the constant-width packing algorithm,
this would yield a total wasted space of O(x2/3).

41

Figure 4.6: Variable-width packing algorithms are more difficult because of the
changing angle required if we want the stacks to touch both walls simultaneously.
If we ignored this and used the trivial packing algorithm pictured above, we will
generate a wasted space of 0(h).
If we instead rotate each stack like we did in the previous section (see Fig¬
ure 4.7), the total amount we would have to rotate the top stack compared to the

bottom stack would be about

Thus the area of the long triangles between

the stacks would amount to O(w3/2). Furthermore, even if the first stack was in¬
clined at a small angle, £1( y/h)) of the y/h stacks would still necessarily be inclined

at £1(1 /\/w). Thus, there will always be small triangles on the left and right-hand
sides of the stacks that will have a total area of 0 (

) . Equalizing the wasted space

here yields a choice of w ~ h1/4 and a wasted space generated of O(h3/8). Over the
entire trapezoidal region, the wasted space accumulated would be O(h7/8), which

would yield the bound W(x) = 0(x7/11).

Making improvements to the variable-width packing algorithm beyond this is
challenging. There are two possible points where we can try to reduce the wasted
space. First, there are the small triangles at the left and right ends of each of the
stacks. Second there are the long sliver triangles between each of the stacks them¬
selves. The first source of wasted space is difficult to reduce because no matter
what packing algorithm we use we are always going to need to have £1(1) pro-

42

Figure 4.7: If we rotate each successive stack and choose w ~ h1/4, then the total
wasted space generated will be O(h7/8).

portion of the squares inclined at an angle that is at least 0(1 /\/w) if we want the
horizontal stacks to touch both walls. The second source of wasted space is where
we can make an improvement if we are careful.

Currently, we are taking stacks and rotating them somewhat to decrease the
amount of horizontal space that they cover. Now, if we are packing a "constant¬
width" space, this works great as we can snugly fit these inclined stacks next to
each other. However, inefficiencies arise when we are packing a "variable-width"

space. The necessary angle change of the stacks generates long sliver triangles
with base 0(w). The key innovation here is to realize that modifying the inclina¬
tion of the stacks is not the only way to modify the space covered by these stacks.

Instead, we can apply a "shear" to the stacks modifying the inclination of each

square individually as supposed to the inclination of the entire stack (see Figure
4.8).

Note that while the net change in angles of the squares in the top stack com¬

pared to squares in the bottom stack is still 0(1 /-/w), the triangles between each of
the stacks now only have area y/w (compared to the old w32). Now, there are un¬

fortunately additional small rectangular regions that are generated in such a pack-

43

Figure 4.8: If we "shear" the stacks instead of "tilt" the stacks, the triangles of
wasted space generated are no longer long "sliver" triangles. Unfortunately, there
are small rectangular regions generated in this packing regimen as indicated by
the circled regions.
ing (see Figure 4.8). However, if we ignore these for a moment, we can see that
the wasted space on the left and right ends is still O(^=), and so equalizing the
two terms yields a choice of w = \/h and a wasted space generated of O(h1/4). phe

wasted space generated over the entire trapezoid would then be O(h3/4), yielding
a total wasted space of O(x3//5).

Now, unfortunately the small rectangular regions are rather problematic and

will increase the wasted space generated. The intuition behind the solution to this

problem is to slide the bottom stacks to the left to close these rectangular gaps,
and then to rotate the entire configuration counterclockwise. There are a couple of
more technical difficulties that arise when we implement this technique which are

beyond the scope of this section, but that we will cover in Chapter 5 to attain the
full bound O (x3/5 ) .

If we only consider the constant-packing portion of the algorithm, it is easy to
see that a choice of h = x only generates a wasted space of yN, at least when we

pack the squares in parallel stacks (see Figure 4.9). This may be why Erdos and
Graham conjectured a proper order of magnitude of yN for the wasted space in

44

Figure 4.9: Packing the majority of S(x) introducing wasted space O(y/x).

their initial paper in 1975 (see [4]). However, it seems infeasible that it would be

possible to find a variable-width packing of necessary strength to support a choice
of h = x. This would require a variable-width packing algorithm that packed a

trapezoid of height h while only generate wasted space 0(h1/7).
Note that a proof claiming to improve the O(x7/11) bound to O(x3/5) will nec¬

essarily require some argument similar to our own. In [3], Chung and Graham

developed a packing algorithm similar to the one employed in [4], but where they

improved the packing of the transitions between successive Tk (see Figure 4.3).
Unfortunately, the amount of angle change that is necessary to lengthen a wlength near-horizontal stack by 0(1) (see Figure 4.7) is on the order of 0(1 /y/w),
as shown in (4.4). As we have just shown, this will limit the attainable wasted

space bound to ©(x7/11 ) no matter how efficient the transitions are packed. Chung
and Graham instead essentially claimed that this angle change was of the order of

magnitude w-3/2.

45

For example, in the first paragraph of page 696, they claim that the "[...] tilt

of the lower stack is

,

c

'' while the "tilt of the upper stack is

fa +

(x-2/5)" (an error term which is consequently dropped from their argument in
the first equation on page 696). On page 696, they then bound this discrepancy by

O(x-4/5y With our notation, w would be of order of magnitude x2/5 and they are
increasing the width covered by the w-length consecutive stacks by ~ -U. Thus,

they are claiming that the discrepancy between these angles is 0(1 /w2), when in

reality it is 0(1 /w).
Unfortunately the constant c they are using is not actually fixed between these
two stacks of differing angles and is dependent on the fractional part of w which

changes by the same amount as w, namely 0(1/y/w), as shown in (4.2). At an
intuitive level, the mistake lies in differentiating the approximation 0 x

some integer n larger than w) by holding n

(for

— w constant instead of allowing it to

depend upon w (see 4.2).
The final observation we make is that we strongly believe that the proper order

of growth of the wasted space is x3/5. We would expect that the argument that
would be necessary to prove this claim would be quite sophisticated, as it would

at the very least require a much more general version of the complex argument in
[13].

46

Chapter 5
Efficient Packing of Unit Squares
Let S(x) denote a square of sidelength x for some large x. Pack S(x) as efficiently
as possible by squares of unit sidelength with disjoint interiors. Let W(x) denote

the minimum amount of area left uncovered in S (x) by any such packing. In this

chapter, we will prove the following result:
Theorem 1.2. The wasted space in packing the square S(x] bp unit squares is bounded bp

wm = o(x3/5).
We will prove Theorem 1.2 in several stages. First, we pack all of S(x) using

"stacks" of unit squares except for a finite number of trapezoidal regions T in Sec¬
tion 5.1. We then pack such a generic trapezoidal region using two different "sub¬

algorithms", described in in sections 5.2 and 5.3. In section 5.4, we show how these
can be combined to form a packing of T. We then optimize our parameters, and

demonstrate that the wasted space generated by our packing is O(x3/5).

47

5.1 Packing S(x) Using Stacks of Unit Squares
We begin by packing S(x) in a trivial manner by placing unit squares snugly with
sides parallel to S(x) starting at one corner until the only unpacked region is two

rectangles with width h (see Figure 4.1). Note that we can fix h to the nearest
0(1 ) by changing the number of squares that we pack during this stage, which is

something we will do at the end of the proof.
Without loss of generality, we will pack only one of the rectangles, which we

call R. We will assume that the short h-length side of R is aligned with the vertical
coordinate axis. We then pack R by near-vertical stacks of unit squares of length n
inclined so that they touch both sides of R (see Figure 4.2). Choose n e Z+ so that
1 < n — h < 1 . If 0 is the angle of inclination of these stacks, then observe that

sec(0) =

n + tan 0
h

Taylor series expansion then gives

-4^-44
Thus,

(5-1)

Pack all of R in such a manner except for a narrow trapezoid on each end of height
h. Without loss of generality, we will pack only one such trapezoid, which we call

T. Note that we can fix the width of T (namely, the width of its smaller side), which

we call w, to the nearest 0(1) by changing the number of n-length stacks that we

pack during this stage, and will do so at a later time. We will assume that the hlength side of T is aligned with the vertical coordinates axis. We will call this the
vertical wall of T. We will call the opposing side the inclined wall of T.
48

Except for a portion that we pack trivially at the top and bottom of T, we will
pack T in a collection of near horizontal strips that will each have a height of about

20-1 . Each such strip will be packed using two packing algorithms. Such packings
will be replicated all the way down the length of T. When we describe these two

packing algorithm in sections 5.2 and 5.3, we will describe them abstractly and
not yet fix where we are vertically within T, but instead will only refer to the two
sides of T as the vertical and inclined walls. We will combine these two packing

algorithms together formally in section 5.4.

5.2 The First Packing Algorithm
First, place a near-horizontal stack Ho inclined at an angle of cp containing m unit

squares so that its left edge touches the vertical wall and its right edge is some dis¬
tance e

0 from the inclined wall (see Figure 5.1). We now place a small rectangle

of width e along the inclined wall stretching over the entire vertical region that
will be covered during the first packing algorithm. This region will not be packed.
Place a vertical stack Vo inclined at an angle of 0 with m squares so that it is sung

against the E-width rectangle and parallel to the inclined wall.

Next place a horizontal stack Hi snugly against Ho containing m — 1 squares
such that it touches the vertical wall. Similarly, place a vertical stack W containing

— 1 squares snugly against Vo and touching Hj . We then continue in a similar
manner to place the stacks Ht and W containing m — i squares for i = 0, .. . , m — 1 .
m

Label the points on the first two horizontal and vertical stacks as in Figure 5.1.
Construct the line GE, noting that this must be vertical by construction. We are

going to fix (p in such a way that the angle ZEDC formed is a right-angle. This
means that there is a line formed from E to the bottom left corner of Vo inclined

at angle 0, just like the inclined wall, which allows us to iteratively pack each

49

50

consecutive Hi and Vi in the same manner as Hp and Vp.

Estimating cp
Observe that

ZFGE = cp,

and

ZECD = cp + 0,

ZCAB = cp + 0,

and so
EC = 1

— tancp and DC = 1 — sin(cp + 0).

(5.2)

Thus, ZEDC is a right angle if and only if

(1 — tan (p) cos(cp + 0) = 1 — sin(ip + 0).

(5.3)

Fix (p to be the solution of (5.3). We now want to determine an approximation for
cp in terms of 0. Applying Taylor series expansions gives

Q — <p + O((p3)J M — — — (p202 —— + O ^(cp + 0)4J j = 1 — — 0 + O(\(p + 0)3j.
ip

Aggregating lower order terms gives

9-Z-^-^ +

^

=

o((<pW).

This implies that cp2 + O(cp3) = 20 + O(02). It follows that cp2 x 0 allowing us to
write cp =

^20 + O(03/2). Taylor series expansion gives
<p

= \/20 + O(0)

and

51

0=

^<p2 + O((p3).

(5.4)

Estimating ip
Now, we have fixed cp (and estimated it in terms of 0) such that the packing setup

shown in Figure 5.1 is feasible and can be iterated for each Hi and Vt. This auto¬

matically fixes the angle 4 formed at the bottom of this region that we are packing
(see Figure 5.1). We now want to estimate this angle. Observe that ZHKJ =4 + 9/
so
DH = 1 — tan(4 + 0).

(5.5)

On the other hand since IEH and ECD are similar, so
DC
ED + DH = — .

Since ZE CD = cp + 0, we can rearrange this as

DH = cos(cp + 0) — EC sin((p + 0).

Combining this with (5.2) gives
DH = cos(cp + 0) — (1 — tan cp) sinfcp + 0)

Comparing this with (5.5) allows us to see that 4 is the unique solution of
1 — tan(4 + 0) = cos(cp + 0) — (1 — tan cp) sin(cp + 0).

(5.6)

We can Taylor expand both sides of this equation, simplifying our error term using
(5-4):
1 - 4 - 0 = 1 - -cp2 - (cp + 0) + cp2 + O(cp3 +43)-

52

Solving for ip gives
ip = <P -

|<p2 + O((p3 + xp3).

It follows that ip + O(ip3) = cp + O(cp2) and so ip x cp, allowing us to simplify the
error term. Combining this observation with (5.4), we get

iP = (p-e + O((p3).

(5.7)

Thus, we have "lost" about 0 in the inclination of the top portion of the region we

are packing compared to the bottom.

Now, at this stage, the only quantity we have fixed is cp, which was chosen in

such a way so that we could perform our first packing algorithm. In the second

packing algorithm we will want to start by packing m + 1 square along the length
PR compared to the m squares we packed at the beginning of the first packing

algorithm (note that R is chosen to be the point on PQ such that the distance from
R to the inclined wall is e). To do this, we need to choose m large enough so that

the first packing algorithm takes up sufficient vertical space, thus and forces PR to

be able to fit m + 1 squares along it.

Estimating m
We want to choose m such that PR is just long enough to fit a near-horizontal stack
of m + 1 squares inclined at an angle of ip. Choose points S on the vertical wall and
T on PR such that ST = 1 and ZPTS is a right-angle (equivalently, ZTSP = ip). Define

m to be the least integer such that TR

m + 1 . Note that the distance between the

inclined and the vertical walls increases at a rate of 0(0). Thus, increasing m by 1
will increase TR by 0(0). Thus, our definition of m automatically gives

TR = m+l +0(0).

53

It is important to note that this definition of m (and the length TR) is independent of
e, although of course T Q depends on e:

TQ = m+ 1 + 0(9 + e).

(5.8)

We now want to find an approximate expression for m in terms of our known

quantities. Observe that the horizontal distance from the vertical wall to the lowerleft corner of Vm_] is the same as the horizontal distance from F to J, which is O ( cp ) .
Thus, the distance from P to the lower-left corner of Vm_] is also 0((p), we have:

TR=^^)+0(*'
However, once again, we know that the difference between TR and m + 1 is at most
0(9). Thus,

—

rr+ 9)
m
cos(i|>
—

-m = 1 + OM-

Upon Taylor expansion, the left-hand side becomes |ip2m+ 0(49™)- Applying
(5.7) and (5.4) thus gives
9m + O((p3m) = 1 +0(<p).

Clearly this implies that m x 9 1 , which allows us to simplify the error term, giving
us an approximate expression for m:

m = 9-1 +0(<p-1}.

54

(5.9)

Summary
This completes the analysis of the first packing stage. We make two important
observations. First, observe that the quantities <p,T and m are all fixed based solely
on 0, independent of e. Second, note that the angle cp at the top of the packed

squares differs from the angle ip at the bottom of the packed squares by about 0 (see
5.7). This is the reason we cannot simply iterate this first packing algorithm all the

way down the trapezoid T. Indeed, if we were to reset and apply the first packing
algorithm successively each application would generate a triangle of height O(m)
and angle cp

— ip ~ 0 having area 0-1. This is an order of magnitude larger than

the area of the other wasted space that is generated during the algorithm we just
described. We instead have to pair this first algorithm with another algorithm that
"undoes" the angle change of 0. We do this in the next section.

5.3 The Second Packing Algorithm
The second packing algorithm will begin at the bottom of where the first packing

algorithm left off, and proceed down the trapezoid T. Place a horizontal stack
inclined at an angle of ip up against PQ that contains m+ 1 squares and so that
its left edge touches the vertical wall and its right side is some distance of s' from

the inclined wall (see Figure 5.2). Note that our choice of m in the last section is

what ensures that we have enough room. We are going to place a small rectangle
of width s' along the inclined wall and will not pack that region during the second

packing algorithm. Note that from (5.8), we have

e'<e + 0.

(5.10)

Next, pack a vertical stack Vo' with m' (an integer which is less than m. which we

55

Figure 5.3: Demonstrating that 0' < 0.
will fix later) squares against the vertical wall so that it touches H^. Choose some

0' such that we can fit another horizontal stack H, with m squares snugly against
Hq so that it touches both Vo' and a new inclined wall of angle 0Z (we will prove the

feasibility of such an arrangement shortly). Label the points on these stacks as in
Figure 5.2.

Estimating 0'
First we prove that 0'

0 by ensuring that there is enough room to pack Hj when

0' = 0 (if the horizontal stacks were too large we would be forced to choose 0' <
0). However, this is feasible if and only if the distance d depicted in Figure 5.3 is

greater than or equal to 1 (otherwise we would not be able to slide in the vertical
stack Vq). But, since <p > ip, then di + d2 > d. Clearly, though, d] is greater than
DC in the first packing algorithm (see Figure 5.1) and d2 is greater than CB. Thus,
d > di + d2 > DB = 1, implying that 0'

0.

We now give an upper bound on the discrepancy between 0' and 0.
Observe that

ZEAB=ip + 0',

ZBCD=xp,

57

and

ZGDF = xp.

Thus,

ED + DB = tan(xp + 0'),

1+ED = —-— ,
cosip

and

DB=tanip.

We can then define 0 ' to be the unique solution to

secxp — 1 + tanip = tan(xp + 0').

(5-11)

Taylor series expansion gives

^ip2 + O(ip3).

0' =
Comparing with (5.4) and (5.7) gives

O<0-0'<<p3.

(5.12)

We then can continue to pack the m + 1 — i-square stacks Hi for i = 0, 1 , . . . , mz
1 in the same manner. Similarly we will pack the m'

—

— i-square stacks W for i =

Estimating <p'
To determine the angle <p'z note that cp' = ZJIH (see Figure 5.2). However the

triangle CKJ is congruent to the triangle CDB, which implies that CJ = DB. Fur¬
thermore, the triangle CDB is congruent to the triangle FGD, which implies that
ED = HC. Thus the triangle JIH is congruent to the triangle BAE, which then im¬

plies that cp ' — ip + 0'. From (5.7) and (5.12), this implies that

(p

— cp' < <p3.

58

(5.13)

Note that cp' is fixed independent of e.

Estimating m'
We want to choose m' such that if we packed a new horizontal stack of length m
at an angle of cp, there would still be just enough room for two vertical stacks up

against the vertical wall. Note that these stacks would continue to the bottom of
the trapezoid T. This setup would allow us to once again apply the first packing

algorithm.
Label the points as in the bottom of Figure 5.2. We are assuming here that
cp

cp '. The case for cp < cp' is analogous. Note that we have chosen points S on

the right-hand side of the two vertical stacks and T on PR such that ST = 1 and
Z PTS is a right-angle (equivalently, ZTSP = cp). Thus, we will want to choose m' to

be the least integer such that TR

m. Of course, we will have to show that such an

m' exists and is less than or equal to m, and we will have to bound the discrepancy
between m and m'. For now, it is easy to see that m' x m x 0-1 .
Note that m' will have to depend upon e, since we are attempting to close the

gap caused by the e '-width rectangle. This is important as the discrepancy TR — m
will generate the e for the next iteration of the first and second packing algorithms,

and we do not want these errors aggregating over each iteration of this pair of

packing algorithms.
Let Q be the point on the inclined wall such that P'Q is parallel to PQ (namely,

inclined at an angle of Q). From the sine rule, and using the fact that m', m. < 0-1,

we have

P'Q
v — PQ
v — PP' . t

—
=m'0 + O(0).
— (m' + 0(1))JJcos(Q
+ 0)

sm(7r/2-ip-0) = v

59

v

1 7

Again, by the sine rule,
p'r = p'q

(

(pq + m'e + 0(e))

\sm(7t/2 — 0 — <p) / = '

(

£± )

'\cos(0 + (p)/

Observe that since <p — xp = 0 + O(cp3) from (5.7), we have
cos(0+4)
cos[0 + (p]

cos(0 + (p) cos(0 + O((p3b + sin(0 + cp) sin(0 + O(cp3))
cos(0 + cp)

4

Thus, since m/ < m < cp-2 and PQ = m+ cp + O(cp2 + s) (from (5.8)), we have

PZR =

(m+ 1 + <p + m/0 + 0(<p2 + e)) (1 + 0<p + O ( <p4))

= m+ 1 + <p + m/0 + 0cpm+ 0(<p2 + e)
We then have
TR = P'R — 2(1 — cos (p) — sin(<p) = m + m/0 + 0cpm— 1 + O(ip2 + s).

Now, observe that it is always possible to find a m'

as e

m such that TR

(5.14)

m as long

cp2, since taking m/ = m would make TR ~ m + cp (larger than m), so such

an m' must exist. We are implicitly using the fact that we can always fix TR to the

nearest 0 (the slope of the inclined wall). We can summarize these observations

with the following equation

0<TR — m<0,

(5.15)

noting that the asymptotic is independent of e. Substituting this into (5.14), and
once again assuming that e = 0(0), gives

0m/ + 0(pm— 1 =0(0).

60

This allows us to solve for m':

m/ = 0 1 + Oftpm).
Combining this with (5.9) gives
m — m/ < (p

(5.16)

Summary
We have now developed two packing algorithms. When applied back to back,
the end of the second packing algorithm is the setup for the initiation of the first

packing algorithm. Note that the only parameter that will vary throughout this
iterative process is m', as it is dependent upon e.

5.4

Proof of Theorem 1.2

Packing T
We can now apply our two packing algorithms to complete the proof of Theorem
1.2. Recall that we had not yet fixed the width of the trapezoid T. Now, the inclined

wall of T was inclined at an angle 0 x h-1/2 (see (5.1)). Observe that with this choice

of 0, we must have m, m' x h1/2, and <p,i|), <p' x h-1/4 yye now £x the width of the

upper edge of T so that the first m-length horizontal stack inclined at an angle of <p
is within O(\/h) of the top of T, thereby implying that T has a width on the order

of y/h (see Figure 5.4).

To pack T, we apply our two packing algorithms back to back, packing a "sub¬

trapezoid" at the top of T of height about 20-1 x \/h. Note that our first choice of
e can be 0. We then pack the two vertical stacks along the entire vertical wall. We

61

Figure 5.4: Packing the trapezoid T.

62

repeat this process, packing each sub-trapezoid all the way until we have packed
everything except a region at the bottom of T that has height at most O(y/h) (see
Figure 5.4). Note that at each stage, we are using the same (p,^, cp' and m, but that
the choices for e, e' and m/ will change for each iteration of the packing algorithm.
However, we can always ensure that e < 0, courtesy of (5.15). Note that we will

have to apply our algorithm a total of x \/h times to pack all of T.

Estimating the wasted space
Let us begin by computing the wasted space from a single iteration of the first and
second packing algorithms. Observe that all of the rectangles in the wasted space

have area at most 0 (

) . To see this, first observe that

in Figure 5.2 has length

at most O((p-1 ) from (5.16). Second, note that we can always force e < 0, and thus

e' < 0 (see (5.15) and (5.10)).
Next, note that there are two large sliver triangles of length O(0-1 ) and angles
0

— 0' and ip — cp' (see Figure 5.2). Thus, from (5.12) and (5.13), the area of these

triangles is <

There is also a small sliver between P'Q' and the rectangle of

width < cp-1 . This has an angle trivially bounded by cp, and so its area is O(^).

Finally, observe that there are < 0 1 0(1 (-length triangles created through both
packing algorithms, and their angles are all < V®, implying that there total contri¬
bution is < 4=.
vn
Thus, the total amount of wasted space generated through these two packing

stages is < 4g < h1/4. Since we are applying these packing algorithms x \/h
times, then the total wasted space contributed by packing the sub-trapezoid re¬

gions becomes O(h3/4). We pack the regions at the top and bottom of T trivially,

which generates an additional wasted space of 0(h1/2) (see Figure 5.4). Thus, the
total wasted space generated by packing T is O(h3/4).
Now, the wasted space generated by packing the O(x) vertical stacks inclined

63

at an angle 0 in Figure 4.2 is O(x0), meaning that our total wasted space is bounded
as follows:
W(x) <

-^

+ h3/4.

Equalizing the two terms gives a choice of h ~ x4/5, yielding the desired result.

64

Bibliography
[1] H.-C. Chang and L.-C. Wang, "A simple proof of thue's theorem on circle
packing," arXiv preprint arXiv:1009A322, 2010.
[2] F. Chung and R. Graham, "Packing equal squares into a large square," /. Com¬
bin. Theory Ser. A, vol. 116, no. 6, pp. 1167-1175, 2009.

[3]

, "Efficient packings of unit squares in a large square," Discrete and Com¬
putational Geometry, vol. 64, 10 2020.

[4] P. Erdos and R. Graham, "On packing squares with equal squares," J. Combin.
Th., vol. 19, pp. 119-123, 1975.

[5] P. Grzegorek and J. Januszewski, "A note on three Moser's problems and two
Paulhus' lemmas," J. Combin. Theory Ser. A, vol. 162, pp. 222-230, 2019.
[6] M. Hifi and R. M'Hallah, "A literature review on circle and sphere packing
problems: Models and methodologies," Advances in Operations Research, vol.
2009, no. 1, p. 150624, 2009.

[7] J. Januszewski and Eukasz Zielonka, "A note on perfect packing of squares
and cubes," Acta Mathematica Hungarica, vol. 163, pp. 530-537, 2021.
[8] A. Joos, "On packing of rectangles in a rectangle," Discrete Math., vol. 341, p.
2544-2552, 2018.
[9] G. Martin, "Compactness theorems for geometric packings," J. Comb. Theory,
Ser. A, vol. 97, pp. 225-238, 2002.
[10] R. McClenagan, "Perfectly packing a cube by cubes of nearly harmonic side¬
length," Canad. Math. Bull., vol. 66, no. 3, pp. 1061-1071, 2023.
[11] A. Meir and L. Moser, "On packing of squares and cubes," Journal of Combina¬
torial Theory, Series A, vol. 5, pp. 126-134, 1968.
[12] M. M. Paulhus, "An algorithm for packing squares," J. Comb. Theory, Ser. A,
vol. 82, pp. 147-157, 1998.

[13] K. Roth and R. Vaughan, "Inefficiency in packing squares with unit squares."
J. Comb. Theory, Ser. A, vol. 24, pp. 170-186, 03 1978.
65

[14] T. Tao, "Perfectly packing a square by squares of nearly harmonic sidelength,"
Discrete Comput. Geom., vol. 71, no. 4, pp. 1178-1189, 2024.
[15] L. F. Toth, "Uber die dichteste kugellagerung," Math Z, vol. 48, pp. 676-684,
1942.

66