OpenFrontiers
Join
← Back to the index
OP-12025OpenProbability

KLS constant for log-concave probability measures (C20cC_{20c})

KLS constant for log-concave probability measures: determine C20cC_{20c} or improve its bounds; the repository records π/2≈1.25331\sqrt{\pi/2} \approx 1.25331 (lower) and ∞\infty (upper).

MSC 52A23 · Asymptotic theory of convex bodiesMSC 60E15 · Inequalities; stochastic orderings

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

C20cC_{20c} is the KLS constant (Kannan–Lovász–Simonovits constant) for log-concave measures. It is defined as

C20c:=sup⁡n≥1ψn,C_{20c} := \sup_{n\ge 1} \psi_n,

where ψn\psi_n is the worst-case inverse Cheeger (isoperimetric) constant among isotropic log-concave probability measures on Rn\mathbb R^n.

More precisely, let μ\mu be a log-concave probability measure on Rn\mathbb R^n (i.e. μ\mu has density ρ(x)=e−V(x)\rho(x)=e^{-V(x)} for some convex V:Rn→R∪{+∞}V:\mathbb R^n\to\mathbb R\cup\{+\infty\}). For a Borel set A⊂RnA\subset\mathbb R^n, define the (outer) Minkowski boundary measure

μ+(A):=lim inf⁡ε→0+μ(Aε)−μ(A)ε,Aε:={x∈Rn:dist⁡(x,A)≤ε}.\mu^+(A) := \liminf_{\varepsilon\to 0^+} \frac{\mu(A_\varepsilon)-\mu(A)}{\varepsilon}, \qquad A_\varepsilon := \{x\in\mathbb R^n:\operatorname{dist}(x,A)\le \varepsilon\}.

The Cheeger constant (isoperimetric coefficient) of μ\mu is

hμ:=inf⁡Aμ+(A)min⁡(μ(A),1−μ(A)),h_\mu := \inf_A \frac{\mu^+(A)}{\min(\mu(A),1-\mu(A))},

and the corresponding inverse Cheeger constant is

ψμ:=1hμ.\psi_\mu := \frac{1}{h_\mu}.

We say that μ\mu is isotropic if it has barycenter 00 and covariance matrix Cov(μ)=In\mathrm{Cov}(\mu)=I_n. One then defines

ψn:=sup⁡{ψμ:μ is an isotropic log-concave probability measure on Rn}.\psi_n := \sup\{\psi_\mu : \mu \text{ is an isotropic log-concave probability measure on }\mathbb R^n\}.

The KLS conjecture asserts that C20c<∞C_{20c}<\infty, i.e. that ψn=O(1)\psi_n=O(1) uniformly in nn (and, in a stronger form, that the infimum defining hμh_\mu is attained up to constants by half-spaces).

It is often convenient to work with the Poincaré (spectral gap) constant CP(μ)C_P(\mu), defined as the smallest constant such that

Varμ(f)≤CP(μ)∫∣∇f∣2 dμ\mathrm{Var}_\mu(f)\le C_P(\mu)\int |\nabla f|^2\,d\mu

for all smooth enough ff. For log-concave measures, CP(μ)C_P(\mu) is equivalent up to universal factors to ψμ2\psi_\mu^2; for instance one has

1π ψμ2 ≤ CP(μ) ≤ 4 ψμ2.\frac{1}{\pi}\,\psi_\mu^2 \ \le\ C_P(\mu)\ \le\ 4\,\psi_\mu^2.

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

  • The KLS conjecture is central in asymptotic convex geometry, high-dimensional probability, and sampling algorithms for log-concave distributions. In particular, a dimension-free bound ψn=O(1)\psi_n=O(1) would imply near-optimal mixing bounds (up to polylog factors) for natural random walks such as the ball walk on isotropic convex bodies starting from a warm start.

  • The KLS constant is closely related to the thin-shell constant σn\sigma_n (see also C20aC_{20a}): very roughly, stochastic localization shows that ψn\psi_n and σn\sigma_n control one another up to logarithmic factors (so that the two problems are equivalent “up to logs”).

  • A useful survey is [LV2018].

References (from the repository page)

  • [Che2021] Yuansi Chen, An almost constant lower bound of the isoperimetric coefficient in the KLS conjecture, Geom. Funct. Anal. 31 (2021), no. 1, 34–61.

  • [JLV2022] Arun Jambulapati, Yin Tat Lee, Santosh S. Vempala, A slightly improved bound for the KLS constant, preprint (2022). arXiv:2208.11644.

  • [K2023] Bo’az Klartag, Logarithmic bounds for isoperimetry and slices of convex sets, Ars Inveniendi Analytica (2023), Paper No. 4. arXiv:2303.14938.

  • [KLS1995] Ravi Kannan, László Lovász, Miklós Simonovits, Isoperimetric problems for convex bodies and a localization lemma, Discrete Comput. Geom. 13 (1995), no. 3–4, 541–560.

  • [KL2022] Bo’az Klartag, Jean Lehec, Bourgain’s slicing problem and KLS isoperimetry up to polylog, Geom. Funct. Anal. 32 (2022), no. 5, 1134–1159. Preprint: arXiv:2203.15551.

  • [LV2018] Yin Tat Lee, Santosh S. Vempala, The Kannan–Lovász–Simonovits conjecture, preprint (2018). arXiv:1807.03465.

  • [LV2024] Yin Tat Lee, Santosh S. Vempala, Eldan’s stochastic localization and the KLS hyperplane conjecture: an improved lower bound for expansion, Annals of Mathematics 199 (2024), no. 1, 1–104. (Conference version: FOCS 2017.)

Progress & source assessment

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

Known upper bounds

Since a dimension-free upper bound is not known, bounds are stated for ψn\psi_n as a function of nn.

Bound Reference Comments
ψn≤Cn\psi_n \le C\sqrt{n} [KLS1995] First general polynomial bound (via localization lemma); more generally ψμ≤Tr(Cov(μ))\psi_\mu \le \sqrt{\mathrm{Tr}(\mathrm{Cov}(\mu))}.
ψn≤Cn1/4\psi_n \le C n^{1/4} [LV2024] Improves the best previous polynomial exponent; based on stochastic localization. (Originally appeared in FOCS 2017.)
ψn≤exp⁡(Clog⁡n log⁡log⁡n)\psi_n \le \exp\big(C\sqrt{\log n}\,\log\log n\big) [Che2021] First subpolynomial bound (equivalently, ψn=no(1)\psi_n=n^{o(1)}).
ψn≤C(log⁡n)5\psi_n \le C(\log n)^5 [KL2022] First polylogarithmic bound.
ψn≤C(log⁡n)3.2226…\psi_n \le C(\log n)^{3.2226\ldots} [JLV2022] Improves the polylog exponent.
ψn≤C(log⁡n)3.082…\psi_n \le C(\log n)^{3.082\ldots} [K2023] Lehec (personal communication), as reported in [K2023].
ψn≤Clog⁡n\psi_n \le C\sqrt{\log n} [K2023] Current best general bound (Theorem 1.2 of [K2023]).

Known lower bounds

Bound Reference Comments
π/2≈1.25331\sqrt{\pi/2} \approx 1.25331 Classical For the standard Gaussian measure, isoperimetric minimizers are half-spaces and hγ=2/πh_\gamma=\sqrt{2/\pi}, hence ψγ=π/2\psi_\gamma=\sqrt{\pi/2}.
References
  1. [1]Davis, Damek; Ivanisvili, Paata; Tao, Terence (maintainers). Optimization Constants in Mathematics, github.com/teorth/optimizationproblems (commit 2c1968c, 26 September 2026). — KLS constant for log-concave probability measures ($C_{20c}$) 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.