# On Boolean functions with a certain number of zeros

Given boolean $f(\Bbb x)$, with $\Bbb x\in\{0,1\}^n$, what are good upper/lower bounds, in terms of $|f^{-1}(0)|$, for minimum $deg(p(\Bbb x))$ of a real polynomial satisfying $p(\Bbb x)=f(\Bbb x)$?

• There is not any upper bound, extra degree does not restrict the class of functions. For lower bound, is min deg a monotone function in the number of zeros? – Kaveh Nov 15 '14 at 21:12
• Why is there no upper bound? I am just looking for two numbers $\theta_f(|f^{-1}(0)|)$ and $\psi_f(|f^{-1}(0)|)$ such that $\theta_f(|f^{-1}(0)|)\leq \mbox{minimum }deg(p(x))\leq\psi_f(|f^{-1}(0)|)$. – ASF Nov 15 '14 at 21:31
• Originally the question asked for upper bound on the degree of any polynomial representing f and that one does not have an upper bound. – Kaveh Nov 15 '14 at 23:03

One relevant result is that if $\deg f = d$ then $2^d\hat{f}(S)$ is an integer for all $S$ (see for example exercise 12(b) here). In particular, $2^d\hat{f}(\emptyset) = 2^{d-n}|f^{-1}(1)|$ is an integer, and so $|f^{-1}(0)|$ is a multiple of $2^{n-d}$. This gives a lower bound on $d$ given $|f^{-1}(0)|$, which is tight for an AND of $d$ variables.
In terms of corresponding upper bounds you can't expect much, since there are balanced functions of maximal degree (parity for example). Moreover, there are functions with $|f^{-1}(0)| = 2^{n-k}$ of maximal degree for all $1 \leq k \leq n$, for example parity on $n-k+1$ variables ORed with $k-1$ variables; you can probably be a bit more cunning and construct a function of maximal degree for any given $0 < |f^{-1}(0)| < 2^n$. However, if $|f^{-1}(0)| \in \{0,2^n\}$ then the function is constant.