26

My question is prompted by this illustration from Eugenia Cheng’s book Beyond Infinity, where it appears in reference to the Basel problem.

Illustration of squares of side 1/2, …, 1/11 in three quarters of a unit square

Is it known whether the infinite set of squares of side $\frac{1}{2}, \frac{1}{3}, \frac{1}{4},...$ can be packed into three quarters of a unit square?

(It doesn't seem obvious that the illustrated packing could be continued to infinity.)

Robin Houston
  • 2,756
  • 3
    Answers regarding this similar problem might suggest some possible approaches: https://mathoverflow.net/questions/34145/can-we-cover-the-unit-square-by-these-rectangles?rq=1 – Yoav Kallus Aug 08 '17 at 14:41
  • @YoavKallus Thanks! The comment by Timothy Chow referencing Marc Paulus's paper An algorithm for packing squares seems particularly relevant. http://www.sciencedirect.com/science/article/pii/S0097316597928363 – Robin Houston Aug 08 '17 at 14:53
  • 7
    I think this actually should be much easier than the other problem, just because $\frac{\pi^2}{6}-1<\frac{3}{4},$ which gives you a chance of reducing this to a finite computation. In particular if there is an $n$ so that you can pack squares of side lengths $1/2\cdots, 1/(n-1)$ and $n$ right triangles of side length $2/n$, then you can also pack the squares in the question. This is because you can pack squares of side length $1,1/2,\cdots$ in a right triangle of side length $2$. – dhy Aug 08 '17 at 15:04

3 Answers3

23

The standard simple proof that $\sum_{n=1}^\infty \frac1{n^2}$ converges is to round each $n$ down to the nearest $2^k$; this rounds each $\frac1{n^2}$ up to the nearest $\frac1{2^{2k}}$. In fact, one gets $2^k$ copies of $\frac1{2^{2k}}$ for each $k$; hence $$\sum_{n=1}^\infty n^{-2} < \sum_{k=0}^\infty 2^k\frac1{2^{2k}} = \sum_{k=0}^\infty \frac1{2^{k}} = 2.$$

This is a sloppy estimate, and one way of improving it is to round each $n$ down to the nearest $2^k$ OR $3\cdot2^{k}$. The first cluster of $\frac1{2^{2k}}$s, comprising a single $\frac1{2^0}$, is unaffected; all subsequent clusters cleave into $2^{k-1}$ copies of $\frac1{2^{2k}}$ and $2^{k-1}$ copies of $\frac1{(3\cdot2^{k-1})^2}$. In this way, we get $$\sum_{n=1}^\infty n^{-2} < 1+\sum_{k=1}^\infty 2^{k-1}\frac1{2^{2k}} + \sum_{k=1}^\infty 2^{k-1}\frac1{(3\cdot2^{k-1})^2} \\ = 1+\sum_{k=1}^\infty \frac1{2^{k+1}} + \frac19\sum_{k=1}^\infty \frac1{2^{k-1}} = 1 + \frac12+\frac29.$$

This sum (minus the irrelevant first term) can be represented geometrically as in the following image, which is reasonably similar to the one you posted. (But the shaded region has area $\frac16+\frac19=\frac5{18}>\frac14$.)

enter image description here

Yoav Kallus
  • 5,926
Jeff Egger
  • 488
  • 2
  • 6
  • 4
    That's a nice solution. I might add that the rows that start with 1/12, 1/24, 1/48, and so on can be rotated to columns and moved into the shaded region between 1/2 and 1/3 to obtain a solution to the problem in the original post. – Yoav Kallus Aug 08 '17 at 19:55
  • 2
    You might observe that the "packing area" in your image can be dissected and rearranged (without cutting any interior squares) into (a continuation of) the image in the question. Gerhard "This Makes 'Yes' Appropriately Explicit" Paseman, 2017.08.08. – Gerhard Paseman Aug 08 '17 at 19:58
  • Thank you! You are, of course, both correct---my main excuse is that I drew what was easiest for me to draw. (Note how the paper has been strategically folded.) I also wanted to emphasise the two geometric series (one up the left-hand side, the other up the right-hand side). If I weren't a dunce at computer graphics, I'd make an animation to show how the various pieces can be rearranged. – Jeff Egger Aug 08 '17 at 20:53
  • Instead of an animation, cut your square in half and rotate the right half. Then take the part that "sticks out" of the unit square and duplicate it to the appropriate place in the unit square, and draw an arrow showing the correspondence. Gerhard "We Can Imagine The Motion" Paseman, 2017.08.08. – Gerhard Paseman Aug 08 '17 at 21:51
  • If I didn't overlook anything, this does prove that total area is less than 3/4, but how does this prove that it is actually possible to put the squares? Perhaps there might be some "leftover space between squares" that can't be dealt with... Although my intuition says it is indeed possible, I think this part should also be explicitly addressed in an answer to this question. For example, I doubt this could be done with circles of areas $\frac{1}{n^2}$. – Pedro A Aug 09 '17 at 10:36
  • @Hamsteriffic See the diagram at the end of the post, which shows how the squares can be placed. – Robin Houston Aug 09 '17 at 13:56
  • @RobinHouston Ah, I see now, thank you. Originally I didn't understand the image, when I looked at the first moment, the 1/5 and 1/7 fractions looked like 1/4. – Pedro A Aug 09 '17 at 14:24
15

Note: This answer is wrong. There are two problems:

  1. The claim of Lemma 1 should presumably be read in the context of the global assumption in Paulhus's paper that $w\leq l$. This assumption invalidates the instance I wanted to use (i.e. $l=\frac12$, $w=1$).

  2. The proof of the lemma seems flawed, as mentioned below and succinctly summarised in Yoav Kallus’s comment. Another example where the packing constructed for the proof does not fit is $l = \frac{9}{5}$, $w = \frac{7}{9}$, $n=2$, which I mention only since (unlike the example below) it has $w<l$.

The answer as written is next, followed by the note of doubt I added after trying to understand the proof.

The answer is yes.

Thanks to the comment by Yoav Kallus above, and a comment by Timothy Chow on the question he linked to, I found the paper An algorithm for packing squares by Marc M. Paulhus. (Journal of Combinatorial Theory, Series A, Volume 82, Issue 2, 1998, Pages 147-157)

Lemma 1 of that paper shows: All the reciprocal squares from n to infinity can be packed in a rectangle of length $l$ and width $w$ provided $$n\geq \frac{1+l}{wl}$$

With $l=1/2$ and $w=1$, this shows that we could place the square of side 1/2 in such a way that the remaining space is a rectangle of dimensions 1 x 1/2, and then pack the remaining squares into that rectangle using Paulhus's procedure.

It doesn't obviously answer the question of whether the packing could be completed if started as shown. In particular, can the squares of side 1/3, 1/4, etc. be packed into two unconnected squares of side 1/2?

Added previously: I am not convinced that the proof of Lemma 1 used above is correct. As I understand it (specialising to the case $l=\frac 12$, $w=1$ for concreteness) the idea is to pack the squares in rows like this:

packing squares of side 1/3, 1/4, … into a rectangle of dimensions 1/2 x 1

If the first square in row $i$ has side $1/{n_i}$, then $n_0=3$ and $n_{i+1}=\lfloor \frac{3}{2}n_i\rfloor$.

But then the total height of the first seven rows is already $$\frac 13 + \frac 14 + \frac 16 + \frac 19 + \frac 1{13} + \frac 1{19} + \frac 1 {28} > 1.$$

On the other hand this arrangement is not optimal, since the sixth row has squares $\frac 1{19}, \dots, \frac 1{27}$ but we could fit up to $\frac 1{30}$. So perhaps the claim is still true, notwithstanding the unconvincing proof?

Robin Houston
  • 2,756
  • 3
    The top-left square in the illustration in the question includes a free rectangle of dimensions $1/4\times3/8$. By Lemma 1, this should be enough to hold reciprocal squares for $n\ge14$. I believe 12 and 13 comfortably fit in the free space in the bottom-right square, next to the 11. – Emil Jeřábek Aug 08 '17 at 16:26
  • 4
    You seem to be correct that the proof is in error. Particularly, I see a false deduction in the last set of inequalities: the proof claims that if $w\ge(1+l)/(n_0 l)$ ($=(1/n_0)\sum_{i=0}^\infty (1/(1+l))^i$), then $w\ge \sum_{i=0}^{\infty} 1/n_i$ follows. That would make sense if we had $n_i\ge n_0 (1+l)^i$, but the inequality shown earlier is actually reversed. – Yoav Kallus Aug 08 '17 at 19:48
  • 5
    Perhaps this could also be due to an assumption in the paper earlier that width is considered smaller (i.e., $l\geq w$)? – LegionMammal978 Aug 08 '17 at 21:12
  • 5
    I think your argument is somewhat useful, though. – Takahiro Waki Aug 08 '17 at 23:42
  • 2
    @RobinHouston Even if you put as many squares as possible into each row, the height of the first seven rows will be $\frac{1}{3}+\frac{1}{4}+\frac{1}{6}+\frac{1}{9}+\frac{1}{14}+\frac{1}{22}+\frac{1}{35}>1$. – Peter Mueller Aug 09 '17 at 07:29
  • With $l\ge w$, my first comment still applies, putting $n\ge15$ in the $1/4\times3/8$ rectangle, and 12, 13, 14 next to 11. Having said that, I don't think the lemma is true this way, the assumption $l\ge w$ seems irrelevant for the faulty proof. Even if this answer is deleted, someone should probably ask Paulhus. – Emil Jeřábek Aug 09 '17 at 08:39
  • 3
    I would recommend not deleting this answer if only because it may be the only existing documentation of a problem with Paulhus's proof. According to MathSciNet, Paulhus last published a mathematical paper about 15 years ago, so it may not be trivial to track him down, or even if it is, he may not be interested in working to repair the proof. – Timothy Chow Aug 09 '17 at 15:23
  • 1
    Okay, I'll tidy it up and leave it for posterity. – Robin Houston Aug 09 '17 at 18:00
  • 1
    I believe I can prove the lemma with the bound $n\ge\frac{1+l+w}{wl}=(1+l^{-1})(1+w^{-1})-1$, or by a little more elaborate proof, with the slightly better bound $n\ge(1-e^{-l})^{-1}(1+w^{-1})-\frac12$. – Emil Jeřábek Aug 10 '17 at 08:07
  • The denominators of the sum are shown here: https://oeis.org/A048577 – Fred Daniel Kline Aug 14 '17 at 19:32
  • 3
    It appears that the errors in Paulhus's paper have now been fixed: https://mathscinet.ams.org/mathscinet-getitem?mr=3873959 – Terry Tao Feb 04 '22 at 15:37
0

Using Clive Tooth's heuristic for this similar (but more difficult) problem https://math.stackexchange.com/questions/2645195/can-the-squares-with-side-1-n-be-packed-into-a-1-times-zeta2-rectangle

I was able to pack the first 10^9 squares into the 3/4 unit square. Not a proof, of course, but evidence, at least, that no "bottleneck" occurs when placing the smallest sized squares.

Brian Trial
  • 1
  • 1