Some comments about homework #2

Here are some comments about the questions in the second home-assignment, which I hope you may find interesting. They are listed by question numbers. Enjoy!

1. For a fixed function $f$, the way the $p$ norm of $f$ behaves as a function of $p$ can say a lot about the structure of $f$, as we shall see in the future. In this question we observe a very simple yet useful behavior of the $p$ norm which holds for all functions, namely that it (weakly) increases with $p$ and tends to the $\infty$ norm as $p$ goes to $\infty$. Unlike the triangle inequality for the $p$ norm, which is quite difficult, the monotonicity of the norm has a short and simple proof.
   
   
2. We said in class that the majority function has the highest weight on linear characters out of all 'non-junta-like' Boolean functions. The technique for proving that will come more naturally in the next few weeks, so this question discusses two other interesting extremal properties of the majority function: out of all Boolean valued monotone functions, majority has the highest possible total influence (would you believe that you could prove such results using the very basic techniques that we covered so far? Would you be able to prove this without learning Fourier techniques first?). Also, majority has the largest possible sum of linear coefficients out of all Boolean functions, monotone or not. If you want a slightly higher challenge, prove that majority also has the largest possible sum of absolute values of linear coefficients out of all Boolean valued functions.
   
   
3. In this question you are asked to find a formula for the variation, defined in the previous home assignment, in the Fourier phase (namely, in terms of Fourier coefficients) - this may require some thought. But once you have the formula, note that showing the sub-additivity of the variation, which you were required to do in the previous assignment, now becomes trivial. The other two important properties of the variation, which are stated in sections (b) and (c), also follow easily from the formula. These properties show that the variation of a function $f$ on a set of $T$ coordinates exactly captures how well $f$ can be approximated by a function which is independent of $T$. This means that the variation (and the influence as a special case) really measures in a quantitative way how much a function depends on a set of coordinates.
   
   
4. It is intuitively obvious that a balanced function that depends equally on all of its coordinates cannot be approximated by a junta, a function that only looks at a few coordinates (the requirement for balancedness comes since otherwise the function may be constant, which is not really fair). Here you are required to prove this fact for a symmetric function. Proving this for a transitive function turns out to be more challenging, and if you do you'll get extra credit (say, 15 points).
   
   
5. We already know that the set of characters is exactly the set of multiplicative functions. Also, note that a function $f$ is multiplicative if and only if $f(x)f(y)f(xy)=1$ for all $x$ and $y$, or alternatively, if and only if $\mathbb{E}[f(x)f(y)f(xy)]=1$. But once you write the expectation in terms of the Fourier coefficients of $f$, it becomes relatively easy to show a robust version of the above observation, namely that a Boolean function which is 'mostly' multiplicative must 'almost' be a character. This is a very strong fact, because it enables us to check whether a function is close to a character by just picking a few triples $(x,y,xy)$ and only reading the value of $f$ on these triples. This question may require a bit more steps of derivation than others (but as I hear from Amir, it may need less than many of you actually often use..).