✳flâneur — a map of the web's best reading

Permutation Check via Product Check

georgwiese.github.io · 206 words · saved by 1 readers

These are equal if and only if a and b are permutations of each other. Equality of polynomials can be checked at a random point β due to the Schwartz-Zippel Lemma. The naive way to compute this would be to have two extra witness columns that compute the accumulated product. However, we can do this with only one extra column, constrained to be equal to: Also, multiple permutation arguments can share the same accumulator (with independent challenges), at the cost of increasing the degree of the constraint. Created with Quartz v4.2.3 © 2024

Or equivalently: Prove equality of two multi-sets Given two length- m lists A = ( a 1 ​ , ... , a n ​ ) and B = ( b 1 ​ , ... , b n ​ ) , we define: p A ​ ( X ) := i = 1 ∏ n ​ ( a i ​ − X ) and p B ​ ( X ) := i = 1 ∏ n ​ ( b i ​ − X ) These are equal if and only if a and b are permutations of each other. Equality of polynomials can be checked at a random point β due to the Schwartz-Zippel Lemma . The naive way to compute this would be to have two extra witness columns that compute the accumulated product. However, we can do this with only one extra column, constrained to be equal to: Z 2 k ​ =

Explore this link on the map →

related reading