The harmonic polytope

Abstract

We study the harmonic polytope, which arose in Ardila, Denham, and Huh’s work on the Lagrangian geometry of matroids. We describe its combinatorial structure, showing that it is a $(2n-2)$-dimensional polytope with $(n!)^2\left( 1+\frac{1}{2}+\cdots +\frac{1}{n}\right)$ vertices and $3^n-3$ facets. We also give a formula for its volume: it is a weighted sum of the degrees of the projective varieties of all the toric ideals of connected bipartite graphs with n edges; or equivalently, a weighted sum of the lattice point counts of all the corresponding trimmed generalized permutahedra.

1 Introduction

Motivated by the Lagrangian geometry of conormal varieties in classical algebraic geometry, Ardila, Denham, and Huh [4] introduced the conormal fan $\Sigma _{{\mathsf {M}}, {\mathsf {M}}^\perp }$ of a matroid ${\mathsf {M}}$—a Lagrangian analog of the better known Bergman fan $\Sigma _{\mathsf {M}}$ [6]. They used the conormal fan $\Sigma _{{\mathsf {M}}, {\mathsf {M}}^\perp }$ to give new geometric interpretations of the Chern-Schartz-MacPherson cycle of a matroid—introduced by López de Medrano et. al. [13]—and of the h-vectors of the broken circuit complex $BC({\mathsf {M}})$ and independence complex $I({\mathsf {M}})$ of ${\mathsf {M}}$. This geometric framework allowed them to prove that these vectors are log-concave, as conjectured by Brylawski and Dawson [11, 14] in the 1980s.

In their work, Ardila, Denham, and Huh encountered two polytopes associated to a positive integer n: the harmonic polytope $H_{n,n}$ and the bipermutohedron $\Pi _{n,n}$; the first is a Minkowski summand of the second. Their geometric origin is explained in Sect. 2. This paper studies the harmonic polytope $H_{n,n}$; its name derives from the fact that its number of vertices is $(n!)^2H_n$ where $H_n = 1 + \frac{1}{2} + \cdots + \frac{1}{n}$ is the nth harmonic sum. The harmonic polytope has nice vertex and inequality descriptions, shown in Propositions 3.5 and 3.7 . We also give a combinatorial formula for its f-vector; we note that giving such a description for an arbitrary polytope is $\#P$-hard. [15, 22]

Computing the volume of an arbitrary polytope is a very difficult task [7]. In principle, one could compute the volume of a given polytope by constructing a triangulation and adding the volumes of each of the maximal dimensional simplices. In practice, this is not a feasible approach: Dyer and Frieze showed that the problem of finding the volume of a polytope is $\#$P-hard [16]. Even among polytopes with well-understood face structures, few exact volume formulas are known.

Our main result is Theorem 1.1, which computes the volume of $H_{n,n}$. We use the combinatorial structure of the harmonic polytope $H_{n,n}$ to show that its volume is a weighted sum of the degrees of the toric ideals of all bipartite multigraphs on n edges; or equivalently, of the lattice point counts of all the corresponding trimmed generalized permutahedra.

Theorem 1.1

The normalized volume of the harmonic polytope is

$$\begin{aligned} \mathsf {Vol}(H_{n,n})= & {} \sum _{\Gamma } \frac{i(P_\Gamma ^-)}{(v(\Gamma )-2)!} \prod _{v\in V(\Gamma )}\mathsf {deg}(v)^{\mathsf {deg}(v)-2} \\= & {} \sum _{\Gamma } \frac{\mathsf {deg}(X_\Gamma )}{(v(\Gamma )-2)!} \prod _{v\in V(\Gamma )}\mathsf {deg}(v)^{\mathsf {deg}(v)-2}, \end{aligned}$$

summing over all connected bipartite multigraphs $\Gamma$ on edge set [n]. Here $i(P_\Gamma ^-)$ is the number of lattice points in the trimmed generalized permutahedron $P_\Gamma ^-$ of $\Gamma$, $X_\Gamma$ is the projective embedding of the toric variety of $\Gamma$ given by the toric ideal of $\Gamma$, $V(\Gamma )$ is the set of vertices of $\Gamma$, and $v(\Gamma ) := |V(\Gamma )|$.

To prove Theorem 1.1 we observe that the harmonic polytope can be expressed as a Minkowski sum of simplices, so its volume is a sum of the associated mixed volumes. Following an idea of Postnikov [25], each mixed volume equals the number of isolated solutions of a system of polynomial equations by Bernstein–Khovanskii–Kushnirenko’s theorem, and we can try to count those solutions. In Postnikov’s case this is easy because one obtains a system of linear equations, which has 0 or 1 solution. Our setting is much more subtle because our equations are not linear. To count their common solutions, we establish a connection with the theory of toric edge ideals [29, 31]. This connection allows us to express each mixed volume in terms of the degree of a toric ideal, the volume of an edge polytope, or the number of lattice points of a trimmed generalized permutahedron.

In order to get an approximation for the volume of the harmonic polytope, it is desirable to count the non-zero terms in the sum of Theorem 1.1. We show that the non-zero mixed volumes are in bijection with the pairs of forests on [n] whose union is connected. We count them in Proposition 5.1 by computing in the Möbius algebra of the partition lattice.

2 Motivation: the Lagrangian geometry of matroids

This section, which is logically independent from the rest of the paper, provides the geometric motivation for this project; it assumes some familiarity with the geometry of matroids. Our discussion overlaps with [4, Section 2.8]; for further details we refer the reader to [1, 2, 4].

The harmonic polytope and the bipermutahedron arose naturally in Ardila, Denham, and Huh’s construction [4] of the conormal fan of a matroid. They used the bipermutahedron to provide a combinatorial model for the Lagrangian geometry of matroids, and derive interesting combinatorial consequences. Our goal in this section is to explain that the harmonic polytope is the universal polytope that is contained in all such models.

2.1 Combinatorial Hodge theory and log-concavity for matroids

The Chow ring, the Bergman fan, and f-vectors The story begins with the proof by Huh [20], Huh–Katz [19], and Adiprasito–Huh–Katz [1] of a series of conjectures by Rota, Heron, Mason, and Welsh in the 1970s and 1980s. Their strongest result is that the f-vector $f_0, f_1 \ldots , f_{r-1}$ of the broken circuit complex of a matroid $\mathsf {M}$ is log-concave.

When $\mathsf {M}$ is realizable as a hyperplane arrangement over the complex numbers, De Concini and Procesi’s wonderful compactification of the arrangement complement is a smooth complex projective variety, whose Chow ring $A^*(\mathsf {M})$ satisfies the Kähler package. Feichtner and Yuzvinsky [17] gave an elegant combinatorial presentation for this Chow ring. There are natural classes $\alpha$ and $\beta$ in $A^*(\mathsf {M})$ whose intersection numbers deg$(\alpha ^k \beta ^{r-1-k})$ equal the f-vector above for $k=0, 1 \ldots , r-1$. The Hodge-Riemann relations then imply the desired log-concavity result.

When $\mathsf {M}$ is not realizable, there seems to be no algebro-geometric context for this proof, but there is a tropical substitute: Ardila and Klivans’s Bergman fan $\Sigma _{\mathsf {M}}$, which is a triangulation of the tropical linear space Trop $\mathsf {M}$ of $\mathsf {M}$. Its Chow ring $A^*(\mathsf {M})$ coincides with the Chow ring above in the realizable case. The approach above can be “tropicalized” to include all matroids, but there are significant new hurdles to overcome. The main technical result of Adiprasito–Huh–Katz [1] is that this combinatorial Chow ring $A^*(\mathsf {M})$ still satisfies the Kähler package for all $\mathsf {M}$, even in the absence of algebraic geometry. The main combinatorial result is that the intersection numbers deg$(\alpha ^k \beta ^{r-1-k})$ still equal the desired f-vector; this is an algebraic combinatorial computation in terms of the flags of flats of $\mathsf {M}$, which correspond to the cones of the Bergman fan $\Sigma _{\mathsf {M}}$.

The conormal Chow ring, the conormal fan, and h-vectors Huh [21] and Ardila–Denham–Huh [4] recently proved stronger conjectures from the 1980s by Brylawski and Dawson. The strongest is that the h-vector $h_0, h_1 \ldots , h_r$ of the broken circuit complex of a matroid $\mathsf {M}$ is log-concave.

When $\mathsf {M}$ is representable over a field of characteristic zero, Huh identified two classes $\gamma$ and $\delta$ in the Chow ring of Varchenko’s variety of critical points and proved that the intersection numbers deg$(\gamma ^k \delta ^{n-2-k})$ now give the desired h-vector, which is log-concave by the Hodge-Riemann relations.

When $\mathsf {M}$ is not realizable, the key tropical geometric object is the conormal fan $\Sigma _{{\mathsf {M}}, {\mathsf {M}}^\perp }$ of the matroid. Ardila–Denham–Huh [4] showed that the resulting Chow ring $A^*({\mathsf {M}},{\mathsf {M}}^\perp )$ still satisfies the Kähler package. Combinatorially, the proof that the degrees deg$(\gamma ^k \delta ^{n-2-k})$ still give the desired h-vector is now much more intricate. It involves giving a Lagrangian interpretation of the Chern-Schwartz-MacPherson classes of the matroid, and studying the combinatorics of the biflags of biflats of $\mathsf {M}$, which correspond to the cones of the conormal fan $\Sigma _{{\mathsf {M}},{\mathsf {M}}^\perp }$.

2.2 The conormal fan: an origin story

A central question in Ardila-Denham-Huh’s program was the following: How should one define the conormal fan $\Sigma =\Sigma _{{\mathsf {M}},{\mathsf {M}}^\perp }$ and the corresponding Chow ring $A^*({\mathsf {M}},{\mathsf {M}}^\perp )$ of a matroid $\mathsf {M}$? This is the question that led to the harmonic polytope and the bipermutahedron, as we now explain.

When ${\mathsf {M}}$ is the matroid of a subspace V of $\mathbb {C}^E$, the conormal fan $\Sigma _{{\mathsf {M}}, {\mathsf {M}}^\perp }$ is a tropical model of the projectivized conormal bundle of V. Since ${\mathsf {M}}^\perp$ is the matroid of the orthogonal complement of V, we expect the conormal fan to be supported on $\text {Trop}({\mathsf {M}}) \times \text {Trop}({\mathsf {M}}^\perp ) \subset {\mathsf {N}}_n \times {\mathsf {N}}_n$, where ${\mathsf {N}}_n = {\mathbb {R}}^n / {\mathbb {R}}$. A desirable fan structure $\Sigma$ on this support should have the following properties:

• 1. There are classes $\gamma$ and $\delta$ in its Chow ring whose intersection numbers give the desired h-vector.

• 2. The Chow ring is tractable for algebraic combinatorial computations, so we can prove 1.

• 3. The fan is a subfan of the normal fan of a polytope, so its ample cone is nonempty.

• 4. The fan is Lefschetz, so we can derive the desired log-concavity results.

Requirement 4. is resolved in [4] by showing that being Lefschetz only depends on the support of the fan – and $\text {Trop}({\mathsf {M}}) \times \text {Trop}({\mathsf {M}}^\perp )$ is the support of a Lefschetz fan $\Sigma _{{\mathsf {M}}} \times \Sigma _{{\mathsf {M}}^\perp }$ by [1] – and not on the fan structure that we choose. Thus we can focus on the first three.

Requirement 2. is stated imprecisely, but a very desirable initial property is that our fan $\Sigma$ is simplicial. In this case the Chow ring $A(\Sigma )$ of the toric variety $X(\Sigma )$ has an algebraic combinatorial presentation due to Brion [10], and an interpretation in terms of piecewise polynomial functions due to Billera [9]. These results make it possible to carry out intersection-theoretic computations in this Chow ring. Thus the first fan structure on $\text {Trop}({\mathsf {M}}) \times \text {Trop}({\mathsf {M}}^\perp )$ that we might try to use is the product of Bergman fans $\Sigma _{{\mathsf {M}}} \times \Sigma _{{\mathsf {M}}^\perp }$. It is simplicial, it does have a nice combinatorial structure, and it is a subfan of the normal fan of the product of permutohedra $\Pi _n \times \Pi _n$, addressing 2-4.

However, requirement 1. poses a problem. Relying on the geometry of the representable case, we expect the classes $\gamma$ and $\delta$ in the conormal Chow ring $A^*({\mathsf {M}}, {\mathsf {M}}^\perp )= A^*(\Sigma )$ should be the pullbacks of a piecewise linear function $\alpha$ on $N_E$ under the maps

$$\begin{aligned} \begin{array}{ccccc} \pi : \Sigma \longrightarrow \Sigma _{\mathsf {M}} &{} \qquad &{} \sigma : \Sigma \longrightarrow \Gamma _n \\ \pi (x,y) = x &{} \qquad &{} \sigma (x,y) = x+y \end{array} \end{aligned}$$

where $\Gamma _n$ is the reduced normal fan of the standard simplex and $\Sigma$ is our desired fan structure on $\text {Trop}({\mathsf {M}}) \times \text {Trop}({\mathsf {M}}^\perp )$. Here the piecewise linear function $\alpha$ can be regarded as a class in the Chow ring of the matroid $A^*(\mathsf {M})$ (where it is the class $\alpha$ of [1]) or in the Chow ring of $\Gamma _n$. If $\Sigma$ equals $\Sigma _{{\mathsf {M}}} \times \Sigma _{{\mathsf {M}}^\perp }$ or any refinement of it, the first map is a map of fans, and $\gamma$ is well defined. However, the second map is not a map of fans for $\Sigma = \Sigma _{{\mathsf {M}}} \times \Sigma _{{\mathsf {M}}^\perp }$. Thus the product fan structure will not serve our purposes; we need to subdivide it further. How might we do this?

At this point, it is instructive to return to the case of tropical linear spaces above. In that case, one wants a similarly convenient fan structure for the tropical linear space $\text {Trop}({\mathsf {M}})$. Fortunately, one can do this for all matroids on [n] at once, by intersecting $\text {Trop}({\mathsf {M}})$ with the permutohedral fan $\Sigma _n$. The result is the Bergman fan $\Sigma _{{\mathsf {M}}}$ of ${\mathsf {M}}$, and the intersection theoretic computations in $\text {Trop}({\mathsf {M}})$ become computations with flags of flats.

Similarly, we might try to find a suitable fan structure of $\text {Trop}({\mathsf {M}}) \times \text {Trop}({\mathsf {M}}^\perp )$ for all matroids ${\mathsf {M}}$ on [n] simultaneously, by intersecting them with an appropriate complete fan. There is a minimal candidate: the coarsest common refinement of the product of permutohedral fans $\Sigma _n \times \Sigma _n$ – which induces the fan structure $\Sigma _{{\mathsf {M}}} \times \Sigma _{{\mathsf {M}}^\perp }$ – and $\sigma ^{-1}(\Gamma _n)$ – the coarsest fan that guarantees that the class $\delta$ is well-defined. The resulting fan is the harmonic fan.

The harmonic fan is the reduced normal fan of a polytope, namely, the Minkowski sum

$$\begin{aligned} H_{n,n} := (\Pi _n \times \Pi _n) + D_n, \end{aligned}$$

of the product of two permutohedra $\Pi _n \times \Pi _n$ and the diagonal simplex $D_n = \mathsf {conv}\{{\mathsf {e}}_i + {\mathsf {f}}_i\}_{i \in E}$. Thus requirement 3. above is satisfied. The resulting polytope is the harmonic polytope.

Combinatorial models for the Lagrangian geometry of matroids The harmonic polytope has a drawback for our geometric purposes: it is not simple, so the resulting fan structure on $\text {Trop}({\mathsf {M}}) \times \text {Trop}({\mathsf {M}}^\perp )$ is not simplicial, posing numerous obstacles. Thus we wish to find a simple polytope that has the harmonic polytope $H_{n,n}$ as a Minkowski summand, and has simple enough combinatorial structure that we can carry out computations. Ardila–Denham–Huh propose the bipermutohedron $\Pi _{n,n}$ as a solution; the combinatorics of this polytope is studied in detail in [3]. Its faces are indexed by biflags of subsets of [n].

The conormal fan $\Sigma _{{\mathsf {M}},{\mathsf {M}}^\perp }$ is then defined as the intersection of $\text {Trop}({\mathsf {M}}) \times \text {Trop}({\mathsf {M}}^\perp )$ with the bipermutahedral fan $\Sigma _{n,n}$; its faces are indexed by the biflags of biflats of $\mathsf {M}$. The resulting intersection-theoretic computations in the Chow ring $A^*({\mathsf {M}},{\mathsf {M}}^\perp )$ require an intricate, interesting analysis of these biflags; this can be done using a tropical geometric approach [4, Sections 3,4] involving Chern-Schartz-MacPherson classes. There is also an algebraic combinatorial approach [5] involving an intricate analysis of the biflags of biflats of ordered matroids. Both of these approaches require significant new ideas and lead to new developments.

As far as we know, there is nothing canonical about the choice of the bipermutahedron $\Pi _{n,n}$ above. It is natural to wonder whether there are alternative, perhaps easier approaches: Are there other simple polytopes in whose normal fans we could carry out these Lagrangian geometric computations on matroids? On the other hand, the harmonic polytope $H_{n,n}$ is canonical: Every such simple polytope in ${\mathsf {N}}_n \times {\mathsf {N}}_n$ must contain the harmonic polytope as a summand.

For every such simple polytope P in ${\mathsf {N}}_n \times {\mathsf {N}}_n$ that we can find, we expect that the program above will produce a combinatorial model for the Lagrangian geometry of matroids on [n]. The building blocks of this model will be given by the face structure of the polytope P, and how it interacts with each matroid $\mathsf {M}$ on [n]. The resulting intersection theoretic computations will teach us about the Lagrangian combinatorics of matroids. This seems to be a direction of study worth pursuing further.

3 The harmonic polytope

Having motivated the study of the harmonic polytope, we now analyze it in detail. Let n be a positive integer and let $[n]:=\{1,\ldots , n\}$. Consider two copies of ${\mathbb {R}}^n$ with respective standard bases $\{{\mathsf {e}}_i \, : \, i \in [n]\}$ and $\{{\mathsf {f}}_i \, : \, i \in [n]\}$. For any subset S of [n], we write

$$\begin{aligned} \mathbf {e}_S=\sum _{i \in S} \mathbf {e}_i, \qquad \mathbf {f}_S=\sum _{i \in S} \mathbf {f}_i. \end{aligned}$$

We also consider the $(n-1)$-dimensional vector space ${\mathsf {N}}_n := \mathbb {R}^n/{\mathbb {R}}{\mathsf {e}}_{[n]}$.

The (inner) normal fan ${\mathcal {N}}(P)$ of a polytope $P \subset {\mathbb {R}}^n$ is a complete fan in the dual space $({\mathbb {R}}^n)^*$ whose cones are

$$\begin{aligned} {\mathcal {N}}(P)_Q := \{w \in ({\mathbb {R}}^n)^* \, : \, P_w \supseteq Q\} \end{aligned}$$

for each nonempty face Q of P, where $P_w = \{x \in P \, : \, w(x) = \min _{y \in P} w(y)\}$ is the w-minimal face of P. The face poset of the normal fan of P is isomorphic to the reverse of the face poset of P. The relative interior of a cone $\sigma$ is the interior of $\sigma$ inside its affine span. In particular, the relative interior of ${\mathcal {N}}(P)_Q$ is

$$\begin{aligned} {\mathcal {N}}(P)_Q^\circ := \{w \in ({\mathbb {R}}^n)^* \, : \, P_w = Q\}. \end{aligned}$$

The chambers of ${\mathcal {N}}(P)$ are the cones of maximal dimension.

The normal fan of the permutohedron

$$\begin{aligned} \Pi _n = \mathsf {conv}\Big \{(x_1,\ldots ,x_n)\ | \ x_1,\ldots ,x_n \text { is a permutation of } [n] \Big \} \subseteq \mathbb {R}^n \end{aligned}$$

is the permutohedral fan $\Sigma _n\subset {\mathsf {N}}_n$, also known as the braid fan or the type A Coxeter complex. It is the complete simplicial fan in ${\mathbb {R}}^n$ whose chambers are cut out by the n-dimensional braid arrangement, the real hyperplane arrangement in ${\mathbb {R}}^n$ consisting of the ${n \atopwithdelims ()2}$ hyperplanes

$$\begin{aligned} z_i = z_j, \ \ \text {for distinct elements } i \text { and } j \text { of } [n]. \end{aligned}$$

The face of the permutohedral fan containing a given point z in its relative interior is determined by the relative order of its homogeneous coordinates $(z_1,\ldots ,z_n)$.

Let $D_n$ be the $(n-1)$-dimensional simplex,

$$\begin{aligned} D_n := \, \mathsf {conv}\Big \{{\mathsf {e}}_i + {\mathsf {f}}_i \, : \, i \in [n] \Big \} \subseteq {\mathbb {R}}^n \times {\mathbb {R}}^n. \ \end{aligned}$$

The normal fan of the simplex $D_{n}$ is the simplicial fan $\Delta _{n,n}$ whose n chambers are the cones

$$\begin{aligned} \mathscr {C}_k = \Big \{(z, w) \in {\mathbb {R}}^n \times {\mathbb {R}}^n \, | \, \min _{i \in [n]} (z_i+w_i) = z_k+w_k\Big \}. \end{aligned}$$

Recall that the Minkowski sum and Minkowski difference of polytopes P and Q in ${\mathbb {R}}^d$ are

$$\begin{aligned} P+Q = \{p+q \, : \, p \in P, \, q \in Q\}, \qquad P-Q = \{r \in {\mathbb {R}}^d \, : \, r+Q \subseteq P\}. \end{aligned}$$

The following polytope is our main object of study.

Definition 3.1

The harmonic polytope is the Minkowski sum

$$\begin{aligned} H_{n,n} := D_n + (\Pi _n \times \Pi _n) \subset {\mathbb {R}}^n \times {\mathbb {R}}^n. \end{aligned}$$

The harmonic fan is its reduced normal fan $\mathcal {N}(H_{n,n})$ in ${\mathsf {N}}_n \times {\mathsf {N}}_n$.

Figure 1 shows the harmonic polytope $H_{2,2}$ and its reduced normal fan. The normal fan of a Minkowski sum of two polytopes is the coarsest common refinement of their normal fans, see e.g. [32, Proposition 7.12]. Therefore, the normal fan of $H_{n,n}$ is the coarsest common refinement of the normal fans of $D_n$ and $\Pi _n \times \Pi _n$. Its lineality space is ${\mathbb {R}}\{{\mathsf {e}}_{[n]}, {\mathsf {f}}_{[n]}\}$.

3.1 The face structure of the harmonic polytope

The cone of the harmonic fan containing a point $(z,w) \in {\mathsf {N}}_n \times {\mathsf {N}}_n$ is determined by:

• the set of indices i for which the minimum of $z_i + w_i$ is attained,

• the reverse¹ relative order of the $z_i$s, and

• the reverse relative order of the $w_i$s.

Our next task is to characterize the triples that arise in this way.

Recall that an ordered set partition of [n] is a sequence $\pi =E_1|\cdots |E_\ell$ such that $E_1 \cup \cdots \cup E_\ell = [n]$ and $E_i \cap E_j = \emptyset$ for all $i \ne j$. The length of $\pi$ is $\ell (\pi ) := \ell$. The ordered set partitions of [n] form a poset under adjacent refinement, where $\pi \le \pi '$ if every block of $\pi '$ is a union of a set of consecutive blocks of $\pi$. For example $14|3|26|8|57 \le 134 | 26 | 578$.

Definition 3.2

The poset of harmonic triples $HT_n$ is defined as follows:

• 1. A harmonic triple $\tau = (K; \pi _1, \pi _2)$ on [n] consists of a nonempty subset $K \subseteq [n]$ and two ordered set partitions $\pi _1$ and $\pi _2$ of [n] such that

  • (a) The restrictions $\pi _1|K$ and $\pi _2|K$ of $\pi _1$ and $\pi _2$ to K are opposite to each other, and

  • (b) If $j \notin K$ appears in the same or a later block than $k \in K$ in one of the set partitions $\pi _1$ and $\pi _2$, then j must appear in an earlier block than k in the other set partition.

• 2. The poset of harmonic triples $HT_n$ is defined by setting $(K; \pi _1, \pi _2) \le (K'; \pi '_1, \pi '_2)$ if and only if $K \subseteq K'$, $\pi _1$ is an adjacent refinement of $\pi '_1$, and $\pi _2$ is an adjacent refinement of $\pi '_2$.

• 3. A fine harmonic triple is a minimal element of the poset $HT_n$. A coarse harmonic triple is a maximal element of $HT_n - \{\widehat{1}\}$.

Notice that the maximum element $\widehat{1}$ of $HT_n$ is the triple ([n], [n], [n]). The fine harmonic triples are the minimal elements, for which K consists of a single element k, and $\pi _1$ and $\pi _2$ only have blocks of size 1 – and hence may be thought of as permutations in one-line notation.

Example 3.3

Consider the triple (3467, 45|8|2|1379|6, 6|1|59|237|8|4), were we omit the brackets and write the elements of K in bold for easier readability. The reader is invited to verify that this triple satisfies the required conditions to be harmonic. On the other hand, $j=1$ and $k=3$ do not satisfy condition (b) in the non-harmonic triple (3467, 45|8|2|1379|6, 6|5|237|89|14).

Fig. 1

The harmonic polytope $H_{2,2}$ in ${\mathbb {Z}}^2 \times {\mathbb {Z}}^2$ and its reduced normal fan. The faces correspond to the harmonic triples on [2]. The table lists the fine harmonic triples $(k; \pi _1, \pi _2)$ and the corresponding vertices of $H_{2,2}$

Proposition 3.4

The combinatorial structure of the harmonic fan $\mathcal {N}(H_{n,n})$ is as follows.

• 1. The cones of the harmonic fan are in bijection with the harmonic triples on [n].

• 2. The dimension of the cone labeled by $\tau = (K; \pi _1, \pi _2)$ is $\ell (\pi _1) + \ell (\pi _2) - \ell (\pi _1|K) - 1$.

• 3. Two cones $\sigma$ and $\sigma '$ of the harmonic fan satisfy $\sigma \supseteq \sigma '$ if and only if their harmonic triples satisfy $\tau \le \tau '$ in $HT_n$.

Proof

• 1. Given a cone $\sigma$ of the harmonic fan, we define the triple $\tau (\sigma )$ as follows. Let (z, w) be an interior point of $\sigma$. We let K be the set of indices k for which the minimum of $z_k + w_k$ is attained, $\pi _1$ be the partition encoding the reverse relative order of the $z_i$s, and $\pi _2$ be the reverse relative order of the $z_i$s, and $\pi _2$ be the reverse relative order of the $w_i$s. For example, we have for the following cone $\sigma$,

  $$\begin{aligned} z_k+w_k \text { is minimum for } k=3,4,6,7 \\ z_6< z_1=z_3=z_7=z_9< z_2< z_8< z_4=z_5\\ w_4< w_8< w_2=w_3=w_7<w_5=w_9<w_1<w_6 \end{aligned}$$

  that

  $$\begin{aligned} \tau (\sigma ) = (\mathbf {3467}, \mathbf {4}\text{5}|8|2|\text{1}\mathbf{37}\text{9}|\mathbf {6},\mathbf {6}|1|59|\text{2}\mathbf {37}|8|\mathbf {4}). \end{aligned}$$

  Since $z_k+w_k$ is constant for k in K, the relative order of the $z_k$s is exactly the opposite of the relative order of the $w_k$s, so (a) holds. Also, if $j \notin K$ appears in the same or a later block than $k \in K$ in, say the first set partition, then we have $z_k \ge z_j$. But then $z_k+w_k < z_j + w_j$ implies that $w_k < w_j$, so j must appear before k in the second set partition. Therefore (b) also holds. Conversely, suppose $\tau =(K;\pi _1, \pi _2)$ is a harmonic triple, and let us construct a point (z, w) whose associated triple is $\tau$. We begin by defining the values of $z_k$ and $w_k$ for $k \in K$. We let $z_k=a$ where k is in the ath block of $\pi _2|K$ and $w_k=b$ where k is in the bth block of $\pi _1|K$. Then the $z_k$s and $w_k$s are in the order specified by $\pi _1|K$ and $\pi _2|K$, respectively, and, since $\pi _1|K$ and $\pi _2|K$ are opposites of each other, $z_k+w_k=c$ where $\pi _1|K$ and $\pi _2|K$ have $c-1$ blocks. Now define the values of $z_j$ for $j \notin K$ as follows. If j is in the same block of $\pi _1$ as $k \in K$ set $z_j=z_k$. Define the remaining entries $z_j$ to have the order stipulated by $\pi _1$, while making each one of them very large – say, within a small $\epsilon >0$ of the first entry $z_k$ such that $z_k > z_j$, if there is one. For example, for the triple $\tau = (\mathbf {3467}, \mathbf {4}\text{5}|8|2|\text{1}\mathbf {37}\text{9}|\mathbf {6}, \mathbf {6}|1|59|\text{2}\mathbf {37}|8|\mathbf {4})$ of Example 3.3, we may set

  $$\begin{aligned}&z_{{\mathbf {6}}} = \mathbf {1}< z_1=z_{{\mathbf {3}}}=z_{{\mathbf {7}}}=z_9=\mathbf {2}< z_2=2.8< z_8 = 2.9< z_{{\mathbf {4}}}=z_5=\mathbf {3} \\&w_{{\mathbf {4}}} = \mathbf {1}< w_8=1.9< w_2 \\&\quad = w_{{\mathbf {3}}}= w_{{\mathbf {7}}}=\mathbf {2}< w_5 = w_9 = 2.8< w_1 = 2.9 < w_{{\mathbf {6}}} = \mathbf {3}. \end{aligned}$$

  By construction, the order of the $z_i$s (resp. the $w_i$s) is the opposite of the order dictated by $\pi _1$ (resp. $\pi _2$). Also $z_k+w_k=c$ is constant for $k \in K$. It remains to show that $z_j+w_j >c$ for $j \notin K$. Assume contrariwise that $z_j+w_j \le c$. Then for any $k \in K$ we must have $z_j \le z_k$ or $w_j \le w_k$. Assume it is the former, and choose $k \in K$ where $z_k$ is minimum such that $z_k \ge z_j$. By construction, we have $z_j > z_k-\epsilon$. Furthermore j comes after k in $\pi _1$, so it must come before k in $\pi _2$; by construction, we have $w_j > (w_k+1)-\epsilon$. Thus $z_j+w_j> c+1-2\epsilon > c$, a contradiction. We conclude that $\tau$ is the label of a cone of the harmonic fan containing (z, w), as desired.

• 2. The set of points $(z,w)\in {\mathsf {N}}_n \times {\mathsf {N}}_n$ that give rise to the ordered set partitions $\pi _1$ and $\pi _2$ have $(\ell (\pi _1)-1) + (\ell (\pi _2)-1)$ degrees of freedom. The condition that $z_k+w_k$ are equal for all $k \in K$ introduces $\ell (\pi _1|K)-1 = \ell (\pi _2|K)-1$ linear constraints.

• 3. To go up the face poset from the cone indexed by $(K; \pi _1, \pi _2)$, we need to turn some of the defining equalities into inequalities. The effect of this on the label is to remove elements from K and break a parts of $\pi _1$ and $\pi _2$ into adjacent parts. $\square$

Using Proposition 3.4, one may check that the harmonic fan is neither simple nor simplicial, already for $n=3$. We now give the vertex and inequality description of the harmonic polytope.

Proposition 3.5

The number of vertices of the harmonic polytope $H_{n,n}$ is

$$\begin{aligned} v(H_{n,n}) = (n!)^2 \left( 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} \right) . \end{aligned}$$

Proof

By Proposition 3.4 we need to count the fine harmonic triples $\tau = (K; \pi _1, \pi _2)$; these are the ones where $K = \{k\}$ and both $\pi _1$ and $\pi _2$ are permutations. To specify $\tau$, we first specify the element k. Out of the remaining $n-1$ elements, we choose which a of them precede k in $\pi _1$ and follow k in $\pi _2$, which b of them precede k in both $\pi _1$ and $\pi _2$, and which c of them follow k in $\pi _1$ and precede k in $\pi _2$. Finally we choose the order of the $a+b$ elements preceding k in $\pi _1$, the order of the c elements following k in $\pi _1$, the order of the $b+c$ elements preceding k in $\pi _2$, and the order of the a elements following k in $\pi _2$. It follows that

$$\begin{aligned} v(H_{n,n})= & {} n \sum _{a+b+c = n-1} {n-1 \atopwithdelims ()a,b,c} (a+b)! \, c! \, a! \, (b+c)! \\= & {} n! \sum _{a+b+c=n-1} \frac{(a+b)!(b+c)!}{b!} \\= & {} n! \,\sum _{a=0}^{n-1} \left( a!(n-1-a)! \sum _{b=0}^{n-1-a} {a+b \atopwithdelims ()a} \right) \\= & {} n! \, \sum _{a=0}^{n-1} \left( a!(n-1-a)! {n \atopwithdelims ()a+1} \right) \\= & {} (n!)^2 \, \sum _{a=0}^{n-1} \frac{1}{a+1}, \end{aligned}$$

as desired. $\square$

Let us give a concrete description of the vertices of $H_{n,n}$.

Proposition 3.6

The vertices of the harmonic polytope $H_{n,n}$ are

$$\begin{aligned} v_\tau = {\mathsf {e}}_k + {\mathsf {f}}_k + (\pi _1^{-1},0) + (0, \pi _2^{-1}) \end{aligned}$$

for the fine harmonic triples $\tau = (k; \pi _1, \pi _2)$ on [n], where $\pi ^{-1}$ denotes the inverse of the permutation $\pi$ in one-line notation.

Proof

Consider a point (z, w) in the interior of the chamber of the normal fan ${\mathcal {N}}(H_{n,n})$ corresponding to a fine harmonic triple $\tau = (k; \pi _1, \pi _2)$. The minimal vertex of $H_{n,n}$ in the direction (z, w) is

$$\begin{aligned} (H_{n,n})_{z,w}= & {} (D_n)_{(z,w)} + (\Pi _n \times 0)_{(z,w)} + (0 \times \Pi _n)_{(z,w)} \\= & {} ({\mathsf {e}}_k + {\mathsf {f}}_k) + (\pi _1^{-1},0) + (0, \pi _2^{-1}) \end{aligned}$$

as desired. $\square$

For example, Fig. 1 shows how the harmonic polytope $H_{2,2}$ sits in the lattice ${\mathbb {Z}}^2 \times {\mathbb {Z}}^2$. Its inner normal fan is the harmonic fan, which coincides with the bipermutohedral fan (only) for $n=2$; the orientation shown here matches the one in [4, Figure 4].

For a larger example, the vertex of the harmonic polytope $H_{5,5}$ corresponding to the fine harmonic triple $\tau = (4; 53412, 14352)$ on [5] is

$$\begin{aligned} v_{T}&= \begin{pmatrix} 0 &{} 0 &{} 0 &{} 1 &{} 0 \\ 0 &{} 0 &{} 0 &{} 1 &{} 0 \end{pmatrix} + \begin{pmatrix} 4 &{} 5 &{} 2 &{} 3 &{} 1 \\ 0 &{} 0 &{} 0 &{} 0 &{} 0 \end{pmatrix} + \begin{pmatrix} 0 &{} 0 &{} 0 &{} 0 &{} 0 \\ 1 &{} 5 &{} 3 &{} 2 &{} 4 \end{pmatrix}\\&= \begin{pmatrix} 4 &{} 5 &{} 2 &{} 4 &{} 1 \\ 1 &{} 5 &{} 3 &{} 3 &{} 4 \end{pmatrix} \end{aligned}$$

since $53412^{-1} = 45231$ and $14352^{-1} = 15324$.

Proposition 3.7

The number of facets of the harmonic polytope $H_{n,n}$ is $3^n-3$.

Proof

In light of Proposition 3.4 we need to enumerate the coarse harmonic triples; that is, those for which $\ell (\pi _1) + \ell (\pi _2) - \ell (\pi _1|K) - 1 = 1$. We consider three cases.

• (i) $\ell (\pi _1)=1$: In this case $\ell (\pi _1|K)=1$ so we must have $\ell (\pi _2)=2$; say $\pi _2 = S|T$. Then we have $\tau =(K;[n],S|T)$, and for this triple to be harmonic we must have $K=T$. Therefore $\tau = (T; [n],S|T)$. The corresponding ray of the harmonic fan is ${\mathsf {e}}_{[n]} + {\mathsf {f}}_T$.

• (ii) $\ell (\pi _2)=1$: Similarly we obtain $\tau = (T; S|T, [n])$. The corresponding ray of the harmonic fan is ${\mathsf {e}}_S + {\mathsf {f}}_{[n]}$.

• (iii) $\ell (\pi _1) >1$ and $\ell (\pi _2) > 1$: Since $(\ell (\pi _1) - \ell (\pi _1|K)) + (\ell (\pi _2) - 2) = 0$ and both summands are nonnegative, we must have $\ell (\pi _2)=2$ and $\ell (\pi _1) = \ell (\pi _1|K)$. Similarly $\ell (\pi _1)=2$ and $\ell (\pi _2) = \ell (\pi _2|K)$. Let us write

  $$\begin{aligned} \pi _1 = S|S', \qquad \pi _2 = T|T', \qquad \text {and} \qquad \pi _1|K = K_S|K_{S'}, \qquad \pi _2|K = K_T|K_{T'}. \end{aligned}$$

  Since $K_S|K_{S'} = K_{T'}|K_T$, an element $j \in S' - K_{S'}$ would contradict Definition 3.2.1(b), so we must have $S' = K_{S'} = K_T$. Similarly $T' = K_{T'} = K_S$. Then $K = K_S \cup K_{S'} = S' \cup T'$. Also $S' \cap T' = K_S \cap K_{S'} = \emptyset$, so $S \cup T = [n]$. Thus

  $$\begin{aligned} \tau = ([n]-(S \cap T); \, S|([n]-S), \, T|([n]-T)) \qquad \text { for } S \cup T = [n]. \end{aligned}$$

  The corresponding ray of the normal fan is ${\mathsf {e}}_S + {\mathsf {f}}_T$.

We conclude that the rays of the harmonic fan are the vectors ${\mathsf {e}}_S + {\mathsf {f}}_T$ where S and T are non-empty, they are not both equal to [n], and $S \cup T = [n]$. There are $3^n-3$ such vectors because we can choose freely, for each $i \in [n]$, whether (a) i is in S and not T, (b) i is in T and not S, or (c) i is in both S and T; but the three pairs $([n], \emptyset ), (\emptyset , [n])$ and ([n], [n]) are invalid. $\square$

As introduced in [4], a bisubset of [n] is a pair S|T of nonempty subsets of [n], not both equal to [n], such that $S \cup T = [n]$. The previous proof shows that they are in correspondence with the facets of $H_{n,n}$. More precisely, we have:

Proposition 3.8

The harmonic polytope $H_{n,n}$ is given by the following minimal inequality description:

$$\begin{aligned} \sum _{e \in [n]} x_e= & {} \frac{n(n+1)}{2} + 1, \\ \sum _{e \in [n]} y_e= & {} \frac{n(n+1)}{2} + 1, \\ \sum _{s \in S} x_s + \sum _{t \in T} y_t\ge & {} \frac{|S|(|S|+1) + |T|(|T|+1)}{2} + 1 \qquad \text {for each bisubset { S}|{ T} of [{ n}]}. \end{aligned}$$

Proof

The first two equations hold, and determine a codimension two subspace perpendicular to the lineality space ${\mathbb {R}}\{{\mathsf {e}}_{[n]}, {\mathsf {f}}_{[n]}\}$ of ${\mathcal {N}}(H_{n,n})$. The minimal inequality description is then determined by the rays ${\mathsf {e}}_S + {\mathsf {f}}_T$ for the bisubsets S|T. We have

$$\begin{aligned}&\min _{(x,y) \in H_{n,n}}({\mathsf {e}}_S+{\mathsf {f}}_T)(x,y)\\&\quad = \min _{(x,y) \in D_{n}}({\mathsf {e}}_S+{\mathsf {f}}_T)(x,y) + \min _{(x,y) \in \Pi _{n} \times 0}{\mathsf {e}}_S(x,0) + \min _{(x,y) \in 0 \times \Pi _{n}}{\mathsf {f}}_T(0,y) \\&\quad = 1 + (1+2+\cdots + |S|) + (1+2+\cdots +|T|), \end{aligned}$$

which implies the given description. $\square$

We now offer an alternative description of the faces of the harmonic polytope, which gives rise to a formula for the f-vector. A harmonic table ${\mathsf {T}}$ on [n] of size $\ell =: \ell ({\mathsf {T}})$ is a triangular table having $2\ell +1$ rows and $2\ell +1$ columns of lengths $2\ell +1, 2\ell -1, 2\ell -1, \ldots , 3, 3, 1, 1$, respectively, decorated with the following data:

• A labeling of the even columns with nonempty, pairwise disjoint subsets of [n].

• A labeling of the even rows with the same subsets, listed in the opposite order.

• A placement of each element of [n] not used as a row or column label in one box of the table.

We let $c_i({\mathsf {T}})$ and $r_i({\mathsf {T}})$ denote the number of elements in column $2i+1$ and row $2i+1$ of ${\mathsf {T}}$, respectively. Figure 2 shows a harmonic table of size 3 on [9], with $c_1({\mathsf {T}}) = 2$, $r_1({\mathsf {T}})=3$, $r_2({\mathsf {T}}) = 1$, and all other $c_i({\mathsf {T}})$ and $r_i({\mathsf {T}})$ equal to 0.

Fig. 2

A harmonic table of size 3 on [9]

Let F(m) be the $\mathsf {M}$th Fubini number (or ordered Bell number), which counts the ordered set partitions of [m]. Also recall that the Stirling number of the second kind S(m, p) counts the number of unordered set partitions of $\mathsf {M}$ into p parts.

Proposition 3.9

The number of faces of the harmonic polytope $H_{n,n}$ is

$$\begin{aligned} f(H_{n,n}) = \sum _{{\mathsf {T}}} \, \prod _{i=0}^{\ell ({\mathsf {T}})} \Big (F(c_i({\mathsf {T}})) F(r_i({\mathsf {T}})) \Big ) \end{aligned}$$

summing over all harmonic tables on [n]. The number of d-dimensional faces of $H_{n,n}$ is

$$\begin{aligned} f_d(H_{n,n}) = \sum _{{\mathsf {T}}} \, \sum _{\mathsf {a}, \mathsf {b}} \, \prod _{i=0}^{\ell ({\mathsf {T}})} \Big (S(c_i({\mathsf {T}}),a_i) \, a_i! \, S(r_i({\mathsf {T}}),b_i) \, b_i! \Big ) \end{aligned}$$

summing over all harmonic tables ${\mathsf {T}}$ on [n] and all sequences $\mathsf {a}=(a_0, a_1, \ldots , a_\ell )$ and $\mathsf {b} = (b_0, b_1, \ldots , b_\ell )$ with $\ell =\ell ({\mathsf {T}})$ and $\sum _i a_i + \sum _i b_i + \ell = 2n-d-1$.

Proof

A harmonic triple $T=(K; \pi _1, \pi _2)$ can be constructed in five steps, with the help of a harmonic table, as follows. This process is illustrated in Figure 2, which shows the harmonic table that gives rise to the harmonic triple $T=(\mathbf {3467}, \mathbf {4}\text{5}|8|2|\text{1}\mathbf {37}\text{9}|\mathbf {6}, \mathbf {6}|1|59|\text{2}\mathbf {37}|8|\mathbf {4})$ of Example 3.3.

• 1. Choose the subset K of [n].

• 2. Choose the ordered set partition $\pi _1|K =: K_1 |\cdots | K_\ell$. This automatically determines $\pi _2|K$, which is its reverse. Record this data on a triangular table ${\mathsf {T}}$ of size $\ell$, labeling the 2ith column from left to right and the 2ith row from bottom to top with the set $K_i$.

• 3. Choose, for each element $j \in J := [n]-K$, its position relative to $K_1, \ldots , K_\ell$ in the ordered set partition $\pi _1$, and its position relative to $K_1, \ldots , K_\ell$ in the ordered set partition $\pi _2$. Record this information in the table ${\mathsf {T}}$ as follows. If j is in the same block as $K_i$ in $\pi _1$ (resp. in $\pi _2$), put it in the column (resp. row) labeled by $K_i$ in ${\mathsf {T}}$. If j is between blocks $K_i$ and $K_{i+1}$ in $\pi _1$ (resp. in $\pi _2$), put it in the unlabeled column (rep. row) between the columns (resp. rows) labeled by $K_i$ and $K_{i+1}$ in ${\mathsf {T}}$. Notice that, by item 1(b) in the Definition 3.2 of a harmonic triple, all these numbers will land inside the triangular table.

• 4. Choose the relative order of the elements of $J = [n]-K$ in the ordered set partition $\pi _1$. To do this, it suffices to choose, for each i, the relative order of the elements of J that appear between blocks $K_i$ and $K_{i+1}$ of $\pi _1$ for each i. These are precisely the $c_i({\mathsf {T}})$ elements in column $2i+1$, and their order is given by an arbitrary ordered set partition of that size, so there are $F(c_1({\mathsf {T}})) \ldots F(c_\ell ({\mathsf {T}}))$ such choices.

• 5. Choose the relative order of the elements of $J = [n]-K$ in the ordered set partition $\pi _2$. As in step 4, there are $F(r_1({\mathsf {T}})) \ldots F(r_\ell ({\mathsf {T}}))$ such choices.

Each harmonic triple on [n] – and hence each face of the harmonic polytope $H_{n,n}$ – arises in a unique way from this procedure. This proves the first formula.

By Proposition 3.4.2, the d-dimensional faces of the harmonic polytope $H_{n,n}$ dimension d correspond to the harmonic triples $(\tau ; \pi _1, \pi _2)$ with $d = \ell (\pi ) + \ell (\pi _2) - \ell (\pi _1|K) - 1$. For the harmonic table ${\mathsf {T}}$ given by $(\tau ; \pi _1, \pi _2)$, let $a_i$ (resp. $b_i$) denote the length of the ordered set partition of the $c_i({\mathsf {T}})$ elements in column $2i+1$ (resp. the $r_i({\mathsf {T}})$ elements in column $2i+1$) has length $a_i$ (resp. $b_i$), for $i=1,\ldots ,\ell ({\mathsf {T}})$. Then $\ell (\pi _1) = \ell ({\mathsf {T}}) + \sum _i a_i$ and $\ell (\pi _2) = \ell ({\mathsf {T}}) + \sum _i b_i$, and $\ell (\pi _1|K) = \ell ({\mathsf {T}})$, so $d = \ell ({\mathsf {T}}) + \sum _i a_i + \sum _i b_i -1$. There are $S(c_i({\mathsf {T}}),a_i)\, a_i!$ (resp. $S(r_i({\mathsf {T}}),b_i)\, b_i!$) such ordered set partitions for each i, from which the result follows. $\square$

For fixed k and $\ell$, there are ${n \atopwithdelims ()k}$ choices for a set K of k elements, there are $\ell ! \, S(k,\ell )$ choices for an ordered set partition $K_1|\cdots |K_\ell$ of K of size $\ell$, and there are $(2\ell +1) + 2(2\ell -1) + \cdots + 2(3) + 2(1) = 2 \ell ^2 + 2 \ell + 1$ choices for where to place each element not in K in the harmonic table. Therefore the number of harmonic tables for [n] is

$$\begin{aligned} \sum _{k=1}^{n-1} \sum _{\ell = 1}^k {n \atopwithdelims ()k} S(k, \ell ) \, \ell ! \, (2 \ell ^2 + 2 \ell + 1)^{n-k}. \end{aligned}$$

Using Proposition 3.9 one can compute the f-vector of the first few harmonic polytopes:

$$\begin{aligned} f(H_{1,1})= & {} (1,1), \\ f(H_{2,2})= & {} (1,6,6,1), \\ f(H_{3,3})= & {} (1,66,144,102,24,1), \\ f(H_{4,4})= & {} (1,1200,4008,5124,3072,834,78,1). \end{aligned}$$

3.2 The harmonic polytope and the bipermutohedron

As stated in the introduction, the harmonic polytope is one of two polytopes that arose in Ardila, Denham, and Huh’s work on the Lagrangian geometry of matroids. The other one is the bipermutohedron. We now describe the combinatorial relationship between them. Only for this subsection, we assume familiarity with the construction of the bipermutohedral fan $\Sigma _{n,n}$ and the bipermutahedron $\Pi _{n,n}$ in [4, Section 2].

We have shown that the harmonic polytope has $3^n-3$ facets and $(n!)^2(1+\frac{1}{2}+ \cdots + \frac{1}{n})$ vertices. In turn, the bipermutohedron has $3^n-3$ facets and $(2n)!/2^n$ vertices. The harmonic polytope is a Minkowski summand of (a multiple of) the bipermutohedron, as shown by the following proposition, originally discovered in [4, Proposition 2.11]. We give an alternative proof that makes the combinatorial relationship between these objects more explicit.

Proposition 3.10

The harmonic fan is a coarsening of the bipermutohedral fan.

Proof

Suppose a point $(z,w) \in {\mathsf {N}}_n \times {\mathsf {N}}_n$ is in the interior of cone $\sigma _{{\mathsf {B}}}$ of the bipermutohedral fan $\Sigma _{n,n}$, corresponding to a bisequence ${\mathsf {B}}$. Then $z_k+w_k$ is minimized precisely for the set K of indices $k \in [n]$ that appear only once in ${\mathsf {B}}$. This places the point (z, w) in the chart $\mathscr {C}_k$ of the bipermutohedral fan for each $k \in K$. Fix one such k.

Now, as explained in [4, Proposition 2.9], the order of the first occurrences of each $i \in [n]$ in the bisequence ${\mathsf {B}}$ is determined by the reverse order of the numbers $Z_i = z_i - z_k$, which is the reverse order of the $z_i$s. Similarly, the order of the second occurrences of each $i \in [n]$ in the bisequence ${\mathsf {B}}$ is determined by the reverse order of the numbers $W_i = w_k-w_i$, which is the order of the $w_i$s.

We conclude that (z, w) is in the interior of the cone of the harmonic fan indexed by the harmonic triple $(K; \pi _1, \pi _2)$ where K is the set of elements of [n] appearing only once in ${\mathsf {B}}$, $\pi _1$ is the ordered set partition obtained from the order of the first occurrence of each i in ${\mathsf {B}}$, and $\pi _2$ is the ordered set partition obtained by reversing the order of the second occurrence of each i in ${\mathsf {B}}$. $\square$

For example, if (z, w) is in the interior of the cone of the bipermutohedral fan $\Sigma _{6,6}$ indexed by the bisequence ${\mathsf {B}}=34|2|356|1|247|6$, then (z, w) is in the interior of the cone of the harmonic fan ${\mathcal {N}}(H_{6,6})$ indexed by the harmonic triple $\tau =(\mathbf {157}; \, 34|2|\mathbf {5}\text{6}|\mathbf {1}|\mathbf {7}, \, 6|\text{24}\mathbf {7}|\mathbf {1}|\text{3}\mathbf {5})$.

4 The volume of $H_{n,n}$

The goal of this section is to compute the volume of the harmonic polytope. As stated in the introduction, computing the volume of an arbitrary polytope is a very difficult task; we need to use in an essential way the combinatorial structure of our polytope. Our computation relies on the theory of mixed volumes and the Bernstein-Khovanskii-Kushnirenko Theorem which relates these volumes to the enumeration of solutions of systems of polynomial equations. It also relies on the theory of toric edge ideals to enumerate those solutions. Before reviewing the basics of this theory, let us comment on the definition of volume used here.

Normalizing the volume Most of the polytopes that we study are not full-dimensional in their ambient space, and we need to define their volumes and mixed volumes carefully. Let P be a d-dimensional polytope on an affine d-plane $L \subset {\mathbb {Z}}^n$. Assume $L \cap {\mathbb {Z}}^n$ is a lattice translate of a d-dimensional lattice $\Lambda$. We call a lattice d-parallelotope in L primitive if its edges generate the lattice $\Lambda$; all primitive parallelotopes have the same volume. Then we define the normalized volume of a d-polytope P in L to be $\mathsf {Vol}(P) := \textsf {EVol}(P)/\textsf {EVol}(\square )$ for any primitive parallelotope $\square$ in L, where $\textsf {EVol}$ denotes Euclidean volume. By convention, the normalized volume of a point is 1. Throughout the paper, all volumes and mixed volumes are normalized in this way.

4.1 Mixed volumes and Bernstein–Khovanskii–Kushnirenko’s Theorem

Theorem 4.1

([24]) There is a unique function $\mathsf {MV}(Q_1, \ldots , Q_d)$ defined on d-tuples of polytopes in ${\mathbb {R}}^d$, called the mixed volume such that for any collection of polytopes $P_1, \ldots , P_m$ in ${\mathbb {R}}^d$ and any nonnegative real numbers $\lambda _1, \ldots , \lambda _m$, we have

$$\begin{aligned} \mathsf {Vol}(\lambda _1P_1+ \cdots + \lambda _m P_m) = \sum _{i_1, \ldots , i_d} \mathsf {MV}(P_{i_1}, \ldots , P_{i_d}) \lambda _{i_1} \cdots \lambda _{i_d}, \end{aligned}$$

(1)

summing over all ordered d-tuples $(i_1, \ldots , i_d)$ with $1 \le i_k \le m$ for $1\le k \le d$. Moreover, the function $\mathsf {MV}(Q_1, \ldots , Q_d)$ is symmetric; that is, $\mathsf {MV}(Q_1, \ldots , Q_d) = \mathsf {MV}(Q_{\sigma (1)}, \ldots , Q_{\sigma (d)})$ for any permutation $\sigma$ of [d].

Mixed volumes have the following algebraic interpretation.

Theorem 4.2

(Bernstein–Khovanskii–Kushnirenko Theorem) [8] Let $A_1,\ldots ,A_d\subset {\mathbb {Z}}^d$ be d finite sets of lattice points, and let $Q_i=\mathsf {conv}(A_i)$ for $i=1,\ldots ,d$. If the number of solutions in the torus $({\mathbb {C}}^*)^d$ to the system

$$\begin{aligned} {\left\{ \begin{array}{ll} \displaystyle \sum _{\alpha \in A_1} \lambda _{1,\alpha } x^\alpha =0,\\ \qquad \qquad \quad \,\,\, \vdots \\ \displaystyle \sum _{\alpha \in A_d} \lambda _{d,\alpha } x^\alpha =0 \end{array}\right. } \end{aligned}$$

is finite for a given choice of complex coefficients $\lambda _{i,\alpha }$, then that number is bounded above by $d! \,\mathsf {MV}(Q_1,\ldots ,Q_d)$. Moreover, if the coefficients $\lambda _{i,\alpha }$ are sufficiently generic, the number of solutions equals $d! \,\mathsf {MV}(Q_1,\ldots ,Q_d)$.

The BKK Theorem is most often used to count or bound the solutions to a system of polynomial equations by computing the corresponding mixed volume. As Postnikov showed in his computation of volumes of generalized permutahedra [25], it can also be used in the reverse direction. This will be our approach as well: we will compute mixed volumes by counting the solutions to the associated systems of polynomial equations. This is seldom possible. In Postnikov’s case it is easy because he obtains systems of linear equations, which have 0 or 1 solutions. In our case it is also possible, though new ideas are needed. Our systems of equations are not linear, but they are bilinear, and this allows us to express the resulting enumeration problems in terms of the combinatorics of toric ideals of graphs and the enumeration of lattice points in polytopes.

To apply this general discussion to the harmonic polytope, we begin by defining the segments

$$\begin{aligned} \Delta _{ij} := \, \mathsf {conv}\{{\mathsf {e}}_i ,{\mathsf {e}}_j \} \qquad \text { and }\qquad \Delta _{\bar{i}\bar{j}} := \, \mathsf {conv}\{{\mathsf {f}}_i ,{\mathsf {f}}_j \} \qquad \text { for } 1 \le i < j \le n. \end{aligned}$$

The permutohedron equals $\displaystyle \Pi _n = {\mathsf {e}}_{[n]} + \sum \nolimits _{i<j}\Delta _{ij}$ [25, Proposition 2.3] so the harmonic polytope equals

$$\begin{aligned} H_{n,n}= {\mathsf {e}}_{[n]} + {\mathsf {f}}_{[n]} + \sum _{i<j}\Delta _{ij}+\sum _{i<j}\Delta _{\bar{i}\bar{j}}+D_n \quad \subset \quad {\mathbb {R}}^n \times {\mathbb {R}}^n. \end{aligned}$$

(2)

The first two summands ${\mathsf {e}}_{[n]}$ and ${\mathsf {f}}_{[n]}$ simply introduce translations, so we focus on the remaining ones. Given graphs G and $G'$ on vertex set [n] with edge multisets $\{i_1j_1, \ldots , i_rj_r\}$ and $\{\bar{i}_1\bar{j}_1, \ldots , \bar{i}_s \bar{j}_s\}$, respectively, we define their mixed volume to be

$$\begin{aligned} \mathsf {MV}(G, G') := \mathsf {MV}(\Delta _{i_1j_1},\ldots ,\Delta _{i_rj_r},\Delta _{\bar{i}_1\bar{j}_1},\ldots ,\Delta _{\bar{i}_s\bar{j}_s},\underbrace{D_{n},\ldots ,D_{n}}_{k \text { times}}) \end{aligned}$$

(3)

where $k=2n-2-r-s$. We also let ${2n-2 \atopwithdelims ()G,G'; D_n}$ denote the number of distinct permutations of the sequence $(\Delta _{i_1j_1},\ldots ,\Delta _{i_rj_r}, \Delta _{\bar{i}_1\bar{j}_1}, \ldots , \Delta _{\bar{i}_s\bar{j}_s},D_{n},\ldots ,D_{n})$. Combining (1) with the fact that mixed volumes are symmetric, we obtain:

$$\begin{aligned} \mathsf {Vol}(H_{n,n})=\sum _{G, G'} \left( {\begin{array}{c}2n-2\\ G,G'; D_n\end{array}}\right) \mathsf {MV}(G, G'), \end{aligned}$$

(4)

summing over all pairs of graphs G and $G'$ on [n]. Therefore it remains to compute the mixed volumes $\mathsf {MV}(G, G')$.

Remark 4.3

The normalized volume $\mathsf {Vol}(H_{n,n})$ is equal to the Euclidean volume of the projection of $H_{n,n}$ onto ${\mathbb {Z}}^{\{2,\ldots ,n\}} \times {\mathbb {Z}}^{\{2,\ldots ,n\}}$. This projection of $H_{n,n}$ is equal to the Minkowski sum of the images under this projection of the polytopes appearing in (2). Thus $\mathsf {MV}(G, G')$ is the mixed volume of the projections of $\Delta _{i_1j_1},\ldots ,\Delta _{i_rj_r}, \Delta _{\bar{i}_1\bar{j}_1}, \ldots , \Delta _{\bar{i}_s\bar{j}_s}, D_n, \ldots , D_n$ onto ${\mathbb {Z}}^{\{2,\ldots ,n\}} \times {\mathbb {Z}}^{\{2,\ldots ,n\}}$.

The BKK Theorem then tells us that $(2n-2)! \, \mathsf {MV}(G, G')$ counts the solutions in $({\mathbb {C}}^*)^n \times ({\mathbb {C}}^*)^n$ to the following system of equations:

$$\begin{aligned} \mathcal {E}(G,G'): \quad {\left\{ \begin{array}{ll} x_{i} = \lambda _{ij}x_{j}, \text { for } ij\in E(G) \qquad \qquad &{}\nu _{11}x_{1}y_{1}+\cdots +\nu _{1n}x_{n}y_{n}=0 \\ y_{i} = \mu _{ij}y_{j}, \text { for } \bar{i}\bar{j}\in E(G') &{}\qquad \qquad \qquad \qquad \qquad \quad \vdots \\ x_1=y_1=1 &{}\nu _{k1}x_{1}y_{1}+\cdots +\nu _{kn}x_{n}y_{n}=0, \end{array}\right. }\nonumber \\ \end{aligned}$$

(5)

where G and $G'$ have r and s edges respectively, $k := 2n-2-r-s$, and the coefficients $\lambda _{ij}, \mu _{ij}, \nu _{ij}$ are chosen generically.

4.2 Mixed volumes, toric ideals, root polytopes, and trimmed generalized permutahedra

In this section we compute the mixed volumes (3) of the harmonic polytope. We begin by showing that most of them vanish.

Lemma 4.4

If G or $G'$ contains a cycle then the mixed volume $\mathsf {MV}(G, G') = 0$.

Proof

By Theorem 4.2, $(2n-2)! \, \mathsf {MV}(G, G')$ counts the solutions in $({\mathbb {C}}^*)^n \times ({\mathbb {C}}^*)^n$ to the system of equations $\mathcal {E}(G,G')$. Suppose that G contains the cycle

$$\begin{aligned} i_1\rightarrow i_2\rightarrow \cdots \rightarrow i_\ell \rightarrow i_1. \end{aligned}$$

for some vertices $i_1, \ldots , i_\ell \in [n]$. The equations of the corresponding k edges

$$\begin{aligned} x_{i_1} = \lambda _{i_1i_2}x_{i_2}\qquad \ldots \qquad x_{i_{k-1}} = \lambda _{i_{k-1}i_k}x_{i_k}\qquad x_{i_k} = \lambda _{i_ki_1}x_{i_1} \end{aligned}$$

imply that $x_{i_1} = (\lambda _{i_1i_2} \cdots \lambda _{i_{k-1}i_k} \lambda _{i_ki_1})x_{i_1}$. Since the $\lambda _{ij}$s are chosen generically, the only solution to this equation is $x_{i_1}=0$. It follows that the system of equations $\mathcal {E}(G,G')$ has no solutions in the torus $({\mathbb {C}}^*)^n \times ({\mathbb {C}}^*)^n$, and $\mathsf {MV}(G, G') = 0$. $\square$

Our next goal is to describe the non-zero mixed volumes $\mathsf {MV}(G, G')$. To accomplish it, we will require some additional constructions.

The bipartite graph and the root polytope Fix graphs G and $G'$ on [n]. Let $\mathcal {I}=\{I_1,\ldots ,I_p\}$ and $\mathcal {J}=\{J_1 , \ldots , J_q\}$ be the set partitions of [n] into connected components of G and $G'$, respectively. Let I(k) and J(k) denote the parts of $\mathcal {I}$ and $\mathcal {J}$ containing vertex k for $k \in [n]$. Define the bipartite graph $\Gamma = \Gamma _{\mathcal {I},\mathcal {J}}$ with vertex set $\mathcal {I}\cup \mathcal {J}$ and n edges I(k)J(k) for $1 \le k \le n$. This graph may have several edges connecting the same pair of vertices. We give the edge I(k)J(k) the label k. Notice that the label of a vertex in $\Gamma$ is just the set of labels of the edges containing it. Therefore we can remove the vertex labels, and simply think of $\Gamma$ as a bipartite multigraph on edge set [n].

The edge polytope of $\Gamma$ is

$$\begin{aligned} R_{\Gamma }:= & {} \mathsf {conv}\{{\mathsf {e}}_{I_a}+{\mathsf {f}}_{J_b} \, : \, I_a \in \mathcal {I}, \, J_b \in \mathcal {J}, \, I_a\cap J_b\ne \varnothing \} \\= & {} \mathsf {conv}\{{\mathsf {e}}_{I(1)} + {\mathsf {f}}_{J(1)}, \ldots , {\mathsf {e}}_{I(n)} + {\mathsf {f}}_{J(n)}\} \subset {\mathbb {R}}^p \times {\mathbb {R}}^q, \end{aligned}$$

writing ${\mathsf {e}}_{I(1)}, \ldots , {\mathsf {e}}_{I(p)}$ and ${\mathsf {f}}_{J(1)}, \ldots , {\mathsf {f}}_{J(p)}$ for the standard bases of ${\mathbb {R}}^p \cong {\mathbb {R}}^\mathcal {I}$ and ${\mathbb {R}}^q \cong {\mathbb {R}}^\mathcal {J}$. This polytope lives on the codimension 2 subspace cut out by the equations $x_1 + \cdots + x_p = y_1 + \cdots + y_q = 1$.

Example 4.5

Consider the following graphs

The partitions corresponding to these graphs are $\mathcal {I}=\{12,34,56\}$ and $\mathcal {J}=\{1456,23\}$, omitting brackets for easier readability. The associated bipartite multigraph is

and the corresponding edge polytope is

$$\begin{aligned} R_\Gamma = \mathsf {conv}({\mathsf {e}}_a + {\mathsf {f}}_A, \, {\mathsf {e}}_a + {\mathsf {f}}_B, \, {\mathsf {e}}_b + {\mathsf {f}}_B, \, {\mathsf {e}}_b + {\mathsf {f}}_A, \, {\mathsf {e}}_c + {\mathsf {f}}_A, \, {\mathsf {e}}_c + {\mathsf {f}}_A) \subset {\mathbb {R}}^{abc} \times {\mathbb {R}}^{AB}, \end{aligned}$$

writing $a=12, b=34, c=56$ and $A=1456, B=23$.

Lemma 4.6

The only lattice points of the edge polytope $R_{\Gamma }$ are its vertices.

Proof

The polytope $R_{\Gamma }$ is contained in the sphere S centered at the origin with radius $\sqrt{2}$, so it can only contain lattice points of norm 0, 1,  or $\sqrt{2}$. Since $R_{\Gamma }$ lies on the hyperplanes $\sum _i x_i = 1$ and $\sum _i y_i = 1$, it cannot contain a lattice point of norm 0 (the origin) or 1 (a point of the form $\pm {\mathsf {e}}_i$ or $\pm {\mathsf {f}}_i$). Therefore every lattice point in $R_{\Gamma }$ must be of the form ${\mathsf {e}}_i + {\mathsf {f}}_j$ for some $i, j \in [n]$. These points are all on the surface of the sphere S, so they are in convex position; therefore, if a point ${\mathsf {e}}_i+{\mathsf {f}}_j$ is in $R_{\Gamma }$, it must in fact be a vertex of $R_{\Gamma }$. The result follows. $\square$

A lattice polytope P is normal if for all positive integers k and all lattice points x in kP there exist lattice points $x_1, \ldots , x_k$ in P such that $x = x_1 + \cdots + x_k$. A lattice polytope P is very ample if the above property holds for all sufficiently large integers k. This is a favorable property algebro-geometrically, because if P is very ample then the lattice points of P provide a concrete projective embedding of the toric variety $X_P$ of P, as follows. Let $P\cap {\mathbb {Z}}^d=\{\mathsf {a}_1,\ldots , \mathsf {a}_s\} =:A$. The projective embedding of $X_P$ is the Zariski closure of the image of the map

$$\begin{aligned} ({\mathbb {C}}^*)^d\longrightarrow & {} {\mathbb {C}}\mathbb {P}^{s-1} \\ \mathbf {t}\longmapsto & {} ( \mathbf {t}^{\mathsf {a}_1},\ldots , \mathbf {t}^{\mathsf {a}_s}) \end{aligned}$$

and its defining ideal $I_A$ is the kernel of the homomorphism

$$\begin{aligned} \varphi : {\mathbb {C}}[x_1, \ldots , x_s]\longrightarrow & {} {\mathbb {C}}[t_1^{\pm 1}, \ldots , t_d^{\pm 1}] \\ x_i\longmapsto & {} \mathbf {t}^{\mathsf {a}_i}. \end{aligned}$$

The map above induces the map of lattices

$$\begin{aligned} {\widehat{\varphi }} : {\mathbb {Z}}^s\longrightarrow & {} {\mathbb {Z}}^d \\ {\mathsf {e}}_i\longmapsto & {} \mathsf {a}_i, \end{aligned}$$

where ${\mathsf {e}}_1,\ldots ,{\mathsf {e}}_s$ is the standard basis of ${\mathbb {Z}}^s$. The kernel of ${\varphi }$ is the toric ideal

$$\begin{aligned} I_A = \langle \mathbf {x}^{\mathsf {u}} - \mathbf {x}^{\mathsf {v}} \, : \, \mathsf {u}, \mathsf {v} \in \mathbb {N}^s, \, {\widehat{\varphi }}(\mathsf {u}) = {\widehat{\varphi }}(\mathsf {v}) \rangle \,\, \subset \,\, {\mathbb {C}}[x_1, \ldots , x_s]; \end{aligned}$$

see [12, §2.1 and §2.3].

Proposition 4.7

If $\Gamma$ is bipartite, the edge polytope $R_{\Gamma }$ is normal.

Proof

Let

$$\begin{aligned} C_{\Gamma } = \textsf {cone}(R_{\Gamma }) = \{\lambda \, q \, : \, q \in R_{\Gamma }, \lambda \ge 0\} \subset {\mathbb {R}}^n \times {\mathbb {R}}^n \end{aligned}$$

be the cone over the polytope $R_{\Gamma }$. Consider a lattice point x in $k \,R_{\Gamma }$. The cone $C_{\Gamma }$ is generated by the vertices of $R_{\Gamma }$, so x is a positive combination of them. By Caratheodory’s theorem, x can be expressed a positive combination of only e linearly independent vertices of $R_{\Gamma }$, say $v_1, \ldots , v_e$, for some $e \le \mathsf {dim}\, R_{\Gamma }$. But the vector configuration $\{{\mathsf {e}}_i + {\mathsf {f}}_j \, : \, 1 \le i, j \le n\}$ is unimodular, so $v_1, \ldots , v_e$ form a lattice basis for $\textsf {cone}(v_1, \ldots , v_e) \cap ({\mathbb {Z}}^n \times {\mathbb {Z}}^n)$. It follows that x is a positive integer combination of $v_1, \ldots , v_e \in R_{\Gamma }$. We conclude that $R_{\Gamma }$ is normal as desired. $\square$

The toric ideal, the toric variety, and the trimmed generalized permutahedra The graph $\Gamma = \Gamma _{\mathcal {I},\mathcal {J}}$ gives rise to a ring homomorphism

$$\begin{aligned} {\mathbb {R}}[z_e \, : e \text { edge of } \Gamma ]\longrightarrow & {} {\mathbb {R}}[y_v \, : v \text { vertex of } \Gamma ] \\ z_e\longmapsto & {} y_iy_j \quad \text { where edge } e \text { joins vertices } i \text { and } j \end{aligned}$$

The kernel of this homomorphism is called the toric ideal $I_\Gamma$ of $\Gamma$; it is a homogeneous ideal given by the cycles of even length in $\Gamma$:

$$\begin{aligned} I_\Gamma = \langle z_{e_1} z_{e_3} \cdots z_{e_{2k-1}} - z_{e_2} z_{e_4} \cdots z_{e_{2k}} \, : \, e_1e_2\cdots e_{2k} \text { is a cycle of } \Gamma \rangle ; \end{aligned}$$

see [18, Section 5.3]. This ideal is related to the edge polytope as follows.

Proposition 4.8

If $\Gamma$ is a bipartite graph, the projective variety of the toric ideal $I_{\Gamma }$ is an embedding of the toric variety $X_\Gamma$ of the edge polytope $R_\Gamma$.

Proof

This holds thanks to Lemmas 4.6 and 4.7 ; see [12, §2.3]. $\square$

The following polytopes will also play an important role. Consider the Minkowski sums

$$\begin{aligned} P_{\Gamma }:=\sum _{i=1}^p \Delta _{\mathsf {nbr}(I_i)}\subset {\mathbb {R}}^{q} \qquad \text {and} \qquad Q_{\Gamma }:=\sum _{j=1}^q \Delta _{\mathsf {nbr}(J_j)}\subset {\mathbb {R}}^{p} \end{aligned}$$

where $\Delta _{I}:=\mathsf {conv}\{{\mathsf {e}}_{i} \, : \, i\in I\}$, and where $\mathsf {nbr}(I_i) = \{j \in [q] \, : \, I_iJ_j \text { is an edge of } \Gamma \}$ and $\mathsf {nbr}(J_j) = \{i \in [p] \, : \, I_iJ_j \text { is an edge of } \Gamma \}$ denote the neighborhoods of $I_i$ and $J_j$ in $\Gamma$. Finally, define the trimmed generalized permutahedra of $\Gamma$ to be the Minkowski differences

$$\begin{aligned} P^{-}_{\Gamma }:=P_{\Gamma }-\Delta _{[q]}\subset {\mathbb {R}}^{q} \qquad \text {and} \qquad Q^{-}_{\Gamma }:=Q_{\Gamma }-\Delta _{[p]}\subset {\mathbb {R}}^{p} \end{aligned}$$

Example 4.9

We return to Example 4.5. The toric ideal of $\Gamma$ is

$$\begin{aligned} I_\Gamma = \langle z_1z_3-z_2z_4, z_5-z_6 \rangle \subset {\mathbb {C}}[z_1,z_2,z_3,z_4,z_5,z_6]. \end{aligned}$$

The generalized permutahedra associated to $\Gamma$ are

$$\begin{aligned} P_{\Gamma }=\Delta _{abc}+\Delta _{ab}\subset {\mathbb {R}}^{abc} \qquad \text {and} \qquad Q_{\Gamma }=2\Delta _{AB}+\Delta _{A} \subset {\mathbb {R}}^{AB} \end{aligned}$$

and the trimmed generalized permutahedra are

$$\begin{aligned} P^{-}_{\Gamma }=\Delta _{ab} \subset {\mathbb {R}}^{abc} \qquad \text {and} \qquad Q^{-}_{\Gamma }=\Delta _{AB}+\Delta _A \subset {\mathbb {R}}^{AB} . \end{aligned}$$

In general, the polytopes $P^{-}_{\Gamma }$ and $Q^{-}_{\Gamma }$ live in different dimensions and can be very different from each other. However, we will see that they always have the same number of lattice points.

Putting it all together We now have all the ingredients to describe the mixed volumes $\mathsf {MV}(G,G')$.

Proposition 4.10

Let G and $G'$ be acyclic graphs on [n] and $\Gamma$ be the corresponding bipartite graph, having p and q vertices on each side of the bipartition. The following numbers are equal:

• 1. The $(2n-2)$-dimensional mixed volume $\mathsf {MV}(G, G')$ multiplied by $(2n-2)!$.

• 2. The $(p+q-2)$-dimensional volume of the edge polytope $R_{\Gamma }$ multiplied by $(p+q-2)!$.

• 3. The number $i(P^{-}_{\Gamma })$ of lattice points in the trimmed generalized permutahedron $P^{-}_{\Gamma }$ in ${\mathbb {R}}^q$.

• 4. The number $i(Q^{-}_{\Gamma })$ of lattice points in the trimmed generalized permutahedron $Q^{-}_{\Gamma }$ in ${\mathbb {R}}^p$.

Furthermore, the numbers above are zero if and only if $\Gamma$ is disconnected. If $\Gamma$ is connected, the numbers above are equal to:

• 5. the degree of the projective embedding $V(I_\Gamma )$ of the toric variety $X_{\Gamma }$.

Recall that all volumes are normalized so the volume of a primitive parallelotope in any dimension is 1.

Proof

Let $\mathcal {E}(G,G')$ be the system of Eq. (5) associated to the mixed volume $\mathsf {MV}(G,G')$. By Theorem 4.2, the quantity in 1. counts the solutions in $({\mathbb {C}}^*)^n \times ({\mathbb {C}}^*)^n$ to $\mathcal {E}(G,G')$.

($1. = 2.$) The set of solutions to $\mathcal {E}(G,G')$ is the variety $V(I_{G,G'}+J)$, where

$$\begin{aligned} I_{G,G'}:= & {} \big \langle x_i-\lambda _{ij}x_j\, : \, i<j, \, ij\in E(G)\big \rangle + \big \langle y_i-\mu _{ij}y_j\, : \, i<j, \, ij\in E(G')\big \rangle \\ J:= & {} \big \langle \nu _{i1}x_{1}y_{1}+\cdots +\nu _{in}x_{n}y_{n} \, : \, 1 \le i \le k\big \rangle + \langle x_1-1, y_1-1 \rangle \end{aligned}$$

in ${\mathbb {C}}[x_1^\pm ,\ldots ,x_n^\pm ,y_1^\pm ,\ldots ,y_n^\pm ]$.

Consider the subspace $\mathcal {L}\subset \mathbb {C}^n \times \mathbb {C}^n$ given by

$$\mathcal {L}=\{(x_1,\ldots ,x_n,y_1,\ldots ,y_n)\, {:} \, x_{i} {=} \lambda _{ij}x_{j} \text { for } ij\in E(G)\,{,} y_{i} {=} \mu _{ij}y_{j} \text { for } ij\in E(G')\}$$

and the projection

$$\begin{aligned} {{\widetilde{\psi }}}: \mathcal {L}\longrightarrow & {} {\mathbb {C}}^p\times {\mathbb {C}}^q\\ (x_1,\ldots ,x_n,y_1,\ldots ,y_n)\longmapsto & {} (x_{\min I_1},\ldots ,x_{\min I_p},y_{\min J_1},\ldots ,y_{\min J_q}). \end{aligned}$$

Note that for $(x,y) \in \mathcal {L}$ if we have $x_{\min I_a}=0$ then $x_{i}=0$ for all $i\in I_a$, since $I_a$ is a connected component in G; the same holds for the ys. Therefore ${{\widetilde{\psi }}}$ is injective and, since $\mathsf {dim}(\mathcal {L})=p+q=\mathsf {dim}({\mathbb {C}}^p \times {\mathbb {C}}^q)$, it follows that ${\widetilde{\psi }}$ is an isomorphism of affine varieties. Moreover, $x_{\min I_a}=0$ if and only if $x_{i}=0$ for some $i\in I_a$; the same holds for the ys. This implies that the restriction of ${\widetilde{\psi }}$ to $\mathcal {L}\cap \big (({\mathbb {C}}^*)^n \times ({\mathbb {C}}^*)^n\big )$ is a morphism with image $({\mathbb {C}}^*)^p \times ({\mathbb {C}}^*)^q$. This morphism defines the following isomorphism between the coordinate rings of $\mathcal {L}\cap \big (({\mathbb {C}}^*)^n \times ({\mathbb {C}}^*)^n \big )$ and $({\mathbb {C}}^*)^p \times ({\mathbb {C}}^*)^q$:

$$\begin{aligned} \psi :{\mathbb {C}}[x_{I_1}^\pm ,\ldots ,x_{I_p}^\pm ,y_{J_1}^\pm ,\ldots ,y_{J_q}^\pm ]\longrightarrow & {} {\mathbb {C}}[x_1^\pm ,\ldots ,x_n^\pm ,y_1^\pm ,\ldots ,y_n^\pm ]/I_{G,G'}\\ x_{I_a}\longmapsto & {} \bar{x}_{\min I_a}\\ y_{J_b}\longmapsto & {} \bar{y}_{\min J_b}. \end{aligned}$$

Let $\overline{J}$ be the image of J in the quotient ${\mathbb {C}}[x_1^\pm ,\ldots ,x_n^\pm ,y_1^\pm ,\ldots ,y_n^\pm ]/I_{G,G'}$. By Noether’s isomorphism theorems we have

$$\begin{aligned}&\mathbb {C}[x_1^\pm ,\ldots ,x_n^\pm ,y_1^\pm ,\ldots ,y_n^\pm ]/(I_{G, G'}+J)\nonumber \\&\cong \left( \mathbb {C}[x_1^\pm ,\ldots ,x_n^\pm ,y_1^\pm ,\ldots ,y_n^\pm ]/ I_{G,G'} \right) \big / \big ( (I_{G,G'}+J)/I_{G,G'} \big )\nonumber \\&\cong \mathbb {C}[x_{I_1}^\pm ,\ldots ,x_{I_p}^\pm ,y_{J_1}^\pm ,\ldots ,y_{J_q}^\pm ] \big / \psi ^{-1}\big ((I_{G,G'} + J)/I_{G,G'} \big )\nonumber \\&=\mathbb {C}[x_{I_1}^\pm ,\ldots ,x_{I_p}^\pm ,y_{J_1}^\pm ,\ldots ,y_{J_q}^\pm ] / \psi ^{-1}(\overline{J}). \end{aligned}$$

(6)

Note that for $1 \le m \le n$ we have $\bar{x}_m = \lambda \, \bar{x}_{\min I(m)}$ and $\bar{y}_m = \mu \, \bar{y}_{\min J(m)}$ for nonzero scalars $\lambda$ and $\mu$. Thus we have, for $i\in [k]$,

$$\begin{aligned} \psi ^{-1}(\nu _{i1}\bar{x}_{1}\bar{y}_{1}+\cdots +\nu _{in}\bar{x}_{n}\bar{y}_{n})=\eta _{i1}x_{I(1)}y_{J(1)}+\cdots +\eta _{in}x_{I(n)}y_{J(n)} \end{aligned}$$

for some nonzero constants $\eta _{ij}$ that are generic if the $\nu _{ij}s$ are sufficiently generic. We conclude that $\psi ^{-1}(\overline{J})$ is generated by k generic equations whose Newton polytope is equal to $R_{\Gamma }$, together with $x_{I(1)} - 1$ and $y_{J(1)} - 1$. Recall that $k=2n-2-r-s$ where r and s are the numbers of edges of G and $G'$ respectively. Since these graphs are acyclic, $r=n-p$ and $s=n-q$, so $k=p+q-2$ equals the ambient dimension of the Newton polytope $R_{\Gamma }$.

By the BKK Theorem, the left-hand side of (6) is a variety consisting of $(2n-2)! \, \mathsf {MV}(G,G')$ points and the right hand side is a variety consisting of $(p+q-2)! \, \mathsf {Vol}_{p+q-2}(R_\Gamma )$ points. Therefore these two numbers are equal to each other.

($2. = 3. = 4.$) In the case that $\Gamma$ is connected, Postnikov [25, Theorem 12.2] showed that the $(p+q-2)$-dimensional volume of the edge polytope $R_\Gamma$ times $(p+q-2)!$ equals $i(P^-_\Gamma )$ and $i(Q^-_\Gamma )$.

Now assume $\Gamma$ is disconnected. Say $\Gamma = \Gamma _1 \cup \Gamma _2$ where $\Gamma _1$ and $\Gamma _2$ have vertex sets $\mathcal {I}_1 \cup \mathcal {J}_1$ and $\mathcal {I}_2 \cup \mathcal {J}_2$ for $\mathcal {I}_1 \cup \mathcal {I}_2 = \mathcal {I}$ and $\mathcal {J}_1 \cup \mathcal {J}_2 = \mathcal {J}$.

First observe that $R_\Gamma$ is the convex hull of the union of the edge polytopes $R_{\Gamma _1}$ and $R_{\Gamma _2}$. But these two polytopes have dimension at most $|\mathcal {I}_1| + |\mathcal {J}_1|-2$ and $|\mathcal {I}_2| + |\mathcal {J}_2|-2$, respectively, so $R_\Gamma$ has dimension at most $|\mathcal {I}| + |\mathcal {J}|-4 = p+q-4$, and hence its $(p+q-2)$-dimensional volume is 0.

On the other hand, by the definition of $P_{\Gamma }$,

$$\begin{aligned} P_{\Gamma } \subset \left\{ x\in {\mathbb {R}}^{q}\, : \, \sum _{j\in \mathcal {J}_1} x_j = |\mathcal {I}_1|, \sum _{j\in \mathcal {J}_2} x_j = |\mathcal {I}_2| \right\} . \end{aligned}$$

so $\mathsf {dim}(P_{\Gamma }) < q-1 = \mathsf {dim}(\Delta _{[q]})$. Therefore $P^-_{\Gamma } = P_{\Gamma } - \Delta _{[q]} = \varnothing$ and $i(P^-_\Gamma ) = 0$. The proof that $i(Q^{-}_{\Gamma })=0$ is analogous.

We have shown that (1.) = (2.) = (3.) = (4.). We have also shown that if $\Gamma$ is disconnected this number is 0. On the other hand, if $\Gamma$ is connected, then $\mathsf {dim}R_\Gamma = p+q-2$ by [18, Lemma 5.4], so its volume is nonzero.

($2. = 5.$ if $\Gamma$ is connected.) The $(p+q-2)$-dimensional volume of $R_\Gamma$ equals the degree of $V(I_\Gamma )$ by [30, Theorem 4.16]. $\square$

4.3 An illustrative example

Let us verify that $(2n-2)! \, \mathsf {MV}(G,G')=i(P^-_{\mathcal {I},\mathcal {J}})=i(Q^-_{\mathcal {I},\mathcal {J}})$ for the graphs in Example 4.5. This case is small enough that we can do it by hand, and it illustrates the need for the machinery of Sect. 4.2. Here $n=6$, so $10! \, \mathsf {MV}(G,G')$ is the number of solutions to the system $\mathcal {E}(G,G')$

$$\begin{aligned} \mathcal {E}(G,G'): \quad {\left\{ \begin{array}{ll} x_{1} = \lambda _{12} \, x_{2}, \qquad \qquad y_{1} = \mu _{14}\,y_{4}, \qquad \qquad \nu _{11}\, x_{1}y_{1}+\cdots +\nu _{16}\, x_{6}y_{6}=0, \\ x_{3} = \lambda _{34}\,x_{4}, \qquad \qquad y_{2} = \mu _{23}\,y_{3}, \qquad \qquad \nu _{21}\,x_{1}y_{1}+\cdots +\nu _{26}\,x_{6}y_{6}=0, \\ x_{5} = \lambda _{56}\,x_{6}, \qquad \qquad y_{4} = \mu _{45}\,y_{5}, \qquad \qquad \nu _{31}\,x_{1}y_{1}+\cdots +\nu _{36}\,x_{6}y_{6}=0,\\ \qquad \qquad \qquad \qquad \ \qquad \ \, y_{5} = \mu _{56}\,y_{6},\\ x_1=1, \qquad \qquad \ \quad \quad \ \, y_1=1. \\ \end{array}\right. } \end{aligned}$$

for a generic choice of coefficients. The first two columns of $\mathcal {E}(G,G')$ may be rewritten as

$$\begin{aligned}&1 = X_{12} := x_1 = \lambda _{12} \, x_2, \quad X_{34}: = x_3 = \lambda _{34} \, x_4, \qquad X_{56}: = x_5 = \lambda _{56}x_6\\&1 = Y_{1456} := y_1 = \mu _{14} \,y_4 \\&\quad = \mu _{14}\mu _{45} \, y_5, = \mu _{14}\mu _{45}\mu _{56} \, y_6, \quad Y_{23} := y_2 = \mu _{23} \, y_3, \quad Y_6:=y_6, \end{aligned}$$

so $\mathcal {E}(G,G')$ reduces to the following system of equations:

$$\begin{aligned} \mathcal {H}_{\mathcal {I},\mathcal {J}}: \quad {\left\{ \begin{array}{ll} \eta _{11} \,X_{12}Y_{1456}+\eta _{12} \,X_{12}Y_{23}+\eta _{13} \,X_{34}Y_{23}+\eta _{14} \,X_{34}Y_{1456}+\eta _{15} \,X_{56}Y_{1456}+\eta _{16} \,X_{56}Y_{1456}=0,\\ \eta _{21} \,X_{12}Y_{1456}+\eta _{22} \,X_{12}Y_{23}+\eta _{23} \,X_{34}Y_{23}+\eta _{24} \,X_{34}Y_{1456}+\eta _{25} \,X_{56}Y_{1456}+\eta _{26} \,X_{56}Y_{1456}=0,\\ \eta _{31} \,X_{12}Y_{1456}+\eta _{32} \,X_{12}Y_{23}+\eta _{33} \,X_{34}Y_{23}+\eta _{34} \,X_{34}Y_{1456}+\eta _{35} \,X_{56}Y_{1456}+\eta _{36} \,X_{56}Y_{1456}=0,\\ X_{12} = Y_{145} = 1, \end{array}\right. } \end{aligned}$$

where each coefficient $\eta _{ij}$ is obtained by multiplying $\nu _{ij}$ with the $\lambda$s (or their inverses) along a path from i to $\min I(i)$ in G and the $\mu$s (or their inverses) along a path from j to $\min J(j)$ in $G'$. These coefficients are generic if the original $\lambda$s, $\mu$s, and $\nu$s are sufficiently generic. This reduction of $\mathcal {E}(G,G')$ to $\mathcal {H}_{\mathcal {I},\mathcal {J}}$ is central to the proof of (1. $\Longleftrightarrow$ 2.) in Proposition 4.10.

If we write

$$\begin{aligned}&z_1 = X_{12}Y_{1456} = 1, \quad z_2 = X_{12}Y_{23}, \quad z_3 = X_{34}Y_{23}, \quad z_4 = X_{34}Y_{1456}, \\&\qquad \quad z_5 = X_{56}Y_{1456}, \quad z_6 = X_{56}Y_{1456} \end{aligned}$$

we get a generic system of 3 equations in 5 unknowns $z_2, \ldots , z_6$. Solving this system, we obtain an expression for each of $z_2, \ldots , z_4$ as a linear function of $z_5$ and $z_6$. Now, the $z_i$s satisfy two equations

$$\begin{aligned} z_1z_3=z_2z_4, \qquad z_5=z_6 \end{aligned}$$

coming from the two even cycles formed by edges 1, 2, 3, 4 and edges 5, 6 in $\Gamma$, respectively. Thus $z_2, z_3$ and $z_4$ can be expressed linearly in terms of $z_6$, and the equation $z_1z_3=z_2z_4$ turns into a quadratic equation satisfied by $z_6$, which has 2 solutions. Reversing the steps of our computation, we obtain 2 solutions to the original system. We conclude that $10! \, \mathsf {MV}(G,G') = 2$. This agrees with the fact that $P^{-}_{\Gamma }=\Delta _{ab} \subset {\mathbb {R}}^{abc}$ and $Q^{-}_{\Gamma }=\Delta _{AB}+\Delta _A \subset {\mathbb {R}}^{AB}$ each contain two lattice points.

The procedure above works for general acyclic graphs G and $G'$ such that $\Gamma$ is connected; the relations among the $z_i$s are precisely given by the toric ideal $I_\Gamma$. The last step of the computation cannot be done by hand in general; instead, one needs to know the degree of $I_\Gamma$. We find it by computing the number of lattice points in $P^{-}_{\mathcal {I},\mathcal {J}}$ or in $Q^{-}_{\mathcal {I},\mathcal {J}}$ – whichever is easier.

4.4 The volume

We are finally ready to prove Theorem 1.1.

Theorem 1.1

The volume of the harmonic polytope is

$$\begin{aligned} \mathsf {Vol}(H_{n,n})= & {} \sum _{\Gamma } \frac{i(P_\Gamma ^-)}{(v(\Gamma )-2)!} \prod _{v\in V(\Gamma )}\mathsf {deg}(v)^{\mathsf {deg}(v)-2} \\= & {} \sum _{\Gamma } \frac{\mathsf {deg}(X_\Gamma )}{(v(\Gamma )-2)!} \prod _{v\in V(\Gamma )}\mathsf {deg}(v)^{\mathsf {deg}(v)-2}, \end{aligned}$$

summing over all connected bipartite multigraphs $\Gamma$ on edge set [n]. Here $i(P_\Gamma ^-)$ is the number of lattice points in the trimmed generalized permutahedron $P_\Gamma ^-$ of $\Gamma$, $X_\Gamma$ is the projective embedding of the toric variety of $\Gamma$ given by the toric ideal of $\Gamma$, $V(\Gamma )$ is the set of vertices of $\Gamma$, and $v(\Gamma ) := |V(\Gamma )|$.

Proof

We use the notation of Sects. 4.1 and 4.2. By (4) and Lemma 4.4 we have that

$$\begin{aligned} \mathsf {Vol}(H_{n,n})&= \sum _{\begin{array}{c} G, G'\\ \text {acyclic} \end{array}} \left( {\begin{array}{c}2n-2\\ G,G'; D_n\end{array}}\right) \mathsf {MV}(G,G')\\&= \sum _{\begin{array}{c} G, G'\\ \text {acyclic} \end{array}} \frac{(2n-2)!}{k!} \mathsf {MV}(G,G'), \end{aligned}$$

since the graphs G and $G'$ have no repeated edges. Write $\Gamma$ for the bipartite graph associated to G and $G'$, abusing notation. Applying Lemma 4.10, and noting that $v(\Gamma )-2 = p+q-2 = k$, it follows that

$$\begin{aligned} \mathsf {Vol}(H_{n,n})&= \sum _{\begin{array}{c} G, G'\\ \text {acyclic} \end{array}} \mathsf {Vol}_{v(\Gamma )-2}(R_\Gamma ) \\&= \sum _{\begin{array}{c} (G,G')\ \text {acyclic}\\ \text {s.t. } \Gamma \text { connected} \end{array}} \frac{i(P^{-}_{\Gamma })}{(v(\Gamma )-2)!}. \end{aligned}$$

Since the summands on the right only depend on the partitions $\mathcal {I},\mathcal {J}$ associated to $G,G'$ we can combine the terms in as follows:

$$\begin{aligned} \mathsf {Vol}(H_{n,n})&= \sum _{\Gamma \text { connected}} \frac{i(P^{-}_{\Gamma })}{(v(\Gamma )-2)!} \cdot AC(\Gamma ), \end{aligned}$$

where $AC(\Gamma )$ denotes the number of acyclic graphs $G,G'$ whose bipartite graph is $\Gamma$. Now, the edges of the bipartite graph $\Gamma$ determine the labels $\mathcal {I}= \{I_1 , \cdots , I_p\}$ and $\mathcal {J}= \{J_1 , \cdots , J_q\}$ of the vertices of $\Gamma$; we need these to be the partitions of [n] into the connected components of G and $G'$, respectively.

We specify an acyclic graph G (resp. $G'$) with components $\mathcal {I}$ (resp. $\mathcal {J}$) by specifying, for each $I\in \mathcal {I}$ (resp. $J\in \mathcal {J}$), a tree with |I| (resp. |J|) vertices. There are $|I|^{|I|-2}$ (resp. $|J|^{|J|-2}$) such trees. By definition of $\Gamma _{\mathcal {I},\mathcal {J}}$, $\mathsf {deg}(I)=|I|$ for any $I\in \mathcal {I}$ (and similarly for any $J\in \mathcal {J}$). We thus conclude that

$$\begin{aligned} \mathsf {Vol}(H_{n,n})= & {} \sum _{\Gamma \text { connected}} \frac{\mathsf {deg}(X_\Gamma )}{(|V(\Gamma )|-2)!} \prod _{v\in V(\Gamma )}\mathsf {deg}(v)^{\mathsf {deg}(v)-2}. \end{aligned}$$

as desired. $\square$

Using Theorem 1.1 one can readily compute the volumes of the first few harmonic polytopes:

$$\begin{aligned} \mathsf {Vol}(H_{1,1}) = 1, \quad \mathsf {Vol}(H_{2,2}) = 3, \quad \mathsf {Vol}(H_{3,3}) = 33, \quad \mathsf {Vol}(H_{4,4}) = 2848/3. \end{aligned}$$

5 The number of non-zero mixed volumes

In this section we compute the number of non-zero mixed volumes of the harmonic polytope, in its Minkowski sum decomposition (2). This is the number of summands that contribute to the volume of the harmonic polytope $H_{n,n}$ in (1). We do so with the help of the Möbius algebra of the partition lattice, which is denoted $\Pi _n$.²

If $\pi = \{B_1, \ldots , B_k\}$ is a set partition of [n], we let $\ell (\pi ): = k$ be the number of parts of $\pi$, and

$$\begin{aligned} t(\pi ) := |B_1|^{|B_1|-2} \cdot \cdots \cdot |B_k|^{|B_k|-2}. \end{aligned}$$

Let $\Pi _n$ be the lattice of set partitions of [n] ordered by refinement, so $\sigma \le \tau$ if every block of $\tau$ is a union of blocks of $\sigma$.

Proposition 5.1

The harmonic polytope $H_{n,n} ={\mathsf {e}}_{[n]} + {\mathsf {f}}_{[n]} + \sum _{i<j} \Delta _{ij} + \sum _{i<j} \Delta _{\bar{i}\bar{j}} + D_n$ has

$$\begin{aligned} a_n:= & {} \text {number of pairs of forests } (F_1, F_2) \text { on } [n] \text { such that } F_1 \cup F_2 \text { is connected} \\= & {} \sum _{\sigma \in \Pi _n} (-1)^{\ell (\sigma )} (\ell (\sigma )-1)! \Big (\sum _{\tau \le \sigma } t(\tau )\Big )^2 \end{aligned}$$

non-zero mixed volumes.

Proof

A non-zero mixed volume cannot involve either of the summands ${\mathsf {e}}_{[n]}$ or ${\mathsf {f}}_{[n]}$, since the corresponding equations $\lambda \, x_1 \cdots x_n = 0$ and $\mu \, y_1 \cdots y_n = 0$ have no solutions on the torus for $\lambda$ and $\mu$ generic. Thus we focus on the mixed volumes $\mathsf {MV}(G,G')$.

By Lemma 4.4 and Proposition 4.10, we have that $\mathsf {MV}(G,G')\ne 0$ if and only if $G,G'$ are forests and the associated bipartite graph $\Gamma = \Gamma _{\mathcal {I},\mathcal {J}}$ is connected. Thus to prove the first statement we will show that $G\cup G'$ is connected if and only if $\Gamma$ is connected.

Suppose that $G\cup G'$ is connected. A path

$$\begin{aligned} i_1\rightarrow i_2\rightarrow \ldots \rightarrow i_\ell \end{aligned}$$

in $G\cup G'$ gives rise to a path in $\Gamma$ as follows. For $j=1,\ldots , \ell$, replace the edge $i_j\rightarrow i_{j+1}$ in $G \cup G'$ with the edge $J(i_j)\rightarrow I(i_j)= I(i_{j+1})$ if $i_j i_{j+1}\in E(G)$, and with $I(i_j)\rightarrow J(i_j)= J(i_{j+1})$ in $\Gamma$ if $i_j i_{j+1}\in E(G')$ Note that the resulting path can easily be modified into a path starting at $I(i_1)$ or $J(i_1)$ by adding or removing the edge $I(i_1)J(i_1)$; a similar modification works for $I(i_\ell )$ or $J(i_\ell )$. Now, to find a path between any two vertices of $\Gamma$, pick an element of each vertex, construct a path between these elements in $G\cup G'$, and use the procedure above to obtain a path between the desired vertices in $\Gamma$.

Conversely, suppose that $\Gamma$ is connected and consider any two vertices $i, i'$ of $G\cup G'$. Consider a path

$$\begin{aligned} P: \qquad I(i_1)\rightarrow J(i_1)=J(i_2)\rightarrow I(i_2)=I(i_3)\rightarrow \ldots \rightarrow J(i_{\ell -1})=J(i_\ell ) \qquad \text { in } \Gamma , \end{aligned}$$

where $i_1=i$ and $i_\ell =i'$. For each $1 \le j \le \ell -1$, we have either $I(i_j) = I(i_{j+1})$ or $J(i_j) = J(i_{j+1})$; since these are connected components of G or $G'$, we can find a path in either G or $G'$ from $i_j$ to $i_{j+1}$. We are then able to construct a path in $G\cup G'$ from i to $i'$ by replacing each edge of the path P in $\Gamma$ with a path from $i_j$ to $i_{j+1}$ in $G \cup G'$. This concludes the proof of the first equation.

Now, to choose a pair of forests $(F_1, F_2)$ on [n] such that $F_1 \cup F_2$ is connected, we first choose the set partitions $\pi _1 := \pi (F_1)$ and $\pi _2 = \pi (F_2)$, where $\pi (F)$ denotes the partition of [n] given by the connected components of F. Notice that $F_1 \cup F_2$ is connected if and only if $\pi _1 \vee \pi _2 = \widehat{1}$ in the partition lattice. Having chosen the partitions $\pi _1$ and $\pi _2$, it simply remains to choose the forests $F_1$ and $F_2$ that give rise to them; there are $t(\pi _1)$ and $t(\pi _2)$ choices for those forests, respectively. It follows that

$$\begin{aligned} a_n = \sum _{\begin{array}{c} \pi _1, \pi _2 \in \Pi _n \\ \pi _1 \vee \pi _2 = \widehat{1} \end{array}} t(\pi _1) t(\pi _2). \end{aligned}$$

Now we compute in the Möbius algebra $A(\Pi _n)$ of $\Pi _n$; this is the real vector space with basis $\Pi _n$ equipped with the bilinear multiplication given by the join of the lattice; in symbols,

$$\begin{aligned} A(\Pi _n) := {\mathbb {R}}\, \Pi _n \, \qquad \text {where} \qquad \sigma \cdot \tau := \sigma \vee \tau . \end{aligned}$$

It follows from the definitions that

$$\begin{aligned} a_n = [\widehat{1}] \, T^2 \qquad \text { for } \qquad T:= \sum _{\pi \in \Pi _n} t(\pi ) \pi , \end{aligned}$$

(7)

where $[\pi ] \alpha$ denotes the coefficient of a set partition $\pi \in \Pi _n$ in an element $\alpha \in A(\Pi _n)$, when expressed in the standard basis.

As explained in [26, Section 3.9], it is useful to define the following elements of the Möbius algebra $A(\Pi _n)$:

$$\begin{aligned} \delta _{\tau } := \sum _{\sigma \ge \tau } \mu (\tau , \sigma ) \sigma \qquad \text { for } \tau \in \Pi _n. \end{aligned}$$

These elements form a basis for $A(\Pi _n)$ because Möbius inversion tells us that

$$\begin{aligned} \tau = \sum _{\sigma \ge \tau } \delta _\sigma , \qquad \text { for } \tau \in \Pi _n. \end{aligned}$$

Furthermore, they are pairwise orthogonal idempotents:

$$\begin{aligned} \delta _\sigma \delta _\tau = {\left\{ \begin{array}{ll} \delta _\sigma &{} \text { if } \sigma = \tau , \\ 0 &{} \text {otherwise}, \end{array}\right. } \end{aligned}$$

which makes them very useful for computations in $A(\Pi _n)$. We compute

$$\begin{aligned} T= & {} \sum _{\tau \in \Pi _n} \Big ( t(\tau ) \sum _{\sigma \ge \tau } \delta _\sigma \Big )\\= & {} \sum _{\sigma \in \Pi _n} s(\sigma ) \, \delta _\sigma , \end{aligned}$$

where

$$\begin{aligned} s(\sigma ) := \sum _{\tau \le \sigma } t(\tau ) \qquad \text { for } \sigma \in \Pi _n. \end{aligned}$$

Therefore, using the orthogonal idempotence of the $\delta _\sigma$s, we have

$$\begin{aligned} T^2= & {} \sum _{\sigma \in \Pi _n} s(\sigma )^2 \delta _\sigma \\= & {} \sum _{\sigma \in \Pi _n} \Big ( s(\sigma )^2 \sum _{\tau \ge \sigma } \mu (\sigma , \tau ) \tau \Big ) \\= & {} \sum _{\tau \in \Pi _n} \Big ( \sum _{\sigma \le \tau } \mu (\sigma , \tau ) s(\sigma )^2 \Big ) \tau \end{aligned}$$

It follows from (7) that

$$\begin{aligned} a_n= & {} \sum _{\sigma \in \Pi _n} \mu (\sigma , \widehat{1}) \, s(\sigma )^2 \\= & {} \sum _{\sigma \in \Pi _n} (-1)^{\ell (\sigma )} (\ell (\sigma )-1)! \, s(\sigma )^2, \end{aligned}$$

using the facts that the interval $[\sigma , \widehat{1}]$ in the partition lattice $\Pi _n$ is isomorphic to the smaller partition lattice $\Pi _{\ell (\sigma )}$ – because the coarsenings of $\sigma$ are obtained by arbitrarily merging blocks of $\sigma$ – and the Möbius number of the partition lattice $\Pi _k$ is $\mu _{\Pi _k}(\widehat{0}, \widehat{1}) = (-1)^{k-1} (k-1)!$. $\square$

Using Proposition 5.1, one easily computes by hand the first values of the sequence:

$$\begin{aligned} a_1 = 1, \quad a_2 = 3, \quad a_3 = 39, \quad a_4 = 1242. \end{aligned}$$

6 Future directions

• 1. Find other simplicial polytopes with an elegant combinatorial structure that have the harmonic polytope as a Minkowski summand.

• 2. Use 1. to discover and explore other combinatorial models for Lagrangian geometry of matroids. Section 2 explains that the bipermutahedron is one such polytope, and leads to a theory of Lagrangian combinatorics of matroids, which is the subject of [5]. Other answers to 1. will lead to other such theories, and give rise to interesting matroid-theoretic directions.

• 3. Study the Ehrhart polynomial and $h^*$-polynomial of $H_{n,n}$.

• 4. Find a triangulation or subdivision of $H_{n,n}$ that will shed light on 3. In particular, $H_{n,n}$ is a Minkowski sum of one simplex and $n(n-1)$ segments, and its mixed subdivisions are likely to have a rich combinatorial structure.