ASYMPTOTIC NUMBER OF

TRIANGULATIONS WITH VERTICES IN Z^{2}

S.Yu.Orevkov

Abstract. Let T_{n}^{2} 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_{n}^{2} < Dn^{2}.

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_{n}^{d} := I_{n} × ⋯ × I_{n} ⊂ R^{d} be the d-dimensional cube with the side n. Denote by T_{n}^{d} the set of all triangulations of I_{n}^{d} whose vertices are integral points.

Question. What are the asymptotics of log Card T_{n}^{d} when n → ∞ ?

Only the evident estimates are known for an arbitrary d ≥ 2:

A_{d} n^{d} < log Card T_{n}^{d} < B_{d} n^{d} log n, (A_{d}, B_{d} > 0).

To get the left inequality, divide I_{n}^{d} 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_{n}^{d} is bounded by c_{1}n^{c_{2}} and the number of d-simplices in each T ∈ T_{n}^{d} is bounded by c_{3}n^{d}, hence,

Card T_{n}^{d} ≤ ∑_{q=1}^{c_{3}n^{d}} \binom{c_{1}n^{c_{2}}}{q} ≤ c_{4}(c_{1}n^{c_{2}})^{c_{3}n^{d}}

(here c_{1}, ..., c_{4} depend on d but do not depend on n).

In this note we show that for d = 2 the main term of the asymptotics is const·n^{2}.

A triangulation T ∈ T_{n}^{d} is called primitive if the volume of each d-dimensional simplex equals 1/d!. Let PT _{n}^{d} = {T ∈ T_{n}^{d} | T is primitive}.

Theorem. There exist positive constants A and B such that

An^{2} < log Card PT _{n}^{2} < Bn^{2}.

Typeset by AMS-TEX

Partially supported by Grants RFFI-96-01-01218 and DGICYT SAB95-0502

Corollary. There exist positive constants C and D such that

Cn^{2} < log Card T_{n}^{2} < Dn^{2}.

Denote by π : I_{n}^{2} → I_{n} the projection (x, y) ↦ x. Given a T ∈ T_{n}^{2}, let us say that a subset U ⊂ I_{n}^{2} is T -univalent if U is a closed simplicial subcomplex of T such that I_{n} × {0} ⊂ U, and all the fibers (π|_{U})^{−1}(x), x ∈ I_{n} are connected.

Lemma. Let T ∈ PT _{n}^{2} and let U be a T -univalent subset of I_{n}^{2}. If U ≠ I_{n}^{2} then there exists a triangle σ ∈ T such that σ ⊄ U and U ∪ σ is T -univalent.

Proof. Denote by T_{U} the set of all triangles σ ∈ T such that σ ⊄ U and σ ∩ U contains a segment. Let σ ∈ T_{U}. Denote the vertices of σ by a, b, c so that π(a) ≤ π(b), [ab] ⊂ U. We shall say that σ hangs to the left (resp. to the right) if π(c) < π(a) (resp. π(b) < π(c)) and c ∉ U. Denote by T_{U}^{(L)} (resp. T_{U}^{(R)}) the set of triangles σ ∈ T_{U} hanging to the left (resp. to the right). Clearly that if σ ∈ T_{U} and U ∪ σ is not T -univalent then σ ∈ T_{U}^{(L)} ∪ T_{U}^{(R)}. Thus, in the case T_{U}^{(L)} = T_{U}^{(R)} = ∅ we can choose any σ ∈ T_{U}. Suppose T_{U}^{(L)} ≠ ∅ (the case T_{U}^{(R)} ≠ ∅ can be treated the same way). Say that σ_{1} ∈ T_{U} is to the left of σ_{2} ∈ T_{U} if σ_{1} ∩ U is to the left of σ_{2} ∩ U. Let σ_{0} be the most left triangle from T_{U}^{(L)} and let σ ∈ T_{U} be such that σ ∩ U is adjacent from the left to σ_{0} ∩ U. Then σ ∉ T_{U}^{(L)} because σ_{0} was the most left. We have also σ ∉ T_{U}^{(R)}. Indeed, otherwise σ would intersect σ_{0} because σ hangs to the right and σ_{0} hangs to the left. Hence, U ∪ σ is T -univalent. □

Proof of Theorem. As we pointed out above, the estimate An^{2} < log Card PT _{n}^{2} is evident. Let us prove that log Card PT _{n}^{2} < Bn^{2}.

To each T ∈ PT _{n}^{2} we associate the sequence of T -univalent subsets I_{n} × {0} = U_{0} ⊂ U_{1} ⊂ ⋯ ⊂ U_{N} = I_{n}^{2}, N = 2n^{2}, where U_{j+1} = U_{j} ∪ σ_{j} and σ_{j} is the most left among the triangles σ ∈ T such that σ ⊄ U_{j}, σ ∪ U_{j} is T -univalent. Denote by E the set of all edges of T and put E_{j} = {e ∈ E | e ⊂ U_{j}}, k_{j} = Card E_{j}. Let e_{1}, …, e_{k_{N}} be all the edges of T numerated so that E_{0} = {e_{1}, …, e_{k_{0}}} and E_{j+1} \ E_{j} = {e_{k_{j}+1}, …, e_{k_{j+1}}} (j = 0, ..., N), the elements of each E_{j+1} \ E_{j} being numerated from the left to the right. Let us define the vector v_{T} = (v_{1}, …, v_{k_{N}}) as follows. If e_{j} is vertical or e_{j} ⊂ I_{n} ×{1} then we put v_{j} = 1. Otherwise, if e_{j} = [ab], π(a) < π(b), and σ = [abc] ∈ T is the triangle adjacent to [ab] from above, then put

v_{j} = \{ \begin{matrix}1 & if π(c) < π(a), \\ 2 & if π(c) = π(a), \\ 3 & if π(a) < π(c) ≤ π(b), \\ 4 & if π(c) > π(b). \end{matrix}

It is clear that that the number of all possible vectors v_{T} is bounded by 4^{3n^{2}}. Therefore, to complete the proof it suffices to show that T is uniquely determined by v_{T}. Indeed, if v_{T} is known then one can inductively reconstruct all the sets E_{0}, E_{1}, … as follows. Suppose U_{j} is already reconstructed. Let e_{j_{1}}, …, e_{j_{m}} be all the non-vertical edges (numerated from the left to the right) lying on ∂U_{j} \ ∂I_{n}^{2}. Then the triangle σ, adjacent to e_{j_{i}} from above, being attached to E_{j} yields a T -univalent set if and only if one of the following three cases holds: (i) 2 ≤ v_{j_{i}} ≤ 3; (ii) v_{j_{i−1}} = 4 and v_{j_{i}} = 1; (iii) v_{j_{i}} = 4 and v_{j_{i+1}} = 1. In all the cases σ is uniquely determined by σ ∩ E_{j} (due to the primitivity condition). □

Proof of Corollary. Each T ∈ T_{n}^{2} can be subdivided to a T′ ∈ PT _{n}^{2}. Let E and E′ be the sets of edges of T and T′ not lying on ∂I_{n}^{2}. Clearly that T is uniquely determined by T′ and E. Hence, Card T_{n}^{2} ≤ ∑_{T′} Card{E ⊂ E′} < (Card PT _{n}^{2}) · 2^{3n^{2}} since Card E′ = 3n^{2} − 2n < 3n^{2}. □

The properties of integral points were essential to our proof. However, the following generalization seems to be true. Given a finite set A ⊂ R^{2}, denote by T (A) the set of triangulations of the convex hull of A with vertices belonging to A.

Conjecture. There exists a constant C_{1} such that log Card T (A) ≤ C_{1} Card A for any finite A ⊂ R^{2}.

This is well-known when A is the set of vertices of a convex polygon. In this case Card T (A) is the Catalan number \frac{1}{n−1} \binom{2n−4}{n−2} where n = Card A. Note also, that an analogue of the Lemma is true for any finite A ⊂ R^{2}.

I am grateful to V. Kharlamov for suggesting the problem and useful discussions. I thank the referee for useful remarks.

References

[1]. I.M. Gelfand, M.M. Kapranov, A.V. Zelevinskii, Discriminants, resultants an multidimen-

sional determinants, Birkhäuser, Boston, 1994.

[2] O.Ya. Viro, Gluing of plane real algebraic curves and constructions of curves of degrees 6 and 7, Lect. Notes Math. 1960 (1984), 187–200.

Steklov Mathematical Institute, Russ. Acad. Sci. Gubkina 8, Moscow, 117966, Russia