Overview of this topic:

- log-derivative lookups have better properties than plookup
- if we make both permutation + lookup relations use log derivatives, we can replace our 2 “grand product” polynomials with a single inverse polynomial

# Log Derivatives

See this HackMD for details on how to do **lookups** via log-derivatives

See this HackMD for details on how to do **permutations** via log-derivatives

An overview of the vectors/polynomials required for lookups

vector | size | comments |
---|---|---|

grand product vector | num_reads + table_size | - |

sorted list vector | num_reads + table_size | - |

An overview of the vectors/polynomials required for log derivatives

vector | size | comments |
---|---|---|

inverse vector | max(num_reads, table size) | - |

counts vector | table size | entries describe # of times a given table entry is read from. values are small |

The log-derivative vectors are smaller `max(num_reads, table_size)`

vs `(num_reads + table_size)`

, which practically enables larger tables.

The log-derivative vectors are faster to commit to due to the “counts” vector element values being small.

# Combining inverse polynomials

The log-derivative relation contains fractional terms (e.g. (`1 / a_i`

)). To convert into polynomial algebra the Prover must commit to these inverses.

To reduce the number of inverse commitments, the Prover can commit to the product of all inverses required for a given row.

This increases the degree of the resulting permutation/lookup relation, but is likely an acceptable trade-off vs having multiple inverse commitments.

We can reduce the degree of the combined permutation/lookup relation by modifying the permutation relation to use more precomputed polynomials (see https://hackmd.io/@aztec-network/B1HHr26Pn?type=view for details)