MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

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

In the study of Boolean functions, the hypercontractive inequality enables one to bound from above the norm of $Tf$ by some norm of $f$, where $T$ is the noise operator depending on the noise parameter. This can be written in terms of the Fourier transform of $f$ as (in a special case of $q=2$):

$\left( \sum\limits_{S \subseteq [n]} (p - 1)^{|S|} \widehat{f}(S)^2 \right)^{1/2} \leq \left( \frac{1}{2^n} \sum\limits_{x \in (0,1)^n} |f(x)|^p \right)^{1/p}$

However, this involves all Fourier levels of $f$. In the application I have in mind, I'm interested only in bounding the norm of the first level of $f$, i.e. restricting the sum on the left to $|S| = 1$. Is it possible to give any inequality of this kind, probably with a different right hand side (but still involving some information about the norm of $f$) and some additional assumptions on $f$? If it's impossible for some trivial reasons, let me know anyway.

Here I'd be mostly interested in matrix-valued Boolean functions (see for example, although any answer would be appreciated.

share|cite|improve this question

Here is some general discussion of the level-1 weight of Boolean functions --

-- including the theorems that:

  1. If f is boolean-valued and all of its degree-1 coefficients are small then the weight at level 1 is not more than $2/\pi$;
  2. If f is boolean-valued and has very small variance $\alpha$ then the weight at level 1 is at most $2 \alpha \log_2(1/\alpha)$. ["Chang's Lemma", or "Talagrand's Lemma"]

For functions that are not boolean-valued, I don't have a lot to say; the main thing I can suggest is taking $p$ in the hypercontractive inequality as you stated it very close to $1$; if it is, say, $1+\epsilon$ then the LHS will have $\widehat{f}(\emptyset)^2$ (which usually you have information about), plus $\epsilon$ times the weight at level 1, plus at most $\epsilon^2$ times the $2$-norm (neglectable if $\epsilon$ is small enough). So this may allow you to "isolate" the level-1 weight after subtracting $\widehat{f}(\emptyset)^2$ and dividing by $\epsilon$.

share|cite|improve this answer

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.