The Most Informative Bit and Beyond: A Proof of the Courtade--Kumar Conjecture and Multibit Extensions
Abstract
Let X=(X1,…,Xn) be uniform on the Boolean cube, and let Y be obtained by passing its coordinates independently through a binary symmetric channel with crossover probability p. For a k-bit quantizer Q(X), reporting k input coordinates retains k(1−h2(p)) bits of information, making coordinate projections a natural quantization benchmark. For k=1, this is the Courtade--Kumar conjecture: every Boolean function f satisfies I(f(X);Y)≤ 1−h2(p), with equality for coordinate functions. We prove the conjecture in every dimension and for every crossover probability, without a balance assumption. The proof tracks the information gap relative to a coordinate as the channel correlation varies. After a monotone rearrangement, an entropy-flow identity relates the derivative of this gap to the edge boundary of the associated Boolean decision set. A sharp local entropy comparison, Fourier analysis, and logarithmic Sobolev estimates for pivotal sets imply that any positive gap must grow as the noise decreases, contradicting its nonpositive value at the noiseless endpoint. For k≥8, a coding-theoretic phenomenon emerges. We construct a shortened-Hamming-code quantizer that beats the coordinate benchmark for k=8, and a direct-sum argument extends the failure to every k≥8. Thus structured coding can retain more information than coordinate selection. Exhaustive searches within several structured code families and Monte Carlo searches over random codebooks for 2≤ k≤7 find that structured codebooks outperform random ones but remain below the coordinate benchmark. This motivates our conjecture that coordinate projections are optimal for 2≤ k≤7.
Related
BibTeX
@misc{mahdavifar2026most,
title = {{The Most Informative Bit and Beyond: A Proof of the Courtade--Kumar Conjecture and Multibit Extensions}},
author = {Hessam Mahdavifar and Ahmad Beirami},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.26444},
eprint = {2609.26444},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.26444},
}
RIS
TY - UNPB
TI - The Most Informative Bit and Beyond: A Proof of the Courtade--Kumar Conjecture and Multibit Extensions
AU - Hessam Mahdavifar
AU - Ahmad Beirami
PY - 2026
DA - 2026/09/28
PB - arXiv
DO - 10.48550/arxiv.2609.26444
UR - https://arxiv.org/abs/2609.26444
AB - Let X=(X_1,…,X_n) be uniform on the Boolean cube, and let Y be obtained by passing its coordinates independently through a binary symmetric channel with crossover probability p. For a k-bit quantizer Q(X), reporting k input coordinates retains k(1−h_2(p)) bits of information, making coordinate projections a natural quantization benchmark. For k=1, this is the Courtade--Kumar conjecture: every Boolean function f satisfies I(f(X);Y)≤ 1−h_2(p), with equality for coordinate functions. We prove the conjecture in every dimension and for every crossover probability, without a balance assumption. The proof tracks the information gap relative to a coordinate as the channel correlation varies. After a monotone rearrangement, an entropy-flow identity relates the derivative of this gap to the edge boundary of the associated Boolean decision set. A sharp local entropy comparison, Fourier analysis, and logarithmic Sobolev estimates for pivotal sets imply that any positive gap must grow as the noise decreases, contradicting its nonpositive value at the noiseless endpoint. For k≥8, a coding-theoretic phenomenon emerges. We construct a shortened-Hamming-code quantizer that beats the coordinate benchmark for k=8, and a direct-sum argument extends the failure to every k≥8. Thus structured coding can retain more information than coordinate selection. Exhaustive searches within several structured code families and Monte Carlo searches over random codebooks for 2≤ k≤7 find that structured codebooks outperform random ones but remain below the coordinate benchmark. This motivates our conjecture that coordinate projections are optimal for 2≤ k≤7.
ER -