Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$

share|cite|improve this question
(Well, the function can also be the negation of the parity function.) HINT Unroll the definition of influence. What does it mean for influence of a coordinate to be $1$? – Srivatsan Sep 11 '11 at 16:12
Thanks for the comment - I've edited the question accordingly. – User1234 Sep 11 '11 at 16:30
up vote 3 down vote accepted

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.

share|cite|improve this answer

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.

share|cite|improve this answer
You are correct, of course - I've forgotten to put the $\pm$ sign. I've edited my post accordingly. – User1234 Sep 11 '11 at 16:29

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.