Can the squares with side $1/n$ be packed into a $1 \times \zeta(2)$ rectangle?

Question

As is well-known the total area of the squares with sides $1, 1/2, 1/3, 1/4, \ldots$ is $\pi^2/6$. But can a $1 \times \pi^2/6$ rectangle be tiled with those squares? I have packed the first $10^{10}$ such squares into the rectangle using a simple greedy algorithm.

The packing program represents the available space by a set of rectangles. I call these rectangles splinters. So, to start with, there is exactly one splinter. The program records the width and length of each splinter - with the convention that the length is always greater than, or equal to, the width. When trying to pack a square of side k (where k = 1/n, for some n) it will find the splinter with the smallest width that will accommodate the square. If there are several suitable smallest-width splinters, all with the same width, the program chooses one arbitrarily. The program does not need to check that the length of the splinter is sufficient to accommodate the square because the length of a splinter is always greater than or equal to its width.

Let the chosen splinter have width W and length L. That splinter is deleted from the list of splinters and two new splinters are inserted with dimensions W × (L-k) and k × (W-k). For each new splinter the program must determine which dimension is the new width and which is the new length. By the way, the splinters are held in a binary search tree.

An obvious, but important, optimization is a consequence of the fact that the program, when started, is given a target number of squares to pack. Thus it knows the size of the smallest square it will ever pack. So, if ever it is about to create a splinter with a width less than the side of the smallest square, it can immediately discard it - that space could never be used. In the case of packing 10 billion squares the number of splinters rises to about 2.7 million after about 230 million squares and thereafter slowly declines until, after the 10 billionth square has been packed, just two splinters remain.

Note that, as far as this packing strategy is concerned, the position and orientation of a splinter is unimportant. Equally, which of the four corners of the splinter is chosen as the home for a new square is arbitrary.

Fwiw, I have now packed in a trillion, $10^{12}$, squares.

In my very first attempts at this packing I used Mathematica to do all the arithmetic, and I just specified the long edge of the rectangle as Zeta[2].

Later, I moved away from Mathematica for this job and used unlimited-precision rational arithmetic in a C# program and specified that the long edge was some high precision rational just less than Zeta[2].

Most recently I have been using an approach where (effectively) all the rational numbers used have the same denominator, (d, say). So I can think of the original rectangle to be an array of square dots, each dot being of side 1/d. So, the "1" side would contain d dots, and the Zeta[2] side would have m dots where m/d is just less than Zeta[2].

Each square packed in has its side, 1/n, rounded up to a fraction whose denominator is d. [Obviously I do not need to actually store any denominators - they are all the same.] Thus each square packed covers a square patch of dots.

Using this method I was able to pack $10^{12}$ squares in about 26 hours. The exact value of d does not seem critical. I did the trillion square packing a couple of of times:

• Once with d=11,214,275,663,373,188,676 - which makes m (the number of dots in the long side) just less that $2^{64}$-1 (I use unsigned 64-bit integer arithmetic for all the bookkeeping).

• And once with d=9,419,588,158,802,421,600 - the LCM of the integers from 1 to 46.

Note, however, that d must be a multiple of 6, otherwise the 1/6 square cannot be packed.

Something that surprised me was that relatively small values of d will allow relatively large numbers of squares to be packed:

d=450 is the smallest d that will allow the first 100 squares to be packed. (The 1/101 square fails.)

d=13,104 (=$2^{4}$ × $3^{2}$ × 7 × 13) is the smallest d that will allow the first 1,000 squares to be packed. (The 1/1,003 square fails.)

d=163,800 (= $2^{3} × 3^{2} × 5^{2} × 7 × 13$) is the smallest d that will allow the first 10,000 squares to be packed. (The 1/10,020 square fails.)

d=1,848,000 (= $2^{6} × 3 × 5^{3} × 7 × 11$) is the smallest d that will allow the first 100,000 squares to be packed. (The 1/101,057 square fails.)

d=36,756,720 (=3∗LCM(1 to 17)) allows the first million squares to be packed in, but there are probably smaller values of d which would also allow that packing. With this value of d my program packs in the first million squares in 73 milliseconds. The first failing square with this d is 1/1,352,878.

I now think that the smallest d which allows a million squares to be packed is probably 22,515,570 (=$2×3^{4}×5×7×11×19^{2}$). This d-value first fails on packing the square with side 1/1,000,784. If there is a smaller d which allows the million-square packing, then that d is less than 22 million.

Answer 1

This answer answers the question only approximately, but at least does so rigorously.

Theorem 4 from

Moon, J.W.; Moser, L., Some packing and covering theorems, Colloq. Math. 17, 103-110 (1967). ZBL0152.39502.

states: Let there be given a set of squares of total area $A$ the largest of which has side $D$. Such a set can be packed in any rectangle of area $2A$ and shorter side $B$, if $D\le B$.

Therefore if a packing exists of the largest $n-1$ squares into the rectangle of size $1 \times \zeta(2)$, and $A = \sum^\infty_n {1\over{n^2}}$ is the total area of the remaining squares, the remaining squares fit into a rectangle of size $1 \times \max(1/n, 2A)$ which can be adjoined to the larger one, giving a packing of the entire set of squares into a rectangle of size $1 \times (\zeta(2)+\max(1/n, 2A))$.

Since you state that a packing exists for the first $10^{12}$ squares, this means that a rectangle not much larger than $1 \times \zeta(2)$ certainly can be packed with all the squares (a naive bound on A yields a width of $\zeta(2) + 4\times 10^{-12}$, if I am not mistaken).

Answer 2

This shows a placement of the first 9 squares. The goal is to keep the unused space as contiguous and usable as possible. Note that the 6 is an exact fill, the 7 nearly so but there is a slight gap at the top. (fig. 1/3)

Answer 3

Squares 1-24. Note the 10 and 15 are an exact placement since 1/3 = 1/6 + 1/10 + 1/15. Similarly the 20 and 12 are exact fits. We are keeping a relatively large block of unused space above the 12 and 4. (fig. 2/3)

Answer 4

Squares 1-60. This shows there is not an early bottleneck in this problem, and we continue to preserve a relatively large unused space above the 4. As we start placing squares greater than 60, there is still space above the 8 that can accommodate them, and spaces above the 23 and 47&48 can also be used as squares in the 70 and 80 range need space. This is not a convincing demonstration for a complete solution, but shows it is possible. (fig. 3/3)