Information law: for a row drawn from a prior and any proposal, E[log(1+χ²)] ≥ I(J; row) and E[1+χ²] ≥ exp I(J; row), where J ~ π is a key drawn from the row
For all , , and , if , , , , and (given , and ), then
What the notation means · or point at any symbol
- Type
- Type: a definition from the library, not special notation. Its name is its meaning; open it in Lean to see how it is defined. (
Type) - x ∈ TVariables
- I, J range over Type: the statement must hold for every choice. (
(I J : Type)) - Fintype
- Fintype: a definition from the library, not special notation. Its name is its meaning; open it in Lean to see how it is defined. (
Fintype) - f(x)Function application
- Fintype applied to I. Lean writes f x; papers write f(x). (
Fintype I) - Nonempty
- Nonempty: a definition from the library, not special notation. Its name is its meaning; open it in Lean to see how it is defined. (
Nonempty) - ⟹Implies
- If I, then ℝ. (Between types, A → B is the type of functions from A to B.) (
I → ℝ) - ∀For all
- The statement after the comma holds for every i. (
∀ i, 0 ≤ lam i) - ∑Summation
- Add up lam(i) for every i. (
∑ i, lam i) - =Equality
- ∑ i, lam(i) and 1 are the same. (
∑ i, lam i = 1) - ∧And
- Both hold: (∑ i, lam(i) · (∑ j, π(i, j) · log(π(i, j)/(∑ k, lam(k) · …, and exp(∑ i, lam(i) · (∑ j, π(i, j) · log(π(i, j)/(∑ k, lam(k)…. (
∑ i, lam i * ∑ j, π i j * Real.log (π i…) - RReal numbers
- The real numbers: every point on the number line. (
ℝ) - ≤At most
- 0 is less than or equal to lam(i). (
0 ≤ lam i) - <Less than
- 0 is strictly smaller than π(i, j). (
0 < π i j) - πPi
- The ratio of a circle's circumference to its diameter, ≈ 3.14159. (
π) - logNatural logarithm
- The logarithm of π(i, j)/(∑ k, lam(k) · π(k, j)) to base e: the power e must be raised to to give π(i, j)/(∑ k, lam(k) · π(k, j)). (
Real.log (π i j / ∑ k, lam k * π k j)) - a/bDivision
- π(i, j) divided by ∑ k, lam(k) · π(k, j). In Lean, dividing by 0 gives 0. (
π i j / ∑ k, lam k * π k j) - ·Multiplication
- lam(k) times π(k, j). (
lam k * π k j) - aᵇPower
- π(i, j) raised to the power 2. (
π i j ^ 2) - eˣExponential function
- e raised to the power ∑ i, lam(i) · (∑ j, π(i, j) · log(π(i, j)/(∑ k, lam(k) · π…, where e ≈ 2.718. (
Real.exp (∑ i, lam i * ∑ j, π i j * Rea…)
theorem vcl-log-cost-ge-mutual-information {I J : Type} [Fintype I] [Fintype J] [Nonempty J] (lam : I → ℝ) (π : I → J → ℝ) (r : J → ℝ) (hlam : ∀ i, 0 ≤ lam i) (hlams : ∑ i, lam i = 1) (hπ : ∀ i j, 0 < π i j) (hπs : ∀ i, ∑ j, π i j = 1) (hr : ∀ j, 0 < r j) (hrs : ∑ j, r j = 1) :
∑ i, lam i * ∑ j, π i j * Real.log (π i j / ∑ k, lam k * π k j) ≤ ∑ i, lam i * Real.log (∑ j, π i j ^ 2 / r j) ∧ Real.exp (∑ i, lam i * ∑ j, π i j * Real.log (π i j / ∑ k, lam k * π k j)) ≤ ∑ i, lam i * ∑ j, π i j ^ 2 / r jShannon form of the variational cost law. For a mixture of positive rows π_i with weights λ_i (the posterior over rows given whatever side information the proposal was built from) and any proposal r: Σ_i λ_i Σ_j π_ij log(π_ij/p̄_j) ≤ Σ_i λ_i log(Σ_j π_ij²/r_j), where p̄ = Σ_i λ_i π_i is the posterior predictive, and the exponential of the left side bounds the expected cost factor. The left side is the mutual information between a sampled key and the row, so, in bits, log₂(cost) ≥ (bits needed to predict the sample from the row) − (bits the side information carries about the sample). Proof: Jensen for log per row, then Gibbs' inequality for the predictive. This is the general form of the argument in the polylog-query lower bound. First-principles reformulation, 2026-10-05.
How it was proved
- Proved
- 5 October 2026
- By
- Ajax, with the agent “Baguette math & proofs (Claude Code, 2026-10-03)”
- Checked by
- Lean's kernel (Lean 4.33.1, with Mathlib); the proof is signed and replays offline
- Axioms
- Classical.choice, Quot.sound, propext
- Proof
- 93 lines of Lean