%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2020}
\articlenumber{88}
\addbibresource{fpsac.bib}

%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc
\usepackage{tikz}
%% note that the class file already loads {amsmath, amsthm, amssymb}

\theoremstyle{plain}
\newtheorem{thm}{Theorem}[section]
\newtheorem{prop}[thm]{Proposition}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{claim}[thm]{Claim}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{conj}[thm]{Conjecture}
\newtheorem{slog}[thm]{Slogan}
\theoremstyle{definition}
\newtheorem{defn}[thm]{Definition}
\newtheorem{setup}[thm]{Setup}
\newtheorem{ques}[thm]{Question}
\newtheorem{ex}[thm]{Example}
\newtheorem{sit}[thm]{Situation}
\newtheorem{notn}[thm]{Notation}
\newtheorem{rem}[thm]{Remark}
\newtheorem{warn}[thm]{Warning}
\numberwithin{equation}{section}

\def\Q{{\mathbb Q}}
\def\N{{\mathbb N}}
\def\Z{{\mathbb Z}}
\def\R{{\mathbb R}}
\def\fS{{\mathfrak S}}

\def\ds{\displaystyle}
%\newcommand{\bm}[1]{{\mbox{\boldmath $#1$}}Fu Liu is partially supported by a grant from the Simons Foundation \#245939 and by NSF grant DMS-1265702.}
\newcommand{\bm}[1]{{\boldsymbol{#1}}}
\def\0{\bm{0}}
\def\a{\bm{a}}
\def\b{\bm{b}}
\def\c{\bm{c}}
\def\e{\bm{e}}
\def\k{\bm{k}}
\def\m{\bm{m}}
\def\n{\bm{n}}
\def\p{\bm{p}}
\def\q{\bm{q}}
\def\r{\bm{r}}
\def\s{\bm{s}}
\def\t{\bm{t}}
\def\v{\bm{v}}
\def\u{\bm{u}}
\def\w{\bm{w}}
\def\x{\bm{x}}
\def\y{\bm{y}}
\def\z{\bm{z}}

\def\balpha{\bm{\alpha}}
\def\bbeta{\bm{\beta}}
\def\bgamma{\bm{\gamma}}

\def\ts{{\tilde{\bm s}}}
\def\tp{{\tilde{\bm p}}}
\def\tq{{\tilde{\bm q}}}
\def\tu{{\tilde{\bm u}}}




\def\cC{\mathcal C}
\def\cD{\mathcal D}
\def\cF{{\mathcal F}}
\def\cG{\mathcal G}
\def\L{\mathcal L}
\def\cM{\mathcal M}
\def\cN{\mathcal N}
\def\cS{\mathcal S}
\def\O{\mathcal O}
\def\cP{\mathcal P}
\def\cQ{\mathcal Q}
\def\l{\ell}


%\newcommand{\conv}{\mathrm{conv}}
\newcommand{\cR}{\mathcal{R}}
%\renewcommand{\S}{\mathcal{S}}

\newcommand{\wt}{\mathrm{wt}}
\newcommand{\intwt}{\mathrm{intwt}}
\newcommand{\bdwt}{\mathrm{bdwt}}
\newcommand{\Lat}{\mathrm{Lat}}
\newcommand{\vol}{\mathrm{Vol}}
\newcommand{\nvol}{\mathrm{nvol}}
\newcommand{\area}{\mathrm{area}}
\newcommand{\boundary}{\mathrm{boundary}}
\newcommand{\mv}{\mathrm{\mathcal{M}Vol}}
\newcommand{\ml}{\mathrm{\mathcal{M}Lat}}
\newcommand{\mphi}{\mathcal{M}\phi}
\def\M{\operatorname{M}}


\def\b{\mathbf{b}}
\def\x{\mathbf{x}}
%\newcommand{\bbeta}{\widetilde{\beta}}
\newcommand{\ggamma}{\widetilde{\gamma}}

\def\tcone{\operatorname{tcone}}
\def\fcone{\operatorname{fcone}}
\def\ncone{\operatorname{ncone}}
\def\conv{\operatorname{ConvexHull}}
\def\cone{\operatorname{Cone}}
\def\vert{\operatorname{vert}}
\def\Perm{\operatorname{Perm}}
\def\proper{\operatorname{prop}}
\def\aff{\operatorname{aff}}
\def\lin{\operatorname{lin}}
\def\td{\operatorname{Td}}
%%%%%%%%%%%%%%%%%%%%%%%%%
%% Blackboard bold
%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\1}{\mathbf{1}}
\newcommand{\K}{\mathbb{K}}

\renewcommand{\k}{\textbf{k}}


%\newcommand{\A}{{\cal A}}
\newcommand{\B}{{\mathcal B}}
\newcommand{\SpD}{\mathrm{SpD}}
\newcommand{\LSpD}{\mathrm{LSpD}}
\newcommand{\Sp}{\mathrm{Sp}}
\newcommand{\Le}{\mathrm{Le}}
\newcommand{\Bi}{\mathrm{Binom}}
\newcommand{\sgn}{\mathrm{sgn}}
\newcommand{\ch}{\mathrm{ch}}
\newcommand{\Tdcoeff}{\mathrm{Tdcoeff}}
\newcommand{\mon}{\mathrm{mon}}
\newcommand{\He}{\mathrm{Heads}}
\newcommand{\hB}{\overline{\mathcal B}}
\newcommand{\CC}{\mathcal{C}}
\newcommand{\FF}{\mathbb{F}}
\newcommand{\bv}{\alpha^\textsc{bv}}
\renewcommand{\H}{\mathcal{H}}
\newcommand{\NN}{{\mathbb{N}}}
\newcommand{\rk}{\textrm{rk}}
%\newcommand{\R}{\mathbb{R}}
\renewcommand{\SS}{\mathcal{S}}
\newcommand{\T}{\mathcal{T}}
\newcommand{\ZZ}{\mathbb{Z}}
%\newcommand{\0}{\widehat{0}}
%\renewcommand{\span}{\textrm{span}}
\newcommand{\Hom}{\textrm{Hom}}
\renewcommand{\Im}{\textrm{Im }}

\newcommand{\fcc}[1]{\textsc{\textcolor{red}{Federico says:}} \textsf{\textcolor{red}{#1}}}
\newcommand{\fu}[1]{\textsc{\textcolor{blue}{Fu says:}} \textsf{\textcolor{blue}{#1}}}
\newcommand\commentout[1]{}
\hyphenation{mar-gin-al-ia}

\usepackage{lipsum}

%% define your title in the usual way
\title{On the Todd Class of the Permutohedral variety}

%% define your authors in the usual way
\author{Federico Castillo\thanks{\href{mailto:fcastillo@ku.edu}{fcastillo@ku.edu}. Partially supported by NSF grant DMS--1440140}\addressmark{1} \and Fu Liu\thanks{\href{mailto:fuliu@math.ucdavis.edu}{fuliu@math.ucdavis.edu} Partially supported by the Simons Foundation grant \#426756 and by NSF grant DMS--1440140}\addressmark{2}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1} Department of Mathematics, University of Kansas, KS, USA \\ \addressmark{2} Department of Mathematics, University of California, Davis, CA, USA}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\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 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.}

\keywords{Ehrhart polynomials, generalized permutohedra, Berline--Vergne construction}



\begin{document}

\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 \textbf{lattice polyope} 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):=|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 polyopes. We can do this by requiring the function $\alpha$ to be \emph{local}, i.e., if the numbers $\alpha(F,P)$ only depend 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 local function $\alpha$ that satisfies \eqref{eq:exterior} for all lattice polytopes $P$ is called a \textbf{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 \textbf{braid fan} $\Sigma_d$ is the complete fan in the quotient space $W_d = \R^{d+1}/(1,1,\dots,1)$ obtained from the hyperplane arrangement $H_{i,j}:=\{x\in\R^{d+1}: x_i-x_j=0\}$ for $1\leq i<j\leq d+1$.
A \textbf{generalized permutohedron} is a polytope whose normal fan is a coarsening of the braid fan $\Sigma_d.$

 Our methods for computing a McMullen function for generalized permutohedra are based on the theory of toric varieties.
\subsection{Todd classes of toric varieties}\label{subsec:toddintro}

Let $P$ be a lattice polytope with normal fan $\Sigma$ and $X_\Sigma$ be the associated toric variety. The \textbf{Todd class} $\td(X_\Sigma)$ is an element in the Chow ring of $X_\Sigma$. As such it can be written as a $\Q$-linear combination of the toric invariant cycles $[V(\sigma)]$:
\begin{equation}\label{eq:toddexpression}
\td(X_\Sigma) = \sum_{\sigma\in \Sigma} r_\Sigma(\sigma)\ [V(\sigma)],\quad r_\Sigma(\sigma)\in\Q.
\end{equation}
Since the cycles $[V(\sigma)]$ satisfy algebraic relations, the values $r_\Sigma(\sigma)$ satisfying \eqref{eq:toddexpression} are not uniquely determined. 
An amazing connection with lattice polytopes is given by the fact that any function $r_\Sigma(\cdot)$ satisfying \eqref{eq:toddexpression} defines a function $\alpha$ satisfying \eqref{eq:exterior} for $P$ by setting 
\[\alpha(F,P)=r_{\Sigma}(\ncone(F,P)).\] A proof of this fact can be found in Danilov's 1978 survey \cite{danilov} where he further asked if there exist a function $r$ that depends only on the cone $\sigma$ and not on $\Sigma$, in other words, if there exist a \emph{local} function $r$ satisfying \eqref{eq:toddexpression} for all fans $\Sigma$.
Accordingly, we call such a function $r$ on pointed cones a \emph{Danilov function}. By setting \[\alpha(F,P)=r(\ncone(F,P)),\] any Danilov function gives a McMullen function.

We want to briefly remark on two constructions of Danilov functions from the last two decades. Pommersheim and Thomas \cite{toddclass} gave a construction of a Danilov function $r(\sigma)$ that depends on choosing a \emph{complement map} for subspaces. A couple of years later Berline and Vergne \cite{bvoriginal} constructed a McMullen function with the property that it is computable in polynomial time fixing the dimension and it is a valuation on cones. We call this construction the BV-function, and denote it by $\bv$. 

Later they showed that if a function $r$ on pointed cones is defined by $r(\sigma) = \bv\left( F,P \right)$ as long as $\sigma = \ncone(F,P)$, then it is a Danilov function. For convenience, we abuse the notation, and consider $\bv$ to be both a function on pairs $(F,P)$ and a function on cones with the connection that $\bv(F,P) = \bv(\ncone(F,P)).$
Thus, $\bv$ is both a McMullen function and a Danilov function.
%In \cite{garpomm} Pommersheim and Garoufalidis proved that using an inner product for a complement map in the methods of \cite{toddclass} results in the Danilov function $\bv$, which in turns gives an alternative way of computing it. 

Both constructions, Berline--Vergne's and Pommersheim-Thomas', are algorithmic. A priori it is very hard to get formulas for general cones. There are very few examples of fans $\Sigma$ for which $\bv(\sigma)$ (or any other Danilov function) have been computed for all $\sigma\in\Sigma$. In this paper, we focus on computing the BV-function on all cones in braid fans using tools developed in previous work of the authors.

In \cite{bvalpha} we exploited an extra symmetry property satisfied by the function $\bv$, and used this symmetry to study the values on cones in \textbf{braid fans}. One main result in \cite{bvalpha} is the \emph{uniqueness theorem}, which in the context of the present paper states that, for the specific example of braid fans, $\bv$ is the unique function satisfying \eqref{eq:toddexpression} and being invariant under the permutation action of the symmetric group on the ambient space.
Using this, we obtain the main result of this paper -- \cref{thm:main} -- which gives a combinatorial formula for $\bv$ on all cones in braid fans. 


\subsection{Connection to Ehrhart theory}
Ehrhart proved that for every lattice polytope $P$ the function $\Lat(tP)$ for $t\in \NN$ is a polynomial in $t$ of dimension $d=\dim P.$ More precisely, there exist $a_0, a_1, \dots, a_d \in\mathbb{Q}$ such that for all $t \in \NN, \Lat(tP) := a_0+a_1t^1+a_2t^2+\cdots+a_dt^d.$ The right hand side is called the \textbf{Ehrhart polynomia}l of $P$. Given a McMullen formula $\alpha$ one can deduce that 
\begin{equation}\label{eq:refine}
	a_k = \sum_{\substack{F: \text{a face of $P$} \\\dim F=k}}\alpha(F,P) \ \nvol(F). 
\end{equation}

%The first, second, and the last coefficients in the Ehrhart polynomial of a lattice polytope are well-understood. In particular, they are all positive. However, any of the remaining ``middle coefficients'' $a_{d-2}, a_{d-3}, \dots, a_1$ can be negative. 
We call a lattice polytope $P$ \textbf{Ehrhart positive} if all the (middle) coefficients of its Ehrhart polynomial are positive (see \cite{positivesurvey} for a recent survey on Ehrhart positivity). 
%In \cite{deloera} the authors conjectured that matroid polytopes are Ehrhart positive.
%One of the main motivations for \cite{bvalpha} was trying to prove that conjecture. 
One of the main motivations for \cite{bvalpha} was to prove a conjecture of De Loera et al. asserting that matriod polytopes are Ehrhart positive \cite{deloera}. 
Noticing that matroid polytopes belong to the family of generalized permutohedra, we focus on the latter larger family of polytopes.
\begin{conj}[{\cite[Conjecture 1.2]{bvalpha}}]\label{conj:main}
Lattice generalized permutohedra are Ehrhart positive.
\end{conj}

One observes that a consequence of \eqref{eq:refine} is that if we have a McMullen function $\alpha$ such that $\alpha(F,P)$ is positive for all faces $F\subset P$ then $P$ is Ehrhart positive. (The converse is not true as shown in Section 3.4 of \cite{nill}.) Using the fact that the BV-function $\bv$ is a McMullen function and it has certain valuation properties, we showed in \cite{bvalpha} that the following conjecture (if true) implies \cref{conj:main}.
%as an attempt to prove \cref{conj:main}, we proposed the following stronger conjecture.
\begin{conj}[{\cite[Conjecture 1.3]{bvalpha}}]\label{conj:refined}
Let $P$ be a generalized permutohedron and $F\subset P$ a face, then $\bv(F,P)$ is positive. 
%In other words, since $\bv(F,P)=\bv(\ncone(F,P))$,
Equivalently, $\bv(\sigma)$ is positive for every cone $\sigma$ in the braid fan.
\end{conj}

%In \cite{bvalpha}, we were able to prove that the third and fourth coefficients of the Ehrhart polynomial of any lattice generalized permutohedron are positive by showing that $\bv(F,P)$ is positive for any pair $(F,P)$ in which $P$ is a lattice generalized permutohedron and $F$ is a face of $P$ of codimension at most $3,$ which is equivalent to that $\bv(\sigma)$ is positive for any cone $\sigma$ of dimension at most $3$ in a braid fan. 

Despite of these positive results we've obtained in our previous work towards \cref{conj:refined}, in the present paper, we use our main result - the combinatorial formula described in \cref{thm:main} - to find negative values for $\bv$ on some cones in braid fans, hence disproving \cref{conj:refined}. Note that this does not imply that \cref{conj:main} is false, and in fact we present a proof, independent of the rest of the paper, that the linear coefficient of the Ehrhart polynomial of any lattice generalized permutohedron is positive, providing further evidence to \cref{conj:main}. This positivity result of linear Ehrhart coefficient was proved independently by Jochemko and Ravichandran in \cite{kat}, using different techniques from what are presented in this paper.



\section{Preliminaries and notation.}\label{sec:prelim}
Here we review concepts and notation that we are going to use. As standard we denote $[d+1]:=\{1,2,3,\cdots,d,d+1\}$. The set of all subsets of $[d+1]$ form a poset $\B_{d+1}$ called the \textbf{boolean algebra} and we define the \textbf{truncated boolean algebra}, denoted by $\hB_{d+1}$, to be the poset obtained from $\B_{d+1}$ by removing $[d+1]$ and $\emptyset$. Two elements $S,S'\in \hB_{d+1}$ are \textbf{incomparable} if neither $S\subseteq S'$ nor $S\supseteq S'$. A \textbf{$k$-chain} $S_{\bullet}=(S_1,\cdots,S_k)$ is a sequence of $k$ totally ordered elements of $\hB_{d+1}$.
For notational purposes, we complete $S_{\bullet}$ by adding $\emptyset$ and $[d+1]$ to obtain
$ \emptyset=S_0\subsetneq S_1\subsetneq\cdots \subsetneq S_k \subsetneq S_{k+1}=[d+1].$ We denote the new sequence by $\widehat{S_{\bullet}}.$ The set of all $k$-chains in $\hB_{d+1}$ is denoted $\CC_{d+1}^k$ and let $\CC_{d+1}=\bigcup_k \CC_{d+1}^k$.


\subsection{Braid fan and Permutohedral variety}\label{subsec:braid}
Let $V_d$ be the $d$-dimensional real vector space $\textbf{1}^\perp\subset \R^{d+1}$, where $\textbf{1}$ is the all one vector. Its dual is $W_d = \R^{[d+1]}/(\textbf{1})$. 

The combinatorics of the braid fans are summarized in \cref{lem:1-1} below.
Let $\e_1,\cdots,\linebreak[0]\e_{d+1}$ be the standard basis of $\R^{d+1}$ and for each $S\in \hB_{d+1}$ we define $\e_S:=\sum_{i\in S}\e_i$ as an element in $W_d$. For any $k$-chain $S_\bullet$ of $\hB_{d+1},$ we define the corresponding \textbf{braid cone} $\sigma_{S_\bullet}:=\cone(\e_S: S\in S_\bullet),$
which is $k$-dimensional. The following is well known.
\begin{lem}\label{lem:1-1}
The map $S_\bullet \mapsto \sigma_{S_\bullet}$ gives a one-to-one correspondence between chains in $\CC_{d+1}$ and cones in the braid fan $\Sigma_d.$ Moreover, $k$-chains in $\CC_{d+1}$ are in bijection with $k$-dimensional cones in $\Sigma_d.$ 
\end{lem}



\subsection{Permutohedral variety}
For toric varieties we follow the notation and terminology of \cite{fulton}. The \textbf{permutohedral variety} $X_d$ is the toric variety associated to $\Sigma_d$. For each $S_\bullet\in\CC_{d+1}$, its corresponding braid cone $\sigma_{S_{\bullet}}$ is associated with a subvariety $V(\sigma_{S_{\bullet}})$. These subvarieties are the \textbf{torus invariant cycles}.


For any $d\in \NN$ we define the following ring \[R_d:=\mathrm{k} [x_S: S\in \hB_{d+1}],\] where $\mathrm{k}$ is any algebraically closed field.  For any element $i\in[d+1]$ we define the linear form $\ell_i:=\sum_{S \ni i} x_S$. 
\begin{defn}
	
	The \textbf{Chow ring of the permutohedral variety $X_d$} can be presented as $A_d \cong R_d/(I_1+I_2)$, where
\[
I_1 = \langle x_Sx_{S'}: \text{ for $S,S'$ incomparable}\rangle,\qquad I_2 = \langle \ell_a-\ell_b:\text{ for all $a,b\in [d+1]$} \rangle.
\]
\end{defn}

We are interested in computing the Todd class of $X_d$ in $A_d$. The following definition follows \cite[Section 5]{fulton}.
\begin{defn}
	The \textbf{Todd class of $X_d$} is the element of $A_d$ defined as
\begin{equation}\label{eq:tddef}
\td (X_d) := \prod_{S\in\hB_{d+1}} \left( \dfrac{x_S}{1-e^{-x_S}}\right),
\end{equation}
which is an element of $A_d$ by expanding each parenthesis on the right hand side as
\begin{equation}\label{eq:tdexpansion}
\dfrac{x}{1-e^{-x}} = 1+\dfrac{x}{2}+\sum_{i=1}^\infty \dfrac{(-1)^{i-1}B_i}{(2i)!}x^{2i}=1+\dfrac{x}{2}+\dfrac{x^2}{12}-\dfrac{x^4}{720}+\dfrac{x^6}{30240}+\cdots.
\end{equation}
Here $B_i$ is the $i$-th Bernoulli number. Also note that $f^{k}=0$ for any $k>d$ and $f\in A_d$, so the sum in \eqref{eq:tdexpansion} is finite. 
\end{defn}

For each $S_\bullet \in \CC_{d+1},$ the class of the subvariety $V(\sigma_{S_{\bullet}})$ in $A_d$ is denoted $[V(\sigma_{S_{\bullet}})]$, and it can be represented as a square-free element in $A_d:$ 
\begin{equation}\label{eq:sqfree}
[V(\sigma_{S_{\bullet}})] = x_{S_{\bullet}}:= \prod_{S\in S_{\bullet}} x_S.
\end{equation}
%where $S_{\bullet}=(S_1,\cdots, S_k)$. 
We are interested in expressions for $\td(X_d)$ in terms of classes of the torus invariant cycles. In other words, we are looking for $r(S_\bullet)\in\Q$ such that
\begin{equation}\label{eq:tdexpression}
	\td(X_d) = \sum_{S_{\bullet}\in\CC_{d+1}} r_d(S_\bullet) \ x_{S_\bullet} = \sum_{S_{\bullet}\in\CC_{d+1}} r_d(S_\bullet) \ [V(\sigma_{S_{\bullet}})].
\end{equation}
We call such an expression a \textbf{square-free expression for the Todd class $\td(X_d)$ of $X_d$}.
Our interest in such an expression lies in the following theorem originally attributed to Danilov which is already mentioned in \cref{subsec:toddintro}. Here we only state it in the particular case of braid fans.
\begin{thm}[Section 5 in \cite{fulton}]\label{thm:dani}
	Let $P$ be a $d$-dimensional lattice generalized permutohedron with normal fan $\Sigma_d$. Suppose $r_d$ is a function defined on $\CC_{d+1}$ such that \eqref{eq:tdexpression} holds. Using the one-to-one correspondence between chains in $\CC_{d+1}$ and cones in $\Sigma_d$ described in \cref{lem:1-1}, we can consider $r_d$ to be a function on braid cones by letting $r_d(\sigma_{S_\bullet}) := r_d(S_\bullet).$
	Then we have that 
\begin{equation}\label{eq:mcmullen}
\Lat(P) = \sum_{F\subset P} r_{d}(\ncone(F,P)) \ \nvol(F).
\end{equation}
\end{thm}
Therefore, an equation of the form \eqref{eq:tdexpression} gives a solution to \eqref{eq:exterior} for lattice generalized permutohedra by setting $\alpha(F,P)=r_d(\ncone(F,P))$.

We are going to require one more special property for our expressions of the form \eqref{eq:tdexpression}.

\begin{defn}\label{def:sym}
The symmetric group $\fS_{d+1}$ acts on elements of $\hB_{d+1}$ hence on the generators of the ring $R_d$. Notice that this action fixes both ideals $I_1$ and $I_2$ so that $\fS_{d+1}$ acts naturally on $A_d$ too. We say an element $f\in A_d$ is \textbf{symmetric} if $\pi\cdot f=f$ for all $\pi\in \fS_{d+1}$. 

For any $f \in A_d,$ we define its \textbf{symmetrization} to be 
\begin{equation}\label{eq:sym}
f^{\sharp}:=\dfrac{1}{(d+1)!}\sum_{\pi\in \fS_{d+1}} \pi\cdot f.
\end{equation}
(It is easy to see that $f^{\sharp}$ is symmetric.)
\end{defn}





%\begin{rem}\label{rem:sym}
%	In the ring $A_d$, any square-free element is of the form $\sum_{S_\bullet\in\CC_{d+1}}c_{S_\bullet} \ x_{S_\bullet}$ where $c_{S_\bullet} \in \mathbb{Q}$, and it is symmetric if the $r(S_\bullet)$ depends only on the sequence of integers $|S_1|,|S_2|,\ldots,|S_k|$ for each each $S_\bullet=(S_1,\cdots,S_k)\in\CC_{d+1}$.
%\end{rem}

Recall that the BV-function $\bv$ is both a McMullen function and a Danilov function. In the case of the braid fan, we abuse notation again, and consider $\bv$ a function on $\CC_{d+1}$ by letting
$ \bv(S_\bullet) := \bv(\sigma_{S_\bullet}), \quad \forall S_\bullet \in \CC_{d+1}.$
Then using results from \cite{bvalpha} we prove the following. 
%(Abusing notation and we let $\bv(S_\bullet)=\bv(\sigma_{S_\bullet})$.)

\begin{thm}\label{thm:uniqueness}[Theorem 5.5 in \cite{bvalpha}] 
	There is a unique symmetric square-free expression for $\td(X_d).$ %\eqref{eq:tdexpression}. 
	It is given by the Berline--Vergne function: 
\begin{equation}\label{eq:bvexp}
\td(X_d) = \sum_{S_{\bullet}\in\CC_{d+1}} \bv(S_{\bullet}) [V(\sigma_{S_{\bullet}})].
\end{equation}
\end{thm}

We call the right hand side of \eqref{eq:bvexp} the \textbf{Berline--Vergne expression} for the Todd class of $X_d$.

Combining the theorem with the symmetrization described in \eqref{eq:sym} we get the following

\begin{prop}\label{prop:symm}
Let $f$ be any square-free expression for $\td(X_d)$ (as in \eqref{eq:tdexpression}), then its symmetrization $f^{\sharp}$ is the Berline--Vergne expression for $\td(X_d)$.
\end{prop}

\section{Spider diagrams}\label{sec:spider}
In this section we develop the necessary combinatorial language that will be used to express our main formulas in \cref{sec:gen}.

\begin{defn}
Let $T_\bullet\in\CC_{d+1}$ and $S\in T_\bullet$ (so $S$ is a subset of $[d+1]$). A \textbf{spider} $\Sp = \Sp(T_\bullet, S)$ on $T_\bullet$ with head $S$ is a graph on the vertex set $T_\bullet$ with edge set $\{S,T\}$ for every $T\in T_\bullet\backslash\{S\}$.
We call $S$ the \textbf{head} and every non head vertex a \textbf{leg}. Legs are partitioned in two subsets $L$ and $R$. The set $L$ consists of the \textbf{left legs}, i.e., of $T\in\T_\bullet$ such that $T\subset S$ and $R$ consists of the \textbf{right legs}, sets $T\in\T_\bullet$ with $S\subset T$.

The \textbf{size} of a spider is $|\Sp(T_\bullet,S)|:=|T_\bullet|$, the size of its vertex set. A spider of size one is called a \textbf{trivial} spider. It has no legs. (Note that number of edges in a spider $\Sp$ is $|\Sp|-1.$)

\end{defn}



\begin{notn}\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 $h$ an additional label $T^L_1;$ similarly, if there are not Right legs, we give the head vertex $S$ an additional label $T^R_1.$ 
\end{notn}

\begin{ex}
To save space we avoid commas, for instance $\{12\}:=\{1,2\}$.
Consider the spider with chain $T_\bullet = \{12\}\subset \{123\}\subset \{123456\}\subset \{12345678\}$ and head $S=\{12\}$. In \cref{fig:singlespider} we have labeled the spider according to \cref{notn:label}. Note that the head $S$ receives also the label of $T^L_1$.
\begin{figure}[ht]
\centering
\input{singlespider.tex}
 \caption{A spider with the head having two different labels.}
 \label{fig:singlespider}
\end{figure}
\end{ex}

\begin{defn}
Let $T_\bullet\in\CC_{d+1}$ be a chain. A \textbf{spider diagram} $D$ consist of a partition of $T_\bullet$ into $k$-disjoint intervals $T_{1,\bullet},\cdots,T_{k,\bullet}$ together with a spider $\Sp_i:=\Sp(T_{i,\bullet},S_i)$ on each interval. Notice that the set of heads form a chain $S_\bullet\in\CC_{d+1}$.
Additionally, we always adjoin two trivial spiders $\Sp_0$ and $\Sp_{k+1}$ having vertex set $\emptyset$ and $[d+1]$ respectively. 
\end{defn}


\begin{notn}\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. See \cref{fig:spiderex} for an example of this indexing system.
\end{notn}
\begin{ex}\label{ex:spiderdiagram}
In \cref{fig:spiderex} we show a spider diagram with two spiders with vertices labeled according to \cref{notn:triple}. Notice the two trivial spiders on the extremes.
\begin{figure}[ht]
%\input{spiderex.tex}
\centering
\input{spiderdiagram.tex}
 \caption{A spider diagram with two spiders.}\label{fig:spiderex}
\end{figure}
\end{ex}




%In all of our applications the ordered set $A$ will consist of chains of subsets. Let $S_\bullet\in \CC_{d+1}^k$ be a $k$-chain of subsets. %, and let $T_\bullet\in\CC_{d+1}^n$ be an $n$-chain that contains $S_\bullet$. 
%The set of all spider diagrams having $S_\bullet$ as heads is denoted $\SpD(S_\bullet)$. %For notational purposes we always extend any spider diagram in $\SpD(S_\bullet)$ to a spider diagram on $\widehat{S_\bullet}$ by adding trivial spiders $\Sp_0$ and $\Sp_{k+1}$ on $\emptyset$ and $[d+1]$ respectively, we refer to these spiders as the extremal one. See \cref{fig:labspider} for an example of this extension.
For our formulas in the next section we to define several terms coming from spider diagrams.

\begin{defn}

Let $T_\bullet\in\CC_{d+1}$ be a chain and let $D$ be a spider diagram on it. We denote the spiders $\Sp_i=(G_i,T_{i,\bullet},S_i)$ for $i=0,\cdots,k+1$, where $\Sp_0$ and $\Sp_{k+1}$ are trivial. For each $i$, let $m_i$ its size, and $L_i$ and $R_i$ be set of left and right legs respectively. 

We define the \textbf{internal weight} of a single spider $\Sp_i$ as
\begin{equation}%\label{eq:weight}
	\intwt(\Sp_i):=\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} 
and the \textbf{boundary weight} of the diagram $D$ as
\begin{equation}%\label{eq:weight}
\bdwt(D):=\prod_{i=1}^{k+1}\left(\dfrac{|T^L_{i,1}-T^R_{i-1,1}|}{|S_i-S_{i-1}|}\right).
\end{equation}
Notice that the internal weights of the extremal spiders is 1.

The \textbf{weight} of a spider diagram $D$ is defined as
\[
\wt(D):=\bdwt(D)\prod_{i=0}^{k+1} \intwt(\Sp_i).
\]
The \textbf{sign} of $D$ is defined as $\sgn(D):=(-1)^{|D|-k}$. The \textbf{Tcoefficient} of $D$ is the coefficient of the monomial $\prod x_{S_i}^{m_i}$ in the expression for $\td(X_d)$ given by expanding \eqref{eq:tddef} using \eqref{eq:tdexpansion} on each parenthesis. The \textbf{binomial} of $D$ is given by $\Bi(D):=\prod \binom{|\Sp_i|-1}{|L_i|,|R_i|}$.
\end{defn}
\begin{rem}
The extremal spiders only affect the weight. In general, when we refer to the heads of a spider diagram we ignore $\emptyset$ and $[d+1]$.
\end{rem}

\section{General formula}\label{sec:gen}

\begin{thm}\label{thm:main}
We have the following square-free expression
\begin{equation}\label{eq:mainexpansion}
\td(X_d)= \sum_{S_{\bullet}\in\CC_{d+1}} \bv(S_{\bullet}) [V(\sigma_{S_{\bullet}})].
\end{equation}
where 
\begin{equation}\label{eq:masterformula}
\bv(S_{\bullet}) = \sum_{D\in \cal{SD}(S_\bullet)} \Tdcoeff(D)\Bi(D)\sgn(D)\wt(D),
\end{equation}
where $\cal{SD}(S_\bullet)$ is the set of all spider diagrams with heads $S_\bullet$.
\end{thm}

The proof comes from directly computing using the definition of Todd class in \eqref{eq:tddef} and using the relations in $I_2$ to express arbitrary monomials as a sum of \emph{square-free} monomials. Every time we make a choice we average over all possible choices to keep symmetry which allow us to invoke \cref{thm:uniqueness}.

\begin{prop}
The number of terms in \eqref{eq:masterformula} has the following generating function
\begin{equation}\label{eq:genfct2}
\sum_{n=1}^{\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}
\end{prop}


\subsection{Formulas for Berline--Vergne function}\label{sec:bv}
To see how the \eqref{eq:masterformula} works we are going to compute some examples.
\begin{prop}[Codimension 2 cones.]
Let $(S_1,S_2)\in\CC_{d+1}$ be an arbitrary $2$-chain, then 
\begin{equation}\label{eq:codim2}
\bv(S_1,S_2) = \dfrac{1}{4}-\dfrac{1}{12}\left(\dfrac{d+1-s_2}{d+1-s_1}+\dfrac{s_1}{s_2}\right),
\end{equation}
where $s_i:=|S_i|$ for $i=1,2$.
\end{prop}
\begin{proof}
We use \cref{thm:main}. In this case all possible spider diagrams are shown in \cref{fig:2}.
\begin{figure}[ht]
\centering
\input{2formula.tex}
\caption{All spider diagrams on two vertices with the corresponding contribution to \eqref{eq:masterformula}. Extremal spiders are omitted from the figure.}\label{fig:2}
\end{figure}
\end{proof}


Formula \eqref{eq:codim2} (and a similar one for three dimesional 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 couldn't push it further than that. The next proposition shows \cref{thm:main} in action. This formula couldn't be obtained with previously known tools.


\begin{prop}
Let $(S_1,S_2,S_3,S_4)\in\CC_{d+1}$ be an arbitrary $4$-chain, then 
\begin{align*}
\bv(S_1,S_2,S_3,S_4) &= \dfrac{1}{16}-\dfrac{1}{48}\left(\dfrac{s_3-s_2}{s_3-s_1}+\dfrac{s_1}{s_2}+\dfrac{s_4-s_3}{s_4-s_2}+\dfrac{s_2-s_1}{s_3-s_1}+\dfrac{d+1-s_4}{d+1-s_3}+\dfrac{s_3-s_2}{s_4-s_2}\right)\\&+\dfrac{1}{144}\left(\dfrac{s_3-s_2}{s_3-s_1}\dfrac{d+1-s_4}{d+1-s_3}+\dfrac{s_3-s_2}{s_4-s_1}+\dfrac{s_1}{s_2}\dfrac{d+1-s_4}{d+1-s_3}+\dfrac{s_1}{s_2}\dfrac{s_3-s_2}{s_4-s_2}\right)\\&+\dfrac{1}{720}\left(\dfrac{s_3-s_2}{s_3-s_1}\dfrac{s_4-s_3}{s_4-s_1}\dfrac{d+1-s_4}{d+1-s_1}+3\dfrac{s_1}{s_2}\dfrac{s_4-s_3}{s_4-s_2}\dfrac{d+1-s_4}{d+1-s_2}\right)\\&+\dfrac{1}{720}\left(3\dfrac{s_1}{s_2}\dfrac{s_2-s_1}{s_3-s_1}\dfrac{d+1-s_4}{d+1-s_3}+\dfrac{s_1}{s_2}\dfrac{s_2-s_1}{s_4-s_2}\dfrac{s_3-s_2}{s_4-s_2}\right)
\end{align*}
where $s_i:=|S_i|$ for $i=1,\cdots,4$.
\end{prop}

\begin{proof}
We use \cref{thm:main}. \cref{fig:4} shows all possible spider diagrams in this case.
\begin{figure}[ht]
\centering
\input{4formula.tex}
\caption{All spider diagrams on four vertices with the corresponding contribution to Equation
\eqref{eq:masterformula}. Extremal spiders are omitted from the figure.}\label{fig:4} 
\end{figure}
\end{proof}

\begin{ex}\label{ex:negative}
Using \textsc{sage} we found negative values for $\alpha_d{•}$ in four dimensional cones in $\Sigma_d$. The smallest $d$ for which this happens is $d+1=25$, where $\alpha_{24}(S_1,S_2,S_3,S_4)=-19/1684800$, for any four chain with $|S_1|=10,|S_2|=12,|S_3|=13, |S_4|=15$. 
\end{ex}

\cref{ex:negative} disproves \cref{conj:refined}. Furthermore, it also enable us to prove the following theorem.

\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 the cycles.
\end{thm}

\section{Edge positivity}\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$, i.e., $\Lat(tP) = a_0+a_1t^1+a_2t^2+\cdots+a_dt^d,\quad a_i\in\mathbb{Q}.$ This is the \textbf{Ehrhart polynomial} of $P$ and will be denoted $\Lat(P,t)$. We also define $\Lat^i(P):=[t^i]\Lat(P,t)$, the coefficient of $t^i$ in the Ehrhart polynomial.

\subsection{Edge positivity}
In this section we take a different argument to show that $\bv$ values are indeed positive on codimension one cones in the braid fan and thus the main conjecture \cref{conj:main} is true for $\Lat^1$. The arguments in this section are independent of the rest of the paper. We make use of hypersimplices.
\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 3, 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}
Or equivalently the more explicit formula
\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{lem}\label{lem:computation}
For any $k\leq d$, $\Lat^1(\Delta_{k,d+1})>0$.
\end{lem}

The proof is a careful tracking of the linear coefficient in \eqref{eq:ugly}.

\begin{thm}\label{thm:linear}
\cref{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 \cref{prop:hyper} and \cref{lem:computation}.
\end{proof}

\acknowledgements{This project started in Fall 2017 when both authors were attending the program ``Geometric and Topological Combinatorics'' at the Mathematical Sciences Research Institute in Berkeley, California. We thank Jamie Pommersheim for many helpful discussions.}

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography



\end{document}
