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.
Best Answer
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.)
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}$:
(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.)