Take the 2-minute tour ×
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.

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|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. –  Tom Sep 11 '11 at 16:30
add comment

2 Answers 2

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|improve this answer
add comment

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|improve this answer
    
You are correct, of course - I've forgotten to put the $\pm$ sign. I've edited my post accordingly. –  Tom Sep 11 '11 at 16:29
add comment

Your Answer

 
discard

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.