Optimally Packing a Large Square by Unit Squares Rory McClenagan Abstract . We show that a large square of sidelength x x can be packed by unit squares in a manner so that the wasted space W ⁡ ( x ) = O ⁡ ( x 3 / 5 ) W(x)=O(x^{3/5}) . 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. Of course, if x is an integer, then W(x)=0 . In general, when x is not an integer, orienting the unit squares so that they are parallel to the sides of S(x) in a naive manner will generate a wasted space W(x)=O(x\{x\}) . Here, \{x\} is the fractional part of x , and if it is bounded away from 0 , the wasted space W(x) simply becomes O(x) . Figure 1. The trivial packing of S(x) by squares of unit sidelength. The wasted space W(x) is only O(x) if \{x\}=x-\lfloor x\rfloor is bounded away from 0 . However, if one packs the squares at slight angles, the wasted space can be decreased. In 1975, Paul Erdös and Ronald Graham showed that W(x)=O(x^{\frac{7}{11}}) (see [ 2 ] ). This prompted discussion around the proper order of growth of W(x) . We do know that the bound can at least be no better than O(x^{1/2}) . This result is due to Roth and Vaughan in 1978 (see [ 3 ] ) who showed that W(x)>10^{-100}\sqrt{x-\lfloor x\rfloor}. On the other end, Montgomery improved the upper bound to W(x)=O(x^{\frac{3-\sqrt{3}}{2}}) , according to personal communication (see, for example, [ 1 ] ). In 2009, Fan Chung and Ronald Graham improved it further to W(x)=O(x^{\frac{3+\sqrt{2}}{7}}\log x) . Now, recently in 2020, Chung and Graham claimed that this could be improved to W(x)=O(x^{3/5}) (see [ 1 ] ). Unfortunately, this result has an error in it, which brings the best known bound back to W(x)=O(x^{\frac{3+\sqrt{2}}{7}}\log x) . In this paper, we show that the bound claimed by Chung and Graham in [ 1 ] is, in fact, correct, using a new algorithm: Theorem 1 . The wasted space in packing the square S(x) by unit squares is bounded by W(x)=O(x^{3/5}). We will prove Theorem 1 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 Section 1 . We then pack such a generic trapezoidal region using two different “sub-algorithms” , described in in sections 2 and 3 . In section 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(x^{3/5}) . Notation Throughout this paper, we will use the standard asymptotic notation X=O(Y) , X\ll Y , and Y\gg X to refer to the relation X\leq C|Y| . If, instead, we use the notation X=O_{M}(Y) or X\ll_{M}Y , then the corresponding constant C is allowed to depend on the parameter M . We use X\asymp Y if X\ll Y and Y\ll X . Finally, we use the notation X=o(Y) if X/Y\rightarrow 0 with respect to some explicit or implicit limiting behaviour defined in context. 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 2 ). Note that we can fix h to the nearest O(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. Figure 2. We begin by packing S(x) trivially except for two rectangles of width h . 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 3 ). Choose n\in\mathbb{Z}^{+} so that 1\psi , then d_{1}+d_{2}>d . Clearly, though, d_{1} is greater than DC in the first packing algorithm (see Figure 4 ) and d_{2} is greater than CB . Thus, d>d_{1}+d_{2}>DB=1 , implying that \theta^{\prime}\leq\theta . We now give an upper bound on the discrepancy between \theta^{\prime} and \theta . Figure 6. Demonstrating that \theta^{\prime}<\theta . Observe that \angle EAB=\psi+\theta^{\prime},\quad\angle BCD=\psi,\quad\text{and}\quad\angle GDF=\psi. Thus, ED+DB=\tan(\psi+\theta^{\prime}),\quad 1+ED=\frac{1}{\cos\psi},\quad\text{and}\quad DB=\tan\psi. We can then define \theta^{\prime} to be the unique solution to (3.2) \sec\psi-1+\tan\psi=\tan(\psi+\theta^{\prime}). Taylor series expansion gives \theta^{\prime}=\frac{1}{2}\psi^{2}+O(\psi^{3}). Comparing with ( 2.3 ) and ( 2.6 ) gives (3.3) 0\leq\theta-\theta^{\prime}\ll\varphi^{3}. We then can continue to pack the m+1-i -square stacks H_{i} for i=0,1,\dots,m^{\prime}-1 in the same manner. Similarly, we will pack the m^{\prime}-i -square stacks V_{i} for i=0,1,\dots,m^{\prime}-1 . Estimating \varphi^{\prime} To determine the angle \varphi^{\prime} , note that \varphi^{\prime}=\angle JIH (see Figure 5 ). However the triangle CKJ is congruent to the triangle CDB , which implies that CJ=DB . Furthermore, 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 implies that \varphi^{\prime}=\psi+\theta^{\prime} . From ( 2.6 ) and ( 3.3 ), this implies that (3.4) \varphi-\varphi^{\prime}\ll\varphi^{3}. Note that \varphi^{\prime} is fixed independent of \varepsilon . Estimating m^{\prime} We want to choose m^{\prime} such that if we packed a new horizontal stack of length m at an angle of \varphi , 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 . We are assuming here that \varphi\geq\varphi^{\prime} . The case for \varphi<\varphi^{\prime} is analogous. Note that we have chosen points S on the right-hand side of the two vertical stacks and T on \overline{PR} such that ST=1 and \angle\hat{P}TS is a right-angle (equivalently, \angle TS\hat{P}=\varphi ). Thus, we will want to choose m^{\prime} to be the least integer such that TR\geq m . Of course, we will have to show that such an m^{\prime} exists and is less than or equal to m , and we will have to bound the discrepancy between m and m^{\prime} . For now, it is easy to see that m^{\prime}\asymp m\asymp\theta^{-1} . Note that m^{\prime} will have to depend upon \varepsilon , since we are attempting to close the gap caused by the \varepsilon^{\prime} -width rectangle. This is important as the discrepancy TR-m will generate the \varepsilon 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 \hat{Q} be the point on the inclined wall such that \overline{P^{\prime}\hat{Q}} is parallel to \overline{PQ} (namely, inclined at an angle of \psi ). From the sine rule, and using the fact that m^{\prime},m\ll\theta^{-1} , we have P^{\prime}\hat{Q}-PQ=PP^{\prime}\frac{\sin\theta}{\sin(\pi/2-\psi-\theta)}=(m^{\prime}+O(1))\frac{\sin\theta}{\cos(\psi+\theta)}=m^{\prime}\theta+O(\theta). Again, by the sine rule, P^{\prime}R=P^{\prime}\hat{Q}\left(\frac{\sin(\pi/2+\theta+\psi)}{\sin(\pi/2-\theta-\varphi)}\right)=\left(PQ+m^{\prime}\theta+O(\theta)\right)\left(\frac{\cos(\theta+\psi)}{\cos(\theta+\varphi)}\right) Observe that since \varphi-\psi=\theta+O(\varphi^{3}) from ( 2.6 ), we have \frac{\cos(\theta+\psi)}{\cos(\theta+\varphi)}=\frac{\cos(\theta+\varphi)\cos(\theta+O(\varphi^{3}))+\sin(\theta+\varphi)\sin(\theta+O(\varphi^{3}))}{\cos(\theta+\varphi)}=1+\theta\varphi+O(\varphi^{4}). Thus, since m^{\prime}\ll m\ll\varphi^{-2} and PQ=m+\varphi+O(\varphi^{2}+\varepsilon) (from ( 2.7 )), we have P^{\prime}R=\left(m+1+\varphi+m^{\prime}\theta+O(\varphi^{2}+\varepsilon)\right)\left(1+\theta\varphi+O(\varphi^{4})\right)=m+1+\varphi+m^{\prime}\theta+\theta\varphi m+O(\varphi^{2}+\varepsilon) We then have (3.5) TR=P^{\prime}R-2(1-\cos\varphi)-\sin(\varphi)=m+m^{\prime}\theta+\theta\varphi m-1+O(\varphi^{2}+\varepsilon). Now, observe that it is always possible to find a m^{\prime}\leq m such that TR\geq m as long as \varepsilon\ll\varphi^{2} , since taking m^{\prime}=m would make TR\sim m+\varphi (larger than m ), so such an m^{\prime} must exist. We are implicitly using the fact that we can always fix TR to the nearest \theta (the slope of the inclined wall). We can summarize these observations with the following equation (3.6) 0\leq TR-m\ll\theta, noting that the asymptotic is independent of \varepsilon . Substituting this into ( 3.5 ), and once again assuming that \varepsilon=O(\theta) , gives \theta m^{\prime}+\theta\varphi m-1=O(\theta). This allows us to solve for m^{\prime} : m^{\prime}=\theta^{-1}+O(\varphi m). Combining this with ( 2.8 ) gives (3.7) m-m^{\prime}\ll\varphi^{-1}. 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^{\prime} , as it is dependent upon \varepsilon . 4. Proof of Theorem 1 Packing T We can now apply our two packing algorithms to complete the proof of Theorem 1 . Recall that we had not yet fixed the width of the trapezoid T . Now, the inclined wall of T was inclined at an angle \theta\asymp h^{-1/2} (see ( 1.1 )). Observe that with this choice of \theta , we must have m,m^{\prime}\asymp h^{1/2} , and \varphi,\psi,\varphi^{\prime}\asymp h^{-1/4} . We now fix the width of the upper edge of T so that the first m -length horizontal stack inclined at an angle of \varphi is within O(\sqrt{h}) of the top of T , thereby implying that T has a width on the order of \sqrt{h} (see Figure 7 ). Figure 7. Packing the trapezoid T . To pack T , we apply our two packing algorithms back to back, packing a “sub-trapezoid” at the top of T of height about 2\theta^{-1}\asymp\sqrt{h} . Note that our first choice of \varepsilon can be 0 . We then pack the two vertical stacks along the entire vertical wall. We 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(\sqrt{h}) (see Figure 7 ). Note that at each stage, we are using the same \varphi,\psi,\varphi^{\prime} and m , but that the choices for \varepsilon,\varepsilon^{\prime} and m^{\prime} will change for each iteration of the packing algorithm. However, we can always ensure that \varepsilon\ll\theta , courtesy of ( 3.6 ). Note that we will have to apply our algorithm a total of \asymp\sqrt{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 O(\frac{1}{\sqrt{\theta}}) . To see this, first observe that H^{\prime}_{m-1} in Figure 5 has length at most O(\varphi^{-1}) from ( 3.7 ). Second, note that we can always force \varepsilon\ll\theta , and thus \varepsilon^{\prime}\ll\theta (see ( 3.6 ) and ( 3.1 )). Next, note that there are two large sliver triangles of length O(\theta^{-1}) and angles \theta-\theta^{\prime} and \varphi-\varphi^{\prime} (see Figure 5 ). Thus, from ( 3.3 ) and ( 3.4 ), the area of these triangles is \ll\frac{1}{\sqrt{\theta}} . There is also a small sliver between \overline{P^{\prime}Q^{\prime}} and the rectangle of width \ll\varphi^{-1} . This has an angle trivially bounded by \varphi , and so its area is O(\frac{1}{\sqrt{\theta}}) . Finally, observe that there are \ll\theta^{-1} O(1) -length triangles created through both packing algorithms, and their angles are all \ll\sqrt{\theta} , implying that there total contribution is \ll\frac{1}{\sqrt{\theta}} . Thus, the total amount of wasted space generated through these two packing stages is \ll\frac{1}{\sqrt{\theta}}\ll h^{1/4} . Since we are applying these packing algorithms \asymp\sqrt{h} times, then the total wasted space contributed by packing the sub-trapezoid regions becomes O(h^{3/4}) . We pack the regions at the top and bottom of T trivially, which generates an additional wasted space of O(h^{1/2}) (see Figure 7 ). Thus, the total wasted space generated by packing T is O(h^{3/4}) . Now, the wasted space generated by packing the O(x) vertical stacks inclined at an angle \theta in Figure 3 is O(x\theta) , meaning that our total wasted space is bounded as follows: W(x)\ll\frac{x}{\sqrt{h}}+h^{3/4}. Equalizing the two terms gives a choice of h\sim x^{4/5} , yielding the desired result.