Multilinear Polynomials

For each field $\mathcal{T}_\iota$, we write $\mathcal{T}_\iota[X_0, \ldots , X_{\ell - 1}]$ for the ring of multivariate polynomials in the indeterminates $X_0, \ldots , X_{\ell - 1}$. A polynomial $t(X_0, \ldots , X_{\ell - 1}) \in \mathcal{T}_\iota[X_0, \ldots, X_{\ell - 1}]$ is multilinear if each indeterminate appears in it with individual degree at most 1.

Here, we explain an important mathematical duality that we will use throughout this site. That is:

Multilinears and Lists

More precisely, for each field $\mathcal{T}_\iota$ and each size parameter $\ell$, we have two objects which are really "the same":

1. A multilinear polynomial $t(X_0, \ldots , X_{\ell - 1})$ with coefficients in $\mathcal{T}_\iota$.
2. An ordered list of $2^\ell$ elements of $\mathcal{T}_\iota$.

To go from 1. to 2. above, we actually take two steps. We begin with a multilinear $t(X_0, \ldots , X_{\ell - 1})$ over $\mathcal{T}_\iota$. First, we can pick up its "Lagrange coordinates"—that is, its restriction to the cube $\mathcal{B}_\ell \subset \mathcal{T}_\tau^\ell$. Indeed, we have the cube-indexed vector of values $\left( t(v) \right)_{v \in \mathcal{B}_\ell}$.

We can then flatten the cube $\mathcal{B}_\ell$ itself, by associating it with the ordered list of integers $\{0, \ldots , 2^\ell - 1\}$. Indeed, we can associate each $v \in \mathcal{B}_\ell \mapsto \{ v \} \coloneqq \sum_{i = 0}^{\ell - 1} 2^i \cdot v_i$. Thus, if we define $t_{\{v\}} \coloneqq t_v$ for each $v \in \mathcal{B}_\ell$, then we get the desired list $(t_i)_{i = 0}^{2^\ell - 1}$. It's not hard to see that this list is just $\left( t(0, \ldots , 0), t(1, 0, \ldots , 0), \ldots , t(0, 1, \ldots , 1), t(1, \ldots , 1) \right)$ (i.e., the evaluation points are taken in lexicographic order).

In the next couple steps, we discuss going in the reverse direction (i.e., from 2. to 1.).

The Equality Indicator Polynomial

We begin by recording a key polynomial. For each fixed $\ell \geq 0$, the $2 \cdot \ell$-variate equality indicator polynomial $\widetilde{\texttt{eq}}(X_0, \ldots , X_{\ell - 1}, Y_0, \ldots , Y_{\ell - 1})$ is defined to be:

This polynomial, on the one hand, is multilinear in its $2 \cdot \ell$ variables. On the other hand, its restriction to the cube $\mathcal{B}_\ell \times \mathcal{B}_\ell$ recovers the equality indicator function, the function which, on two bitstrings $u$ and $v$, equals 1 if and only if $u = v$ and 0 otherwise.

This polynomial has two key properties:

• It is succinct. Indeed, given any pair of points $r$ and $r'$ in $\mathcal{T}_\tau^\ell$, the evaluation $\widetilde{\texttt{eq}}(r, r')$ can be computed in $O(\ell)$ work. (Indeed, we can work one at a time through the $\ell$ factors of the right-hand side above, and then multiply them all together.) This is not true for generic, $2 \cdot \ell$-variate multilinear polynomials! Indeed, $\widetilde{\texttt{eq}}$ is special. (To get a hint for what's special about it, just look at how it factors into a product of $\ell$ terms—not all polynomials will do this.)
• Its partial specializations give us Lagrange basis polynomials. Indeed, if we pick a cube point $v \in \mathcal{B}_\ell$, nothing stops us from partially specializing $\widetilde{\texttt{eq}}$'s later variables $(Y_0, \ldots , Y_{\ell - 1})$ to $(v_0, \ldots , v_{\ell - 1})$. Doing this gives us the $\ell$-variate polynomial $(X_0, \ldots , X_{\ell - 1}) \mapsto \widetilde{\texttt{eq}}(X_0, \ldots , X_{\ell - 1}, v_0, \ldots , v_{\ell - 1})$. Now this polynomial has two important properties. First, it's multilinear in the variables $X_0, \ldots , X_{\ell - 1}$. Second, its restriction to the cube $\mathcal{B}_\ell$ is identically zero except for one point, namely the point $v \in \mathcal{B}_\ell$. This makes it useful as a "building block", as we'll see just below.

Multilinear Extensions

As we'll argue now, the association between the list items 1. and 2. above is bijective. That is, we already saw that each multilinear polynomial determines a list of values on the cube (i.e., we went from 1. to 2.). What we want to do is reverse this process: beginning with a list of values $\left( t_i \right)_{i = 0}^{2^\ell - 1}$, we want to reverse-engineer a multilinear $t(X_0, \ldots , X_{\ell - 1})$ whose evaluations $\left( t(v) \right)_{v \in \mathcal{B}_\ell}$ on the cube recover the initial list $\left( t_i \right)_{i = 0}^{2^\ell - 1}$.

It turns out that the desired multilinear $t(X_0, \ldots , X_{\ell - 1})$:

• Exists. Indeed, to recover $t(X_0, \ldots , X_{\ell - 1})$, we reverse the process above. Beginning with the ordered list $\left( t_i \right)_{i = 0}^{2^\ell - 1}$, we can arrange the list elements onto the cube vertices by taking $\left( t_{\{v\}} \right)_{v \in \mathcal{B}_\ell}$. Next, we need to "extend" this mapping into a polynomial. It turns out we can use the Lagrange basis polynomials just introduced. That is, we can take the combination $$\begin{equation*}t(X_0, \ldots , X_{\ell - 1}) \coloneqq \sum_{v \in \mathcal{B}_\ell} t_{\{v\}} \cdot \widetilde{\texttt{eq}}(v_0, \ldots , v_{\ell - 1}, X_0, \ldots , X_{\ell - 1}).\end{equation*}$$ You can check that this candidate $t(X_0, \ldots , X_{\ell - 1})$ indeed fulfills our desideratum: namely, its values on the cube satisfy $t(v) = t_{\{v\}}$ for each $v \in \mathcal{B}_\ell$.
• Is unique. The slightly trickier part is to argue that the multilinear polynomial $t(X_0, \ldots , X_{\ell - 1})$ is unique—that is, it's the only possible multilinear whose restriction to the cube equals $\left( t_i \right)_{i = 0}^{2^\ell - 1}$. To show this, it's enough to argue that if a multilinear vanishes identically on the cube, then it must actually be the 0 polynomial. This proof is elementary but a bit delicate (and pretty interesting); it is carried out for example in Thaler [Tha23, Fact 3.5.].

Thus, not only can we associate to each multilinear $t(X_0, \ldots , X_{\ell - 1})$ a list of values $\left( t_i \right)_{i = 0}^{2^\ell - 1}$, but this association is reversible: to each list $\left( t_i \right)_{i = 0}^{2^\ell - 1}$, we get a unique multilinear whose evaluations on the cube recover that list.