Key idea

<aside> 💡 Encode a multiset as a sum of simple poles instead of a product of linear factors ... and moreover encode multiplicities as scalar multiples of the poles (instead of powers of the linear factors).

</aside>

Summary

• LogUp (="logarithmic derivatives" + lookups) provides lookup functionality for multivariate proof systems (like Remainder!). It is appropriate for smallish tables (2^20 — 2^25 rows) in the batch-witness setting.
• LogUp re-casts the usual multiplicative identity for lookups as an additive identity. Most importantly, the multiplicities no longer need to be provided as binary decompositions, but can instead be provided as field elements!
• There are two versions of logUp. The latest and greatest is the 2023 paper of Papini & Haböck, Improving logarithmic derivative lookups using GKR, which is also covered in a video of Ulrich Haböck talking about it at PSE. The previous (2022) version (paper and video) is no longer directly relevant.

Walkthrough

logUp-video-2023-12-21.mp4

Supplements

The induction proof we skipped:

Alright, what’s the “field of fractions”?

The “fractional identity” (i.e. equation “*” from the talk) is an equation in the field of fractions of the univariate polynomial ring. It consists of formal ratios of polynomials, where the denominator is non-zero, and where arithmetic works in the way that the fraction notation suggests.

Why does this work?

i.e. how does the “fractional identity” of logUp prove a subset argument? And how is it that the multiplicities are field elements (instead of non-negative integers in the familiar lookup case)?

This is answered by Lemma 5 (which relies on Lemma 4) from of the 2022 logUp paper (see reference above), reproduced here: