Counting points on lattices - MathOverflow

Counting points on lattices

2010-07-19T14:53:50Z

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=(ℤ/pⁿℤ)^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.

Answer by Victor Miller for Counting points on lattices

2010-07-19T17:33:09Z

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.

Answer by Victor Protsak for Counting points on lattices

2010-07-19T17:54:29Z

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.