Polarization formula.

Let $V$ be a $\mathbb{R}$-vector space. Let $\Phi:V^n\to\mathbb{R}$ a multilinear symmetric operator.

Is it true and how do we show that for any $v_1,\ldots,v_n\in V$, we have:

$$\Phi[v_1,\ldots,v_n]=\frac{1}{n!} \sum_{k=1}^n \sum_{1\leq j_1<\cdots<j_k\leq n} (-1)^{n-k}\phi (v_{j_1}+\cdots+v_{j_k}),$$ where $\phi(v)=\Phi(v,\ldots,v)$.

My question come from that, I have seen this formula when I was reading about mixed volume, and also when I was reading about mixed Monge-Ampère measure. The setting was not exactly the one of a vector space $V$ but I think the formula is true here and I am interested by having this property shown out of the specific context of Monge-Ampère measures or volumes. I have done some work in the other direction, i.e. starting from an operator $\phi:V\to\mathbb{R}$ satisfying some condition and obtaining a multilinear operator $\Phi$ ; bellow are the results I have seen in this direction.

I already know that if $\phi':V\to\mathbb{R}$ is such that for any $v_1,\ldots,v_n\in V$, $\phi'(\lambda_1 v_1+\ldots+\lambda_n v_n)$ is a homogeneous polynomial of degree $n$ in the variables $\lambda_i$, then there exists a unique multilinear symmetric operator $\Phi':V^n\to\mathbb{R}$ such that $\Phi'(v,\ldots,v)=\phi'(v)$ for any $v\in V$. Moreover $\Phi'(v_1,\ldots,v_n)$ is the coefficient of the symmetric monomial $\lambda_1\cdots\lambda_n$ in $\phi'(\lambda_1 v_1+\ldots+\lambda_n v_n)$ (see Symmetric multilinear form from an homogenous form.).

I also know that if $\phi'(\lambda v)=\lambda^n \phi'(v)$ and we define $$\Phi''(v_1,\ldots,v_n)=\frac{1}{n!} \sum_{k=1}^n \sum_{1\leq j_1<\cdots<j_k\leq n} (-1)^{n-k}\phi' (v_{j_1}+\cdots+v_{j_k}),$$ then $\Phi''(v,\ldots,v)=\frac{1}{n!} \sum_{k=1}^n (-1)^{n-k} \binom{n}{k} k^n \phi'(v)=\phi'(v)$ (see Show this equality (The factorial as an alternate sum with binomial coefficients).). It is clear that $\Phi''$ is symmetric, but I don't know if $\Phi''$ is multilinear.

Formula for $n=2$: $$\Phi[v_1,v_2]=\frac12 [\phi(v_1+v_2)-\phi(v_1)-\phi(v_2)].$$

Formula for $n=3$: $$\Phi[v_1,v_2,v_3]=\frac16 [\phi(v_1+v_2+v_3)-\phi(v_1+v_2)-\phi(v_1+v_3)-\phi(v_2+v_3)+\phi(v_1)+\phi(v_2)+\phi(v_3)].$$

(This is just the summary of the answers by Ewan and Anthony, but a lot simpler.)

Let $$S_n$$ denote the symmetric group. Also, let us write $$X=\{1,\dots,n\}$$. We compute $$\begin{eqnarray}\sum_{k=1}^{n}\sum_{1\leq j_{1}<\cdots where the fourth equality follows from the binomial formula.

This is true, here's a proof.

I'm going to use the polynomial notation $\Phi\left(v_{1},\ldots,v_{n}\right)=v_{1}\cdots v_{n}$ - note that the multilinearity and symmetry of $\Phi$ means that manipulating these like polynomials (i.e. commuting elements, distributing multiplication'') is completely legitimate. Let the RHS of your proposed equation be $\frac{1}{n!}F\left(n\right)$.

Using the multinomial expansion, we have $$F\left(n\right)=\sum_{k=1}^{n}\left(-1\right)^{n-k}f\left(n,k\right)$$ where $$f\left(n,k\right)=\sum_{1\le j_{1}<\cdots<j_{k}\le n}\ \sum_{l_{1}+\cdots+l_{k}=n}{n \choose l_{1},\ldots,l_{k}}v_{j_{1}}^{l_{1}}\cdots v_{j_{k}}^{l_{k}}.$$ Let's try to compute the coefficient of $v_{j_{1}}^{l_{1}}\cdots v_{j_{k}}^{l_{k}}$ in $F\left(n\right)$. The most obvious contribution is from $f\left(n,k\right)$, which gives $\left(-1\right)^{n-k}{n \choose l_{1},\ldots,l_{k}}.$ But there are more contributions: for every $K>k$ we have terms where $K-k$ of the $l$s are zero. The contribution from $f\left(n,K\right)$ is $$\left(-1\right)^{n-K}\sum\left\{ {n \choose l_{1},\ldots,l_{k},0,0,\ldots}:j_{k+1},\ldots,j_{K}\textrm{ distinct from }j_{1},\ldots,j_{k}\right\} .$$ All we need to do to compute this is count the number of choices of $K-k$ of the $n-k$ remaining indices, so we get $$\left(-1\right)^{n-K}{n \choose l_{1},\ldots,l_{k}}{n-k \choose K-k}.$$ The coefficient of $v_{j_{1}}^{l_{1}}\cdots v_{j_{k}}^{l_{k}}$ in $F\left(n\right)$ is thus $$\sum_{K=k}^{n}\left(-1\right)^{n-K}{n \choose l_{1},\ldots,l_{k}}{n-k \choose K-k}=\sum_{K=k}^{n}\left(-1\right)^{n-K}\frac{n!}{l_{1}!\cdots l_{k}!}{n-k \choose K-k}.$$ We want to show that this is $n!$ when $k=n,l_{j}=1$ and zero otherwise. The first case is easy - there is only a single term in the sum and all of $n,k,K$ are just $n$, so it falls out immediately. Let's try the zero case. Factoring out the $K$-independent terms gives $$\left(-1\right)^{n}\frac{n!}{l_{1}!\cdots l_{k}!}\sum_{K=k}^{n}\left(-1\right)^{K}{n-k \choose K-k}.$$ Making a change of variables $j=K-k$ turns the sum to $$\left(-1\right)^{k}\sum_{j=0}^{n-k}\left(-1\right)^{j}{n-k \choose j}.$$ This is the alternating sum of the binomial coefficients, which vanishes as required.

• Our two proofs are basically the same (and were posted at about the same time). Your proof is less formal and easier to read ; on the other hand I find my sketch useful. – Ewan Delanoy Sep 3 '13 at 14:10
• @EwanDelanoy: Yeah, I laughed when you submitted so soon after me. The proofs are indeed pretty much identical once you translate the notation. – Anthony Carapetis Sep 3 '13 at 14:20
• Your proof and the one of @EwanDelanoy are both really nice. Thanks! It gonna be hard to attribute the bounty to one of you more then the other. I believe that I cannot share it between both of you. – Gilles Bonnet Sep 3 '13 at 15:26

This in not an answer, but an incomplete attempt of induction proof.

First, we will consider the following notation: $$\Phi_v[v_1,\ldots,v_{n-1}]=\Phi[v_1,\ldots,v_{n-1},v],$$ so $\Phi_v:V^{n-1}\to\mathbb{R}$ is the multinear symmetric operator we obtain when we fix a variable in $\Phi$. We then of course note $\phi_w(v)=\Phi_w[v,\ldots,v]=\Phi[v,\ldots,v,w]$.

In this 'answer', I show that the formula is proved if $$\phi(v_1+\cdots+v_n) =\sum_{k=1}^{n-1} \sum_{1\leq j_1<\cdots<j_k\leq n} (-1)^{n-1-k}\phi_{v_1+\cdots+v_n}(v_{j_1}+\cdots+v_{j_k}),$$ which is probably not more easy then the polarization formula itself, but that where lead me my attempt of induction.

We also write $$\Phi_v[v_1,\ldots,\hat{v_i},\ldots,v_n]=\Phi_v[v_1,\ldots,v_{i-1},v_{i+1},\ldots,v_n].$$

Let assume the formula is true for multilinear symmetric operator $V^{n-1}\to\mathbb{R}$. Since $\Phi[v_1,\ldots,v_n]=\Phi_{v_i}[v_1,\ldots,\hat{v_i},\ldots,v_n]$ by symmetry, we have: $$\Phi[v_1,\ldots,v_n]=\frac1n \sum_{i=1}^n \Phi_{v_i}[v_1,\ldots,\hat{v_i},\ldots,v_n].$$ By the induction we have $$\Phi_{v_i}[v_1,\ldots,\hat{v_i},\ldots,v_n] =\frac{1}{(n-1)!} \sum_{k=1}^{n-1} \sum_{1\leq j_1<\cdots<j_k\leq n\ ;\ j_l\neq i} (-1)^{n-1-k}\phi_{v_i} (v_{j_1}+\cdots+v_{j_k}).$$ So $$\Phi[v_1,\ldots,v_n] =\frac1{n!}\sum_{k=1}^{n-1} \sum_{1\leq j_1<\cdots<j_k\leq n} (-1)^{n-1-k} \sum_{\{i\mid i\neq j_l \forall l\leq k\}}\phi_{v_i} (v_{j_1}+\cdots+v_{j_k}).$$ But \begin{align} \sum_{\{i\mid i\neq j_l \forall l\leq k\}}\phi_{v_i} (v_{j_1}+\cdots+v_{j_k}) &={\phi_{v_1+\cdots+v_n}(v_{j_1}+\cdots+v_{j_k})-\phi_{v_{j_1}+\cdots+v_{j_k}}(v_{j_1}+\cdots+v_{j_k})}\\ &={\phi_{v_1+\cdots+v_n}(v_{j_1}+\cdots+v_{j_k})-\phi(v_{j_1}+\cdots+v_{j_k})}. \end{align} So \begin{align} &\Phi[v_1,\ldots,v_n]\\ &=\frac1{n!}\sum_{k=1}^{n-1} \sum_{1\leq j_1<\cdots<j_k\leq n} (-1)^{n-1-k} (\phi_{v_1+\cdots+v_n}(v_{j_1}+\cdots+v_{j_k})-\phi(v_{j_1}+\cdots+v_{j_k}))\\ &=\frac1{n!}\sum_{k=1}^{n-1} \sum_{1\leq j_1<\cdots<j_k\leq n} (-1)^{n-k} \phi(v_{j_1}+\cdots+v_{j_k})\\ &\qquad +\frac1{n!}\sum_{k=1}^{n-1} \sum_{1\leq j_1<\cdots<j_k\leq n} (-1)^{n-1-k}\phi_{v_1+\cdots+v_n}(v_{j_1}+\cdots+v_{j_k}).\\ \end{align} In this last expression the first part is almost the R.H.S. of the polarisation formula ; the sum goes until $n-1$ instead of $n$. But when $k=n$, $\sum_{1\leq j_1<\cdots<j_k\leq n} (-1)^{n-k} \phi(v_{j_1}+\cdots+v_{j_k}) =\phi(v_1+\cdots+v_n)$. Hence we will have prove the polarization formula if $$\phi(v_1+\cdots+v_n) =\sum_{k=1}^{n-1} \sum_{1\leq j_1<\cdots<j_k\leq n} (-1)^{n-1-k}\phi_{v_1+\cdots+v_n}(v_{j_1}+\cdots+v_{j_k}).$$

Unfortunately I don't see how to show that, it is maybe as difficult as the polarization formula.

SKETCH OF THE PROOF : Your big sums are always sums of (sums of sums of) terms of the form $\Phi(v_{k_1},v_{k_2},\ldots ,v_{k_n})$ for some uples of indices $(k_1,k_2, \ldots ,k_n)$. Thanks to the symmetry of $\Phi$, we can always rearrange and put the uple in increasing order. You are then left with a simpler sum with less terms, where exactly one term is multilinear (the term $\Phi(v_1,v_2, \ldots ,v_n)$) and all the others are not. So this is a Rambo-like situation of one against a hundred. But fortunately for us, the combinatorial property (let us call it $P$) that for any finite set $X$, the sum $\sum_{B \subseteq X}(-1)^{|B|}$ is zero except when $X$ is empty, allows us to show that all the non-multilinear terms have zero coefficient in the sum.

THE DETAILS : Given a uple $(k_1,\ldots ,k_n)$, denote by $\rho(k_1,k_2,\ldots,k_n)$ the rearranged uple according to increasing order. (Thus, $\rho(1,3,2)=(1,2,3)$).

It is more convenient here to view uples as functions, so we shall speak of $u$ and $\rho u$ where $u$ and $\rho u$ are maps $\lbrace 1,2, \ldots, n\rbrace \to \lbrace 1,2, \ldots, n\rbrace$ and $\rho u$ is increasing. Also, we put $\psi(f)=\Phi(v_{f(1)},\ldots,v_{f(n)})$.

For an arbitrary increasing uple $i$, denote by $w(i)$ the number of uples $j$ satisfying $\rho(j)=i$. For any $A \subseteq \lbrace 1,2, \ldots ,n \rbrace$, denote by $I(A)$ the set of all increasing maps $\lbrace 1,2, \ldots ,n \rbrace \to A$. Also, let $I=I(\lbrace 1,2, \ldots, n \rbrace)$ and $V(f)=\lbrace A \subseteq \lbrace 1,2, \ldots ,n \rbrace | f\in I(A) \rbrace$ . Note that if $K(f)=\lbrace 1,2, \ldots ,n \rbrace \setminus Im(f)$, then there is a natural bijection between ${\cal P}(K(f))$ and $V(f)$, given by $B \mapsto Im(f) \cup B$.

Let $$\lambda (A)=\phi\bigg(\sum_{a\in A}v_a\bigg) \tag{2}$$

Then, expanding $\lambda(A)$ completely shows that

$$\lambda (A)=\sum_{f\in I(A)} w(f) \psi(f) \tag{3}$$

Then, the RHS (call it $\Phi''$) of the desired equality can be rewritten as

$$\begin{eqnarray} \Phi'' &=& \sum_{A\subseteq \lbrace 1,2, \ldots ,n \rbrace}(-1)^{n-|A|}\lambda(A)\\ &=& \sum_{A\subseteq \lbrace 1,2, \ldots ,n \rbrace}(-1)^{n-|A|}\sum_{f\in I(A)} w(f) \psi(f) \\ &=& \sum_{f\in I}w(f)\psi(f)\sum_{A\in V(f)}(-1)^{n-|A|} \\ &=& \sum_{f\in I}w(f)\psi(f)\sum_{B\subseteq K(f)}(-1)^{n-|Im(f)|+|B|} \\ &=& w({\mathsf{id}})\psi(\mathsf{id}) \ \text{by property } P. \\ &=& n! \Phi(v_1,v_2, \ldots ,v_n) \end{eqnarray}$$

which concludes the proof.

• I think you mean $\psi(f)=\Phi(v_{f(1)},\ldots,v_{f(n)})$, and not $\psi(f)=\phi(v_{f(1)},\ldots,v_{f(n)})$. – Gilles Bonnet Sep 3 '13 at 14:52
• @GillesBonnet Corrected, thanks. – Ewan Delanoy Sep 3 '13 at 14:55
• Do you have a reference for the combinatorial property P? – Gilles Bonnet Sep 4 '13 at 11:12
• @GillesBonnet This property $P$ is called “alternating sum of binomial coefficients” in Anthony Carapetis' answer. In other words, it is the binomial Newton expansion of $(1-1)^n$. – Ewan Delanoy Sep 4 '13 at 11:44