Newton polytopes in algebraic combinatorics

Abstract

A polynomial has saturated Newton polytope (SNP) if every lattice point of the convex hull of its exponent vectors corresponds to a monomial. We compile instances of SNP in algebraic combinatorics (some with proofs, others conjecturally): skew Schur polynomials; symmetric polynomials associated to reduced words, Redfield–Pólya theory, Witt vectors, and totally nonnegative matrices; resultants; discriminants (up to quartics); Macdonald polynomials; key polynomials; Demazure atoms; Schubert polynomials; and Grothendieck polynomials, among others. Our principal construction is the Schubitope. For any subset of $[n]^2$, we describe it by linear inequalities. This generalized permutahedron conjecturally has positive Ehrhart polynomial. We conjecture it describes the Newton polytope of Schubert and key polynomials. We also define dominance order on permutations and study its poset-theoretic properties.

1 Introduction

The Newton polytope of a polynomial $f=\sum _{\alpha \in {\mathbb {Z}}_{\ge 0}^n}c_{\alpha } x^{\alpha }\in {\mathbb {C}}[x_1,\ldots ,x_n]$ is the convex hull of its exponent vectors, i.e.,

$$\begin{aligned} \textsf { Newton}(f)=\mathrm{conv}(\{\alpha :c_{\alpha }\ne 0\})\subseteq {\mathbb {R}}^n. \end{aligned}$$

Definition 1.1

f has saturated Newton polytope (SNP) if $c_{\alpha }\ne 0$ whenever $\alpha \in \textsf { Newton}(f)$.

Example 1.2

$f=$ the determinant of a generic $n\times n$ matrix. The exponent vectors correspond to permutation matrices. $\textsf { Newton}(f)$ is the Birkhoff polytope of $n\times n$ doubly stochastic matrices. SNPness says there are no additional lattice points, which is obvious here. (The Birkhoff–von Neumann theorem states all lattice points are vertices.) $\square$

Generally, polynomials are not SNP. Worse still, SNP is not preserved by basic polynomial operations. For example, $f=x_1^2+x_2x_3+x_2x_4+x_3x_4$ is SNP but $f^2$ is not (it misses $x_1 x_2 x_3 x_4$). Nevertheless, there are a number of families of polynomials in algebraic combinatorics where every member is (conjecturally) SNP. Examples motivating our investigation include:

• The Schur polynomials are SNP. This rephrases R. Rado’s theorem [35] about permutahedra and dominance order on partitions; cf. Proposition 2.5.

• Classical resultants are SNP (Theorem 2.20). Their Newton polytopes were studied by I. M. Gelfand-M. Kapranov-A. Zelevinsky [16]. (Classical discriminants are SNP up to quartics — but not quintics; see Proposition 2.23.)

• Cycle index polynomials from Redfield–Pólya theory (Theorem 2.30)

• C. Reutenauer’s symmetric polynomials linked to the free Lie algebra and to Witt vectors [37] (Theorem 2.32)

• J. R. Stembridge’s symmetric polynomials associated to totally nonnegative matrices [44] (Theorem 2.28)

• R. P. Stanley’s symmetric polynomials [40], introduced to enumerate reduced words of permutations (Theorem 5.8)

• Any generic (q, t)-evaluation of a symmetric Macdonald polynomial is SNP; see Theorem 3.1 and Proposition 3.6.

• The key polynomials are $(\infty ,\infty )$-specializations of non-symmetric Macdonald polynomials. These also seem to be SNP. We give two conjectural descriptions of the Newton polytopes. We determine a list of vertices of the Newton polytopes (Theorem 3.12) and conjecture this list is complete (Conjecture 3.13).

• Schubert polynomials (Conjecture 5.1). We conjecturally describe the Newton polytope (Conjecture 5.13).

• Inhomogeneous versions of Schuberts/keys are also conjecturally SNP (Conjectures 5.5 and 5.6).

The core part of our study concerns the Schubert and key polynomials. We conjecture a description of their Newton polytopes in terms of a new family of polytopes.

A diagram $\textsf {D}$ is a subset boxes of an $n \times n$ grid. Fix $S\subseteq [n]:=\{1,2,\ldots ,n\}$ and a column $c \in [n]$. Let $\mathtt{word}_{c,S}(\textsf {D})$ be formed by reading c from top to bottom and recording

• ( if $(r,c) \notin \textsf {D}$ and $r \in S$,

• ) if $(r,c) \in \textsf {D}$ and $r \notin S$, and

• $\star$ if $(r,c) \in \textsf {D}$ and $r \in S$.

(Nothing is recorded if $(r,c)\not \in D$ and $r\not \in S$.) For $\textsf {D}$ shown above, $\mathtt{word}_{2,\{1,2\}}(\textsf {D})=$“$(\ \star \ )$”, $\mathtt{word}_{3,\{1,2,3,4\}}(\textsf {D})=$“$\star \ (( \ \star$”, $\mathtt{word}_{3,\{1,2\}}(\textsf {D})=$“$\star \ (\ )$”, and $\mathtt{word}_{3,\{2,3\}}(\textsf {D})=$“$)\ (\ (\ )$”. Let

$$\begin{aligned} \theta _\textsf {D}^c(S)= \#\text {paired }(\ )\text {'s in }\mathtt{word}_{c,S}(\textsf {D}) + \#\star \text {'s in }{} \mathtt{word}_{c,S}(\textsf {D}). \end{aligned}$$

Set $\theta _\textsf {D}(S) = \sum _{c \in [n]} \theta _\textsf {D}^c(S)$. For instance, $\theta _\textsf {D}(\{ 2,4 \}) = 4$ above. Define the Schubitope as

$$\begin{aligned} {\mathcal {S}}_\textsf {D}=\left\{ (\alpha _1,\ldots ,\alpha _n)\in {\mathbb R}_{\ge 0}^n: \sum _{i=1}^n \alpha _i=\#\textsf {D} \text { and } \sum _{i\in S}\alpha _i \le \theta _\textsf {D}(S) \text { for all }S \subset [n]\right\} . \end{aligned}$$

Fix a partition $\lambda =(\lambda _1,\lambda _2,\ldots ,\lambda _n)$. The $\lambda$-permutahedron, denoted ${\mathcal {P}}_{\lambda }$, is the convex hull of the $S_n$-orbit of $\lambda$ in ${\mathbb {R}}^n$. The Schubitope is a generalization of the permutahedron (Proposition 5.23). We conjecture that the Schubitope for a skyline diagram and for a Rothe diagram respectively are the Newton polytopes of a key and Schubert polynomial. The figure to above depicts ${\mathcal {S}}_{\textsf {D}_{21543}}$, which is a three-dimensional convex polytope in ${\mathbb {R}}^4$. Conjecture 5.19 asserts that Ehrhart polynomials of Schubitopes ${\mathcal {S}}_{\textsf {D}_w}$ have positive coefficients; cf. [9, Conjecture 1.2].

A cornerstone of the theory of symmetric polynomials is the combinatorics of Littlewood–Richardson coefficients. An important special case of these numbers are the Kostka coefficients $\textsf {K}_{\lambda ,\mu }$. The nonzeroness of $\textsf { K}_{\lambda ,\mu }$ is governed by dominance order which is defined by the linear inequalities (2). Alternatively, Rado’s theorem [35, Theorem 1] states this order characterizes when ${\mathcal {P}}_{\mu }\subseteq {\mathcal {P}}_{\lambda }$. These two viewpoints on dominance order are connected since ${\mathcal {P}}_{\lambda }$ is the Newton polytope of the Schur polynomial $s_{\lambda }(x_1,x_2,\ldots ,x_n)$.

For Schubert polynomials, there is no analogous Littlewood–Richardson rule. However, with a parallel in mind, we propose a “dominance order for permutations” via Newton polytopes. The inequalities of the Schubitope generalize (2); see Proposition 5.23.

1.1 Organization

Section 2 develops and applies basic results about SNP symmetric polynomials. Section 3 turns to flavors of Macdonald polynomials and their specializations, including the key polynomials and Demazure atoms. Section 4 concerns quasisymmetric functions. Monomial quasisymmetric and Gessel’s fundamental quasisymmetric polynomials are not SNP, but have equal Newton polytopes. The quasisymmetric Schur polynomials [20] are also not SNP, which demonstrates a qualitative difference with Schur polynomials. Section 5 discusses Schubert polynomials and a number of variations. We define dominance order for permutations and study its poset-theoretic properties. We connect the Schubitope to work of A. Kohnert [22] and explain a salient contrast (Remark 5.21). Section 6 lists some advances connected to this paper since initial submission.

2 Symmetric functions

2.1 Preliminaries

The monomial symmetric polynomial for a partition $\lambda$ is

$$\begin{aligned} m_{\lambda }=\sum _{\alpha } x_1^{\alpha _1}x_2^{\alpha _2}\cdots x_n^{\alpha _n} \end{aligned}$$

where the sum is over distinct rearrangements of $\lambda$. The set $\{m_{\lambda }\}_{\ell (\lambda )\le n}$ forms a ${\mathbb {Z}}$-basis of $\textsf { Sym}_n$, the ring of symmetric polynomials in $x_1,x_2,\ldots ,x_n$ (here $\ell (\lambda )$ is the number of nonzero parts of $\lambda$).

Identify a partition $\lambda$ with its Young diagram (in English notation). A semistandard Young tableau T is a filling of $\lambda$ with entries from ${\mathbb {Z}}_{>0}$ that is weakly increasing along rows and strictly increasing down columns. The content of T is $\mu =(\mu _1,\mu _2,\ldots ,\mu _n)$ where $\mu _i$ is the number of i’s appearing in T. The Schur polynomial is

$$\begin{aligned} s_{\lambda }=\sum _{\mu }\textsf { K}_{\lambda ,\mu }m_{\mu } \end{aligned}$$

(1)

where $\textsf { K}_{\lambda ,\mu }$ is the number of semistandard Young tableaux of shape $\lambda$ and content $\mu$.

Let $\textsf { Par}(d)=\{\lambda :\lambda \vdash d\}$ be the set of partitions of size d. Dominance order $\le _D$ on $\textsf { Par}(d)$ is defined by

$$\begin{aligned} \mu \le _{D} \lambda \text { if } \sum _{i=1}^k\mu _i\le \sum _{i=1}^k\lambda _i \text { for all }k\ge 1. \end{aligned}$$

(2)

Recall this result about tableaux (see e.g., [42, Proposition 7.10.5 and Exercise 7.12]):

$$\begin{aligned} \textsf { K}_{\lambda ,\mu } \ne 0 \iff \mu \le _D \lambda . \end{aligned}$$

(3)

Since $\textsf { K}_{\lambda ,\lambda }=1$, it follows from (1) and (3) combined that $\{s_{\lambda }\}_{\ell (\lambda ) \le n}$ also forms a basis of $\textsf { Sym}_n$.

Setting $x_{n+1}=0$ defines a surjective homomorphism $\textsf { Sym}_{n+1}\twoheadrightarrow \textsf { Sym}_n$ for each $n\ge 0$. Let $\textsf { Sym}$ denote $\underset{n}{\varprojlim }\ \textsf { Sym}_n$, the ring of symmetric functions in $x_1,x_2,\ldots$. We refer the reader to [42, Chapter 7] for additional background.

2.2 Basic facts about SNP

Given $f\in \textsf { Sym}$, let $f(x_1,\ldots ,x_n)\in \textsf { Sym}_n$ be the specialization that sets $x_{i}=0$ for $i\ge n+1$. Whether $f(x_1,\ldots ,x_n)$ is SNP depends on n (e.g., $f=\sum _i x_i^2$).

Definition 2.1

$f\in \textsf { Sym}$ is SNP if $f(x_1,\ldots ,x_m)$ is SNP for all $m\ge 1$.

Proposition 2.2

(Stability of SNP) Suppose $f\in \textsf { Sym}$ has finite degree. Then f is SNP if there exists $m\ge \deg (f)$ such that $f(x_1,\ldots ,x_m)$ is SNP.

Proof

We first show that if $f(x_1,\ldots ,x_m)$ is SNP, $f(x_1,\ldots ,x_n)$ is SNP for any $n \le m$. Suppose $\alpha \in \mathtt{Newton}(f(x_1,\ldots ,x_n))$. Let $\overline{\alpha }\in {\mathbb {R}}^m$ be $\alpha$ with $m-n$ many 0’s adjoined to the end. Since $\alpha$ is a convex linear combination of exponent vectors $\beta$ of $f(x_1,\ldots ,x_n)$, and each $\overline{\beta }$ is an exponent vector of $f(x_1,\ldots ,x_m)$, then $\overline{\alpha }\in \mathtt{Newton}(f(x_1,\ldots ,x_m))$. Since $f(x_1,\ldots ,x_m)$ is SNP, $x^{\overline{\alpha }}$ is a monomial of $f(x_1,\ldots ,x_m)$. Thus $x^{\overline{\alpha }}$ is a monomial of $f(x_1,\ldots ,x_n,0,\ldots ,0)$ and hence $x^{\alpha }$ is a monomial of $f(x_1,\ldots ,x_n)$, as desired.

To complete the proof, we now show if $f(x_1,\ldots ,x_m)$ for $m \ge \deg (f)$ is SNP, then $f(x_1,\ldots ,x_n)$ is SNP for all $n \ge m$. Suppose $\alpha \in \mathtt{Newton}(f(x_1,\ldots ,x_n))$ and thus

$$\begin{aligned} \alpha = \sum _i c_i \beta ^i \end{aligned}$$

(4)

where $x^{\beta ^i}$ is a monomial of f. Since $\alpha \in {\mathbb Z}_{\ge 0}^n$, by (4), there are at most $\deg (f)\le m$ coordinates where $\alpha _j > 0$, say $j_1,\ldots ,j_m$. Furthermore, since each $\beta ^i$ is nonnegative, if $c_i > 0$, $\beta _j^i = 0$ for $j \ne j_1, \ldots , j_m$. Choose $w \in S_n$ such that $w(j_c) = c$ for $c = 1,\ldots ,m$. Applying w to (4) gives

$$\begin{aligned} w(\alpha ) = \sum _i c_i w(\beta ^i). \end{aligned}$$

So nonzero coordinates of $w(\alpha )$ only occur in positions $1, \ldots , m$. Since $f\in \textsf { Sym}$, each $x^{w(\beta ^i)}$ is a monomial of $f(x_1,\ldots ,x_m)$, and so $w(\alpha ) \in \mathtt{Newton}(f(x_1,\ldots ,x_m))$. Since $f(x_1,\ldots ,x_m)$ is SNP, $[x^{w(\alpha )}]f\ne 0$. Again, $f\in \textsf { Sym}$ implies $[x^\alpha ]f\ne 0$. Hence, $f(x_1,\ldots ,x_n)$ is SNP. $\square$

Remark 2.3

In the proof of Proposition 2.2, w is chosen so that the nonzero components of the vectors $\alpha$ and $w(\alpha )$ are in the same relative order. Thus the result extends to the quasisymmetric case of Sect. 4.$\square$

Remark 2.4

The stabilization constant $\deg (f)$ is tight. Let $f=s_{\lambda }-\textsf { f}^{\lambda }m_{(1^{|\lambda |})}$. Here $\textsf { f}^{\lambda }=[m_{(1^{|\lambda |})}]s_{\lambda }$ (=  the number of standard Young tableaux of shape $\lambda$.) Then $f(x_1,\ldots ,x_n)$ is SNP for $n<|\lambda |=\deg (f)$ but not SNP for $n\ge |\lambda |$. One can see this from the ideas in the next proposition.

Proposition 2.5

Suppose $f\in \textsf { Sym}_n$ is homogeneous of degree d such that

$$\begin{aligned} f = \sum _{\mu \in \textsf { Par}(d)} c_\mu s_\mu . \end{aligned}$$

Suppose there exists a $\lambda$, such that $c_{\lambda }\ne 0$ and $c_\mu \ne 0$ only if $\mu \le _D \lambda$. If $n < \ell (\lambda )$, $f = 0$. Otherwise:

• (I) $\textsf { Newton}(f) = {\mathcal {P}}_{\lambda }\subset {\mathbb {R}}^n$.

• (II) The vertices of $\textsf { Newton}(f)$ are rearrangements of $\lambda$.

• (III) If moreover $c_{\mu }\ge 0$ for all $\mu$, f has SNP.

Proof

If $\mu \le _D \lambda$, $\ell (\mu ) \ge \ell (\lambda )$. Thus if $n < \ell (\lambda )$, $s_\mu (x_1,\ldots ,x_n) \equiv 0$ for all $\mu$ such that $c_\mu \ne 0$. Otherwise, suppose $n \ge \ell (\lambda )$.

(I): Since $\displaystyle f = \sum _{\mu \le _D \lambda } c_\mu s_\mu$, by (3) we have

$$\begin{aligned} f=\sum _{\mu \le _D\lambda } d_{\mu } m_{\mu }. \end{aligned}$$

Clearly,

$$\begin{aligned} \textsf { Newton}(m_\mu (x_1,\ldots ,x_n)) = {\mathcal {P}}_{\mu }\subset {\mathbb {R}}^n \end{aligned}$$

(5)

(by the definitions of both). Also,

$$\begin{aligned} \textsf { Newton}(f+g)=\textsf { conv}(\textsf { Newton}(f)\cup \textsf { Newton}(g)). \end{aligned}$$

Hence,

$$\begin{aligned} \textsf { Newton}(f) = \mathrm{conv}\left( \bigcup _{\mu \le _D \lambda } \textsf { Newton}(m_\mu )\right) = \mathrm{conv}\left( \bigcup _{\mu \le _D \lambda } {\mathcal {P}}_{\mu }\right) . \end{aligned}$$

R. Rado’s theorem [35, Theorem 1] states:

$$\begin{aligned} {\mathcal {P}}_{\mu } \subseteq {\mathcal {P}}_{\lambda }\iff \mu \le _D \lambda . \end{aligned}$$

(6)

Now $\textsf { Newton}(f) = {\mathcal {P}}_{\lambda }$ holds by (6), proving (I).

(II): In view of (I), it suffices to know this claim for ${\mathcal P}_{\lambda }$. This is well-known, but we include a proof for completeness.

Since ${\mathcal {P}}_{\lambda }$ is the convex hull of the $S_n$-orbit of $\lambda$, any vertex of ${\mathcal {P}}_{\lambda }$ is a rearrangement of $\lambda$. It remains to show that every such rearrangement $\beta$ is in fact a vertex. Thus it suffices to show there is no nontrivial convex combination

$$\begin{aligned} \beta = \sum _{\gamma } c_\gamma \gamma , \end{aligned}$$

(7)

where the sum is over distinct rearrangements $\gamma \ne \beta$ of $\lambda$.

Let $\lambda = (\Lambda _1^{k_1}\ldots \Lambda _m^{k_m})$ with $\Lambda _1> \Lambda _2> \cdots > \Lambda _m$. Since $\beta$ is a rearrangement of $\lambda$, let $i_1^1, \ldots , i_{k_1}^1$ be the positions in $\beta$ of the $k_1$ parts of size $\Lambda _1$. Since $\gamma _{i_j^1}\le \Lambda _1$ for all $\gamma$ we have that $c_{\gamma } = 0$ whenever $\gamma$ satisfies $\gamma _{i_j^1}\ne \Lambda _1$ for any $1\le j\le k_1$.

Let $i_1^2, \ldots , i_{k_2}^2$ be the positions in $\beta$ of the $k_2$ parts of size $\Lambda _2$. Similarly, $c_{\gamma }=0$ whenever $\gamma$ satisfies $\gamma _{i_j^2}\ne \Lambda _2$ for any $1\le j\le k_2$. Continuing, we see that $c_{\gamma }= 0$ for all $\gamma \ne \beta$. That is, there is no convex combination (7), as desired.

(III): Suppose $\alpha$ is a lattice point in $\textsf { Newton}(f) = {\mathcal P}_{\lambda }\subset {\mathbb {R}}^{n}.$ Let $\lambda (\alpha )$ be the rearrangement of $\alpha$ into a partition. By symmetry, ${\mathcal {P}}_{\lambda (\alpha )} \subseteq {\mathcal P}_{\lambda }$. Then by (6), $\lambda (\alpha ) \le _D \lambda$ and so by (3), $\textsf { K}_{\lambda ,\lambda (\alpha )} \ne 0$. Since $x^\alpha$ appears in $m_{\lambda (\alpha )}(x_1,\ldots ,x_n)$, $x^\alpha$ appears in $f(x_1,\ldots ,x_n)$ (here we are using the Schur positivity of f and the fact $\ell (\lambda (\alpha ))\le n$). Thus f is SNP. $\square$

Example 2.6

(Schur positivity does not imply SNP) Let

$$\begin{aligned} f=s_{(8,2,2)}+ s_{(6,6)}. \end{aligned}$$

It is enough to show $f(x_1,x_2,x_3)$ is not SNP. Now, $m_{(8,2,2)}(x_1,x_2,x_3)$ and $m_{(6,6)}(x_1,x_2,x_3)$ appear in the monomial expansion of $f(x_1,x_2,x_3)$. However, $m_{(7,4,1)}(x_1,x_2,x_3)$ is not in $f(x_1,x_2,x_3)$ since (7, 4, 1) is not $\le _D$-comparable with (8, 2, 2) nor (6, 6, 0). Yet, $(7,4,1)=\frac{1}{2}(8,2,2)+\frac{1}{2}(6,6,0)\in \textsf { Newton}(f(x_1,x_2,x_3))$. Hence f is not SNP. $\square$

Example 2.7

The Schur positivity assumption in Proposition 2.5(III) is necessary:

$$\begin{aligned} f=s_{(3,1)}(x_1,x_2)-s_{(2,2)}(x_1,x_2)=x_1^3x_2+x_1x_2^3 \end{aligned}$$

is not SNP. $\square$

Example 2.8

$f\in \textsf { Sym}$ can be SNP without a unique $\le _D$-maximal term. For example,

$$\begin{aligned} f=s_{(2,2,2)}+s_{(3,1,1,1)} \end{aligned}$$

is SNP but (2, 2, 2) and (3, 1, 1, 1) are $\le _D$-incomparable. An instance of this from “nature” is found in Example 2.34.$\square$

Proposition 2.9

(Products of Schur polynomials are SNP) $s_{\lambda ^{(1)}}s_{\lambda ^{(2)}}\cdots s_{\lambda ^{(N)}}\in \textsf { Sym}$ is SNP for any partitions $\lambda ^{(1)},\ldots ,\lambda ^{(N)}$.

Proof

We have

$$\begin{aligned} s_{\lambda }s_{\mu }=\sum _{\nu } \textsf { LR}_{\lambda ,\mu }^{\nu }s_{\nu }\in \textsf { Sym}, \end{aligned}$$

where $\textsf { LR}_{\lambda ,\mu }^{\nu }\in {\mathbb {Z}}_{\ge 0}$ is the Littlewood–Richardson coefficient. By homogeneity, clearly $\textsf { LR}_{\lambda ,\mu }^{\nu }=0$ unless $|\nu |=|\lambda |+|\mu |$. Let $\lambda +\mu =(\lambda _1+\mu _1,\lambda _2+\mu _2,\ldots )$. It suffices to show $\nu \le _D \lambda +\mu$ whenever $\textsf { LR}_{\lambda ,\mu }^{\nu }\ge 0$. Actually, we show $s_{\lambda +\mu }$ is the unique $\le _D$-maximal term in the Schur expansion of $s_{\lambda }e_{\mu '}$. Indeed, since $e_{\mu '}=s_{\mu }+\text {(positive sum of Schur functions)}$, this will suffice. The strengthening holds by an easy induction on the number of nonzero parts of $\mu$ and the Pieri rule (in the form of [42, Example 7.15.8]). Alternatively, this is straightforward to prove from the Littlewood–Richardson rule. Iterating this argument shows that $s_{\lambda ^{(1)}}\cdots s_{\lambda ^{(N)}}$ has unique $\le _D$ maximal term $s_{\lambda ^{(1)}+\cdots + \lambda ^{(N)}}$ and hence is SNP. $\square$

Let

$$\begin{aligned} p_{k}=\sum _{i=1}^n x_i^k \end{aligned}$$

be the power sum symmetric polynomial. Moreover, let

$$\begin{aligned} p_{\lambda }:=p_{\lambda _1}p_{\lambda _2}\cdots . \end{aligned}$$

Proposition 2.10

Let

$$\begin{aligned} f=\sum _{\lambda \vdash n} c_{\lambda } p_{\lambda }\in \textsf { Sym} \end{aligned}$$

be not identically zero. Assume $c_{\lambda }\ge 0$ for all $\lambda$, and that f is Schur positive. Then f is SNP.

Proof

Recall, (n) indexes the trivial representation of $S_n$ that sends each $\pi \in S_n$ to the $1\times 1$ identity matrix. The character value $\chi ^{(n)}(\mu )$, being the trace of this matrix, is independent of $\pi$’s conjugacy class $\mu \vdash n$. Hence $\chi ^{(n)}(\mu )=1$.

We have

$$\begin{aligned} p_{\mu }=\sum _{\lambda }\chi ^{\lambda }(\mu )s_{\lambda }. \end{aligned}$$

Therefore,

$$\begin{aligned} f=\sum _{\lambda \vdash n}c_{\lambda }p_{\lambda }=\left( \sum _{\lambda \vdash n}c_{\lambda }\right) s_{(n)}+\sum _{\lambda \ne (n)} d_{\lambda }s_{\lambda }. \end{aligned}$$

By hypothesis, each $c_{\lambda }\ge 0$. Since $f\not \equiv 0$, some $c_{\lambda }>0$ and hence $s_{(n)}$ appears. Now, (n) is the (unique) maximum in $(\textsf { Par}(n),\le _D)$. Also, since f is Schur positive, each $d_{\lambda }\ge 0$. Hence the result follows from Proposition 2.5(III). $\square$

Let

$$\begin{aligned} \omega :\textsf { Sym}\rightarrow \textsf { Sym} \end{aligned}$$

be the involutive automorphism defined by

$$\begin{aligned} \omega (s_{\lambda })=s_{\lambda '}, \end{aligned}$$

where $\lambda '$ is the shape obtained by transposing the Young diagram of $\lambda$.

Example 2.11

($\omega$ does not preserve SNP) Example 2.6 shows $f=s_{(8,2,2)}+s_{(6,6)}\in \textsf { Sym}$ is not SNP. Now

$$\begin{aligned} \omega (f)=s_{(3,3,1,1,1,1,1,1)}+s_{(2,2,2,2,2,2)}\in \textsf { Sym}. \end{aligned}$$

To see that $\omega (f)$ is SNP, it suffices to show that any partition $\nu$ that is is a linear combination of rearrangements of $\lambda =(3,3,1,1,1,1,1,1)$ and $\mu =(2,2,2,2,2,2)$ satisfies $\nu \le _D \lambda$ or $\nu \le _D\mu$. We leave the details to the reader. $\square$

2.3 Examples and counterexamples

Example 2.12

(Monomial symmetric and forgotten symmetric polynomials) It is immediate from (5) and (6) that

$$\begin{aligned} m_{\lambda }\in \textsf { Sym} \text { is SNP }\iff \lambda =(1^n). \end{aligned}$$

The forgotten symmetric functions are defined by

$$\begin{aligned} f_{\lambda }=\varepsilon _{\lambda }\omega (m_{\lambda }) \end{aligned}$$

where $\varepsilon _{\lambda }=(-1)^{|\lambda |-\ell (\lambda )}$.

Proposition 2.13

$f_{\lambda }\in \textsf { Sym}$ is SNP if and only if $\lambda =(1^n)$.

Proof

($\Leftarrow$) If $\lambda =(1^n)$ then $m_{\lambda }=s_{(1^n)}$ and $f_\lambda =s_{(n,0,0,\ldots ,0)}$ which is SNP.

($\Rightarrow$) We use the following formula [42, Exercise 7.9]:

$$\begin{aligned} f_{\lambda }=\sum _{\mu } a_{\lambda \mu } m_{\mu } \end{aligned}$$

where $a_{\lambda \mu }$ is the number of distinct rearrangements $(\gamma _1,\ldots ,\gamma _{\ell (\lambda )})$ of $\lambda =(\lambda _1,\ldots ,\lambda _{\ell (\lambda )})$ such that

$$\begin{aligned} \left\{ \sum _{s=1}^{i}\gamma _s:1\le i\le \ell (\lambda )\right\} \supseteq \left\{ \sum _{t=1}^j \mu _t: 1\le j\le \ell (\mu )\right\} . \end{aligned}$$

(8)

Suppose $\lambda \ne (1^n)$. If $\mu =(1^n)$ then

$$\begin{aligned} \left\{ \sum _{t=1}^j \mu _t: 1\le j\le \ell (\mu )\right\} =\{1,2,3,\ldots ,n\}. \end{aligned}$$

On the other hand, $\ell (\lambda )<n$ and hence the set on the lefthand side of (8) has size strictly smaller than n. Thus $a_{\lambda ,(1^n)}=0$.

Now, $(1^n)\in {\mathcal {P}}_{\mu }$ for all $\mu =(\mu _1,\ldots ,\mu _n)\vdash n$. Then since $f_{\lambda }$ is m-positive, $(1^n)\in \textsf { Newton}(f_{\lambda })$ so long as we are working in at least $\deg (f_{\lambda })$ many variables. If $\lambda \ne (1^n)$ then $a_{\lambda ,(1^n)}=0$ means $(1^n)$ is not an exponent vector of $f_{\lambda }$. This proves the contrapositive of ($\Rightarrow$). $\square$

Example 2.14

(Elementary and complete homogeneous symmetric polynomials) The elementary symmetric polynomial is defined by

$$\begin{aligned} e_k(x_1,\ldots ,x_n)=\sum _{1\le i_1<i_2<\ldots <i_k\le n} x_{i_1}x_{i_2}\cdots x_{i_k}. \end{aligned}$$

Also define

$$\begin{aligned} e_{\lambda }=e_{\lambda _1}e_{\lambda _2}\cdots \end{aligned}$$

The complete homogeneous symmetric polynomial $h_k(x_1,\ldots ,x_n)$ is the sum of all degree k monomials. Also define

$$\begin{aligned} h_{\lambda }=h_{\lambda _1}h_{\lambda _2}\cdots . \end{aligned}$$

Proposition 2.15

Each $e_{\lambda }$ and $h_{\lambda }$ is SNP.

Proof

Since $e_k=s_{(1^k)}$ and $h_k=s_{(k)}$ the claim holds by Proposition 2.9. $\square$

The Minkowski sum of two polytopes ${\mathcal {P}}$ and ${\mathcal {Q}}$ is

$$\begin{aligned} {\mathcal {P}}+{\mathcal {Q}}=\{p+q:p\in {\mathcal {P}},q\in {\mathcal {Q}}\}. \end{aligned}$$

It is a basic fact (see, e.g., [45, (1.6)]) that

$$\begin{aligned} \textsf { Newton}(f\cdot g)=\textsf { Newton}(f)+\textsf { Newton}(g). \end{aligned}$$

By the Pieri rule,

$$\begin{aligned} e_{(1)}(x_1,\ldots ,x_n)^k=\sum _{\lambda } \textsf { f}^{\lambda } s_{\lambda }(x_1,\ldots ,x_n). \end{aligned}$$

In particular $s_{(k,0,\ldots ,0)}$ appears on the right hand side. Since $\lambda \le _D (k)$ for all $\lambda \vdash k$, by Proposition 2.5(I) one recovers that the Minkowski sum of k regular simplices in ${\mathbb {R}}^n$ is ${\mathcal {P}}_{(k,0,\ldots ,0)}$. Similarly, by the argument of Proposition 2.9, ${\mathcal {P}}_{\lambda }=\textsf { Newton}(e_{\lambda '})$ and hence one recovers that ${\mathcal P}_{\lambda }$ is a Minkowski sum of hypersimplices. For earlier work see, e.g., [2, 10, 33].$\square$

Example 2.16

(e-Positivity does not imply SNP) $f\in \textsf { Sym}$ is e -positive if $f=\sum _{\lambda }a_{\lambda } e_{\lambda }$ where $a_{\lambda }\ge 0$ for every $\lambda$. (Since

$$\begin{aligned} e_{\lambda }=\sum _{\mu }\textsf { K}_{\mu ',\lambda }s_{\mu }, \end{aligned}$$

e-positivity implies Schur positivity.) Look at

$$\begin{aligned} f=e_{(3,3,1,1,1,1,1,1)}+ e_{(2,2,2,2,2,2)} \in \textsf { Sym}. \end{aligned}$$

In the monomial expansion, $m_{(8,2,2)}$ and $m_{(6,6)}$ appear. However, $m_{(7,4,1)}$ does not appear. This implies f is not SNP.$\square$

Example 2.17

(More on power sum symmetric polynomials) Recall the power sum symmetric polynomials defined immediately before Proposition 2.10. Clearly $p_k$ is not SNP if $k>1$ and $n>1$. Also, $p_{\lambda }$ is not SNP for $n>1$ whenever $\lambda _i\ge 2$ for all i. This is since $x_1^{|\lambda |}$ and $x_2^{|\lambda |}$ both appear as monomials in $p_{\lambda }$ but $x_1^{|\lambda |-1}x_2$ does not. Furthermore:

Proposition 2.18

$p_\lambda \in \textsf { Sym}_n$ for $n > \ell (\lambda )$ is SNP if and only if $\lambda = (1^k)$.

Proof

($\Leftarrow$) If $\lambda = (1^k)$, $p_\lambda = e_\lambda$ which is SNP by Proposition 2.15.

($\Rightarrow$) Suppose $\lambda _1 \ge 2$ and let $\ell = \ell (\lambda )$. Then since $n > \ell$, $x_1^{\lambda _1}x_2^{\lambda _2}\cdots x_\ell ^{\lambda _\ell }$ and $x_2^{\lambda _2}\cdots x_\ell ^{\lambda _\ell }x_{\ell + 1}^{\lambda _1}$ are monomials in $p_\lambda$. Thus,

$$\begin{aligned}&(\lambda _1-1,\lambda _2,\ldots ,\lambda _\ell ,1) = \frac{\lambda _1-1}{\lambda _1}(\lambda _1,\lambda _2,\ldots ,\lambda _\ell ,0)\\&\quad + \frac{1}{\lambda _1}(0,\lambda _2,\ldots ,\lambda _\ell ,\lambda _1) \in \textsf { Newton}(p_\lambda ). \end{aligned}$$

However, this point cannot be an exponent vector since it has $\ell +1$ nonzero components whereas every monomial of $p_\lambda$ uses at most $\ell$ distinct variables. $\square$

Example 2.19

(The resultant, the Gale–Ryser theorem and (0, 1)-matrices) Let

$$\begin{aligned} f=\sum _{i=0}^m a_i z^i \text { and } g=\sum _{i=1}^n b_i z^i \end{aligned}$$

be two polynomials of degree m and n respectively and with roots $\{x_1,\ldots ,x_m\}$ and $\{y_1,\ldots ,y_n\}$ respectively (not necessarily distinct). The resultant is

$$\begin{aligned} R(f,g)=a_m^n b_n^m\prod _{i=1}^m \prod _{j=1}^n (x_i-y_j). \end{aligned}$$

This polynomial is separately symmetric in the x and y variables. In [16] the Newton polytope of R(f, g) is determined; see also the book [17]. However, we are not aware of the following result appearing explicitly in the literature:

Theorem 2.20

R(f, g) is SNP.

Proof

Consider

$$\begin{aligned} F=\prod _{i=1}^m\prod _{j=1}^n(1+x_i y_j). \end{aligned}$$

In fact, $[x^{\alpha }y^{\beta }]F$ equals the number of (0, 1)-matrices of dimension $m\times n$ whose row sums are given by $\alpha$ and column sums are given by $\beta$; see, e.g., [42, Proposition 7.4.3]. Let $\textsf { M}(\alpha ,\beta )$ equal the number of these matrices. The Gale-Ryser theorem states

$$\begin{aligned} \textsf { M}(\alpha ,\beta )>0 \iff \lambda (\beta )\le _D \lambda (\alpha )', \end{aligned}$$

(9)

where $\lambda (\gamma )$ is the partition obtained by sorting a nonnegative integer sequence in decreasing order. Call a pair of vectors $(\alpha ,\beta )\in {\mathbb {Z}}_{\ge 0}^{m+n}$ a GR pair if it satisfies either of the equivalent conditions in (9).

In fact F is SNP. Suppose

$$\begin{aligned} (\alpha ^{(1)},\beta ^{(1)}), (\alpha ^{(2)},\beta ^{(2)}),\ldots , (\alpha ^{(N)},\beta ^{(N)}) \end{aligned}$$

are GR pairs and

$$\begin{aligned} (\alpha ,\beta )=\sum _{t=1}^N d_i (\alpha ^{(t)},\beta ^{(t)}) \end{aligned}$$

with $d_i\ge 0$ and $\sum _{t=1}^N d_i=1$ be a convex combination. The SNPness of F is equivalent to the claim $(\alpha ,\beta )$ is a GR pair whenever $(\alpha ,\beta )\in {\mathbb {Z}}_{\ge 0}^{m+n}$. The latter claim is immediate from [6, Theorem 3, part 1] which establishes the “approximate log-concavity” of $\textsf { M}(\alpha ,\beta )$. We thank A. Barvinok for pointing out this reference to us. More exactly, in our notation, the stated result of A. Barvinok asserts there exists an absolute constant $\gamma >0$ such that

$$\begin{aligned} (mn)^{\gamma (m+n)}\textsf { M}(\alpha ,\beta )\ge \prod _{t=1}^N \textsf { M}(\alpha ^{(t)},\beta ^{(t)})^{d_t}. \end{aligned}$$

Since by assumption each $\textsf { M}(\alpha ^{(t)},\beta ^{(t)})>0$, we have $\textsf { M}(\alpha ,\beta )>0$ as required.

Now notice that

$$\begin{aligned} F\text { is SNP}&\iff \prod _{i=1}^m\prod _{j=1}^n\left( 1+x_i y_j^{-1}\right) \text { is SNP}\\&\iff y_1^m y_2^m\cdots y_n^m \prod _{i=1}^m\prod _{j=1}^n\left( 1+x_i y_j^{-1}\right) \text { is SNP}\\&\iff \prod _{i=1}^m\prod _{j=1}^n (x_i+y_j)\text { is SNP}\\&\iff \prod _{i=1}^m\prod _{j=1}^n (x_i-y_j)\text { is SNP}\\&\iff R(f,g)\text { is SNP.} \end{aligned}$$

The final equivalence is true since $a_0,b_0\ne 0$ and the previous equivalence holds since the polynomials in the third and fourth lines clearly share the same monomials. This relation between F and R(f, g) appears in [16] where the authors use it to obtain a formula for the monomials of R(f, g) in terms of counts for (0, 1)-matrices. $\square$

Conjecture 5.2 claims a generalization of Theorem 2.20; see Example 5.4.$\square$

Example 2.21

(Powers of the Vandermonde) The Vandermonde determinant is

$$\begin{aligned} a_{\delta _n}=\prod _{1\le i<j\le n} (x_i-x_j). \end{aligned}$$

(This polynomial is only skew-symmetric.) It is known that

$$\begin{aligned} \textsf { Newton}(a_{\delta _n})={\mathcal {P}}_{(n-1,n-2,\ldots ,2,1,0)}\subset {\mathbb {R}}^n; \end{aligned}$$

see e.g., [33, Proposition 2.3].

Proposition 2.22

$a_{\delta _n}$ is SNP if and only if $n \le 2$.

The classical discriminant is $\Delta _n=\alpha _{\delta _n}^2$. Its Newton polytope was also determined by in work of I. M. Gelfand-M. Kapranov-A. V. Zelevinsky [16].

Proposition 2.23

$\Delta _n$ is SNP if and only if $n\le 4$.

Proposition 2.23 is a curious coincidence with the Abel–Ruffini theorem.

Our proofs of Propositions 2.22 and 2.23 will use this lemma:

Lemma 2.24

If $a_{\delta _n}^k$ is not SNP, then $a_{\delta _{n+1}}^k$ is not SNP.

Proof

Suppose $a_{\delta _n}^k$ is not SNP. There exists a lattice point $\alpha \in \textsf { Newton}(a_{\delta _n}^k)$ that is not an exponent vector of $a_{\delta _n}^k$. Hence we have a convex combination

$$\begin{aligned} \alpha =\sum _{i=1}^N c_i \beta ^i \end{aligned}$$

where $\beta ^i$ is an exponent vector. For $\gamma \in {\mathbb R}^n$, let $\gamma '=(\gamma ,kn)\in {\mathbb {R}}^{n+1}$. Since

$$\begin{aligned} a_{\delta _{n+1}}^k=a_{\delta _n}^k \times \prod _{i=1}^n (x_i-x_{n+1})^k, \end{aligned}$$

each $(\beta ^i)'$ is an exponent vector of $a_{\delta _{n+1}}^k$ and hence $\alpha '$ is a lattice point of $\textsf { Newton}(a_{\delta _{n+1}}^k)$. Since $x^{\alpha '} = x^\alpha x_{n+1}^{kn}$ and $x_{n+1}$ does not appear in $a_{\delta _{n}}^k$, if $\alpha '$ is an exponent vector of $a_{\delta _{n+1}}^k$, $\alpha$ is an exponent vector of $a_{\delta _n}^k$, a contradiction. Thus $a_{\delta _{n+1}}^k$ is not SNP. $\square$

Proof of Propositions 2.22 and 2.23

Clearly, $a_{\delta _n}$ is SNP for $n =1,2$. One checks that $(1,1,1) \in \textsf { Newton}(a_{\delta _3})$ but is not an actual exponent vector. $\square$

Separately, one checks $\Delta _n$ is SNP for $n\le 4$. Also $\Delta _5$ is not SNP. In fact, the only lattice points that are not exponent vectors are all 5! rearrangements of (1, 3, 4, 5, 7).

Now apply Lemma 2.24 to complete an induction argument for each of the two propositions being proved.$\square$

Conjecture 2.25

For all k, there exists $N_k$ such that $a_{\delta _n}^k$ is not SNP for any $n \ge N_k$.

More precisely, for $1\le j\le 4$ we computed $N_{2j-1}=3$ and moreover that $(1,3j-2,3j-2)$ is a lattice point that is not an exponent vector. Moreover, $N_2=5, N_4=4,N_6=4,N_8=3$. For more on (higher) powers of the Vandermonde, see, e.g., [5, 39].$\square$

Example 2.26

(q-Discriminant) The q -discriminant is $\prod _{1\le i<j\le n}(x_i-qx_j)$. At $q=-1$,

$$\begin{aligned} f_n=\prod _{1\le i<j\le n}(x_i+x_j)\in \textsf { Sym}_n. \end{aligned}$$

It is known that

$$\begin{aligned} f_n=s_{\rho _n}(x_1,x_2,\ldots ,x_n) \text { where} \rho _n=(n-1,n-2,\ldots ,3,2,1,0). \end{aligned}$$

Hence $f_n$ is SNP and $\textsf { Newton}(f_n)={\mathcal P}_{\rho _n}\subset {\mathbb {R}}^n$. $\square$

Example 2.27

(Totally nonnegative matrices) Let

$$\begin{aligned} M=(m_{ij})_{1\le i,j\le n} \end{aligned}$$

be an $n\times n$ totally nonnegative real matrix. That is, every determinant of a square submatrix is nonnegative. Define

$$\begin{aligned} F_M=\sum _{w\in S_n} \left( \prod _{i=1}^{n} m_{i,w(i)}\right) p_{\lambda (w)}, \end{aligned}$$

where $\lambda (w)$ is the cycle type of w.

Theorem 2.28

$F_M$ is SNP.

Proof

By assumption, $m_{ij}\ge 0$. A theorem of J. R. Stembridge [44] (cf. [42, Exercise 7.92]) states that $F_{M}$ is also Schur positive. Now apply Proposition 2.10. $\square$

Example 2.29

(Redfield–Pólya theory) Let G be a subgroup of $S_n$. The cycle index polynomial is

$$\begin{aligned} Z_G=\frac{1}{|G|}\sum _{g\in G} p_{\lambda (g)}, \end{aligned}$$

where $\lambda (g)$ is the cycle type of g.

Theorem 2.30

$Z_G$ has SNP.$\square$

Proof

It is true that

$$\begin{aligned} Z_G=\sum _{\lambda } c_{\lambda } s_{\lambda }, \end{aligned}$$

where each $c_{\lambda }\in {\mathbb {Z}}_{\ge 0}$; see [42, p. 396]: this positivity is known for representation-theoretic reasons (no combinatorial proof is available). Now use Proposition 2.10. $\square$

Example 2.31

(C. Reutenauer’s $q_{\lambda }$ basis) C. Reutenauer [37] introduced a new basis $\{q_{\lambda }\}$ of symmetric polynomials, recursively defined by setting

$$\begin{aligned} \sum _{\lambda \vdash n} q_{\lambda } = s_{(n)}, \end{aligned}$$

where $q_{\lambda }=q_{\lambda _1}q_{\lambda _2}\ldots$.

Theorem 2.32

$q_{\lambda }$ has SNP.

Proof

Reutenauer in loc. cit. conjectured that $-q_{(n)}$ is Schur positive for $n\ge 2$. Indeed,

$$\begin{aligned} q_{(1)}=s_{(1)}, q_{(2)}=-s_{(1,1)}, q_{(3)}=-s_{(2,1)}. \end{aligned}$$

Reutenauer’s conjecture was later established by W. M. Doran IV [11]. The proof sets

$$\begin{aligned} f(n,k)=\sum _{\lambda \vdash n, \mathrm{min}(\lambda _i)\ge k} q_{\lambda }. \end{aligned}$$

The argument inducts on n and proceeds by showing that

$$\begin{aligned} -f(n,k)=s_{(n-1,1)}+\sum _{2\le i<k} (-f(i,i))(-f(n-i,i)). \end{aligned}$$

His induction claim is that $-f(n,k)$ is Schur positive for $k\ge 2$. Let us strengthen his induction hypothesis, and assume $-f(n,k)$ is Schur positive with $s_{(n-1,1)}$ as the unique $\le _D$ maximal term. In the induction step, note each $s_{\alpha }$ appearing in $-f(i,i)$ has $\alpha _1\le i-1$ and each $s_{\beta }$ in $-f(n-i,i)$ has $\beta _1\le n-i-1$. Thus, by the argument of Proposition 2.9, if $s_{\gamma }$ appears in $s_{\alpha }s_{\beta }$ then $\gamma _1\le n-2$, implying the strengthening we need.

It follows from the above argument and the Littlewood–Richardson rule that if $\lambda =(\lambda _1, \ldots , \lambda _{\ell },1^r)$ where each $\lambda _{i}\ge 2$ then $q_{\lambda }$ has a unique $\le _D$-leading term $s_{a,b}$ where $a = |\lambda |-\ell$ and $b = \ell$. Thus, $q_{\lambda }$ has SNP by Proposition 2.5(III). $\square$

Example 2.33

(Stanley’s chromatic symmetric polynomial) For a graph G, let $c_{G}(x_1,\ldots ,x_n)$ be Stanley’s chromatic symmetric polynomial [41]. If $G=K_{1,3}$,

$$\begin{aligned} c_{G}(x_1,x_2,\ldots )= x_1^3x_2+x_1 x_2^3+\cdots \end{aligned}$$

is not SNP. $\square$

Example 2.34

(Kronecker product of Schur polynomials) The Kronecker product is

$$\begin{aligned} s_{\lambda }*s_{\mu }=\sum _{\nu } \textsf { Kron}_{\lambda ,\mu }^{\nu } s_{\nu }\in \textsf { Sym}. \end{aligned}$$

$\textsf { Kron}_{\lambda ,\mu }^{\nu }$ is the Kronecker coefficient, the multiplicity of the $S_n$-character $\chi ^{\nu }$ appearing in $\chi ^\lambda \otimes \chi ^\mu$. We conjecture that $s_{\lambda }*s_{\mu }$ is SNP. We have verified this for all $\lambda ,\mu \in \textsf { Par}(n)$ for $1\le n\le 7$. Consider

$$\begin{aligned} s_{(4,2)}*s_{(2,2,1,1)}= & {} s_{(1, 1, 1, 1, 1, 1)} + s_{(2, 1, 1, 1, 1)} + 2s_{(2, 2, 1, 1)} + s_{(3, 1, 1, 1)} \\&+ 2s_{(3, 2, 1)} + s_{(3, 3)} + s_{(4, 1, 1)}. \end{aligned}$$

Notice (3, 3) and (4, 1, 1) are both $\le _D$-maximal. Hence in this case, SNPness cannot be blamed on Proposition 2.5(III); cf. [4, Lemma 3.2] and [46].$\square$

Example 2.35

(Lascoux–Leclerc–Thibon (LLT) polynomials) A. Lascoux-B. Leclerc-J. Y. Thibon [25] introduced $G_{\lambda }^{(m)}(X;q)$. $G_{\lambda }^{(m)}(X;1)$ is a product of Schur polynomials. Hence $G_{\lambda }^{(m)}(X;1)$ is SNP by Proposition 2.9. $G_{\lambda }^{(m)}(X;q)\in \textsf { Sym}_n[q]$ is not always SNP. One example is

$$\begin{aligned} G_{(3,3)}^{(2)}(x_1,x_2;q) = q^3(x_1^3+x_1^2 x_2+x_1 x_2^2 +x_2^3)+q(x_1^2 x_2 +x_2^2 x_1). \end{aligned}$$

LLT polynomials arise in the study of Macdonald polynomials, the topic of Sect. 3. (Another related topic is affine Schubert calculus; see the book [23].) $\square$

3 Macdonald polynomials

3.1 Symmetric and nonsymmetric Macdonald polynomials

In [28], I. G. Macdonald introduced a family of polynomials depending of parameters q and t. Define an inner product $\langle \bullet ,\bullet \rangle _{q,t}$ on Sym by

$$\begin{aligned} \langle p_{\lambda },p_{\mu }\rangle _{q,t}=\delta _{\lambda ,\mu }z_{\lambda }(q,t), \end{aligned}$$

where

$$\begin{aligned} z_{\lambda }(q,t)=z_{\lambda }\prod _{i=1}^{\ell (\lambda )} \frac{1-q^{\lambda }}{1-t^{\lambda }}, \end{aligned}$$

and

$$\begin{aligned} z_{\lambda }=\prod _{r\ge 1}r^{m_r}m_r! \end{aligned}$$

for $\lambda =(1^{m_1}2^{m_2}\cdots )$. Macdonald polynomials $\{P_{\mu }(X;q,t)\}$ are uniquely determined by

$$\begin{aligned} P_{\lambda }(X;q,t)=m_{\lambda }(X)+\sum _{\mu <_D\lambda } \textsf { c}_{\lambda ,\mu }(q,t)m_{\mu }(X) \end{aligned}$$

(10)

where $\textsf { c}_{\lambda ,\mu }(q,t)\in {\mathbb {Q}}(q,t)$, together with

$$\begin{aligned} \langle P_{\lambda },P_{\mu }\rangle _{q,t}=0 \quad \text {if}\quad \lambda \ne \mu . \end{aligned}$$

Theorem 3.1

$P_{\lambda }(X;q=q_0,t=t_0)$ is SNP, and $\textsf { Newton}(P_{\lambda }(x_1,\ldots ,x_n;q=q_0,t=t_0))={\mathcal P}_{\lambda }\subset {\mathbb {R}}^n$ whenever $n\ge \ell (\lambda )$, for any $(q_0,t_0)$ in a Zariski open subset of ${\mathbb {C}}^2$.

Lemma 3.2

$\textsf { Newton}(P_{\lambda }(x_1,\ldots ,x_n;q=q_0,t=t_0))={\mathcal P}_{\lambda }\subset {\mathbb {R}}^n$ whenever $n\ge \ell (\lambda )$, for any $(q_0,t_0)\in {\mathbb {C}}^2$.

Proof

This is by (10) and Proposition 2.5(I). Since $n\ge \ell (\lambda )$, $s_{\lambda }(x_1,\ldots ,x_n) \not \equiv 0$.   $\square$

Lemma 3.3

Fix $q_0,t_0\in {\mathbb {C}}$. $P_{\lambda }(X;q=q_0,t=t_0)$ is SNP if and only if $\textsf { c}_{\lambda ,\mu }(q_0,t_0)\ne 0$ for all $\mu <_D\lambda$.

Proof

($\Rightarrow$) By Lemma 3.2, $\textsf { Newton}(P_{\lambda }(X;q=q_0,t=t_0))={\mathcal {P}}_{\lambda }$. Thus each $\mu <_D\lambda$ appears as a lattice point of $\textsf { Newton}(P_{\lambda }(X;q=q_0,t=t_0))$. Since we assume $P_{\lambda }(X;q=q_0,t=t_0)$ is SNP, $[x^{\mu }]P_{\lambda }(X;q=q_0,t=t_0)\ne 0$. Among monomial symmetric functions, $x^\mu$ only appears in $m_{\mu }$. Hence $\textsf { c}_{\lambda ,\mu }(q_0,t_0)\ne 0$, as desired.

The proof of $(\Leftarrow )$ just reverses the above argument, using the fact that

$$\begin{aligned} \mu \in \textsf { Newton}(P_{\lambda }(X;q=q_0,t=t_0))\iff \alpha \in \textsf { Newton}(P_{\lambda }(X;q=q_0,t=t_0)) \end{aligned}$$

for any rearrangement $\alpha$ of $\mu \in {\mathbb {R}}^n$. $\square$

Proof of Theorem 3.1

The Newton polytope assertion is by Lemma 3.2. Now

$$\begin{aligned} P_{\lambda }(X;0,0)=s_{\lambda }(X) \end{aligned}$$

and $m_{\mu }$ appears in $s_{\lambda }$ for every $\mu <_D\lambda$. Hence $\textsf { c}_{\lambda ,\mu }(q,t)\not \equiv 0$. Now choose q, t that is neither a pole nor a root of any of these rational functions (for $\mu <_D\lambda$). Therefore the SNP assertion follows from Lemma 3.3.$\square$

The Hall–Littlewood polynomial is $P_{\lambda }(X;t):=P_{\lambda }(X,q=0,t)$. One has

$$\begin{aligned} P_{\lambda }(X;t)=\sum _{\mu } \textsf { K}_{\lambda ,\mu }(t)s_{\mu }(X) \end{aligned}$$

where $\textsf { K}_{\lambda ,\mu }(t)$ is the Kostka–Foulkes polynomial. It is known that

$$\begin{aligned} \textsf { K}_{\lambda ,\mu }(t)=\sum _{T}t^{\mathrm{charge}(T)}. \end{aligned}$$

The sum is over all semistandard tableau T of shape $\lambda$ and content $\mu$. It is true that $\mathrm{charge}(T)\in {\mathbb {Z}}_{\ge 0}$. Since these tableaux can only occur if $\mu \le _D \lambda$, $\textsf { K}_{\lambda ,\mu }(t)\not \equiv 0$ if and only if $\mu \le _D\lambda$. Hence we immediately obtain:

Proposition 3.4

If $t_0>0$ then $P_{\lambda }(X;t=t_0)\in \textsf { Sym}$ is SNP and $\textsf { Newton}(P_{\lambda }(x_1,\ldots ,x_n;t=t_0)={\mathcal P}_{\lambda }\subset {\mathbb {R}}^n$ whenever $n\ge \ell (\lambda )$.

The Schur $P-$ polynomial is

$$\begin{aligned} SP_{\lambda }(X)=\sum _{T} x^{T}. \end{aligned}$$

The sum is over shifted semistandard Young tableaux of a partition $\lambda$ with distinct parts. There is also the Schur $Q-$ polynomial,

$$\begin{aligned} SQ_{\lambda }(X)=2^{\ell (\lambda )} SP_{\lambda }. \end{aligned}$$

Proposition 3.5

$SP_{\lambda }(X)$ and $SQ_{\lambda }(S)$ are SNP and

$$\begin{aligned} \textsf { Newton}(SP_{\lambda }(X))=\textsf { Newton}(SQ_{\lambda }(X))={\mathcal {P}}_{\lambda }. \end{aligned}$$

Proof

In fact,

$$\begin{aligned} SP_{\lambda }(X)=P_{\lambda }(X;t=-1); \end{aligned}$$

see [43]. Also $K_{\lambda ,\lambda }(t)=1$. Now, $SP_{\lambda }$ is Schur-positive; see, e.g., [43, p. 131–132]. Thus the result follows from Proposition 2.5(III). $\square$

The modified Macdonald polynomial ${\widetilde{H}}_{\lambda }(X;q,t)$ is a certain transformation of $P_{\lambda }(X;q,t)$ also introduced in [28].

Proposition 3.6

For any $q_0,t_0> 0$, ${\widetilde{H}}_{\lambda }(X;q=q_0,t=t_0)$ is SNP and $\textsf { Newton}({\widetilde{H}}_{\lambda }(x_1,\ldots ,x_n;q=q_0,t=t_0))={\mathcal P}_{|\lambda |}\subset {\mathbb {R}}^n$ whenever $n\ge |\lambda |$.

Proof

A formula of J. Hagland-M. Haiman-N. Loehr [18] states that

$$\begin{aligned} {\widetilde{H}}_{\lambda }(X;q,t)=\sum _{\sigma :\lambda \rightarrow {\mathbb Z}_{>0}} x^{\sigma }q^{\mathrm{inv}(\sigma )}t^{\mathrm{maj}(\sigma )}, \end{aligned}$$

where $\sigma$ is any assignment of positive integers to the boxes of $\lambda$. Also, $\mathrm{inv}(\sigma )$ and $\mathrm{maj}(\sigma )$ are certain combinatorially defined statistics, whose specifics we do not need here. Thus, for $q,t>0$, every monomial of degree $|\lambda |$ appears. $\square$

In contrast, ${\widetilde{H}}_{(3,1,1)}(x_1,x_2,x_3,x_4,x_5;q,t)$ is not SNP as it misses the monomial $qtx_3x_4^4$. This example does not contradict Proposition 3.6 (which sets q and t to positive reals).

Example 3.7

(Modified q, t-Kostka polynomials are not SNP) Consider the expansion

$$\begin{aligned} {\widetilde{H}}_{\lambda }(X;q,t)=\sum _{\mu } {\widetilde{\textsf { K}}}_{\lambda ,\mu }(q,t)s_{\mu }(X). \end{aligned}$$

The coefficients ${\widetilde{\textsf { K}}}_{\lambda ,\mu }(q,t)$ are the (modified) q ,  t -Kostka coefficients. Now,

$$\begin{aligned} {\widetilde{\textsf { K}}}_{(2,2,2),(2,1,1,1)}(q,t)=qt^7+t^8+qt^5+t^6+qt^4. \end{aligned}$$

Hence, ${\widetilde{\textsf { K}}}_{\lambda ,\mu }(q,t)$ need not be SNP.$\square$

Let $\alpha \in {\mathbb {Z}}_{\ge 0}^n$. There is the nonsymmetric Macdonald polynomial $E_{\alpha }(x_1,\ldots ,x_n;q,t)$; see [19] for details.

It is part of a definition that

$$\begin{aligned} E_{\alpha }(X;q,t)=x^{\alpha }+ \sum _{\beta <_{S}\alpha } \textsf {d}_{\alpha ,\beta }(q,t)x^\beta \end{aligned}$$

where $\textsf {d}_{\alpha ,\beta }(q,t)\in {\mathbb {Q}}(q,t)$. S. Sahi [38] proved each $\textsf {d}_{\alpha ,\beta }(q,t)\not \equiv 0$. Here $<_{S}$ is the ordering whose covering relations are that if $\alpha _i<\alpha _j$ then $t_{ij}(\alpha )<_S \alpha$ (where $t_{ij}(\alpha )$ swaps positions i and j of $\alpha$). If also $\alpha _j-\alpha _i>1$ then $\alpha +e_i-e_j<_S t_{ij}(\alpha )$; see [19, Section 2.1]. Let ${\widehat{\mathcal P}_{\alpha }}$ be the convex hull of all $\beta \in {\mathbb {Z}}_{\ge 0}^n$ such that $\beta \le _S \alpha$. Thus ${\widehat{\mathcal P}_{\alpha }}$ is the Newton polytope of $E_{\alpha }(X;q=q_0,t=t_0)$ for any generic choice of $(q_0,t_0)\in {\mathbb {C}}^2$. The conjecture below says $E_{\alpha }(X;q,t)$ is “generically SNP”:

Conjecture 3.8

If $\beta \in {\widehat{\mathcal {P}}_{\alpha }}$ and $\beta \in {\mathbb Z}_{\ge 0}^n$ then $\beta \le _S \alpha$.

Conjecture 3.8 has been checked for $n\le 7$ and whenever $|\alpha |\le 7$.

3.2 Keys and Demazure atoms

Complementing the above analysis, we now investigate SNP for two specializations of $E_{\alpha }(X;q,t)$. The first is $\kappa _{\alpha }=E_{\alpha }(X;q=\infty ,t=\infty )$ [21, Theorem 3]. The Demazure operator is

$$\begin{aligned} \pi _i(f)=\partial _i(x_i \cdot f ), \text{ for } f\in {\mathbb Z}[x_1,x_2,\ldots ]. \end{aligned}$$

Let $\alpha =(\alpha _1,\alpha _2,\ldots )\in {\mathbb {Z}}_{\ge 0}^\infty$ and suppose that $|\alpha |=\sum _i \alpha _i<\infty$. Define the key polynomial $\kappa _{\alpha }$ to be

$$\begin{aligned} x^{\alpha }:=x_1^{\alpha _1}x_2^{\alpha _2}\cdots , \text{ if } \alpha \text { is weakly decreasing.} \end{aligned}$$

Otherwise, set

$$\begin{aligned} \kappa _{\alpha }=\pi _i(\kappa _{\widehat{\alpha }}) \text{ where }\quad \widehat{\alpha }=(\ldots ,\alpha _{i+1},\alpha _i,\ldots )\text { and } \alpha _{i+1}>\alpha _{i}. \end{aligned}$$

(11)

The key polynomials form a ${\mathbb {Z}}$-basis of ${\mathbb Z}[x_1,x_2,\ldots ]$; see work of V. Reiner–M. Shimozono [36] (and references therein) for more on $\kappa _{\alpha }$.

Define $\textsf {D}_{\alpha }$ to be the “skyline” diagram with a left-justified row of $\alpha _i$ boxes in row i.

Conjecture 3.9

${\mathcal {S}}_{\textsf {D}_{\alpha }}=\textsf { Newton}(\kappa _{\alpha })$.

We have a proof (omitted here) of the “$\supseteq$” part of Conjecture 3.9. See Remark 5.22.

Conjecture 3.10

$\kappa _{\alpha }$ has SNP.

We have a second conjectural description of $\textsf { Newton}(\kappa _{\alpha })$. Let

$$\begin{aligned} m_{ij}(\alpha ) = \alpha + e_i - e_j. \end{aligned}$$

Then for any composition $\alpha$, let $\beta <_{\kappa } \alpha$ if $\beta$ can be generated from $\alpha$ by applying a sequence of the moves $t_{ij}$ for $\alpha _i < \alpha _j$, and $m_{ij}$ if $\alpha _j - \alpha _i > 1$.

Conjecture 3.11

$\kappa _\alpha = x^\alpha + \sum _{\beta <_{\kappa } \alpha } \textsf { Key}_{\alpha ,\beta } x^\beta$ with $\textsf { Key}_{\alpha ,\beta } > 0$ for all $\beta <_{\kappa } \alpha$.

(Observe that $\beta <_{\kappa } \alpha$, then $\beta <_S \alpha$. However, the converse fails as $11 <_S 20$ but one does not have $11 <_{\kappa } 20$.)

For two compositions $\gamma$ and $\alpha$ we write

$$\begin{aligned} \gamma \preceq \alpha \text { if } \lambda (\gamma )=\lambda (\alpha )\text { and }w(\gamma )\le w(\alpha )\text { in Bruhat order.} \end{aligned}$$

Here $\lambda (\gamma )$ is the partition obtained by resorting the parts of $\gamma$. Also $w(\gamma )$ is the shortest length permutation that sends $\lambda (\gamma )$ to $\gamma$. (Strong) Bruhat order refers to the ordering on permutations obtained as the closure of the relation $w\le wt_{ij}$ if $\ell (wt_{ij})=\ell (w)+1$ and $t_{ij}$ is a transposition.

Theorem 3.12

If $\beta \preceq \alpha$ then $\beta$ is a vertex of $\textsf { Newton}(\kappa _{\alpha })$.

Conjecture 3.13

The converse of Theorem 3.12 holds.

Our proof of Theorem 3.12 uses the other specialization of interest, namely $E_{\alpha }(X;q=0,t=0)$. Let

$$\begin{aligned} \widehat{\pi }_i:=\pi _i-\mathrm{id} \end{aligned}$$

and define the Demazure atom $A_{\alpha }=x^{\alpha }$ if $\alpha$ is weakly decreasing. Otherwise $A_{\alpha }=\widehat{\pi _i}(A_{\widehat{\alpha }})$ where $\widehat{\alpha }$ is defined as in (11). By the way,

Conjecture 3.14

$A_{\alpha }$ has SNP.

That $E_{\alpha }(X;q=0,t=0)=A_{\alpha }$ is [30, Theorem 1.1].

The five conjectures above, namely Conjectures 3.9, 3.10, 3.11, 3.13 and 3.14 have been checked for $|\alpha |\le 7$ where $\alpha$ has at most three parts of size zero.

We will also use

$$\begin{aligned} \kappa _{\alpha }=\sum _{\gamma \preceq \alpha } A_{\gamma } \end{aligned}$$

(12)

One reference for (12) is [30, Section 1]; a proof is found in [34, Lemma 3.5].

Proposition 3.15

Suppose $\beta \preceq \alpha$. Let $\lambda =\lambda (\beta )=\lambda (\alpha )$. Then

$$\begin{aligned} \{\lambda \}\subseteq \textsf { Newton}(\kappa _{\beta })\subseteq \textsf { Newton}(\kappa _{\alpha })\subseteq {\mathcal {P}}_{\lambda }\subseteq {\mathbb {R}}^n, \end{aligned}$$

where n is the position of the last nonzero part of $\alpha$.

Proof

Using (12) twice, we have

$$\begin{aligned} \kappa _\alpha = \sum _{\gamma \preceq \alpha } A_\gamma = \sum _{\gamma \preceq \beta } A_\gamma + \sum _{\begin{array}{c} \gamma \preceq \alpha \\ \gamma \not \preceq \beta \end{array}} A_\gamma = \kappa _\beta + \sum _{\begin{array}{c} \gamma \preceq \alpha \\ \gamma \not \preceq \beta \end{array}} A_\gamma . \end{aligned}$$

Since each $A_{\gamma }$ is monomial positive [30, Theorem 1.1],

$$\begin{aligned} \textsf { Newton}(\kappa _\beta )\subseteq \textsf { Newton}(\kappa _{\alpha }). \end{aligned}$$

Now, $\lambda$ is $\preceq$-minimum among rearrangements of $\lambda$. By definition $\kappa _{\lambda }=x^{\lambda }$. This explains the leftmost containment.

Let $\lambda ^\mathrm{rev}=(0,0,\ldots ,0,\ldots ,\lambda _3,\lambda _2,\lambda _1)\in {\mathbb Z}^n$. Then $\lambda ^\mathrm{rev}$ is the $\preceq$-maximum among rearrangements of $\lambda$ in ${\mathbb {Z}}^n$. Also, we have $\kappa _{\lambda ^\mathrm{rev}} = s_\lambda$ (see, e.g., [30, Section 4] and references therein). However we know $\textsf { Newton}(s_{\lambda })={\mathcal {P}}_{\lambda }$. $\square$

Lemma 3.16

Suppose ${\mathcal {P}}$ and ${\mathcal {Q}}$ are polytopes such that ${\mathcal {P}}\subseteq {\mathcal {Q}}$. If v is a vertex of ${\mathcal {Q}}$ and $v\in {\mathcal {P}}$, then v is a vertex of ${\mathcal {P}}$.

Proof

v is a vertex of ${\mathcal {Q}}$ if and only if there is a separating hyperplane H, i.e., there exists a vector c such that $\mathbf{c}'v<\mathbf{c}'y$ for all $y\in {\mathcal {Q}}$. Since ${\mathcal P}\subseteq {\mathcal {Q}}$, H works for ${\mathcal {P}}$ also. $\square$

Proof of Theorem 3.12

Now,

$$\begin{aligned} \kappa _{\alpha }=x^{\alpha }+\text {(positive sum of monomials)}; \end{aligned}$$

see, e.g., [36, Corollary 7]. Hence, $\alpha$ is in $\textsf { Newton}(\kappa _{\alpha })$. By Proposition 3.15,

$$\begin{aligned} \beta \in \textsf { Newton}(\kappa _{\beta })\subseteq \textsf { Newton}(\kappa _{\alpha }) \text { if }\beta \preceq \alpha . \end{aligned}$$

Again applying Proposition 3.15 we have that $\textsf { Newton}(\kappa _{\alpha })\subseteq {\mathcal {P}}_{\lambda (\alpha )}$. Now we are done by combining Proposition 2.5(II) and Lemma 3.16. $\square$

Fig. 1

The permutahedron for $\lambda =(2,1,0)$. The shaded region is $\textsf { Newton}(\kappa _{1,0,2})$. See Proposition 3.15

4 Quasisymmetric functions

A power series $f\in {\mathbb {Z}}[[x_1,x_2,\ldots ]]$ is quasisymmetric if

$$\begin{aligned}{}[x_1^{a_1}x_2^{a_2}\cdots x_k^{a_k}]f= [x_{i_1}^{a_1}x_{i_2}^{a_2}\cdots x_{i_k}^{a_k}]f \end{aligned}$$

for any natural numbers $i_1<i_2<\ldots <i_k$. As with $\textsf { Sym}$, define a quasisymmetric function f to be SNP if $f(x_1,x_2,\ldots ,x_m,0,0,\ldots )$ is SNP for all $m\ge 1$. In view of Remark 2.3, f is SNP if $f(x_1,x_2,\ldots ,x_m,0,0,\ldots )$ is SNP for any $m\ge \deg (f)$.

Let $\alpha =(\alpha _1,\ldots ,\alpha _k)\in {\mathbb {Z}}_{>0}^k$. The monomial quasisymmetric function is defined as

$$\begin{aligned} M_{\alpha }=\sum _{i_1<i_2<\ldots <i_k} x_{i_1}^{a_1}\cdots x_{i_k}^{a_k}. \end{aligned}$$

Let $\textsf { QSym}$ be the ${\mathbb {Q}}$-span of all $M_{\alpha }$.

Example 4.1

($M_{\alpha }$ need not be SNP) $M_{(2)}=p_2=x_1^2+x_2^2+\cdots$ does not have SNP. $\square$

Another basis of $\textsf { QSym}$ is given by Gessel’s fundamental quasisymmetric functions

$$\begin{aligned} F_{\alpha }=\sum _{\beta \rightarrow \alpha } M_{\beta }. \end{aligned}$$

(13)

Here, $\beta \rightarrow \alpha$ means that $\alpha$ is obtained by successively adding adjacent parts of $\beta$.

For a composition $\gamma$, let $\gamma ^+$ be the composition formed by removing parts of size zero from $\gamma$.

Theorem 4.2

$\textsf { Newton}(F_{\alpha }(x_1,\ldots ,x_n)) = \textsf { Newton}(M_{\alpha }(x_1,\ldots ,x_n))\subset {\mathbb {R}}^n$. The vertices of this polytope are $\{ \gamma \in \mathbb {Z}_{\ge 0}^n : \gamma ^+ = \alpha \}$.

Proof

Each $M_{\beta }$ is a positive sum of monomials. Also, $\alpha \rightarrow \alpha$ so $M_{\alpha }$ appears in the expansion (13). Therefore,

$$\begin{aligned} \textsf { Newton}(F_{\alpha }(x_1,\ldots ,x_n)) \supseteq \textsf { Newton}(M_{\alpha }(x_1,\ldots ,x_n)). \end{aligned}$$

Suppose ${\beta }=(\beta _1,\beta _2,\ldots , \beta _k)\in {\mathbb Z}_{>0}^k$ and $\widehat{\beta }\rightarrow \beta$ where

$$\begin{aligned} {\widehat{\beta }}=(\beta _1,\beta _2,\ldots ,\beta _i',\beta _{i}'',\ldots ,\beta _k)\in {\mathbb {Z}}^{k+1}_{>0} \end{aligned}$$

and $\beta _i=\beta _i'+\beta _{i}''$.

We wish to show

$$\begin{aligned} \textsf { Newton}(M_{{\widehat{\beta }}}(x_1,\ldots ,x_n)) \subseteq \textsf { Newton}(M_{\beta }(x_1,\ldots ,x_n)). \end{aligned}$$

(14)

By induction, this implies the remaining containment

$$\begin{aligned} \textsf { Newton}(F_{\alpha }(x_1,\ldots ,x_n)) \subseteq \textsf { Newton}(M_{\alpha }(x_1,\ldots ,x_n)). \end{aligned}$$

Suppose

$$\begin{aligned} {\widetilde{\beta }}=({\widetilde{\beta _1}},\ldots ,{\widetilde{\beta _n}}) \in {\mathbb {Z}}_{\ge 0}^n \text { where }({\widetilde{\beta }})^+={\widehat{\beta }}. \end{aligned}$$

Thus,

$$\begin{aligned} {\widetilde{\beta }}= (0,\ldots ,0,\beta _1,0,\ldots ,0,\beta _2,\ldots ,\beta _i',0,\ldots ,0,\beta _i'', 0,\ldots ,0,\ldots ,\beta _k,0,\ldots ,0) \end{aligned}$$

where we are depicting the additional 0’s inserted between components of ${{\widehat{\beta }}}$ to obtain ${\widetilde{\beta }}$. In particular, $x^{{\widetilde{\beta }}}$ appears in $M_{{\widehat{\beta }}}$.

Now let

$$\begin{aligned} \beta ^{\circ }=(0,\ldots ,0,\beta _1,0,\ldots ,0,\beta _2,\ldots ,\beta _i,0,\ldots ,0,0,0, \ldots ,0,\ldots ,\beta _k,0,\ldots ,0) \end{aligned}$$

and

$$\begin{aligned} \beta ^{\bullet }=(0,\ldots ,0,\beta _1,0,\ldots ,0,\beta _2,\ldots ,0,0,\ldots ,0,\beta _i,0, \ldots ,0,\ldots ,\beta _k,0,\ldots ,0). \end{aligned}$$

That is, $\beta ^{\circ }$ differs from ${\widetilde{\beta }}$ only by replacing $\beta _i'$ and $\beta _i''$ by $\beta _i$ and 0, respectively. Similarly, $\beta ^{\bullet }$ differs from ${\widetilde{\beta }}$ only by replacing $\beta _i'$ and $\beta _i''$ by 0 and $\beta _i$, respectively.

Since $\beta _i',\beta _{i}''\ge 0$, we have that

$$\begin{aligned} {\widetilde{\beta }}=\frac{\beta _i'}{\beta _i}\beta ^{\circ }+ \frac{\beta _i^{''}}{\beta _i}\beta ^{\bullet } \end{aligned}$$

is a convex combination. This proves (14) and hence the asserted equality of Newton polytopes.

Every monomial of $M_{\alpha }(x_1,\ldots ,x_n)$ is a monomial of $m_{\alpha }(x_1,\ldots ,x_n)$. Therefore,

$$\begin{aligned} \textsf { Newton}(M_{\alpha }(x_1,\ldots ,x_n))\subseteq \textsf { Newton}(m_{\alpha }(x_1,\ldots ,x_n)). \end{aligned}$$

Recall,

$$\begin{aligned} \textsf { Newton}(m_{\alpha }(x_1,\ldots ,x_n))={\mathcal {P}}_{\lambda (\alpha )} \subseteq {\mathbb {R}}^n. \end{aligned}$$

One knows the vertices of ${\mathcal {P}}_{\lambda (\alpha )}$ are all rearrangements of $\alpha$ (thought of as a vector in ${\mathbb Z}^n_{\ge 0}$, where we concatenate 0’s as necessary); cf. Proposition 2.5(II). Thus, every exponent vector of $m_{\alpha }(x_1,\ldots ,x_n)$ is also a vertex of ${\mathcal {P}}_{\lambda (\alpha )}$. Hence to obtain the final claim of the theorem we may appeal to Lemma 3.16. $\square$

Example 4.3

($F_{\alpha }$ need not be SNP) One can also check that

$$\begin{aligned} F_{(2,2)} = M_{(2,2)} + M_{(2,1,1)} + M_{(1,1,2)} + M_{(1,1,1,1)}. \end{aligned}$$

Thus, $(0,1,2,1) = \frac{1}{2}(0,2,2,0) + \frac{1}{2}(0,0,2,2) \in \textsf { Newton}(F_{(2,2)})$. However, (0, 1, 2, 1) is not an exponent vector of $F_{(2,2)}$. Hence $F_{(2,2)}$ is not SNP. $\square$

J. Hagland-K. Luoto-S. Mason-S. van Willigenburg [20] introduced the quasisymmetric Schur polynomial:

$$\begin{aligned} S_{\alpha }=\sum _{\gamma } A_{\gamma } \end{aligned}$$

where the sum is over all compositions $\gamma$ such that $\gamma ^+=\alpha$ and where $\gamma ^+$ is the composition $\gamma$ with any 0 parts removed. $\textsf { QSym}$ is also spanned by $\{S_{\alpha }\}$. Also, recall $A_{\gamma }$ is the Demazure atom defined in Sect. 3.2.

Many aspects of quasi-Schur theory are parallel to Schur theory [20]. For instance, consider the transition between the S and M bases of $\textsf { QSym}$:

$$\begin{aligned} S_{\alpha }=\sum _{\beta }{\overline{\textsf {K}}}_{\alpha ,\beta }M_{\beta }. \end{aligned}$$

It is proved in loc. cit. that ${\overline{\textsf {K}}}_{\alpha ,\beta }$ counts composition tableaux. Hence ${\overline{\textsf {K}}}_{\alpha ,\beta }$ is an analogue of the Kostka coefficient. However, there are divergences from the perspective of Newton polytopes as seen in the next three examples:

Example 4.4

($S_{\alpha }$ need not be SNP) An example is $S_{(2,1,3)}$. In at least four variables, $x_1x_2^2x_3^2x_4$ does not appear but $x_1^2x_2^2x_3^2$ and $x_2^2x_3^2x_4^2$ both do. Nonetheless, it should be interesting to describe the Newton polytope, and to characterize when $S_{\alpha }$ is SNP.$\square$

Example 4.5

In the symmetric function case,

$$\begin{aligned} \textsf { Newton}(s_{\lambda }(x_1,\ldots ,x_n))=\textsf { Newton}(m_{\lambda }(x_1,\ldots ,x_n))={\mathcal {P}}_{\lambda }\subset {\mathbb {R}}^n. \end{aligned}$$

However,

$$\begin{aligned}&(0,0,2,2)\in \textsf { Newton}(S_{(1,3)}(x_1,x_2,x_3,x_4)) \text { but }\\&\quad (0,0,2,2)\not \in \textsf { Newton}(M_{(1,3)}(x_1,x_2,x_3,x_4)). \end{aligned}$$

Hence $\textsf { Newton}(S_{\alpha }(x_1,\ldots ,x_n)) \ne \textsf { Newton}(M_{\alpha }(x_1,\ldots ,x_n))$ in general. $\square$

Example 4.6

We may define a dominance order $\preceq _D'$ on strict compositions by $\alpha \preceq _D' \beta$ if $\textsf { Newton}(M_{\alpha })\subseteq \textsf { Newton}(M_{\beta })$. The above example shows that ${\overline{\textsf {K}}}_{\alpha ,\beta }>0$ if and only if $\beta \preceq _D' \alpha$ is not generally true. This is in contrast with (6).$\square$

5 Schubert polynomials and variations

5.1 The Schubert SNP conjectures

A. Lascoux–M.-P. Schützenberger [26] introduced Schubert polynomials. If $w_0=n \ n-1 \ \cdots 2 \ 1$ (in one-line notation) is the longest length permutation in $S_n$ then

$$\begin{aligned} {\mathfrak {S}}_{w_0}(x_1,\ldots ,x_n):=x_1^{n-1}x_2^{n-2}\cdots x_{n-1}. \end{aligned}$$

Otherwise, $w\ne w_0$ and there exists i such that $w(i)<w(i+1)$. Then one sets

$$\begin{aligned} {\mathfrak {S}_w}(x_1,\ldots ,x_n)=\partial _i {\mathfrak {S}}_{ws_i}(x_1,\ldots ,x_n), \text { where }\partial _i f:= \frac{f-s_if}{x_i-x_{i+1}}, \end{aligned}$$

and $s_i$ is the simple transposition swapping i and $i+1$. Since $\partial _i$ satisfies

$$\begin{aligned} \partial _i\partial _j=\partial _j\partial _i \text { for }|i-j|>1,\text { and } \partial _i\partial _{i+1}\partial _i=\partial _{i+1}\partial _i\partial _{i+1}, \end{aligned}$$

the above description of ${\mathfrak {S}}_w$ is well-defined. In addition, under the inclusion $\iota : S_n\hookrightarrow S_{n+1}$ defined by $w(1)\cdots w(n) \mapsto w(1) \ \cdots w(n) \ n+1$, we have ${\mathfrak {S}}_w={\mathfrak {S}}_{\iota (w)}$. Thus one unambiguously refers to ${\mathfrak {S}}_w$ for each $w\in S_{\infty }=\bigcup _{n\ge 1} S_n$.

Conjecture 5.1

${\mathfrak {S}}_w$ has SNP.

We have checked Conjecture 5.1 for all $w\in S_n$ where $n\le 8$.

Let $X=\{x_1,x_2,\ldots \}$ and $Y=\{y_1,y_2,\ldots \}$. The double Schubert polynomial ${\mathfrak {S}}_{w}(X;Y)$ is defined by setting

$$\begin{aligned} {\mathfrak {S}}_{w_0}(X;Y)=\prod _{i+j\le n} (x_i-y_j) \end{aligned}$$

and recursively determining ${\mathfrak {S}}_w(X;Y)$ for $w\ne w_0$ precisely as for ${\mathfrak {S}}_w(X)$.

We have also checked for $n\le 5$ (and many other cases) that:

Conjecture 5.2

${\mathfrak {S}}_{w}(X;Y)$ is SNP.

Since ${\mathfrak {S}}_{w}(X;0)={\mathfrak {S}}_{w}(X)$, Conjecture 5.2 implies Conjecture 5.1.

Example 5.3

($\partial _i$ and $\pi _i$ does not preserve SNP) This polynomial is SNP:

$$\begin{aligned} f=x_1^4+x_1^3 x_2 +x_1^2 x_2^2 +2x_1 x_2^3. \end{aligned}$$

However

$$\begin{aligned} \partial _1(f)=x_1^3+x_2^3 \end{aligned}$$

is not SNP.

Since $\pi _i(g)=\partial _i(x_i\cdot g)$, if we set

$$\begin{aligned} g=x_1^3+x_1^2x_2+x_1x_2^2+2x_2^3 \end{aligned}$$

we have $\pi _1(g)=\partial _1(f)$. Hence, $\pi _i$ does not preserve SNP. $\square$

Example 5.4

(Double Schubert polynomials are generalized resultants) Pick w to be the “dominant” permutation $n+1 \ n+2 \ \cdots n+m \ 1 \ 2 \ \cdots \ n \in S_{n+m}$. Then

$$\begin{aligned} {\mathfrak {S}}_w(X;Y)=\prod _{i=1}^n\prod _{j=1}^m (x_i-y_j). \end{aligned}$$

(One reference is [29, Proposition 2.6.7].) This has the same Newton polytope as R(f, g). Thus Conjecture 5.2 is proposes a generalization of Theorem 2.20.$\square$

A. Lascoux–M.-P. Schützenberger also introduced the family of Grothendieck polynomials [27]. These polynomials are defined using

$$\begin{aligned} \overline{\pi }_i(f)=\partial _i((1-x_{i+1})f). \end{aligned}$$

For $w_0\in S_n$ declare

$$\begin{aligned} {\mathfrak {G}}_{w_0}(X)=x_1^{n-1}x_2^{n-2}\cdots x_{n-1}. \end{aligned}$$

If $w\in S_n$ and $w\ne w_0$, let

$$\begin{aligned} {\mathfrak {G}}_w(X)={\overline{\pi }}_i({\mathfrak {G}}_{ws_i}) \end{aligned}$$

if i is an ascent of w. This is an inhomogenous analogue of the Schubert polynomial since

$$\begin{aligned} {\mathfrak {G}}_w(X)={\mathfrak {S}}_w(X)+\text{(higher } \text{ degree } \text{ terms) }. \end{aligned}$$

Like the Schubert polynomials, ${\mathfrak {G}}_w={\mathfrak {G}}_{\iota (w)}$, where $\iota :S_n\hookrightarrow S_{n+1}$ is the natural inclusion. Hence it make sense to define ${\mathfrak {G}}_w$ for $w\in S_{\infty }$.

Conjecture 5.5

${\mathfrak {G}}_w$ has SNP.

Conjecture 5.5 has been exhaustively checked for $n\le 7$. Conjecture 5.5 generalizes Conjecture 5.1 since

$$\begin{aligned} \textsf { Newton}({\mathfrak {S}}_w)=\textsf { Newton}({\mathfrak {G}}_w) \cap \left\{ (\alpha _1,\ldots ,\alpha _n)\in {\mathbb {R^n}}: \sum _{i=1}^n \alpha _i=\#\textsf {D}_w\right\} . \end{aligned}$$

Grothendieck polynomials arise in combinatorial K-theory. Another family of polynomials from this topic was introduced by A. Lascoux in [24]. He defines $\Omega _{\alpha }$ for $\alpha =(\alpha _1,\alpha _2,\ldots ) \in {\mathbb {Z}}_{\ge 0}^{\infty }$ by replacing $\pi _i$ in the definition of $\kappa _{\alpha }$ with

$$\begin{aligned} \tau _i(f)=\partial _i(x_i(1-x_{i+1})f). \end{aligned}$$

The initial condition is $\Omega _{\alpha }=x^{\alpha }(=\kappa _{\alpha }), \text { if }\alpha \text { is weakly decreasing}$. $\Omega _{\alpha }$ is an inhomogeneous analogue of $\kappa _{\alpha }$.

Conjecture 5.6

${\Omega }_\alpha$ has SNP.

The Lascoux atom ${\mathcal {L}}_\alpha$ is defined [32] by replacing $\pi _i$ in the definition of $\kappa _\alpha$ with

$$\begin{aligned} \widehat{\tau }_i(f) = (\tau _i-1)f. \end{aligned}$$

Conjecture 5.7

${\mathcal {L}}_\alpha$ has SNP.

${\mathcal {L}}_{\alpha }$ is an inhomogeneous analogue of $A_{\alpha }$.

Conjectures 5.6 and 5.7 have been verified for $|\alpha |\le 7$ where $\alpha$ has at most three parts of size zero.

5.2 Stanley polynomials and the stable limit of Conjecture 5.1

For $w\in S_{n}$, let $1^t\times w\in S_{t+n}$ be the permutation defined by $1^t\times w(i)=i$ for $1\le i\le t$ and $1^t\times w(i)=n+i$ for $t+1\le i\le t+n$. The Stanley symmetric polynomial (also known as the stable Schubert polynomial) is defined by

$$\begin{aligned} F_w=\lim _{t\rightarrow \infty }{\mathfrak {S}}_{1^t\times w}\in \textsf { Sym}. \end{aligned}$$

This power series is well-defined.

$F_w$ was originally introduced by R. P. Stanley in [40]. Every $w\in S_n$ can be expressed as a product of simple transpositions

$$\begin{aligned} w=s_{i_1}s_{i_2}\cdots s_{i_{\ell }}. \end{aligned}$$

When $\ell =\ell (w)$ is the number of inversions of w, this factorization is reduced. Then $s_{i_1}\cdots s_{i_{\ell }}$, or equivalently $(i_1,\ldots ,i_{\ell })$, is a reduced word for w. Let $\#\mathrm{Red}(w)$ be the number of reduced words of w. In loc. cit. it is shown that

$$\begin{aligned} \#\mathrm{Red}(w)=[x_1\cdots x_{\ell (w)}]F_w. \end{aligned}$$

The next result is a “stable limit” version of Conjecture 5.13.

Theorem 5.8

$F_{w}\in \textsf { Sym}$ is SNP.

Our proof rests on:

Theorem 5.9

(Theorems 3.2, 4.1, [40]) For

$$\begin{aligned} F_w = \sum _\lambda \textsf { a}_{w,\lambda } s_\lambda , \end{aligned}$$

$\textsf { a}_{w,\lambda } \ge 0$ and there exists $\lambda (w)$ and $\mu (w)$ such that $a_{w,\lambda (w)}=a_{w,\mu (w)}=1$ and if $\textsf { a}_{w,\lambda } \ne 0$, then $\lambda (w) \le _D \lambda \le _D \mu (w)$.

Proof of Theorem 5.8

Combine Theorem 5.9 and Proposition 2.5(III).$\square$

Corollary 5.10

Any skew-Schur polynomial $s_{\lambda /\mu }(X)$ has SNP.

Proof

To every skew shape $\lambda /\mu$ there is a 321-avoiding permutation $w_{\lambda /\mu }$ with the property that $F_{w_{\lambda /\mu }}(X)=s_{\lambda /\mu }$ [8]. Now apply Theorem 5.8. $\square$

Let

$$\begin{aligned} S_{\infty ,\ell }=\{w\in S_{\infty }:\ell (w)=\ell \}. \end{aligned}$$

Declare

$$\begin{aligned} u\preceq _{D} v \text { for }u,v\in S_{\infty ,\ell }\text { if }\textsf { Newton}({\mathfrak {S}}_u)\subseteq \textsf { Newton}({\mathfrak {S}}_v). \end{aligned}$$

Given a partition $\lambda =(\lambda _1\ge \lambda _2\ge \cdots \ge \lambda _k>0)$, define $w_{\lambda ,k}\in S_{\lambda _1+k}$ to be the unique permutation that satisfies

$$\begin{aligned} w_{\lambda ,k}(i)=\lambda _{k-i+1}+i \text{ for } 1\le i\le k \end{aligned}$$

and is Grassmannian, i.e., it has at most one descent, at position k. Then one has

$$\begin{aligned} {\mathfrak {S}}_{w_{\lambda ,k}}=s_{\lambda }(x_1,\ldots ,x_k). \end{aligned}$$

We now show that $(S_{\infty },\preceq _D)$ extends $(\textsf { Par}(n),\le _D)$:

Proposition 5.11

Suppose $\lambda ,\mu \in \textsf { Par}(n)$ and let $k=\max \{\ell (\lambda ),\ell (\mu )\}$. Then $\lambda \le _D\mu$ if and only if $w_{\lambda ,k}\preceq _D w_{\mu ,k}$.

Proof

Since ${\mathfrak {S}}_{w_{\lambda ,k}}(x_1,\ldots ,x_k)=s_{\lambda }(x_1,\ldots ,x_k)$ and ${\mathfrak {S}}_{w_{\mu ,k}}(x_1,\ldots ,x_k)=s_{\mu }(x_1,\ldots ,x_k)$,

$$\begin{aligned} {\mathcal {P}}_{\lambda }=\textsf { Newton}(s_{\lambda }(x_1,\ldots ,x_k)) =\textsf { Newton}({\mathfrak {S}}_{w,\lambda }(x_1,\ldots ,x_k)) \subseteq \mathbb {R}^k. \end{aligned}$$

The same statement holds where we replace $\lambda$ by $\mu$. Now apply Rado’s theorem (6). $\square$

Figure 2 shows part of $(S_{\infty ,2},\preceq _D)$. From this one can see that the poset is not graded, just like dominance order $\le _D$ on partitions. Unlike $\le _D$, it is not a lattice: in Fig. 2, the elements 231456 and 312456 do not have a unique least upper bound as 142356 and 214356 are incomparable minimal upper bounds.

Fig. 2

The $S_6$ part of the Hasse diagram of $(S_{\infty ,2},\preceq _D)$

Theorem 5.12

Every two elements $u,v\in S_{\infty ,\ell }$ have an upper bound under $\preceq _D$.

Proof

Suppose $\{\alpha _i\}$ and $\{\beta _j\}$ are the exponent vectors of ${\mathfrak {S}}_u$ and ${\mathfrak {S}}_v$, respectively. It suffices to show there exists $w\in S_{\infty ,\ell }$ such that

$$\begin{aligned} {\mathfrak {S}}_w=\sum _i x^{\alpha _i}+\sum _{j} x^{\beta _j}+\text {(positive sum of monomials)}. \end{aligned}$$

We first show that there is a $F_w$ such that each $s_{\lambda (\alpha _i)}$ and $s_{\lambda (\beta _j)}$ appear (possibly with multiplicity). A theorem of S. Fomin-C. Greene [15] states that

$$\begin{aligned} F_w=\sum _{\nu } \textsf { a}_{w,\nu }s_{\nu } \end{aligned}$$

where $\textsf { a}_{w,\nu }$ is the number of semistandard tableaux of shape $\nu$ such that the top-down, right-to-left reading word is a reduced word for w. Let

$$\begin{aligned} w=s_1 s_{3} s_{5}\cdots s_{2\ell -1}. \end{aligned}$$

Clearly this is a reduced word. All reduced words of w are obtained by permuting the simple transpositions.

Filling any shape of size $\ell$ by successively placing $1,3,5,\ldots ,2\ell -1$ along rows in left to right order gives a semistandard tableaux. Thus every $s_{\mu }$ where $\mu \vdash \ell$ appears in $F_w$. In particular each $s_{\lambda (\alpha _i)}$ and each $s_{\lambda (\beta _j)}$ appears. Since $x^{\lambda (\alpha _i)}$ appears in $s_{\lambda (\alpha _i)}$, by symmetry of $s_{\lambda (\alpha _i)}$, $x^{\alpha _i}$ appears as well. That is, $x^{\alpha _i}$ appears in $F_w$. Similarly $x^{\beta _j}$ appears in $F_w$.

By definition, for any monomial $x^\gamma$ appearing in $F_w$, there is a finite $N_\gamma$ such that $x^\gamma$ appears in ${\mathfrak {S}}_{1^{N_\gamma }\times w}$. It suffices to pick N larger than all $N_{\alpha _i}$ and $N_{\beta _j}$. $\square$

5.3 Conjectural inequalities for the $\textsf { Newton}({\mathfrak {S}}_w)$

Let

$$\begin{aligned} \textsf {D}_w=\{(i, j) : 1 \le i, j \le n, w(i)> j \text { and } w^{-1}(j) > i\} \end{aligned}$$

be the Rothe diagram of a permutation $w\in S_n$.

Conjecture 5.13

${\mathcal {S}}_{\textsf {D}_{w}}=\textsf { Newton}({\mathfrak {S}}_w)$.

This has been checked for all $w \in S_8$, as well as many larger instances. Notice that Conjecture 5.13 is equivalent to the assertion that $w\preceq _D v$ if and only if $\theta _{\textsf {D}_w}(S)\le \theta _{\textsf {D}_v}(S)$ for all $S\subseteq [n]$.

Example 5.14

Suppose $w=21543$, the Rothe diagram $\textsf {D}_w$ is given by

One can check that the defining inequalities are

$$\begin{aligned}&\alpha _1+\alpha _2+\alpha _3+\alpha _4=4\\&\alpha _1\le 3,\ \alpha _2\le 2,\ \alpha _3\le 2,\ \alpha _4\le 1\\&\alpha _1+\alpha _2\le 4,\ \alpha _1+\alpha _3\le 4,\ \alpha _1+\alpha _4\le 4,\ \alpha _2+\alpha _3\le 3,\ \alpha _{2}+\alpha _4\le 3, \alpha _3+\alpha _4\le 3\\&\alpha _1+\alpha _2+\alpha _3\le 4, \ \alpha _1+\alpha _2+\alpha _4\le 4, \ \alpha _2+\alpha _3+\alpha _4\le 3\\&\alpha _1+\alpha _2+\alpha _3+\alpha _4\le 4. \end{aligned}$$

together with $\alpha _i \ge 0$ for each i. The polytope is depicted in Sect. 1.$\square$

One can uniquely reconstruct $u\in S_{\infty }$ with the defining inequalities.

Proposition 5.15

If $u,v\in S_{n}$ are of the same length $\ell =\ell (u)=\ell (v)$ and $\theta _{\textsf {D}_{u}}(S)=\theta _{\textsf {D}_v}(S)$ for all $S=\{i,i+1,\ldots ,n\}$ where $1\le i\le n$, then $u=v$.

Proof

Let

$$\begin{aligned} c_i(\pi )=\#\{j:(i,j)\in \textsf {D}_{\pi }\}. \end{aligned}$$

Thus $(c_1(\pi ),c_2(\pi ),\ldots )$ is the Lehmer code of $\pi$. The Lehmer code uniquely determines $\pi \in S_{\infty }$; see, e.g., [29, Proposition 2.1.2]. Hence it suffices to show the codes of u and v are the same. This follows from:

$$\begin{aligned} \sum _{j=1}^i c_j(u)=\ell -\theta _{\textsf {D}_u}(\{i+1,i+2,\ldots ,n\})=\ell -\theta _{\textsf {D}_v}(\{i+1,i+2,\ldots ,n\})=\sum _{j=1}^i c_j(v), \end{aligned}$$

(15)

for $i=1,2,\ldots n-1$. It remains to show (15). Now, $\sum _{j=1}^i c_j(u)$ is by definition the number of boxes in the first i rows of $\textsf {D}_u$. Since $\ell =\ell (u)=\#\textsf {D}_{u}$, $\sum _{j=1}^i c_j(u)=\ell -\xi _u(i)$ where $\xi _u(i)$ is the number of boxes of $\textsf {D}_u$ in rows $i+1,i+2,\ldots n$. By definition, $\theta ^c_{\textsf {D}_u}(\{i+1,i+2,\ldots ,n\})$ is the number of boxes of $\textsf {D}_u$ in column c and rows $i+1,i+2,\ldots ,n$ (the point being that no paired $(\ )$’s can occur in $\mathtt{word}_{c,\{i+1,i+2,\ldots ,n\}}(\textsf {D}_u)$ and each $\star$ precisely corresponds to one of the said boxes). Hence $\theta _{\textsf {D}_u}(\{i+1,i+2,\ldots ,n\})=\xi _u(i)$, proving the first equality of (15); the third equality is similar. The middle equality is by hypothesis. Thus (15) holds and we are done. $\square$

The inequalities of ${\mathcal {S}}_\textsf {D}$ are in general redundant. If

$$\begin{aligned} \theta _\textsf {D}(S)=\theta _\textsf {D}(T) \text { and }S\supseteq T \end{aligned}$$

(16)

then the inequality

$$\begin{aligned} \sum _{i\in T}\alpha _i\le \theta _\textsf {D}(T) \end{aligned}$$

is unnecessary. Similarly, if

$$\begin{aligned} S= \sqcup _i T_i \text { and }\theta _\textsf {D}(S)=\sum _i \theta _\textsf {D}(T_i) \end{aligned}$$

(17)

then the S-inequality is implied by the $T_i$ inequalities.

Problem 5.16

Give the minimal set of inequalities associated to $\textsf {D}_w$ (or more generally, any $\textsf {D}$).

Example 5.17

Continuing Example 5.14, minimal inequalities are

$$\begin{aligned}&\alpha _1+\alpha _2+\alpha _3+\alpha _4=4\\&\alpha _1\le 3,\ \alpha _2\le 2,\ \alpha _3\le 2,\ \alpha _4\le 1\\&\alpha _2+\alpha _3+\alpha _4\le 3, \end{aligned}$$

combined with positivity. This minimization is obtained using reductions (16) and (17).

Example 5.18

If $w=23154$ then using the reductions (16) and (17) leaves:

$$\begin{aligned} \alpha _1+\alpha _2+\alpha _3+\alpha _4=3, \alpha _3+\alpha _4\le 1, \alpha _1+\alpha _3+\alpha _4\le 2, \alpha _2+\alpha _3+\alpha _4\le 2. \end{aligned}$$

However, $\alpha _3+\alpha _4\le 1$ is actually not necessary.$\square$

Given a polytope P, recall its Ehrhart polynomial, denoted $L_P(t)$, is the polynomial such that for $t \in \mathbb {Z}_{\ge 1}$, $L_P(t)$ equals the number of lattice points in the polytope tP. Ehrhart [12] showed that for a polytope of dimension d in $\mathbb {R}^n$, $L_P(t)$ is in fact a polynomial of degree d. For more see, e.g., [7].

Conjecture 5.19

If $L_{{\mathcal {N}}({\mathcal {S}}_\textsf {D})}(t) = c_dt^d + \cdots + c_0$, then $c_i > 0$ for $i = 0,\ldots ,d.$

Conjecture 5.19 also seems true for ${\mathcal {S}}_\textsf {D}$ where $\textsf {D}$ is arbitrary. We have exhaustively checked this for $n=4$ and many random cases for $n=5$.

Below we give some data about the positive dimensional Schubitopes ${\mathcal {S}}_{\textsf {D}_w}$ for $w\in S_4$:

w	${\mathfrak {S}}_w$	$\dim {\mathcal {S}}_{\textsf {D}_w}$	vertices of ${\mathcal {S}}_{\textsf {D}_w}$	$L_{{\mathcal {S}}_{\textsf {D}_w}}(t)$
1243	$x_1 + x_2 + x_3$	2	(1, 0, 0), (0, 1, 0), (0, 0, 1)	$\frac{1}{2} t^2 + \frac{3}{2}t + 1$
1324	$x_1 + x_2$	1	(1, 0), (0, 1)	$t+1$
1342	$x_1x_2 + x_1x_3 + x_2x_3$	2	(1, 1, 0), (1, 0, 1), (0, 1, 1)	$\frac{1}{2} t^2 + \frac{3}{2}t + 1$
1423	$x_1^2 + x_1x_2 + x_2^2$	1	(2, 0), (0, 2)	$2t+1$
1432	$x_1^2x_2 + x_1x_2^2 + x_1^2x_3 + x_1x_2x_3 + x_2^2x_3$	2	(2, 0, 1), (1, 2, 0), (2, 1, 0), (0, 2, 1)	$\frac{3}{2} t^2 + \frac{5}{2}t + 1$
2143	$x_1^2 + x_1x_2 + x_1x_3$	2	(2, 0, 0), (1, 1, 0), (1, 0, 1)	$\frac{1}{2} t^2 + \frac{3}{2}t + 1$
2413	$x_1^2x_2 + x_1x_2^2$	1	(2, 1), (1, 2)	$t+1$
2431	$x_1^2x_2x_3 + x_1x_2^2x_3$	1	(2, 1, 1), (1, 2, 1)	$t+1$
3142	$x_1^2x_2 + x_1^2x_3$	1	(2, 1, 0), (2, 0, 1)	$t+1$
4132	$x_1^3x_2 + x_1^3x_3$	1	(3, 1, 0), (3, 0, 1)	$t+1$

5.4 Relationship of the Schubitope to Kohnert’s rule

A. Kohnert [22] conjectured a combinatorial rule for ${\mathfrak {S}}_w(X)$. Starting from $\textsf {D}_{w}$ one moves the rightmost box in any row up to the southmost unoccupied square of $n\times n$. Repeating this gives a finite set of diagrams $\textsf { Koh}(w)=\{D\}$. Define

$$\begin{aligned} \mathtt{Kohwt}(D)=\prod x_i^{\#\text {boxes of }D\text { in row }i}. \end{aligned}$$

Let

$$\begin{aligned} {\mathfrak {K}}_w=\sum _{D\in \textsf { Koh}(w)} \mathtt{Kohwt}(D). \end{aligned}$$

The conjecture is that ${\mathfrak {S}}_w={\mathfrak {K}}_w$. For a proof see work of Winkel [47] and of Assaf [3]. With this in hand, one obtains part of Conjecture 5.1, i.e.,

Proposition 5.20

${\mathcal {S}}_{\textsf {D}_w}\supseteq \textsf { Newton}({\mathfrak {K}}_w)$.

Proof

Consider a diagram $D\in \textsf { Koh}(w)$ such that $\mathtt{Kohwt}(D)=\alpha$. Each Kohnert move preserves the number of boxes. Hence $\sum _{i=1}^n \alpha _i=\#\textsf {D}_{w}$ holds.

Now fix a column c and $S\subseteq [n]$. Compare the positions of the boxes of D to the boxes of $\textsf {D}_{w}$. Let

$$\begin{aligned} T_{D,S,c}=\#\text {boxes of }D \text { in the rows of }S \text { and column } c. \end{aligned}$$

Let

$$\begin{aligned} \textsf { V}_{\textsf {D}_w,S,c}=\{(r,r'):r\in S, r'\not \in S, r<r', (r,c)\not \in \textsf {D}_{w} \text { but }(r',c)\in \textsf {D}_{w}\}. \end{aligned}$$

Also, let $U_{\textsf {D}_w,S,c}$ be the maximum size of any $\textsf { X}_{\textsf {D}_w,S,c}\subseteq \textsf { V}_{\textsf {D}_w,S,c}$ such that if $(x,x'), (y, y')\in \textsf { X}_{\textsf {D}_w,S,c}$ then $x\ne y$ and $x'\ne y'$. Now, since Kohnert moves only bring boxes in from lower rows into higher rows (i.e., boxes migrate from the south),

$$\begin{aligned}\ T_{D,S,c}\le T_{\textsf {D}_{w},S,c}+U_{\textsf {D}_w,S,c}. \end{aligned}$$

Now it is easy to check from the definitions that

$$\begin{aligned} \theta _{\textsf {D}_w}^c(S)=T_{\textsf {D}_{w},S,c}+U_{\textsf {D}_w,S,c}. \end{aligned}$$

Since $\alpha _i$ counts the number of boxes in row i of D, we have

$$\begin{aligned} \sum _{i\in S}\alpha _i =\sum _c T_{D,S,c} \le \sum _c T_{\textsf {D}_{w},S,c}+U_{\textsf {D}_w,S,c} =\sum _c \theta _{\textsf {D}_w}^c(S) =\theta _{\textsf {D}_w}(S), \end{aligned}$$

as required. $\square$

Remark 5.21

Unlike the computation of each $\theta _D^c(s)$, the Kohnert moves are not column independent. Perhaps surprisingly, Conjecture 5.1 says that the a priori coarse upper bound on $\sum _{i\in s} \alpha _i$ captures all monomials appearing in the Schubert polynomial. $\square$

Remark 5.22

Kohnert’s rule extends to key polynomials (with proof). Hence a similar argument (which we omit) establishes the “$\supseteq$” containment of Conjecture 3.9. $\square$

Fix a partition $\lambda =(\lambda _1,\lambda _2,\ldots ,\lambda _n)$. Let $\textsf {D}_{\lambda }$ be the Young diagram for $\lambda$ (in French notation) placed flush left in $n\times n$ (hence row n has $\lambda _1$ boxes).

Proposition 5.23

(The Schubitope is a generalized permutahedron) ${\mathcal {S}}_{\textsf {D}_{\lambda }}={\mathcal {P}}_{\lambda }\subset {\mathbb {R}}^n$.

Lemma 5.24

If $w(i) < w(i+1)$, ${\mathcal {S}}_{\textsf {D}_{w}}$ is symmetric about i and $i+1$. That is,

$$\begin{aligned} (\alpha _1,\alpha _2,\ldots ,\alpha _i,\alpha _{i+1},\ldots ,\alpha _n)\in {\mathcal {S}}_{\textsf {D}_w} \iff (\alpha _1,\alpha _2,\ldots ,\alpha _{i+1},\alpha _{i},\ldots ,\alpha _n)\in {\mathcal {S}}_{\textsf {D}_w}. \end{aligned}$$

Proof

Suppose $S \subseteq [n]$ such that $i \in S, i+1 \notin S$. Let $S'$ be the set formed from S by replacing i with $i+1$. Then it suffices to show for any column c,

$$\begin{aligned} \theta _{\textsf {D}_w}^c(S) = \theta _{\textsf {D}_w}^c(S'). \end{aligned}$$

Since $w(i) < w(i+1)$, if $(i,c) \in \textsf {D}_w$, then $(i+1,c) \in \textsf {D}_w$ as well. There are three cases:

Case 1: ($(i,c), (i+1,c) \in {\textsf {D}_w}$): in $\mathtt{word}_{c,S}(\textsf {D}_w)$, rows $i,i+1$ contribute $\star )$ whereas in $\mathtt{word}_{c,S'}(\textsf {D}_w)$ the contribution is $)\star$. The ) does not change whether or not it is paired and thus $\theta _{\textsf {D}_w}^c(S) = \theta _{\textsf {D}_w}^c(S')$.

Case 2: ($(i,c) \notin \textsf {D}_w, (i+1,c) \in \textsf {D}_w$): in $\mathtt{word}_{c,S}(\textsf {D}_w)$, rows $i,i+1$ contributes (). In $\mathtt{word}_{c,S'}(\textsf {D}_w)$, the contribution is only ‘$\star$’. Both contribute 1 to $\theta _{\textsf {D}_w}^c(S)$ and $\theta _{\textsf {D}_w}^c(S')$ respectively. Hence $\theta _{\textsf {D}_w}^c(S) = \theta _{\textsf {D}_w}^c(S')$.

Case 3: ($(i,c), (i+1,c) \notin \textsf {D}_w$): in both $\mathtt{word}_{c,S}(\textsf {D}_w)$ for rows $i,i+1$ and $\mathtt{word}_{c,S'}(\textsf {D}_w)$, rows i and $i+1$ contribute (. The ( does not change whether or not it is paired and so $\theta _{\textsf {D}_w}^c(S) = \theta _{\textsf {D}_w}^c(S')$. $\square$

Proof of Proposition 5.23

By Proposition 2.5(I),

$$\begin{aligned} \textsf { Newton}(s_{\lambda }(x_1,\ldots ,x_n))={\mathcal P}_{\lambda }\subseteq {\mathbb {R}}^n \end{aligned}$$

(18)

Let $w_{\lambda ,n}$ be the Grassmannian permutation associated to $\lambda$. This permutation only has descent at position n. Then

$$\begin{aligned} {\mathfrak {S}}_{w_{\lambda ,n}}=s_{\lambda }(x_1,\ldots ,x_n). \end{aligned}$$

(19)

We next show that

$$\begin{aligned} {\mathcal S}_{\textsf {D}_{w_{\lambda ,n}}}=\textsf { Newton}({\mathfrak {S}}_{w_{\lambda ,n}}). \end{aligned}$$

(20)

The “$\supseteq$” containment of (20) is given by Proposition 5.20. In the case at hand, this proposition can be deduced from A. Kohnert’s work [22] who proved his conjecture for Grassmannian permutations. Below we will use that in loc cit., A. Kohnert proved the Grassmannian case by giving a weight-preserving bijection $\phi :\textsf { SSYT}(\lambda ,[n])\rightarrow \mathtt{Koh}(w_{\lambda ,n})$, where $\textsf { SSYT}(\lambda ,[n])$ is the set of semistandard tableaux of shape $\lambda$ with fillings using $1,2,\ldots ,n$.

We now obtain the other containment of (20). Let $(\alpha _1,\alpha _2,\ldots ,\alpha _n)\in {\mathcal {S}}_{\textsf {D}_{w_{\lambda ,n}}}$. In fact, $\textsf {D}_{w_{\lambda ,n}}$ differs from $\textsf {D}_{\lambda }$ by removing empty columns and left justifying. Hence it is clear from the definition of ${\theta }_{\textsf {D}_{\lambda }}(S)$ that

$$\begin{aligned} \sum _{i=1}^t \alpha _i \le \sum _{i=1}^t \lambda _i \text { for } t=1,\ldots ,n. \end{aligned}$$

(21)

Lemma 5.24 implies that $\textsf {D}_{w_{\lambda ,n}}$ has an $S_n$-action by permutation of the coordinates. Hence if $\beta =\lambda (\alpha )$ is the decreasing rearrangement of $\alpha$, then $\beta$ also satisfies (21), where $\beta$ replaces $\alpha$. That is, $\beta \le _D\lambda$.

Therefore by (3), $K_{\lambda ,\beta }\ne 0$ and there exists a semistandard tableau of shape $\lambda$ and content $\beta$. By symmetry of $s_{\lambda }(x_1,\ldots ,x_n)$ (and the fact it is the weight-generating series for $\textsf { SSYT}(\lambda ,[n])$), there is a semistandard tableau U of shape $\lambda$ and content $\alpha$.

Now apply Kohnert’s bijection $\phi$ to contain $D\in \mathtt{Koh}(w_{\lambda ,n})$ with $\mathtt{Kohwt}(D)=\alpha$, as desired. This completes the proof of (20).

Since $\textsf {D}_w$ and $\textsf {D}_{\lambda }$ only differ by a column permutation ${\mathcal {S}}_{\textsf {D}_{\lambda }}= {\mathcal {S}}_{\textsf {D}_{w_{\lambda ,n}}}$. Now combine this with (20), (19) and (18). $\square$

The above result can be also deduced by comparing the inequalities of ${\mathcal {S}}_{\textsf {D}_{\lambda }}$ with those for ${\mathcal P}_{\lambda }$. However, the above argument has elements that might apply more generally.

6 Post submission update (June 2019)

Since this paper was initially submitted (March 2017), a number of developments connected to this work have occurred. We briefly summarize these here, listed in arXiv chronological order:

• (a) K. Mészáros and A. St. Dizier [31] prove Conjecture 5.5 for the special case when $w=1w'$ and $w'$ is 132-avoiding. This paper also contains a Conjecture (with A. Fink) that refines Conjecture 5.5.

• (b) L. Escobar and the third author [13] prove the aforementioned conjecture (a) of A. Fink-K. Mészáros-A. St. Dizier, and thus Conjecture 5.5, in the case w is a Grassmannian permutation.

• (c) A. Fink-K. Mészáros-A. St. Dizier [14] proved Conjectures 3.9, 3.10, 5.1 and 5.13.

• (d) A. Woo and the third author [48] applied Corollary 5.10, and more precisely, Proposition 2.5 to disprove a Conjecture of D. Grigoriev-G. Koshevoy on the tropical semiring complexity of tropical skew Schur polynomials.

• (e) A. Adve, C. Robichaux and the third author [1] propose a computational complexity significance of the notion of SNP. In addition, using the results from [14]. In addition [1] gives the first polynomial time algorithm for deciding if a monomial coefficient of ${\mathfrak {S}}_w$ is nonzero.