Next: Applications of the Degree
Up: A DegreeDecreasing Lemma for
Previous: Preliminaries
The following lemma is our main tool. It exploits a surprising property of (MOD_{p}, MOD_{q})circuits, which lacks in (MOD_{p}, MOD_{p}) circuits, since constantdepth circuits with MOD_{p} 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 MOD_{m} gate to be chosen from set
.
Remark 2. The output of the general MOD_{m} gates depend only on the sum of the inputs. In the next lemma it will be more convenient to denote
i.e., gate MOD^{A}_{m} with inputs
,
by
.
Lemma 4 (Degree Decreasing Lemma)
Let
p and
q be different primes, and let
x_{1},
x_{2},
x_{3} be variables with values from
.
Then
where
H_{i} abbreviates
for
,
where
is the multiplicative inverse of
p modulo
q:
,
and
is a positive integer satisfying
.
In the special case of
)
circuit, the statement of Lemma 4 is illustrated on Figure 1.
Figure 1:
Degreedecreasing in the
case: on the left the input is a degree two polynomial, on the right the inputs are linear polynomials.

Proof: Let x_{1}=k and let
.
Then
and
since for any fixed x_{2},x_{3}, i,k expression
kx_{2}+x_{3}+j(ki) takes on every value exactly once modulo p while
;
so
equals to 1 exactly A times.
Consequently,
Next: Applications of the Degree
Up: A DegreeDecreasing Lemma for
Previous: Preliminaries
Vince Grolmusz
19991108