Multilinear Polynomials

Taken from: Oleg Fomenko and Anton Levochko: Understanding Lasso - A Novel Lookup Argument Protocol

---

We call an $\ell$-variate polynomial $f:{\mathbb{F}}^{\ell }\to \mathbb{F}$ multilinear if it has degree at most one in each variable.

Let $f:\{0,1{\}}^{\ell }\to \mathbb{F}$ be any function mapping the $\ell$-dimensional Boolean hypercube to a field $\mathbb{F}$. By definition, it equals:

$$f(x)=\sum _{k\subseteq [\ell ]}{a}_k\prod _{i\in k}{x}_i$$

For $f$, we can observe an equivalence between the notions of a “multilinear polynomial” and an “ordered list.” Indeed, any $\ell$-variate multilinear polynomial $f$ can be represented as a vector of $2^{\ell }$ elements, where the element at position $i={\sum }_{j=0}^{\ell -1}{2}^j\cdot r_j$ equals $f(r_0,\dots ,r_{\ell -1})$. This list can be naturally expressed as:

$$t=\{f(0,\dots ,0),f(1,0,\dots ,0),\dots ,f(0,\dots ,0,1),\dots ,f(0,1,\dots ,1),f(1,\dots ,1)\}$$

where the arguments are lexicographically ordered.

To perform the inverse transformation, we can define the equality function $\text{eq}:\{0,1{\}}^{\ell }\times \{0,1{\}}^{\ell }\to \mathbb{F}$ as follows:

$$\text{eq}(x,e)=\{\begin{array}{ll}1& \text{if }x=e\\ 0& \text{otherwise}\end{array}\text{\hspace{1em}(1)}$$

If we can represent this function as a polynomial, then we can build a multilinear polynomial from our array $t$ as follows (here, $t[i]$ denotes the $i$-th element of the array $t$):

$$f(r_0,\dots ,r_{\ell -1})=\sum _{x\in \{0,1{\}}^{\ell }}t\left[\sum _{j=0}^{\ell -1}{2}^j\cdot x_j\right]\cdot \text{eq}(x_0,\dots ,x_{\ell -1},r_0,\dots ,r_{\ell -1})$$

Remark

We’ve shown the equivalence between ordered lists and multilinear polynomials. In particular, most papers assume that any multilinear polynomial can be accessed in either of these two forms (and their derivative forms) at any time.