Multilinearization in one variable

Let $F$ be a field and let $P\in F[X_1,\dots ,X_m]$ with $m\ge 1$. For $1\le i\le m$ define the multilinearization of $P$ in $X_i$ by $R_{X_i}P:=(1-X_i)(P{\mathrm{\mid }}_{X_i=0})+X_i(P{\mathrm{\mid }}_{X_i=1})\mathrm{.}$ This is a polynomial in $F[X_1,\dots ,X_m]$ of degree at most one in $X_i$; in every other variable its degree is at most the corresponding degree of $P$.

Let $\mathrm{\Phi }=Q_1{x}_1\cdots Q_n{x}_n\psi$ be a closed prenex quantified Boolean formula (Quantified Boolean formulas and the language TQBF) with quantifier-free matrix $\psi$ and matrix arithmetization $b=P_{\psi }$ (Field arithmetization of QBF quantifiers). The multilinearized ordered arithmetization of $\mathrm{\Phi }$ is obtained from $b$ by applying, for $j=n,n-1,\dots ,1$, first the $j$ reductions $R_{X_1},R_{X_2},\dots ,R_{X_j}$ in this order and then the quantifier operator $O_j$, where $O_j:=A_{X_j}$ when $Q_j=\mathrm{\forall }$ and $O_j:=E_{X_j}$ when $Q_j=\mathrm{\exists }$. The operator list of $\mathrm{\Phi }$ is the resulting sequence of operations read in application order, $R_{X_1},\dots ,R_{X_n},O_n,R_{X_1},\dots ,R_{X_{n-1}},O_{n-1},\dots ,R_{X_1},O_1,$ and its length is denoted $T$. Then $T=n(n+1)\mathrm{/}2+n=n(n+3)\mathrm{/}2$, and for $n=0$ the list is empty.

Write $P^{(n)}:=b$. For $j=n,\dots ,1$, write $M_j$ for the polynomial obtained from $P^{(j)}$ by the $j$ reductions of the $j$-th block, and $P^{(j-1)}:=O_j(M_j)$. The final $P^{(0)}$ is a constant.

• Substituting $X_i=0$ into $R_{X_i}P$ gives $(1-0)P{\mathrm{\mid }}_{X_i=0}+0=P{\mathrm{\mid }}_{X_i=0}$, and substituting $X_i=1$ gives $P{\mathrm{\mid }}_{X_i=1}$; so $R_{X_i}P$ agrees with $P$ where the substituted variable is Boolean, and its coefficient of $X_i$ is $P{\mathrm{\mid }}_{X_i=1}-P{\mathrm{\mid }}_{X_i=0}$.
• Reductions in distinct variables commute with one another, because $R_{X_i}$ alters only the $X_i$-dependence. The displayed order is the one the interactive protocol of The Shamir interactive protocol for TQBF reverses; it is recorded here so that the protocol has a definite node list.
• The operator list is not the same as the ordered arithmetization of Field arithmetization of QBF quantifiers: the reductions are inserted before each quantifier operation, and they are what keep the individual degrees of the intermediate polynomials bounded. That bound, together with the agreement of the sequence with the Boolean semantics, is proved in Multilinearization preserves Boolean values and bounds individual degree and The ordered arithmetization evaluates to the quantified Boolean truth value.