Hypercontractive Inequality for Pseudo-Boolean Functions of Bounded Fourier Width

A function $f:\{-1,1{\}}^n\to \mathbb{R}$ is called pseudo-Boolean. It is well-known that each pseudo-Boolean function $f$ can be written as $f(x)={\sum }_{I\in \mathcal{F}}\widehat{f}(I){\chi }_I(x),$ where ${\cal F}\subseteq {I:
I\subseteq [n]}$,$[n]={1,2,…,n}$,and$\chi_I(x)=\prod_{i\in I}x_i$and$\hat{f}(I)$arenon-zeroreals\mathrm{.}Thedegreeof$f$is$\max {|I|:\ I\in {\cal F}}$andthewidthof$f$istheminimuminteger$\rho$suchthatevery$i\in [n]$appearsinatmost$\rho$setsin$\cal F$\mathrm{.}For$i\in [n]$,let$$\mathbf{x}$_i$ be a random variable taking values 1 or -1 uniformly and independently from all other variables ${\mathbf{x}}_j$, $j\mathrm{\ne }i\mathrm{.}$ Let $\mathbf{x}=({\mathbf{x}}_1,\mathrm{.}\mathrm{.}\mathrm{.},{\mathbf{x}}_n)$. The $p$-norm of $f$ is $\mathrm{\mid }\mathrm{\mid }f\mathrm{\mid }{\mathrm{\mid }}_p=(\mathbb{E}[\mathrm{\mid }f(\mathbf{x}){\mathrm{\mid }}^p]{)}^{1\mathrm{/}p}$ for any $p\ge 1$. It is well-known that $\mathrm{\mid }\mathrm{\mid }f\mathrm{\mid }{\mathrm{\mid }}_q\ge \mathrm{\mid }\mathrm{\mid }f\mathrm{\mid }{\mathrm{\mid }}_p$ whenever $q>p\ge 1$. However, the higher norm can be bounded by the lower norm times a coefficient not directly depending on $f$: if $f$ is of degree $d$ and $q>p>1$ then $ ||f||_q\le (\frac{q-1}{p-1})^{d/2}||f||_p.$ This inequality is called the Hypercontractive Inequality. We show that one can replace $d$ by $\rho$ in the Hypercontractive Inequality for each $q>p\ge 2$ as follows: $ ||f||_q\le ((2r)!\rho^{r-1})^{1/(2r)}||f||_p,$where$r=\lceil q/2\rceil$\mathrm{.}Forthecase$q=4$and$p=2$, which is important in many applications, we prove a stronger inequality: $\mathrm{\mid }\mathrm{\mid }f\mathrm{\mid }{\mathrm{\mid }}_4\le (2\rho +1{)}^{1\mathrm{/}4}\mathrm{\mid }\mathrm{\mid }f\mathrm{\mid }{\mathrm{\mid }}_2\mathrm{.}$