Todays problem is from Pugh’s great book “Real Mathematical Analysis“, it’s problem 23 in chapter 1.
Let b(R) and s(R) be the number of integer unit cubes in 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
(b) Take What exponent k makes the limit
(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
(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 and similarly for where and are the functions and restricted to the first quadrant. For the rest of this solution I only work with the first quadrant. Let The area of is so as a first approximation
After some thought the best way to count the number of unit cubes in is to imagine tracing out the curve as goes from 0 to 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 we add 1 to c since the curve has entered a new unit square, similarly if , 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 3 times, similarly y goes from 0 to 2 so 3 times.
This gives us an initial count of 6 for 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 To a first approximation the formula for in m dimensions is
To calculate first note that if the packing of was perfect than b(R) would be It’s not a perfect packing so b(R) is greater than 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 and half their area outside (remember we’re taking the limit to large R, so the result follows from symmetry).
There are of these unit cubes that are only half in So they cover an area of R – 3/2 inside so b(R) must be (the part of covered by unit cubes that are completely contained in ) + 2R – 3 (the unit cubes that are part-in and part-out) =
Now that we’ve worked out b(R), s(R), and c(R) the answers are:
(a) 0 and
(b) m, higher dimensions follow the same methods of calculations.
(d) Hehe, I haven’t tried this part maybe in a future post. My instinct is that the limits are identical.