combinatorics.simple_graph.regularity.energy
⟷
Mathlib.Combinatorics.SimpleGraph.Regularity.Energy
The following section lists changes to this file in mathlib3 and mathlib4 that occured after the initial port. Most recent changes are shown first. Hovering over a commit will show all commits associated with the same mathlib3 commit.
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(last sync)
Define the increment partition and prove its two crucial properties:
This is all internal to the proof of SRL, so I made most lemmas private
.
Co-authored-by: Bhavik Mehta <bhavikmehta8@gmail.com>
@@ -6,6 +6,7 @@ Authors: Yaël Dillies, Bhavik Mehta
import algebra.big_operators.order
import algebra.module.basic
import combinatorics.simple_graph.density
+import data.rat.big_operators
/-!
# Energy of a partition
@@ -18,6 +19,10 @@ This file defines the energy of a partition.
The energy is the auxiliary quantity that drives the induction process in the proof of Szemerédi's
Regularity Lemma. As long as we do not have a suitable equipartition, we will find a new one that
has an energy greater than the previous one plus some fixed constant.
+
+## References
+
+[Yaël Dillies, Bhavik Mehta, *Formalising Szemerédi’s Regularity Lemma in Lean*][srl_itp]
-/
open finset
@@ -44,4 +49,8 @@ div_le_of_nonneg_of_le_mul (sq_nonneg _) zero_le_one $
... = P.parts.off_diag.card : nat.smul_one_eq_coe _
... ≤ _ : by { rw [off_diag_card, one_mul, ←nat.cast_pow, nat.cast_le, sq], exact tsub_le_self }
+@[simp, norm_cast] lemma coe_energy {𝕜 : Type*} [linear_ordered_field 𝕜] :
+ (P.energy G : 𝕜) = (∑ uv in P.parts.off_diag, G.edge_density uv.1 uv.2 ^ 2) / P.parts.card ^ 2 :=
+by { rw energy, norm_cast }
+
end finpartition
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(first ported)
mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83
@@ -3,7 +3,7 @@ Copyright (c) 2022 Yaël Dillies, Bhavik Mehta. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Yaël Dillies, Bhavik Mehta
-/
-import Algebra.BigOperators.Order
+import Algebra.Order.BigOperators.Group.Finset
import Algebra.Module.Basic
import Combinatorics.SimpleGraph.Density
import Data.Rat.BigOperators
mathlib commit https://github.com/leanprover-community/mathlib/commit/ce64cd319bb6b3e82f31c2d38e79080d377be451
@@ -3,10 +3,10 @@ Copyright (c) 2022 Yaël Dillies, Bhavik Mehta. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Yaël Dillies, Bhavik Mehta
-/
-import Mathbin.Algebra.BigOperators.Order
-import Mathbin.Algebra.Module.Basic
-import Mathbin.Combinatorics.SimpleGraph.Density
-import Mathbin.Data.Rat.BigOperators
+import Algebra.BigOperators.Order
+import Algebra.Module.Basic
+import Combinatorics.SimpleGraph.Density
+import Data.Rat.BigOperators
#align_import combinatorics.simple_graph.regularity.energy from "leanprover-community/mathlib"@"bf7ef0e83e5b7e6c1169e97f055e58a2e4e9d52d"
mathlib commit https://github.com/leanprover-community/mathlib/commit/8ea5598db6caeddde6cb734aa179cc2408dbd345
@@ -2,17 +2,14 @@
Copyright (c) 2022 Yaël Dillies, Bhavik Mehta. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Yaël Dillies, Bhavik Mehta
-
-! This file was ported from Lean 3 source module combinatorics.simple_graph.regularity.energy
-! leanprover-community/mathlib commit bf7ef0e83e5b7e6c1169e97f055e58a2e4e9d52d
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
-/
import Mathbin.Algebra.BigOperators.Order
import Mathbin.Algebra.Module.Basic
import Mathbin.Combinatorics.SimpleGraph.Density
import Mathbin.Data.Rat.BigOperators
+#align_import combinatorics.simple_graph.regularity.energy from "leanprover-community/mathlib"@"bf7ef0e83e5b7e6c1169e97f055e58a2e4e9d52d"
+
/-!
# Energy of a partition
mathlib commit https://github.com/leanprover-community/mathlib/commit/9fb8964792b4237dac6200193a0d533f1b3f7423
@@ -40,16 +40,21 @@ variable {α : Type _} [DecidableEq α] {s : Finset α} (P : Finpartition s) (G
namespace Finpartition
+#print Finpartition.energy /-
/-- The energy of a partition, also known as index. Auxiliary quantity for Szemerédi's regularity
lemma. -/
def energy : ℚ :=
(∑ uv in P.parts.offDiag, G.edgeDensity uv.1 uv.2 ^ 2) / P.parts.card ^ 2
#align finpartition.energy Finpartition.energy
+-/
+#print Finpartition.energy_nonneg /-
theorem energy_nonneg : 0 ≤ P.energy G :=
div_nonneg (Finset.sum_nonneg fun _ _ => sq_nonneg _) <| sq_nonneg _
#align finpartition.energy_nonneg Finpartition.energy_nonneg
+-/
+#print Finpartition.energy_le_one /-
theorem energy_le_one : P.energy G ≤ 1 :=
div_le_of_nonneg_of_le_mul (sq_nonneg _) zero_le_one <|
calc
@@ -59,12 +64,15 @@ theorem energy_le_one : P.energy G ≤ 1 :=
_ = P.parts.offDiag.card := (Nat.smul_one_eq_coe _)
_ ≤ _ := by rw [off_diag_card, one_mul, ← Nat.cast_pow, Nat.cast_le, sq]; exact tsub_le_self
#align finpartition.energy_le_one Finpartition.energy_le_one
+-/
+#print Finpartition.coe_energy /-
@[simp, norm_cast]
theorem coe_energy {𝕜 : Type _} [LinearOrderedField 𝕜] :
(P.energy G : 𝕜) = (∑ uv in P.parts.offDiag, G.edgeDensity uv.1 uv.2 ^ 2) / P.parts.card ^ 2 :=
by rw [energy]; norm_cast
#align finpartition.coe_energy Finpartition.coe_energy
+-/
end Finpartition
mathlib commit https://github.com/leanprover-community/mathlib/commit/a3e83f0fa4391c8740f7d773a7a9b74e311ae2a3
@@ -53,7 +53,7 @@ theorem energy_nonneg : 0 ≤ P.energy G :=
theorem energy_le_one : P.energy G ≤ 1 :=
div_le_of_nonneg_of_le_mul (sq_nonneg _) zero_le_one <|
calc
- (∑ uv in P.parts.offDiag, G.edgeDensity uv.1 uv.2 ^ 2) ≤ P.parts.offDiag.card • 1 :=
+ ∑ uv in P.parts.offDiag, G.edgeDensity uv.1 uv.2 ^ 2 ≤ P.parts.offDiag.card • 1 :=
sum_le_card_nsmul _ _ 1 fun uv _ =>
(sq_le_one_iff <| G.edgeDensity_nonneg _ _).2 <| G.edgeDensity_le_one _ _
_ = P.parts.offDiag.card := (Nat.smul_one_eq_coe _)
mathlib commit https://github.com/leanprover-community/mathlib/commit/7e5137f579de09a059a5ce98f364a04e221aabf0
@@ -58,7 +58,6 @@ theorem energy_le_one : P.energy G ≤ 1 :=
(sq_le_one_iff <| G.edgeDensity_nonneg _ _).2 <| G.edgeDensity_le_one _ _
_ = P.parts.offDiag.card := (Nat.smul_one_eq_coe _)
_ ≤ _ := by rw [off_diag_card, one_mul, ← Nat.cast_pow, Nat.cast_le, sq]; exact tsub_le_self
-
#align finpartition.energy_le_one Finpartition.energy_le_one
@[simp, norm_cast]
mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb
@@ -33,7 +33,7 @@ has an energy greater than the previous one plus some fixed constant.
open Finset
-open BigOperators
+open scoped BigOperators
variable {α : Type _} [DecidableEq α] {s : Finset α} (P : Finpartition s) (G : SimpleGraph α)
[DecidableRel G.Adj]
mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb
@@ -40,34 +40,16 @@ variable {α : Type _} [DecidableEq α] {s : Finset α} (P : Finpartition s) (G
namespace Finpartition
-/- warning: finpartition.energy -> Finpartition.energy is a dubious translation:
-lean 3 declaration is
- forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {s : Finset.{u1} α}, (Finpartition.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s) -> (forall (G : SimpleGraph.{u1} α) [_inst_2 : DecidableRel.{succ u1} α (SimpleGraph.Adj.{u1} α G)], Rat)
-but is expected to have type
- forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {s : Finset.{u1} α}, (Finpartition.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s) -> (forall (G : SimpleGraph.{u1} α) [_inst_2 : DecidableRel.{succ u1} α (SimpleGraph.Adj.{u1} α G)], Rat)
-Case conversion may be inaccurate. Consider using '#align finpartition.energy Finpartition.energyₓ'. -/
/-- The energy of a partition, also known as index. Auxiliary quantity for Szemerédi's regularity
lemma. -/
def energy : ℚ :=
(∑ uv in P.parts.offDiag, G.edgeDensity uv.1 uv.2 ^ 2) / P.parts.card ^ 2
#align finpartition.energy Finpartition.energy
-/- warning: finpartition.energy_nonneg -> Finpartition.energy_nonneg is a dubious translation:
-lean 3 declaration is
- forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {s : Finset.{u1} α} (P : Finpartition.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s) (G : SimpleGraph.{u1} α) [_inst_2 : DecidableRel.{succ u1} α (SimpleGraph.Adj.{u1} α G)], LE.le.{0} Rat Rat.hasLe (OfNat.ofNat.{0} Rat 0 (OfNat.mk.{0} Rat 0 (Zero.zero.{0} Rat Rat.hasZero))) (Finpartition.energy.{u1} α (fun (a : α) (b : α) => _inst_1 a b) s P G (fun (a : α) (b : α) => _inst_2 a b))
-but is expected to have type
- forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {s : Finset.{u1} α} (P : Finpartition.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s) (G : SimpleGraph.{u1} α) [_inst_2 : DecidableRel.{succ u1} α (SimpleGraph.Adj.{u1} α G)], LE.le.{0} Rat Rat.instLERat (OfNat.ofNat.{0} Rat 0 (Rat.instOfNatRat 0)) (Finpartition.energy.{u1} α (fun (a : α) (b : α) => _inst_1 a b) s P G (fun (a : α) (b : α) => _inst_2 a b))
-Case conversion may be inaccurate. Consider using '#align finpartition.energy_nonneg Finpartition.energy_nonnegₓ'. -/
theorem energy_nonneg : 0 ≤ P.energy G :=
div_nonneg (Finset.sum_nonneg fun _ _ => sq_nonneg _) <| sq_nonneg _
#align finpartition.energy_nonneg Finpartition.energy_nonneg
-/- warning: finpartition.energy_le_one -> Finpartition.energy_le_one is a dubious translation:
-lean 3 declaration is
- forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {s : Finset.{u1} α} (P : Finpartition.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s) (G : SimpleGraph.{u1} α) [_inst_2 : DecidableRel.{succ u1} α (SimpleGraph.Adj.{u1} α G)], LE.le.{0} Rat Rat.hasLe (Finpartition.energy.{u1} α (fun (a : α) (b : α) => _inst_1 a b) s P G (fun (a : α) (b : α) => _inst_2 a b)) (OfNat.ofNat.{0} Rat 1 (OfNat.mk.{0} Rat 1 (One.one.{0} Rat Rat.hasOne)))
-but is expected to have type
- forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {s : Finset.{u1} α} (P : Finpartition.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s) (G : SimpleGraph.{u1} α) [_inst_2 : DecidableRel.{succ u1} α (SimpleGraph.Adj.{u1} α G)], LE.le.{0} Rat Rat.instLERat (Finpartition.energy.{u1} α (fun (a : α) (b : α) => _inst_1 a b) s P G (fun (a : α) (b : α) => _inst_2 a b)) (OfNat.ofNat.{0} Rat 1 (Rat.instOfNatRat 1))
-Case conversion may be inaccurate. Consider using '#align finpartition.energy_le_one Finpartition.energy_le_oneₓ'. -/
theorem energy_le_one : P.energy G ≤ 1 :=
div_le_of_nonneg_of_le_mul (sq_nonneg _) zero_le_one <|
calc
@@ -79,12 +61,6 @@ theorem energy_le_one : P.energy G ≤ 1 :=
#align finpartition.energy_le_one Finpartition.energy_le_one
-/- warning: finpartition.coe_energy -> Finpartition.coe_energy is a dubious translation:
-lean 3 declaration is
- forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {s : Finset.{u1} α} (P : Finpartition.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s) (G : SimpleGraph.{u1} α) [_inst_2 : DecidableRel.{succ u1} α (SimpleGraph.Adj.{u1} α G)] {𝕜 : Type.{u2}} [_inst_3 : LinearOrderedField.{u2} 𝕜], Eq.{succ u2} 𝕜 ((fun (a : Type) (b : Type.{u2}) [self : HasLiftT.{1, succ u2} a b] => self.0) Rat 𝕜 (HasLiftT.mk.{1, succ u2} Rat 𝕜 (CoeTCₓ.coe.{1, succ u2} Rat 𝕜 (Rat.castCoe.{u2} 𝕜 (DivisionRing.toHasRatCast.{u2} 𝕜 (Field.toDivisionRing.{u2} 𝕜 (LinearOrderedField.toField.{u2} 𝕜 _inst_3)))))) (Finpartition.energy.{u1} α (fun (a : α) (b : α) => _inst_1 a b) s P G (fun (a : α) (b : α) => _inst_2 a b))) (HDiv.hDiv.{u2, u2, u2} 𝕜 𝕜 𝕜 (instHDiv.{u2} 𝕜 (DivInvMonoid.toHasDiv.{u2} 𝕜 (DivisionRing.toDivInvMonoid.{u2} 𝕜 (Field.toDivisionRing.{u2} 𝕜 (LinearOrderedField.toField.{u2} 𝕜 _inst_3))))) (Finset.sum.{u2, u1} 𝕜 (Prod.{u1, u1} (Finset.{u1} α) (Finset.{u1} α)) (AddCommGroup.toAddCommMonoid.{u2} 𝕜 (OrderedAddCommGroup.toAddCommGroup.{u2} 𝕜 (StrictOrderedRing.toOrderedAddCommGroup.{u2} 𝕜 (LinearOrderedRing.toStrictOrderedRing.{u2} 𝕜 (LinearOrderedCommRing.toLinearOrderedRing.{u2} 𝕜 (LinearOrderedField.toLinearOrderedCommRing.{u2} 𝕜 _inst_3)))))) (Finset.offDiag.{u1} (Finset.{u1} α) (fun (a : Finset.{u1} α) (b : Finset.{u1} α) => Finset.decidableEq.{u1} α (fun (a : α) (b : α) => _inst_1 a b) a b) (Finpartition.parts.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s P)) (fun (uv : Prod.{u1, u1} (Finset.{u1} α) (Finset.{u1} α)) => HPow.hPow.{u2, 0, u2} 𝕜 Nat 𝕜 (instHPow.{u2, 0} 𝕜 Nat (Monoid.Pow.{u2} 𝕜 (Ring.toMonoid.{u2} 𝕜 (StrictOrderedRing.toRing.{u2} 𝕜 (LinearOrderedRing.toStrictOrderedRing.{u2} 𝕜 (LinearOrderedCommRing.toLinearOrderedRing.{u2} 𝕜 (LinearOrderedField.toLinearOrderedCommRing.{u2} 𝕜 _inst_3))))))) ((fun (a : Type) (b : Type.{u2}) [self : HasLiftT.{1, succ u2} a b] => self.0) Rat 𝕜 (HasLiftT.mk.{1, succ u2} Rat 𝕜 (CoeTCₓ.coe.{1, succ u2} Rat 𝕜 (Rat.castCoe.{u2} 𝕜 (DivisionRing.toHasRatCast.{u2} 𝕜 (Field.toDivisionRing.{u2} 𝕜 (LinearOrderedField.toField.{u2} 𝕜 _inst_3)))))) (SimpleGraph.edgeDensity.{u1} α G (fun (a : α) (b : α) => _inst_2 a b) (Prod.fst.{u1, u1} (Finset.{u1} α) (Finset.{u1} α) uv) (Prod.snd.{u1, u1} (Finset.{u1} α) (Finset.{u1} α) uv))) (OfNat.ofNat.{0} Nat 2 (OfNat.mk.{0} Nat 2 (bit0.{0} Nat Nat.hasAdd (One.one.{0} Nat Nat.hasOne)))))) (HPow.hPow.{u2, 0, u2} 𝕜 Nat 𝕜 (instHPow.{u2, 0} 𝕜 Nat (Monoid.Pow.{u2} 𝕜 (Ring.toMonoid.{u2} 𝕜 (StrictOrderedRing.toRing.{u2} 𝕜 (LinearOrderedRing.toStrictOrderedRing.{u2} 𝕜 (LinearOrderedCommRing.toLinearOrderedRing.{u2} 𝕜 (LinearOrderedField.toLinearOrderedCommRing.{u2} 𝕜 _inst_3))))))) ((fun (a : Type) (b : Type.{u2}) [self : HasLiftT.{1, succ u2} a b] => self.0) Nat 𝕜 (HasLiftT.mk.{1, succ u2} Nat 𝕜 (CoeTCₓ.coe.{1, succ u2} Nat 𝕜 (Nat.castCoe.{u2} 𝕜 (AddMonoidWithOne.toNatCast.{u2} 𝕜 (AddGroupWithOne.toAddMonoidWithOne.{u2} 𝕜 (AddCommGroupWithOne.toAddGroupWithOne.{u2} 𝕜 (Ring.toAddCommGroupWithOne.{u2} 𝕜 (StrictOrderedRing.toRing.{u2} 𝕜 (LinearOrderedRing.toStrictOrderedRing.{u2} 𝕜 (LinearOrderedCommRing.toLinearOrderedRing.{u2} 𝕜 (LinearOrderedField.toLinearOrderedCommRing.{u2} 𝕜 _inst_3))))))))))) (Finset.card.{u1} (Finset.{u1} α) (Finpartition.parts.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s P))) (OfNat.ofNat.{0} Nat 2 (OfNat.mk.{0} Nat 2 (bit0.{0} Nat Nat.hasAdd (One.one.{0} Nat Nat.hasOne))))))
-but is expected to have type
- forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {s : Finset.{u1} α} (P : Finpartition.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s) (G : SimpleGraph.{u1} α) [_inst_2 : DecidableRel.{succ u1} α (SimpleGraph.Adj.{u1} α G)] {𝕜 : Type.{u2}} [_inst_3 : LinearOrderedField.{u2} 𝕜], Eq.{succ u2} 𝕜 (Rat.cast.{u2} 𝕜 (LinearOrderedField.toRatCast.{u2} 𝕜 _inst_3) (Finpartition.energy.{u1} α (fun (a : α) (b : α) => _inst_1 a b) s P G (fun (a : α) (b : α) => _inst_2 a b))) (HDiv.hDiv.{u2, u2, u2} 𝕜 𝕜 𝕜 (instHDiv.{u2} 𝕜 (LinearOrderedField.toDiv.{u2} 𝕜 _inst_3)) (Rat.cast.{u2} 𝕜 (LinearOrderedField.toRatCast.{u2} 𝕜 _inst_3) (Finset.sum.{0, u1} Rat (Prod.{u1, u1} (Finset.{u1} α) (Finset.{u1} α)) Rat.addCommMonoid (Finset.offDiag.{u1} (Finset.{u1} α) (fun (a : Finset.{u1} α) (b : Finset.{u1} α) => Finset.decidableEq.{u1} α (fun (a : α) (b : α) => _inst_1 a b) a b) (Finpartition.parts.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s P)) (fun (uv : Prod.{u1, u1} (Finset.{u1} α) (Finset.{u1} α)) => HPow.hPow.{0, 0, 0} Rat Nat Rat (instHPow.{0, 0} Rat Nat (Monoid.Pow.{0} Rat Rat.monoid)) (SimpleGraph.edgeDensity.{u1} α G (fun (a : α) (b : α) => _inst_2 a b) (Prod.fst.{u1, u1} (Finset.{u1} α) (Finset.{u1} α) uv) (Prod.snd.{u1, u1} (Finset.{u1} α) (Finset.{u1} α) uv)) (OfNat.ofNat.{0} Nat 2 (instOfNatNat 2))))) (Rat.cast.{u2} 𝕜 (LinearOrderedField.toRatCast.{u2} 𝕜 _inst_3) (HPow.hPow.{0, 0, 0} Rat Nat Rat (instHPow.{0, 0} Rat Nat (Monoid.Pow.{0} Rat Rat.monoid)) (Nat.cast.{0} Rat (Semiring.toNatCast.{0} Rat Rat.semiring) (Finset.card.{u1} (Finset.{u1} α) (Finpartition.parts.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s P))) (OfNat.ofNat.{0} Nat 2 (instOfNatNat 2)))))
-Case conversion may be inaccurate. Consider using '#align finpartition.coe_energy Finpartition.coe_energyₓ'. -/
@[simp, norm_cast]
theorem coe_energy {𝕜 : Type _} [LinearOrderedField 𝕜] :
(P.energy G : 𝕜) = (∑ uv in P.parts.offDiag, G.edgeDensity uv.1 uv.2 ^ 2) / P.parts.card ^ 2 :=
mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb
@@ -75,9 +75,7 @@ theorem energy_le_one : P.energy G ≤ 1 :=
sum_le_card_nsmul _ _ 1 fun uv _ =>
(sq_le_one_iff <| G.edgeDensity_nonneg _ _).2 <| G.edgeDensity_le_one _ _
_ = P.parts.offDiag.card := (Nat.smul_one_eq_coe _)
- _ ≤ _ := by
- rw [off_diag_card, one_mul, ← Nat.cast_pow, Nat.cast_le, sq]
- exact tsub_le_self
+ _ ≤ _ := by rw [off_diag_card, one_mul, ← Nat.cast_pow, Nat.cast_le, sq]; exact tsub_le_self
#align finpartition.energy_le_one Finpartition.energy_le_one
@@ -90,9 +88,7 @@ Case conversion may be inaccurate. Consider using '#align finpartition.coe_energ
@[simp, norm_cast]
theorem coe_energy {𝕜 : Type _} [LinearOrderedField 𝕜] :
(P.energy G : 𝕜) = (∑ uv in P.parts.offDiag, G.edgeDensity uv.1 uv.2 ^ 2) / P.parts.card ^ 2 :=
- by
- rw [energy]
- norm_cast
+ by rw [energy]; norm_cast
#align finpartition.coe_energy Finpartition.coe_energy
end Finpartition
mathlib commit https://github.com/leanprover-community/mathlib/commit/75e7fca56381d056096ce5d05e938f63a6567828
@@ -81,6 +81,12 @@ theorem energy_le_one : P.energy G ≤ 1 :=
#align finpartition.energy_le_one Finpartition.energy_le_one
+/- warning: finpartition.coe_energy -> Finpartition.coe_energy is a dubious translation:
+lean 3 declaration is
+ forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {s : Finset.{u1} α} (P : Finpartition.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s) (G : SimpleGraph.{u1} α) [_inst_2 : DecidableRel.{succ u1} α (SimpleGraph.Adj.{u1} α G)] {𝕜 : Type.{u2}} [_inst_3 : LinearOrderedField.{u2} 𝕜], Eq.{succ u2} 𝕜 ((fun (a : Type) (b : Type.{u2}) [self : HasLiftT.{1, succ u2} a b] => self.0) Rat 𝕜 (HasLiftT.mk.{1, succ u2} Rat 𝕜 (CoeTCₓ.coe.{1, succ u2} Rat 𝕜 (Rat.castCoe.{u2} 𝕜 (DivisionRing.toHasRatCast.{u2} 𝕜 (Field.toDivisionRing.{u2} 𝕜 (LinearOrderedField.toField.{u2} 𝕜 _inst_3)))))) (Finpartition.energy.{u1} α (fun (a : α) (b : α) => _inst_1 a b) s P G (fun (a : α) (b : α) => _inst_2 a b))) (HDiv.hDiv.{u2, u2, u2} 𝕜 𝕜 𝕜 (instHDiv.{u2} 𝕜 (DivInvMonoid.toHasDiv.{u2} 𝕜 (DivisionRing.toDivInvMonoid.{u2} 𝕜 (Field.toDivisionRing.{u2} 𝕜 (LinearOrderedField.toField.{u2} 𝕜 _inst_3))))) (Finset.sum.{u2, u1} 𝕜 (Prod.{u1, u1} (Finset.{u1} α) (Finset.{u1} α)) (AddCommGroup.toAddCommMonoid.{u2} 𝕜 (OrderedAddCommGroup.toAddCommGroup.{u2} 𝕜 (StrictOrderedRing.toOrderedAddCommGroup.{u2} 𝕜 (LinearOrderedRing.toStrictOrderedRing.{u2} 𝕜 (LinearOrderedCommRing.toLinearOrderedRing.{u2} 𝕜 (LinearOrderedField.toLinearOrderedCommRing.{u2} 𝕜 _inst_3)))))) (Finset.offDiag.{u1} (Finset.{u1} α) (fun (a : Finset.{u1} α) (b : Finset.{u1} α) => Finset.decidableEq.{u1} α (fun (a : α) (b : α) => _inst_1 a b) a b) (Finpartition.parts.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s P)) (fun (uv : Prod.{u1, u1} (Finset.{u1} α) (Finset.{u1} α)) => HPow.hPow.{u2, 0, u2} 𝕜 Nat 𝕜 (instHPow.{u2, 0} 𝕜 Nat (Monoid.Pow.{u2} 𝕜 (Ring.toMonoid.{u2} 𝕜 (StrictOrderedRing.toRing.{u2} 𝕜 (LinearOrderedRing.toStrictOrderedRing.{u2} 𝕜 (LinearOrderedCommRing.toLinearOrderedRing.{u2} 𝕜 (LinearOrderedField.toLinearOrderedCommRing.{u2} 𝕜 _inst_3))))))) ((fun (a : Type) (b : Type.{u2}) [self : HasLiftT.{1, succ u2} a b] => self.0) Rat 𝕜 (HasLiftT.mk.{1, succ u2} Rat 𝕜 (CoeTCₓ.coe.{1, succ u2} Rat 𝕜 (Rat.castCoe.{u2} 𝕜 (DivisionRing.toHasRatCast.{u2} 𝕜 (Field.toDivisionRing.{u2} 𝕜 (LinearOrderedField.toField.{u2} 𝕜 _inst_3)))))) (SimpleGraph.edgeDensity.{u1} α G (fun (a : α) (b : α) => _inst_2 a b) (Prod.fst.{u1, u1} (Finset.{u1} α) (Finset.{u1} α) uv) (Prod.snd.{u1, u1} (Finset.{u1} α) (Finset.{u1} α) uv))) (OfNat.ofNat.{0} Nat 2 (OfNat.mk.{0} Nat 2 (bit0.{0} Nat Nat.hasAdd (One.one.{0} Nat Nat.hasOne)))))) (HPow.hPow.{u2, 0, u2} 𝕜 Nat 𝕜 (instHPow.{u2, 0} 𝕜 Nat (Monoid.Pow.{u2} 𝕜 (Ring.toMonoid.{u2} 𝕜 (StrictOrderedRing.toRing.{u2} 𝕜 (LinearOrderedRing.toStrictOrderedRing.{u2} 𝕜 (LinearOrderedCommRing.toLinearOrderedRing.{u2} 𝕜 (LinearOrderedField.toLinearOrderedCommRing.{u2} 𝕜 _inst_3))))))) ((fun (a : Type) (b : Type.{u2}) [self : HasLiftT.{1, succ u2} a b] => self.0) Nat 𝕜 (HasLiftT.mk.{1, succ u2} Nat 𝕜 (CoeTCₓ.coe.{1, succ u2} Nat 𝕜 (Nat.castCoe.{u2} 𝕜 (AddMonoidWithOne.toNatCast.{u2} 𝕜 (AddGroupWithOne.toAddMonoidWithOne.{u2} 𝕜 (AddCommGroupWithOne.toAddGroupWithOne.{u2} 𝕜 (Ring.toAddCommGroupWithOne.{u2} 𝕜 (StrictOrderedRing.toRing.{u2} 𝕜 (LinearOrderedRing.toStrictOrderedRing.{u2} 𝕜 (LinearOrderedCommRing.toLinearOrderedRing.{u2} 𝕜 (LinearOrderedField.toLinearOrderedCommRing.{u2} 𝕜 _inst_3))))))))))) (Finset.card.{u1} (Finset.{u1} α) (Finpartition.parts.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s P))) (OfNat.ofNat.{0} Nat 2 (OfNat.mk.{0} Nat 2 (bit0.{0} Nat Nat.hasAdd (One.one.{0} Nat Nat.hasOne))))))
+but is expected to have type
+ forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {s : Finset.{u1} α} (P : Finpartition.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s) (G : SimpleGraph.{u1} α) [_inst_2 : DecidableRel.{succ u1} α (SimpleGraph.Adj.{u1} α G)] {𝕜 : Type.{u2}} [_inst_3 : LinearOrderedField.{u2} 𝕜], Eq.{succ u2} 𝕜 (Rat.cast.{u2} 𝕜 (LinearOrderedField.toRatCast.{u2} 𝕜 _inst_3) (Finpartition.energy.{u1} α (fun (a : α) (b : α) => _inst_1 a b) s P G (fun (a : α) (b : α) => _inst_2 a b))) (HDiv.hDiv.{u2, u2, u2} 𝕜 𝕜 𝕜 (instHDiv.{u2} 𝕜 (LinearOrderedField.toDiv.{u2} 𝕜 _inst_3)) (Rat.cast.{u2} 𝕜 (LinearOrderedField.toRatCast.{u2} 𝕜 _inst_3) (Finset.sum.{0, u1} Rat (Prod.{u1, u1} (Finset.{u1} α) (Finset.{u1} α)) Rat.addCommMonoid (Finset.offDiag.{u1} (Finset.{u1} α) (fun (a : Finset.{u1} α) (b : Finset.{u1} α) => Finset.decidableEq.{u1} α (fun (a : α) (b : α) => _inst_1 a b) a b) (Finpartition.parts.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s P)) (fun (uv : Prod.{u1, u1} (Finset.{u1} α) (Finset.{u1} α)) => HPow.hPow.{0, 0, 0} Rat Nat Rat (instHPow.{0, 0} Rat Nat (Monoid.Pow.{0} Rat Rat.monoid)) (SimpleGraph.edgeDensity.{u1} α G (fun (a : α) (b : α) => _inst_2 a b) (Prod.fst.{u1, u1} (Finset.{u1} α) (Finset.{u1} α) uv) (Prod.snd.{u1, u1} (Finset.{u1} α) (Finset.{u1} α) uv)) (OfNat.ofNat.{0} Nat 2 (instOfNatNat 2))))) (Rat.cast.{u2} 𝕜 (LinearOrderedField.toRatCast.{u2} 𝕜 _inst_3) (HPow.hPow.{0, 0, 0} Rat Nat Rat (instHPow.{0, 0} Rat Nat (Monoid.Pow.{0} Rat Rat.monoid)) (Nat.cast.{0} Rat (Semiring.toNatCast.{0} Rat Rat.semiring) (Finset.card.{u1} (Finset.{u1} α) (Finpartition.parts.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s P))) (OfNat.ofNat.{0} Nat 2 (instOfNatNat 2)))))
+Case conversion may be inaccurate. Consider using '#align finpartition.coe_energy Finpartition.coe_energyₓ'. -/
@[simp, norm_cast]
theorem coe_energy {𝕜 : Type _} [LinearOrderedField 𝕜] :
(P.energy G : 𝕜) = (∑ uv in P.parts.offDiag, G.edgeDensity uv.1 uv.2 ^ 2) / P.parts.card ^ 2 :=
mathlib commit https://github.com/leanprover-community/mathlib/commit/33c67ae661dd8988516ff7f247b0be3018cdd952
@@ -4,13 +4,14 @@ Released under Apache 2.0 license as described in the file LICENSE.
Authors: Yaël Dillies, Bhavik Mehta
! This file was ported from Lean 3 source module combinatorics.simple_graph.regularity.energy
-! leanprover-community/mathlib commit f47581155c818e6361af4e4fda60d27d020c226b
+! leanprover-community/mathlib commit bf7ef0e83e5b7e6c1169e97f055e58a2e4e9d52d
! Please do not edit these lines, except to modify the commit id
! if you have ported upstream changes.
-/
import Mathbin.Algebra.BigOperators.Order
import Mathbin.Algebra.Module.Basic
import Mathbin.Combinatorics.SimpleGraph.Density
+import Mathbin.Data.Rat.BigOperators
/-!
# Energy of a partition
@@ -23,6 +24,10 @@ This file defines the energy of a partition.
The energy is the auxiliary quantity that drives the induction process in the proof of Szemerédi's
Regularity Lemma. As long as we do not have a suitable equipartition, we will find a new one that
has an energy greater than the previous one plus some fixed constant.
+
+## References
+
+[Yaël Dillies, Bhavik Mehta, *Formalising Szemerédi’s Regularity Lemma in Lean*][srl_itp]
-/
@@ -76,5 +81,13 @@ theorem energy_le_one : P.energy G ≤ 1 :=
#align finpartition.energy_le_one Finpartition.energy_le_one
+@[simp, norm_cast]
+theorem coe_energy {𝕜 : Type _} [LinearOrderedField 𝕜] :
+ (P.energy G : 𝕜) = (∑ uv in P.parts.offDiag, G.edgeDensity uv.1 uv.2 ^ 2) / P.parts.card ^ 2 :=
+ by
+ rw [energy]
+ norm_cast
+#align finpartition.coe_energy Finpartition.coe_energy
+
end Finpartition
mathlib commit https://github.com/leanprover-community/mathlib/commit/21e3562c5e12d846c7def5eff8cdbc520d7d4936
@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
Authors: Yaël Dillies, Bhavik Mehta
! This file was ported from Lean 3 source module combinatorics.simple_graph.regularity.energy
-! leanprover-community/mathlib commit f7707875544ef1f81b32cb68c79e0e24e45a0e76
+! leanprover-community/mathlib commit f47581155c818e6361af4e4fda60d27d020c226b
! Please do not edit these lines, except to modify the commit id
! if you have ported upstream changes.
-/
@@ -15,6 +15,9 @@ import Mathbin.Combinatorics.SimpleGraph.Density
/-!
# Energy of a partition
+> THIS FILE IS SYNCHRONIZED WITH MATHLIB4.
+> Any changes to this file require a corresponding PR to mathlib4.
+
This file defines the energy of a partition.
The energy is the auxiliary quantity that drives the induction process in the proof of Szemerédi's
mathlib commit https://github.com/leanprover-community/mathlib/commit/195fcd60ff2bfe392543bceb0ec2adcdb472db4c
@@ -32,16 +32,34 @@ variable {α : Type _} [DecidableEq α] {s : Finset α} (P : Finpartition s) (G
namespace Finpartition
+/- warning: finpartition.energy -> Finpartition.energy is a dubious translation:
+lean 3 declaration is
+ forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {s : Finset.{u1} α}, (Finpartition.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s) -> (forall (G : SimpleGraph.{u1} α) [_inst_2 : DecidableRel.{succ u1} α (SimpleGraph.Adj.{u1} α G)], Rat)
+but is expected to have type
+ forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {s : Finset.{u1} α}, (Finpartition.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s) -> (forall (G : SimpleGraph.{u1} α) [_inst_2 : DecidableRel.{succ u1} α (SimpleGraph.Adj.{u1} α G)], Rat)
+Case conversion may be inaccurate. Consider using '#align finpartition.energy Finpartition.energyₓ'. -/
/-- The energy of a partition, also known as index. Auxiliary quantity for Szemerédi's regularity
lemma. -/
def energy : ℚ :=
(∑ uv in P.parts.offDiag, G.edgeDensity uv.1 uv.2 ^ 2) / P.parts.card ^ 2
#align finpartition.energy Finpartition.energy
+/- warning: finpartition.energy_nonneg -> Finpartition.energy_nonneg is a dubious translation:
+lean 3 declaration is
+ forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {s : Finset.{u1} α} (P : Finpartition.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s) (G : SimpleGraph.{u1} α) [_inst_2 : DecidableRel.{succ u1} α (SimpleGraph.Adj.{u1} α G)], LE.le.{0} Rat Rat.hasLe (OfNat.ofNat.{0} Rat 0 (OfNat.mk.{0} Rat 0 (Zero.zero.{0} Rat Rat.hasZero))) (Finpartition.energy.{u1} α (fun (a : α) (b : α) => _inst_1 a b) s P G (fun (a : α) (b : α) => _inst_2 a b))
+but is expected to have type
+ forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {s : Finset.{u1} α} (P : Finpartition.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s) (G : SimpleGraph.{u1} α) [_inst_2 : DecidableRel.{succ u1} α (SimpleGraph.Adj.{u1} α G)], LE.le.{0} Rat Rat.instLERat (OfNat.ofNat.{0} Rat 0 (Rat.instOfNatRat 0)) (Finpartition.energy.{u1} α (fun (a : α) (b : α) => _inst_1 a b) s P G (fun (a : α) (b : α) => _inst_2 a b))
+Case conversion may be inaccurate. Consider using '#align finpartition.energy_nonneg Finpartition.energy_nonnegₓ'. -/
theorem energy_nonneg : 0 ≤ P.energy G :=
div_nonneg (Finset.sum_nonneg fun _ _ => sq_nonneg _) <| sq_nonneg _
#align finpartition.energy_nonneg Finpartition.energy_nonneg
+/- warning: finpartition.energy_le_one -> Finpartition.energy_le_one is a dubious translation:
+lean 3 declaration is
+ forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {s : Finset.{u1} α} (P : Finpartition.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s) (G : SimpleGraph.{u1} α) [_inst_2 : DecidableRel.{succ u1} α (SimpleGraph.Adj.{u1} α G)], LE.le.{0} Rat Rat.hasLe (Finpartition.energy.{u1} α (fun (a : α) (b : α) => _inst_1 a b) s P G (fun (a : α) (b : α) => _inst_2 a b)) (OfNat.ofNat.{0} Rat 1 (OfNat.mk.{0} Rat 1 (One.one.{0} Rat Rat.hasOne)))
+but is expected to have type
+ forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {s : Finset.{u1} α} (P : Finpartition.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s) (G : SimpleGraph.{u1} α) [_inst_2 : DecidableRel.{succ u1} α (SimpleGraph.Adj.{u1} α G)], LE.le.{0} Rat Rat.instLERat (Finpartition.energy.{u1} α (fun (a : α) (b : α) => _inst_1 a b) s P G (fun (a : α) (b : α) => _inst_2 a b)) (OfNat.ofNat.{0} Rat 1 (Rat.instOfNatRat 1))
+Case conversion may be inaccurate. Consider using '#align finpartition.energy_le_one Finpartition.energy_le_oneₓ'. -/
theorem energy_le_one : P.energy G ≤ 1 :=
div_le_of_nonneg_of_le_mul (sq_nonneg _) zero_le_one <|
calc
mathlib commit https://github.com/leanprover-community/mathlib/commit/4c586d291f189eecb9d00581aeb3dd998ac34442
@@ -48,7 +48,7 @@ theorem energy_le_one : P.energy G ≤ 1 :=
(∑ uv in P.parts.offDiag, G.edgeDensity uv.1 uv.2 ^ 2) ≤ P.parts.offDiag.card • 1 :=
sum_le_card_nsmul _ _ 1 fun uv _ =>
(sq_le_one_iff <| G.edgeDensity_nonneg _ _).2 <| G.edgeDensity_le_one _ _
- _ = P.parts.offDiag.card := Nat.smul_one_eq_coe _
+ _ = P.parts.offDiag.card := (Nat.smul_one_eq_coe _)
_ ≤ _ := by
rw [off_diag_card, one_mul, ← Nat.cast_pow, Nat.cast_le, sq]
exact tsub_le_self
mathlib commit https://github.com/leanprover-community/mathlib/commit/bd9851ca476957ea4549eb19b40e7b5ade9428cc
Similar to #12486, which did this for Algebra.Algebra.Basic
.
Splits Algebra.Module.Defs
off Algebra.Module.Basic
. Most imports only need the Defs file, which has significantly smaller imports. The remaining Algebra.Module.Basic
is now a grab-bag of unrelated results, and should probably be split further or rehomed.
This is mostly motivated by the wasted effort during minimization upon encountering Algebra.Module.Basic.
Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Ruben Van de Velde <65514131+Ruben-VandeVelde@users.noreply.github.com>
@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
Authors: Yaël Dillies, Bhavik Mehta
-/
import Mathlib.Algebra.GroupPower.Order
-import Mathlib.Algebra.Module.Basic
+import Mathlib.Algebra.Module.Defs
import Mathlib.Algebra.Order.BigOperators.Group.Finset
import Mathlib.Combinatorics.SimpleGraph.Density
import Mathlib.Data.Rat.BigOperators
@@ -51,7 +51,7 @@ theorem energy_le_one : P.energy G ≤ 1 :=
∑ uv in P.parts.offDiag, G.edgeDensity uv.1 uv.2 ^ 2 ≤ P.parts.offDiag.card • (1 : ℚ) :=
sum_le_card_nsmul _ _ 1 fun uv _ =>
(sq_le_one_iff <| G.edgeDensity_nonneg _ _).2 <| G.edgeDensity_le_one _ _
- _ = P.parts.offDiag.card := (Nat.smul_one_eq_coe _)
+ _ = P.parts.offDiag.card := Nat.smul_one_eq_coe _
_ ≤ _ := by
rw [offDiag_card, one_mul]
norm_cast
Take the content of
Algebra.BigOperators.List.Basic
Algebra.BigOperators.List.Lemmas
Algebra.BigOperators.Multiset.Basic
Algebra.BigOperators.Multiset.Lemmas
Algebra.BigOperators.Multiset.Order
Algebra.BigOperators.Order
and sort it into six files:
Algebra.Order.BigOperators.Group.List
. I credit Yakov for https://github.com/leanprover-community/mathlib/pull/8543.Algebra.Order.BigOperators.Group.Multiset
. Copyright inherited from Algebra.BigOperators.Multiset.Order
.Algebra.Order.BigOperators.Group.Finset
. Copyright inherited from Algebra.BigOperators.Order
.Algebra.Order.BigOperators.Ring.List
. I credit Stuart for https://github.com/leanprover-community/mathlib/pull/10184.Algebra.Order.BigOperators.Ring.Multiset
. I credit Ruben for https://github.com/leanprover-community/mathlib/pull/8787.Algebra.Order.BigOperators.Ring.Finset
. I credit Floris for https://github.com/leanprover-community/mathlib/pull/1294.Here are the design decisions at play:
Data.Nat.Order.Basic
in a few List
files.Algebra.Order.BigOperators
instead of Algebra.BigOperators.Order
because algebraic order theory is more of a theory than big operators algebra. Another reason is that algebraic order theory is the only way to mix pure order and pure algebra, while there are more ways to mix pure finiteness and pure algebra than just big operators.Algebra.Order.BigOperators.Group
should be additivisable (except a few Nat
- or Int
-specific lemmas). In contrast, things under Algebra.Order.BigOperators.Ring
are more prone to having heavy imports.List
vs Multiset
vs Finset
. This is not strictly necessary, and can be relaxed in cases where there aren't that many lemmas to be had. As an example, I could split out the AbsoluteValue
lemmas from Algebra.Order.BigOperators.Ring.Finset
to a file Algebra.Order.BigOperators.Ring.AbsoluteValue
and it could stay this way until too many lemmas are in this file (or a split is needed for import reasons), in which case we would need files Algebra.Order.BigOperators.Ring.AbsoluteValue.Finset
, Algebra.Order.BigOperators.Ring.AbsoluteValue.Multiset
, etc...Finsupp
big operator and finprod
/finsum
order lemmas also belong in Algebra.Order.BigOperators
. I haven't done so in this PR because the diff is big enough like that.@@ -3,9 +3,9 @@ Copyright (c) 2022 Yaël Dillies, Bhavik Mehta. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Yaël Dillies, Bhavik Mehta
-/
-import Mathlib.Algebra.BigOperators.Order
import Mathlib.Algebra.GroupPower.Order
import Mathlib.Algebra.Module.Basic
+import Mathlib.Algebra.Order.BigOperators.Group.Finset
import Mathlib.Combinatorics.SimpleGraph.Density
import Mathlib.Data.Rat.BigOperators
refine
s (#10762)
I replaced a few "terminal" refine/refine'
s with exact
.
The strategy was very simple-minded: essentially any refine
whose following line had smaller indentation got replaced by exact
and then I cleaned up the mess.
This PR certainly leaves some further terminal refine
s, but maybe the current change is beneficial.
@@ -42,7 +42,7 @@ def energy : ℚ :=
#align finpartition.energy Finpartition.energy
theorem energy_nonneg : 0 ≤ P.energy G := by
- refine' div_nonneg (Finset.sum_nonneg fun _ _ => sq_nonneg _) <| sq_nonneg _
+ exact div_nonneg (Finset.sum_nonneg fun _ _ => sq_nonneg _) <| sq_nonneg _
#align finpartition.energy_nonneg Finpartition.energy_nonneg
theorem energy_le_one : P.energy G ≤ 1 :=
positivity
extensions (#10140)
The goal here is to have access to positivity
earlier in the import hierarchy
@@ -4,6 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
Authors: Yaël Dillies, Bhavik Mehta
-/
import Mathlib.Algebra.BigOperators.Order
+import Mathlib.Algebra.GroupPower.Order
import Mathlib.Algebra.Module.Basic
import Mathlib.Combinatorics.SimpleGraph.Density
import Mathlib.Data.Rat.BigOperators
This is the supremum of
along with some minor fixes from failures on nightly-testing as Mathlib master
is merged into it.
Note that some PRs for changes that are already compatible with the current toolchain and will be necessary have already been split out: #8380.
I am hopeful that in future we will be able to progressively merge adaptation PRs into a bump/v4.X.0
branch, so we never end up with a "big merge" like this. However one of these adaptation PRs (#8056) predates my new scheme for combined CI, and it wasn't possible to keep that PR viable in the meantime.
In particular this includes adjustments for the Lean PRs
We can get rid of all the
local macro_rules | `($x ^ $y) => `(HPow.hPow $x $y) -- Porting note: See issue [lean4#2220](https://github.com/leanprover/lean4/pull/2220)
macros across Mathlib (and in any projects that want to write natural number powers of reals).
Changes the default behaviour of simp
to (config := {decide := false})
. This makes simp
(and consequentially norm_num
) less powerful, but also more consistent, and less likely to blow up in long failures. This requires a variety of changes: changing some previously by simp
or norm_num
to decide
or rfl
, or adding (config := {decide := true})
.
This changed the behaviour of simp
so that simp [f]
will only unfold "fully applied" occurrences of f
. The old behaviour can be recovered with simp (config := { unfoldPartialApp := true })
. We may in future add a syntax for this, e.g. simp [!f]
; please provide feedback! In the meantime, we have made the following changes:
(config := { unfoldPartialApp := true })
in some places, to recover the old behaviour@[eqns]
to manually adjust the equation lemmas for a particular definition, recovering the old behaviour just for that definition. See #8371, where we do this for Function.comp
and Function.flip
.This change in Lean may require further changes down the line (e.g. adding the !f
syntax, and/or upstreaming the special treatment for Function.comp
and Function.flip
, and/or removing this special treatment). Please keep an open and skeptical mind about these changes!
Co-authored-by: leanprover-community-mathlib4-bot <leanprover-community-mathlib4-bot@users.noreply.github.com> Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Eric Wieser <wieser.eric@gmail.com> Co-authored-by: Mauricio Collares <mauricio@collares.org>
@@ -32,8 +32,6 @@ open BigOperators
variable {α : Type*} [DecidableEq α] {s : Finset α} (P : Finpartition s) (G : SimpleGraph α)
[DecidableRel G.Adj]
-local macro_rules | `($x ^ $y) => `(HPow.hPow $x $y) -- Porting note: See issue lean4#2220
-
namespace Finpartition
/-- The energy of a partition, also known as index. Auxiliary quantity for Szemerédi's regularity
Type _
and Sort _
(#6499)
We remove all possible occurences of Type _
and Sort _
in favor of Type*
and Sort*
.
This has nice performance benefits.
@@ -29,7 +29,7 @@ open Finset
open BigOperators
-variable {α : Type _} [DecidableEq α] {s : Finset α} (P : Finpartition s) (G : SimpleGraph α)
+variable {α : Type*} [DecidableEq α] {s : Finset α} (P : Finpartition s) (G : SimpleGraph α)
[DecidableRel G.Adj]
local macro_rules | `($x ^ $y) => `(HPow.hPow $x $y) -- Porting note: See issue lean4#2220
@@ -61,7 +61,7 @@ theorem energy_le_one : P.energy G ≤ 1 :=
#align finpartition.energy_le_one Finpartition.energy_le_one
@[simp, norm_cast]
-theorem coe_energy {𝕜 : Type _} [LinearOrderedField 𝕜] : (P.energy G : 𝕜) =
+theorem coe_energy {𝕜 : Type*} [LinearOrderedField 𝕜] : (P.energy G : 𝕜) =
(∑ uv in P.parts.offDiag, (G.edgeDensity uv.1 uv.2 : 𝕜) ^ 2) / (P.parts.card : 𝕜) ^ 2 := by
rw [energy]; norm_cast
#align finpartition.coe_energy Finpartition.coe_energy
@@ -32,7 +32,7 @@ open BigOperators
variable {α : Type _} [DecidableEq α] {s : Finset α} (P : Finpartition s) (G : SimpleGraph α)
[DecidableRel G.Adj]
-local macro_rules | `($x ^ $y) => `(HPow.hPow $x $y) -- Porting note: See issue #2220
+local macro_rules | `($x ^ $y) => `(HPow.hPow $x $y) -- Porting note: See issue lean4#2220
namespace Finpartition
@@ -2,17 +2,14 @@
Copyright (c) 2022 Yaël Dillies, Bhavik Mehta. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Yaël Dillies, Bhavik Mehta
-
-! This file was ported from Lean 3 source module combinatorics.simple_graph.regularity.energy
-! leanprover-community/mathlib commit bf7ef0e83e5b7e6c1169e97f055e58a2e4e9d52d
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
-/
import Mathlib.Algebra.BigOperators.Order
import Mathlib.Algebra.Module.Basic
import Mathlib.Combinatorics.SimpleGraph.Density
import Mathlib.Data.Rat.BigOperators
+#align_import combinatorics.simple_graph.regularity.energy from "leanprover-community/mathlib"@"bf7ef0e83e5b7e6c1169e97f055e58a2e4e9d52d"
+
/-!
# Energy of a partition
∑'
precedence (#5615)
∑
, ∏
and variants).([^a-zA-Zα-ωΑ-Ω'𝓝ℳ₀𝕂ₛ)]) \(([∑∏][^()∑∏]*,[^()∑∏:]*)\) ([⊂⊆=<≤])
replaced by $1 $2 $3
@@ -52,7 +52,7 @@ theorem energy_nonneg : 0 ≤ P.energy G := by
theorem energy_le_one : P.energy G ≤ 1 :=
div_le_of_nonneg_of_le_mul (sq_nonneg _) zero_le_one <|
calc
- (∑ uv in P.parts.offDiag, G.edgeDensity uv.1 uv.2 ^ 2) ≤ P.parts.offDiag.card • (1 : ℚ) :=
+ ∑ uv in P.parts.offDiag, G.edgeDensity uv.1 uv.2 ^ 2 ≤ P.parts.offDiag.card • (1 : ℚ) :=
sum_le_card_nsmul _ _ 1 fun uv _ =>
(sq_le_one_iff <| G.edgeDensity_nonneg _ _).2 <| G.edgeDensity_le_one _ _
_ = P.parts.offDiag.card := (Nat.smul_one_eq_coe _)
@@ -35,20 +35,22 @@ open BigOperators
variable {α : Type _} [DecidableEq α] {s : Finset α} (P : Finpartition s) (G : SimpleGraph α)
[DecidableRel G.Adj]
+local macro_rules | `($x ^ $y) => `(HPow.hPow $x $y) -- Porting note: See issue #2220
+
namespace Finpartition
/-- The energy of a partition, also known as index. Auxiliary quantity for Szemerédi's regularity
lemma. -/
def energy : ℚ :=
- ((∑ uv in P.parts.offDiag, G.edgeDensity uv.1 uv.2 ^ 2) : ℚ) / (P.parts.card ^ 2 : ℕ)
+ ((∑ uv in P.parts.offDiag, G.edgeDensity uv.1 uv.2 ^ 2) : ℚ) / (P.parts.card : ℚ) ^ 2
#align finpartition.energy Finpartition.energy
theorem energy_nonneg : 0 ≤ P.energy G := by
- refine' div_nonneg (Finset.sum_nonneg fun _ _ => sq_nonneg _) <| Nat.cast_nonneg _
+ refine' div_nonneg (Finset.sum_nonneg fun _ _ => sq_nonneg _) <| sq_nonneg _
#align finpartition.energy_nonneg Finpartition.energy_nonneg
theorem energy_le_one : P.energy G ≤ 1 :=
- div_le_of_nonneg_of_le_mul (Nat.cast_nonneg _) zero_le_one <|
+ div_le_of_nonneg_of_le_mul (sq_nonneg _) zero_le_one <|
calc
(∑ uv in P.parts.offDiag, G.edgeDensity uv.1 uv.2 ^ 2) ≤ P.parts.offDiag.card • (1 : ℚ) :=
sum_le_card_nsmul _ _ 1 fun uv _ =>
@@ -62,10 +64,9 @@ theorem energy_le_one : P.energy G ≤ 1 :=
#align finpartition.energy_le_one Finpartition.energy_le_one
@[simp, norm_cast]
-theorem coe_energy {𝕜 : Type _} [LinearOrderedField 𝕜] :
- (P.energy G : 𝕜) =
- (∑ uv in P.parts.offDiag, G.edgeDensity uv.1 uv.2 ^ 2 : ℚ) / ((↑P.parts.card : ℚ) ^ 2 : ℚ) :=
- by rw [energy]; norm_cast
+theorem coe_energy {𝕜 : Type _} [LinearOrderedField 𝕜] : (P.energy G : 𝕜) =
+ (∑ uv in P.parts.offDiag, (G.edgeDensity uv.1 uv.2 : 𝕜) ^ 2) / (P.parts.card : 𝕜) ^ 2 := by
+ rw [energy]; norm_cast
#align finpartition.coe_energy Finpartition.coe_energy
end Finpartition
Match https://github.com/leanprover-community/mathlib/pull/19051 (and one line of https://github.com/leanprover-community/mathlib/pull/18371)
combinatorics.simple_graph.regularity.energy
@f7707875544ef1f81b32cb68c79e0e24e45a0e76
..bf7ef0e83e5b7e6c1169e97f055e58a2e4e9d52d
combinatorics.simple_graph.regularity.equitabilise
@4c19a16e4b705bf135cf9a80ac18fcc99c438514
..bf7ef0e83e5b7e6c1169e97f055e58a2e4e9d52d
combinatorics.simple_graph.regularity.uniform
@32b08ef840dd25ca2e47e035c5da03ce16d2dc3c
..bf7ef0e83e5b7e6c1169e97f055e58a2e4e9d52d
@@ -4,13 +4,14 @@ Released under Apache 2.0 license as described in the file LICENSE.
Authors: Yaël Dillies, Bhavik Mehta
! This file was ported from Lean 3 source module combinatorics.simple_graph.regularity.energy
-! leanprover-community/mathlib commit f7707875544ef1f81b32cb68c79e0e24e45a0e76
+! leanprover-community/mathlib commit bf7ef0e83e5b7e6c1169e97f055e58a2e4e9d52d
! Please do not edit these lines, except to modify the commit id
! if you have ported upstream changes.
-/
import Mathlib.Algebra.BigOperators.Order
import Mathlib.Algebra.Module.Basic
import Mathlib.Combinatorics.SimpleGraph.Density
+import Mathlib.Data.Rat.BigOperators
/-!
# Energy of a partition
@@ -20,6 +21,10 @@ This file defines the energy of a partition.
The energy is the auxiliary quantity that drives the induction process in the proof of Szemerédi's
Regularity Lemma. As long as we do not have a suitable equipartition, we will find a new one that
has an energy greater than the previous one plus some fixed constant.
+
+## References
+
+[Yaël Dillies, Bhavik Mehta, *Formalising Szemerédi’s Regularity Lemma in Lean*][srl_itp]
-/
@@ -56,4 +61,11 @@ theorem energy_le_one : P.energy G ≤ 1 :=
exact tsub_le_self
#align finpartition.energy_le_one Finpartition.energy_le_one
+@[simp, norm_cast]
+theorem coe_energy {𝕜 : Type _} [LinearOrderedField 𝕜] :
+ (P.energy G : 𝕜) =
+ (∑ uv in P.parts.offDiag, G.edgeDensity uv.1 uv.2 ^ 2 : ℚ) / ((↑P.parts.card : ℚ) ^ 2 : ℚ) :=
+ by rw [energy]; norm_cast
+#align finpartition.coe_energy Finpartition.coe_energy
+
end Finpartition
This PR fixes two things:
align
statements for definitions and theorems and instances that are separated by two newlines from the relevant declaration (s/\n\n#align/\n#align
). This is often seen in the mathport output after ending calc
blocks.#align
statements. (This was needed for a script I wrote for #3630.)@@ -54,7 +54,6 @@ theorem energy_le_one : P.energy G ≤ 1 :=
norm_cast
rw [sq]
exact tsub_le_self
-
#align finpartition.energy_le_one Finpartition.energy_le_one
end Finpartition
The unported dependencies are