Let $\mathcal{P}_n$ be the polynomial ring $k\left[x_1, x_2, \ldots, x_n\right]$.

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\;\;\;\mbox{and}\;\;\; \partial_i\partial_{i+1}\partial_i=\partial_{i+1}\partial_i\partial_{i+1}$$
for $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 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 $\mathcal{P}_n$ is free over $NH_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$

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


\textbf{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$