OpenFrontiers
Join
← Back to the index
OP-12011OpenProbability

L1L^1 Poincaré constant on the Hamming cube (C11aC_{11a})

L1L^1 Poincaré constant on the Hamming cube: determine C11aC_{11a} or improve its bounds; the repository records π/2≈1.2533\sqrt{\pi/2} \approx 1.2533 (lower) and π/2−0.00013≈1.5707\pi/2 - 0.00013 \approx 1.5707 (upper).

MSC 60E15 · Inequalities; stochastic orderingsMSC 06E30 · Boolean functions

Editorial MSC2020 classification. Original article codes and source evidence are recorded in the literature directory.

Licensed source statementAs of Repository table at commit 2c1968c (2026-09-26); open while the recorded lower and upper bounds differSource & evidence ↓
Read original source ↗ 0Submit progressLean 4 ↓Discussion (0)

Problem statement

C11aC_{11a} is the smallest constant such that, for every n≥1n\ge 1 and every function ff:{-1,1}^n →R\to \mathbb{R}

E∣f(x)−Ef(x)∣ ≤ C11aE∣∇f∣(x),\mathbb{E}\bigl|f(x)-\mathbb{E}f(x)\bigr|\ \le\ C_{11a}\mathbb{E}|\nabla f|(x),

where x=(x1,…,xn)x=(x_{1},\dots,x_{n}) is uniform on {-1,1}^n and

∣∇f∣(x)=(∑j=1n∣Djf(x)∣2)1/2,Djf(x)=f(x)−f(x(j))2,|\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)=(x1,...,xj−1,−xj,xj+1,...,xn).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 L1L^1 Poincaré inequality on the discrete cube.

Lean 4

Not yet attached

No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.

Share a formalization →Verification guide ↗

Background

References (from the repository page)

  • [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 L1L^1 and L2L^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).

Progress & source assessment

Repository table (commit 2c1968c, 26 September 2026): best known lower bound π/2≈1.2533\sqrt{\pi/2} \approx 1.2533; best known upper bound π/2−0.00013≈1.5707\pi/2 - 0.00013 \approx 1.5707. Values marked with an asterisk have minimal verification.

Known upper bounds

Bound Reference Comments
π/2≈1.57080\pi/2 \approx 1.57080 [BELP2008] First proof (non-commutative/CAR algebra). Several later proofs recover the same constant.
π/2−δ\pi/2-\delta for some δ>0\delta>0 [ILvHV2019] First proof that C11aC_{11a} is strictly smaller than π/2\pi/2.
π/2−δ\pi/2-\delta with δ≈0.00013\delta\approx 0.00013 [IS2024] Provides an explicit integral expression for δ\delta and evaluates it numerically (about 1.3×10−41.3\times 10^{-4}).

Known lower bounds

Bound Reference Comments
11 Trivial For n=1n=1, take f(x)=xf(x)=x to get ratio 11.
π/2≈1.25331\sqrt{\pi/2} \approx 1.25331 [Pisier1986], [ILvHV2019] Comes from the sharp Gaussian L1L^1-Poincaré inequality (Pisier).
References
  1. [1]Davis, Damek; Ivanisvili, Paata; Tao, Terence (maintainers). Optimization Constants in Mathematics, github.com/teorth/optimizationproblems (commit 2c1968c, 26 September 2026). — $L^1$ Poincaré constant on the Hamming cube ($C_{11a}$) linkApache-2.0 (repository license); constant pages reproduced with attribution; repository references retained.

Recorded progress

Add yours →

Nothing recorded yet. A pointer to a paper the entry is missing counts.

Machine attempts

0 recorded

Attempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.

No machine attempts recorded.

Sign in to run an attempt. New accounts start with enough credits for ten.

Discussion

0 notes

Notes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.

No notes yet.

Sign in to add a note.