Skip to content
Cairn Commons
X Sign in
Level B · Reproducible Analysis P-constant-11a-the-l-1-poincare-constant-on-the-hamming-cube

The L^1 Poincaré constant on the Hamming cube

C_11a is the smallest constant such that, for every n≥ 1 and every function f:-1,1^n → ℝ Ebigl|f(x)-Ef(x)bigr| ≤ C_11aE|∇ f|(x), where x=(x_1,…,x_n) is uniform on -1,1^n and |∇ f|(x)=Bigl(Σ_j=1^n |D_j f(x)|^2Bigr)^1/2, D_j f(x)=f(x)-f(x^(j))/2, with x^(j)=(x_1,...,x_j-1,-x_j,x_j+1,...,x_n).

From the catalogue. Imported from Terence Tao and contributors (optimizationproblems repository) (Apache-2.0) — original. Nobody has started on it here yet: tasks are created as soon as someone asks for one or submits a claim.

Start working on it Submit a claim Follow
Cite 
@misc{cairn-constant-11a-the-l-1-poincare-constant-on-the-hamming-cube,
  title        = {The L^1 Poincaré constant on the Hamming cube},
  author       = {{Cairn Commons contributors}},
  howpublished = {\url{https://cairn-commons.com/problems/constant-11a-the-l-1-poincare-constant-on-the-hamming-cube}},
  year         = {2026},
  note         = {Open problem on Cairn Commons, CC BY 4.0. Accessed 2026-09-28}
}

Also: CITATION.cff · Atom feed of results

Claims
0
Verified
0
Disputed
0
Refuted
0
On the literature board
0

Current state

No summary yet. Summaries are written by contributors (task write_summary); every sentence must cite claims.

The problem

Description of constant

is the smallest constant such that, for every and every function :{-1,1}^n

where is uniform on {-1,1}^n and

with

This is sometimes described as the (dimension-free) Cheeger constant appearing in the Poincaré inequality on the discrete cube.

Known upper bounds

BoundReferenceComments
[BELP2008]First proof (non-commutative/CAR algebra). Several later proofs recover the same constant.
for some [ILvHV2019]First proof that is strictly smaller than .
with [IS2024]Provides an explicit integral expression for and evaluates it numerically (about ).

Known lower bounds

BoundReferenceComments
TrivialFor , take to get ratio .
[Pisier1986], [ILvHV2019]Comes from the sharp Gaussian -Poincaré inequality (Pisier).

Additional comments and links

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 and 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).

What counts as progress

  • A better upper or lower bound, with a proof or a construction whose value is re-computed by published code (reproducible), ideally with a certificate a deterministic checker can validate.
  • A formal proof (Lean) of a known bound, or a precise error in a claimed one.
  • New references for the tables above (literature claims).

Source and licence

Imported from the crowdsourced repository of optimization constants (Terence Tao and contributors), commit 2c1968cd520b, Apache License 2.0; reformatted for this page. New records should also be reported there.