Counting integral points of a polytope in R^3 (the c_1 coefficient of Ehrhart polynomial) - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T11:28:08Z http://mathoverflow.net/feeds/question/46387 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/46387/counting-integral-points-of-a-polytope-in-r3-the-c-1-coefficient-of-ehrhart-po Counting integral points of a polytope in R^3 (the c_1 coefficient of Ehrhart polynomial) Dmitry Kerner 2010-11-17T18:27:34Z 2010-11-19T06:18:18Z <p>(Sorry I'm outsider in this field.)</p> <p>I need to count the number of integral points in a convex polytope in $\mathbf{R}^3$. The cones in the dual fan are not necessarily regular (does it create any problem?)</p> <p>So, I need the $c_1$ coefficient of the Ehrhart polynomial. There're some formulas (complicated enough for me) but I heard one can express $c_1$ as the sum (over all the edges of the polytope) of the integral lengths of the edges times some correction factors.</p> <ol> <li>Can someone give the formula? (In the simple English, please.) Or a reference to something very down-to-earth? </li> <li>In fact I do not need the precise expression but only a very good lower bound. Does something like this exist? </li> </ol> http://mathoverflow.net/questions/46387/counting-integral-points-of-a-polytope-in-r3-the-c-1-coefficient-of-ehrhart-po/46398#46398 Answer by Andres Caicedo for Counting integral points of a polytope in R^3 (the c_1 coefficient of Ehrhart polynomial) Andres Caicedo 2010-11-17T19:22:42Z 2010-11-17T19:22:42Z <p>Hi. You probably will be interested in the beautiful book by Matthias Beck and Sinai Robins, "Computing the Continuous Discretely. Integer-Point Enumeration in Polyhedra", Springer 2009. A pdf is <a href="http://math.sfsu.edu/beck/ccd.html" rel="nofollow">available</a> from Beck's website. </p> http://mathoverflow.net/questions/46387/counting-integral-points-of-a-polytope-in-r3-the-c-1-coefficient-of-ehrhart-po/46596#46596 Answer by matthias beck for Counting integral points of a polytope in R^3 (the c_1 coefficient of Ehrhart polynomial) matthias beck 2010-11-19T06:18:18Z 2010-11-19T06:18:18Z <p>Jamie Pommersheim gave a general formula for $c_1$ in his 1993 paper in Math. Ann. for the case of a tetrahedron. So if you can easily triangulate your polytope, this might be useful.</p> <p>If you're "only" interested in bounds, you might want to look at the Ehrhart series instead, i.e., the generating function of the Ehrhart polynomial. This is a rational function with denominator (1-x)^4, so the information encoded in the numerator is the same information encoded in the Ehrhart polynomial (in fact, it's a linear transformation). A famous theorem of Stanley states that the numerator coefficients of the Ehrhart series are nonnegative, and of course this gives you inequalities among the coefficients of the Ehrhart polynomial. For more inequalities of this type, check out Alan Stapledon's work (e.g., <a href="http://front.math.ucdavis.edu/0904.3035" rel="nofollow">http://front.math.ucdavis.edu/0904.3035</a> or <a href="http://front.math.ucdavis.edu/0801.0873" rel="nofollow">http://front.math.ucdavis.edu/0801.0873</a>).</p> <p>(And thanks for your kind words, Andres.)</p>