# Packing Calculations

Todays problem is from Pugh’s great book “Real Mathematical Analysis“, it’s problem 23 in chapter 1.

Problem Statement:

Let b(R) and s(R) be the number of integer unit cubes in $\textbf{R}^M$ that intersect the ball and the sphere of radius R respectively, centered at the origin. By integer unit cube I mean a unit cube which has its vertices on the integer lattice.

(a) Let m = 2 and calculate the limits

$\textrm{lim}_{R \rightarrow \infty} \frac{s(R)}{b(R)}$ and $\textrm{lim}_{R \rightarrow \infty} \frac{s(R)^2}{b(R)}.$

(b) Take $m \ge 3.$ What exponent k makes the limit

$\textrm{lim}_{R \rightarrow \infty} \frac{s(R)^k}{b(R)}$

interesting?

(c) Let c(R) be the number of integer unit cubes that are contained in the ball of radius R, centered at the origin. Calculate

$\textrm{lim}_{R \rightarrow \infty} \frac{c(R)}{b(R)}.$

(d) Shift the ball to a new, arbitrary center (not on the integer lattice) and re-calculate the limits.

End Problem Statement

This problem doesn’t involve finding a packing but instead involves counting the number of unit cubes after the packing has been chosen (in this case we’re packing a ball with integer unit cubes). So I find it to be a very interesting problem.

The first simplification I make is to only consider the first quadrant of the ball with radius R. By symmetry $s(R) = 4 s_{\textrm{quad 1}}(R)$ and similarly for $b(R) = 4 b_{\textrm{quad 1}}(R),$ where $s_{\textrm{quad 1}}$ and $b_{\textrm{quad 1}}$ are the functions $s$ and $b$ restricted to the first quadrant. For the rest of this solution I only work with the first quadrant. Let $B_R = \{(x, y) \in \textbf{R}^2 : x^2 + y^2 \le R^2, x \ge 0, y \ge 0\}.$ The area of $B_R$ is $\pi R^2/4$ so as a first approximation $b(R) \approx \pi R^2/4.$

After some thought the best way to count the number of unit cubes in $s(R)$ is to imagine tracing out the curve $y = R\sin(\theta), \textrm{ } x = R\cos(\theta)$ as $\theta$ goes from 0 to $\pi/2.$ Let c be the number of unit cubes the curve has been traced through. Initially c = 0. As we trace out the curve, every time $y \in \textbf{N}$ we add 1 to c since the curve has entered a new unit square, similarly if $x \in \textbf{N}$, 1 is added to c. If y and x are both integers then only 1 should be added to c (this happens very rarely so I mostly ignore this case).

For a small example let R = 2. Then x goes from 2 to 0, so $x \in \textbf{N}$ 3 times, similarly y goes from 0 to 2 so $y \in \textbf{N}$ 3 times.

This gives us an initial count of 6 for $s(2)$ but we need to handle the corner cases.

The corner cases are (x = 0, y = 2) and (x = 2, y = 0). Note that x = 0, y = 2 means both x and y are integers so that square was counted twice instead of once, also don’t forget that the square was counted when the curve entered it. So we need to subtract two from 3 + 3 giving 3 + 3 – 2. Also when x = 2, y = 0 this square is again counted twice so we need to subtract 1 from 3 + 3 – 2 giving 3 + 3 – 3 = 3 Thus s(2) = 3.

Example 2: R = 4, x goes from 4 to 0 and y goes from 0 to 4 so we have 5 + 5 – 3 (remember the corner cases) = 7.

From the above derivations $s(R) = 2R - 3.$ To a first approximation the formula for $s(R)$ in m dimensions is $mR.$

To calculate $b(R)$ first note that if the packing of $B_R$ was perfect than b(R) would be $\pi R^2/4.$ It’s not a perfect packing so b(R) is greater than $\pi R^2/4.$ To calculate how much more we first note that all the unit cubes used in counting s(R) have on average half their area in $B_R$ and half their area outside $B_R$ (remember we’re taking the limit to large R, so the result follows from symmetry).

There are $2R - 3$ of these unit cubes that are only half in $B_R.$ So they cover an area of R – 3/2 inside $B_R$ so b(R) must be $\pi R^2/4 - R + 3/2$ (the part of $B_R$ covered by unit cubes that are completely contained in $B_R$) + 2R – 3 (the unit cubes that are part-in and part-out) = $\pi R^2/4 + R - 3/2.$

To summarize:

$s(R) = 2R - 3, \textrm{ } b(R) = \pi R^2/4 + R - 3/2,$

$c(R) = b(R) - s(R) = \pi R^2/4 - R + 3/2.$

Now that we’ve worked out b(R), s(R), and c(R) the answers are:

(a) 0 and $8/\pi.$

(b) m, higher dimensions follow the same methods of calculations.

(c) 1.

(d) Hehe, I haven’t tried this part maybe in a future post. My instinct is that the limits are identical.