# $L^{p}$ isoperimetric inequalities on the Hamming cube

Let $A \subset \{-1,1\}^{n}$ be a subset of the Hamming cube with cardinality $|A|=2^{n-1}$. Define $w_{A} : \{-1,1\}^{n} \to \mathbb{N}\cup \{0\}$ so that $w_{A}(x)$ to be number of boundary edges to $A$ containing $x$, i.e., $w_{A}(x)$ counts number of edges of $\{-1,1\}^{n}$ with endpoints in $A$ and in the complement of $A$ so that one of the endpoint is $x$. Clearly $w_{A}(x)=0$ if $x$ is in the "strict interior" of $A$, or in the "strict complement" of $A$, and it is nonzero if and only if $x$ is on the "boundary" of $A$. Notice that $w_{A}(x)$ can be nonzero for some $x \notin A$.

The classical edge--isoperimetric inequality on the Hamming cube of Harper implies that $$\frac{1}{2^{n}}\sum_{x \in \{-1,1\}^{n}}w_{A}(x) \geq 1$$ and the constant $1$ on the right hand side is sharp.

My question is what is known about the best possible $C(p)\geq 0$ such that $$\frac{1}{2^{n}}\sum_{x \in \{-1,1\}^{n}}w_{A}^{p/2}(x) \geq C(p), \quad 1\leq p\leq 2$$ for all sets $A \subset \{-1,1\}^{n}$ with cardinality $2^{n-1}$.

• Just a remark: you can ask the same question for $0 < p \leq 2$. Then as $p$ tends to zero the problem degenerates into the vertex-isopermetric inequality, whose minimizers are Hamming balls instead of half-cubes. One can check that half-cubes become better than Hamming balls when $p>p_0(n)$ with $p_0(n)<1$ and $\lim p_0(n)=1$. It is possible that $C(p)=1$ for all $p \geq 1$ ? – Guillaume Aubrun May 17 '17 at 8:36
• @AnthonyQuas Note that raising power is $p/2$ (and not $p$) – Guillaume Aubrun May 17 '17 at 14:12
• @GuillaumeAubrun: thanks - I removed my comment – Anthony Quas May 17 '17 at 14:55
• @GuillaumeAubrun I am not sure about $C(p)=1$ for $p\geq 1$. For $1<p\leq 2$ I can show that $C(p)\geq Z_{p/(p-1)}^{p}$ where $Z_{q}$ is the smallest positive zero of the confluent hypergeometric function $M(-q/2, 1/2, x^{2}/2)$. – Paata Ivanishvili May 17 '17 at 20:05
• For certain values of $n$ and $p<1$ you can beat both the Hamming ball and the half-cube ; for example $n=5$, $p/2=0.43$, and $A$ the set of vertices with a majority of $1$ among the first 3 coordinates. It seems reasonable to conjecture that extremizers will always be obtained as the intersection of the discrete cube with a half-space in $\mathbb{R}^n$. – Guillaume Aubrun May 19 '17 at 8:45

The bound $C(1) \geq \frac{1}{\sqrt{2 \pi}}$ follows from "Bobkov's Inequality" [Bob97], which says that for any $f : \{-1,1\}^n \to [0,1]$ it holds that $\mathcal{U}(\mathbb{E}[f]) \leq \mathbb{E}\sqrt{\mathcal{U}(f)^2 + |\nabla f|^2}$, where $\nabla f$ is the discrete gradient $\nabla f(x) = \left(\frac{f(x_1, \dots, x_{i-1}, 1, x_{i+1}, \dots, x_n) - f(x_1, \dots, x_{i-1}, -1, x_{i+1}, \dots, x_n)}{2}\right)_{i=1\dots n}$ and $\mathcal{U}$ denotes the "Gaussian isoperimetric function" $\phi \circ \overline{\Phi}^{-1}$ (with $\phi$ the Gaussian pdf and $\overline{\Phi}$ the Gaussian complementary cdf). In particular, if $f$ is the $0$-$1$ indicator of a set $A \subseteq \{-1,1\}^n$, then this reduces to $\mathbb{E}_x[\sqrt{w_A(x)}] \geq \mathcal{U}(\text{vol}(A))$, where $\text{vol}(A) = |A|/2^{n}$. Thus in your case where $\text{vol}(A) = 1/2$ we get a lower bound of $\mathcal{U}(1/2) = \frac{1}{\sqrt{2 \pi}}$.

This is sharp up to a factor of $\sqrt{2}$ by virtue of the "Majority" function -- i.e., $A$ being a Hamming ball of radius $n/2$ -- which has $\mathbb{E}_x[\sqrt{w_A(x)}] \sim \frac{1}{\sqrt{\pi}}$. Bobkov remarks on this missing factor of $\sqrt{2}$; presumably $\frac{1}{\sqrt{\pi}}$ is the correct answer but it's not known how to improve $\frac{1}{\sqrt{2\pi}}$ as far as I'm aware.

Given this result, one can get $C(p) \geq \left(\frac{1}{2\pi}\right)^{p/2}$ for any $1 < p < 2$ by monotonicity of $\ell_p$-norms, which is a decent bound but is surely not optimal. Getting the optimal answer in this range is presumably harder than getting the optimal answer for $p = 1$.

By the way, it was Talagrand who first studied the $p = 1$ case; this notion of looking at the average square-root of the number of sensitive coordinates seems to be a pretty good notion of "discrete surface area". Talagrand's original paper [Tal93] proved Bobkov's Inequality (for sets $A$) up to a universal constant factor on the LHS; in particular, he established $C(1)$ is bounded away from $0$ by a univeral constant.

[Bob97] Bobkov, S.G., An isoperimetric inequality on the discrete cube and an elementary proof of the isoperimetric inequality in Gauss space, Ann. Probab. 25, No.1, 206-214 (1997). ZBL0883.60031.

[Tal93] Talagrand, M., Isoperimetry, logarithmic Sobolev inequalities on the discrete cube, and Margulis' graph connectivity theorem, Geom. Funct. Anal. 3, No.3, 295-314 (1993). ZBL0806.46035.

• Thank you. By the way if $f$ is 0-1 indicator of a set $A \subseteq \{-1,1\}^{n}$ then $|\nabla \chi_{A}| = \frac{\sqrt{w_{A}(x)}}{2}$ and Bobkov's inequality gives $C(1)\geq \sqrt{\frac{2}{\pi}}\approx 0.79$. But Hamming balls give $C(1)\leq \frac{2}{\sqrt{\pi}}$ which is worse than $C(1)\leq 1$. So the optimizer cannot be Hamming ball in this particular case – Paata Ivanishvili May 19 '17 at 16:24