# Ehrhart period collapse for $123\ldots k$-avoiding Birkhoff polytope?

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!

• The fact that all coefficients are positive is also surprising... Jan 1 '21 at 7:57
• Btw a different perspective is that this polytope is a subpolytope of (a dilate of) the chain polytope of $[n]\times[n]$. Jan 1 '21 at 19:19

The Ehrhart function $$L(\mathcal B^n_r;t)$$ is an honest polynomial. We will show this by following Per's suggestion and proving that it coincides with the Ehrhart function of a certain Gelfand-Tsetlin polytope. The following two steps can probably be combined into one, but I thought it was natural to think of it this way.

Step 1: For every $$k\in \mathbb N$$, the lattice points of $$k\mathcal B_r^n$$ are in bijection with the set of arrays $$\tau\in \mathbb Z_{\geq 0} ^{n\times n}$$ that are plane partitions, meaning that $$i\geq i', j\geq j'$$ implies $$\tau_{i,j}\le \tau_{i',j'}$$, that also satisfy $$kr\geq \tau_{1,1}$$ and for each $$-n\le s\le n$$ we have the traces $$tr_s(\tau)=\sum_{i}\tau_{i,i+s}=k(n-|s|).$$ Proof: This bijection is simply RSK applied to the array $$\pi$$. The entry $$\tau_{1,1}$$ records the length of longest increasing subsequence in the biword recording $$\pi$$, which is exactly the largest possible sum of $$\pi_{i,j}$$'s along an upper left-lower right chain. This is where the restriction $$kr\geq \tau_{1,1}$$ comes from.

Let's introduce the partitions $$\lambda^n_r=\{r^n0^n\}$$ and $$\mu^n_r=\{(r-1)^n1^n\}$$.

Step 2: The plane partitions from the previous lemma are in bijection with the lattice points in the Gelfand-Tsetlin polytope $$GT(k\lambda^n_r, k\mu^n_r)=kGT(\lambda^n_r, \mu^n_r)$$, therefore they are counted by the Kostka number $$K(k\lambda^n_r, k\mu^n_r)$$.

Proof: If we write a Gelfand-Tseltin pattern with top row given by $$k\lambda^n_r=\{kr,kr,\dots, kr, 0, 0,\dots, 0\}$$ we can erase the leftmost entries that are forced to be $$=kr$$ and the rightmost entries that are forced to be $$=0$$ to be left with a ($$45^{\circ}$$ rotated) $$n\times n$$ array. This array is a plane partition with largest part $$\le kr$$ and the appropriate traces.

For $$k\mathcal B^{4}_2$$ this bijection looks like simply selecting the array of $$*$$'s. $$\begin{matrix} 2k && 2k && 2k && 2k && 0 && 0 && 0 && 0\\ & 2k && 2k && 2k && * && 0 && 0 && 0 \\ && 2k && 2k && * && * && 0 && 0\\ &&& 2k && * && * && * && 0 \\ &&&& * && * && * && * \\ &&&&& * && * && * \\ &&&&&& * && * \\ &&&&&&& * \end{matrix}$$

Combining both steps gives $$L(\mathcal B^n_r ;t)=L(GT(\lambda^n_r, \mu^n_r);t)$$ which implies the desired polynomiality. It is also expected that positivity of coefficients holds, but I believe it is not known yet.

• This is excellent! Jan 17 '21 at 1:10
• By the way, in case you're interested in the context in which I started thinking about this polytope, if $P$ is the poset corresponding to the staircase Young diagram $(n-1,n-2,\ldots,1)$, then there is a certain "natural" embedding of $\mathcal{C}(P)$, the chain polytope of $P$, into $\mathcal{B}^{n}_2$; and in particular points in $\frac{1}{m}\mathbb{Z}^{P}\cap\mathcal{C}(P)$ to points in $\frac{1}{m}\mathbb{Z}^{n\times n} \cap \mathcal{B}^{n}_2$ (see Section 6.3 of arxiv.org/abs/2012.15795). Jan 17 '21 at 2:07
• There's a product formula for $\#\frac{1}{m}\mathbb{Z}^{P}\cap\mathcal{C}(P)$, i.e., the Ehrhart polynomial of $\mathcal{C}(P)$, due to Proctor (phrased in terms of staricase plane partitions). For $m=1$ the above embedding hits all the rational points, but not for $m>1$, so I wanted to count those to see how many more there are. Jan 17 '21 at 2:08
• @SamHopkins Fascinating! Can the embedding be used to give a different proof for the order polynomial of $P$? Jan 17 '21 at 2:30
• I'm not sure about that. For our purposes the point was that these rational points of both polytopes carry a natural cyclic group action (called "picewise-linear rowmotion"), and the embedding is equivariant with respect to that action (essentially, that's how it's defined). Jan 17 '21 at 2:34

I strongly suspect that the polytope in question is type of a (skew) Gelfand-Tsetlin polytope. The corresponding Ehrhart functions are polynomials, even though the polytopes are non-integral in general.

The classical Birkhoff polytope is an example of this; you can get it from skew Kostka polynomials associated with the skew shape, which consists of $$n$$ disconnected boxes. Dilation of the polytope with factor $$k$$ corresponds to having $$n$$ disjoint rows of length $$k$$.

Moreover, it is conjectured that the Ehrhart polynomials here always have non-negative coefficients (in fact, a more general conjecture states this for the Berenstein-Zelevinsky polytopes).

• Good point about GT polytopes, Per! Although I don't quite see the realization yet... Jan 1 '21 at 16:36
• @SamHopkins The connection between Koska coefficients and the Birkhoff polytope is described in section 8, in my paper here: sciencedirect.com/science/article/pii/… (although I am sure this was known much earlier). Jan 1 '21 at 19:02