Skip to main content
All packages

teorth/PFR

PFR

Repository for formalization of the Polynomial Freiman Ruzsa conjecture (and related results)

Therefore indexed 350 complete source declarations from the exact package revision. Individual authorship and independent verification remain unset.

Research project222 GitHub starsApache-2.023 indexed versionsRepositoryFull history on Reservoir
mathadditive-combinatoricsinformation-theory

Head version

v4.33.0-rc1

a177b2e4abe4b31c8024b9afebe646bf6bb8f91b

Toolchain
leanprover/lean4:v4.33.0-rc1
Revision date
16 Jul 2026
Dependencies
11
Versions
23

External build observation

Exact head commit and toolchain

Reservoir recorded build status passed and test status not observed for commit a177b2e4abe4 with leanprover/lean4:v4.33.0-rc1 on 20 Jul 2026. Therefore did not run this build.

Pin this source in lakefile.lean

require PFR from git "https://github.com/teorth/pfr.git" @ "a177b2e4abe4b31c8024b9afebe646bf6bb8f91b"

Source declarations

350 indexed proofs

Package history

Showing 321 to 340 of 350 declarations.

lemma

mutual_information_le_t_12

We have I[Z_1 : Z_2 | W], I[Z_2 : Z_3 | W], I[Z_1 : Z_3 | W] ≤ 4m^2 η k.

PFR.TorsionEndgame · PFR/TorsionEndgame.lean:70

lemma

mutual_information_le_t_23

Open the record for the exact Lean statement and complete source.

PFR.TorsionEndgame · PFR/TorsionEndgame.lean:103

lemma

mutual_information_le_t_13

Open the record for the exact Lean statement and complete source.

PFR.TorsionEndgame · PFR/TorsionEndgame.lean:167

lemma

Q_ident

Open the record for the exact Lean statement and complete source.

PFR.TorsionEndgame · PFR/TorsionEndgame.lean:226

lemma

Q_dist

Open the record for the exact Lean statement and complete source.

PFR.TorsionEndgame · PFR/TorsionEndgame.lean:251

lemma

Q_indep

Open the record for the exact Lean statement and complete source.

PFR.TorsionEndgame · PFR/TorsionEndgame.lean:276

lemma

entropy_of_W_le

We have \bbH[W](2m1)k+1mi=1m\bbH[Xi]\bbH[W] \leq (2m-1)k + \frac1m \sum_{i=1}^m \bbH[X_i].

PFR.TorsionEndgame · PFR/TorsionEndgame.lean:288

lemma

entropy_of_Z_two_le

We have \bbH[Z2](8m216m+1)k+1mi=1m\bbH[Xi]\bbH[Z_2] \leq (8m^2-16m+1) k + \frac{1}{m} \sum_{i=1}^m \bbH[X_i].

PFR.TorsionEndgame · PFR/TorsionEndgame.lean:330

lemma

mutual_of_W_Z_two_le

We have \bbI[W:Z2]2(m1)k\bbI[W : Z_2] \leq 2(m-1) k.

PFR.TorsionEndgame · PFR/TorsionEndgame.lean:381

lemma

sum_of_conditional_distance_le

We have i=1md[Xi;Z2W]4(m3m2)k\sum_{i=1}^m d[X_i;Z_2|W] \leq 4(m^3-m^2) k.

PFR.TorsionEndgame · PFR/TorsionEndgame.lean:423

lemma

pigeonhole

Open the record for the exact Lean statement and complete source.

PFR.TorsionEndgame · PFR/TorsionEndgame.lean:493

lemma

dist_of_U_add_le

Let GG be an abelian group, let (T1,T2,T3)(T_1,T_2,T_3) be a G3G^3-valued random variable such that T1+T2+T3=0T_1+T_2+T_3=0 holds identically, and write [ \delta := \bbI[T_1 : T_2] + \bbI[T_1 : T_3] + \bbI[T_2 : T_3]. ] Let Y1,,YnY_1,\dots,Y_n be some further GG-valued random variables and let α>0\alpha>0 be a constant. Then there exists a random variable UU such that

\Bigl(2 + \frac{\alpha n}{2} \Bigr) \delta + \alpha \sum_{i=1}^n d[Y_i;T_2].$$

PFR.TorsionEndgame · PFR/TorsionEndgame.lean:526

lemma

k_eq_zero

We have k=0k = 0.

PFR.TorsionEndgame · PFR/TorsionEndgame.lean:621

lemma

dist_of_X_U_H_le

Suppose that GG is a finite abelian group of torsion mm. Suppose that XX is a GG-valued random variable. Then there exists a subgroup HGH \leq G such that [ d[X;U_H] \leq 64 m^3 d[X;X].].

PFR.TorsionEndgame · PFR/TorsionEndgame.lean:710

theorem

rdist_le_of_isUniform_of_card_add_le'

A uniform distribution on a set with doubling constant K has self Rusza distance at most log K.

PFR.TorsionEndgame · PFR/TorsionEndgame.lean:766

lemma

torsion_exists_subgroup_subset_card_le

Every subgroup H of a finite m-torsion abelian group G contains a subgroup H' of order between k and mk, if 0 < k < |H|.

PFR.TorsionEndgame · PFR/TorsionEndgame.lean:918

theorem

torsion_PFR

Suppose that GG is a finite abelian group of torsion mm. If AGA \subset G is non-empty and A+AKA|A+A| \leq K|A|, then AA can be covered by most mK64m3+1mK^{64m^3+1} translates of a subspace HH of GG with HA|H| \leq |A|.

PFR.TorsionEndgame · PFR/TorsionEndgame.lean:962

lemma

wlog_notInCoset

Without loss of generality, one can move (up to translation and embedding) any pair A, B of non-empty sets into a subgroup where they are not in a coset.

PFR.WeakPFR · PFR/WeakPFR.lean:49

lemma

torsion_free_doubling

If G is torsion-free and X, Y are G-valued random variables then d[X; 2Y] ≤ 5d[X; Y].

PFR.WeakPFR · PFR/WeakPFR.lean:92

lemma

app_ent_PFR'

Let G=F2nG=\mathbb{F}_2^n and X, Y be G-valued random variables such that [\mathbb{H}(X)+\mathbb{H}(Y)> (20/\alpha) d[X;Y],] for some α>0\alpha > 0. There is a non-trivial subgroup HGH\leq G such that [\log \lvert H\rvert <(1+\alpha)/2 (\mathbb{H}(X)+\mathbb{H}(Y))] and [\mathbb{H}(\psi(X))+\mathbb{H}(\psi(Y))< \alpha (\mathbb{H}(X)+\mathbb{H}(Y))] where ψ:GG/H\psi:G\to G/H is the natural projection homomorphism.

PFR.WeakPFR · PFR/WeakPFR.lean:241

Static source extraction only. Package code was not executed. Every result keeps its complete declaration, exact file and line range, commit, toolchain, license file, and content hash.