Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Take an infinite hexagonal lattice (or equivalently, an equilateral triangular lattice), with unit spacing between the closest lattice point pairs, and draw a disc of radius $r$ centered on a lattice point at $(0, 0)$. Let $N(r, hex)$ denote the number of hexagonal lattice points at coordinates $(a, b)$ s.t. $(a^2 + b^2) \leq r^2$, i.e. the number of lattice points on or within the aforementioned disc of radius $r$.

Are there any literature references for approximations to $N(r, hex)$ (I haven't been able to find any through a Google search)? What is an exact counting solution for $N(r, hex)$?

Using the exact counting solution for the $Z^2$ integer lattice, (http://mathworld.wolfram.com/GausssCircleProblem.html) I suppose we can guess a lowerbound for the hexagonal lattice of:

Lowerbound $N(r, hex) = 1 + Floor[\frac{r}{2}] + 4*\sum^{Floor[\frac{r}{2}]}_{i=1} Floor[((\frac{r}{2})^2-i^2)^{\frac{1}{2}}] + 2*Floor[r]$

Where we simply overlay the $Z^2$ lattice with (closest) nearest-neighbor spacing $2$ on top of an $A_2$ hexagonal lattice with (closest) nearest-neighbor spacing $1$, and add an additional $2*Floor[r]$ correctional term.

[10/13/12] The OEIS sequences are extremely helpful, but after searching the literature for awhile, I'm still having difficulty finding an exact (counting) solution for the number of lattice points within a circle of real number radius $r$. Any references would be very much appreciated!

[10/14/12] Still no luck finding a reference in the literature. Surely someone has looked at this problem for, say, graphene and other molecular or atomic lattices where one would like to have a precise atom count a certain physical distance away from one atom?

[10/19/12] I managed to find the exact OEIS sequence I was looking for: http://oeis.org/A053416

However, I'd still like to find an exact counting solution, like the one presented above the $Z^2$ integer lattice.

share|improve this question
You want the partial sums of this sequence oeis.org/A004016 (those are actually provided in this sequence oeis.org/A038589). The OEIS entry provides many references you might want to look at. –  Yoav Kallus Oct 13 '12 at 5:07
Usually a change of basis is applied, so you count ordinary lattice points in an certain type of ellipse. The general "lattice points in an ellipse" problem is well known, and you'll have more luck with it on Google. The asymptotic formula is the area (could hardly be anything else). –  Charles Matthews Oct 13 '12 at 11:05
A good estimate by a simple formula seems more worthwhile than an exact formula. By the way, the Gauss curcle problem is, in my understanding, a question about how well the obvious asymptotic formula approximates the true count, which does not seem to be what you are asking –  Yemon Choi Oct 14 '12 at 18:50
@Yemon Choi I'd be very happy with a good estimate, but an exact counting solution would be useful in any case to characterize an error term. –  user27203 Oct 14 '12 at 19:00
Can't you just use the exact same trick as is used for the square lattice solution: sum up the number of points in each column? It's easy to get a solution for the number of points in a column in terms of a floor function of a square root. –  Will Sawin Oct 19 '12 at 20:46

2 Answers 2

up vote 10 down vote accepted

Lax and Phillips (J. Funct. Anal. vol 46 (1982), 280--350) showed, for any crystallographic group $\Gamma$ in the Euclidean plane, that $$ N(r;x,x_0)= \frac{\pi r^2}{|F|} + O(r^{2/3} (\log r)^{1/2}), $$ as $r\to+\infty$, where $|F|$ denotes the volume of the fundamental domain of $\Gamma$, $x,x_0\in\mathbb R^2$ and $N(r;x,x_0)$ is the number of elements $\gamma\in\Gamma$ such that $$ |x-\gamma (x_0)|\leq r. $$

Later, Levitan (Russian Math. Surveys vol 42:3 (1987), 13--42) improved the error term to $O(r^{2/3})$.

In your particular case, $\Gamma$ is the subgroup of the isometries of the plane generated by the translations for $(1,0)$ and $(1/2,\sqrt{3}/2)$, thus $|F|=\sqrt{3}/2$.

Both papers works in higher dimensions and in hyperbolic spaces.

share|improve this answer
@emiliocba Fantastic literature reference, thanks! However, looking at the paper, I think you meant to have $s \to r$. –  user27203 Oct 20 '12 at 11:36
@emiliocba This is basically the answer that I want, but do you think an exact counting solution is possible? –  user27203 Oct 20 '12 at 11:36
Surely, the exact counting solution in your case is as difficult as the Gauss circle problem. –  emiliocba Oct 20 '12 at 11:42
@emiliocba That was my initial impression... However, what makes this harder than finding the rectangular lattice exact counting solution? Looking at Will Sawin's comment, and I hope I'm not misinterpreting here, there seems to be some notion that the same method can be extended to the hexagonal lattice in two-dimensions? –  user27203 Oct 20 '12 at 12:13
@unknown: I'm sorry, but I can't understand when you say "an exact solution". The circle problem is to find the best error term of $E(r):=N(r)-\pi r^2$ as $r\to+\infty$, which is still open as far as I known. The conjecture is $N(r)=O(r^{1/2+\varepsilon})$. –  emiliocba Oct 20 '12 at 13:21

By using a transformation, it is possible to give a counting formula for the hexagonal lattice, similar to the formula on MathWolf. Here are the details.

Suppose your lattice is given by $\Lambda=T(\mathbb{Z}^2)$, where $T$ is an invertible 2x2 matrix.

Let $E$ be an ellipse, and let $N_E(R)$ denote the number of points of $\mathbb{Z}^2$ that are in the dilate $R\cdot E$. That is, $$ N_E(R)=|R\cdot E\cap\mathbb{Z}^2|, $$ where the vertical bars denote cardinality.

Now if we let $D$ be the unit disk, you wish to count $$ |R\cdot D\cap \Lambda| = | R\cdot D\cap T(\mathbb{Z}^2)| = |R\cdot T^{-1}(D)\cap\mathbb{Z}^2| = N_E(R), $$ where $E=T^{-1}D$ is an ellipse.

If $$ T=\begin{pmatrix} a & b\\ c& d \\ \end{pmatrix} $$ then the boundary of $R\cdot E$ is given by the equation $$ (ax+by)^2+(cx+dy)^2=R^2. $$ In general, the explicit expression for $y$ is fairly messy. But for a hexagonal lattice, $a=1,b=0,c=1/2,d=\sqrt{3}/2$, so we have $$ x^2+\frac{(x+\sqrt 3 y)^2}{4} = R^2, $$ hence $$ y=\frac 1{\sqrt 3}[ -x\pm \sqrt{4R^2-x^2}]. $$

This explicit expression let's us write down a counting expression like the one on MathWorld.

Since $E$ is symmetric under $(x,y)\mapsto (-x,-y)$, it suffices to count the number of lattice points above the $x$-axis. The number of lattice points on the axes can be counted fairly easily. It is slightly tricky to count the number of lattice points within the ellipse. In the first quadrant, we may count as usual, but in the second quadrant, we must subtract lattice points that are below the ellipse: $$ N(R)=1 + 2\lfloor \sqrt{4/5}R\rfloor + 2\lfloor \sqrt{4/3}R\rfloor + 2\sum_{i=1}^{\lfloor \sqrt{4/5}R\rfloor} \left\lfloor \frac 1{\sqrt 3}[ - i+\sqrt{4R^2-i^2}]\right\rfloor +2\sum_{i=1}^{\lfloor 2R\rfloor}\left\lfloor \frac 1{\sqrt 3}[ i+\sqrt{4R^2-i^2}]\right\rfloor -2\sum_{i=\lceil\sqrt{4/5}R\rceil}^{\lfloor 2R\rfloor}\left\lfloor \frac 1{\sqrt 3}[ i-\sqrt{4R^2-i^2}]\right\rfloor $$

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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