---
# System prepended metadata

title: Permutation argument lemma proof

---

# 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.
