For $1 \leq r \leq n$, let $\mathcal{B}^n_r$ denote the polytope of all real matrices $$ \pi = \begin{pmatrix} \pi_{1,1} & \pi_{1,2} & \cdots & \pi_{1,n} \\ \pi_{2,1} & \ddots & \cdots & \pi_{2,n} \\ \vdots & \ddots & \ddots & \vdots \\ \pi_{n,1} & \cdots & \cdots & \pi_{n,n} \end{pmatrix} \in \mathbb{R}^{n\times n}$$ for which

• all entries are nonnegative: $\pi_{i,j}\geq 0$;
• the sum along any row or column is equal to one: $\sum_{j}\pi_{i,j}=1$ for all $i$; $\sum_{i}\pi_{i,j}=1$ for all $j$.
• the sum along any upper-left to lower-right chain of entries is at most $r$: $\sum_{k} \pi_{i_k,j_k} \leq r$ for all $(i_1,j_1)<(i_2,j_2) < \cdots < (i_m,j_m)$, where $(i,j) < (i',j')$ means $i\leq i'$, $j\leq j'$ with at least one of these inequalities being strict.

By definition $\mathcal{B}^n_n$ is the Birkhoff polytope of doubly-stochastic matrices. In general $\mathcal{B}^n_r$ is a subpolytope of the Birkhoff polytope.

It is well-known that $\mathcal{B}^n_n$ is the convex hull of all permutation matrices, and so in particular $\mathcal{B}^n_n$ is an integral polytope. But this is not true of the $\mathcal{B}^n_r$ in general: for instance, $$ \begin{pmatrix} 0.5 & 0 & 0.5 \\ 0 & 1 & 0 \\ 0.5 & 0 & 0.5 \end{pmatrix}$$ is a vertex of $\mathcal{B}^3_2$. The vertices of $\mathcal{B}^n_r$ which are integral are precisely the permutation matrices of $123...r+1$-avoiding permutations.

For a polytope $\mathcal{P} \subseteq \mathbb{R}^n$ I use $L(\mathcal{P};t)$ to denote the Ehrhart function which at nonnegative integers $t$ counts the number of lattice points of $t\mathcal{P}$: $$ L(\mathcal{P};t) := \# (t\mathcal{P}\cap \mathbb{Z}^n).$$

Since $\mathcal{B}^n_r$ is not an integral polytope, but it is a rational polytope, its Ehrhart function $L(\mathcal{B}^n_r;t)$ is a priori only a quasipolynomial in $t$.

Question: Is $L(\mathcal{B}^n_r;t)$ in fact always an honest polynomial in $t$?

I have verified this for $1\leq r \leq n \leq 5$ via Sage. The computation that took the longest was $L(\mathcal{B}^5_2;t)$ which is equal to

(5959/249080832000) * (t + 1) * (t + 2) * (t + 3) * (t + 4) * (t^12 + 30*t^11 + 2534915/5959*t^10 + 22404750/5959*t^9 + 137606217/5959*t^8 + 620455590/5959*t^7 + 2117653385/5959*t^6 + 5561311650/5959*t^5 + 11311600324/5959*t^4 + 17737953240/5959*t^3 + 21126074400/5959*t^2 + 18162144000/5959*t + 10378368000/5959)

$\mathcal{B}^5_2$ has over 3000 vertices. The other data is available upon request. Probably someone with better computer skills than me can produce more data.

This phenomenon whereby an Ehrhart quasipolynomial has a smaller period than a priori predicted, or in extreme cases is in fact an honest polynomial, is called Ehrhart period collapse. It has apparently attracted some attention but remains mysterious.

Even if the above question has a negative answer, I'd still be interested in what could be said about the integer points $t\mathcal{B}^n_r\cap \mathbb{Z}^{n\times n}$.

P.S., Happy New Year's and here's to a better 2021!

For $1 \leq r \leq n$, let $\mathcal{B}^n_r$ denote the polytope of all real matrices $$ \pi = \begin{pmatrix} \pi_{1,1} & \pi_{1,2} & \cdots & \pi_{1,n} \\ \pi_{2,1} & \ddots & \cdots & \pi_{2,n} \\ \vdots & \ddots & \ddots & \vdots \\ \pi_{n,1} & \cdots & \cdots & \pi_{n,n} \end{pmatrix} \in \mathbb{R}^{n\times n}$$ for which

• all entries are nonnegative: $\pi_{i,j}\geq 0$;
• the sum along any row or column is equal to one: $\sum_{j}\pi_{i,j}=1$ for all $i$; $\sum_{i}\pi_{i,j}=1$ for all $j$.
• the sum along any upper-left to lower-right chain of entries is at most $r$: $\sum_{k} \pi_{i_k,j_k} \leq r$ for all $(i_1,j_1)<(i_2,j_2) < \cdots < (i_m,j_m)$, where $(i,j) < (i',j')$ means $i\leq i'$, $j\leq j'$ with at least one of these inequalities being strict.

By definition $\mathcal{B}^n_n$ is the Birkhoff polytope of doubly-stochastic matrices. In general $\mathcal{B}^n_r$ is a subpolytope of the Birkhoff polytope.

It is well-known that $\mathcal{B}^n_n$ is the convex hull of all permutation matrices, and so in particular $\mathcal{B}^n_n$ is an integral polytope. But this is not true of the $\mathcal{B}^n_r$ in general: for instance, $$ \begin{pmatrix} 0.5 & 0 & 0.5 \\ 0 & 1 & 0 \\ 0.5 & 0 & 0.5 \end{pmatrix}$$ is a vertex of $\mathcal{B}^3_2$. The vertices of $\mathcal{B}^n_r$ which are integral are precisely the permutation matrices of $123...r+1$-avoiding permutations.

For a polytope $\mathcal{P} \subseteq \mathbb{R}^n$ I use $L(\mathcal{P};t)$ to denote the Ehrhart function which at nonnegative integers $t$ counts the number of lattice points of $t\mathcal{P}$: $$ L(\mathcal{P};t) := \# (t\mathcal{P}\cap \mathbb{Z}^n).$$

Since $\mathcal{B}^n_r$ is not an integral polytope, but it is a rational polytope, its Ehrhart function $L(\mathcal{B}^n_r;t)$ is a priori only a quasipolynomial in $t$.

Question: Is $L(\mathcal{B}^n_r;t)$ in fact always an honest polynomial in $t$?

I have verified this for $1\leq r \leq n \leq 5$ via Sage. The computation that took the longest was $L(\mathcal{B}^5_2;t)$ which is equal to

(5959/249080832000) * (t + 1) * (t + 2) * (t + 3) * (t + 4) * (t^12 + 30*t^11 + 2534915/5959*t^10 + 22404750/5959*t^9 + 137606217/5959*t^8 + 620455590/5959*t^7 + 2117653385/5959*t^6 + 5561311650/5959*t^5 + 11311600324/5959*t^4 + 17737953240/5959*t^3 + 21126074400/5959*t^2 + 18162144000/5959*t + 10378368000/5959)

$\mathcal{B}^5_2$ has over 3000 vertices. The other data is available upon request. Probably someone with better computer skills than me can produce more data.

This phenomenon whereby an Ehrhart quasipolynomial has a smaller period than a priori predicted, or in extreme cases is in fact an honest polynomial, is called Ehrhart period collapse. It has apparently attracted some attention but remains mysterious.

Even if the above question has a negative answer, I'd still be interested in what could be said about the integer points $t\mathcal{B}^n_r\cap \mathbb{Z}^{n\times n}$.

P.S., Happy New Year's and here's to a better 2021!

EDIT: This question and the answers are now in the paper https://arxiv.org/abs/2206.02276.

For $1 \leq r \leq n$, let $\mathcal{B}^n_r$ denote the polytope of all real matrices $$ \pi = \begin{pmatrix} \pi_{1,1} & \pi_{1,2} & \cdots & \pi_{1,n} \\ \pi_{2,1} & \ddots & \cdots & \pi_{2,n} \\ \vdots & \ddots & \ddots & \vdots \\ \pi_{n,1} & \cdots & \cdots & \pi_{n,n} \end{pmatrix} \in \mathbb{R}^{n\times n}$$ for which

• all entries are nonnegative: $\pi_{i,j}\geq 0$;
• the sum along any row or column is equal to one: $\sum_{j}\pi_{i,j}=1$ for all $i$; $\sum_{i}\pi_{i,j}=1$ for all $j$.
• the sum along any upper-left to lower-right chain of entries is at most $r$: $\sum_{k} \pi_{i_k,j_k} \leq r$ for all $(i_1,j_1)<(i_2,j_2) < \cdots < (i_m,j_m)$, where $(i,j) < (i',j')$ means $i\leq i'$, $j\leq j'$ with at least one of these inequalities being strict.

By definition $\mathcal{B}^n_n$ is the Birkhoff polytope of doubly-stochastic matrices. In general $\mathcal{B}^n_r$ is a subpolytope of the Birkhoff polytope.

It is well-known that $\mathcal{B}^n_n$ is the convex hull of all permutation matrices, and so in particular $\mathcal{B}^n_n$ is an integral polytope. But this is not true of the $\mathcal{B}^n_r$ in general: for instance, $$ \begin{pmatrix} 0.5 & 0 & 0.5 \\ 0 & 1 & 0 \\ 0.5 & 0 & 0.5 \end{pmatrix}$$ is a vertex of $\mathcal{B}^3_2$. The vertices of $\mathcal{B}^n_r$ which are integral are precisely the permutation matrices of $123...r+1$-avoiding permutations.

For a polytope $\mathcal{P} \subseteq \mathbb{R}^n$ I use $L(\mathcal{P};t)$ to denote the Ehrhart function which at nonnegative integers $t$ counts the number of lattice points of $t\mathcal{P}$: $$ L(\mathcal{P};t) := \# (t\mathcal{P}\cap \mathbb{Z}^n).$$

Since $\mathcal{B}^n_r$ is not an integral polytope, but it is a rational polytope, its Ehrhart function $L(\mathcal{B}^n_r;t)$ is a priori only a quasipolynomial in $t$.

Question: Is $L(\mathcal{B}^n_r;t)$ in fact always an honest polynomial in $t$?

I have verified this for $1\leq r \leq n \leq 5$ via Sage. The computation that took the longest was $$ L(\mathcal{B}^5_2;t) = (5959/249080832000) \cdot (t + 1) \cdot (t + 2) \cdot (t + 3) \cdot (t + 4) \cdot (t^12 + 30\cdot t^11 + 2534915/5959\cdot t^10 + 22404750/5959\cdot t^9 + 137606217/5959\cdot t^8 + 620455590/5959\cdot t^7 + 2117653385/5959\cdot t^6 + 5561311650/5959\cdot t^5 + 11311600324/5959\cdot t^4 + 17737953240/5959\cdot t^3 + 21126074400/5959\cdot t^2 + 18162144000/5959\cdot t + 10378368000/5959).$$ $\mathcal{B}^5_2$ has over 3000 vertices. The other data is available upon request. Probably someone with better computer skills than me can produce more data.

This phenomenon whereby an Ehrhart quasipolynomial has a smaller period than a priori predicted, or in extreme cases is in fact an honest polynomial, is called Ehrhart period collapse. It has apparently attracted some attention but remains mysterious.

Even if the above question has a negative answer, I'd still be interested in what could be said about the integer points $t\mathcal{B}^n_r\cap \mathbb{Z}^{n\times n}$.

P.S., Happy New Year's and here's to a better 2021!

For $1 \leq r \leq n$, let $\mathcal{B}^n_r$ denote the polytope of all real matrices $$ \pi = \begin{pmatrix} \pi_{1,1} & \pi_{1,2} & \cdots & \pi_{1,n} \\ \pi_{2,1} & \ddots & \cdots & \pi_{2,n} \\ \vdots & \ddots & \ddots & \vdots \\ \pi_{n,1} & \cdots & \cdots & \pi_{n,n} \end{pmatrix} \in \mathbb{R}^{n\times n}$$ for which

• all entries are nonnegative: $\pi_{i,j}\geq 0$;
• the sum along any row or column is equal to one: $\sum_{j}\pi_{i,j}=1$ for all $i$; $\sum_{i}\pi_{i,j}=1$ for all $j$.
• the sum along any upper-left to lower-right chain of entries is at most $r$: $\sum_{k} \pi_{i_k,j_k} \leq r$ for all $(i_1,j_1)<(i_2,j_2) < \cdots < (i_m,j_m)$, where $(i,j) < (i',j')$ means $i\leq i'$, $j\leq j'$ with at least one of these inequalities being strict.

By definition $\mathcal{B}^n_n$ is the Birkhoff polytope of doubly-stochastic matrices. In general $\mathcal{B}^n_r$ is a subpolytope of the Birkhoff polytope.

It is well-known that $\mathcal{B}^n_n$ is the convex hull of all permutation matrices, and so in particular $\mathcal{B}^n_n$ is an integral polytope. But this is not true of the $\mathcal{B}^n_r$ in general: for instance, $$ \begin{pmatrix} 0.5 & 0 & 0.5 \\ 0 & 1 & 0 \\ 0.5 & 0 & 0.5 \end{pmatrix}$$ is a vertex of $\mathcal{B}^3_2$. The vertices of $\mathcal{B}^n_r$ which are integral are precisely the permutation matrices of $123...r+1$-avoiding permutations.

For a polytope $\mathcal{P} \subseteq \mathbb{R}^n$ I use $L(\mathcal{P};t)$ to denote the Ehrhart function which at nonnegative integers $t$ counts the number of lattice points of $t\mathcal{P}$: $$ L(\mathcal{P};t) := \# (t\mathcal{P}\cap \mathbb{Z}^n).$$

Since $\mathcal{B}^n_r$ is not an integral polytope, but it is a rational polytope, its Ehrhart function $L(\mathcal{B}^n_r;t)$ is a priori only a quasipolynomial in $t$.

Question: Is $L(\mathcal{B}^n_r;t)$ in fact always an honest polynomial in $t$?

I have verified this for $1\leq r \leq n \leq 5$ via Sage. The computation that took the longest was $L(\mathcal{B}^5_2;t)$ which is equal to

(5959/249080832000) * (t + 1) * (t + 2) * (t + 3) * (t + 4) * (t^12 + 30*t^11 + 2534915/5959*t^10 + 22404750/5959*t^9 + 137606217/5959*t^8 + 620455590/5959*t^7 + 2117653385/5959*t^6 + 5561311650/5959*t^5 + 11311600324/5959*t^4 + 17737953240/5959*t^3 + 21126074400/5959*t^2 + 18162144000/5959*t + 10378368000/5959)

$\mathcal{B}^5_2$ has over 3000 vertices. The other data is available upon request. Probably someone with better computer skills than me can produce more data.

This phenomenon whereby an Ehrhart quasipolynomial has a smaller period than a priori predicted, or in extreme cases is in fact an honest polynomial, is called Ehrhart period collapse. It has apparently attracted some attention but remains mysterious.

Even if the above question has a negative answer, I'd still be interested in what could be said about the integer points $t\mathcal{B}^n_r\cap \mathbb{Z}^{n\times n}$.

P.S., Happy New Year's and here's to a better 2021!