Careless packing - MathOverflow

Careless packing

2012-03-06T04:39:54Z

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.

Answer by Johan Wästlund for Careless packing

2012-03-06T10:44:07Z

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.

Answer by Boris Bukh for Careless packing

2012-03-06T18:42:37Z

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.