Counting points on lattices - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T12:13:16Z http://mathoverflow.net/feeds/question/32506 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/32506/counting-points-on-lattices Counting points on lattices Tzanko Matev 2010-07-19T14:53:50Z 2010-07-19T21:04:16Z <p>I expect that the following is a standard problem from analytic number theory, but I don't know where exactly to look for an answer. </p> <p>Let f: &#8484;<sup>r</sup>&rarr; H be a surjective homomorphism into a finite group. Let </p> <p><code>$S(N)= \frac{1}{N^r}\#\{(x_1,\dots,x_r)\in \ker f\colon 0\leq x_i &lt;N\}$</code>. </p> <p>One expects that S(N) is roughly |H|<sup>-1</sup>. My question is:</p> <blockquote> <p>What is the best known estimate of the error term S(N)-|H|<sup>-1</sup> in terms of N and the structure of H? I am especially interested in the case, when H=(&#8484;/p<sup>n</sup>&#8484;)<sup>d</sup>, for some d&lt;r.</p> </blockquote> <p>To give some idea of what kind of results I am looking for, I will give the estimate, that I managed to find myself. If "e" is the exponent of the group H, and "h" is its size, then by estimating character sums one gets</p> <p><code>$S(N) - h^{-1} \ll h^{-1}(\log \min\{h,N\})^r \max\{eN^{-1},e^rN^{-r}\}$</code>,</p> <p>where the implicit constant depends only on r. I think, that this can be improved at least when N is small with respect to e.</p> http://mathoverflow.net/questions/32506/counting-points-on-lattices/32517#32517 Answer by Victor Miller for Counting points on lattices Victor Miller 2010-07-19T17:33:09Z 2010-07-19T17:43:43Z <p>Note that $ker(f)$ is a sublattice of the integer lattice <code>$\mathbb{Z}^r$</code>. And conversely any such integer sublattice will give you such a homomorphism $f$. The index of this sublattice is exactly what you call $h$ (since the homomorphism is surjective). If $C$ is a symmetric convex body in <code>$\mathbb{R}^r$</code> and $L$ a full rank lattice then the number of lattice points in $t C$ (the dilation of $C$ by a real factor of $t$) is asymptotic to $t^r vol(C)/D$, where $D$ is the volume of the fundamental domain of $L$. In your case $D=h$ and $C$ is the unit hypercube. Getting a good remainder is usually a much harder job. In general the remainder is bounded by something proportional to the area of $C$. When $C$ has a smooth boundary (which alas, the hypercube doesn't) you can get better estimates (but usually have to work quite hard). When you're working in a high dimension a large fraction of the volume is close to the vertices -- making things much more difficult.</p> <p>In particular you might look at the work of Martin Huxley. For example his book "Lattice Points, Area and Exponential Sums" or a number of his papers on this subject.</p> http://mathoverflow.net/questions/32506/counting-points-on-lattices/32520#32520 Answer by Victor Protsak for Counting points on lattices Victor Protsak 2010-07-19T17:54:29Z 2010-07-19T21:04:16Z <p>Not a full answer, but here is a standard approach to questions of this kind. [<b>Added</b> Upon a further reflection, I am not sure whether this approach is the best or robust enough.]</p> <p>The set </p> <p><code>$$\Gamma_f=\{(x,y)\in\mathbb{Z}^r\oplus\mathbb{Z}: x\in\operatorname{Ker} f,\ 0\leq x_i\leq y \text{ for } 1\leq i\leq r\}$$</code> is an affine semigroup whose semigroup algebra is the homogeneous coordinate ring of a projective toric variety with Hilbert polynomial $H_{\Gamma_f}(t)$ with respect to a positive $\mathbb{Z}$-grading by $\deg y.$ For a large enough $N$, the number that you are interested in is $\frac{1}{N^r}H_{\Gamma_f}(N-1)$ and the error term you need is determined by the subleading coefficient of $H_{\Gamma_f}(t).$ It can probably be extracted from the information in Miller and Sturmfels, Combinatorial Commutative Algebra.</p>