Let $C_n$ denote the convex hull of all integer vectors $(x,y)\in\mathbb{R}^2$ satisfying
$x^2+y^2\leq n$. What can be said about the number of vertices of $C_n$ and the number of integer points on the boundary of $C_n$? Are there nice asymptotic formulas, possibly for special values of $n$?
[Math] Convex hull of lattice points in a circle
nt.number-theory
Related Solutions
For general ellipses I doubt you can do much better than Bombieri-Pila sort of bounds:
MR1016893 (90j:11099) Reviewed
Bombieri, E.; Pila, J.
The number of integral points on arcs and ovals.
Duke Math. J. 59 (1989), no. 2, 337–357.
11P21 (11D99)
(you should check out the many papers that cite this, as well, but most of them seem to be interested in higher degrees/dimensions).
For integer coefficients, the best seems to be
Lattice points on Ellipses Cilleruelo and Cordoba, DMJ 1994
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.)
- The case $r \gg \sqrt{d}/2$, where $N_{r,d}$ is basically just the volume of the ball of radius $r$.
- 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$.
- 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}$:
(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.)
Best Answer
Asymptotic formulas might be asking for a lot, but there is some work by I. Barany et al. See:
RANDOM POINTS AND LATTICE POINTS IN CONVEX BODIES IMRE BA ́RA ́NY (in BAMS 2008) and the paper referred to therein by Balog/Barany:
Balog, Antal(H-AOS); Bárány, Imre(H-AOS) On the convex hull of the integer points in a disc. Discrete and computational geometry (New Brunswick, NJ, 1989/1990), 39–44, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 6, Amer. Math. Soc., Providence, RI, 1991. 11H06 (11P21 52C07)
The former talks about some nice probabilistic results, the latter shows that there is an estimate of the form $c_1r^{2/3} \leq N(r) \leq c_2 r^{2/3},$ where $N(r) = C_n,$ and $r=n$ in your notation.
EDIT Answering my own question in the comments: it is a result of Renyi-Sulanke, 1963, that for $n$ random points in the disk, the expected number of extremal points is $O(n^{1/3}),$ so this is of the same order as for lattice points. A bit surprising.