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 - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-18T05:26:39Z http://mathoverflow.net/feeds/question/110186 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/110186/an-exact-counting-solution-for-the-number-of-points-within-a-circle-of-radius-r 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 unknown (yahoo) 2012-10-20T20:25:17Z 2012-10-20T22:31:15Z <p>In a previous question: (http://mathoverflow.net/questions/109515/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: </p> <p>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). </p> <p>With a best current error term of $O(r^{\frac{2}{3}})$ provided by:</p> <p>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).</p> <hr> <p>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 - <a href="http://mathworld.wolfram.com/GausssCircleProblem.html" rel="nofollow">http://mathworld.wolfram.com/GausssCircleProblem.html</a> ): </p> <p>$N(r) = 1 + 4*Floor[r] + 4*\sum^{Floor[r]}_{i=1} Floor[(r^2-i^2)^{\frac{1}{2}}]$</p> <p>Can we write a similar counting function for the $A_2$ lattice?</p> <hr> <p>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). </p> <p>For $n = {0, 1, 2, ...}$ we have $N(r) = {1, 1, 7, 7, 19, 19, 37, 43, 61, 73, 91}$.</p> http://mathoverflow.net/questions/110186/an-exact-counting-solution-for-the-number-of-points-within-a-circle-of-radius-r/110190#110190 Answer by Will Sawin for 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 Will Sawin 2012-10-20T20:52:56Z 2012-10-20T21:29:27Z <p>Assume the lattice is generated by vectors $(1,0)$ and $(1/2,\sqrt{3}/2$.</p> <p>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.</p> <p>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.</p> <p>Then we're going to add the column at $0$. This gives the exact counting formula</p> <p>$1+2*Floor[r]+2*Floor[r/ \sqrt{3}]+4* \sum_{i=1}^{Floor[r]} Floor[ \sqrt{(4r^2-4i^2)/3}]$</p> <p>$+4*\sum_{i=0}^{Floor[r-1/2]} Floor[ \sqrt{(4r^2-(2i+1)^2)/3}+1/2]$</p> <p>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.</p> http://mathoverflow.net/questions/110186/an-exact-counting-solution-for-the-number-of-points-within-a-circle-of-radius-r/110201#110201 Answer by Yoav Kallus for 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 Yoav Kallus 2012-10-20T22:09:14Z 2012-10-20T22:31:15Z <p>This Mathematica formula reproduces the numbers in the OEIS and should be self explanatory:</p> <blockquote> <p>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}]</p> </blockquote> <p><a href="http://oeis.org/A053416" rel="nofollow">http://oeis.org/A053416</a> has the values corresponding to n[1/2], n[1], n[3/2], n[2] etc.</p> <p>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$.</p>