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

multidist_ruzsa_I_indep

PFR.MoreRuzsaDist · PFR/MoreRuzsaDist.lean:1081 to 1136

Source documentation

To prove multidist_ruzsa_I, we first establish a special case when the random variables are defined on the same space and are jointly independent.

Exact Lean statement

lemma multidist_ruzsa_I_indep {m : ℕ} (hm : m ≥ 1) {Ω : Type*} (hΩ : MeasureSpace Ω)
    [IsProbabilityMeasure (hΩ.volume)] (X : Fin m → Ω → G) (h_indep : iIndepFun X)
    (hmes : ∀ j, Measurable (X j)) (hfin : ∀ j, FiniteRange (X j)) :
    ∑ j, ∑ k, (if j = k then (0:ℝ) else d[X j # -X k]) ≤ m * (m - 1) * D[X; fun _ ↦ hΩ]

Complete declaration

Lean source

Canonical source
Full Lean sourceLean 4
lemma multidist_ruzsa_I_indep {m : } (hm : m  1) {Ω : Type*} (hΩ : MeasureSpace Ω)    [IsProbabilityMeasure (hΩ.volume)] (X : Fin m  Ω  G) (h_indep : iIndepFun X)    (hmes :  j, Measurable (X j)) (hfin :  j, FiniteRange (X j)) :    ∑ j, ∑ k, (if j = k then (0:) else d[X j # -X k])  m * (m - 1) * D[X; fun _  hΩ] := by  have claim1 {j k : Fin m} (h: j  k) : H[X j + X k]  H[∑ i, X i] := by    set S := ∑ i  {j,k}ᶜ, X i    have : ∑ i, X i = X j + X k + S := by      rw [Finset.sum_compl_add_sum {j,k} _, add_comm]      congr      simp [h]    rw [this]    apply (le_max_left _ _).trans (max_entropy_le_entropy_add _ _ _)    · exact Measurable.add (hmes j) (hmes k)    · have :  i  ({j,k}: Finset (Fin m))ᶜ, Measurable (X i) := by        intro i _; exact hmes i      convert Finset.measurable_sum _ this with ω      simp only [Finset.sum_apply,S]    set s : Fin 2  Finset (Fin m) := ![{j,k}, {j,k}ᶜ]    set γ : Fin 2  Type uG := fun _  G    set ϕ : (j:Fin 2)  (({ x // x  s j }  G)  γ j) := fun _ x  ∑ i, x i    have hϕ:  a : Fin 2, Measurable (ϕ a) := by      intro _      convert Finset.measurable_sum _ _ with ω      · simp [γ]        infer_instance      measurability    have h_disjoint: Set.univ.PairwiseDisjoint s := by      simp [Set.PairwiseDisjoint, Set.Pairwise, Fin.forall_fin_two, Function.onFun, s]    have hneq : (0:Fin 2)  (1:Fin 2) := by norm_num    replace h_indep := (h_indep.finsets_comp s h_disjoint hmes ϕ hϕ).indepFun hneq    simp [s,ϕ] at h_indep    convert h_indep with ω ω    · calc        _ = ∑ i  {j,k}, X i ω := by simp [Finset.sum_pair h]        _ = _ := by          convert (Finset.sum_attach _ _).symm          simp    simp only [Finset.sum_apply,S]    exact (Finset.sum_attach _ _).symm  have claim2 (j k : Fin m) (h: j  k) : d[X j # -X k]  H[∑ i, X i] - (H[X j] + H[X k]) / 2 := by    rw [IndepFun.rdist_eq _ (hmes j) _]    · simp only [sub_neg_eq_add, tsub_le_iff_right, entropy_neg (hmes k)]      convert claim1 h using 1      ring    · exact (h_indep.indepFun h).neg_right    exact (hmes k).neg  calc    _  offDiag_sum (fun j k  (H[∑ i, X i] - (H[X j] + H[X k]) / 2)) := offDiag_sum_le _ _ claim2    _ = m * (m - 1) * H[∑ i, X i] - ((m - 1) * ∑ j, H[X j] + (m - 1) * ∑ j, H[X j]) / 2 := by      rw [offDiag_sum_sub, offDiag_sum_div, offDiag_sum_add, offDiag_sum_const hm,        offDiag_sum_left hm, offDiag_sum_right hm]    _ = m * (m - 1) * D[X; fun _  hΩ] := by      rw [multiDist_indep hΩ hmes h_indep, mul_sub ((m:) * (m - 1 : )) _ _]      congr      field_simp      ring