Parity is the only function with maximal influences

Question

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$

Answer 1

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 function¹ $c \in \{ -1, 1\}$. That is, $f(x) = c \, p(x)$ for all $x$.

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

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