3
$\begingroup$

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.

$\endgroup$

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.