16
$\begingroup$

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

$\endgroup$

3 Answers 3

8
$\begingroup$

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.

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

$\endgroup$
7
$\begingroup$

I think it might still be unknown whether the constant can be reduced below $e$. By the Central Limit Theorem, if it can be so reduced, then it can also be reduced below $e$ for functions on Gaussian space. In Remark 5.11 of Janson's book Gaussian Hilbert Spaces, he says that the best possible constant in the inequality $\|f\|_q \leq c(p,q)^k \|f\|_p$ (for $f$ of degree $k$ and $p \leq q$) is only known in case $p = 2$ (in which case it is $\sqrt{q-1}$). In particular, I guess that means the best possible value for $c(1,2)$ was unknown at the time of his writing, 1997. Note that he gives the argument for $c(1,2) = e$ in Remark 5.13. (It's the same argument that is reproduced in my book in the Boolean case.)

Finally, as Janson notes in Remark 5.12, even in case $p = 2$, it's not true that $\sqrt{q-1}^k$ is the best constant that can be put on the right-hand side; it's merely the best constant of the form $C^k$. In particular, when $q$ is an even integer you can slightly sharpen the inequality, by a factor of roughly $k^{1/4}$. (The arguments for this are sketched in the exercises of my book.)

$\endgroup$
0
$\begingroup$

I have an association with classical Statistical Mechanics. You may check Asano contraction. (I am not a true St.Mech.; you may ask here our @Robert Israel, possibly others too).

This is only an association due to the form of the required polynomials. The key words are ferromagnetic models, (generalized!) Ising models, Lee-Yang circle theorem, David Ruelle's papers and monographies(!) (the old classic "Rigorous Statistical Mechanics", and a much newer one), Joseph Slawny's papers, etc. (@Robert made significant contributions to Statistical Mechanics, and he should tell us more--my own active contact with this wonderful branch of mathematics was unfortunately short).

$\endgroup$
4
  • 3
    $\begingroup$ (I don't detect a link.) If there is a specific result related to Asano contraction that you can give that will answer the question, then please provide it. Otherwise this may have to be moved to a comment, as the question of whether it answers the question is being disputed -- thanks. $\endgroup$
    – Todd Trimble
    Oct 14, 2014 at 14:24
  • $\begingroup$ I've extended my answer. Sorry, I don't have exact references. Almost everybody around here has an easy access to the required material. $\endgroup$ Oct 14, 2014 at 16:29
  • 5
    $\begingroup$ There may be some connection between this question and Asano contraction, but at the moment I really don't see it. This seems to be quite a different sort of problem than what's usually considered in statistical mechanics, and I don't know what I can contribute to it. $\endgroup$ Oct 14, 2014 at 16:59
  • $\begingroup$ Thank you, @Robert. A peasant shoots, God carries the bullet. $\endgroup$ Oct 14, 2014 at 18:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.