doubt in the proof of reducing any arithmetic circuit to log(d) depth, where d is the degree of the polynomial it is computing

Question

In the survey see section 5.3.2 : Depth reduction for arithmetic circuits for notations.

I follow the proof of the following two identities :

$[u]=\Sigma_{w\in \cal{F}_m}[u:w].[w]$ where $deg(u)\geq m$ and

$[u:v]=\Sigma_{w \in \cal{F}_m} [u:w][w:v]$ where $deg(u)\geq m \gt deg(v)$

By using these identities we are trying to reduce the depth of the circuit.

The idea it to write $[u]$ as product of polynomials that have degree at most half the degree of $[u]$.

Let $\cal{F}(u)=\cal{F}_m$ where $m=deg(u)/2$ and

$\cal{F}(u,v)=\cal{F}_m$ where $m=(deg(u)+deg(v))/2$ .

Then we have

1. $[u]=\Sigma_{w\in \cal{F}(u)}[u:w].[w]$ and

2. $[u:v]=\Sigma_{w \in \cal{F}(u,v)} [u:w][w:v]$.

The proof in the survey further expands both the equations writing $[w]$ as $[w_L].[w_R]$ in the first equation and $[w:v]$ as $[w_L].[w_R:v]$ in the second.

However I see no need for this as for the 1st equation we have

degree on RHS = $deg(u)$

degree on LHS : degree of $[u:w] \leq deg(u)-deg(w)$ and degree of $[w] = m = deg(u)/2$ as $w\in \cal{F}(u)$ .

For the second equation :

degree on RHS = $deg(u) - deg(v)$

degree on LHS $deg[u:w] \leq deg(u) -deg(w) = (deg(u)-deg(v))/2$ and $deg[w:v] \leq (deg(u)-deg(v))/2$ as $deg(w) = (deg(u)+deg(v))/2$ for all $w's$.

So my question is why in the proof presented in the survey, they are expanding further. They claim that the degrees are not yet halved if do not expand further but my working above shows that the degrees are halved.

Have I misunderstood anything here ?

Answer 1

See that $w\in \mathcal{F}_m$ so $\deg(w)\geq m$ but $\deg(w_L),\deg(w_R)<m$. So if $\deg(w_L)=\deg(w_R)=m-1$ then $\deg(w)$ becomes $2m-2$. If $m$ is large enough then $2m-2 >m$. Hence we can certainly have $\deg(w)>m$. Then $\deg([w])>m$ and all the terms in RHS will not have degree at most $\deg(u)/2$

Similarly think about the second part.