Krause and Pudlák [12] proved that any
circuit which computes the
function has size at least 2^{c''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
computes
,
then its size is at least
2^{c'n}.

Proof: From the result of [12] and from Theorem 9 the statement is immediate.
Vince Grolmusz 1999-11-08