# Boolean function and real degree

Let $f$ be a boolean function with minimum degree real polynomial representing it be of degree $d$.

Is there a relation between number of zeros $f$ or $1-f$ and degree $d$?

• Yes. More generally, the Fourier coefficients are all multiples of $2^{-d}$. May 10, 2016 at 4:36
• ah serious???? how so? May 10, 2016 at 4:40
• You can prove it by induction. Should be in O'Donnell's book. May 10, 2016 at 4:57

Exercise 12 (online version) in §1 of Ryan O'Donnell's Analysis of Boolean functions shows that all Fourier coefficients of a degree $d$ function are integer multiples of $2^{-d}$. In particular, the number of zeroes of $f$ is an integer multiple of $2^{n-d}$.
Moreover, for every integer $k \in \{0,\ldots,2^d\}$ there is a degree $d$ Boolean function having exactly $k2^{n-d}$ zeroes. This easily follows from the fact that a function on $d$ variables has degree at most $d$.
• Right, I meant Boolean degree $d$ function. I'm not sure what happens in general – if you're interested, you can ask a question about it. Sep 27, 2021 at 21:30
• The question is about number of zeroes. That's not a $p$-norm for any $p$, though it's related to the so-called $L_0$ "norm". Sep 27, 2021 at 21:33