Skip to main content
teorth/PFR
Source indexedlemma · leanprover/lean4:v4.33.0-rc1

multidist_ruzsa_III'

PFR.MoreRuzsaDist · PFR/MoreRuzsaDist.lean:1184 to 1260

Source documentation

A version of multidist_ruzsa_III assuming independence.

Exact Lean statement

lemma multidist_ruzsa_III' {m : ℕ} (hm : m ≥ 2) {Ω : Type*} {hΩ : MeasureSpace Ω}
    {X : Fin (m + 1) → Ω → G} (hmes : ∀ i, Measurable (X i))
    (hident : ∀ j k, IdentDistrib (X j) (X k)) (hindep : iIndepFun X)
    (hfin : ∀ i, FiniteRange (X i)) [IsProbabilityMeasure (ℙ : Measure Ω)] (i₀ : Fin m) :
    D[Fin.init X ; fun _ ↦ hΩ] ≤ m * d[X i₀.castSucc # X i₀.castSucc]

Complete declaration

Lean source

Canonical source
Full Lean sourceLean 4
lemma multidist_ruzsa_III' {m : } (hm : m  2) {Ω : Type*} {hΩ : MeasureSpace Ω}    {X : Fin (m + 1)  Ω  G} (hmes :  i, Measurable (X i))    (hident :  j k, IdentDistrib (X j) (X k)) (hindep : iIndepFun X)    (hfin :  i, FiniteRange (X i)) [IsProbabilityMeasure (ℙ : Measure Ω)] (i₀ : Fin m) :    D[Fin.init X ; fun _  hΩ]  m * d[X i₀.castSucc # X i₀.castSucc] := by  set m' : Fin (m + 1) := Fin.last _  set X₀ := X m'  set S := ∑ i : Fin m, X i.castSucc  have hent (i : Fin (m + 1)) : H[X i] = H[X₀] := (hident _ _).entropy_congr  have hind' (i : Fin m) : IndepFun (X i.castSucc) X₀ ℙ := hindep.indepFun <| by simp [m']  have hind_S : IndepFun S X₀ ℙ := by    set s : Finset (Fin (m + 1)) := .Iio m'    set s' : Finset (Fin (m + 1)) := {m'}    have h_disjoint : Disjoint s s' := by aesop    have hm': m'  s' := Finset.mem_singleton.mpr rfl    let φ (x : s  G) : G := ∑ i, x i    let φ' (x : s'  G) : G := x m', hm'    have hφ : Measurable φ := by fun_prop    have hφ' : Measurable φ' := by fun_prop    convert hindep.finsets_comp' h_disjoint hmes hφ hφ' with ω    simp only [Finset.sum_apply, Finset.univ_eq_attach, s.sum_attach (X · ω), S, φ]    exact Fin.sum_univ_castSucc' (X · ω)  have hmes_S : Measurable S := by fun_prop  calc    _ = H[S] - (∑ i : Fin m, H[X i.castSucc])/m :=       multiDist_indep _ (X := Fin.init X) (by simp [Fin.init]; fun_prop) <|         (hindep.precomp <| Fin.castSucc_injective m:)    _  H[-X₀ + S] - (∑ i : Fin m, H[X i.castSucc])/m := by      gcongr      rw [neg_add_eq_sub]      exact (le_max_left _ _).trans (max_entropy_le_entropy_sub hmes_S (hmes _) hind_S)    _ = (H[-X₀ + S] - H[-X₀]) - (∑ i : Fin m, H[X i.castSucc])/m + H[-X₀] := by abel    _  ∑ i : Fin m, (H[-X₀ + X i.castSucc] - H[-X₀])        - (∑ i : Fin m, H[X i.castSucc]) / m + H[-X₀] := by      gcongr      set Y : Fin (m + 1)  Ω  G := fun i  if (i = m') then - X₀ else X i      have hYfin (i : Fin (m + 1)) : FiniteRange (Y i) := by        by_cases h : i = m' <;> simp [Y, h]        all_goals infer_instance      have hYfin (i : Fin (m + 1)) : Measurable (Y i) := by        by_cases h : i = m' <;> simp [Y, h]        · exact (hmes _).neg        · exact hmes i      have : H[Y m' + ∑ i < m', Y i] - H[Y m']  ∑ i < m', (H[Y m' + Y i] - H[Y m']) := by        apply kvm_ineq_I Finset.notMem_Iio_self hYfin _        set f : Fin (m + 1)  G  G := fun i g  if i = m' then -g else g        convert iIndepFun.comp hindep f _ with i        · ext ω          by_cases h : i = m' <;> simp [f, h, Y, X₀]        intro i        by_cases h : i = m' <;> simp [f, h]        all_goals measurability      convert! this using 1      · congr        · simp [Y, X₀]        · convert Fin.sum_univ_castSucc' Y using 2 with i _          have : i.castSucc  m' := by simp [m']          simp [Y, this]        simp [Y,X₀]      rw [ Fin.sum_univ_castSucc' _]      congr; ext i      have : i.castSucc  m' := by simp [m']      congr      all_goals simp [Y,this,X₀]    _ = ∑ i : Fin m, d[X i.castSucc # X₀] - (∑ i : Fin m, H[X₀])/m + H[-X₀] := by      congr 2      · apply Finset.sum_congr rfl        intro i _        rw [(hind' i).rdist_eq (hmes _) (hmes _), hent, entropy_neg (hmes _), neg_add_eq_sub]        linarith      congr 1; apply Finset.sum_congr rfl      intro i _; exact hent _    _ = ∑ i : Fin m, d[X i.castSucc # X₀] := by simp [X₀, entropy_neg (hmes _)]; field_simp; ring    _ = ∑ i : Fin m, d[X i₀.castSucc # X i₀.castSucc] := by      congr; ext i      exact (hident _ _).rdist_congr (hident _ _)    _ = _ := by simp