Careless packing - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T19:07:11Z http://mathoverflow.net/feeds/question/90331 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/90331/careless-packing Careless packing David Feldman 2012-03-06T04:39:54Z 2012-03-07T08:02:37Z <p>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:</p> <p>a) the series with these terms sums to 1; </p> <p>b) no process of sequentially packing open intervals with these lengths into the unit interval $[0,1]$ can ever come to an impasse.</p> <p>Many other sequences also enjoy this property.</p> <p>Question: has this type of phenomena ever appeared in the literature?</p> <p>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.</p> http://mathoverflow.net/questions/90331/careless-packing/90345#90345 Answer by Johan Wästlund for Careless packing Johan Wästlund 2012-03-06T10:44:07Z 2012-03-06T17:18:03Z <p>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&lt;4/3$. </p> <p>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. </p> http://mathoverflow.net/questions/90331/careless-packing/90389#90389 Answer by Boris Bukh for Careless packing Boris Bukh 2012-03-06T18:42:37Z 2012-03-07T08:02:37Z <p>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&lt;\alpha&lt;1.1716$, then we never get stuck provided we have placed enough balls already. </p> <p>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 &lt; N} \pi(n^{-\alpha/2}+N^{-\alpha/2})^2=\sum_{n &lt; 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&lt;4-2\sqrt{2}=1.17157\ldots$.</p> <p><em>Edit</em>: 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.</p> <p><em>Edit 2</em>: 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.</p>