Question 1:
There are two list \((a_1, a_2, a_3,…a_n)\) and \((b_1,b_2,b_3,…,b_n)\)
how can we prove they contain the same element? (now we only consider to have the same elements, permutation comes in next question) This question would help you to understand why the permutation construction in Plonk is constructed in that way.
we can check the following equation holds or not
$$\frac{\prod\limits_{i\in[1,n]}a_i+\beta}{\prod\limits_{i\in[1,n]}b_i+\beta}=1$$
we can expand the equation in another format
$$\frac{\beta^n+n\beta^{n-1}(\sum\limits_{i\in[1,n]}a_i)+C_n^2\beta(\sum\limits_{i,j\in[1,n], i\neq j}a_ia_j)+C_n^3\beta^{n-2}(\sum\limits_{i,j,k\in [n],i\neq k \neq j}a_ia_ja_k)+…}{\beta^n+n\beta^{n-1}(\sum\limits_{i\in[1,n]}b_i)+C_n^2\beta(\sum\limits_{i,j\in[1,n], i\neq j}b_ib_j)+C_n^3\beta^{n-2}(\sum\limits_{i,j,k\in [n],i\neq k \neq j}b_ib_jb_k)+…}$$
where \(C_n^k=\frac{n(n-1)(n-k+1)}{(k)!}\)
if the quotient is 1, which mean the numerator and denominator are the same. Since \(\beta\) is consider as random, by Schwartz–Zippel lemma, the polynomials of numerator and denominator are the same
The the question reduced to prove
if we have
$$\sum\limits_{i\in[1,n]}a_i=\sum\limits_{i\in [1,n]}b_i$$
$$\sum\limits_{i,j\in[1,n], i\neq j}a_ia_j=\sum\limits_{i,j\in[1,n], i\neq j}b_ib_j$$
$$\sum\limits_{i,j,k\in [n],i\neq k \neq j}a_ia_ja_k=\sum\limits_{i,j,k\in [n],i\neq k \neq j}b_ib_jb_k$$
$$…$$ (the sum of the product of different numbers of elements )
$$a_1a_2\cdot … a_n=b_1b_2\cdot … b_n$$
then the two list \(a_1, a_2, a_3,…a_n\) and \(b_1,b_2,b_3,…,b_n\) should contains the same elements, I didn’t find the exact theorem to prove this claim is true, but only prove when the list has 2 or 3 elements, it is obvious.
Question 2
In question 1 we explain the example with two list that contain simple elements, now let’s move to the case that is actually used in Plonk, which is to compare two list that contain tuples, each tuple has two element, an index, and a variable that represent the wire value, i.e., the lists are \([(1,a_1),(2,a_2),…,(SID_a,a_{sid}),…,(n,a_n)]\) and \([(1,b_1),(2,b_2),…,(SID_b,b_{sid}),…,(n,b_n)]\)
Now we need to add one more randomness to the quotient:
$$\frac{\prod\limits_{i\in[1,n]}a_i+\beta SID_{a_i} +\gamma}{\prod\limits_{i\in[1,n]}b_i+\beta SID_{b_i} +\gamma}=1$$
If \(a_1,…,a_n\) are all unique values, then not only \(b_1,…,b_n\) need to have the same values with \(a_1,…,a_n\) , but also the same value has the same index, then the quotient can be \(1\). But as in these two list, there are sets of values that equal to each other, then the index of these values can swap. Therefore, the \(S_{ID}\) can swap with \(S_{\sigma(i)}\) in Plonk paper.
Grand product in plonk
There are two list \((a_1, a_2, a_3,…a_n)\) and \((b_1,b_2,b_3,…,b_n)\)
Suppose \(f(g^i)=a_i\) and \(g(i)=b_i\)
let \(f’ = f +\beta S_{ID} + \gamma\)
\(g’=g+\beta \cdot S+{\sigma} + \gamma\)
Define \(Z(g^i)=\prod\limits_{i\leq j < i} \frac{f”(g^j)}{g'(g^j)}\)
the verification reduced to check the polynomials satisfy the following restrictions:
for all \(a\) in the evaluation domain \(H\)
$$L_1(a)(Z(a)-1)=0$$
$$Z(a)f'(a)=g'(a)Z(a\cdot g$$