Let T 2 n be the set of all triangulations of the square [0, n] 2 with all the vertices belonging to Z 2 . We show that Cn 2 <log Card T 2 n <Dn 2 .
1999 Academic Press
Triangulations with integral vertices appear in the algebraic geometry. They are used in Viro's method of construction of real algebraic varieties with controlled topological properties [2]. In [1], the discriminant of a polynomial a # A c a x a with a fixed finite set of multi-indices A/Z d is described in terms of triangulations of the convex hull of A with vertices in A. Here we study the asymptotics of the number of triangulations with integral vertices when the size of the triangulated polytope tends to infinity.
Denote by I n the segment [0, n]/R and let I d n :=I n _ } } } _I n /R d be the d-dimensional cube with the side n. Denote by T d n the set of all triangulations of I d n whose vertices are integral points.
Question. What are the asymptotics of log Card T d n when n Γ ?
Only the evident estimates are known for an arbitrary d 2:
To get the left inequality, divide I d n into n d cubes; each of them can be subdivided into simplices at least in two ways. To obtain the right inequality, note that the number of all integral d-simplices contained in I d n is bounded