combinatorics.simple_graph.regularity.energyMathlib.Combinatorics.SimpleGraph.Regularity.Energy

This file has been ported!

Changes since the initial port

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.

Changes in mathlib3

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(no changes)

(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)

feat(combinatorics/simple_graph/regularity): Increment partition (#19051)

Define the increment partition and prove its two crucial properties:

  • It has size depending only on the size of the original partition
  • It increases the energy by a fixed amount

This is all internal to the proof of SRL, so I made most lemmas private.

Co-authored-by: Bhavik Mehta <bhavikmehta8@gmail.com>

Diff
@@ -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)

Changes in mathlib3port

mathlib3
mathlib3port
Diff
@@ -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
Diff
@@ -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"
 
Diff
@@ -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
 
Diff
@@ -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
 
Diff
@@ -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 _)
Diff
@@ -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]
Diff
@@ -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]
Diff
@@ -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 :=
Diff
@@ -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
Diff
@@ -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 :=
Diff
@@ -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
 
Diff
@@ -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
Diff
@@ -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
Diff
@@ -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

Changes in mathlib4

mathlib3
mathlib4
chore: split Algebra.Module.Basic (#12501)

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>

Diff
@@ -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
chore: superfluous parentheses part 2 (#12131)

Co-authored-by: Moritz Firsching <firsching@google.com>

Diff
@@ -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
chore: Sort big operator order lemmas (#11750)

Take the content of

  • some of Algebra.BigOperators.List.Basic
  • some of Algebra.BigOperators.List.Lemmas
  • some of Algebra.BigOperators.Multiset.Basic
  • some of Algebra.BigOperators.Multiset.Lemmas
  • Algebra.BigOperators.Multiset.Order
  • Algebra.BigOperators.Order

and sort it into six files:

Here are the design decisions at play:

  • Pure algebra and big operators algebra shouldn't import (algebraic) order theory. This PR makes that better, but not perfect because we still import Data.Nat.Order.Basic in a few List files.
  • It's 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.
  • There are separate files for group/monoid lemmas vs ring lemmas. Groups/monoids are the natural setup for big operators, so their lemmas shouldn't be mixed with ring lemmas that involves both addition and multiplication. As a result, everything under 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.
  • Lemmas are separated according to 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.
Diff
@@ -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
 
chore: remove terminal, terminal refines (#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 refines, but maybe the current change is beneficial.

Diff
@@ -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 :=
chore: Move positivity extensions (#10140)

The goal here is to have access to positivity earlier in the import hierarchy

Diff
@@ -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
chore: bump to v4.3.0-rc2 (#8366)

PR contents

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.

Lean PRs involved in this bump

In particular this includes adjustments for the Lean PRs

leanprover/lean4#2778

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).

leanprover/lean4#2722

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}).

leanprover/lean4#2783

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:

  • switching to using explicit lemmas that have the intended level of application
  • (config := { unfoldPartialApp := true }) in some places, to recover the old behaviour
  • Using @[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>

Diff
@@ -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
chore: banish Type _ and Sort _ (#6499)

We remove all possible occurences of Type _ and Sort _ in favor of Type* and Sort*.

This has nice performance benefits.

Diff
@@ -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
chore: regularize HPow.hPow porting notes (#6465)
Diff
@@ -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
 
chore: script to replace headers with #align_import statements (#5979)

Open in Gitpod

Co-authored-by: Eric Wieser <wieser.eric@gmail.com> Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

Diff
@@ -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
 
fix: ∑' precedence (#5615)
  • Also remove most superfluous parentheses around big operators (, and variants).
  • roughly the used regex: ([^a-zA-Zα-ωΑ-Ω'𝓝ℳ₀𝕂ₛ)]) \(([∑∏][^()∑∏]*,[^()∑∏:]*)\) ([⊂⊆=<≤]) replaced by $1 $2 $3
Diff
@@ -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 _)
feat: port Combinatorics.SimpleGraph.Regularity.Increment (#5476)
Diff
@@ -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
Diff
@@ -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
chore: fix #align lines (#3640)

This PR fixes two things:

  • Most 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.
  • All remaining more-than-one-line #align statements. (This was needed for a script I wrote for #3630.)
Diff
@@ -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
feat: port Combinatorics.SimpleGraph.Regularity.Energy (#2575)

Co-authored-by: Moritz Firsching <firsching@google.com>

Dependencies 7 + 280

281 files ported (97.6%)
115407 lines ported (97.4%)
Show graph

The unported dependencies are