# Careless packing

The sequence $\frac{1}{2}, \frac{1}{2\cdot 2}, \frac{1}{3\cdot 4}, \frac{1}{4\cdot 6}, \frac{1}{5\cdot 8}, \frac{1}{6\cdot 10},\ldots$ has a curious property, as follows:

a) the series with these terms sums to 1;

b) no process of sequentially packing open intervals with these lengths into the unit interval $[0,1]$ can ever come to an impasse.

Many other sequences also enjoy this property.

Question: has this type of phenomena ever appeared in the literature?

In particular I wonder about possible decompositions (up to a set of measure zero) of, say, the unit square (or unit sphere) into open sets which enjoy the corresponding property.

• I did not know such a sequence exists! Cool! The reason (b) holds is the divergence of the harmonic series, so I do not think there is a generalization to squares in 2d, say. The case of 1xL rectangles of course follows trivially from the 1d case. – Boris Bukh Mar 6 '12 at 7:58
• John Shier, a retired physicist turned artist, has an interest in sequences of this type for use in computer-generated abstract art. He has a nice write-up at john-art.com/stat_geom_described_v3.pdf (and you can get to more by backing up the url). – Barry Cipra Mar 6 '12 at 13:58
• It is easy to characterize all sequences $a_1,a_2,\dots$ with this property: A necessary and sufficient condition is that $(k+1)a_{k+1}\leq 1−\sum_{j=1}^ka_j$ for all $k$. The above sequence $1/2,1/4,\dots$ is thus the optimal sequence starting with $1/2$. – Roland Bacher Mar 8 '12 at 14:59
• Sorry for the naive question, but, can you please explain what do you mean by "come to an impasse"? What happens if you take the following sequence: 0.5, 0.25, 0.125, 0.125, 0, 0, ...? – Erel Segal-Halevi Dec 9 '13 at 10:18
• As a (very belated) example: If I place the first two intervals at $[0.1, 0.6]$ and $[0.7, 0.95]$, then there is now nowhere I can place the third interval. While there's enough space overall for it $(0.25)$, the space is split up into pieces of size smaller than $0.125$. – Kevin P. Costello Mar 9 '17 at 22:48

This is a rigorous justification of Johan Wästlund's intuition. Namely, I will show that if we tile a round ball $B$ of area $\pi\zeta(\alpha)$ by round balls of area $\pi/n^\alpha$ for some $1<\alpha<1.1716$, then we never get stuck provided we have placed enough balls already.

For later use note that the radius of $n$'th ball is $n^{-\alpha/2}$. Suppose we have placed the first $N-1$ balls. Let $U$ be the union of them, and let $U'$ be the complement of $B$. We can place $N$'th ball iff the $N^{-\alpha/2}$-neighborhood of $U\cup U'$ does not contain all of $B$. We can bound the area of the neighborhood of $U$ by $$\sum_{n < N} \pi(n^{-\alpha/2}+N^{-\alpha/2})^2=\sum_{n < N} \pi(n^{-\alpha}+2n^{-\alpha/2}N^{-\alpha/2}+N^{-\alpha})=\pi(\Sigma_1+\Sigma_2+\Sigma_3).$$ We have $\Sigma_1\approx \zeta(\alpha)-\frac{N^{1-\alpha}}{\alpha-1}$, $\Sigma_2\approx 2N^{-\alpha/2} \frac{N^{1-\alpha/2}}{1-\alpha/2}=\frac{2}{1-\alpha/2}N^{1-\alpha}$ and $\Sigma_3\approx N^{1-\alpha}$. The area of the neighborhood of $U'$ is less than $2\pi\zeta(\alpha)^{1/2}N^{-\alpha/2}=o(N^{1-\alpha})$. The result follows since $$\frac{1}{\alpha-1}-\frac{2}{1-\alpha/2}-1$$ is positive for $\alpha<4-2\sqrt{2}=1.17157\ldots$.

Edit: Actually, the argument works for any centrally symmetric convex shapes. The only thing I used about balls is that the Minkowski sum of a ball and a ball is a ball of the correct size.

Edit 2: It is clear that if one wants a stronger conclusion that one never gets stuck, then one needs to make explicit errors in the asymptotic estimates above. Then one can either decrease $\alpha$ to subsume those errors, or to consider the balls of area $\pi m^{-\alpha},\pi(m+1)^{-\alpha},\dotsc$ in a ball of total area $\pi\sum_{n\geq m} n^{-\alpha}$ to reduce the errors. This mirrors the suggestion of John Shier in the write-up linked above.

• Doesn't the Nth neighborhood depend on 2N rather than on N? Gerhard "Ask Me About System Design" Paseman, 2012.03.06 – Gerhard Paseman Mar 6 '12 at 20:33
• No, think of the centers of the balls. $r$-neighborhood of a set $U$ is the set of all the points $p$ such that the ball centered at $p$ intersects $U$. – Boris Bukh Mar 6 '12 at 20:40
• Are you accounting for the boundary of the packed region? You won't be able to squeeze a ball on the outer edge if the others are placed too near the edge. Not that I am against the proof, I am just concerned that the error is larger than you think. Gerhard "Still Worried About The Calculation" Paseman, 2012.03.06 – Gerhard Paseman Mar 6 '12 at 22:37
• So one should look now to raise that upper bound 1.1716, right? Some sort of sieve should improve the area estimate. – David Feldman Mar 6 '12 at 23:38
• Great! But as Gerhard points out, there is also a problem near the boundary of the box. There is an unavailable region of area at most $2\pi\zeta(\alpha)^{1/2}N^{-\alpha/2}$. The estimate becomes a little messier, but it's clear it will work for all $N$ if $\alpha$ is small. – Johan Wästlund Mar 7 '12 at 7:23

My guess is that such sets exist in all dimensions. Here's a partial answer that explains why. Let's consider tilings of a rectangular box of area $\zeta(\alpha)$ by axis-parallel rectangular tiles of areas $1/n^\alpha$ for some $\alpha>1$. We allow the tiles to be squeezed and stretched by axis-parallel linear transformations as long as the area is preserved. Suppose that we have carelessly placed the first $N$ tiles. Then the remaining space can be divided into $3N+1$ rectangular sub-boxes. Since the next tile has area roughly $(\alpha-1)/N$ times the remaining space, we can fit the next tile into the largest sub-box provided $\alpha<4/3$.

If we don't permit squeezing and stretching, we might get into trouble because all sub-boxes that are large enough are too oblong. But it seems that if $\alpha$ is small enough and we subdivide in some reasonable way (say to minimize the total perimeter of the sub-boxes), then this should not happen.

• For those for whom the appearance of $3N+1$ is not immediately obvious: Think of a line that sweeps the box from top to bottom. Above the line there are partially completed rectangles that rectangulate the free area above the line. Each time the sweep line meets a placed rectangle R, any partially completed rectangle is declared completed, and the vertical sides of R are two vertical lines that define three new rectangles to be completed. This is in essence a "line sweep algorithm" (see wikipedia) applied to rectangulation of the box minus rectangles. – Boris Bukh Mar 6 '12 at 18:00