7
$\begingroup$

The circle problem in $k$ dimensions: "For $n>0$, how many points $z\in \ \mathbb{Z}^k$ have $\|z\|^2\leq n$?"

For large $n$, the answer is $\approx n^{k/2}\cdot \operatorname{Vol}(B^k(0,1))+\Omega(n^{k/2-1})$.

This approximation is very bad in limit with dimension. For example, if $n$ grows linearly with $k$ then the approximation term dominates the volume term. Do results exist for this regime, or at least for $n$ small relative to $k$?

Improve this question
$\endgroup$
2
  • $\begingroup$ apologies for my confusion: if $n$ grows linearly with $k$, why does the term $n^{k/2-1}\simeq k^{k/2-1}$ dominate the volume term $n^{k/2}\simeq k^{k/2}$? --- it's $1/k$ smaller, isn't it? $\endgroup$
    – Carlo Beenakker
    Commented Jun 26, 2018 at 14:53
  • 4
    $\begingroup$ Yes but the volume term shrinks factorially in $k$. $\endgroup$
    – Christian Chapman
    Commented Jun 26, 2018 at 16:59

1 Answer 1

Reset to default
6
$\begingroup$

This problem was studied by J.E. Mazo and A.M. Odlyzko in Lattice Points in High-Dimensional Spheres. If $n$ grows with $k$ faster than linearly then the volume asymptotic still applies. If it increases slower than linearly then for most locations of the center of the circle there will be no lattice points inside it. The linear increase mentioned in the OP is a borderline case. For $n=\alpha k$ the asymptotics of the number of points $N$ inside the circle is $$\lim_{k\rightarrow\infty}N=e^{ck},$$ with $c$ a coefficient of order unity that depends on $\alpha$ and on the location of the center of the circle. (For a circle centered at the origin and $\alpha=1$ the value is $c=1.418938538$.)

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks. Do you know if $c(\alpha)$ is readily computable in general? $\endgroup$
    – Christian Chapman
    Commented Jun 26, 2018 at 18:47
  • 1
    $\begingroup$ I don't think there is a closed form expression for $c$, there is a transcendental equation that is solved numerically in the cited reference, to produce their table for the $\alpha$ dependence of $c$. It is relatively weak, for $\alpha=0.1$ they find $\alpha=0.394414813$. $\endgroup$
    – Carlo Beenakker
    Commented Jun 26, 2018 at 18:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .