2

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

Martin Sleziak
  • 53,687
Johannes
  • 1,192
  • 1
  • 6
  • 19
  • So, to clarify, you want the points that are exactly an integer distance from $0$, say? That that is, $(3,4)$ is allowed, but $(3,3)$ is not? – Thomas Andrews Jul 08 '13 at 13:52
  • Correct, (4,3,0) is allowed, (3,3,0) isn't. – Johannes Jul 08 '13 at 14:03
  • You can use 'Hardy-Littlewood Asymptotic Formula'. I'm writing my answer now. – Flan Jul 08 '13 at 14:07
  • Some details for counting the number of ways distance $k$ can be achieved in dimension $n=2$ (sums of two squares) are given in this PDF. It is well known that among square-free positive integer, those which are products of primes congruent to 1 mod 4 are sums of two squares. Every positive integer is the sum of four squares, and all but those congruent to 7 mod 8 are the sums of three squares. – hardmath Jul 08 '13 at 14:10
  • 1
    Hm, let's argue for a physicist with physical approximations ;) The value of $x^2+y^2+z^2+\ldots$ (if it is approximately $R^2$) is a perfect square with probability $\approx\frac1{2R}$, so the growth yould be expected to be $\sim k^{n-1}$ instead of the $k^n$ from user1086219's answer ... – Hagen von Eitzen Jul 08 '13 at 14:16
  • I wrote the comment which had disappeared now, but I deleted it by my mistake, oops. (I wrote the comment again.) By the way, how did you get $N(k)\sim ck^{n/2}$? I think it should be $ck^{n-1}$. We have to calculate $r_n(1^{2})+r_n(2^{2})+\cdots +r_n([k]^{2})$. According to the reference you found, you can calculate $c(1^{n-2}+2^{n-2}+\cdots +[k]^{n-2})$ instead. Using Euler's Summation Formula, we get $N(k)\sim ck^{n-1}/(n-1)$. – Flan Jul 08 '13 at 16:37
  • Oops, you're right (lower-cased $N$ instead of making the substitution $N = n^2$). Have corrected it. Thanks. – Johannes Jul 09 '13 at 02:50
  • @HagenVonEitzen - as a physicist I indeed consider your answer as most insightful. Thanks! – Johannes Jul 09 '13 at 16:13

2 Answers2

3

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.

Flan
  • 587
0

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.

user1086219
  • 36