Number of integer distance grid points in a cubic grid

Question

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$.

Answer 1

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.

Answer 2

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.