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

bf7ef0e8

(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

f7707875

(first ported)

Changes in mathlib3port

mathlib3

mathlib3port

bf7ef0e8

bump to nightly-2024-04-07-08

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

b03b8656

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

bf7ef0e8

bump to nightly-2023-09-24-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/ce64cd319bb6b3e82f31c2d38e79080d377be451

5655435f

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"

bf7ef0e8

bump to nightly-2023-07-20-09

mathlib commit https://github.com/leanprover-community/mathlib/commit/8ea5598db6caeddde6cb734aa179cc2408dbd345

9c56d0dd

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

bf7ef0e8

bump to nightly-2023-06-13-21

mathlib commit https://github.com/leanprover-community/mathlib/commit/9fb8964792b4237dac6200193a0d533f1b3f7423

829520ac

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

bf7ef0e8

bump to nightly-2023-06-10-07

mathlib commit https://github.com/leanprover-community/mathlib/commit/a3e83f0fa4391c8740f7d773a7a9b74e311ae2a3

3fdc57bc

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

bf7ef0e8

bump to nightly-2023-06-09-07

mathlib commit https://github.com/leanprover-community/mathlib/commit/7e5137f579de09a059a5ce98f364a04e221aabf0

16afdc39

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]

bf7ef0e8

bump to nightly-2023-05-28-18

mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb

8d353152

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]

bf7ef0e8

bump to nightly-2023-05-28-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb

ba5d8b97

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 :=

bf7ef0e8

bump to nightly-2023-05-28-04

mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb

6797a637

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

bf7ef0e8

bump to nightly-2023-05-23-03

mathlib commit https://github.com/leanprover-community/mathlib/commit/75e7fca56381d056096ce5d05e938f63a6567828

ed98987c

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 :=

bf7ef0e8

bump to nightly-2023-05-21-03

mathlib commit https://github.com/leanprover-community/mathlib/commit/33c67ae661dd8988516ff7f247b0be3018cdd952

7b1466d5

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

f4758115

bump to nightly-2023-03-09-03

mathlib commit https://github.com/leanprover-community/mathlib/commit/21e3562c5e12d846c7def5eff8cdbc520d7d4936

061741a1

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

f7707875

bump to nightly-2023-03-02-10

mathlib commit https://github.com/leanprover-community/mathlib/commit/195fcd60ff2bfe392543bceb0ec2adcdb472db4c

01978261

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

f7707875

bump to nightly-2023-03-01-20

mathlib commit https://github.com/leanprover-community/mathlib/commit/4c586d291f189eecb9d00581aeb3dd998ac34442

20cadee0

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

f7707875

bump to nightly-2023-02-21-16

mathlib commit https://github.com/leanprover-community/mathlib/commit/bd9851ca476957ea4549eb19b40e7b5ade9428cc

1107b979

Changes in mathlib4

mathlib3

mathlib4

bf7ef0e8

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>

7d5102df

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

bf7ef0e8

chore: superfluous parentheses part 2 (#12131)

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

d48d30ac

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

bf7ef0e8

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:

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:

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.

3cc22ef5

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

bf7ef0e8

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.

ea36aa7d

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 :=

bf7ef0e8

chore: Move positivity extensions (#10140)

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

65a5eadc

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

bf7ef0e8

chore: bump to v4.3.0-rc2 (#8366)

PR contents

This is the supremum of

#8284
#8056
#8023
#8332
#8226 (already approved)
#7834 (already approved)

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>

40b64f79

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

bf7ef0e8

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.

32de3f67

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

bf7ef0e8

chore: regularize HPow.hPow porting notes (#6465)

0f85d19f

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

bf7ef0e8

chore: script to replace headers with #align_import statements (#5979)

depends on: #5966

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

89aa3a3b

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

bf7ef0e8

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

03fc68aa

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

bf7ef0e8

feat: port Combinatorics.SimpleGraph.Regularity.Increment (#5476)

6f0a97ee

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

bf7ef0e8

chore: Add reference for SRL (#4160)

Match https://github.com/leanprover-community/mathlib/pull/19051 (and one line of https://github.com/leanprover-community/mathlib/pull/18371)

02d14be2

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

f7707875

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

2b42dc7c

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

f7707875

feat: port Combinatorics.SimpleGraph.Regularity.Energy (#2575)

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

a7cd169c

`combinatorics.simple_graph.regularity.energy` ⟷ `Mathlib.Combinatorics.SimpleGraph.Regularity.Energy`

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

PR contents

Lean PRs involved in this bump

leanprover/lean4#2778

leanprover/lean4#2722

leanprover/lean4#2783

Dependencies 7 + 280

combinatorics.simple_graph.regularity.energy ⟷ Mathlib.Combinatorics.SimpleGraph.Regularity.Energy

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

PR contents

Lean PRs involved in this bump

leanprover/lean4#2778

leanprover/lean4#2722

leanprover/lean4#2783

Dependencies 7 + 280

`combinatorics.simple_graph.regularity.energy` ⟷ `Mathlib.Combinatorics.SimpleGraph.Regularity.Energy`