# A basis of the symmetric power consisting of powers

I have asked this question on math.se, but did not get an answer - I was quite surprised because I thought that lots of people must have though about this before:

Let $V$ be a complex vector space with basis $x_1,\ldots,x_n\in V$. Denote by $v_1\odot\cdots\odot v_k$ the image of $v_1\otimes\cdots\otimes v_k$ in the symmetric power $\newcommand{\Sym}{\mathrm{Sym}}\Sym^k(V)$. It is well-known that the Elements $v^{\odot k}$ for $v\in V$ generate this space (see, for instance, this answer on math.se), so they must contain a basis.

In other words, let $N=\binom{n+k-1}k$, then there must be $v_1,\ldots,v_N\in V$ with $$\mathrm{Sym}^k V = \mathbb Cv_1^{\odot k} \oplus \cdots \oplus \mathbb C v_N^{\odot k}.$$ I am looking for an explicit description of such a basis. Is such a description known? Is there maybe even a "nice" or somewhat "natural" choice for the $v_i$ as linear combinations of the $x_i$?

-
The best reason I know of that powers of linear forms span $Sym^k(V)$ is that $Sym^k(V)$ is an irreducible $GL(V)$-module. Hence, the orbit of any particular (non-zero) power must span the entire space. After choosing the standard basis for $V$ as $e_1,\dots,e_n$ and viewing $GL(V)$ as square matrices, a highest weight vector for $Sym^k(V)$ is $e_1^k$. Hence, to obtain a basis one only needs to apply lowering operators to this element (which are lower triangular matrices). The proper choice of lowering operators will yield a basis. – Andy B May 1 '13 at 19:15

I would look up a book on the calculus of finite differences in a multivariate setting. The claim here is to show that for any multi-index $\alpha=(\alpha_1,\ldots,\alpha_n)$ of length $k$ one can express the multiple derivative at zero $$\left(\frac{\partial}{\partial t}\right)^\alpha \ (t_1x_1+\cdots+ t_n x_n)^k$$ as a linear combination of finite difference analogous expressions which should only involve the evaluation of $(t_1x_1+\cdots+ t_n x_n)^k$ at integer points $(t_1,\ldots,t_n)$ with nonnegative coordinates adding up to $k$. This is the same as the above candidate basis considered by you and Peter. I don't know if there exists a multivariate analogue of the Newton series. If so then this would immediately imply the wanted statement.

Edit: Apparently there is such a formula due to Lascoux and Schutzenberger, see Theorem 9.6.1 page 148 in the book "Symmetric functions and combinatorial operators on polynomials" by Alain Lascoux. Another source on the web is here. It also has the required property here which is that the number of finite differences taken is the same as the degree of the multiplying Schubert polynomial.

Edit: @Jesko you're right it is a bit more complicated than what I said. Also, the Lascoux-Schutzenberger formula might not be the simplest to use here.

First note that expressions $$\prod_{i=1}^{n-1} (x_i-x_n)^{\beta_i}\ \times\ (kx_n)^{k-|\beta|}\ ,$$ where $\beta$ ranges over multiindices with $n-1$ components and length $|\beta|\le k$, form a basis. Now you get the latter as derivatives $$\left(\frac{\partial}{\partial t}\right)^{\beta} \ \left(t_1x_1+\cdots+ t_{n-1} x_{n-1}+\left(k-\sum_{i=1}^{n-1}t_i\right)x_n\right)^k$$ at $t=0$.

Call $f(t_1,\ldots,t_{n-1})$ the polynomial function to be hit with derivatives. One has a multivariate Newton expansion for it: $$f(t)=\sum_{m} (t-a)^m \partial^m f(a_{11},a_{21},\ldots,a_{n-1,1})$$ as follows. Here $a$ stands for a matrix of indeterminates $(a_{ij})$ with $1\le i\le n-1$ and $1\le j\le d$, with $d$ high enough. Let $\partial_{ij}$ denote the divided difference operator acting on functions of these indeterminates as $$\partial_{ij} g=\frac{1}{a_{i,j+1}-a_{ij}}\left( g({\rm argument\ with\ }a_{i,j+1}\ {\rm and}\ a_{ij}\ {\rm exchanged})- g \right)\ .$$ The notation $m=(m_1,\ldots,m_{n-1})$ is for a multiindex with nonnegative entries. We also write the corresponding operator $$\partial^m = \prod_{i=1}^{n-1} \left(\partial_{i, m_i} \cdots\partial_{i,2}\partial_{i,1}\right)$$ noting that finite difference operators concerning different groups of variables commute. Finally $$(t-a)^m=\prod_{i=1}^{n-1} \left((t_i-a_{i,m_i})\cdots(t_i-a_{i,2})(t_i-a_{i,1})\right)\ .$$ The formula basically amounts to applying Newton's univariate formula in each coordinate direction separately. Now use this with the choice $a_{i,j}=j-1$, then take the beta derivative in the $t$'s and that should be it.

-
Hey! This sounds like a really great approach, but I must confess I do not see (at all) how the formula in Theorem 9.6.1 implies the claim that all the $(\sum_i \alpha_i x_i)^k$ form a basis of the degree-$k$ polynomials. Would you mind giving a little more detail? I would really appreciate it. – Jesko Hüttenhain May 8 '13 at 8:18
@Jesko: see my last edit. – Abdelmalek Abdesselam May 8 '13 at 19:10
I still didn't find the time to go through all the details, but I think I got the general idea now, and this answer should definitely be accepted. Thanks a bunch! – Jesko Hüttenhain May 31 '13 at 11:49

Can you work with polarization?
$2 x_1x_2 = (x_1-x_2)^2 -x_1^2-x_2^2$.
If $k=2$ then $(x_i+x_j)^2$ for $i\le j$ is already a basis.
In general, $(x_{i_1}+\dots +x_{i_k})^k$ for $1\le i_1\le\dots\le i_k\le n$ might do the job.

-
That's basically the elements from the proof I referenced, but for $k>2$ it requires more than $\binom{n+k-1}k$ terms, namely all the $(x_{i_1}+\cdots+x_{i_j})^k$ for $2\le j\le k$. It's not obvious to me why only the ones for $j=k$ should suffice. – Jesko Hüttenhain Apr 17 '13 at 9:44
Is not $(x_1+x_1+x_2)^3$ as good as $(x_1+x_2)^3$? – Peter Michor Apr 17 '13 at 11:53
Oh, don't get me wrong, these elements were my first choice as well and I very much believe that they work, but I can't prove it. – Jesko Hüttenhain Apr 17 '13 at 12:08

Is this along the lines of what you were looking for?

Suppose $\{e_1,\ldots,e_n\}$ is a basis for $V$ over $\mathbb{C}$. Then I claim that the set $\mathcal{B}=\{e_1^{a_1}\odot\cdots\odot e_n^{a_n} \, | \, \sum_{i=1}^n a_i=k\}$ is a basis for $S^k(V)$ (where by $e_i^{a_i}$ I mean the $a_i$-fold product $e_i\odot\cdots\odot e_i$). This set definitely spans $S^k(V)$. To see that it is linearly independent, consider the symmetric $k$-multilinear function $f:V^k \to \mathbb{C}[x_1,\ldots,x_n]_{(k)}$ (the degree $k$ homogeneous component of $\mathbb{C}[x_1,\ldots,x_n]$), sending $(v_1,\ldots,v_k) \mapsto \prod_{i=1}^k(\sum_{j=1}^na_{ij}x_j)$, where $v_i=\sum_{j=1}^na_{ij}e_j$. Appealing to the universal property of $S^k(V)$ yields a unique $\mathbb{C}$-linear map $g_k:S^k(V) \to \mathbb{C}[x_1,\ldots,x_n]_{(k)}$ such that $g_k(v_1\odot\cdots\odot v_k)=\prod_{i=1}^k(\sum_{j=1}^na_{ij}x_j)$. In particular, $g_k(e_1^{a_1}\odot\cdots\odot e_n^{a_n})=x_1^{a_1}\cdots x_n^{a_n}$ for every $(a_1,\ldots,a_n) \in \mathbb{Z}_{\geq 0}^n$ with $\sum_{i=1}^n a_i=k$. Since $\{x_1^{a_1}\cdots x_n^{a_n} \, | \, \sum_{i=1}^na_i=k\}$ is a basis for $\mathbb{C}[x_1,\ldots,x_n]_{(k)}$ we deduce that $\mathcal{B}$ is linearly independent.

-
The elements of your $B$ are not powers, but monomials. – Mariano Suárez-Alvarez Nov 6 '13 at 5:04
What @MarianoSuárez-Alvarez said. – Jesko Hüttenhain Nov 6 '13 at 7:54
Could you explain your objection? – dmdmdmdmdmd Nov 7 '13 at 18:52