Progress on the Courtade-Kumar Conjecture: Optimal High-Noise Entropy Bounds and Generalized Coordinate-wise Mutual Information

Adel Javanmard, David P. Woodruff · 2026

Read Progress on the Courtade-Kumar Conjecture: Optimal High-Noise Entropy Bounds and Generalized Coordinate-wise Mutual Information by Adel Javanmard, David P. Woodruff (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-09679.txt.

Introduction

Adel Javanmard and David P. Woodruff advance a conjecture about noise and information on the Boolean cube. Their 2026 arXiv paper concerns the Courtade-Kumar conjecture. It claims that dictatorship functions maximize the mutual information between a function's output and a noisy copy of its input.

The authors report two advances on the problem. One gives optimal entropy bounds in the high-noise regime. The other develops a generalized coordinate-wise mutual information. The conjecture sits where information theory meets analysis of Boolean functions. Progress on it sharpens tools used across learning theory and coding.

Catalog record

CREATORAdel Javanmard, David P. Woodruff
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE38 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-09679

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Progress on the Courtade-Kumar Conjecture: Optimal High-Noise Entropy Bounds and Generalized Coordinate-wise Mutual Information Adel Javanmard, David P. Woodruff Abstract The Courtade-Kumar conjecture [ 4 ] posits that dictatorship functions maximize the mutual information between the function’s output and a noisy version of its input over the Boolean hypercube. We present two significant advancements related to this conjecture. First, we resolve an open question posed by Courtade and Kumar [ 4 ] , proving that for any Boolean function (regardless of bias), the sum of mutual information between the function’s output and the individual noisy input coordinates is bounded by 1 − H ⁡ ( α ) 1-H(\alpha) , where α \alpha is the noise parameter of the Binary Symmetric Channel. This generalizes their previous result which was restricted to balanced Boolean functions. Second, we advance the study of the main conjecture in the high noise regime. We establish an optimal error bound of O ⁡ ( λ 2 ) O(\lambda^{2}) for the asymptotic entropy expansion, where λ = ( 1 − 2 ​ α ) 2 \lambda=(1-2\alpha)^{2} , improving upon the previous best-known bounds. This refined analysis leads to a sharp, linear Fourier concentration bound for highly informative functions and significantly extends the range of the noise parameter λ \lambda for which the conjecture is proven to hold. Index Terms– Boolean functions, mutual information, Fourier analysis, hypercontractivity, high noise regime, Courtade-Kumar conjecture 1 Introduction The study of Boolean functions under noise is a cornerstone of theoretical computer science and information theory, with deep connections to coding theory, hardness of approximation, and learning theory. A fundamental question in this area concerns the resilience of information transmission when the input to a function is corrupted by noise. Consider the Boolean hypercube \{-1,1\}^{n} . Let X be drawn uniformly from this space. Suppose X is transmitted through a memoryless Binary Symmetric Channel with crossover probability \alpha\in[0,1/2] , denoted \mathrm{BSC}(\alpha) , resulting in the noisy output Y . We are interested in the mutual information I(b(X);Y) for a Boolean function b:\{-1,1\}^{n}\to\{-1,1\} . In their influential work, Courtade and Kumar [ 4 ] conjectured that this mutual information is maximized by the simplest functions, namely the dictatorships (e.g., b(x)=x_{1} ). Conjecture 1 (Courtade-Kumar Conjecture [ 4 ] ) . For any Boolean function b:\{-1,1\}^{n}\to\{-1,1\} , I(b(X);Y)\leq 1-H(\alpha). The quantity 1-H(\alpha) is the capacity of the \mathrm{BSC}(\alpha) . The conjecture suggests that concentrating the function’s dependence on a single coordinate is the optimal strategy for preserving information through noise. Despite significant interest, Conjecture 1 remains open. Progress has been made in specific regimes. Notably, Samorodnitsky [ 8 ] proved the conjecture in the high noise regime, i.e., when \alpha is sufficiently close to 1/2 . This regime corresponds to the noise correlation parameter \rho=1-2\alpha being close to 0. In addition to their main conjecture, Courtade and Kumar proved a related statement concerning the sum of mutual information with individual coordinates. Theorem 1 (Theorem 1 in [ 4 ] ) . If b is a balanced Boolean function ( \mathbb{E}[b]=0 ), \sum_{i=1}^{n}I(b(X);Y_{i})\leq 1-H(\alpha). They posed as Open Question 1 whether this result extends to arbitrary, potentially biased, Boolean functions. Beyond the primary Courtade-Kumar conjecture, several related conjectures have been proposed in [ 6 , 1 ] (see also [ 3 ] ). These works generally posit that dictatorship functions are the maximizers for various functionals of Boolean functions. 1.1 Our Contributions This paper provides two main contributions towards understanding the information-theoretic properties of Boolean functions under noise. 1.1.1 Resolution of Open Question 1 We provide a complete and affirmative resolution to the open question posed by Courtade and Kumar. We prove that Theorem 1 holds for all Boolean functions. Theorem 2 (Generalized Coordinate-wise Bound) . For any Boolean function b:\{-1,1\}^{n}\to\{-1,1\} , \sum_{i=1}^{n}I(b(X);Y_{i})\leq 1-H(\alpha). The proof, presented in Section 2 , involves analyzing the optimization landscape. We show that the objective function, viewed as a function of the squared level-1 Fourier coefficients, is convex. We analyze the extreme points of the feasible region defined by Parseval’s identity and bounds on Fourier coefficients. The proof requires establishing a non-trivial inequality involving derivatives of the mutual information expression with respect to \rho . A key distinction from the proof strategy in [ 4 , Theorem 1] is our demonstration that the objective function is maximized by Boolean functions that are monotone in each coordinate (defined via a 1-d compression operator). Using this structure we can impose tighter constraints on the feasible set which allows us to generalize the result of [ 4 , Theorem 1] to all Boolean functions. 1.1.2 Optimal Entropy Bounds in High Noise We significantly refine the analysis of Conjecture 1 in the high noise regime. We introduce the noise parameter \lambda=\rho^{2}=(1-2\alpha)^{2} , which is small in this regime. The approach initiated by [ 8 ] relies on an asymptotic expansion of the entropy of the noisy function, \mathrm{Ent}(T_{\alpha}f) , where T_{\alpha} is the noise operator corresponding to \mathrm{BSC}(\alpha) , defined as defined as: T_{\alpha}f(x)=E(f(Y)\mid X=x)\,, (1) where f is defined on the hypercube \{-1,1\}^{n} . Note that T_{\alpha} is a linear mapping and can be expressed as (T_{\alpha}f)(x)=\sum_{y\in\{0,1\}^{n}}\alpha^{d(x,y)}(1-\alpha)^{n-d(x,y)}f(y), where d(\cdot,\cdot) is the Hamming distance. Previous work established the following bound for any nonnegative non-zero function f (normalized without loss of generality to satisfy \mathbb{E}[f]=1 ): \mathrm{Ent}(T_{\alpha}f)\leq\left(\frac{L_{1}(f)}{2\ln 2}\right)\cdot\lambda+E(\lambda), where L_{1}(f) is the level-1 Fourier energy, given by L_{1}(f)=\sum_{i\in[n]}\hat{f}(\{i\})^{2} , and E(\lambda)=O(\lambda^{4/3}) [ 8 ] . Our next result improves this bound to O(\lambda^{2}) and proves its optimality (recall that \lambda\in[0,1] .) While the rate O(\lambda^{2}) is anticipated to be the correct asymptotic behavior (as it matches the expansion for the dictatorship function), rigorously establishing this upper bound for general functions requires delicate handling of the higher-order terms. Theorem 3 (Optimal Asymptotic Entropy Bound) . For any bounded non-negative function f with \mathbb{E}[f]=1 : \mathrm{Ent}(T_{\alpha}f)\leq\left(\frac{L_{1}(f)}{2\ln 2}\right)\cdot\lambda+O(\lambda^{2}). The proof, detailed in Section 3 , relies on a direct Taylor expansion approach combined with rigorous moment bounds derived using hypercontractivity. Crucially, we employ a careful application of the Minkowski inequality over the Fourier decomposition to establish the necessary higher-moment bounds. The optimality of this bound is demonstrated by the fact that the O(\lambda^{2}) error rate is tight for Boolean dictatorship functions. This optimal error bound has profound implications for the structure of highly informative functions. Theorem 4 (Linear Fourier Concentration) . If a Boolean function f (with bounded bias) achieves near-maximal mutual information, I(f(X);Y)\geq 1-H(\alpha) , then \sum_{|S|\geq 2}\hat{f}(S)^{2}=O(\lambda). This linear concentration bound (improving the prior bound of O(\lambda^{1/3}) from [ 8 ] ) is the tightest possible within this framework. It confirms that functions maximizing information must concentrate their Fourier mass on level 1. Consequently, this allows us to significantly extend the range of the noise parameter \lambda for which the Courtade-Kumar conjecture is proven to hold. We show there exists a threshold \delta_{opt}>0 such that the conjecture holds for all \lambda<\delta_{opt} , and this threshold is strictly larger than that established in [ 8 ] . We formalize it in the next theorem. Theorem 5 (Extended Range for the Conjecture) . There exists an absolute constant \delta_{opt}>0 such that if the noise parameter \lambda\leq\delta_{opt} , the Courtade-Kumar conjecture holds. Furthermore, \delta_{opt} is strictly larger than the threshold

Read the complete text