Families of Polytopes with Rational Linear Precision in Higher Dimensions
DOI: 10.1007/s10208-022-09583-7
© The Author(s) 2022
Received: 27 September 2021
Accepted: 27 June 2022
Published: 8 August 2022
Abstract
In this article, we introduce a new family of lattice polytopes with rational linear precision. For this purpose, we define a new class of discrete statistical models that we call multinomial staged tree models. We prove that these models have rational maximum likelihood estimators (MLE) and give a criterion for these models to be log-linear. Our main result is then obtained by applying Garcia-Puente and Sottile’s theorem that establishes a correspondence between polytopes with rational linear precision and log-linear models with rational MLE. Throughout this article, we also study the interplay between the primitive collections of the normal fan of a polytope with rational linear precision and the shape of the Horn matrix of its corresponding statistical model. Finally, we investigate lattice polytopes arising from toric multinomial staged tree models, in terms of the combinatorics of their tree representations.
Keywords
Lattice polytope Horn parametrisation Rational linear precision Primitive collection Log-linear model Maximum likelihood estimator Toric variety Staged treeMathematics Subject Classification
Primary: 52B20 Secondary: 14M25 62R01 65D171 Introduction
In geometric modelling, pieces of parametrised curves and surfaces are used as building blocks to describe geometric shapes in 2D and 3D. Some of the most widely used parametric units for this purpose are Bézier curves, triangular Bézier surfaces, and tensor product surfaces. These pieces of curves and surfaces are constructed using a set of polynomial blending functions defined on the convex hull of a set of points \({\mathscr {A}}\), together with a set of control points. Taking as inspiration the theory of toric varieties and the form of the blending functions for the previous examples, Krasauskas introduced the more general notion of a toric patch whose domain is a lattice polytope \(P \subseteq \mathbb {R}^d\) [15]. The blending functions, \(\{\beta _{w,m}:P\rightarrow \mathbb {R}\}_{m\in {\mathscr {A}}}\), of a toric patch are constructed from the set of lattice points \({\mathscr {A}}{:=}P\cap \mathbb {Z}^d\) and a vector of positive weights w associated with each point in \({\mathscr {A}}\).
It is an open problem, motivated by geometric modelling, to characterise all pairs (P, w) that have rational linear precision in dimension \(d\ge 3\) [5, 15]. The classification of all such pairs in dimension \(d=2\) is given in [4].
Garcia-Puente and Sottile studied the property of rational linear precision for toric patches by associating a scaled projective toric variety \(X_{{\mathscr {A}},w}\) to the pair (P, w) [12]. The variety \(X_{{\mathscr {A}},w}\) is the image of the map \([w\chi ]_{{\mathscr {A}}}: (\mathbb {C}^*)^d\rightarrow \mathbb {P}^{n-1}\) defined by \({\mathbf {t}}\mapsto [w_1 {\mathbf {t}}^{m_1}:w_2 {\mathbf {t}}^{m_2}:\ldots : w_s {\mathbf {t}}^{m_n}]\) where \({\mathscr {A}}=\{m_1,\ldots ,m_n\}\). One of their main results states that a pair (P, w) has rational linear precision if and only if the variety \(X_{{\mathscr {A}},w}\), seen as a discrete statistical model, has rational maximum likelihood estimator (MLE). This result establishes a communication channel between geometric modelling and algebraic statistics. Thus, it is natural to use ideas from Algebraic Statistics to study the property of rational linear precision.
Models with rational MLE are algebraic varieties that admit a parametrisation known as Horn uniformisation [11, 14]. This parametrisation depends on a Horn matrix H and a coefficient for each column of H. In their recent study of moment maps of toric varieties [5], Clarke and Cox go one step further in strengthening the relationship between pairs (P, w) with rational linear precision and models \(X_{{\mathscr {A}},w}\) with rational MLE by using Horn matrices to characterise all pairs (P, w) that have strict linear precision. They propose the use of Horn matrices to study polytopes with rational linear precision and state several questions and conjectures about the relationship between the Horn matrix of \(X_{{\mathscr {A}},w}\) and the primitive collections of the normal fan of P.
In this article, we study the property of rational linear precision of pairs (P, w) from the point of view of Algebraic Statistics. Our main contribution is Theorem 4.1, which introduces a new family of polytopes (with associated weights) that has rational linear precision. We construct this family from a subclass of discrete statistical models introduced in Sect. 4 that we call multinomial staged trees. Looking at specific members of this family in 3D, we settle some of the questions raised in [5] related to Horn matrices and primitive collections.
This paper is structured as follows: In Sects. 2.1–2.4 we provide background material on rational linear precision, discrete statistical models with rational MLE, and Horn matrices. In Sect. 2.5, we state Questions 2.1 and 2.2 which guided our investigations related to Horn matrices and primitive collections. These questions are followed by a quick outline referring to the places in this article where they are addressed. In Sect. 3, we characterise the shape of the Horn matrix for pairs (P, w) in 2D. We also present a family of pairs (P, w) in 3D that has rational linear precision and explain several aspects of this family that relate to Questions 2.1 and 2.2. In Sect. 4.1, we define multinomial staged tree models, we prove they have rational MLE in Sect. 4.6 and we characterise the subclass of these models that are toric varieties in Sect. 4.5. These results lead to our main theorem, Theorem 4.1. Finally, in Sect. 5, we show that the examples from Sect. 3 are all multinomial staged trees and prove our conjectures about the relationship between the combinatorics of the trees and primitive collections.
2 Preliminaries
We assume the reader is familiar with introductory material on computational algebraic geometry and toric geometry at the level of [7] and [8].
2.1 Notation and Conventions
2.2 Rational Linear Precision
In this section, we follow closely the exposition in [5]. A more elementary introduction to this topic is available in [6, Chapter 3].
Definition 2.1
- 1.
For \(1\le j \le n\) and \(p\in P\), \(\beta _{j}(p){:=}h(p)^{h(m_j)}=\prod _{i=1}^r h_{i}(p)^{h_i(m_j)}.\)
- 2.
The functions \(\beta _{w,j}{:=}w_j \beta _{j}/\beta _{w}\) are the toric blending functions of (P, w), where \(\beta _{w}(p){:=} \sum _{j=1}^n w_j \beta _{j}(p).\)
- 3.Given control points \(\{Q_{j}\}_{1\le j \le n} \in \mathbb {R}^\ell \), the toric patch \(F:P\rightarrow \mathbb {R}^{\ell }\) is defined by$$\begin{aligned} p \mapsto \frac{1}{\beta _{w}(p)}\sum _{j=1}^n w_j \beta _{j}(p)Q_j. \end{aligned}$$(1)
In part (3) of the previous definition, it is natural to choose the set of control points to be \({\mathscr {A}}\).
Definition 2.2
- 1.
The tautological patch \(K_{w}\!:P\!\rightarrow \! P\) is the toric patch (1) where \(\{Q_j\!=\!m_j\}_{1\le j\le n}\).
- 2.The pair (P, w) has strict linear precision if \(K_{w}\) is the identity on P, that is$$\begin{aligned} p = \frac{1}{\beta _{w}(p)}\sum _{j=1}^n w_j \beta _{j}(p)m_j, \text { for all } p\in P. \end{aligned}$$
- 3.The pair (P, w) has rational linear precision if there are rational functions \(\hat{\beta _1},\ldots , \hat{\beta _n}\) on \(\mathbb {C}^d\) satisfying:
- (a)
\(\sum _{j=1}^n\hat{\beta }_j=1\) as rational functions on \(\mathbb {C}^d\).
- (b)
The map \(\hat{\beta }:\mathbb {C}^d \dasharrow X_{{\mathscr {A}},w}\subset \mathbb {P}^{n-1}\), \({\mathbf {t}}\rightarrow (\hat{\beta }_1({\mathbf {t}}), \ldots , \hat{\beta }_n({\mathbf {t}}))\) is a rational parametrisation of \(X_{{\mathscr {A}},w}\).
- (c)
For every \(p\in P \subset \mathbb {C}^d\), \(\hat{\beta }_j(p)\) is defined and is a nonnegative real number.
- (d)
\(\sum _{j=1}^{n}\hat{\beta }_j(p)m_j=p\) for all \(p\in P\).
- (a)
Remark 2.1
We are interested in the property of linear precision. By [12, Proposition 2.6], the blending functions \(\{\beta _{w,j}: 1\le j\le n \}\) have linear precision if and only if the pair (P, w) has strict linear precision. Rational linear precision requires the existence of rational functions \(\{\hat{\beta _j}: P\rightarrow \mathbb {R}: 1\le j\le n\}\) that have strict linear precision, and that are related to the blending functions of (P, w) via 3(b) in Definition 2.2.
Remark 2.2
An alternative way to specify a pair (P, w) is by using a homogeneous polynomial \(F_{{\mathscr {A}},w}\) whose dehomogenisation \(f_{{\mathscr {A}},w}= \sum _{j=1}^n w_j {\mathbf {t}}^{m_i}\) encodes the weights in the coefficients and the lattice points in \({\mathscr {A}}\) as exponents. We use this notation in Sect. 3 to describe toric patches in 2D and 3D.
Remark 2.3
If (P, w) has rational linear precision then \((aP,\tilde{w})\), \(a\ge 1\), also has this property where \(\tilde{w}\) is the vector of coefficients of \((f_{{\mathscr {A}},w})^a\). See [4, Lemma 2.2].
Example 2.1
Example 2.2
2.3 Discrete Statistical Models with Rational MLE
Definition 2.3
Let \(\mathcal {M}\) be a discrete statistical model with MLE \(\varPhi : \mathbb {R}^{n}\rightarrow \mathcal {M}, u\mapsto {\hat{p}}\). The model \(\mathcal {M}\) has rational MLE if the coordinate functions of \(\varPhi \) are rational functions in u.
Example 2.3
Definition 2.4
Example 2.4
Definition 2.5
We say that \((H,\lambda )\) is a Horn pair if: (1) the sum of the coordinates of \(\varphi _{(H,\lambda )}\) as rational functions in u is equal to 1 and (2) the map \(\varphi _{(H,\lambda )}\) is defined for all positive vectors and it sends these to positive vectors in \(\mathbb {R}^{r}\).
Theorem 2.1
[11, Theorem 1] A discrete statistical model \(\mathcal {M}\) has rational MLE \(\varPhi \) if and only if there exists a Horn pair \((H,\lambda )\) such that \(\mathcal {M}\) is the image of the Horn parametrisation \(\varphi _{(H,\lambda )}\) restricted to the open orthant \(\mathbb {R}_{>0}^{n}\) and \(\varPhi = \varphi _{(H,\lambda )}\) on \(\mathbb {R}_{>0}^{n}\).
It is possible that two Horn parametrisations \(\varphi _{(H,\lambda )}\) and \(\varphi _{(\tilde{H},{\tilde{\lambda }})}\) are equal even if \(H\ne \tilde{H}\) and \(\lambda \ne {\tilde{\lambda }}\). A Horn matrix H is minimal if it has no zero rows and no two rows are linearly dependent. By [5, Proposition 6.11] there exists a unique, up to permutation of the rows, minimal Horn matrix that defines \(\varphi _{(H,\lambda )}\). Any other pair \((H,\lambda )\) that defines the same Horn parametrisation may be transformed into one where H is a minimal Horn matrix; this is done by adding collinear rows, deleting zero rows, and adjusting the vector \(\lambda \) accordingly, see [11, Lemma 3]. We end this section by noting that [11, Proposition 23] states that if \((H,\lambda )\) is a minimal Horn pair, then every row of H has either all entries greater than or equal zero or all entries less than or equal to zero. We call the submatrix of H that consists of all rows with nonnegative entries, the positive part of H, and its complement the negative part of H.
2.4 The Links between Algebraic Statistics and Geometric Modelling
Remark 2.4
Theorem 2.2
[18, Corollary 7.3.9] The maximum likelihood estimate in \(\mathcal {M}_{{\mathscr {A}},w}\) for the empirical distribution \({\overline{u}}\in \varDelta _{n-1}^{\circ }\) is the unique point \({\hat{p}}\in \mathcal {M}_{{\mathscr {A}},w}\) that satisfies \(\tau _{{\mathscr {A}}}({\hat{p}})=\tau _{{\mathscr {A}}}({\overline{u}})\).
In the Algebraic Statistics literature, models with rational MLE are also known as models with maximum likelihood degree equal to 1. Even though the previous theorem guarantees the existence and uniqueness of the MLE, it is not true that every log-linear model has rational MLE. We refer the reader to [1] for several examples of log-linear models that do not have rational MLE, or equivalently for examples of models with maximum likelihood degree greater than 1. We end this section by recalling two theorems that connect models with rational MLE and pairs with rational linear precision.
Theorem 2.3
[12, Proposition 5.1] The pair (P, w) has rational linear precision if and only if the model \(\mathcal {M}_{{\mathscr {A}},w}\) has rational MLE.
Theorem 2.4
- 1.
The pair (P, w) has strict linear precision.
- 2.
\(n_P =0\) and \(\beta _{w}(p)=\sum _{j=1}^{n}w_j \beta _{j}(p) =\sum _{j=1}^n w_j \prod _{i=1}^r h_{i}(p)^{h_{i}(m_j)}\) is a nonzero constant c.
- 3.\(\mathcal {M}_{{\mathscr {A}},w}\) has rational MLE with minimal Horn pair \((H,\lambda )\) given by$$\begin{aligned} H=\begin{pmatrix} h_1(m_1) &{} h_1(m_2) &{} \ldots &{} h_1(m_n) \\ h_2(m_1) &{} h_2(m_2) &{} \ldots &{} h_2(m_n) \\ \vdots &{} \vdots &{} &{} \vdots \\ h_r(m_1) &{} h_r(m_2) &{} \ldots &{} h_{r}(m_n) \\ -a_P &{} -a_P &{} \ldots &{}-a_P \end{pmatrix},\;\;\;\; \lambda _j = \frac{w_j}{c}(-a_P)^{a_{P}} \end{aligned}$$
2.5 Primitive Collections and Horn Pairs
The notion of primitive collections was first introduced by Batyrev in [3] for a smooth and projective toric variety \(X_{\varSigma _P}\) of the polytope P. It provides an elegant description of the nef cone for \(X_{\varSigma _P}\). This result has been generalised to the simplicial case and the definition of primitive collections for the non-simplicial case has been introduced in [9].
Definition 2.6
- 1.
\(C \nsubseteq \sigma (1)\) for all \(\sigma \in \varSigma _P\).
- 2.
For every proper subset \(C' \subsetneq C\), there exists \(\sigma \in \varSigma _P\) such that \(C' \subseteq \sigma (1)\).
For strict linear precision, Theorem 2.4 gives the minimal Horn pair based only on the lattice distance functions of the facets of the polytope. The authors in [5] raise the question whether it is possible to obtain a similar description of minimal Horn pairs of polytopes with rational linear precision.
Question 2.1
Is the positive part of the minimal Horn matrix of a pair (P, w) with rational linear precision always equal to the lattice distance matrix of \({\mathscr {A}}\)?
For pairs (P, w) in 2D with rational linear precision, and the family of prismatoids in Sect. 3.2, the answer to Question 2.1 is affirmative, see Theorem 3.1, Proposition 3.2, and Appendix A.
In [5], there are two examples, one of a trapezoid [5, Section 8.1] and one of a decomposable graphical model [5, Section 8.3], where the positive part of the Horn matrix is the lattice distance matrix of \({\mathscr {A}}\) and the negative rows are obtained via the primitive collections of the normal fan of P. These examples motivate the next definition and Question 2.2:
Definition 2.7
To a pair (P, w) we associate the matrix \(M_{{\mathscr {A}},\varSigma _P}\) which consists of the lattice distance matrix of \({\mathscr {A}}\), with ij-th entry \(h_{i}(m_j)\), together with negative rows given by summing the rows of the lattice distance functions \(-h_i\), for which the facet normals \(n_i\) belong to the same primitive collection of \(\varSigma _P\).
Question 2.2
For a pair (P, w) with rational linear precision is there a Horn pair \((H,\lambda )\) for which \(H=M_{{\mathscr {A}},\varSigma _P}\)?
For pairs (P, w) in 2D with rational linear precision, the answer to Question 2.2 is affirmative, see Theorem 3.1. For the family of prismatoids in Sect. 3.2, Question 2.2 is affirmative only for certain subclasses, see Theorem 3.3. For an arbitrary pair (P, w) with rational linear precision, the matrix \(M_{{\mathscr {A}},\varSigma _P}\) is not necessarily a Horn matrix, see Sect. 3.3.1. Even in the case that \(M_{{\mathscr {A}},\varSigma _P}\) is a Horn matrix, it does not necessarily give rise to a Horn pair for (P, w), see Sect. 3.3.2. In Sect. 3, we see a number of special cases for which the answer to Question 2.2 is affirmative. In Sect. 5, we give a condition on (P, w) which guarantees the existence of a Horn pair \((H,\lambda )\) with \(H=M_{{\mathscr {A}},\varSigma _P}\). We also provide an explanation for the negative rows of the Horn matrix in the language of multinomial staged tree models—introduced in Sect. 4.
3 Examples of Horn Pairs in 2D and 3D
In this section, we present families of 2D and 3D pairs (P, w) with rational linear precision and explore the connection between the geometry of the polytope and the shape of its corresponding Horn pair. Throughout this section, we use (s, t), respectively, (s, t, v) to denote \({\mathbf {t}}\) in the 2D, respectively, 3D case.
3.1 Toric Surface Patches and Horn Pairs in 2D
Left: Bézier triangles. Middle: Tensor product patches. Right: Trapezoids. The normal fan of each polygon is displayed in the bottom row; two rays with the same colour are in the same primitive collection
For general a, b, d, the Newton polytope associated with \(f_{a,b,d}\), which we will denote by \(T_{a,b,d}\), will be a trapezoidal patch, in the special cases \(T_{0,b,1}=b\varDelta _2\) and \(T_{a,b,0}=a\varDelta _1\times b\varDelta _1\), we will have the more familiar Bézier triangles and tensor product patches. The lattice points in \(T_{a,b,d}\cap \mathbb {Z}^{2}\) are \( {\mathscr {A}}= \{(i,j): 0\le j \le b, 0\le i\le a+d(b-j)\} \). By Theorems 2.1 and 2.3 we know that the statistical model associated with a pair in \(\mathcal {F}\) admits a Horn pair.
Proposition 3.1
Proof
Remark 3.1
The blending functions \(\{\hat{\beta }_m: m\in {\mathscr {A}}\}\) for each pair (P, w) in \(\mathcal {F}\) that satisfy Definition 2.2 (3) are given in equation (4) in the previous proof. For the case \(a=d=1\) and \(b=2\), these are written in Example 2.1.
Remark 3.2
For general a, b, d, Proposition 3.1 gives the minimal Horn pair for \(T_{a,b,d}\); this is not the case for \(T_{0,b,1}\) and \(T_{a,b,0}\). For the last two cases, the minimal Horn pair is obtained after row reduction operations or from Theorem 2.4.
Using Proposition 3.1 and Theorem 2.4 we obtain an affirmative answer to Question 2.1 for pairs (P, w) in 2D. A closer look at the primitive collections in Fig. 1 also reveals an affirmative answer to Question 2.2. This is contained in the next theorem.
Theorem 3.1
Every pair (P, w) in 2D with rational linear precision has a Horn pair \((H,\lambda )\) with \(H=M_{{\mathscr {A}},\varSigma _P}\).
Proof
The normal fans of the polygons in \(\mathcal {F}\) are depicted in Fig. 1, in each subcase the shape of the normal fan and its primitive collections are independent of the values of a, b, d. The minimal Horn pair \((H,\lambda )\) for the 2D simplex, \(T_{0,b,1}=b\varDelta _2\), given in Theorem 2.4 satisfies \(H=M_{{\mathscr {A}},\varSigma _P}\). This follows because \(b\varDelta _2\) has one primitive collection, \(\{n_1,n_2,n_3\}\) and hence \(M_{{\mathscr {A}},\varSigma _P}\) has a single negative row. For the tensor product patch \(T_{a,b,0}=a\varDelta _1 \times b\varDelta _1\) and the general trapezoid \(T_{a,b,d}\), the primitive collections are \(\{n_1,n_3\}\) and \(\{n_2,n_4\}\). In these cases, the Horn pair \((H,\lambda )\) in Proposition 3.1 satisfies \(H=M_{{\mathscr {A}},\varSigma _P}\). \(\square \)
3.2 A Family of Prismatoids with Rational Linear Precision
The general representative of a prismatoid in \(\mathcal {P}\) is the convex hull of two trapezoids, \(conv(T_{a,b,d}\times \{0\}, T_{a',b',d}\times \{1\})\), dilated by l. For the labelling of facets, we refer to Notation 3.2
Representative members of \(\mathcal {P}\)
(A) Prismatoids with trapezoidal base \(a>0,b>0,d>0,l>0\) | |||
Trapezoidal frusta \(a'>0\), \(b'>0\) |
| Triangle top (simplex if \(d=1\)) \(a'=0\), \(b'>0\) |
|
Trapezoidal wedges \(a'>0\), \(b'=0\) |
| Trapezoidal Pyramids \(a'=0\), \(b'=0\) |
|
(B) Prismatoids with tensor product base \(a>0\), \(b>0\), \(d=0\), \(l>0\) | |||
Tensor product frusta \(a'>0,\,b'>0\) |
| Tensor product wedges \(a'=0\), \(b'>0\) |
|
Tensor product pyramids \(a'=0,\,b'=0\) |
| Tensor product wedges \(a'>0\), \(b'=0\) | |
(C) Prismatoids with triangular base \(a=0\), \(b>0\), \(d>0\), \(l>0\) | |||
Triangular frusta (simplices if \(d=1\))\(a'=0\), \(b'>0\) |
| Pyramid (simplex-based if \(d=1\)) \(a'=0\), \(b'=0\) |
|
(D) 3D Bézier simploids \(l>0\) | |||
3D Tensor Product \(a'=a>0\) \(b'=b>0\) \(d=0\) \(la\varDelta _{1}\times lb\varDelta _{1}\times l\varDelta _{1}\) |
| Triangular Prism \(a'=a=0\) \(b'= b>0\) \( d=1\) \(lb\varDelta _{2}\times l\varDelta _{1}\) |
|
3D simplex \(a'=a=0\) \(b'=0,b=1\) \( d=1\) \(l\varDelta _{3}\) |
| ||
Proposition 3.2
Proof
3.3 Minimal Horn Pairs for Prismatoids in \(\mathcal {P}\)
We now study Questions 2.1 and 2.2 for elements in \(\mathcal {P}\). Proposition 3.2 gives a Horn pair \((H,\lambda )\) for each \((P,w)\in \mathcal {P}\) in Table 1, however H need not be the minimal Horn matrix in each case. By [11, Lemma 9], we can find the minimal Horn matrix associated with (P, w) using row reduction operations on H.
Notation 3.2
3.3.1 The Non-simple Prismatoids
For a pair (P, w) in the subfamily of non-simple prismatoids in \(\mathcal {P}\), the matrix \(M_{{\mathscr {A}},\varSigma _P}\) cannot be a Horn matrix since the primitive collections are not a partition of the 1-dimensional rays of the normal fan and therefore the columns cannot add to zero.
Example 3.1
3.3.2 The Simple Prismatoids with Fewer Facets
Example 3.2
3.3.3 The Trapezoidal and Tensor Product Frusta
Example 3.3
Theorem 3.3
For all pairs in \(\mathcal {P}\), the positive part of the minimal Horn matrix is the lattice distance matrix of \({\mathscr {A}}\). For the subfamilies of \(\mathcal {P}\) in Table 2, the matrix \(M_{{\mathscr {A}},\varSigma _P}\) gives rise to a Horn pair for (P, w).
Subfamilies of prismatoids for which there exists a Horn pair \((H,\lambda )\) with \(H=M_{{\mathscr {A}},\varSigma _{P}}\)
Name of subfamily | Constraints on \(a'\le a,b'\le b,d\) |
|---|---|
Trapezoidal wedges | \(a'>0,\,b'=0,\,b=1,\,d>0\) |
Tensor product wedges (\(a'=0\)) | \(a'=0,\,a=1,\,b'>0,\,d=0\) |
Tensor product wedges (\(b'=0\)) | \(a'>0,\,b'=0,\,b=1,\,d=0\) |
3D simplex | \(a'=a=b'=0,\,b=1,\,d=1\) |
Triangular frusta | \(a'=a=0,\,b>0,\,d=1\) |
Tensor product frusta | \(a'>0,\,b'>0,\,d=0\) |
Trapezoidal frusta | \(a'>0,\,b'>0,\,d>0\) |
Proof
Let \((P,w)\in \mathcal {P}\), if \(M_{{\mathscr {A}},\varSigma _P}\) is a Horn matrix, then after row reduction operations, we get a minimal Horn matrix. Comparing this matrix with the minimal Horn matrix associated with (P, w) in Table 3 (Appendix A) and by uniqueness of minimal Horn matrices, one can verify both statements on the theorem. \(\square \)
4 Multinomial Staged Tree Models
In this section, we define multinomial staged tree models, we prove that every such model has rational MLE and we give criteria to determine when such models are toric varieties for binary multinomial staged trees, see Theorem 4.4 and Theorem 4.3, respectively. To each toric binary multinomial staged tree, one can associate a polytope, by Theorem 2.3 such a polytope has rational linear precision. These results imply our main theorem:
Theorem 4.1
Polytopes of toric binary multinomial staged trees have rational linear precision.
General sketch of a multinomial staged tree. The vertex v is labelled by the floret of degree 3 on \(S_l\), denoted by \(f_{l,3}\). The green vertices are the leaves and a root-to-leaf path is shown in orange
4.1 Definition of Multinomial Staged Trees
We start by introducing the multinomial model as an event tree. This model is the building block of multinomial staged tree models. Throughout this section m denotes a positive integer and \([m]{:=}\{1,2,\ldots ,m\}\), this differs from Sect. 3 where m was used for lattice point.
Example 4.1
The multinomial model encodes the experiment of rolling a q-sided die n independent times and recording the side that came up each time. The outcome space for this model is the set \(\varOmega \) of all tuples \(K=(k_1,\cdots ,k_q)\in \mathbb {N}^q\) whose entries sum to n. We can depict this model by a rooted tree \(\mathcal {T}=(V,E)\) with vertices \(V=\{r\}\cup \{r(K):K\in \varOmega \}\) and edges \(E=\{r\rightarrow r(K): K\in \varOmega \}\). To keep track of the probability of each outcome we can further label \(\mathcal {T}\) with monomials on the set of symbols \(\{s_1,\ldots , s_q\}\). Each symbol \(s_i\) represents the probability that the die shows side i when rolled once. The monomial representing the probability of outcome K is the term with vector of exponents K in the multinomial expansion of \((s_1+\ldots +s_q)^n\), namely \({n\atopwithdelims ()K}\prod _{i=1}^ns_i^{k_i}\), where \({n\atopwithdelims ()K}{:=}{n\atopwithdelims ()k_1,\cdots ,k_m}\). The labelled tree \(b\mathcal {T}_{\varDelta _2}\) in Fig. 4, represents the multinomial model with \(n=b\) and \(q=3\).
In general terms a multinomial staged tree, is a labelled and directed event tree such that at each vertex, the subsequent event is given by a multinomial model as in Example 4.1. To introduce this concept formally, we start with a rooted and directed tree \(\mathcal {T}=(V,E)\) with vertex set V and edge set E such that edges are directed away from the root. The directed edge from v to w is denoted \(v\rightarrow w\), the set of children of a vertex \(v\in V\) is \(\mathrm {ch}(v){:=}\{u\in V:v\rightarrow u\in E\}\) and the set of outgoing edges from v is \(E(v){:=}\{v\rightarrow u: u\in \mathrm {ch}(v)\}\). If \(\mathrm {ch}(v)=\emptyset \) then we say that v is a leaf and we let \({\widetilde{V}}\) denote the set of non-leaf vertices of \(\mathcal {T}\).
Given a rooted and directed tree \(\mathcal {T}\), we now explain how to label its edges using monomials terms. Figure 3 shows a general sketch of a multinomial staged tree.
Definition 4.1
- (1)
The sets \(S_1,\ldots ,S_m\) are called stages.
- (2)
For \(a\in \mathbb {Z}_{\ge 1}\) and \(\ell \in [m]\), a floret of degree a on \(S_{\ell }\) is the set of terms in the multinomial expansion of the expression \((\sum _{i\in I_{\ell }}s_i)^a\), we denote this set by \(f_{\ell ,a}\).
- (3)
A function \(\mathcal {L}:E \rightarrow \bigcup _{\ell \in [m], a\in \mathbb {Z}_{\ge 1}}f_{\ell ,a}\) is a labelling of \(\mathcal {T}\) if for every \(v\in {\widetilde{V}}\), \(\mathcal {L}(E(v))=f_{\ell ,a}\) for some \(\ell \in [m],\;a\in \mathbb {Z}_{\ge 1}\), and the restriction \(\mathcal {L}_{v}: E(v)\rightarrow f_{\ell ,a}\) is a bijection.
- (4)
A multinomial staged tree is a pair \((\mathcal {T},\mathcal {L})\), where \(\mathcal {T}\) is a rooted directed tree and \(\mathcal {L}\) is a labelling of \(\mathcal {T}\) as in condition (3).
In a multinomial staged tree \((\mathcal {T},\mathcal {L})\), each \(v\in {\widetilde{V}}\) is associated with the floret \(f_{\ell ,a}\) that satisfies \(\mathrm {im}(\mathcal {L}_v)=f_{\ell ,a}\). In this case, we index the children of v by v(K) where \(K=(k_{i_1},\ldots , k_{i_{|I_{\ell }|}}) \in \mathbb {N}^{|I_{\ell }|}\) is a tuple of nonnegative integers that add to a and \(i_1,\ldots , i_{|I_{\ell }|}\) is a fixed ordering of the elements in \(I_{\ell }\). It follows that when \(\mathrm {im}(\mathcal {L}_{v})=f_{\ell ,a}\), then \(E(v)=\{v\rightarrow v(K): K\in \mathbb {N}^{|I_{\ell }|}, |K|=a\}\), where \(|K|{:=} \sum _{q=1}^{|I_{\ell }|}k_{i_{q}}\). We further assume that the indexing of the children v is compatible with the labelling \(\mathcal {L}\), namely for all multinomial staged trees, \(\mathcal {L}_{v}(v\rightarrow v(K)) = {a\atopwithdelims ()K}\prod _{q=1}^{|I_{\ell }|}s_{i_q}^{k_{i_q}}\), where \({a\atopwithdelims ()K}={a \atopwithdelims ()k_{i_1},\ldots , k_{i_{|I_{\ell }|}}}\). It is important to note that this local description of the tree at the vertex v is the multinomial model described in Example 4.1 up to a change of notation. To clarify the notation just introduced we revisit Example 4.1 with a concrete choice of parameters.
Example 4.2
Consider the multinomial model for \(q=2\) and \(n=3\), the outcome space are all possible outcomes of flipping a coin 3 times. Here \(S=S_1=\{s_1,s_2\}\) and the root vertex v will have 4 children, all of which are leaves. The 4 edges of the tree will be labelled by the elements in the floret \(f_{1,3}=\{s_1^3,3s_1^2s_2,3s_1s_2^2,3s_2^3\}\). The sets of children and outgoing edges of v are then \(\mathrm {ch}(v)=\{v(3,0),v(2,1),v(1,2),v(0,3)\}\) and \(E(v)=\{v\rightarrow v(3,0),v\rightarrow v(2,1),v\rightarrow v(1,2),v \rightarrow v(0,3)\}\).
Remark 4.1
We will always consider a multinomial staged tree \((\mathcal {T},\mathcal {L})\) as an embedded tree in the plane. This means the tree has a fixed ordering of its edges and vertices. The level of a vertex v in \(\mathcal {T}\) is the number edges in a path from the root to v. All the trees we consider satisfy the property that two florets associated with two vertices in different levels must be on different stages. This implies that each root-to-leaf path contains at most one monomial term from each floret. Several figures in Sect. 5 contain multinomial staged trees, in these pictures, for simplicity, we omit the coefficients of the monomial edge labels.
Definition 4.2
Remark 4.2
The sum-to-one conditions on the parameter space \(\varTheta _{\mathcal {T}}\) imply that the image of \(\phi _{\mathcal {T}}\) is contained in \(\varDelta _{n-1}^{\circ }\). The multinomial coefficients on the labels of \(\mathcal {T}\) are necessary for this condition to hold. The model \(\mathcal {M}_{(\mathcal {T},\mathcal {L})}\) is an algebraic variety inside \(\varDelta _{n-1}^{\circ }\) with an explicit parameterisation given by \(\phi _{\mathcal {T}}\). For \(\theta \in \varTheta _{\mathcal {T}}\), \(\mathrm {eval}_{\theta }\) is the evaluation map \(s_i \mapsto \theta _i\). The j-th coordinate of \(\phi _{\mathcal {T}}\) is \(\mathrm {eval}_{\theta }(p_j)\), where \(p_{j}=c_j\prod _{i\in I}s_{i}^{a_{ij}}\) (Definition 4.2). For this reason we also use \(p_j\) to denote the j-th coordinate in the probability simplex \(\varDelta _{n-1}^\circ \).
Remark 4.3
If all of the florets in a multinomial staged tree have degree one, then it is called a staged tree. Multinomial staged tree models are a generalisation of discrete Bayesian networks [16] and of staged tree models introduced in [17].
Example 4.3
Definition 4.3
Remark 4.4
The ideal \(\ker (\varPsi _{\mathcal {T}})\) defines the model \(\mathcal {M}_{(\mathcal {T},\mathcal {L})}\) implicitly, i.e. \(\mathcal {M}_{(\mathcal {T},\mathcal {L})}= V(\ker (\varPsi _{\mathcal {T}}))\cap \varDelta _{n}^{\circ }\). Because of the containment \(\ker (\varPsi _{\mathcal {T}}^{\mathrm {toric}})\subset \ker (\varPsi _{\mathcal {T}})\), \(V(\ker (\varPsi _{\mathcal {T}}^{\mathrm {toric}}))\) is a toric variety that contains \(\mathcal {M}_{(\mathcal {T},\mathcal {L})}\). The polynomial \(1-\sum _{j\in J}P_j \) is always an element in \(\ker (\varPsi _{\mathcal {T}})\), hence using this polynomial as a homogenising element, we shall always consider \(\ker (\varPsi _{\mathcal {T}})\) as a homogeneous ideal in \(\mathbb {R}[P_{j}:j\in J]\).
4.2 The Ideal of Model Invariants for \(\mathcal {M}_{(\mathcal {T},\mathcal {L})}\)
As is common in algebraic geometry, finding the explicit equations of the prime ideal \(\ker (\varPsi _{\mathcal {T}})\) is hard. Luckily, the statistical insight of the problem allows us to find a nonprime ideal, usually referred to as the ideal of model invariants, that defines the model inside the probability simplex. We now define this ideal and postpone the proof that it has the aforementioned property to Sect. 4.4.
Definition 4.4
The previous definition indicates, that there are equations that must hold for every pair of vertices with the same associated stage, and equations that must hold for every vertex. The motivation for this definition of the ideal of model invariants arises from the technical Lemma 7.1 in Appendix B.
Remark 4.5
The generators of \(I_{\mathrm {vertices}}\) for each fixed vertex v are similar to the Veronese relations of the embedding \(\nu _{a}:\mathbb {P}^{|I_{\ell }|-1}\rightarrow \mathbb {P}^{M}\) by monomials of total degree a. The only difference is in the coefficients, defined in Lemma 7.1 part (2), that are needed for cancellation.
Remark 4.6
By definition, \(I_{\mathcal {M}(\mathcal {T},\mathcal {L})}\) always contains the sum-to-one condition \(1-\sum _{j\in J}P_{j}\), thus in a similar way as for \(\ker (\varPsi _{\mathcal {T}})\) in Remark 4.4, we always consider \(I_{\mathcal {M}(\mathcal {T},\mathcal {L})}\) as a homogeneous ideal generated by \(I_{\mathrm {stages}}\) and \(I_{\mathrm {vertices}}\).
4.3 Algebraic Lemmas for Multinomial Staged trees
To understand the defining equations of \(\ker (\varPsi _{\mathcal {T}})\) and the case when this ideal is toric, it is important to establish several lemmas that describe algebraic relations that hold in \(\mathbb {R}[P_j:j\in J]\), \(\mathbb {R}[s_i:i\in I]\), \(\mathbb {R}[P_j:j\in J]/\ker (\varPsi _{\mathcal {T}})\) and \(\mathbb {R}[P_j:j\in J]/I_{\mathcal {M}(\mathcal {T},\mathcal {L})}\). The reader may decide to skip this section and only get back to it when the lemmas are used in the proofs of Theorems 4.2 and 4.3.
Definition 4.5
Lemma 4.1
- (1)The polynomial t(v) satisfies$$\begin{aligned} t(v)=\sum _{|K|=a}{a \atopwithdelims ()K}\prod _{i\in I_{\ell }} s_i^{k_i}\cdot t(v(K)); \end{aligned}$$
- (2)
The image of \(P_{[v]}\) under \(\varPsi _{\mathcal {T}}^{\mathrm {toric}}\) is \(\left( \prod _{e\in \lambda _{r, v}}\mathcal {L}(e)\right) \cdot t(v)\), where \(\lambda _{r,v}\) is the set of edges in the root-to-v path in \(\mathcal {T}\). Moreover \(\varPsi _{\mathcal {T}}(P_{[v]})= \prod _{e\in \lambda _{r,v}}\mathcal {L}(e)\).
Proof
(1) Any path in \(\varLambda _{v}\) goes through a child v(K) of v. The sum of all the edge products corresponding to the paths that go through child v(K) is equal to the sum of all the edge products corresponding to the paths starting at v(K) (t(v(K))) multiplied by the label of the edge from v to v(K) (\({a \atopwithdelims ()K}\prod _{i\in I_{\ell }} s_i^{k_i}\)). Taking the sum of this expression over all children of v gives the desired result.
Lemma 4.2
Let \((\mathcal {T},\mathcal {L})\) be a multinomial staged tree, there is a containment of ideals \(I_{\mathcal {M}(\mathcal {T},\mathcal {L})}\subset \ker (\varPsi _{\mathcal {T}})\) in \(\mathbb {R}[P_j:j\in J]\).
Proof
\(\underline{\hbox {Claim}:}\) \(\quad \varPsi _{\mathcal {T}}(\sum _{\begin{array}{c} |K|=a\\ k_{i_q}\ge 1 \end{array}}k_{i_q}P_{[v(K)]})=as_{i_q}\prod _{e\in \lambda _{r,v}}\mathcal {L}(e)\).
4.4 Defining Equations of Binary Multinomial Staged Trees
In this section and the next, we prove Theorems 4.2 and 4.3 for binary multinomial staged trees; despite being unable to provide a proof, we believe these statements also hold for non-binary multinomial staged trees. First we show that the ring homomorphism \(\varPsi _{\mathcal {T}}\) admits an inverse when localised at a suitable element. From this, it follows as a corollary that the ideal of model invariants defines \(\mathcal {M}_{(\mathcal {T},\mathcal {L})}\) inside the probability simplex.
Theorem 4.2
Proof
Corollary 4.1
The ideal of model invariants defines the binary multinomial staged tree model inside the probability simplex, i.e. \(\mathcal {M}_{(\mathcal {T},\mathcal {L})}= V(I_{\mathcal {M}(\mathcal {T},\mathcal {L})})\cap \varDelta _{n-1}^{\circ }\).
Proof
The variety \(V(I_{\mathcal {M}(\mathcal {T},\mathcal {L})}: {\mathbf {P}}^{\infty })\) exactly describes the points in \(V(I_{\mathcal {M}(\mathcal {T},\mathcal {L})})\) that are not in \(V({\mathbf {P}})\). The latter variety contains the boundary of the simplex, hence restricting to positive points that add to one, yields \(\mathcal {M}_{(\mathcal {T},\mathcal {L})}= V(I_{\mathcal {M}(\mathcal {T},\mathcal {L})})\cap \varDelta _{n-1}^{\circ }\). \(\square \)
4.5 Toric Binary Multinomial Staged Tree Models
It is not true in general the ideal \(\ker (\varPsi _{\mathcal {T}})\) of a multinomial staged tree is toric. For the case of staged trees, a characterisation of when \(\ker (\varPsi _{\mathcal {T}})\) is equal to a subideal generated by binomials is available in [11]. The goal of this section is to establish a similar criterion, based on interpolating polynomials from Definition 4.5, for multinomial staged trees. This criterion will allow us to study the polyhedral geometry of these models in Sect. 5.
Definition 4.6
- (1)The vertex v is balanced if for all \(K^1,K^2,K^3,K^4\in \mathbb {N}^{|I_{\ell }|}\) with \(|K^1|=|K^2|=|K^3|=|K^4|=a\) and \(K^1+K^2=K^3+K^4\), the next identity holds in \(\mathbb {R}[s_i: i\in I]\)$$\begin{aligned} t(v(K^1))t(v(K^2))=t(v(K^3))t(v(K^4)). \end{aligned}$$
- (2)The pair of vertices v, w is balanced if for all tuples \(K,K',Q,Q' \in \mathbb {N}^{|I_{\ell }|}\) with \(|K|=|K'|=a\) and \(|Q|=|Q'|=b\) with \(K+Q'=K'+Q\) the following identity holds in \(\mathbb {R}[s_i: i\in I]\)$$\begin{aligned} t(v(K))\cdot t(w(Q'))= t(v(K'))\cdot t(w(Q)). \end{aligned}$$
Remark 4.7
Condition (1) in Definition 4.6 is an empty condition for florets of degree one. For staged trees, condition (2) specialises to the definition of balanced stated in [2].
Remark 4.8
If all root-to-leaf paths in \((\mathcal {T},\mathcal {L})\) have length 1, then \((\mathcal {T},\mathcal {L})\) is vacuously balanced. If \((\mathcal {T},\mathcal {L})\) has all root-to-leaf paths of length 2, such as \(\mathcal {T}_{a,b,d}\) in Fig. 5, it suffices to check that the root is balanced. For the other vertices, the conditions in Definition 4.6 reduce to the trivial equality \(1\cdot 1= 1\cdot 1\).
Theorem 4.3
Let \((\mathcal {T},\mathcal {L})\) be a binary multinomial staged tree. The model \(\mathcal {M}_{(\mathcal {T},\mathcal {L})}\) is toric if and only if \((\mathcal {T},\mathcal {L})\) is balanced.
Proof
Finally, combining Claim 1 and 2 we conclude that \(I_{\mathcal {M}(\mathcal {T},\mathcal {L})}\subset J \subset \ker (\varPsi _{\mathcal {T}}^{\mathrm {toric}})\subset \ker (\varPsi _{\mathcal {T}})\) if and only if \(\mathcal {T}\) is balanced. We now saturate this chain of ideals as in Theorem 4.2 to obtain \((I_{\mathcal {M}(\mathcal {T},\mathcal {L})}: {\mathbf {P}}^{\infty })=(\ker (\varPsi _{\mathcal {T}})^{\mathrm {toric}}:{\mathbf {P}}^{\infty }) = (\ker (\varPsi _{\mathcal {T}}):{\mathbf {P}}^{\infty })\). But \((\ker (\varPsi _{\mathcal {T}})^{\mathrm {toric}}:{\mathbf {P}}^{\infty })=\ker (\varPsi _{\mathcal {T}})^{\mathrm {toric}}\) and \((\ker (\varPsi _{\mathcal {T}}):{\mathbf {P}}^{\infty })= \ker (\varPsi _{\mathcal {T}})\) because they are prime ideals. Hence, \(\ker (\varPsi _{\mathcal {T}}^{\mathrm {toric}})\) and \(\ker (\varPsi _{\mathcal {T}})\) are equal. \(\square \)
4.6 Multinomial Staged Tree Models have Rational MLE
In this last section on multinomial staged trees, we prove that they have rational MLE. This fact together with Theorem 4.3 establishes Theorem 4.1 and thus provides a new class of polytopes that have rational linear precision.
Theorem 4.4
Proof
Corollary 4.2
Proof
5 Polytopes Arising from Toric Multinomial Staged Trees
The aim of this section is to bring together the examples of 2D and 3D polytopes with rational linear precision (Sect. 3) and multinomial staged trees (Sect. 4). To this end, we investigate certain properties of the lattice polytopes arising from toric multinomial staged trees. This leads to a better understanding of the negative part of the Horn matrix than that provided by the primitive collections. Recall that J denotes the set of root-to-leaf paths in \(\mathcal {T}\). For \(j \in J\), \(p_j\) is defined to be the product of all edge labels in the path j. We denote the stages of \((\mathcal {T},\mathcal {L})\) by \(S_1, \ldots , S_m\). Throughout this section m is a positive integer as in Sect. 4 and \(m_j\) (m with a subindex) denotes a lattice point as in Sect. 3.
Definition 5.1
The lattice polytope \(P_{\mathcal {T}}\) of a balanced multinomial staged tree \((\mathcal {T},\mathcal {L})\) is the convex hull of exponent vectors \(a_j\) of \(p_j\) for every root-to-leaf path j in \(\mathcal {T}\).
Note that \(P_{\mathcal {T}}\subset \mathbb {R}^d\) is not a full-dimensional polytope for \(d=|S_1|+\cdots +|S_m|\). This can be observed, e.g. in Fig. 4 (left) for \(P_{\mathcal {T}_{b\varDelta _2}} \cong b\varDelta _2\) (unimodularly equivalent). We call \((\mathcal {T}, \mathcal {L})\) a multinomial staged tree representation of a full-dimensional polytope \(P \cong P_{\mathcal {T}}\).
5.1 Two-Dimensional Multinomial Staged Tree Models
The polytopes in 2D from Sect. 3.1 admit a multinomial staged tree representation.
Proposition 5.1
All statistical models associated with pairs (P, w) in 2D with rational linear precision are toric multinomial staged tree models. The multinomial staged tree representations for each family in 2D are described in Fig. 4.
Proof
For the model \(b\varDelta _2=T_{0,b,1}\), it suffices to note that the polytope \(b\varDelta _n\) with weights given by multinomial coefficients has a Horn pair given by Theorem 2.4 which is equal to that one described in [11, Example 20] for multinomial models with b trials and \(n+1\) outcomes. The statistical model for \(T_{a,b,d}\) is the binary multinomial staged tree \(\mathcal {M}_{a,b,d}\) in Example 4.3, denoted by \(\mathcal {T}_{a,b,d}\) in Fig. 4. The Horn matrix in Proposition 3.1, associated with the model for \(T_{a,b,d}\), is equal to the Horn matrix of the model \(\mathcal {M}_{a,b,d}\). Firstly, in both cases the columns are indexed by pairs (i, j) such that \(0\le j\le b, 0\le i\le a+d(b-j)\) so these matrices have the same number of columns. Using Corollary 4.2, we see that the column corresponding to the outcome (i, j) in \(\mathcal {M}_{a,b,d}\) is \((i,j,a+d(b-j)-i,b-j,-(a+d(b-j)),-b)\), which equals the column associated with the lattice point (i, j) in Proposition 3.1. Uniqueness of the minimal Horn matrix, implies that the model associated with \(T_{a,b,d}\) is \(\mathcal {M}_{a,b,d}\).
The multinomial staged trees \(\mathcal {T}_{b\varDelta _2}\) and \(\mathcal {T}_{a,b,d}\) represent the multinomial model with three outcomes and b trials and the model in Example 4.3, respectively
Note that we obtain \(P_{\mathcal {T}_{0,b,1}} \cong b \varDelta _2\), i.e. we have two different tree representations of \(b\varDelta _2\): \(\mathcal {T}_{b \varDelta _2}\) and \(\mathcal {T}_{0,b,1}\). For the investigation of the shape of a Horn matrix, we will be interested in those trees \(\mathcal {T}\) where the positive part of the Horn matrix \(H_{(\mathcal {T},\mathcal {L})}\) from Corollary 4.2 is the lattice distance matrix of \(P_{\mathcal {T}}\) (Definition 5.3)(1). For simple polytopes \(P_{\mathcal {T}}\), these trees with an additional property provide us an explanation for the negative part of \(H_{(\mathcal {T},\mathcal {L})}\) in terms of primitive collections in Theorem 5.1.
5.2 Three-Dimensional Binary Multinomial Staged Tree Models
Before we examine the multinomial staged tree representations more generally, we present the multinomial staged trees for the family \(\mathcal {P}\) in Sect. 3.
Proposition 5.2
All statistical models associated with pairs in \(\mathcal {P}\) are toric binary multinomial staged trees.
Proof
Multinomial staged trees in 3D for pairs in Table 1(A)
To obtain the multinomial staged tree representations for the models of the polytopes in Table 1, we use the tree in the proof of Proposition 5.2 and specialise the values of the parameters \(a,a',b,b',d,l\) accordingly. The trees for the family of prismatoids with trapezoidal base in Table 1 (A), with \(l=1\), are depicted in Fig. 5. The trapezoidal frusta is represented by \(\mathcal {T}_{(A)_1}\), the upper branch is the model for \(T_{a,b,d}\) and the lower branch is the model for \(T_{a',b',d}\). The other trees, \(\mathcal {T}_{(A)_2}\), \(\mathcal {T}_{(A)_3}\) and \(\mathcal {T}_{(A)_4}\), have the same upper branch as \(\mathcal {T}_{(A)_1}\). For the prismatoid with simplex on top, the substitution \(a'=0\) has the effect of chopping a floret from \(\mathcal {T}_{(A)_1}\), this gives \(\mathcal {T}_{(A)_2}\). For the trapezoidal wedge, \(b'=0\), the edges in \(\mathcal {T}_{(A)_1}\) that contain \(b'\) contract to a single vertex, yielding \(\mathcal {T}_{(A)_3}\). For the trapezoidal pyramid, \(a'=b'=0\), we chop off the lower part of the tree after the edge labelled by \(s_1\). The trees for the remaining part of Table 1 (B), (C), and (D) are obtained similarly.
5.3 Properties of the Polytope \(P_{\mathcal {T}}\)
In this section, we study certain properties of \(P_{\mathcal {T}}\) that can be formulated in terms of the combinatorics of its tree \(\mathcal {T}\). We start by looking at root-to-leaf paths in \(\mathcal {T}\) that represent vertices of \(P_{\mathcal {T}}\), this allows us to work with the normal fan \(\varSigma _{P_{\mathcal {T}}}\). For simplicity we assume that \((\mathcal {T},\mathcal {L})\) has a root-to-leaf path of length m where \(S_1, \ldots , S_m\) are the stages of \(\mathcal {T}\).
Definition 5.2
A root-to-leaf path j is vertex representing if the exponent vector \(a_j\) of \(p_j\) is a vertex of \(P_{\mathcal {T}}\).
Lemma 5.1
Let \(P_{\mathcal {T}} \subset \mathbb {R}^d\) be a polytope where \((\mathcal {T},\mathcal {L})\) is a multinomial staged tree from Proposition 5.1 or Proposition 5.2. Then, the vertex representing paths in \(P_{\mathcal {T}}\) are those for which \(p_j\) is divisible by at most one symbol from each stage.
Proof
The upper and lower branches of the tree \(\mathcal {T}_{(A)_1}\) are the same up to a choice of parameters, thus we prove it only for the upper branch. Consider a root-to-leaf path \({\mathbf {j}}\) in \(\mathcal {T}_{(A)_1}\) such that \(a_{{\mathbf {j}}} = (1,0,j,b-j, k,a+d(b-j)-k)\) for \(0<j<b\) and \(0<k<a+d(b-j)\). Let \({\mathbf {j}}_1\) and \({\mathbf {j}}_2\) be two root-to-leaf paths such that \(a_{{\mathbf {j}}_1} = (1,0,j,b-j,a+d(b-j),0)\) and \(a_{{\mathbf {j}}_2} = (1,0,j,b-j,0,a+d(b-j))\). Then, we obtain the equality \(a_{{\mathbf {j}}} = \frac{k}{a+d(b-j))} a_{{\mathbf {j}}_1} + \frac{a+d(b-j)-k}{a+d(b-j))} a_{{\mathbf {j}}_2}\) and hence \(a_{{\mathbf {j}}}\) cannot be a vertex of \(P_{\mathcal {T}_{(A)_1}}\). It remains to show that \(a_{{\mathbf {j}}} = (1,0,j,b-j,a+d(b-j),0))\) is not a vertex. Let now \({\mathbf {j}}'_1\) and \({\mathbf {j}}'_2\) be two root-to-leaf paths such that \(p_{{\mathbf {j}}'_1}\) and \(p_{{\mathbf {j}}'_2}\) are divisible by one symbol from each stage and \(a_{{\mathbf {j}}'_1} = (1,0,b,0,a,0)\), \(a_{{\mathbf {j}}'_2} = (1,0,0,b, a+db,0)\). Hence, \(a_{{\mathbf {j}}} = \frac{j}{b} a_{{\mathbf {j}}'_1} + \frac{b-j}{b} a_{{\mathbf {j}}'_2}\) and \(a_{{\mathbf {j}}}\) is not a vertex of \(P_{\mathcal {T}_{(A)_1}}\). The proofs for the remaining trees follow similarly. \(\square \)
Next, we investigate the relation between primitive collections, Horn matrices, and stages of multinomial staged trees. The following definition was motivated by the observations on the trees from Sects. 5.1, 5.2 and by an attempt to answer Question 2.2.
Definition 5.3
Note that isomorphic polytopes have the same lattice distance matrices.
Lemma 5.2
Let \(P_{\mathcal {T}}\subset \mathbb {R}^d\) be a polytope with property \((\star )\). Then, \(P_{\mathcal {T}}\) is simple if and only if all root-to-leaf paths have the same length m and \(|S_1| + \cdots + |S_{m}| - m = \dim (P_{\mathcal {T}})\).
Proof
Recall that we assumed that there exists a root-to-leaf path of length m. All root-to-leaf paths have the same length m if and only if all vertex representing root-to-leaf paths have the same length m. Recall also that the vertices of \(P_{\mathcal {T}}\) are in one-to-one correspondence with the maximal cones of the normal fan \(\varSigma _{P_{\mathcal {T}}}\). First suppose that \(P_{\mathcal {T}}\) is simple and there exists a vertex representing root-to-leaf path \(j'\) of length \(m' <m\). Since the positive part of \(H_{(\mathcal {T},\mathcal {L})}\) is the lattice distance matrix of \(P_{\mathcal {T}}\), the symbols which do not divide \(p_{j'}\) represent the facets of \(P_{\mathcal {T}}\) which are lattice distance 0 to \(a_{j'}\). Since \(P_{\mathcal {T}}\) satisfies the conclusion of Lemma 5.1, the maximal cone associated with the vertex \(a_{j'}\) in \(\varSigma _{P_{\mathcal {T}}}\) has more 1-face (ray) generators than the one associated with \(a_{j}\) where j has length m. Thus, \(\varSigma _{P_{\mathcal {T}}}\) is not simplicial, contradiction. Moreover we obtain that the maximal cone associated with a vertex \(a_j\) is generated by the normal vectors associated with \(\bigcup _{l=1}^m S_l \backslash s_{i_l}\) for some \(s_{i_l} \in S_l\) and where \(\prod _{l=1}^m s_{i_l}\) divides \(p_j\). This implies that \(\dim (P_{\mathcal {T}})=|S_1|+\cdots +|S_m|-m\). Now suppose that all vertex representing root-to-leaf paths have the same length m. Then, the number of symbols which do not divide \(p_j\) is \(|S_1| + \cdots + |S_{m}| - m\) where j is a vertex representing root-to-leaf path. If this number is equal to \(\dim (P_{\mathcal {T}})\), then \(P_{\mathcal {T}}\) is simple. \(\square \)
Remark that the equality \(|S_1|+\cdots + |S_m| - m = \dim (P_{\mathcal {T}})\) holds for all models from Propositions 5.1 and 5.2.
Example 5.1
The multinomial staged tree \(\mathcal {T}_{(A)_4}\) in Fig. 5 for the trapezoidal pyramid, does not satisfy Definition 5.3 (1). However when \(b=1\), we can find such a balanced multinomial staged tree representation for this polytope, it is shown in Fig. 6 (left). This tree \(\mathcal {T}\) and \(\mathcal {T}_{(A)_4}\) represent the same model because their minimal Horn matrices are equal. When \(a=b=d=1\), the tree and its polytope are in Fig. 6 (centre) and (right). There are five vertex representing root-to-leaf paths namely 1, 3, 4, 5, and 6 and thus \(a_1, a_3, a_4,a_5\) and \(a_6\) are the vertices of the trapezoidal pyramid. In particular \(a_2 =\frac{1}{2} a_1 + \frac{1}{2} a_3.\) Hence, \(P_{\mathcal {T}}\) has property \((\star )\). Moreover, \(P_{\mathcal {T}}\) is not simple by Lemma 5.2, since not all root-to-leaf paths have the length 2.
Multinomial staged tree representation of the non-simple trapezoidal pyramid, \(b=1\)
For simple polytopes \(P_{\mathcal {T}}\) with property \((\star )\) we show that the stages coincide with the primitive collections of \(\varSigma _{P_{\mathcal {T}}}\).
Theorem 5.1
Let \(P_{\mathcal {T}} \subset \mathbb {R}^d\) be a simple polytope with property \((\star )\). Then, the primitive collections of the simplicial normal fan \(\varSigma _{P_{\mathcal {T}}}\) are represented by the stages \(S_1, \ldots , S_m\).
Proof
By Definition 5.3(1), the symbols of the stages represent the facets of \(P_{\mathcal {T}}\). Let now j be a vertex representing root-to-leaf path. Recall by the proof of Lemma 5.2, the maximal cone associated with \(a_j\) is generated by the normal vectors (1-faces) associated with \(\bigcup _{l=1}^m S_l \backslash s_{i_l}\) for some \(s_{i_l} \in S_l\) and where \(\prod _{l=1}^m s_{i_l}\) divides \(p_j\). Since any intersection of two cones in \(\varSigma _{P_{\mathcal {T}}}\) is also a cone in \(\varSigma _{P_{\mathcal {T}}}\), we obtain that \(\bigcup _{l=1}^m S_l \backslash S'_l\) for all \(S'_l \subseteq S_l\) with \(|S'_l| \ge 1\) is a cone of \(\varSigma _{P_{\mathcal {T}}}\). By Definition 2.6, since \(\varSigma _{P_{\mathcal {T}}}\) is simplicial, a primitive collection is a set of 1-faces which does not generate a cone itself but any proper subset does. This concludes that the partition \(S_1, \ldots . S_m\) are the primitive collections of \(\varSigma _{P_{\mathcal {T}}}\). \(\square \)
The following corollary gives an affirmative answer to Question 2.2.
Corollary 5.1
Let \(P_{\mathcal {T}} \subset \mathbb {R}^d\) be a simple polytope with property \((\star )\). Then, we have \(H_{(\mathcal {T},\mathcal {L})} = M_{{\mathscr {A}}, \varSigma _{P_{\mathcal {T}}}}\), i.e. the negative rows are given by the primitive collections of \(\varSigma _{P_{\mathcal {T}}}\).
Example 5.2
The multinomial staged trees \(\mathcal {T}_{b\varDelta _2}\) and \(\mathcal {T}_{a,b,d}\) satisfy Definition 5.3(1) for the simplex and trapezoid (\(a,b,d>0\)), respectively. That means the facets of the polytopes are in one-to-one correspondence with the symbols in the stages. Moreover \(P_{\mathcal {T}_{b\varDelta _2}}\) and \(P_{\mathcal {T}_{a,b,d}}\) are simple polytopes. Hence, by Theorem 5.1 we obtain that the primitive collections are given by the partition of the stages. For the simplex \(P_{\mathcal {T}_{b\varDelta _2}} \cong a\varDelta _{2}\) we have only one primitive collection \(\{s_0,s_1,s_2\}\). Similarly, for \(P_{\mathcal {T}_{a,b,d}}\cong T_{a,b,d}\) we have the partition of the stages as \(\{s_0,s_1\}\) and \(\{s_2,s_3\}\), which correspond exactly to the primitive collections obtained in Theorem 3.1.
Multinomial staged tree representation of the simple trapezoidal wedge with \(b=1\) considered in Example 5.3
Example 5.3
Let us consider the balanced multinomial staged tree representation, satisfying Definition 5.3, of the trapezoidal wedge from Table 1 (A) with \(b=1\) seen in Fig. 7. This tree representation encodes the same model as the tree \(\mathcal {T}_{(A)_3}\) in Fig. 5, because they have the same minimal Horn matrix. In particular we observe by Lemma 5.2 that \(P_{\mathcal {T}}\) is simple. By Theorem 5.1, the primitive collections are represented by the partition of the stages: \(\{n_2,n_3,n_5\} = \{s_0, s_1, s_2\}\) and \(\{n_1,n_4\}= \{s_3,s_4\}\). By Corollary 5.1 the negative part of the minimal Horn matrix \(a=b=d=a'=1\) (top), is explained by primitive collections. In Sect. 3.3.2, we saw that even for simple polytopes, the negative part of the Horn matrix is not always explained by the primitive collections.
Acknowledgements
Eliana Duarte was supported by the Deutsche Forschungsgemeinschaft DFG under grant 314838170, GRK 2297 MathCoRe, by the FCT grant 2020.01933.CEECIND, and partially supported by CMUP under the FCT grant UIDB/00144/2020. Computations using the software system Sagemath [19] and Macaulay2 [13] were crucial for the development of this paper. We thank Bernd Sturmfels for introducing us to each other and for encouraging us to work on this project.
Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
