Multilinearization preserves Boolean values and bounds individual degree

Substituting $X_i=0$ in the right side of [A1] leaves $P{\mathrm{\mid }}_{X_i=0}$ and substituting $X_i=1$ leaves $P{\mathrm{\mid }}_{X_i=1}$. The coefficient of $X_i$ is $P{\mathrm{\mid }}_{X_i=1}-P{\mathrm{\mid }}_{X_i=0}$, so the $X_i$-degree is at most one; specialization, multiplication by $1-X_i$ or by $X_i$, and addition do not raise the degrees in the other variables. This proves claims (1) and (2), including for constant and zero polynomials.

If $P$ agrees with a function $g$ at every Boolean point, then at each Boolean point the value of $R_{X_i}P$ is the value of $P$ at the same point by step 1.1 and hence equals $g$ there. So $R_{X_i}P$ also agrees with $g$ on the Boolean cube, whichever bits $g$ takes.

By [L1] the matrix arithmetization $b=P_{\psi }$ has individual degree at most $L$ in every variable. Let $1\le j\le n$ and suppose $P^{(j)}$ has individual degree at most $2$ in $x_1,\dots ,x_j$ when $j\le n-1$. By step 1.1 the reductions of the block $j$ do not increase degrees in $x_{j+1},\dots ,x_n$ and make each of $x_1,\dots ,x_j$ have degree at most one, so $M_j$ is multilinear in $x_1,\dots ,x_j$ and its individual degrees in $x_{j+1},\dots ,x_n$ are at most those of $P^{(j)}$.

Applying $O_j$ specializes $M_j$ at $X_j=0$ and $X_j=1$ and multiplies or combines the two results, so [L2] gives $P^{(j-1)}$ individual degree at most twice that of $M_j$ in each remaining variable. At $j=n$ the polynomial $P^{(n-1)}$ has individual degree at most $2$ in $x_1,\dots ,x_{n-1}$, because $M_n$ is multilinear; inductively the same bound holds at every level $j\le n-1$.

For the degree of a node polynomial in its active variable, consider the blocks in turn. The reductions of the first block act on $b$ and on its successive reductions; repeated use of claim (2) of step 1.1 shows that the input polynomial of the reduction $R_{X_i}$ in that block has $X_i$-degree at most that of $b$, namely at most $L$. Every later reduction acts on some $P^{(j)}$ with $j\le n-1$, whose individual degrees are at most $2$ by step 3.1, and the quantifier node $O_j$ acts on the multilinear $M_j$, of $X_j$-degree at most one. Substituting arbitrary field elements for the other variables cannot raise any of these degrees, so every node polynomial specializes to a univariate of degree at most $D=\max (L,2)$.

The operator list consists of ${\sum }_{j=1}^{n}j=n(n+1)\mathrm{/}2$ reductions and $n$ quantifier operators, so $T=n(n+3)\mathrm{/}2$, which is $O(n^2)$; for $n=0$ the list is empty and all degree assertions are vacuous.