%% 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]{FPSAC2023}
\articlenumber{17}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}

\usepackage{graphicx}
\usepackage{latexsym,amsfonts}
   \usepackage{amsfonts}
\usepackage{mathrsfs}
\usepackage{epsf,psfrag,eepic,epic}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{colordvi}

\usepackage{array}
\usepackage{multirow}

%\parskip 12pt
%\setlength{\evensidemargin}{0.3in}
%\setlength{\oddsidemargin}{0.3in}
%\setlength{\textwidth}{15.7cm}
%\setlength{\textheight}{22cm}

\def\supp{\operatorname{supp}}
\def\g{\hbox{\germ g}}
\def\negra#1{\bf {#1}}
\def\conjunto#1{{\negra [}\,#1\,{\negra ]}}
\def\vector#1#2{({#1}_1,\dots, {#1}_{#2})}
\def\dominada{\unlhd}
\def\dominadaest{\lhd}
\def\flecha{\longrightarrow}
\def\implica{\Longrightarrow}
\def\siysolosi{\Longleftrightarrow}
\def\matriz{{\sf M}(\lambda,\mu)}
\def\matrizr{{\sf T}(\lambda,\mu)}
\def\permuta#1{{\sf P}({#1})}
\def\politopo#1{{\sf Q}({#1})}
\def\parti#1{\pi(#1)}
\def\fia#1{\Phi_A({#1})}

\newtheorem{theorem}{Theorem}[section] 
\newtheorem{thm}[theorem]{theorem}
\newtheorem{metathm}[theorem]{Target Theorem}
\newtheorem{mainthm}[theorem]{Main Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{cor}[theorem]{Corollary}
%\newtheorem{example}[theorem]{Example}
%\newtheorem{definition}[theorem]{Definition}
\newtheorem{exm}[theorem]{Example}
%\newtheorem{rem}[theorem]{Remark}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{pbm}[theorem]{Question}

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

\newcommand{\R}{\mathbb R}
\newcommand{\T}{{\cal T}}
\newcommand{\e}{\epsilon}
\newcommand{\w}{\omega}
\newcommand{\dif}{\mathrm{d}}
\newcommand{\nat}{\mathbb N}
\newcommand{\real}{\mathbb R}
\newcommand{\p}{{\frak P}}
\newcommand{\CH}{\cal H}
%\newcommand{\sg}{\rm sg}
\newcommand{\LOG}{\mathrm LOG}
\newcommand{\ld}{\lambda}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\gen}[1]{\langle #1 \rangle_{\F_2}}
\newcommand{\FC}{{\overline{\mathbb{F}}}}
\newcommand{\KC}{{\overline{\mathbb{K}}}}
\newcommand{\K}{\mathbb{K}}
\newcommand{\KS}{\K^\infty}
\newcommand{\KD}{\KC^*}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\G}{\mathcal{G}}
\newcommand{\W}{\mathcal{W}}
\newcommand{\x}{{\bf x}}
\newcommand{\RD}{{\K[[x]]}}
\newcommand{\RP}{{\K[x]}}
\newcommand{\codim}[2]{dim(#1/#2)}
\newcommand{\Var}[2]{{\mathcal{V}_{#1}(#2)}}
\newcommand{\genR}[1]{\mathbf{ideal}(#1)}
\newcommand{\genK}[1]{\mathbf{span}(#1)}
\newcommand{\weightsum}[3]{ L_{#1}(#2,#3)}

\DeclareMathOperator{\sg}{ sg}
\DeclareMathOperator{\cone}{cone}
\DeclareMathOperator{\sat}{sat}
\DeclareMathOperator{\monoid}{semi-group}
\DeclareMathOperator{\lattice}{lattice}
\DeclareMathOperator{\conv}{conv}
\DeclareMathOperator{\inter}{int}

\newcommand{\nathan}[1]{{ \sf $\spadesuit\spadesuit\spadesuit$ Nathan: [#1]}}


\def\jdlqed{\vbox{\hrule \hbox{\vrule\hbox to
5pt{\vbox to 6pt{\vfil}\hfil}\vrule}\hrule}}


%% define your title in the usual way
\title{Sums of Weighted Lattice Points of Polytopes}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author[De Loera, Escobar, Kaplan, Wang]{Jes\'us A.\ De Loera\thanks{\href{mailto:deloera@math.ucdavis.edu}{deloera@math.ucdavis.edu}. Supported by NSF Grant DMS-1818969.}\addressmark{1}, Laura Escobar\thanks{\href{mailto:laurae@wustl.edu}{laurae@wustl.edu}. Supported by NSF Grant DMS-1855598 and NSF CAREER Grant DMS-2142656.}\addressmark{2},  \\ Nathan Kaplan\thanks{\href{mailto:nckaplan@math.uci.edu}{nckaplan@math.uci.edu}. Supported by NSF Grants DMS-1802281 and DMS-2154223.}\addressmark{3}, \and Chengyang Wang\thanks{\href{mailto:cyywang@ucdavis.edu}{cyywang@ucdavis.edu}. Supported by NSF Grant DMS-1818969.}\addressmark{1}
}

%\thanks{\href{mailto:hello@world.c}{hello@world.c}. Longer names me was partially supported by Grant 2017.11.14.$\partial$\;supp.

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, University of California, Davis \\ \addressmark{2}Department of Mathematics and Statistics, Washington University in St.\ Louis\\ \addressmark{3}Department of Mathematics, University of California, Irvine
}

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

%% 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{We study the problem of counting lattice points of a polytope that are weighted by an Ehrhart quasi-polynomial of a family of parametric polytopes. As applications one can compute integrals and maximum values of such quasi-polynomials. We not only recover some known identities in representation theory and semigroup theory but obtain new ones.}

%% put your French abstract here, or comment this out if you don't have one
%\resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{%lattice points in polyhedra,
quasi-polynomials, Ehrhart functions, combinatorial identities, polyhedra.}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations; i.e., [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex]{biblatex}
\addbibresource{sample.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}
\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

\section{Introduction}

We are given a rational convex polytope $P$ in $\R^n$ and $w(x)$ a quasi-polynomial function in $n$ variables. We call $w$ a  \emph{weight function} (the precise definition of the quasi-polynomials we use here is below, but for now you can think of $w$ as a polynomial). A computational problem arising throughout the mathematical sciences is to compute, or at least estimate,  
%the sum of values of $w(x)$ over the integral points belonging to the dilation $tP$, namely

\begin{equation} \label{thesummation}
\weightsum{P}{w}{t}=\sum_ {x\in tP \cap \Z^n}w(x).
\end{equation}



Note that, for a fixed $w$ as the polytope $P$ 
%\nathan{we are switching back and forth between `polytope' and polyhedron'.  Maybe `polytope' is better for $P$?} 
is dilated by an integer factor $t\in \N$  we obtain a function of $t$, which we call the \emph{weighted Ehrhart quasi-polynomial} for the pair $(P,w)$. The name is natural
as when $w(x)=1$ then $\weightsum{P}{1}{t}$ yields the  classical \emph{Ehrhart quasi-polynomial}.
%We remark that when $w=1$, $L_P(w,t)$ is the classical \emph{Ehrhart counting function}.
We recommend  Chapter 4 of \cite{Stanley1997Enumerative-Com} or  \cite{beckrobins} and the references there for excellent introductions to Ehrhart functions and Ehrhart quasi-polynomials.

One can prove $\weightsum{P}{w}{t}$ is a quasi-polynomial in the sense that it is a function in the variable $t$ which is a sum of monomials up to degree $d+M$, where $M=\deg w$, but  whose coefficients $E_m $ are periodic functions of $n\in \N$:
$$
\weightsum{P}{w}{t}= \sum_{m=0}^{d+M} E_m t ^m.
$$
The evaluation of Equation \eqref{thesummation} at the dilation $tP$ of $P$ is obviously what we need in order to understand this Ehrhart quasi-polynomial. The leading coefficient of $\weightsum{P}{w}{t}$ is given by the integral of $w$ over the polytope $P$. 
These integrals were studied in \cite{Barvinok-1991}, \cite{Barvinok-1992} and 
more recently in \cite{BBDKV08}. 
%\nathan{This is ok when $w(x)$ is a polynomial, but when it is a periodic function of the integers, what does it mean to integrate?} 


We will illustrate soon many important examples of such weighted Ehrhart problems. For now note they appear in enumerative combinatorics \cite{andrewspaulereise}, algebraic combinatorics \cite{FedericoErwan, chapotonqanalogues}, statistics \cite{DG, Chenetalstats},  and in symbolic integration and optimization \cite{BBDKV08,deloera-hemmecke-koeppe-weismantel:intpoly-fixeddim}, among others. 

\subsection*{Our Contributions:} 
We now outline the main contributions whose details will appear in the forthcoming full version.
The main theorem 
is a surprisingly simple way to evaluate the function $\weightsum{P}{w}{t}$ where $P$ is a rational polytope and $w(x)$ is a very general weight function. The key idea is that we build a new polytope, the \emph{weight lifting polytope} $P^*$, for which these functions become simply $\weightsum{P^*}{1}{t}$, in other words, just a ``standard'' lattice point counting function. This way (often) the weighted Ehrhart polynomial $P$ is equivalent to the (usual) Ehrhart polynomial of $P^*$. Clearly, $P^*$ will depend on both $P$ and $w$:

\begin{theorem}[The existence of weight lifting polytopes] \label{polytopelifting} \quad
Let $P$ be a rational convex polytope in the form $\{\mathbf{x}\mid \mathbf{Ax} = \mathbf{b}, \mathbf{x}\geq 0\}$, where $\mathbf{A} \in \Z^{s \times n}, \mathbf{b} \in \Z^{s}$.
Let $Q(x_{1},\ldots,x_{n})$ be the parametric family of rational convex polytopes parameterized by $x_{1},\ldots,x_{n}$, given by
$$Q(x_{1},\ldots,x_{n}) = \left\{ \mathbf{y} \mid \mathbf{Cy} = \sum_{i=1}^{n}x_{i}\mathbf{d_{i}} + \mathbf{e}, \mathbf{y} \geq \mathbf{0} \right\},$$
where $\mathbf{C} \in \Z^{r \times m}, \mathbf{d_{i}},\mathbf{e} \in \Z^{r}$. Using $Q$ define $w(\mathbf{x})$ to be the multivariate Ehrhart quasi-polynomial function in $n$ variables that counts the number of lattice points in the parametric polytope $Q(x_{1},\ldots,x_{n})$ when $x_{i}$ are chosen integers, i.e., 
$$w(x_{1},\ldots,x_{n}) = |Q(x_{1},\ldots,x_{n}) \cap \mathbb{Z}^{m}|.$$
%Hence %(1)
\begin{enumerate}
\item There is a \emph{weight lifting polytope} $P^*\subset \mathbb{R}^{n+m}$ defined by
$$P^{*} = \left\{ \left. \begin{pmatrix} \mathbf{x} \\ \mathbf{y} \end{pmatrix} \right|   \mathbf{A}^{*}\begin{pmatrix} \mathbf{x} \\ \mathbf{y} \end{pmatrix} = \begin{pmatrix} \mathbf{b} \\ -\mathbf{e} \end{pmatrix} ,\mathbf{x} \geq \mathbf{0}, \mathbf{y} \geq \mathbf{0} \right\}$$
where
$$\mathbf{A}^{*} = \begin{bmatrix} \mathbf{A} & \mathbf{0}  \\ \begin{matrix} \mathbf{d_{1}} & \mathbf{d_{2}} & \cdots & \mathbf{d_{n}} \end{matrix} & -\mathbf{C}  \end{bmatrix},
$$
for which the summation of the lattice points of $P$ weighted by $w$ equals the number of lattice points of $P^*$.

%the weighted summation using $w$ of the lattice points of $P$ equals counting the lattice points of the weight lifting polytope 
%$$P^{*} = \left\{ \left. \begin{pmatrix} \mathbf{x} \\ \mathbf{y} \end{pmatrix} \right|   \mathbf{A}^{*}\begin{pmatrix} \mathbf{x} \\ \mathbf{y} \end{pmatrix} = \begin{pmatrix} \mathbf{b} \\ -\mathbf{e} \end{pmatrix} ,\mathbf{x} \geq \mathbf{0}, \mathbf{y} \geq \mathbf{0} \right\}$$
%$$\mathbf{A}^{*} = \begin{bmatrix} \mathbf{A} & \mathbf{0}  \\ \begin{matrix} \mathbf{d_{1}} & \mathbf{d_{2}} & \cdots & \mathbf{d_{n}} \end{matrix} & -\mathbf{C}  \end{bmatrix}.
%$$

%(2) 
\item Moreover, when $\mathbf{e} = 0$, the construction is parametric in the sense that  the weight $w$ is a homogeneous function, $(tP)^{*} = t(P^{*})$, and 
%the resulting weighted Ehrhart quasi-polynomial $\weightsum{P}{w}{t}$ equals the usual Ehrhart polynomial of $P^*$, namely $\weightsum{P^*}{1}{t}$ 
$$\weightsum{P}{w}{t} = |(tP)^{*}\cap\mathbb{Z}^{n+m}| = |t(P^{*})\cap\mathbb{Z}^{n+m}| = \weightsum{P^*}{1}{t}.$$
\end{enumerate}
\end{theorem}

\begin{rem}
To the best of our knowledge the first version of \cref{polytopelifting} appeared in print in work by Ardila and Brugall\'e (see \cite[Section 4]{FedericoErwan}), but in \cite{FedericoErwan} the weights $w(x)$ were special polynomials and in that case some of the consequences we show were not possible.
In \cref{pruebas}, we present a direct constructive/algorithmic proof of \cref{polytopelifting} and describe several interesting special cases depending on the type of Ehrhart quasi-polynomials (in particular, we recover the results of \cite{FedericoErwan}). 
\end{rem}

\begin{rem}
The second half of \cref{polytopelifting} uses special weights that are by construction non-negative. But we note that most of the proof of the theorem works even when $w(x)$ takes negative or zero values over $P$. The function $\weightsum{P}{w}{t}$ still makes sense, but what we obtain is not a traditional Ehrhart polynomial, because, for example, the leading coefficient could be negative, and volumes are never negative.
\end{rem}

\begin{rem}
 \cref{polytopelifting} says the weight $w(x)$ can be any Ehrhart quasi-polynomial. In \cref{pruebas}, we carefully discuss many ways to express polynomials in terms of these quasi-polynomial weights. A key point of our paper is that \cref{polytopelifting} is more versatile and expressive because it applies to more functions than just polynomial weights. In fact, \cref{pruebas} shows $w$ can have many different representations (e.g., polynomials), some more efficient than others. To demonstrate the power in \cref{applications} we present applications to Combinatorial Representation Theory and Number Theory. 
\end{rem}

\cref{integrate-maximize}  below is a notable new consequence of \cref{polytopelifting} that can be applied to many problems of interest. For example, these ideas can be applied to integration and maximization of Kostka numbers, Littlewood--Richardson coefficients, and any other combinatorial invariant that is given by an Ehrhart quasi-polynomial. 

\begin{cor} \label{integrate-maximize} Let $w$ be weight obtained from an Ehrhart quasi-polynomial function of a parametric polyhedron $Q$, 
whose parameters are defined over the lattice points of a polytope $P$. Here $P,Q,w$ are just as in \cref{polytopelifting}.
%\nathan{Why have we switched from using $w$ to using $Q$?} 
Using the weight lifting polytope construction of \cref{polytopelifting} one can integrate and maximize $w$ over $P$ as follows:

\begin{itemize}
\item One can compute the integral $\int_P w(x) dx$ reformulated as a volume computation of the weight lifting polytope $P^*$.

\item One can solve the maximization problem and determine $max_{\alpha \in P \cap \Z^n} w(\alpha)$. It reduces to counting the lattice points of a finite sequence of weight lifting polytopes which contain each other and can be read from $P^*$ efficiently. 
\end{itemize}
\end{cor}

We sketch the proof of \cref{integrate-maximize} in \cref{pruebas}. In the forthcoming full version we will include computational experiments with LattE \cite{latte-1.2}.

% I THINK IT IS BEST TO COMMENT THIS OUT, IT IS RIGHT NOW A LOOSE END
%Our second main theorem is a generalization a famous classical identity from 
%Ehrhart theory. It is a well-known in traditional Ehrhart theory (weight $w=1$) that there is a theory of reciprocity, where there is an identity relating the number of lattice points of the interior of the polytope to the number of lattice points of the closed polytope.
%counting the lattice points of the interior of the polyhedron are related by an identity counting the points of the closed polytope. 
%Our main result generalizes Theorem 4.6 in Section 4 of \cite{FedericoErwan}.%, 
%we show

%\begin{theorem}[Weighted Ehrhart Reciprocity]\label{Ehrhart}
%Let $P$ be a rational polytope in $\mathbb{R}^{n}$ and $P^{\circ}$ be the relative interior, and let $w: \mathbb{R}^{n} \to \mathbb{R}$ be a function in the form $ \prod_{i=1}^{n}\sum_{j=1}^{m_{i}}P_{ij}(u_{i})\gamma_{ij}^{u_{i}}$ with $P_{ij}$'s are polynomials and $\gamma_{ij}$ are nonzero complex numbers. The functions in $t \in \mathbb{N}$
%$$\weightsum{P}{w}{t} := \sum_{u \in tP\cap \mathbb{Z}^{n}}w(u), \quad  \weightsum{-P^{\circ}}{w}{t}  := \sum_{u \in -tP^{\circ}\cap \mathbb{Z}^{n}}w(u),$$
%extend to quasi-polynomial functions on $\mathbb{R}$ that satisfy 
%$$ \weightsum{-P^{\circ}}{w}{t} = (-1)^{\dim{P}}\weightsum{P}{w}{-t}.$$
%\end{theorem}

%We omit the proof of \cref{Ehrhart}, but it will appear in the full version of the paper.

\section{Proofs of \cref{polytopelifting} and sketch of other results} \label{pruebas}

Here we present proofs of \cref{polytopelifting} and some variations of it.
%and variations of \cref{polytopelifting}:

\begin{proof}[Proof of \cref{polytopelifting}]
Note that there is a natural projection map $  \pi: P^{*} \to P $ via $  (\mathbf{x}, \mathbf{y} ) \mapsto \mathbf{x}$. 
It suffices to show that for any fixed $\mathbf{x} \in P\cap \Z^{n}$, $w(\mathbf{x}) = |\pi^{-1}(\mathbf{x}) \cap \Z^{n+m}|.$
Recall that $(\mathbf{x}, \mathbf{y} ) \in \pi^{-1}(\mathbf{x})  $ if and only if $\mathbf{A}\mathbf{x} = \mathbf{b}$ and $\mathbf{Cy} = \sum_{i=1}^{n}x_{i}\mathbf{b_{i}} + \mathbf{e}$ where $\mathbf{x}\geq \mathbf{0},\mathbf{ y} \geq \mathbf{0}$. Given $\mathbf{x} \in P \cap \Z^{n}$, we see that  $(\mathbf{x},\mathbf{y} ) \in \pi^{-1}(\mathbf{x}) \cap \Z^{n+m} $ if and only if $ \mathbf{y} \in  Q(x_{1},\ldots,x_{n}) \cap \Z^{m}$. Hence, for a fixed $\mathbf{x} \in P \cap \Z^{n}$,
    $ |\pi^{-1}(\mathbf{x}) \cap \Z^{n+m}|
    =  | Q(\mathbf{x}) \cap \Z^{m}|
    = w(\mathbf{x}).$ 
    %\nathan{I don't think we have actually defined $n^*$ anywhere.  Since we can express it easily in terms of $n$ and $w(x)$, I think we should avoid this notation if possible.}
    
%Next note that \cref{polytopelifting} implies that the weight lifting polytope $P^{*}$ is parametric with respect to the right-hand side $\mathbf{b}$.
We now consider second part of \cref{polytopelifting}.  We show that $P^{*}$ is parametric with respect to $\mathbf{b}$ in the following sense. 
If $P = \{ \mathbf{x} : \mathbf{Ax} = \mathbf{b}, \mathbf{x} \geq \mathbf{0} \}$, then
$$P^{*} = \left\{ \left. \begin{pmatrix} \mathbf{x} \\ \mathbf{y} \end{pmatrix} \right|   \mathbf{A}^{*}\begin{pmatrix} \mathbf{x} \\ \mathbf{y} \end{pmatrix} = \begin{pmatrix} \mathbf{b} \\ -\mathbf{e} \end{pmatrix} ,\mathbf{x} \geq \mathbf{0}, \mathbf{y} \geq \mathbf{0} \right\}.$$
Therefore, $tP = \{ \mathbf{x} : \mathbf{Ax} = t\mathbf{b}, \mathbf{x} \geq \mathbf{0} \}$ and
$$(tP)^{*} = \left\{ \left. \begin{pmatrix} \mathbf{x} \\ \mathbf{y} \end{pmatrix} \right|   \mathbf{A}^{*}\begin{pmatrix} \mathbf{x} \\ \mathbf{y} \end{pmatrix} = \begin{pmatrix} t\mathbf{b} \\ -\mathbf{e} \end{pmatrix} ,\mathbf{x} \geq \mathbf{0}, \mathbf{y} \geq \mathbf{0} \right\}.$$
Given $\mathbf{e} = 0$, we can see that $(tP)^{*} =t(P^{*}).$
%$$(tP)^{*} = \left\{ \left. \begin{pmatrix} \mathbf{x} \\ \mathbf{y} \end{pmatrix} \right|   \mathbf{A}^{*}\begin{pmatrix} \mathbf{x} \\ \mathbf{y} \end{pmatrix} = t\begin{pmatrix} \mathbf{b} \\ \mathbf{0} \end{pmatrix} ,\mathbf{x} \geq \mathbf{0}, \mathbf{y} \geq \mathbf{0} \right\} = t(P^{*}).$$
By the first part of the proof we conclude
\begin{equation*}
    \weightsum{P}{w}{t} = |(tP)^{*}\cap\mathbb{Z}^{n+m}| = |t(P^{*})\cap\mathbb{Z}^{n+m}| = \weightsum{P^*}{1}{t}. \qedhere
\end{equation*}
\end{proof}

Now we outline more results and corollaries of \cref{polytopelifting}. From now on we deal with the most general \emph{quasi-polynomial weighted} case, i.e., $w(x)$ is a non-constant quasi-polynomial as in the statement of \cref{polytopelifting}.

%Form the Stanley's Enumerative Combinatorics:
%\begin{proposition}[Equivalent Characterizations of quasi-polynomials]\label{quasichara}
%The following conditions on a function $f:  \N \to \C$ and integer $N > 0$ are equivalent.
%\begin{enumerate}
%\item $f$ is a quasi-polynomial of quasiperiod $N$.
%\item $\sum_{n \geq 0} f(n)x^{n} = \frac{P(x)}{Q(x)}$, where $P(x), Q(x) \in \C[x]$, every zero $\alpha$ of $Q(x)$ satisfies $\alpha^{N} = 1$ (provided $\frac{P(x)}{Q(x)}$ has been reduced to lowest terms), and $\deg P < \deg Q$.
%\item For all $n \geq 0$,
%$$f(n) = \sum_{i = 1}^{k} P_{i}(n) \gamma_{i}^{n},$$
%where each $P_{i}$ is a polynomial function of $n$ and each $\gamma$ satisfies $\gamma_{i}^{N} = 1$.
%\end{enumerate}
%Moreover, the degree of $P_{i}(n)$ in equation is equal to one less than the multiplicity of the root $\gamma^{-1}$ in $Q(x)$, provided $\frac{P(x)}{Q(x)}$ has been reduced to lowest terms.
%\end{proposition}
%\begin{lemma}
%Consider $n = a_{1}y_{1} +a_{2}y_{2} + \cdots + a_{k}y_{k} $ with $a_{i},y_{i} \in \mathbb{Z}_{\geq 0}$, for any $n \in \Z_{\geq 0}$, denote the number of solutions $(y_{1},y_{2},...,y_{k})$ as $f(n)$, known as Sylvester Denumerant
%, then
%\begin{enumerate}
%\item $f(n)$ agrees with a quasi-polynomial of the quasiperiod $\text{lcm}(a_{1},...,a_{k})$ for $n \in \Z_{\geq 0}$.
%\item  $f(n) = \sum_{i = 1}^{k} P_{i}(n) \gamma_{i}^{n}$ for $n \in \Z_{\geq 0}$.
%\end{enumerate}
%\end{lemma}
%\begin{proof}
%By the Proposition $\ref{quasichara}$, we just need to verify that the power series $\sum_{n \geq 0} f(n)x^{n}$ agrees with a rational function  $\frac{P(x)}{Q(x)}$. Note that
%\begin{align*}
% \sum_{n \geq 0} f(n)x^{n} &=  \sum_{n \geq 0} \left( \underset{ n = a_{1}y_{1} +a_{2}y_{2} + \cdots + a_{k}y_{k} }{\sum_{(y_{1},...,y_{k})\in \N^{k} }}x^{n} \right) \\
% &=  \sum_{n \geq 0} \left( \underset{ n = a_{1}y_{1} +a_{2}y_{2} + \cdots + a_{k}y_{k} }{\sum_{(y_{1},...,y_{k}) \in \N^{k}  }}x^{a_{1}y_{1} +a_{2}y_{2} + \cdots + a_{k}y_{k} } \right) \\
%  &=  \sum_{(y_{1},...,y_{k})\in \N^{k}   }x^{a_{1}y_{1} +a_{2}y_{2} + \cdots + a_{k}y_{k} } \\
%  &= \frac{1}{1-x^{a_{1}}} \frac{1}{1-x^{a_{2}}} \cdots \frac{1}{1-x^{a_{k}}}.
%\end{align*}
%\end{proof}

%\begin{cor}
%Consider a weak composition of $n = y_{1} + y_{2} + \cdots + y_{k}$ with at most $k$ parts, the number of solutions $(y_{1},\cdots,y_{k})$ is a polynomial of degree $k$ $\left( \binom{n}{k} \right) = \binom{n+k-1}{k-1}$
%\end{cor}



%\begin{proposition}
%Let $f_{1}(x_{1}),f_{2}(x_{2}),...,f_{n}(x_{n})$ be $n$ Sylvester Denumerants and $(a_{1,i},\cdots,a_{k_{i},i})$ be the parameters of Sylvester Denumerant $f_{i}$. Given a polytope of the form $P = \{ x : Ax = b, x \geq 0 \}$ where $A \in \Z^{d\times n}, b \in \Z^{d}$ and consider a multivariate function $q(x) = \prod_{i=1}^{n} f_{i}(x_{i})$. Then
%$$ \sum_{x\in P \cap \Z^{n}}q(x) =  \left| P^{*} \cap \Z^{n^{*}} \right|,$$
%where $P^{*}$ is a lifting of the polytope $P$ and $n^{*} = n + k_{1}+\cdots+k_{n}$. Specifically,
%$$P^{*} = \left\{ \left. \begin{pmatrix}x\\y_{1}\\ \vdots \\y_{n} \end{pmatrix} \right|   A^{*}\begin{pmatrix}x\\y_{1}\\ \vdots \\y_{n} \end{pmatrix} = \begin{pmatrix}b\\0\\ \vdots \\0 \end{pmatrix} ,x \geq 0, y_{i} \geq 0 \right\}$$
%and
%$$A^{*} = \begin{bmatrix} A & 0 & \cdots & 0 \\ \begin{matrix} 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\  \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \end{matrix} & \begin{matrix} -a_{1,1} \quad \cdots \quad -a_{k_{1},1} \\ 0 \\ \vdots \\ 0  \end{matrix}  & \ddots &   \begin{matrix} 0 \\ 0 \\ \vdots \\ -a_{1,n} \quad \cdots \quad -a_{k_{n},n}  \end{matrix}  \end{bmatrix}.
%$$
%\end{proposition}

%\begin{cor}
%Let $x^{\alpha} = x_{1}^{\alpha_{1}}x_{2}^{\alpha_{2}}\cdots x_{n}^{\alpha_{n}}$ be a monomial of degree $|\alpha|$, Given a polytope of the form $P = \{ x : Ax = b, x \geq 0 \}$ where $A \in \Z^{d\times n}, b \in \Z^{d}$, then
%$$ \sum_{x\in P \cap \Z^{n}}x^{\alpha} =  \sum_{P^{*}}\left| P^{*} \cap \Z^{n^{*}} \right|,$$
%\end{cor}

\begin{definition}\label{def:Q}
%Given a rational polytope of the form $Q = \{\mathbf{y} : \mathbf{C}\mathbf{y} = \mathbf{d}, \mathbf{y} \geq \mathbf{0}\}$ where $\mathbf{C} \in \Z^{r \times m}, \mathbf{d} \in \Z^{r}$. For every integer $n$, $n Q$ is defined as
Let $Q = \{\mathbf{y} \mid \mathbf{C}\mathbf{y} = \mathbf{d}, \mathbf{y} \geq \mathbf{0}\} \subseteq \mathbb{R}^m$ where $\mathbf{C} \in \Z^{r \times m}, \mathbf{d} \in \Z^{r}$ be a rational polytope. 
For every integer $t$, we define $tQ = \{\mathbf{y} \mid \mathbf{Cy} = t \mathbf{d}, \mathbf{y} \geq \mathbf{0}\}$.
\end{definition}
\begin{example}
Consider the $(m-1)$-dimensional standard simplex 
\[
\Delta_{m-1}= \{\mathbf{y} \mid y_{1}+\cdots+y_{m} = 1, y_{i} \geq 0 \}.
\] 
Then $-2 \Delta_{m-1} = \{\mathbf{y} \mid y_{1}+\cdots+y_{m} = -2\cdot 1, y_{i} \geq 0 \}$.
\end{example}
\begin{definition}
A function $w(t)$ is a \textbf{late-dilated} Ehrhart quasi-polynomial if
$$w(t) = |(t-c) Q \cap \Z^{m}|,$$
where $c\in\Z$ and $Q$ is a rational polytope of the form given in \cref{def:Q}.
\end{definition}
\begin{example}
The function $\binom{t}{m-1}$ is a {late-dilated} Ehrhart polynomial in the variable $t$, because $\binom{t}{m-1}  = |(t-m+1) \Delta_{m-1} \cap \Z^{m}|$.
\end{example}



\begin{cor}\label{lifting} \quad
Let $w_{1},w_{2},\cdots,w_{n}$ be $n$ {late-dilated} Ehrhart quasi-polynomials, i.e., $w_{i}(t) = |(t-c_{i}) Q_{i} \cap \Z^{m_{i}}|$ where $Q_{i} = \{ \mathbf{y_{i}} \mid \mathbf{C_{i}y_{i}} = \mathbf{d_{i}}, \mathbf{y_{i}} \geq \mathbf{0} \}$ and $\mathbf{C_{i}} \in \Z^{r_{i} \times m_{i}}, \mathbf{d_{i}} \in \Z^{r_{i}}, c_{i} \in \Z$. Consider a rational polytope of the form $P = \{ \mathbf{x} \mid \mathbf{Ax} = \mathbf{b}, \mathbf{x} \geq \mathbf{0} \} \subseteq \mathbb{R}^n$ where $\mathbf{A} \in \Z^{s\times n}, \mathbf{b} \in \Z^{s}$ and the multivariate function $w( \mathbf{x} ) = \prod_{i=1}^{n} w_{i}(x_{i})$. 
There exists a \emph{weight lifting polytope} $P^{*}\subseteq \mathbb{R}^{n^*}$ of $P$, where $n^{*} = n + m_{1} + \cdots + m_{n}$,  such that
$$  \sum_{\mathbf{x} \in P \cap \Z^{n}}w(\mathbf{x}) =  \left| P^{*} \cap \Z^{n^{*}} \right|.$$
%Specifically, $$P^{*} = \left\{ \left. \begin{pmatrix} \mathbf{x} \\ \mathbf{y_{1}}\\ \vdots \\ \mathbf{y_{n}} \end{pmatrix} \right|   \mathbf{A}^{*}\begin{pmatrix} \mathbf{x} \\ \mathbf{y_{1}}\\ \vdots \\ \mathbf{y_{n}} \end{pmatrix} = \begin{pmatrix} \mathbf{b} \\ c_{1}\mathbf{d_{1}} \\ \vdots \\ c_{n}\mathbf{d_{n}} \end{pmatrix} ,\mathbf{x} \geq \mathbf{0}, \mathbf{y_{i}} \geq \mathbf{0} \right\}$$
%and
%$$\mathbf{A}^{*} = \begin{bmatrix} \mathbf{A} & \mathbf{0} & \cdots & \mathbf{0} \\ \begin{matrix} \mathbf{d_{1}} & \mathbf{0} & \cdots & \mathbf{0} \\ \mathbf{0} & \mathbf{d_{2}}  & \cdots & \mathbf{0} \\  \vdots & \vdots & \ddots & \vdots \\ \mathbf{0} & \mathbf{0} & \cdots & \mathbf{d_{n}} \end{matrix} & \begin{matrix} -\mathbf{C_{1}} \\ \mathbf{0} \\ \vdots \\ \mathbf{0}  \end{matrix}  & \ddots &   \begin{matrix} \mathbf{0} \\ \mathbf{0} \\ \vdots \\ \mathbf{-C_{n}}  \end{matrix}  \end{bmatrix}.$$
\end{cor}
\begin{proof}
We need only show that there is a rational polytope $Q(x_1,\ldots, x_n)$ of the form given in \cref{polytopelifting} for which $w(\mathbf{x}) = | Q(x_{1},\ldots,x_{n}) \cap \mathbb{Z}^{m_{1}+\cdots+m_{n}}|$ and then apply \cref{polytopelifting}.
Let $Q(x_{1},\ldots,x_{n}) = \prod_{i=1}^{n}(x_{i}-c_{i})Q_{i}$. Specifically, $Q(x_1,\ldots, x_n)$ has the form
\begin{equation*}\left\{ \begin{pmatrix} \mathbf{y_{1}}\\ \vdots \\ \mathbf{y_{n}} \end{pmatrix}\left| \begin{pmatrix} \mathbf{C_{1}} &  \cdots & \mathbf{0} \\   \vdots &  \ddots & \vdots \\ \mathbf{0}  & \cdots & \mathbf{C_{n}} \end{pmatrix}
\begin{pmatrix} \mathbf{y_{1}}\\ \vdots \\ \mathbf{y_{n}} \end{pmatrix} =
x_{1}\begin{pmatrix} \mathbf{d_{1}}\\\mathbf{0} \\ \vdots \\ \mathbf{0} \end{pmatrix}+ \cdots + x_{n}\begin{pmatrix} \mathbf{0}\\ \vdots \\ \mathbf{0}  \\ \mathbf{d_{n}} \end{pmatrix} + \mathbf{e}, \mathbf{y} \geq \mathbf{0}\right\}.\right.
\qedhere
\end{equation*}
\end{proof}

\begin{cor}\label{monomial}
For every monomial $w(\mathbf{x}) = \mathbf{x}^{\alpha} = x_{1}^{\alpha_{1}}x_{2}^{\alpha_{2}}\cdots x_{n}^{\alpha_{n}}$, there exists a weight lifting polytope $P^{*}\subseteq \mathbb{R}^{n^*}$ where $n^* = n + 2|\alpha| = n + 2\sum_{i=1}^n \alpha_i$ such that
%which lies in the dimension $n^{*} = n + 2|\alpha|$ such that
$$  \sum_{\mathbf{x} \in P \cap \Z^{n}}w( \mathbf{x} ) =  \left| P^{*} \cap \Z^{n^{*}} \right|.$$
\end{cor}
\begin{proof}
By \cref{lifting}, we just need to show that $x_{i}^{\alpha_{i}}$ is a {late-dilated} Ehrhart polynomial. It is well known that $(k+1)^{\alpha_{i}}$ is the Ehrhart polynomial of the $\alpha_{i}$-dimensional hypercube of length $k$. In particular, the hypercube has the form
\begin{equation*}
t Q_{i} = \left\{ \begin{pmatrix} y_{1} \\ \vdots \\ y_{\alpha_{i}} \\ z_{1} \\ \vdots \\ z_{\alpha_{i}} \end{pmatrix} \left| \begin{bmatrix} \begin{matrix} 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\  \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1  \end{matrix} & \begin{matrix} 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\  \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1  \end{matrix} \end{bmatrix} \begin{pmatrix} y_{1} \\ \vdots \\ y_{\alpha_{i}} \\ z_{1} \\ \vdots \\ z_{\alpha_{i}} \end{pmatrix} = t\begin{pmatrix} 1 \\ \vdots \\ 1  \end{pmatrix} , y_{i}\geq 0,z_{i}\geq 0 \right. \right\}.
\qedhere
\end{equation*}
\end{proof}

\begin{cor}\label{polynomial}
For every polynomial $w( \mathbf{x} ) = \sum_{\alpha \in I}c_{\alpha} \mathbf{x} ^{\alpha} = \sum_{\alpha \in I}c_{\alpha}x_{1}^{\alpha_{1}}x_{2}^{\alpha_{2}}\cdots x_{n}^{\alpha_{n}}$, there exist $|I|$ weight lifting polytopes $P^{*}_{\alpha}$ indexed by the exponents of monomials such that
$$  \sum_{ \mathbf{x} \in P \cap \Z^{n}}w(x) =  \sum_{\alpha \in I}c_{\alpha}\left| P^{*}_{\alpha} \cap \Z^{n^{*}} \right|.$$
\end{cor}
\begin{proof}
This follows directly from \cref{monomial}
\end{proof}

\begin{rem}
\cref{polynomial} implies that if $w(x)$ is a polynomial with $|I|$ nonzero monomials, then we can compute the sum of lattice points of $P$ weighted by $w$ by counting integral points in $|I|$ weight lifting polytopes.
%for a polynomial with $|I|$ terms the number of weight lifting polytopes we need is $|I|$. \nathan{I think the `we need is' sounds awkward here.}
\end{rem} 

We give another two corollaries of \cref{polytopelifting}. %about encoding polynomials in terms of Ehrhart-quasipolynomials.
\begin{cor}\label{choose}
Consider the polynomial $w( \mathbf{x} ) = \prod_{i=1}^{n} \binom{x_{i}+\alpha_{i}-1}{\alpha_{i} -1 }$. There exists a weight lifting polytope $P^{*} \subseteq \mathbb{R}^{n^*}$ where $n^* = n+|\alpha|$ such that 
%which lies in the dimension $n^{*} = n+|\alpha|$ such that
$$  \sum_{ \mathbf{x} \in P \cap \Z^{n}}w( \mathbf{x} ) =  \left| P^{*} \cap \Z^{n^{*}} \right|.$$
\end{cor}
\begin{proof}
Recall that $\binom{x_{i}+\alpha_{i}-1}{\alpha_{i} -1 }$ is the Ehrhart polynomial of the standard $(\alpha_{i}-1)$-simplex $1 = y_{1} + \cdots + y_{\alpha_{i}}$ with $y_{i} \geq 0$.
In particular, the simplex has the form
$$t Q_{i} = \left\{ \begin{pmatrix} y_{1} \\ \vdots \\ y_{\alpha_{i}}  \end{pmatrix} \left| \begin{bmatrix}  1  & \cdots & 1  \end{bmatrix} \begin{pmatrix} y_{1} \\ \vdots \\ y_{\alpha_{i}} \end{pmatrix} = t\cdot 1 , y_{i}\geq 0 \right. \right\}.$$
Applying \cref{lifting} gives the weight lifting polytope from the statement.
\end{proof}

\begin{cor}\label{multichoose}
Consider the polynomial $w( \mathbf{x} ) = \prod_{i=1}^{n} \binom{x_{i}}{\alpha_{i} -1 }$. There exists a weight lifting polytope $P^{*}$ of the dimension $n^{*} = n+|\alpha|$ such that
  $\sum_{ \mathbf{x} \in P \cap \Z^{n}}w( \mathbf{x} ) =  \left| P^{*} \cap \Z^{n^{*}} \right|.$
\end{cor}
\begin{proof}
The function $\binom{x_{i}}{\alpha_{i} -1 }$ is a {late-dilated} Ehrhart polynomial because $\binom{x_{i} + \alpha_{i} -1 }{ \alpha_{i} -1 }$ is the Ehrhart polynomial of the standard $(\alpha_i-1)$-simplex. Applying \cref{lifting} gives the weight lifting polytope from the statement.
\end{proof}

Note that $\{ \binom{x+k-1}{k -1 } \mid k=1,2,\dots \}$ and $\{\binom{x}{k -1 } \mid k=1,2,\dots \}$ are two well-known bases of the vector space of polynomials in $x$. 

% \begin{lemma}[Stanley's EC1]\label{transition} \quad
% \begin{enumerate}
%     \item $x^{d} = \sum_{k=1}^{d+1} k!S(d,k)\binom{x}{k -1 } $.
%     \item $x^{d} = \sum_{k=1}^{d+1} (-1)^{d-k} k!S(d, k)\binom{x+k-1}{k -1 } $.
% \end{enumerate}
% \end{lemma}

\begin{cor}\label{monomial2}
For every monomial $w( \mathbf{x} ) =  \mathbf{x}^{\alpha} = x_{1}^{\alpha_{1}}\cdots x_{n}^{\alpha_{n}}$, there exist at most $\alpha_{1}\cdots \alpha_{n}$ weight lifting polytopes $P^{*}_{\beta}$ indexed by the vector $\beta$ and $P^{*}_{\beta} \subset \mathbb{R}^{n^{*}}$ where $n^{*} = n + |\beta|$
%of the dimension $n + |\beta|$ 
such that
$$  \sum_{ \mathbf{x} \in P \cap \Z^{n}}w( \mathbf{x} ) =  \sum_{\beta \leq \alpha}c_{\beta} \left| P^{*}_{\beta} \cap \Z^{n^{*}} \right|.$$
\end{cor}
\begin{proof}
Let $v_{k}(x)$ be one of the two binomial bases described above.
%and $c(d,k)$ be the correspondent transition coefficients in the lemma \ref{transition},
% \begin{align*}
%     & \quad x_{1}^{\alpha_{1}}x_{2}^{\alpha_{2}}\cdots x_{n}^{\alpha_{n}}\\
%      &= \left[ \sum_{\beta_{1}=1}^{\alpha_{1}} c(\alpha_{1},\beta_{1})v_{\beta_{1}}(x_{1}) \right]\left[ \sum_{\beta_{2}=1}^{\alpha_{2}} c(\alpha_{2},\beta_{2})v_{\beta_{2}}(x_{2}) \right]\cdots\left[ \sum_{\beta_{n}=1}^{\alpha_{n}} c(\alpha_{n},\beta_{n})v_{\beta_{n}}(x_{n}) \right] \\
%     &= \sum_{\beta \leq \alpha}c(\alpha_{1},\beta_{1})c(\alpha_{2},\beta_{2})\cdots c(\alpha_{n},\beta_{n}) \cdot v_{\beta_{1}}(x_{1})v_{\beta_{2}}(x_{2})\cdots v_{\beta_{n}}(x_{n}).
% \end{align*}
We can transform the monomial basis $\{x^k\mid k = 0,1,2,\ldots\}$
into the binomial basis, 
\[
x_{1}^{\alpha_{1}}x_{2}^{\alpha_{2}}\cdots x_{n}^{\alpha_{n}} = \sum_{\beta \leq \alpha}c(\alpha,\beta) \cdot v_{\beta_{1}}(x_{1})v_{\beta_{2}}(x_{2})\cdots v_{\beta_{n}}(x_{n}).
\]
By \cref{choose,multichoose}, for each $\beta$ and each polynomial $v_{\beta_{1}}(x_{1})v_{\beta_{2}}(x_{2})\cdots v_{\beta_{n}}(x_{n})$, there exists a corresponding weight lifting polytope $P^{*}_{\beta} \subset \mathbb{R}^{n + |\beta|}$.
%such that
%$$  \sum_{x\in P \cap \Z^{n}}v_{\beta_{1}}(x_{1})v_{\beta_{2}}(x_{2})\cdots v_{\beta_{n}}(x_{n}) =  \left| P^{*} \cap \Z^{n^{*}} \right|.$$
\end{proof}
\begin{rem}
In \cref{monomial} we express the weighted sum of lattice points of $P$ using a single $P^* \subset \mathbb{R}^{n + 2|\alpha|}$, but in \cref{monomial2} we express this sum using at most $\alpha_{1}\alpha_{2}\cdots \alpha_{n}$ polytopes of lower dimension $P^*_{\beta} \subset \mathbb{R}^{n + |\beta|}$.
\end{rem}


%Now we move to prove \cref{integrate-maximize}. 

\begin{proof}[Proof of \cref{integrate-maximize}]
Applying \cref{polytopelifting} to $P$ gives a weight lifting polytope $P^*$ for which $\weightsum{P}{w}{t} = \weightsum{P^*}{1}{t}$.  Applying a classical result relating the volume and lead coefficient of the Ehrhart quasi-polynomial of $P^*$ completes the proof.  Both $\weightsum{P}{w}{t}$ and $\weightsum{P^*}{1}{t}$ are quasi-polynomial functions of $t$, and concretely, this equality implies that their leading coefficients are the same.

%The first claim follows from \cref{polytopelifting} %because of
%and $\weightsum{P}{w}{t} = \weightsum{P^*}{1}{t}$  
%\nathan{This argument is also using the fact that we know the leading coefficient is related to the integral for $P^*$, right?  I think we should include a reference.}
%Because as hypothesis $w(x)$ is an Ehrhart quasi-polynomial the leading coefficients  $\weightsum{P}{w}{t}=\weightsum{P^*}{1}{t}$ are the same.  
%Concretely, this equality  implies that the leading coefficients of both quasi-polynomials are the same.
%We can then replace integration with computation of the leading coefficient of an usual Ehrhart function which is a direct volume computation. 
We can then replace integration of $w(x)$ over $P$ with computation of the leading coefficient of $\weightsum{P^*}{1}{t}$, which is equivalent to computing the volume of $P^*$. 
Note that this transformation can be carried out in a number of steps that is polynomial in the size of the inputs describing $P^*$.
%time {\color{red}as the $P^*$.}


%The second claim requires just a bit more work. We start by recalling an elementary fact for a collection $S=\{s_1,\dots,s_r\}$ of non-negative real numbers, $\hbox{\rm
For the second claim, we start by recalling an elementary fact. Let $S = \{s_1,\ldots, s_r\}$ be a set of non-negative real numbers.  Then $\max\{s_i \mid s_i \in S\} = \lim_{k \rightarrow \infty}\sqrt[k]{\sum_{j=1}^r s_j^k}$.
%for a collection $S=\{s_1,\dots,s_r\}$ of non-negative real numbers, $\hbox{\rm
%  maximum} \{s_i | s_i \in S \}$ equals $\lim_{k \rightarrow \infty}
%\sqrt[k]{\sum_{j=1}^r s_j^k}.$ 
The arithmetic mean of $S$ is at most its maximum value, which in turn is at most as big as $\sum_i s_i$. We apply these ideas to the set $S = \{w(\alpha) \mid \alpha \in P \cap \Z^n\}$. This gives upper and lower bounds for each positive integer $k$:
\[
L_{k}=
\sqrt[k]{\frac{\sum\limits_{\alpha\in P \cap \Z^n}
w(\alpha)^{k}}{|P\cap\Z^d|}} \leq
\max\{w(\alpha):\alpha\in P\cap\Z^n\}\leq
\sqrt[k]{\sum\limits_{\alpha\in P \cap \Z^n}
w(\alpha)^{k}}=U_{k}.
\]

%Using this fact that the arithmetic mean of a finite set
 % of nonnegative values is at most as big as the maximum value, which
 % in turn is at most as big as the sum of all values, we obtain the
 % sequences of lower and upper bounds, $L_{k}$ and $U_{k}$, for
 % the maximum:
%\[
%L_{k}=
%\sqrt[k]{\frac{\sum\limits_{\alpha\in P \cap \Z^d}
%w(\alpha)^{k}}{|P\cap\Z^d|}} \leq
%\max\{w(\alpha):\alpha\in P\cap\Z^d\}\leq
%\sqrt[k]{\sum\limits_{\alpha\in P \cap \Z^d}
%w(\alpha)^{k}}=U_{k}.
%\]
As $k\rightarrow\infty$, $L_{k}$ and $U_{k}$ approach
this maximum value monotonically (from below and above, respectively).
Trivially, if the difference between the (rounded) upper and lower bounds
becomes strictly less than $1$, we have determined $\max\{w(x)\mid x\in P\cap\Z^n\}=\lceil L_{k}\rceil$. Thus the process 
terminates with the correct value. Finally, the key value in the sequences $L_{k}$ and $U_{k}$  is the term $\weightsum{P}{w^k}{t}=\sum\limits_{\alpha\in tP \cap \Z^n} w(\alpha)^{k}.$
\cref{lifting} describes how to construct the weight lifting polytope $P^*$ corresponding to the pair $P$ and $w(\alpha)^k$.
%\nathan{I am confused by this argument.}
\end{proof}


% Here we generalize prior work on reciprocity (see the book \cite{beckrobins} for details on this extensive topic and Section 4 on \cite{FedericoErwan}).
% We omit details and just state the main preliminary result

% % SKIP ALL THESE DETAILS
% Let $C \subset \mathbb{R}^{d}$ be a rational polyhedral cone, $C^{\circ}$ be the relative interior of $C$ and $w(\alpha)$ be a function of $d$ variables. We can define weighted Ehrhart series
% $$G(C,w;\mathbf{x}) = \sum_{\alpha \in C \cap \mathbb{Z}^{d}}w(\alpha)\mathbf{x}^{\alpha}, \qquad \overline{G}(C^{\circ},w;\mathbf{x}) = \sum_{\alpha \in C^{\circ} \cap \mathbb{Z}^{d}}w(-\alpha)\mathbf{x}^{\alpha}.$$

% \begin{theorem}[Naive Weighted Reciprocity Theorem]\quad
% \begin{itemize}
%     \item Assume the cone $C$ is simplicial, i.e., $C = \mathbb{R}_{\geq 0}v_{1} + \cdots + \mathbb{R}_{\geq 0}v_{d}$ with $\{v_{i}\}$ forms a basis of $\mathbb{R}^{d}$.
%     \item Assume $w(\alpha)$ is separable and multiplicative with respect to the basis $\{v_{i}\}$, i.e., there exist univariate functions $w_{i}$ such that $w(\alpha) = w_{1}(a_{1})\cdots w_{d}(a_{d})$ with $\alpha = a_{1}v_{1} + \cdots + a_{d}v_{d}$.
%     \item Assume $w_{i}(a) = \sum_{j = 1}^{k_{i}}P_{ij}(a)\gamma_{ij}^{a}$ where $P_{ij}$'s are polynomials and $\gamma_{ij}$ are nonzero complex numbers.
% \end{itemize}
% Under these assumptions,
% \begin{enumerate}
%     \item $G\left(C,w; \mathbf{x} \right)$ and $\overline{G}(C^{\circ},w; \mathbf{x} )$ are rational Ehrhart series,
%     \item they satisfy the reciprocity relation, $$\overline{G}(C^{\circ},w; \mathbf{x} ) =  (-1)^{d} G\left(C,w; \frac{1}{\mathbf{x}} \right).$$
% \end{enumerate}
% \end{theorem}
% \begin{proof}
% Denote $\Diamond  = \{\sum c_{i}v_{i}: 0 \leq c_{i} <1\}$ as the fundamental parallelepiped generated by $\{v_{i}\}$.
% For any $\alpha \in C\cap \mathbb{Z}^{d}$, we can represent $\alpha = a_{1}v_{1} +\cdots + a_{d}v_{d}$. Decompose it into integer parts and fractional parts, we have 
% $$ \alpha = \underbrace{\lfloor a_{1} \rfloor v_{1} +\cdots + \lfloor a_{d} \rfloor v_{d} }_{\text{integer parts}} + \underbrace{ \{a_{1}\}v_{1} + \cdots + \{a_{d}\}v_{d}}_{\text{fractional parts}}.$$
% For simplicity, we denote the fractional parts as $\beta \in \Diamond$. Then
% \[
%     G(C,w;\mathbf{x}) = \sum_{\alpha \in C \cap \mathbb{Z}^{d}}w(\alpha)\mathbf{x}^{\alpha} = \sum_{\alpha=a_{1}v_{1} +\cdots + a_{d}v_{d} \in C \cap \mathbb{Z}^{d}}\prod_{i=1}^{d}\left( w_{i}(a_{i})\mathbf{x}^{\lfloor a_{i} \rfloor v_{i}}\right) \cdot \mathbf{x}^{\beta} 
% \]
% \[
% = \sum_{\beta \in \Diamond}\sum_{\lfloor a_{1} \rfloor=0}^{\infty}\cdots\sum_{\lfloor a_{d} \rfloor=0}^{\infty}\prod_{i=1}^{d}\left( w_{i}(a_{i})\mathbf{x}^{\lfloor a_{i} \rfloor v_{i}}\right) \cdot \mathbf{x}^{\beta} 
% \]
% \[
% = \sum_{\beta \in \Diamond}\sum_{n_{1}=0}^{\infty}\cdots\sum_{n_{d}=0}^{\infty}\prod_{i=1}^{d}\left( w_{i}(n_{i}+\{a_{i}\})\mathbf{x}^{n_{i} v_{i}}\right) \cdot \mathbf{x}^{\beta} = \sum_{\beta \in \Diamond} \prod_{i=1}^{d}\left(\sum_{n_{i}=0}^{\infty} w_{i}(n_{i}+\{a_{i}\})\mathbf{x}^{n_{i} v_{i}} \right) \cdot \mathbf{x}^{\beta}.
% \]

% Similarly, for any $\alpha \in C^{\circ} \cap \mathbb{Z}^{d}$, we can decompose it into
% $$  \alpha = \underbrace{\lceil a_{1} \rceil v_{1} +\cdots + \lceil a_{d} \rceil v_{d} }_{\text{integer parts}} - \underbrace{ ( \{-a_{1}\}v_{1} + \cdots + \{-a_{d}\}v_{d} )}_{\text{fractional parts}}.$$
% Denote the fractional part as $\gamma \in \Diamond$. Then
% \[
%     \overline{G}(C^{\circ},w;\mathbf{x}) = \sum_{\alpha \in C^{\circ} \cap \mathbb{Z}^{d}}w(-\alpha)\mathbf{x}^{\alpha} = \sum_{\alpha=a_{1}v_{1} +\cdots + a_{d}v_{d} \in C^{\circ} \cap \mathbb{Z}^{d}}\prod_{i=1}^{d}\left( w_{i}(-a_{i})\mathbf{x}^{\lceil a_{i} \rceil v_{i}}\right) \cdot \mathbf{x}^{-\gamma} 
% \]  
% \[
%     = \sum_{\gamma \in \Diamond}\sum_{n_{1}=1}^{\infty}\cdots\sum_{n_{d}=1}^{\infty}\prod_{i=1}^{d}\left( w_{i}(-n_{i}+\{-a_{i}\})\mathbf{x}^{n_{i} v_{i}}\right) \cdot \mathbf{x}^{-\gamma}  = \sum_{\gamma \in \Diamond} \prod_{i=1}^{d}\left(\sum_{n_{i}= 1}^{\infty} w_{i}(-n_{i}+\{-a_{i}\})\mathbf{x}^{n_{i}v_{i}}\right) \cdot \mathbf{x}^{-\gamma}.
% \]

% According to the assumption and the equivalent characterizations of rational power series. For each $\beta,\gamma \in \Diamond$, generating functions
% $$ F_{i}(\mathbf{x},\beta) := \sum_{n_{i}=0}^{\infty} w_{i}(n_{i}+\{a_{i}\})\mathbf{x}^{n_{i} v_{i}} \quad\text{and}\quad  
% \overline{F_{i}}(\mathbf{x},\gamma)  := \sum_{n_{i}= 1}^{\infty}w_{i}(-n_{i}+\{-a_{i}\})\mathbf{x}^{n_{i}v_{i}}$$
% are rational. In particular, when $\beta = \gamma$, they satisfy the reciprocity property, i.e.,
% $$\overline{F_{i}}(\mathbf{x},\beta) = (-1)F_{i}\left(\frac{1}{\mathbf{x}},\beta \right).$$
% Therefore,
% \[
%     \overline{G}(C^{\circ},w; \mathbf{x} )  = \sum_{\gamma \in \Diamond} \prod_{i=1}^{d}\left( \overline{F_{i}}(\mathbf{x},\beta) \right) \cdot \mathbf{x}^{-\gamma} = \sum_{\beta \in \Diamond} \prod_{i=1}^{d}\left( (-1)F_{i}\left(\frac{1}{\mathbf{x}},\beta \right) \right) \cdot \mathbf{x}^{-\beta} = (-1)^{d} G\left(C,w; \frac{1}{\mathbf{x}}\right).
% \]
% \end{proof}

% \begin{lemma}\label{transf}
% Assume $w(\alpha) = \prod_{i=1}^{d}\sum_{j=1}^{m_{i}}P_{ij}(\alpha_{i})\gamma_{ij}^{\alpha_{i}}$ with $P_{ij}$'s are polynomials and $\gamma_{ij}$ are nonzero complex numbers, then 
% $w(\alpha)$ can be decomposed into finite terms where each term is separable and multiplicative with respect to any basis $\{v_{i}\}$ of $\mathbb{R}^{d}$.
% \end{lemma}
% \begin{proof}
% Only need to prove when $w(\alpha) = \alpha_{1}^{k_{1}}\cdots \alpha_{d}^{k_{d}} \cdot \gamma_{1}^{\alpha_{1}}\cdots \gamma_{d}^{\alpha_{d}}$. Suppose $\alpha = a_{1}v_{1} + \cdots +a_{d}v_{d}$, then we can simply replace $\alpha_{i}$ by $a_{1}v_{1i}+ \cdots + a_{d}v_{di}$ to get
% \begin{align*}
%     & (a_{1}v_{11}+ \cdots + a_{d}v_{d1})^{k_{1}}\cdots (a_{1}v_{1d}+ \cdots + a_{d}v_{dd})^{k_{d}} \cdot \gamma_{1}^{a_{1}v_{11}+ \cdots + a_{d}v_{d1}}\cdots \gamma_{d}^{a_{1}v_{1d}+ \cdots + a_{d}v_{dd}} \\
%     =&\sum_{\mathbf{k}}c_{\mathbf{k}}\mathbf{a}^{\mathbf{k}}(\gamma_{1}^{v_{11}}\cdots \gamma_{d}^{v_{1d}})^{a_{1}} \cdots (\gamma_{1}^{v_{d1}}\cdots \gamma_{d}^{v_{dd}})^{a_{d}} = \sum_{\mathbf{k}}c_{\mathbf{k}}\mathbf{a}^{\mathbf{k}} \hat{\gamma}_{1}^{a_{1}} \cdots \hat{\gamma}_{d}^{a_{d}}.
% \end{align*}

% \end{proof}

% \begin{theorem}[Weighted Reciprocity Theorem]\label{Weighted}
% Let $C \subset \mathbb{R}^{d}$ be a rational polyhedral cone and $w(\alpha) = \prod_{i=1}^{d}\sum_{j=1}^{m_{i}}P_{ij}(\alpha_{i})\gamma_{ij}^{\alpha_{i}}$ with $P_{ij}$'s are polynomials and $\gamma_{ij}$ are nonzero complex numbers, then
% \begin{enumerate}
%     \item $G\left(C,w; \mathbf{x} \right)$ and $\overline{G}(C^{\circ},w; \mathbf{x} )$ are rational Ehrhart series,
%     \item they satisfy the reciprocity relation, $$\overline{G}(C^{\circ},w; \mathbf{x} ) =  (-1)^{d} G\left(C,w; \frac{1}{\mathbf{x}} \right).$$
% \end{enumerate}
% \end{theorem}

% \begin{proof}
% Use the fact that every rational polyhedral cone can be triangulated into simplicial cones and the Inclusion--exclusion principle, we can assume that $C$ is simplicial. Then apply Lemma \ref{transf}, we can assume $w(\alpha)$ is separable and multiplicative with respect to a basis. Finally, we can apply Naive Weighted Reciprocity Theorem.
% \end{proof}

% \begin{proof}[(sketch of) Proof of \cref{Ehrhart}]
% Lift the polytope $P$ and the function $w$ to $\mathbb{R}^{n+1}$, we get a rational polyhedral cone $C$. Apply \cref{Weighted}, we have the reciprocity relation
% $$\overline{G}(C^{\circ},w; \mathbf{x} ) =  (-1)^{\dim{C}} G\left(C,w; \frac{1}{\mathbf{x}} \right).$$
% Specify $x_{1} = 1,\ldots, x_{n}=1, x_{n+1} = q$, we get
% \[
%     G\left(C,w; (1,\ldots,1,q) \right)  = \sum_{t = 0}^{\infty} \weightsum{P}{w}{t}q^{t}. \qquad
%     \overline{G}(C^{\circ},w; (1,\ldots,1,q) ) = \sum_{t = 1}^{\infty} \weightsum{-P^{\circ}}{w}{t}q^{t}.
% \]
% As the generating functions of $t$, they satisfy the reciprocity relation
% $$\overline{G}(C^{\circ},w; (1,\ldots,1,q) ) =  (-1)^{\dim{C}} G\left(C,w; (1,\ldots,1,\frac{1}{q}) \right).$$
% Therefore, the coefficients satisfy the reciprocity relation
% $$  \weightsum{-P^{\circ}}{w}{t} = (-1)^{\dim{C}-1}\weightsum{P}{w}{t} = (-1)^{\dim{P}}\weightsum{P}{w}{-t}. $$
% \end{proof}
% The following corollary was first presented as Theorem 4.6 in \cite{FedericoErwan}:

% \begin{cor}[Special case of Weighted Ehrhart Reciprocity]
% Let $P$ be a rational polytope in $\mathbb{R}^{n}$ and $P^{\circ}$ be the relative interior, and let $f: \mathbb{R}^{n} \to \mathbb{R}$ be a polynomial. The functions in $t \in \mathbb{N}$
% $$\weightsum{P}{f}{t} := \sum_{u \in tP\cap \mathbb{Z}^{n}}f(u), \quad   \weightsum{-P^{\circ}}{f}{t}  := \sum_{u \in -tP^{\circ}\cap \mathbb{Z}^{n}}f(u),$$
% extends to a quasi-polynomial on $\mathbb{R}$, which satisfy that
% $$ \weightsum{-P^{\circ}}{f}{t} = (-1)^{\dim{P}} \weightsum{P}{f}{-t}.$$
% \end{cor}
% %\begin{proof}
% %Apply \cref{Ehrhart} for the monomials $u^{k}$ and use linearity.
% %\end{proof}

 
% OLD VERSION HERE

%\begin{theorem}[Weighted Ehrhart Reciprocity]

%Let $P$ be a rational polytope in $\mathbb{R}^{n}$ and $P^{\circ}$ be the relative interior, and let $f: \mathbb{R}^{n} \to \mathbb{R}$ be a polynomial. The functions in $t \in \mathbb{N}$
%$$L_{P,f}(t) := \sum_{u \in tP\cap \mathbb{Z}^{n}}f(u), \quad   %L_{-P^{\circ},f}(t) := \sum_{u \in -tP^{\circ}\cap \mathbb{Z}^{n}}f(u),$$
%extends to a quasi-polynomial on $\mathbb{R}$, which satisfy that
%$$ L_{-P^{\circ},f}(t) = (-1)^{\dim{P}}L_{P,f}(-t).$$
%\end{theorem}


%Consider the special case when $P$ lies in the positive orthant and $f = %\mathbf{x}^{\alpha}$ or $f = \prod_{i=1}^{n} \binom{x_{i}+\alpha_{i}-1}{\alpha_{i} %-1 }$ , by \cref{monomial} and \ref{choose}, there exists a weight %lifting polytope $(tP)^{*}$ such that
%$$ L_{P,f}(t) = \sum_{u \in tP\cap \mathbb{Z}^{n}}f(u) = |(tP)^{*} \cap %\mathbb{Z}^{n^{*}}|.$$
%Since the polytopes $Q(\mathbf{x}) = \left\{ \mathbf{y} : \mathbf{Cy} = %\sum_{i=1}^{n}x_{i}\mathbf{d_{i}} + \mathbf{e}, \mathbf{y} \geq \mathbf{0} %\right\}$ associated with $f$ satisfies $\mathbf{e} = 0$. By Corollary %\ref{lifting}, we have $(tP)^{*} = t(P)^{*}$. Hence, $L_{P,f}(t)$ is an Ehrhart %polynomial of the weight lifting polytope $P^{*}$. Ehrhart reciprocity of %$L_{P,f}(t)$ suggests that it is possible to extend \cref{polytopelifting} %to general polytopes. A potential approach is to introduce counting interior %lattice points. 

\section{Applications} \label{applications}

%As we will see in some situations the Weighted Ehrhart polynomials can be thought of as (trivially weighted $h=1$) Ehrhart quasi-polynomial of a higher-dimensional polytope.
%We hope the reader is now motivated enough to continue reading and understand the %summation expressions of type shown in Equation \eqref{thesummation}. The goal of %our article is to show that summations $S(P,h)$ of Equation \eqref{thesummation} %always yield RSK-style identities. Indeed, the original RSK is just a very special %example of a principle saying that \emph{``Evaluating a quasi-polynomial over the %lattice points of a polytope is equivalent to counting the lattice points of %another bigger polytope''} (we call this bigger polytope the \emph{weight lifting %polytope}). We will see that RSK-style identities are everywhere. This of course %provides many interesting computational and theoretical consequences. E.g., At %least in some cases it gives a new way to perform the evaluation of $S(P,h)$ by %counting and the coefficients $E_m$ for $S(tP,h)$ can reduce to the usual Ehrhart %coefficients. Here is our main starting theorem describing our philosophy:
\cref{polytopelifting} has applications beyond integration and maximization of Ehrhart quasi-polynomials.  In this section we discuss how to use it to find new algebraic combinatorial identities by carefully choosing the polytope $P$ and reinterpreting the weight function $w$ in terms of Ehrhart quasi-polynomials of some polytopes $Q_i$.
%Besides integration and maximization of Ehrhart quasi-polynomials another of \cref{polytopelifting} is for finding new algebraic combinatorial identities expressing interesting invariants. 
%To obtain the identities it requires we carefully choose the polytope $P$ and reinterprete the weight function $w$ as an Ehrhart quasi-polynomial of some polytopes $Q_i$. 

\subsection{Weighted Ehrhart in number theory}



\noindent\textbf{Simultaneous Core Partitions.}
%\begin{example}[Simultaneous Core Partitions] 
We first describe an area in which weighted Ehrhart machinery has already been applied to prove a significant result.  Let $\lambda$ be a partition and $\mathcal{H}(\lambda)$ denote its multiset of hook lengths.  The partition $\lambda$ is called an \emph{$a$-core partition} if no element of $\mathcal{H}(\lambda)$ is divisible by $a$.  If $\lambda$ is both an $a$-core partition and a $b$-core partition, then we say that it is an $(a,b)$-core partition.  There is an extensive literature about statistical properties of sizes of simultaneous core partitions \cite{CoreSurveyNam,CoreSurveyNath}.  Anderson proved that if $a$ and $b$ are relatively prime positive integers then the number of $(a,b)$-core partitions is $\frac{1}{a+b}\binom{a+b}{a}$ \cite{Anderson}.  Johnson proved a conjecture of Armstrong, showing that the average size of an $(a,b)$-core partition is $(a+b+1)(a-1)(b-1)/24$ \cite{Johnson}.  Johnson's proof fits into the framework of weighted Ehrhart theory.

Suppose that $a$ and $b$ are relatively prime positive integers.  It is not hard to show that $a$-core partitions are in bijection with elements of $\Lambda_a = \left\{ (c_0,\ldots, c_{a-1}) \in \Z^a \colon \sum_i c_i = 0\right\}$. 
%The set of $(a,b)$-core partitions are in bijection with the elements of $\Lambda_a$ satisfying certain additional inequalities.  
Let $r_a(x)$ be the remainder when $x$ is divided by $a$.  We use cyclic indexing for elements $\mathbf{c} \in \Lambda_a$, that is, for $k \in \Z$ we set $c_k = c_{r_a(k)}$.  Simultaneous $(a,b)$-core partitions are in bijection with the elements of $\Lambda_a$ satisfying the inequalities $c_{i+b}-c_i \le  \left\lfloor \frac{b+i}{a} \right\rfloor$ for each $i \in \{0,1,\ldots, a-1\}$ \cite[Lemma 23]{Johnson}.  In this way, we see that $(a,b)$-core partitions are in bijection with integer points in a rational polytope $\mathrm{SC}_a(b)$.  The size of the $a$-core partition corresponding to $\mathbf{c} = (c_0,\ldots,c_{a-1})$ is $h_a(\mathbf{c}) = \frac{a}{2} \sum_{i=0}^{a-1} \left(c_i^2 + i c_i\right)$ \cite[Theorem 22]{Johnson}.  Therefore, Anderson's theorem is equivalent to computing the number of integer points in $\mathrm{SC}_a(b)$, and Johnson's theorem is equivalent to computing $\sum_{\mathbf{c} \in \mathrm{SC}_a(b)} h_a(\mathbf{c})$.
%{\bf NATHAN Maybe if you directly write the quadrtic function in terms of $c_i$'s is more direct?}

Johnson computes this weighted sum of lattice points by relating it
%$\sum_{\mathbf{c} \in \mathrm{SC}_a(b)} h_a(\mathbf{c})$ 
to a sum over the subset of integer points $(z_0,\ldots, z_{a-1})$ of the dilation of the standard simplex $b\Delta_{a-1}$ that satisfy $\sum i z_i \equiv 0 \pmod{a}$.  Johnson then shows that the sum he needs to compute is equal to $1/a$ times the sum of a quadratic function $w$ taken over all integer points of $b\Delta_{a-1}$. In order to conclude, he applies a result from Euler--Maclaurin theory, which is a version of the first part of \cref{integrate-maximize}, and also applies a version of weighted Ehrhart reciprocity that appears in \cite{FedericoErwan}. 
%We will discuss a generalization of weighted Ehrhart reciprocity for quasi-polynomials in the full version of the paper.

By \cref{polynomial}, there exists a family of weight lifting polytopes $P^{*}_{\alpha} \subset \mathbb{R}^{n^{*}}$ such that
\[
\sum_{x\in b\triangle_{a-1} \cap \mathbb{Z}^{a} }w(x) = \sum_{\alpha \in I}c_{\alpha}\left| P^{*}_{\alpha} \cap \Z^{n^{*}} \right|.
\]
It seems likely that further study of these kinds of weight lifting polytopes can lead to new techniques in the study of simultaneous core partitions.
%\end{example}

%{\bf NATHAN I see it is commented here below}

%Let $h$ be a quadratic function in $a$ variables and $\triangle^{a-1}$ be the standard $a-1$-simplex, by \cref{polynomial}, there exists a family of weight lifting polytope $P^{*}_{\alpha}$ such that
%$$ \sum_{x\in b\triangle^{a-1} \cap \mathbb{Z}^{a} }h(x) = \sum_{\alpha \in I}c_{\alpha}\left| P^{*}_{\alpha} \cap \Z^{n^{*}} \right|.$$
%\end{example}


\medskip 
\noindent\textbf{Numerical Semigroups.}
%\begin{example}[Numerical Semigroups]
A numerical semigroup $S$ is an additive submonoid of $\mathbb{N}_0 = \{0,1,2,\ldots\}$ with finite complement.  The elements of $\mathbb{N}_0 \setminus S$ are the \emph{gaps} of $S$, denoted $G(S) = \{h_{1},\ldots ,h_{g}\}$.
%Let $S$ be a numerical semigroup with gaps: $G(S) = \{h_{1},\ldots ,h_{g}\}$.  
The \emph{weight} of $S$ is defined by $w(S) = (h_{1}+ \cdots+h_{g})-(1+2+\cdots+g)$.  The motivation for studying $w(S)$ comes from the theory of Weierstrass semigroups of algebraic curves \cite[Chapter 1, Appendix E]{ACGH}.

Numerical semigroups containing $m$ are in bijection with integer points $(x_1,\ldots, x_{m-1})$ in the \emph{Kunz polyhedron} $P_{m}\subset \R^{m-1}$, which is defined via bounding inequalities
\[
x_{i} + x_{j} \geq x_{i+j} \text{ if } i+j < m,\quad
    x_{i} + x_{j} + 1 \geq x_{i+j - m} \text{ if }i+j > m.
\]
Let $NS(m,g)$ be the set of numerical semigroups containing  $m$ with genus $g$.  These semigroups are in bijection with the integer points of $P_{m,g}$, the polytope we get from 
$P_m$ by adding the additional constraint $\sum x_i = g$.  For a more extensive discussion of the connection between numerical semigroups containing $m$ and integer points in the Kunz polyhedron, see \cite[Section 4]{KaplanONeill}.
%If we consider the set $NS(m,g)$ of numerical semigroups with multiplicity $m$ and genus $g$, then it is correspondent to the lattice points in the Kunz polytope $P_{m,g}$. 
%{\bf NATHAN: Perhaps a reference to Kunz polytope?}
If $(k_1,\dots, k_{m-1})$ is the integer point corresponding to a semigroup $S$ of genus $g$, then $w(S) = \frac{m}{2}\sum_{i=1}^{m-1}k_i(k_i-1) + \sum_{i=1}^{m-1}i k_i-g(g+1)/2$.
%Furthermore, $w(S)$ is a quadratic polynomial in terms of the coordinates of the lattice point.  
There has been recent interest in statistical properties of weights of families of semigroups, see for example \cite[Section 5]{KaplanYe} and \cite{KaplanSinghal}.

By \cref{polynomial}, there exists a family of weight lifting polytopes $P^{*}_{\alpha}\subset \mathbb{R}^{n^*}$ such that
\[
\sum_{S \in NS(m,g)}w(S) = \sum_{S \in P_{m,g}\cap \mathbb{Z}^{m-1}}w(S) = \sum_{\alpha \in I}c_{\alpha}\left| P^{*}_{\alpha} \cap \Z^{n^{*}} \right|.
\]
Studying this family of polytopes and applying a version of \cref{integrate-maximize} suggests an approach to the following two questions:
% \begin{enumerate}
%     \item What is the maximum of $w(S)$ for $S \in NS(g,m)$?
%     \item For fixed $m$, what is the main term in the expression for $\sum_{S \in NS(g,m)}w(S)$ as $g\rightarrow \infty$?
% \end{enumerate}

1. What is the maximum of $w(S)$ for $S \in NS(m,g)$?
    
2. For fixed $m$, what is the main term in the expression for $\sum_{S \in NS(m,g)}w(S)$ as $g\rightarrow \infty$?


%\end{example}

\subsection{Weighted Ehrhart in combinatorial representation theory}

There is a long tradition of using lattice points of polytopes in representation theory (see \cite{GTDeLoera+McAllister2004} and the references there).
Here, as an application of \cref{polytopelifting}, we provide new connections. 

\medskip 
\noindent\textbf{Maximizing Kostka numbers.}
%\subsubsection{Maximizing Kostka numbers}
%For our second application we consider Schur functions.
%Schur functions are central objects in representation theory, it is a symmetric formal sum with countably many variables. 
Fix a partition $\lambda \vdash n$ and let $SSYT(\lambda)$ denote the set of semi-standard Young tableaux of shape $\lambda$.
The Schur function $s_\lambda$ is 
$$s_{\lambda}(x) = \sum_{T \in SSYT(\lambda)} x^{T}= \sum_{\alpha \in \text{comp}(n)} K_{\lambda\alpha}x^{\alpha},$$
where $\text{comp}(n)$ is the set of weak compositions $n$ and $K_{\lambda\alpha}$ is the \emph{Kostka number} that counts the number of tableaux in $SSYT(\lambda)$ with content $\alpha$.
Evaluating $s_\lambda$ at $x_{1}=1,x_{2} = 1,\ldots,x_{N} = 1,x_{N+1} = 0,x_{N+2} = 0,\ldots$ yields 
$$ |SSYT(\lambda,N)| = \sum_{\alpha \in N\text{-comp}(n)} K_{\lambda\alpha},$$
where $SSYT(\lambda,N)$ is the set of semi-standard Young tableaux of shape $\lambda$ and entries bounded by $N$ and $N\text{-comp(n)}$ is the set of weak composition of $n$ with $N$ parts.

A weak composition of $n$ with $N$ parts is a lattice point in the scaled standard $(N-1)$-simplex $n\triangle_{N-1}$. The Kostka number $K_{\lambda\alpha}$ equals the number of lattice points in the Gelfand--Tsetlin polytope $GT(\lambda,\alpha)$ (see e.g.,
\cite{GTDeLoera+McAllister2004}), so $w(\alpha)=K_{\lambda\alpha}$ is a weight function. 
% Specifically, the Gelfand--Tsetlin polytope $GT(\lambda,\alpha)$ is defined as $$\left\{(x_{ij})_{1\leq i \leq j \leq n} : \begin{aligned}
%     x_{in} &= \lambda_{i},\\
%     x_{11} = \alpha_{1}; \sum_{i=1}^{j}x_{ij} &- \sum_{i=1}^{j-1}x_{i,j-1} = \alpha_{j},\\
%     x_{ij} \geq 0, x_{i,j+1} &\geq x_{ij} \geq x_{i+1,j+1}.
% \end{aligned} \right\}.$$
There have been contributions to understanding the behavior of $K_{\lambda\alpha}$ as $(\lambda,\alpha)$ vary and an example is \cite{HuhMatherneMeszarosStDizier} in which it is shown that they are log-concave.
Applying the method in \cref{integrate-maximize} one can use the weight lifting polytope given by \cref{polytopelifting} to compute $max_{\alpha \in N\text{-comp(n)}} K_{\lambda\alpha}$ and we will include generated data in the full version of this paper. %Analogous claims will hold for the weight functions in the other applications of this section.

% By the \cref{polytopelifting}, there exists a weight lifting polytope $P^{*}(\lambda,N)$ such that
% $$\sum_{\alpha \in N\text{-comp}(n)} K_{\lambda\alpha} = |P^{*}(\lambda,N) \cap \mathbb{Z}^{n^{*}} |.$$
%Notice that $SSYT(\lambda,N)$ also corresponds to the lattice points of a polytope described by
%$$\{(x_{ij})_{1\leq j \leq \lambda_{i}}: x_{ij} \leq N, x_{ij} \leq x_{i,j+1}, x_{ij} + 1 \leq x_{i+1,j}\}.$$


\medskip
\noindent\textbf{Robinson--Schensted--Knuth (RSK) identity.}
%\subsubsection{Robinson-Schensted-Knuth (RSK) identity}
%\begin{example}
%\bigskip
%\noindent\textbf{Robinson-Schensted-Knuth (RSK) identity.}
Fix partitions $\mu ,\nu \vdash n$ and recall the famous \emph{RSK identity} (for %an introduction and 
details see e.g., \cite{combinatorialreptheory}):
%It is well-know that from the Cauchy identity
%$$\sum_{\lambda}s_{\lambda}(x)s_{\lambda}(y) = \prod_{i,j}(1-x_{i}y_{j})^{-1}, $$
%comparing the expression of the coefficient at the monomial $x^{\mu}y^{\nu}$, one %can prove the famous RSK identity we saw earlier
%$$ \sum_{\lambda \vdash n }K_{\lambda\mu}K_{\lambda\nu} = N_{\mu\nu}.$$
$$ \sum_{\lambda \vdash n }K_{\lambda\mu}K_{\lambda\nu} =   N_{\mu,\nu}.$$
The left sum is over partitions of $n$ and the summands are products of  {Kostka numbers}. %$K_{\lambda\mu}$, which count the number of semi-standard Young tableaux with shape $\lambda$ and content $\mu$. 
In fact, the left side of the identity is a weighted sum over the lattice points of %the polytope 
\begin{equation}\label{eq_partition_simplex}
    P=\{\mathbf{x}\in\R^n \mid x_1+\cdots+x_n=n, x_1\ge x_2\ge \cdots \ge x_n\ge 0 \}.
\end{equation}
%in fact a sum of the evaluations of a quasi-polynomial over the lattice points of a simplex. 
This is because the weight function  $w(\lambda)=K_{\lambda\mu}K_{\lambda\nu}$ is the number of lattice points in the Cartesian product $GT(\lambda,\mu)\times GT(\lambda,\nu)$ of two {Gelfand--Tsetlin polytopes}. %(see e.g., \cite{GTDeLoera+McAllister2004}).
%\cite{GTArdilaetal2011,GTDeLoera+McAllister2004,GTLiuetal2019} and the references therein).
The right-hand side of RSK, %is in fact another example of the summation identity, with $w=1$.  This time, 
$N_{\mu\nu}$,
%, counts the number of n-by-n matrices with row sum $\mu$ and column sum $\nu$, which is precisely
is the number of lattice points in the transportation polytope 
$$Mat_{n,n}(\mu,\nu) = \left\{(z_{ij})_{1 \leq i,j \leq n}\mid \sum_{j}z_{ij} = \mu_{i},\sum_{i}z_{ij} = \nu_{j}, z_{ij} \geq 0\right\}.$$

While RSK provides more information (e.g., a bijection), \cref{polytopelifting} gives a new polytope whose number of lattice points is the sum $\sum_{\lambda \vdash n }K_{\lambda\mu}K_{\lambda\nu}$.


\begin{cor}[A new RSK-like identity]
%Here the ambient space of $P$ is $\mathbb{R}^{2n-1}$$ since we have to include $n-1$ slack variables for it to have the form of Theorem 1.1. We then have that $s=n-1+1$ and thus $n^*=3n-1$.
There exists a weight lifting 
polytope $P^{*}(\mu,\nu)\subseteq\mathbb{R}^{n^{2}+2n}$ which is combinatorially different from $Mat_{n,n}(\mu,\nu)$ such that
$$ \sum_{\lambda \vdash n }K_{\lambda\mu}K_{\lambda\nu} =   |P^{*}(\mu,\nu)\cap \mathbb{Z}^{n^{2}+2n}|.$$
\end{cor}


% Although $P^{*}(\mu,\nu)$ and $Mat_{n,n}(\mu,\nu)$ contain the same number of lattice points and have the same dimension, they are not combinatorially equivalent. Concretely, we have computed examples in which they have different $f$-vectors.



% \begin{example}[Schur Functions]
% %For our second application we consider Schur functions.
% %Schur functions are central objects in representation theory, it is a symmetric formal sum with countably many variables. 
% The Schur function $s_\lambda$ indexed by a partition $\lambda \vdash n$ is 
% $$s_{\lambda}(x) = \sum_{T \in SSYT(\lambda)} x^{T},$$
% where $SSYT(\lambda)$ is the set of semi-standard Young tableaux of shape $\lambda$. % \cite{combinatorialreptheory}
% For a weak composition $\alpha$ of $n$, we can sum over  all semi-standard Young tableaux of shape $\lambda$ and weight $\alpha$ first and the Kostka number $K_{\lambda\alpha}$ denotes the number of these tableaux, then
% $$s_{\lambda}(x) = \sum_{\alpha \in \text{comp}(n)} K_{\lambda\alpha}x^{\alpha}.$$
% On the one hand, the evaluation at $x_{1}=1,x_{2} = 1,\ldots,x_{N} = 1,x_{N+1} = 0,x_{N+2} = 0,\ldots$ means that the summation over the set of semi-standard Young tableaux of shape $\lambda$ and entries bounded by $N$, i.e., $SSYT(\lambda,N)$; on the other hand, it means the summation of Kostka number over the set of weak composition of $n$ with $N$ parts, i.e. $N\text{-comp(n)}$. We yield an identity
% $$ |SSYT(\lambda,N)| = \sum_{\alpha \in N\text{-comp}(n)} K_{\lambda\alpha}.$$
% Note that a weak composition of $n$ with $N$ parts is a lattice points in the scaled standard $(N-1)$-simplex $n\triangle^{N-1}$. The Kostka number $K_{\lambda\alpha}$ is correspondent to the number of lattice points in Gelfand--Tsetlin polytope $GT(\lambda,\alpha)$, so $K_{\lambda\alpha}$ can be viewed as a multivariate counting function of $\alpha$. Specifically, the Gelfand--Tsetlin polytope $GT(\lambda,\alpha)$ is defined as $$\left\{(x_{ij})_{1\leq i \leq j \leq n} : \begin{aligned}
%     x_{in} &= \lambda_{i},\\
%     x_{11} = \alpha_{1}; \sum_{i=1}^{j}x_{ij} &- \sum_{i=1}^{j-1}x_{i,j-1} = \alpha_{j},\\
%     x_{ij} \geq 0, x_{i,j+1} &\geq x_{ij} \geq x_{i+1,j+1}.
% \end{aligned} \right\}.$$
% By the \cref{polytopelifting}, there exists a weight lifting polytope $P^{*}(\lambda,N)$ such that
% $$\sum_{\alpha \in N\text{-comp}(n)} K_{\lambda\alpha} = |P^{*}(\lambda,N) \cap \mathbb{Z}^{n^{*}} |.$$
% Notice that $SSYT(\lambda,N)$ also corresponds to the lattice points of a polytope described by
% $$\{(x_{ij})_{1\leq j \leq \lambda_{i}}: x_{ij} \leq N, x_{ij} \leq x_{i,j+1}, x_{ij} + 1 \leq x_{i+1,j}\}.$$
% \end{example}



%\begin{example}[Littlewood--Richardson Coefficients]
\noindent\textbf{Littlewood--Richardson Coefficients.}
%\subsubsection{Littlewood--Richardson Coefficients.}
Schur functions are central objects in representation theory and combinatorics.
%Skew Schur functions are one of the generalizations of Schur functions. 
%They have a combinatorial interpretation via semi-standard Young tableaux of skew shape,
The skew Schur function for partitions $\lambda,\mu \vdash n$ is
$$s_{\lambda / \mu}(x) = \sum_{\alpha \in \text{comp}(n)} K_{\lambda/\nu,\alpha}x^{\alpha},$$
where the sum is over all compositions of $n$ and $K_{\lambda/\nu,\alpha}$ counts the number of skew semi-standard Young tableaux of shape $\lambda/\nu$ and weight $\alpha$.
The Littlewood--Richardson rule (see e.g., \cite{Sagan}) expresses the skew Schur functions in terms of Schur functions,
$$ s_{\lambda / \mu}(x) =  \sum_{\nu \vdash n}c_{\mu\nu}^{\lambda}s_{\nu}(x).$$
Comparing the expression of the coefficient of the monomial $x^{\alpha}$ yields
$$K_{\lambda/\nu,\alpha} = \sum_{\nu \vdash n}c_{\mu\nu}^{\lambda}K_{\nu\alpha}.$$
The Littlewood--Richardson coefficient $c_{\mu\nu}^{\lambda}$ counts the number of lattice points in the \emph{hive polytope} $H_{\mu\nu}^{\lambda}$ (see e.g., \cite{hive_polytopes}).
Applying \cref{polytopelifting} to the simplex in \eqref{eq_partition_simplex} and %the weight function
$w(\nu)=c_{\mu\nu}^{\lambda}K_{\nu\alpha}$, which counts the number of lattice points in $H_{\mu\nu}^{\lambda}\times GT(\nu,\alpha)$, we obtain the following corollary.


\begin{cor}
There exists a weight lifting polytope $P^{*}(\lambda/\mu,\alpha)\subseteq\mathbb{R}^{n^{2}+2n}$ such that
%so $c_{\mu\nu}^{\lambda}$ can be viewed as a multivariate counting function of $\nu$. 
%Specifically, hive polytope $H_{\mu\nu}^{\lambda}$ is defined as
%By \cref{polytopelifting}, there exists a weight lifting polytope $P^{*}(\lambda/\mu,\alpha)$ such that
$$ \sum_{\lambda \vdash n }c_{\mu\nu}^{\lambda}K_{\nu\alpha} =   |P^{*}(\lambda/\mu,\alpha)\cap \mathbb{Z}^{n^{2}+2n}|.$$
\end{cor}

%\end{example}

% \begin{example}[New Newell-Littlewood Polytopes]
% Newell-Littlewood coefficients are defined from Littlewood--Richardson coefficients by the cubic expression,
% $$ N_{\mu,\nu,\lambda,} = \sum_{\alpha,\beta,\gamma}c_{\alpha,\beta}^{\mu}c_{\alpha,\gamma}^{\nu}c_{\beta,\gamma}^{\lambda},$$
% where the summation is taken over all possible integer  partitions with $|\alpha|+|\beta| = |\mu|$, $|\alpha|+|\gamma| = |\nu|$ and $|\beta|+|\gamma| = |\lambda|$. By \cref{polytopelifting}, there exists a weight lifting polytope $P^{*}(\mu,\nu,\lambda)$ such that
% $$ \sum_{\alpha,\beta,\gamma}c_{\alpha,\beta}^{\mu}c_{\alpha,\gamma}^{\nu}c_{\beta,\gamma}^{\lambda} = |P^{*}(\mu,\nu,\lambda) \cap \mathbb{Z}^{n^{*}}|.$$

% Note that for partitions $\mu,\nu,\lambda$ with at most $k$ parts, Gao et al. \cite{Gaoetal2020} define Newell-Littlewood polytopes $\mathcal{P}_{\mu,\nu,\lambda} $with $N_{\mu,\nu,\lambda,} = |\mathcal{P}_{\mu,\nu,\lambda}\cap  \mathbb{Z}^{3k^{2}}|$.
% \end{example}

% \subsection{Weighted Ehrhart for Integration}

% We last present an application to symbolic computing. Let $P$ be a $d$-dimensional
% rational convex polyhedron inside $\R^n$ and let $w \in \Q[x_1,\dots,x_n]$ be a (homogeneous) polynomial with rational coefficients. We
% consider an application to the problem of efficiently computing the \emph{exact} value of the integral of the polynomial $w$ over $P$, denoted $\int_{P} w \dif m$, where $\dif m$ is the \emph{integral Lebesgue measure}
%  on the affine hull of the polytope $P$. For rational input, the output will 
%  always be a rational number $\int_P f \dif m$ (Integration over polytopes was studied extensively in \cite{Barvinok-1991}, \cite{Barvinok-1992} and more recently at \cite{BBDKV08,DDM2013}.). 
 
 
% Integration over polytopes is in general an important but difficult problem.  
%  (see \cite{BBDKV08,Gritzmann+Klee} and the references therein). Our contribution starts from an old observation: It is known the computation of the leading coefficient of $\weightsum{P}{w}{t}$ is the same as computing the integral of $w$ over the polytope $P$ (see \cite{BBDKV08}). But the new \cref{polytopelifting} provides a new avenue of compute that leading coefficient because $\weightsum{P}{w}{t}=\weightsum{P^*}{1}{t}$.  We can replace integration with computation of the leading coefficient of a usual Ehrhart leading coefficient or direct volume computation. 
 
% In the papers \cite{DDM2013} the authors released an integration software implemented in LattE (code is available from \url{https://www.math.ucdavis.edu/~latte/}) several fast algorithms for integration. They depends on two main facts. The first key fact is integrals of 
%  arbitrary \emph{powers of  linear forms} can be computed in polynomial time Therefore, to integrate an input polynomial LattE decomposes it into a finite sum of \emph{powers of linear forms}, $\sum_{\ell}c_{\ell} \langle \ell, x \rangle^M$, using the  well-known identity shown by Waring's theorem. The second fact, is we can triangulate any polytope and just do the integral over simplices, then add the pieces. For all details of the LattE Integration algorithms and implementation see \cite{alexanderhirschowitz,Barvinok-1991,Barvinok-1992,BBDKV08,DDM2013}.
 
%  For this paper we implemented in SAGE our new algorithm, we call it the \emph{WLPvolume} algorithm. We used \cref{polytopelifting}, to find the weight lifting polytope and then we compute its volume using existing LattE code. We compared this with LattE \emph{Integration} as implemented in \cite{DDM2013} and available in the latest LattE release. Tables \ref{tab:monomialsimplex}, \ref{tab:linearformsimplex}  present a comparison of the LattE Integration method and the WLPvolume method. The columns represent the dimension of the polytope and the rows means the degree of the integrand. Each cell has two running times, integration method is the top one and WLPvolume method is the bottom one. 
 
%  Table \ref{tab:monomialsimplex} is the case when we integrate a monomial over 
%  the standard simplex. The LattE integration method is extremely slow when both dimension and degree are high. LattE's algorithm needs to turn one monomial a sum of powers of linear forms and  often thousands of linear forms. At the last case it did not even finish. In contrast WLPvolume largest computation was 3 seconds. In contrast, Table \ref{tab:linearformsimplex} is the case when we integrate a power of a linear form over the standard simplex. The performance reverses and WLPvolume method is extremely inefficient when both dimension and degree are high. The WLPvolume algorithm often needs to decompose the constructed weight lifting polytope into thousands of simplicial cones to compute the volume.


% \begin{table}[htbp]
%     \centering
%     \begin{tabular}{ m{2em} || c c c c c c c c c c }
%          & \multicolumn{10}{c}{Dimension of the simplex} \\
%         Deg & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
%         \hline\hline
%         \multirow{2}{0.8em}{1}
%          & 0.01 & 0.00 & 0.00 & 0.01 & 0.01 & 0.02 & 0.01 & 0.02 & 0.02 & 0.06 \\
%          & 0.00 & 0.01 & 0.01 & 0.02 & 0.02 & 0.02 & 0.03 & 0.05 & 0.06 & 0.08 \\
%         \hline
%         \multirow{2}{0.8em}{2}
%         & 0.00 & 0.01 & 0.01 & 0.01 & 0.01 & 0.04 & 0.12 & 0.41 & 1.43 & 5.13 \\
%         & 0.01 & 0.01 & 0.01 & 0.03 & 0.04 & 0.06 & 0.10 & 0.13 & 0.21 & 0.31 \\
%         \hline
%         \multirow{2}{0.8em}{3}
%         & 0.01 & 0.00 & 0.00 & 0.02 & 0.04 & 0.21 & 1.01 & 5.12 & 25.87 & 123.82 \\
%         & 0.00 & 0.01 & 0.03 & 0.03 & 0.09 & 0.13 & 0.21 & 0.35 & 0.55 & 0.80 \\
%         \hline
%         \multirow{2}{0.8em}{4}
%         & 0.00 & 0.00 & 0.01 & 0.02 & 0.11 & 0.80 & 5.38 & 35.49 & 222.07 & 1345.95 \\
%         & 0.01 & 0.01 & 0.03 & 0.07 & 0.13 & 0.27 & 0.45 & 0.74 & 1.18 & 1.73 \\
%         \hline
%         \multirow{2}{0.8em}{5}
%         & 0.00 & 0.01 & 0.01 & 0.04 & 0.29 & 2.55 & 21.53 & 166.20 & 1282.92 & - \\
%         & 0.01 & 0.02 & 0.06 & 0.12 & 0.25 & 0.48 & 0.87 & 1.39 & 2.21 & 3.32 \\
%         \hline
%     \end{tabular}
%     \caption{Integration(upper) v.s. WLPvolume(lower): one monomial $\prod x_i^{row}$  over the standard $col$-simplex.}
%     \label{tab:monomialsimplex}
% \end{table}
   


% \begin{table}[htbp]
%     \centering
%     \begin{tabular}{ m{2em} || c c c c c c c c c c }
%          & \multicolumn{10}{c}{Dimension of the simplex} \\
%         Deg & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
%         \hline\hline
%         \hline
%         \multirow{2}{0.8em}{2}
%         & 0.01 & 0.01 & 0.01 & 0.01 & 0.01 & 0.01 & 0.01 & 0.01 & 0.01 & 0.02 \\ 
%         & 0.01 & 0.01 & 0.01 & 0.02 & 0.01 & 0.01 & 0.02 & 0.01 & 0.03 & 0.03 \\
%         \hline
%         \multirow{2}{0.8em}{3}
%         & 0.01 & 0.00 & 0.01 & 0.00 & 0.01 & 0.02 & 0.01 & 0.01 & 0.01 & 0.01 \\ 
%         & 0.01 & 0.01 & 0.02 & 0.02 & 0.01 & 0.02 & 0.03 & 0.03 & 0.04 & 0.05 \\
%         \hline
%         \multirow{2}{0.8em}{4}
%         & 0.00 & 0.01 & 0.01 & 0.01 & 0.01 & 0.00 & 0.00 & 0.01 & 0.02 & 0.02 \\
%         & 0.01 & 0.01 & 0.01 & 0.02 & 0.02 & 0.03 & 0.03 & 0.07 & 0.11 & 0.15 \\
%         \hline
%         \multirow{2}{0.8em}{5}
%         & 0.00 & 0.01 & 0.01 & 0.00 & 0.02 & 0.01 & 0.01 & 0.01 & 0.01 & 0.01 \\
%         & 0.01 & 0.01 & 0.02 & 0.02 & 0.03 & 0.05 & 0.10 & 0.17 & 0.32 & 0.54 \\
%         \hline
%         \multirow{2}{0.8em}{6}
%         & 0.00 & 0.01 & 0.00 & 0.01 & 0.00 & 0.01 & 0.01 & 0.01 & 0.01 & 0.01 \\ 
%         & 0.00 & 0.01 & 0.02 & 0.03 & 0.04 & 0.08 & 0.21 & 0.41 & 1.48 & 3.43 \\
%         \hline
%         \multirow{2}{0.8em}{7}
%         & 0.01 & 0.00 & 0.00 & 0.00 & 0.02 & 0.02 & 0.01 & 0.01 & 0.01 & 0.02 \\ 
%         & 0.01 & 0.02 & 0.02 & 0.03 & 0.06 & 0.19 & 0.53 & 1.61 & 6.42 & 14.95 \\
%         \hline
%         \multirow{2}{0.8em}{8}
%         & 0.00 & 0.01 & 0.01 & 0.01 & 0.00 & 0.01 & 0.01 & 0.01 & 0.01 & 0.01 \\
%         & 0.01 & 0.02 & 0.03 & 0.04 & 0.10 & 0.33 & 1.13 & 5.49 & 20.54 & 72.00 \\
%         \hline
%         \multirow{2}{0.8em}{9}
%         & 0.00 & 0.00 & 0.01 & 0.01 & 0.01 & 0.01 & 0.01 & 0.01 & 0.02 & 0.01 \\
%         & 0.02 & 0.03 & 0.03 & 0.04 & 0.15 & 0.76 & 2.85 & 16.05 & 76.25 & 236.78 \\
%         \hline
%         \multirow{2}{0.8em}{10}
%         & 0.00 & 0.01 & 0.01 & 0.01 & 0.01 & 0.00 & 0.01 & 0.01 & 0.02 & 0.01 \\
%         & 0.02 & 0.02 & 0.02 & 0.06 & 0.30 & 1.43 & 6.68 & 38.55 & 231.76 & 1694.71 \\
%         \hline
%     \end{tabular}
%     \caption{Integration(upper) v.s. WLPvolume(lower): a power of a linear form $(\sum c_ix_i)^{row}$ over the standard $col$-simplex.}
%     \label{tab:linearformsimplex}
% \end{table}

%\begin{table}[]
%    \centering
%    \begin{tabular}{ m{2em} || c c c c c c c c c c }
%         & \multicolumn{10}{c}{Dimension of the cube} \\
%        Deg & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
%        \hline\hline
%        \multirow{2}{0.8em}{1}
%        & 0.01 & 0.00 & 0.01 & 0.01 & 0.01 & 0.02 & 0.02 & 0.03 & 0.08 & 0.16  \\
%        & 0.00 & 0.01 & 0.01 & 0.01 & 0.01 & 0.01 & 0.04 & 0.08 & 0.17 & 0.38  \\
%        \hline
%        \multirow{2}{0.8em}{2}
%        & 0.01 & 0.00 & 0.01 & 0.00 & 0.00 & 0.02 & 0.02 & 0.03 & 0.06 & 0.18  \\
%        & 0.01 & 0.01 & 0.01 & 0.02 & 0.02 & 0.04 & 0.07 & 0.14 & 0.30 & 0.63 \\
%        \hline
%        \multirow{2}{0.8em}{3}
%        & 0.01 & 0.00 & 0.01 & 0.00 & 0.00 & 0.02 & 0.02 & 0.04 & 0.07 & 0.16  \\
%        & 0.01 & 0.01 & 0.00 & 0.03 & 0.04 & 0.06 & 0.10 & 0.22 & 0.45 & 0.97 \\
%        \hline
%        \multirow{2}{0.8em}{4}
%        & 0.00 & 0.01 & 0.01 & 0.01 & 0.01 & 0.01 & 0.01 & 0.03 & 0.08 & 0.16  \\
%        & 0.00 & 0.01 & 0.02 & 0.02 & 0.04 & 0.06 & 0.16 & 0.34 & 0.67 & 1.52  \\
%        \hline
%        \multirow{2}{0.8em}{5}
%        & 0.00 & 0.00 & 0.00 & 0.01 & 0.01 & 0.01 & 0.02 & 0.02 & 0.07 & 0.15  \\
%       & 0.00 & 0.01 & 0.01 & 0.03 & 0.06 & 0.10 & 0.22 & 0.46 & 1.16 & 2.46  \\
%        \hline
%        \multirow{2}{0.8em}{6}
%        & 0.01 & 0.00 & 0.02 & 0.01 & 0.01 & 0.02 & 0.02 & 0.04 & 0.06 & 0.15  \\
%        & 0.01 & 0.02 & 0.03 & 0.04 & 0.09 & 0.17 & 0.38 & 0.96 & 2.35 & 5.20  \\
%        \hline
%        \multirow{2}{0.8em}{7}
%        & 0.00 & 0.00 & 0.01 & 0.01 & 0.01 & 0.02 & 0.03 & 0.03 & 0.07 & 0.16  \\ 
%        & 0.02 & 0.01 & 0.03 & 0.05 & 0.11 & 0.26 & 0.74 & 1.86 & 7.15 & 16.77  \\
%        \hline
%        \multirow{2}{0.8em}{8}
%        & 0.01 & 0.01 & 0.00 & 0.01 & 0.01 & 0.02 & 0.01 & 0.04 & 0.08 & 0.15  \\
%        & 0.02 & 0.03 & 0.03 & 0.08 & 0.15 & 0.45 & 1.34 & 4.59 & 19.75 & 47.96  \\
%       \hline
%        \multirow{2}{0.8em}{9}
%        & 0.01 & 0.01 & 0.01 & 0.02 & 0.02 & 0.02 & 0.02 & 0.05 & 0.09 & 0.15  \\
%        & 0.02 & 0.03 & 0.04 & 0.08 & 0.25 & 0.90 & 3.56 & 15.06 & 39.77 & 169.69  \\
%        \hline
%        \multirow{2}{0.8em}{10}
%        & 0.01 & 0.00 & 0.00 & 0.00 & 0.01 & 0.02 & 0.02 & 0.04 & 0.07 & 0.17  \\
%        & 0.02 & 0.02 & 0.06 & 0.12 & 0.33 & 1.72 & 8.34 & 34.66 & 148.63 & 1336.20  \\
%        \hline
%    \end{tabular}
%    \caption{Integration(upper) v.s. WLPvolume(lower): one linear form $(\sum c_ix_i)^{row}$ over the standard $col$-cube.}
%    \label{tab:linearformcube}
%\end{table}
%\section{Conclusions}

%We  presented two identities on weighted Ehrhart functions and several applications. consequences. We also showed with many situations we get identities between weighted combinatorial sums and counting expressions. 

\acknowledgements{We are truly grateful to Ardila who introduced us to his results with Brugall\'e that we have here extended to quasi-polynomial weights. Part of this work was done while most of the authors visited the American Institute of Mathematics in Palo Alto. 
%The authors are truly grateful for the hospitality of AIM and the support received.
}

%% 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}
