OpenFrontiers
Join
← Back to the index
OP-12042OpenControl and information theory

Constant term of one-shot channel simulation (C32C_{32})

Constant term of one-shot channel simulation: determine C32C_{32} or improve its bounds; the repository records −log⁡2log⁡2e≈−0.53-\log_2 \log_2 e \approx -0.53 (lower) and ∑k=1∞2−k−1klog⁡2k−log⁡2log⁡2e≈0.76\sum_{k=1}^{\infty}2^{-k-1}k\log_{2}k-\log_{2}\log_{2}e \approx 0.76 (upper).

MSC 94A15 · Information theory (general)

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

The constant term of one-shot channel simulation [HJMR07], [BG14], [LEG18], [Li25] is given as (we use the definition in [Li25])

C32=limsupt→∞(sup⁡pX,Y:I(X;Y)=tinf⁡pS∣X,Y:I(X;S)=0H(Y∣S)−t−log⁡2t),C_{32}=\mathrm{limsup}_{t\to\infty}(\sup_{p_{X,Y}: I(X;Y)=t} \inf_{p_{S|X,Y}: I(X;S)=0}H(Y|S)-t-\log_{2}t),

where H(Y∣S)=H(Y,S)−H(S)H(Y\lvert S)=H(Y,S)-H(S) is the conditional entropy (in bits), and I(X;Y)=H(X)+H(Y)−H(X,Y)I(X;Y)=H(X)+H(Y)-H(X,Y) is the mutual information (in bits). The supremum and infimum are over arbitrary finite discrete joint probability distributions pX,Yp_{X,Y} with I(X;Y)=tI(X;Y)=t and finite discrete conditional distributions pS∣X,Yp_{S\lvert X,Y} with I(X;S)=0I(X;S)=0, respectively.

Equivalently, it is the smallest (i.e., infimum of) α∈R\alpha\in\mathbb{R} satisfying that there exists β>0\beta>0 such that for every jointly-distributed random variables X,YX,Y with finite support, we can construct a random variable SS with finite support (jointly-distributed with X,YX,Y, possibly after extending the probability space) with I(X;S)=0I(X;S)=0 and H(Y∣S)≤I(X;Y)+log⁡2(I(X;Y)+β)+αH(Y\lvert S)\le I(X;Y)+\log_{2}(I(X;Y)+\beta)+\alpha [LEG18], [Li25].

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 bound −1≤C32<3.871-1\le C_{32} <3.871 was given in [LEG18], where the following result (called "strong functional representation lemma") was shown: for every (not necessarily discrete) random variables X,YX,Y, there exists a (not necessarily discrete) random variable SS such that I(X;S)=H(Y∣X,S)=0I(X;S)=H(Y\lvert X,S)=0 and H(Y∣S)≤I(X;Y)+log⁡(I(X;Y)+1)+3.871H(Y\lvert S)\le I(X;Y)+\log(I(X;Y)+1)+3.871.

  • It is conjectured that C32=−log⁡2log⁡2eC_{32}=-\log_{2}\log_{2}e [Li25].

  • A bound on C32C_{32} would have applications in communication complexity [HJMR07],[BG14], distributed channel simulation [FT23],[Li24a], lossy compression [LEG18],[LHB22], rate-distortion-perception trade-off [TW21], and privacy-utility trade-off [ZOS23].

References (from the repository page)

  • [BG14] Mark Braverman and Ankit Garg, Public vs private coin in bounded-round information, International Colloquium on Automata, Languages, and Programming, Springer, 2014, pp. 502-513.
  • [FT23] Gergely Flamich and Lucas Theis, Adaptive greedy rejection sampling, 2023 IEEE International Symposium on Information Theory (ISIT), IEEE, 2023, pp. 454-459.
  • [HJMR07] Prahladh Harsha, Rahul Jain, David McAllester, and Jaikumar Radhakrishnan, The communication complexity of correlation, Twenty-Second Annual IEEE Conference on Computational Complexity (CCC'07), IEEE, 2007, pp. 10-23.
  • [HJMR10] Prahladh Harsha, Rahul Jain, David McAllester, and Jaikumar Radhakrishnan, The communication complexity of correlation, IEEE Transactions on Information Theory 56 (2010), no. 1, 438-449.
  • [LA21] Cheuk Ting Li and Venkat Anantharam, A unified framework for one-shot achievability via the Poisson matching lemma, IEEE Transactions on Information Theory 67 (2021), no. 5, 2624-2651.
  • [LEG18] Cheuk Ting Li and Abbas El Gamal, Strong functional representation lemma and applications to coding theorems, IEEE Transactions on Information Theory 64 (2018), no. 11, 6967-6978.
  • [LHB22] Eric Lei, Hamed Hassani, and Shirin Saeedi Bidokhti, Neural estimation of the rate-distortion function with applications to operational source coding, IEEE Journal on Selected Areas in Information Theory 3 (2022), no. 4, 674-686.
  • [Li24a] Cheuk Ting Li, Channel simulation: Theory and applications to lossy compression and differential privacy, Foundations and Trends in Communications and Information Theory 21 (2024), no. 6, 847-1106.
  • [Li24b] Cheuk Ting Li, Pointwise redundancy in one-shot lossy compression via Poisson functional representation, International Zurich Seminar on Information and Communication (IZS 2024), 2024.
  • [Li25] Cheuk Ting Li, Discrete layered entropy, conditional compression and a tighter strong functional representation lemma, 2025 IEEE International Symposium on Information Theory (ISIT), 2025. Full version: arXiv preprint arXiv:2501.13736.
  • [TW21] Lucas Theis and Aaron B Wagner, A coding theorem for the rate-distortion-perception function, Neural Compression: From Information Theory to Applications-Workshop@ ICLR 2021, 2021.
  • [ZOS23] Amirreza Zamani, Tobias J Oechtering, and Mikael Skoglund, On the privacy-utility trade-off with and without direct access to the private data, IEEE Transactions on Information Theory 70 (2023), no. 3, 2177-2200.

Progress & source assessment

Repository table (commit 2c1968c, 26 September 2026): best known lower bound −log⁡2log⁡2e≈−0.53-\log_2 \log_2 e \approx -0.53; best known upper bound ∑k=1∞2−k−1klog⁡2k−log⁡2log⁡2e≈0.76\sum_{k=1}^{\infty}2^{-k-1}k\log_{2}k-\log_{2}\log_{2}e \approx 0.76. Values marked with an asterisk have minimal verification.

Known upper bounds

Bound Reference Comments
<∞<\infty [HJMR07], [HJMR10], [BG14]
3.8713.871 [LEG18] Usually reported as 4.
3.7323.732 [LA21]
3.453.45 [FT23]
22 [Li24b], [Li24a]
∑k=1∞2−k−1klog⁡2k−log⁡2log⁡2e≈0.76\sum_{k=1}^{\infty}2^{-k-1}k\log_{2}k-\log_{2}\log_{2}e \approx 0.76 [Li25]

Known lower bounds

Bound Reference Comments
>−∞>-\infty [BG14]
−1-1 [LEG18]
−log⁡2log⁡2e≈−0.53-\log_{2}\log_{2}e\approx-0.53 [Li25]
References
  1. [1]Davis, Damek; Ivanisvili, Paata; Tao, Terence (maintainers). Optimization Constants in Mathematics, github.com/teorth/optimizationproblems (commit 2c1968c, 26 September 2026). — Constant term of one-shot channel simulation ($C_{32}$) 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.