2
$\begingroup$

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

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

1 Answer 1

3
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Sorry to nitpick, but when you said ‘degree d function’ above did you mean ‘degree d Boolean function’? If so, do you know what happens if we drop the Boolean requirement? I.e. take f to be any real valued function (of Fourier degree d) on the hypercube. $\endgroup$
    – gen
    Sep 27, 2021 at 21:27
  • $\begingroup$ 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. $\endgroup$ Sep 27, 2021 at 21:30
  • $\begingroup$ Oh yes, of course. I wonder if there still might be a way to relate the 1-norm of f to it’s Fourier degree in this case as well… What if one assumes that the 2-norm of f is 1? $\endgroup$
    – gen
    Sep 27, 2021 at 21:30
  • $\begingroup$ 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". $\endgroup$ Sep 27, 2021 at 21:33

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.