Proof of Minsky Papert Symmetrization technique
Over $0/1$ inputs we have
$$
\begin{align*}
(y_1+\cdots+y_N)^0 &amp;= 1 \\
(y_1+\cdots+y_N)^1 &amp;= \sum_i y_i \\
(y_1+\cdots+y_N)^2 &amp;= \sum_i y_i+2\sum_{i&lt;j} y_iy_j \\
(y_1+\cdots+y_N)^3 &amp;= \sum_i y_i+6\sum_{i&lt;j} y_iy_j + 6\sum_{i&lt;j&lt;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.