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

Construct good prelim

construct_good_prelim

Plain-language statement

A preliminary endgame bound. In the τ\tau-minimizer setup, let k=d[X1;X2]k=d[X_1;X_2] and let measurable T1,T2,T3T_1,T_2,T_3 satisfy T1+T2+T3=0T_1+T_2+T_3=0. Put δ=I[T1:T2]+I[T2:T3]+I[T3:T1]\delta=I[T_1:T_2]+I[T_2:T_3]+I[T_3:T_1] and c[T1#T2]=d[X10;T1]d[X10;X1]+d[X20;T2]d[X20;X2].c[T_1\#T_2]=d[X_1^0;T_1]-d[X_1^0;X_1]+d[X_2^0;T_2]-d[X_2^0;X_2]. Then kδ+ηc[T1#T2]+η2(I[T1:T3]+I[T2:T3]).k\le\delta+\eta c[T_1\#T_2]+\frac{\eta}{2}\bigl(I[T_1:T_3]+I[T_2:T_3]\bigr).

Exact Lean statement

lemma construct_good_prelim :
    k ≤ δ + p.η * c[T₁ # T₂] + p.η * (I[T₁: T₃] + I[T₂ : T₃])/2

Formal artifact

Lean source

Canonical source
Full Lean sourceLean 4
lemma construct_good_prelim :    k  δ + p.η * c[T₁ # T₂] + p.η * (I[T₁: T₃] + I[T₂ : T₃])/2 := by  let sum1 :  := (Measure.map T₃ ℙ)[fun t  d[T₁; ℙ[|T₃ ⁻¹' {t}] # T₂; ℙ[|T₃ ⁻¹' {t}]]]  let sum2 :  := (Measure.map T₃ ℙ)[fun t  d[p.X₀₁; ℙ # T₁; ℙ[|T₃ ⁻¹' {t}]] - d[p.X₀₁ # X₁]]  let sum3 :  := (Measure.map T₃ ℙ)[fun t  d[p.X₀₂; ℙ # T₂; ℙ[|T₃ ⁻¹' {t}]] - d[p.X₀₂ # X₂]]  let sum4 :  := (Measure.map T₃ ℙ)[fun t  ψ[T₁; ℙ[|T₃ ⁻¹' {t}] # T₂; ℙ[|T₃ ⁻¹' {t}]]]  have hp.η : 0  p.η := by linarith [p.hη]  have hP : IsProbabilityMeasure (Measure.map T₃ ℙ) :=    Measure.isProbabilityMeasure_map hT₃.aemeasurable  have h2T₃ : T₃ = T₁ + T₂ :=    calc T₃ = T₁ + T₂ + T₃ - T₃ := by rw [hT, zero_sub]; simp [ZModModule.neg_eq_self]      _ = T₁ + T₂ := by rw [add_sub_cancel_right]  have h2T₁ : T₁ = T₂ + T₃ := by simp [h2T₃, add_left_comm, ZModModule.add_self]  have h2T₂ : T₂ = T₃ + T₁ := by simp [h2T₁, add_left_comm, ZModModule.add_self]  have h1 : sum1  δ := by    have h1 : sum1  3 * I[T₁ : T₂] + 2 * H[T₃] - H[T₁] - H[T₂] := by      subst h2T₃; exact ent_bsg hT₁ hT₂    have h2 : H[T₂, T₃] = H[T₁, T₂] := by      rw [h2T₃, entropy_add_right', entropy_comm] <;> assumption    have h3 : H[T₁, T₂] = H[T₃, T₁] := by      rw [h2T₃, entropy_add_left, entropy_comm] <;> assumption    simp_rw [mutualInfo_def] at h1 ; linarith  have h2 : p.η * sum2  p.η * (d[p.X₀₁ # T₁] - d[p.X₀₁ # X₁] + I[T₁ : T₃] / 2) := by    have : sum2 = d[p.X₀₁ # T₁ | T₃] - d[p.X₀₁ # X₁] := by      simp only [integral_sub .of_finite .of_finite, integral_const, smul_eq_mul, sum2]      simp [condRuzsaDist'_eq_sum hT₁ hT₃, integral_eq_setIntegral        (FiniteRange.ae_mem_toFinset _ T₃), setIntegral_finset _ .finset,        map_measureReal_apply hT₃ (.singleton _)]    gcongr    linarith [condRuzsaDist_le' ℙ ℙ p.hmeas1 hT₁ hT₃]  have h3 : p.η * sum3  p.η * (d[p.X₀₂ # T₂] - d[p.X₀₂ # X₂] + I[T₂ : T₃] / 2) := by    have : sum3 = d[p.X₀₂ # T₂ | T₃] - d[p.X₀₂ # X₂] := by      simp only [integral_sub .of_finite .of_finite, integral_const, smul_eq_mul, sum3]      simp [condRuzsaDist'_eq_sum hT₂ hT₃,        integral_eq_setIntegral (FiniteRange.ae_mem_toFinset _ T₃),         setIntegral_finset _ .finset,        map_measureReal_apply hT₃ (.singleton _)]    gcongr    linarith [condRuzsaDist_le' ℙ ℙ p.hmeas2 hT₂ hT₃]  have h4 : sum4  δ + p.η * c[T₁ # T₂] + p.η * (I[T₁ : T₃] + I[T₂ : T₃]) / 2 := by    suffices sum4 = sum1 + p.η * (sum2 + sum3) by linarith    simp only [sum1, sum2, sum3, sum4, integral_add .of_finite .of_finite, integral_const_mul]  have hk : k  sum4 := by    suffices (Measure.map T₃ ℙ)[fun _  k]  sum4 by simpa using this    refine integral_mono_ae .of_finite .of_finite <| ae_iff_of_countable.2 fun t ht  ?_    have : IsProbabilityMeasure (ℙ[|T₃ ⁻¹' {t}]) :=      cond_isProbabilityMeasure (by simpa [hT₃] using ht)    dsimp only    linarith only [distance_ge_of_min' (μ := ℙ[|T₃ ⁻¹' {t}]) (μ' := ℙ[|T₃ ⁻¹' {t}]) p h_min hT₁ hT₂]  exact hk.trans h4
Project
Polynomial Freiman-Ruzsa project
License
Apache-2.0
Commit
a177b2e4abe4
Source
PFR/Endgame.lean:352-401

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