## Counting points on lattices

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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.

Let f: ℤr→ H be a surjective homomorphism into a finite group. Let

`$S(N)= \frac{1}{N^r}\#\{(x_1,\dots,x_r)\in \ker f\colon  0\leq x_i <N\}$`.

One expects that S(N) is roughly |H|-1. My question is:

What is the best known estimate of the error term S(N)-|H|-1 in terms of N and the structure of H? I am especially interested in the case, when H=(ℤ/pnℤ)d, for some d<r.

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

`$S(N) - h^{-1} \ll h^{-1}(\log \min\{h,N\})^r \max\{eN^{-1},e^rN^{-r}\}$`,

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.

-

## 2 Answers

Note that $ker(f)$ is a sublattice of the integer lattice `$\mathbb{Z}^r$`. 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 `$\mathbb{R}^r$` 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.

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.

-

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

Not a full answer, but here is a standard approach to questions of this kind. [Added Upon a further reflection, I am not sure whether this approach is the best or robust enough.]

The set

`$$\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\}$$` 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.

-

To supplement this -- by applying the inverse of the matrix formed by the basis of the lattice $ker(f)$ we reduce to the problem of counting integral lattice points in a polytope.  This paper math.ucdavis.edu/~deloera/RECENT_WORK/… contains a nice survey.  In particular using the Hilbert Polynomial (as Victor P. suggested) will be helpful. – Victor Miller Jul 21 2010 at 13:27
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 22, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9357429146766663, "perplexity_flag": "head"}