Exponential degree without multilinearization

Every ${\mathrm{\Phi }}_k$ is a closed prenex quantified Boolean formula: its prefix is the $k+1$ quantifiers $\mathrm{\exists }y,\mathrm{\forall }{x}_1,\dots ,\mathrm{\forall }{x}_k$ read left to right and its matrix is the variable leaf $(y)$, so it has $k+2$ syntax nodes. Fix the explicit binary-index encoding that writes each $x_i$ using its binary index and fixed punctuation. This is a fixed effective encoding allowed by [A3]; its length $m_k$ satisfies $m_k\ge k+1$ and $m_k=O(k\log (k+1))$. By [A2] the arithmetization of the matrix $(y)$ is $b=Y$. Each ${\mathrm{\Phi }}_k$ is also true, since the assignment $y=1$ makes the matrix $(y)$ true under every assignment to $x_1,\dots ,x_k$, so $\mathrm{\forall }{x}_1\cdots \mathrm{\forall }{x}_k(y)$ holds and then $\mathrm{\exists }y$ holds by [A3].

By the inner-to-outer rule of [A1] the naive sequence of ${\mathrm{\Phi }}_k$ applies the $k$ universal operators first, in the order $A_{x_k},A_{x_{k-1}},\dots ,A_{x_1}$, and applies the outer existential operator $E_y$ for the variable $y$ last, no reduction $R_{X_i}$ being inserted.

Base case of the induction on $j$: after zero universal operators the carried polynomial is $b=Y=Y^{2^0}$ by step 1.1.

Induction hypothesis: for some $0\le j<k$, after the first $j$ universal operators of the sequence of step 2.1 the carried polynomial is $Y^{2^j}$.

Under the hypothesis of step 3.1 the polynomial $Y^{2^j}$ involves none of the variables $X_1,\dots ,X_k$, so both specializations at the next variable $X_i$ coincide with $Y^{2^j}$, and the operator $A_{X_i}$ of [A1] returns the product $Y^{2^j}\cdot Y^{2^j}=Y^{2^{j+1}}$; hence the hypothesis holds again at $j+1$.

Steps 2.2, 3.1 and 4.1 give, after all $k$ universal operators, the carried polynomial $Y^{2^k}$, which is the polynomial immediately before the outer quantifier on $y$ is processed; the protocol's message at the node for $\mathrm{\exists }y$ is the restriction of this polynomial in the active variable $y$, namely the univariate polynomial with value $y^{2^k}$ and $2^k+1$ coefficients, so its degree in the active variable is exactly $2^k$. Since $m_k=O(k\log (k+1))$ for the fixed encoding of step 1.1, for every polynomial $q$ one has $2^k>q(m_k)$ for all sufficiently large $k$, so the degree bound asserted in [A4] fails for this allowed encoding: the exponential degree is witnessed on instances that are true, and the failure is therefore one of degree and not of Boolean semantics. No length bound is inferred from syntax-node count alone.