# Counting lattice points inside an n-dimensional tetrahedron.

Suppose, $1 < a_1\leq a_2\leq....\leq a_n$ are n-real numbers. Consider the hyperplanes defined by the equations,

$x_1=0,\;x_2=0,.......,x_n=0$ and $\frac{x_1}{a_1}+\frac{x_2}{a_2}+...+\frac{x_n}{a_n}=1$..... (1)

I want to know a sharp upper bound on the number of lattice points inside (1). That is, the cardinality of the set of points $(x_1, x_2,...,x_n)\in (\mathbb{Z}^+)^n$ such that $\frac{x_1}{a_1}+\frac{x_2}{a_2}+...+\frac{x_n}{a_n} < 1.$ Indeed I will be thankful if somebody could give me some references.

Thanks.

-
A good keyword to search on is "Ehrhart polynomial" for finding out about counting lattice points in polytopes. –  Patricia Hersh Nov 1 '12 at 12:20
Since the $a_i$'s are real numbers, the Ehrhart theory is not going to be applicable. A first approximation will be the volume of the tetrahedron, viz., $a_1a_2\cdots a_n/n!$. Computing the error may be analogous to counting lattice points in a circle (en.wikipedia.org/wiki/Gauss_circle_problem). –  Richard Stanley Nov 1 '12 at 13:02
Richard, thank you for clarifying. At first I had actually missed that the $a_i$'s were not integers. –  Patricia Hersh Nov 1 '12 at 13:11

Here are some further thoughts in addition to my comment. Suppose that $a_1,\dots,a_n$ are integers $>1$. Write $\alpha=(a_1,\dots,a_n)$ and let $N(\alpha)$ be the number of integer vectors $(x_1,\dots,x_n)$ satisfying $x_i> 0$ and $\frac{x_1}{a_1}+\cdots+\frac{x_n}{a_n}< 1$. Let $\mathrm{lcm}(a_1,\dots,a_n)$ denote the least common multiple of $a_1,\dots,a_n$. Let $u$ be a positive integer. If my computations are correct, the Ehrhart theory gives that as $u\to\infty$, $$N(u\alpha) = \frac{a_1\cdots a_n}{n!}u^n - \frac{a_1\cdots a_n}{2(n-1)!}\left( \frac{1}{a_1} +\cdots+\frac{1}{a_n} +\frac{1}{\mathrm{lcm}(a_1,\dots,a_n)}\right)u^{n-1} +O(u^{n-2}).$$ It seems reasonable that the above formula with $u=1$ will be a good approximation to $N(\alpha)$ when all $a_i$'s are large (and integers). It should be a better approximation than the first term, which just comes from the volume. (The second term comes from the "relative surface area.")

If $\epsilon>0$ is sufficiently small, then the points counted by $N((u+\epsilon)\alpha)$ will be the same as those counted by $N(u\alpha)$, except for the additional points satisfying $x_i>0$ and $\frac{x_1}{a_1}+\cdots+\frac{x_n}{a_n}=1$. We then get $$N((u+\epsilon)\alpha) = \frac{a_1\cdots a_n}{n!}u^n - \frac{a_1\cdots a_n}{2(n-1)!}\left( \frac{1}{a_1} +\cdots+\frac{1}{a_n} -\frac{1}{\mathrm{lcm}(a_1,\dots,a_n)}\right)u^{n-1} +O(u^{n-2}).$$ This suggests the following question. Suppose that the $a_i$'s are any real numbers $>1$, as in the statement of the problem. What are the lim sup and lim inf of $$u^{-n+1}\left(N(u\alpha)-\frac{a_1\cdots a_n}{n!}u^n\right)$$ as $u\to\infty$, $u\in\mathbb{R}$?

-

This kind of question has come up in the context of "smooth numbers" and their use in factoring large integers. But even in two dimensions, the real right-angled triangle has posed serious difficulties, starting with a sequence of papers by Hardy and Littlewood:

G. H. Hardy and J. E. Littlewood, Some Problems of Diophantine Approximation, in ‘’Proc. 5th Int. Congress of Mathematics” (1912), 223–229.

G. H. Hardy and J. E. Littlewood , The lattice points of a right-angled triangle, Proc. London Math. Soc. (2) 20 (1921) 15–36.

G. H. Hardy and J. E. Littlewood , The lattice points of a right-angled triangle (second memoir), Hamburg Math. Abh. 1 (1922) 212–249.

To add flesh to my comment above, suppose you wish to factor a large integer N, and use a fixed "factor base" of primes, so you attempt to write N as a product of these primes to some powers, take logarithms of both sides, divide by log N, and you have an equality of the sort that you are asking about.

For more references, there is a sequence of papers trying to solve this problem in the context of a conjecture they call the "Durfree Conjecture" about the genus of algebraic curves. They have a nice bibliography, and one of their more recent papers for this line of research that I could find for you is:

Stephen T. Yau and Letian Zhang, AN UPPER ESTIMATE OF INTEGRAL POINTS IN REAL SIMPLICES WITH AN APPLICATION TO SINGULARITY THEORY, Math. Res. Lett. 13 (2006), no. 6, 911–921.

The Ehrhart theory can bound such integer counts in real tetrahedra from above and from below, which I've also thought about a bit, but these bounds are of course always asymptotic, as Richard Stanley points out.

-
Hi Sinai, I'm told it's not appropriate to sign your answers; you can edit your answer and remove the signature :-) –  Dima Pasechnik Nov 6 '12 at 6:19
Welcome to mathoverflow! –  Ian Agol Nov 7 '12 at 23:13
Thanks, Agol, it seems like a fun hangout. –  Sinai Robins Nov 8 '12 at 10:27

-
Wow, beat me by 1 minute. See also pnas.org/content/100/2/426.full; the earlier work of Brion and Vergne in JAMS may also be of interest: jstor.org/discover/10.2307/…. –  Steve Huntsman Nov 1 '12 at 12:20
Thanks, Dima, for the nice comment about my book with Matthias. ;) –  Sinai Robins Nov 10 '12 at 19:30
I'd like to mention that I was always motivated by chapter 4 of Stanley's Enumerative Combinatorics book, for which the 2'nd edition is now available. It's a great resource. –  Sinai Robins Nov 10 '12 at 19:32