Free $k[x_1, \dots, x_n]^{S_n}$-module?

Question

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]?$$

Answer 1

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

Answer 2

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$