Back to Arithmetic Circuits
Back to notes

# Useful tricks

20%

## Identities

### Newton identity

Newton identity provides a bridge between $\Sym_k$ and $\Pow_k$. For our interest in arithmetic circuits, Newton identity tells us that $\Sym_d$ has a $\Sigma\Pi\Sigma\Lambda$ circuit of size $2^{O(\sqrt{d})}\cdot\poly(n)$. Note that the resulting circuit is homogeneous. Recall that there is $n^{\Omega(d)}$ lower bound for $\Sigma\Lambda\Sigma$ circuits computing $\Sym_d$.

For any $k\in[n]$, we have \begin{eqnarray*} \Sym_k &=\frac{1}{k!} \begin{vmatrix} \Pow_1 & 1 & 0 & \cdots & 0 \\ \Pow_2 & \Pow_1 & 2 & \cdots & 0 \\ \vdots & \vdots & \ddots & \cdots & 0 \\ \Pow_{k-1} & \Pow_{k-2} & \cdots & \Pow_1 & k-1 \\ \Pow_k & \Pow_{k-1} & \cdots & \Pow_2 & \Pow_1 \end{vmatrix}. \end{eqnarray*} Specifically, one can write $x_1x_2\cdots x_k=\sum_{\mathbf{a}:\ \sum_iia_i=k}\alpha_{\mathbf{a}}(\Pow_1)^{a_1}(\Pow_2)^{a_2}\cdots(\Pow_k)^{a_k}$.

Applications:

• Any non-homogeneous $\Sigma\Pi\Sigma$ circuit can be converted to homogeneous $\Sigma\Pi\Sigma\Lambda\Sigma$ circuit with $2^{O(\sqrt{d})}\cdot\poly(n)$ blow-up.

### Ryser-Fischer identity

Ryser-Fischer identity expresses multilinear monomial into sums of the power of sum. To our interest in arithmetic circuits, it implies that one can replace monomial $x_1x_2\cdots c_d$ with a size $2^d$ $\Sigma\Lambda\Sigma$ circuit. Note that the circuit is homogeneous.

For any $d\in\N$, we have $$x_1x_2\cdots x_d = \sum_{S\subseteq[d]}(-1)^{d-\card{S}}(\sum_{i\in S}x_i)^d.$$

The proof is based on simple inclusion-exclusion principle so here we omit the details.

### Duality trick

The duality trick converts $\Lambda\Sigma\Lambda$ circuit to $\Sigma\Pi\Sigma$ circuit.