Every $f\colon\{-1,1\}^n\to \mathbb{R}$ can be repsenented as a multilinean polynomial of the form $$f(x\_1,x\_2,\ldots ,x\_n)=\sum \_{S\subseteq [n]} \hat{f}(S)\prod\_{i\in S} x\_i $$ The *degree* of the function is defined to be $\max \{|S|\,:\,\hat{f}(S)\neq0\}$.


Give $\{-1,1\}^n$ the uniform probability measure. Khintchine's inequality says that if $f$ is of the form $(x\_1,x\_2,\ldots ,x\_n)\mapsto a\_1x\_1+\cdots+a\_nx\_n$, then $\|f\|\_2 \le \sqrt 2\|f\|\_1$. 


Theorem 22 here: <http://analysisofbooleanfunctions.org/?p=1472> says that every function of degree at most $k$ satisfies $\|f\|\_2\le e^k\|f\|\_1$.


The example $(x\_1+1)(x\_2+1)\cdots (x\_k+1)$ shows that the constant $e^k$ in this theorem cannot be reduced bellow $\sqrt 2 ^k$.


My question is: What is the minimal $C\_k$, such that every $f\colon \{-1,1\}^n\to \mathbb{R}$ of degree at most $k$ satisfies $\|f\|\_2\le C\_k\|f\|\_1$? In particular, is it true that $C\_k=\sqrt 2^k$? 



What is the minimal $C_k$, such that every $f\colon \{-1,1\}^n\to \mathbb{R}$ of degree at most $k$ satisfies $\|f\|_2\le C_k\|f\|_1$
When $f : \{-1,1\}^{n} \to \mathbb{C}$ is Walsh--Rademacher chaoes of degree $k$, i.e., 
$$
f(x) = \sum\_{1\leq j\_{1}<\ldots<j\_{k}\leq n} a\_{j\_{1}\ldots j\_{k}}x\_{j\_{1}}\cdots x\_{j\_{k}} \quad (\*)
$$
where $x = (x\_{1}, \ldots, x\_{n}) \in \{-1,1\}^{n}$ then one can improve by square root the bound in [Theorem 22](http://www.cs.tau.ac.il/~amnon/Classes/2016-PRG/Analysis-Of-Boolean-Functions.pdf).


Namely, jointly with Tomasz Tkocz, we have obtained the following result



> 
> **Theorem**. For any $f(x) = \sum\_{1\leq j\_{1}<\ldots<j\_{k}\leq n} a\_{j\_{1}\ldots j\_{k}}x\_{j\_{1}}\cdots x\_{j\_{k}}$ we have
>  $$\|f\|\_{2}\leq e^{k/2}\|f\|\_{1}.$$
> 
> 
> 


The argument uses complex hypercontractivity instead of real one. Using Beckner's result in the proof of Hausdorff--Young inequality with sharp constants, one has $\|T\_{i\sqrt{p-1}} h\|\_{q}\leq\|h\|\_{p}$, for any $h :\{-1,1\}^{n} \to \mathbb{C}$, and any $1\leq p \leq q <\infty$, $\frac{1}{p}+\frac{1}{q}=1$. This immediately implies that we have *strong* hypercontractivity for Rademacher chaoses of degree $k$ on the Hamming cube
$$
\left(\sqrt{\frac{p}{q}}\right)^{k}\|f\|\_{q} = \|T\_{\sqrt{\frac{p}{q}}}f\|\_{q}\leq \|f\|\_{p} \quad (\*\*)
$$ 
whenever $q\geq p$, and $p,q$ are dual exponents. Using Holder's inequality one can show 
$$
\|f\|\_{2} \leq \|f\|\_{1} \left(\frac{\|f\|\_{q}}{\|f\|\_{p}}\right)^{\frac{1}{2(1/p-1/q)}}
$$
Finally applying (\*\*), and then taking the limit $p \to 2-$ we obtain the theorem. 


Our starting point in these questions was Pelczinski's conjecture which says that for degree k=2 chaoses we have the sharp estimate $\|f\|\_{2}\leq2\|f\|\_{1}$, and as you can see our theorem gives $e$ instead of $2$ (real hypercontractivity would give $e^{2}>7.3...$). It is also interesting to remark that for degree 1 chaoses (Khinchin case) the sharp bound is $\sqrt{2}$ due to Szarek, however, our theorem gives $\sqrt{e}$ for free.


**UPDATE 9/14/2018**



> 
> I think it might still be unknown whether the constant can be reduced below $e$
> 
> 
> 


With Alexandros Eskenazis we came up with an argument which improves the bound $\|f\|\_{2}\leq e^{k}\|f\|\_{1}$ to $\|f\|\_{2}\leq (2.69075...)^{k}\|f\|\_{1}$ for polynomials $f$ of degree $k$ on the Hamming cube. I suspect one can further improve the bound but then one needs to carefully play with conformal maps. Anyways, here is the proof which in a sense corresponds to "averaging" the previous argument.


*Proof.* Take any $q>2$ and consider the following domain in the complex plane
$$
\Omega := \left\{ z \in \mathbb{C}\, :\, \left|z\pm \frac{q-2}{2(q-1)}\right|\leq \frac{q}{2(q-1)}\right\}. 
$$
Let $p$ be the conjugate exponent to $q$. It follows from complex hypercontractivity that for any $f:\{-1,1\}^{n} \to \mathbb{C}$, $f(x) = \sum\_{S \subset \{1,2,\ldots, n\}} a\_{S} W\_{S}(x)$, where $W\_{S}(x)=\prod\_{j \in S}x\_{j}$, $x=(x\_{1}, \ldots, x\_{n})$ are Walsh functions, we have 
$$
\|T\_{z}f\|\_{q} \leq \|f\|\_{p}
$$
whenever $z \in \Omega$, where $T\_{z}f(x) = \sum\_{S \subset \{1,2,\ldots, n\}} z^{|S|}a\_{S} W\_{S}(x)$. Let $\pi \beta$ be the exterior angle (measured in radians) of the domain $\Omega$ at point $z=i\sqrt{p-1}$. Clearly $\beta = \frac{1}{2}+ \frac{1}{\pi}\arctan\left(\frac{q-2}{2}\right)$. Next, consider the conformal map 
$$
\varphi(z) = \frac{1+\left(\frac{zi\sqrt{q-1}+1}{zi\sqrt{q-1}-1}\right)^{1/2\beta}}{1-\left(\frac{zi\sqrt{q-1}+1}{zi\sqrt{q-1}-1}\right)^{1/2\beta}}.
$$
Notice that $\varphi$ maps conformally the comploment of $\Omega$ onto the complement of the unit disk in $\mathbb{C}$, and it has a linear growth at infinity. Therefore for any polynomial $p(z)$ of degree $k$ on $\Omega$ we see that the map $z \mapsto \frac{p(z)}{\varphi(z)^{k}\|p\|\_{C(\Omega)}}$ is regular at infinity and it is bounded by $1$ on $\partial \Omega$. Therefore by the maximum principle we have $|p(z)|\leq |\varphi(z)|^{k}\|p\|\_{C(\Omega)}$ for all $z \in \Omega^{c}$. In particular this means that 
$$
|p(1)|\leq |\varphi(1)|^{k}\|p\|\_{C(\Omega)} \qquad (\*\*\*)
$$ 


Next, let $V$ be the vector space of all polynomials of degree $k$ on $\Omega$. It is the subspace of $C(\Omega)$. Let $L$ be the linear functional on $V$ which acts as follows: for any $p \in V$, $L(p)=p(1)$. It follows from (\*\*\*) that $|L(p)|\leq |\varphi(1)|^{k}\|p\|\_{C(\Omega)}$. By Hahn--Banach theorem $L$ extends to a bounded functional $\tilde{L} \in C^{\*}(\Omega)$ so that $\|\tilde{L}\|\_{C^{\*}(\Omega)}\leq |\varphi(1)|^{k}$, and $\tilde{L}|\_{V}=L$. The space $C^{\*}(\Omega)$ can be identified to the Banach space of complex Radon measures on $\Omega$ equipped with total vartiation norm, so that $\tilde{L}(g) = \int\_{\Omega} g d\mu$ for all $g \in C(\Omega)$, and $|\mu|(\Omega):=\|\mu\|\_{TV} = \|\tilde{L}\|\_{C^{\*}(\Omega)}\leq |\varphi(1)|^{k}$. 


Now pick any $f:\{-1,1\}^{n} \to \mathbb{C}$ of degree $k$, and consider the polynomial $p(z)=T\_{z}f(x)$. We have 
$$
\left\|f\right\|\_{q} = \left\|\int\_{\Omega}T\_{z}f d\mu(z) \right\|\_{q} \leq \int\_{\Omega} \left\|T\_{z}f \right\|\_{q}d|\mu|(z)\\
 \leq \int\_{\Omega} \left\|f \right\|\_{p}d|\mu|(z) \leq \|\mu\|\_{TV} \|f\|\_{p}\leq |\varphi(1)|^{k} \|f\|\_{p}
$$


for all $q\geq 2$ and the conjugate $p$. Using log-convexity of $L^{p}$ norms we obtain 


$$
\|f\|\_{2} \leq \|f\|\_{1} \left(\frac{\|f\|\_{q}}{\|f\|\_{p}}\right)^{\frac{1}{2(1/p-1/q)}} = \|f\|\_{1} |\varphi(1)|^{\frac{k}{2(1/p-1/q)}}
$$


Now if my calculation is correct we have 
$$
|\varphi(1)|^{\frac{k}{2(1/p-1/q)}} = \left(\frac{1+\cos\left(\frac{\arctan\left(\frac{2\sqrt{q-1}}{q-2}\right)}{1+\frac{2}{\pi}\arctan\left(\frac{q-2}{2}\right)}\right)}{1-\cos\left(\frac{\arctan\left(\frac{2\sqrt{q-1}}{q-2}\right)}{1+\frac{2}{\pi}\arctan\left(\frac{q-2}{2}\right)}\right)}\right)^{\frac{k}{4(1/p-1/q)}},
$$


optimizing the latter quantity over all $q>2$, and using the fact that $p=\frac{q}{q-1}$, we see that the minimal value is attained around the point $q=2.39079...$ which gives the value $(2.69075...)^{k}$. 


