Three Conjectures on Binary Channels for the Doubly Symmetric Binary Source
Georg Pichler
cs.IT
Sep 23, 2026 · v1
TL;DR
Three information-theory conjectures on doubly symmetric binary sources are formalised in Lean 4 with Mathlib, including certified interval sweeps and polynomial positivity checks.
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.
Problem
Three open conjectures concern binary test channels applied to a doubly symmetric binary source with crossover p: the averaged BSC conjecture of Pichler, Piantanida and Matz, and two double-sided information bottleneck conjectures of Dikshtein, Ordentlich and Shamai at p=0.
Approach
Each extremal problem over pairs of arbitrary binary channels is reduced to inequalities on the two atoms of a bias variable on each side, yielding finite-dimensional statements. A two-point Lagrangian characterises the attainable rate region, and the DSIB extrema are shown to be attained by Z/S-channel pairs. Proofs were found with substantial AI assistance and formalised in Lean 4 with Mathlib, depending only on standard axioms. Certified computations, a polynomial bound, an 88-cell interval sweep, and a polynomial positivity certificate are checked by the Lean kernel via decide+kernel, ring and norm_num.
Results
The averaged BSC conjecture is proved for every p in [0,1], and both DSIB conjectures are proved for binary U,V, with the maximum and minimum of I(U;V) attained by Z/S-channel pairs in opposite and same orientations respectively. All three theorems are formally verified in Lean 4.