Counting lattice points inside an n-dimensional tetrahedron. - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T20:59:06Z http://mathoverflow.net/feeds/question/111141 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/111141/counting-lattice-points-inside-an-n-dimensional-tetrahedron Counting lattice points inside an n-dimensional tetrahedron. Ankush 2012-11-01T11:31:56Z 2012-11-07T14:58:59Z <p>Suppose, $1 &lt; a_1\leq a_2\leq....\leq a_n$ are n-real numbers. Consider the hyperplanes defined by the equations,</p> <p>$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) </p> <p>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} &lt; 1.$ Indeed I will be thankful if somebody could give me some references. </p> <p>Thanks.</p> http://mathoverflow.net/questions/111141/counting-lattice-points-inside-an-n-dimensional-tetrahedron/111148#111148 Answer by Dima Pasechnik for Counting lattice points inside an n-dimensional tetrahedron. Dima Pasechnik 2012-11-01T12:18:34Z 2012-11-01T12:18:34Z <p>Try the <a href="http://math.sfsu.edu/beck/ccd.html" rel="nofollow">book</a> by M.Beck and S.Robins (the link brings you to a PDF version)</p> http://mathoverflow.net/questions/111141/counting-lattice-points-inside-an-n-dimensional-tetrahedron/111472#111472 Answer by Richard Stanley for Counting lattice points inside an n-dimensional tetrahedron. Richard Stanley 2012-11-04T16:19:42Z 2012-11-04T16:19:42Z <p>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}&lt; 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.")</p> <p>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}$?</p> http://mathoverflow.net/questions/111141/counting-lattice-points-inside-an-n-dimensional-tetrahedron/111619#111619 Answer by Sinai Robins for Counting lattice points inside an n-dimensional tetrahedron. Sinai Robins 2012-11-06T05:17:44Z 2012-11-07T14:58:59Z <p>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:</p> <p>G. H. Hardy and J. E. Littlewood, Some Problems of Diophantine Approximation, in ‘’Proc. 5th Int. Congress of Mathematics” (1912), 223–229.</p> <p>G. H. Hardy and J. E. Littlewood , The lattice points of a right-angled triangle, Proc. London Math. Soc. (2) 20 (1921) 15–36.</p> <p>G. H. Hardy and J. E. Littlewood , The lattice points of a right-angled triangle (second memoir), Hamburg Math. Abh. 1 (1922) 212–249.</p> <p>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.</p> <p>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:</p> <p>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.</p> <p>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.</p>