Representing symmetric boolean functions with polynomial over composite moduli

Polynomial degree is an important measure for studying the computational complexity of Boolean function. A polynomial PZ_m[x] is a generalized representation of f over Z_m if x, y(0, 1)ⁿ; f(x)f(y)P(x)≢P(y)(mod m). Denote the minimum degree as deg_m ^ge(f), and deg_m ^{sym 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 m₁ and m₂ be relatively prime numbers and have s and t distinct prime factors respectively. Then we have m₁m₂ (deg_m ^sym ₁ ^{, ge} (f ))^s (deg_m ^sym ₂ ^{, ge} (f ))^t n. A polynomial QZ_m[x] is a one-sided representation of f over Z_m if x(0, 1)ⁿ; f(x)=0Q(x)0(mod m). Denote the minimum degree among these Q as deg_m ^os(f). Note that Q(x) can be non-symmetric. Then with the same conditions as above, at least one of m₁m₂ (deg_m ^sym ₁ ^{, ge} (f ))^s (deg_m ^sym ₂ ^{, ge} (f ))^t n and m₁m₂ (deg_m ^sym ₁ ^{, ge} (f ))^s (deg_m ^sym ₂ ^{, ge} (f ))^t n is true.