Number of integer distance grid points in a cubic grid Given an $n$-dimensional integer lattice $\mathbb Z^n$, how does the number of grid points $N(k)$ at integer distance $\leq k$ from a given grid point scale asymptotically? I'm mostly interested in $n = 3$ (I'm a physicist :) ), but having also the results for $n = 2$ and $n\geq 4$ would complete the picture.
EDIT: guided by a comment that has now disappeared, I stumbled upon this reference that provides the result $N(k) = c k^{n-1}$ for $n \geq 5$. 
 A: You can use 'Hardy-Littlewood Asymptotic Formula' but it is very tricky...
Let $r_{k,s}(N)$ denote the number of representations of $N$ as the sum of $s$ positive $k$th powers.
Then we have
$$r_{k,s}(N)=S(N)\Gamma\left(1+\frac{1}{k}\right)^{s}\Gamma\left(\frac{s}{k}\right)^{-1}N^{(s/k)-1}+O\left(N^{(s/k)-1-\delta}\right)$$
where $S(N)$ is uniformly bounded above and below by positive constants depending only on $k$ and $s$. $\delta$ also depends only on $k$ and $s$.
Now We put $k=2$ and $s=n$. Applying Hardy-Littlewood Asymptotic Formula, we have
$$r_{2,n}(N)=S(N)\left(\frac{\sqrt{\pi}}{2}\right)^{n}\Gamma\left(\frac{n}{2}\right)^{-1}N^{(n/2)-1}+O\left(N^{(n/2)-1-\delta}\right)$$
where $S(N)$ is uniformly bounded and $\delta$ depends on $n$. Assume that $c_1<S(N)<c_2$ for positive constant $c_1$, $c_2$.
Now we have to calculate
$$N(k)=\sum_{N<k}r_{2,n}(N^{2}).$$
The result is
$$\sum_{N<k}\left(S(N^{2})\left(\frac{\sqrt{\pi}}{2}\right)^{n}\Gamma\left(\frac{n}{2}\right)^{-1}N^{n-2}+O\left(N^{n-2-2\delta}\right)\right).$$
This means you can simply calcute $N(k)$ with the inequality
$$\frac{c_{1}\sqrt{\pi}^{n}\Gamma(n/2)^{-1}}{(n-1)2^{n}}k^{n-1}+O\left(k^{n-1-2\delta}\right)<N(k)<\frac{c_{2}\sqrt{\pi}^{n}\Gamma(n/2)^{-1}}{(n-1)2^{n}}k^{n-1}+O\left(k^{n-1-2\delta}\right).$$
This means
$$C_1<\frac{N(k)}{k^{n-1}}<C_2$$
for some constant $C_1$ and $C_2$ depends on $n$.
Well, I think the result is too complicated to use in physics. Maybe you would not be satisfied with the answer. Sorry.
A: Asymptotically, it simply goes as the volume of the sphere (or the $n$ hyper-ball for generic dimensions).
For $n = 2$ 
 $N(k) \longrightarrow  \pi k^2 $
For $n = 3$  $N(k) \longrightarrow \frac{4}{3} \pi k^3 $
For $n = 4$  $N(k) \longrightarrow \frac{1}{2}\pi^2 k^4 $
You can find the generalization for any $n$ here:
http://en.wikipedia.org/wiki/Volume_of_an_n-ball
Note that I'm just stating what happens for $k \rightarrow \infty$. 
The formulas above are neither upper bounds or lower bounds of the real integer value, which oscillates above or below that real number.
