# Given $f \in \mathbb{Z}_2[x_1, …, x_n]$, are there properties of $f$ which can be used to bound $\mathbb{E}_{i \in [n]}|gap(f) - gap(f + x_i)$|?

Let $f \in \mathbb{Z}_2[x_1, ..., x_n]$ be arbitrary. We define $gap(f) = |f^{-1}(0)| - |f^{-1}(1)|$. I want to understand, as a function of any properties of $f$ you find relevant (number of terms, sparsity of variable occurrence, etc.), upper bounds on the the quantity

$\mathbb{E}_{i \in [n]} |gap(f) - gap(f + x_i)|.$

Doing a little bit of manipulation, I can do at least something, but it isn't as strong as I'd like. We define $X^{(i)}_{a, b} = \{ x \mid f(x) = a \wedge x_i = b \}.$ Note then that

$f^{-1}(a) = X^{(i)}_{a, 0} \oplus X^{(i)}_{a, 1}$

$(f + x_i)^{-1}(0) = X^{(i)}_{0, 0} \oplus X^{(i)}_{1, 1}$

$(f + x_i)^{-1}(1) = X^{(i)}_{1, 0} \oplus X^{(i)}_{0, 1}$

and thus that

$gap(f) - gap(f + x_i) = |X^{(i)}_{0, 0}| + |X^{(i)}_{0, 1}| - |X^{(i)}_{1, 0}| - |X^{(i)}_{1, 1}| -|X^{(i)}_{0, 0}| - |X^{(i)}_{1, 1}| +|X^{(i)}_{1, 0}| + |X^{(i)}_{0, 1}| = 2|X^{(i)}_{0, 1}| - 2|X^{(i)}_{1, 1}|$

which is two times the gap of $f$ restricted to inputs where $x_i = 1$. Rewriting this further in terms of the number of zeroes of this restricted $f$, one can use Schwartz-Zippel to get a bound, but it is hardly informative. This problem is a toy version of something which would yield interesting results in quantum circuits: it is a step towards computing the average sensitivity of quantum circuits. As such, if one can find an infinite family of polynomials which bounds this quantity above, say, $\sqrt{s}$, where $s$ is the number of terms in the polynomial, this would be a very interesting result in this respect. For more information on how this relates to quantum circuits, see this paper.