Inequality for the first Fourier level of a Boolean function

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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 http://arxiv.org/abs/0705.3806), although any answer would be appreciated.

-

1 Answer

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

http://analysisofbooleanfunctions.org/?p=885

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

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 24, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.3, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9304800033569336, "perplexity_flag": "head"}