# \[Future Project\] Replace permutation+plookup with log-derivative technique

**URL:** <https://forum.aztec.network/t/future-project-replace-permutation-plookup-with-log-derivative-technique/709>\
**Category:** Honk!\
**Created:** [August 2, 2023, 9:21am UTC](https://forum.aztec.network/t/future-project-replace-permutation-plookup-with-log-derivative-technique/709 "2023-08-02T09:21:08Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![zac-williamson](https://dub1.discourse-cdn.com/flex013/user_avatar/forum.aztec.network/zac-williamson/32/8_2.png) [@zac-williamson](https://forum.aztec.network/u/zac-williamson)\
**Post date:** [August 2, 2023, 9:21am UTC](https://forum.aztec.network/t/future-project-replace-permutation-plookup-with-log-derivative-technique/709/1 "2023-08-02T09:21:08Z")

</div>

Overview of this topic:

1. log-derivative lookups have better properties than plookup
2. 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](https://hackmd.io/jnlD8RjKRaOuZoi4QOvNMA?view) for details on how to do **lookups** via log-derivatives

See [this HackMD](https://hackmd.io/@aztec-network/B1HHr26Pn?type=view) 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 [Using log-derivatives to check copy constraints - HackMD](https://hackmd.io/@aztec-network/B1HHr26Pn?type=view) for details)

---

<div class="post-metadata">

**Author:** ![jat9292](https://dub1.discourse-cdn.com/flex013/user_avatar/forum.aztec.network/jat9292/32/756_2.png) [@jat9292](https://forum.aztec.network/u/jat9292)\
**Post date:** [September 30, 2023, 12:06am UTC](https://forum.aztec.network/t/future-project-replace-permutation-plookup-with-log-derivative-technique/709/2 "2023-09-30T00:06:02Z")

</div>

Hello sir. All the HackMD links are access-restricted, unfortunately I do not have permission to read them.