26
$\begingroup$

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.)

$\endgroup$
3
  • 3
    $\begingroup$ Answers regarding this similar problem might suggest some possible approaches: mathoverflow.net/questions/34145/… $\endgroup$ Aug 8, 2017 at 14:41
  • $\begingroup$ @YoavKallus Thanks! The comment by Timothy Chow referencing Marc Paulus's paper An algorithm for packing squares seems particularly relevant. sciencedirect.com/science/article/pii/S0097316597928363 $\endgroup$ Aug 8, 2017 at 14:53
  • 6
    $\begingroup$ 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$. $\endgroup$
    – dhy
    Aug 8, 2017 at 15:04

3 Answers 3

23
$\begingroup$

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

$\endgroup$
7
  • 4
    $\begingroup$ 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. $\endgroup$ Aug 8, 2017 at 19:55
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 8, 2017 at 19:58
  • $\begingroup$ 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. $\endgroup$
    – Jeff Egger
    Aug 8, 2017 at 20:53
  • $\begingroup$ 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. $\endgroup$ Aug 8, 2017 at 21:51
  • $\begingroup$ 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}$. $\endgroup$
    – Pedro A
    Aug 9, 2017 at 10:36
16
$\begingroup$

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?

$\endgroup$
11
  • 3
    $\begingroup$ 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. $\endgroup$ Aug 8, 2017 at 16:26
  • 4
    $\begingroup$ 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. $\endgroup$ Aug 8, 2017 at 19:48
  • 5
    $\begingroup$ Perhaps this could also be due to an assumption in the paper earlier that width is considered smaller (i.e., $l\geq w$)? $\endgroup$ Aug 8, 2017 at 21:12
  • 5
    $\begingroup$ I think your argument is somewhat useful, though. $\endgroup$ Aug 8, 2017 at 23:42
  • 3
    $\begingroup$ 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. $\endgroup$ Aug 9, 2017 at 15:23
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.