# 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}$. – Yuval Filmus May 10 '16 at 4:36
• ah serious???? how so? – 1.. May 10 '16 at 4:40
• You can prove it by induction. Should be in O'Donnell's book. – Yuval Filmus May 10 '16 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$.