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 .

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 i.e., gate MODAm with inputs , by .

Lemma 4 (Degree Decreasing Lemma)     Let p and q be different primes, and let x1,x2,x3 be variables with values from . Then

where Hi 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.

Proof:    Let x1=k and let . Then

and

since for any fixed x2,x3, i,k expression kx2+x3+j(k-i) takes on every value exactly once modulo p while ; so equals to 1 exactly |A| times. Consequently,

Next: Applications of the Degree Up: A Degree-Decreasing Lemma for Previous: Preliminaries
Vince Grolmusz
1999-11-08