\documentclass[finalversion]{FPSAC2020}
\articlenumber{83}
\bibliography{references}

\PassOptionsToPackage{cmyk}{xcolor}
\definecolor{mycyan}{cmyk}{1,.2,0,0} 
\definecolor{mymagenta}{cmyk}{0,1,0,0}
\definecolor{DarkOrchid}{RGB}{153,50,204}

\usepackage{color}
\usepackage{bbm}
\usepackage{datetime}
\usepackage{geometry}
\usepackage{caption}
\usepackage{tikz}
\usepackage{lscape}
\usepackage{graphicx}


\usetikzlibrary{calc}
\tikzstyle{vertex}=[circle, draw, inner sep=0pt, minimum size=6pt]
\newcommand{\vertex}{\node[vertex]}

\usepackage{pifont}
\usepackage{array,tabularx}
\usepackage{rotating}

% theorems
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}


%%%%%%%%%%%%%%%%%%%%%
\makeatletter
\newtheorem*{rep@theorem}{\rep@title} \newcommand{\newreptheorem}[2]{%
\newenvironment{rep#1}[1]{%
\def\rep@title{\bf #2 \ref{##1}}%
\begin{rep@theorem} }%
{\end{rep@theorem} } }
\makeatother
\newreptheorem{theorem}{Theorem}
\newreptheorem{conjecture}{Conjecture}
%%%%%%%%%%%%%%%%%%%%%


\newcommand{\bv}{\mathbf{v}}
\newcommand{\bu}{\mathbf{u}}
\newcommand{\bo}{\mathbf{0}}
\newcommand{\be}{\mathbf{e}}

\newcommand{\aff}{\operatorname{aff}}
\newcommand{\Ehr}{\operatorname{Ehr}}
\newcommand{\vol}{\operatorname{vol}}
\newcommand{\val}{\operatorname{val}_2}
\renewcommand{\phi}{H^*}

\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}

\newcommand{\blue}{\textcolor{blue}}
\newcommand{\red}{\textcolor{red}}
\newcommand{\green}{\textcolor{green}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\title{The equivariant Ehrhart theory of the permutahedron}

\author{
Federico Ardila\thanks{\href{mailto:federico@sfsu.edu}{federico@sfsu.edu}.
Supported by NSF grants DMS--1600609, DMS--1855610, and Simons Fellowship grant \#613384.}\addressmark{1}\addressmark{2},
Mariel Supina\thanks{\href{mailto:mariel_supina@berkeley.edu}{mariel\_supina@berkeley.edu}.
Supported by the Graduate Fellowships for STEM Diversity.}\addressmark{4}, 
\and
Andr\'es~R.~Vindas-Mel\'endez\thanks{\href{mailto:andres.vindas@uky.edu}{andres.vindas@uky.edu}.
Supported by NSF Graduate Research Fellowship DGE--1247392.}\addressmark{1}\addressmark{3}
}

\address{\addressmark{1} Department of Mathematics, San Francisco State University, CA, USA\\
\addressmark{2} Department of Mathematics, Universidad de Los Andes, Bogot\'a, Colombia\\
\addressmark{3} Department of Mathematics, University of Kentucky, Lexington, KY, USA\\
\addressmark{4} Department of Mathematics, University of California, Berkeley, CA, USA}

\received{\today}

\abstract{
Equivariant Ehrhart theory enumerates the lattice points in a polytope with respect to a group action. Answering a question of Stapledon, we describe the equivariant Ehrhart theory of the permutahedron, and we prove his Effectiveness Conjecture in this special case.
}

\keywords{Ehrhart theory, permutahedron, quasipolynomial, symmetric group, representation theory, zonotope}


\begin{document}


\maketitle




\section{Introduction}

Ehrhart theory measures a polytope $P$ by counting the lattice points in its dilations $tP$ for positive integers $t$.
Stapledon \cite{Stapledon} introduced \emph{equivariant Ehrhart theory} as a refinement of Ehrhart theory that takes into account the symmetries of the polytope $P$. 
He asked for a description of the equivariant Ehrhart theory of the permutahedron under its group of symmetries, the symmetric group. 
In this extended abstract, we completely answer Stapledon's question, computing the equivariant Ehrhart polynomials of the standard permutahedra and verifying several conjectures in this special case.

\subsection{Ehrhart theory for fixed polytopes of the permutahedron}\label{sec:quasi}

We consider the action of the symmetric group $S_n$ on the $(n-1)$-dimensional permutahedron $\Pi_n$.
For each permutation $\sigma\in S_n$, we define the \emph{fixed polytope} $\Pi_n^\sigma \subseteq \Pi_n$ to be the subset of the permutahedron $\Pi_n$ fixed by $\sigma$.
Our first main result is a combinatorial formula for the lattice point enumerator $L_{\Pi_n^\sigma}(t) := |t\Pi_n^\sigma\cap \Z^n|$:
 



\begin{theorem}\label{thm:main theorem}
Let $\sigma$ be a permutation of $[n]:=\{1,2,\ldots,n\}$ and let $\lambda=(\ell_1, \ldots, \ell_m)$ be the partition of $n$ given by the lengths of the cycles of $\sigma$. Say a set partition $\pi = \{B_1,\dots,B_k\}$ of $[m]$ is \emph{$\lambda$-compatible} if for each block $B_i$, either $\ell_j$ is odd for some $j \in B_i$, or the minimum $2$-valuation among $\{\ell_j : j \in B_i\}$ is attained at least twice. Also write
\begin{equation}\label{eq:v_pi}
v_\pi = \prod_{i=1}^k\bigg(
\gcd(\ell_j:j\in B_i)
\cdot\Big(\sum_{j\in B_i}\ell_j\Big)^{|
B_i|-2}\bigg).
\end{equation}
Then the Ehrhart quasipolynomial of the fixed polytope $\Pi_n^\sigma$ is
 \begin{equation*}
        L_{\Pi_n^\sigma}(t) = 
            \begin{cases}
                \displaystyle \quad \,\, \sum_{\pi \vDash[m]}v_\pi \cdot t^{m-|\pi|} &\text{if $t$ is even}
                \\
                \displaystyle\sum_{\substack{\pi \vDash[m]\\\lambda-\text{compatible}}}  \hspace{-.5cm} v_\pi \cdot t^{m-|\pi|} &\text{if $t$ is odd}
            \end{cases}.
    \end{equation*}
\end{theorem}




\subsection{Equivariant Ehrhart theory}\label{sec:equivEhr}

\cref{thm:main theorem} fits into the framework of equivariant Ehrhart theory, as we now explain.


Let $G$ be a finite group acting linearly on $\Z^n$ and $P\subseteq \R^n$ be a $d$-dimensional lattice polytope that is invariant under the action of $G$.
Let $M$ be the sublattice of $\Z^n$ obtained by translating the affine span of $P$ to the origin, and consider the induced representation $\rho: G \rightarrow GL(M)$.
We then obtain a family of permutation representations by looking at how $\rho$ permutes the lattice points inside the dilations of $P$.
Let $\chi_{tP}: G \rightarrow \C$ denote the permutation character associated to the action of $G$ on the lattice points in the $t^{\text{th}}$ dilate of $P$. For $g\in G$, we have
\[
\chi_{tP}(g) =   L_{P^g}(t),
\]
where $P^g$ is the polytope of points in $P$ fixed by $g$ and $L_{P^g}(t)$ is its lattice point enumerator.

The permutation characters $\chi_{tP}$ live in the ring $R(G)$ of \emph{virtual characters} of $G$, which are the integer combinations of the irreducible characters of $G$. The positive integer combinations are called \emph{effective}; they are the characters of representations of $G$.

Stapledon encoded the characters $\chi_{tP}$ in a power series $\phi[z] \in R(G)[[z]]$ given by
\begin{equation}\label{eq:phi_equation}
    \sum_{t\geq 0}\chi_{tP}(g)z^t= \frac{\phi[z](g)}{(1-z)\det(I- g \cdot z)}.
\end{equation}
We call it the \emph{equivariant $\phi$-series} because for the identity element $e\in G$, the evaluation $\phi[z](e)$ is the well-studied \emph{$h$*-polynomial} of $P$.
We say that $\phi[z] =: \sum_{i\ge0}\phi_iz^i $ is $\emph{effective}$ if each virtual character $\phi_i$ is a character.

The main open problem in equivariant Ehrhart theory is to characterize when $\phi[z]$ is effective, and Stapledon offered the following conjecture.

\begin{conjecture}[{\cite[Effectiveness Conjecture~12.1]{Stapledon}}]\label{conj:Stapledon}
Let $P$ be a lattice polytope fixed by the action of a group $G$.
The following conditions are equivalent.

\begin{enumerate}[label=(\roman*)]
	\item The toric variety of $P$ admits a $G$-invariant non-degenerate hypersurface.
	\item The equivariant $\phi$-series of $P$ is effective.
	\item The equivariant $\phi$-series of $P$ is a polynomial.
	\end{enumerate}
\end{conjecture}

Our second main result is the following.

\begin{theorem}\label{thm:phi polynomial}
Stapledon's Effectiveness Conjecture holds for the permutahedron under the action of the symmetric group.
\end{theorem}

Finally, in \cref{prop:otherconjectures} we verify three other conjectures of Stapledon in this case.


\subsection{Organization}

In \cref{sec:background} we introduce some background on Ehrhart theory and zonotopes.
In \cref{sec:Ehrhart quasipolynomial} we compute the Ehrhart quasipolynomial of the fixed polytope $\Pi_n^\sigma$, proving \cref{thm:main theorem}. 
In \cref{sec:phi} we compute the equivariant $\phi$-series $\phi[z]$ for permutahedra and we verify Stapledon's Effectiveness conjecture in this special case (\cref{thm:phi polynomial}).




\section{Preliminaries}
\label{sec:background}

\subsection{Ehrhart quasipolynomials}

Let $P$ be a convex polytope in $\R^n$.
The \emph{lattice point enumerator} of $P$ is the function $L_P:\Z_{\ge1}\to\Z_{\ge0}$ given by $L_P(t) := |tP\cap\Z^n|$.
A function $f:\Z \rightarrow \R$ is a \emph{quasipolynomial} if there exists a period $d$ and polynomials $f_0, f_1, \ldots, f_{d-1}$ such that $f(n) = f_i(n)$ whenever $n \equiv i$ (mod $d$).


\begin{theorem}[Ehrhart's Theorem \cite{Ehrhart1962}]\label{thm:ehrharts theorem rational}
If $P$ is a rational polytope, then $L_P(t)$ agrees with a quasipolynomial in $t$ of degree $\dim P$.
Its period divides the least common multiple of the denominators of the coordinates of the vertices of $P$. 
\end{theorem}

\subsection{Zonotopes}

Let $V$ be a finite set of vectors in $\R^n$.
The \emph{zonotope} generated by $V$, denoted $Z(V)$, is defined to be the Minkowski sum of the line segments connecting the origin to $\bv$ for each $\bv\in V$.
We will also adapt the same notation to refer to any translation of $Z(V)$, that is, the Minkowski sum of any collection of line segments whose direction vectors are the elements of $V$.
Zonotopes have a combinatorial decomposition that is useful when calculating volumes and counting lattice points.  
The following result is due to Shephard.

\begin{proposition}[{\cite[Theorem~54]{Shephard1974}}]
A zonotope $Z(V)$ can be subdivided into half-open parallelotopes that are in bijection with the linearly independent subsets of $V$.
\end{proposition}

A linearly independent subset $S\subseteq V$ corresponds under this bijection to the half-open parallelotope 
    $$
    \Box S :=\sum_{\bv\in S} (\bo,\bv].
    $$

\begin{theorem}[{\cite[Theorem~2.2]{Stanleyzonotope}}] \label{thm:Stanley}
Let $Z(V)$ be a lattice zonotope generated by $V$. Then
    \begin{equation}\label{eq:stanley_formula}
        L_{Z(V)}(t) = \sum_{\substack{S\subseteq V\\\text{lin. indep.}}}\vol(\Box S)\cdot t^{|S|}.
    \end{equation}
    \end{theorem}
    
    
\noindent In the statement above and throughout the paper, volumes are normalized so that any primitive lattice parallelotope has volume $1$.


\subsection{Fixed polytopes of the permutahedron}

The symmetric group $S_n$ acts on $\R^n$ by permuting coordinates of points.
The \emph{permutahedron} $\Pi_n$ is the convex hull of the $n!$ permutations of $[n]$.
 
Let $\sigma \in S_n$ be a permutation with cycles $\sigma_1, \ldots, \sigma_m$; their lengths form a partition $\lambda = (\ell_1,\dots,\ell_m)$ of $n$.
For each cycle $\sigma_k$ of $\sigma$, let $\be_{\sigma_k}=\sum_{i\in\sigma_k}\be_i$.
The \emph{fixed polytope} $\Pi_n^\sigma$ is defined to be the polytope consisting of all points in $\Pi_n$ that are fixed under the action of $\sigma$.
We will use a few results from \cite{ASV}, which we now summarize.

\begin{theorem}[{\cite[Theorem 2.12]{ASV}}]\label{thm:vol}
The fixed polytope $\Pi_n^\sigma$ has the following zonotope description:
    \begin{equation}\label{eq:fixed_polytope_zonotope_desc}
        \Pi_n^\sigma = \sum_{1\le i<j\le m}[\ell_i \be_{\sigma_j},\ell_j \be_{\sigma_i}] + \sum_{k=1}^m \frac{\ell_k+1}{2}\be_{\sigma_k}.
    \end{equation}
\end{theorem}

\begin{figure}
    \centering
    \includegraphics[scale=.42]{img/pi4-12withlattice2.pdf} 
    \caption{The fixed polytope $\Pi_4^{(12)}$ is a half-integral hexagon containing 6 lattice points.}
    \label{fig:example}
\end{figure}


\begin{corollary}\label{cor:oddparts}
The fixed polytope $\Pi_n^\sigma$ is integral or half-integral. 
It is a lattice polytope if and only if all cycles of $\sigma$ have odd length.
\end{corollary}

Equation \eqref{eq:fixed_polytope_zonotope_desc} also shows that $\Pi_n^\sigma$ is a rational translation of the zonotope $Z(V)$ where $V=\{\ell_i\be_{\sigma_j}-\ell_j\be_{\sigma_i}:1\le i<j\le m\}$.
The following result characterizes the linearly independent subsets of $V$.

\begin{lemma}[{\cite[Lemma~3.2]{ASV}}]\label{lem:lin_indep_sets}
The linearly independent subsets of $V$ are in bijection with forests with vertex set $[m]$, where the vector $\ell_i\be_{\sigma_j}-\ell_j\be_{\sigma_i}$ corresponds to the edge connecting vertices $i$ and $j$.
\end{lemma}

In light of this lemma, the fixed polytope $\Pi_n^\sigma$ gets subdivided into half-open parallelotopes $\Box_F$ of the form

    \begin{equation} \label{eq:boxF}
        \Box_F = \sum_{\{i,j\}\in E(F)} [\ell_i\be_{\sigma_j},\ell_j\be_{\sigma_i}] + \sum_{k=1}^m \frac{\ell_k+1}{2}\be_{\sigma_k} + \bv_F,  \qquad \qquad \bv_F \in \Z^n
    \end{equation}
for each forest of $F$. 

When $F$ is a tree $T$ we have that
    $\vol (\Box_T) = 
    \Big(\prod_{i=1}^m \ell_i^{\deg_T(i)-1}\Big)
    \gcd(\ell_1,\dots,\ell_m)$
by \cite[Lemma~3.3]{ASV}. 
For a general forest $F$, the parallelotopes $\Box_T$ corresponding to each connected component $T$ of $F$ live in orthogonal subspaces, so

    \begin{equation}\label{eq:volume_forest}
        \vol(\Box_F) = \Big( \prod_{j=1}^m\ell_j^{\deg_F(j)-1} \Big)\bigg( \prod_{\substack{\text{conn. comp.}\\ T\text{ of } F}} \gcd(\ell_j:j\in\mathrm{vert}(T)) \bigg).
    \end{equation}




\section{Ehrhart quasipolynomial of \texorpdfstring{$\Pi_n^\sigma$}{Pi n sigma}}
\label{sec:Ehrhart quasipolynomial}

Since $\Pi_n^\sigma$ is a zonotope, we can decompose it into half-open parallelotopes.
However, since $\Pi_n^\sigma$ is half-integral, some of the parallelotopes in this decomposition may not contain any lattice points.


\begin{figure}
    \begin{center}
       \scalebox{.7}{ \input{img/decomp2.tikz}}
    \end{center}
    \caption{Decomposition of the fixed polytope $\Pi_4^{(12)}$ into half-open parallelepipeds.}
    \label{fig:half_integral_hexagon} 
\end{figure}


\begin{example}\label{ex:quasipolynomial}
The fixed polytope $\Pi_4^{(1 2)}$ of \cref{fig:example}, which corresponds to the cycle type $\lambda = (2,1,1)$, is
$$
\Pi_4^{(12)} = [2\be_{3},\be_{12}] + [2\be_{4},\be_{12}] + [\be_{4},\be_{3}]+\frac{3}{2}\be_{12}+\be_{3}+\be_{4}.
 $$
\cref{fig:half_integral_hexagon} shows its decomposition into parallelograms indexed by the forests on vertex set $\{12, 3, 4\}$.
The three trees give parallelograms with volumes $2, 1, 1$ that contain $2,1,1$ lattice points, respectively. 
The three forests with one edge give segments of volumes $1, 1, 1$ and  $1,1,0$ lattice points, respectively. 
The empty forest gives a point of volume $1$ and $0$ lattice points. 
Hence the Ehrhart quasipolynomial of $\Pi_4^{(12)}$ is
    $$
    L_{\Pi_4^{(1 2)}}(t) = \begin{cases}
    (2+1+1)t^2+(1+1+1)t+1 &\text{if } t \text{ is even}\\
    (2+1+1)t^2+(1+1+0)t+0 &\text{if } t \text{ is odd}
    \end{cases}.
    $$
\end{example}



Following the reasoning of \cref{ex:quasipolynomial}, we will find the Ehrhart quasipolynomial of $\Pi_n^\sigma$ by examining its decomposition into half-open parallelotopes. In order to find the number of lattice points in each parallelotope $\Box_F$, the following observation is crucial.

\begin{lemma}\label{lem:num_lattice_points} \cite{ArdilaBeckMcWhirter, McWhirter}
If $\Box$ is a half-open lattice parallelotope in $\Z^n$ and $\bv \in \Q^n$, the number of lattice points in $\Box + \bv$ is
\[
|(\Box + \bv) \cap \Z^n| = 
\begin{cases}
	\vol(\Box) & \text{if the affine span of } \Box+\bv \text{ intersects the lattice } \Z^n \\
	0 & \text{otherwise}
\end{cases}.
\]
\end{lemma}

We now apply \cref{lem:num_lattice_points} to the parallelotopes $\Box_F$. Surprisingly,  whether $\aff(\Box_F)$ contains lattice points does not depend on the forest $F$, but only on the set partition $\pi$ of the vertex set $[m]$ induced by the connected components of $F$. To make this precise we need a definition.
Recall that the $2$\emph{-valuation} of a positive integer is the largest power of $2$ dividing that integer; for example, $\val(24)=3$.


\begin{definition}\label{def:compatibility}
Let $\lambda=(\ell_1,\dots,\ell_m)$ be a partition of the integer $n$.
A set partition $\pi=\{B_1,\dots,B_k\}$ of $[m]$ is called $\lambda$-\emph{compatible} if for each block $B_i\in \pi$, at least one of the following conditions holds:
    \begin{enumerate}[label=(\roman*)]
        \item $\ell_j$ is odd for some $j\in B_i$, or
        \item the minimum $2$-valuation among $\{\ell_j:j\in B_i\}$ occurs an even number of times.
    \end{enumerate}
\end{definition}


\begin{example}
Let $\lambda = (\ell_1,\ell_2,\ell_3)$ and $\val(\lambda) = (v_1,v_2,v_3)$
and assume that $v_1\geq v_2 \geq v_3$.
\cref{tab:lambda_compatibility} shows which partitions of $[3]$ are $\lambda$-compatible depending on $\val(\lambda)$.
    \begin{table}
        \begin{center}
            \input{tables/lambda_compatibility_table3.tex}
        \end{center}
        \caption{$\lambda$-compatibility for $m=3$.}
       \label{tab:lambda_compatibility}
    \end{table}
\end{example}

\begin{lemma}\label{lem:affine_subspace}
Let $\sigma\in S_n$ have cycle type $\lambda=(\ell_1,\dots,\ell_m)$. Let $F$ be a forest on $[m]$ whose connected components induce the partition $\pi=\{B_1,\dots,B_k\}$ of $[m]$.
Then $\aff(\Box_F)$ intersects the lattice $\Z^n$ if and only if $\pi$ is $\lambda$-compatible.
\end{lemma}

\begin{proof}
First we claim that 
\begin{equation} \label{eq:lambda comp}
\aff(\Box_F) = \left\{\sum_{j=1}^m x_j \be_{\sigma_j} \, : \, 
                \sum_{j\in B_i}\ell_jx_j =
                \sum_{j\in B_i} \frac{\ell_j(\ell_j+1)}{2} \textrm{ for } 1\le i\le k \right\}.
\end{equation}

This affine subspace intersects the lattice $\Z^n$ if and only if \eqref{eq:lambda comp} has integer solutions.
Elementary number theory tells us that this is the case if and only if each block $B_i$ satisfies
\begin{equation}\label{eq:div}
\gcd(\ell_j:j\in B_i) \;\Bigg|\; \sum_{j\in B_i} \frac{\ell_j(\ell_j+1)}{2}.
\end{equation}
It is always true that 
    $\gcd(\ell_j:j\in B_i)$ divides $\displaystyle \sum_{j\in B_i} \ell_j(\ell_j+1)$,
so \eqref{eq:div} holds if and only if
	\begin{equation}\label{eq:valuations}
	\val\Big(\gcd(\ell_j:j\in B_i)\Big) < \val\Big(\sum_{j\in B_i} \ell_j(\ell_j+1)\Big).
	\end{equation}
We consider two cases.

\medskip
\noindent
\emph{(i)}
Suppose $\ell_j$ is odd for some $j\in B_i$. Then $\gcd(\ell_j:j\in B_i)$ is odd, whereas $\sum_{j\in B_i}\ell_j(\ell_j+1)$ is always even.
Hence (\ref{eq:valuations}) always holds in this case.

\medskip
\noindent
\emph{(ii)} 
Suppose that $\ell_j$ is even for all $j\in B_i$.
For each $\ell_j$, write $\ell_j = 2^{p_j}q_j$ for some integer $p_j\ge 1$ and odd integer $q_j$.
Then $\val(\gcd(\ell_j:j\in B_i)) = \min_{j\in B_i}p_j$; we will call this integer $p$.
We have
    \begin{equation*}
        \val\Big(\sum_{j\in B_i}\ell_j(\ell_j+1)\Big)
	= \val\Big(\sum_{j\in B_i}2^{p_j}q_j(\ell_j+1)\Big)
	= p + \val\Big( \sum_{j\in B_i} 2^{p_j-p}q_j(\ell_j+1) \Big).
    \end{equation*}
Note that $q_j(\ell_j+1)$ is odd for each $j$.
If the minimum $2$-valuation $p$ of $\{\ell_j \,: \, j\in B_i\}$ occurs an odd number of times, then $\sum_{j\in B_i}2^{p_j-p}q_j(\ell_j+1)$ will be odd and we will have $\val(\sum_{j\in B_i}\ell_j(\ell_j+1)) = p$.
Otherwise, this sum will be even and we will have $\val(\sum_{j\in B_i}\ell_j(\ell_j+1)) > p$.
Therefore $(\ref{eq:valuations})$ holds if and only if the minimum $2$-valuation among the $\ell_j$ for $j\in B_i$ occurs an even number of times.
This is precisely the condition of $\lambda$-compatibility.
\end{proof}




We now have all of the tools to compute the Ehrhart quasipolynomial of  $\Pi_n^\sigma$. Recall the definition of $\lambda$-compatibility in \cref{def:compatibility} and the definition of $v_\pi$ in \eqref{eq:v_pi}.



\begin{reptheorem}{thm:main theorem}
%\begin{theorem}{thm:main theorem}
Let $\sigma$ be a permutation of $[n]$ with cycle type $\lambda = (\ell_1, \ldots, \ell_m)$. 
Then the Ehrhart quasipolynomial of the fixed polytope $\Pi_n^\sigma$ is
 \begin{equation*}
        L_{\Pi_n^\sigma}(t) = 
            \begin{cases}
                \displaystyle \quad \,\, \sum_{\pi \vDash[m]}v_\pi \cdot t^{m-|\pi|} &\text{if $t$ is even}
                \\
                \displaystyle\sum_{\substack{\pi \vDash[m]\\\lambda-\text{compatible}}} \hspace{-.5cm} v_\pi \cdot t^{m-|\pi|} &\text{if $t$ is odd}.
            \end{cases}
    \end{equation*}
\end{reptheorem}
%\end{theorem}

\begin{proof}
We calculate the number of lattice points in each integer dilate $t\Pi_n^\sigma$ by decomposing it into half-open parallelotopes and adding up the number of lattice points inside of each parallelotope.

First, suppose that $t$ is even.
Then $t\Pi_n^\sigma$ is a lattice polytope, all parallelotopes in the decomposition of $t\Pi_n^\sigma$ have vertices on the integer lattice, and each $i$-dimensional parallelotope $\Box$ contains $\vol(\Box)t^i$ lattice points \cite[Lemma 9.2]{BeckRobins}.
The parallelotopes correspond to linearly independent subsets of the vector configuration $\{\ell_i\be_{\sigma_j}-\ell_j\be_{\sigma_i}:1\le i<j\le m\}$, which are in bijection with forests on $[m]$.
It follows from \cref{thm:Stanley} and \eqref{eq:volume_forest} that when $t$ is even,
    \[L_{\Pi_n^\sigma}(t) = \sum_{\pi\vDash[m]}v_\pi \cdot t^{m-|\pi|}.\]

Next, suppose $t$ is odd.
Then $t\Pi_n^\sigma$ is half-integral, but it may not be a lattice polytope.
As before, we may decompose $t\Pi_n^\sigma$ into half-open parallelotopes that are in bijection with forests on $[m]$.
\cref{lem:num_lattice_points}, \cref{lem:affine_subspace}, and \cite[Lemma 9.2]{BeckRobins} tell us that $\Box_F$ contains $\vol(\Box_F)t^{m-|\pi|}$ lattice points if the set partition $\pi$ induced by $F$ is $\lambda$-compatible, and $0$ otherwise. Therefore if $t$ is odd,
    $$
    L_{\Pi_n^\sigma}(t) = \sum_{\substack{\pi\vDash[m]\\\lambda-\text{compatible}}} v_\pi\cdot t^{m-|\pi|}
    $$
as desired.
\end{proof}




\section{The equivariant \texorpdfstring{$\phi$}{H*}-series of the permutahedron}
\label{sec:phi}

We now compute the equivariant $\phi$-series of the permutahedron and characterize when it is polynomial and when it is effective, proving Stapledon's Effectiveness \cref{conj:Stapledon} in this special case.


The \emph{Ehrhart series} of a rational polytope $P$ is
    $$
    \Ehr_P(z) = 1+ \sum_{t=1}^\infty L_P(t)\cdot z^t.
    $$
In computing the Ehrhart series of $\Pi_n^\sigma$, Eulerian polynomials naturally arise.
The \emph{Eulerian polynomial} $A_k(z)$ is defined by the identity 
$$    \sum_{t\geq 0}t^kz^t = \dfrac{A_k(z)}{(1-z)^{k+1}}.
$$

\begin{proposition}\label{prop:Ehrhart_series}
Let $\sigma\in S_n$ have cycle type $\lambda=(\ell_1,\dots,\ell_m)$. 
The Ehrhart series of $\Pi_n^\sigma$ is
    \begin{equation*}
        \Ehr_{\Pi_n^\sigma}(z) = \sum_{\substack{\pi\vDash[m]\\\lambda\text{-compatible}}}\frac{v_\pi\cdot A_{m-|\pi|}(z)}{(1-z)^{m-|\pi|+1}}
        +
        \sum_{\substack{\pi\vDash[m] \\ \lambda\text{-incompatible}}} \frac{v_\pi\cdot 2^{m-|\pi|}\cdot A_{m-|\pi|}(z^2)}{(1-z^2)^{m-|\pi|+1}}
    \end{equation*}
and the $\phi$-series of the permutahedron equals
    %\begin{equation*}
        $\phi[z](\sigma) = (\prod_{i=1}^m(1-z^{\ell_i}))\cdot\Ehr_{\Pi_n^\sigma}(z)$.
    %\end{equation*}
\end{proposition}
\begin{proof}
Omitted.
\end{proof}


    \begin{table}
    \resizebox{\textwidth}{!}{
    \input{tables/tableS4.tex}
    }
    \caption{The equivariant $\phi$-series of $\Pi_4$}
    \label{tab:n=4}
    \end{table}

\cref{tab:n=4} shows the equivariant $\phi$-series of $\Pi_4$.    
Stapledon writes that \emph{``The main open problem is to characterize when $\phi[z]$ is effective''}, and he conjectures the following characterization:

\begin{repconjecture}{conj:Stapledon}[{\cite[Effectiveness Conjecture~12.1]{Stapledon}}]
Let $P$ be a lattice polytope fixed by the action of a group $G$.
The following conditions are equivalent.
	\begin{enumerate}[label=(\roman*)]
	\item\label{item:toric} The toric variety of $P$ admits a $G$-invariant non-degenerate hypersurface.
	\item\label{item:effective} The equivariant $\phi$-series of $P$ is effective.
	\item\label{item:poly} The equivariant $\phi$-series of $P$ is a polynomial.
	\end{enumerate}
\end{repconjecture}

He shows that \ref{item:toric} $\implies$ \ref{item:effective} $\implies$ \ref{item:poly}, so only the reverse implications are conjectured. Our next goal is to verify Stapledon's conjecture for the action of $S_n$ on the permutahedron $\Pi_n$.

    




\subsection{Polynomiality of \texorpdfstring{$\phi[z]$}{H*[z]}}


\begin{lemma}\label{lem:phi[z](sigma) polynomial}
Let $\sigma\in S_n$ have cycle type $\lambda= (\ell_1,\dots,\ell_m)$.
The equivariant $\phi$-series evaluated at $\sigma$, $\phi[z](\sigma)$,  is a polynomial if and only if the number of even parts in $\lambda$ is $0$, $m-1$, or $m$.
\end{lemma}
\begin{proof}
Omitted.
\end{proof}

\begin{proposition} \label{prop:poly}
The equivariant $\phi$-series of  the permutahedron $\Pi_n$ is a polynomial if and only if $n\le 3$.
\end{proposition}

\begin{proof}
When $n\le 3$, all partitions of $n$ have $0$, $1$, or all odd parts.
Hence $\phi[z](\sigma)$ is a polynomial for all $\sigma\in S_n$, so $\phi[z]$ is a polynomial.

Suppose $n\ge4$.
Then there always exists some partition of $n$ with more than $1$ but fewer than all odd parts: if $n$ is even we can take the partition $(n-2,1,1)$, and if $n$ is odd we can take the partition $(n-3,1,1,1)$.
Therefore $\phi[z]$ is not polynomial.
\end{proof}



\subsection{Effectiveness of \texorpdfstring{$\phi[z]$}{H*[z]}}

\begin{proposition} \label{prop:eff}
The equivariant $\phi$-series of  the permutahedron $\Pi_n$ is effective if and only if $n\le 3$.
\end{proposition}

\begin{proof}
We prove this by computing the decomposition of the $H^*$ characters into irreducibles.
\end{proof}




\subsection{\texorpdfstring{$S_n$}{Sn}-invariant non-degenerate hypersurfaces in the permutahedral variety}


We begin by explaining condition \ref{item:toric} of \cref{conj:Stapledon}, which arises from Khovanskii's notion of non-degeneracy \cite{Khovanskii}. We refer the reader to \cite[Section 7]{Stapledon} for more details.

Let $P \subset \R^n$ be a lattice polytope that is invariant under the action of a finite group $G$.
For $\bv\in \Z^n$ we write $x^\bv:=x_1^{v_1}\cdot\ldots\cdot x_n^{v_n}$.
The coordinate ring of the projective toric variety $X_P$  of $P$ has the form $\C[x^\bv:\bv\in P\cap \Z^n]$, so a hypersurface in $X_P$ is given by a linear equation $\sum_{\bv\in P\cap \Z^n}a_\bv x^\bv=0$ for some complex coefficients $a_\bv$.
The group $G$ acts on the monomials $x^\bv$ by its action on the lattice points $\bv\in P\cap \Z^n$, so the equation of a $G$-invariant hypersurface should have $a_\bv = a_\bu$ whenever $\bu$ and $\bv$ are in the same $G$-orbit.
A projective hypersurface in $X_P$ with equation $f(x_1,\dots,x_n)=0$ is \emph{smooth} if the gradient $(\partial f/\partial x_1,\dots,\partial f/\partial x_n)$ is never zero when $(x_1,\dots,x_n)\in(\C^*)^n$.
There is a unique polynomial in the $a_\bv$s, called the \emph{discriminant}, such that  the hypersurface is smooth when the discriminant does not vanish at the coefficients $a_\bv$.
A hypersurface in the toric variety of $P$ is \emph{non-degenerate} if it is smooth and for each face $F$ of $P$, the hypersurface $\sum_{\bv\in F\cap \Z^n}a_\bv x^\bv=0$ is also smooth.


The \emph{permutahedral variety} $X_{\Pi_n}$ is the projective toric variety associated to the permutahedron $\Pi_n$.

\begin{proposition}\label{prop:smooth}
The permutahedral variety $X_{\Pi_n}$ admits an $S_n$-invariant non-degenerate hypersurface if and only if $n \leq 3$.
\end{proposition}
\begin{proof}
We prove this by checking gradients when $n=1,2$.
For $n=3$, we compute a discriminant using a formula from \cite{discriminant}.
\end{proof}



\subsection{Stapledon's Effectiveness Conjecture}

\cref{thm:phi polynomial} now follows as a corollary.

\begin{reptheorem}{thm:phi polynomial}
%\begin{theorem}{thm:phi polynomial}
Stapledon's Effectiveness Conjecture holds for the permutahedron under the action of the symmetric group.
\end{reptheorem}
%\end{theorem}

\begin{proof}
This follows immediately from \cref{prop:poly,prop:eff,prop:smooth}
\end{proof}

\subsection{Other conjectures}
 
 

\begin{conjecture}[{\cite[Conjecture~12.2]{Stapledon}}]\label{conj:12.2}
If $\phi[z]$ is effective, then $\phi[1]$ is a permutation representation.
\end{conjecture}

\begin{conjecture}[{\cite[Conjecture~12.3]{Stapledon}}]\label{conj:12.3}
For any $g\in G$, the quantity $\phi[1](g)$ is a non-negative integer.
\end{conjecture}

\begin{conjecture}[{\cite[Conjecture~12.4]{Stapledon}}]\label{conj:12.4}
If $\phi[z]$ is a polynomial and the $i^{\text{th}}$ coefficient of the $h^*$-polynomial of $P$ is positive, then the trivial representation occurs with non-zero multiplicity in the virtual character $\phi_i$.
\end{conjecture}

\begin{proposition}\label{prop:otherconjectures}
\cref{conj:12.2,conj:12.3,conj:12.4} hold for permutahedra under the action of the symmetric group.
\end{proposition}
\begin{proof}
Omitted.
\end{proof}




\acknowledgments{
We would like to thank Sophia Elia for developing a useful Sage package for equivariant Ehrhart theory, and Matthias Beck, Benjamin Braun, Christopher Borger, Ana Botero, Sophia Elia, Donghyun Kim, Jodi McWhirter, Dusty Ross, Kristin Shaw, and Anna Schindler for fruitful conversations. 
This work was completed while FA was a Spring 2019 Visiting Professor at the Simons Institute for Theoretical Computer Science in Berkeley, and a 2019-2020 Simons Fellow while on sabbatical in Bogot\'a from San Francisco State University; he is very grateful to the Simons Foundation, SFSU, and the Universidad de Los Andes  for their support.}



\printbibliography

\end{document}



