# Proof of Minsky Papert Symmetrization technique

I frequently hear about the Minsky-Papert Symmetrization technique in many papers with a reference to the book of Minsky. I could not locate the book online. Could someone supply me a proof of the symmetrization technique?

For instance, it is used in Lemma $5$ in this paper http://www.csee.usf.edu/~tripathi/Publication/polynomial-degree-conference.pdf

Over $0/1$ inputs we have \begin{align*} (y_1+\cdots+y_N)^0 &= 1 \\ (y_1+\cdots+y_N)^1 &= \sum_i y_i \\ (y_1+\cdots+y_N)^2 &= \sum_i y_i+2\sum_{i<j} y_iy_j \\ (y_1+\cdots+y_N)^3 &= \sum_i y_i+6\sum_{i<j} y_iy_j + 6\sum_{i<j<k} y_iy_jy_k \end{align*} And so on. It follows that for $0/1$ inputs, $p_{sym}$ can be written as a linear combination of $(y_1+\cdots+y_n)^0,\ldots,(y_1+\cdots+y_n)^d$, where $d$ is its degree. This linear combination can also be viewed as a polynomial $\tilde{p}$ in $y_1+\cdots+y_n$, which is equal to $p_{sym}$ for $0/1$ inputs.
• If you look at invariant theory, perhaps what I am asking cannot be done since $S_n$ and the cyclic groups $C_2$ are special (Chevalley theorem). – 1.. Dec 1 '14 at 1:37