Three Conjectures on Binary Channels for the Doubly Symmetric Binary Source
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 𝒜 be the set of rate triples $(I(U;V),I(U;X),I(Y;V))$ attainable with arbitrary binary channels X→ U, Y→ V, and ℬ the subset attainable with binary symmetric channels. The averaged BSC conjecture, Conjecture 5.2 of Pichler, Piantanida and Matz (2022), asserts conv𝒜=convℬ. We prove this for every p∈[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.
Related
- Finite BSC-Decomposition of Binary-Input Symmetric-Output Channels and Applications to Channel Simulation
- Binary X-rays of doubly stochastic matrices
- Solutions to Three Conjectures and an Open Problem on Binary BCH Codes
- Six Families of Binary Codes Arising from Ding's Conjectures
- Diagnosing the Refuted Mismatched Decoding Converse for Binary-Input Channels
BibTeX
@misc{pichler2026three,
title = {{Three Conjectures on Binary Channels for the Doubly Symmetric Binary Source}},
author = {Georg Pichler},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.27991},
eprint = {2609.27991},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.27991},
}
RIS
TY - UNPB
TI - Three Conjectures on Binary Channels for the Doubly Symmetric Binary Source
AU - Georg Pichler
PY - 2026
DA - 2026/09/23
PB - arXiv
DO - 10.48550/arxiv.2609.27991
UR - https://arxiv.org/abs/2609.27991
AB - 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 𝒜 be the set of rate triples $(I(U;V),I(U;X),I(Y;V))$ attainable with arbitrary binary channels X→ U, Y→ V, and ℬ the subset attainable with binary symmetric channels. The averaged BSC conjecture, Conjecture 5.2 of Pichler, Piantanida and Matz (2022), asserts conv𝒜=convℬ. We prove this for every p∈[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.
ER -