# Permutation argument lemma proof

Proof of the non-trivial direction of the permutation argument lemma, based on the proof of claim A.1 on the last page of the PLONK paper.

Suppose that

$\prod_{x \in H}\frac{P(x) + Y\cdot W(x) + Z}{P(x) + Y\cdot x + Z} \equiv 1$

Pass the denominator to the right:

$\prod_{x \in H}(P(x) + Y\cdot W(x) + Z) \equiv \prod_{x \in H} (P(x) + Y\cdot x + Z)$

Substitute $x = W(x')$ on the right-hand side. This is allowed since W is a permutation (meaning it's bijective).

$\prod_{x \in H}(P(x) + Y\cdot W(x) + Z) \equiv \prod_{x' \in H} (P(W(x')) + Y\cdot W(x') + Z)$

Now rename the variable back to x

$\prod_{x \in H}(P(x) + Y\cdot W(x) + Z) \equiv \prod_{x \in H} (P(W(x)) + Y\cdot W(x) + Z)$

Consider each side as a polynomial in Y,Z. In fact, because they're identical, it's the same polynomial expressed in two ways. Because polynomials in Y,Z are a unique factorization domain, this polynomial has a unique factorization into irreducible terms. Each term in each of the products here is linear (there are no $Y^2$, $Y\cdot Z$, etc. terms) and so each of the products here is in fact such a factorization. This means that each term on the left is identical, up to a constant factor, to a term on the right. But because $Z$ has coefficient 1 in each factor on each side, they're just plain identical (the constant factor is always 1).

Now, pick an arbitrary $a \in H$. We want to show that $P(W(a)) = P(a)$. Because $W$ is a permutation, there will be exactly one factor on each side having $W(a)$ as the coefficient of $Y$, and so these two factors must be identical (since there are no other factors for either of them to be identical to). These factors are $P(a) + Y\cdot W(a) + Z$ on the left and $P(W(a)) + Y \cdot W(a) + Z$ on the right. Since they're identical, their coefficients are equal, and so, in particular, we have $P(a) = P(W(a))$, which is what we wanted to show.