On the size of balls in $\mathbb{Z}^d$ Consider the iterative Cartesian product of the integers: $\Bbb Z^d,$ where $\Bbb Z$ denotes the set of integers in the real line. Equip $\Bbb Z^d$ with the standard graph distance $d(x, y) = \sum |x_k - y_k|,$ where $x = (x_1, \ldots, x_d)$ and similarly for $y.$
Is it known the (exact) size of the balls $\{x \in \Bbb Z^d \mid d(x, y) < r\}$, where $r > 0$? In fact, I only need to know the asymptotics of the size and my intuition says that this size should be comparable with the size of the same ball but taking $d$ to be the $\ell^\infty$ distance defined by $d(x, y) = \max |x_k - y_k|$ and that is easy to calculate to be $(2r)^d.$ Any hints on how to proceed?
 A: $\mathbb{R}^d$ is a finite dimensional vector space, and $l_1$ and $l^\infty$ are two norms on it. Thus, they are equivalent, meaning there exist constants $c_1,c_2$ so that $c_1||x||_1 \le ||x||_\infty \le c_2||x||_1$ for all $x \in \mathbb{R}^d$. So if we restrict the norms from $\mathbb{R}^d$ to $\mathbb{Z}^d$, these inequalities of course still hold. You are interested in $\#\{x \in \mathbb{Z} : ||x-y||_1 < r\}$ which lies between $\#\{x : ||x-y||_\infty < c_1r\}$ and $\#\{x : ||x-y||_\infty <c_2r\}$, so your answer is between $(2c_1r)^d$ and $(2c_2r)^d$, which gives you the asymptotics you want.
A: This can be worked out, and I am sure it has been worked out, but here are
some hints.
Assume $y=0$. The lattice points in the ball that are also in the
positive orthant are the $(a_1,\ldots,a_k)$ with $a_i$ non-negative integers
with $\sum_i a_i\le n$. The number of these is $\binom{n+k}k$. There are
$2^k$ orthants, but one must count points in two or more of them by
using inclusion-exclusion or other artifices.
Asymptotically, for a fixed $k$ the number of lattice points is
about $2^kn^k/k!$ as that is the volume of the set $\{x\in\Bbb R^k:|x|\le n\}$. By Ehrhart's theorem or otherwise the error will be $O(n^{k-1})$.
