2
$\begingroup$

Suppose we have a circle of radius $r$ centered at the origin $(0,0)$. The number of integer lattice points within the circle, $N$, can be bounded using Gauss circle problem .

Suppose that another circle of radius $r/2$ centered at the origin inside the initial circle of radius $r$, let $N^*$ represents the number of integer lattice points within the the smallest circle. I am mainly interested in the relation between $N$ and $N^*$. More precisely, to find the number of integer lattice points within the circle of radius $r$ and outside(and at the boundary of) the circle of radius $r/2$.

This page provides the number $N$ for some distances $r$ in $2$ dimensions. For example if we take "ignore the integer lattice point represents the origin":

$r=4$, then $N^*=12, N=48 $ and $N^* = \frac{1}{4}N$

$r=6$, then $N^*=28, N=112 $ and $N^* = \frac{1}{4}N$

.

.

.

$r=40$, then $N^*=1256, N=5024 $ and $N^* = \frac{1}{4}N$

By doing more calculations, in general (considering $r$ is even *for simplicity) we can say $$\frac{1}{5}N \leq N^* \leq \frac{1}{3}N$$

I searched in the literature to find something about this relation in $2$ or $d$ dimensions but without success. I think there is a result or a bound about it, could you kindly direct me to a reference or to a bound and I would be very grateful.

$\endgroup$
  • $\begingroup$ Here is a visualization that may lead to quick results. Draw a circle of radius r and count the lattice points. Then (instead of drawing a circle of radius 2r) color in the points with coordinates both multiples of 1/2. This is almost like making four copies of the original lattice. Now draw three more circles of radius r with origin near one of the shifted versions of the original origin, and consider what points lie outside the intersection (or don't get copied). Gerhard "Try Eyeballing As Discovery Method" Paseman, 2018.09.19. $\endgroup$ – Gerhard Paseman Sep 19 '18 at 18:00
  • 4
    $\begingroup$ As the Wikipedia page notes, the standard (and fairly straightforward) estimate for this is that $N=\pi r^2+O(r)$ (most of the challenge is in finding the linear term); since similarly, $N^*=\frac14\pi r^2+O(r)$, this immediately gives $N^*=\frac14N+O(\sqrt{N})$. In $d$ dimensions the corresponding statement is $N^*=2^{-d}N+O(N^{(1-1/d)})$, and again it's all pretty straightforward. Do you need more than this? $\endgroup$ – Steven Stadnicki Sep 19 '18 at 19:32
  • $\begingroup$ @GerhardPaseman thanks for your comment but sorry I didn't understand your idea! Is it possible to clarify more? $\endgroup$ – Noah16 Sep 20 '18 at 15:33
  • $\begingroup$ Take the larger circle and scale it and the lattice points down by a factor of 1/2. The image looks like the small circle but with more points, most of which are translates of the lattice points inside the small circle by 1/2. The idea is to use these translates to get an idea of the size of (number of points inside big circle minus 4 times number of points inside small circle). Gerhard "Let's See If This Helps" Paseman, 2018.09.20. $\endgroup$ – Gerhard Paseman Sep 20 '18 at 15:39
  • $\begingroup$ @StevenStadnicki thanks. Your calculations confirm what I wrote above but I am looking for something more powerful and accurate so that I can enumerate the points lie between circles as detailed in my question. Unfortunately, your calculations will not provide an upper and lower bounds. In fact I thought there is a result about this and because of that I asked for a reference! $\endgroup$ – Noah16 Sep 20 '18 at 15:42
3
$\begingroup$

Glad to see there's another Noah interested in such questions :).

Let $N_{r,d}$ be the number of (non-zero) integer points in a $d$-dimensional ball of radius $r$. I'll try to summarize the state of our knowledge on $N_{r,d}$ below, at least as I understand it. Along the way, I'll answer your question for $d= 2$:

$$ 3 \leq \frac{N_{2r,2}}{N_{r,2}}\leq 4.5 $$

for $r \geq 1$, which is tight. (If you exclude radii $r$ with no integer points of length $r$, then the upper bound drops to $4 + 1/6$, which is also tight.)

I'll just say up front that a decent quick and dirty approximation is $N_{r,d} = \binom{d+r^2}{r^2}^{1\pm O(1)}$ (for $r \geq 1$). You can ignore the rest of this long post if you're happy knowing that.

There are in some sense three different regimes in which $N_{r,d}$ behaves rather differently, as follows. (I'm being deliberately vague for now. Precise statements below.)

  1. The case $r \gg \sqrt{d}/2$, where $N_{r,d}$ is basically just the volume of the ball of radius $r$.
  2. The case $r \ll \sqrt{d}$, where $N_{r,d}$ is basically just the number of points in $\{-1,0,1\}^d$ with norm $\approx r^2$.
  3. The intermediate case $r \approx \sqrt{d}/2$, where it's a bit more complicated.

For $d = 2$, there's a sense in which only the first case comes up because, well, the question is only interesting for $r \geq 1$, and $\sqrt{2}/2 = 1/\sqrt{2}$ is less than one. So, you don't see the more complicated structure until you get to higher dimensions.

$\mathbf{r \gg \sqrt{d}/2}$:

In this regime, volume estimates become very precise. In particular, by noting that every point in $\mathbb{R}^d$ is at distance at most $\sqrt{d}/2$ from $\mathbb{Z}^d$ and applying a simple argument [****], we see that

$$\mathrm{Vol}(B_d(r - \sqrt{d}/2)) \leq N_{r,d} \leq \mathrm{Vol}(B_d(r + \sqrt{d}/2)) \; ,$$

where $B_d(r)$ is the $d$-dimensional $\ell_2$ ball in dimension $d$, which has volume $r^d \pi^{d/2}/\Gamma(d/2+1) \approx (2\pi e r^2/d)^{d/2}$. I.e., we have upper and lower bounds for $N_{r,d}$ that differ by a multiplicative factor of

$$\Big( \frac{1+\sqrt{d}/(2r)}{1-\sqrt{d}/(2r)} \Big)^{d} \; , $$

which in particular implies that the ratio $N_{2r,d}/N_{r,d}$ that interests you is equal to $2^d$ up to a factor of at most

$$\Big( \frac{1+\sqrt{d}/(4r)}{1-\sqrt{d}/(2r)} \Big)^{d} \; . $$

Finishing ${\bf d = 2}$

When $d = 2$, we can use the above estimate to find the maximum and minimum of $N_{2r,2}/N_{r,2}$ relatively easily. We do this by just brute-force computing the ratio for all small $r$. (I used Mathematica and the simple formula $N_{r,2} = \sum _{z_1=-\lfloor r\rfloor }^{\lfloor r\rfloor } (2 \lfloor \sqrt{r^2-z_1^2}\rfloor +1)-1$.) For integer $r^2$, we find that the maximum ratio is achieved at $r=\sqrt{3}$ with

$$\frac{N_{2\sqrt{3}, 2}}{N_{\sqrt{3}, 2}} = \frac{36}{8} = 4.5 \; ,$$

and the minimum is actually achieved at $r = 1$ with

$$\frac{N_{2, 2}}{N_{1, 2}} = \frac{12}{4} = 3 \; .$$

(The same ratio occurs again at $r = \sqrt{2}$.)

If we don't want to include radii where $r^2$ cannot be written as the sum of two squares, then the maximum ratio occurs at $r = \sqrt{8}$ with

$$ \frac{N_{2\sqrt{8}, 2}}{N_{\sqrt{8},2}} = \frac{100}{24} = 4.1666\ldots \; .$$

The volume approximation discussed above shows that no more extreme ratios can occur for, $r > 52$, so we can terminate our search there. (There's probably a better argument that lets you check fewer radii, but checking up to $r = 52$ isn't too bad.)

(Geometrically, we can think of this very nice behavior as a result of the fact that $\mathbb{Z}^2$ actually isn't such a terrible sphere packing/covering, whereas $\mathbb{Z}^d$ is a really bad sphere packing/covering for large $d$.)

Here are some plots of $N_{2r,2}/N_{r,2}$:

enter image description here

enter image description here

(The bands that are clearly visible in the second image correspond to ratios of the form $4 + c/n$ for fixed $c$ and $n = $.

$\mathbf{r \ll \sqrt{d}}$:

Here, we can get quite tight bounds simply by noting that when $r^2$ is an integer and $r \ll \sqrt{d}$,

$$N_{r,d} \approx |\{z \in \{-1,0,1\}^d \ : \ \|z\|= r\}| = 2^{r^2} \binom{d}{r^2} \; . $$

In other words, almost all of the integer points in a ball of radius $r \ll \sqrt{d}$ actually lie on the sphere of radius $r$ and have coordinates from $\{-1,0,1\}$. This immediately shows that the $2^d$ heuristic fails in this regime. In fact, until $N_{r,d} < 2^d$ for all radii $r$ with, say, $r < 0.4 \sqrt{d}$, so the $2^d$ heuristic obviously fails here.

To be more precise, here's a smooth estimate with this flavor:

$$ N_{r,d} = (2 e^{1+\chi} d /r^2)^{r^2} \; , $$

for any $r \leq \sqrt{d}/2$, where $B(r)$ is the ball of radius $r$ and the error parameter $\chi$ satisfies

$$ -\frac{r^2}{d} - \frac{\log(C r)}{r^2} \leq \chi \leq \sqrt{\frac{C}{\log(d/r^2)}} \; , $$

for some not very large constant $C > 0$ [*]. Notice that these bounds are quite tight for $1 \ll r \ll \sqrt{d}$, since in this regime $\chi$ is subconstant. (A smooth function in $r$ can't give a much better approximation when $r$ is constant since, e.g., $N_{\sqrt{2} - \varepsilon, d} = 2d$, but $N_{\sqrt{2}, d} \approx d^2$. But the binomial coefficient is quite accurate in this case for integer $r^2$.) This gives

$$\frac{N_{2r,d}}{N_{r,d}} \approx (e d /r^2)^{3r^2}2^{-5r^2} $$

for $1 \ll r \ll \sqrt{d}$.

Geometrically, we can think of this strange behavior as a result of the integer lattice ``having short points that shouldn't be there.'' In particular, in $d$ dimensions, the ball of radius $1$ has volume much less than one, $\approx (C/d)^{d/2}$, but the integer lattice manages to have $2d+1$ points inside this ball anyway.

The hard case, ${\bf r \approx \sqrt{d} }$

When $r \ll \sqrt{d}$ or $r \gg \sqrt{d}$, there are nice smooth functions with closed formulas that approximate $N_{r,d}$ well. For $r \approx \sqrt{d}$ one can approximate $N_{r,d}$ to arbitrary accuracy by studying the theta function $\Theta(\tau) := \sum_{z \in \mathbb{Z}} e^{-\tau z^2}$. (Actually, one can do this for all radii $r$, but it just gives the above answers back when $r \ll\sqrt{d}$ or $r \gg \sqrt{d}$.) Mazo and Odlyzko showed this in [**]. Specifically, they showed that

$$N_{\alpha \sqrt{d} ,d}^{1/d} = e^{-\chi/\sqrt{d}}\inf_{\tau > 0} e^{\alpha^2 \tau}\Theta(\tau) \; , $$ where $0 \leq \chi \leq C_\alpha$ for some easily computable constant $C_{\alpha}$ that depends only on $\alpha$. (The constant $C_{\alpha}$ is essentially the standard deviation of the Gaussian distribution over the integers with the parameter $\tau$ chosen by the infimum.) Notice that Markov's inequality immediately yields

$$N_{\alpha \sqrt{d} ,d}e^{-\alpha^2 d\tau}< \sum_{\stackrel{z \in \mathbb{Z}^d}{\|z\| \leq \alpha \sqrt{d}}} e^{-\tau z^2} < \sum_{z \in \mathbb{Z}^d} e^{-\tau z^2} = \Theta(\tau)^d \; $$ for any $\tau > 0$. Rearranging and taking the infimum shows that $\chi \geq 0$. So, the hard part is to show a nearly matching lower bound for appropriately chosen $\tau$, which amounts to showing that the summation is dominated by the contribution from points in a thin shell.

Turning back to your original question, one can use this to show that

$$\frac{N_{2\alpha \sqrt{d},d}}{N_{\alpha \sqrt{d}, d}} = e^{\chi_{\alpha}' \sqrt{d}} \cdot (C^*_{\alpha})^d$$,

where $0 < C^*_{\alpha} < 2$ is some constant depending only on $\alpha$ and $|\chi_\alpha|$ is bounded by some constant also depending only on $\alpha$. Again, $C^*_{\alpha}$ is less than $2$ because ``the integer lattice has too many short points.'' I.e., it is in some sense a really really bad sphere packing [***].


[*] This particular bound is from my thesis (On the Gaussian measure over lattices), where I give an easy proof using the theta function $\Theta(\tau) := \sum_{z \in \mathbb{Z}} e^{-\tau z^2}$. (I'm sure that this result is not original, and the technique of using the theta function was already used by Mazo and Odlyzko in [**] to approximate $N_{r,d}$ in a more interesting regime.)

[**] Mazo and Odlyzko. Lattice Points in high-dimensional spheres, 1990. https://link.springer.com/article/10.1007/BF01571276 .

[***] With Oded Regev, we showed that it's actually ``the worst packing'' in a certain precise sense, up to a certain error term: https://arxiv.org/abs/1611.05979 . Basically, its theta function is almost maximal for stable (aka, "non-degenerate") lattices.

[****] To see this, notice that if we sample a random point $t$ from the cube $[0,1/2]^d$, the expected number of points in a ball of radius $r-\sqrt{d}/2$ around $t$ must equal the volume of the ball exactly. In particular, there exists a $t$ such that this value is at least the volume, and since this $t$ is in the cube, the ball of radius $r$ around the origin contains this ball. (The upper bound follows from the same argument.)

$\endgroup$
  • $\begingroup$ Thanks a lot for this effort. I just wanna know why you compared $r$ to $d$ so as a result you divided the process into cases while enumerating the number of lattice points? $\endgroup$ – Noah16 Sep 22 '18 at 20:59
  • $\begingroup$ i.e Yes I understand why you divided them into 3 cases but is it possible to generalize without comparing $r$ to $d$ $\endgroup$ – Noah16 Sep 22 '18 at 22:49
  • $\begingroup$ Sorry, I don't understand the question. $N_{r,d}$ depends both on $r$ and $d$. How can one discuss it without "comparing $r$ to $d$"? If you want to fix $d$ and vary $r$ or fix $r$ and vary $d$, then the first and second cases handle this, respectively. The three cases that I described can be collapsed into one by showing that $N_{r,d} \approx \inf_{\tau > 0} e^{r \tau}\Theta(\tau)^d$ for all $r,d$. However, the behavior of $\Theta(\tau)$ is very differently in three different regimes, $\tau \ll 1$, $\tau \gg 1$, and $\tau \approx 1$, which correspond to the three cases that I listed above. $\endgroup$ – Noah Stephens-Davidowitz Sep 23 '18 at 3:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.