# Lookup Argument

The Lookup Argument establishes that all elements of list also occur in list . In this context, contains the values that are being looked up, while is the lookup table.1 Both lists and may contain duplicates. However, it is inefficient if does, and is therefor assumed not to.

The example at the end of this section summarizes the necessary computations for the Lookup Argument. The rest of the section derives those computations. The first step is to interpret both lists' elements as the roots of polynomials and , respectively:

By counting the number of occurrences of unique elements and eliminating duplicates, can equivalently be expressed as:

The next step uses

• the formal derivative of , and
• the multiplicity-weighted formal derivative of .

The former is the familiar formal derivative:

The multiplicity-weighted formal derivative uses the lookup-multiplicities as additional factors:

Let the greatest common divisor of and . The polynomial has the same roots as , but all roots have multiplicity 1. This polynomial is identical to if and only if all elements in list also occur in list .

A similar property holds for the formal derivatives: The polynomial is identical to if and only if all elements in list also occur in list . By solving for and equating, the following holds:

## Optimization through Logarithmic Derivatives

The logarithmic derivative of is defined as . Furthermore, the equality of monic polynomials and is equivalent to the equality of their logarithmic derivatives.2 This allows rewriting above equation as:

Using logarithmic derivatives for the equality check decreases the computational effort for both prover and verifier. Concretely, instead of four running products – one each for , , , and – only two logarithmic derivatives are needed. Namely, considering once again list containing duplicates, above equation can be written as:

To compute the sums, the lists and are base columns in the two respective tables. Additionally, the lookup multiplicity is recorded explicitly in a base column of the lookup table.

## Example

In Table A:

base column Aextension column A: logarithmic derivative
0
2
2
1
2

And in Table B:

base column Bmultiplicityextension column B: logarithmic derivative
01
11
23

It is possible to establish a subset relation by skipping over certain elements when computing the logarithmic derivative. The logarithmic derivative must incorporate the same elements with the same multiplicity in both tables. Otherwise, the Lookup Argument will fail.

An example for a Lookup Argument can be found between the Program Table and the Processor Table.

1

The lookup table may represent a mapping from one or more “input” elements to one or more “output” elements – see “Compressing Multiple Elements.”

2

See Lemma 3 in this paper for a proof.