← All papers
First page of Three Conjectures on Binary Channels for the Doubly Symmetric Binary Source

Three Conjectures on Binary Channels for the Doubly Symmetric Binary Source

Georg Pichler

cs.IT Sep 23, 2026 · v1
Three information-theory conjectures on doubly symmetric binary sources are formalised in Lean 4 with Mathlib, including certified interval sweeps and polynomial positivity checks.
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.

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.

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.

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.