jensen_shannon_binary_cid_not_subadditive
There exists a binary Markov chain with conditionally identically distributed observations Y, Z given X where the unregularized Jensen-Shannon mutual information strictly violates subadditivity.
Statement
theorem jensen_shannon_binary_cid_not_subadditive : ∃ (pX : Fin 2 → ℝ) (P : Fin 2 → Fin 2 → ℝ), (∀ x, 0 ≤ pX x) ∧ (∑ x, pX x = 1) ∧ (∀ x y, 0 ≤ P x y) ∧ (∀ x, ∑ y, P x y = 1) ∧ 2 * mutual_f_information jensen_shannon_generator (fun x y => pX x * P x y) < mutual_f_information jensen_shannon_generator (fun x (yz : Fin 2 × Fin 2) => pX x * P x yz.1 * P x yz.2)
- Source
- arXiv:2610.21231
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- jensen_shannon_generatorThe f-divergence generator for Jensen-Shannon divergence is f(x) = (1/2) x log x - ((x + 1)/2) log((x + 1)/2).
- mutual_f_informationFor a joint probability mass function p_{XY} on finite sets, the mutual f-information is Ĩ_f(X; Y) = D_f(p_{XY} ‖ p_X p_Y) = Σ_{x,y}…
Read back from the Lean
There exist a probability mass function $pX : \text{Fin } 2 \to \mathbb{R}$ and a transition kernel $P : \text{Fin } 2 \to \text{Fin } 2 \to \mathbb{R}$—meaning that: 1. $0 \le pX(x)$ for all $x \in \text{Fin } 2$, 2. $\sum_{x \in \text{Fin } 2} pX(x) = 1$, 3. $0 \le P(x, y)$ for all $x, y \in \text{Fin } 2$, and 4. $\sum_{y \in \text{Fin } 2} P(x, y) = 1$ for all $x \in \text{Fin } 2$— such that twice the Jensen-Shannon mutual $f$-information of the joint distribution $(x, y) \mapsto pX(x) P(x, y)$ on $\text{Fin } 2 \times \text{Fin } 2$ is strictly less than the Jensen-Shannon mutual $f$-information of the joint distribution $(x, (y_1, y_2)) \mapsto pX(x) P(x, y_1) P(x, y_2)$ on $\text{Fin } 2 \times (\text{Fin } 2 \times \text{Fin } 2)$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The theorem is proved by constructing an explicit counterexample: a binary source X with distribution pX = (0.99, 0.01) and a transition channel P with conditional probabilities P(· | 0) = (0.99, 0.01) and P(· | 1) = (0.7, 0.3). After verifying that pX and P define valid probability distributions, the mutual information expressions are expanded into explicit sums and simplified to an inequality between linear combinations of logarithms. This strict transcendental inequality is then verified numerically by the `num_ineq` decision procedure.
There exist candidate distributions pX on {0, 1} and channel transition matrix P on {0, 1} × {0, 1}.
We instantiate the existential quantifier with explicit witnesses: the prior distribution pX(0) = 99/100, pX(1) = 1/100, and the transition probabilities P(0 | 0) = 99/100, P(1 | 0) = 1/100, P(0 | 1) = 7/10, P(1 | 1) = 3/10. This leaves five obligations: non-negativity and normalization of pX, non-negativity and row normalization of P, and the strict inequality 2 * I_JS(X; Y) < I_JS(X; Y, Z).
refine ⟨fun x => if x = 0 then (99:ℝ)/100 else 1/100, fun x y => if x = 0 then (if y = 0 then (99:ℝ)/100 else 1/100) else (if y = 0 then 7/10 else 3/10), ?_, ?_, ?_, ?_, ?_⟩
The prior probabilities are non-negative: pX(x) ≥ 0 for all x ∈ {0, 1}.
We perform a case exhaustion on x ∈ Fin 2 (covering x = 0 and x = 1) using `fin_cases` and check that 99/100 ≥ 0 and 1/100 ≥ 0 by numerical normalization (`norm_num`).
· intro x; fin_cases x <;> norm_num
The prior probabilities sum to 1: ∑ x, pX(x) = 1.
We expand the sum over the two elements of Fin 2 into pX(0) + pX(1) using `Fin.sum_univ_two`, reducing the goal to 99/100 + 1/100 = 1, which `norm_num` verifies.
uses
Fin.sum_univ_two· simp only [Fin.sum_univ_two]; norm_num
The channel transition probabilities are non-negative: P(x, y) ≥ 0 for all x, y ∈ {0, 1}.
We exhaust all four combinations (x, y) ∈ {0, 1}² using `fin_cases` on both variables and check that each value (99/100, 1/100, 7/10, 3/10) is non-negative via `norm_num`.
· intro x y; fin_cases x <;> fin_cases y <;> norm_num
The transition probabilities from each state sum to 1: ∑ y, P(x, y) = 1 for each x ∈ {0, 1}.
We split into cases on x ∈ Fin 2, expand each sum over y ∈ Fin 2 into the sum of two terms using `Fin.sum_univ_two`, and verify that 99/100 + 1/100 = 1 and 7/10 + 3/10 = 1 using `norm_num`.
uses
Fin.sum_univ_two· intro x; fin_cases x <;> simp only [Fin.sum_univ_two] <;> norm_num
The unregularized Jensen-Shannon mutual information strictly violates subadditivity: 2 * I_JS(X; Y) < I_JS(X; Y, Z). automation
We expand the definitions of mutual f-information (`mutual_f_information`) and the Jensen-Shannon generator (`jensen_shannon_generator`), rewriting the sums over Fin 2 and Fin 2 × Fin 2 into explicit summations via `Fin.sum_univ_two` and `Fintype.sum_prod_type`. The simplifier resolves conditional expressions with `if_true` and `if_false`, and `norm_num` computes all rational arithmetic. This reduces the problem to an explicit numerical inequality between linear combinations of natural logarithms, which is closed by the automated decision procedure `num_ineq`.
uses
Fin.sum_univ_two,Fintype.sum_prod_type,if_true,if_false· simp only [mutual_f_information, jensen_shannon_generator, Fin.sum_univ_two, Fintype.sum_prod_type] simp only [Fin.isValue, if_true, if_false, Fin.reduceEq] norm_num num_ineq
Fin.sum_univ_two- A summation over the two elements of `Fin 2` evaluates to the sum of the terms at 0 and 1: ∑ i, f i = f 0 + f 1.
Fintype.sum_prod_type- A summation over the product of two finite types equals the iterated summation: ∑ x, f x = ∑ x₁, ∑ x₂, f (x₁, x₂).
if_true- An if-then-else expression whose condition is True simplifies to the then-branch: (if True then t else e) = t.
if_false- An if-then-else expression whose condition is False simplifies to the else-branch: (if False then t else e) = e.
- The strict inequality between mutual informations is established by numerical interval arithmetic (`num_ineq`) on an explicit transcendental expression involving logarithms, without an analytical paper-style derivation.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- The unregularized Jensen-Shannon mutual information is not subadditive on binary Markov chains with conditionally identically distributed observations. -/theorem jensen_shannon_binary_cid_not_subadditive : ∃ (pX : Fin 2 → ℝ) (P : Fin 2 → Fin 2 → ℝ), (∀ x, 0 ≤ pX x) ∧ (∑ x, pX x = 1) ∧ (∀ x y, 0 ≤ P x y) ∧ (∀ x, ∑ y, P x y = 1) ∧ 2 * mutual_f_information jensen_shannon_generator (fun x y => pX x * P x y) < mutual_f_information jensen_shannon_generator (fun x (yz : Fin 2 × Fin 2) => pX x * P x yz.1 * P x yz.2) := by refine ⟨fun x => if x = 0 then (99:ℝ)/100 else 1/100, fun x y => if x = 0 then (if y = 0 then (99:ℝ)/100 else 1/100) else (if y = 0 then 7/10 else 3/10), ?_, ?_, ?_, ?_, ?_⟩ · intro x; fin_cases x <;> norm_num · simp only [Fin.sum_univ_two]; norm_num · intro x y; fin_cases x <;> fin_cases y <;> norm_num · intro x; fin_cases x <;> simp only [Fin.sum_univ_two] <;> norm_num · simp only [mutual_f_information, jensen_shannon_generator, Fin.sum_univ_two, Fintype.sum_prod_type] simp only [Fin.isValue, if_true, if_false, Fin.reduceEq] norm_num num_ineq