Let $\text{char}\,k = 0$ and $n \ge 2$. What is the easiest way to see that $k[x_1, \dots, x_n]$ is a free $k[x_1, \dots, x_n]^{S_n}$-module with basis$$x_2^{m_2}x_3^{m_3} \dots x_{n-1}^{m_{n-1}} x_n^{m_n},\text{ }m_2 \in [0, 1],\text{ }m_3 \in [0, 2], \dots,\text{ }m_n \in [0, n-1]?$$

  • $\begingroup$ The characteristic-$0$ assumption is useless. $\endgroup$ – darij grinberg Sep 2 '15 at 15:31
  • 1
    $\begingroup$ By writing down the Poincare Series, we see that the dimension is correct. So you need to prove either it is free or it generates, whichever is easier. $\endgroup$ – user43326 Sep 2 '15 at 17:05
  • $\begingroup$ It would be more constructive to explain why the characteristic 0 assumption isn't needed. One proof I've seen of this uses the averaging operator for $S_n$, which isn't defined in characteristic less than $n$. $\endgroup$ – Peter Samuelson Sep 3 '15 at 0:01
  • $\begingroup$ @PeterSamuelson: Sure it would, but two people beat me to it before I could even remind myself of how the proof went. $\endgroup$ – darij grinberg Sep 3 '15 at 0:07
  • $\begingroup$ Another source (though with far less useful answers): math.stackexchange.com/questions/1004341/… $\endgroup$ – darij grinberg Sep 3 '15 at 0:11

It is enough to show that the given generators span $k[x_1, \ldots, x_n]$ as a $k[x_1, \ldots, x_n]^{S_n}$ module. Once we've shown this, it is easy to see that $k(x_1, \ldots, x_n)$ is dimension $n!$ as a $k(x_1, \ldots, x_n)^{S_n}$ vector space, so $n!$ vector which span must be linearly independent.

Notation: For every $r \in \left\{0,1,\ldots,n\right\}$, let $e^r_k$ be the $k$-th elementary symmetric polynomial in $x_1$, ..., $x_r$. Let $R = k[x_1, \ldots, x_n]$ and let $A = R^{S_n}$.

Lemma 1 The polynomial $e^r_k$ is in the ring $A[x_{r+1}, \ldots, x_n]$.

Proof Induction on $n-r$. The base case, $r=n$, is that $e_k(x_1, \ldots, x_n) \in A$; this is true. Now, $e_k^r = e_k^{r+1} - x_{r+1} e_{k-1}^{r +1}$, so the result follows by induction. $\square$.

Lemma 2 The monomial $x_r^r$ is in the $A[x_{r+1}, \ldots, x_n]$-linear span of monomials of the form $x_r^s$ with $0 \leq s < r$.

Proof Expand $(x_r-x_1) (x_r-x_2) \cdots (x_r-x_r) = 0$ to get $x_r^r - e^r_1 x_r^{r-1} + e^r_2 x_r^{r-2} - \cdots = 0$ or, in other words, $x_r^r = \sum_{s=0}^{r-1} (-1)^{r-s+1} x_r^s e^r_{r-s}$. Now apply Lemma 1. $\square$

We now prove the following result by induction on $r$:

The ring $R$ is spanned as an $A[x_{r+1}, \ldots, x_n]$-module by monomials of the form $x_1^{d_1} x_2^{d_2} \cdots x_r^{d_r}$ with $0 \leq d_j < j$.

The base case $r=0$ is trivial (it says $R = A \cdot 1$); the case $r=n$ is the claim.

We now do the inductive step. Since $R$ is spanned as an $A[x_{r}, \ldots, x_n]$-module by monomials of the form $x_1^{d_1} x_2^{d_2} \cdots x_{r-1}^{d_{r-1}}$ with $0 \leq d_j < j$, we know that $R$ is spanned as an $A[x_{r+1}, \ldots, x_n]$-module by monomials of the form $x_1^{d_1} x_2^{d_2} \cdots x_{r-1}^{d_{r-1}} x_r^t$, with $0 \leq d_j < j$, and no bound on $t$. But Lemma 2 allows us to replace $x_r^t$ by lower powers of $x_r$ if $t \geq r$. QED


Let $\mathcal{P}_n$ be the polynomial ring $k\left[x_1, x_2, \ldots, x_n\right]$. The symmetric group $S_n$ acts on $\mathcal{P}_n$ from the left by the formula $${}^\pi f = f\left(x_{\pi\left(1\right)}, x_{\pi\left(2\right)}, \ldots, x_{\pi\left(n\right)}\right)$$ for all $\pi \in S_n$ and $f \in \mathcal{P}_n$. We let $s_1, s_2, \ldots, s_{n-1}$ denote the $n-1$ adjacent transpositions generating $S_n$ (so $s_i = \left(i,i+1\right)$ for each $i$).

For $i=1,\ldots,n-1$, let $$\partial_i:\mathcal{P}_n\longrightarrow\mathcal{P}_n$$ be the divided difference operator $$\partial_i(f)=\frac{f-{}^{s_i}f}{x_{i+1}-x_i}.$$ (It is easy to see that $\partial_i(f) \in \mathcal{P}_n$ for every $f \in \mathcal{P}_n$, so this is well-defined.)

Let $$NC_n=\langle \partial_i\mid i=1,\ldots,n-1\rangle$$ be the algebra generated by the $\partial_i$. This is called the NilCoxeter algebra. It is clear that $\ker\partial_i=\mathrm{Im}\partial_i$ consists of polynomials which are symmetric in $x_i$ and $x_{i+1}$. It follows that \begin{align*} \partial_i^2&=0&(1) \end{align*}

Exercise: Verify that the following relations hold in $NC_n$: $$\partial_i\partial_j=\partial_j\partial_i\mbox{ if }|i-j|>1,$$ and $$\partial_i\partial_{i+1}\partial_i=\partial_{i+1}\partial_i\partial_{i+1} \mbox{ if } i<n-1.$$

Now, define the NilHecke algebra to be $$NH_n=NC_n\ltimes\mathcal{P}_n.$$ The mixed relations are given by $$\partial_i f={}^{s_i}f\partial_i+\partial_i(f).$$ For example, \begin{align*} \partial_ix_i&=x_{i+1}\partial_i-1\\ \partial_ix_{i+1}&=x_i\partial_i+1\\ \partial_ix_j&=x_j\partial_i\mbox{ if }j\neq i,i+1. \end{align*}

If $w=s_{i_1}\cdots s_{i_k}$ is a reduced expression for $w\in S_n$, the braid relations (and Matsumoto's theorem for the standard presentation of $S_n$ as a Coxeter group) imply that the element $$\partial_w=\partial_{i_1}\cdots\partial_{i_k}$$ is well defined. Moreover, by (1) we have $$\partial_u\partial_v=\begin{cases}\partial_{uv}&\mbox{if }\ell(u)+\ell(v)=\ell(uv),\\ 0&\mbox{otherwise}.\end{cases}$$

Exercise: Show that $NH_n$ is free over $\mathcal{P}_n$of rank $n!$.

The main goal of this set of notes is to prove the following theorem:

Theorem: $\mathcal{P}_n$ is free over $\mathcal{P}_n^{S_n}$ of rank $n!$.

To do this, we need Schubert polynomials. Recall that for $\alpha=(\alpha_1,\ldots,\alpha_n)\in\mathbb{Z}_+^n$, $$x^\alpha=x_1^{\alpha_1}x_2^{\alpha_2}\cdots x_n^{\alpha_n}.$$ Let $\delta=(0,1,\ldots,n-1)$, so $x^\delta=x_2x_3^2\cdots x_n^{n-1}$.

Define the Schubert polynomial $$S_w=\partial_{w^{-1}w_0}(x^\delta)\in\mathcal{P}_n,$$ where $w_0\in S_n$ is the longest element.

Example: Consider $S_3=\{e,s_1,s_2,s_1s_2,s_2s_1,s_1s_2s_1\}$, so the Schubert polynomials belong to $\mathcal{P}_3=F[x_1,x_2,x_3]$. \begin{align*} S_{s_1s_2s_1}&=x_2x_3^2\\ S_{s_2s_1}&=\partial_1(x_2x_3^2)=\frac{x_2-x_1}{x_2-x_1}x_3^2=x_3^2\\ S_{s_1s_2}&=\partial_2(x_2x_3^2)=\frac{x_2x_3^2-x_3x_2^2}{x_3-x_2}=x_2x_3\\ S_{s_2}&=\partial_1\partial_2(x_2x_3^2)=\partial_1(x_2x_3)=x_3\\ S_{s_1}&=\partial_2\partial_1(x_2x_3^2)=\partial_2(x_3^2)=x_2+x_3\\ S_e&=\partial_2\partial_1\partial_2(x_2x_3^2)=\partial_2(x_3)=1. \end{align*}

Proposition: We have $$\partial_uS_w=\begin{cases} S_{wu^{-1}}&\mbox{if }\ell(wu^{-1})=\ell(w)-\ell(u)\\ 0&\mbox{otherwise}\end{cases}$$

Proof: Note that $\partial_uS_w=\partial_u\partial_{w^{-1}w_0}(x^\delta)$. We have $$\partial_u\partial_{w^{-1}w_0}=\begin{cases}\partial_{(wu^{-1})^{-1}w_0}&\mbox{if }\ell(uw^{-1}w_0)=\ell(u)+\ell(w^{-1}w_0)\\0&\mbox{otherwise.}\end{cases}$$ Now, $$\ell(uw^{-1}w_0)=\ell(w_0)-\ell(uw^{-1})=\ell(w_0)-\ell(wu^{-1})$$ and $$\ell(u)+\ell(w^{-1}w_0)=\ell(u)+\ell(w_0)-\ell(w^{-1})=\ell(u)+\ell(w_0)-\ell(w).$$ The result follows. $\square$

Proposition: The Schubert polynomial $S_w$ is homogeneous of degree $\ell(w)$.

Proof: Note that $\deg(x^\delta)=1+2+\cdots+(n-1)={n\choose 2}=\ell(w_0)$. Now, let $\mathcal{P}_n^d$ be the degree $d$ component of $\mathcal{P}_n$. Then, $$\partial_i:\mathcal{P}_n^d\longrightarrow\mathcal{P}_n^{d-1}$$ so $$\deg (S_w)=\deg (\partial_{w^{-1}w_0}(x^\delta))={n\choose 2}-\ell(w^{-1}w_0)={n\choose 2}-\ell(w_0)+\ell(w)=\ell(w).$$ $\square$

Let $\mathcal{A}_n$ be the subspace of $\mathcal{P}_n$ with basis $\{x^\alpha\mid \alpha\subseteq\delta\}$, where $\alpha\subseteq\delta$ means $\alpha_1=0$, $\alpha_2\leq 1$, $\alpha_3\leq 2$, $\ldots$, $\alpha_{n}\leq n-1$. Note that $\dim\mathcal{A}_n=n!$.

Exercise: Prove that the Schubert polynomials belong to $\mathcal{A}_n$.

Proposition: The Schubert polynomials form a basis of $\mathcal{A}_n$.

Proof: It is straighforward to proof that the Schubert polynomials belong to $\mathcal{A}_n$, so they span a subspace of $\mathcal{A}_n$. Let's prove they are linearly independent. Indeed, suppose that we have \begin{align*} 0&=\sum_w a_w S_w.&(2)\end{align*} Since we've proved the Schubert polynomial $S_w$ is homogeneous of degree $\ell(w)$, we may assume this sum is over $w\in S_n$ such that $\ell(w)=k$. If $k=0$, there is only one such polynomial, $S_{e}$. Therefore, in this case $a_{e}=0$.

Now assume that $k\neq 0$. Note that if $\ell(w)=\ell(v)$, then $\partial_wS_v=0$ unless $w=v$ since \begin{align*} \partial_w(S_v)&=\begin{cases}S_e&\mbox{if }\ell(vw^{-1})=0\\0&\mbox{otherwise.}\end{cases}&(3) \end{align*} Therefore, applying $\partial_v$ to (2) we obtain $$0=\partial_v\left(\sum_w a_w S_w\right)=\sum_w a_w \partial_v(S_w)=a_v$$ Doing this for all $v\in S_n$ with $\ell(v)=k$ shows that the $S_w$ are linearly independent.

Finally, since $\dim\mathcal{A}_n=n!=|S_n|=|\{S_w\mid w\in S_n\}|$, we must have $\mathcal{A}_n=\mathrm{span}\{S_w\mid w\in S_n\}$. This completes the proof. $\square$

Proposition: The multiplication map $\mathcal{A}_n\otimes\mathcal{P}_n^{S_n}\longrightarrow \mathcal{P}_n$ is an isomorphism.

The easiest way to prove this is to observe the following.

Exercise: The following holds for $f,g\in\mathcal{P}_n$: $\partial_i(fg)=\partial_i(f)g+{}^{s_i}f\partial_i(g)$.

Given this exercise, we now prove the proposition.

Proof: We first show that the multiplication map spans. To do this, recall the elementary symmetric functions $$e_k(x_1,\ldots,x_n)=\sum_{1\leq i_1<i_2<\cdots<i_k\leq n} x_{i_1}x_{i_2}\cdots x_{i_k}\in\mathcal{P}_n^{S_n}.$$ It is well known that $\mathcal{P}_n^{S_n}=F[e_1,\ldots,e_n]$.

The following identity is easy to prove: $$e_k(x_1,\ldots,x_{n-1})=\sum_{j=0}^n(-1)^jx_n^je_{k-j}(x_1,\ldots,x_n).$$ Using this identity, we see that $\mathcal{P}_n^{S_n}[x_n]=\mathcal{P}_{n-1}^{S_{n-1}}[x_n]$. Assume by induction on $n$ that the map $\mathcal{A}_{n-1}\otimes\mathcal{P}_{n-1}^{S_{n-1}}\to\mathcal{P}_n$ is surjective (it is certainly true when $n=1$). Then, we can express any $f\in\mathcal{P}_n$ as $f=\sum_k f_k(x_1,\ldots,x_{n-1})x_n^k$, which in turn can be written as $$f=\sum_{k\geq 0}\sum_j a_{k,j} \sigma_{k,j} x_n^k$$ where $a_{k,j}\in\mathcal{A}_{n-1}$, $\sigma_{k,j}\in\mathcal{P}_{n-1}^{S_{n-1}}$.

We are almost done, except that we need to somehow bound $k$ in the expression above by $n-1$. To do this, recall that the generating series for the elementary functions is $$\prod_{i=1}^n(1+x_it)=\sum_{k\geq 0}e_k(x_1,\ldots,x_n)t^k.$$ Hence, $$\prod_{i=1}^n(x_n+x_it)=\sum_{k\geq 0}x_n^{n-k}e_k(x_1,\ldots,x_n)t^k.$$ Plugging $t=-1$ into this expression, we get $$0=\prod_{i=1}^n(x_n-x_i)=\sum_{k\geq0}(-1)^kx_n^{n-k}e_k(x_1,\ldots,x_n)t^k.$$ Therefore, $$x_n=\sum_{k\geq 1}(-1)^{k+1}x_n^{n-k}e_k(x_1,\ldots,x_n).$$ This shows the map is surjective.

To prove the map is injective, suppose we have \begin{align*} 0=&\sum_{w}f_w S_w&(4) \end{align*} where $f_w\in\mathcal{P}_n^{S_n}$. Note that by the previous exercise, $\partial_i(f_wS_w)=\partial_i(f_w)S_w+{}^{s_i}f_w\partial_i(S_w)$. Since $f_w$ is symmetric in $x_i$ and $x_{i+1}$, $\partial_i(f_w)=0$ and ${}^{s_i}f_w=f_w$. Hence, $\partial_i(f_wS_w)=f_w\partial_i(S_w)$.

Now, let $v$ have maximal length such that $f_v\neq 0$. Then, applying $\partial_v$ to (4) we have by (3) $$0=\sum_wf_w\partial_v(S_w)=f_v$$ a contradiction. This completes the proof. $\square$

  • $\begingroup$ Great ! and explicit (+1). One of my masters, A. Lascoux, used to tell the same proof ! $\endgroup$ – Duchamp Gérard H. E. Sep 2 '15 at 17:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.