The material in Thaler's Section 3.5 does provide a complete treatment of the theory of multilinear Lagrange interpolation (including relevant proofs), but the logic has some nuance. Here's a short outline of how it works:
-
A multilinear polynomial in k variables is defined (Definition 3.4) as a polynomial in k variables which is linear in each variable individually (thinking of the other variables as constants). E.g. for the polynomial g(x, y) = xy + 4x + 3y, if you substitute y=1, then you get g(x, 1) = x + 4x + 3 = 5x + 3, which is linear. If you substitute x=1, then you get g(1, y) = y + 4 + 3y = 4y + 4 is also linear. Thus g is multilinear in the two variables x and y. A polynomial which is not multilinear is h(x, y) = y^2 + 4x + 3y, since h(1, y) = y^2 + 3y + 4, which is not linear as a univariate polynomial.
In other words, a polynomial is multilinear exactly when it only has monomials whose variables have exponent at most 1.
Relevant facts: any sum of multilinear polynomials is also multilinear, since adding two polynomials doesn't introduce new monomials to the result, so you still don't have any variables with exponent 2 or higher; similarly, a constant times a multilinear polynomial is mutilinear.
-
(Fact 3.5) If you have a function f assigning values to 0/1-valued inputs of k variables, then this defines a unique multilinear polynomial which extends f to all (possibly not 0/1-valued) inputs. This statement has two parts: there *exists* a multilinear extension of f, and this extension is *unique*, so that there is only one possible value for a multilinear polynomial which is equal to f on 0/1-valued inputs (even if it is written in an unusual or indirect way).
-
(Lemma 3.6) We can see the exact form of a multilinear extension by giving an explicit multilinear polynomial evaluating to a function f on the 0/1-valued inputs. Specifically, notice that the function \chi_w(x_1, ..., x_v) from this lemma (Equation 3.2) is very nice: for x_1, ..., x_v with values 0 or 1, \chi_w evaluates to 1 *exactly* when (x_1, ..., x_v) = (w_1, ..., w_v), and it evaluates to 0 for any other 0/1-valued input. It is also multilinear. (If you're not convinced of this, write the function out for two variables, with (w_1, w_2) = (0, 1).)
Now look at Equation 3.1. This is a sum of the functions \chi_w multiplied by some values f(w). That means it evaluates to exactly f(w) for each 0/1-valued input vector w, since every other term has a \chi_w' component for a different w', which evaluates to 0 at input w. Further, since sums of multilinear polynomials are multilinear, the sum in Equation 3.1 is also multilinear. Since Fact 3.5 tells us that a multilinear extension of f is unique, this equation describes *the* multilinear extension of f.
Here's how to interpret this last result: the functions \chi_w are the "multilinear Lagrange basis", meaning that any multilinear polynomial can be simply represented as a sum of these basis polynomials multiplied by constant factors (the f(w) terms in Equation 3.1), and this representation is unique. In the language of linear algebra, "the Lagrange polynomials \chi_w form a linear basis of the space of multilinear polynomials". Using this representation, a multilinear polynomial can be thought of in terms of its "2^k evaluations on the 2^k 0/1-valued inputs" instead of its "2^k coefficients of the 2^k square-free monomials".
Another consideration if you're familiar with the more traditional univariate Lagrange interpolation: the "multilinear 0/1 Lagrange basis" is analogous to the "Lagrange basis for univariate polynomials up to a fixed degree with chosen base points". In particular, the collection of polynomials represented in this way is fairly restricted -- it doesn't describe all multivariate polynomials, which in general have more complicated structure than the univariate case. More general interpolation schemes can be described for other families of multivariate polynomials besides the multilinear ones, but multilinear polynomials are expressive enough to represent data that is useful in proof or argument systems that we will get into in upcoming chapters (e.g. to represent the truth values of a circuit with given boolean inputs).