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

  • $\begingroup$ Yes. More generally, the Fourier coefficients are all multiples of $2^{-d}$. $\endgroup$ May 10 '16 at 4:36
  • $\begingroup$ ah serious???? how so? $\endgroup$
    – Mr.
    May 10 '16 at 4:40
  • $\begingroup$ You can prove it by induction. Should be in O'Donnell's book. $\endgroup$ 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.