> ## Documentation Index
> Fetch the complete documentation index at: https://mintlify.com/a16z/jolt/llms.txt
> Use this file to discover all available pages before exploring further.

# Multilinear Extensions

> Understanding multilinear polynomial extensions and their role in Jolt

Multilinear extensions (MLEs) are the central data structure in sumcheck-based proof systems like Jolt. They provide a way to represent discrete functions over the boolean hypercube as smooth polynomials over a field.

## Definition

A function $f \colon \{0,1\}^v \to \mathbb{F}$ defined on the $v$-dimensional boolean hypercube has a unique **multilinear extension** (MLE) $\tilde{f} \colon \mathbb{F}^v \to \mathbb{F}$: the unique polynomial of degree at most 1 in each variable that agrees with $f$ on all $2^v$ boolean inputs.

Concretely, the MLE is defined as:

$$
\tilde{f}(x_1, \dots, x_v) = \sum_{b \in \{0,1\}^v} f(b) \cdot \prod_{i=1}^{v} \bigl(b_i \cdot x_i + (1 - b_i)(1 - x_i)\bigr)
$$

The product term $\prod_{i=1}^{v} \bigl(b_i \cdot x_i + (1 - b_i)(1 - x_i)\bigr)$ is the **equality polynomial** $\widetilde{\textsf{eq}}(x, b)$, which equals 1 when $x = b$ on the boolean hypercube and interpolates smoothly elsewhere.

## Role in Jolt

MLEs are used throughout Jolt's proving system:

* The [sumcheck protocol](/architecture/theory/sumcheck) operates over multilinear polynomials
* Essentially all witness data in Jolt is represented as MLEs
* Committed polynomials in the execution trace are MLEs

## Representation

An MLE over $v$ variables is stored as a vector of $n = 2^v$ **evaluations** over the boolean hypercube $\{0,1\}^v$. The $i$-th entry of this vector stores $f(b)$ where $b$ is the binary representation of $i$.

**Indexing convention:** Jolt uses big-endian indexing, where the most significant bit of $i$ corresponds to $x_1$.

## Variable Binding

Given $\tilde{f}(x_1, \dots, x_v)$ represented by $n = 2^v$ evaluations, **binding** the most significant variable to a challenge $r \in \mathbb{F}$ produces a new MLE $\tilde{f}'(x_2, \dots, x_v) = \tilde{f}(r, x_2, \dots, x_v)$ represented by $n/2$ evaluations.

For each index $i \in \{0, \dots, n/2 - 1\}$:

$$
E'[i] = E[i] + r \cdot (E[i + n/2] - E[i])
$$

where $E[i] = \tilde{f}(0, b)$ and $E[i + n/2] = \tilde{f}(1, b)$ for the same suffix $b$.

This operation takes a single $O(n)$ pass through the evaluation vector.

### Binding Order

Which variable gets bound in each round is determined by the `BindingOrder`:

* **HighToLow**: Most significant variable first (pairs left/right halves)
* **LowToHigh**: Least significant variable first (pairs even/odd entries)

For `LowToHigh` binding, the formula becomes:

$$
E'[i] = E[2i] + r \cdot (E[2i+1] - E[2i])
$$

## Implementation in Jolt

The MLE implementations live in `jolt-core/src/poly/`. All are unified under the `MultilinearPolynomial<F>` enum, which dispatches binding and evaluation to the appropriate concrete type.

### DensePolynomial

`DensePolynomial<F>` is the straightforward representation: a `Vec<F>` of $2^v$ field elements. This is the baseline MLE type used when coefficients are full-sized field elements.

Binding operates in-place on the evaluation vector:

```rust theme={null}
// HighToLow order
let (left, right) = self.Z.split_at_mut(n);
left.iter_mut().zip(right.iter()).for_each(|(a, b)| {
    *a += r * (*b - *a);
});

// LowToHigh order
for i in 0..n {
    self.Z[i] = self.Z[2 * i] + r * (self.Z[2 * i + 1] - self.Z[2 * i]);
}
```

Both orders have parallel variants (`bind_parallel`) using Rayon for performance.

### CompactPolynomial

`CompactPolynomial<T, F>` stores coefficients as small scalars of type `T` (such as `bool`, `u8`, `u16`, `u32`, `u64`, `u128`, `i64`, `i128`) rather than full field elements. This is the "pay-per-bit" representation that makes Dory commitments efficient.

The polynomial maintains two storage vectors:

* `coeffs: Vec<T>` - Original small-scalar coefficients (immutable after construction)
* `bound_coeffs: Vec<F>` - Field elements materialized lazily on the first bind

On the first bind, coefficients are promoted from small scalars to field elements using overflow-safe arithmetic:

```rust theme={null}
// For a pair (a, b) of small scalars:
match a.cmp(&b) {
    Ordering::Equal => a.to_field(),
    Ordering::Less  => a.to_field() + r * (b - a).to_field(),
    Ordering::Greater => a.to_field() - r * (a - b).to_field(),
}
```

After this first bind populates `bound_coeffs`, subsequent binds operate on field elements identically to `DensePolynomial`.

### Specialized Representations

Jolt includes several specialized MLE types that exploit structure in witness polynomials:

* **OneHotPolynomial**: Stores only the index of the single nonzero entry per cycle rather than a dense vector of 0s and 1s. Used for read/write address polynomials.
* **RaPolynomial**: A state machine that lazily materializes address polynomials across sumcheck rounds, keeping memory proportional to the address-space size rather than full trace length until final rounds.
* **RLCPolynomial**: Represents a random linear combination of multiple polynomials. Dense components are eagerly combined; one-hot components are combined lazily during evaluation.
* **EqPolynomial**: The equality MLE $\widetilde{\textsf{eq}}(r, \cdot)$, commonly used as a building block in sumcheck and MLE evaluation.

## The Equality Polynomial

The $\widetilde{\text{eq}}$ MLE is used throughout Jolt. It is the MLE of the function $\text{eq} \colon \{0, 1\}^m \times \{0, 1\}^m \to \mathbb{F}$ defined as:

$$
\text{eq}(r,x) = \begin{cases}
1 & \text{if } r = x \\
0 & \text{otherwise}
\end{cases}
$$

The explicit formula for the MLE is:

$$
\widetilde{\text{eq}}(r,x) = \prod_{i=1}^{\log(m)} (r_i \cdot x_i + (1 - r_i) \cdot (1 - x_i))
$$

where $r, x \in \{0,1\}^{\log(m)}$.

## Further Reading

For a more formal introduction to multilinear extensions, see **Section 3.5** of [Proofs, Arguments, and Zero Knowledge](https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf) by Justin Thaler.