🏛️ Atlas✒️Formalizations.Analysis.TransformerAttention.MaxEnt view on GitHub ↗17 theorems
/-Copyright (c) 2026 Carles Marín. All rights reserved.Released under Apache 2.0 license as described in the file LICENSE.Authors: Carles Marín, Claude (AI assistant)-/module public import Mathlib.Analysis.SpecialFunctions.Pow.Realpublic import Mathlib.Analysis.SpecialFunctions.Log.Basicpublic import Mathlib.Algebra.BigOperators.Group.Finset.Defspublic import Mathlib.Data.Fintype.Cardpublic import Mathlib.Algebra.BigOperators.Group.Finset.Basicpublic import Mathlib.Algebra.BigOperators.Fieldpublic import Mathlib.Algebra.Order.BigOperators.Group.Finsetpublic import Mathlib.Analysis.SpecialFunctions.Exppublic import Mathlib.Analysis.SpecialFunctions.ExpDerivpublic import Mathlib.Topology.Order.IntermediateValuepublic import Mathlib.Tactic.FieldSimppublic import Mathlib.Tactic.Ringpublic import Mathlib.Tactic.Positivitypublic import Mathlib.Tactic.FunProp /-!# Maximum entropy with a log-distance constraint is a power law Among probability distributions on the distances `1, …, N` with prescribed `E[log d] = λ`, the powerlaw `p_γ(d) = d^(−γ)/Σ_e e^(−γ)` is the unique maximiser of Shannon entropy, and when`0 < λ < (1/N) Σ_d log d` the exponent `γ > 0` is unique. This corrects Theorem 6.2 of «PredictingHow Transformers Attend» (Part I, v3), which omitted the condition on `λ`. Proof: Gibbs' inequality— `Σ p log p_γ` is the same for every feasible `p`, so `H(p_γ) − H(p)` is a relative entropy,nonnegative by `log x ≤ x − 1` and zero only at `p = p_γ`; the exponent comes from the intermediatevalue theorem. ## Main results * `MaxEntPowerLaw.maxent_power_law`: corrected MaxEnt theorem: unique γ > 0, unique entropy maximiser ## References * C. Marín, «Predicting How Transformers Attend», Zenodo 20314038 (v3), Thm 6.2 (corregido).* E. T. Jaynes, Phys. Rev. 106 (1957) 620; T. Cover, J. Thomas, Elements of Information Theory (2006), §12.-/ @[expose] public section open Finset Real namespace MaxEntPowerLaw /-- `E_p[log d]` for a distribution `p` on distances `1..N`. -/noncomputable def logMean {N : ℕ} (p : Fin N → ℝ) : ℝ := ∑ i, p i * Real.log ((i : ℝ) + 1) /-- Shannon entropy `-Σ p log p`. -/noncomputable def entropy {N : ℕ} (p : Fin N → ℝ) : ℝ := -∑ i, p i * Real.log (p i) /-- The power law `p_γ(d) = d^(-γ) / Σ_e e^(-γ)` on distances `1..N`. -/noncomputable def powerLaw (N : ℕ) (γ : ℝ) (i : Fin N) : ℝ :=  ((i : ℝ) + 1) ^ (-γ) / ∑ j : Fin N, ((j : ℝ) + 1) ^ (-γ) /-- Unnormalised weight `d^(-γ)` written with `exp`. -/noncomputable def wt {N : ℕ} (γ : ℝ) (i : Fin N) : ℝ := Real.exp (-γ * Real.log ((i : ℝ) + 1)) /-- Partition function. -/noncomputable def Z (N : ℕ) (γ : ℝ) : ℝ := ∑ i : Fin N, wt γ i theorem rpow_eq {N : ℕ} (γ : ℝ) (i : Fin N) : ((i : ℝ) + 1) ^ (-γ) = wt γ i := by  have h : (0 : ℝ) < (i : ℝ) + 1 := by positivity  rw [Real.rpow_def_of_pos h, wt, mul_comm] theorem powerLaw_eq {N : ℕ} (γ : ℝ) (i : Fin N) : powerLaw N γ i = wt γ i / Z N γ := by  simp only [powerLaw, Z, rpow_eq] theorem Z_pos {N : ℕ} (hN : 0 < N) (γ : ℝ) : 0 < Z N γ :=  Finset.sum_pos (fun _ _ => Real.exp_pos _) ⟨⟨0, hN⟩, Finset.mem_univ _⟩ theorem pl_pos {N : ℕ} (hN : 0 < N) (γ : ℝ) (i : Fin N) : 0 < powerLaw N γ i := by  rw [powerLaw_eq]; exact div_pos (Real.exp_pos _) (Z_pos hN γ) theorem pl_sum {N : ℕ} (hN : 0 < N) (γ : ℝ) : ∑ i, powerLaw N γ i = 1 := by  simp only [powerLaw_eq, ← Finset.sum_div]  exact div_self (Z_pos hN γ).ne' theorem log_pl {N : ℕ} (hN : 0 < N) (γ : ℝ) (i : Fin N) :    Real.log (powerLaw N γ i) = -γ * Real.log ((i : ℝ) + 1) - Real.log (Z N γ) := by  rw [powerLaw_eq, wt, Real.log_div (Real.exp_pos _).ne' (Z_pos hN γ).ne', Real.log_exp] theorem sum_mul_log_pl {N : ℕ} (hN : 0 < N) (γ : ℝ) (p : Fin N → ℝ) (hp : ∑ i, p i = 1) :    ∑ i, p i * Real.log (powerLaw N γ i) = -γ * logMean p - Real.log (Z N γ) := by  calc ∑ i, p i * Real.log (powerLaw N γ i)      = ∑ i, (-γ * (p i * Real.log ((i : ℝ) + 1)) - p i * Real.log (Z N γ)) := by        refine Finset.sum_congr rfl (fun i _ => ?_)        rw [log_pl hN]; ring    _ = -γ * logMean p - Real.log (Z N γ) := by        rw [Finset.sum_sub_distrib, ← Finset.mul_sum, ← Finset.sum_mul, hp, one_mul]; rfl /-- Termwise Gibbs inequality. -/theorem term_gibbs (a b : ℝ) (ha : 0 ≤ a) (hb : 0 < b) :    0 ≤ a * (Real.log a - Real.log b) - (a - b) ∧      (a * (Real.log a - Real.log b) - (a - b) = 0 → a = b) := by  rcases ha.eq_or_lt with h | h  · subst h    refine ⟨by simp [hb.le], fun h' => ?_⟩    simp at h'; linarith  · have key : a * (Real.log a - Real.log b) - (a - b) = a * ((b / a - 1) - Real.log (b / a)) := by      rw [Real.log_div hb.ne' h.ne']; field_simp; ring    have hx : 0 < b / a := div_pos hb h    refine ⟨?_, fun h' => ?_⟩    · rw [key]; exact mul_nonneg h.le (sub_nonneg.2 (Real.log_le_sub_one_of_pos hx))    · by_contra hne      have hne' : b / a ≠ 1 := fun e => hne ((div_eq_one_iff_eq h.ne').1 e).symm      have := Real.log_lt_sub_one_of_pos hx hne'      rw [key] at h'      have : 0 < a * ((b / a - 1) - Real.log (b / a)) := mul_pos h (by linarith)      linarith theorem gibbs_le {N : ℕ} (hN : 0 < N) (γ : ℝ) (p : Fin N → ℝ) (hp0 : ∀ i, 0 ≤ p i)    (hp1 : ∑ i, p i = 1) (hlm : logMean p = logMean (powerLaw N γ)) :    entropy p ≤ entropy (powerLaw N γ) ∧ (entropy p = entropy (powerLaw N γ) → p = powerLaw N γ) := by  set q := powerLaw N γ with hq  have hq1 : ∑ i, q i = 1 := pl_sum hN γ  have hcross : ∑ i, p i * Real.log (q i) = ∑ i, q i * Real.log (q i) := by    rw [hq, sum_mul_log_pl hN γ p hp1, sum_mul_log_pl hN γ _ (pl_sum hN γ), hlm]  set t : Fin N → ℝ := fun i => p i * (Real.log (p i) - Real.log (q i)) - (p i - q i) with ht  have hsum : ∑ i, t i = entropy q - entropy p := by    have e1 : ∑ i, t i = ∑ i, p i * Real.log (p i) - ∑ i, p i * Real.log (q i)        - (∑ i, p i - ∑ i, q i) := by      simp only [ht, mul_sub, Finset.sum_sub_distrib]    rw [e1, hp1, hq1, hcross]; unfold entropy; ring  have hnn : ∀ i ∈ Finset.univ, 0 ≤ t i := fun i _ => (term_gibbs (p i) (q i) (hp0 i) (pl_pos hN γ i)).1  refine ⟨?_, fun heq => ?_⟩  · have := Finset.sum_nonneg hnn    linarith  · have h0 : ∑ i, t i = 0 := by rw [hsum]; linarith    rw [Finset.sum_eq_zero_iff_of_nonneg hnn] at h0    funext i    exact (term_gibbs (p i) (q i) (hp0 i) (pl_pos hN γ i)).2 (h0 i (Finset.mem_univ _)) theorem logMean_pl {N : ℕ} (_hN : 0 < N) (γ : ℝ) :    logMean (powerLaw N γ) = (∑ i : Fin N, wt γ i * Real.log ((i : ℝ) + 1)) / Z N γ := by  unfold logMean  rw [Finset.sum_div]  refine Finset.sum_congr rfl (fun i _ => ?_)  rw [powerLaw_eq]; ring theorem continuous_logMean {N : ℕ} (hN : 0 < N) : Continuous fun γ : ℝ => logMean (powerLaw N γ) := by  have : (fun γ : ℝ => logMean (powerLaw N γ))      = fun γ => (∑ i : Fin N, wt γ i * Real.log ((i : ℝ) + 1)) / Z N γ := by    funext γ; exact logMean_pl hN γ  rw [this]  have hw : ∀ i : Fin N, Continuous fun γ : ℝ => wt γ i := fun i => by unfold wt; fun_prop  refine Continuous.div ?_ ?_ (fun γ => (Z_pos hN γ).ne')  · exact continuous_finsetSum _ (fun i _ => (hw i).mul continuous_const)  · exact continuous_finsetSum _ (fun i _ => hw i) theorem logMean_zero {N : ℕ} (hN : 0 < N) :    logMean (powerLaw N 0) = (∑ i : Fin N, Real.log ((i : ℝ) + 1)) / N := by  rw [logMean_pl hN]  simp [wt, Z] theorem Z_ge_one {N : ℕ} (hN : 0 < N) (γ : ℝ) : 1 ≤ Z N γ := by  have := Finset.single_le_sum (f := fun j : Fin N => wt γ j) (fun j _ => (Real.exp_pos _).le)    (Finset.mem_univ (⟨0, hN⟩ : Fin N))  simpa [wt, Z] using this theorem logMean_le {N : ℕ} (hN : 0 < N) (γ : ℝ) (hγ : 0 ≤ γ) :    logMean (powerLaw N γ) ≤ N * Real.exp (-γ * Real.log 2) * Real.log N := by  rw [logMean_pl hN]  have hN1 : (1 : ℝ) ≤ N := by exact_mod_cast hN  have hlogN : 0 ≤ Real.log N := Real.log_nonneg hN1  have hE : 0 < Real.exp (-γ * Real.log 2) := Real.exp_pos _  have hterm : ∀ i ∈ (Finset.univ : Finset (Fin N)),      wt γ i * Real.log ((i : ℝ) + 1) ≤ Real.exp (-γ * Real.log 2) * Real.log N := by    intro i _    rcases Nat.eq_zero_or_pos (i : ℕ) with h0 | h0    · simp [wt, h0]; positivity    · have hi1 : (2 : ℝ) ≤ (i : ℝ) + 1 := by        have : (1 : ℝ) ≤ (i : ℝ) := by exact_mod_cast h0        linarith      have hiN : (i : ℝ) + 1 ≤ N := by        have : (i : ℕ) + 1 ≤ N := i.isLt        exact_mod_cast this      have hl2 : Real.log 2 ≤ Real.log ((i : ℝ) + 1) := Real.log_le_log (by norm_num) hi1      have hlN : Real.log ((i : ℝ) + 1) ≤ Real.log N :=        Real.log_le_log (by positivity) hiN      have hlpos : 0 ≤ Real.log ((i : ℝ) + 1) := le_trans (Real.log_nonneg (by norm_num)) hl2      have hw : wt γ i ≤ Real.exp (-γ * Real.log 2) := by        unfold wt        apply Real.exp_le_exp.2        nlinarith      exact mul_le_mul hw hlN hlpos hE.le  have hS : ∑ i : Fin N, wt γ i * Real.log ((i : ℝ) + 1) ≤ N * Real.exp (-γ * Real.log 2) * Real.log N := by    calc _ ≤ ∑ _i : Fin N, Real.exp (-γ * Real.log 2) * Real.log N := Finset.sum_le_sum hterm      _ = _ := by simp; ring  have hS0 : 0 ≤ ∑ i : Fin N, wt γ i * Real.log ((i : ℝ) + 1) :=    Finset.sum_nonneg (fun i _ => mul_nonneg (Real.exp_pos _).le      (Real.log_nonneg (by have : (0 : ℝ) ≤ (i : ℝ) := by positivity                           linarith)))  exact le_trans (div_le_self hS0 (Z_ge_one hN γ)) hS theorem exists_gamma (N : ℕ) (hN : 2 ≤ N) (lam : ℝ) (h0 : 0 < lam)    (h1 : lam < (∑ i : Fin N, Real.log ((i : ℝ) + 1)) / N) :    ∃ γ : ℝ, 0 < γ ∧ logMean (powerLaw N γ) = lam := by  have hN0 : 0 < N := by omega  have hlog2 : 0 < Real.log 2 := Real.log_pos (by norm_num)  have ht : Filter.Tendsto (fun γ : ℝ => (N : ℝ) * Real.exp (-γ * Real.log 2) * Real.log N)      Filter.atTop (nhds 0) := by    have h1 := Real.tendsto_exp_neg_atTop_nhds_zero.comp      (Filter.tendsto_id.atTop_mul_const hlog2)    have h2 := (h1.const_mul (N : ℝ)).mul_const (Real.log N)    simpa [Function.comp_def, neg_mul] using h2  obtain ⟨Γ, hΓ, hΓ0⟩ := ((ht.eventually (gt_mem_nhds h0)).and (Filter.eventually_ge_atTop 0)).exists  have hfΓ : logMean (powerLaw N Γ) < lam := lt_of_le_of_lt (logMean_le hN0 Γ hΓ0) hΓ  have hf0 := logMean_zero hN0  have hcont := (continuous_logMean hN0).continuousOn (s := Set.Icc 0 Γ)  have hmem : lam ∈ Set.Icc (logMean (powerLaw N Γ)) (logMean (powerLaw N 0)) :=    ⟨hfΓ.le, by rw [hf0]; exact h1.le⟩  obtain ⟨γ, ⟨hγ0, _⟩, hγ⟩ := intermediate_value_Icc' hΓ0 hcont hmem  refine ⟨γ, ?_, hγ⟩  rcases hγ0.eq_or_lt with h | h  · subst h    have hγ' : logMean (powerLaw N 0) = lam := hγ    rw [hf0] at hγ'; linarith  · exact h theorem gamma_unique {N : ℕ} (hN : 2 ≤ N) (lam γ₁ γ₂ : ℝ)    (h₁ : logMean (powerLaw N γ₁) = lam) (h₂ : logMean (powerLaw N γ₂) = lam) : γ₁ = γ₂ := by  have hN0 : 0 < N := by omega  have a := gibbs_le hN0 γ₂ (powerLaw N γ₁) (fun i => (pl_pos hN0 γ₁ i).le) (pl_sum hN0 γ₁)    (by rw [h₁, h₂])  have b := gibbs_le hN0 γ₁ (powerLaw N γ₂) (fun i => (pl_pos hN0 γ₂ i).le) (pl_sum hN0 γ₂)    (by rw [h₁, h₂])  have hq : powerLaw N γ₁ = powerLaw N γ₂ := a.2 (le_antisymm a.1 b.1)  have e0 := congrFun hq ⟨0, hN0⟩  have e1 := congrFun hq ⟨1, by omega⟩  have w0 : ∀ γ : ℝ, wt γ (⟨0, hN0⟩ : Fin N) = 1 := fun γ => by simp [wt]  have w1 : ∀ γ : ℝ, wt γ (⟨1, by omega⟩ : Fin N) = Real.exp (-γ * Real.log 2) := fun γ => by    simp [wt]; norm_num  rw [powerLaw_eq, powerLaw_eq, w0, w0] at e0  rw [powerLaw_eq, powerLaw_eq, w1, w1] at e1  have hZ : Z N γ₁ = Z N γ₂ := by simpa using e0  rw [hZ] at e1  have hz := (Z_pos hN0 γ₂).ne'  have e3 := Real.exp_injective ((div_left_inj' hz).1 e1)  have hlog2 : 0 < Real.log 2 := Real.log_pos (by norm_num)  have : γ₁ * Real.log 2 = γ₂ * Real.log 2 := by linarith  exact mul_right_cancel₀ hlog2.ne' this /-- **MaxEnt power law (corrected Theorem 6.2).** -/theorem maxent_power_law (N : ℕ) (hN : 2 ≤ N) (lam : ℝ) (h0 : 0 < lam)    (h1 : lam < (∑ i : Fin N, Real.log ((i : ℝ) + 1)) / N) :    ∃! γ : ℝ, 0 < γ ∧ logMean (powerLaw N γ) = lam ∧      ∀ p : Fin N → ℝ, (∀ i, 0 ≤ p i) → ∑ i, p i = 1 → logMean p = lam →        entropy p ≤ entropy (powerLaw N γ) ∧ (entropy p = entropy (powerLaw N γ) → p = powerLaw N γ) := by  have hN0 : 0 < N := by omega  obtain ⟨γ, hγ0, hγ⟩ := exists_gamma N hN lam h0 h1  refine ⟨γ, ⟨hγ0, hγ, fun p hp0 hp1 hpl => gibbs_le hN0 γ p hp0 hp1 (by rw [hpl, hγ])⟩, ?_⟩  rintro γ' ⟨_, h', _⟩  exact gamma_unique hN lam γ' γ h' hγ end MaxEntPowerLaw  end