next up previous
Next: The Proof of Theorem Up: Applications of the Degree Previous: The ID function

The MOD r function

Krause and Pudlák [12] proved that any $(\hbox{\rm MOD}_{p^k}^{\{0\}}, \hbox{\rm MOD}_{q}^{\{0\}};1)$ circuit which computes the $\hbox{\rm MOD}_{r}^{\{0\}}$ function has size at least 2c''n, for some c>0, where p,q and r are different primes. We also generalize this result as follows:

Theorem 8   There exist 0<c'<c<1 for different primes p,q,r, and positive integer k, if circuit $(\hbox{\rm MOD}_{p^k}^{\{0\}}, \hbox{\rm MOD}_{q}^{\{0\}};{cn}-\hbox{\rm AND})$ computes $\hbox{\rm MOD}_{r}^{\{0\}}(x_1,x_2,\ldots,x_n)$, then its size is at least 2c'n.

Proof:    From the result of [12] and from Theorem 9 the statement is immediate. $\Box$

Vince Grolmusz