# An exact counting solution for the number of points within a circle of radius $r$ centered on a lattice point in a $A_2$ hexagonal lattice

In a previous question: (The Gauss circle problem on a hexagonal lattice) I asked for an analytic approximation for the number of lattice points in or along the contour of a circle centered on a lattice point in an $A_2$ hexagonal lattice. The user emiliocba noted that such an approximation was provided by:

Lax, P.D., Phillips, R.S. The asymptotic distribution of lattice points in Euclidean and non-Euclidean spaces. J. Funct. Anal. 46(3), pp. 280 – 350 (1982).

With a best current error term of $O(r^{\frac{2}{3}})$ provided by:

Levitan, B.M. Asymptotic formulae for the number of lattice points in Euclidean and Lobachevskii spaces. Russian Mathematical Surveys 42(3), pp. 13 - 42 (1987).

My question is now if there exists an exact counting solution for the number of points within a circle of radius $r$ centered on a lattice point in an $A_2$ hexagonal lattice. We know that an exact counting solution exists for the $Z^2$ integer lattice using the Floor[] function (see - http://mathworld.wolfram.com/GausssCircleProblem.html ):

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

Can we write a similar counting function for the $A_2$ lattice?

For a list of example values, the number of lattice points in a circle of diameter $r$ (i.e. radius $\frac{r}{2}$) centered on a lattice point in an $A_2$ hexagonal lattice, is given in (http://oeis.org/A053416/list).

For $n = {0, 1, 2, ...}$ we have $N(r) = {1, 1, 7, 7, 19, 19, 37, 43, 61, 73, 91}$.

-

This Mathematica formula reproduces the numbers in the OEIS and should be self explanatory:

n[r_] := Sum[ 1 + 2 Floor[Sqrt[r^2 - 3 x^2]], {x, -Floor[r/Sqrt[3]], Floor[r/Sqrt[3]]}] + Sum[2 Floor[ Sqrt[r^2 - 3 x^2] + 1/2], {x, -Floor[(r/Sqrt[3]) + 1/2] + 1/2, Floor[(r/Sqrt[3]) + 1/2] - 1/2}]

http://oeis.org/A053416 has the values corresponding to n[1/2], n[1], n[3/2], n[2] etc.

Assuming the lattice is generated by $(0,1)$ and $(\sqrt{3}/2,1/2)$, then the first sum counts the number of points of the form $(\sqrt{3}x,y)$ where $x,y\in\mathbb{Z}$, $\sqrt{3}x\le r$, and $3x^2+y^2\le r^2$. The second sum counts the number of points of the form $(\sqrt{3}x,y)$ where $x,y\in(\mathbb{Z}+1/2)$, $\sqrt{3}x\le r$, and $3x^2+y^2\le r^2$.

-
@Yoav I was following what Will Sawin was doing, but to make sure I understand, could you quickly note your approach? –  user27203 Oct 20 '12 at 22:19
@unkown, I added a short explanation. –  Yoav Kallus Oct 20 '12 at 22:31

Assume the lattice is generated by vectors $(1,0)$ and $(1/2,\sqrt{3}/2$.

Then the number of lattice points in the column with $x$ coordinate $k/2$ is $1+2 * Floor[ ((4r^2-k^2)/3)^{1/2}]$ if $k$ is even and $2*Floor[ ((4r^2-k^2)/3)^{1/2}+1/2]$ if $k$ is odd.

So we are going to write two sums, one for $k=2i$ and $i=1$ to $Floor[r]$ and one for $k=2i+1$ and $i=0$ to $Floor[r-1/2]$, of these rows.

Then we're going to add the column at $0$. This gives the exact counting formula

$1+2*Floor[r]+2*Floor[r/ \sqrt{3}]+4* \sum_{i=1}^{Floor[r]} Floor[ \sqrt{(4r^2-4i^2)/3}]$

$+4*\sum_{i=0}^{Floor[r-1/2]} Floor[ \sqrt{(4r^2-(2i+1)^2)/3}+1/2]$

I didn't double-check these calculations so there might be some mistakes, but it's clear that some version of this formula is correct.

-
With: Table[1 + 2*Floor[r] + 2*Floor[r/3^(1/2)] + 4*Sum[Floor[((4*r^2 - 4*i^2)/3)^(1/2)], {i, 1, Floor[r]}] + 4*Sum[Floor[((4*r^2 - (2*i + 1)^2)/3)^(1/2) + 1/2], {i, 0, Floor[r - 1/2]}], {r, 0, 10}] ... I'm getting the table: {1, 7, 31, 61, 117, 179, 259, 351, 457, 573, 723}, which doesn't match anything in OEIS... –  user27203 Oct 20 '12 at 21:35
@Will Sawin Hmm... I don't see the error. –  user27203 Oct 20 '12 at 21:48