Eliminating the need to sort lookup values

[ndbunner]

Because of the "randomized differences" check in plookup, we (allegedly) have to sort the sequence of values (ℓ_i)_i∈[n] to the sequence (f_i)_i∈[n] where the f_i'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_ρ(g⁰) = 1

Z_ρ(g^k) = Z_ρ(g^k-1) (γ + ℓ_i) / (γ + f_i)

Z_ρ(gⁿ) = 1

Checking that Z_ρ has these properties will show that some permutation holds because Z_ρ(gⁿ) = Π_i(γ + ℓ_i) / Π_i(γ + f_i) 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 -f_i (for all 1≤i≤n), respectively and so the polynomials are equal only if (ℓ_i)_i∈[n] and (f_i)_i∈[n] are related by a permutation.

Plookup's accumulator is of the form

Z_plookup(g^k) = Z_plookup(g^k-1) • (1 + β) (γ + f_i) T_i(β,γ) / H_i(β,γ)

Each condition to check is multiplicative in nature. If we instead create a combined accumulator that agrees with Z_ρ • Z_plookup on the relevant domain, then the (γ + f_i) terms cancel right?

Then the combined accumulator has numerator terms (1+β)(γ + ℓ_i) T_i(β,γ) and we could drop the whole business of making sure that (ℓ_i)_i∈[n] is sorted into (f_i)_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.

[cwgoes]

Let's explain the soundness bit (what the chance that Z_ρ(gⁿ) = 1/x and Z_plookup(gⁿ) = x for some x using this trick).