next up previous
Next: Applications of the Degree Up: A Degree-Decreasing Lemma for Previous: Preliminaries

The Degree-Decreasing Lemma

The following lemma is our main tool. It exploits a surprising property of (MODp, MODq)-circuits, which lacks in (MODp, MODp) circuits, since constant-depth circuits with MODp gates are capable only to compute a constant degree polynomial of the inputs, and this constant depends on the depth, and not on the size.

Remark 1. Generally, the inputs of the modular gates are Boolean variables. Here, however, for wider applicability of the lemma, we allow input x for a general MODm gate to be chosen from set $\{0,1,\ldots,m-1\}$.

Remark 2. The output of the general MODm gates depend only on the sum of the inputs. In the next lemma it will be more convenient to denote $\hbox{\rm MOD}^A_m(y_1,y_2,\ldots,y_\ell)$ i.e., gate MODAm with inputs $y_1,y_2,\ldots,y_\ell$, by $\hbox{\rm MOD}^A_m(y_1+y_2+\cdots+y_\ell)$.

Lemma 4 (Degree Decreasing Lemma)     Let p and q be different primes, and let x1,x2,x3 be variables with values from $\{0,1,\ldots,p-1\}$. Then

\begin{displaymath}\hbox{\rm MOD}_q^B(\hbox{\rm MOD}_p^A(x_1x_2+x_3))=\hbox{\rm MOD}_q^B(H_0+H_1+\cdots+H_{p-1}+\beta ),\end{displaymath}

where Hi abbreviates

\begin{displaymath}H_i=\alpha \sum_{j=0}^{p-1} \hbox{\rm MOD}^A_p(ix_2+x_3+j(x_1+(p-i)))\end{displaymath}

for $i=0,1,\ldots,p-1$, where $\alpha$ is the multiplicative inverse of p modulo q: $\alpha p\equiv 1\pmod{q}$, and $\beta$ is a positive integer satisfying $\beta=-\vert A\vert(p-1)\alpha\bmod{q}$.

In the special case of $(\hbox{\rm MOD}_3, \hbox{\rm MOD}^{\{1\}}_2$) circuit, the statement of Lemma 4 is illustrated on Figure 1.

Figure 1: Degree-decreasing in the $( \hbox {\rm MOD}_3,\hbox {\rm MOD}^{\{1\}}_2)$ case: on the left the input is a degree two polynomial, on the right the inputs are linear polynomials.
\hskip -2.2cm

Proof:    Let x1=k and let $0\leq i\leq p-1, \ k\ne i$. Then

\begin{displaymath}H_k=\alpha \sum_{j=0}^{p-1} \hbox{\rm MOD}^A_p(kx_2+x_3)=\alp...
...OD}^A_p(kx_2+x_3)\equiv \hbox{\rm MOD}^A_p(x_1x_2+x_3)\pmod{q},\end{displaymath}


\begin{displaymath}H_i=\alpha \sum_{j=0}^{p-1} \hbox{\rm MOD}^A_p(ix_2+x_3+j(k-i))=\alpha \vert A\vert,\end{displaymath}

since for any fixed x2,x3, i,k expression kx2+x3+j(k-i) takes on every value exactly once modulo p while $j=0,1,\ldots,p-1$; so $\hbox{\rm MOD}^A_p(ix_2+x_3+j(k-i))$ equals to 1 exactly |A| times. Consequently,

\begin{displaymath}\hbox{\rm MOD}^B_q(H_0+H_1+\cdots+H_{p-1}+\beta )=\hbox{\rm M...
...\hbox{\rm MOD}^A_p(x_1x_2+x_3)+(p-1)\alpha \vert A\vert+\beta)=\end{displaymath}

\begin{displaymath}=\hbox{\rm MOD}^B_q(\hbox{\rm MOD}^A_p(x_1x_2+x_3)).\end{displaymath}

next up previous
Next: Applications of the Degree Up: A Degree-Decreasing Lemma for Previous: Preliminaries
Vince Grolmusz