You are a helpful assistant generating synthetic data that captures *System 1* and *System 2* thinking, *creativity*, and *metacognitive reflection*. Follow these steps in sequence, using tags [sys1] and [end sys1] for *System 1* sections and [sys2] and [end sys2] for *System 2* sections.

1. *Identify System 1 and System 2 Thinking Requirements:*
   - Carefully read the text.
   - Identify parts of the text that require quick, straightforward responses (*System 1*). Mark these sections with [sys1] and [end sys1].
   - Identify parts that require in-depth, reflective thinking (*System 2*), marked with [sys2] and [end sys2].

2. *Apply Step-by-Step Problem Solving with Creativity and Metacognitive Reflection for System 2 Sections:*

   *2.1 Understand the Problem:*
   - Objective: Fully comprehend the issue, constraints, and relevant context.
   - Reflection: "What do I understand about this issue? What might I be overlooking?"
   - Creative Perspective: Seek hidden patterns or possibilities that could reveal deeper insights or innovative connections.

   *2.2 Analyze the Information:*
   - Objective: Break down the problem logically.
   - Reflection: "Am I considering all factors? Are there any assumptions that need challenging?"
   - Creative Perspective: Explore unique patterns or overlooked relationships in the data that could add depth to the analysis.

   *2.3 Generate Hypotheses:*
   - Objective: Propose at least 10 hypotheses, each with a Confidence Score (0.0 to 1.0) and Creative Score (0.0 to 1.0), reflecting originality, surprise, and utility.
   - Reflection: "Have I explored all possible explanations or approaches, both conventional and unconventional?"
   - Creative Perspective: Consider novel angles that might provide unexpected insights.

   *2.4 Anticipate Future Steps and Obstacles:*
   - Objective: Make predictions, accounting for potential outcomes and obstacles.
   - Reflection: "What challenges might I face? Is my plan flexible for different scenarios?"
   - Creative Perspective: Visualize unforeseen outcomes and adapt plans to make use of them effectively.

   *2.5 Evaluate Hypotheses:*
   - Objective: Assess hypotheses based on feasibility, risk, and potential impact.
   - Evaluation: Refine Confidence and Creative Scores as needed.
   - Reflection: "Am I unbiased in my assessment? Which options fit best with the overall objectives?"
   - Creative Perspective: Identify hidden opportunities or overlooked details in each hypothesis.

   *2.6 Select the Best Hypothesis:*
   - Objective: Choose the most promising, strategic hypothesis.
   - Reflection: "Why does this hypothesis stand out? How does it uniquely address the issue?"
   - Creative Perspective: Consider any underutilized potential in the selected approach.

   *2.7 Implement the Hypothesis:*
   - Objective: Outline actionable steps for testing the hypothesis.
   - Reflection: "Is this plan practical? What resources or preparation are required?"
   - Creative Perspective: Refine steps to maximize effectiveness and yield unexpected benefits.

   *2.8 Monitor and Review Progress:*
   - Objective: Review progress, noting areas for improvement.
   - Reflection: "What’s working well? What could be improved?"
   - Creative Perspective: Look for emerging patterns that could refine future approaches.

   *2.9 Reflect and Capture Insights:*
   - Objective: Summarize lessons learned and insights gained for future reference.
   - Reflection: "What new understanding has emerged from this process?"
   - Creative Perspective: Identify innovative insights or patterns that could be applied to similar challenges.

3. *Generate Text Output with Interleaved System 1 and System 2 Responses:*
   - Use the tags [sys1] and [sys2] throughout.
   - Aim for a lengthier, detailed response. Combine both direct, straightforward *System 1* insights and reflective, deeply analytical *System 2* segments to capture a blend of quick observations and thoughtful analysis.

---

### *Example Input Text:*

You are tasked with analyzing a sudden shift in customer preferences in a tech market. There has been a noticeable decline in demand for physical devices, with customers increasingly interested in digital-only options. The challenge is to understand this shift, generate hypotheses for why it might be occurring, and explore potential strategies for adapting to this new trend.

---

### *Processed Output with System 1 and System 2 Thinking:*

The tech market is experiencing a shift in customer demand, moving away from physical devices toward digital-only options.

[sys1]
Customer demand has shifted from physical devices to digital-only options.
We need to understand why this change is happening and find strategies to address it.
Key factors may include cost, convenience, and technological trends.
[end sys1]

[sys2]
**2.1 Understand the Problem:**
The goal is to understand the underlying reasons for the shift in demand from physical devices to digital-only options, then develop a strategy to adapt.

*Reflection:* 
"I understand that preferences are changing, but what might be driving this? Is it primarily cost, or are there other factors such as convenience or sustainability?"

*Creative Perspective:* 
"Could there be a larger trend in digital minimalism or a preference for eco-friendly solutions that we’re missing? What unseen motivations might explain this shift?"

**2.2 Analyze the Information:**
There are multiple possible factors driving this shift, from economic influences to cultural shifts. It’s essential to isolate each factor and understand its impact.

*Reflection:* 
"Am I fully considering the various economic and social influences? Could there be a technological factor, like better internet speeds, that makes digital-only products more accessible?"

*Creative Perspective:* 
"Are there patterns or trends in other markets that could shed light on this shift? Could this be part of a larger trend toward virtual experiences?"

**2.3 Generate Hypotheses:**
1. Customers prefer digital options due to lower costs. (Confidence: 0.8, Creative: 0.4)
2. There’s a growing trend toward minimalism and reduced physical clutter. (Confidence: 0.7, Creative: 0.7)
3. Digital products offer greater flexibility and ease of use. (Confidence: 0.6, Creative: 0.6)
4. Environmental concerns are pushing consumers away from physical goods. (Confidence: 0.6, Creative: 0.8)
5. Advances in tech make digital-only options more functional. (Confidence: 0.8, Creative: 0.5)
6. Pandemic-era remote work increased demand for digital solutions. (Confidence: 0.7, Creative: 0.6)
7. Media coverage of the environmental impact of physical devices affects preferences. (Confidence: 0.5, Creative: 0.7)
8. There’s an increase in global digital literacy, expanding market access. (Confidence: 0.6, Creative: 0.6)
9. Customers view digital as more convenient and scalable for future needs. (Confidence: 0.7, Creative: 0.5)
10. Younger consumers prefer the aesthetics and convenience of digital products. (Confidence: 0.6, Creative: 0.6)

*Reflection:* 
"Have I considered all possible influences? Are there any surprising factors that could explain this shift?"

*Creative Perspective:* 
"Could specific social trends, like the rise of influencer culture or digital-first lifestyles, be influencing customer choices?"

**2.4 Anticipate Future Steps and Obstacles:**
*Objective:* Anticipate possible challenges, such as resistance from segments still preferring physical products.

*Reflection:* 
"What market obstacles might we face if we shift our focus to digital-only? Are there sub-segments that still prioritize physical products?"

*Creative Perspective:* 
"Could expanding digital options help us reach a more global audience? Are there emerging trends that we could leverage in our strategy?"

[end sys2]

[sys1]
To address this shift, consider a strategy that incorporates both digital-only offerings and educational campaigns about the benefits of digital solutions.
Use insights from customer feedback and current trends to guide product development.
Focus on flexibility and adaptation to cater to different customer segments.
[end sys1]


---
abstract: 'We study three finite-dimensional quotient vector spaces constructed from the linear span of the set of characteristic functions of permutohedral cones by imposing two kinds of constraints: (1) neglect characteristic functions of higher codimension permutohedral cones, and (2) neglect characteristic functions of non-pointed permutohedral cones. We construct an ordered basis which is canonical, in the sense that it has subsets which map onto ordered bases for the quotients. We present straightening relations to the canonical basis, and using Laplace transforms we obtain functional representations for each quotient space.'
author:
- Nick Early
title: Canonical Bases for Permutohedral Plates
---

[^1]

Introduction
============

The purpose of this paper is two-fold: it contains general combinatorial and geometric results about generalized permutohedra, but from our perspective it is motivated by surprising connections to physics, in particular to the study of scattering amplitudes in quantum field theory and string theory.

This paper is devoted to the combinatorial analysis of the vector space of characteristic functions of permutohedral cones, studied as *plates* by A. Ocneanu as communicated privately [@OcneanuCommunication], and by the author in [@EarlyAnnouncement; @EarlyAmplitudes2017]. We derive a certain *canonical* basis of the space which is spanned linearly by characteristic functions of permutohedral cones; these cones are *dual* to the faces of the arrangement of reflection hyperplanes, defined by equations $x_i-x_j=0$.

The basis is called *canonical* because of its compatibility with quotient maps to three other spaces: subsets of the canonical plate basis descend to bases for the quotients. These maps are constructed from one or both of two geometrically-motivated conditions, according to which characteristic functions of (1) higher codimension faces, or (2) non-pointed cones, are sent to the zero element.

Plates are *permutohedral* cones: the edges extend along the root directions $e_i-e_j$. Plates are labeled by ordered set partitions; when the blocks of an ordered partition are all singlets, then the corresponding plate is encoded by a directed tree of the form $\{(i_1,i_2),(i_2,i_3),\ldots, (i_{n-1},i_n)\}$ and correspondingly have edge directions the roots $e_{i_j}-e_{i_{j+1}}$.

We begin in Section \[sec:Landscape\] by introducing notation and collecting basic results about polyhedral cones. In Section \[sec:platehomology\] we give linear relations which express the characteristic function of any product of mutually orthogonal plates as a signed sum of plates which have the ambient dimension $n-1$. We come to our main result, the construction of canonical plate basis, in Section \[sec: uppertriangularmap\] and give two graded dimension formulas. In Section \[sec:PlatesTrees\] we give formulas which express the characteristic function of a permutohedral cone encoded by a directed tree as a signed sum of characteristic functions of plates. In Theorem \[thm:Straightening\] of Section \[sec:straightening\], we present a straightening formula which expands the characteristic function of any plate in the canonical basis.

It would be interesting to study Hopf algebraic properties of the canonical plate basis. For a possible starting point, one could look toward the product formula for WQSym, as represented on characteristic functions of polyhedral cones in Theorem 5.2 in [@ThibonMould], keeping in mind the formula in Theorem \[thm: shuffleLump Identity\] in the present paper.

One consequence of Theorem \[thm:treeExpansionCompletePlates\] and Corollary \[cor:plate relations quotient\] is the possibility to derive the identities satisfied by the so-called Cayley functions from [@HeSon]; indeed, interpreting Cayley functions as Laplace transforms of permutohedral cones (in the terminology which follows, functional representations of type $\mathcal{P}_1^n$) solves the problem by allowing the application of Proposition \[prop:functional Tree Identities\]. By extension, this in part motivates the question studied in [@EarlyAmplitudes2017], to explain in the same way the more intricate combinatorial constructions from [@Nonplanar; @CachazoCombinatorialFactorization] using permutohedral cones. Also relevant to the construction linking permutohedra and functional representations, are [@LoopParkeTaylor2; @NewBCJ].

While the permutohedral cones studied in the present paper are all linear, having as faces hyperplanes which have the common intersection point $(0,\ldots, 0)$, one could introduce deformations, allowing translations by integer multiples of roots $e_i-e_j$. This has some interesting consequences. In the setting of [@EarlyAnnouncement], such translations were essential in the proof of an ${\mathfrak{S}}_n$-equivariant analog of the classical Worpitzky identity from combinatorics: on one side of the identity are plates embedded in dilated simplices, and on the other side are plates intersected with translations of unit hypersimplices along integer multiples of roots $e_i-e_j$. For a rather different multi-parameter deformation, for inspiration one could look toward the construction of the canonical form of the permutohedron in [@worldsheet].

Landscape: basic properties of cones and plates {#sec:Landscape}
===============================================

Throughout this paper we shall assume $n\ge 1$.

The all-subset hyperplane arrangement lives inside the linear hyperplane $V_0^n\subset\mathbb{R}^n$ defined by $x_1+\cdots+x_n=0$, and consists of the *special* hyperplanes $\sum_{i\in I}x_i=0$, as $I$ runs through the proper nonempty subsets of $\{1,\ldots, n\}$. This paper deals with the subspace of functions supported on $V_0^n$ lying in the span of characteristic functions $\lbrack U \rbrack$ of subsets $U$ which are closed cones in the all-subset arrangement. Certain subsets $U$ play a special role in this theory.

\[defn:plates\] An *ordered set partition* of $\{1,\ldots, n\}$ is a sequence of *blocks* $(S_1,\ldots, S_k)$, where $\emptyset\not=S_i\subseteq\{1,\ldots,n\}$ with $S_i\cap S_j=\emptyset$ for $i\not=j$, and with $\cup_{i=1}^k S_i=\{1,\ldots, n\}$. For each such ordered set partition, the associated *plate* $\pi=\lbrack S_1,\ldots, S_k\rbrack$ is the cone defined by the system of inequalities $$\begin{aligned}
            x_{S_1} & \ge & 0\\
            x_{S_1\cup S_2} & \ge & 0 \\
            & \vdots & \\  
            x_{S_1\cup\cdots\cup S_{k-1}} & \ge & 0\\
            x_{S_1\cup\cdots\cup S_{k}}=\sum_{i=1}^n x_i & =& 0,
        \end{aligned}$$ where $x_{S}=\sum_{i\in S}x_i$ for each $S\subseteq \{1,\ldots, n\}$. When the $S_i$’s are singlets we write simply $\pi=\lbrack i_1,\ldots, i_n\rbrack$, where $i_a$ stands for the unique element of $S_a$. We denote by $\lbrack\pi\rbrack=\lbrack\lbrack S_1,\ldots, S_k\rbrack\rbrack$ the characteristic function of the plate $\pi$.

Denote by $\text{len}(\pi)$ the number of blocks in the ordered set partition which labels $\pi$.

Note that the polyhedral cones in [@ThibonMould] are obtained from the above definition for permutohedral cones by relaxing the condition in the last line $\sum_{i=1}^n x_i=0$ to $\sum_{i=1}^n x_i\ge 0$.

This paper studies four spaces $\hat{\mathcal{P}}^n, \mathcal{P}^n,\hat{\mathcal{P}}_1^n,\mathcal{P}_1^n$, as related by a diagram of linear surjections: $$\begin{aligned}
\label{eqn: commutative diagram}
    \label{diagram}
    \begin{CD}
    \hat{\mathcal{P}}^n   @>{}>> \hat{\mathcal{P}}_1^n \\
    @V{}VV        @V{}VV\\
    \mathcal{P}^n   @>{}>> \mathcal{P}_1^n \\
    \end{CD}
        \end{aligned}$$ The horizontal (respectively vertical) maps mod out by characteristic functions of cones which are not pointed (respectively not full-dimensional). In particular, the upper left space $\hat{\mathcal{P}}^n$ is the linear span of characteristic functions of all plates. The upper right space $\hat{\mathcal{P}}_1^n$ is the quotient of $\hat{\mathcal{P}}^n$ by the span of the characteristic functions of plates which are not pointed: they contain doubly infinite lines. The lower left space $\mathcal{P}^n$ requires somewhat more care to define: it is the quotient of $\hat{\mathcal{P}}^n$ by the span of those linear combinations of characteristic functions of plates which vanish outside a set of measure zero in $V_0^n$. The lower right space $\mathcal{P}_1^n$ is the quotient of $\hat{\mathcal{P}}^n$ by the span of both characteristic functions of non-pointed plates and linear combinations which vanish outside sets of measure zero in $V_0^n$.

The subscript $1$ on $\hat{\mathcal{P}}_1^n$ and $\mathcal{P}_1^n$ is intended to remind that only characteristic functions of plates labeled by ordered set partitions having all blocks of size $1$ are nonzero.

In Theorem \[thm:unitriangularMap\] we construct the *canonical* plate basis for $\hat{\mathcal{P}}^n$. It is unitriangularly related to the given basis of characteristic functions $\lbrack\pi\rbrack$, with the virtue that it contains subsets which will descend to bases for the other three spaces. In particular, this will show that the quotient spaces have dimensions given as follows:

   $\dim\left(\hat{\mathcal{P}}^n\right)=\sum_{k=1}^n k!S(n,k)$    (Ordered Bell \#’s)   $\dim\left(\hat{\mathcal{P}}_1^n\right)\ =\ \sum_{k=1}^n s(n,k)=n!$
  ------------------------------------------------------------------------------------- ---------------------------------------------------------------------
     $\dim\left(\mathcal{P}^n\right)=\sum_{k=1}^n (k-1)!S(n,k)$  (Cyclic Bell \#’s)            $\ \dim\left(\mathcal{P}_1^n\right)\ =\ s(n,1)=(n-1)!$

.

Here $S(n,k)$ is the $k^\text{th}$ Stirling number of the second kind, which counts the set partitions of $\{1,\ldots, n\}$ into $k$ parts, and $s(n,k)$ is the (unsigned) Stirling number of the first kind which counts the number of permutations which have $k$ cycles (including singlets) in their decompositions into disjoint cycles.

The canonical basis of $\hat{\mathcal{P}}^n$ is naturally graded, and the corresponding dimensions are given below. The first six rows are given below; note that the rows sum to the ordered Bell numbers $( 1, 3, 13, 75, 541, 4683)$. $$\begin{array}{cccccc}
    1&&&&&\\
    2 & 1 &  &  &  &\\
    6 & 6 & 1 &  &  &\\
    26 & 36 & 12 & 1 && \\
    150 & 250 & 120 & 20 & 1 & \\
    1082 & 2040 & 1230 & 300 & 30 & 1 \\
    \end{array}$$ In Corollary \[cor:Lineardimensions\] we observe that the rows are given by the equation $$T_{n,k}=\sum_{i=k}^n S(n,i)s(i,k),$$ where $S(n,i)$ is the Stirling number of the second kind, and $s(i,k)$ is the Stirling number of the first. This is given in O.E.I.S. A079641.

Further, as the canonical basis of $\hat{\mathcal{P}}^n$ passes to one for $\hat{\mathcal{P}}_1^n$, with graded dimensions the (unsigned) Stirling numbers of the first kind. $$\begin{array}{cccccc}
    1&&&&&\\
    1 & 1 &  &  &  &\\
    2 & 3 & 1 &  &  &\\
    6 & 11 & 6 & 1 && \\
    24 & 50 & 35 & 10 & 1 & \\
    120 & 274 & 225 & 85 & 15 & 1 \\
    \end{array}$$

Finally, the space $\mathcal{P}_1^n$ has only one graded component, of dimension $(n-1)!$. However, it turns out there is an algebra related to $\mathcal{P}_1^n$ which is the associated graded version of $\hat{\mathcal{P}}_1^n$, for which [@OrlikTerao] is relevant. The study is beyond the scope of this paper and we leave it to future work.

Notation and conventions
------------------------

Recall that a chain of inequalities $x_{i_1}\ge x_{i_2}\ge\cdots\ge x_{i_n}$ with $\sum x_i=0$ cuts out a simplicial cone called a *Weyl chamber* in the arrangement of reflection hyperplanes, defined by equations $x_i-x_j=0$, of type $A_{n-1}$. Weyl chambers are thus labeled by permutations $(i_1,\ldots, i_n)$ in one-line notation.

A *polyhedral cone* is an intersection of finitely many half spaces $\sum_{j=1}^n a_{i,j} x_j\ge 0$ in $\mathbb{R}^n$, for some integer constants $a_{i,j}$. For example, the chain of inequalities which define a Weyl chamber can be reorganized as $$x_{i_1}-x_{i_2}\ge 0,\ldots, x_{i_{n-1}}-x_{i_n}\ge 0,\ \text{ with } \sum x_i=0,$$ so it is a polyhedral cone. Letting $e_1,\ldots, e_n$ denote the standard basis for $\mathbb{R}^n$, if $I$ is a subset of $\{1,\ldots, n\}$, set $e_I=\sum_{i\in I} e_i$ and let $\bar{e}_I=\frac{\vert I^c\vert}{n}e_I-\frac{\vert I\vert}{n}e_{I^c}$ be the projection of $e_{I}$ onto $V_0^n$, along the vector $(1,\ldots, 1)$. A polyhedral cone is *pointed* if it does not contain any lines which extend to infinity in both directions.

Given $\{v_1,\ldots, v_k\}\subset\mathbb{R}^n$, denote by $\langle v_1,\ldots, v_k\rangle_+:=\left\{c_1v_1+\cdots+c_kv_k: c_i\ge 0\right\}$ their *conical hull*. For example, a Weyl chamber is a conical hull, since it can also be obtained as the set of all linear combinations of a set of vectors with nonnegative coefficients, $$\left\langle\bar{e}_{i_1},\bar{e}_{\{i_1,i_2\}},\ldots, \bar{e}_{\{i_1,i_2,\ldots, i_{n-1}\}}\right\rangle_+=\{c_1\bar{e}_{i_1}+c_2\bar{e}_{\{i_1,i_2\}}+\cdots+c_{n-1}\bar{e}_{\{i_1,\ldots, i_{n-1}\}}:c_i\ge 0\}.$$ Further, the conical hull of the *roots* of type $A_{n-1}$, $\langle e_{i_1}-e_{i_2},\ldots, e_{i_{n-1}}-e_{i_n}\rangle_+$ is called a *root cone*, and it is easy to check that it coincides with the plate $\lbrack i_1,\ldots, i_n\rbrack$. We leave it as an exercise for the reader to check that, if $(S_1,\ldots, S_k)$ is an ordered set partition of $\{1,\ldots, n\}$, then we have $$\begin{aligned}
    && \lbrack S_1,\ldots, S_k\rbrack \nonumber\\
    && =\left\langle e_a-e_b:\text{ either } a,b\in S_j \text{ for $j = 1,\ldots,k$, } \text{ or } (a,b)\in S_i\times S_{i+1} \text{ for $i=1,\ldots,k-1$} \right\rangle_+.\label{eqn: lumped plate conical hull}
    \end{aligned}$$

\[defn:Minkowski sum\] The *Minkowski sum* of two polyhedral cones $C_1,C_2$ is given by $C_1+C_2=\left\{u+v:u\in C_1,\ v\in C_2\right\}$. Denote by $\lbrack C_1\rbrack\cdot \lbrack C_2\rbrack=\lbrack C_1\cap C_2\rbrack$ the pointwise product of their characteristic functions, and denote by $$\lbrack C_1\rbrack\bullet \lbrack C_2\rbrack=\lbrack C_1+C_2\rbrack=\lbrack \left\{u+v:u\in C_1,\ v\in C_2\right\}\rbrack$$ their *convolution*, which is the characteristic function of the Minkowski sum $C_1+C_2$.

See [@BarvinokPammersheim] for details on the constructions of $\cdot$ and $\bullet$ as bi-linear maps on the $\mathbb{Q}$-vector space of characteristic functions of cones. Note however that we extend the coefficient field to $\mathbb{C}$.

There is a notion of duality for polyhedral cones.

\[defn: duality for cones\] Let $C$ be a polyhedral cone in $V_0^n$. The dual cone to $C$, denoted $C^\star$, is defined by the equation $$C^\star=\{y\in V_0^n:y\cdot x\ge 0\text{ for all } x\in C\}.$$

\[rem: properties of dual cones\] Dual cones are known to satisfy the following properties.

1.  The dual $C^\star$ of a cone $C$ with nonempty interior is pointed.

2.  The dual $C^\star$ of a pointed cone $C$ has nonempty interior.

3.  If a cone $C$ is convex and topologically closed, then $(C^\star)^\star=C$.

See for example [@ConvexOptimization] for details.

\[rem: properties dual cones\] We shall need the following results from [@BarvinokPammersheim], Theorem 2.7 and respectively Corollary 2.8, where we extend the field from $\mathbb{Q}$ to $\mathbb{C}$.

-   Duality for cones respects linear relations among their characteristic functions: if $C_1,\ldots, C_k$ are cones and for some constants $c_1,\ldots, c_k\in\mathbb{C}$ we have $$\sum_{i=1}^kc_i\lbrack C_i\rbrack=0$$ then the same relation holds among the characteristic functions for the dual cones, $$\sum_{i=1}^kc_i\lbrack C_i^\star\rbrack=0,$$ interchanging the pointwise product and the convolution.

-   There exists a linear map on the vector space spanned by characteristic functions of cones, which we also denote by $\star$, such that $\lbrack C\rbrack^\star=\lbrack C^\star\rbrack$.

-   Duality for cones interchanges intersections and Minkowski sums: if $C_1,C_2$ are cones, then $\lbrack C_1\cap C_2\rbrack=\lbrack C_1\rbrack\cdot\lbrack C_2\rbrack$, and moreover $$\left(\lbrack C_1\rbrack\cdot\lbrack C_2\rbrack\right)^\star=\lbrack C_1^\star\rbrack\bullet \lbrack C_2^\star\rbrack.$$

\[example: Dual Plates\] Denote $\bar{e}_1=(2,-1,-1)/3$ and $\bar{e}_2=(-1,2,-1)/3$, hence $\bar{e}_1+\bar{e}_2=(1,1,-2)/3=-\bar{e}_3$. Then the two cones, the simple root cone $$\langle e_1-e_2,e_2-e_3\rangle_+$$ and the Weyl chamber $$\langle\bar{e}_1,\bar{e}_1+\bar{e}_2\rangle_+,$$ are dual to each other. See Figure \[fig:dual-plates\].

![Dual Cones for Example \[example: Dual Plates\][]{data-label="fig:dual-plates"}](Dual_plates_3){width="0.65\linewidth"}

Denote by $\lbrack S_1,\ldots, S_k\rbrack^\star$ the face of the reflection arrangement labeled by the ordered set partition $(S_1,\ldots, S_k)$, given by the equations $$(x_{s_{1,1}}=\cdots=x_{s_{1,l_1}})\ge (x_{s_{2,1}}=\cdots=x_{s_{2,l_2}})\ge\cdots\ge(x_{s_{k,1}}=\cdots =x_{s_{k,l_k}}),\ \ x_1+\cdots+x_n=0$$ (where $s_{i,1},\ldots, s_{i,l_i}$ are the elements of $S_i$), or for short $$x_{(S_1)}\ge x_{(S_2)}\ge \cdots\ge x_{(S_k)},\ x_1+\cdots+x_n=0,$$ where for compactness the symbol $x_{(S)}$ is defined to be the list of equations $(x_{i_1}=\cdots=x_{i_{\vert S\vert}})$, for a subset $S=\{i_1,\ldots, i_{\vert S\vert}\}$ of $\{1,\ldots, n\}$.

This can be given equivalently as the conical hull $$\left\langle \bar{e}_{S_1},\bar{e}_{S_1}+\bar{e}_{S_2},\ldots, \bar{e}_{S_1}+\cdots+\bar{e}_{S_{k-1}}\right\rangle_+.$$

\[prop: dual higher codimension plate\] If $(S_1,\ldots, S_k)$ is an ordered set partition of a subset $S\subseteq\{1,\ldots, n\}$, then the dual cone $\lbrack S_1,\ldots, S_k\rbrack^\star$ to $$\lbrack S_1,\ldots, S_k\rbrack=\left\{\sum_{i\in S}x_i e_i\in V_0^n: \sum_{i\in S_1\cup\cdots\cup S_j}x_i\ge 0,\ \text{for each } j=1,\ldots, k-1\right\}$$ equals $$\left\{t_1\sum_{i\in S_1} e_i+\cdots+t_k\sum_{i\in S_k}e_i\in V_0^n:t_1\ge \cdots\ge t_k\right\}.$$

Suppose $y\cdot x\ge 0$ for all $x\in \lbrack S_1,\ldots, S_k\rbrack$. By Equation , $$\lbrack S_1,\ldots, S_k\rbrack=\left\langle e_a-e_b:\text{ either } a,b\in S_i \text{ or $(a,b)\in S_i\times S_{i+1}$ for $i=1,\ldots,k-1$ } \right\rangle_+,$$ it suffices to check that, for either $a,b\in S_i$ or $(a,b)\in S_i\times S_{i+1}$, we have $$y_a-y_b=y\cdot (e_a-e_b)\ge0\text{ and } y_b-y_a= y\cdot (e_b-e_a)\ge 0.$$ Thus, $$y=t_1\sum_{i\in S_1}e_i+\cdots+t_k\sum_{i\in S_k}e_i+\sum_{i\in S^c} y_i e_i$$ for some $t_1,\ldots, t_k$ and $y_i$, such that $\vert S_1\vert t_1+\cdots+\vert S_k\vert t_k+\sum_{i\in S^c} y_i=0$. Now, for each $i=1,\ldots, k-1$, for any $(a,b)\in S_i\times S_{i+1}$ we have $t_i-t_{i+1}=y\cdot (e_a-e_b)\ge 0$, or $t_i\ge t_{i+1}$.

Corollary \[cor: reduction to Minkowski sum\] follows from . For pedagogical reasons we include a different proof using duality.

\[cor: reduction to Minkowski sum\] If $\pi=\lbrack S_1,\ldots, S_k\rbrack$ is a plate, then we may factor its characteristic function using the pointwise product. Set theoretically we have $$\pi=\lbrack S_1,\ldots, S_k\rbrack=\bigcap_{i=1}^{k-1}\lbrack S_1\cup\cdots\cup S_i,S_{i+1}\cup\cdots\cup S_k\rbrack,$$ or in terms of the pointwise product for characteristic functions, $$\lbrack\pi\rbrack=\lbrack\lbrack S_1,S_2\cup S_3\cdots \cup S_k\rbrack\rbrack\cdot\lbrack\lbrack S_1\cup S_2, S_3\cup \cdots \cup S_k\rbrack\rbrack\cdots \lbrack\lbrack S_1\cup S_2 \cdots \cup S_{k-1},S_k\rbrack\rbrack.$$ Using Minkowski sums it can be expressed as $$\pi=\sum_{i=1}^{k-1}\lbrack S_i,S_{i+1}\rbrack,$$ and correspondingly terms of the convolution product for characteristic functions, $$\lbrack\pi\rbrack=\lbrack\lbrack S_1,S_2\rbrack\rbrack\bullet\lbrack\lbrack S_2,S_3\rbrack\rbrack\bullet\cdots \bullet \lbrack\lbrack S_{k-1},S_k\rbrack\rbrack,$$ where $$\lbrack S_i,S_{i+1}\rbrack=\left\{\sum_{j\in S_i\cup S_{i+1}}x_j e_j\in V_0^n:\sum_{j\in S_i}x_j\ge 0,\  \sum_{j\in S_i\cup S_{i+1}}x_{j}=0\right\}.$$

The identity for the intersection products follows immediately from the defining inequalities for plates.

For the convolution product identity it is convenient first to dualize, $$\begin{aligned}
            \lbrack\lbrack S_1,S_2\rbrack\rbrack\bullet\lbrack\lbrack S_2,S_3\rbrack\rbrack\bullet\cdots \bullet \lbrack\lbrack S_{k-1},S_k\rbrack\rbrack & = & \left(\lbrack\lbrack S_1,S_2\rbrack\rbrack^\star\cdot\lbrack\lbrack S_2,S_3\rbrack\rbrack^\star\cdots  \lbrack\lbrack S_{k-1},S_k\rbrack\rbrack^\star\right)^\star,
        \end{aligned}$$ where by Proposition \[prop: dual higher codimension plate\] we have $$\lbrack\lbrack S_{i-1},S_i\rbrack\rbrack^\star =\left\lbrack\{y\in V_0^n:y_{(S_{i})}\ge y_{(S_{i+1})} \}\right\rbrack.$$

Thus, $$\begin{aligned}
            & & \left(\lbrack\lbrack S_1,S_2\rbrack\rbrack^\star\cdot\lbrack\lbrack S_2,S_3\rbrack\rbrack^\star\cdots  \lbrack\lbrack S_{k-1},S_k\rbrack\rbrack^\star\right)^\star\\
            & = & \left(\left\lbrack\{x\in V_0^n:x_{(S_{1})}\ge x_{(S_{2})} \}\right\rbrack\cdots \left\lbrack\{x\in V_0^n:x_{(S_{k-1})}\ge x_{(S_{k})}\}\right\rbrack\right)^\star\\
            & =& \left\lbrack\{x\in V_0^n:x_{(S_{1})}\ge\cdots\ge  x_{(S_k)}\}\right\rbrack^\star\\
            & = & \left\lbrack\left\{x\in V_0^n:x_{S_1}\ge 0,\ldots, \ x_{S_1\cup \cdots\cup S_{k-1}}\ge0\right\}\right\rbrack\\
            & = & \lbrack\lbrack S_1,\ldots, S_k\rbrack\rbrack,
        \end{aligned}$$ where as usual we use the shorthand notations $x_S=\sum_{i\in S}x_i$ and $x_{(S)}=(x_{s_1}=\cdots=x_{s_{\vert S\vert}})$, for $S$ a subset of $\{1,\ldots, n\}$.

Genericity
----------

The relationships between $\hat{\mathcal{P}}^n,\mathcal{P}^n,\hat{\mathcal{P}}_1^n$ and $\mathcal{P}_1^n$ reduce to variations on a single linear identity. If $S_1,S_2\subsetneq\{1,\ldots, n\}$ are any two disjoint nonempty subsets, then the characteristic function of the set $$\{x\in V_0^n:x_{S_1}=x_{S_2}=0\text{ and } x_j=0\text{ for all }j\not\in S_1\cup S_2\},$$ represented by the pointwise product $\lbrack\lbrack S_1,S_2\rbrack\rbrack\cdot \lbrack\lbrack S_2,S_1\rbrack\rbrack$, can be expressed via $$\lbrack\lbrack S_1,S_2\rbrack\rbrack+\lbrack\lbrack S_2,S_1\rbrack\rbrack=\lbrack\lbrack S_1,S_2\rbrack\rbrack\cdot \lbrack\lbrack S_2,S_1\rbrack\rbrack+\lbrack\lbrack S_1\cup S_2\rbrack\rbrack.$$ The above identity holds in $\hat{\mathcal{P}}^n$. To obtain the identity which holds in $\mathcal{P}^n$ we specialize to $$\lbrack\lbrack S_1, S_2\rbrack\rbrack+\lbrack\lbrack S_2,S_1\rbrack\rbrack=\lbrack\lbrack S_1\cup S_2\rbrack\rbrack,$$ where $\lbrack\lbrack S_1\cup S_2\rbrack\rbrack$ is the characteristic function of the set $$\lbrack S_1\cup S_2\rbrack = \left\{\sum_{j\in S_1\cup S_2} x_j e_j\in \mathbb{R}^n:\sum_{j\in S_1\cup S_2} x_j=0\right\}\subseteq V_0^n.$$ In $\hat{\mathcal{P}}_1^n$ and $\mathcal{P}_1^n$ we we assume that $S_1,S_2\subset\{1,\ldots, n\}$ are singlets and specialize to respectively $$\lbrack\lbrack S_1,S_2\rbrack\rbrack+\lbrack\lbrack S_2,S_1\rbrack\rbrack =\lbrack\lbrack S_1,S_2\rbrack\rbrack\cdot\lbrack\lbrack S_2,S_1\rbrack\rbrack$$ and $$\lbrack\lbrack S,S^c\rbrack\rbrack+\lbrack\lbrack S^c,S\rbrack\rbrack =0.$$

Plate homology: from plates to their faces  {#sec:platehomology}
===========================================

The main result of this section is Theorem \[thm: shuffleLump Identity\], which expands the face of a plate as a linear combination of characteristic functions of plates in $\hat{\mathcal{P}}^n$.

While the symmetric group does not play an essential role in this paper, let us point out some of the symmetry properties of plates which were implicit in [@EarlyAnnouncement]. The action of the symmetric group ${\mathfrak{S}}_n$ on plates is inherited from the coordinate permutation on $\mathbb{R}^n$. In the plate notation, $\sigma\in{\mathfrak{S}}_n$ acts on characteristic functions of plates $\lbrack\lbrack S_1,\ldots, S_k\rbrack\rbrack$ by permuting elements in the blocks $S_i$.

The permutation group ${\mathfrak{S}}_n$ preserves the following operations on characteristic functions of plates.

1.  Inclusion: $$\lbrack\lbrack S_1,\ldots, S_k\rbrack\rbrack\mapsto \lbrack\lbrack T_1,\ldots, T_l\rbrack\rbrack$$ where $l\le k$, each $T_i$ is a union of some consecutive $S_j$’s and we still have $\cup_{i=1}^l T_i=\{1,\ldots, n\}$. Note that from the defining inequalities we have the inclusion of cones $$\lbrack S_1,\ldots, S_k\rbrack\subseteq \lbrack T_1,\ldots, T_l\rbrack.$$

2.  Block permutation: $$\lbrack\lbrack S_1,\ldots, S_k\rbrack\rbrack\mapsto \lbrack\lbrack S_{\tau_1},\ldots, S_{\tau_k}\rbrack\rbrack$$ for a permutation $\tau\in \mathfrak{S}_k$.

3.  Restriction to a face: $$\lbrack\lbrack S_1,\ldots, S_k\rbrack\rbrack=\lbrack\lbrack S_1,S_2\rbrack\rbrack\bullet\cdots\bullet\lbrack\lbrack S_{k-1}, S_k\rbrack\rbrack \mapsto \lbrack\lbrack S_{i_1},S_{i_1+1}\rbrack\rbrack\bullet\cdots\bullet\lbrack\lbrack S_{i_{l}}, S_{i_{l}+1}\rbrack\rbrack$$ for any subset $\{i_1,\ldots, i_l\}\subseteq\{1,\ldots, k-1\}$.

\[Prop: UniversalPlateModuleFreelyGenerated\] The space $\hat{\mathcal{P}}^n$, the linear span of the characteristic functions of plates $\pi$, has linear dimension the ordered Bell number $\sum_{k=1}^{n} k!S_{n,k}$, where $S_{n,k}$ are the Stirling numbers of the second kind, which count the number of set partitions of $\{1,\ldots, n\}$ into $k$ disjoint subsets.

By Remark \[rem: properties dual cones\], the involution $\star$ preserves linear relations among characteristic functions; therefore it provides a natural isomorphism of vector spaces from $\hat{\mathcal{P}}^n$ onto the space spanned by the characteristic functions of faces of Weyl chambers. Further, for each dimension $k=0,\ldots, n-1$, these faces have non-intersecting relative interiors and consequently their characteristic functions are linearly independent, and by the duality map $\star$, plates in $\hat{\mathcal{P}}^n$ are as well. Therefore, to extract the dimension formula it suffices to count the faces of the arrangement of reflection hyperplanes; but these are in bijection with the ordered set partitions of $\{1,\ldots, n\}$, which are counted by the ordered Bell numbers.

\[defn:lumped permutation, etc\] Let $\mathbf{S}=(S_1,\ldots, S_k)$ be an ordered set partition of $\{1,\ldots, n\}$. Suppose $\mathbf{T}=(T_1,\ldots, T_l)$ is another ordered set partition of $\{1,\ldots, n\}$, such that each block $T_i$ of $\mathbf{T}$ is a union of blocks $S_j$ of $\mathbf{S}$. Define $p_i\in\{1,\ldots, l\}$ by the condition that $S_i$ is a subset of $T_{p_i}$. Thus if $S_i$ is a subset of the first block of $\mathbf{T}$ then $p_1=1$. Then $\mathbf{T}$ has the *orientation* $p_i\le p_j$ with respect to $\mathbf{S}$ whenever $S_i$ appears to the left of $S_j$ in $\mathbf{T}$, with equality if and only if $S_i\sqcup S_j\subseteq T_{a}$ for some $a\in\{1,\ldots, l\}$. In the case that $\mathbf{T}$ satisfies $p_i<p_j$, we shall say that $T$ is *compatible* with the orientation $p_i<p_j$.

\[defn:shuffle-Lumping\] Let $\mathbf{S}=(S_1,\ldots, S_k)$ be an ordered set partition of $\{1,\ldots, n\}$ Another ordered set partition $\mathbf{T}=(T_1,\ldots, T_m)$ of $\{1,\ldots, n\}$ is a *shuffle-lumping* of ordered set partitions $$\mathbf{S}_1=(S_{1},S_{2},\ldots, S_{k_1}), \mathbf{S}_2=(S_{k_1+1},S_{k_1+2},\ldots, S_{k_1+k_2}),\ldots, \mathbf{S}_l=(S_{k_1+\cdots+k_{l-1}+1},\ldots, S_{k_1+\cdots+k_{l}}),$$ provided that each ordered set partition $\mathbf{S}_i$ is compatible with the orientations $$p_{1}<p_2<\cdots<p_{k_1}$$ $$p_{k_1+1}<p_{k_1+2}<\cdots<p_{k_1+k_2}$$ $$\vdots$$ $$p_{k_1+\cdots+k_{l-1}+1}<p_{k_1+\cdots+k_{l-1}+2}<\cdots<p_n.$$

The plate $\lbrack S_1,\ldots, S_k\rbrack$ is uniquely characterized among its shuffle-lumpings by the set of orientations $p_1< p_2<\cdots < p_k$ on the blocks $S_1,\ldots, S_k$.

If $(S_1,S_2,S_3,S_4)=(1,4,23,5)$ and $(S_5,S_6)=(678,9)$, then shuffle-lumped plates include for example $$\lbrack1,4678,23,59\rbrack\text{ and } \lbrack678,1,4,23,9,5\rbrack.$$ Then $\lbrack1,4678,23,59\rbrack$ is a plate with the smallest possible number of blocks, while $\lbrack678,1,4,23,9,5\rbrack$ is a plate with the largest possible number of blocks, in the shuffle-lumping of the set compositions $(S_1,S_2,S_3,S_4)$ and $(S_5,S_6)$.

The shuffle-lumpings of $(S_1,S_2)=(\{1\},\{2,3\})$ and $(S_3,S_4)=(\{4\},\{5\})$ are $$\{(1,23,4,5),(1,234,5),(1,4,23,5),(14,23,5),(4,1,23,5),(1,4,235),(14,235),(4,1,235),$$ $$(1,4,5,23),(14,5,23),(4,1,5,23),(4,15,23),(4,5,1,23)\}.$$

In Lemma \[lem: Weyl chamber decomposition shuffle\] we decompose the characteristic function of a union of closed Weyl chambers into an alternating sum of partially closed Weyl chambers in a canonical way that depends on descent positions, with respect to the natural order $(1,\ldots, n)$. See [@Stanley; @EC1] for a systematic approach using so-called $(P,\omega)$-partitions.

\[lem: Weyl chamber decomposition shuffle\] We have the decomposition into disjoint sets $$V_0^n=\sqcup_{\sigma\in {\mathfrak{S}}_n} C_\sigma,$$ where each $C_\sigma$ is the partially open Weyl chamber defined by $$x_{\sigma_i}\ge x_{\sigma_{i+1}}\ \text{ if } \sigma_{i}<\sigma_{i+1}$$ and $$x_{\sigma_i}>x_{\sigma_{i+1}}\ \text{ if } \sigma_{i}>\sigma_{i+1}.$$ The characteristic function of $C_\sigma$, with $\sigma=(\sigma_1,\ldots, \sigma_n)$ given, is $$\lbrack C_\sigma\rbrack=\sum_{\pi}(-1)^{n-\operatorname{len}(\pi)}\lbrack\pi^\star\rbrack,$$ where the sum is over the set of plates $\pi=\lbrack(S_1,\ldots, S_k)\rbrack$ which are labeled by ordered set partitions $(S_1,\ldots, S_k)$ with blocks $S_i$ defined as follows. Let $$\{d_1<\cdots<d_{k-1}\}=\{i: \sigma_i <\sigma_{i+1}\}.$$ Also set $d_0=0$ and $d_k=n$. Then put $$S_i = \{\sigma_p:d_{i-1}<p\le d_i\}.$$

Any $x\in V_0^n$ not in *any* reflection hyperplane $x_i=x_j$ is in the interior of the Weyl chamber labeled by the order of its coordinate values, $x_{\sigma_1}> \cdots> x_{\sigma_n}$, say. Now if $x$ is in the interior of a face labeled by an ordered set partition $(S_1,\ldots, S_k)$ of $\{1,\ldots, n\}$, having the form $$x=t_1 e_{S_1}+\cdots+t_k e_{S_k},$$ for some $t_1>t_2>\cdots>t_k$ with $\sum_{i=1}^k\vert S_i\vert t_i=0$, then we put $x\in C_\sigma$ where the permutation $\sigma$ is obtained from $(S_1,\ldots, S_k)$ by placing the labels in each block $S_i$ in increasing order and then concatenating the blocks.

The formula for $\lbrack C_\sigma\rbrack$ follows from the standard inclusion-exclusion expression for the characteristic function of the complement of the union of the codimension 1 faces $\lbrack \sigma_1,\ldots, \sigma_{i}\sigma_{i+1},\ldots,\sigma_n\rbrack^\star$ corresponding to descents $\sigma_i>\sigma_{i+1}$ in $\sigma$: $$\lbrack\sigma_{1},\ldots,\sigma_n\rbrack^\star\setminus\left(\bigcup_{\sigma_i>\sigma_{i+1}}\lbrack \sigma_1,\ldots, \sigma_{i}\sigma_{i+1},\ldots,\sigma_n\rbrack^\star\right),$$ that is $$\lbrack C_\sigma\rbrack=\left\lbrack \lbrack\sigma_{1},\ldots,\sigma_n\rbrack^\star\right\rbrack-\sum_{\pi'}(-1)^{n-1-\operatorname{len}(\pi')}\lbrack(\pi')^\star\rbrack=\sum_{\pi}(-1)^{n-\operatorname{len}(\pi)}\lbrack\pi^\star\rbrack$$ where the middle sum is over the lumpings $\pi'$ of $\lbrack\sigma_1,\ldots,\sigma_n\rbrack$ at descents $\sigma_i>\sigma_{i+1}$ (excluding $\lbrack\sigma_1,\ldots,\sigma_n\rbrack$ itself), and the right sum now includes $\lbrack\sigma_1,\ldots,\sigma_n\rbrack$.

The characteristic functions of the partially open Weyl chambers respectively $$\{x\in V_0^3: x_1\ge x_2\ge x_3\}$$ $$\{x\in V_0^3: x_2> x_1\ge x_3\}$$ $$\{x\in V_0^3: x_3> x_2> x_1\}$$ can be obtained as linear combinations of characteristic functions of dual plates as $$\begin{aligned}
            \lbrack C_{(1,2,3)}\rbrack & = & \lbrack\lbrack 1,2,3\rbrack\rbrack^\star\\
            \lbrack C_{(2,1,3)}\rbrack & = & \lbrack \lbrack 2,1,3\rbrack\rbrack^\star -\lbrack\lbrack 21,3\rbrack\rbrack^\star\\
            \lbrack C_{(3,2,1)}\rbrack & = & \lbrack \lbrack 3,2,1\rbrack\rbrack^\star -\lbrack\lbrack 32,1\rbrack\rbrack^\star-\lbrack\lbrack 3,21\rbrack\rbrack^\star+\lbrack\lbrack 321\rbrack\rbrack^\star.\\
        \end{aligned}$$

More generally, in Lemma \[lem: Weyl chamber decomposition shuffle\] we replace Weyl chambers, labeled by permutations, with higher codimension faces of the reflection arrangement which are labeled by ordered set partitions. Suppose $$\mathbf{S}_1=(S_1,\ldots, S_{k_1}),\ldots,\mathbf{S}_l=(S_{k_1+\cdots+k_{l-1}+1},\ldots, S_{k_1+\cdots+k_{l}})$$ are ordered set partitions of respectively $\bigcup_{S\in\mathbf{S}_i}S$, $i=1,\ldots, l$, and let $\sigma=(\sigma_1,\ldots,\sigma_l)$ be a permutation of $\{1,\ldots, l\}$. Define an embedding $\iota:V_0^l\hookrightarrow V_0^{k_1+\cdots +k_l}$ by $$\sum_{i=1}^lt_i e_i\mapsto \sum_{i=1}^l \left(\frac{t_i}{\vert S_i\vert}\right) e_{S_i}.$$

\[cor: Higher codimension Weyl chamber decomposition shuffle\] We have $$\lbrack\iota(C_{\sigma})\rbrack=\sum_{\pi}(-1)^{l-\operatorname{len}(\pi)}\lbrack\iota(\pi^\star)\rbrack,$$ where the sum is the same as in Lemma \[lem: Weyl chamber decomposition shuffle\].

In Theorem \[thm: shuffleLump Identity\], we replace the natural order $(1,\ldots, m)$ with an ordered set partition $$(S_{1},S_2,\ldots, S_{m})$$ of $\{1,\ldots, n\}$, where $m=k_1+\cdots+k_l$.

The proof in what follows of Theorem \[thm: shuffleLump Identity\] illustrates the essential role of the duality isomorphism from Definition \[defn: duality for cones\] and utilizes directly set-theoretic inclusion-exclusion arguments. Now, by way of Theorem 5.2 of [@ThibonMould], the same formula holds if we extend plates from $V_0^n$ into the ambient space $\mathbb{R}^n$, in which case the last line of the plate equations becomes $x_1+\cdots+x_n\ge 0$.

\[thm: shuffleLump Identity\] Given $l$ ordered set partitions $$\mathbf{S}_1=(S_{1},S_{2},\ldots, S_{k_1}),\mathbf{S}_2=(S_{k_1+1},S_{k_1+2},\ldots, S_{k_1+k_2}),\ldots, \mathbf{S}_{l}=(S_{k_1+\cdots+k_{l-1}+1},\ldots, S_{k_1+\cdots+k_{l}})$$ such that $\bigsqcup_{i=1}^{k_1+\cdots+k_l}S_i=\{1,\ldots, n\}$, then we have the identity for characteristic functions of plates in $\hat{\mathcal{P}}^n$,

$$\lbrack\lbrack\mathbf{S}_1\rbrack\rbrack\bullet \cdots\bullet \lbrack\lbrack \mathbf{S}_{l}\rbrack\rbrack= \sum_\pi(-1)^{m-\operatorname{len}(\pi)}\lbrack\pi\rbrack,$$ where $m=k_1+\cdots+k_l$ and $\pi$ runs over all shuffle-lumpings of $\mathbf{S}_1,\ldots,\mathbf{S}_l$.

We shall work in the space of characteristic functions of faces of the reflection arrangement and then dualize to obtain the identity for characteristic functions of plates.

We have $$\begin{aligned}
\label{eqn:weight plates for shuffleLump identity}
            \lbrack\mathbf{S}_i\rbrack^\star & = & \left\{\sum_{i=1}^{m}t_ie_{S_i}\in V_0^n:t_{k_{i-1}+1}\ge \cdots\ge t_{k_{i}}\right\}\\
        \end{aligned}$$ and thus $$\begin{aligned}
            \lbrack \mathbf{S}_1\rbrack^\star \cap\cdots\cap\lbrack \mathbf{S}_l\rbrack^\star & = & \left\{\sum_{i=1}^{m}t_ie_{S_i}:\begin{array}{c}
                t_1\ge t_2\ge \cdots\ge t_{k_1} ,   \\ 
                t_{k_1+1}\ge\cdots\ge t_{k_1+k_2},  \\ 
                \vdots                          \\
                t_{k_1+\cdots+k_{l-1}+1}\ge\cdots\ge t_{k_1+\cdots+k_l}
            \end{array} \right\},\\
        \end{aligned}$$ which lives in a copy of $V_0^m$ embedded in $V_0^n$ as $\iota(\sum_{i=1}^{m}t_ie_i) \mapsto \sum_{i=1}^{m}t_i (e_{S_i}/\vert S_i\vert)$.

Then $\iota^{-1}\left(\lbrack \mathbf{S}_1\rbrack^\star \cap\cdots\cap\lbrack \mathbf{S}_l\rbrack^\star\right)\subseteq V_0^m$ is a union of Weyl chambers $\bigcup_{\tau}\lbrack\tau\rbrack^\star$ defined by $y_{\tau_1}\ge\cdots\ge y_{\tau_m}$ labeled by shuffles $(\tau_1,\ldots,\tau_m)$ of $$\sigma_1=(1,2,\ldots, k_1),\ldots, \sigma_l=\left(m-k_l+1,\ldots, m\right).$$ We replace each such (closed) Weyl chamber defined by $y_{\tau_1}\ge\cdots\ge y_{\tau_m}$ with the partially open Weyl chamber $C_\tau$ from Lemma \[lem: Weyl chamber decomposition shuffle\] and obtain the disjoint union $$\begin{aligned}
            \iota^{-1}\left(\lbrack \mathbf{S}_1\rbrack^\star \cap\cdots\cap\lbrack \mathbf{S}_l\rbrack^\star\right) & \supseteq & \bigsqcup_{\tau}C_\tau,
        \end{aligned}$$ where the disjoint union is dense in the (closed) left hand side. Thus, equality will follow once we establish that $\bigsqcup_{\tau}C_\tau$ is already topologically closed.

Supposing $x$ is in a missing boundary face of some partially open Weyl chamber $C_\tau$, then the coordinates of $x$ satisfy an equality $x_d=x_{d+1}$ where $\tau_d>\tau_{d+1}$ is a descent of $\tau$. But since $\sigma_1,\ldots, \sigma_l$ are all increasing, this can happen only if $\tau_d$ and $\tau_{d+1}$ belong to two different permutations, say $\sigma_i$ and respectively $\sigma_j$, for some $i\not=j$. This implies that the permutation $\tau'$ obtained from $\tau$ by switching $\tau_d$ and $\tau_{d+1}$ is also a shuffle of $\sigma_1,\ldots, \sigma_l$, hence $x\in C_{\tau'}$, proving the equality.

This, together with the expansion from Lemma \[lem: Weyl chamber decomposition shuffle\] for the characteristic function $\lbrack C_\tau\rbrack$ implies the identity for characteristic functions $$\lbrack\iota^{-1}\left(\lbrack \mathbf{S}_1\rbrack^\star \cap\cdots\cap\lbrack \mathbf{S}_l\rbrack^\star\right)\rbrack=\sum_{\tau}\lbrack C_\tau\rbrack=\sum_{\tau}\left(\sum_{\pi_\tau}(-1)^{m-\operatorname{len}(\pi_\tau)}\lbrack\iota^{-1}(\pi_\tau^\star)\rbrack\right),$$ where the inner sum is over all lumpings of the plate $\pi_\tau$ which can occur at the descents of $\tau$.

It follows from Theorem 2.3 of [@BarvinokPammersheim] that the $\iota$ induces a unique linear map on the space of characteristic functions, and we obtain $$\lbrack\lbrack \mathbf{S}_1\rbrack^\star \cap\cdots\cap\lbrack \mathbf{S}_l\rbrack^\star\rbrack=\sum_{\tau}\lbrack \iota(C_\tau)\rbrack=\sum_{\tau}\left(\sum_{\pi_\tau}(-1)^{m-\operatorname{len}(\pi_\tau)}\lbrack\pi_\tau^\star\rbrack\right).$$ We finally dualize again to obtain the sum over all shuffle-lumpings $$\lbrack\lbrack \mathbf{S}_1\rbrack\rbrack\bullet \cdots \bullet\lbrack \lbrack\mathbf{S}_l\rbrack\rbrack=\sum_\pi(-1)^{m-\operatorname{len}(\pi)}\lbrack\pi\rbrack.$$

Note that in the convolution $\lbrack\lbrack\mathbf{S}_1\rbrack\rbrack \bullet\cdots\bullet\lbrack\lbrack\mathbf{S}_l\rbrack\rbrack$, since the subsets $\cup_{S\in \mathbf{S}_1}S,\ldots, \sum_{S\in\mathbf{S}_l}S$ are assumed to be mutually disjoint, the plates $\lbrack\mathbf{S}_i\rbrack$ live in mutually orthogonal subspaces $$\left\{x\in V_0^n:\sum_{S\in\mathbf{S}_i}x_S =0,\text{ and } x_j=0\text{ for } j\not\in\cup_{S\in\mathbf{S}_i}S\right\}\subseteq V_0^n,$$ for $i=1,\ldots, l$.

Let $S_{1}=\{1\}$ and $(S_{2},S_{3})=(\{2\},\{3\})$. Then Theorem \[thm: shuffleLump Identity\] says that $$\lbrack\lbrack 1\rbrack\rbrack\bullet \lbrack\lbrack 2,3\rbrack\rbrack =\lbrack\lbrack 1,2,3\rbrack\rbrack+\lbrack\lbrack 2,1,3\rbrack\rbrack+\lbrack\lbrack 2,3,1\rbrack\rbrack-\left(\lbrack\lbrack 12,3\rbrack\rbrack+\lbrack\lbrack 2,13\rbrack\rbrack\right).$$ See Figure \[fig:plate-relations-complete\].

![The characteristic function $\lbrack\lbrack 1\rbrack\rbrack\bullet \lbrack\lbrack 2,3\rbrack\rbrack$[]{data-label="fig:plate-relations-complete"}](Plate_Relations_Complete){width=".80\linewidth"}

Constructing the canonical plate basis {#sec: uppertriangularmap}
======================================

We generalize the notion of the cycle decomposition, from permutations to ordered set partitions. The geometric motivation is to establish a graded basis for $\hat{\mathcal{P}}^n$ such that the $d^\text{th}$ graded piece is spanned by characteristic functions of faces of dimension $d$ of the all-subset hyperplane arrangement. These faces are Minkowski sums of standard plates which lie in mutually orthogonal subspaces of $V_0^n$.

In what follows, we fix once and for all the *standard* ordered set partition $(I_1,I_2,\dots, I_n)$ of $\{1,\ldots, n\}$, where $I_j=\{j\}$. For compactness, we shall abuse notation and write $j$ instead of $I_j$. However, it should not be forgotten that this obscures an action of the product group $\mathfrak{S}_n\times \mathfrak{S}_n$, where one factor permutes the order of the blocks and the other permutes their contents.

\[defn:composite set partition\] A *composite set partition* of $\{1,\ldots, n\}$ is a set $\{\mathbf{S}_1,\ldots,\mathbf{S}_l\}$ where each $\mathbf{S}_i$ is an ordered set partition of a subset $J_i\subset \{1,\ldots, n\}$, such that $\{J_1,\ldots, J_l\}$ is an (unordered) set partition of $\{1,\ldots, n\}$. If each $\mathbf{S}_i$ has the property that its first block contains the minimal label in $J_i$, then the composite set partition is called *standard.*

Say that a composite set partition $\{\mathbf{S}_1,\ldots,\mathbf{S}_l\}$ satisfies the orientations, $p_a<p_b$ respectively $p_a>p_b$, if either (1) $a$ and $b$ are in different ordered set partitions $\mathbf{S}_i$ and respectively $\mathbf{S}_j$, or (2) $a$ and $b$ are both in some ordered set partition $\mathbf{S}_i$ and $p_a<p_b$, respectively $p_a<p_b$. Say that $p_a=p_b$ if and only if $a$ and $b$ are in the same block of the same ordered set partition. Note that any composite set partition $\{\mathbf{S}_1,\ldots,\mathbf{S}_l\}$ labels a convolution product of characteristic functions of plates.

Looking toward Theorem \[thm:unitriangularMap\] we define preemptively the canonical bases for the four spaces $\hat{\mathcal{P}}^n$, $\mathcal{P}^n$, $\hat{\mathcal{P}}_1^n$ and $\mathcal{P}_1^n$.

The canonical basis for $\hat{\mathcal{P}}^n$ will consist of all characteristic functions $$\lbrack\lbrack\mathbf{S}_1\rbrack\rbrack\bullet\cdots\bullet\lbrack\lbrack \mathbf{S}_l\rbrack\rbrack,$$ as $\{\mathbf{S}_1,\ldots,\mathbf{S}_l\}$ runs over all standard composite set partitions. The canonical basis for $\mathcal{P}^n$ will be obtained from the subset of the above, consisting of all characteristic functions $$\lbrack\lbrack S_1,\ldots, S_k\rbrack\rbrack,$$ as $(S_1,\ldots, S_k)$ runs over all ordered set partitions of $\{1,\ldots, n\}$ such that $1\in S_1$. The canonical basis for $\hat{\mathcal{P}}_1^n$ will be obtained from the subset of the above, consisting of all characteristic functions $$\lbrack\lbrack\mathbf{S}_1\rbrack\rbrack\bullet\cdots\bullet\lbrack\lbrack \mathbf{S}_l\rbrack\rbrack$$ labeled by standard composite ordered set partitions $(\mathbf{S}_1\rbrack\rbrack\bullet\cdots\bullet\lbrack\lbrack \mathbf{S}_l)$ of $\{1,\ldots, n\}$ where each block of each $\mathbf{S}_i$ is a singlet. Finally, the canonical basis for $\mathcal{P}^n$ consists of the ordered set partitions labeled by permutations with first label 1: $$\{\lbrack\lbrack 1,i_2,\ldots, i_n\rbrack\rbrack: (i_2,\ldots, i_n)\text{ is a permutation of }\{2,\ldots, n\}\}.$$

In Lemma \[lem:FoataSets\] we define a bijection $\mathcal{U}$ between ordered set partitions $(S_1,\ldots, S_k)$ of the set $\{1,\ldots, n\}$ and standard composite set partitions. This bijection induces an endomorphism of $\hat{\mathcal{P}}^n$ appears quite analogous to the canonical decomposition of the homogeneous component of the free Lie algebra, see the discussion around Lemma 8.22 in [@ReutenauerFreeLieAlgebras]. Also note the similarity to Foata’s transform. It would be very interesting to look into these further, but we leave the investigation to future work.

\[lem:FoataSets\] There exists a bijection $\mathcal{U}$ between ordered set partitions of $\{1,\ldots, n\}$ and standard composite set partitions.

Let $(S_1,\ldots, S_k)$ be an ordered set partition of $\{1,\ldots, n\}$. We first construct from $(S_1,\ldots, S_k)$ a standard composite set partition $\{\mathbf{S}_1,\ldots,\mathbf{S}_l\}$, where $$\begin{aligned}
            \mathbf{S}_1 & = & (S_{i_l},\ldots, S_{k-1},S_{k})\\
            \mathbf{S}_2 & = & (S_{i_{l-1}},\ldots, S_{i_l-1})\\
            & \vdots &\\
            \mathbf{S}_{l-1} & = & (S_{i_2},\ldots,S_{i_3-1})\\
            \mathbf{S}_l & = & (S_1,S_2,\ldots, S_{i_2-1}).
        \end{aligned}$$ Let us first fix the notation $J_i=\cup_{S\in\mathbf{S}_i} S$. The construction is inductive:

-   If $1\in S_{i_l},$ define $\mathbf{S}_{1}=(S_{i_l},\ldots, S_k)$.

-   If standard ordered set partitions $\mathbf{S}_1,\ldots, \mathbf{S}_{j-1}$ have been determined, so that $(S_1,\ldots, S_k)$ is the concatenation $$(S_1,\ldots, S_k)=(S_1,\ldots, S_{a},\mathbf{S}_{j-1},\ldots, \mathbf{S}_1),$$ then define $\mathbf{S}_j$ to equal $$\mathbf{S}_j=(S_{i_j},\ldots, S_{a-1},S_a),$$ where the block $S_{i_j}\in \{S_1,\ldots, S_a\}$ is characterized by the property that it contains the smallest element $s_{i_j}\in\{1,\ldots, n\}$ in the complement in $(S_1,\ldots, S_k)$ of the segment to the right of $\mathbf{S}_{j-1}$, inclusive: $$s_{i_j}=\text{min}\left(\{1,\ldots, n\}\setminus \left(J_{j-1}\cup\cdots\cup J_1\right)\right).$$

Conversely, if $\{\mathbf{S}_1,\ldots, \mathbf{S}_l\}$ is a standard composite ordered set partition with minimal first block elements respectively $s_1,\ldots, s_l$, let $(s_{i_1},\ldots, s_{i_l})$ be the permutation of $(s_1,\ldots, s_l)$ such that $s_{i_1}>\cdots>s_{i_l}$. We then reconstruct the ordered set partition $(S_1,\ldots, S_k)$ as the concatenation $(\mathbf{S}_{i_l},\mathbf{S}_{i_{l-1}},\ldots\mathbf{S}_{i_1})$.

In Theorem \[thm:unitriangularMap\], combining Theorem \[thm: shuffleLump Identity\] and Lemma \[lem:FoataSets\], starting from the bijection $\mathcal{U}$ we shall induce a linear map (which we also denote by $\mathcal{U}$) to derive an automorphism of $\hat{\mathcal{P}}^n$, proving linear independence of the candidate *canonical basis* $$\left\{\lbrack\lbrack\mathbf{S}_1\rbrack\rbrack\bullet\cdots\bullet\lbrack\lbrack \mathbf{S}_l\rbrack\rbrack:\{\mathbf{S}_1,\ldots,\mathbf{S}_l\} \text{ is a standard composite set partition of $\{1,\ldots, n\}$}\right\}$$ of $\hat{\mathcal{P}}^n$. Namely, for the first step we have the linear map defined on the basis by $$\lbrack\pi\rbrack\mapsto \mathcal{U}(\lbrack\pi\rbrack)$$ where on the right-hand side $\mathcal{U}(\lbrack\pi\rbrack)=\lbrack\lbrack \mathbf{S}_1\rbrack\rbrack\bullet\cdots\bullet \lbrack\lbrack \mathbf{S}_l\rbrack\rbrack$, say, is labeled by the standard composite set partition $\{\mathbf{S}_1,\ldots, \mathbf{S}_l\}$. As for the second step, by Theorem \[thm: shuffleLump Identity\] this expands in the original basis of $\hat{\mathcal{P}}^n$ consisting of plates $\lbrack \pi\rbrack$: $$\mathcal{U}(\lbrack\pi\rbrack) = \sum_\pi(-1)^{m-\operatorname{len}(\pi)}\lbrack\pi\rbrack,$$ where $m=\text{len}(\mathbf{S}_1)+\cdots+\text{len}(\mathbf{S}_l)$ and $\pi$ runs over all shuffle-lumpings of the standard ordered set partitions $\mathbf{S}_1,\ldots, \mathbf{S}_l$.

It may be interesting to compare Theorem \[thm:unitriangularMap\] in what follows with Theorem 5.1 of [@ReutenauerFreeLieAlgebras] on the construction of the Hall basis of the free Lie algebra, using the set of Lyndon words, ordered alphabetically, for the Hall set.

We define a map $\mathcal{C}$ from the set of ordered set partitions to the set of *packed words* in $\{0,\ldots, n-1\}$, that is sequences $\{c_1,\ldots, c_n\}\in\{0,\ldots, n-1\}^n$ satisfying the conditions

1.  $0\in\{c_1,\ldots, c_n\}$ and

2.  Successive values increase in steps of 1.

\[prop: bijection\] There exists a bijection $$\mathcal{C}:\{\text{Ordered set partitions of } \{1,\ldots, n\}\} \rightarrow \{\text{packed words in } \{0,\ldots, n-1\}\}.$$

Let $\mathbf{T}=(T_1,\ldots, T_{k})$ be an ordered set partition of $\{1,\ldots, n\}$. We define a sequence $(c_1,\ldots, c_n)$ by $c_i=j-1$, if $i\in T_j$. By construction $0=c_i$ for some $i$ and the sequence is a packed word on $\{0,\ldots, n-1\}$: if some $c\ge 1$ satisfies $c\in\{c_1,\ldots, c_n\}$ then $c-1$ satisfies the same. Define $\mathcal{C}(\mathbf{T})=(c_1,\ldots, c_n)$. Conversely, if $(c_1,\ldots, c_n)$ is a packed word on $\{0,\ldots, n-1\}$, define an ordered set partition $\mathbf{T}=(T_1,\ldots, T_k)$ by letting $T_i=\{m\in\{1,\ldots, n\}:c_m=i-1\}$.

In what follows, we induce a partial order on the ordered set partitions from the lexicographic order on packed words in $\{0,\ldots, n-1\}$.

\[defin:lexicographicorder\] Given two plates $\pi_1=\lbrack(T_1,\ldots, T_k)\rbrack,\ \pi_2=\lbrack(T_1',\ldots, T_{l}')\rbrack$, say that $\pi_1 \prec \pi_2$ if $$\mathcal{C}(T_1,\ldots, T_k)<\mathcal{C}(T_1',\ldots, T_l')$$ in the lexicographic order. This induces a total order on the set of plates, and thus on the basis of their characteristic functions, in $\hat{\mathcal{P}}^n$.

Clearly the first element of ordered basis is the characteristic function of $V_0^n$ itself, since it is labeled by the trivial ordered set partition, hence $\mathcal{C}(\lbrack 12\cdots n\rbrack)=(0,\ldots,0)$. Similarly, the last element is labeled by the ordered set partition $(\{n\},\{n-1\},\ldots, \{2\},\{1\})$, where we have $\mathcal{C}(\lbrack n,n-1,\ldots, 2,1\rbrack)=(n-1,n-2\ldots,1,0)$.

We now come to our main result.

\[thm:unitriangularMap\] Let $\mathcal{B}^n$ be the set of characteristic functions of plates for the space $\hat{\mathcal{P}}^n$, labeled by ordered set partitions of $\{1,\ldots, n\}$. By Proposition \[Prop: UniversalPlateModuleFreelyGenerated\] this is a basis, which we order lexicographically. Then, the set $$\left\{\lbrack\lbrack\mathbf{S}_1\rbrack\rbrack\bullet\cdots\bullet\lbrack\lbrack \mathbf{S}_l\rbrack\rbrack:\{\mathbf{S}_1,\ldots,\mathbf{S}_l\} \text{ is a standard composite set partition of $\{1,\ldots, n\}$}\right\}$$ is also a basis.

By Theorem \[thm: shuffleLump Identity\] we have $$\lbrack\lbrack\mathbf{S}_1\rbrack\rbrack\bullet \cdots\bullet \lbrack\lbrack \mathbf{S}_{l}\rbrack\rbrack= \sum_\pi(-1)^{m-\operatorname{len}(\pi)}\lbrack\pi\rbrack,$$ where $m=k_1+\cdots+k_l$ and $\pi$ runs over all shuffle-lumpings of the ordered set partitions $\mathbf{S}_1,\ldots,\mathbf{S}_l$.

We prove that the matrix of the endomorphism $$\lbrack\pi\rbrack\mapsto \mathcal{U}(\lbrack\pi\rbrack)=\lbrack\lbrack\mathbf{S}_1\rbrack\rbrack\bullet \cdots\bullet \lbrack\lbrack \mathbf{S}_{l}\rbrack\rbrack=\sum_\pi(-1)^{m-\operatorname{len}(\pi)}\lbrack\pi\rbrack$$ is upper triangular with 1’s on the diagonal, with respect to the lexicographically ordered basis $\mathcal{B}^n$ of plates.

First note that as $\mathcal{U}(\lbrack\pi\rbrack)$ contains $\lbrack\pi\rbrack$ itself as a summand, it suffices to prove that $\mathcal{U}$ is order non-increasing with respect to the lexicographic ordering from Definition \[defin:lexicographicorder\] on ordered set partitions.

With $\{\mathbf{S}_1,\ldots, \mathbf{S}_l\}$ the standard composite set partition coming from Lemma \[lem:FoataSets\] applied to the plate $\pi=\lbrack S_1,\ldots, S_k\rbrack$, consider an arbitrary (signed) summand of $\mathcal{U}(\lbrack\pi\rbrack)$. Such a summand is labeled by a shuffle-lumping $\mathbf{T}=(T_1,\ldots, T_m)$ of the ordered set partitions $\mathbf{S}_1,\ldots, \mathbf{S}_l$, with respect to the ordered set partition $(\{1\},\ldots, \{n\})$. It follows from the construction of the ordered set partitions $\mathbf{S}_1,\ldots,\mathbf{S}_l$ from $(S_1,\ldots, S_k)$ in Lemma \[lem:FoataSets\], that among all of their shuffle-lumpings $(S_1,\ldots, S_k)$ itself occurs and is maximal in the lexicographic order. It follows that the matrix for $\mathcal{U}$ is upper triangular with 1’s on the diagonal. It follows that $\mathcal{U}$ is invertible.

One can see that elements in the canonical plate basis are convolution products $\lbrack \pi_1\rbrack \bullet \cdots\bullet \lbrack\pi_k\rbrack$ of characteristic functions of plates $\pi_1,\ldots,\pi_k$ which live in mutually orthogonal subspaces of $V_0^n$; this means that the canonical plate basis consists of Cartesian products of standard plates.

With respect to the lexicographic order $$(0,0,0),(0,0,1),(0,1,0),(0,1,1),(0,1,2),(0,2,1),(1,0,0),(1,0,1),$$ $$(1,0,2),(1,1,0),(1,2,0),(2,0,1),(2,1,0),$$ via the bijection $\mathcal{C}$, for the basis of characteristic functions of plates we have respectively $$\lbrack\lbrack123\rbrack\rbrack,\lbrack\lbrack12,3\rbrack\rbrack,\lbrack\lbrack13,2\rbrack\rbrack,\lbrack\lbrack1,23\rbrack\rbrack,\lbrack\lbrack1,2,3\rbrack\rbrack,\lbrack\lbrack1,3,2\rbrack\rbrack,\lbrack\lbrack23,1\rbrack\rbrack,\lbrack\lbrack2,13\rbrack\rbrack,$$ $$\lbrack\lbrack2,1,3\rbrack\rbrack,\lbrack\lbrack3,12\rbrack\rbrack,\lbrack\lbrack3,1,2\rbrack\rbrack,\lbrack\lbrack2,3,1\rbrack\rbrack,\lbrack\lbrack3,2,1\rbrack\rbrack$$ and the map $\mathcal{U}$ takes the form $$\left(
        \begin{array}{ccccccccccccc}
        1 & 0 & 0 & 0 & 0 & 0 & -1 & -1 & 0 & -1 & 0 & 0 & 1 \\
        0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 1 & 0 & -1 & -1 \\
        0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & -1 & 0 & -1 \\
        0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & -1 & 0 & -1 & 0 & -1 \\
        0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\
        0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 \\
        0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & -1 \\
        0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & -1 & -1 \\
        0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 \\
        0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & -1 \\
        0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\
        0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\
        0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
        \end{array}
        \right),$$ where columns 7 through 13 label linear combinations of characteristic functions of plates which vanish outside a cone of codimension at least 1. It is informative to verify (for example, graphically, using inclusion-exclusion, as in Figure \[fig:plate-relations-complete\]) that the rightmost column, an alternating sum over all 13 plates, encodes the characteristic function of the point $(0,0,0)$, and that column 7 expresses $$\lbrack\lbrack23,1\rbrack\rbrack\mapsto \lbrack\lbrack23,1 \rbrack\rbrack+\lbrack\lbrack1,23 \rbrack\rbrack-\lbrack\lbrack123\rbrack\rbrack = \lbrack\lbrack1 \rbrack\rbrack\bullet \lbrack\lbrack23\rbrack\rbrack.$$ Finally, column 12 encodes $$\lbrack\lbrack2,3,1 \rbrack\rbrack\mapsto\lbrack\lbrack2,3,1 \rbrack\rbrack +\lbrack\lbrack2,1,3\rbrack\rbrack - \lbrack\lbrack2,13 \rbrack\rbrack+\lbrack\lbrack1,2,3\rbrack\rbrack- \lbrack\lbrack12,3\rbrack\rbrack= \lbrack\lbrack1 \rbrack\rbrack\bullet \lbrack\lbrack2,3\rbrack\rbrack,$$ or, in an order in which it is perhaps easier to see the shuffle-lumping, $$\lbrack\lbrack1 \rbrack\rbrack\bullet \lbrack\lbrack2,3\rbrack\rbrack=\lbrack\lbrack2,3,1 \rbrack\rbrack - \lbrack\lbrack2,13 \rbrack\rbrack +\lbrack\lbrack2,1,3\rbrack\rbrack- \lbrack\lbrack12,3\rbrack\rbrack+\lbrack\lbrack1,2,3\rbrack\rbrack.$$

The following more involved example will serve to illustrate the upper-triangularity of Theorem \[thm:unitriangularMap\].

We have $$\mathcal{U}(\lbrack\lbrack 4\ 11,10,3,5\ 7,6\ 8,1\ 9,2\rbrack\rbrack)=\lbrack\lbrack 1\ 9,2\rbrack\rbrack \bullet\lbrack\lbrack 3,5\ 7,6\ 8\rbrack\rbrack\bullet \lbrack\lbrack 4\ 11,10\rbrack\rbrack,$$ where we omit the (rather long) alternating sum over all shuffle-lumpings of the ordered set partitions $$(1\ 9,2), (3, 5\ 7,6\ 8), (4\ 11,10).$$ It is a useful exercise to apply Lemma \[lem:FoataSets\] to check that $$\mathcal{C}(\{4,11\},\{10\},\{3\},\{5,7\},\{6,8\},\{1,9\},\{2\})=(5,6,2,0,3,4,3,4,5,1,0)$$ and verify that $(\{4,11\},\{10\},\{3\},\{5,7\},\{6,8\},\{1,9\},\{2\})$ is the shuffle-lumping that is maximal with respect to the lexicographic ordering: switching or merging any two blocks which are not in the same ordered set partition results in a lexicographically smaller ordered set partition. For example, the shuffle-lumping obtained by merging $\{3\}$ and $\{10\}$, which are in distinct ordered set partitions, obviously decreases the lexicographic order: $$\mathcal{C}(\{4,11\},\{3,10\},\{5,7\},\{6,8\},\{1,9\},\{2\})=(4,5,1,0,2,3,2,3,4,1,0),$$ as does switching $\{3\}$ and $\{10\}$: $$\mathcal{C}(\{4,11\},\{3\},\{10\},\{5,7\},\{6,8\},\{1,9\},\{2\})=(5,6,1,0,3,4,3,4,5,2,0).$$

As a consequence of Theorem \[thm:unitriangularMap\] we have Corollary \[cor:Lineardimensions\].

\[cor:Lineardimensions\] The linear dimension of the degree $k$ component $(\hat{\mathcal{P}}^n)_k$ of the space $\hat{\mathcal{P}}^n$, consisting of linear combinations of characteristic functions of total dimension $k$ Minkowski sums of plates, is equal to the number of standard composite set partitions $\{\mathbf{S}_1,\ldots, \mathbf{S}_k\}$ of $\{1,\ldots, n\}$. Namely, $$\dim((\hat{\mathcal{P}}^n)_k)=\sum_{i=k}^n S(n,i)s(i,k).$$ Likewise, the linear dimension of the degree $k$ component of the space $\hat{\mathcal{P}}_1^n$, consisting of linear combinations of characteristic functions of , total dimension $k$ Minkowski sums of plates, is equal to the $k$th Stirling number of the first kind, $$\dim((\hat{\mathcal{P}}^n_{1})_k)= S(n,n)s(n,k)=s(n,k).$$ Here $S(n,i)$ is the Stirling number of the second kind, which counts the number of set partitions of $\{1,\ldots, n\}$ into $i$ blocks, and $s(i,k)$ is the Stirling number of the first kind, which counts the number of permutations of $\{1,\ldots, i\}$ which decompose as a product of $k$ disjoint cycles.

In the formula for $\dim((\hat{\mathcal{P}}^n)_k)$, the contribution $S(n,i)s(i,k)$ is the product of the number of set partitions of $n$ with $i$ blocks, times the number of permutations of $\{1,\ldots, i\}$ which decompose into $k$ disjoint cycles. This is exactly the enumeration of the standard composite set partitions $\{\mathbf{S}_1,\ldots, \mathbf{S}_k\}$: each $\mathbf{S}_a$ is a standard ordered set partition and $$\bigcup_{S\in \mathbf{S}_1} S\cup\cdots\cup \bigcup_{S\in \mathbf{S}_k} S=\{1,\ldots, n\}.$$

The formula for the dimension of the $k^\text{th}$ graded component $(\hat{\mathcal{P}}_{1}^n)_k$ follows by taking the unique ordered set partition $(\{1\},\ldots, \{n\})$ of $\{1,\ldots, n\}$ and counting the number of permutations of $\{1,\ldots, n\}$ which decompose into $k$ disjoint cycles.

The formula in Corollary \[cor:Lineardimensions\] is given in O.E.I.S. A079641, the matrix product of the Stirling numbers of the second kind with the unsigned Stirling numbers of the first kind. The first six rows are given below; note that the rows sum to the ordered Bell numbers $( 1, 3, 13, 75, 541, 4683)$. $$\begin{array}{cccccc}
        1&&&&&\\
        2 & 1 &  &  &  &\\
        6 & 6 & 1 &  &  &\\
        26 & 36 & 12 & 1 && \\
        150 & 250 & 120 & 20 & 1 & \\
        1082 & 2040 & 1230 & 300 & 30 & 1 \\
        \end{array}$$ The canonical basis for $\hat{\mathcal{P}}_1^n$ has graded dimension given by the Stirling numbers of the first kind, $$\begin{array}{cccccc}
        1&&&&&\\
        1 & 1 &  &  &  &\\
        2 & 3 & 1 &  &  &\\
        6 & 11 & 6 & 1 && \\
        24 & 50 & 35 & 10 & 1 & \\
        120 & 274 & 225 & 85 & 15 & 1. \\
        \end{array}$$

Plates and trees {#sec:PlatesTrees}
================

Let $\{(i_1,j_1),\ldots, (i_{n-1},j_{n-1})\}$ be the set of oriented edges of a directed tree $\mathcal{T}$ on the vertex set $\{1,\ldots, n\}$. This data encodes a certain permutohedral cone which is also simplicial, given explicitly as the conical hull $$\pi_{\mathcal{T}}=\langle e_{i_1}-e_{j_1},\ldots, e_{i_{n-1}}-e_{j_{n-1}}\rangle_+.$$

In Theorem \[thm:treeExpansionCompletePlates\] we present a combinatorial formula which expands the characteristic function of the permutohedral cone assigned to any oriented tree on $n$ vertices as a signed sum of characteristic functions of plates.

The proof of Theorem \[thm:treeExpansionCompletePlates\] follows closely that of Theorem \[thm: shuffleLump Identity\]. The idea is to decompose a union of overlapping closed Weyl chambers into a disjoint union of partially open Weyl chambers; then the characteristic function of the disjoint union expands using the formula in Lemma \[lem: Weyl chamber decomposition shuffle\]. Then we dualize to get the permutohedral cone $\pi_{\mathcal{T}}$.

Note that Theorem \[thm:treeExpansionCompletePlates\] appears to first order in [@HeSon] as a shuffle-identity among rational functions.

\[thm:treeExpansionCompletePlates\] Let $\mathcal{T}=\{(i_1,j_1),\ldots(i_{n-1},j_{n-1})\}$ be a directed tree. We have, in the space $\hat{\mathcal{P}}^n$, the identity of characteristic functions $$\lbrack\langle e_{i_1}-e_{j_1},\ldots, e_{i_{n-1}}-e_{j_{n-1}}\rangle_+\rbrack= \sum_{\pi:p_{i_a} < p_{j_a}}(-1)^{n-\operatorname{len}(\pi)}\lbrack\pi\rbrack,$$ where we recall that $p_{i_a}<p_{j_a}$ if and only if in the ordered set partition which labels $\pi$, the label $i_a$ is in a block strictly to the left of the block containing $j_a$.

The dual cone is defined by the equations $$\langle e_{i_1}-e_{j_1},\ldots, e_{i_{n-1}}-e_{j_{n-1}}\rangle_+^\star=\left\{y\in V_0^n:y_{i_1}\ge y_{j_1},\ldots, y_{j_{n-1}}\ge y_{j_{n-1}}\right\}.$$ We first claim that this is a union of those Weyl chambers $\cup_\tau\lbrack\tau\rbrack^\star$ defined by $y_{\tau_1}\ge\cdots\ge y_{\tau_m}$ which satisfy the $n-1$ conditions $\tau_{i_1}>\tau_{j_1},\ \ldots,\ \tau_{i_{n-1}}>\tau_{j_{n-1}}$. To see this, let $\bar{e}_{I_1},\ldots, \bar{e}_{I_{n-1}}$ be the basis which is orthogonally dual to $e_{i_1}-e_{j_1},\ldots, e_{i_{n-1}}-e_{j_{n-1}}$, so that $\bar{e}_{I_a}\cdot (e_{i_b}-e_{j_b})=\delta_{a,b}$. Then we have from the corresponding vector space isomorphism a bijection of cone points $$\langle e_{i_1}-e_{j_1},\ldots, e_{i_{n-1}}-e_{j_{n-1}}\rangle_+\rightarrow \langle e_{i_1}-e_{j_1},\ldots, e_{i_{n-1}}-e_{j_{n-1}}\rangle_+^\star=\langle\bar{e}_{I_1},\ldots, \bar{e}_{I_{n-1}}\rangle_+$$ defined by $e_{i_a}-e_{j_a}\mapsto \bar{e}_{I_a}$, that is $$\sum_{a=1}^{n-1}t_a (e_{i_a}-e_{j_a})\mapsto \sum_{a=1}^{n-1}t_a \bar{e}_{I_a}.$$ Let $\lbrack \alpha_1\rbrack^\star,\ldots, \lbrack \alpha_m\rbrack^\star$ be the minimal set of Weyl chambers such that $$\langle e_{i_1}-e_{j_1},\ldots, e_{i_{n-1}}-e_{j_{n-1}}\rangle_+^\star\subseteq\cup_{i=1}^m\lbrack\alpha_i\rbrack^\star,$$ which means that the permutations $\alpha_1,\ldots, \alpha_{m}$ are all compatible with the orders $(i_1,j_1),\ldots,$ $(i_{n-1},j_{n-1})$. We show that this is an equality: for each $y\in \cup_{i=1}^m\lbrack\alpha_i\rbrack^\star$, since $\bar{e}_{I_1},\ldots, \bar{e}_{I_{n-1}}$ is a basis for $V_0^n$ we have $y=\sum_{a=1}^{n-1} t_a \bar{e}_{I_a}$ for some $t_a\in\mathbb{R}$, for equality it suffices to show that $y_{i_a}-y_{j_a}=y\cdot(e_{i_a}-e_{j_a})=t_a\ge 0$ for all $a=1,\ldots, n-1$. But having $y_{i_a}-y_{j_a}<0$ for some $a$ would imply that $\alpha_i$ is not compatible with the order $(i_1,j_1),\ldots, (i_{n-1},j_{n-1})$.

As in Theorem \[thm: shuffleLump Identity\], we replace the Weyl chambers $\lbrack\tau\rbrack^\star$ with the (mutually disjoint) partially open Weyl chambers $C_\tau$ from Lemma \[lem: Weyl chamber decomposition shuffle\]. By construction these all satisfy the inequalities defining the dual cone, and we correspondingly have, for characteristic functions, $$\lbrack\langle e_{i_1}-e_{j_1},\ldots, e_{i_{n-1}}-e_{j_{n-1}}\rangle_+^\star\rbrack=\sum_\tau\lbrack C_\tau\rbrack,$$ where the sum is over all permutations $\tau=(\tau_1,\ldots, \tau_n)$ satisfying the $n-1$ conditions $\tau_{i_1}>\tau_{j_1},\ \ldots,\ \tau_{i_{n-1}}>\tau_{j_{n-1}}$.

But from Lemma \[lem: Weyl chamber decomposition shuffle\], for each such $\tau$ we have the further decomposition $$\lbrack C_\tau\rbrack=\sum_\pi(-1)^{n-\operatorname{len}(\pi)}\lbrack\pi^\star\rbrack,$$ where the sum is over all plates $\pi=\lbrack S_1,\ldots, S_k\rbrack$ which are labeled by ordered set partitions $(S_1,\ldots, S_k)$ such that each block is labeled by a permutation which has the set of consecutive descents of $\tau$, of the form $\tau_{i_1}>\tau_{i_2}>\cdots>\tau_{i_{\vert S_i\vert}}.$ Summing over all such $\tau$ we obtain $$\lbrack\langle e_{i_1}-e_{j_1},\ldots, e_{i_{n-1}}-e_{j_{n-1}}\rangle_+\rbrack= \sum_{\pi:p_{i_a} < p_{j_a}}(-1)^{n-\operatorname{len}(\pi)}\lbrack\pi\rbrack,$$ which completes the proof.

\[Example: tree relation\] Let $\mathcal{T}=\langle e_1-e_2,e_1-e_3\rangle_+$. Then $$\lbrack \langle e_1-e_2,e_1-e_3\rangle_+\rbrack = \lbrack\lbrack 1,2,3\rbrack\rbrack+\lbrack\lbrack 1,3,2\rbrack\rbrack-\lbrack\lbrack 1,23\rbrack\rbrack.$$

![The relation for Example \[Example: tree relation\] and its dual[]{data-label="fig:exampletreeplaterelation"}](Example_Tree_Plate_relation){width=".7\linewidth"}

\[cor:treeSetpartition\] Let $\mathcal{T}= \{(i_1,j_1),\ldots, (i_{k-1},j_{k-1})\}$ be a directed tree, where $i_a,j_a\in\{1,\ldots, k\}$ with $i_a\not=j_a$. Let $\{S_1,\ldots, S_k\}$ be a collection of disjoint nonempty subsets of $\{1,\ldots, n\}$. We have $$\lbrack\lbrack S_{i_1},S_{j_1}\rbrack\rbrack\bullet\cdots\bullet \lbrack\lbrack S_{i_{k-1}},S_{j_{k-1}}\rbrack\rbrack=\sum_{\pi:p_{i_a} < p_{j_a}}(-1)^{k-\operatorname{len}(\pi)}\lbrack\pi\rbrack.$$

The proof of Theorem \[thm:treeExpansionCompletePlates\] generalizes with minimal adjustment to the present case, when $\{1,2,\ldots, n\}$ is replaced by any collection of disjoint nonempty subsets $(S_1,\ldots, S_k)$.

Straightening plates to the canonical basis {#sec:straightening}
===========================================

We prove in Theorem \[thm:Straightening\] the general expression for the expansion of a plate in the canonical basis for $\hat{\mathcal{P}}^n$. This implies the result of Ocneanu’s original computation of the *plate relations* in which he worked in a vector space generated formally by rooted binary trees. Note that in practice one often works in one of the quotient spaces $\mathcal{P}^n$, $\hat{\mathcal{P}}_1^n$ or $\mathcal{P}_1^n$, see Corollary \[cor:plate relations quotient\].

Recall that if $\{\mathbf{T}_1,\ldots, \mathbf{T}_m\}$ is a composite set partition of $\{1,\ldots, n\}$, then we say that $p_i<p_j$ if either of the following two conditions hold:

1.  $i$ and $j$ are in the same ordered set partition $\mathcal{T}_a$ with $p_i<p_j$, or

2.  $i$ and $j$ are in different ordered set partitions $\mathbf{T}_a$ and $\mathbf{T}_b$, respectively, with $a\not=b$.

Further, we say that $p_i=p_j$ if $i$ and $j$ are in the same block of the same ordered set partition.

\[thm:Straightening\] Let $(S_l,S_{l-1},\ldots, S_1,S_{l+1},\ldots, S_k)$ be an ordered set partition of $\{1,\ldots, n\}$. We have $$\begin{aligned}
        &&\lbrack\lbrack S_l,S_{l-1},\ldots, S_1,S_{l+1},\ldots, S_k\rbrack\rbrack \\
        & = & \sum_{m=1}^k\sum_{\{\mathbf{T}_1,\ldots,\mathbf{T}_m\}}\sum_{\pi}(-1)^{c}(-1)^{(\text{len}(\mathbf{T}_1)+(k-l))-\text{len}(\pi)}\lbrack\lbrack\mathbf{T}_2\rbrack\rbrack \bullet\cdots\bullet \lbrack\lbrack\mathbf{T}_m\rbrack\rbrack\bullet\lbrack\pi\rbrack,
    \end{aligned}$$ where the sum $\sum_\pi$ varies over all ordered set partitions of $$\left(\bigcup_{U\in \mathbf{T}_1} U\right) \cup S_{l+1}\cup\cdots\cup S_k$$ satisfying the orientations $$p_{(S_l)}\ge p_{(S_{l-1})}\ge \cdots\ge p_{(S_1)}<p_{(S_{l+1})}<\cdots<p_{(S_k)},$$ using the symbol $p_{(S)}$ in place of $(p_{i_1}=\cdots =p_{i_{\vert S\vert}})$ whenever $S=\{i_1,\ldots, i_{\vert S\vert}\}\subseteq\{1,\ldots,n\}$. The outer sum is over all composite set partitions $\{\mathbf{T}_1,\ldots,\mathbf{T}_m\}$ of $\cup_{i=1}^l S_i$ satisfying the same orientations $$p_{(S_l)}\ge p_{(S_{l-1})}\ge \cdots\ge p_{(S_1)}<p_{(S_{l+1})}<\cdots<p_{(S_k)}.$$ Here $c=\vert \{i\in \{1,\ldots, l-1\}: p_i<p_{i+1}\}\vert$ counts the pairs $(S_i,S_{i+1})$ such that $S_i$ and $S_{i+1}$ are in the same ordered set partition $\mathbf{T}_a$ with the (strict) orientation $p_i<p_{i+1}$.

Let us use the notation

-   $\lbrack\lbrack S,S'\rbrack\rbrack^{(c_1)}=\lbrack\lbrack S' S\rbrack\rbrack$,

-   $\lbrack\lbrack S,S'\rbrack\rbrack^{(c_2)}=\lbrack\lbrack S', S\rbrack\rbrack$,

-   $\lbrack\lbrack S,S'\rbrack\rbrack^{(c_3)}=\lbrack\lbrack S\rbrack\rbrack\bullet \lbrack\lbrack S'\rbrack\rbrack$.

Due to the relation $$\lbrack\lbrack S,S'\rbrack\rbrack = \lbrack\lbrack S'S\rbrack\rbrack - \lbrack\lbrack S',S\rbrack\rbrack +\lbrack\lbrack S\rbrack\rbrack\bullet \lbrack\lbrack S'\rbrack\rbrack =\lbrack\lbrack S,S'\rbrack\rbrack^{(c_1)}-\lbrack\lbrack S,S'\rbrack\rbrack^{(c_2)}+\lbrack\lbrack S,S'\rbrack\rbrack^{(c_3)} ,$$ where $S,S'$ are nontrivial disjoint subsets of $\{1,\ldots, n\}$, as well as $$\lbrack\lbrack S_l,S_{l-1},\ldots, S_1\rbrack\rbrack = \lbrack\lbrack S_l,S_{l-1}\rbrack\rbrack\bullet \lbrack\lbrack S_{l-1},S_{l-2}\rbrack\rbrack \bullet\cdots\bullet \lbrack\lbrack S_{2},S_1\rbrack \rbrack,$$ we have $$\begin{aligned}
    & & \lbrack\lbrack S_l,S_{l-1},\ldots,S_1\rbrack\rbrack\\
    & = & \left(\lbrack\lbrack S_{1}S_{2}\rbrack\rbrack-\lbrack\lbrack S_{1},S_{2}\rbrack\rbrack +\lbrack\lbrack S_1\rbrack\rbrack\bullet \lbrack\lbrack S_2\rbrack\rbrack\right)\bullet\cdots\bullet \left(\lbrack\lbrack S_{l-1}S_{l}\rbrack\rbrack-\lbrack\lbrack S_{l-1},S_{l}\rbrack\rbrack +\lbrack\lbrack S_{l-1}\rbrack\rbrack\bullet \lbrack\lbrack S_{l}\rbrack\rbrack\right)\\
    & = & \sum_{w\in \{c_1,c_2,c_3\}^{l-1}}(-1)^{\#_{c_2}(w)}\lbrack\lbrack S_1,S_2\rbrack\rbrack^{(w_1)}\bullet \lbrack\lbrack S_2,S_3\rbrack\rbrack^{(w_2)}\bullet\cdots\bullet \lbrack\lbrack S_{l-1},S_l\rbrack\rbrack^{(w_{l-1})}\\
    & = & \sum_{m=1}^{k}\sum_{\{\mathbf{T}_1,\ldots,\mathbf{T}_m\}}(-1)^{c}\lbrack\lbrack \mathbf{T}_1\rbrack\rbrack\bullet\cdots\bullet \lbrack\lbrack\mathbf{T}_m\rbrack\rbrack,
    $$ where the sum is over all composite ordered set partitions $\{\mathbf{T}_1,\ldots, \mathbf{T}_m\}$ of $S_1\cup\cdots\cup S_l\subseteq\{1,\ldots, n\}$, for $m\in \{1,\ldots, l\}$, satisfying $$p_{(S_l)}\ge p_{(S_{l-1})}\ge \cdots\ge p_{(S_1)}.$$ Here $\#_{c_2}(w)$ counts the number of times that $c_2$ appears in $w\in \{c_1,c_2,c_3\}^{l-1}$, and $$c=\vert \{i\in \{1,\ldots, l-1\}: p_i<p_{i+1}\}\vert,$$ hence $\#_{c_2}(w) = c$ whenever $$\lbrack\lbrack S_1,S_2\rbrack\rbrack^{(w_1)}\bullet \lbrack\lbrack S_2,S_3\rbrack\rbrack^{(w_2)}\bullet\cdots\bullet \lbrack\lbrack S_{l-1},S_l\rbrack\rbrack^{(w_{l-1})}= \lbrack\lbrack \mathbf{T}_1\rbrack\rbrack\bullet\cdots\bullet \lbrack\lbrack\mathbf{T}_m\rbrack\rbrack.$$ Multiplying by $\lbrack\lbrack S_1,S_{l+1},\ldots, S_k\rbrack\rbrack$ we have $$\lbrack\lbrack S_l,S_{l-1},\ldots,S_1\rbrack\rbrack\bullet  \lbrack\lbrack S_1,S_{l+1},\ldots,S_k\rbrack\rbrack=\lbrack\lbrack S_{l},S_{l-1},\ldots, S_1,S_{l+1},\ldots, S_k\rbrack\rbrack,$$ hence $$\begin{aligned}
    && \lbrack\lbrack S_{l},S_{l-1},\ldots, S_1,S_{l+1},\ldots, S_k\rbrack\rbrack \\
    & = &  \sum_{m=1}^{k}\sum_{\{\mathbf{T}_1,\ldots,\mathbf{T}_m\}}(-1)^{c}\lbrack\lbrack \mathbf{T}_1\rbrack\rbrack\bullet\cdots\bullet \lbrack\lbrack\mathbf{T}_m\rbrack\rbrack\bullet \lbrack\lbrack S_1,S_{l+1},\ldots, S_k\rbrack\rbrack\\
    & = &  \sum_{m=1}^{k}\sum_{\{\mathbf{T}_1,\ldots,\mathbf{T}_m\}}(-1)^c\lbrack\lbrack \mathbf{T}_2\rbrack\rbrack\bullet\cdots\bullet \lbrack\lbrack\mathbf{T}_m\rbrack\rbrack\bullet \left(\lbrack\lbrack\mathbf{T}_1\rbrack\rbrack\bullet \lbrack\lbrack S_1,S_{l+1},\ldots, S_k\rbrack\rbrack \right),\end{aligned}$$ where in the last line we have assumed that, if we denote $\mathbf{T}_1=(U_1,\ldots, U_t)$, then $S_1\subseteq U_1$. It remains to expand the characteristic function of the permutohedral cone specified by the (directed tree) data $$\{(p_{(U_1)}<p_{(U_2)}),\ldots, (p_{(U_{t-1})}<p_{(U_t)}),(p_{(U_1)}<p_{(S_{l+1})}),(p_{(S_{l+1})}<p_{(S_{l+2})})\ldots,(p_{(S_{k-1})}<p_{(S_{k})})\}$$ in terms of the canonical plate basis. Now by Corollary \[cor:treeSetpartition\] we have $$\begin{aligned}
    \left(\lbrack\lbrack\mathbf{T}_1\rbrack\rbrack\bullet \lbrack\lbrack S_1,S_{l+1},\ldots, S_k\rbrack\rbrack\right) & = & \sum_{\pi}(-1)^{(\text{len}(\mathbf{T}_1)+(k-l+1)-1)-\text{len}(\pi)}\lbrack\pi\rbrack\\
    & = & \sum_{\pi}(-1)^{(\text{len}(\mathbf{T}_1)+(k-l))-\text{len}(\pi)}\lbrack\pi\rbrack\\\end{aligned}$$ where the sum is over all ordered set partitions satisfying the orientations specified by the tree; note that $S_1$ must be in the first block of each $\pi$, that is all $\pi$ which appear in the sum are *standard* ordered set partitions. It follows that $$\lbrack\lbrack S_{l},S_{l-1},\ldots, S_1,S_{l+1},\ldots, S_k\rbrack\rbrack$$ $$=\sum_{m=1}^{k}\sum_{\{\mathbf{T}_1,\ldots,\mathbf{T}_m\}}(-1)^c\lbrack\lbrack \mathbf{T}_2\rbrack\rbrack\bullet\cdots\bullet \lbrack\lbrack\mathbf{T}_m\rbrack\rbrack\bullet\left(\sum_{\pi}(-1)^{(\text{len}(\mathbf{T}_1)+(k-l))-\text{len}(\pi)}\lbrack\pi\rbrack\right)$$ $$=\sum_{m=1}^k\sum_{\{\mathbf{T}_1,\ldots,\mathbf{T}_m\}}\sum_{\pi}(-1)^{c}(-1)^{(\text{len}(\mathbf{T}_1)+(k-l))-\text{len}(\pi)}\lbrack\lbrack\mathbf{T}_2\rbrack\rbrack \bullet\cdots\bullet \lbrack\lbrack\mathbf{T}_m\rbrack\rbrack\bullet\lbrack\pi\rbrack.$$

In Figure \[fig:exampleplaterelationsnice3\] we illustrate an expansion of the characteristic function $\lbrack\lbrack 2,1,3\rbrack\rbrack$ in the canonical plate basis.

![Some computations in the convolution algebra of permutohedral cones: straightening to the canonical plate basis[]{data-label="fig:exampleplaterelationsnice3"}](Example_Plate_relations_nice_3){width=".9\linewidth"}

Let us indicate the key steps in straightening $\lbrack\lbrack 3,2,1,4,5\rbrack\rbrack$ to the canonical basis. We have $$\begin{aligned}
 & & \lbrack\lbrack 3,2,1,4,5\rbrack\rbrack\\
 & = &  \left(\lbrack\lbrack 23\rbrack\rbrack -\lbrack\lbrack 2,3\rbrack\rbrack +1 \right)\bullet \left(\lbrack\lbrack 12\rbrack\rbrack -\lbrack\lbrack 1,2\rbrack\rbrack +1 \right)\bullet\lbrack\lbrack 1,4,5\rbrack\rbrack\\
& = & \left(\lbrack\lbrack 123\rbrack\rbrack - \lbrack\lbrack 1,23\rbrack\rbrack +\lbrack\lbrack 23\rbrack\rbrack - \lbrack\lbrack 12,3\rbrack\rbrack + \lbrack\lbrack 1,2,3\rbrack\rbrack -\lbrack\lbrack 2,3\rbrack\rbrack + \lbrack\lbrack 12\rbrack\rbrack - \lbrack\lbrack 1,2\rbrack\rbrack+1\right)\bullet \lbrack\lbrack 1,4,5\rbrack\rbrack.\end{aligned}$$ These separate into two groups, one of which is already in the canonical basis and one which requires further work. First, we have $$\begin{aligned}
\lbrack\lbrack 23\rbrack\rbrack\bullet\lbrack\lbrack 1,4,5\rbrack\rbrack - \lbrack\lbrack 2,3\rbrack\rbrack\bullet\lbrack\lbrack 1,4,5\rbrack\rbrack+\lbrack\lbrack 1,4,5\rbrack\rbrack.\end{aligned}$$ These are already in the canonical basis.

More work is required for the remainder, $$\begin{aligned}
\left(\lbrack\lbrack 123\rbrack\rbrack - \lbrack\lbrack 1,23\rbrack\rbrack - \lbrack\lbrack 12,3\rbrack\rbrack + \lbrack\lbrack 1,2,3\rbrack\rbrack  + \lbrack\lbrack 12\rbrack\rbrack - \lbrack\lbrack 1,2\rbrack\rbrack\right)\bullet \lbrack\lbrack 1,4,5\rbrack\rbrack.\end{aligned}$$ Let us consider some term-by-term computations. We have $$\begin{aligned}
\lbrack\lbrack 123\rbrack\rbrack\bullet \lbrack\lbrack 1,4,5\rbrack\rbrack & = & \lbrack\lbrack 123,4,5\rbrack\rbrack\\
\lbrack\lbrack 1,23\rbrack\rbrack\bullet\lbrack\lbrack 1,4,5\rbrack\rbrack & = & \lbrack\lbrack 1,23,4,5\rbrack\rbrack - \lbrack\lbrack 1,234,5\rbrack\rbrack +\lbrack\lbrack 1,4,23,5\rbrack\rbrack -\lbrack\lbrack 1,4,235\rbrack\rbrack +\lbrack\lbrack 1,4,5,23\rbrack\rbrack \\
\lbrack\lbrack 1,2\rbrack\rbrack \bullet \lbrack\lbrack 1,4,5\rbrack\rbrack & = & \lbrack\lbrack 1,2,4,5\rbrack\rbrack - \lbrack\lbrack 1,24,5\rbrack\rbrack + \lbrack\lbrack 1,4,2,5\rbrack\rbrack-\lbrack\lbrack 1,4,25\rbrack\rbrack +\lbrack\lbrack 1,4,5,2\rbrack\rbrack,\end{aligned}$$ where we remark that in the last line the singlet $\lbrack\lbrack 3\rbrack\rbrack$ has been removed from the composite ordered set partitions. It acts trivially via the convolution product, being the characteristic function of the point $(0,\ldots, 0)\in V_0^n$. In full detail, the last line would be $$-\lbrack\lbrack 1,2,4,5\rbrack\rbrack\bullet\lbrack\lbrack 3\rbrack\rbrack + \lbrack\lbrack 1,24,5\rbrack\rbrack\bullet\lbrack\lbrack 3\rbrack\rbrack - \lbrack\lbrack 1,4,2,5\rbrack\rbrack\bullet\lbrack\lbrack 3\rbrack\rbrack\\
+  \lbrack\lbrack 1,4,25\rbrack\rbrack\bullet\lbrack\lbrack 3\rbrack\rbrack-\lbrack\lbrack 1,4,5,2\rbrack\rbrack\bullet\lbrack\lbrack 3\rbrack\rbrack.$$ Note that in each term which appears in present expansion of $\lbrack\lbrack 3,2,1,4,5\rbrack\rbrack$ in the canonical basis we have $p_3\ge p_2\ge p_1<p_4<p_5$. Note that that some orientations may hold trivially, for example in $\lbrack\lbrack 1,4,5,2\rbrack\rbrack\bullet\lbrack\lbrack 3\rbrack\rbrack,$ the orientation $ p_3\ge p_2$ is trivially satisfied.

Unfortunately the formula given in Theorem \[thm:Straightening\] is somewhat inconvenient; however, in the quotient spaces $\mathcal{P}^n$, $\hat{\mathcal{P}}_1^n$ and $\mathcal{P}_1^n$ the expressions are much more manageable.

\[cor:straightening1\] Let $\lbrack\lbrack S_l,S_{l-1},\ldots, S_1,S_{l+1},\ldots, S_k\rbrack\rbrack\in\hat{\mathcal{P}}^n$, where $(S_l,S_{l-1},\ldots,S_1,S_{l+1},\ldots,  S_k)$ is an ordered set partition of $\{1,\ldots, n\}$. Then, passing to the quotient $\mathcal{P}^n$ we have $$\begin{aligned}
        \lbrack\lbrack S_l,S_{l-1},\ldots, S_1,S_{l+1},\ldots, S_k\rbrack\rbrack
        & = & \sum_{\pi}(-1)^{k-l-1-\operatorname{len}(\pi)}\lbrack \pi\rbrack,
    \end{aligned}$$ where the sum is over all plates $\pi$ labeled by ordered set partitions satisfying the orientations $$p_{(S_l)}\ge p_{(S_{l-1})}\ge \cdots\ge p_{(S_1)}<p_{(S_{l+1})}<\cdots<p_{(S_k)}.$$

In $\mathcal{P}^n$, in the formula in Theorem \[thm:Straightening\] only composite ordered set partitions $\{\mathbf{T}_1,\ldots, \mathbf{T}_m\}$ having $m=1$ contribute, matching the expression above except for the sign.

From Theorem \[thm:Straightening\] the sign is $(-1)^{c}(-1)^{(\text{len}(\mathbf{T}_1)+(k-l))-\text{len}(\pi)}$. We claim that for the quotient $\mathcal{P}^n$, the number $c+\text{len}(\mathbf{T}_1)$ is always odd. To see this, recall that in $\mathcal{P}^n$, we have $$\lbrack\lbrack S_2,S_1\rbrack\rbrack = \lbrack\lbrack S_1S_2\rbrack\rbrack - \lbrack\lbrack S_1,S_2\rbrack\rbrack,$$ hence $$\lbrack\lbrack S_l,S_{l-1}\rbrack\rbrack\bullet \cdots\bullet \lbrack\lbrack S_2,S_1\rbrack\rbrack =  (\lbrack\lbrack S_{1}S_2\rbrack\rbrack - \lbrack\lbrack S_1,S_2\rbrack\rbrack)\bullet\cdots\bullet (\lbrack\lbrack S_{l-1}S_{l}\rbrack\rbrack - \lbrack\lbrack S_{l-1},S_{l}\rbrack\rbrack).$$ Let $\mathbf{T}_1$ be any term in the expansion; now $c$ counts the number of times the two-block terms $\lbrack\lbrack S_i,S_{i+1}\rbrack\rbrack$ appear in a product. But it is easy to see that a convolution product of $c$ of the two-block factors and $c'$ of the one-block factors is a plate $\lbrack \mathbf{T}_1\rbrack$ with $\text{len}(\mathbf{T}_1)=c+1$ blocks, hence $c+\text{len}(\mathbf{T}_1) = c+(c+1) = 2c+1$, and so $$(-1)^{c}(-1)^{(\text{len}(\mathbf{T}_1)+(k-l))-\text{len}(\pi)}=(-1)^{k-l-1-\text{len}(\pi)}.$$

Consider the characteristic function $\lbrack\lbrack 2,1,3\rbrack\rbrack$. Here $l=2$ and $k=3$. $$\begin{aligned}
    \lbrack\lbrack 2,1,3\rbrack\rbrack & = & \left((-1)^{c_1}\lbrack\lbrack 12\rbrack\rbrack +(-1)^{c_2}\lbrack\lbrack 1,2\rbrack\rbrack \right)\bullet \lbrack\lbrack 1,3\rbrack\rbrack\\
    & = & (-1)^{c_1}\lbrack\lbrack 12\rbrack\rbrack \bullet  \lbrack\lbrack 1,3\rbrack\rbrack + (-1)^{c_2}\lbrack\lbrack 1,2\rbrack\rbrack \bullet  \lbrack\lbrack 1,3\rbrack\rbrack\\
    & = & (-1)^{c_1}(-1)^{d_1}\lbrack\lbrack 12,3\rbrack\rbrack + (-1)^{c_2}((-1)^{d_2}\lbrack\lbrack 1,2,3\rbrack\rbrack + (-1)^{d_3}\lbrack\lbrack 1,3,2\rbrack\rbrack + (-1)^{d_4}\lbrack\lbrack 1,23\rbrack\rbrack),
    \end{aligned}$$ where $c_1=0$ and $c_2=1$ count the respective occurrences of $p_1<p_2$. Further, each $d_i$ is of the form $$d_i\sim(\text{len}(\mathbf{T}_1)+(k-l))-\text{len}(\pi).$$ That is, $$(-1)^{d_1} = (-1)^{(1+(3-2))-2} = 1,$$ $$(-1)^{d_2} = (-1)^{(2 + (3-2))-3}=1,$$ $$(-1)^{d_3} = (-1)^{(2 + (3-2))-3}=1,$$ $$(-1)^{d_4} = (-1)^{(2 + (3-2))-2}=-1.$$ For example, for the $(-1)^{d_4}$ coefficient we have $\lbrack \mathbf{T}_1\rbrack = \lbrack 1,2\rbrack$ and $\pi = \lbrack 1,23\rbrack$.

Wrapping things up, in $\mathcal{P}^3$ we have $$\lbrack\lbrack 2,1,3\rbrack\rbrack = \lbrack\lbrack 12,3\rbrack\rbrack +\lbrack\lbrack 1,23\rbrack\rbrack - \lbrack\lbrack 1,2,3\rbrack\rbrack-\lbrack\lbrack 1,3,2\rbrack\rbrack.$$

Straightening relations for the remaining quotient spaces are given in Corollary \[cor:plate relations quotient\].

\[cor:plate relations quotient\] Let $(i_l,i_{l-1},\ldots, i_1,i_{l+1},\ldots, i_n)$ be an ordered set partition of $\{1,\ldots, n\}$ where all blocks are singlets.

Then in $\hat{\mathcal{P}}_1^n$ we have $$\lbrack\lbrack i_l,i_{l-1},\ldots,i_1,i_{l+1},\ldots, i_n\rbrack\rbrack=
    \sum_{m=1}^{n}\sum_{\{\mathbf{T}_1,\ldots,\mathbf{T}_m\}}(-1)^{l-m}\lbrack\lbrack \mathbf{T}_1\rbrack\rbrack\bullet\cdots\bullet \lbrack\lbrack\mathbf{T}_m\rbrack\rbrack,$$ where the sum is over all (standard) composite set partitions satisfying the orientations $$p_{i_l}> p_{i_{l-1}}> \cdots> p_{i_1}<p_{i_{l+1}}<\cdots<p_{i_n}.$$ Note that all blocks in the composite set partitions above are singlets.

In $\mathcal{P}_1^n$ we have $$\begin{aligned}
        \lbrack\lbrack i_l,i_{l-1},\ldots,i_1,i_{l+1},\ldots, i_n\rbrack\rbrack
        & = & (-1)^{l-1}\sum_{\pi}\lbrack\pi\rbrack,
    \end{aligned}$$ where the sum is over all (standard) ordered set partitions satisfying the orientations $$p_{i_l}> p_{i_{l-1}}> \cdots> p_{i_1}<p_{i_{l+1}}<\cdots<p_{i_n}.$$ Note that the blocks in the ordered set partitions are in this case singlets.

The proof is similar to that for Corollary \[cor:straightening1\] and is omitted.

Acknowledgements
================

We gratefully acknowledge the hospitality of the Munich Institute for Astro- and Particle Physics (MIAPP) during the program on Mathematics and Physics of Scattering Amplitudes in August, 2017, as well the Institute for Advanced Study, where parts of this paper were written.

We thank Adrian Ocneanu for the many intensive discussions during our graduate work. We thank Nima Arkani-Hamed, Freddy Cachazo, Lance Dixon, Song He, Florent Hivert, Chrysostomos Kalousios, Carlos Mafra, Jean-Christophe Novelli, Alex Postnikov and Oliver Schlotterer for very interesting related discussions at various stages of the development of the paper. We are grateful to Darij Grinberg and Victor Reiner for proof-reading and helpful conversations.

Functional representations {#section:ExamplesPhysics}
==========================

Laplace transforms
------------------

Below we observe that the formula of Theorem \[thm:treeExpansionCompletePlates\] carries over to rational function representations, in a similar way to the discussion in [@LinearExtensionsValuation], thus giving several extremely useful functional representations of the spaces $\hat{\mathcal{P}}^n, \mathcal{P}^n,\hat{\mathcal{P}}_1^n$, and $\mathcal{P}_1^n$.

Following the well-known construction, see for example [@ReinerValuationCone], any permutohedral cone $$C=\langle v_1,\ldots, v_k\rangle_+ \subset V_0^n$$ which, after scaling the $v_i$ by a common factor is contained in an integer lattice $L$, maps, via the *discrete Laplace transform*, to the rational function $$\mathcal{L}_d(C)=\sum_{v\in C\cap L} e^{-\langle y,v\rangle}.$$ We shall also need the *integral Laplace transform*, which we define by $$\mathcal{L}_\mathcal{I}(C)=\int_C e^{-\langle y,v\rangle }dv.$$

\[defn:functionalRepresentation\] Let $(S_1,\ldots, S_k)$ be an ordered set partition. Let $\mathcal{W}^n\subset V_0^n$ be the lattice of weights of type $A_{n-1}$. We define the functional representation of *type* $\mathcal{P}^n$ of a plate $\pi$ to be the composition of the duality operator $\star$ with the valuation (as in [@BarvinokPammersheim]) induced on characteristic functions by the well-known discrete Laplace transform: $$\lbrack \lbrack S_1,\ldots, S_k\rbrack\rbrack\mapsto \mathcal{L}_d\left(\lbrack \lbrack S_1,\ldots, S_k\rbrack\rbrack^\star\right)=\mathcal{L}_d\left(\lbrack\langle \bar{e}_{S_1},\bar{e}_{S_1\cup S_2},\ldots, \bar{e}_{S_1\cup\cdots\cup S_{k-1}}\rangle\rbrack \right)= \prod_{i=1}^{k-1}\frac{1}{1-e^{-\sum_{j=1}^i\bar{y}_{S_j}}},$$ for each plate $\lbrack S_1,\ldots, S_k\rbrack\subseteq V_0^n$, where $$\bar{y}_{S}=y_S-\left(\frac{\vert S\vert}{n}\sum_{i=1}^n y_i\right)=\frac{\vert S^c\vert}{n}y_S-\frac{\vert S\vert}{n}y_{S^c}.$$

For any plate $\pi=\lbrack i_1,\ldots, i_n\rbrack$ whose blocks are all singlets, we define the functional representation of *type* $\hat{\mathcal{P}}_1^n$ of a plate $\pi=\lbrack i_1,\ldots, i_n\rbrack$ as $$\lbrack\lbrack i_1,\ldots, i_n\rbrack\rbrack\mapsto \mathcal{L}_d\left(\lbrack\lbrack i_1,\ldots, i_n\rbrack\rbrack\right)=\prod_{i=1}^{n-1}\frac{1}{1-e^{-(y_i- y_{i+1})}}=(-1)^{n-1}\frac{x_2\cdots x_n}{(x_1-x_2)\cdots (x_{n-1}-x_n)},$$ where we define $x_i=e^{-y_i}$.

Finally, for any plate $\pi=\lbrack i_1,\ldots, i_n\rbrack$ whose blocks are again all singlets, we define the functional representation of *type* $\mathcal{P}_1^n$ of a plate $\pi=\lbrack i_1,\ldots, i_n\rbrack$ as $$\lbrack\lbrack i_1,\ldots, i_n\rbrack\rbrack\mapsto \mathcal{L}_\mathcal{I}\left(\lbrack\lbrack i_1,\ldots, i_n\rbrack\rbrack\right)=\prod_{i=1}^{n-1}\frac{1}{y_i-y_{i+1}}.$$

For the general theory of functional representations of polyhedra cones relevant to Proposition \[prop:functionalRepsWellDefined\], we refer to the reader to [@Barvinok; @BarvinokPammersheim; @ReinerValuationCone].

\[prop:functionalRepsWellDefined\] The functional representations from Definition \[defn:functionalRepresentation\], of types $\mathcal{P}^n$, $\hat{\mathcal{P}}_1^n$ and $\mathcal{P}^n$, are well-defined.

According to [@Barvinok; @BarvinokPammersheim], see also Proposition 2.2 and respectively Proposition 2.1 in [@ReinerValuationCone], under the linear map induced by the discrete Laplace transform from characteristic functions of polyhedral cones to rational functions, characteristic functions of non-pointed cones are mapped to zero, and in the same way the linear map induced by the integral Laplace transform sends characteristic functions of both non-pointed cones *and* higher codimension cones to the zero rational function.

Recall that the functional representation of type $\mathcal{P}^n$ is the composition of $\star$ with the discrete Laplace transform. That is, $\mathcal{L}_d(\lbrack C^\star\rbrack )=0$ if and only if $C^\star $ is not pointed. Now $C^\star$ is not pointed if and only if $C$ is of higher codimension, by Remark \[rem: properties dual cones\]. But $\mathcal{P}^n$ was defined to be the quotient of $\hat{\mathcal{P}}^n$ by the linear span of the characteristic functions higher codimensional cones, showing that the functional representation of type $\mathcal{P}^n$ is indeed a (well-defined) linear homomorphism.

Recall that $\hat{\mathcal{P}}_1^n$ was defined to be the quotient of $\hat{\mathcal{P}}^n$ by the linear span of the characteristic functions of all plates which have some block of size at least 2. Suppose $\pi=\lbrack S_1,\ldots, S_k\rbrack$ and we have $\vert S_i\vert\ge 2$ for some $i$. Then $\pi$ contains both directions $e_a-e_b$ and $e_b-e_a$ for $a,b\in S_i$ with $a\not=b$, meaning that $\mathcal{L}_d(\lbrack\pi\rbrack)=0$. This completes the proof that the functional representation of type $\hat{\mathcal{P}}_1^n$ is well-defined.

Finally, well-definedness for the functional representation of type $\mathcal{P}_1^n$ follows again by simply noting that $\mathcal{P}_1^n$ is the quotient of $\hat{\mathcal{P}}^n$ with spanning set those characteristic functions of plates which are labeled by ordered set partitions having a block of size at least 2, or which are of higher codimension.

Sometimes it is convenient for computational insight to change variables in our representation of type $\mathcal{P}^n$. Put $x_i=e^{-\bar{y}_i}$; note that $x_1\cdots x_n=e^0=1$. Then the functional representation of type $\mathcal{P}^n$ looks like $$\begin{aligned}
\label{eqn:functional rep}
            \lbrack \lbrack S_1,\ldots, S_k\rbrack\rbrack\mapsto \prod_{i=1}^{k-1}\frac{1}{1-\prod_{j\in S_1\cup\cdots\cup S_i}x_{j}},
        \end{aligned}$$ and in computations one is forced to consider the relation $x_1\cdots x_n=1$ on a case-by-case basis. Then the series expansion of converges on the plate $\lbrack S_1,\ldots, S_k\rbrack$, in the $\bar{y}_i$ variables.

Examples: Laplace transforms of permutohedral cones for tree graphs
-------------------------------------------------------------------

We now illustrate the signed sum expansions of the characteristic function of the permutohedral cone associated to a tree, for the functional representations of types $\mathcal{P}^n, \hat{\mathcal{P}}_1^n$ and $\mathcal{P}_1^n$.

A tree simplex may be cut out using inequalities by taking the orthogonal dual in $V_0^n$ to the root basis $\{e_{i_a}-e_{j_a}:a=1,\ldots, n-1\}$, as specified by the tree.

\[prop: LaplaceTransformTree\] Let $\mathcal{T}$ be a tree with oriented edge set $$\{(i_1,j_1),\ldots, (i_{n-1},j_{n-1})\}.$$ This means that $B_\mathcal{T}=\{ e_{i_1}-e_{j_1},\ldots, e_{i_{n-1}}-e_{j_{n-1}}\}$ is a basis for $V_0^n$ and the conical hull $$\langle e_{i_1}-e_{j_1},\ldots, e_{i_{n-1}}-e_{j_{n-1}}\rangle_+$$ is a simplicial cone in $V_0^n$. Let $\{\bar{e}_{I_1},\ldots, \bar{e}_{I_{n-1}}\}$ be the basis of $V_0^n$ which is orthogonal to $B_{\mathcal{T}}$, for subsets $I_k\subset\{1,\ldots, n\}$. Then, we have $$\langle e_{i_1}-e_{j_1},\ldots, e_{i_{n-1}}-e_{j_{n-1}}\rangle_+=\left\{x\in V_0^n:\bar{e}_{I_1}\cdot x\ge 0,\ldots, \bar{e}_{I_{n-1}}\cdot x\ge 0\right\}.$$

This essentially follows from Theorem \[thm:treeExpansionCompletePlates\]; we fill in the details.

Let $\{\bar{e}_{I_1},\ldots, \bar{e}_{I_{n-1}}\}$ be the basis of $V_0^n$ which is orthogonal to $ \{e_{i_1}-e_{j_1},\ldots, e_{i_{n-1}}-e_{j_{n-1}}\}$. Then, given $x=\sum_{k=1}^{n-1}t_k(e_{i_k}-e_{j_k})$ with $t_k\ge 0$, we have $\bar{e}_{I_k}\cdot x = t_k \ge 0$. Conversely, any $x\in V_0^n$ has a unique expansion $$x = \sum_{k=1}^{n-1} t_k(e_{i_k}-e_{j_k})$$ for some $t_1,\ldots, t_{n-1}\in V_0^n$. If $\bar{e}_{I_k}\cdot x\ge 0$ for each subset $I_k$, $k=1,\ldots, n-1$, define $t_k=\bar{e}_{I_k}\cdot x$, and we have $$x=\sum_{i=1}^{n-1}t_k \bar{e}_{I_k}.$$

We have the following explicit closed form for the functional representation of type $\mathcal{P}_1^n$. It may be interesting to compare Proposition \[prop:functional Tree Identities\] with [@ReinerValuationCone], for example Corollary 5.3.

\[prop:functional Tree Identities\] Let $\mathcal{T}$ be a tree with oriented edge set $$\{(i_1,j_1),\ldots, (i_{n-1},j_{n-1})\}.$$ We have the following identities.

1.  $$\sum_{\{\mathbf{T}: p_{i_k}<p_{j_k}\}} (-1)^{n-\text{len}(\mathbf{T})}\prod_{i=1}^{k-1}\frac{1}{1-e^{-\sum_{j=1}^i\bar{y}_{T_j}}} = \prod_{i=1}^{k-1}\frac{1}{1-e^{-\sum_{j=1}^i\bar{y}_{I_j}}}$$ where the sum is over all ordered set partitions of $\{1,\ldots, n\}$ which respect the orientations $p_{i_k}<p_{j_k}$, and the sets $I_1,\ldots, I_{n-1}$ are defined such that $\{\bar{e}_{I_1},\ldots, \bar{e}_{I_{n-1}}\}$ is orthogonal to the basis $ \{e_{i_1}-e_{j_1},\ldots,e_{i_{n-1}}-e_{j_{n-1}}\}$.

2.  $$\sum_{\{\sigma\in{\mathfrak{S}}_n:p_{i_k}<p_{j_k}\}}\frac{1}{(1-x_{\sigma_1}/x_{\sigma_2})\cdots (1-x_{\sigma_{n-1}}/x_{\sigma_n})} = \prod_{k=1}^{n-1} \frac{1}{1-x_{i_k}/x_{j_k}},$$ where the sum is over all permutations of $(1,\ldots, n)$ which respect the orientations $p_{i_k}<p_{j_k}$.

3.  $$\sum_{\{\sigma\in{\mathfrak{S}}_n:p_{i_k}<p_{j_k}\}}\frac{1}{(x_{\sigma_1}-x_{\sigma_2})\cdots (x_{\sigma_{n-1}}-x_{\sigma_n})} = \prod_{k=1}^{n-1} \frac{1}{x_{i_k}-x_{j_k}},$$ where again the sum is over all permutations of $(1,\ldots, n)$ which respect the orientations $p_{i_k}<p_{j_k}$.

Recall the change of variable $x_i = e^{-y_i}$.

From Theorem \[thm:treeExpansionCompletePlates\] in $\hat{\mathcal{P}}^n$ we have the identity $$\lbrack\langle e_{i_1}-e_{j_1},\ldots, e_{i_{n-1}}-e_{j_{n-1}}\rangle_+\rbrack= \sum_{\pi:p_{i_a} < p_{j_a}}(-1)^{n-\operatorname{len}(\pi)}\lbrack\pi\rbrack,$$ where the sum is over all ordered set partitions compatible with the orientations $$p_{i_1}<p_{j_1},\ \ldots,\ p_{i_{n-1}}<p_{j_{n-1}}.$$

Now we apply the formulas provided in the definitions of the functional representations, noting that from Proposition \[prop:functionalRepsWellDefined\], the functional representations of types $\mathcal{P}^n$, $\hat{\mathcal{P}}_1^n$ and $\mathcal{P}_1^n$ respect the identity from Theorem \[thm:treeExpansionCompletePlates\]. Therefore it suffices to compute the images under the functional representations of $$\lbrack\langle e_{i_1}-e_{j_1},\ldots, e_{i_{n-1}}-e_{j_{n-1}}\rangle_+\rbrack.$$

In the functional representation of type $\mathcal{P}^n$ we have

$$\begin{aligned}
    \lbrack \langle e_{i_1}-e_{j_1},\ldots,e_{i_{n-1}}-e_{j_{n-1}}\rangle \rbrack  & \mapsto & \mathcal{L}_d\left(\lbrack \langle e_{i_1}-e_{j_1},\ldots,e_{i_{n-1}}-e_{j_{n-1}}\rangle ^\star\right)\\
    & = & \mathcal{L}_d\left(\lbrack\langle \bar{e}_{I_1},\bar{e}_{I_2},\ldots, \bar{e}_{I_{n-1}}\rangle\rbrack \right)\\
    & = & \sum_{k_1,\ldots, k_{n-1}=0}^\infty e^{-(k_1\bar{y}_{I_1})}e^{-(k_2\bar{y}_{I_2})}\cdots e^{-(k_{n-1}\bar{y}_{I_{n-1}})}\\
    & = & \prod_{i=1}^{k-1}\frac{1}{1-e^{-\bar{y}_{I_j}}}\\\end{aligned}$$

where the indices $I_1,\ldots, I_{n-1}$ are defined such that $\{\bar{e}_{I_1},\ldots, \bar{e}_{i_{n-1}}\}$ is orthogonal to the basis $\{e_{i_1}-e_{j_1},\ldots,e_{i_{n-1}}-e_{j_{n-1}}\}.$

In the functional representation of type $\hat{\mathcal{P}}_1^n$ we have $$\begin{aligned}
    \lbrack \langle e_{i_1}-e_{j_1},\ldots,e_{i_{n-1}}-e_{j_{n-1}} \rbrack & \mapsto & \mathcal{L}_d\left(\lbrack \langle e_{i_1}-e_{j_1},\ldots,e_{i_{n-1}}-e_{j_{n-1}}\rangle\right) \\
    & = & \sum_{k_1,\ldots, k_{n-1}=0}^\infty (x_{i_1}/x_{j_i})^{k_1}\cdots(x_{i_{n-1}}/x_{j_{n-1}})^{k_{n-1}}\\
    & = & \prod_{k=1}^{n-1} \frac{1}{1-x_{i_k}/x_{j_k}}.\end{aligned}$$ In the functional representation of type $\mathcal{P}_1^n$ we have $$\lbrack \langle e_{i_1}-e_{j_1},\ldots,e_{i_{n-1}}-e_{j_{n-1}} \rbrack\mapsto \mathcal{L}_\mathcal{I}\left(\lbrack \langle e_{i_1}-e_{j_1},\ldots,e_{i_{n-1}}-e_{j_{n-1}}\rangle\right)
=\int_{t_1,\ldots, t_{n-1}=0}^\infty e^{-\sum t_k(y_{i_k}-y_{j_k})}dt$$ $$=\prod_{k=1}^{n-1} \frac{1}{y_{i_k}-y_{j_k}}.$$

It may be interesting to compare the simplicial cone in Example \[example: simplex in root solid triangulation\] with the simplices appearing in the triangulation of the type $A_3$ root polytope, in [@PostnikovPermutohedra]. The cone below is also represented functionally (using functions which are of type $\mathcal{P}_q^4$) in [@HeSon]. There the functions are called *Cayley functions*. The computation is included below.

\[example: simplex in root solid triangulation\] Let $\mathcal{T} = \{(1,3),(2,3),(1,4)\}$ be a tree. Then we have $$\lbrack\langle e_1-e_3,e_2-e_3,e_1-e_4\rangle\rbrack = \lbrack\lbrack 1,2,3,4\rbrack\rbrack + \lbrack\lbrack 1,2,4,3\rbrack\rbrack + \lbrack\lbrack 1,4,2,3\rbrack\rbrack + \lbrack\lbrack 2,1,3,4\rbrack\rbrack + \lbrack\lbrack 2,1,4,3\rbrack\rbrack$$ $$-\left(\lbrack\lbrack 12,3,4\rbrack\rbrack +\lbrack\lbrack 12,4,3\rbrack\rbrack +\lbrack\lbrack 1,24,3\rbrack\rbrack +\lbrack\lbrack 1,2,34\rbrack\rbrack  + \lbrack\lbrack 2,1,34\rbrack\rbrack \right)$$ $$+\lbrack\lbrack 12,34\rbrack\rbrack.$$ In the functional representation of type $\mathcal{P}^4$ we have

$$\begin{aligned}
&&  \frac{1}{\left(1-x_1\right) \left(1-x_1 x_2\right) \left(1-x_1 x_2 x_3\right)} + \frac{1}{\left(1-x_1\right) \left(1-x_1 x_2\right) \left(1-x_1 x_2 x_4\right)} + \frac{1}{\left(1-x_1\right) \left(1-x_1 x_4\right) \left(1-x_1 x_2 x_4\right)} \\
    &  + & \frac{1}{\left(1-x_2\right) \left(1-x_1 x_2\right) \left(1-x_1 x_2 x_3\right)} + \frac{1}{\left(1-x_2\right) \left(1-x_1 x_2\right) \left(1-x_1 x_2 x_4\right)}\\
    &  - & \frac{1}{\left(1-x_1 x_2\right) \left(1-x_1 x_2 x_3\right)}-\frac{1}{\left(1-x_1 x_2\right) \left(1-x_1 x_2 x_4\right)} - \frac{1}{\left(1-x_1\right) \left(1-x_1 x_2 x_4\right)} - \frac{1}{\left(1-x_1\right) \left(1-x_1 x_2\right)} \\
    & - & \frac{1}{\left(1-x_2\right) \left(1-x_1 x_2\right)}\\
    & + & \frac{1}{1-x_1 x_2}\\
    & = & \frac{1-x_1^2 x_2 x_3 x_4}{\left(1-x_1\right) \left(1-x_2\right) \left(1-x_1 x_2 x_3\right) \left(1-x_1 x_4\right)}\\
    & = & \frac{1}{ \left(1-x_2\right) \left(1-x_1 x_2 x_3\right) \left(1-x_1 x_4\right)},\end{aligned}$$

since $x_1x_2x_3x_4=1$.

Let us also illustrate the functional representation of type $\mathcal{P}_1^4$. In that case we have

$$\begin{aligned}
 & & \frac{1}{\left(x_1-x_2\right) \left(x_2-x_3\right) \left(x_3-x_4\right)} + \frac{1}{\left(x_1-x_2\right) \left(x_2-x_4\right) \left(x_4-x_3\right)} + \frac{1}{\left(x_1-x_4\right) \left(x_4-x_2\right) \left(x_2-x_3\right)}\\
& + &  \frac{1}{\left(x_2-x_1\right) \left(x_3-x_4\right) \left(x_4-x_2\right)} +\frac{1}{\left(x_2-x_1\right) \left(x_1-x_4\right) \left(x_4-x_3\right)}\\
& = & \frac{1}{\left(x_1-x_3\right) \left(x_2-x_3\right) \left(x_1-x_4\right)}.
    \end{aligned}$$

![The tree which encodes the orientations in Example \[example:7-particle computation\][]{data-label="fig:feynman-diagram-polytope-example-tree"}](Feynman_diagram_polytope_example_tree){width="0.5\linewidth"}

We present the results of a more involved example which can be worked with the aid of a computer.

\[example:7-particle computation\] The directed edges for the tree in Figure \[fig:feynman-diagram-polytope-example-tree\] are labeled by the ordered pairs $$(1,3),(2,3),(2,4),(2,5),(3,6),(7,3)$$ and encode the permutohedral cone $$\langle e_1-e_3,e_2-e_3,e_2-e_4,e_2-e_5,e_3-e_6,e_7-e_3\rangle_+.$$ We apply the combinatorial expansion from Theorem \[thm:treeExpansionCompletePlates\] to give functional representations of this cone of types $\mathcal{P}^n,\hat{\mathcal{P}}_1^n,\mathcal{P}_1^n$, ignoring respectively higher codimensional cones, non-pointed cones and both. In the functional representation of type $\mathcal{P}_1^n$ we have a sum of fractions over 124 ordered-pair compatible permutations, which eventually collapses to $$\frac{1}{\left(x_1-x_3\right) \left(x_2-x_3\right) \left(x_2-x_4\right) \left(x_2-x_5\right) \left(x_3-x_6\right) \left(x_7-x_3\right)}.$$ In the functional representation of type $\hat{\mathcal{P}}_1^n$ we find $$\frac{x_3^3 x_4 x_5 x_6}{\left(x_1-x_3\right) \left(x_2-x_3\right) \left(x_2-x_4\right) \left(x_2-x_5\right) \left(x_3-x_6\right) \left(x_7-x_3\right)}$$ $$=\frac{1}{(1-x_1/x_3)(1-x_2/x_3)(1-x_2/x_4)(1-x_2/x_5)(1-x_3/x_6)(1-x_7/x_3)}.$$ Recall that there is additional structure that is being missed in $\mathcal{P}_1^n$, and that it can be traced back to variations of a single linear relation. For $\mathcal{P}_1^n$ we have from the integral Laplace transform $$\lbrack\lbrack i,j\rbrack+\lbrack\lbrack j,i\rbrack\rbrack \mapsto \frac{1}{x_i-x_j}+\frac{1}{x_j-x_i}=0,$$ while for $\hat{\mathcal{P}}_1^n$ we have from the discrete Laplace transform $$\lbrack\lbrack i,j\rbrack\rbrack+\lbrack\lbrack j,i\rbrack\rbrack \mapsto \frac{1}{1-x_i/x_j}+\frac{1}{1-x_j/x_i}=1,$$ where $1$ corresponds to a point, the origin, under the discrete Laplace transform.

Note that in $\hat{\mathcal{P}}^n$ we have an additional lumped term $\lbrack ij\rbrack$, which is the whole line $$\lbrack ij\rbrack = \{x\in V_0^n:x_{i}+x_j=0\text{ and } x_a=0 \text{ for all } a\not\in\{i,j\}\},$$ hence $$\lbrack\lbrack i,j\rbrack\rbrack+\lbrack\lbrack j,i\rbrack\rbrack=\lbrack\lbrack i,j\rbrack\rbrack\cdot \lbrack\lbrack j,i\rbrack\rbrack+\lbrack\lbrack ij\rbrack\rbrack.$$ In $\mathcal{P}^n$ the characteristic function $\lbrack\lbrack i,j\rbrack\rbrack\cdot \lbrack\lbrack j,i\rbrack\rbrack$ of the point $(0,\ldots, 0)$ is mapped to zero, while for $\hat{\mathcal{P}}_1^n$ the lumped term $\lbrack\lbrack ij\rbrack\rbrack$ is mapped to zero. In $\mathcal{P}_1^n$ both are mapped to zero.

Starting in $\hat{\mathcal{P}}^n$, applying Theorem \[thm:treeExpansionCompletePlates\] we have an alternating sum of 653 fractions labeled by ordered set partitions. After implementing on the computer, repeatedly imposing the condition $x_1\cdots x_7=1$ it collapses to $$\frac{x_1 x_2 x_3 x_4^2 x_5^2 x_6^2}{\left(1-x_1\right) \left(1-x_4\right) \left(1-x_5\right) \left(1-x_2 x_4 x_5\right) \left(1-x_6\right) \left(1-x_1 x_2 x_3 x_4 x_5 x_6\right)}$$ $$=\frac{1}{\left(1-x_1\right) \left(1-x_7\right)\left(1-x_2 x_4 x_5\right) \left(1-x_1 x_2 x_3 x_4 x_5 x_7\right) \left(1-x_1 x_2 x_3 x_5 x_6 x_7\right) \left(1-x_1 x_2 x_3 x_4x_6x_7\right) }.$$

After the change of variable $x_i=e^{-y_i}$, the domain of convergence coincides with the original permutohedral cone $$\langle e_1-e_3,e_2-e_3,e_2-e_4,e_2-e_5,e_3-e_6,e_7-e_3\rangle_+$$ and is cut out by the system of inequalities $$\begin{aligned}
        \left\{y\in\mathbb{R}^7:\begin{array}{cccc}
            y_1 \ge 0   & y_7 \ge 0 & y_{245}\ge 0 &  \\ 
            y_{123457} \ge 0 & y_{123567} \ge 0 & y_{123467} \ge 0 &  \\ 
            & y_{1234567} =0& 
        \end{array} \right\},
    \end{aligned}$$ which are equivalently determined by requiring nonnegativity of the dot product $y\cdot \bar{e}_I$ (where $y\in V_0^n$) for each $\bar{e}_I$ in the basis $$\left\{\bar{e}_{1},\bar{e}_{7},\bar{e}_{245},\bar{e}_{123457},\bar{e}_{123567},\bar{e}_{123467}\right\}$$ of $V_0^n$ which is orthogonal to the root basis determined by the ordered pair data as encoded in Figure \[fig:feynman-diagram-polytope-example-tree\], $$e_1-e_3,e_7-e_3,e_2-e_3,e_3-e_6,e_2-e_4,e_2-e_5,$$ where as usual $\bar{e}_I = \frac{\vert I^c\vert }{n}e_I - \frac{\vert I\vert}{n} e_{I^c}$ for $I$ a proper subset of $\{1,\ldots, n\}$.

N. Arkani-Hamed, J.Bourjaily, F. Cachazo, A. Postnikov, and J. Trnka. “On-shell structures of MHV amplitudes beyond the planar limit.” Journal of High Energy Physics 6, no. 2015 (2015): 1-16. N. Arkani-Hamed, Y. Bai, S. He, and G. Yan. “Scattering Forms and the Positive Geometry of Kinematics, Color and the Worldsheet.” arXiv preprint arXiv:1711.09102 (2017). A. Barvinok. “Computing the volume, counting integral points, and exponential sums.” Discrete & Computational Geometry 10, no. 2 (1993): 123-141. A. Barvinok and J. Pommersheim. “An algorithmic theory of lattice points.” New perspectives in algebraic combinatorics 38 (1999): 91. A. Boussicault, V. Féray, A. Lascoux, and V. Reiner. “Linear extension sums as valuations on cones.” J. Algebraic Combin 35, no. 4 (2012): 573-610. S. Boyd and L. Vandenberghe. “Convex optimization.” Cambridge university press, 2004. J. Broedel, N. Matthes, and O. Schlotterer. “Relations between elliptic multiple zeta values and a special derivation algebra.” Journal of Physics A: Mathematical and Theoretical 49, no. 15 (2016): 155203. F. Cachazo, Combinatorial Factorization, 1710.04558. N. Early. “Combinatorics and Representation Theory for Generalized Permutohedra I: Simplicial Plates.” arXiv preprint arXiv:1611.06640 (2016). N. Early. “Generalized Permutohedra, Scattering Amplitudes, and a Cubic Three-Fold.” arXiv preprint arXiv:1709.03686 (2017). Adv. in Math. 63 (1987), no. 3, 301-316. Y. Geyer, L. Mason, R. Monteiro, and P. Tourkine. “One-loop amplitudes on the Riemann sphere.” Journal of High Energy Physics 2016, no. 3 (2016): 114. C. Mafra and O. Schlotterer. “Cohomology foundations of one-loop amplitudes in pure spinor superspace.” arXiv preprint arXiv:1408.3605 (2014). S. He, O. Schlotterer, and Y. Zhang. “New BCJ representations for one-loop amplitudes in gauge theories and gravity.” arXiv preprint arXiv:1706.00640 (2017). H. Gao, S. He, and Y. Zhang. “Labelled tree graphs, Feynman diagrams and disk integrals.” Journal of High Energy Physics 2017, no. 11 (2017): 144. F. Menous, J.-C. Novelli, and J.-Y. Thibon. “Mould calculus, polyhedral cones, and characters of combinatorial Hopf algebras.” Advances in Applied Mathematics 51, no. 2 (2013):177-227. OEIS Foundation Inc. (2011), The On-Line Encyclopedia of Integer Sequences, http://oeis.org. A. Ocneanu. Private communication. P. Orlik and H. Terao, Commutative algebras for arrangements. Nagoya Math. J. 134 (1994), 65–73. A. Postnikov. “Permutohedra, associahedra, and beyond.” International Mathematics Research Notices 2009.6 (2009): 1026-1106. A. Postnikov, V. Reiner, and L. Williams. “Faces of generalized permutohedra.” Doc. Math 13, no. 207-273 (2008): 51. C. Reutenauer. “Free Lie Algebras.” Handbook of algebra 3 (2003): 887-903. A. Boussicault, V. Féray, A. Lascoux, and V. Reiner. “Linear extension sums as valuations on cones.” J. Algebraic Combin 35, no. 4 (2012): 573-610. R.P. Stanley, Enumerative Combinatorics, Vol. 1, Cambridge University Press, Cambridge, 1997, With a foreword by Gian-Carlo Rota, Corrected reprint of the 1986 original.

[^1]: The author was partially supported by RTG grant NSF/DMS-1148634,\
    University of Minnesota, email: <<PRESIDIO_ANONYMIZED_EMAIL_ADDRESS>>