I’ve just uploaded to the arXiv my preprint “Perfectly packing a square by squares of nearly harmonic sidelength“. This paper concerns a variant of an old problem of Meir and Moser, who asks whether it is possible to perfectly pack squares of sidelength for into a single square or rectangle of area . (The following variant problem, also posed by Meir and Moser and discussed for instance in this MathOverflow post, is perhaps even more well known: is it possible to perfectly pack rectangles of dimensions for into a single square of area ?) For the purposes of this paper, rectangles and squares are understood to have sides parallel to the axes, and a packing is perfect if it partitions the region being packed up to sets of measure zero. As one partial result towards these problems, it was shown by Paulhus that squares of sidelength for can be packed (not quite perfectly) into a single rectangle of area , and rectangles of dimensions for can be packed (again not quite perfectly) into a single square of area . (Paulhus’s paper had some gaps in it, but these were subsequently repaired by Grzegorek and Januszewski.)

Another direction in which partial progress has been made is to consider instead the problem of packing squares of sidelength , perfectly into a square or rectangle of total area , for some fixed constant (this lower bound is needed to make the total area finite), with the aim being to get as close to as possible. Prior to this paper, the most recent advance in this direction was by Januszewski and Zielonka last year, who achieved such a packing in the range .

In this paper we are able to get arbitrarily close to (which turns out to be a “critical” value of this parameter), but at the expense of deleting the first few tiles:

Theorem 1If , and is sufficiently large depending on , then one can pack squares of sidelength , perfectly into a square of area .

As in previous works, the general strategy is to execute a greedy algorithm, which can be described somewhat incompletely as follows.

- Step 1: Suppose that one has already managed to perfectly pack a square of area by squares of sidelength for , together with a further finite collection of rectangles with disjoint interiors. (Initially, we would have and , but these parameter will change over the course of the algorithm.)
- Step 2: Amongst all the rectangles in , locate the rectangle of the largest width (defined as the shorter of the two sidelengths of ).
- Step 3: Pack (as efficiently as one can) squares of sidelength for into for some , and decompose the portion of not covered by this packing into rectangles .
- Step 4: Replace by , replace by , and return to Step 1.

The main innovation of this paper is to perform Step 3 somewhat more efficiently than in previous papers.

The above algorithm can get stuck if one reaches a point where one has already packed squares of sidelength for , but that all remaining rectangles in have width less than , in which case there is no obvious way to fit in the next square. If we let and denote the width and height of these rectangles , then the total area of the rectangles must be

and the total perimeter of these rectangles is Thus we have and so to ensure that there is at least one rectangle with it would be enough to have the perimeter bound for a sufficiently small constant . It is here that we now see the critical nature of the exponent : for , the amount of perimeter we are permitted to have in the remaining rectangles increases as one progresses with the packing, but for the amount of perimeter one is “budgeted” for stays constant (and for the situation is even worse, in that the remaining rectangles should steadily decrease in total perimeter).In comparison, the perimeter of the squares that one has already packed is equal to

which is comparable to for large (with the constants blowing up as approaches the critical value of ). In previous algorithms, the total perimeter of the remainder rectangles was basically comparable to the perimeter of the squares already packed, and this is the main reason why the results only worked when was sufficiently far away from . In my paper, I am able to get the perimeter of significantly smaller than the perimeter of the squares already packed, by grouping those squares into lattice-like clusters (of about squares arranged in an pattern), and sliding the squares in each cluster together to almost entirely eliminate the wasted space between each square, leaving only the space around the cluster as the main source of residual perimeter, which will be comparable to about per cluster, as compared to the total perimeter of the squares in the cluster which is comparable to . This strategy is perhaps easiest to illustrate with a picture, in which squares of slowly decreasing sidelength are packed together with relatively little wasted space:

By choosing the parameter suitably large (and taking sufficiently large depending on ), one can then prove the theorem. (In order to do some technical bookkeeping and to allow one to close an induction in the verification of the algorithm’s correctness, it is convenient to replace the perimeter by a slightly weighted variant for a small exponent , but this is a somewhat artificial device that somewhat obscures the main ideas.)

## 41 comments

Comments feed for this article

8 February, 2022 at 8:08 pm

AnonymousI think you meant the link in the first sentence of this post to send you to arXiv. Instead it seems to just send you to the blog post itself.

[Corrected, thanks – T.]8 February, 2022 at 9:55 pm

domotorpHere is the link: https://arxiv.org/abs/2202.03594

8 February, 2022 at 10:56 pm

AnonymousThank you!

8 February, 2022 at 9:04 pm

waltonmathI think you’re missing a set of parentheses in “is it possible to perfectly pack rectangles of dimensions {1/n \times 1/n+1}”

[Corrected, thanks – T.]9 February, 2022 at 1:48 am

DaveWonderful stuff! Thanks!

9 February, 2022 at 3:43 am

Liewyeethanks for giving another possibility of square partition，more beautiful and elegant.（ and I should say “divide a square evenly”in the last situation follows the last blog～）

9 February, 2022 at 3:23 am

Oliver KnillI like the elegance of the theorem. Of course, it would be interesting to know your personal guess whether the result holds also in the case t=1, where it is a Meir-Moser problem. Only having briefly looked at things yet, it is also not clear to me what happens for t>1. Is it an obvious case where one can pack things? In this zeta function context it would also be interesting to know whether the geometric packing problem could make any sense for s=2t complex. The “area” makes sense by analytic continuation but the packing problem might not have an analytic continuation. [Lastly as this has been mentioned in a comment, I was for a second also stuck with 1/n+1 but decided there is absolutely no way to interpret this differently than 1/(n+1). ]

9 February, 2022 at 8:47 am

Terence TaoMy feeling is that the greedy-type algorithms that have been used to handle the case will not work for the cases, because of the unfavorable relationship between the perimeter of the squares already used and the area of the squares remaining which suggests (unless one somehow finds an _extremely_ efficient packing algorithm) that the maximum width of the rectangles remaining will not stay above the width of the largest square that is yet to be packed, although there is perhaps some hope of clever trickery to get around this problem in the critical case.

(ADDED LATER): In a bit more detail: suppose one has already packed all the squares of sidelength for into a square of area , leaving a remaining area of left to pack, which we view as a union of disjoint rectangles of width and height , thus . Now if all the remaining rectangles have width less than , then it is now impossible to fit in the next square into any of the remaining rectangles (though it is perhaps conceivable that one could fit it into some union of the rectangles , but this would require a substantial reworking of the method in order to keep the rectangles sufficiently adjacent to each other that this becomes possible.) So we would like to ensure that . The simplest way to ensure this, given the area bound , is to obtain a bound of the form , that is to say we would like the total perimeter of all the rectangles in the unpacked space to be small. This looks very difficult to achieve; even the most efficient packing algorithms that I know of will keep the perimeter of the unpacked region roughly unchanged, or increase very slowly, but without a lot of algebraic miracles to ensure a "flush fit" of squares, I don't see how to achieve packings that _decrease_ the perimeter over time, or at least keep it smaller than a small absolute constant. In comparison, the perimeter of the squares already packed is for large , which (barely) diverges to infinity as goes to infinity. It may still be that a perfect packing of the squares of sidelength , is possible here (at least for large enough), but I think it would require a much more sophisticated algorithm than the greedy type algorithms used here.

I'm not sure how to make sense of a complex-analytic packing problem, unless perhaps one wants to consider tilings where the locations of the squares depend in an analytic fashion on t. But my first reaction is that this is a primarily combinatorial problem with no complex analytic structure.

9 February, 2022 at 9:31 am

AnonymousIt should be remarked that the Riemann mapping theorem has a proof via circle packing – so it may indicate a similar possibility of using squares packing to approximate analytical functions (or analytical mappings).

24 February, 2022 at 9:07 pm

Jonathan MastrogiacomoMy questions are as follows:

1. How could an algorithm that is, at its core, “greedy”, as admitted, form part of the basis of a “perfect” solution?

2. What are we to do with what Christopher Langan said in his book, and theory of everything:

“Of all mathematical structures, language is the most general, powerful and necessary. Not only is every formal or working theory of science and mathematics by definition a language, but science and mathematics in whole and in sum are languages”

These questions now lead me to quote Proverbs 15:27 ESV, which says:

“Whoever is greedy for unjust gain troubles his own household”

I think what we should all do at this point is ask ourselves the following questions:

1. Which gains are just

2. What is the proper affair of a household

Let me know

Anyone

9 February, 2022 at 3:34 am

AnonymousIs it possible to express RH (using these methods) in terms of a similar packing problem?

9 February, 2022 at 5:10 am

AnonymousThanks. And managed to understand most it. Consulting job coming up for Amazon trucks and shipping containers to maximise profits!

9 February, 2022 at 12:29 pm

AnonymousA naive question: is it known whether there exists a sequence of side-lengths such that diverges (but converges), yet it is not possible to find a and perfectly pack squares of side-lengths into a square of area ? (The truncation being necessary to avoid the obvious obstruction of e.g. the sequence beginning with two large squares and then all other squares being substantially smaller.)

9 February, 2022 at 3:04 pm

Terence TaoThis is a good question! If the sequence decays sufficiently quickly, e.g., , then I’m pretty sure it is not possible to pack squares of sidelength perfectly into any square (or rectangle) just from perimeter considerations, but creating a counterexample with divergent is very close to the original Meir-Moser problem which addresses the case . It seems kind of hard actually to establish negative results in which one can exclude perfect packings from existing; basically the only obstruction I know of is if the first few squares leave behind a region that necessarily has larger perimeter than all the remaining squares put together, but this of course not an obstruction in the infinite perimeter case.

9 February, 2022 at 1:51 pm

AnonymousDo you know if anyone has done work on an analogous higher-dimensional version of this problem — say, a cube-packing problem? If so, do the methods you use here generalize?

9 February, 2022 at 2:57 pm

Terence TaoThere are some results in higher dimensions; for instance in this recent paper of Januszewski and Zielonka, the cubes of sidelength were packed perfectly into a rectangular box in the range . I'm hoping to interest one of my postdocs in the question of whether the methods in this paper also apply in this three-dimensional case.

9 February, 2022 at 3:09 pm

AnonymousThank you for your reply. I’ll take a look at that paper.

10 February, 2022 at 6:50 am

Sandy GanzellIs there an obvious reason an analogous question for circles would be false? For example (though perhaps this is too naive), could a sequence of circles of harmonic (or nearly harmonic) radius be packed into a circle of radius ?

10 February, 2022 at 10:06 am

AnonymousNice question. I hope Dr. Tao will also compare and contrast on sphere packing vs. square packing, for those who are new to the problem.

10 February, 2022 at 1:43 pm

Terence TaoI don’t see any obstruction to this, but it is likely harder to prove than the analogous problem for squares. With squares, once one packs a finite number of squares inside a square, the remaining region can be partitioned fairly efficiently into rectangles, which allows for efficient packing algorithms. When one packs a finite number of circles into circles, the remaining regions decompose into various circular triangles of various eccentrities; it may be possible to adapt the existing packing arguments to this setting, though I don’t know if it is efficient enough to get as close to the harmonic radius case as one can in the square case.

8 March, 2022 at 10:08 pm

AnonymousDo you know if there has been any work done on this problem?

9 March, 2022 at 8:17 am

Terence TaoSome people in my research group are looking into this question currently.

10 February, 2022 at 2:23 pm

AnonymousThis is by far not my area of expertise, but I wonder whether almost-perfect packings could be used to obtain a perfect packing? That is, suppose that for all we can pack the squares into a square of area . Can we then pack the squares into a square of area ?

[Yes, this follows from a standard compactness argument, and appears to have first been observed in this context by Martin. -T]13 February, 2022 at 3:02 pm

AnonymousJust a minor typo… In the abstract of your paper, you mention that this was “previously known for ", while in the third paragraph of the first page of your paper, you mention that "an affirmative answer to this question was given in the range " (one inequality is strict, the other is not).

[Thanks, this will be corrected in the next revision of the ms – T.]13 February, 2022 at 9:37 pm

AnonymousAlso, there is a typo in the first sentence of Proposition 2.2 of your paper, you say, “suppose that is a rectangle of with dimensions…”

[Thanks, this will be corrected i the next revision of the ms. -T]13 February, 2022 at 11:43 pm

AnonymousIn the first (unnumbered) equation of page 5 in your paper, you bound the total weighted perimeter by . I’m wondering if that should be , or am I just missing something?

[This was a typo, and will be corrected in the next revision of the ms. -T]13 February, 2022 at 11:44 pm

Keiju SonoIn page5, line 12

I can’t understand why the exponent of is .

It’s no problem, but I think is more natural.

[This was a typo, and will be corrected in the next revision of the ms. -T]15 February, 2022 at 9:28 am

Keiju SonoI guess

Page7, line 10. $w(R)$ should be $h(R)$

Page8, line -8. $y_{i,j+1}=y_{i,j}$ should be $y_{i,j+1}=y_{i,j}+n_{i,j}^{-t}$

Page 9, lines -5~-4. $M_{i}$, $M_{j}$ should be $M_{1}$, $M_{2}$ respectively.

[Thanks, this will be corrected in the next revision of the ms. -T]20 February, 2022 at 5:58 pm

AnonymousOn page 7 of your paper, in the third and fourth equations, I’m thinking that the ‘s should probably be ‘s. In addition, in the fourth equation, I’m thinking that the should be .

[Thanks, this will be corrected in the next revision of the ms – T.]21 February, 2022 at 10:54 pm

AnonymousIn the first equation of page 7 of your paper, I’m wondering if the upper bound of the sum should be instead of .

[Thanks, this will be corrected in the next revision of the ms – T.]21 February, 2022 at 10:58 pm

AnonymousSame sort of thing in the second equation page 7… I think the lower bound in the sum might should be instead of .

[Thanks, this will be corrected in the next revision of the ms – T.]8 March, 2022 at 2:33 pm

AnonymousOn page 4, when deducing Theorem 1.1 from Proposition 2.1, you state that you use a standard compactness argument (citing Martin) to complete the proof. Why do we need Martin’s result here?

8 March, 2022 at 2:51 pm

Terence TaoMartin’s argument is cited just an example of the type of compactness argument used here that happens already to be in the literature on this type of problem. One can use a number of other (closely related) compactness arguments to get from a finite packing of arbitrarily many squares in a sequence to an infinite packing of all the squares in that sequence; for instance, one can use Tychonoff’s theorem, the Arzeli-Ascoli theorem, or the compactness theorem in first-order logic. (One could also use nonstandard analysis to transfer the finite packing to an infinite packing, though this is a somewhat gratuitious use of that formalism.)

8 March, 2022 at 7:54 pm

AnonymousHey Mr Tao could I have some of your time for an idea I have come up for an application of the natural numbers?

9 March, 2022 at 11:37 pm

Keiju Sonop.8

In the definition of y_{i,j}, maybe j’ runs from 0 to j-1.

[Thanks, this will be corrected in the next revision of the ms – T.]19 March, 2022 at 7:25 am

Keiju SonoI think there are some minor mistakes in your argument on disjointness of the interiors of two different squares.

I considered the following modification.

1. If i’≦i and j’>j, y_{i,j}+n_{i.j}^{-t}≦y_{i’,j’}. Hence the interior of S_{i,j} lies below of the interior of S_{i’,j’}. Similarly if i≦i’, j>j’.

2. If i'<i and j'≦j, x_{i',j'}+n_{i',j'}^{-t}≦x_{i,j}. Hence the interior of S_{i',j'} lies left to the interior of S_{i,j}. Similarly if i<i', j≦j'.

(It is very possible that I'm mistaken.)

[Oops, the roles of and need to be switched in several places in this part of the argument. This will be corrected in the next revision of the ms – T.]7 April, 2022 at 8:33 pm

Keiju SonoPage9, (3.4)

The surrounded rectangle will be

[x_{i+1,j},x_{i+1,j+1}]×[y_{i+1,j+1},y_{i,j+1}].

[This will be corrected in the next revision of the ms, thanks – T.]8 April, 2022 at 12:44 pm

AnonymousAre these 3D packing problems related to the Erdos-Graham problem (as a 1D packing problem for Egyptian fraction representation of 1)?

8 April, 2022 at 12:47 pm

AnonymousCorrection: 3D should be 2D

12 April, 2022 at 8:19 pm

Keiju SonoI’m now trying to generalize your theorem to the problem of perfectly packing a square by squares of sidelength f(n)^{-t}. I’m also trying to give effective lower bounds for M and N_{0} depending on f and t.

In this process I thought that your lower bound for M (which is exp(C/δ), where C is an absolute constant) might be too small.

As far as I considered, M should be larger than (at least) (4/(1-t))^(2/(1-t)) as t→1 to justify your argument to obtain (2.7) in page 5.

It’s a bit difficult for me to explain this reason in this form, so I’ve made a PDF file and I’ll send you by e-mail. I hope you will read some of it, although it may contain some of my misunderstandings.

[This will be corrected in the next revision of the ms – T.]15 April, 2022 at 10:29 am

AnonymousI’ve just uploaded a preprint of a three-dimensional analogue of this result: https://arxiv.org/abs/2204.06038.