# Monomial Sparsity of Boolean Functions

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.