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

Rho PFR conjecture

rho_PFR_conjecture

Plain-language statement

Fix a nonempty finite set AA in an elementary abelian 22-group. For any measurable random variables Y1,Y2Y_1,Y_2, there are a subspace HH and a random variable UU uniformly distributed on HH such that the source's ρ[#A]\rho[\,\cdot\,\#A] functional satisfies 2ρ[U#A]ρ[Y1#A]+ρ[Y2#A]+8d[Y1;Y2]2\rho[U\#A]\le\rho[Y_1\#A]+\rho[Y_2\#A]+8d[Y_1;Y_2].

Exact Lean statement

theorem rho_PFR_conjecture [MeasurableSpace G] [DiscreteMeasurableSpace G]
    (Y₁ Y₂ : Ω → G) (hY₁ : Measurable Y₁) (hY₂ : Measurable Y₂) (A : Finset G) (hA : A.Nonempty) :
    ∃ (H : Submodule (ZMod 2) G) (Ω' : Type uG) (mΩ' : MeasureSpace Ω') (U : Ω' → G),
    IsProbabilityMeasure (ℙ : Measure Ω') ∧ Measurable U ∧
    IsUniform H U ∧ 2 * ρ[U # A] ≤ ρ[Y₁ # A] + ρ[Y₂ # A] + 8 * d[Y₁ # Y₂]

Formal artifact

Lean source

Canonical source
Full Lean sourceLean 4
theorem rho_PFR_conjecture [MeasurableSpace G] [DiscreteMeasurableSpace G]    (Y₁ Y₂ : Ω  G) (hY₁ : Measurable Y₁) (hY₂ : Measurable Y₂) (A : Finset G) (hA : A.Nonempty) :     (H : Submodule (ZMod 2) G) (Ω' : Type uG) (mΩ' : MeasureSpace Ω') (U : Ω'  G),    IsProbabilityMeasure (ℙ : Measure Ω')  Measurable U     IsUniform H U  2 * ρ[U # A]  ρ[Y₁ # A] + ρ[Y₂ # A] + 8 * d[Y₁ # Y₂] := by  obtain Ω', mΩ', X₁, X₂, hX₁, hX₂, hP, htau_min, hdist := phiMinimizer_exists_rdist_eq_zero hA  wlog h : ρ[X₁ # A]  ρ[X₂ # A] generalizing X₁ X₂  · rw [rdist_symm] at hdist    exact this X₂ X₁ hX₂ hX₁ (phiMinimizes_comm htau_min) hdist (by linarith)  -- use for `U` a translate of `X` to make sure that `0` is in its support.  obtain x₀, h₀ :  x₀, ℙ (X₁⁻¹' {x₀})  0 := by    by_contra! h    have A a : (ℙ : Measure Ω').map X₁ {a} = 0 := by      rw [Measure.map_apply hX₁ .of_discrete]      exact h _    have B : (ℙ : Measure Ω').map X₁ = 0 := by      rw [ Measure.sum_smul_dirac:= (ℙ : Measure Ω').map X₁)]      simp [A]    have : IsProbabilityMeasure ((ℙ : Measure Ω').map X₁) :=      isProbabilityMeasure_map hX₁.aemeasurable    exact IsProbabilityMeasure.ne_zero _ B  have h_unif : IsUniform (symmGroup X₁ hX₁) (fun ω  X₁ ω - x₀) := by    have h' : d[X₁ # X₁] = 0 := by      apply le_antisymm _ (rdist_nonneg hX₁ hX₁)      calc        d[X₁ # X₁]  d[X₁ # X₂] + d[X₂ # X₁] := rdist_triangle hX₁ hX₂ hX₁        _ = 0 := by rw [hdist, rdist_symm, hdist, zero_add]    exact isUniform_sub_const_of_rdist_eq_zero hX₁ h' h₀  refine AddSubgroup.toZModSubmodule 2 (symmGroup X₁ hX₁), Ω', by infer_instance,    fun ω  X₁ ω - x₀, by infer_instance, by fun_prop, by exact h_unif, ?_  have J : d[X₁ # X₂] + (1/8) * (ρ[X₁ # A] + ρ[X₂ # A])       d[Y₁ # Y₂] + (1/8) * (ρ[Y₁ # A] + ρ[Y₂ # A]) := by    have Z := le_rdist_of_phiMinimizes htau_min hY₁ hY₂ (μ₁ := ℙ) (μ₂ := ℙ)    linarith  rw [hdist, zero_add] at J  have : ρ[fun ω  X₁ ω - x₀ # A] = ρ[X₁ # A] := by    simp_rw [sub_eq_add_neg, rho_of_translate hX₁ hA]  linarith
Project
Polynomial Freiman-Ruzsa project
License
Apache-2.0
Commit
a177b2e4abe4
Source
PFR/RhoFunctional.lean:1933-1970

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