Suppose you have some boolean function $f: \{-1,1\}^n \rightarrow \{-1,1\}$ with rational coefficients such that all degree 1 monomials of $f$ have a nonzero coefficient and the degree $n$ monomial has a nonzero coefficient.

Can we lower bound the number of monomials in $f$ by $2^{\Omega(n)}$?

One can show a lower bound of $n^2$ monomials as follows. Take $f^2(x)$. This will be a constant function always equal to 1, so all monomials must have coefficient 0. But when we look at the product of $f^2$, we see the degree 1 monomials and the degree $n$ imply degree 2 and degree $n-1$ monomials with nonzero coefficients. So there must be at least one other monomial present for each of these terms so the coefficients sum to 0.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.