Because of the "randomized differences" check in plookup, we (allegedly) have to sort the sequence of values (ℓi)i∈[n] to the sequence (fi)i∈[n] where the fi's appear in the same order that they do in the lookup table. A simple product argument to do this produces an accumulator Zρ such that
Zρ(g0) = 1
Zρ(gk) = Zρ(gk-1) (γ + ℓi) / (γ + fi)
Zρ(gn) = 1
Checking that Zρ has these properties will show that some permutation holds because Zρ(gn) = Πi(γ + ℓi) / Πi(γ + fi) which is one only if the numerator and denominator are the same. Treating γ as a variable/indeterminate, these polynomials have roots -ℓi (for all 1≤i≤n) and -fi (for all 1≤i≤n), respectively and so the polynomials are equal only if (ℓi)i∈[n] and (fi)i∈[n] are related by a permutation.
Plookup's accumulator is of the form
Zplookup(gk) = Zplookup(gk-1) • (1 + β) (γ + fi) Ti(β,γ) / Hi(β,γ)
Each condition to check is multiplicative in nature. If we instead create a combined accumulator that agrees with Zρ • Zplookup on the relevant domain, then the (γ + fi) terms cancel right?
Then the combined accumulator has numerator terms (1+β)(γ + ℓi) Ti(β,γ) and we could drop the whole business of making sure that (ℓi)i∈[n] is sorted into (fi)i∈[n]. This seems to make implementation much easier, and all the pieces were there so I'm not sure why this wasn't mentioned in the paper. I'll try to write up a proof of correctness but it'd be helpful to have more eyes on it.
Because of the "randomized differences" check in plookup, we (allegedly) have to sort the sequence of values (ℓi)i∈[n] to the sequence (fi)i∈[n] where the fi's appear in the same order that they do in the lookup table. A simple product argument to do this produces an accumulator Zρ such that
Zρ(g0) = 1
Zρ(gk) = Zρ(gk-1) (γ + ℓi) / (γ + fi)
Zρ(gn) = 1
Checking that Zρ has these properties will show that some permutation holds because Zρ(gn) = Πi(γ + ℓi) / Πi(γ + fi) which is one only if the numerator and denominator are the same. Treating γ as a variable/indeterminate, these polynomials have roots -ℓi (for all 1≤i≤n) and -fi (for all 1≤i≤n), respectively and so the polynomials are equal only if (ℓi)i∈[n] and (fi)i∈[n] are related by a permutation.
Plookup's accumulator is of the form
Zplookup(gk) = Zplookup(gk-1) • (1 + β) (γ + fi) Ti(β,γ) / Hi(β,γ)
Each condition to check is multiplicative in nature. If we instead create a combined accumulator that agrees with Zρ • Zplookup on the relevant domain, then the (γ + fi) terms cancel right?
Then the combined accumulator has numerator terms (1+β)(γ + ℓi) Ti(β,γ) and we could drop the whole business of making sure that (ℓi)i∈[n] is sorted into (fi)i∈[n]. This seems to make implementation much easier, and all the pieces were there so I'm not sure why this wasn't mentioned in the paper. I'll try to write up a proof of correctness but it'd be helpful to have more eyes on it.