What is the expected difference in the gap of two polynomials in $Z_2[x_1, ..., x_n]$ when adding a randomly chosen variable $x_i, i \in [n]$?

28 Views Asked by At

I define the gap of a polynomial $f \in Z_2[x_1, ..., x_n]$ as

$gap(f) = |f^{-1}(0)| - |f^{-1}(1)|$.

I'm curious about the quantity $\mathbb{E}_i[|gap(f) - gap(f + x_i)|]$. I'm interested in this quantity expressed as a function of whatever properties of $f$ you find salient to its computation. Ones that would be particularly useful for me is $s$, the number of terms in the polynomial, $d$, the maximum number of variables included in a single term.