MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

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.

share|cite|improve this answer

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.

share|cite|improve this answer
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 contains a nice survey. In particular using the Hilbert Polynomial (as Victor P. suggested) will be helpful. – Victor Miller Jul 21 '10 at 13:27

You want to count points of sublattice $\mathrm{ker}(f)\subset\mathbb{Z}^r$ in some convex body. A general answer to this question was given by Davenport in the note On a Principle of Lipschitz.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.