Counting lattice points inside an n-dimensional tetrahedron. - MathOverflow

Counting lattice points inside an n-dimensional tetrahedron.

2012-11-01T11:31:56Z

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.

Answer by Dima Pasechnik for Counting lattice points inside an n-dimensional tetrahedron.

2012-11-01T12:18:34Z

Try the book by M.Beck and S.Robins (the link brings you to a PDF version)

Answer by Richard Stanley for Counting lattice points inside an n-dimensional tetrahedron.

2012-11-04T16:19:42Z

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}$?

Answer by Sinai Robins for Counting lattice points inside an n-dimensional tetrahedron.

2012-11-06T05:17:44Z

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.