--- abstract: 'The polytope subalgebra of deformations of a zonotope can be endowed with the structure of a module over the Tits algebra of the corresponding hyperplane arrangement. We explore this construction and find relations between statistics on (signed) permutations and the module structure in the case of (type B) generalized permutahedra. In type B, the module structure surprisingly reveals that any family of generators (via signed Minkowski sums) for generalized permutahedra of type B will contain at least $2^{d-1}$ full-dimensional polytopes. We find a generating family of simplices attaining this minimum. Finally, we prove that the relations defining the polytope algebra are compatible with the Hopf monoid structure of generalized permutahedra.' address: | Department of Mathematics\ Cornell University\ Ithaca, NY 14853 author: - Jose Bastidas bibliography: - 'bib.bib' title: The polytope algebra of generalized permutahedra --- Introduction ============ Generalized permutahedra serve as a geometric model for many *classical* (type A) combinatorial objects and have been extensively studied in resent years. Notably, Aguiar and Ardila [@aa17] endowed generalized permutahedra with the structure of a Hopf monoid <span>GP</span> in the category of species and, in so doing, gave a unified framework to study similar algebraic structures over many different families of combinatorial objects. At the same time, McMullen's polytope algebra [@mcmullen89] offers a different algebraic perspective to study generalized permutahedra. One of the goals of the present paper is to investigate the compatibility between both structures. To achieve this goal, we take a more general approach and study deformations of an arbitrary zonotope. We then specialize our results to deformations Coxeter permutahedra of type A and type B, revealing remarkable connections with (type B) Eulerian polynomials and statistics over (signed) permutations. The results in type B allow us to find a family of generalized permutahedra that generates all other deformations via signed Minkowski sums, thus solving a question posed by Ardila, Castillo, Eur, and Postnikov [@acep20submodular]. Let $V$ be a finite-dimensional real vector space. The polytope algebra $\Pi(V)$ is generated by the classes $[{{\mathfrak{p}}}]$ of polytopes ${{\mathfrak{p}}}\subseteq V$. These classes satisfy the following *valuation* and *translation invariance* relations: $ [{{\mathfrak{p}}}\cup {{\mathfrak{q}}}] + [{{\mathfrak{p}}}\cap {{\mathfrak{q}}}] = [{{\mathfrak{p}}}] + [{{\mathfrak{q}}}] $ and $ [{{\mathfrak{p}}}+ \{t\}] = [{{\mathfrak{p}}}], $ whenever ${{\mathfrak{p}}}\cup {{\mathfrak{q}}}$ is a polytope and for every $t \in V$. The product structure of $\Pi(V)$ is given by the Minkowski sum of polytopes: $[{{\mathfrak{p}}}] \cdot [{{\mathfrak{q}}}] = [{{\mathfrak{p}}}+ {{\mathfrak{q}}}]$. $$\left[ \begin{gathered} \begin{tikzpicture}[scale=.7] \draw [thick,fill=gray!30!white] (0,0) -- (1,0) -- (.5,.866) -- cycle; \end{tikzpicture} \end{gathered} \right] \cdot\left[ \begin{gathered} \begin{tikzpicture}[scale=.7] \draw [very thick,fill=gray!30!white] (0,0) -- (1,0); \end{tikzpicture} \end{gathered} \right] \quad = \quad \left[ \begin{gathered} \begin{tikzpicture}[scale=.7] \draw [thick,fill=gray!30!white] (0,0) -- (2,0) -- (1.5,.866) -- (.5,.866) -- cycle; \end{tikzpicture} \end{gathered} \right] \quad = \quad \left[ \begin{gathered} \begin{tikzpicture}[scale=.7] \draw [thick,fill=gray!30!white] (0,0) -- (1,0) -- (1.5,.866) -- (.5,.866) -- cycle; \end{tikzpicture} \end{gathered} \right] + \left[ \begin{gathered} \begin{tikzpicture}[scale=.7] \draw [thick,fill=gray!30!white] (0,0) -- (1,0) -- (.5,.866) -- (-.5,.866) -- cycle; \end{tikzpicture} \end{gathered} \right] - \left[ \begin{gathered} \begin{tikzpicture}[scale=.7] \draw [thick,fill=gray!30!white] (1,0) -- (1.5,.866) -- (.5,.866) -- cycle; \end{tikzpicture} \end{gathered} \right]$$ For a fixed polytope ${{\mathfrak{p}}}\subseteq V$, $\Pi({{\mathfrak{p}}})$ denotes the subalgebra of $\Pi(V)$ generated by classes of *deformations* of ${{\mathfrak{p}}}$; see McMullen [@mcmullen93simple]. We are particularly interested in the case where ${{\mathfrak{p}}}$ is a zonotope corresponding to a linear hyperplane arrangement ${\mathcal A}$. In this case, let ${\mathsf{\Sigma}}[{\mathcal A}]$ denote the Tits algebra of ${\mathcal A}$, see Section \[s:Tits\]. It is linearly generated by the elements ${\mathtt{H}}_F$ as $F$ runs through the faces of the arrangement. The following is a central result of this paper. Let ${{\mathfrak{p}}}$ and ${\mathcal A}$ be as above. The algebra $\Pi({{\mathfrak{p}}})$ is a right ${\mathsf{\Sigma}}[{\mathcal A}]$-module under the following action: $$[{{\mathfrak{q}}}] \cdot {\mathtt{H}}_F := [{{\mathfrak{q}}}_v],$$ where $v \in \operatorname{relint}(F)$ and ${{\mathfrak{q}}}_v$ denotes the face of ${{\mathfrak{q}}}$ *maximal in the direction* of $v$. Moreover, the action of ${\mathtt{H}}_F$ is an endomorphism of graded algebras. In the particular case of the permutahedron and the braid arrangement, the compatibility between the algebra structure and the action of the Tits algebra is related to the Hopf monoid structure of Aguiar and Ardila. Similar results for the Hopf monoid of extended generalized permutahedra were independently obtained by Ardila and Sanchez in [@as20valGP]. The species $\Pi$ defined by $\Pi[I] = \Pi(\pi_I)$, where $\pi_I \subseteq {\mathbb{R}}^I$ is the standard permutahedron, is a Hopf monoid quotient of ${\sf GP}$. We embark on further understanding the module structure of $\Pi({{\mathfrak{z}}})$ when ${{\mathfrak{z}}}$ is a zonotope corresponding to a hyperplane arrangement ${\mathcal A}$. The decomposition of $\Pi({{\mathfrak{z}}}) = \bigoplus_r \Xi_r({{\mathfrak{z}}})$ into its graded components will play an essential role here. McMullen characterized $\Xi_r({{\mathfrak{z}}})$ as the eigenspace of the dilation morphism $\delta_\lambda$, defined by $\delta_\lambda[{{\mathfrak{p}}}] = [\lambda {{\mathfrak{p}}}]$, with eigenvalue $\lambda^r$ for any positive $\lambda \neq 1$. Theorem \[t:mod\_str\] then implies that each graded component is a ${\mathsf{\Sigma}}[{\mathcal A}]$-submodule. The simple modules over ${\mathsf{\Sigma}}[{\mathcal A}]$ are one-dimensional and indexed by the flats of the arrangement [@am17 Chapter 9]. Given a module $M$ over ${\mathsf{\Sigma}}[{\mathcal A}]$, the number of copies of the simple module associated with the flat ${\mathrm{X}}$ that appear as a composition factor of $M$ is $\eta_{\mathrm{X}}(M)$. We propose that studying these algebraic invariants for the modules $\Xi_r({{\mathfrak{z}}})$ yields important geometric and combinatorial information of the deformations of ${{\mathfrak{z}}}$. In Sections \[s:braid\] and \[s:typeB\], we do this for the algebra of deformations of the permutahedron and the type B permutahedron, respectively. The main results in these sections relate the invariants $\eta_{\mathrm{X}}$ with statistics over (signed) permutations: For any flat ${\mathrm{X}}$ of the braid arrangement in ${\mathbb{R}}^d$ and $r=0,1,\dots,d-1$, $$\eta_{\mathrm{X}}(\Xi_r(\pi_d)) = \big|\{ \sigma \in {{\mathfrak{S}}}_d \,:\, \operatorname{s}(\sigma) = {\mathrm{X}},\ \operatorname{exc}(\sigma) = r \}\big|.$$ For any flat ${\mathrm{X}}$ of type B Coxeter arrangement in ${\mathbb{R}}^d$ and $r=0,1,\dots, d$, $$\eta_{\mathrm{X}}(\Xi_r(\pi^B_d)) = \big|\{ \sigma \in {{\mathfrak{B}}}_d \,:\, \operatorname{s}(\sigma) = {\mathrm{X}},\ \operatorname{exc}_B(\sigma) = r \}\big|.$$ This surprising relation arises from the remarkable results of McMullen and Brenti that we explain now. McMullen [@mcmullen93simple] proved that when ${{\mathfrak{p}}}$ is a simple polytope, just like the (type B) permutahedron, the dimension of the graded components $\Xi_r({{\mathfrak{p}}})$ are determined by the $h$-numbers of ${{\mathfrak{p}}}$. On the other hand, building on top of work by Björner [@bjorner84], Brenti proved that the $h$-polynomial of the Coxeter permutahedron associated with any Coxeter group is the corresponding Eulerian polynomial [@brenti94cox-eul Theorem 2.3]. Ardila, Benedetti, and Doker [@abd10volume] proved that any generalized permutahedron in ${\mathbb{R}}^d$ can be written as the *signed Minkowski sum* of the faces of the standard simplex $\Delta_{[d]} = \operatorname{Conv}\{ e_j \,:\, j \in [d]\}$. As a consequence of Theorem \[t:dims\_simul\_e-spaces\_B\], we show that any such set of generators for type B generalized permutahedra contains at least $2^{d-1}$ full dimensional polytopes. We manage to obtain a family of generators that attains this minimum. Every type B generalized permutahedron in ${\mathbb{R}}^d$ can be written uniquely as a signed Minkowski sum of the simplices $\Delta_S$ and $\Delta^0_S$ for *special involution-exclusive* subsets $S \subseteq [\pm d]$. This document is organized as follows. We review McMullen's construction in Section \[s:polytope\]. In Section \[s:Tits\], we recall the definition of the Tits algebra of a hyperplane arrangement and some of its representation theoretic properties. Characteristic elements and Eulerian idempotents are also reviewed in this section. In Section \[s:module\], we introduce the McMullen module of a hyperplane arrangement, this is the central construction for this paper. We study the polytope algebra of generalized permutahedra in Section \[s:braid\]. In particular, we provide a conjectural basis of simultaneous eigenvectors for the action of the *Adams element* and positive dilations on the module $\Pi(\pi_d)$. Section \[s:typeB\] contains the analogous results for type B. We also give an explicit set of *signed Minkowski generators* for type B generalized permutahedra. In Section \[s:hopf\] we prove that the valuation and translation invariance relations are compatible with the Hopf monoid structure of <span>GP</span>. Section \[s:remarks\] contains some final remarks and questions. We begin with some preliminaries. Preliminaries ------------- Let $V$ be a real vector space of dimension $d$ endowed with an inner product $\langle \,\cdot\, , \cdot\, \rangle$, and let ${\bf 0} \in V$ denote its zero vector. For a polytope ${{\mathfrak{p}}}\subseteq V$ and a vector $v \in V$, let ${{\mathfrak{p}}}_v$ denote the face of ${{\mathfrak{p}}}$ maximized in the direction $v$. That is, $${{\mathfrak{p}}}_v := \{ p \in {{\mathfrak{p}}}\,:\, \langle p , v \rangle \geq \langle q , v \rangle \text{ for all } q \in {{\mathfrak{p}}}\}.$$ The (outer) **normal cone** of a face ${{\mathfrak{f}}}$ of ${{\mathfrak{p}}}$ is the polyhedral cone $$N({{\mathfrak{f}}},{{\mathfrak{p}}}) := \{ v \in V \,:\, {{\mathfrak{f}}}\leq {{\mathfrak{p}}}_v\} = \overline{\{ v \in V \,:\, {{\mathfrak{f}}}= {{\mathfrak{p}}}_v\}},$$ and the **normal fan** of ${{\mathfrak{p}}}$ is the collection $ {\Sigma}_{{\mathfrak{p}}}= \{ N({{\mathfrak{f}}},{{\mathfrak{p}}}) \,:\, {{\mathfrak{f}}}\leq {{\mathfrak{p}}}\} $ of all normal cones of faces of ${{\mathfrak{p}}}$. There is a natural order-reversing correspondence between faces of ${{\mathfrak{p}}}$ and cones in ${\Sigma}_{{\mathfrak{p}}}$. For $F \in {\Sigma}_{{\mathfrak{p}}}$, we let ${{\mathfrak{p}}}_F \leq {{\mathfrak{p}}}$ denote the face whose normal cone is $F$. That is ${{\mathfrak{p}}}_F = {{\mathfrak{p}}}_v$ for any $v$ in the relative interior of $F$. $$\begin{gathered} \begin{tikzpicture}[->] \draw [blue1] (0,0) -- (-1,0) node [left] {\small$w$}; \draw [red1] (0,0) -- (0,1) node [above] {\small$v$}; \end{tikzpicture} \end{gathered} \hspace*{.1\linewidth} \begin{gathered} \begin{tikzpicture} \draw [thick, fill=gray!30!white] (-1,0) -- (1,0) -- (1.5,.866) -- (1,1.732) -- (0,1.732) -- (-1,0); \draw [line width=0.7mm, red1] (1,1.732) -- (0,1.732); \node at (.5,.866) {\small${{\mathfrak{p}}}$}; \node [red1] at (.5,2) {\small${{\mathfrak{p}}}_v$}; \node [circle, inner sep = 1pt, fill = blue1, color = blue1, draw] at (-1,0) {}; \node [blue1] at (-1.3,0) {\small${{\mathfrak{p}}}_w$}; \end{tikzpicture} \end{gathered} \hspace*{.1\linewidth} \begin{gathered} \begin{tikzpicture} \newdimen\R \R=1.2cm \draw [fill, color = blue1, opacity = .3] (0,0) -- (150:\R) arc (150:270:\R); \draw [fill, color = gray!20!white] (0,0) -- (-90:\R) arc (-90:150:\R); \draw [<->] (30:\R) -- (0,0) -- (-90:\R); \draw [<->] (150:\R) -- (-30:\R); \draw [line width=0.4mm, red1, ->] (0,0) -- (90:\R) node [above] {\small $N({{\mathfrak{p}}}_v,{{\mathfrak{p}}})$}; \node [blue1] at (200:1.5\R) {\small $N({{\mathfrak{p}}}_w,{{\mathfrak{p}}})$}; \end{tikzpicture} \end{gathered}$$ Recall that a fan ${\Sigma}$ **refines** ${\Sigma}'$ if every cone in ${\Sigma}'$ is a union of cones in ${\Sigma}$. We say that a polytope ${{\mathfrak{q}}}$ is a **deformation** of ${{\mathfrak{p}}}$ if ${\Sigma}_{{\mathfrak{p}}}$ refines ${\Sigma}_{{\mathfrak{q}}}$. The **Minkowski sum** of two polytopes ${{\mathfrak{p}}},{{\mathfrak{q}}}\subseteq V$ is the polytope ${{\mathfrak{p}}}+ {{\mathfrak{q}}}:= \{ p + q \,:\, p \in {{\mathfrak{p}}},\, q \in {{\mathfrak{q}}}\}$. We say that a polytope ${{\mathfrak{q}}}$ is a **Minkowski summand** of ${{\mathfrak{p}}}$ if ${{\mathfrak{p}}}= {{\mathfrak{q}}}+ {{\mathfrak{q}}}'$ for some polytope ${{\mathfrak{q}}}'$. The normal fan of ${{\mathfrak{p}}}+ {{\mathfrak{q}}}$ is the common refinement of ${\Sigma}_{{\mathfrak{p}}}$ and ${\Sigma}_{{\mathfrak{q}}}$. Hence, ${\Sigma}_{{\mathfrak{p}}}$ refines the normal fan of any of its Minkowski summands, and the Minkowski sum of deformations of ${{\mathfrak{p}}}$ is again a deformation of ${{\mathfrak{p}}}$. The $f$-polynomial of a $d$-dimensional polytope ${{\mathfrak{p}}}$ is $$f({{\mathfrak{p}}},z) = \sum_{i=0}^d f_i({{\mathfrak{p}}}) z^i,$$ where $f_i({{\mathfrak{p}}})$ is the number of $i$-dimensional faces of ${{\mathfrak{p}}}$. The $h$-polynomial of ${{\mathfrak{p}}}$ is defined by $$h({{\mathfrak{p}}},z) = \sum_{i=0}^d h_i({{\mathfrak{p}}}) z^i = f({{\mathfrak{p}}},z-1).$$ The sequences $(f_0({{\mathfrak{p}}}),\dots,f_d({{\mathfrak{p}}}))$ and $(h_0({{\mathfrak{p}}}),\dots,h_d({{\mathfrak{p}}}))$ are the $f$-vector and $h$-vector of ${{\mathfrak{p}}}$, respectively. These polynomials behave nicely with respect to the Cartesian product of polytopes: $$f({{\mathfrak{p}}}\times {{\mathfrak{q}}},z) = f({{\mathfrak{p}}},z)f({{\mathfrak{q}}},z) \qquad h({{\mathfrak{p}}}\times {{\mathfrak{q}}},z) = h({{\mathfrak{p}}},z)h({{\mathfrak{q}}},z),$$ where ${{\mathfrak{p}}}\times {{\mathfrak{q}}}= \{ (p,q) \,:\, p \in {{\mathfrak{p}}},\, q \in {{\mathfrak{q}}}\}$. The polytope algebra {#s:polytope} ==================== We briefly review the construction of McMullen's polytope algebra [@mcmullen89] and its main properties. A hands on introduction to this topic can be found in the survey [@castillo19]. The subalgebra relative to a fixed polytope [@mcmullen93simple] is studied at the end of this section. Definition and structure theorem -------------------------------- As an abelian group, the **polytope algebra** $\Pi(V)$ is generated by elements $[{{\mathfrak{p}}}]$, one for each polytope ${{\mathfrak{p}}}\subseteq V$. These generators satisfy the relations $$\label{eq:valuation_property} [{{\mathfrak{p}}}\cup {{\mathfrak{q}}}] + [{{\mathfrak{p}}}\cap {{\mathfrak{q}}}] = [{{\mathfrak{p}}}] + [{{\mathfrak{q}}}],$$ whenever ${{\mathfrak{p}}}$, ${{\mathfrak{q}}}$ and ${{\mathfrak{p}}}\cup {{\mathfrak{q}}}$ are polytopes; and $$\label{eq:translation_property} [{{\mathfrak{p}}}+ \{t\}] = [{{\mathfrak{p}}}],$$ for any polytope ${{\mathfrak{p}}}$ and translation vector $t \in V$. These relations are referred as the **valuation property** and the **translation invariance property**, respectively. The group $\Pi(V)$ is endowed with a commutative product defined on generators by means of the Minkowski sum $$[{{\mathfrak{p}}}] \cdot [{{\mathfrak{q}}}] := [ {{\mathfrak{p}}}+ {{\mathfrak{q}}}].$$ It readily follows from that the class of a point $1 := [\{{\bf 0}\}]$ is the unit of $\Pi(V)$. For each scalar $\lambda \in {\mathbb{R}}$, the **dilation morphism** $\delta_\lambda:\Pi(V) \rightarrow \Pi(V)$ is defined on generators by $ \delta_\lambda [{{\mathfrak{p}}}] = [\lambda {{\mathfrak{p}}}]. $ Recall that for any subset $S \subseteq V$ and $\lambda \in {\mathbb{R}}$, $\lambda S := \{\lambda v \,:\, v \in S\}$. One can easily verify that $\delta_\lambda$ preserves the valuation and translation invariance relations, and that it defines a morphism of rings. The main structural result for the polytope algebra is the following. \[<span>[@mcmullen89 Theorem 1]</span>\] The commutative ring $\Pi(V)$ is almost a graded ${\mathbb{R}}$-algebra, in the following sense: i. as an abelian group, $\Pi(V)$ admits a direct sum decomposition $$\Pi(V) = \Xi_0(V) \oplus \Xi_1(V) \oplus \cdots \oplus \Xi_d(V);$$ ii. under multiplication, $ \Xi_r(V) \cdot \Xi_s(V) = \Xi_{r+s}(V), $ with $\Xi_r(V) = 0$ for $r > d$; iii. $\Xi_0(V) \cong {\mathbb{Z}}$, and for $r=1,\dots,d$, $\Xi_r(V)$ is a real vector space; iv. the product of elements in $\bigoplus_{r \geq 1} \Xi_r(V)$ is bilinear. v. the dilations $\delta_\lambda$ are algebra endomorphisms, and for $r = 0,1,\dots,d$, if $x \in \Xi_r(V)$ and $\lambda \geq 0$, then $ \delta_\lambda x = \lambda^r x. $ We discuss the definition of the graded components $\Xi_r(V)$ below. The component $\Xi_0(V)$ of degree $0$ is simply the subring of $\Pi(V)$ generated by $1$, and thus $\Xi_0(V) \cong {\mathbb{Z}}$. Let $Z_1$ be the subgroup of $\Pi(V)$ generated by all elements of the form $[{{\mathfrak{p}}}] - 1$. Observe that $\delta_0[{{\mathfrak{p}}}] = 1$ for every polytope ${{\mathfrak{p}}}$, so $Z_1 = \ker\delta_0$ is an ideal. As an abelian group, $\Pi(V)$ has a direct sum decomposition $ \Pi(V) = \Xi_0(V) \oplus Z_1. $ Moreover, $Z_1$ is a nil ideal, since for any $k$-dimensional polytope ${{\mathfrak{p}}}$, $$([{{\mathfrak{p}}}] - 1)^r = 0 \quad \text{for } r > k.$$ This is <span>[@mcmullen89 Lemma 13]</span>. McMullen also shows that $Z_1$ has the structure of a vector space (first over ${\mathbb{Q}}$ and then over ${\mathbb{R}}$). Therefore, we can define inverse maps $$\begin{tikzcd} 1 + Z_1 \arrow[rr, "\log" description, bend left] & & Z_1 \arrow[ll, "\exp" description, bend left] \end{tikzcd}$$ by means of their usual power series. In particular, we can define the *log-class* of a $k$-dimensional polytope ${{\mathfrak{p}}}$ by $$\label{eq:def-log} \log[{{\mathfrak{p}}}] := \log(1 + ([{{\mathfrak{p}}}]-1)) = \sum_{r = 1}^k \dfrac{(-1)^{r-1}}{r}([{{\mathfrak{p}}}]-1)^r.$$ Using the exponential map, we recover $[{{\mathfrak{p}}}]$ from $\log[{{\mathfrak{p}}}]$: $$\label{eq:def-exp} [{{\mathfrak{p}}}] = \sum_{r = 0}^k \dfrac{1}{r!} (\log[{{\mathfrak{p}}}])^r.$$ The $\log$ and $\exp$ maps satisfy the standard properties of logarithms and exponentials. In particular, $$\label{eq:log_add} \log[{{\mathfrak{p}}}+ {{\mathfrak{q}}}] = \log([{{\mathfrak{p}}}] \cdot [{{\mathfrak{q}}}]) = \log[{{\mathfrak{p}}}] + \log[{{\mathfrak{q}}}].$$ \[ex:prod\_intervals\] Let $v_1,\dots,v_k \in V$ be nonzero vectors and let ${{\mathfrak{l}}}_i$ denote the line segment $\operatorname{Conv}\{ {\bf 0} ,v_i\}$. Then, $\log[{{\mathfrak{l}}}_i] = [{{\mathfrak{l}}}_i] - 1$. We will see that the product $\prod_{i=1}^k \log[{{\mathfrak{l}}}_i] \in \Xi_k(V)$ is nonzero if and only if the collection $\{v_1,\dots,v_k\}$ is linearly independent. See Figure \[f:ex-prod-log\] for an example with $k = 3$. Consider the polytope ${{\mathfrak{z}}}= {{\mathfrak{l}}}_1 + {{\mathfrak{l}}}_1 + \dots + {{\mathfrak{l}}}_k$, a Minkowski sum of segments. Using the logarithm property , we get $ (\log[{{\mathfrak{z}}}])^k = ( \sum_{i=1}^k \log[{{\mathfrak{l}}}_i] )^k = k! \prod_{i=1}^k \log[{{\mathfrak{l}}}_i]. $ The last equality follows since $k! \prod \log[{{\mathfrak{l}}}_i]$ is the only square-free term in the expansion of $( \sum\log[{{\mathfrak{l}}}_i])^k$, and $(\log[{{\mathfrak{l}}}])^2 = ([{{\mathfrak{l}}}] - 1)^2 = 0$ for any line segment ${{\mathfrak{l}}}$. Finally, $(\log[{{\mathfrak{z}}}])^k \neq 0$ if and only if $k \leq \dim({{\mathfrak{z}}})$, and ${{\mathfrak{z}}}$ being the sum of $k$ line segments has dimension at most $k$, with equality precisely when the vectors $v_1,\dots,v_k$ are linearly independent. $$\begin{gathered} \begin{tikzpicture}[->,black] \draw (0,0) -- (0:1) node [right] {\small$v_1$}; \draw (0,0) -- (60:1) node [above right] {\small$v_2$}; \draw (0,0) -- (120:1) node [above left] {\small$v_3$}; \end{tikzpicture} \end{gathered} \quad ([{{\mathfrak{l}}}_1]-1)([{{\mathfrak{l}}}_2]-1) = \quad \begin{gathered} \begin{tikzpicture} \draw [fill=gray!30!white] (0,0) -- (1,0) -- (1.5,.866) -- (.5,.866) -- (0,0); \node [] at (.75,.433) {\small$[{{\mathfrak{l}}}_1][{{\mathfrak{l}}}_2]$}; \end{tikzpicture} \end{gathered} \quad - \quad \begin{gathered} \begin{tikzpicture} \node [above] at (-.5,0) {\small$[{{\mathfrak{l}}}_1]$}; \draw [thick] (0,0) -- (-1,0); \end{tikzpicture} \end{gathered} \quad - \quad \begin{gathered} \begin{tikzpicture} \node [above] at (.6,.1) {\small$[{{\mathfrak{l}}}_2]$}; \draw [shift={(.05,.05)}, thick] (0,0) -- (.5,.866); \end{tikzpicture} \end{gathered} \quad + \quad \bullet \quad = \quad \begin{gathered} \begin{tikzpicture} \draw [color = white, fill=gray!30!white] (0,0) -- (1,0) -- (1.5,.866) -- (.5,.866) -- (0,0); \draw [] (.5,.866) -- (0,0) -- (1,0); \draw [dashed] (.5,.866) -- (1.5,.866) -- (1,0); \end{tikzpicture} \end{gathered}$$ $$([{{\mathfrak{l}}}_1]-1)([{{\mathfrak{l}}}_2]-1)([{{\mathfrak{l}}}_3]-1) = \quad \begin{gathered} \begin{tikzpicture} \draw [fill=gray!30!white] (0,0) -- (1,0) -- (1.5,.866) -- (1,1.732) -- (0,1.732) -- (-.5,.866) -- (0,0); \node at (.5,.866) {\small$[{{\mathfrak{l}}}_1][{{\mathfrak{l}}}_2][{{\mathfrak{l}}}_3]$}; \draw [dotted] (-.5,.866) -- (.5,.866) -- (1,1.732); \draw [dotted] (.5,.866) -- (1,0); \end{tikzpicture} \end{gathered} \quad - \quad \begin{gathered} \begin{tikzpicture} \draw [fill=gray!30!white] (0,0) -- (1,0) -- (.5,.866) -- (-.5,.866) -- (0,0); \node at (.25,.433) {\small$[{{\mathfrak{l}}}_1][{{\mathfrak{l}}}_3]$}; \draw [shift={(1.1,.05)}, fill=gray!30!white] (0,0) -- (.5,.866) -- (0,1.732) -- (-.5,.866) -- (0,0); \node [shift={(1.1,.05)}] at (0,.866) {\small$[{{\mathfrak{l}}}_2][{{\mathfrak{l}}}_3]$}; \draw [shift={(-.5,.966)}, fill=gray!30!white] (0,0) -- (1,0) -- (1.5,.866) -- (.5,.866) -- (0,0); \node [shift={(-.5,.966)}] at (.75,.433) {\small$[{{\mathfrak{l}}}_1][{{\mathfrak{l}}}_2]$}; \end{tikzpicture} \end{gathered} \quad + \quad \begin{gathered} \begin{tikzpicture} \node [above] at (-.5,0) {\small$[{{\mathfrak{l}}}_1]$}; \node [above] at (.6,.1) {\small$[{{\mathfrak{l}}}_2]$}; \node [below] at (.6,-.1) {\small$[{{\mathfrak{l}}}_3]$}; \draw [thick] (0,0) -- (-1,0); \draw [shift={(.05,.05)}, thick] (0,0) -- (.5,.866); \draw [shift={(.05,-.05)}, thick] (0,0) -- (.5,-.866); \end{tikzpicture} \end{gathered} \quad - \quad \bullet \quad = 0$$ \[f:ex-prod-log\] For $r \geq 1$ let $\Xi_r(V)$ be the subgroup (or subspace) of $\Pi(V)$ generated by elements of the form $(\log[{{\mathfrak{p}}}])^r$. The following result implies that the sum $\Pi(V) = \Xi_0(V) + \Xi_1(V) + \dots + \Xi_d(V)$ is direct, and characterizes each graded component as the space of eigenvectors for the positive dilations $\delta_\lambda$. \[<span>[@mcmullen89 Lemma 20]</span>\] Let $x \in \Pi(V)$ and $\lambda > 0$, with $\lambda \neq 1$. Then, $$\label{eq:Xi_dilation} x \in \Xi_r(V) \qquad\text{if and only if}\qquad \delta_\lambda x = \lambda^r x.$$ It is clear by the definition of the graded components $\Xi_r(V)$ that the class of a half-open parallelogram in Figure \[f:ex-prod-log\] is in $\Xi_2(V)$. We can also verify this using with $\lambda = 2$: $$\delta_2 \left( \begin{gathered} \begin{tikzpicture} \draw [color = white, fill=gray!30!white] (0,0) -- (1,0) -- (1.5,.866) -- (.5,.866) -- (0,0); \draw [] (.5,.866) -- (0,0) -- (1,0); \draw [dashed] (.5,.866) -- (1.5,.866) -- (1,0); \end{tikzpicture} \end{gathered} \right) = \begin{gathered} \begin{tikzpicture}[scale = 2] \draw [color = white, fill=gray!30!white] (0,0) -- (1,0) -- (1.5,.866) -- (.5,.866) -- (0,0); \draw [] (.5,.866) -- (0,0) -- (1,0); \draw [dashed] (.5,.866) -- (1.5,.866) -- (1,0); \end{tikzpicture} \end{gathered} = \begin{gathered} \begin{tikzpicture} \draw [color = white, fill=gray!30!white] (0,0) -- (1,0) -- (1.5,.866) -- (.5,.866) -- (0,0); \draw [] (.5,.866) -- (0,0) -- (1,0); \draw [dashed] (.5,.866) -- (1.5,.866) -- (1,0); \draw [shift={(1.15,0)}, color = white, fill=gray!30!white] (0,0) -- (1,0) -- (1.5,.866) -- (.5,.866) -- (0,0); \draw [shift={(1.15,0)}] (.5,.866) -- (0,0) -- (1,0); \draw [shift={(1.15,0)}, dashed] (.5,.866) -- (1.5,.866) -- (1,0); \draw [shift={(.6,1.039)}, color = white, fill=gray!30!white] (0,0) -- (1,0) -- (1.5,.866) -- (.5,.866) -- (0,0); \draw [shift={(.6,1.039)}] (.5,.866) -- (0,0) -- (1,0); \draw [shift={(.6,1.039)}, dashed] (.5,.866) -- (1.5,.866) -- (1,0); \draw [shift={(1.75,1.039)}, color = white, fill=gray!30!white] (0,0) -- (1,0) -- (1.5,.866) -- (.5,.866) -- (0,0); \draw [shift={(1.75,1.039)}] (.5,.866) -- (0,0) -- (1,0); \draw [shift={(1.75,1.039)}, dashed] (.5,.866) -- (1.5,.866) -- (1,0); \end{tikzpicture} \end{gathered} = 2^2 \begin{gathered} \begin{tikzpicture} \draw [color = white, fill=gray!30!white] (0,0) -- (1,0) -- (1.5,.866) -- (.5,.866) -- (0,0); \draw [] (.5,.866) -- (0,0) -- (1,0); \draw [dashed] (.5,.866) -- (1.5,.866) -- (1,0); \end{tikzpicture} \end{gathered}$$ As in later work of McMullen [@mcmullen93separation; @mcmullen93simple], we replace $\Xi_0(V) \cong {\mathbb{Z}}$ with the tensor product $\Xi_0(V)_{\mathbb{R}}:= {\mathbb{R}}\otimes \Xi_0(V) \cong {\mathbb{R}}$ to get a genuine graded ${\mathbb{R}}$-algebra $\Pi(V)_{\mathbb{R}}:= \Xi_0(V)_{\mathbb{R}}\oplus Z_1$. To simplify notation, we drop the subscript ${\mathbb{R}}$ and sometimes wirte $\Xi_r$ and $\Pi$ instead of $\Xi_r(V)$ and $\Pi(V)_{\mathbb{R}}$. For an arbitrary vector $v \in V$, we can define a **maximization operator** ${{\mathfrak{p}}}\mapsto {{\mathfrak{p}}}_v$ on the space of all polytopes ${{\mathfrak{p}}}\subseteq V$. The next result shows that it induces a well-defined map on $\Pi(V)$. \[<span>[@mcmullen89 Theorem 7]</span>\]\[t:direction\_morphism\] The map ${{\mathfrak{p}}}\mapsto {{\mathfrak{p}}}_v$ induces an endomorphism $x \mapsto x_v$ on $\Pi(V)$, defined on generators by $$[{{\mathfrak{p}}}] \mapsto [{{\mathfrak{p}}}]_v := [{{\mathfrak{p}}}_v].$$ This endomorphism commutes with nonnegative dilations. In particular, the morphism $x \mapsto x_v$ restricts to each graded component $\Xi_r$. Subalgebra relative to a fixed polytope {#ss:subalgebra_polytope} --------------------------------------- Fix a polytope ${{\mathfrak{p}}}\subseteq V$. The **subalgebra relative to ${{\mathfrak{p}}}$**, denoted $\Pi({{\mathfrak{p}}})$, is the subalgebra of $\Pi(V)$ generated by classes $[{{\mathfrak{q}}}]$ of deformations ${{\mathfrak{q}}}$ of ${{\mathfrak{p}}}$. It is worth pointing out that if ${{\mathfrak{q}}},{{\mathfrak{q}}}'$ are deformations of ${{\mathfrak{p}}}$ such that ${{\mathfrak{q}}}\cup {{\mathfrak{q}}}'$ is a polytope, then both ${{\mathfrak{q}}}\cup {{\mathfrak{q}}}'$ and ${{\mathfrak{q}}}\cap {{\mathfrak{q}}}'$ are deformations of ${{\mathfrak{p}}}$. This follows since, in this case, ${{\mathfrak{q}}}\cup {{\mathfrak{q}}}' + {{\mathfrak{q}}}\cap {{\mathfrak{q}}}' = {{\mathfrak{q}}}+ {{\mathfrak{q}}}'$ and Minkowski summands of a deformation of ${{\mathfrak{p}}}$ are again deformations of ${{\mathfrak{p}}}$. Thus, the valuation property is not introducing classes of new polytopes to $\Pi({{\mathfrak{p}}})$. McMullen @mcmullen93simple originally defined $\Pi({{\mathfrak{p}}})$ as the subalgebra generated by the classes of Minkowski summands of ${{\mathfrak{p}}}$. The following result of Shephard @grunbaum03convex [Section 15.2.7] implies that both definitions are equivalent: a polytope ${{\mathfrak{q}}}$ is a deformation of ${{\mathfrak{p}}}$ if and only if for small enough $\lambda > 0$, $\lambda {{\mathfrak{q}}}$ is a Minkowski summand of ${{\mathfrak{p}}}$. The relations between $[{{\mathfrak{q}}}]$ and $\log[{{\mathfrak{q}}}]$ in and show that $\Pi({{\mathfrak{p}}})$ is generated by homogeneous elements. Thus, the grading of $\Pi(V)$ induces a grading of $\Pi({{\mathfrak{p}}})$. We let $\Xi_r({{\mathfrak{p}}}) = \Pi({{\mathfrak{p}}}) \cap \Xi_r(V)$ denote the component of $\Pi({{\mathfrak{p}}})$ in degree $r$. Unlike the full algebra $\Pi(V)$, the subalgebra $\Pi({{\mathfrak{p}}})$ has finite dimension. McMullen described the dimension of the graded components of $\Pi({{\mathfrak{p}}})$ when ${{\mathfrak{p}}}$ is a simple polytope. \[<span>[@mcmullen93simple Theorem 6.1]</span>\]\[t:simple\_h\_dimension\] Let ${{\mathfrak{p}}}$ be a $d$-dimensional simple polytope. Then, $$\dim_{\mathbb{R}}(\Xi_r({{\mathfrak{p}}})) = h_r({{\mathfrak{p}}})$$ for $r = 0,1,\dots,d$. Let ${{\mathfrak{f}}}$ be a face of ${{\mathfrak{p}}}$ and $v \in \operatorname{relint}\big(N({{\mathfrak{f}}},{{\mathfrak{p}}})\big)$. The maximization operator $x \mapsto x_v$ defines a morphism of graded algebras $$\label{eq:morphism_to_face} \psi_{{\mathfrak{f}}}: \Pi({{\mathfrak{p}}}) \rightarrow \Pi({{\mathfrak{f}}})$$ that only depends on the face ${{\mathfrak{f}}}$ and not on the particular choice of $v \in \operatorname{relint}\big(N({{\mathfrak{f}}},{{\mathfrak{p}}})\big)$. First observe that this map is well defined; that is, $[{{\mathfrak{q}}}_v] \in \Pi({{\mathfrak{f}}})$ for every generator $[{{\mathfrak{q}}}]$ of $\Pi({{\mathfrak{p}}})$. Indeed, if ${{\mathfrak{q}}}$ is a summand of ${{\mathfrak{p}}}$, say ${{\mathfrak{p}}}= {{\mathfrak{q}}}+ {{\mathfrak{q}}}'$, then $ {{\mathfrak{f}}}= {{\mathfrak{p}}}_v = {{\mathfrak{q}}}_v + {{\mathfrak{q}}}'_v, $ so ${{\mathfrak{q}}}_v$ is a Minkowski summand of ${{\mathfrak{f}}}$. Moreover, since the normal fan of ${{\mathfrak{p}}}$ refines that of ${{\mathfrak{q}}}$, then ${{\mathfrak{q}}}_w = {{\mathfrak{q}}}_v$ for any other $w \in \operatorname{relint}\big(N({{\mathfrak{f}}},{{\mathfrak{p}}})\big)$. Therefore the morphism only depends on ${{\mathfrak{f}}}$. \[<span>[@mcmullen93simple Theorem 2.4]</span>\]\[t:simple\_surjective\] Let ${{\mathfrak{p}}}$ be a simple polytope and ${{\mathfrak{f}}}$ a face of ${{\mathfrak{p}}}$. Then, the morphism $\psi_{{\mathfrak{f}}}$ is surjective. The Tits algebra of a linear hyperplane arrangement {#s:Tits} =================================================== Basic definitions ----------------- Let ${\mathcal A}$ be a linear hyperplane arrangement in $V$. An arbitrary intersection of hyperplanes in ${\mathcal A}$ is a **flat** of the arrangement. The set ${\mathcal{L}}[{\mathcal A}]$ of flats of ${\mathcal A}$ is a lattice with maximum $\top:= V$ and minimum $\perp$, the intersection of all hyperplanes in ${\mathcal A}$. For a flat ${\mathrm{X}}\in {\mathcal{L}}[{\mathcal A}]$, the **arrangement under ${\mathrm{X}}$** is the following hyperplane arrangement in ambient space ${\mathrm{X}}$: $${\mathcal A}^{\mathrm{X}}= \{{{\mathrm{H}}}\cap{\mathrm{X}}\,:\, {{\mathrm{H}}}\in{\mathcal A},\, {\mathrm{X}}\not\subseteq{{\mathrm{H}}}\}.$$ The **characteristic polynomial** of ${\mathcal A}$ is $${\chi}({\mathcal A},t) := \sum_{{\mathrm{X}}\in {\mathcal{L}}[{\mathcal A}]} \,\mu({\mathrm{X}},{\top}) \,t^{\dim({\mathrm{X}})},$$ where $\mu({\mathrm{X}},{\top})$ denotes the Möbius function of ${\mathcal{L}}[{\mathcal A}]$. It is a monic polynomial of degree $\dim(V)$. The hyperplanes in ${\mathcal A}$ split $V$ into a collection ${\Sigma}[{\mathcal A}]$ of polyhedral cones called **faces** of ${\mathcal A}$. Explicitly, the complement in $V$ of the union of hyperplanes in ${\mathcal A}$ is the disjoint union of open subsets of $V$; and ${\Sigma}[{\mathcal A}]$ is the collection of the closures of these regions together with all their faces. ${\Sigma}[{\mathcal A}]$ is a poset under containment, its maximal elements are called **chambers**. The **central face** $O$ is the minimum element of ${\Sigma}[{\mathcal A}]$, it coincides with the minimal flat $\perp$ of the arrangement. See Figure \[f:ex\_arr\] for an example. The **support** of a face $F$ is the smallest flat $\operatorname{s}(F)$ containing it. Equivalently, it is the linear span of $F$. The support map $$\label{eq:supp-map} \operatorname{s}:{\Sigma}[{\mathcal A}]\to{\mathcal{L}}[{\mathcal A}]$$ is surjective and order preserving. $$\begin{array}{C} \begin{gathered} \begin{tikzpicture}[<->,black] \node [] at (-2.2,1.3) {${\mathcal A}$}; \draw (-90:1.5) -- (90:1.5) node [above] {\small${{\mathrm{H}}}_1$}; \draw (150:1.5) -- (-30:1.5) node [below right] {\small${{\mathrm{H}}}_3$}; \draw (210:1.5) -- (30:1.5) node [above right] {\small${{\mathrm{H}}}_2$}; \draw [fill] (0,0) circle (.1); \end{tikzpicture} \end{gathered} \\ \phantom{a}\\ \begin{gathered} \begin{tikzpicture} \node [fill=white] at (-3.5,2) {${\Sigma}[{\mathcal A}]$}; \draw (-2.5,1) -- (2.5,2); \foreach \x in {-2.5 , -1.5 , -.5, .5 , 1.5} { \draw[preaction={draw=white, -,line width=6pt}] (\x+1,1) -- (\x,2); } \foreach \x in {-2.5 , -1.5 , -.5, .5 , 1.5 , 2.5} { \draw (0,0) -- (\x,1) -- (\x,2); \draw[preaction={draw=white, -,line width=6pt}] (\x,1) -- (\x,2); \foreach \y in {1,2} { \node [fill=white] at (\x,\y) {}; \node [circle, inner sep=1.5pt,fill,draw] at (\x,\y) {}; } } \node [fill=white] at (0,0) {\small~$O$}; \end{tikzpicture} \end{gathered} \hspace*{.15\linewidth} \begin{gathered} \begin{tikzpicture} \draw (0,0) -- (-1.4,1) -- (0,2); \draw (0,0) -- (0,1) -- (0,2); \draw (0,0) -- (1.4,1) -- (0,2); \node [fill=white] at (-2,2) {${\mathcal{L}}[{\mathcal A}]$}; \node [color=blue1,fill=white] at (2,2) {\small~$\mu({\bm\cdot},\top)$}; \node [fill=white] at (0,0) {\small~$\perp^{{{\color{blue1}{2}}}}$}; \node [fill=white] at (-1.2,1) {\small~${{{\mathrm{H}}}_1}^{{{\color{blue1}{-1}}}}$}; \node [fill=white] at (0.05,1) {\small~${{{\mathrm{H}}}_2}^{{{\color{blue1}{-1}}}}$}; \node [fill=white] at (1.2,1) {\small~${{{\mathrm{H}}}_3}^{{{\color{blue1}{-1}}}}$}; \node [fill=white] at (0,2) {\small~$\top^{{{\color{blue1}{1}}}}$}; \end{tikzpicture} \end{gathered} \end{array}$$ The Tits algebra and characteristic elements -------------------------------------------- The set ${\Sigma}[{\mathcal A}]$ has the structure of a monoid under the **Tits product** illustrated in Figure \[f:ex\_arr\_prod\]. The product of two faces $F$ and $G$, denoted $FG$, is the first face you encounter after moving a small positive distance from an interior point of $F$ to an interior point of $G$. The unit of this product is the central face $O \in {\Sigma}[{\mathcal A}]$. The **Tits algebra** of ${\mathcal A}$ is the monoid algebra ${\mathsf{\Sigma}}[{\mathcal A}] := {\mathbb{R}}\Sigma[{\mathcal A}]$. See @am17 [Chapters 1 and 9] for more details. We let ${\mathtt{H}}_F$ denote the basis element of ${\mathsf{\Sigma}}[{\mathcal A}]$ associated with the face $F$ of ${\mathcal A}$. $$\begin{gathered} \begin{tikzpicture}[<->,black] \newdimen\R \R=1.7cm \draw (-90:\R) node [below] {\small$G$} -- (0,0) node [left] {\small$O$} -- (90:\R); \draw (150:\R) node [above left] {\small$F$} -- (-30:\R); \draw (210:\R) -- (30:\R); \draw [fill] (0,0) circle (.1); \node [] at (0:.7\R) {\small$C$}; \node [] at (120:.7\R) {\small$FC$}; \node [] at (240:.7\R) {\small$GF$}; \end{tikzpicture} \end{gathered} \hspace*{.2\linewidth} \begin{gathered} \begin{tikzpicture}[scale=.7,black] \newdimen\R \R=2.5cm \coordinate (madhya) at (0,0); \draw (madhya) circle (\R); \coordinate (P) at (-1,0); \coordinate (Q) at (1,0); \coordinate (A1) at (54.735:\R); \coordinate (B1) at (180+54.735:\R); { { \coordinate (middle1) at ($(A1)!.5!(P)$); \coordinate (middle2) at ($(P)!.5!(B1)$); \coordinate (aux1) at ($(middle1)!1!90:(P)$); \coordinate (aux2) at ($(middle2)!1!90:(B1)$); \coordinate (centerA1) at ($(intersection of middle1--aux1 and middle2--aux2)$); \draw[,draw=none,name path=kamaanA1] let {{\mathfrak{p}}}1=($(A1)-(centerA1)$), {{\mathfrak{p}}}2=($(B1)-(centerA1)$), \n0={veclen({{\mathfrak{p}}}1)}, \n1={atan2(\y1,\x1)}, \n2={atan2(\y2,\x2)}, \n3={\n2>\n1?\n2:\n2+360} in (A1) arc(\n1:\n3:\n0); }; \draw (A1) to[anticlockwise arc centered at=centerA1] (B1); }; { { \coordinate (middle1) at ($(B1)!.5!(Q)$); \coordinate (middle2) at ($(Q)!.5!(A1)$); \coordinate (aux1) at ($(middle1)!1!90:(Q)$); \coordinate (aux2) at ($(middle2)!1!90:(A1)$); \coordinate (centerB1) at ($(intersection of middle1--aux1 and middle2--aux2)$); \draw[,draw=none,name path=kamaanB1] let {{\mathfrak{p}}}1=($(B1)-(centerB1)$), {{\mathfrak{p}}}2=($(A1)-(centerB1)$), \n0={veclen({{\mathfrak{p}}}1)}, \n1={atan2(\y1,\x1)}, \n2={atan2(\y2,\x2)}, \n3={\n2>\n1?\n2:\n2+360} in (B1) arc(\n1:\n3:\n0); }; \draw (B1) to[anticlockwise arc centered at=centerB1] (A1); }; \coordinate (A2) at (180-54.735:\R); \coordinate (B2) at (-54.735:\R); { { \coordinate (middle1) at ($(A2)!.5!(P)$); \coordinate (middle2) at ($(P)!.5!(B2)$); \coordinate (aux1) at ($(middle1)!1!90:(P)$); \coordinate (aux2) at ($(middle2)!1!90:(B2)$); \coordinate (centerA2) at ($(intersection of middle1--aux1 and middle2--aux2)$); \draw[,draw=none,name path=kamaanA2] let {{\mathfrak{p}}}1=($(A2)-(centerA2)$), {{\mathfrak{p}}}2=($(B2)-(centerA2)$), \n0={veclen({{\mathfrak{p}}}1)}, \n1={atan2(\y1,\x1)}, \n2={atan2(\y2,\x2)}, \n3={\n2>\n1?\n2:\n2+360} in (A2) arc(\n1:\n3:\n0); }; \draw (A2) to[anticlockwise arc centered at=centerA2] (B2); }; { { \coordinate (middle1) at ($(B2)!.5!(Q)$); \coordinate (middle2) at ($(Q)!.5!(A2)$); \coordinate (aux1) at ($(middle1)!1!90:(Q)$); \coordinate (aux2) at ($(middle2)!1!90:(A2)$); \coordinate (centerB2) at ($(intersection of middle1--aux1 and middle2--aux2)$); \draw[,draw=none,name path=kamaanB2] let {{\mathfrak{p}}}1=($(B2)-(centerB2)$), {{\mathfrak{p}}}2=($(A2)-(centerB2)$), \n0={veclen({{\mathfrak{p}}}1)}, \n1={atan2(\y1,\x1)}, \n2={atan2(\y2,\x2)}, \n3={\n2>\n1?\n2:\n2+360} in (B2) arc(\n1:\n3:\n0); }; \draw (B2) to[anticlockwise arc centered at=centerB2] (A2); }; \coordinate (A3) at (0:\R); \coordinate (B3) at (180:\R); \draw (A3) -- (B3); \path[name intersections={of=kamaanA1 and kamaanB2, by=a1b2}]; \path[name intersections={of=kamaanB1 and kamaanA2, by=b1a2}]; \node [circle, inner sep=1.5pt,fill,draw] at (a1b2) {}; \node [circle, inner sep=1.5pt,fill,draw] at (b1a2) {}; \node [circle, inner sep=1.5pt,fill,draw] at (P) {}; \node [circle, inner sep=1.5pt,fill,draw] at (Q) {}; \node [circle, inner sep=1.5pt,fill,draw] at (A1) {}; \node [circle, inner sep=1.5pt,fill,draw] at (B1) {}; \node [circle, inner sep=1.5pt,fill,draw] at (A2) {}; \node [circle, inner sep=1.5pt,fill,draw] at (B2) {}; \node [circle, inner sep=1.5pt,fill,draw] at (A3) {}; \node [circle, inner sep=1.5pt,fill,draw] at (B3) {}; \node [black] at (180+54.735:1.2\R) {\small~$F$}; \node [black] at (180+54.735:0.7\R) {\small~$FH$}; \node [black, circle, inner sep = 0pt, minimum size = 1pt, fill=white] at (0.47,.63) {\small~$H$}; \node [black, inner sep = 2pt, fill=white, right] at (27.367:.85\R) {\small~$G=GF$}; \node [black, inner sep = 1pt, fill=white] at (270:1\R) {\small~$FG$}; \end{tikzpicture} \end{gathered}$$ We view ${\mathcal{L}}[{\mathcal A}]$ as a commutative monoid with the join operation $\vee$ for the product. This makes the support map a morphism of monoids. We let ${\mathtt{H}}_{\mathrm{X}}$ denote the basis element of ${\mathbb{R}}{\mathcal{L}}[{\mathcal A}]$ associated to the flat ${\mathrm{X}}$ of ${\mathcal A}$, so that ${\mathtt{H}}_{\mathrm{X}}\cdot {\mathtt{H}}_{\mathrm{Y}}= {\mathtt{H}}_{{\mathrm{X}}\vee {\mathrm{Y}}}$. A result of Solomon @solomon67 [Theorem 1] shows that the monoid algebra ${\mathbb{R}}{\mathcal{L}}[{\mathcal A}]$ is split-semisimple. This rests on the fact that the unique complete system of orthogonal idempotents for ${\mathbb{R}}{\mathcal{L}}[{\mathcal A}]$ consists of elements ${\mathtt{Q}}_{\mathrm{X}}$ uniquely determined by $$\label{eq:H_and_Q} {\mathtt{H}}_{\mathrm{X}}= \sum_{{\mathrm{Y}}:\,{\mathrm{Y}}\geq{\mathrm{X}}}{\mathtt{Q}}_{\mathrm{Y}}\quad\text{or equivalently}\quad {\mathtt{Q}}_{\mathrm{X}}= \sum_{{\mathrm{Y}}:\,{\mathrm{Y}}\geq {\mathrm{X}}} \mu({\mathrm{X}},{\mathrm{Y}}) {\mathtt{H}}_{\mathrm{Y}}.$$ In particular, ${\mathbb{R}}{\mathcal{L}}[{\mathcal A}]$ is the maximal split-semisimple quotient of ${\mathsf{\Sigma}}[{\mathcal A}]$ via the support map and the simple modules of ${\mathsf{\Sigma}}[{\mathcal A}]$ are indexed by flats. The character $\chi_{\mathrm{X}}$ of the simple module associated with the flat ${\mathrm{X}}$ evaluated on an element $$w = \sum_F w^F {\mathtt{H}}_F$$ of ${\mathsf{\Sigma}}[{\mathcal A}]$ yields $$\label{eq:elt-char} \chi_{\mathrm{X}}(w) = \sum_{F:\,\operatorname{s}(F)\leq{\mathrm{X}}} w^F.$$ Let $t$ be a fixed scalar. An element $w$ of the Tits algebra is **characteristic of parameter $t$** if for each flat ${\mathrm{X}}$ $$\chi_{\mathrm{X}}(w) = t^{\dim({\mathrm{X}})},$$ with $\chi_{\mathrm{X}}(w)$ as in . Characteristic elements determine the characteristic polynomial of the arrangement and also determine the characteristic polynomial of the arrangements under each flat. See [@am17 Section 12.4] and [@abm19] for more information. Eulerian idempotents and diagonalization ---------------------------------------- An **Eulerian family** of ${\mathcal A}$ is a collection of idempotent and mutually orthogonal elements $\{{\mathtt{E}}_{\mathrm{X}}\}_{{\mathrm{X}}\in {\mathcal{L}}[{\mathcal A}]} \subseteq {\mathsf{\Sigma}}[{\mathcal A}]$ of the form $${\mathtt{E}}_{\mathrm{X}}= \sum_{F \,:\, \operatorname{s}(F) \geq {\mathrm{X}}} a^F {\mathtt{H}}_F,$$ with $a^F \neq 0$ for at least one $F$ with $\operatorname{s}(F) = {\mathrm{X}}$. It follows that $\{{\mathtt{E}}_{\mathrm{X}}\}_{\mathrm{X}}$ is a complete system of primitive orthogonal idempotents and that $\operatorname{s}({\mathtt{E}}_{\mathrm{X}}) = {\mathtt{Q}}_{\mathrm{X}}$ @am17 [Theorem 11.20]. That is, $${\mathtt{E}}_{\mathrm{X}}{\mathtt{E}}_{\mathrm{Y}}= \begin{cases} {\mathtt{E}}_{\mathrm{X}}& \text{if } {\mathrm{X}}= {\mathrm{Y}},\\ 0 & \text{otherwise}, \end{cases} \qquad\qquad\qquad \sum_{\mathrm{X}}{\mathtt{E}}_{\mathrm{X}}= {\mathtt{H}}_O,$$ and ${\mathtt{E}}_{\mathrm{X}}$ cannot be written as the sum of two non-trivial idempotents. \[ex:Eul\_C2\] Let ${{\mathcal{C}}}_2$ be the coordinate arrangement in ${\mathbb{R}}^2$. The following is an Eulerian family of ${{\mathcal{C}}}_2$. Observe that in this example only faces in the first quadrant have non-zero coefficients. $${\mathtt{E}}_\perp = \begin{gathered} \begin{tikzpicture} \filldraw [fill=green1, draw=white, opacity = .3] (0,0) -- (1,0) arc (0:90:1) -- cycle; \draw [<->] (-.5,0) -- (0,0) node [blue1, below left] {\small~$1$} -- (0,-.5); \draw [<->,red1] (1,0) node [right] {\small~$-1$} -- (0,0) -- (0,1) node [above] {\small~$-1$}; \node [circle, inner sep = 1.5pt, fill = blue1] at (0,0) {}; \node [color=green1!70!black] at (.8,.8) {\small~$1$}; \end{tikzpicture} \end{gathered} \qquad {\mathtt{E}}_{x=0} = \begin{gathered} \begin{tikzpicture} \filldraw [fill=green1, draw=white, opacity = .3] (0,0) -- (1,0) arc (0:90:1) -- cycle; \draw [<->] (-.5,0) -- (0,0) -- (0,-.5); \draw [->] (0,0) -- (1,0); \draw [->,red1] (0,0) -- (0,1) node [above] {\small~$1$}; \node [circle, inner sep = 1.5pt, fill = black] at (0,0) {}; \node [color=green1!70!black] at (.8,.8) {\small~$-1$}; \end{tikzpicture} \end{gathered} \qquad {\mathtt{E}}_{y=0} = \begin{gathered} \begin{tikzpicture} \filldraw [fill=green1, draw=white, opacity = .3] (0,0) -- (1,0) arc (0:90:1) -- cycle; \draw [<->] (-.5,0) -- (0,0) -- (0,-.5); \draw [->,red1] (0,0) -- (1,0) node [right] {\small~$1$}; \draw [->] (0,0) -- (0,1); \node [circle, inner sep = 1.5pt, fill = black] at (0,0) {}; \node [color=green1!70!black] at (.8,.8) {\small~$-1$}; \end{tikzpicture} \end{gathered} \qquad {\mathtt{E}}_\top = \begin{gathered} \begin{tikzpicture} \filldraw [fill=green1, draw=white, opacity = .3] (0,0) -- (1,0) arc (0:90:1) -- cycle; \draw [<->] (-.5,0) -- (0,0) -- (0,-.5); \draw [<->] (0,1) -- (0,0) -- (1,0); \node [circle, inner sep = 1.5pt, fill = black] at (0,0) {}; \node [color=green1!70!black] at (.8,.8) {\small~$1$}; \end{tikzpicture} \end{gathered}$$ A characteristic element $w$ of *non-critical*[^1] parameter $t$ uniquely determines an Eulerian family ${\mathtt{E}} = \{{\mathtt{E}}_{\mathrm{X}}\}_{\mathrm{X}}$, which satisfies $$\label{eq:char_eul_idempotent} w = \sum_{\mathrm{X}}t^{\dim({\mathrm{X}})} \rm E_{\mathrm{X}}.$$ This is a consequence of [@am17 Propositions 11.9, 12.59]. It follows that the action of such a characteristic elements $w$ on any ${\mathsf{\Sigma}}[{\mathcal A}]$-module $M$ is diagonalizable. Let $M$ be a (right) ${\mathsf{\Sigma}}[{\mathcal A}]$-module, $w \in {\mathsf{\Sigma}}[{\mathcal A}]$ be a characteristic element of non-critical parameter $t$ and $\{{\mathtt{E}}_{\mathrm{X}}\}_{\mathrm{X}}$ be the corresponding Eulerian family. Then, we have a decomposition $$\label{eq:M-decomposition} M = \bigoplus_{{\mathrm{X}}} M \cdot {\mathtt{E}}_{\mathrm{X}}$$ of vector spaces. Expression shows that $w$ acts on $M \cdot {\mathtt{E}}_{\mathrm{X}}$ by multiplication by $t^{\dim({\mathrm{X}})}$. We define $$\eta_{\mathrm{X}}(M) := \dim_{\mathbb{R}}(M \cdot {\mathtt{E}}_{\mathrm{X}}).$$ The character $\chi_M: {\mathsf{\Sigma}}[{\mathcal A}] \rightarrow {\mathbb{R}}$ of $M$ factors through ${\mathbb{R}}{\mathcal{L}}[{\mathcal A}]$: $$\begin{tikzcd}[row sep=small] {{\mathsf{\Sigma}}[{\mathcal A}]} \arrow[rd, "\chi_M"] \arrow[d, "\operatorname{s}"'] & \\ {{\mathbb{R}}{\mathcal{L}}[{\mathcal A}]} \arrow[r, "\overline{\chi}_M"', dashed] & {\mathbb{R}}\end{tikzcd}$$ Thus, $\eta_{\mathrm{X}}(M) = \dim_{\mathbb{R}}(M \cdot {\mathtt{E}}_{\mathrm{X}}) = \chi_M({\mathtt{E}}_{\mathrm{X}}) = {\overline{\chi}}_M({\mathtt{Q}}_{\mathrm{X}})$ is independent of the characteristic element $w$. Furthermore, using relations and the linearity of ${\overline{\chi}}_M$ we deduce $$\begin{gathered} \label{eq:compute_eta} \eta_{\mathrm{X}}(M) = {\overline{\chi}}_M({\mathtt{Q}}_{\mathrm{X}}) = \sum_{{\mathrm{Y}}\geq {\mathrm{X}}} \mu({\mathrm{X}},{\mathrm{Y}}) {\overline{\chi}}_M({\mathtt{H}}_{\mathrm{Y}})\\ = \sum_{{\mathrm{Y}}\geq {\mathrm{X}}} \mu({\mathrm{X}},{\mathrm{Y}}) \chi_M({\mathtt{H}}_{F_{\mathrm{Y}}}) = \sum_{{\mathrm{Y}}\geq {\mathrm{X}}} \mu({\mathrm{X}},{\mathrm{Y}}) \dim_{\mathbb{R}}(M \cdot {\mathtt{H}}_{F_{\mathrm{Y}}})\end{gathered}$$ where $F_{\mathrm{Y}}\in {\Sigma}[{\mathcal A}]$ is such that $\operatorname{s}(F_{\mathrm{Y}}) = {\mathrm{Y}}$. The last equality follows since ${\mathtt{H}}_{F_{\mathrm{Y}}}$ is an idempotent element, and thus $\chi_M({\mathtt{H}}_{F_{\mathrm{Y}}}) = \dim_{\mathbb{R}}(M \cdot {\mathtt{H}}_{F_{\mathrm{Y}}})$. Moreover, the number of composition factors $M_{i+1}/M_i$ isomorphic to the simple module indexed by ${\mathrm{X}}$ in a composition series $ 0 \subset M_1 \subset M_2 \subset \dots \subset M_k = M $ of $M$ is precisely $\eta_{\mathrm{X}}(M)$. See [@am17 Section 9.5 and Theorem D.37] for details. The McMullen module of a hyperplane arrangement {#s:module} =============================================== Fix a hyperplane arrangement ${\mathcal A}$ in $V$. Take a normal vector $v_{{\mathrm{H}}}$ for each hyperplane ${{\mathrm{H}}}\in {\mathcal A}$, and consider the zonotope (Minkowski sum of segments): $$\label{eq:zon_A} {{\mathfrak{z}}}= \sum_{{{\mathrm{H}}}} \operatorname{Conv}\{ {\bf 0} , v_{{\mathrm{H}}}\}.$$ Its normal fan ${\Sigma}_{{\mathfrak{z}}}$ coincides with the collection of faces ${\Sigma}[{\mathcal A}]$ of the arrangement ${\mathcal A}$. We say that a polytope ${{\mathfrak{q}}}$ is a **generalized zonotope** of ${\mathcal A}$ it is a deformation of ${{\mathfrak{z}}}$. We now consider the algebra $\Pi({{\mathfrak{z}}})$ introduced in Section \[ss:subalgebra\_polytope\]. It is generated by the classes of generalized zonotopes of ${\mathcal A}$. It only depends on the arrangement ${\mathcal A}$ and not on the particular choice of normal vectors $v_{{\mathrm{H}}}$. We start with a simple yet interesting result. Recall the morphism $\psi_{{\mathfrak{f}}}: \Pi({{\mathfrak{z}}}) \rightarrow \Pi({{\mathfrak{f}}})$ defined for every face ${{\mathfrak{f}}}\leq {{\mathfrak{z}}}$ in , it sends the class $[{{\mathfrak{q}}}]$ of a generalized zonotope of ${\mathcal A}$ to $[{{\mathfrak{q}}}_v]$ where $v \in V$ is any vector such that ${{\mathfrak{f}}}= {{\mathfrak{z}}}_v$. \[p:zonotope\_surjective\] Let ${{\mathfrak{z}}}$ be a zonotope, and ${{\mathfrak{f}}}$ a face of ${{\mathfrak{z}}}$. Then, the morphism $\psi_{{\mathfrak{f}}}$ is surjective. Let ${{\mathfrak{f}}}$ be a face of ${{\mathfrak{z}}}$, $F \in {\Sigma}[{\mathcal A}]$ be its normal cone, and ${\mathrm{X}}= \operatorname{s}(F)$ be the flat orthogonal to ${{\mathfrak{f}}}$. It follows from that ${{\mathfrak{f}}}= {{\mathfrak{z}}}_F$ is a translate of $${{\mathfrak{z}}}_{\mathrm{X}}:= \sum_{{{\mathrm{H}}}\,:\, {{\mathrm{H}}}\supseteq {\mathrm{X}}} \operatorname{Conv}\{ {\bf 0} , v_{{\mathrm{H}}}\}.$$ In particular, ${{\mathfrak{f}}}$ is a Minkowski summand of ${{\mathfrak{z}}}$. Being a Minkowski summand is a transitive relation. Hence, any generator $[{{\mathfrak{q}}}]$ of $\Pi({{\mathfrak{f}}})$ is also in $\Pi({{\mathfrak{z}}})$. That is, $\Pi({{\mathfrak{f}}})$ is a subalgebra of $\Pi({{\mathfrak{z}}})$. Moreover, if $v \in \operatorname{relint}(F)$ and ${{\mathfrak{q}}}$ is a Minkowski summand of ${{\mathfrak{f}}}$, then ${{\mathfrak{q}}}_v = {{\mathfrak{q}}}$. Therefore, the composition $ \Pi({{\mathfrak{f}}}) \hookrightarrow \Pi({{\mathfrak{z}}}) \xrightarrow{\psi_{{\mathfrak{f}}}} \Pi({{\mathfrak{f}}}) $ is the identity map. Consequently, the morphism $\psi_{{\mathfrak{f}}}$ is surjective. Compare with Theorem \[t:simple\_surjective\] and note that we do not assume the zonotope ${{\mathfrak{z}}}$ to be simple. For an arbitrary polytope ${{\mathfrak{p}}}$ and a face ${{\mathfrak{f}}}$ of ${{\mathfrak{p}}}$, there is no natural morphism $\Pi({{\mathfrak{f}}}) \rightarrow \Pi({{\mathfrak{p}}})$, unlike in the previous case. This is a particular property of zonotopes. Indeed, a polytope ${{\mathfrak{p}}}$ is a zonotope if and only if every face ${{\mathfrak{f}}}\leq {{\mathfrak{p}}}$ is a Minkowski summand of ${{\mathfrak{p}}}$, see [@blswz Proposition 2.2.14] for a proof. Let $F$ be a face of ${\mathcal A}$ and ${{\mathfrak{f}}}= {{\mathfrak{z}}}_F$ the corresponding face of ${{\mathfrak{z}}}$. We define right multiplication by the basis element ${\mathtt{H}}_F \in {\mathsf{\Sigma}}[{\mathcal A}]$ on $\Pi({{\mathfrak{z}}})$ as the projection $\psi_{{\mathfrak{f}}}: \Pi({{\mathfrak{z}}}) \rightarrow \Pi({{\mathfrak{f}}}) \subseteq \Pi({{\mathfrak{z}}})$. \[t:mod\_str\] The algebra $\Pi({{\mathfrak{z}}})$ is a right ${\mathsf{\Sigma}}[{\mathcal A}]$-module under the action above. Explicitly, for a generator $[{{\mathfrak{q}}}]$ of $\Pi({{\mathfrak{z}}})$ and a basis element ${\mathtt{H}}_F$ of ${\mathsf{\Sigma}}[{\mathcal A}]$, $$[{{\mathfrak{q}}}] \cdot {\mathtt{H}}_F := [{{\mathfrak{q}}}_v], \qquad \text{where }v \in \operatorname{relint}(F).$$ Moreover, each graded component $\Xi_r({{\mathfrak{z}}})$ is a ${\mathsf{\Sigma}}[{\mathcal A}]$-submodule and the action of basis elements $\{{\mathtt{H}}_F\}_F$ on $\Pi({{\mathfrak{z}}})$ is by (graded) algebra endomorphisms. The zero vector belongs to the central face $O$, so the action is clearly unital. Associativity follows from the following fact about polytopes [@grunbaum03convex Section 3.1.5]. If ${{\mathfrak{q}}}\subseteq V$ is a polytope and $v,w \in V$, then $ ({{\mathfrak{q}}}_v)_w = {{\mathfrak{q}}}_{v + \lambda w} $ for any small enough $\lambda > 0$. Similarly, the definition of the Tits product is such that if $v \in \operatorname{relint}(F)$ and $w \in \operatorname{relint}(G)$, then $v + \lambda w \in \operatorname{relint}(FG)$ for any small enough $\lambda > 0$. Hence, $$([{{\mathfrak{q}}}] \cdot {\mathtt{H}}_F) \cdot {\mathtt{H}}_G = [({{\mathfrak{q}}}_v)_w] = [{{\mathfrak{q}}}_{v + \lambda w}] = [{{\mathfrak{q}}}] \cdot {\mathtt{H}}_{FG}.$$ It follows that this product gives $\Pi({{\mathfrak{z}}})$ the structure of a right ${\mathsf{\Sigma}}[{\mathcal A}]$-module. The second statement follows directly from Theorem \[t:direction\_morphism\] and the characterization of the graded components $\Xi_r$ in . Indeed, for any $x \in \Xi_r({{\mathfrak{z}}})$ and $\lambda > 0$, $$\delta_\lambda(x \cdot {\mathtt{H}}_F) = \delta_\lambda(x) \cdot {\mathtt{H}}_F = \lambda^r x \cdot {\mathtt{H}}_F = \lambda^r (x \cdot {\mathtt{H}}_F),$$ thus $x \cdot {\mathtt{H}}_F \in \Xi_r({{\mathfrak{z}}})$. Simultaneous diagonalization ---------------------------- Let $\lambda > 0$ and let $w \in {\mathsf{\Sigma}}[{\mathcal A}]$ be a characteristic element of non-critical parameter $t$. We know that the dilation morphism $\delta_\lambda$ and the action of $w$ are diagonalizable. Moreover, since $\delta_\lambda$ and the action of $w$ commute, they are simultaneously diagonalizable. A natural question is to determine the eigenvalues of $\delta_\lambda$ and of the action of $w$ in their simultaneous eigenspaces. We completely answer this question in the case of the Coxeter arrangements of type A and B in the next two sections. The following result holds in the general case. Let $x \in \Pi({{\mathfrak{z}}})$ be a (nonzero) simultaneous eigenvector for $\delta_\lambda$ and $w$ with eigenvalues $\lambda^r$ and $t^k$, respectively. Then, $r + k \leq d$. Let $\{{\mathtt{E}}_{\mathrm{X}}\}_{\mathrm{X}}$ be the Eulerian family associated to $w$. Using the characterization of the graded components $\Xi_r$ as the eigenspaces of $\delta_\lambda$, and the decomposition of ${\mathsf{\Sigma}}[{\mathcal A}]$-modules in , we deduce that the common eigenspace for $\delta_\lambda$ and $w$ with the given eigenvalues is $\bigoplus_{\mathrm{X}}\Xi_r({{\mathfrak{z}}}) \cdot {\mathtt{E}}_{\mathrm{X}}$, where the sum is over all $k$-dimensional flats of ${\mathcal A}$. Without loss of generality, we assume that $x \in \Xi_r({{\mathfrak{z}}}) \cdot {\mathtt{E}}_{\mathrm{X}}$ for a single $k$-dimensional flat ${\mathrm{X}}$. Proposition \[p:zonotope\_surjective\] implies that $\Xi_r({{\mathfrak{z}}}) \cdot {\mathtt{H}}_F = \Xi_r({{\mathfrak{z}}}_{\mathrm{Y}})$, where $F \in {\Sigma}[{\mathcal A}]$ is any face of support ${\mathrm{Y}}$. Hence, formula yields $$\label{eq:eta_general_arr} \eta_{\mathrm{X}}(\Xi_r({{\mathfrak{z}}})) = \sum_{{\mathrm{Y}}\geq {\mathrm{X}}} \mu({\mathrm{X}},{\mathrm{Y}}) \dim_{\mathbb{R}}(\Xi_r({{\mathfrak{z}}}_{\mathrm{Y}})).$$ If $k > d-r$, then $\dim({{\mathfrak{z}}}_{\mathrm{Y}}) = d - \dim({\mathrm{Y}}) \leq d - k < r$ and $\dim_{\mathbb{R}}(\Xi_r({{\mathfrak{z}}}_{\mathrm{Y}})) = 0$ for any ${\mathrm{Y}}$ in the sum. So, in this case, $\dim_{\mathbb{R}}(\Xi_r({{\mathfrak{z}}}) \cdot {\mathtt{E}}_{\mathrm{X}}) = \eta_{\mathrm{X}}(\Xi_r({{\mathfrak{z}}})) = 0$. This contradicts that $x \in \Xi_r({{\mathfrak{z}}}) \cdot {\mathtt{E}}_{\mathrm{X}}$ is a nonzero element. Therefore, $r + k \leq d$. If in addition ${\mathcal A}$ is a simplicial arrangement, like in the case of reflection arrangements, then ${{\mathfrak{z}}}$ and each of its faces are simple polytopes. In that case, Theorem \[t:simple\_h\_dimension\] allows us to replace $\dim_{\mathbb{R}}(\Xi_r({{\mathfrak{z}}}_{\mathrm{Y}}))$ by $h_r({{\mathfrak{z}}}_{\mathrm{Y}})$ in expression . Multiplying by $z^r$ and taking the sum over all values of $r$, we obtain $$\label{eq:eta_simplicial_arr} \sum_r \eta_{\mathrm{X}}(\Xi_r({{\mathfrak{z}}})) z^r = \sum_{{\mathrm{Y}}\geq {\mathrm{X}}} \mu({\mathrm{X}},{\mathrm{Y}}) h({{\mathfrak{z}}}_{\mathrm{Y}},z).$$ First example: the cube and the coordinate arrangement ------------------------------------------------------ Let ${{\mathcal{C}}}_d$ be the coordinate arrangement in ${\mathbb{R}}^d$. It consists of the $d$ coordinate hyperplanes $x_i = 0$ for $i=1,\dots,d$. We identify the lattice of flats ${\mathcal{L}}[{{\mathcal{C}}}_d]$ with the (opposite) boolean lattice $2^{[d]}$ in the following manner: $$S \subseteq [d] \longleftrightarrow {\mathrm{X}}_S := \bigcap_{i \in S} \{x \,:\, x_i = 0\}.$$ Observe that ${\mathrm{X}}_S \leq {\mathrm{X}}_T$ if and only if $T \subseteq S$, and in this case $\mu_{\mathcal{L}}({\mathrm{X}}_S,{\mathrm{X}}_T) = \mu_{2^{[d]}}(T,S) = (-1)^{|S \setminus T|}$. The $d$-cube ${{\mathfrak{c}}}_d = [0,1]^d$ a zonotope of ${{\mathcal{C}}}_d$. It is the Minkowski sum of the $d$ line segments ${{\mathfrak{l}}}_i := \operatorname{Conv}\{{\bf 0},e_i\}$ for $i=1,\dots,d$. It is a simple polytope with $h$-polynomial $h({{\mathfrak{c}}}_d,z) = (1+z)^d$. Furthermore, for any $S \subseteq [d]$ we have $$({{\mathfrak{c}}}_d)_{{\mathrm{X}}_S} = \sum_{i \in S} {{\mathfrak{l}}}_i \cong {{\mathfrak{c}}}_{|S|}.$$ Let us consider the right ${\mathsf{\Sigma}}[{{\mathcal{C}}}_d]$-module $\Pi({{\mathfrak{c}}}_d)$. For a flat ${\mathrm{X}}_S$, formula yields $$\sum_r \eta_{{\mathrm{X}}_S}(\Xi_r({{\mathfrak{c}}}_d)) z^r = \sum_{T \subseteq S} \mu({\mathrm{X}}_S,{\mathrm{X}}_T) h({{\mathfrak{c}}}_{|T|},z) = \sum_{T \subseteq S} (-1)^{|S \setminus T|} (1+z)^{|T|} = z^{|S|}.$$ Hence, $$\eta_{{\mathrm{X}}_S}(\Xi_r({{\mathfrak{c}}}_d)) = \begin{cases} 1 & \text{if } |S| = r,\\ 0 & \text{otherwise}. \end{cases}$$ In particular, a series decomposition of $\Xi_r({{\mathfrak{c}}}_d)$ contains exactly one copy of the simple module indexed by ${\mathrm{X}}_S$ for every $S \in {[d] \choose r}$. Let us now consider the characteristic element $\gamma_t \in {\mathsf{\Sigma}}[{{\mathcal{C}}}_d]$ introduced in [@abm19 Section 5.3] for $t \neq 1$. It is defined by $$\gamma_t = \sum_F \gamma_t^F {\mathtt{H}}_F, \quad \text{where} \quad \gamma_t^F = \begin{cases} (t-1)^{\dim(F)} & \text{ if~$F$ lies in the first orthant,} \\ 0 & \text{ otherwise.} \end{cases}$$ For each $S \subseteq [d]$, let $F_S$ be the intersection of the first orthant with ${\mathrm{X}}_S$, it is a face of ${{\mathcal{C}}}_d$. We have $\operatorname{s}(F_S) = {\mathrm{X}}_S$ and $T \subseteq S$ if and only if $F_S \leq F_T$. A simple computation shows that the Eulerian family corresponding to the characteristic element $\gamma_t$ is determined by $${\mathtt{E}}_{{\mathrm{X}}_S} = \sum_{T \subseteq S} (-1)^{|S \setminus T|} {\mathtt{H}}_{F_T}.$$ In dimension 2, this is the Eulerian family in Example \[ex:Eul\_C2\]. For each $S \subseteq [d]$, define $$y_S = \prod_{i \in S} \log[{{\mathfrak{l}}}_i] \in \Pi({{\mathfrak{c}}}_d).$$ Example \[ex:prod\_intervals\] shows that $y_S$ is a nonzero element of $\Pi({{\mathfrak{c}}}_d)$. We claim that $\{y_S\}_{S\subseteq [d]}$ is a basis of simultaneous eigenvectors of $\Pi({{\mathfrak{c}}}_d)$. Explicitly, $y_S$ is an eigenvector for the action of $\gamma_t$ of eigenvalue $t^{d-|S|}$, and for the action of $\delta_\lambda$ of eigenvalue $\lambda^{|S|}$ ($\lambda > 0$). The second statement is clear, since $\log[{{\mathfrak{l}}}_i] \in \Xi_1({{\mathfrak{c}}}_d)$. Moreover, using that $\log[{{\mathfrak{l}}}_i] = [{{\mathfrak{l}}}_i] - 1$, we have $$y_S = \prod_{i \in S} ([{{\mathfrak{l}}}_i] - 1) = \sum_{T \subseteq S} (-1)^{|S \setminus T|} [{{\mathfrak{c}}}_{{\mathrm{X}}_T}].$$ On the other hand, observe that $$[{{\mathfrak{c}}}_{{\mathrm{X}}_S}] \cdot {\mathtt{E}}_{{\mathrm{X}}_S} = \sum_{T \subseteq S} (-1)^{|S \setminus T|} [{{\mathfrak{c}}}_{{\mathrm{X}}_S}] \cdot {\mathtt{H}}_{F_T} = \sum_{T \subseteq S} (-1)^{|S \setminus T|} [{{\mathfrak{c}}}_{{\mathrm{X}}_T}] = y_S.$$ Therefore, $$y_S \in \Xi_r({{\mathfrak{c}}}_d) \cap (\Pi({{\mathfrak{c}}}_d) \cdot {\mathtt{E}}_{{\mathrm{X}}_S}) = \Xi_r({{\mathfrak{c}}}_d) \cdot {\mathtt{E}}_{{\mathrm{X}}_S}.$$ The claim follows since $\dim({\mathrm{X}}_S) = d - |S|$. The McMullen module of a product of arrangements ------------------------------------------------ The Cartesian product of two arrangements ${\mathcal A}$ in $V$ and ${\mathcal A}'$ in $W$ is the following collection of hyperplanes in $V \oplus W$: $${\mathcal A}\times {\mathcal A}' = \{ {{\mathrm{H}}}\oplus W \,:\, {{\mathrm{H}}}\in {\mathcal A}\} \cup \{ V \oplus {{\mathrm{H}}}\,:\, {{\mathrm{H}}}\in {\mathcal A}' \}.$$ One can easily verify that ${\Sigma}[{\mathcal A}\times {\mathcal A}'] \cong {\Sigma}[{\mathcal A}] \times {\Sigma}[{\mathcal A}']$ as monoids. Hence, ${\mathsf{\Sigma}}[{\mathcal A}\times {\mathcal A}'] \cong {\mathsf{\Sigma}}[{\mathcal A}] \otimes {\mathsf{\Sigma}}[{\mathcal A}']$. In fact, it is also true that $$\Pi({{\mathfrak{z}}}\times {{\mathfrak{z}}}') \cong \Pi({{\mathfrak{z}}}) \otimes \Pi({{\mathfrak{z}}}'),$$ where ${{\mathfrak{z}}}$ and ${{\mathfrak{z}}}'$ are zonotopes of ${\mathcal A}$ and ${\mathcal A}'$, respectively, and therefore ${{\mathfrak{z}}}\times {{\mathfrak{z}}}'$ is a zonotope of ${\mathcal A}\times {\mathcal A}'$. Indeed, every generalized zonotope of ${\mathcal A}\times {\mathcal A}'$ is the Cartesian product of generalized zonotopes of ${\mathcal A}$ and ${\mathcal A}'$. The corresponding isomorphism is induced by $$\begin{array}{CCC} \Pi({{\mathfrak{z}}}) \otimes \Pi({{\mathfrak{z}}}') & \rightarrow & \Pi({{\mathfrak{z}}}\times {{\mathfrak{z}}}')\\ {[{{\mathfrak{p}}}]} \otimes [{{\mathfrak{q}}}] & \mapsto & [{{\mathfrak{p}}}\times {{\mathfrak{q}}}] \end{array}$$ The fact that this map is well-defined and a morphism of ${\mathsf{\Sigma}}[{\mathcal A}\times {\mathcal A}']$-modules follows from the ideas in Section \[ss:mc\]. The module of generalized permutahedra {#s:braid} ====================================== Generalized permutahedra are the deformations of the standard permutahedron $\pi_d \subseteq {\mathbb{R}}^d$. Edmonds first introduced them under a different name in [@edmonds], where he studied their relation to submodular functions and optimization. For a thorough study of the combinatorics of these polytopes, see [@aa17; @postnikov09; @prw08faces]. In this section, we study the algebra $\Pi(\pi_d)$ of generalized permutahedra and its structure as a module over the Tits algebra of the braid arrangement ${\mathcal A}_d$. We begin with a brief review of the braid arrangement, its relation with the symmetric group, and some statistics on permutations. The braid arrangement --------------------- The <span>braid arrangement</span> ${\mathcal A}_d$ in ${\mathbb{R}}^d$ consists of the diagonal hyperplanes $x_i=x_j$ for $1\leq i<j\leq d$. Its central face is the line perpendicular to the hyperplane $x_1+\cdots+x_d=0$. Intersecting ${\mathcal A}_d$ with this hyperplane and a sphere around the origin we obtain the *Coxeter complex of type $A_{d-1}$*. The pictures below show the cases $d=3$ and $4$. $$\begin{gathered} \begin{tikzpicture}[scale=.6] \newdimen\R \R=2.5cm \draw (0,0) circle (\R); \node [circle, inner sep=1.5pt,fill=magenta,draw] at (30:\R) {}; \node [circle, inner sep=1.5pt,fill=cyan,draw] at (90:\R) {}; \node [circle, inner sep=1.5pt,fill=magenta,draw] at (150:\R) {}; \node [circle, inner sep=1.5pt,fill=cyan,draw] at (210:\R) {}; \node [circle, inner sep=1.5pt,fill=magenta,draw] at (270:\R) {}; \node [circle, inner sep=1.5pt,fill=cyan,draw] at (330:\R) {}; \end{tikzpicture} \end{gathered} \hspace*{.2\linewidth} \begin{gathered} \begin{tikzpicture}[scale=.6] \newdimen\R \R=2.5cm \draw (0,0) circle (\R); \coordinate (P) at (-1,0); \coordinate (Q) at (1,0); \coordinate (A1) at (54.735:\R); \coordinate (B1) at (180+54.735:\R); { { \coordinate (middle1) at ($(A1)!.5!(P)$); \coordinate (middle2) at ($(P)!.5!(B1)$); \coordinate (aux1) at ($(middle1)!1!90:(P)$); \coordinate (aux2) at ($(middle2)!1!90:(B1)$); \coordinate (centerA1) at ($(intersection of middle1--aux1 and middle2--aux2)$); \draw[,draw=none,name path=kamaanA1] let {{\mathfrak{p}}}1=($(A1)-(centerA1)$), {{\mathfrak{p}}}2=($(B1)-(centerA1)$), \n0={veclen({{\mathfrak{p}}}1)}, \n1={atan2(\y1,\x1)}, \n2={atan2(\y2,\x2)}, \n3={\n2>\n1?\n2:\n2+360} in (A1) arc(\n1:\n3:\n0); }; \draw (A1) to[anticlockwise arc centered at=centerA1] (B1); }; { { \coordinate (middle1) at ($(B1)!.5!(Q)$); \coordinate (middle2) at ($(Q)!.5!(A1)$); \coordinate (aux1) at ($(middle1)!1!90:(Q)$); \coordinate (aux2) at ($(middle2)!1!90:(A1)$); \coordinate (centerB1) at ($(intersection of middle1--aux1 and middle2--aux2)$); \draw[,draw=none,name path=kamaanB1] let {{\mathfrak{p}}}1=($(B1)-(centerB1)$), {{\mathfrak{p}}}2=($(A1)-(centerB1)$), \n0={veclen({{\mathfrak{p}}}1)}, \n1={atan2(\y1,\x1)}, \n2={atan2(\y2,\x2)}, \n3={\n2>\n1?\n2:\n2+360} in (B1) arc(\n1:\n3:\n0); }; \draw (B1) to[anticlockwise arc centered at=centerB1] (A1); }; \coordinate (A2) at (180-54.735:\R); \coordinate (B2) at (-54.735:\R); { { \coordinate (middle1) at ($(A2)!.5!(P)$); \coordinate (middle2) at ($(P)!.5!(B2)$); \coordinate (aux1) at ($(middle1)!1!90:(P)$); \coordinate (aux2) at ($(middle2)!1!90:(B2)$); \coordinate (centerA2) at ($(intersection of middle1--aux1 and middle2--aux2)$); \draw[,draw=none,name path=kamaanA2] let {{\mathfrak{p}}}1=($(A2)-(centerA2)$), {{\mathfrak{p}}}2=($(B2)-(centerA2)$), \n0={veclen({{\mathfrak{p}}}1)}, \n1={atan2(\y1,\x1)}, \n2={atan2(\y2,\x2)}, \n3={\n2>\n1?\n2:\n2+360} in (A2) arc(\n1:\n3:\n0); }; \draw (A2) to[anticlockwise arc centered at=centerA2] (B2); }; { { \coordinate (middle1) at ($(B2)!.5!(Q)$); \coordinate (middle2) at ($(Q)!.5!(A2)$); \coordinate (aux1) at ($(middle1)!1!90:(Q)$); \coordinate (aux2) at ($(middle2)!1!90:(A2)$); \coordinate (centerB2) at ($(intersection of middle1--aux1 and middle2--aux2)$); \draw[,draw=none,name path=kamaanB2] let {{\mathfrak{p}}}1=($(B2)-(centerB2)$), {{\mathfrak{p}}}2=($(A2)-(centerB2)$), \n0={veclen({{\mathfrak{p}}}1)}, \n1={atan2(\y1,\x1)}, \n2={atan2(\y2,\x2)}, \n3={\n2>\n1?\n2:\n2+360} in (B2) arc(\n1:\n3:\n0); }; \draw (B2) to[anticlockwise arc centered at=centerB2] (A2); }; \coordinate (A3) at (0:\R); \coordinate (B3) at (180:\R); \draw (A3) -- (B3); \path[name intersections={of=kamaanA1 and kamaanB2, by=a1b2}]; \path[name intersections={of=kamaanB1 and kamaanA2, by=b1a2}]; \node [circle, inner sep=1.5pt,fill=magenta,draw] at (a1b2) {}; \node [circle, inner sep=1.5pt,fill=magenta,draw] at (b1a2) {}; \node [circle, inner sep=1.5pt,fill=orange,draw] at (P) {}; \node [circle, inner sep=1.5pt,fill=cyan,draw] at (Q) {}; \node [circle, inner sep=1.5pt,fill=orange,draw] at (A1) {}; \node [circle, inner sep=1.5pt,fill=cyan,draw] at (B1) {}; \node [circle, inner sep=1.5pt,fill=cyan,draw] at (A2) {}; \node [circle, inner sep=1.5pt,fill=orange,draw] at (B2) {}; \node [circle, inner sep=1.5pt,fill=magenta,draw] at (A3) {}; \node [circle, inner sep=1.5pt,fill=magenta,draw] at (B3) {}; \end{tikzpicture} \end{gathered}$$ Flats and faces of ${\mathcal A}_d$ are in one-to-one correspondence with set partitions and set compositions of $[d] : = \{1,2,\dots,d\}$, respectively. We proceed to review this correspondence. A **weak set partition** of a finite set $I$ is a collection ${\mathrm{X}}= \{S_1,\dots,S_k\}$ of pairwise disjoint subsets $S_i \subseteq I$ such that $I = S_1 \cup \dots \cup S_k$. The subsets $S_i$ are the **blocks** of ${\mathrm{X}}$. A **set partition** is a weak set partition with no empty blocks. We write ${\mathrm{X}}\vdash I$ to denote that ${\mathrm{X}}$ is a set partition of $I$. Given a partition ${\mathrm{X}}\vdash [d]$, the corresponding flat of ${\mathcal A}_d$ is the intersection of the hyperplanes $x_a = x_b$ for all $a,b$ that belong to the same block of ${\mathrm{X}}$, as illustrated in the following example for $d=8$: $$x_1 = x_3, \quad x_2 = x_5 = x_6 = x_8 \qquad \longleftrightarrow \qquad \{13,2568,4,7\},$$ where we write $13$ to abbreviate the set $\{1,3\}$, $2568$ to abbreviate the set $\{2,5,6,8\}$ and so on. We use ${\mathrm{X}}$ to denote both a flat of ${\mathcal A}_d$ and the corresponding set partition of $[d]$. Observe that $\dim({\mathrm{X}})$ is precisely the number of blocks of ${\mathrm{X}}$ as a partition. The partial order relation of ${\mathcal{L}}[{\mathcal A}_d]$ becomes the ordering by refinement of set partitions. That is, ${\mathrm{X}}\leq {\mathrm{Y}}$ if the set partition ${\mathrm{X}}$ is **refined by** ${\mathrm{Y}}$. Recall that ${\mathrm{X}}$ is refined by ${\mathrm{Y}}$ if every block of ${\mathrm{X}}$ is the union of some blocks in ${\mathrm{Y}}$. For instance, $\{12345678\} \leq \{13,2568,4,7\} \leq \{1,28,3,4,56,7\}$. If $S \subseteq I$ is a union of blocks of a partition ${\mathrm{X}}\vdash I$, we let ${\mathrm{X}}|_S \vdash S$ denote the partition of $S$ formed by the blocks of ${\mathrm{X}}$ whose union is $S$. Let ${\mathrm{X}}= \{S_1,\dots,S_k\} \vdash [d]$ be a partition. Then, the choice of ${\mathrm{Y}}\geq {\mathrm{X}}$ is equivalent to the choice of partitions ${\mathrm{Y}}|_{S_i} \vdash S_i$ for each block of ${\mathrm{X}}$. With ${\mathrm{X}}$ and ${\mathrm{Y}}$ as above, the Möbius function of ${\mathcal{L}}[{\mathcal A}_d]$ is determined by $$\label{eq:mu_prod_A} \mu(\perp,{\mathrm{X}}) = (-1)^{k-1} (k-1)! {\qquad\text{and}\qquad}\mu({\mathrm{X}},{\mathrm{Y}}) = \mu(\perp,{\mathrm{Y}}|_{S_1}) \dots \mu(\perp,{\mathrm{Y}}|_{S_k}),$$ where in each factor, $\perp$ denotes the minimum partition of $S_i$. A **set composition** of $I$ is an ordered set partition $F = (S_1,\dots,S_k)$. We write $F \vDash I$ to denote that $F$ is a composition of $I$, and let $\operatorname{s}(F) \vdash I$ be the underlying (unordered) set partition. Given a set composition $F \vDash [d]$, the corresponding face of ${\mathcal A}_d$ is obtained by intersecting the hyperplanes $x_a = x_b$ whenever $a,b$ are in the same block of $F$, and the halfspaces $x_a \geq x_b$ whenever the block containing $a$ precedes the block containing $b$. For example, $$x_1 = x_3 \geq x_4 \geq x_2 = x_5 = x_6 = x_8 \geq x_7 \qquad \longleftrightarrow \qquad (13,4,2568,7).$$ The symmetric group and the Eulerian polynomial ----------------------------------------------- The symmetric group ${{\mathfrak{S}}}_d$ is the group of *permutations* $\sigma : [d] \rightarrow [d]$ under composition. It is the Coxeter group corresponding to the braid arrangement. It acts on ${\mathbb{R}}^d$ by permuting coordinates: $$\sigma(x_1,x_2,\dots,x_d) = (x_{\sigma(1)},x_{\sigma(2)},\dots,x_{\sigma(d)}).$$ For a permutation $\sigma \in {{\mathfrak{S}}}_d$, we let $\operatorname{s}(\sigma)$ denote the **subspace of points fixed by the action** of $\sigma$; it is a flat of ${\mathcal A}_d$. In
{'source': 'arXiv_out/2009'}