## Multi-linear extension

Following the definition from Justin Thaler

Let \(\mathbb{F}\) be any finite field, and let \( f : \{0,1\}^v \rightarrow \mathbb{F} \) be any function mapping the \( v \)-dimensional Boolean hypercube to \(\mathbb{F}\). A \( v \)-variate polynomial \( g \) over \(\mathbb{F}\) is said to be an extension of \( f \) if \( g \) agrees with \( f \) at all Boolean-valued inputs, i.e., \( g(x) = f(x) \) for all \( x \in \{0,1\}^v \).

an example:

x | y | f |

0 | 0 | \(f(0,0)\) |

0 | 1 | \(f(0,1)\) |

1 | 0 | \(f(1,0)\) |

1 | 1 | \(f(1,1)\) |

The multi-linear extension of \(f\) can be expressed as:

$$\tilde f=f(0,0)(1-x)(1-y)+f(0,1)(1-x)y+f(1,0)x(1-y)+f(1,1)xy$$

## Notes

sum-check protocol deals with binary inputs.

In every layer of GKR, a sum-check is used, which means all the inputs need to be binary.

The multi linear extension is for \(P(x_1,…,x_n)\), not for the sum.

## The protocol

Input:

– A multilinear polynomial \( g(x_1, x_2, \ldots, x_n) \) of degree at most 1 in each variable over a finite field \(\mathbb{F}\).

– A value \( S \in \mathbb{F} \) that is claimed to be the sum of \( g \) over all possible binary inputs, i.e., \( S = \sum_{x_1 \in \{0,1\}} \sum_{x_2 \in \{0,1\}} \cdots \sum_{x_n \in \{0,1\}} g(x_1, x_2, \ldots, x_n) \).

**Protocol:**

**Initialize: **

Let \( i = 1 \).

Prover’s Claim:

The Prover claims that \[ S = \sum_{x_1 \in \{0,1\}} \sum_{x_2 \in \{0,1\}} \cdots \sum_{x_n \in \{0,1\}} g(x_1, x_2, \ldots, x_n). \]

**While \( i \leq n \):**

Prover computes the univariate polynomial \[ h_i(z) = \sum_{x_{i+1} \in \{0,1\}} \cdots \sum_{x_n \in \{0,1\}} g(x_1, \ldots, x_{i-1}, z, x_{i+1}, \ldots, x_n) \] and sends \( h_i(z) \) to the Verifier.

– Verifier: Checks that \[ h_i(0) + h_i(1) = h_{i-1}(r_{i-1}), \] where \( h_0 = S \) and \( r_{i-1} \) is the value chosen by the Verifier in the previous round. If the check fails, the Verifier rejects and terminates.

– Verifier: Picks a random \( r_i \in \mathbb{F} \) and sends \( r_i \) to the Prover.

– Prover: Sets \( g(x_1, \ldots, x_{i-1}, r_i, x_{i+1}, \ldots, x_n) \) as the new polynomial and continues to the next iteration.

– Increment \( i \).

**Final Check:** After \( n \) rounds, the Prover sends the value \( g(r_1, r_2, \ldots, r_n) \) to the Verifier.

– Verifier: Evaluates \( g(r_1, r_2, \ldots, r_n) \) directly and checks if it matches the value sent by the Prover.

– If the values match, the Verifier accepts.

– Otherwise, the Verifier rejects.

## Notes

The above sum-check protocol directly start with a multilinear polynomial over finite field \(\mathbb{F}\). While many other description will start with a polynomial defined over binary hypercube, i.e., \(x_n\in\{0,1\}\), the multilinear extension of the polynomial will have notation as \(\tilde g(x_1, x_2, \ldots, x_n).\)

In every round, the polynomial sent by the prover to the verifier is a one degree polynomial \(h(z)=\alpha+\beta z\), \(\alpha\) and \(\beta\) are coefficients.

Given an example of 3 variants linear polynomial \(f(x,y,z)\), it has a universal representation as

$$g(X,Y,Z)=a_0+a_xX+a_yY+a_zZ+a_{xy}XY+a_{xz}XZ+a_{yz}YZ+a_{xyz}XYZ$$

Then in the first round, the polynomial sent by prover to the verifier is:

\(h(t)=g(t,0,0)+g(t,0,1)+g(t,1,0)+g(t,1,1)=(4a_x+2a_{xz}+2a_{xy}+a_{xyz})t+4a_0+2a_y+2a_z+a_{yz}\)

i.e.,

$$\alpha=4a_x+2a_{xz}+2a_{xy}+a_{xyz}$$

$$\beta=4a_0+2a_y+2a_z+a_{yz}$$