All proofs
Project-declaredLean 4.33.0-rc1 · mathlib@79d0395a1825

Dist of min eq zero

dist_of_min_eq_zero'

Plain-language statement

If X1,X2X_1, X_2 is a ϕ\phi-minimizer, then d[X1;X2]=0d[X_1;X_2] = 0.

Exact Lean statement

lemma dist_of_min_eq_zero' (hA : A.Nonempty) (hη' : η < 1 / 8) : d[X₁ # X₂] = 0

Formal artifact

Lean source

Canonical source
Full Lean sourceLean 4
lemma dist_of_min_eq_zero' (hA : A.Nonempty) (hη' : η < 1 / 8) : d[X₁ # X₂] = 0 := by  let T₁ := X₁ + X₂  let T₂ := X₁ + X₁'  let T₃ := X₁' + X₂  have hsum : T₁ + T₂ + T₃ = 0 := by    have : T₁ + T₂ + T₃ = 2 • (X₁ + X₁' + X₂) := by simp only [T₁, T₂, T₃]; abel    rwa [ZModModule.char_nsmul_eq_zero 2 (X₁ + X₁' + X₂)] at this  let S := X₁ + X₂ + X₁' + X₂'  have J₁ : k  I₁ + 2 * I₂ + η / 3 *      (ρ[T₁ | T₂, S # A] + ρ[T₂ | T₁, S # A] + ρ[T₁ | T₃, S # A] + ρ[T₃ | T₁, S # A]        + ρ[T₂ | T₃, S # A] + ρ[T₃ | T₂, S # A] - 3 * (ρ[X₁ # A] + ρ[X₂ # A])) := by    have K := dist_le_of_sum_zero_cond' h_min S hsum      (by fun_prop) (by fun_prop) (by fun_prop) (by fun_prop)    have : I[T₂ : T₃ | S] = I₂ := by      rw [condMutualInfo_comm (by fun_prop) (by fun_prop)]      have : X₁ + X₁' = X₁' + X₁ := by abel      convert I₃_eq _ _ _ _ hX₁ hX₂ hX₁' hX₂' h₁ h_indep using 2    linarith  have J₂ : k  I₁ + 2 * I₂ +      η / 3 * (k + d[X₁ # X₁'] + d[X₁ # X₂'] + d[X₂ # X₁'] + d[X₂ # X₂'] + d[X₁' # X₂']) := by    apply J₁.trans    gcongr    have W : X₂ + X₁' = X₁' + X₂ := by abel    have := condRho_sum_le' hX₁ hX₂ hX₁' hX₂' h_indep hA    simp only [W] at this    have : ρ[X₁' # A] = ρ[X₁ # A] := rho_eq_of_identDistrib h₁.symm    have : ρ[X₂' # A] = ρ[X₂ # A] := rho_eq_of_identDistrib h₂.symm    linarith  have J₃ : k  I₁ + 2 * I₂ + η / 3 * (6 * k + I₂ - I₁) := by    apply J₂.trans_eq    congr 2    have : d[X₁ # X₁'] = d[X₁ # X₁] := h₁.symm.rdist_congr_right hX₁.aemeasurable    have : d[X₁ # X₂'] = d[X₁ # X₂] := h₂.symm.rdist_congr_right hX₁.aemeasurable    have : d[X₂ # X₁'] = d[X₁ # X₂] := by      rw [rdist_symm]; exact h₁.symm.rdist_congr_left hX₂.aemeasurable    have : d[X₂ # X₂'] = d[X₂ # X₂] := h₂.symm.rdist_congr_right hX₂.aemeasurable    have : d[X₁' # X₂'] = d[X₁ # X₂] := h₁.symm.rdist_congr h₂.symm    have := rdist_add_rdist_eq h₁ h₂ h_indep hX₁ hX₂ hX₁' hX₂'    linarith  let D := 2 * η * k - I₁  have J₄ : k  8 * η * k - (3 - 10 * η) / (3 * (1 - η)) * D := by    have I₁_eq : I₁ = 2 * η * k - D := by simp only [D]; abel    have : I₂  2 * η * k + η / (1 - η) * D :=      I_two_le hη h_min h₁ h₂ h_indep hX₁ hX₂ hX₁' hX₂' hA (by linarith)    calc    k  I₁ + 2 * I₂ + η / 3 * (6 * k + I₂ - I₁) := J₃    _ = 2 * η * k + I₁ + 2 * I₂ + η / 3 * (I₂ - I₁) := by ring    _  2 * η * k + (2 * η * k - D) + 2 * (2 * η * k + η / (1 - η) * D)        + η / 3 * ((2 * η * k + η / (1 - η) * D) - (2 * η * k - D)) := by      rw [I₁_eq]      gcongr    _ = 8 * η * k - (3 - 10 * η) / (3 * (1 - η)) * D := by      have : 1 - η  0 := ne_of_gt (by linarith)      field_simp      ring  have J₅ : k  8 * η * k - 0 := by    apply J₄.trans    gcongr    have : 0  D := sub_nonneg_of_le (I_one_le hη h_min h₁ h₂ h_indep hX₁ hX₂ hX₁' hX₂' hA)    apply mul_nonneg _ this    exact div_nonneg (by linarith) (by linarith)  have : k  0 := by nlinarith  exact le_antisymm this (rdist_nonneg hX₁ hX₂)
Project
Polynomial Freiman-Ruzsa project
License
Apache-2.0
Commit
a177b2e4abe4
Source
PFR/RhoFunctional.lean:1792-1854

Reuse this declaration

Bring the exact result into your workflow

The import identifies the source module. Your project still needs the pinned package dependency shown on this page.

What this badge means

This completion status comes from the project or community source. It has not yet been represented here as an independent rebuild and axiom audit.

Continue in this project

Related declarations

Project-declaredLean 4.33.0-rc1

Approx hom pfr

approx_hom_pfr

Project documentation

An approximate-homomorphism theorem for finite elementary abelian 22-groups. Let f:GGf:G\to G' and K>0K>0. If at least a proportion K1K^{-1} of pairs (x,y)G2(x,y)\in G^2 satisfy f(x+y)=f(x)+f(y)f(x+y)=f(x)+f(y), then there are an additive homomorphism φ:GG\varphi:G\to G' and a constant cGc\in G' such that f(x)=φ(x)+cf(x)=\varphi(x)+c for at least G/(2144K122)|G|/(2^{144}K^{122}) values of xx.

additive combinatoricsentropyprobability

Source project: Polynomial Freiman-Ruzsa project

Person-level attribution pending.

View proof record
Project-declaredLean 4.33.0-rc1

Better PFR conjecture

better_PFR_conjecture

Plain-language statement

If AF2nA \subset {\bf F}_2^n is finite non-empty with A+AKA|A+A| \leq K|A|, then there exists a subgroup HH of F2n{\bf F}_2^n with HA|H| \leq |A| such that AA can be covered by at most 2K92K^9 translates of HH.

additive combinatoricsentropyprobability

Source project: Polynomial Freiman-Ruzsa project

Person-level attribution pending.

View proof record
Project-declaredLean 4.33.0-rc1

Better PFR conjecture

better_PFR_conjecture'

Project documentation

Polynomial Freiman-Ruzsa theorem with exponent 99, without a finite ambient-group assumption. Let AA be a nonempty finite subset of an elementary abelian 22-group. If A+AKA|A+A|\le K|A|, then there are a finite subspace HH and a finite set cc such that Ac+HA\subseteq c+H, c<2K9|c|<2K^9, and HA|H|\le|A|.

additive combinatoricsentropyprobability

Source project: Polynomial Freiman-Ruzsa project

Person-level attribution pending.

View proof record