\documentclass[ALCO,ThmDefs,Unicode,epreuves]{cedram} \OneNumberAllTheorems \usepackage{tikz} %\usepackage{pdflscape} \newcommand\Q{{\mathbb Q}} \newcommand\R{{\mathbb R}} \newcommand\fS{{\mathfrak S}} \newcommand{\bm}[1]{{\boldsymbol{#1}}} \renewcommand\c{\bm{c}} \newcommand\e{\bm{e}} \newcommand\m{\bm{m}} \renewcommand\v{\bm{v}} \renewcommand\u{\bm{u}} \renewcommand\a{\bm{a}} \renewcommand\b{\bm{b}} \renewcommand\r{\bm{r}} \renewcommand\t{\bm{t}} \renewcommand\L{\mathcal L} \renewcommand\O{\mathcal O} \renewcommand\l{\ell} \newcommand{\important}[1]{\emph{\textcolor{red}{#1}}} \DeclareMathOperator{\wt}{wt} \DeclareMathOperator{\intwt}{intwt} \DeclareMathOperator{\bdwt}{bdwt} \DeclareMathOperator{\Lat}{Lat} \DeclareMathOperator{\prune}{Prune} \DeclareMathOperator{\nvol}{nvol} \DeclareMathOperator{\Sp}{Sp} \DeclareMathOperator{\Bi}{Binom} \DeclareMathOperator{\sgn}{sgn} \DeclareMathOperator{\Tdcoeff}{Tdcoeff} \DeclareMathOperator{\ncone}{ncone} \DeclareMathOperator{\conv}{ConvexHull} \DeclareMathOperator{\cone}{Cone} \DeclareMathOperator{\Perm}{Perm} \DeclareMathOperator{\td}{Td} %%%%%%%%%%%%%%%%%%%%%%%%% %% Blackboard bold %%%%%%%%%%%%%%%%%%%%%%%%% \renewcommand{\k}{\mathbf{k}} \newcommand{\B}{{\mathcal B}} \newcommand{\D}{{\Gamma}} \newcommand{\spd}{\mathcal F} \newcommand{\lspd}{\mathcal O} \newcommand{\hB}{\overline{\mathcal B}} \newcommand{\CC}{\mathcal{C}} \newcommand{\bv}{\alpha^{\textsc{bv}}} \newcommand{\NN}{{\mathbb{N}}} \newcommand{\ZZ}{\mathbb{Z}} %%%%%%%%% a placer avant \begin{document} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newcommand*{\mk}{\mkern -1mu} \newcommand*{\Mk}{\mkern -2mu} \newcommand*{\mK}{\mkern 1mu} \newcommand*{\MK}{\mkern 2mu} \hypersetup{urlcolor=purple, linkcolor=blue, citecolor=red} \newcommand*{\romanenumi}{\renewcommand*{\theenumi}{\roman{enumi}}} \newcommand*{\Romanenumi}{\renewcommand*{\theenumi}{\Roman{enumi}}} \newcommand*{\alphenumi}{\renewcommand*{\theenumi}{\alph{enumi}}} \newcommand*{\Alphenumi}{\renewcommand*{\theenumi}{\Alph{enumi}}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%% Auteur %%%1 \author{\firstname{Federico} \lastname{Castillo}} \address{Max Planck Institutefor Mathematics in the Sciences\\ Inselstr. 22\\ 04103 Leipzig\\ Germany} %% e-mail address \email{castillo@mis.mpg.de} %%%2 \author{\firstname{Fu} \lastname{Liu}} \address{Department of Mathematics\\ University of California, Davis\\ One Shields Avenue, Davis, CA 95616 USA.} \email{fuliu@math.ucdavis.edu} \thanks{The second author was partially supported by a grant from the Simons Foundation \#426756.} %%%%% Sujet \keywords{Ehrhart polynomials, generalized permutohedra, Berline--Vergne construction} \subjclass{52B20, 14M25} %%%%% Gestion \DOI{10.5802/alco.157} \datereceived{2020-04-20} \daterevised{2020-10-07} \dateaccepted{2020-10-07} %%%%% Titre et résumé \title [On the Todd class of the permutohedral variety] {On the Todd class of the permutohedral variety} \begin{abstract} In the special case of braid fans, we give a combinatorial formula for the Berline--Vergne's construction for an Euler--Maclaurin type formula that computes the number of lattice points in polytopes. Our formula is obtained by computing a symmetric expression for the Todd class of the permutohedral variety. By showing that this formula does not always have positive values, we prove that the Todd class of the permutohedral variety $X_d$ is not effective for $d\geq 24$. Additionally, we prove that the linear coefficient in the Ehrhart polynomial of any lattice generalized permutohedron is positive. \end{abstract} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% Authors according to amsart's syntax + distinction between Given %% and Proper names: % Key words and phrases: \begin{document} %% Abstracts must be placed before \maketitle \maketitle \section{Introduction} \label{sec:in} Let $\Lambda$ be a lattice of finite rank and $V=\Lambda\otimes\R$ be the corresponding real finite-dimensional vector space. A \important{lattice polytope} in $V$ is a polytope such that all of its vertices lie in $\Lambda$. A classical problem in the crossroads between enumerative combinatorics and discrete geometry is that of counting lattice points in lattice polytopes. For any polytope $P\subset V$ we define $\Lat(P)\coloneqq |P\cap\Lambda|$. One of the earliest results in the area is Pick's theorem, which says that for any lattice polygon $P\subset\R^2$ we have \[ \Lat(P) = a(P)+\dfrac{1}{2}b(P)+1, \] where $a(P)$ is the area of $P$ and $b(P)$ is the number of lattice points on the boundary of $P$. One way to obtain a higher dimensional analog of Pick's formula is to find a formula relating the number of lattice points of $P$ with the different normalized volumes of the faces $F$ of $P$. We want a real-valued function $\alpha$ on pairs $(F,P)$, where $F$ is a face of a lattice polytope $P$, such that \begin{equation}\label{eq:exterior} \Lat(P) = \sum_{F: \text{ a face of $P$}} \alpha(F,P) \nvol(F), \end{equation} where $\nvol(F)$ is the normalized volume of $F$. It is clear that for a given lattice polytope $P$ one can always find many functions $\alpha$ satisfying~\eqref{eq:exterior}. What we want is a function that works simultaneously for \emph{all} lattice polytopes. We can do this by requiring the function $\alpha$ to be \emph{local}, \ie the value of $\alpha(F,P)$ only depends on the local geometry of $P$ around $F$, or more specifically, the value only depends on $\ncone(F,P)$, the normal cone of $P$ at $F.$ Any \emph{local} function $\alpha$ that satisfies Equation~\eqref{eq:exterior} for all lattice polytopes $P$ is called a \important{McMullen function}, since McMullen was the first to prove their existence~\cite{mcmullenext}. His proof is nonconstructive and shows that there are infinitely many McMullen functions. In the present paper we compute the values for a particular McMullen function on a special family of polytopes: generalized permutohedra, originally defined by Postnikov as deformations of usual permutohedra. An alternative and equivalent definition can be given in terms of normal fans: The \important{braid fan} $\Sigma_d$ is the complete fan in the quotient space $W_d \coloneqq \R^{d+1}/(1,1,\dots,1)$ obtained from the hyperplane arrangement $H_{i,j}\coloneqq \{x\in\R^{d+1}: x_i-x_j=0\}$ for $1\leq i\omega(\{S,T'\})$ whenever $S\subset T\subset T'$ or $T'\subset T\subset S$. We use notation $(\Sp, \omega)$ to indicate a spider $\Sp$ with a natural edge labeling $\omega$. \begin{exam} We draw a natural edge labeling on the spider of Figure~\ref{ex:1st}. \begin{figure}[ht] \input{Figures/firstexomega.tex} \caption{A drawn spider with a natural edge labeling.} \end{figure} \end{exam} \begin{nota}\label{notn:label} A left leg will be labeled as $T_i^L$ if it is the $i$-th \emph{smallest} vertex among all left legs, and a right leg will be labeled by $T_j^R$ if it is the $j$-th \emph{largest} vertex among all right legs. If there are no left legs, we give the head vertex $S$ an additional label $T^L_1$ similarly, if there are no right legs, we give the head vertex $S$ an additional label $T^R_1$. \end{nota} \begin{exam} Consider the spider with chain $T_\bullet = \{12\}\subset \{123\}\subset \{123456\}\subset \{12345678\}$ and head $S=\{12\}$. In Figure~\ref{fig:singlespider} we have labeled the spider according to Notation~\ref{notn:label}. Note that the head $S$ also receives the label $T^L_1$. \begin{figure}[ht] \input{Figures/singlespider.tex} \caption{A spider with the head having two different labels.} \label{fig:singlespider} \end{figure} \end{exam} \begin{defi}\label{def:sd} Let $T_\bullet\in\CC_{d+1}$ be a chain. A \important{spider diagram} $\D$ on $T_\bullet$ consists of a partition of $T_\bullet$ into $k$-disjoint intervals $T_{1,\bullet},\cdots,T_{k,\bullet}$ together with a spider $\Sp_i\coloneqq \Sp(T_{i,\bullet},S_i)$ on each interval. The set of heads $S_i$ is called the \important{head set} of $\D$. Note that the head set is always a chain $S_\bullet\in\CC_{d+1}$. For each $i$, let $m_i=|\Sp_i|$, and $L_i$ and $R_i$ be the set of left and right legs respectively. The vector $\m\coloneqq (m_1,\cdots,m_k)$ is the \important{length vector} of $\D$. The \important{size} of $\D$ is $|\D|\coloneqq \sum m_i$, the size of its vertex set. An \important{ordered spider diagram} $\D$ is a spider diagram in which additionally we have a natural edge labeling $\omega_i$ on each spider $\Sp_i$. A pair $(S_\bullet,\m)$ is \important{admissible} if $S_\bullet\in\CC^k_{d+1}$, $\m\in\ZZ^k$. Such a pair is \important{d-admissible} if furthermore $\sum_{i=1}^k{m_i}\leq d$. Let $\spd(S_\bullet,\m)$ (respectively $\lspd(S_\bullet,\m)$) be the set of spider diagrams (respectively ordered spider diagrams) with head set $S_\bullet$ and length vector $\m$. \end{defi} \begin{rema} Notice that if $(S_\bullet,\m)$ is not d-admissible, that is, $\sum_{i=1}^k{m_i}> d$, then $\spd(S_\bullet,\m)$ and $\lspd(S_\bullet,\m)$ are empty. \end{rema} \begin{nota}\label{notn:triple} In a spider diagram $\D$ the legs are now triply indexed: the element $T^P_{i,j}$ with $P\in\{L,R\}$ is the $j$-th smallest/largest on the side $L/R$ of the $i$-th spider $\Sp_i$. We also let $l_i$ be the number of left legs of $\Sp_i$ and $r_i$ be the number of right legs of $\Sp_i.$ Hence, $T^L_{i, l_i}$ is the largest vertex among all left legs and $T^R_{i, r_i}$ is the largest vertex among all right legs. \end{nota} \begin{exam} In Figure~\ref{fig:spiderex} we show an ordered spider diagram of two spiders where vertices are labeled according to Notation~\ref{notn:triple}. This diagram has size 10 and length vector $(6,4)$. We have also included a natural edge labeling $\omega.$ \begin{figure}[ht]\label{ex:spiderdiagram} \input{Figures/spiderdiagram.tex} \caption{A spider diagram of two spiders together with a natural edge labeling.} \label{fig:spiderex} \end{figure} \end{exam} For our formulas in the next section we need to define the weight of a spider diagram. %%%%%%%%%%%%%% %% WEIGHT DEFINITION %%%%%%%%%%%%%% \begin{defi}\label{def:weight} Let $T_\bullet\in\CC_{d+1}$ be a chain and $\D$ a spider diagram on $T_\bullet$ with $k$ spiders. We define the \important{internal weight} of a single spider $\Sp_i$ as \begin{equation}%\label{eq:weight} \intwt(\Sp_i)\coloneqq \left(\prod_{j>1}\dfrac{|T^L_{i,j}-T^L_{i,j-1}|}{|S_i-T^L_{i,j-1}|}\right)\left(\prod_{j>1}\dfrac{|T^R_{i,j-1}-T^R_{i,j}|}{|T^R_{i,j-1}-S_i|}\right), \end{equation} (note that the internal weights of a spider is 1) and the \important{boundary weight} of the diagram $\D$ as \begin{equation}%\label{eq:weight} \bdwt(\D)\coloneqq \dfrac{|T^L_{1,1}-\emptyset|}{|S_1-\emptyset|}\left(\prod_{i=2}^{k}\dfrac{|T^L_{i,1}-T^R_{i-1,1}|}{|S_i-S_{i-1}|}\right)\dfrac{|[d+1]-T^R_{k,1}|}{|[d+1]-S_{k}|}. \end{equation} The \important{weight} of a spider diagram $\D$ is defined as \[ \wt(\D)\coloneqq \bdwt(\D)\prod_{i=1}^{k} \intwt(\Sp_i). \] \end{defi} \begin{exam} The weight of the spider diagram $\D$ depicted in Figure~\ref{fig:spiderex} is \begin{multline*} \underbrace{\left(\dfrac{|T_{1,1}^L-\emptyset|}{|S_1-\emptyset|}\cdot\dfrac{|T_{2,1}^L-T_{1,1}^R|}{|S_2-S_{1}|}\cdot\dfrac{|[d+1]-T_{2,1}^R|}{|[d+1]-S_2|}\right)}_{\bdwt(\D)}\\ \underbrace{\left(\dfrac{|T_{1,2}^L-T_{1,1}^L|}{|S_1-T_{1,1}^L|}\right)\left(\dfrac{|T_{1,1}^R-T_{1,2}^R|}{|T_{1,1}^R-S_1|}\cdot\dfrac{|T_{1,2}^R-T_{1,3}^R|}{|T_{1,2}^R-S_1|}\right)}_{\intwt(\Sp_1)}\\ \times \underbrace{\left(\dfrac{|T_{2,2}^L-T_{2,1}^L|}{|S_2-T_{2,1}^L|}\right)\cdot 1}_{\intwt(\Sp_2)}. \end{multline*} \end{exam} \section{Computations in the Chow ring \texorpdfstring{$A_d$}{Ad}}\label{sec:gen} The main goal of this section is to express any element in $A_d$ as a sum of square-free monomials. We start by treating squares. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% FIRST LEMMA %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{lemm}\label{lem:nonsym} Let $S\in\hB_{d+1}$. Choose $a\in S$, $b\notin S$ then we have the following equality in the ring $A_d$: \begin{equation}\label{eq:nonsym} x_S^2 = -\sum_{\substack{T\subset S \\ a\in T}}x_Tx_S -\sum_{\substack{S\subset T \\ b\notin T}} x_Sx_T. \end{equation} \end{lemm} \begin{proof} Using the relation $\l_a-\l_b\in I_2$, we get $x_S(\l_a-\l_b)=0$ in $A_d$. Hence, %Expanding we get \begin{equation} x_S\left(\sum_{a\in T}x_T-\sum_{b\in T}x_T\right) = 0. \end{equation} The relations in $I_1$ imply that $x_S x_T=0$ for any $T$ that is neither $T\subseteq S$ nor $S\subseteq T$. Thus we expand the above equation to get \begin{equation} x_S^2+\sum_{ \substack{T\subset S\\ a\in T}} x_Tx_S + \sum_{\substack{S\subset T\\ a\in T}} x_Sx_T - \sum_{ \substack{T\subset S\\ b\in T}} x_Tx_S - \sum_{\substack{S\subset T\\ b\in T}} x_Sx_T = 0. \end{equation} The fourth term is zero since the condition is vacuous. In the third term notice that the condition $a\in T$ is redundant. After canceling terms from the second and fourth sums, everything reduces to \[ x_S^2+\sum_{\substack{T\subset S \\ a\in T}}x_Tx_S + \sum_{\substack{S\subset T \\ b\notin T}}x_Sx_T = 0. \] By solving for $x_S^2$ we get Equation~\eqref{eq:nonsym}. \end{proof} %~\end{document} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% SECOND LEMMA %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% The square-free expression obtained in Lemma~\ref{lem:nonsym} is not symmetric. To adjust this, we average over all possibilities. \begin{lemm}\label{lem:squares} Let $S_1,\cdots,S_k$ be a k-chain in $\hB_{d+1}$ and $S_l$ a set in the chain. We have the following equality in $A_d$: \begin{align} x_{S_1}\cdots x_{S_{l-1}}x_{S_l}^2x_{S_{l+1}}\cdots x_{S_k} =& -\sum_{S_{l-1}\subset T\subset S_l} \dfrac{|T-S_{l-1}|}{|S_l-S_{l-1}|} x_{S_1}\cdots x_{S_{l-1}}x_Tx_{S_l}x_{S_{l+1}}\cdots x_{S_k} \label{eq:squares}\\ & -\sum_{S_{l}\subset T\subset S_{l+1}} \dfrac{|S_{l+1}-T|}{|S_{l+1}-S_{l}|} x_{S_1}\cdots x_{S_{l}}x_Tx_{S_{l+1}}x_{S_{l+2}}\cdots x_{S_k}.\nonumber \end{align} By convention, we let $S_0=\emptyset$ and $S_{k+1}=[d+1]$. \end{lemm} \begin{proof} We expand $x_{S_l}^2$ as in Lemma~\ref{lem:nonsym} using all possible pairs $(a,b)\in (S_{l}-S_{l-1})\times (S_{l+1}-S_{l})$ and take the average. We obtain \begin{multline*} x_{S_1}\cdots x_{S_{l-1}}x_{S_l}^2x_{S_{l+1}}\cdots x_{S_k} \\ \begin{aligned} =& -\frac{1}{|S_l-S_{l-1}|\Mk\cdot\Mk |S_{l+1}-S_l|} \left( \sum_{\substack{a \in S_l- S_{l-1} \\ b \in S_{l+1}-S_l}} \sum_{\substack{S_{l-1}\subset T\subset S_{l} \\ a\in T}} x_{S_1}\cdots x_{S_{l-1}}x_Tx_{S_l}x_{S_{l+1}}\cdots x_{S_k}\right) \\ & - \frac{1}{|S_l-S_{l-1}|\Mk\cdot\Mk |S_{l+1}-S_l|} \left(\sum_{\substack{a \in S_l- S_{l-1} \\ b \in S_{l+1}-S_l}} \sum_{\substack{S_l\subset T\subset S_{l+1} \\ b\notin T}} x_{S_1}\cdots x_{S_{l}}x_Tx_{S_{l+1}}x_{S_{l+2}}\cdots x_{S_k} \right)\Mk\Mk. \end{aligned} \end{multline*} For the first term in the above expression, one sees that a set $T$ contributes to the summation if and only if $S_{l-1}\subset T\subset S_l$, and for any $T$ %%%ICI 2 such that $ S_{l-1}\subset T\subset S_l,$ it appears if and only if $a \in T-S_{l-1}$ which can be paired with any $b \in S_{l+1}-S_l,$ and thus it appears exactly $|T-S_{l-1}|\cdot |S_{l+1}-S_l|$ times. Hence, the first term above agrees with the first term on the right hand side of~\eqref{eq:squares}. Similarly, we can show that the second term above coincides with the second term on the right hand side of~\eqref{eq:squares}. \end{proof} \begin{rema}\label{rem:zerocase} The two sums on the right hand side of Equation~\eqref{eq:squares} can be over empty index sets simultaneously, in which case the monomial on the left hand side of~\eqref{eq:squares} is equal to zero. In particular, notice that this happens when $(S_{l}-S_{l-1})\times (S_{l+1}-S_{l})$ is a singleton. \end{rema} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% THIRD LEMMA: EXPANSION %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Repeated use of this lemma allows us to expand any monomial in $A_d$ as a sum of squarefree monomials. First we need more notation. %%%ICI3 \begin{defi} For a spider diagram $\D$ we define $\sgn(\D)\coloneqq (-1)^{|\D|-k}$. The number $|\D|-k$ is equal to the total number of legs. Also we let $x_\D\coloneqq x_{T_\bullet}$, where $T_\bullet$ is the vertex set of $\D$. \end{defi} \begin{prop}\label{prop:expanding} Let $S_\bullet\in\CC_{d+1}^k$ be a $k$-chain and $\m = (m_1,\cdots,m_k)$ a vector of positive integers. Recall from Definition~\ref{def:sd} that $\lspd(S_\bullet,\m)$ is the set of ordered spider diagrams where each spider $\Sp_i$ has head $S_i$, size $m_i$, and an edge labeling $\omega_i$. Then we have the following equality in the ring $A_d$: \begin{equation}\label{eq:expansion} x_{S_\bullet}^\m\coloneqq \prod_{i=1}^k x_{S_i}^{m_i} = \sum_{\D\in\lspd(S_\bullet,\m)}\sgn(\D)\wt(\D)x_\D. \end{equation} \end{prop} \begin{proof} We prove by induction on $|\m|=\sum m_i$. The base case is $|\m| = k$ which happens exactly when $m_i=1$ for all $i$. In this case we have the square-free monomial $\prod_{i=1}^k x_{S_i}$ and $\lspd(S_\bullet,\m)$ consists of a single diagram $\D_0$ with $k$ trivial spiders. One sees that $\sgn(\D_0)=1$ and $\wt(\D_0)=1$ so Equation~\eqref{eq:expansion} is trivially true. We proceed to the induction step. Suppose that $N > k$ is a positive integer, and for any $\m=(m_1, \dots, m_k)$ with $|\m| = \sum m_i < N,$ we have the equality~\eqref{eq:expansion} holds in $A_d.$ Now we assume that $\m=(m_1, \dots, m_k)$ is a vector of positive integers satisfying $|\m| = \sum m_i =N.$ Let $j=\max\{i:m_i>1\}$ and $\m'\coloneqq (m_1,\cdots,m_j-1,\cdots)$. By the induction hypothesis, we have the following equality in $A_d:$ \begin{equation}\label{eq:induction} x_{S_j}^{-1}\prod_{i=1}^k x_{S_i}^{m_i}=\sum_{\D'\in\lspd(S_\bullet,\m')}\sgn(\D')\wt(\D')x_{\D'}. \end{equation} We see that in order to show that~\eqref{eq:expansion} holds for $\m$, it is enough to show \begin{equation}\label{eq:needtoshow} \sum_{\D'\in\lspd(S_\bullet,\m')}\sgn(\D')\wt(\D')x_{S_j}x_{\D'} = \sum_{\D\in\lspd(S_\bullet,\m)}\sgn(\D)\wt(\D)x_\D. \end{equation} For the rest of the proof, we will use notations developed in Section 3, in particular recall those given in Notation~\ref{notn:triple}. In order to prove~\eqref{eq:needtoshow}, we construct a \important{pruning} map $\prune$ from $\lspd(S_\bullet,\m)$ to $\lspd(S_\bullet, \m')$ in the following way: Let $\D \in \lspd(S_\bullet,\m)$, where $\Sp_j$ is the $j$-th spider in $\D$ together with a natural edge labeling $\omega_j$. Suppose $T$ is the leg in $\Sp_j$ such that $\omega_j\left(\{S_j,T\}\right)$ has the largest edge label in $\Sp_j$. (Note that $T$ is either the closest leg/vertex $T^L_{j,l_j}$ on the left of $S_j$ or the closest leg/vertex $T^R_{j,r_j}$ on the right of $S_j$.) Then we define $\prune(\D)$ to be the ordered spider diagram obtained from $\D$ by removing $T$. For example, if $\D$ is the ordered spider diagram in Figure~\ref{fig:spiderex}, then $\prune(\D)$ is the one depicted in Figure~\ref{fig:prune}. \begin{figure}[ht] \input{Figures/prune.tex} \caption{An example of the pruning function.} \label{fig:prune} \end{figure} As sets we have $\lspd(S_\bullet,\m)=\coprod_{\D'\in \lspd(S_\bullet,\m')} \prune^{-1}(\D')$, %so we can rewrite the right hand side of~\eqref{eq:needtoshow} to obtain so we can rewrite the right hand side of~\eqref{eq:needtoshow} as \[ \sum_{\D'\in\lspd(S_\bullet,\m')}\sum_{\D\in\prune^{-1}(\D')}\sgn(\D)\wt(\D)x_\D \quad \text{or} \quad \sum_{\D'\in\lspd(S_\bullet,\m')} \sum_{\substack{\D\in\lspd(S_\bullet,\m)\\ \prune(\D)=\D'}} \sgn(\D)\wt(\D)x_\D.\] Hence, we can reduce the problem of proving~\eqref{eq:needtoshow} to proving that for every $\D' \in \lspd(S_\bullet, \m'),$ \begin{equation}\label{eq:needtoshow2} \sgn(\D')\wt(\D')x_{S_j}x_{\D'} = \sum_{\substack{\D\in\lspd(S_\bullet,\m)\\ \prune(\D)=\D'}} \sgn(\D)\wt(\D)x_\D. \end{equation} We now apply Lemma~\ref{lem:squares} to rewrite $x_{S_j} x_{\D'}$. One notices that the two summations on the right side of~\eqref{eq:squares} correspond to reversing the ``pruning'' operation by adding a left or a right leg back. Hence, \begin{equation}\label{eq:application} x_{S_j}\cdot x_{\D'} = -\sum_{\substack{\D\in\lspd(S_\bullet,\m)\\ \prune(\D)=\D'}} c_j(\D) x_\D, \end{equation} where %for any $\D,$ if $T$ is the leg that is removed when pruning $\D$, we define \[ c_j(\D) \coloneqq \begin{cases} \dfrac{|T^L_{j,l_j}-T^L_{j,l_j-1}|}{|S_j-T^L_{j,l_j-1}|}, & \quad \text{if the left leg $T^L_{j,l_i}$ is removed when pruning $\D$;} \\ \dfrac{|T^R_{j,r_j-1}-T^R_{j,r_j}|}{|T^R_{j,r_j-1}-S_j|}, & \quad \text{if the right leg $T^R_{j,r_i}$ is removed when pruning $\D$.} \\ \end{cases} \] Also, if $l_j=1$ we let $T^L_{j, l_j-1} = T^R_{j-1, 1}$, and if $r_j=1$ we let $T^R_{j, r_j-1} \coloneqq T^L_{j+1,1}.$ (Note that if $j=1,$ we consider $T^R_{j-1,1} = S_0 = \emptyset$; likewise, if $j=k,$ we consider $T^L_{k+1,1} = S_{k+1} = [d+1].$) Plugging~\eqref{eq:application} into the left hand side of~\eqref{eq:needtoshow2}, we obtain \begin{equation}\label{eq:application2} \sgn(\D')\wt(\D')x_{S_j}x_{\D'} = \sum_{\substack{\D\in\lspd(S_\bullet,\m)\\ \prune(\D)=\D'}} - \sgn(\D')\wt(\D')c_j(\D) x_\D. \end{equation} Comparing it with the right hand side of~\eqref{eq:needtoshow2} and observing that $-\sgn(\D')=\sgn(\D)$ when $\D' =\prune(\D)$, one sees that the proof is completed if we can prove that for any $\D \in \lspd(S_\bullet,\m)$, if $\D'=\prune(\D)$, then \begin{equation}\label{eq:comparison2} %\D'=\prune(\D)\quad\Rightarrow\quad \wt(\D')c_j(\D)=\wt(\D). \end{equation} Suppose $T$ is the leg that is removed when we ``prune'' $\D$ to obtain $\D'.$ We will only consider the case when $T= T^L_{j,l_j}$ is a left leg of $\Sp_j.$ (The case when $T$ is a right left of $\Sp_j$ can be proved analogously.) It is straightforward to check from the definitions of weights that $c_j(\D')\wt(\D')=\wt(\D)$ when $l_j >1,$ \ie $T^L_{j,l_j}$ is not the only left leg of $\Sp_j$. Indeed, in this case the boundary weights of $\D$ and $\D'$ are the same and the internal weights of $\D$ and $\D'$ differ exactly by a factor $c_j(\D)$ so~\eqref{eq:comparison2} holds. Suppose $l_j=1.$ Thus $T^L_{j,1}$ is the only left leg of $\Sp_j$ (which is the $j$-th spider in $\D$), and the $j$-th spider in $\D'$ has no left legs. Then the internal weights of $\D$ and $\D'$ are the same, whereas the boundary weights are different. Comparing $\bdwt(\D')$ and $\bdwt(\D)$, we see all but one factors in their expression are the same. The different factors $\bdwt(\D')$ and $\bdwt(\D)$ are \[ \dfrac{|S_j-T^R_{j-1,1}|}{|S_j-S_{j-1}|} \text{ and } \frac{|T^L_{j,1}-T^R_{j-1,1}|}{|S_j-S_{j-1}|},\] respectively. Since \[ c_j(\Gamma) =\dfrac{|T^L_{j,l_j}-T^L_{j,l_j-1}|}{|S_j-T^L_{j,l_j-1}|} = \dfrac{|T^L_{j,1}-T^R_{j-1,1}|}{|S_j-T^R_{j-1,1}|}.\] we conclude that $\bdwt(\D') \c_j(\D) =\bdwt(\D)$. Therefore,~\eqref{eq:comparison2} follows, completing the proof. \end{proof} %%%%%%%%%%%% %% Corollary %%%%%%%%%%%% \begin{coro}\label{cor:highdegree} Monomials in $R_d$ of degree larger than $d$ vanish in $A_d$. \end{coro} \begin{proof} Because of the relations in the ideal $I_1$, we only need to consider monomials of the form $x_{S_\bullet}^\m$ where $(S_\bullet,\m)$ is an admissible pair. Applying Equation~\eqref{eq:expansion} we get an empty sum on the right if $\sum_i m_i>d$, hence a monomial $x_{S_\bullet}^\m$ is nonzero only if $(S_\bullet,\m)$ is d-admissible. \end{proof} %~\end{document} %%%%%%%%%%%%%%%%%%%%%%%%%%%% %% FOURTH LEMMA: SIMPLIFICATION %%%%%%%%%%%%%%%%%%%%%%%%%%%% The proof of Proposition~\ref{prop:expanding} prunes one leg from a spider diagram at the time until we obtain a spider diagram consisting only of trivial spiders. The natural edge labelings are used to keep track of the order in which we remove the legs. However, one notices that if $\D_1, \D_2 \in \lspd(S_\bullet,\m)$ are on the same spider diagram $\D$ with two different natural edge labelings, then \[ \sgn(\D_1)\wt(\D_1)x_{\D_1} = \sgn(\D)\wt(\D)x_\D = \sgn(\D_2)\wt(\D_2)x_{\D_2}.\] We have the following immediate consequence to Proposition~\ref{prop:expanding}: \begin{coro}\label{cor:expanding} Let $S_\bullet\in\CC_{d+1}^k$ be a $k$-chain and $\m= (m_1,\cdots,m_k)$ a vector of positive integers. Recall from Definition~\ref{def:sd} that $\spd(S_\bullet,\m)$ is the set of \emph{unordered} spider diagrams where each spider $\Sp_i$ has head $S_i$ and size $m_i$. Then we have the following equality in the ring $A_d$: \begin{equation}\label{eq:expansionsimpl} x_{S_\bullet}^\m = \sum_{\D\in\spd(S_\bullet,\m)}\Bi(\D)\sgn(\D)\wt(\D)x_\D, \end{equation} where \[\Bi(\D)\coloneqq \prod_{i=1}^k \binom{|\Sp_i|-1}{|L_i|,|R_i|}\] counts the number of natural edge labelings on $\D.$ \end{coro} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% FORMULAS FOR BV %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Formulas for the Berline--Vergne function}\label{sec:bv} With Corollary~\ref{cor:expanding} in hand, we can now write down square-free expressions of any element in $A_d$, in particular of the Todd class. First we need one more piece of notation. Any monomial $\u\in R_d$ that is non-zero in $A_d$ is of the form $x_{S_\bullet}^\m$ for some d-admissible pair $(S_\bullet,\m)$. \begin{defi} Expand the Todd class by plugging Equation~\eqref{eq:tdexpansion} into Equation~\eqref{eq:tddef} to obtain: \begin{equation}\label{eq:masterbegin} \td(X_d) = \sum_{(S_\bullet,\m)}\Tdcoeff(S_\bullet,\m)\cdot x_{S_\bullet}^\m,\quad \Tdcoeff(S_\bullet,\m)\in\mathbb{Q}, \end{equation} where the summation is over all d-admissible pairs $(S_\bullet,\m)$. For $\D\in\spd(S_\bullet,\m)$ define $\Tdcoeff(\D)\coloneqq \Tdcoeff(S_\bullet,\m)$. \end{defi} \begin{exam} Let $d\geq 7$, $S_\bullet=(S_1,S_2,S_3)$ be any chain of length three and $\m=(2,4,1)$. The monomial $x_{S_1}^2x_{S_2}^4x_{S_3}^1$ appears in Equation~\eqref{eq:tdexpansion} with coefficient \[ \left(\frac{1}{12}\right)\left(-\frac{1}{720}\right)\left(\frac{1}{2}\right) = -\frac{1}{17280}, \] hence $\Tdcoeff(S_\bullet,(2,4,1))=-1/17280$. \end{exam} \begin{rema}\label{rem:Tsymm} Notice that by definition $\Tdcoeff$ only depends on the length and entries of $\m$. \end{rema} %~\end{document} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% THEOREM: MAIN FORMULA %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Now we can present our main result. \begin{thm}\label{thm:main} Let $X_d$ be the permutohedral variety. Its Todd class has the following representation in terms of toric invariant cycles: \begin{equation}\label{eq:mainexpansion} \td(X_d)= \sum_{T_{\bullet}\in\CC_{d+1}} \alpha(T_{\bullet}) [V(\sigma_{T_{\bullet}})], \end{equation} with coefficients $\alpha(T_\bullet)$ given by following explicit combinatorial formula \begin{equation}\label{eq:masterformula} \alpha(T_{\bullet}) = \sum_{\D\in\mathcal{D}(T_\bullet)} \Tdcoeff(\D)\Bi(\D)\sgn(\D)\wt(\D), \end{equation} where $\mathcal{D}(T_\bullet)$ is the set of all spider diagrams on $T_\bullet$. Furthermore, we have that $\alpha(T_\bullet)=\bv(T_\bullet)$, where $\bv(\cdot)$ is the Berline--Vergne function. \end{thm} \begin{proof} We start with the expansion in Equation~\eqref{eq:masterbegin}. Then we expand each $ x_{S_\bullet}^\m$ by using Corollary~\ref{cor:expanding}. We obtain \begin{equation}\label{eq:masterproof1} \td(X_d) = \sum_{\D}\Tdcoeff(\D)\Bi(\D)\sgn(\D)\wt(\D)x_\D, \end{equation} where the sum is over \emph{all} possible spider diagrams, to be more precise over $\bigcup\spd(S_\bullet,\m)$ where the union is over all d-admissible pairs. We can rearrange the sum as follows \begin{equation}\label{eq:masterproof2} \td(X_d) = \sum_{T_\bullet\in\CC_{d+1}}x_{T_\bullet}\left(\sum_{\D\in\mathcal{D}(T_\bullet)}\Tdcoeff(\D)\Bi(\D)\sgn(\D)\wt(\D)\right). \end{equation} We proceed to show that the expression obtained in~\eqref{eq:masterproof2} is symmetric. By Remark~\ref{rem:sym} it is enough to prove that two different chains with the same size vector have the same coefficient. Consider two chains $T_\bullet$ and $T'_\bullet$ with same size vector and fix a bijection $\phi$ on $[d+1]$ that simultaneously bijects $T_i$ with $T'_i$ for all relevant $i$. The function $\phi$ also induces a natural bijection (which abusing notation we call $\phi$ also) $\phi:\mathcal{D}(T_\bullet)\to\mathcal{D}(T'_\bullet)$. By Remark~\ref{rem:Tsymm} $\Tdcoeff(\D)=\Tdcoeff(\phi(\D))$. Also $\sgn(\D)=\sgn(\phi(\D))$ since they both have the same number of legs. Finally $(\Bi(\D),\wt(\D))=(\Bi(\phi(\D)),\wt(\phi(\D)))$ since by definition $\Bi$ and $\wt$ depend only on the sizes involved. We have thus proved that~\eqref{eq:masterproof2} is a symmetric square-free expression of $\td(X_d)$. By Theorem~\ref{thm:uniqueness} there is only one such expression, the one given by the Berline--Vergne function, hence we obtain the last part of the theorem. \end{proof} To end this section we count the number of terms appearing in Equation~\eqref{eq:masterformula}. \begin{prop} The number of terms in Equation~\eqref{eq:masterformula} is exponential. \end{prop} \begin{proof} Let $h(n)$ be the number of spider diagrams $\D$ on $[n]$ such that $|\Sp|\in\{1,2,4,6,\cdots\}$ for each $\Sp\in \D$. Its generating function is \begin{equation}\label{eq:genfct1} \sum_{n=1}^{\infty} h(n)z^n = \sum_{k=1}^{\infty}\left(z+2z^2+4z^4+6z^6+\cdots\right)^k. \end{equation} Observe that $z+2z^2+4z^4+6z^6+\cdots = z + \frac{1}{2}\left(\frac{z}{(1-z)^2}+\frac{(-z)}{(1-(-z)^2)}\right)=\frac{z(z^4-2z^2+2z+1)}{(z^2-1)^2}$. Plugging into each term in the right of~\eqref{eq:genfct1} and using the geometric series formula we obtain \begin{equation}\label{eq:genfct2} \sum_{n=z1}^{\infty} h(n)z^n = -\dfrac{z(z^4-2z^2+2z+1)}{z^5-z^4-2z^3+4z^2+z-1}=z+3z^2+5z^3+15z^4+29z^5+\cdots. \end{equation} The conclusion follows since the coefficients of a rational function are asymptotically the powers of the largest root of the denominator~\cite[Theorem~4.1.1]{ec2}, which in this case is $\approx 1.602$. \end{proof} \section{Examples in low (co)dimension}\label{sec:ex} In this section we explicitly compute Equation~\eqref{eq:masterformula} for chains of small length. \begin{prop}[Codimension 2 cones.] Let $(T_1,T_2)\in\CC^2_{d+1}$ be an arbitrary $2$-chain, then \begin{equation}\label{eq:codim2} \bv(T_1,T_2) = \dfrac{1}{4}-\dfrac{1}{12}\left(\dfrac{d+1-t_2}{d+1-t_1}+\dfrac{t_1}{t_2}\right), \end{equation} where $t_i\coloneqq |T_i|$ for $i\in\{1,2\}$. \end{prop} \begin{proof} We use Theorem~\ref{thm:main} to compute $\bv(T_1,T_2)$. We apply Equation~\eqref{eq:masterformula} to $T_\bullet=(T_1,T_2)$. The set $\mathcal{D}(T_\bullet)$ of all possible spider diagrams is shown in Figure~\ref{fig:2}. The leftmost diagram, $\D_1$, consists of trivial spiders. The only contribution of this diagram to the right hand side of~\eqref{eq:masterformula} comes from $\Tdcoeff(\D_1)$, since the other statistics are $1$. For the other two diagrams, $\D_2$ and $\D_3$, we have $\Tdcoeff(\D_i)=1/12$, $\sgn(\D_i)=-1$ (notice that there is only one leg), $\Bi(\D_i)=1$ for $i\in\{2,3\}$. Finally the corresponding weights for $\D_2,\D_3$ are written in Figure~\ref{fig:2}. Formula~\eqref{eq:codim2} then follows. \begin{figure}[ht] \centering \begin{tikzpicture}% \begin{scope}[xshift=0cm,yshift=0cm] \draw (.5,.5)--(4.5,.5)--(4.5,-.6)--(.5,-.6)--cycle; \node[right] at (3,0) {$\frac{1}{4}$}; \node at (1,-.4) {$T_1$}; \node at (2,-.4) {$T_2$}; \node at (2.5,-1) {$\Gamma_1$}; \tikzstyle{every node}=[circle, fill, draw,radius=2pt, inner sep=3.25pt,scale=0.5] \node (i1) at (1,0) {}; \node (i2) at (2,0) {}; \draw [thick] (1,0) circle [radius=0.15]; \draw [thick] (2,0) circle [radius=0.15]; \end{scope} \begin{scope}[xshift=4.4cm,yshift=0cm] \draw (.5,.5)--(4.5,.5)--(4.5,-.6)--(.5,-.6)--cycle; \node[right] at (2.2,0) {$-\frac{1}{12}\cdot\frac{d+1-t_2}{d+1-t_1}$}; \node at (1,-.4) {$T_1$}; \node at (2,-.4) {$T_2$}; \node at (2.5,-1) {$\Gamma_2$}; \tikzstyle{every node}=[circle, fill, draw,radius=2pt, inner sep=3.25pt,scale=0.5] \node (i2) at (2,0) {}; \node (i1) at (1,0) {}; \draw [thick] (1,0) circle [radius=0.15]; \draw [thick] (i1) to[out=45, in=135] (i2); \end{scope} \begin{scope}[xshift=8.8cm,yshift=0cm] \draw (.5,.5)--(4.5,.5)--(4.5,-.6)--(.5,-.6)--cycle; \node[right] at (2.2,0) {$-\frac{1}{12}\cdot\frac{t_1}{t_2}$}; \node at (1,-.4) {$T_1$}; \node at (2,-.4) {$T_2$}; \node at (2.5,-1) {$\Gamma_3$}; \tikzstyle{every node}=[circle, fill, draw,radius=2pt, inner sep=3.25pt,scale=0.5] \node (i1) at (1,0) {}; \node (i2) at (2,0) {}; \draw [thick] (2,0) circle [radius=0.15]; \draw [thick] (i1) to[out=45, in=135] (i2); \end{scope} \end{tikzpicture} \label{fig:2} \caption{All spider diagrams on two vertices with the corresponding contribution to Equation~\eqref{eq:masterformula}.} \end{figure} \end{proof} Formula~\eqref{eq:codim2} (and a similar one for three dimensional cones) was already obtained in~\cite{bvalpha} relying on some general formulas in the Berline--Vergne constructions. Since there is no simple closed formula for their construction for unimodular cones of dimension larger than three, we were not able to obtain more formulas in~\cite{bvalpha} using the same approach. However, by applying Theorem~\ref{thm:main}, we obtain in the proposition below a formula for the $\bv$-value of any arbitrary $4$-dimensional braid cone, which could not be obtained with the previously known tools. \begin{prop} Let $(T_1,T_2,T_3,T_4)\in\CC^4_{d+1}$ be an arbitrary $4$-chain, then \begin{align*} \bv(T_1,T_2,T_3,T_4) &\Mk =\Mk \dfrac{1}{16}\Mk -\Mk \dfrac{1}{48}\left(\dfrac{t_3\Mk -\Mk t_2}{t_3\Mk -\Mk t_1}\Mk +\Mk \dfrac{t_1}{t_2}\Mk +\Mk \dfrac{t_4\Mk -\Mk t_3}{t_4\Mk -\Mk t_2}\Mk +\Mk \dfrac{t_2\Mk -\Mk t_1}{t_3\Mk -\Mk t_1}\Mk +\Mk \dfrac{d\Mk +\Mk 1\Mk -\Mk t_4}{d\Mk +\Mk 1\Mk -\Mk t_3}\Mk +\Mk \dfrac{t_3\Mk -\Mk t_2}{t_4\Mk -\Mk t_2}\right)\\ &\Mk +\Mk \dfrac{1}{144}\left(\dfrac{t_3\Mk -\Mk t_2}{t_3\Mk -\Mk t_1}\Mk \cdot\Mk \dfrac{d\Mk +\Mk 1\Mk -\Mk t_4}{d\Mk +\Mk 1\Mk -\Mk t_3}\Mk +\Mk \dfrac{t_3\Mk -\Mk t_2}{t_4\Mk -\Mk t_1}\Mk +\Mk \dfrac{t_1}{t_2}\Mk \cdot\Mk \dfrac{d\Mk +\Mk 1\Mk -\Mk t_4}{d\Mk +\Mk 1\Mk -\Mk t_3}\Mk +\Mk \dfrac{t_1}{t_2}\Mk \cdot\Mk \dfrac{t_3\Mk -\Mk t_2}{t_4\Mk -\Mk t_2}\right)\\ &\Mk +\Mk \dfrac{1}{720}\left(\dfrac{t_3-t_2}{t_3-t_1}\cdot\dfrac{t_4-t_3}{t_4-t_1}\cdot\dfrac{d+1-t_4}{d+1-t_1}+3\dfrac{t_1}{t_2}\cdot\dfrac{t_4-t_3}{t_4-t_2}\cdot\dfrac{d+1-t_4}{d+1-t_2}\right)\\ &\Mk +\Mk \dfrac{1}{720}\left(3\dfrac{t_1}{t_2}\cdot\dfrac{t_2-t_1}{t_3-t_1}\cdot\dfrac{d+1-t_4}{d+1-t_3}+\dfrac{t_1}{t_2}\cdot\dfrac{t_2-t_1}{t_4-t_2}\cdot\dfrac{t_3-t_2}{t_4-t_2}\right) \end{align*} where $t_i\coloneqq |T_i|$ for $i\in\{1,2,3,4\}$. \end{prop} \begin{proof} We use Theorem~\ref{thm:main} to compute $\bv(T_1,T_2,T_3,T_4)$. We apply Equation~\eqref{eq:masterformula} to $T_\bullet=(T_1,T_2,T_3,T_4)$. The set $\mathcal{D}(T_\bullet)$ of all possible spider diagrams is shown in Figure~\ref{fig:4}. Notice that only for two diagrams $\D$ we have a nontrivial $\Bi(\D)$ and in those two cases $\Bi(\D)=3$. Since the coefficients for~\eqref{eq:tdexpansion} of odd powers bigger than one are all zero, we do not need to consider spider diagrams with spiders of odd sizes (other than trivial spiders of size one) since $\Tdcoeff$ is zero in that case. \end{proof} \begin{exam}\label{ex:negative} Using \textsc{sage}~\cite{sagemath} we found negative values for $\bv_d$ in four dimensional cones in $\Sigma_d$. The smallest $d$ for which this happens is $d+1=25$, where $\bv_{24}(T_1,T_2,T_3,T_4)=-19/1684800$, for any four chain with $|T_1|=10,|T_2|=12,|T_3|=13, |T_4|=15$. \end{exam} Example~\ref{ex:negative} disproves Conjecture~\ref{conj:refined}. Furthermore, it also enables us to prove Theorem~\ref{thm:noneffective}, which we restate here. \begin{thm}\label{thm:noneffective-restate} The Todd class of the permutohedral variety $X_d$ is not effective for $d\geq 24$. That is, there is no way of expressing it as a nonnegative combination of cycles. \end{thm} \begin{proof} It is well known that in the Chow ring of a toric variety arbitrary cycles can be expressed as positive combinations of torus invariant cycles (see Lemma~\ref{lem:aux}), so it suffices to show that there is no positive expansion using torus invariant cycles, \ie that there is no expression of the form~\eqref{eq:toddexpression} with all coefficients positive. By Proposition~\ref{prop:symm}, if there is any positive square-free expression for the Todd class of $X_d$, then $\bv(\cdot)$ is positive for all chains $T_\bullet$ in $\CC_{d+1}$, but Example~\ref{ex:negative} shows that this is false for $d=24$. Moreover, Remark 3.6 in~\cite{bvalpha} implies that there are negative values for all $d\geq 24$. \end{proof} %\begin{landscape} \begin{figure}[ht] \centering \scalebox{0.79}{\begin{tikzpicture}% \begin{scope}[xshift=0cm,yshift=0cm] \node[right] at (3,0) {$\frac{1}{16}$}; \tikzstyle{every node}=[circle, fill, draw,radius=2pt, inner sep=3.5pt,scale=0.5] \node (i1) at (1,0) {}; \node (i2) at (1.5,0) {}; \node (i3) at (2,0) {}; \node (i4) at (2.5,0) {}; \draw [thick] (1,0) circle [radius=0.15]; \draw [thick] (1.5,0) circle [radius=0.15]; \draw [thick] (2,0) circle [radius=0.15]; \draw [thick] (2.5,0) circle [radius=0.15]; \end{scope} \begin{scope}[xshift=0cm,yshift=-2cm] \node[right] at (3,0) {$-\frac{1}{48}\cdot\frac{t_3-t_2}{t_3-t_1}$}; \tikzstyle{every node}=[circle, fill, draw,radius=2pt, inner sep=3.5pt,scale=0.5] \node (i2) at (1.5,0) {}; \node (i1) at (1,0) {}; \node (i3) at (2,0) {}; \node (i4) at (2.5,0) {}; \draw [thick] (1,0) circle [radius=0.15]; \draw [thick] (2,0) circle [radius=0.15]; \draw [thick] (2.5,0) circle [radius=0.15]; \draw [thick] (i1) to[out=30, in=150] (i2); \end{scope} \begin{scope}[xshift=0cm,yshift=-4cm] \node[right] at (3,0) {$-\frac{1}{48}\cdot\frac{t_1}{t_2}$}; \tikzstyle{every node}=[circle, fill, draw,radius=2pt, inner sep=3.5pt,scale=0.5] \node (i1) at (1,0) {}; \node (i2) at (1.5,0) {}; \node (i3) at (2,0) {}; \node (i4) at (2.5,0) {}; \draw [thick] (1.5,0) circle [radius=0.15]; \draw [thick] (2,0) circle [radius=0.15]; \draw [thick] (2.5,0) circle [radius=0.15]; \draw [thick] (i1) to[out=30, in=150] (i2); \end{scope} \begin{scope}[xshift=0cm,yshift=-6cm] \node[right] at (3,0) {$-\frac{1}{48}\cdot\frac{t_4-t_3}{t_4-t_2}$}; \tikzstyle{every node}=[circle, fill, draw,radius=2pt, inner sep=3.5pt,scale=0.5] \node (i3) at (2,0) {}; \node (i2) at (1.5,0) {}; \node (i1) at (1,0) {}; \node (i4) at (2.5,0) {}; \draw [thick] (1,0) circle [radius=0.15]; \draw [thick] (1.5,0) circle [radius=0.15]; \draw [thick] (2.5,0) circle [radius=0.15]; \draw [thick] (i2) to[out=30, in=150] (i3); \end{scope} \begin{scope}[xshift=0cm,yshift=-8cm] \node[right] at (3,0) {$-\frac{1}{48}\cdot\frac{t_2-t_1}{t_3-t_1}$}; \tikzstyle{every node}=[circle, fill, draw,radius=2pt, inner sep=3.5pt,scale=0.5] \node (i2) at (1.5,0) {}; \node (i3) at (2,0) {}; \node (i1) at (1,0) {}; \node (i4) at (2.5,0) {}; \draw [thick] (1,0) circle [radius=0.15]; \draw [thick] (2,0) circle [radius=0.15]; \draw [thick] (2.5,0) circle [radius=0.15]; \draw [thick] (i2) to[out=30, in=150] (i3); \end{scope} \begin{scope}[xshift=5cm,yshift=0cm] \node[right] at (3,0) {$-\frac{1}{48}\cdot\frac{d+1-t_4}{d+1-t_3}$}; \tikzstyle{every node}=[circle, fill, draw,radius=2pt, inner sep=3.5pt,scale=0.5] \node (i4) at (2.5,0) {}; \node (i1) at (1,0) {}; \node (i3) at (2,0) {}; \node (i2) at (1.5,0) {}; \draw [thick] (1,0) circle [radius=0.15]; \draw [thick] (1.5,0) circle [radius=0.15]; \draw [thick] (2,0) circle [radius=0.15]; \draw [thick] (i3) to[out=30, in=150] (i4); \end{scope} \begin{scope}[xshift=5cm,yshift=-2cm] \node[right] at (3,0) {$-\frac{1}{48}\cdot\frac{t_3-t_2}{t_4-t_2}$}; \tikzstyle{every node}=[circle, fill, draw,radius=2pt, inner sep=3.5pt,scale=0.5] \node (i3) at (2,0) {}; \node (i4) at (2.5,0) {}; \node (i1) at (1,0) {}; \node (i2) at (1.5,0) {}; \draw [thick] (1,0) circle [radius=0.15]; \draw [thick] (1.5,0) circle [radius=0.15]; \draw [thick] (2.5,0) circle [radius=0.15]; \draw [thick] (i3) to[out=30, in=150] (i4); \end{scope} \begin{scope}[xshift=5cm,yshift=-4cm] \node[right] at (2.5,0) {$\frac{1}{144}\cdot\frac{t_3-t_2}{t_3-t_1}\cdot\frac{d+1-t_4}{d+1-t_3}$}; \tikzstyle{every node}=[circle, fill, draw,radius=2pt, inner sep=3.5pt,scale=0.5] \node (i2) at (1.5,0) {}; \node (i4) at (2.5,0) {}; \node (i1) at (1,0) {}; \node (i3) at (2,0) {}; \draw [thick] (1,0) circle [radius=0.15]; \draw [thick] (2,0) circle [radius=0.15]; \draw [thick] (i1) to[out=30, in=150] (i2); \draw [thick] (i3) to[out=30, in=150] (i4); \end{scope} \begin{scope}[xshift=5cm,yshift=-6cm] \node[right] at (3,0) {$\frac{1}{144}\cdot\frac{t_3-t_2}{t_4-t_1}$}; \tikzstyle{every node}=[circle, fill, draw,radius=2pt, inner sep=3.5pt,scale=0.5] \node (i2) at (1.5,0) {}; \node (i3) at (2,0) {}; \node (i1) at (1,0) {}; \node (i4) at (2.5,0) {}; \draw [thick] (1,0) circle [radius=0.15]; \draw [thick] (2.5,0) circle [radius=0.15]; \draw [thick] (i1) to[out=30, in=150] (i2); \draw [thick] (i3) to[out=30, in=150] (i4); \end{scope} \begin{scope}[xshift=5cm,yshift=-8cm] \node[right] at (3,0) {$\frac{1}{144}\cdot\frac{t_1}{t_2}\cdot\frac{d+1-t_4}{d+1-t_3}$}; \tikzstyle{every node}=[circle, fill, draw,radius=2pt, inner sep=3.5pt,scale=0.5] \node (i1) at (1,0) {}; \node (i4) at (2.5,0) {}; \node (i2) at (1.5,0) {}; \node (i3) at (2,0) {}; \draw [thick] (1.5,0) circle [radius=0.15]; \draw [thick] (2,0) circle [radius=0.15]; \draw [thick] (i1) to[out=30, in=150] (i2); \draw [thick] (i3) to[out=30, in=150] (i4); \end{scope} \begin{scope}[xshift=10cm,yshift=0cm] \node[right] at (3,0) {$\frac{1}{144}\cdot\frac{t_1}{t_2}\cdot\frac{t_3-t_2}{t_4-t_2}$}; \tikzstyle{every node}=[circle, fill, draw,radius=2pt, inner sep=3.5pt,scale=0.5] \node (i1) at (1,0) {}; \node (i3) at (2,0) {}; \node (i2) at (1.5,0) {}; \node (i4) at (2.5,0) {}; \draw [thick] (1.5,0) circle [radius=0.15]; \draw [thick] (2.5,0) circle [radius=0.15]; \draw [thick] (i1) to[out=30, in=150] (i2); \draw [thick] (i3) to[out=30, in=150] (i4); \end{scope} \begin{scope}[xshift=10cm,yshift=-2cm] \node[right] at (3,0) {$\frac{1}{720}\cdot\frac{t_3-t_2}{t_3-t_1}\cdot\frac{t_4-t_3}{t_4-t_1}\cdot\frac{d+1-t_4}{d+1-t_1}$}; \tikzstyle{every node}=[circle, fill, draw,radius=2pt, inner sep=3.5pt,scale=0.5] \node (i3) at (2,0) {}; \node (i2) at (1.5,0) {}; \node (i4) at (2.5,0) {}; \node (i1) at (1,0) {}; \draw [thick] (1,0) circle [radius=0.15]; \draw [thick] (i1) to[out=30, in=150] (i2); \draw [thick] (i1) to[out=60, in=120] (i3); \draw [thick] (i1) to[out=75, in=105] (i4); \end{scope} \begin{scope}[xshift=10cm,yshift=-4cm] \node[right] at (3,0) {$\frac{1}{720}3\frac{t_1}{t_2}\cdot\frac{t_4-t_3}{t_4-t_2}\cdot\frac{d+1-t_4}{d+1-t_2}$}; \tikzstyle{every node}=[circle, fill, draw,radius=2pt, inner sep=3.5pt,scale=0.5] \node (i1) at (1,0) {}; \node (i3) at (2,0) {}; \node (i4) at (2.5,0) {}; \node (i2) at (1.5,0) {}; \draw [thick] (1.5,0) circle [radius=0.15]; \draw [thick] (i2) to[out=150, in=30] (i1); \draw [thick] (i2) to[out=30, in=150] (i3); \draw [thick] (i2) to[out=60, in=120] (i4); \end{scope} \begin{scope}[xshift=10cm,yshift=-6cm] \node[right] at (3,0) {$\frac{1}{720}3\frac{t_1}{t_2}\cdot\frac{t_2-t_1}{t_3-t_1}\cdot\frac{d+1-t_4}{d+1-t_3}$}; \tikzstyle{every node}=[circle, fill, draw,radius=2pt, inner sep=3.5pt,scale=0.5] \node (i1) at (1,0) {}; \node (i2) at (1.5,0) {}; \node (i4) at (2.5,0) {}; \node (i3) at (2,0) {}; \draw [thick] (2,0) circle [radius=0.15]; \draw [thick] (i3) to[out=150, in=30] (i2); \draw [thick] (i3) to[out=30, in=150] (i4); \draw [thick] (i1) to[out=60, in=120] (i3); \end{scope} \begin{scope}[xshift=10cm,yshift=-8cm] \node[right] at (3,0) {$\frac{1}{720}\cdot\frac{t_1}{t_2}\cdot\frac{t_2-t_1}{t_4-t_2}\cdot\frac{t_3-t_2}{t_4-t_2}$}; \tikzstyle{every node}=[circle, fill, draw,radius=2pt, inner sep=3.5pt,scale=0.5] \node (i3) at (2,0) {}; \node (i2) at (1.5,0) {}; \node (i1) at (1,0) {}; \node (i4) at (2.5,0) {}; \draw [thick] (2.5,0) circle [radius=0.15]; \draw [thick] (i3) to[out=30, in=150] (i4); \draw [thick] (i2) to[out=60, in=120] (i4); \draw [thick] (i1) to[out=75, in=105] (i4); \end{scope} \end{tikzpicture}} \caption{All spider diagrams on four vertices with the corresponding contribution to Equation~\eqref{eq:masterformula}.} \label{fig:4} \end{figure} %\end{landscape} \section{Positivity for linear coefficients}\label{sec:edge} As mentioned in the introduction for every lattice polytope $P$ the function $\Lat(tP), t\in \NN$ is a polynomial in $t$ of dimension $d=\dim P$, \ie $\Lat(tP) = a_0+a_1t^1+a_2t^2+\cdots+a_dt^d, a_i\in\mathbb{Q}.$ This is the \important{Ehrhart polynomial} of $P$ and will be denoted by $\Lat(P,t)$. We also define $\Lat^i(P)\coloneqq [t^i]\Lat(P,t)$, the coefficient of $t^i$ in the Ehrhart polynomial. \subsection{Positivity of Berline--Vergne function} In this section we take a different argument to show that the $\bv$ values are indeed positive on codimension one cones of the braid fan and thus the main Conjecture~\ref{conj:main} is true for $\Lat^1$. The arguments in this section are independent of the rest of the paper. We make use of special polytopes called \emph{hypersimplices}. \begin{defi} The \emph{hypersimplex} $\Delta_{k,d+1}$ is defined as \[ \Delta_{k,d+1} = \Perm ( \underbrace{0,\cdots,0}_{d+1-k}, \underbrace{1,\cdots,1}_{k} ).\] \end{defi} \begin{prop}\label{prop:hyper} If $\Lat^1(\Delta_{k,d+1})>0$ for all $1\leq k\leq n$ then $\bv$ is positive on every codimension one cone, thus $\Lat^1(P)>0$ for any generalized permutohedra. \end{prop} \begin{proof} This is a consequence of~\cite[Theorem~5.5]{bvalpha}. In the case of an edge the mixed valuation is equal to the valuation itself, the rest of the formula is positive hence the first part follows. The second part is a consequence of the reduction theorem~\cite[Theorem~3.5]{bvalpha} which shows how the positivity of $\bv$ for all codimension $k$ cones in $\Sigma_d$ implies positivity of $\Lat^k$ for all generalized permutohedra. \end{proof} The following result is standard~\cite[Chapter~4, Ex.~62]{ec1}. \begin{prop} The Ehrhart polynomial for $\Delta_{k,d+1}$ is given by \begin{equation}\label{eq:ehrhart} \Lat(\Delta_{k,d+1}, t) = [z^{kt}]\left(\dfrac{1-z^{t+1}}{1-z}\right)^{d+1}. \end{equation} This formula can be turned into the more explicit \begin{equation}\label{eq:ugly} \Lat(\Delta_{k,d+1}, t) = \sum_{i=0}^k (-1)^i\binom{d+1}{i}\binom{d+t(k-i)-i}{d}. \end{equation} \end{prop} \begin{lemm}\label{lem:computation} For any $k\leq d$, $\Lat^1(\Delta_{k,d+1})>0$. \end{lemm} \begin{proof} We are going to keep track of the linear term on each summand on Equation~\eqref{eq:ugly}. There are two cases. For $i=0$ we get $(-1)^0\binom{d+1}{0}\binom{d+tk}{d}$ so \begin{align*} [t^1]\binom{d+tk}{d}&=[t^1]\dfrac{(tk+d)\cdots(tk+1)}{d!} =\sum_{i=1}^d\dfrac{k}{i}. \end{align*} For $i>0$ we get $(-1)^i\binom{d+1}{i}\binom{d+t(k-i)-i}{d}$ so we first look for the linear term of \begin{align*} \prod_{j=1}^d(t(k-i)-i+j)&=\left(\prod_{j=1}^{i-1}(t(k-i)-i+j)\right)\left(t(k-i)\right)\left(\prod_{j=i+1}^d(t(k-i)-i+j)\right),\\ \end{align*} which is equal to $(i-1)!(-1)^{i-1}(k-i)(d-i)!$. Now we can compute \begin{align*} [t^1](-1)^i\binom{d+1}{i}\binom{d+t(k-i)-i}{d}&\Mk =\Mk (-1)^i\binom{d+1}{i}\cdot\dfrac{1}{d!} (i-1)!(-1)^{i-1}(k-i)(d-i)!\\ &\Mk =\Mk -\dfrac{(d+1)(k-i)}{i(d+1-i)}. \end{align*} Putting these equations together we get that the linear term in~\eqref{eq:ugly} is \begin{align*} [t^1]\sum_{i=0}^k (-1)^i\binom{d\Mk +\Mk 1}{i}\binom{d\Mk +\Mk t(k\Mk -\Mk i)-i}{d}&=\sum_{i=0}^k [t^1]\left((-1)^i\binom{d+1}{i}\binom{d+t(k-i)-i}{d}\right)\\ &=\sum_{i=1}^n\dfrac{k}{i} - \sum_{i=1}^k\dfrac{(d+1)(k-i)}{i(d+1-i)}\\ &=\sum_{i=1}^k \left(\dfrac{k}{i}-\dfrac{(d+1)(k-i)}{i(d+1-i)}\right) + \sum_{i=k+1}^n \dfrac{k}{i}\\ &>0, \end{align*} because each parenthesis is positive since $\dfrac{k}{k-i}\geq \dfrac{d+1}{d+1-i}$ for $d+1>k$. \end{proof} \begin{thm}\label{thm:linear} Conjecture~\ref{conj:main} is true for the linear terms. More precisely, $\Lat^1(P)>0$ for every lattice generalized permutohedron $P$. \end{thm} \begin{proof} It follows from Proposition~\ref{prop:hyper} and Lemma~\ref{lem:computation}. \end{proof} In~\cite{kat} the authors use their results in Minkowski linear functionals to give an alternative proof of Theorem~\ref{thm:linear}. \appendix \section{Algebraic cycles in toric varieties} We include a sketch of the following lemma, since it is a crucial reduction in the proof of Theorem~\ref{thm:noneffective-restate} and we could not find a reference in the literature. \begin{lemm}\label{lem:aux} Let $X$ be a smooth projective toric variety of dimension $n$ over an algebraically closed field $\k$. Then arbitrary algebraic cycles of $X$ are \emph{positive} combination of the torus invariant cycles. \end{lemm} \begin{proof}[Sketch of proof:] Let $T\subset X$ be its dense torus and fix an isomorphism $T\cong T_1\times\cdots\times T_n$, where each $T_i$ is isomorphic to $\k^*$. Let $Z$ be a general cycle. We can assume that $Z$ is an irreducible subvariety. Taking the \emph{flat limit} (See~\cite[Section~II.3.4]{schemes}) of $Z$ over $T_1\cong \k^*$ we obtain an subvariety $Z_1$ whose associated algebraic cycle is effective and rationally equivalent to $Z$, and furthermore each irreducible component of $Z_1$ is $T_1$-invariant. For every irreducible component of $Z_1$ we now take the flat limit over $T_2$, taking the union we obtain an effective cycle $Z_2$ rationally equivalent to $Z_1$ that is $T_1$- and $T_2$-invariant. Continuing in this way after $n$ iterations we get at an effective cycle $Z_n$ rationally equivalent to each $Z_i, i