can't figure it out-

Let $F = \Bbb{F}_2 = \{0,1\}$ and Let $f(x_1, \ldots , x_m)$ be a non-constant polynomial of total degree $d$, with individual degrees smaller than 2. Prove that:

$$1/(2^d) \le Pr [ f (a_1,\ldots, a_m) = 0] \le 1 − 1/(2^d)$$

where $a_1 ,\ldots ,a_m$ are chosen uniformly from $F$

I was suggested to prove it using induction on the total degree $d$. The basis was easy (for example, one part of the inequality can be proven directly from Schwartz–Zippel lemma) but I got stuck on the inductive step.

Help will be highly appreciated

  • 1
    $\begingroup$ Because the question is essentially about the weights of the Reed-Muller code $RM(d,m)$ you can find a solution in many a book on coding theory. It suffices to prove the lower bound, because you get the upper bound by applying the lower bound to $1+f$ (or vice versa). $\endgroup$ – Jyrki Lahtonen Nov 13 '15 at 19:38
  • 1
    $\begingroup$ A hint for the induction step. Without loss of generality we can assume that $x_m$ appears in $f$. We can then write $$f(x_1,\ldots,x_m)= x_mg(x_1,\ldots,x_{m-1})+h(x_1,\ldots,x_{m-1}),$$ where $g$ has total degree $\le d-1$. The induction hypothesis says something about the number of times $g(a_1,\ldots,a_{m-1})=1$. When that happens the values $f(a_1,\ldots,a_{m-1},0)$ and $f(a_1,\ldots,a_{m-1},1)$ are different. One is $0$ the other $1$. $\endgroup$ – Jyrki Lahtonen Nov 13 '15 at 19:44
  • 1
    $\begingroup$ I will add to Jyrki's comment that the bounds are tight in the sense that there are polynomials (e.g. $x_1x_2\cdots x_d$) for which the probability is exactly $2^{-d}$, and the complements of these polynomials have the complementary probability. $\endgroup$ – Dilip Sarwate Nov 19 '15 at 16:16

Your Answer

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

Browse other questions tagged or ask your own question.