CS Paper Radar

Three Conjectures on Binary Channels for the Doubly Symmetric Binary Source

Georg Pichler

cs.IT ·submitted 2026-09-23 12:18 UTC · v1
theorycode/datahot direction

Abstract

We settle three conjectures concerning a doubly symmetric binary source $(X,Y)$ with crossover $p$. Consider Markov chains $U - X - Y - V$ with $U,V$ binary, and let $\mathcal{A}$ be the set of rate triples $(I(U;V),I(U;X),I(Y;V))$ attainable with arbitrary binary channels $X\to U$, $Y\to V$, and $\mathcal{B}$ the subset attainable with binary symmetric channels. The averaged BSC conjecture, Conjecture 5.2 of Pichler, Piantanida and Matz (2022), asserts $\operatorname{conv}\mathcal{A}=\operatorname{conv}\mathcal{B}$. We prove this for every $p\in[0,1]$. Two conjectures of Dikshtein, Ordentlich and Shamai (2022) concern the double-sided information bottleneck at $p=0$, where $Y=X$ and the two channels see the same source: their Conjecture 1 identifies the exact maximum of $I(U;V)$ at prescribed rates $I(U;X)$ and $I(Y;V)$, and their Conjecture 2 the exact minimum. We prove both for binary $U,V$: the two extrema are attained by the same pair of Z/S-channels, in opposite orientation for the maximum and in the same orientation for the minimum. The proofs were found with substantial AI assistance, and all three theorems are formalised in Lean 4 with Mathlib, depending only on the standard axioms. The development is available at https://github.com/g-pichler/bsc-averaging . The proof of Conjecture 1 of Dikshtein, Ordentlich and Shamai (2022) contains three certified computations, a polynomial bound, an interval sweep and a polynomial positivity certificate, all of which are checked in Lean.

Closest papers

Nearest neighbours by meaning across the whole index.

The Most Informative Bit and Beyond: A Proof of the Courtade--Kumar Conjecture and Multibit Extensions

cs.IT ·2026-09-22 ·Hessam Mahdavifar, Ahmad Beirami
benchmarktheoryhighly cited similarity 0.75
Abstract

Let \(X=(X_1,\ldots,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)\leq 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\geq8\), 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\geq8\). 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\leq k\leq7\) find that structured codebooks outperform random ones but remain below the coordinate benchmark. This motivates our conjecture that coordinate projections are optimal for \(2\leq k\leq7\).

0.48

A Proof of the Most Informative Boolean Function Conjecture

cs.DS cs.IT ·2026-09-21 ·Zijie Chen, Amin Gohari, Adel Javanmard, Honghao Lin, Vahab Mirrokni +2 more
similarity 0.68
Abstract · Added links to end-to-end lean formalization, a short expository note, and discussion of concurrent work

Let $X$ be uniform on $\{-1,1\}^n$, let $Y$ be obtained by passing its coordinates independently through a binary symmetric channel with crossover probability $p$, and let $g:\{-1,1\}^n\to\{0,1\}$ be a Boolean function. We give a computer-assisted proof of the Courtade--Kumar conjecture $I(g(X);Y)\le1-H_2(p)$, where $H_2$ is binary entropy, with equality attained by dictator functions. The present work builds on the differential-equation method, itself a limiting form of the auxiliary-receiver approach in network information theory using a continuum of degraded receivers. The proof proceeds from a local inequality to a dimension-independent bound on entropy production. Differentiation along the Boolean noise semigroup expresses entropy production as an average of edge costs. The key estimate is therefore an unrestricted Bellman inequality with two mean constraints and two entropy constraints, allowing arbitrary couplings of the edge variables. This paper and its supplement provide the proofs and computational verification records. The document is lengthy because it is designed to be entirely self-contained, deriving all proofs from first principles and reproducing the proofs of cited results. We also give a self-contained expository note explaining the reduction to a low-dimensional inequality and the ideas behind the key lower bounds. The entire proof, including all numerical certificates, has been formally verified in Lean end-to-end, and is available online.

0.45

On the Cardinality of Optimal Representations in the Binary-Source Information Bottleneck

cs.IT cs.LGmath.OC ·2026-10-05 ·Dier Tang, Jun Chen
similarity 0.67
Abstract · 9 pages. Feedback and comments are welcome!

The information bottleneck (IB) seeks a representation $U$ of a source $X$ that retains as much information as possible about a target $Y$, subject to a constraint on $I(U;X)$. A classical argument shows that it suffices to consider representations with at most $|\mathcal{X}|+1$ symbols, and this bound is known to be tight whenever $|\mathcal{X}| \geq 3$. We show that the binary case behaves differently: if $X$ is binary and $Y$ is finite, then for every joint distribution of $(X,Y)$ and every rate constraint, the IB optimum is attained by a binary $U$. Hence the bound $|\mathcal{U}| \leq |\mathcal{X}|+1$ sharpens to $|\mathcal{U}| \leq |\mathcal{X}|$ for binary sources. The proof combines a separating hyperplane argument with the observation that, for a binary source, the ratio of the second derivatives of the two entropy functions involved is concave.

0.16

Proof of the Kahn Saks Conjecture

cs.DM math.CO ·2026-09-25 ·Max Aires
theory similarity 0.63
Abstract · 25 pages

Let $\mathbb{P}(x\prec y)$ be the probability that $x$ precedes $y$ in a uniformly random linear extension of an $n$-element poset $P$, and define the balancing coefficient to be $δ(x,y)=\min(\mathbb{P}(x\prec y),\mathbb{P}(y\prec x))$ with $δ(P)=\max_{x,y}δ(x,y)$. We prove (Theorem 1) that sufficiently large width forces $δ(P)$ to be arbitrarily close to $1/2$, answering a long-standing conjecture of Kahn and Saks. In fact, we prove the stronger result (Theorem 2) that large width forces one of two configurations in our poset: either a nearly uniform order on $k$ vertices, or an almost fixed order on $t$ vertices with one further vertex inserted uniformly among the $t+1$ slots. We also show that, for fixed $k$, the first possibility must occur within any antichain $X$ of size $Ω(n^{2/3})$.

0.48

Counterexamples to the Markovity Conjecture for the Two-Receiver Broadcast Channel

cs.IT ·2026-08-13 ·Yanxiao Liu, Mian Huang
similarity 0.62
Abstract

We present two counterexamples to the \emph{Markovity Conjecture} of Gohari, Liu and Nair (ISIT 2025), which is a structural conjecture concerning the optimizers of the dual functional associated with Marton's inner bound and, if true, would greatly simplify the evaluation of Marton's inner bound. Both counterexamples are ternary-input broadcast channels with strictly positive transition probabilities and use the same nonrectangular $2\times2$ auxiliary structure. In each case, we exhibit an explicit non-Markov construction whose objective value is rigorously larger than that achievable by any construction satisfying the conjectured Markov structure. Both examples are obtained with the assistance of GPT-5.6 Sol and disprove the Markovity Conjecture.

0.04

On the most informative Boolean function under noise

cs.IT math.CO ·2026-11-03 ·Dimiter Kramer, Mert Saglam
similarity 0.62
Abstract · 17 pages, 2 figures

Let $X$ be a uniform random bit string and $Y$ be obtained by flipping each bit of $X$ independently with probability $p$. Let $C$ be a random bit obtained as a function of $Y$. We show that $\mathbf{I}(C:X)\le \mathbf{I}(Y_1:X)$ for all $p\in[0,1]$, which resolves a conjecture posed by Courtade and Kumar in 2013.

0.48

Spatially Coupled MacKay-Neal Codes on Symmetric Markov Noise: A Reduction to BMS Channels

cs.IT ·2026-09-22 ·Kenta Kasai
theory similarity 0.61
Abstract · 15 pages

We prove a capacity criterion for fixed-degree spatially coupled MacKay--Neal codes on additive symmetric Markov noise. The noise bit flips with probability $p$, so the channel has one parameter and capacity $1-h_2(p)$. For every integer $\ell\geq4$ with $3/\ell<1-h_2(p)$, matched finite-window BCJR and sum-product decoding admit code sequences, possibly depending on $p$, with actual rate tending to $3/\ell$ and vanishing average information-bit error. The proof parallels the GEC-to-BEC argument: a conditional-entropy correction transfers BMS fixed-point positivity to the channel with memory. The correction also covers a capacity deficit of the effective BMS channel. A two-state posterior contraction supplies the additional derivative bound needed for threshold saturation. The result uses the cited BMS positivity theorem, with an analytic proof for $\ell\geq33$ and exact interval certificates for $4\leq\ell\leq32$.

0.17

A Sharp Mutual Information Bound for Binary Pairs

cs.IT ·2026-11-02 ·Qianmian Guo
theory similarity 0.61
Abstract

We prove a sharp upper bound on the mutual information between two binary random variables in terms of their distribution-dependent KL contraction coefficient. This resolves the binary-pair conjecture of Anantharam, Gohari, Kamath, and Nair. Equality holds if and only if the variables are independent or form a doubly symmetric binary source. The proof uses supporting tangents of an entropy curve to vary the input distribution and the channel while preserving the contraction coefficient. Together with tensorization and data processing, the result also bounds the mutual information between binary outputs obtained separately from two correlated observation sequences. When the observation pairs are independent copies of a finite-alphabet pair, this bound depends only on the law of one pair and not on the number of observations.

0.24