<p>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) <a href="http://www.contrib.andrew.cmu.edu/~ryanod/?p=301" rel="nofollow">here</a>). 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.</p>

<p>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 &lt; |f^{-1}(0)| &lt; 2^n$. However, if $|f^{-1}(0)| \in \{0,2^n\}$ then the function is constant.</p>

CC BY-SA 3.0
2014-11-16T07:53:03.603Z
I think you missed the reference for exercise 12(b). Do you think this problem can be approached by sensitivity technique (say if one can pick the zero set structurally)?
ASF
CC BY-SA 3.0
2014-11-16T15:21:25.560Z
Added the reference. If you know more then you can probably say more, but this is a very open-ended direction, and I'm not aware of anything of that sort.
Yuval Filmus
CC BY-SA 3.0
2014-11-15T23:33:09.880Z
2014-11-16T15:19:11.247Z
2014-11-16T15:19:11.247Z
Yuval Filmus
<p>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)$?</p>

CC BY-SA 3.0
2014-11-15T21:12:47.620Z
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
CC BY-SA 3.0
2014-11-15T21:31:42.560Z
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
CC BY-SA 3.0
2014-11-15T23:03:46.490Z
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
<boolean-functions>
On Boolean functions with a certain number of zeros
ASF
# On Boolean functions with a certain number of zeros

(Asked by: username_0 on 2014-11-15)

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)$?

**Tags:** boolean-functions
> **Comments:**
> **username_1**: 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?  
> **username_0**: 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)|)$.  
> **username_1**: Originally the question asked for upper bound on the degree of any polynomial representing f and that one does not have an upper bound.  

---

## 1 answers

### Answer by username_2 on 2014-11-15. Score: 4

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](http://www.contrib.andrew.cmu.edu/~ryanod/?p=301)). 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.

> **Comments:**
> **username_0**: I think you missed the reference for exercise 12(b). Do you think this problem can be approached by sensitivity technique (say if one can pick the zero set structurally)?  
> **username_2**: Added the reference. If you know more then you can probably say more, but this is a very open-ended direction, and I'm not aware of anything of that sort.  

---

