Lower Bounds on Representing Boolean Functions as Polynomials in $Z_m $
Shi‐Chun Tsai · SIAM Journal on Discrete Mathematics · 1996
Define the $MOD_m $-degree of a boolean function F to be the smallest degree of any polynomial P, over the ring of integers modulo m, such that for all 0-1 assignments $\vec x$, $F(\vec x) = 0$ iff $P(\vec x) = 0$. By exploring the periodic property of the binomial coefficients modulo m, two new lower bounds on the $MOD_m $-degree of the $MOD_l $ and $- MOD_m $ functions are proved, where m is any composite integer and l has a prime factor not dividing m. Both bounds improve from sublinear to $\Omega (n)$. With the periodic property, a simple proof of a lower bound on the $MOD_m $-degree with symmetric multilinear polynomial of the OR function is given. It is also proved that the majority function has a lower bound $\frac{n}{2}$ and the MidBit function has a lower bound $\sqrt n $.