Asymptotics of the number of primitive lattice triangulations of rectangles of width 4 4 and 5 5

S. Yu. Orevkov · 2024

Read Asymptotics of the number of primitive lattice triangulations of rectangles of width 4 4 and 5 5 by S. Yu. Orevkov (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-17065.txt.

Introduction

Stepan Orevkov counts the ways a rectangle on a grid can be split into basic triangles. Each triangle must have no grid points inside it or on its edges, apart from its corners. He asks how the count grows as the long side of the rectangle grows. The growth rate is summed up by a limit for each fixed width.

For widths of four and five, he writes those limits through sets of integral equations of Fredholm type. The equations act on functions that build the counts step by step. He solves them on a computer to get close values for the limits. Earlier work had settled widths up to three, so the study extends the known range.

Catalog record

CREATORS. Yu. Orevkov
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE69 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-17065

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Asymptotics of the number of primitive lattice triangulations of rectangles of width 4 4 and 5 5 S. Yu. Orevkov Abstract . Let f ⁡ ( m , n ) f(m,n) be the number of primitive lattice triangulations of an m × n m\times n rectangle. We express the limits lim n f ​ ( m , n ) 1 / n \lim_{n}f(m,n)^{1/n} for m = 4 m=4 and m = 5 m=5 in terms of certain systems of Fredholm integral equations on generating functions (the case m ≤ 3 m\leq 3 was treated in a previous paper). Solving these equations numerically, we compute approximate values of these limits with a rather high precision. 1. Introduction. Main results This paper is a sequel of [ 7 ] . A lattice triangulation of a polygon in \mathbb{R}^{2} is a triangulation with all vertices in \mathbb{Z}^{2} . A lattice triangulation is called primitive (or unimodular ) if each triangle is primitive, i.e., has the minimal possible area 1/2 . We denote the number of primitive lattice triangulations of an m\times n rectangle by f(m,n) . Let c_{m,n}=\frac{\log_{2}f(m,n)}{mn},\qquad c_{m}=\lim_{n\to\infty}c_{m,n},\qquad c=\lim_{m\to\infty}c_{m}=\lim_{n\to\infty}c_{n,n}. The existence of the limits is proven in [ 3 , Proposition 3.6] . In [ 3 ] the number c(m,n) is called the capacity of an m\times n rectangle. Some estimates of c_{m} and c were obtained in [ 1 , 3 , 5 , 6 , 7 , 11 ] (see more details in [ 7 ] ). In particular, the best known upper bound for c is c\leq 4\log_{2}\frac{1+\sqrt{5}}{2}\approx 2.777 ; see [ 11 ] . It is easy to show that f(1,n)=\binom{2n}{n} and hence c_{1}=2 ; see [ 3 , §2.1] . The exact value c_{2}=\frac{1}{2}\log_{2}\frac{611+\sqrt{73}}{36} and 360 decimal digits of c_{3} were computed in [ 7 ] . Using the same approach, we compute here 65 digits of c_{4} and 15 digits of c_{5} , namely, \lim_{n}f(4,n)^{\frac{1}{4n}}=4.29876675750096911161795913111746998157492178224986284763745615251, \lim_{n\to\infty}f(5,n)^{\frac{1}{5n}}=4.34096161931753, and hence c_{4}=2.10392283469307790885509194765035290599163301991475089470275817980, c\geq c_{5}=2.11801466703561. So far this is the best proven lower bound for c . As in [ 7 ] , we express c_{4} (see § 2 ) and c_{5} (see § 3 ) in terms of solutions of systems of integral equations, and we compute the approximate values of c_{4} and c_{5} by solving systems of usual linear equations obtained by replacing the integrals with Riemann sums. However, the computations here are more complicated than in [ 7 ] . Another difference from [ 7 ] is the following. In [ 7 ] we reduced the problem to a single classical Fredholm equation of the first kind with an analytic kernel of integration. Since the integral operator was compact, it was easy to prove the uniqueness of its solution and the exponential rate of convergence of its discretizations. In the present paper, the integral operators are no longer compact: the unknown functions are functions of two (for c_{4} ) or three (for c_{5} ) variables but the operators involve the integration with respect to only one variable (i.e., the kernel of integration is a kind of delta-function). In § 2.6 we discuss the uniqueness of solutions and the convergence of discretizations for such operators. In § 4 we expose two simple observations which allowed us to improve the convergence. They were crucial for the computation of c_{4} and c_{5} with so high accuracy. They also allowed us to compute c_{3} to 1100 digits. In § 5 we report about newly computed exact values of f(m,n) and about an empirical estimate for c_{6} , c_{7} , and for the subexponential factor of the asymptotics, which we computed via known values of f(m,n) by a method proposed by Lando and Zvonkin in [ 4 , §6] . In § 6 we give an asymptotic lower bound for the number of all (not only primitive) lattice triangulations. 2. Strips of width 4 In this section we express c_{4} via solution of a certain system of integral equations on the generating functions, whose numerical solution allows us to compute c_{4} to 65 decimal digits. 2.1. Reduction to trapezoids (which decreases the dimension of the problem) (Cf. [ 7 , §4.1] .) For a,e\geq 0 such that a+e is even, let j_{a,e}^{*} be the number of primitive triangulations of the trapezoid T_{4}(a,e) spanned by (0,0) , (1,4) , (1+e,4) , (a,0) . We set j_{0,0}^{*}=1 and j^{*}_{a,e}=0 when a+e is odd. Consider the generating function J^{*}(x)=\sum_{n}j_{n}^{*}x^{n}=\sum_{a,e\geq 0}j_{a,e}^{*}x^{a+e}=1+6x^{2}+750x^{4}+189121x^{6}+\dots Let j_{a,e} be the number of the primitive triangulations of T_{4}(a,e) which do not have interior edges of the form [(k,0),(l,4)] (by convention, j_{0,0}=0 ) and let J(x)=\sum_{n}j_{n}x^{n}=\sum_{a,e\geq 0}j_{a,e}x^{a+e}=6x^{2}+714x^{4}+180337x^{6}+\dots Then we have J^{*}(x)=\frac{1}{1-J(x)}\qquad\text{and}\qquad\lim_{n\to\infty}f(4,n)^{1/n}=\lim_{n\to\infty}(j_{2n}^{*})^{1/n} (see [ 7 , §4.1] and [ 7 , Lemma 3.1] respectively). Thus c_{4}=-\frac{1}{2}\log_{2}\beta_{4}, (2.1) where \beta_{4} is the first real root of the equation J(x)=1 . 2.2. Recurrence relations We introduce a notation similar to that in [ 7 , §4] . For integers a,b,c,d,e such that a\geq-1 and b,c,d,e\geq 0 , let f_{a,b,c,d,e} denote the number of primitive lattice triangulations of the polygon [(0,a),(1,b),(2,c),(3,d),(4,e),(4,0),(0,-1)] (see Figure 1 ) without interior edges of the form [(0,y_{1}),(4,y_{2})] ( side-to-side edges). Following [ 3 ] , we call these polygons shapes . Similarly we define g,h,j with corresponding subscripts and superscripts according to Figure 1 . For example, if a\geq-1 , \min(c,d,e)\geq 0 , and c-a\equiv 1 mod 2 , then we define g_{a,c,d,e}^{(1)} to be the number of primitive lattice triangulations of the shape [(0,a),(2,c),(3,d),(4,e),(4,0),(0,-1)] without interior side-to-side edges. If the inequalities or congruences are not satisfied, we set the corresponding numbers to zero. By convention, j_{-1,0}^{(1)}=0 ; in this case the shape degenerates to the segment [(0,-1),(4,0)] . f_{a,b,c,d,e} g^{(1)}_{a,c,d,e} g^{(2)}_{a,b,d,e} g^{(3)}_{a,b,c,e} c-a\equiv 1(2) d-b\equiv 1(2) e-c\equiv 1(2) h^{(1)}_{a,d,e} h^{(2)}_{a,d,e} h^{(3)}_{a,c,e} h^{(4)}_{a,b,e} h^{(5)}_{a,b,e} d-a\equiv 1(3) d-a\equiv 2(3) c-a\equiv 1(2) e-b\equiv 1(3) e-b\equiv 2(3) \,e-c\equiv 1(2) j^{(1)}_{a,e} j^{(2)}_{a,e} e-a\equiv 1(4) e-a\equiv 3(4) Figure 1. We introduce the generating functions for these numbers F(x,y,z,w,v)=\sum_{a,b,c,d,e}f_{a,b,c,d,e}x^{a}y^{b}z^{c}w^{d}v^{e},\qquad J_{k}(x,v)=\sum_{a,e}j^{(k)}_{a,e}x^{a}v^{e}\quad(k=1,2), G_{1}(x,z,w,v)=\sum_{a,c,d,e}g^{(1)}_{a,c,d,e}x^{a}z^{c}w^{d}v^{e},\qquad G_{2}(x,y,w,v)=\sum_{a,b,d,e}g^{(2)}_{a,b,d,e}x^{a}y^{b}w^{d}v^{e}, G_{3}(x,y,z,v)=\sum_{a,b,c,e}g^{(3)}_{a,b,c,e}x^{a}y^{b}z^{c}v^{e},\qquad H_{3}(x,z,v)=\sum_{a,c,e}h^{(3)}_{a,c,e}x^{a}z^{c}v^{e}, H_{k}(x,w,v)=\sum_{a,d,e}h^{(k)}_{a,d,e}x^{a}w^{d}v^{e}\;(k=1,2),\quad H_{k}(x,y,v)=\sum_{a,b,e}h^{(k)}_{a,b,e}x^{a}y^{b}v^{e}\;(k=4,5), and their symmetrizations \displaystyle\widetilde{F}(x,y,z,w,v) \displaystyle=F(x,y,z,w,v)+F(v,w,z,y,x), \displaystyle\widetilde{G}_{1}(x,z,w,v) \displaystyle=G_{1}(x,z,w,v)+G_{3}(v,w,z,x), \displaystyle\widetilde{G}_{2}(x,y,w,v) \displaystyle=G_{2}(x,y,w,v)+G_{2}(v,w,y,x), \displaystyle\widetilde{H}_{k}(x,w,v) \displaystyle=H_{k}(x,w,v)+H_{6-k}(v,w,x),\qquad k=1,2, \displaystyle\widetilde{H}_{3}(x,z,v) \displaystyle=H_{3}(x,z,v)+H_{3}(v,z,x), \displaystyle\widetilde{J}_{1}(x,v) \displaystyle=J_{1}(x,v)+J_{2}(v,x). Throughout the paper we use the notation \operatorname{\mathfrak{cf}}_{\mathbf{m}}\mathcal{F} for the coefficient of a monomial \mathbf{m}=\mathbf{m}(x_{1},x_{2},\dots) in a Laurent series \mathcal{F}=\mathcal{F}(x_{1},x_{2},\dots) . In this notation, the recurrence relations in [ 7 , Lemma 2.2] take the following form (cf. [ 7 , §4.2] ; here we omit the intermediate step consisting in finding the relations between the non-symmetrized generating functions): \displaystyle\widetilde{F}(x,y,z,w,v)Q(x,y,z,w,v) \displaystyle=y^{1/2}\widetilde{G}_{1}\big(xy^{1/2},y^{1/2}z,w,v\big)(1-w-v) \displaystyle\quad+z^{1/2}\widetilde{G}_{2}\big(x,yz^{1/2},z^{1/2}w,v\big)(1-x)(1-v) \displaystyle\quad+w^{1/2}\widetilde{G}_{1}\big(vw^{1/2},w^{1/2}z,y,x\big)(1-y-x) \displaystyle\quad-y^{1/2}w^{1/2}\widetilde{H}_{3}\big(xy^{1/2},y^{1/2}zw^{1/2},w^{1/2}v\big), where Q(x,y,z,w,v)=1-x-y-z-w-v+xz+xw+xv+yw+yv+zv-xzv , \displaystyle\widetilde{G}_{1}(x,z,w,v)(1-w-v) \displaystyle=\operatorname{\mathfrak{cf}}_{\xi^{-1}}\widetilde{F}\Big(\frac{x}{\xi},\xi^{2},\frac{z}{\xi},w,v\Big)(1-w-v) \displaystyle\quad-w^{1/2}\operatorname{\mathfrak{cf}}_{\xi^{-1}}\widetilde{G}_{1}\Big(vw^{1/2},\frac{w^{1/2}z}{\xi},\xi^{2},\frac{x}{\xi}\Big) \displaystyle\quad+z^{1/3}(1-v)\widetilde{H}_{1}\big(xz^{1/3},z^{2/3}w,v\big) \displaystyle\quad+w^{1/2}\widetilde{H}_{3}\big(x,zw^{1/2},w^{1/2}v\big), \displaystyle\widetilde{G}_{2}(x,y,w,v)(1-x)(1-v) \displaystyle=\operatorname{\mathfrak{cf}}_{\xi^{-1}}\widetilde{F}\Big(x,\frac{y}{\xi},\xi^{2},\frac{w}{\xi},v\Big)(1-x)(1-v) \displaystyle\quad+y^{1/3}(1-v)\widetilde{H}_{2}\big(xy^{2/3},y^{1/3}w,v\big) \displaystyle\quad+w^{1/3}(1-x)\widetilde{H}_{2}\big(vw^{2/3},w^{1/3}y,x\big), \displaystyle\widetilde{H}_{1}(x,w,v)(1-v)=\operatorname{\mathfrak{cf}}_{\xi^{-1}}\widetilde{G}_{2}\Big(\frac{x}{\xi^{2}},\xi^{3},\frac{w}{\xi},v\Big)(1-v)+\frac{1}{x}, \displaystyle\widetilde{H}_{2}(x,w,v)=\operatorname{\mathfrak{cf}}_{\xi^{-1}}\widetilde{G}_{1}\Big(\frac{x}{\xi},\xi^{3},\frac{w}{\xi^{2}},v\Big), \displaystyle\widetilde{H}_{3}(x,z,v)=\operatorname{\mathfrak{cf}}_{\xi^{-1}}\!\widetilde{G}_{1}\Big(x,\frac{z}{\xi},\xi^{2},\frac{v}{\xi}\Big)+\operatorname{\mathfrak{cf}}_{\xi^{-1}}\!\widetilde{G}_{1}\Big(v,\frac{z}{\xi},\xi^{2},\frac{x}{\xi}\Big)-\operatorname{\mathfrak{cf}}_{\xi_{1}^{-1}\xi_{2}^{-1}}\!\widetilde{F}\Big(\frac{x}{\xi_{1}},\xi_{1}^{2},\frac{z}{\xi_{1}\xi_{2}},\xi_{2}^{2},\frac{v}{\xi_{2}}\Big), \displaystyle\widetilde{J}_{1}(x,v)=\operatorname{\mathfrak{cf}}_{\xi^{-1}}\widetilde{H}_{2}\Big(\frac{v}{\xi},\xi^{4},\frac{x}{\xi^{3}}\Big). Notice that (see § 2.1 for the definition of J(x) ) J(x)=x\widetilde{J}_{1}(x,x). (2.2) 2.3. A change of variables We set \displaystyle f(t,s,u)=\widetilde{F}\Big(\frac{x}{t},\frac{x^{2}t^{2}}{s},\frac{x^{2}s^{2}}{tu},\frac{x^{2}u^{2}}{s},\frac{x}{u}\Big), \displaystyle\qquad q(t,s,u)=Q\Big(\frac{x}{t},\frac{x^{2}t^{2}}{s},\frac{x^{2}s^{2}}{tu},\frac{x^{2}u^{2}}{s},\frac{x}{u}\Big), \displaystyle g_{1}(s,u)=\frac{1}{s^{1/2}}\,\widetilde{G}_{1}\Big(\frac{x^{2}}{s^{1/2}},\frac{x^{3}s^{3/2}}{u},\frac{x^{2}u^{2}}{s},\frac{x}{u}\Big), \displaystyle\quad g_{2}(t,u)=\frac{1}{(tu)^{1/2}}\,\widetilde{G}_{2}\Big(\frac{x}{t},\frac{x^{3}t^{3/2}}{u^{1/2}},\frac{x^{3}u^{3/2}}{t^{1/2}},\frac{x}{u}\Big), \displaystyle h_{k}(u)=\frac{1}{u^{k/3}}\widetilde{H}_{k}\Big(\frac{x^{3}}{u^{1/3}},x^{4}u^{4/3},\frac{x}{u}\Big)\;\;(k=1, \displaystyle 2),\qquad h_{3}(s)=\widetilde{H}_{3}\Big(\frac{x^{2}}{s^{1/2}},x^{4}s,\frac{x^{2}}{s^{1/2}}\Big), \displaystyle j_{1}(x)=\widetilde{J}_{1}(x^{4},x^{4}),\qquad\quad p(s,u)=1\,-\, \displaystyle\frac{x^{2}u^{2}}{s}-\frac{x}{u},\qquad\quad r(t,u)=\Big(1-\frac{x}{t}\Big)\Big(1-\frac{x}{u}\Big). The combinatorial meaning of f,g_{k},h_{k},j_{1} is the following. Let S be a shape contributing to the coefficient of a monomial \mathbf{m} of one of these series. Then the exponent of x in \mathbf{m} is equal to 2\int_{0}^{4}\varphi(x)dx where y=\varphi(x) is the equation of the upper boundary of S . The variables t,s,u correspond to the vertical lines x=1 , x=2 , x=3 respectively. If (x_{0},y_{0}) , (x_{1},y_{1}) , (x_{2},y_{2}) are three consecutive vertices on the upper boundary of

Read the complete text