The $L^1$ Poincaré constant on the Hamming cube
Description of constant
$C_{11a}$ is the smallest constant such that, for every $n\ge 1$ and every function $f$:{-1,1}^n $\to \mathbb{R}$
\[\mathbb{E}\bigl|f(x)-\mathbb{E}f(x)\bigr|\ \le\ C_{11a}\mathbb{E}|\nabla f|(x),\]where $x=(x_{1},\dots,x_{n})$ is uniform on {-1,1}^n and
\[|\nabla f|(x)=\Bigl(\sum_{j=1}^n |D_{j} f(x)|^2\Bigr)^{1/2},\qquad D_{j} f(x)=\frac{f(x)-f(x^{(j)})}{2},\]with $x^{(j)}=(x_{1},…,x_{j-1},-x_{j},x_{j+1},…,x_{n}).$
This is sometimes described as the (dimension-free) Cheeger constant appearing in the $L^1$ Poincaré inequality on the discrete cube.
Known upper bounds
| Bound | Reference | Comments |
|---|---|---|
| $\pi/2 \approx 1.57080$ | [BELP2008] | First proof (non-commutative/CAR algebra). Several later proofs recover the same constant. |
| $\pi/2-\delta$ for some $\delta>0$ | [ILvHV2019] | First proof that $C_{11a}$ is strictly smaller than $\pi/2$. |
| $\pi/2-\delta$ with $\delta\approx 0.00013$ | [IS2024] | Provides an explicit integral expression for $\delta$ and evaluates it numerically (about $1.3\times 10^{-4}$). |
Known lower bounds
| Bound | Reference | Comments |
|---|---|---|
| $1$ | Trivial | For $n=1$, take $f(x)=x$ to get ratio $1$. |
| $\sqrt{\pi/2} \approx 1.25331$ | [Pisier1986], [ILvHV2019] | Comes from the sharp Gaussian $L^1$-Poincaré inequality (Pisier). |
Additional comments and links
- It remains open whether $C_{11a}$ equals $\sqrt{\pi/2}$.
- arXiv:1811.05584, arXiv:2407.04835.
References
- [BELP2008] Ben Efraim, L.; Lust-Piquard, F. Poincaré type inequalities on the discrete cube and in the CAR algebra. Probab. Theory Related Fields 141 (2008), no. 3–4, 569–602.
- [ILvHV2019] Ivanisvili, P.; Li, D.; van Handel, R.; Volberg, A. Improving constant in end-point Poincaré inequality on Hamming cube. arXiv:1811.05584 (2018/2019).
- [IS2024] Ivanisvili, P.; Stone, Y. Sharpening the gap between $L^1$ and $L^2$ norms. arXiv:2407.04835 (2024).
- [Pisier1986] Pisier, G. Probabilistic methods in the geometry of Banach spaces. In: Probability and Analysis (Varenna, 1985), Lecture Notes in Math. 1206, Springer, Berlin (1986).