Polynomial degree is an important measure for studying the computational complexity f Boolean function. A polynomial P€Zm[x] is a generalized representation of f over Zm if x, y€{0, 1}n; f(x)≢f(y)⇒P(x)≢P(y)(mod m). Denote the minimum degree as degmge(f), and degmsym,ge(f) if the minimum is taken from symmetric polynomials. In this paper we prove new lower bounds for the symmetric Boolean functions that depend on n variables. First, let m1 and m2 be relatively prime numbers and have s and t distinct prime factors respectively. Then we have
m1m2(degm1sym,ge(f))s(degm2sym,ge(f))t > n
A polynomial Q€Zm[x] is a one-sided representation of f over Zm if x€{0, 1}n; f(x)≢0⇔Q(x)=0(mod m). Denote the minimum degree among these Q as degmos(f). Note that Q(x) can be non-symmetric. Then with the same conditions as above, at least one of
m1m2(degm1sym,ge(f) (f))s(degm2sym,ge(f))t > n
and
m1m2(degm1sym,ge(f) (f))s(degm2sym,ge(¬f))t > n
is true.