combinatorics.additive.ruzsa_covering | Mathlib porting status

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

b363547b

(last sync)

Changes in mathlib3port

mathlib3

mathlib3port

50832dae

bump to nightly-2024-03-17-08

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

22f01ce4

Diff

@@ -38,7 +38,7 @@ theorem exists_subset_mul_div (ht : t.Nonempty) :
   set C := s.powerset.filter fun u => (u : Set α).PairwiseDisjoint (· • t)
   obtain ⟨u, hu, hCmax⟩ :=
     C.exists_maximal (filter_nonempty_iff.2 ⟨∅, empty_mem_powerset _, Set.pairwiseDisjoint_empty⟩)
-  rw [mem_filter, mem_powerset] at hu 
+  rw [mem_filter, mem_powerset] at hu
   refine'
     ⟨u,
       (card_mul_iff.2 <| pairwise_disjoint_smul_iff.1 hu.2).ge.trans
@@ -51,8 +51,8 @@ theorem exists_subset_mul_div (ht : t.Nonempty) :
   · refine' (hCmax _ _ <| ssubset_insert hau).elim
     rw [mem_filter, mem_powerset, insert_subset, coe_insert]
     exact ⟨⟨ha, hu.1⟩, hu.2.insert fun b hb _ => H _ hb⟩
-  push_neg at H 
-  simp_rw [not_disjoint_iff, ← inv_smul_mem_iff] at H 
+  push_neg at H
+  simp_rw [not_disjoint_iff, ← inv_smul_mem_iff] at H
   obtain ⟨b, hb, c, hc₁, hc₂⟩ := H
   exact mem_mul.2 ⟨_, _, hb, mem_div.2 ⟨_, _, hc₂, hc₁, by simp [div_eq_mul_inv a b]⟩, by simp⟩
 #align finset.exists_subset_mul_div Finset.exists_subset_mul_div

50832dae

bump to nightly-2023-09-24-06

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

5655435f

Diff

@@ -3,7 +3,7 @@ Copyright (c) 2022 Yaël Dillies. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Yaël Dillies
 -/
-import Mathbin.Data.Finset.Pointwise
+import Data.Finset.Pointwise
 
 #align_import combinatorics.additive.ruzsa_covering from "leanprover-community/mathlib"@"50832daea47b195a48b5b33b1c8b2162c48c3afc"

50832dae

bump to nightly-2023-07-20-09

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

9c56d0dd

Diff

@@ -2,14 +2,11 @@
 Copyright (c) 2022 Yaël Dillies. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Yaël Dillies
-
-! This file was ported from Lean 3 source module combinatorics.additive.ruzsa_covering
-! leanprover-community/mathlib commit 50832daea47b195a48b5b33b1c8b2162c48c3afc
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathbin.Data.Finset.Pointwise
 
+#align_import combinatorics.additive.ruzsa_covering from "leanprover-community/mathlib"@"50832daea47b195a48b5b33b1c8b2162c48c3afc"
+
 /-!
 # Ruzsa's covering lemma

50832dae

bump to nightly-2023-06-13-21

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

829520ac

Diff

@@ -31,6 +31,7 @@ namespace Finset
 
 variable {α : Type _} [DecidableEq α] [CommGroup α] (s : Finset α) {t : Finset α}
 
+#print Finset.exists_subset_mul_div /-
 /-- **Ruzsa's covering lemma**. -/
 @[to_additive "**Ruzsa's covering lemma**"]
 theorem exists_subset_mul_div (ht : t.Nonempty) :
@@ -59,6 +60,7 @@ theorem exists_subset_mul_div (ht : t.Nonempty) :
   exact mem_mul.2 ⟨_, _, hb, mem_div.2 ⟨_, _, hc₂, hc₁, by simp [div_eq_mul_inv a b]⟩, by simp⟩
 #align finset.exists_subset_mul_div Finset.exists_subset_mul_div
 #align finset.exists_subset_add_sub Finset.exists_subset_add_sub
+-/
 
 end Finset

50832dae

bump to nightly-2023-06-04-18

mathlib commit https://github.com/leanprover-community/mathlib/commit/5f25c089cb34db4db112556f23c50d12da81b297

3fb4268b

Diff

@@ -53,7 +53,7 @@ theorem exists_subset_mul_div (ht : t.Nonempty) :
   · refine' (hCmax _ _ <| ssubset_insert hau).elim
     rw [mem_filter, mem_powerset, insert_subset, coe_insert]
     exact ⟨⟨ha, hu.1⟩, hu.2.insert fun b hb _ => H _ hb⟩
-  push_neg  at H 
+  push_neg at H 
   simp_rw [not_disjoint_iff, ← inv_smul_mem_iff] at H 
   obtain ⟨b, hb, c, hc₁, hc₂⟩ := H
   exact mem_mul.2 ⟨_, _, hb, mem_div.2 ⟨_, _, hc₂, hc₁, by simp [div_eq_mul_inv a b]⟩, by simp⟩

50832dae

bump to nightly-2023-06-01-16

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

b9c87c70

Diff

@@ -40,7 +40,7 @@ theorem exists_subset_mul_div (ht : t.Nonempty) :
   set C := s.powerset.filter fun u => (u : Set α).PairwiseDisjoint (· • t)
   obtain ⟨u, hu, hCmax⟩ :=
     C.exists_maximal (filter_nonempty_iff.2 ⟨∅, empty_mem_powerset _, Set.pairwiseDisjoint_empty⟩)
-  rw [mem_filter, mem_powerset] at hu
+  rw [mem_filter, mem_powerset] at hu 
   refine'
     ⟨u,
       (card_mul_iff.2 <| pairwise_disjoint_smul_iff.1 hu.2).ge.trans
@@ -53,8 +53,8 @@ theorem exists_subset_mul_div (ht : t.Nonempty) :
   · refine' (hCmax _ _ <| ssubset_insert hau).elim
     rw [mem_filter, mem_powerset, insert_subset, coe_insert]
     exact ⟨⟨ha, hu.1⟩, hu.2.insert fun b hb _ => H _ hb⟩
-  push_neg  at H
-  simp_rw [not_disjoint_iff, ← inv_smul_mem_iff] at H
+  push_neg  at H 
+  simp_rw [not_disjoint_iff, ← inv_smul_mem_iff] at H 
   obtain ⟨b, hb, c, hc₁, hc₂⟩ := H
   exact mem_mul.2 ⟨_, _, hb, mem_div.2 ⟨_, _, hc₂, hc₁, by simp [div_eq_mul_inv a b]⟩, by simp⟩
 #align finset.exists_subset_mul_div Finset.exists_subset_mul_div

50832dae

bump to nightly-2023-05-28-18

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

8d353152

Diff

@@ -25,7 +25,7 @@ Merge this file with other prerequisites to Freiman's theorem once we have them.
 -/
 
 
-open Pointwise
+open scoped Pointwise
 
 namespace Finset

50832dae

bump to nightly-2023-05-28-06

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

ba5d8b97

Diff

@@ -31,12 +31,6 @@ namespace Finset
 
 variable {α : Type _} [DecidableEq α] [CommGroup α] (s : Finset α) {t : Finset α}
 
-/- warning: finset.exists_subset_mul_div -> Finset.exists_subset_mul_div is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] [_inst_2 : CommGroup.{u1} α] (s : Finset.{u1} α) {t : Finset.{u1} α}, (Finset.Nonempty.{u1} α t) -> (Exists.{succ u1} (Finset.{u1} α) (fun (u : Finset.{u1} α) => And (LE.le.{0} Nat Nat.hasLe (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) (Finset.card.{u1} α u) (Finset.card.{u1} α t)) (Finset.card.{u1} α (HMul.hMul.{u1, u1, u1} (Finset.{u1} α) (Finset.{u1} α) (Finset.{u1} α) (instHMul.{u1} (Finset.{u1} α) (Finset.mul.{u1} α (fun (a : α) (b : α) => _inst_1 a b) (MulOneClass.toHasMul.{u1} α (Monoid.toMulOneClass.{u1} α (DivInvMonoid.toMonoid.{u1} α (Group.toDivInvMonoid.{u1} α (CommGroup.toGroup.{u1} α _inst_2))))))) s t))) (HasSubset.Subset.{u1} (Finset.{u1} α) (Finset.hasSubset.{u1} α) s (HDiv.hDiv.{u1, u1, u1} (Finset.{u1} α) (Finset.{u1} α) (Finset.{u1} α) (instHDiv.{u1} (Finset.{u1} α) (Finset.div.{u1} α (fun (a : α) (b : α) => _inst_1 a b) (DivInvMonoid.toHasDiv.{u1} α (Group.toDivInvMonoid.{u1} α (CommGroup.toGroup.{u1} α _inst_2))))) (HMul.hMul.{u1, u1, u1} (Finset.{u1} α) (Finset.{u1} α) (Finset.{u1} α) (instHMul.{u1} (Finset.{u1} α) (Finset.mul.{u1} α (fun (a : α) (b : α) => _inst_1 a b) (MulOneClass.toHasMul.{u1} α (Monoid.toMulOneClass.{u1} α (DivInvMonoid.toMonoid.{u1} α (Group.toDivInvMonoid.{u1} α (CommGroup.toGroup.{u1} α _inst_2))))))) u t) t))))
-but is expected to have type
-  forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] [_inst_2 : CommGroup.{u1} α] (s : Finset.{u1} α) {t : Finset.{u1} α}, (Finset.Nonempty.{u1} α t) -> (Exists.{succ u1} (Finset.{u1} α) (fun (u : Finset.{u1} α) => And (LE.le.{0} Nat instLENat (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) (Finset.card.{u1} α u) (Finset.card.{u1} α t)) (Finset.card.{u1} α (HMul.hMul.{u1, u1, u1} (Finset.{u1} α) (Finset.{u1} α) (Finset.{u1} α) (instHMul.{u1} (Finset.{u1} α) (Finset.mul.{u1} α (fun (a : α) (b : α) => _inst_1 a b) (MulOneClass.toMul.{u1} α (Monoid.toMulOneClass.{u1} α (DivInvMonoid.toMonoid.{u1} α (Group.toDivInvMonoid.{u1} α (CommGroup.toGroup.{u1} α _inst_2))))))) s t))) (HasSubset.Subset.{u1} (Finset.{u1} α) (Finset.instHasSubsetFinset.{u1} α) s (HDiv.hDiv.{u1, u1, u1} (Finset.{u1} α) (Finset.{u1} α) (Finset.{u1} α) (instHDiv.{u1} (Finset.{u1} α) (Finset.div.{u1} α (fun (a : α) (b : α) => _inst_1 a b) (DivInvMonoid.toDiv.{u1} α (Group.toDivInvMonoid.{u1} α (CommGroup.toGroup.{u1} α _inst_2))))) (HMul.hMul.{u1, u1, u1} (Finset.{u1} α) (Finset.{u1} α) (Finset.{u1} α) (instHMul.{u1} (Finset.{u1} α) (Finset.mul.{u1} α (fun (a : α) (b : α) => _inst_1 a b) (MulOneClass.toMul.{u1} α (Monoid.toMulOneClass.{u1} α (DivInvMonoid.toMonoid.{u1} α (Group.toDivInvMonoid.{u1} α (CommGroup.toGroup.{u1} α _inst_2))))))) u t) t))))
-Case conversion may be inaccurate. Consider using '#align finset.exists_subset_mul_div Finset.exists_subset_mul_divₓ'. -/
 /-- **Ruzsa's covering lemma**. -/
 @[to_additive "**Ruzsa's covering lemma**"]
 theorem exists_subset_mul_div (ht : t.Nonempty) :

50832dae

bump to nightly-2023-02-21-16

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

1107b979

Changes in mathlib4

mathlib3

mathlib4

b363547b

refactor(*): change definition of Set.image2 etc (#9275)

Redefine Set.image2 to use ∃ a ∈ s, ∃ b ∈ t, f a b = c instead of ∃ a b, a ∈ s ∧ b ∈ t ∧ f a b = c.
Redefine Set.seq as Set.image2. The new definition is equal to the old one but rw [Set.seq] gives a different result.
Redefine Filter.map₂ to use ∃ u ∈ f, ∃ v ∈ g, image2 m u v ⊆ s instead of ∃ u v, u ∈ f ∧ v ∈ g ∧ ...
Update lemmas like Set.mem_image2, Finset.mem_image₂, Set.mem_mul, Finset.mem_div etc

The two reasons to make the change are:

∃ a ∈ s, ∃ b ∈ t, _ is a simp-normal form, and
it looks a bit nicer.

8f17470f

Diff

@@ -49,8 +49,8 @@ theorem exists_subset_mul_div (ht : t.Nonempty) :
   push_neg at H
   simp_rw [not_disjoint_iff, ← inv_smul_mem_iff] at H
   obtain ⟨b, hb, c, hc₁, hc₂⟩ := H
-  refine' mem_mul.2 ⟨b, a / b, hb, _, by simp⟩
-  exact mem_div.2 ⟨_, _, hc₂, hc₁, by simp [div_eq_mul_inv a b, mul_comm]⟩
+  refine' mem_mul.2 ⟨b, hb, a / b, _, by simp⟩
+  exact mem_div.2 ⟨_, hc₂, _, hc₁, by simp [inv_mul_eq_div]⟩
 #align finset.exists_subset_mul_div Finset.exists_subset_mul_div
 #align finset.exists_subset_add_sub Finset.exists_subset_add_sub

b363547b

chore: Improve Finset lemma names (#8894)

Change a few lemma names that have historically bothered me.

Finset.card_le_of_subset → Finset.card_le_card
Multiset.card_le_of_le → Multiset.card_le_card
Multiset.card_lt_of_lt → Multiset.card_lt_card
Set.ncard_le_of_subset → Set.ncard_le_ncard
Finset.image_filter → Finset.filter_image
CompleteLattice.finset_sup_compact_of_compact → CompleteLattice.isCompactElement_finset_sup

7d3d6e43

Diff

@@ -37,7 +37,7 @@ theorem exists_subset_mul_div (ht : t.Nonempty) :
   rw [mem_filter, mem_powerset] at hu
   refine' ⟨u,
     (card_mul_iff.2 <| pairwiseDisjoint_smul_iff.1 hu.2).ge.trans
-      (card_le_of_subset <| mul_subset_mul_right hu.1),
+      (card_le_card <| mul_subset_mul_right hu.1),
     fun a ha ↦ _⟩
   rw [mul_div_assoc]
   by_cases hau : a ∈ u

b363547b

feat: Ruzsa covering for sets (#8916)

Add a version covering for Set α and Nat.card.

From PFR

Co-authored-by: Eric Wieser <wieser.eric@gmail.com>

5e71f8d0

Diff

@@ -4,6 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Yaël Dillies
 -/
 import Mathlib.Data.Finset.Pointwise
+import Mathlib.SetTheory.Cardinal.Finite
 
 #align_import combinatorics.additive.ruzsa_covering from "leanprover-community/mathlib"@"b363547b3113d350d053abdf2884e9850a56b205"
 
@@ -54,3 +55,23 @@ theorem exists_subset_mul_div (ht : t.Nonempty) :
 #align finset.exists_subset_add_sub Finset.exists_subset_add_sub
 
 end Finset
+
+namespace Set
+variable {α : Type*} [CommGroup α] {s t : Set α}
+
+/-- **Ruzsa's covering lemma** for sets. See also `Finset.exists_subset_mul_div`. -/
+@[to_additive "**Ruzsa's covering lemma**. Version for sets. For finsets,
+see `Finset.exists_subset_add_sub`."]
+lemma exists_subset_mul_div (hs : s.Finite) (ht' : t.Finite) (ht : t.Nonempty) :
+    ∃ u : Set α, Nat.card u * Nat.card t ≤ Nat.card (s * t) ∧ s ⊆ u * t / t ∧ u.Finite := by
+  lift s to Finset α using hs
+  lift t to Finset α using ht'
+  classical
+  obtain ⟨u, hu, hsut⟩ := Finset.exists_subset_mul_div s ht
+  refine ⟨u, ?_⟩
+  -- `norm_cast` would find these automatically, but breaks `to_additive` when it does so
+  rw [← Finset.coe_mul, ← Finset.coe_mul, ← Finset.coe_div]
+  norm_cast
+  simp [*]
+
+end Set

b363547b

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

@@ -23,7 +23,7 @@ open Pointwise
 
 namespace Finset
 
-variable {α : Type _} [DecidableEq α] [CommGroup α] (s : Finset α) {t : Finset α}
+variable {α : Type*} [DecidableEq α] [CommGroup α] (s : Finset α) {t : Finset α}
 
 /-- **Ruzsa's covering lemma**. -/
 @[to_additive "**Ruzsa's covering lemma**"]

b363547b

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,14 +2,11 @@
 Copyright (c) 2022 Yaël Dillies. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Yaël Dillies
-
-! This file was ported from Lean 3 source module combinatorics.additive.ruzsa_covering
-! leanprover-community/mathlib commit b363547b3113d350d053abdf2884e9850a56b205
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathlib.Data.Finset.Pointwise
 
+#align_import combinatorics.additive.ruzsa_covering from "leanprover-community/mathlib"@"b363547b3113d350d053abdf2884e9850a56b205"
+
 /-!
 # Ruzsa's covering lemma

b363547b

feat(Data.Set.Basic/Data.Finset.Basic): rename insert_subset (#5450)

Currently, (for both Set and Finset) insert_subset is an iff lemma stating that insert a s ⊆ t if and only if a ∈ t and s ⊆ t. For both types, this PR renames this lemma to insert_subset_iff, and adds an insert_subset lemma that gives the implication just in the reverse direction : namely theorem insert_subset (ha : a ∈ t) (hs : s ⊆ t) : insert a s ⊆ t .

This both aligns the naming with union_subset and union_subset_iff, and removes the need for the awkward insert_subset.mpr ⟨_,_⟩ idiom. It touches a lot of files (too many to list), but in a trivial way.

d8b62864

Diff

@@ -46,7 +46,7 @@ theorem exists_subset_mul_div (ht : t.Nonempty) :
   · exact subset_mul_left _ ht.one_mem_div hau
   by_cases H : ∀ b ∈ u, Disjoint (a • t) (b • t)
   · refine' (hCmax _ _ <| ssubset_insert hau).elim
-    rw [mem_filter, mem_powerset, insert_subset, coe_insert]
+    rw [mem_filter, mem_powerset, insert_subset_iff, coe_insert]
     exact ⟨⟨ha, hu.1⟩, hu.2.insert fun _ hb _ ↦ H _ hb⟩
   push_neg at H
   simp_rw [not_disjoint_iff, ← inv_smul_mem_iff] at H

b363547b

feat: port Combinatorics.Additive.RuzsaCovering (#2065)

ba613812

`combinatorics.additive.ruzsa_covering` ⟷ `Mathlib.Combinatorics.Additive.RuzsaCovering`

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Dependencies 7 + 240

combinatorics.additive.ruzsa_covering ⟷ Mathlib.Combinatorics.Additive.RuzsaCovering

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Dependencies 7 + 240

`combinatorics.additive.ruzsa_covering` ⟷ `Mathlib.Combinatorics.Additive.RuzsaCovering`