/- Copyright 2026 The Formal Conjectures Authors. Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at https://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. -/ module public import FormalConjecturesUtil

The Courtade–Kumar (most informative Boolean function) conjecture

Let $X$ be uniform on the Boolean cube ${0,1}^n$. Independently of $X$, let the coordinates of $Z$ be i.i.d. Bernoulli random variables with parameter $p \in [0, 1]$, and put $Y = X \oplus Z$, so that $Y$ is the output of $n$ independent binary symmetric channels with crossover probability $p$ on input $X$. The Courtade–Kumar conjecture asserts that for every Boolean function $f : {0,1}^n \to {0,1}$,

$I(f(X); Y) \le 1 - h(p)$,

where mutual information and binary entropy are measured in bits.

The usual restriction to $p \in [0, 1/2]$ is equivalent to the range used here. For $p > 1/2$, complementing every output bit replaces $Z$ by its bitwise complement, which is i.i.d. Bernoulli($1 - p$) noise still independent of $X$; this bijective relabelling of the output preserves $I(f(X); Y)$, and $h(1 - p) = h(p)$.

This file contains two formulations:

    CourtadeKumar.courtade_kumar is the elementary finite-sum statement used by the external Lean proof and its comparator check. Its definitions and statement are retained unchanged.

    CourtadeKumar.variants.courtade_kumar_random_variable is the random-variable formulation. Its product-law hypothesis specifies a uniform input and independent i.i.d. Bernoulli channel noise, and its conclusion is about the mutual information of the actual random variables.

CourtadeKumar.courtade_kumar_iff_random_variable proves that the two formulations are equivalent, without using either research statement. Shannon entropy and mutual information of finite-valued random variables are defined in FormalConjecturesForMathlib.InformationTheory.FiniteEntropy.

For $n \ge 1$, coordinate dictators attain the bound: $I(X_i; Y) = I(X_i; Y_i) = 1 - h(p)$, since the other output coordinates are independent of $(X_i, Y_i)$. The test mutualInfo_dictator checks $n = 1$.

References:

    [CK14] T. A. Courtade and G. R. Kumar, Which Boolean functions maximize mutual information on noisy inputs?, IEEE Trans. Inf. Theory 60 (2014), no. 8, 4515–4525.

Independent work on the conjecture from September 2026, in alphabetical order:

    [CGJLMNW26] Z. Chen, A. Gohari, A. Javanmard, H. Lin, V. Mirrokni, C. Nair, D. P. Woodruff, A Proof of the Most Informative Boolean Function Conjecture, arXiv:2609.24931. A Lean 4 formalisation of the proof is at https://github.com/dpwoodru/general-courtade-kumar-lean.

    [KS26] D. Kramer and M. Saglam, On the most informative Boolean function under noise, manuscript, https://github.com/deepinfra/courtade-kumar.

    [KT26] Vu Khac Ky and Tuan Tran, Dictators are most informative, arXiv:2609.24184. See also their follow-up Stability of the Courtade–Kumar inequality, arXiv:2609.31797.

    [MB26] H. Mahdavifar and A. Beirami, The Most Informative Bit and Beyond: A Proof of the Courtade–Kumar Conjecture and Multibit Extensions, arXiv:2609.26444.

@[expose] public sectionnamespace CourtadeKumaropen scoped BigOperators ENNRealopen MeasureTheory

The elementary formulation

The probability interpretations of bsc, jointProb and mutualInfo assume $0 \le p \le 1$, and entropy q is Shannon entropy when the masses $q$ are nonnegative and sum to one; otherwise these definitions are just total real-valued expressions.

The Boolean cube ${0,1}^n$, with bits represented by Bool.

abbrev Cube (n : ℕ) := Fin n → Bool

Binary entropy in bits, $h(p) = -p \log_2 p - (1 - p) \log_2 (1 - p)$, with $h(0) = h(1) = 0$.

noncomputable def binEntropyBits (p : ℝ) : ℝ := Real.binEntropy p / Real.log 2

Transition probability of $n$ independent binary symmetric channels with crossover probability $p$: $P(Y = y \mid X = x) = \prod_i q_i$, where $q_i = 1 - p$ if $x_i = y_i$ and $q_i = p$ otherwise.

noncomputable def bsc {n : ℕ} (p : ℝ) (x y : Cube n) : ℝ := ∏ i, if x i = y i then 1 - p else p

The joint probability $P(f(X) = b, Y = y)$ for $X$ uniform on the cube and $Y$ the channel output on input $X$.

noncomputable def jointProb {n : ℕ} (f : Cube n → Bool) (p : ℝ) (b : Bool) (y : Cube n) : ℝ := (2 : ℝ) ^ (-(n : ℤ)) * ∑ x, if f x = b then bsc p x y else 0

Shannon entropy in bits of a probability mass function $q$ on a finite type.

noncomputable def entropy {α : Type*} [Fintype α] (q : α → ℝ) : ℝ := (∑ a, Real.negMulLog (q a)) / Real.log 2

The mutual information $I(f(X); Y) = H(f(X)) + H(Y) - H(f(X), Y)$, in bits.

noncomputable def mutualInfo {n : ℕ} (f : Cube n → Bool) (p : ℝ) : ℝ := entropy (fun b => ∑ y, jointProb f p b y) + entropy (fun y => ∑ b, jointProb f p b y) - entropy (fun z : Bool × Cube n => jointProb f p z.1 z.2)

The Courtade–Kumar conjecture. For every $n$, every Boolean function $f$ on ${0,1}^n$ and every crossover probability $p \in [0, 1]$, $I(f(X); Y) \le 1 - h(p)$.

@[category research solved, AMS 94, formal_proof using lean4 at "https://github.com/dpwoodru/general-courtade-kumar-lean/blob/c3599c05181ad357331b701edf8fd8ec75c88305/verification/comparator/CKChallenge/Solution.lean#L6"] theorem courtade_kumar (n : ℕ) (f : Cube n → Bool) (p : ℝ) (hp₀ : 0 ≤ p) (hp₁ : p ≤ 1) : mutualInfo f p ≤ 1 - binEntropyBits p := n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1⊢ mutualInfo f p ≤ 1 - binEntropyBits p All goals completed! 🐙

The random-variable formulation

Coordinatewise xor on the Boolean cube.

def cubeXor {n : ℕ} (x z : Cube n) : Cube n := fun i => Bool.xor (x i) (z i)

The joint law of a uniform input and independent i.i.d. Bernoulli channel noise.

On this probability space the input and noise are the two coordinate projections.

noncomputable def inputNoiseLaw (n : ℕ) (p : ℝ) (hp₀ : 0 ≤ p) (hp₁ : p ≤ 1) : Measure (Cube n × Cube n) := (PMF.uniformOfFintype (Cube n)).toMeasure.prod (Measure.pi fun _ : Fin n => ProbabilityTheory.bernoulliMeasure true false (⟨p, hp₀, hp₁⟩ : unitInterval))@[category API, AMS 94] instance (n : ℕ) (p : ℝ) (hp₀ : 0 ≤ p) (hp₁ : p ≤ 1) : IsProbabilityMeasure (inputNoiseLaw n p hp₀ hp₁) := n:ℕp:ℝhp₀:0 ≤ php₁:p ≤ 1⊢ IsProbabilityMeasure (inputNoiseLaw n p hp₀ hp₁) n:ℕp:ℝhp₀:0 ≤ php₁:p ≤ 1⊢ IsProbabilityMeasure ((PMF.uniformOfFintype (Cube n)).toMeasure.prod (Measure.pi fun x ↦ ProbabilityTheory.bernoulliMeasure true false ⟨p, ⋯⟩)) All goals completed! 🐙namespace variants

The Courtade–Kumar conjecture, in random-variable form.

The pushforward in the hypothesis is the joint distribution of $(X, Z)$. The uniform measure on Cube n is the law of $n$ i.i.d. Bernoulli($1/2$) bits. The product law makes the coordinates of $Z$ i.i.d. Bernoulli($p$) and makes the whole noise vector independent of $X$. In bernoulliMeasure true false p, true has probability $p$ and denotes a flip.

Conditional on $X$, $Y = X \oplus Z$ flips each input coordinate independently with probability $p$: this is the memoryless binary symmetric channel with crossover probability $p$ from $X$ to $Y$. Every Boolean function is allowed, including constants. All maps between these finite discrete types are measurable, so $f \circ X$ and $Y$ are measurable. The conclusion is $I(f(X); Y) \le 1 - h(p)$ in bits, for the entire output vector $Y$.

The linked proof proves the elementary statement CourtadeKumar.courtade_kumar, and CourtadeKumar.courtade_kumar_iff_random_variable transfers it to this formulation.

@[category research solved, AMS 94, formal_proof using lean4 at "https://github.com/dpwoodru/general-courtade-kumar-lean/blob/c3599c05181ad357331b701edf8fd8ec75c88305/verification/comparator/CKChallenge/Solution.lean#L6"] theorem courtade_kumar_random_variable : ∀ (n : ℕ) (f : Cube n → Bool) (p : ℝ) (hp₀ : 0 ≤ p) (hp₁ : p ≤ 1) (Ω : Type) [MeasurableSpace Ω] (μ : Measure Ω) [IsProbabilityMeasure μ] (X Z : Ω → Cube n), Measurable X → Measurable Z → μ.map (fun ω => (X ω, Z ω)) = (PMF.uniformOfFintype (Cube n)).toMeasure.prod (Measure.pi fun _ : Fin n => ProbabilityTheory.bernoulliMeasure true false (⟨p, hp₀, hp₁⟩ : unitInterval)) → let Y : Ω → Cube n := fun ω => cubeXor (X ω) (Z ω) InformationTheory.mutualInformationBits μ (f ∘ X) Y ≤ 1 - binEntropyBits p := ⊢ ∀ (n : ℕ) (f : Cube n → Bool) (p : ℝ) (hp₀ : 0 ≤ p) (hp₁ : p ≤ 1) (Ω : Type) [inst : MeasurableSpace Ω] (μ : Measure Ω) [IsProbabilityMeasure μ] (X Z : Ω → Cube n), Measurable X → Measurable Z → Measure.map (fun ω ↦ (X ω, Z ω)) μ = (PMF.uniformOfFintype (Cube n)).toMeasure.prod (Measure.pi fun x ↦ ProbabilityTheory.bernoulliMeasure true false ⟨p, ⋯⟩) → let Y := fun ω ↦ cubeXor (X ω) (Z ω); InformationTheory.mutualInformationBits μ (f ∘ X) Y ≤ 1 - binEntropyBits p All goals completed! 🐙end variants

API: equivalence of the formulations

@[category API, AMS 94] private theorem cubeXor_eq_iff {n : ℕ} (x z y : Cube n) : cubeXor x z = y ↔ z = cubeXor x y := n:ℕx:Cube nz:Cube ny:Cube n⊢ cubeXor x z = y ↔ z = cubeXor x y n:ℕx:Cube nz:Cube ny:Cube n⊢ (∀ (x_1 : Fin n), (x x_1 ^^ z x_1) = y x_1) ↔ ∀ (x_1 : Fin n), z x_1 = (x x_1 ^^ y x_1) exact forall_congr' fun i => n:ℕx:Cube nz:Cube ny:Cube ni:Fin n⊢ (x i ^^ z i) = y i ↔ z i = (x i ^^ y i) n:ℕx:Cube nz:Cube ny:Cube ni:Fin n⊢ (false ^^ z i) = y i ↔ z i = (false ^^ y i)n:ℕx:Cube nz:Cube ny:Cube ni:Fin n⊢ (true ^^ z i) = y i ↔ z i = (true ^^ y i) n:ℕx:Cube nz:Cube ny:Cube ni:Fin n⊢ (false ^^ z i) = y i ↔ z i = (false ^^ y i)n:ℕx:Cube nz:Cube ny:Cube ni:Fin n⊢ (true ^^ z i) = y i ↔ z i = (true ^^ y i) n:ℕx:Cube nz:Cube ny:Cube ni:Fin n⊢ (true ^^ false) = y i ↔ false = (true ^^ y i)n:ℕx:Cube nz:Cube ny:Cube ni:Fin n⊢ (true ^^ true) = y i ↔ true = (true ^^ y i) n:ℕx:Cube nz:Cube ny:Cube ni:Fin n⊢ (false ^^ false) = y i ↔ false = (false ^^ y i)n:ℕx:Cube nz:Cube ny:Cube ni:Fin n⊢ (false ^^ true) = y i ↔ true = (false ^^ y i)n:ℕx:Cube nz:Cube ny:Cube ni:Fin n⊢ (true ^^ false) = y i ↔ false = (true ^^ y i)n:ℕx:Cube nz:Cube ny:Cube ni:Fin n⊢ (true ^^ true) = y i ↔ true = (true ^^ y i) n:ℕx:Cube nz:Cube ny:Cube ni:Fin n⊢ (true ^^ true) = false ↔ true = (true ^^ false)n:ℕx:Cube nz:Cube ny:Cube ni:Fin n⊢ (true ^^ true) = true ↔ true = (true ^^ true) n:ℕx:Cube nz:Cube ny:Cube ni:Fin n⊢ (false ^^ false) = false ↔ false = (false ^^ false)n:ℕx:Cube nz:Cube ny:Cube ni:Fin n⊢ (false ^^ false) = true ↔ false = (false ^^ true)n:ℕx:Cube nz:Cube ny:Cube ni:Fin n⊢ (false ^^ true) = false ↔ true = (false ^^ false)n:ℕx:Cube nz:Cube ny:Cube ni:Fin n⊢ (false ^^ true) = true ↔ true = (false ^^ true)n:ℕx:Cube nz:Cube ny:Cube ni:Fin n⊢ (true ^^ false) = false ↔ false = (true ^^ false)n:ℕx:Cube nz:Cube ny:Cube ni:Fin n⊢ (true ^^ false) = true ↔ false = (true ^^ true)n:ℕx:Cube nz:Cube ny:Cube ni:Fin n⊢ (true ^^ true) = false ↔ true = (true ^^ false)n:ℕx:Cube nz:Cube ny:Cube ni:Fin n⊢ (true ^^ true) = true ↔ true = (true ^^ true) All goals completed! 🐙@[category API, AMS 94] private theorem noiseProduct_cubeXor {n : ℕ} (p : ℝ) (x y : Cube n) : (∏ i, if cubeXor x y i then p else 1 - p) = bsc p x y := n:ℕp:ℝx:Cube ny:Cube n⊢ (∏ i, if cubeXor x y i = true then p else 1 - p) = bsc p x y n:ℕp:ℝx:Cube ny:Cube n⊢ (∏ i, if cubeXor x y i = true then p else 1 - p) = ∏ i, if x i = y i then 1 - p else p n:ℕp:ℝx:Cube ny:Cube n⊢ ∀ x_1 ∈ Finset.univ, (if cubeXor x y x_1 = true then p else 1 - p) = if x x_1 = y x_1 then 1 - p else p n:ℕp:ℝx:Cube ny:Cube ni:Fin na✝:i ∈ Finset.univ⊢ (if cubeXor x y i = true then p else 1 - p) = if x i = y i then 1 - p else p n:ℕp:ℝx:Cube ny:Cube ni:Fin na✝:i ∈ Finset.univhx:x i = false⊢ (if cubeXor x y i = true then p else 1 - p) = if false = y i then 1 - p else pn:ℕp:ℝx:Cube ny:Cube ni:Fin na✝:i ∈ Finset.univhx:x i = true⊢ (if cubeXor x y i = true then p else 1 - p) = if true = y i then 1 - p else p n:ℕp:ℝx:Cube ny:Cube ni:Fin na✝:i ∈ Finset.univhx:x i = false⊢ (if cubeXor x y i = true then p else 1 - p) = if false = y i then 1 - p else pn:ℕp:ℝx:Cube ny:Cube ni:Fin na✝:i ∈ Finset.univhx:x i = true⊢ (if cubeXor x y i = true then p else 1 - p) = if true = y i then 1 - p else p n:ℕp:ℝx:Cube ny:Cube ni:Fin na✝:i ∈ Finset.univhx:x i = truehy:y i = false⊢ (if cubeXor x y i = true then p else 1 - p) = if true = false then 1 - p else pn:ℕp:ℝx:Cube ny:Cube ni:Fin na✝:i ∈ Finset.univhx:x i = truehy:y i = true⊢ (if cubeXor x y i = true then p else 1 - p) = if true = true then 1 - p else p n:ℕp:ℝx:Cube ny:Cube ni:Fin na✝:i ∈ Finset.univhx:x i = falsehy:y i = false⊢ (if cubeXor x y i = true then p else 1 - p) = if false = false then 1 - p else pn:ℕp:ℝx:Cube ny:Cube ni:Fin na✝:i ∈ Finset.univhx:x i = falsehy:y i = true⊢ (if cubeXor x y i = true then p else 1 - p) = if false = true then 1 - p else pn:ℕp:ℝx:Cube ny:Cube ni:Fin na✝:i ∈ Finset.univhx:x i = truehy:y i = false⊢ (if cubeXor x y i = true then p else 1 - p) = if true = false then 1 - p else pn:ℕp:ℝx:Cube ny:Cube ni:Fin na✝:i ∈ Finset.univhx:x i = truehy:y i = true⊢ (if cubeXor x y i = true then p else 1 - p) = if true = true then 1 - p else p All goals completed! 🐙

The singleton masses of the input/noise product probability space.

n:ℕp:ℝhp₀:0 ≤ php₁:p ≤ 1x:Cube nz:Cube nhB:∀ (b : Bool), ((ProbabilityTheory.bernoulliMeasure true false ⟨p, ⋯⟩) {b}).toReal = if b = true then p else 1 - phs:{(x, z)} = {x} ×ˢ Set.univ.pi fun i ↦ {z i}⊢ ((PMF.uniformOfFintype (Cube n)).toMeasure {x}).toReal * ∏ i, ((ProbabilityTheory.bernoulliMeasure true false ⟨p, ⋯⟩) {z i}).toReal = 2 ^ (-↑n) * ∏ i, if z i = true then p else 1 - p All goals completed! 🐙

The joint probability of $(f(X), X \oplus Z)$ on the product probability space is the elementary jointProb.

n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1b:Booly:Cube nhsum:∀ (s : Set (Cube n × Cube n)), (inputNoiseLaw n p hp₀ hp₁).real s = ∑ w, if w ∈ s then (inputNoiseLaw n p hp₀ hp₁).real {w} else 0⊢ (∑ x, ∑ x_1, if f x = b ∧ cubeXor x x_1 = y then 2 ^ (-↑n) * ∏ i, if x_1 i = true then p else 1 - p else 0) = ∑ i, 2 ^ (-↑n) * if f i = b then bsc p i y else 0 n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1b:Booly:Cube nhsum:∀ (s : Set (Cube n × Cube n)), (inputNoiseLaw n p hp₀ hp₁).real s = ∑ w, if w ∈ s then (inputNoiseLaw n p hp₀ hp₁).real {w} else 0⊢ ∀ x ∈ Finset.univ, (∑ x_1, if f x = b ∧ cubeXor x x_1 = y then 2 ^ (-↑n) * ∏ i, if x_1 i = true then p else 1 - p else 0) = 2 ^ (-↑n) * if f x = b then bsc p x y else 0 n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1b:Booly:Cube nhsum:∀ (s : Set (Cube n × Cube n)), (inputNoiseLaw n p hp₀ hp₁).real s = ∑ w, if w ∈ s then (inputNoiseLaw n p hp₀ hp₁).real {w} else 0x:Cube na✝:x ∈ Finset.univ⊢ (∑ x_1, if f x = b ∧ cubeXor x x_1 = y then 2 ^ (-↑n) * ∏ i, if x_1 i = true then p else 1 - p else 0) = 2 ^ (-↑n) * if f x = b then bsc p x y else 0 n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1b:Booly:Cube nhsum:∀ (s : Set (Cube n × Cube n)), (inputNoiseLaw n p hp₀ hp₁).real s = ∑ w, if w ∈ s then (inputNoiseLaw n p hp₀ hp₁).real {w} else 0x:Cube na✝:x ∈ Finset.univh:f x = b⊢ (∑ x_1, if f x = b ∧ cubeXor x x_1 = y then 2 ^ (-↑n) * ∏ i, if x_1 i = true then p else 1 - p else 0) = 2 ^ (-↑n) * if f x = b then bsc p x y else 0n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1b:Booly:Cube nhsum:∀ (s : Set (Cube n × Cube n)), (inputNoiseLaw n p hp₀ hp₁).real s = ∑ w, if w ∈ s then (inputNoiseLaw n p hp₀ hp₁).real {w} else 0x:Cube na✝:x ∈ Finset.univh:¬f x = b⊢ (∑ x_1, if f x = b ∧ cubeXor x x_1 = y then 2 ^ (-↑n) * ∏ i, if x_1 i = true then p else 1 - p else 0) = 2 ^ (-↑n) * if f x = b then bsc p x y else 0 n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1b:Booly:Cube nhsum:∀ (s : Set (Cube n × Cube n)), (inputNoiseLaw n p hp₀ hp₁).real s = ∑ w, if w ∈ s then (inputNoiseLaw n p hp₀ hp₁).real {w} else 0x:Cube na✝:x ∈ Finset.univh:f x = b⊢ (∑ x_1, if f x = b ∧ cubeXor x x_1 = y then 2 ^ (-↑n) * ∏ i, if x_1 i = true then p else 1 - p else 0) = 2 ^ (-↑n) * if f x = b then bsc p x y else 0 All goals completed! 🐙 n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1b:Booly:Cube nhsum:∀ (s : Set (Cube n × Cube n)), (inputNoiseLaw n p hp₀ hp₁).real s = ∑ w, if w ∈ s then (inputNoiseLaw n p hp₀ hp₁).real {w} else 0x:Cube na✝:x ∈ Finset.univh:¬f x = b⊢ (∑ x_1, if f x = b ∧ cubeXor x x_1 = y then 2 ^ (-↑n) * ∏ i, if x_1 i = true then p else 1 - p else 0) = 2 ^ (-↑n) * if f x = b then bsc p x y else 0 All goals completed! 🐙

Mutual information on the explicit input/noise probability space equals the elementary finite-sum expression.

n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1μ:Measure (Cube n × Cube n) := inputNoiseLaw n p hp₀ hp₁T:Cube n × Cube n → Bool × Cube n := fun ω ↦ (f ω.1, cubeXor ω.1 ω.2)hT:Measurable Thν:∀ (w : Bool × Cube n), (Measure.map T μ).real {w} = jointProb f p w.1 w.2hMI:InformationTheory.mutualInformationBits (Measure.map T μ) Prod.fst Prod.snd = InformationTheory.mutualInformationBits μ (fun ω ↦ f ω.1) fun ω ↦ cubeXor ω.1 ω.2⊢ (∑ a, (∑ b, (Measure.map T μ).real {(a, b)}).negMulLog) / Real.log 2 + (∑ b, (∑ a, (Measure.map T μ).real {(a, b)}).negMulLog) / Real.log 2 - (∑ ab, ((Measure.map T μ).real {ab}).negMulLog) / Real.log 2 = mutualInfo f p All goals completed! 🐙

The same identity on any measurable space carrying the specified joint input/noise law.

n:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1Ω:Type u_1inst✝:MeasurableSpace Ωμ:Measure ΩX:Ω → Cube nZ:Ω → Cube nhX:Measurable XhZ:Measurable Zhlaw:Measure.map (fun ω ↦ (X ω, Z ω)) μ = inputNoiseLaw n p hp₀ hp₁hXZ:Measurable fun ω ↦ (X ω, Z ω)⊢ (InformationTheory.mutualInformationBits μ (f ∘ X) fun ω ↦ cubeXor (X ω) (Z ω)) = InformationTheory.mutualInformationBits μ ((fun ω ↦ f ω.1) ∘ fun ω ↦ (X ω, Z ω)) ((fun ω ↦ cubeXor ω.1 ω.2) ∘ fun ω ↦ (X ω, Z ω)) All goals completed! 🐙

The elementary formulation and the random-variable formulation are equivalent.

Neither direction uses either research declaration.

h:∀ (n : ℕ) (f : Cube n → Bool) (p : ℝ) (hp₀ : 0 ≤ p) (hp₁ : p ≤ 1) (Ω : Type) [inst : MeasurableSpace Ω] (μ : Measure Ω) [IsProbabilityMeasure μ] (X Z : Ω → Cube n), Measurable X → Measurable Z → Measure.map (fun ω ↦ (X ω, Z ω)) μ = (PMF.uniformOfFintype (Cube n)).toMeasure.prod (Measure.pi fun x ↦ ProbabilityTheory.bernoulliMeasure true false ⟨p, ⋯⟩) → have Y := fun ω ↦ cubeXor (X ω) (Z ω); InformationTheory.mutualInformationBits μ (f ∘ X) Y ≤ 1 - binEntropyBits pn:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1⊢ (InformationTheory.mutualInformationBits (inputNoiseLaw n p hp₀ hp₁) (fun ω ↦ f ω.1) fun ω ↦ cubeXor ω.1 ω.2) ≤ 1 - binEntropyBits p exact h n f p hp₀ hp₁ (Cube n × Cube n) (inputNoiseLaw n p hp₀ hp₁) Prod.fst Prod.snd measurable_fst measurable_snd (h:∀ (n : ℕ) (f : Cube n → Bool) (p : ℝ) (hp₀ : 0 ≤ p) (hp₁ : p ≤ 1) (Ω : Type) [inst : MeasurableSpace Ω] (μ : Measure Ω) [IsProbabilityMeasure μ] (X Z : Ω → Cube n), Measurable X → Measurable Z → Measure.map (fun ω ↦ (X ω, Z ω)) μ = (PMF.uniformOfFintype (Cube n)).toMeasure.prod (Measure.pi fun x ↦ ProbabilityTheory.bernoulliMeasure true false ⟨p, ⋯⟩) → have Y := fun ω ↦ cubeXor (X ω) (Z ω); InformationTheory.mutualInformationBits μ (f ∘ X) Y ≤ 1 - binEntropyBits pn:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1⊢ Measure.map (fun ω ↦ (ω.1, ω.2)) (inputNoiseLaw n p hp₀ hp₁) = (PMF.uniformOfFintype (Cube n)).toMeasure.prod (Measure.pi fun x ↦ ProbabilityTheory.bernoulliMeasure true false ⟨p, ⋯⟩) h:∀ (n : ℕ) (f : Cube n → Bool) (p : ℝ) (hp₀ : 0 ≤ p) (hp₁ : p ≤ 1) (Ω : Type) [inst : MeasurableSpace Ω] (μ : Measure Ω) [IsProbabilityMeasure μ] (X Z : Ω → Cube n), Measurable X → Measurable Z → Measure.map (fun ω ↦ (X ω, Z ω)) μ = (PMF.uniformOfFintype (Cube n)).toMeasure.prod (Measure.pi fun x ↦ ProbabilityTheory.bernoulliMeasure true false ⟨p, ⋯⟩) → have Y := fun ω ↦ cubeXor (X ω) (Z ω); InformationTheory.mutualInformationBits μ (f ∘ X) Y ≤ 1 - binEntropyBits pn:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1⊢ Measure.map id (inputNoiseLaw n p hp₀ hp₁) = inputNoiseLaw n p hp₀ hp₁ All goals completed! 🐙)

The random-variable formulation, stated over probability spaces in universe zero, implies the same bound on probability spaces in any universe. This does not use either research declaration.

hCK:∀ (n : ℕ) (f : Cube n → Bool) (p : ℝ) (hp₀ : 0 ≤ p) (hp₁ : p ≤ 1) (Ω : Type) [inst : MeasurableSpace Ω] (μ : Measure Ω) [IsProbabilityMeasure μ] (X Z : Ω → Cube n), Measurable X → Measurable Z → Measure.map (fun ω ↦ (X ω, Z ω)) μ = (PMF.uniformOfFintype (Cube n)).toMeasure.prod (Measure.pi fun x ↦ ProbabilityTheory.bernoulliMeasure true false ⟨p, ⋯⟩) → have Y := fun ω ↦ cubeXor (X ω) (Z ω); InformationTheory.mutualInformationBits μ (f ∘ X) Y ≤ 1 - binEntropyBits pn:ℕf:Cube n → Boolp:ℝhp₀:0 ≤ php₁:p ≤ 1Ω:Type u_1inst✝¹:MeasurableSpace Ωμ:Measure Ωinst✝:IsProbabilityMeasure μX:Ω → Cube nZ:Ω → Cube nhX:Measurable XhZ:Measurable Zhlaw:Measure.map (fun ω ↦ (X ω, Z ω)) μ = inputNoiseLaw n p hp₀ hp₁⊢ mutualInfo f p ≤ 1 - binEntropyBits p All goals completed! 🐙

Tests of the definitions

h:Real.log 2 ≠ 0⊢ binEntropyBits (1 / 2) = 1 All goals completed! 🐙All goals completed! 🐙p:ℝb:Booly:Cube 1⊢ 2 ^ (-↑1) * ((if ((fun x ↦ x 0) fun x ↦ true) = b then ∏ i, if (fun x ↦ true) i = y i then 1 - p else p else 0) + if ((fun x ↦ x 0) fun x ↦ false) = b then ∏ i, if (fun x ↦ false) i = y i then 1 - p else p else 0) = (if b = y 0 then 1 - p else p) / 2 p:ℝb:Booly:Cube 1⊢ 2 ^ (-↑1) * ((if true = b then if true = y 0 then 1 - p else p else 0) + if false = b then if false = y 0 then 1 - p else p else 0) = (if b = y 0 then 1 - p else p) / 2 p:ℝy:Cube 1⊢ 2 ^ (-↑1) * ((if true = false then if true = y 0 then 1 - p else p else 0) + if false = false then if false = y 0 then 1 - p else p else 0) = (if false = y 0 then 1 - p else p) / 2p:ℝy:Cube 1⊢ 2 ^ (-↑1) * ((if true = true then if true = y 0 then 1 - p else p else 0) + if false = true then if false = y 0 then 1 - p else p else 0) = (if true = y 0 then 1 - p else p) / 2 p:ℝy:Cube 1⊢ 2 ^ (-↑1) * ((if true = false then if true = y 0 then 1 - p else p else 0) + if false = false then if false = y 0 then 1 - p else p else 0) = (if false = y 0 then 1 - p else p) / 2p:ℝy:Cube 1⊢ 2 ^ (-↑1) * ((if true = true then if true = y 0 then 1 - p else p else 0) + if false = true then if false = y 0 then 1 - p else p else 0) = (if true = y 0 then 1 - p else p) / 2 p:ℝy:Cube 1⊢ 2 ^ (-↑1) * ((if true = true then if true = false then 1 - p else p else 0) + if false = true then if false = false then 1 - p else p else 0) = (if true = false then 1 - p else p) / 2p:ℝy:Cube 1⊢ 2 ^ (-↑1) * ((if true = true then if true = true then 1 - p else p else 0) + if false = true then if false = true then 1 - p else p else 0) = (if true = true then 1 - p else p) / 2 p:ℝy:Cube 1⊢ 2 ^ (-↑1) * ((if true = false then if true = false then 1 - p else p else 0) + if false = false then if false = false then 1 - p else p else 0) = (if false = false then 1 - p else p) / 2p:ℝy:Cube 1⊢ 2 ^ (-↑1) * ((if true = false then if true = true then 1 - p else p else 0) + if false = false then if false = true then 1 - p else p else 0) = (if false = true then 1 - p else p) / 2p:ℝy:Cube 1⊢ 2 ^ (-↑1) * ((if true = true then if true = false then 1 - p else p else 0) + if false = true then if false = false then 1 - p else p else 0) = (if true = false then 1 - p else p) / 2p:ℝy:Cube 1⊢ 2 ^ (-↑1) * ((if true = true then if true = true then 1 - p else p else 0) + if false = true then if false = true then 1 - p else p else 0) = (if true = true then 1 - p else p) / 2 p:ℝy:Cube 1⊢ 2⁻¹ * (1 - p) = (1 - p) / 2 p:ℝy:Cube 1⊢ 2⁻¹ * (1 - p) = (1 - p) / 2p:ℝy:Cube 1⊢ 2⁻¹ * p = p / 2p:ℝy:Cube 1⊢ 2⁻¹ * p = p / 2p:ℝy:Cube 1⊢ 2⁻¹ * (1 - p) = (1 - p) / 2 All goals completed! 🐙x:ℝh:2⁻¹.negMulLog = Real.log 2 / 2⊢ 2⁻¹ * x.negMulLog + x * (Real.log 2 / 2) = x.negMulLog / 2 + x * Real.log 2 / 2 All goals completed! 🐙

Algebraic identity for the one-coordinate dictator $f(x) = x_0$. For $p \in [0, 1]$, it shows that the bound is attained, so the conjecture is sharp and the statement is not vacuous.

p:ℝhlog:Real.log 2 ≠ 0jm:∀ (b : Bool) (y : Cube 1), jointProb (fun x ↦ x 0) p b y = (if b = y 0 then 1 - p else p) / 2half:(1 / 2).negMulLog = Real.log 2 / 2mf:∀ (b : Bool), ∑ y, jointProb (fun x ↦ x 0) p b y = 1 / 2my:∀ (y : Cube 1), ∑ b, jointProb (fun x ↦ x 0) p b y = 1 / 2e1:(entropy fun b ↦ ∑ y, jointProb (fun x ↦ x 0) p b y) = 1e2:(entropy fun y ↦ ∑ b, jointProb (fun x ↦ x 0) p b y) = 1e3:(entropy fun z ↦ jointProb (fun x ↦ x 0) p z.1 z.2) = 1 + binEntropyBits p⊢ 1 + 1 - (1 + binEntropyBits p) = 1 - binEntropyBits p All goals completed! 🐙end CourtadeKumar