3
$\begingroup$

Let $f:\{-1,1\}^n\to\{-1,1\}$ be a boolean function. Define the influence of the $i$'th coordinate of $f$ as follows: $\operatorname{Inf}_i(f)=\Pr_{x}[f(x)\neq f(\hat x_i)]$ where $x$ is uniformly picked from $\{-1,1\}^n$, and $\hat x_i$ is $x$ with its $i$'th coordinate flipped (e.g., say $x=(1,1,1,1,-1)$, then $\hat x_3=(1,1,-1,1,-1)$).

How do I show that if the influence of a boolean function is $1$ at each coordinate, then the boolean function must be the $\pm$parity function ?

Formally speaking, if a boolean function $f$ holds $\displaystyle\sum_{i=1}^n \operatorname{Inf}_i(f)=n$ then $\displaystyle f(x_1,\ldots,x_n)=\pm\prod_{i=1}^n x_i$

  • 0
    Thanks for the comment - I've edited the question accordingly.2011-09-11

2 Answers 2

2

As noted earlier, the function is either the parity function or its negation. joriki has explained the (more intuitive) idea of flipping coordinates successively. Here's a different approach.

Let $p(x)$ be the parity function on $x$. Consider the function $g(x) = f(x) p(x)$. Flipping any one coordinate of $x$ flips the value of $f(x)$ (by hypothesis), as well as of $p(x)$ (well-known property of parity). Therefore, flipping any coordinate of $x$ leaves $g(x)$ unchanged. Hence $g(x)$ must be a constant function1 $c \in \{ -1, 1\}$. That is, $f(x) = c \, p(x)$ for all $x$.

1Of course, this needs an argument, but hopefully it's easy to see.

2

This is not quite true. The function can be the parity function or its negative. Fix any particular function value (with two choices, $1$ or $-1$) and then for any given argument, flip the inputs one by one; all function values along the way are determined by the influence condition, so the function values for arbitrary arguments are determined.

  • 0
    You are correct, of course - I've forgotten to put the $\pm$ sign. I've edited my post accordingly.2011-09-11