group_theory.exponent
⟷
Mathlib.GroupTheory.Exponent
The following section lists changes to this file in mathlib3 and mathlib4 that occured after the initial port. Most recent changes are shown first. Hovering over a commit will show all commits associated with the same mathlib3 commit.
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(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)
mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83
@@ -3,10 +3,10 @@ Copyright (c) 2021 Julian Kuelshammer. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Julian Kuelshammer
-/
-import Data.Zmod.Quotient
+import Data.ZMod.Quotient
import GroupTheory.NoncommPiCoprod
import GroupTheory.OrderOfElement
-import Algebra.GcdMonoid.Finset
+import Algebra.GCDMonoid.Finset
import Data.Nat.Factorization.Basic
import Tactic.ByContra
@@ -244,7 +244,7 @@ theorem Nat.Prime.exists_orderOf_eq_pow_factorization_exponent {p : ℕ} (hp : p
refine' ⟨g ^ k, _⟩
rw [ht]
apply orderOf_eq_prime_pow
- · rwa [hk, mul_comm, ht, pow_succ', ← mul_assoc, Nat.mul_div_cancel _ hp.pos, pow_mul] at hg
+ · rwa [hk, mul_comm, ht, pow_succ, ← mul_assoc, Nat.mul_div_cancel _ hp.pos, pow_mul] at hg
· rw [← Nat.succ_eq_add_one, ← ht, ← pow_mul, mul_comm, ← hk]
exact pow_exponent_eq_one g
#align nat.prime.exists_order_of_eq_pow_factorization_exponent Nat.Prime.exists_orderOf_eq_pow_factorization_exponent
@@ -367,7 +367,7 @@ theorem exponent_eq_iSup_orderOf (h : ∀ g : G, 0 < orderOf g) : exponent G =
simp [hp]
rw [(Commute.all _ g).orderOf_mul_eq_mul_orderOf_of_coprime hcoprime, hpk', hg, ha, ← ht, ← hk,
pow_add, pow_add, pow_one, ← mul_assoc, ← mul_assoc, Nat.div_mul_cancel, mul_assoc,
- lt_mul_iff_one_lt_right <| h t, ← pow_succ']
+ lt_mul_iff_one_lt_right <| h t, ← pow_succ]
exact one_lt_pow hp.one_lt a.succ_ne_zero
exact hpk
#align monoid.exponent_eq_supr_order_of Monoid.exponent_eq_iSup_orderOf
mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83
@@ -228,9 +228,9 @@ theorem Nat.Prime.exists_orderOf_eq_pow_factorization_exponent {p : ℕ} (hp : p
rcases eq_or_ne ((exponent G).factorization p) 0 with (h | h)
· refine' ⟨1, by rw [h, pow_zero, orderOf_one]⟩
have he : 0 < exponent G :=
- Ne.bot_lt fun ht => by rw [ht] at h ; apply h;
+ Ne.bot_lt fun ht => by rw [ht] at h; apply h;
rw [bot_eq_zero, Nat.factorization_zero, Finsupp.zero_apply]
- rw [← Finsupp.mem_support_iff] at h
+ rw [← Finsupp.mem_support_iff] at h
obtain ⟨g, hg⟩ : ∃ g : G, g ^ (exponent G / p) ≠ 1 :=
by
suffices key : ¬exponent G ∣ exponent G / p
@@ -244,7 +244,7 @@ theorem Nat.Prime.exists_orderOf_eq_pow_factorization_exponent {p : ℕ} (hp : p
refine' ⟨g ^ k, _⟩
rw [ht]
apply orderOf_eq_prime_pow
- · rwa [hk, mul_comm, ht, pow_succ', ← mul_assoc, Nat.mul_div_cancel _ hp.pos, pow_mul] at hg
+ · rwa [hk, mul_comm, ht, pow_succ', ← mul_assoc, Nat.mul_div_cancel _ hp.pos, pow_mul] at hg
· rw [← Nat.succ_eq_add_one, ← ht, ← pow_mul, mul_comm, ← hk]
exact pow_exponent_eq_one g
#align nat.prime.exists_order_of_eq_pow_factorization_exponent Nat.Prime.exists_orderOf_eq_pow_factorization_exponent
@@ -266,12 +266,12 @@ theorem exponent_ne_zero_iff_range_orderOf_finite (h : ∀ g : G, 0 < orderOf g)
have htpos : 0 < t.prod id :=
by
refine' Finset.prod_pos fun a ha => _
- rw [← Finset.mem_coe, ht] at ha
+ rw [← Finset.mem_coe, ht] at ha
obtain ⟨k, rfl⟩ := ha
exact h k
suffices exponent G ∣ t.prod id by
intro h
- rw [h, zero_dvd_iff] at this
+ rw [h, zero_dvd_iff] at this
exact htpos.ne' this
refine' exponent_dvd_of_forall_pow_eq_one _ _ fun g => _
rw [pow_mod_orderOf, Nat.mod_eq_zero_of_dvd, pow_zero g]
@@ -288,7 +288,7 @@ theorem exponent_eq_zero_iff_range_orderOf_infinite (h : ∀ g : G, 0 < orderOf
exponent G = 0 ↔ (Set.range (orderOf : G → ℕ)).Infinite :=
by
have := exponent_ne_zero_iff_range_orderOf_finite h
- rwa [Ne.def, not_iff_comm, Iff.comm] at this
+ rwa [Ne.def, not_iff_comm, Iff.comm] at this
#align monoid.exponent_eq_zero_iff_range_order_of_infinite Monoid.exponent_eq_zero_iff_range_orderOf_infinite
#align add_monoid.exponent_eq_zero_iff_range_order_of_infinite AddMonoid.exponent_eq_zero_iff_range_addOrderOf_infinite
-/
@@ -346,12 +346,12 @@ theorem exponent_eq_iSup_orderOf (h : ∀ g : G, 0 < orderOf g) : exponent G =
by_contra! h
obtain ⟨p, hp, hpe⟩ := h
replace hp := Nat.prime_of_mem_factors hp
- simp only [Nat.factors_count_eq] at hpe
+ simp only [Nat.factors_count_eq] at hpe
set k := (orderOf t).factorization p with hk
obtain ⟨g, hg⟩ := hp.exists_order_of_eq_pow_factorization_exponent G
suffices orderOf t < orderOf (t ^ p ^ k * g)
by
- rw [ht] at this
+ rw [ht] at this
exact this.not_le (le_csSup hfin.bdd_above <| Set.mem_range_self _)
have hpk : p ^ k ∣ orderOf t := Nat.ord_proj_dvd _ _
have hpk' : orderOf (t ^ p ^ k) = orderOf t / p ^ k := by
@@ -399,7 +399,7 @@ variable [CancelCommMonoid G]
theorem exponent_eq_max'_orderOf [Fintype G] :
exponent G = ((@Finset.univ G _).image orderOf).max' ⟨1, by simp⟩ :=
by
- rw [← Finset.Nonempty.cSup_eq_max', Finset.coe_image, Finset.coe_univ, Set.image_univ, ← iSup]
+ rw [← Finset.Nonempty.csSup_eq_max', Finset.coe_image, Finset.coe_univ, Set.image_univ, ← iSup]
exact exponent_eq_supr_order_of orderOf_pos
#align monoid.exponent_eq_max'_order_of Monoid.exponent_eq_max'_orderOf
#align add_monoid.exponent_eq_max'_order_of AddMonoid.exponent_eq_max'_addOrderOf
@@ -429,7 +429,7 @@ theorem card_dvd_exponent_pow_rank : Nat.card G ∣ Monoid.exponent G ^ Group.ra
rw [← MonoidHom.range_top_iff_surjective, eq_top_iff, ← hS2, closure_le]
exact fun g hg => ⟨Pi.mulSingle ⟨g, hg⟩ ⟨g, mem_zpowers g⟩, noncomm_pi_coprod_mul_single _ _⟩
replace hf := nat_card_dvd_of_surjective f hf
- rw [Nat.card_pi] at hf
+ rw [Nat.card_pi] at hf
refine' hf.trans (Finset.prod_dvd_prod_of_dvd _ _ fun g hg => _)
rw [← Nat.card_zpowers]
exact Monoid.order_dvd_exponent (g : G)
mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83
@@ -175,7 +175,7 @@ theorem exp_eq_one_of_subsingleton [Subsingleton G] : exponent G = 1 :=
apply exponent_pos_of_exists 1 Nat.one_pos
simp
#align monoid.exp_eq_one_of_subsingleton Monoid.exp_eq_one_of_subsingleton
-#align add_monoid.exp_eq_zero_of_subsingleton AddMonoid.exp_eq_zero_of_subsingleton
+#align add_monoid.exp_eq_zero_of_subsingleton AddMonoid.exp_eq_one_of_subsingleton
-/
#print Monoid.order_dvd_exponent /-
mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83
@@ -79,17 +79,17 @@ noncomputable def exponent :=
variable {G}
-#print Monoid.exponentExists_iff_ne_zero /-
+#print Monoid.exponent_ne_zero /-
@[to_additive]
-theorem exponentExists_iff_ne_zero : ExponentExists G ↔ exponent G ≠ 0 :=
+theorem exponent_ne_zero : ExponentExists G ↔ exponent G ≠ 0 :=
by
rw [exponent]
split_ifs
· simp [h, @not_lt_zero' ℕ]
--if this isn't done this way, `to_additive` freaks
· tauto
-#align monoid.exponent_exists_iff_ne_zero Monoid.exponentExists_iff_ne_zero
-#align add_monoid.exponent_exists_iff_ne_zero AddMonoid.exponentExists_iff_ne_zero
+#align monoid.exponent_exists_iff_ne_zero Monoid.exponent_ne_zero
+#align add_monoid.exponent_exists_iff_ne_zero AddMonoid.exponent_ne_zero
-/
#print Monoid.exponent_eq_zero_iff /-
@@ -293,16 +293,16 @@ theorem exponent_eq_zero_iff_range_orderOf_infinite (h : ∀ g : G, 0 < orderOf
#align add_monoid.exponent_eq_zero_iff_range_order_of_infinite AddMonoid.exponent_eq_zero_iff_range_addOrderOf_infinite
-/
-#print Monoid.lcm_order_eq_exponent /-
+#print Monoid.lcm_orderOf_eq_exponent /-
@[to_additive lcm_add_order_eq_exponent]
-theorem lcm_order_eq_exponent [Fintype G] : (Finset.univ : Finset G).lcm orderOf = exponent G :=
+theorem lcm_orderOf_eq_exponent [Fintype G] : (Finset.univ : Finset G).lcm orderOf = exponent G :=
by
apply Nat.dvd_antisymm (lcm_order_of_dvd_exponent G)
refine' exponent_dvd_of_forall_pow_eq_one G _ fun g => _
obtain ⟨m, hm⟩ : orderOf g ∣ finset.univ.lcm orderOf := Finset.dvd_lcm (Finset.mem_univ g)
rw [hm, pow_mul, pow_orderOf_eq_one, one_pow]
-#align monoid.lcm_order_eq_exponent Monoid.lcm_order_eq_exponent
-#align add_monoid.lcm_add_order_eq_exponent AddMonoid.lcm_addOrder_eq_exponent
+#align monoid.lcm_order_eq_exponent Monoid.lcm_orderOf_eq_exponent
+#align add_monoid.lcm_add_order_eq_exponent AddMonoid.lcm_addOrderOf_eq_exponent
-/
end Monoid
mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83
@@ -157,7 +157,7 @@ theorem exponent_min' (n : ℕ) (hpos : 0 < n) (hG : ∀ g : G, g ^ n = 1) : exp
@[to_additive]
theorem exponent_min (m : ℕ) (hpos : 0 < m) (hm : m < exponent G) : ∃ g : G, g ^ m ≠ 1 :=
by
- by_contra' h
+ by_contra! h
have hcon : exponent G ≤ m := exponent_min' m hpos h
linarith
#align monoid.exponent_min Monoid.exponent_min
@@ -343,7 +343,7 @@ theorem exponent_eq_iSup_orderOf (h : ∀ g : G, 0 < orderOf g) : exponent G =
apply order_dvd_exponent
refine' Nat.dvd_of_factors_subperm he _
rw [List.subperm_ext_iff]
- by_contra' h
+ by_contra! h
obtain ⟨p, hp, hpe⟩ := h
replace hp := Nat.prime_of_mem_factors hp
simp only [Nat.factors_count_eq] at hpe
mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83
@@ -431,7 +431,7 @@ theorem card_dvd_exponent_pow_rank : Nat.card G ∣ Monoid.exponent G ^ Group.ra
replace hf := nat_card_dvd_of_surjective f hf
rw [Nat.card_pi] at hf
refine' hf.trans (Finset.prod_dvd_prod_of_dvd _ _ fun g hg => _)
- rw [← order_eq_card_zpowers']
+ rw [← Nat.card_zpowers]
exact Monoid.order_dvd_exponent (g : G)
#align card_dvd_exponent_pow_rank card_dvd_exponent_pow_rank
#align card_dvd_exponent_nsmul_rank card_dvd_exponent_nsmul_rank
mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83
@@ -238,7 +238,7 @@ theorem Nat.Prime.exists_orderOf_eq_pow_factorization_exponent {p : ℕ} (hp : p
exact fun hd =>
hp.one_lt.not_le
((mul_le_iff_le_one_left he).mp <|
- Nat.le_of_dvd he <| Nat.mul_dvd_of_dvd_div (Nat.dvd_of_mem_factorization h) hd)
+ Nat.le_of_dvd he <| Nat.mul_dvd_of_dvd_div (Nat.dvd_of_mem_primeFactors h) hd)
obtain ⟨k, hk : exponent G = p ^ _ * k⟩ := Nat.ord_proj_dvd _ _
obtain ⟨t, ht⟩ := Nat.exists_eq_succ_of_ne_zero (finsupp.mem_support_iff.mp h)
refine' ⟨g ^ k, _⟩
@@ -274,7 +274,7 @@ theorem exponent_ne_zero_iff_range_orderOf_finite (h : ∀ g : G, 0 < orderOf g)
rw [h, zero_dvd_iff] at this
exact htpos.ne' this
refine' exponent_dvd_of_forall_pow_eq_one _ _ fun g => _
- rw [pow_eq_mod_orderOf, Nat.mod_eq_zero_of_dvd, pow_zero g]
+ rw [pow_mod_orderOf, Nat.mod_eq_zero_of_dvd, pow_zero g]
apply Finset.dvd_prod_of_mem
rw [← Finset.mem_coe, ht]
exact Set.mem_range_self g
mathlib commit https://github.com/leanprover-community/mathlib/commit/ce64cd319bb6b3e82f31c2d38e79080d377be451
@@ -3,12 +3,12 @@ Copyright (c) 2021 Julian Kuelshammer. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Julian Kuelshammer
-/
-import Mathbin.Data.Zmod.Quotient
-import Mathbin.GroupTheory.NoncommPiCoprod
-import Mathbin.GroupTheory.OrderOfElement
-import Mathbin.Algebra.GcdMonoid.Finset
-import Mathbin.Data.Nat.Factorization.Basic
-import Mathbin.Tactic.ByContra
+import Data.Zmod.Quotient
+import GroupTheory.NoncommPiCoprod
+import GroupTheory.OrderOfElement
+import Algebra.GcdMonoid.Finset
+import Data.Nat.Factorization.Basic
+import Tactic.ByContra
#align_import group_theory.exponent from "leanprover-community/mathlib"@"0b7c740e25651db0ba63648fbae9f9d6f941e31b"
mathlib commit https://github.com/leanprover-community/mathlib/commit/ce64cd319bb6b3e82f31c2d38e79080d377be451
@@ -357,7 +357,7 @@ theorem exponent_eq_iSup_orderOf (h : ∀ g : G, 0 < orderOf g) : exponent G =
have hpk' : orderOf (t ^ p ^ k) = orderOf t / p ^ k := by
rw [orderOf_pow' t (pow_ne_zero k hp.ne_zero), Nat.gcd_eq_right hpk]
obtain ⟨a, ha⟩ := Nat.exists_eq_add_of_lt hpe
- have hcoprime : (orderOf (t ^ p ^ k)).coprime (orderOf g) :=
+ have hcoprime : (orderOf (t ^ p ^ k)).Coprime (orderOf g) :=
by
rw [hg, Nat.coprime_pow_right_iff (pos_of_gt hpe), Nat.coprime_comm]
apply Or.resolve_right (Nat.coprime_or_dvd_of_prime hp _)
mathlib commit https://github.com/leanprover-community/mathlib/commit/8ea5598db6caeddde6cb734aa179cc2408dbd345
@@ -2,11 +2,6 @@
Copyright (c) 2021 Julian Kuelshammer. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Julian Kuelshammer
-
-! This file was ported from Lean 3 source module group_theory.exponent
-! leanprover-community/mathlib commit 0b7c740e25651db0ba63648fbae9f9d6f941e31b
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
-/
import Mathbin.Data.Zmod.Quotient
import Mathbin.GroupTheory.NoncommPiCoprod
@@ -15,6 +10,8 @@ import Mathbin.Algebra.GcdMonoid.Finset
import Mathbin.Data.Nat.Factorization.Basic
import Mathbin.Tactic.ByContra
+#align_import group_theory.exponent from "leanprover-community/mathlib"@"0b7c740e25651db0ba63648fbae9f9d6f941e31b"
+
/-!
# Exponent of a group
mathlib commit https://github.com/leanprover-community/mathlib/commit/9fb8964792b4237dac6200193a0d533f1b3f7423
@@ -111,6 +111,7 @@ theorem exponent_eq_zero_of_order_zero {g : G} (hg : orderOf g = 0) : exponent G
#align add_monoid.exponent_eq_zero_of_order_zero AddMonoid.exponent_eq_zero_addOrder_zero
-/
+#print Monoid.pow_exponent_eq_one /-
@[to_additive exponent_nsmul_eq_zero]
theorem pow_exponent_eq_one (g : G) : g ^ exponent G = 1 :=
by
@@ -120,6 +121,7 @@ theorem pow_exponent_eq_one (g : G) : g ^ exponent G = 1 :=
· simp_rw [exponent, dif_neg h, pow_zero]
#align monoid.pow_exponent_eq_one Monoid.pow_exponent_eq_one
#align add_monoid.exponent_nsmul_eq_zero AddMonoid.exponent_nsmul_eq_zero
+-/
#print Monoid.pow_eq_mod_exponent /-
@[to_additive]
@@ -131,6 +133,7 @@ theorem pow_eq_mod_exponent {n : ℕ} (g : G) : g ^ n = g ^ (n % exponent G) :=
#align add_monoid.nsmul_eq_mod_exponent AddMonoid.nsmul_eq_mod_exponent
-/
+#print Monoid.exponent_pos_of_exists /-
@[to_additive]
theorem exponent_pos_of_exists (n : ℕ) (hpos : 0 < n) (hG : ∀ g : G, g ^ n = 1) : 0 < exponent G :=
by
@@ -139,7 +142,9 @@ theorem exponent_pos_of_exists (n : ℕ) (hpos : 0 < n) (hG : ∀ g : G, g ^ n =
exact (Nat.find_spec h).1
#align monoid.exponent_pos_of_exists Monoid.exponent_pos_of_exists
#align add_monoid.exponent_pos_of_exists AddMonoid.exponent_pos_of_exists
+-/
+#print Monoid.exponent_min' /-
@[to_additive]
theorem exponent_min' (n : ℕ) (hpos : 0 < n) (hG : ∀ g : G, g ^ n = 1) : exponent G ≤ n :=
by
@@ -149,7 +154,9 @@ theorem exponent_min' (n : ℕ) (hpos : 0 < n) (hG : ∀ g : G, g ^ n = 1) : exp
· exact ⟨n, hpos, hG⟩
#align monoid.exponent_min' Monoid.exponent_min'
#align add_monoid.exponent_min' AddMonoid.exponent_min'
+-/
+#print Monoid.exponent_min /-
@[to_additive]
theorem exponent_min (m : ℕ) (hpos : 0 < m) (hm : m < exponent G) : ∃ g : G, g ^ m ≠ 1 :=
by
@@ -158,6 +165,7 @@ theorem exponent_min (m : ℕ) (hpos : 0 < m) (hm : m < exponent G) : ∃ g : G,
linarith
#align monoid.exponent_min Monoid.exponent_min
#align add_monoid.exponent_min AddMonoid.exponent_min
+-/
#print Monoid.exp_eq_one_of_subsingleton /-
@[simp, to_additive]
@@ -183,6 +191,7 @@ theorem order_dvd_exponent (g : G) : orderOf g ∣ exponent G :=
variable (G)
+#print Monoid.exponent_dvd_of_forall_pow_eq_one /-
@[to_additive]
theorem exponent_dvd_of_forall_pow_eq_one (G) [Monoid G] (n : ℕ) (hG : ∀ g : G, g ^ n = 1) :
exponent G ∣ n := by
@@ -200,7 +209,9 @@ theorem exponent_dvd_of_forall_pow_eq_one (G) [Monoid G] (n : ℕ) (hG : ∀ g :
linarith
#align monoid.exponent_dvd_of_forall_pow_eq_one Monoid.exponent_dvd_of_forall_pow_eq_one
#align add_monoid.exponent_dvd_of_forall_nsmul_eq_zero AddMonoid.exponent_dvd_of_forall_nsmul_eq_zero
+-/
+#print Monoid.lcm_orderOf_dvd_exponent /-
@[to_additive lcm_add_order_of_dvd_exponent]
theorem lcm_orderOf_dvd_exponent [Fintype G] : (Finset.univ : Finset G).lcm orderOf ∣ exponent G :=
by
@@ -209,6 +220,7 @@ theorem lcm_orderOf_dvd_exponent [Fintype G] : (Finset.univ : Finset G).lcm orde
exact order_dvd_exponent g
#align monoid.lcm_order_of_dvd_exponent Monoid.lcm_orderOf_dvd_exponent
#align add_monoid.lcm_add_order_of_dvd_exponent AddMonoid.lcm_addOrderOf_dvd_exponent
+-/
#print Nat.Prime.exists_orderOf_eq_pow_factorization_exponent /-
@[to_additive exists_order_of_eq_pow_padic_val_nat_add_exponent]
@@ -284,6 +296,7 @@ theorem exponent_eq_zero_iff_range_orderOf_infinite (h : ∀ g : G, 0 < orderOf
#align add_monoid.exponent_eq_zero_iff_range_order_of_infinite AddMonoid.exponent_eq_zero_iff_range_addOrderOf_infinite
-/
+#print Monoid.lcm_order_eq_exponent /-
@[to_additive lcm_add_order_eq_exponent]
theorem lcm_order_eq_exponent [Fintype G] : (Finset.univ : Finset G).lcm orderOf = exponent G :=
by
@@ -293,6 +306,7 @@ theorem lcm_order_eq_exponent [Fintype G] : (Finset.univ : Finset G).lcm orderOf
rw [hm, pow_mul, pow_orderOf_eq_one, one_pow]
#align monoid.lcm_order_eq_exponent Monoid.lcm_order_eq_exponent
#align add_monoid.lcm_add_order_eq_exponent AddMonoid.lcm_addOrder_eq_exponent
+-/
end Monoid
@@ -383,6 +397,7 @@ section CancelCommMonoid
variable [CancelCommMonoid G]
+#print Monoid.exponent_eq_max'_orderOf /-
@[to_additive]
theorem exponent_eq_max'_orderOf [Fintype G] :
exponent G = ((@Finset.univ G _).image orderOf).max' ⟨1, by simp⟩ :=
@@ -391,6 +406,7 @@ theorem exponent_eq_max'_orderOf [Fintype G] :
exact exponent_eq_supr_order_of orderOf_pos
#align monoid.exponent_eq_max'_order_of Monoid.exponent_eq_max'_orderOf
#align add_monoid.exponent_eq_max'_order_of AddMonoid.exponent_eq_max'_addOrderOf
+-/
end CancelCommMonoid
@@ -424,6 +440,7 @@ theorem card_dvd_exponent_pow_rank : Nat.card G ∣ Monoid.exponent G ^ Group.ra
#align card_dvd_exponent_nsmul_rank card_dvd_exponent_nsmul_rank
-/
+#print card_dvd_exponent_pow_rank' /-
@[to_additive]
theorem card_dvd_exponent_pow_rank' {n : ℕ} (hG : ∀ g : G, g ^ n = 1) :
Nat.card G ∣ n ^ Group.rank G :=
@@ -431,6 +448,7 @@ theorem card_dvd_exponent_pow_rank' {n : ℕ} (hG : ∀ g : G, g ^ n = 1) :
(pow_dvd_pow_of_dvd (Monoid.exponent_dvd_of_forall_pow_eq_one G n hG) (Group.rank G))
#align card_dvd_exponent_pow_rank' card_dvd_exponent_pow_rank'
#align card_dvd_exponent_nsmul_rank' card_dvd_exponent_nsmul_rank'
+-/
end CommGroup
mathlib commit https://github.com/leanprover-community/mathlib/commit/7e5137f579de09a059a5ce98f364a04e221aabf0
@@ -127,7 +127,6 @@ theorem pow_eq_mod_exponent {n : ℕ} (g : G) : g ^ n = g ^ (n % exponent G) :=
calc
g ^ n = g ^ (n % exponent G + exponent G * (n / exponent G)) := by rw [Nat.mod_add_div]
_ = g ^ (n % exponent G) := by simp [pow_add, pow_mul, pow_exponent_eq_one]
-
#align monoid.pow_eq_mod_exponent Monoid.pow_eq_mod_exponent
#align add_monoid.nsmul_eq_mod_exponent AddMonoid.nsmul_eq_mod_exponent
-/
mathlib commit https://github.com/leanprover-community/mathlib/commit/cca40788df1b8755d5baf17ab2f27dacc2e17acb
@@ -220,9 +220,9 @@ theorem Nat.Prime.exists_orderOf_eq_pow_factorization_exponent {p : ℕ} (hp : p
rcases eq_or_ne ((exponent G).factorization p) 0 with (h | h)
· refine' ⟨1, by rw [h, pow_zero, orderOf_one]⟩
have he : 0 < exponent G :=
- Ne.bot_lt fun ht => by rw [ht] at h; apply h;
+ Ne.bot_lt fun ht => by rw [ht] at h ; apply h;
rw [bot_eq_zero, Nat.factorization_zero, Finsupp.zero_apply]
- rw [← Finsupp.mem_support_iff] at h
+ rw [← Finsupp.mem_support_iff] at h
obtain ⟨g, hg⟩ : ∃ g : G, g ^ (exponent G / p) ≠ 1 :=
by
suffices key : ¬exponent G ∣ exponent G / p
@@ -236,7 +236,7 @@ theorem Nat.Prime.exists_orderOf_eq_pow_factorization_exponent {p : ℕ} (hp : p
refine' ⟨g ^ k, _⟩
rw [ht]
apply orderOf_eq_prime_pow
- · rwa [hk, mul_comm, ht, pow_succ', ← mul_assoc, Nat.mul_div_cancel _ hp.pos, pow_mul] at hg
+ · rwa [hk, mul_comm, ht, pow_succ', ← mul_assoc, Nat.mul_div_cancel _ hp.pos, pow_mul] at hg
· rw [← Nat.succ_eq_add_one, ← ht, ← pow_mul, mul_comm, ← hk]
exact pow_exponent_eq_one g
#align nat.prime.exists_order_of_eq_pow_factorization_exponent Nat.Prime.exists_orderOf_eq_pow_factorization_exponent
@@ -258,12 +258,12 @@ theorem exponent_ne_zero_iff_range_orderOf_finite (h : ∀ g : G, 0 < orderOf g)
have htpos : 0 < t.prod id :=
by
refine' Finset.prod_pos fun a ha => _
- rw [← Finset.mem_coe, ht] at ha
+ rw [← Finset.mem_coe, ht] at ha
obtain ⟨k, rfl⟩ := ha
exact h k
suffices exponent G ∣ t.prod id by
intro h
- rw [h, zero_dvd_iff] at this
+ rw [h, zero_dvd_iff] at this
exact htpos.ne' this
refine' exponent_dvd_of_forall_pow_eq_one _ _ fun g => _
rw [pow_eq_mod_orderOf, Nat.mod_eq_zero_of_dvd, pow_zero g]
@@ -280,7 +280,7 @@ theorem exponent_eq_zero_iff_range_orderOf_infinite (h : ∀ g : G, 0 < orderOf
exponent G = 0 ↔ (Set.range (orderOf : G → ℕ)).Infinite :=
by
have := exponent_ne_zero_iff_range_orderOf_finite h
- rwa [Ne.def, not_iff_comm, Iff.comm] at this
+ rwa [Ne.def, not_iff_comm, Iff.comm] at this
#align monoid.exponent_eq_zero_iff_range_order_of_infinite Monoid.exponent_eq_zero_iff_range_orderOf_infinite
#align add_monoid.exponent_eq_zero_iff_range_order_of_infinite AddMonoid.exponent_eq_zero_iff_range_addOrderOf_infinite
-/
@@ -336,12 +336,12 @@ theorem exponent_eq_iSup_orderOf (h : ∀ g : G, 0 < orderOf g) : exponent G =
by_contra' h
obtain ⟨p, hp, hpe⟩ := h
replace hp := Nat.prime_of_mem_factors hp
- simp only [Nat.factors_count_eq] at hpe
+ simp only [Nat.factors_count_eq] at hpe
set k := (orderOf t).factorization p with hk
obtain ⟨g, hg⟩ := hp.exists_order_of_eq_pow_factorization_exponent G
suffices orderOf t < orderOf (t ^ p ^ k * g)
by
- rw [ht] at this
+ rw [ht] at this
exact this.not_le (le_csSup hfin.bdd_above <| Set.mem_range_self _)
have hpk : p ^ k ∣ orderOf t := Nat.ord_proj_dvd _ _
have hpk' : orderOf (t ^ p ^ k) = orderOf t / p ^ k := by
@@ -417,7 +417,7 @@ theorem card_dvd_exponent_pow_rank : Nat.card G ∣ Monoid.exponent G ^ Group.ra
rw [← MonoidHom.range_top_iff_surjective, eq_top_iff, ← hS2, closure_le]
exact fun g hg => ⟨Pi.mulSingle ⟨g, hg⟩ ⟨g, mem_zpowers g⟩, noncomm_pi_coprod_mul_single _ _⟩
replace hf := nat_card_dvd_of_surjective f hf
- rw [Nat.card_pi] at hf
+ rw [Nat.card_pi] at hf
refine' hf.trans (Finset.prod_dvd_prod_of_dvd _ _ fun g hg => _)
rw [← order_eq_card_zpowers']
exact Monoid.order_dvd_exponent (g : G)
mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb
@@ -50,7 +50,7 @@ universe u
variable {G : Type u}
-open Classical
+open scoped Classical
namespace Monoid
@@ -401,7 +401,7 @@ section CommGroup
open Subgroup
-open BigOperators
+open scoped BigOperators
variable (G) [CommGroup G] [Group.FG G]
mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb
@@ -111,12 +111,6 @@ theorem exponent_eq_zero_of_order_zero {g : G} (hg : orderOf g = 0) : exponent G
#align add_monoid.exponent_eq_zero_of_order_zero AddMonoid.exponent_eq_zero_addOrder_zero
-/
-/- warning: monoid.pow_exponent_eq_one -> Monoid.pow_exponent_eq_one is a dubious translation:
-lean 3 declaration is
- forall {G : Type.{u1}} [_inst_1 : Monoid.{u1} G] (g : G), Eq.{succ u1} G (HPow.hPow.{u1, 0, u1} G Nat G (instHPow.{u1, 0} G Nat (Monoid.Pow.{u1} G _inst_1)) g (Monoid.exponent.{u1} G _inst_1)) (OfNat.ofNat.{u1} G 1 (OfNat.mk.{u1} G 1 (One.one.{u1} G (MulOneClass.toHasOne.{u1} G (Monoid.toMulOneClass.{u1} G _inst_1)))))
-but is expected to have type
- forall {G : Type.{u1}} [_inst_1 : Monoid.{u1} G] (g : G), Eq.{succ u1} G (HPow.hPow.{u1, 0, u1} G Nat G (instHPow.{u1, 0} G Nat (Monoid.Pow.{u1} G _inst_1)) g (Monoid.exponent.{u1} G _inst_1)) (OfNat.ofNat.{u1} G 1 (One.toOfNat1.{u1} G (Monoid.toOne.{u1} G _inst_1)))
-Case conversion may be inaccurate. Consider using '#align monoid.pow_exponent_eq_one Monoid.pow_exponent_eq_oneₓ'. -/
@[to_additive exponent_nsmul_eq_zero]
theorem pow_exponent_eq_one (g : G) : g ^ exponent G = 1 :=
by
@@ -138,12 +132,6 @@ theorem pow_eq_mod_exponent {n : ℕ} (g : G) : g ^ n = g ^ (n % exponent G) :=
#align add_monoid.nsmul_eq_mod_exponent AddMonoid.nsmul_eq_mod_exponent
-/
-/- warning: monoid.exponent_pos_of_exists -> Monoid.exponent_pos_of_exists is a dubious translation:
-lean 3 declaration is
- forall {G : Type.{u1}} [_inst_1 : Monoid.{u1} G] (n : Nat), (LT.lt.{0} Nat Nat.hasLt (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero))) n) -> (forall (g : G), Eq.{succ u1} G (HPow.hPow.{u1, 0, u1} G Nat G (instHPow.{u1, 0} G Nat (Monoid.Pow.{u1} G _inst_1)) g n) (OfNat.ofNat.{u1} G 1 (OfNat.mk.{u1} G 1 (One.one.{u1} G (MulOneClass.toHasOne.{u1} G (Monoid.toMulOneClass.{u1} G _inst_1)))))) -> (LT.lt.{0} Nat Nat.hasLt (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero))) (Monoid.exponent.{u1} G _inst_1))
-but is expected to have type
- forall {G : Type.{u1}} [_inst_1 : Monoid.{u1} G] (n : Nat), (LT.lt.{0} Nat instLTNat (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0)) n) -> (forall (g : G), Eq.{succ u1} G (HPow.hPow.{u1, 0, u1} G Nat G (instHPow.{u1, 0} G Nat (Monoid.Pow.{u1} G _inst_1)) g n) (OfNat.ofNat.{u1} G 1 (One.toOfNat1.{u1} G (Monoid.toOne.{u1} G _inst_1)))) -> (LT.lt.{0} Nat instLTNat (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0)) (Monoid.exponent.{u1} G _inst_1))
-Case conversion may be inaccurate. Consider using '#align monoid.exponent_pos_of_exists Monoid.exponent_pos_of_existsₓ'. -/
@[to_additive]
theorem exponent_pos_of_exists (n : ℕ) (hpos : 0 < n) (hG : ∀ g : G, g ^ n = 1) : 0 < exponent G :=
by
@@ -153,12 +141,6 @@ theorem exponent_pos_of_exists (n : ℕ) (hpos : 0 < n) (hG : ∀ g : G, g ^ n =
#align monoid.exponent_pos_of_exists Monoid.exponent_pos_of_exists
#align add_monoid.exponent_pos_of_exists AddMonoid.exponent_pos_of_exists
-/- warning: monoid.exponent_min' -> Monoid.exponent_min' is a dubious translation:
-lean 3 declaration is
- forall {G : Type.{u1}} [_inst_1 : Monoid.{u1} G] (n : Nat), (LT.lt.{0} Nat Nat.hasLt (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero))) n) -> (forall (g : G), Eq.{succ u1} G (HPow.hPow.{u1, 0, u1} G Nat G (instHPow.{u1, 0} G Nat (Monoid.Pow.{u1} G _inst_1)) g n) (OfNat.ofNat.{u1} G 1 (OfNat.mk.{u1} G 1 (One.one.{u1} G (MulOneClass.toHasOne.{u1} G (Monoid.toMulOneClass.{u1} G _inst_1)))))) -> (LE.le.{0} Nat Nat.hasLe (Monoid.exponent.{u1} G _inst_1) n)
-but is expected to have type
- forall {G : Type.{u1}} [_inst_1 : Monoid.{u1} G] (n : Nat), (LT.lt.{0} Nat instLTNat (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0)) n) -> (forall (g : G), Eq.{succ u1} G (HPow.hPow.{u1, 0, u1} G Nat G (instHPow.{u1, 0} G Nat (Monoid.Pow.{u1} G _inst_1)) g n) (OfNat.ofNat.{u1} G 1 (One.toOfNat1.{u1} G (Monoid.toOne.{u1} G _inst_1)))) -> (LE.le.{0} Nat instLENat (Monoid.exponent.{u1} G _inst_1) n)
-Case conversion may be inaccurate. Consider using '#align monoid.exponent_min' Monoid.exponent_min'ₓ'. -/
@[to_additive]
theorem exponent_min' (n : ℕ) (hpos : 0 < n) (hG : ∀ g : G, g ^ n = 1) : exponent G ≤ n :=
by
@@ -169,12 +151,6 @@ theorem exponent_min' (n : ℕ) (hpos : 0 < n) (hG : ∀ g : G, g ^ n = 1) : exp
#align monoid.exponent_min' Monoid.exponent_min'
#align add_monoid.exponent_min' AddMonoid.exponent_min'
-/- warning: monoid.exponent_min -> Monoid.exponent_min is a dubious translation:
-lean 3 declaration is
- forall {G : Type.{u1}} [_inst_1 : Monoid.{u1} G] (m : Nat), (LT.lt.{0} Nat Nat.hasLt (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero))) m) -> (LT.lt.{0} Nat Nat.hasLt m (Monoid.exponent.{u1} G _inst_1)) -> (Exists.{succ u1} G (fun (g : G) => Ne.{succ u1} G (HPow.hPow.{u1, 0, u1} G Nat G (instHPow.{u1, 0} G Nat (Monoid.Pow.{u1} G _inst_1)) g m) (OfNat.ofNat.{u1} G 1 (OfNat.mk.{u1} G 1 (One.one.{u1} G (MulOneClass.toHasOne.{u1} G (Monoid.toMulOneClass.{u1} G _inst_1)))))))
-but is expected to have type
- forall {G : Type.{u1}} [_inst_1 : Monoid.{u1} G] (m : Nat), (LT.lt.{0} Nat instLTNat (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0)) m) -> (LT.lt.{0} Nat instLTNat m (Monoid.exponent.{u1} G _inst_1)) -> (Exists.{succ u1} G (fun (g : G) => Ne.{succ u1} G (HPow.hPow.{u1, 0, u1} G Nat G (instHPow.{u1, 0} G Nat (Monoid.Pow.{u1} G _inst_1)) g m) (OfNat.ofNat.{u1} G 1 (One.toOfNat1.{u1} G (Monoid.toOne.{u1} G _inst_1)))))
-Case conversion may be inaccurate. Consider using '#align monoid.exponent_min Monoid.exponent_minₓ'. -/
@[to_additive]
theorem exponent_min (m : ℕ) (hpos : 0 < m) (hm : m < exponent G) : ∃ g : G, g ^ m ≠ 1 :=
by
@@ -208,12 +184,6 @@ theorem order_dvd_exponent (g : G) : orderOf g ∣ exponent G :=
variable (G)
-/- warning: monoid.exponent_dvd_of_forall_pow_eq_one -> Monoid.exponent_dvd_of_forall_pow_eq_one is a dubious translation:
-lean 3 declaration is
- forall (G : Type.{u1}) [_inst_2 : Monoid.{u1} G] (n : Nat), (forall (g : G), Eq.{succ u1} G (HPow.hPow.{u1, 0, u1} G Nat G (instHPow.{u1, 0} G Nat (Monoid.Pow.{u1} G _inst_2)) g n) (OfNat.ofNat.{u1} G 1 (OfNat.mk.{u1} G 1 (One.one.{u1} G (MulOneClass.toHasOne.{u1} G (Monoid.toMulOneClass.{u1} G _inst_2)))))) -> (Dvd.Dvd.{0} Nat Nat.hasDvd (Monoid.exponent.{u1} G _inst_2) n)
-but is expected to have type
- forall (G : Type.{u1}) [_inst_2 : Monoid.{u1} G] (n : Nat), (forall (g : G), Eq.{succ u1} G (HPow.hPow.{u1, 0, u1} G Nat G (instHPow.{u1, 0} G Nat (Monoid.Pow.{u1} G _inst_2)) g n) (OfNat.ofNat.{u1} G 1 (One.toOfNat1.{u1} G (Monoid.toOne.{u1} G _inst_2)))) -> (Dvd.dvd.{0} Nat Nat.instDvdNat (Monoid.exponent.{u1} G _inst_2) n)
-Case conversion may be inaccurate. Consider using '#align monoid.exponent_dvd_of_forall_pow_eq_one Monoid.exponent_dvd_of_forall_pow_eq_oneₓ'. -/
@[to_additive]
theorem exponent_dvd_of_forall_pow_eq_one (G) [Monoid G] (n : ℕ) (hG : ∀ g : G, g ^ n = 1) :
exponent G ∣ n := by
@@ -232,12 +202,6 @@ theorem exponent_dvd_of_forall_pow_eq_one (G) [Monoid G] (n : ℕ) (hG : ∀ g :
#align monoid.exponent_dvd_of_forall_pow_eq_one Monoid.exponent_dvd_of_forall_pow_eq_one
#align add_monoid.exponent_dvd_of_forall_nsmul_eq_zero AddMonoid.exponent_dvd_of_forall_nsmul_eq_zero
-/- warning: monoid.lcm_order_of_dvd_exponent -> Monoid.lcm_orderOf_dvd_exponent is a dubious translation:
-lean 3 declaration is
- forall (G : Type.{u1}) [_inst_1 : Monoid.{u1} G] [_inst_2 : Fintype.{u1} G], Dvd.Dvd.{0} Nat Nat.hasDvd (Finset.lcm.{0, u1} Nat G Nat.cancelCommMonoidWithZero Nat.normalizedGcdMonoid (Finset.univ.{u1} G _inst_2) (orderOf.{u1} G _inst_1)) (Monoid.exponent.{u1} G _inst_1)
-but is expected to have type
- forall (G : Type.{u1}) [_inst_1 : Monoid.{u1} G] [_inst_2 : Fintype.{u1} G], Dvd.dvd.{0} Nat Nat.instDvdNat (Finset.lcm.{0, u1} Nat G Nat.cancelCommMonoidWithZero instNormalizedGCDMonoidNatCancelCommMonoidWithZero (Finset.univ.{u1} G _inst_2) (orderOf.{u1} G _inst_1)) (Monoid.exponent.{u1} G _inst_1)
-Case conversion may be inaccurate. Consider using '#align monoid.lcm_order_of_dvd_exponent Monoid.lcm_orderOf_dvd_exponentₓ'. -/
@[to_additive lcm_add_order_of_dvd_exponent]
theorem lcm_orderOf_dvd_exponent [Fintype G] : (Finset.univ : Finset G).lcm orderOf ∣ exponent G :=
by
@@ -321,12 +285,6 @@ theorem exponent_eq_zero_iff_range_orderOf_infinite (h : ∀ g : G, 0 < orderOf
#align add_monoid.exponent_eq_zero_iff_range_order_of_infinite AddMonoid.exponent_eq_zero_iff_range_addOrderOf_infinite
-/
-/- warning: monoid.lcm_order_eq_exponent -> Monoid.lcm_order_eq_exponent is a dubious translation:
-lean 3 declaration is
- forall {G : Type.{u1}} [_inst_1 : Monoid.{u1} G] [_inst_2 : Fintype.{u1} G], Eq.{1} Nat (Finset.lcm.{0, u1} Nat G Nat.cancelCommMonoidWithZero Nat.normalizedGcdMonoid (Finset.univ.{u1} G _inst_2) (orderOf.{u1} G _inst_1)) (Monoid.exponent.{u1} G _inst_1)
-but is expected to have type
- forall {G : Type.{u1}} [_inst_1 : Monoid.{u1} G] [_inst_2 : Fintype.{u1} G], Eq.{1} Nat (Finset.lcm.{0, u1} Nat G Nat.cancelCommMonoidWithZero instNormalizedGCDMonoidNatCancelCommMonoidWithZero (Finset.univ.{u1} G _inst_2) (orderOf.{u1} G _inst_1)) (Monoid.exponent.{u1} G _inst_1)
-Case conversion may be inaccurate. Consider using '#align monoid.lcm_order_eq_exponent Monoid.lcm_order_eq_exponentₓ'. -/
@[to_additive lcm_add_order_eq_exponent]
theorem lcm_order_eq_exponent [Fintype G] : (Finset.univ : Finset G).lcm orderOf = exponent G :=
by
@@ -426,9 +384,6 @@ section CancelCommMonoid
variable [CancelCommMonoid G]
-/- warning: monoid.exponent_eq_max'_order_of -> Monoid.exponent_eq_max'_orderOf is a dubious translation:
-<too large>
-Case conversion may be inaccurate. Consider using '#align monoid.exponent_eq_max'_order_of Monoid.exponent_eq_max'_orderOfₓ'. -/
@[to_additive]
theorem exponent_eq_max'_orderOf [Fintype G] :
exponent G = ((@Finset.univ G _).image orderOf).max' ⟨1, by simp⟩ :=
@@ -470,12 +425,6 @@ theorem card_dvd_exponent_pow_rank : Nat.card G ∣ Monoid.exponent G ^ Group.ra
#align card_dvd_exponent_nsmul_rank card_dvd_exponent_nsmul_rank
-/
-/- warning: card_dvd_exponent_pow_rank' -> card_dvd_exponent_pow_rank' is a dubious translation:
-lean 3 declaration is
- forall (G : Type.{u1}) [_inst_1 : CommGroup.{u1} G] [_inst_2 : Group.FG.{u1} G (CommGroup.toGroup.{u1} G _inst_1)] {n : Nat}, (forall (g : G), Eq.{succ u1} G (HPow.hPow.{u1, 0, u1} G Nat G (instHPow.{u1, 0} G Nat (Monoid.Pow.{u1} G (DivInvMonoid.toMonoid.{u1} G (Group.toDivInvMonoid.{u1} G (CommGroup.toGroup.{u1} G _inst_1))))) g n) (OfNat.ofNat.{u1} G 1 (OfNat.mk.{u1} G 1 (One.one.{u1} G (MulOneClass.toHasOne.{u1} G (Monoid.toMulOneClass.{u1} G (DivInvMonoid.toMonoid.{u1} G (Group.toDivInvMonoid.{u1} G (CommGroup.toGroup.{u1} G _inst_1))))))))) -> (Dvd.Dvd.{0} Nat Nat.hasDvd (Nat.card.{u1} G) (HPow.hPow.{0, 0, 0} Nat Nat Nat (instHPow.{0, 0} Nat Nat (Monoid.Pow.{0} Nat Nat.monoid)) n (Group.rank.{u1} G (CommGroup.toGroup.{u1} G _inst_1) _inst_2)))
-but is expected to have type
- forall (G : Type.{u1}) [_inst_1 : CommGroup.{u1} G] [_inst_2 : Group.FG.{u1} G (CommGroup.toGroup.{u1} G _inst_1)] {n : Nat}, (forall (g : G), Eq.{succ u1} G (HPow.hPow.{u1, 0, u1} G Nat G (instHPow.{u1, 0} G Nat (Monoid.Pow.{u1} G (DivInvMonoid.toMonoid.{u1} G (Group.toDivInvMonoid.{u1} G (CommGroup.toGroup.{u1} G _inst_1))))) g n) (OfNat.ofNat.{u1} G 1 (One.toOfNat1.{u1} G (InvOneClass.toOne.{u1} G (DivInvOneMonoid.toInvOneClass.{u1} G (DivisionMonoid.toDivInvOneMonoid.{u1} G (DivisionCommMonoid.toDivisionMonoid.{u1} G (CommGroup.toDivisionCommMonoid.{u1} G _inst_1)))))))) -> (Dvd.dvd.{0} Nat Nat.instDvdNat (Nat.card.{u1} G) (HPow.hPow.{0, 0, 0} Nat Nat Nat (instHPow.{0, 0} Nat Nat instPowNat) n (Group.rank.{u1} G (CommGroup.toGroup.{u1} G _inst_1) _inst_2)))
-Case conversion may be inaccurate. Consider using '#align card_dvd_exponent_pow_rank' card_dvd_exponent_pow_rank'ₓ'. -/
@[to_additive]
theorem card_dvd_exponent_pow_rank' {n : ℕ} (hG : ∀ g : G, g ^ n = 1) :
Nat.card G ∣ n ^ Group.rank G :=
mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb
@@ -256,9 +256,7 @@ theorem Nat.Prime.exists_orderOf_eq_pow_factorization_exponent {p : ℕ} (hp : p
rcases eq_or_ne ((exponent G).factorization p) 0 with (h | h)
· refine' ⟨1, by rw [h, pow_zero, orderOf_one]⟩
have he : 0 < exponent G :=
- Ne.bot_lt fun ht => by
- rw [ht] at h
- apply h
+ Ne.bot_lt fun ht => by rw [ht] at h; apply h;
rw [bot_eq_zero, Nat.factorization_zero, Finsupp.zero_apply]
rw [← Finsupp.mem_support_iff] at h
obtain ⟨g, hg⟩ : ∃ g : G, g ^ (exponent G / p) ≠ 1 :=
mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb
@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
Authors: Julian Kuelshammer
! This file was ported from Lean 3 source module group_theory.exponent
-! leanprover-community/mathlib commit 52fa514ec337dd970d71d8de8d0fd68b455a1e54
+! leanprover-community/mathlib commit 0b7c740e25651db0ba63648fbae9f9d6f941e31b
! Please do not edit these lines, except to modify the commit id
! if you have ported upstream changes.
-/
@@ -18,6 +18,9 @@ import Mathbin.Tactic.ByContra
/-!
# Exponent of a group
+> THIS FILE IS SYNCHRONIZED WITH MATHLIB4.
+> Any changes to this file require a corresponding PR to mathlib4.
+
This file defines the exponent of a group, or more generally a monoid. For a group `G` it is defined
to be the minimal `n≥1` such that `g ^ n = 1` for all `g ∈ G`. For a finite group `G`,
it is equal to the lowest common multiple of the order of all elements of the group `G`.
@@ -426,10 +429,7 @@ section CancelCommMonoid
variable [CancelCommMonoid G]
/- warning: monoid.exponent_eq_max'_order_of -> Monoid.exponent_eq_max'_orderOf is a dubious translation:
-lean 3 declaration is
- forall {G : Type.{u1}} [_inst_1 : CancelCommMonoid.{u1} G] [_inst_2 : Fintype.{u1} G], Eq.{1} Nat (Monoid.exponent.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1)))) (Finset.max'.{0} Nat Nat.linearOrder (Finset.image.{u1, 0} G Nat (fun (a : Nat) (b : Nat) => Nat.decidableEq a b) (orderOf.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1)))) (Finset.univ.{u1} G _inst_2)) (Exists.intro.{1} Nat (fun (x : Nat) => Membership.Mem.{0, 0} Nat (Finset.{0} Nat) (Finset.hasMem.{0} Nat) x (Finset.image.{u1, 0} G Nat (fun (a : Nat) (b : Nat) => Nat.decidableEq a b) (orderOf.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1)))) (Finset.univ.{u1} G _inst_2))) (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne))) (Eq.mpr.{0} (Membership.Mem.{0, 0} Nat (Finset.{0} Nat) (Finset.hasMem.{0} Nat) (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne))) (Finset.image.{u1, 0} G Nat (fun (a : Nat) (b : Nat) => Nat.decidableEq a b) (orderOf.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1)))) (Finset.univ.{u1} G _inst_2))) True (id_tag Tactic.IdTag.simp (Eq.{1} Prop (Membership.Mem.{0, 0} Nat (Finset.{0} Nat) (Finset.hasMem.{0} Nat) (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne))) (Finset.image.{u1, 0} G Nat (fun (a : Nat) (b : Nat) => Nat.decidableEq a b) (orderOf.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1)))) (Finset.univ.{u1} G _inst_2))) True) (Eq.trans.{1} Prop (Membership.Mem.{0, 0} Nat (Finset.{0} Nat) (Finset.hasMem.{0} Nat) (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne))) (Finset.image.{u1, 0} G Nat (fun (a : Nat) (b : Nat) => (fun (a : Nat) (b : Nat) => Nat.decidableEq a b) a b) (orderOf.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1)))) (Finset.univ.{u1} G _inst_2))) (Exists.{succ u1} G (fun (a : G) => Eq.{succ u1} G a (OfNat.ofNat.{u1} G 1 (OfNat.mk.{u1} G 1 (One.one.{u1} G (MulOneClass.toHasOne.{u1} G (Monoid.toMulOneClass.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1)))))))))) True (Eq.trans.{1} Prop (Membership.Mem.{0, 0} Nat (Finset.{0} Nat) (Finset.hasMem.{0} Nat) (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne))) (Finset.image.{u1, 0} G Nat (fun (a : Nat) (b : Nat) => (fun (a : Nat) (b : Nat) => Nat.decidableEq a b) a b) (orderOf.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1)))) (Finset.univ.{u1} G _inst_2))) (Exists.{succ u1} G (fun (a : G) => Exists.{0} (Membership.Mem.{u1, u1} G (Finset.{u1} G) (Finset.hasMem.{u1} G) a (Finset.univ.{u1} G _inst_2)) (fun (H : Membership.Mem.{u1, u1} G (Finset.{u1} G) (Finset.hasMem.{u1} G) a (Finset.univ.{u1} G _inst_2)) => Eq.{1} Nat (orderOf.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1))) a) (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne)))))) (Exists.{succ u1} G (fun (a : G) => Eq.{succ u1} G a (OfNat.ofNat.{u1} G 1 (OfNat.mk.{u1} G 1 (One.one.{u1} G (MulOneClass.toHasOne.{u1} G (Monoid.toMulOneClass.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1)))))))))) (propext (Membership.Mem.{0, 0} Nat (Finset.{0} Nat) (Finset.hasMem.{0} Nat) (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne))) (Finset.image.{u1, 0} G Nat (fun (a : Nat) (b : Nat) => (fun (a : Nat) (b : Nat) => Nat.decidableEq a b) a b) (orderOf.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1)))) (Finset.univ.{u1} G _inst_2))) (Exists.{succ u1} G (fun (a : G) => Exists.{0} (Membership.Mem.{u1, u1} G (Finset.{u1} G) (Finset.hasMem.{u1} G) a (Finset.univ.{u1} G _inst_2)) (fun (H : Membership.Mem.{u1, u1} G (Finset.{u1} G) (Finset.hasMem.{u1} G) a (Finset.univ.{u1} G _inst_2)) => Eq.{1} Nat (orderOf.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1))) a) (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne)))))) (Finset.mem_image.{u1, 0} G Nat (fun (a : Nat) (b : Nat) => Nat.decidableEq a b) (orderOf.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1)))) (Finset.univ.{u1} G _inst_2) (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne))))) ((fun (p : G -> Prop) (p_1 : G -> Prop) (e_1 : Eq.{succ u1} (G -> Prop) p p_1) => congr_arg.{succ u1, 1} (G -> Prop) Prop p p_1 (Exists.{succ u1} G) e_1) (fun (a : G) => Exists.{0} (Membership.Mem.{u1, u1} G (Finset.{u1} G) (Finset.hasMem.{u1} G) a (Finset.univ.{u1} G _inst_2)) (fun (H : Membership.Mem.{u1, u1} G (Finset.{u1} G) (Finset.hasMem.{u1} G) a (Finset.univ.{u1} G _inst_2)) => Eq.{1} Nat (orderOf.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1))) a) (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne))))) (fun (a : G) => Eq.{succ u1} G a (OfNat.ofNat.{u1} G 1 (OfNat.mk.{u1} G 1 (One.one.{u1} G (MulOneClass.toHasOne.{u1} G (Monoid.toMulOneClass.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1))))))))) (funext.{succ u1, 1} G (fun (x : G) => Prop) (fun (x : G) => Exists.{0} (Membership.Mem.{u1, u1} G (Finset.{u1} G) (Finset.hasMem.{u1} G) x (Finset.univ.{u1} G _inst_2)) (fun (H : Membership.Mem.{u1, u1} G (Finset.{u1} G) (Finset.hasMem.{u1} G) x (Finset.univ.{u1} G _inst_2)) => Eq.{1} Nat (orderOf.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1))) x) (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne))))) (fun (x : G) => (fun (x_1 : True) => Eq.{succ u1} G x (OfNat.ofNat.{u1} G 1 (OfNat.mk.{u1} G 1 (One.one.{u1} G (MulOneClass.toHasOne.{u1} G (Monoid.toMulOneClass.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1))))))))) True.intro) (fun (a : G) => Eq.trans.{1} Prop (Exists.{0} (Membership.Mem.{u1, u1} G (Finset.{u1} G) (Finset.hasMem.{u1} G) a (Finset.univ.{u1} G _inst_2)) (fun (H : Membership.Mem.{u1, u1} G (Finset.{u1} G) (Finset.hasMem.{u1} G) a (Finset.univ.{u1} G _inst_2)) => Eq.{1} Nat (orderOf.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1))) a) (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne))))) (Exists.{0} True (fun (h : True) => (fun (h : Membership.Mem.{u1, u1} G (Finset.{u1} G) (Finset.hasMem.{u1} G) a (Finset.univ.{u1} G _inst_2)) => Eq.{succ u1} G a (OfNat.ofNat.{u1} G 1 (OfNat.mk.{u1} G 1 (One.one.{u1} G (MulOneClass.toHasOne.{u1} G (Monoid.toMulOneClass.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1))))))))) (Iff.mpr (Membership.Mem.{u1, u1} G (Finset.{u1} G) (Finset.hasMem.{u1} G) a (Finset.univ.{u1} G _inst_2)) True ((fun {α : Type.{u1}} [_inst_1 : Fintype.{u1} α] (x : α) => iff_true_intro (Membership.Mem.{u1, u1} α (Finset.{u1} α) (Finset.hasMem.{u1} α) x (Finset.univ.{u1} α _inst_1)) (Finset.mem_univ.{u1} α _inst_1 x)) G _inst_2 a) h))) ((fun (x : True) => Eq.{succ u1} G a (OfNat.ofNat.{u1} G 1 (OfNat.mk.{u1} G 1 (One.one.{u1} G (MulOneClass.toHasOne.{u1} G (Monoid.toMulOneClass.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1))))))))) True.intro) (exists_prop_congr' (Membership.Mem.{u1, u1} G (Finset.{u1} G) (Finset.hasMem.{u1} G) a (Finset.univ.{u1} G _inst_2)) True (fun (H : Membership.Mem.{u1, u1} G (Finset.{u1} G) (Finset.hasMem.{u1} G) a (Finset.univ.{u1} G _inst_2)) => Eq.{1} Nat (orderOf.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1))) a) (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne)))) (fun (h : Membership.Mem.{u1, u1} G (Finset.{u1} G) (Finset.hasMem.{u1} G) a (Finset.univ.{u1} G _inst_2)) => Eq.{succ u1} G a (OfNat.ofNat.{u1} G 1 (OfNat.mk.{u1} G 1 (One.one.{u1} G (MulOneClass.toHasOne.{u1} G (Monoid.toMulOneClass.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1))))))))) (fun (h : Membership.Mem.{u1, u1} G (Finset.{u1} G) (Finset.hasMem.{u1} G) a (Finset.univ.{u1} G _inst_2)) => orderOf_eq_one_iff.{u1} G a (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1)))) ((fun {α : Type.{u1}} [_inst_1 : Fintype.{u1} α] (x : α) => iff_true_intro (Membership.Mem.{u1, u1} α (Finset.{u1} α) (Finset.hasMem.{u1} α) x (Finset.univ.{u1} α _inst_1)) (Finset.mem_univ.{u1} α _inst_1 x)) G _inst_2 a)) (propext (Exists.{0} True (fun (x : True) => (fun (x : True) => Eq.{succ u1} G a (OfNat.ofNat.{u1} G 1 (OfNat.mk.{u1} G 1 (One.one.{u1} G (MulOneClass.toHasOne.{u1} G (Monoid.toMulOneClass.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1))))))))) x)) ((fun (x : True) => Eq.{succ u1} G a (OfNat.ofNat.{u1} G 1 (OfNat.mk.{u1} G 1 (One.one.{u1} G (MulOneClass.toHasOne.{u1} G (Monoid.toMulOneClass.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1))))))))) True.intro) (exists_true_left (fun (x : True) => Eq.{succ u1} G a (OfNat.ofNat.{u1} G 1 (OfNat.mk.{u1} G 1 (One.one.{u1} G (MulOneClass.toHasOne.{u1} G (Monoid.toMulOneClass.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1))))))))))))))) (propext (Exists.{succ u1} G (fun (a : G) => Eq.{succ u1} G ((fun (a : G) => a) a) ((fun (a : G) => a) (OfNat.ofNat.{u1} G 1 (OfNat.mk.{u1} G 1 (One.one.{u1} G (MulOneClass.toHasOne.{u1} G (Monoid.toMulOneClass.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1))))))))))) True ((fun {α : Type.{u1}} {β : Type.{u1}} (f : α -> β) (a' : α) => iff_true_intro (Exists.{succ u1} α (fun (a : α) => Eq.{succ u1} β (f a) (f a'))) (exists_apply_eq_apply.{succ u1, succ u1} α β f a')) G G (fun (a : G) => a) (OfNat.ofNat.{u1} G 1 (OfNat.mk.{u1} G 1 (One.one.{u1} G (MulOneClass.toHasOne.{u1} G (Monoid.toMulOneClass.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1)))))))))))) trivial)))
-but is expected to have type
- forall {G : Type.{u1}} [_inst_1 : CancelCommMonoid.{u1} G] [_inst_2 : Fintype.{u1} G], Eq.{1} Nat (Monoid.exponent.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1)))) (Finset.max'.{0} Nat Nat.linearOrder (Finset.image.{u1, 0} G Nat (fun (a : Nat) (b : Nat) => instDecidableEqNat a b) (orderOf.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1)))) (Finset.univ.{u1} G _inst_2)) (Exists.intro.{1} Nat (fun (x : Nat) => Membership.mem.{0, 0} Nat (Finset.{0} Nat) (Finset.instMembershipFinset.{0} Nat) x (Finset.image.{u1, 0} G Nat (fun (a : Nat) (b : Nat) => instDecidableEqNat a b) (orderOf.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1)))) (Finset.univ.{u1} G _inst_2))) (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1)) (of_eq_true (Membership.mem.{0, 0} Nat (Finset.{0} Nat) (Finset.instMembershipFinset.{0} Nat) (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1)) (Finset.image.{u1, 0} G Nat (fun (a : Nat) (b : Nat) => instDecidableEqNat a b) (orderOf.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1)))) (Finset.univ.{u1} G _inst_2))) (Eq.trans.{1} Prop (Membership.mem.{0, 0} Nat (Finset.{0} Nat) (Finset.instMembershipFinset.{0} Nat) (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1)) (Finset.image.{u1, 0} G Nat (fun (a : Nat) (b : Nat) => instDecidableEqNat a b) (orderOf.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1)))) (Finset.univ.{u1} G _inst_2))) (Exists.{succ u1} G (fun (x : G) => Eq.{succ u1} G x (OfNat.ofNat.{u1} G 1 (One.toOfNat1.{u1} G (Monoid.toOne.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1)))))))) True (Eq.trans.{1} Prop (Membership.mem.{0, 0} Nat (Finset.{0} Nat) (Finset.instMembershipFinset.{0} Nat) (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1)) (Finset.image.{u1, 0} G Nat (fun (a : Nat) (b : Nat) => instDecidableEqNat a b) (orderOf.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1)))) (Finset.univ.{u1} G _inst_2))) (Exists.{succ u1} G (fun (a : G) => And (Membership.mem.{u1, u1} G (Finset.{u1} G) (Finset.instMembershipFinset.{u1} G) a (Finset.univ.{u1} G _inst_2)) (Eq.{1} Nat (orderOf.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1))) a) (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1))))) (Exists.{succ u1} G (fun (x : G) => Eq.{succ u1} G x (OfNat.ofNat.{u1} G 1 (One.toOfNat1.{u1} G (Monoid.toOne.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1)))))))) (Mathlib.Data.Finset.Image._auxLemma.23.{u1, 0} G Nat (fun (a : Nat) (b : Nat) => instDecidableEqNat a b) (orderOf.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1)))) (Finset.univ.{u1} G _inst_2) (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1))) (congrArg.{succ u1, 1} (G -> Prop) Prop (fun (x : G) => And (Membership.mem.{u1, u1} G (Finset.{u1} G) (Finset.instMembershipFinset.{u1} G) x (Finset.univ.{u1} G _inst_2)) (Eq.{1} Nat (orderOf.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1))) x) (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1)))) (fun (x : G) => Eq.{succ u1} G x (OfNat.ofNat.{u1} G 1 (One.toOfNat1.{u1} G (Monoid.toOne.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1))))))) (Exists.{succ u1} G) (funext.{succ u1, 1} G (fun (x : G) => Prop) (fun (x : G) => And (Membership.mem.{u1, u1} G (Finset.{u1} G) (Finset.instMembershipFinset.{u1} G) x (Finset.univ.{u1} G _inst_2)) (Eq.{1} Nat (orderOf.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1))) x) (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1)))) (fun (x : G) => Eq.{succ u1} G x (OfNat.ofNat.{u1} G 1 (One.toOfNat1.{u1} G (Monoid.toOne.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1))))))) (fun (a : G) => Eq.trans.{1} Prop (And (Membership.mem.{u1, u1} G (Finset.{u1} G) (Finset.instMembershipFinset.{u1} G) a (Finset.univ.{u1} G _inst_2)) (Eq.{1} Nat (orderOf.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1))) a) (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1)))) (And True (Eq.{succ u1} G a (OfNat.ofNat.{u1} G 1 (One.toOfNat1.{u1} G (Monoid.toOne.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1)))))))) (Eq.{succ u1} G a (OfNat.ofNat.{u1} G 1 (One.toOfNat1.{u1} G (Monoid.toOne.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1))))))) (congr.{1, 1} Prop Prop (And (Membership.mem.{u1, u1} G (Finset.{u1} G) (Finset.instMembershipFinset.{u1} G) a (Finset.univ.{u1} G _inst_2))) (And True) (Eq.{1} Nat (orderOf.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1))) a) (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1))) (Eq.{succ u1} G a (OfNat.ofNat.{u1} G 1 (One.toOfNat1.{u1} G (Monoid.toOne.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1))))))) (congrArg.{1, 1} Prop (Prop -> Prop) (Membership.mem.{u1, u1} G (Finset.{u1} G) (Finset.instMembershipFinset.{u1} G) a (Finset.univ.{u1} G _inst_2)) True And (Mathlib.Data.Fintype.Basic._auxLemma.1.{u1} G _inst_2 a)) (Mathlib.GroupTheory.OrderOfElement._auxLemma.8.{u1} G a (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1))))) (true_and (Eq.{succ u1} G a (OfNat.ofNat.{u1} G 1 (One.toOfNat1.{u1} G (Monoid.toOne.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1)))))))))))) (Std.Logic._auxLemma.35.{succ u1} G (OfNat.ofNat.{u1} G 1 (One.toOfNat1.{u1} G (Monoid.toOne.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1)))))))))))
+<too large>
Case conversion may be inaccurate. Consider using '#align monoid.exponent_eq_max'_order_of Monoid.exponent_eq_max'_orderOfₓ'. -/
@[to_additive]
theorem exponent_eq_max'_orderOf [Fintype G] :
mathlib commit https://github.com/leanprover-community/mathlib/commit/ef95945cd48c932c9e034872bd25c3c220d9c946
@@ -55,6 +55,7 @@ section Monoid
variable (G) [Monoid G]
+#print Monoid.ExponentExists /-
/-- A predicate on a monoid saying that there is a positive integer `n` such that `g ^ n = 1`
for all `g`.-/
@[to_additive
@@ -63,7 +64,9 @@ def ExponentExists :=
∃ n, 0 < n ∧ ∀ g : G, g ^ n = 1
#align monoid.exponent_exists Monoid.ExponentExists
#align add_monoid.exponent_exists AddMonoid.ExponentExists
+-/
+#print Monoid.exponent /-
/-- The exponent of a group is the smallest positive integer `n` such that `g ^ n = 1` for all
`g ∈ G` if it exists, otherwise it is zero by convention.-/
@[to_additive
@@ -72,9 +75,11 @@ noncomputable def exponent :=
if h : ExponentExists G then Nat.find h else 0
#align monoid.exponent Monoid.exponent
#align add_monoid.exponent AddMonoid.exponent
+-/
variable {G}
+#print Monoid.exponentExists_iff_ne_zero /-
@[to_additive]
theorem exponentExists_iff_ne_zero : ExponentExists G ↔ exponent G ≠ 0 :=
by
@@ -85,19 +90,30 @@ theorem exponentExists_iff_ne_zero : ExponentExists G ↔ exponent G ≠ 0 :=
· tauto
#align monoid.exponent_exists_iff_ne_zero Monoid.exponentExists_iff_ne_zero
#align add_monoid.exponent_exists_iff_ne_zero AddMonoid.exponentExists_iff_ne_zero
+-/
+#print Monoid.exponent_eq_zero_iff /-
@[to_additive]
theorem exponent_eq_zero_iff : exponent G = 0 ↔ ¬ExponentExists G := by
simp only [exponent_exists_iff_ne_zero, Classical.not_not]
#align monoid.exponent_eq_zero_iff Monoid.exponent_eq_zero_iff
#align add_monoid.exponent_eq_zero_iff AddMonoid.exponent_eq_zero_iff
+-/
+#print Monoid.exponent_eq_zero_of_order_zero /-
@[to_additive]
theorem exponent_eq_zero_of_order_zero {g : G} (hg : orderOf g = 0) : exponent G = 0 :=
exponent_eq_zero_iff.mpr fun ⟨n, hn, hgn⟩ => orderOf_eq_zero_iff'.mp hg n hn <| hgn g
#align monoid.exponent_eq_zero_of_order_zero Monoid.exponent_eq_zero_of_order_zero
-#align add_monoid.exponent_eq_zero_of_order_zero AddMonoid.exponent_eq_zero_of_order_zero
+#align add_monoid.exponent_eq_zero_of_order_zero AddMonoid.exponent_eq_zero_addOrder_zero
+-/
+/- warning: monoid.pow_exponent_eq_one -> Monoid.pow_exponent_eq_one is a dubious translation:
+lean 3 declaration is
+ forall {G : Type.{u1}} [_inst_1 : Monoid.{u1} G] (g : G), Eq.{succ u1} G (HPow.hPow.{u1, 0, u1} G Nat G (instHPow.{u1, 0} G Nat (Monoid.Pow.{u1} G _inst_1)) g (Monoid.exponent.{u1} G _inst_1)) (OfNat.ofNat.{u1} G 1 (OfNat.mk.{u1} G 1 (One.one.{u1} G (MulOneClass.toHasOne.{u1} G (Monoid.toMulOneClass.{u1} G _inst_1)))))
+but is expected to have type
+ forall {G : Type.{u1}} [_inst_1 : Monoid.{u1} G] (g : G), Eq.{succ u1} G (HPow.hPow.{u1, 0, u1} G Nat G (instHPow.{u1, 0} G Nat (Monoid.Pow.{u1} G _inst_1)) g (Monoid.exponent.{u1} G _inst_1)) (OfNat.ofNat.{u1} G 1 (One.toOfNat1.{u1} G (Monoid.toOne.{u1} G _inst_1)))
+Case conversion may be inaccurate. Consider using '#align monoid.pow_exponent_eq_one Monoid.pow_exponent_eq_oneₓ'. -/
@[to_additive exponent_nsmul_eq_zero]
theorem pow_exponent_eq_one (g : G) : g ^ exponent G = 1 :=
by
@@ -108,6 +124,7 @@ theorem pow_exponent_eq_one (g : G) : g ^ exponent G = 1 :=
#align monoid.pow_exponent_eq_one Monoid.pow_exponent_eq_one
#align add_monoid.exponent_nsmul_eq_zero AddMonoid.exponent_nsmul_eq_zero
+#print Monoid.pow_eq_mod_exponent /-
@[to_additive]
theorem pow_eq_mod_exponent {n : ℕ} (g : G) : g ^ n = g ^ (n % exponent G) :=
calc
@@ -116,7 +133,14 @@ theorem pow_eq_mod_exponent {n : ℕ} (g : G) : g ^ n = g ^ (n % exponent G) :=
#align monoid.pow_eq_mod_exponent Monoid.pow_eq_mod_exponent
#align add_monoid.nsmul_eq_mod_exponent AddMonoid.nsmul_eq_mod_exponent
+-/
+/- warning: monoid.exponent_pos_of_exists -> Monoid.exponent_pos_of_exists is a dubious translation:
+lean 3 declaration is
+ forall {G : Type.{u1}} [_inst_1 : Monoid.{u1} G] (n : Nat), (LT.lt.{0} Nat Nat.hasLt (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero))) n) -> (forall (g : G), Eq.{succ u1} G (HPow.hPow.{u1, 0, u1} G Nat G (instHPow.{u1, 0} G Nat (Monoid.Pow.{u1} G _inst_1)) g n) (OfNat.ofNat.{u1} G 1 (OfNat.mk.{u1} G 1 (One.one.{u1} G (MulOneClass.toHasOne.{u1} G (Monoid.toMulOneClass.{u1} G _inst_1)))))) -> (LT.lt.{0} Nat Nat.hasLt (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero))) (Monoid.exponent.{u1} G _inst_1))
+but is expected to have type
+ forall {G : Type.{u1}} [_inst_1 : Monoid.{u1} G] (n : Nat), (LT.lt.{0} Nat instLTNat (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0)) n) -> (forall (g : G), Eq.{succ u1} G (HPow.hPow.{u1, 0, u1} G Nat G (instHPow.{u1, 0} G Nat (Monoid.Pow.{u1} G _inst_1)) g n) (OfNat.ofNat.{u1} G 1 (One.toOfNat1.{u1} G (Monoid.toOne.{u1} G _inst_1)))) -> (LT.lt.{0} Nat instLTNat (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0)) (Monoid.exponent.{u1} G _inst_1))
+Case conversion may be inaccurate. Consider using '#align monoid.exponent_pos_of_exists Monoid.exponent_pos_of_existsₓ'. -/
@[to_additive]
theorem exponent_pos_of_exists (n : ℕ) (hpos : 0 < n) (hG : ∀ g : G, g ^ n = 1) : 0 < exponent G :=
by
@@ -126,6 +150,12 @@ theorem exponent_pos_of_exists (n : ℕ) (hpos : 0 < n) (hG : ∀ g : G, g ^ n =
#align monoid.exponent_pos_of_exists Monoid.exponent_pos_of_exists
#align add_monoid.exponent_pos_of_exists AddMonoid.exponent_pos_of_exists
+/- warning: monoid.exponent_min' -> Monoid.exponent_min' is a dubious translation:
+lean 3 declaration is
+ forall {G : Type.{u1}} [_inst_1 : Monoid.{u1} G] (n : Nat), (LT.lt.{0} Nat Nat.hasLt (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero))) n) -> (forall (g : G), Eq.{succ u1} G (HPow.hPow.{u1, 0, u1} G Nat G (instHPow.{u1, 0} G Nat (Monoid.Pow.{u1} G _inst_1)) g n) (OfNat.ofNat.{u1} G 1 (OfNat.mk.{u1} G 1 (One.one.{u1} G (MulOneClass.toHasOne.{u1} G (Monoid.toMulOneClass.{u1} G _inst_1)))))) -> (LE.le.{0} Nat Nat.hasLe (Monoid.exponent.{u1} G _inst_1) n)
+but is expected to have type
+ forall {G : Type.{u1}} [_inst_1 : Monoid.{u1} G] (n : Nat), (LT.lt.{0} Nat instLTNat (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0)) n) -> (forall (g : G), Eq.{succ u1} G (HPow.hPow.{u1, 0, u1} G Nat G (instHPow.{u1, 0} G Nat (Monoid.Pow.{u1} G _inst_1)) g n) (OfNat.ofNat.{u1} G 1 (One.toOfNat1.{u1} G (Monoid.toOne.{u1} G _inst_1)))) -> (LE.le.{0} Nat instLENat (Monoid.exponent.{u1} G _inst_1) n)
+Case conversion may be inaccurate. Consider using '#align monoid.exponent_min' Monoid.exponent_min'ₓ'. -/
@[to_additive]
theorem exponent_min' (n : ℕ) (hpos : 0 < n) (hG : ∀ g : G, g ^ n = 1) : exponent G ≤ n :=
by
@@ -136,6 +166,12 @@ theorem exponent_min' (n : ℕ) (hpos : 0 < n) (hG : ∀ g : G, g ^ n = 1) : exp
#align monoid.exponent_min' Monoid.exponent_min'
#align add_monoid.exponent_min' AddMonoid.exponent_min'
+/- warning: monoid.exponent_min -> Monoid.exponent_min is a dubious translation:
+lean 3 declaration is
+ forall {G : Type.{u1}} [_inst_1 : Monoid.{u1} G] (m : Nat), (LT.lt.{0} Nat Nat.hasLt (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero))) m) -> (LT.lt.{0} Nat Nat.hasLt m (Monoid.exponent.{u1} G _inst_1)) -> (Exists.{succ u1} G (fun (g : G) => Ne.{succ u1} G (HPow.hPow.{u1, 0, u1} G Nat G (instHPow.{u1, 0} G Nat (Monoid.Pow.{u1} G _inst_1)) g m) (OfNat.ofNat.{u1} G 1 (OfNat.mk.{u1} G 1 (One.one.{u1} G (MulOneClass.toHasOne.{u1} G (Monoid.toMulOneClass.{u1} G _inst_1)))))))
+but is expected to have type
+ forall {G : Type.{u1}} [_inst_1 : Monoid.{u1} G] (m : Nat), (LT.lt.{0} Nat instLTNat (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0)) m) -> (LT.lt.{0} Nat instLTNat m (Monoid.exponent.{u1} G _inst_1)) -> (Exists.{succ u1} G (fun (g : G) => Ne.{succ u1} G (HPow.hPow.{u1, 0, u1} G Nat G (instHPow.{u1, 0} G Nat (Monoid.Pow.{u1} G _inst_1)) g m) (OfNat.ofNat.{u1} G 1 (One.toOfNat1.{u1} G (Monoid.toOne.{u1} G _inst_1)))))
+Case conversion may be inaccurate. Consider using '#align monoid.exponent_min Monoid.exponent_minₓ'. -/
@[to_additive]
theorem exponent_min (m : ℕ) (hpos : 0 < m) (hm : m < exponent G) : ∃ g : G, g ^ m ≠ 1 :=
by
@@ -145,6 +181,7 @@ theorem exponent_min (m : ℕ) (hpos : 0 < m) (hm : m < exponent G) : ∃ g : G,
#align monoid.exponent_min Monoid.exponent_min
#align add_monoid.exponent_min AddMonoid.exponent_min
+#print Monoid.exp_eq_one_of_subsingleton /-
@[simp, to_additive]
theorem exp_eq_one_of_subsingleton [Subsingleton G] : exponent G = 1 :=
by
@@ -156,15 +193,24 @@ theorem exp_eq_one_of_subsingleton [Subsingleton G] : exponent G = 1 :=
simp
#align monoid.exp_eq_one_of_subsingleton Monoid.exp_eq_one_of_subsingleton
#align add_monoid.exp_eq_zero_of_subsingleton AddMonoid.exp_eq_zero_of_subsingleton
+-/
+#print Monoid.order_dvd_exponent /-
@[to_additive add_order_dvd_exponent]
theorem order_dvd_exponent (g : G) : orderOf g ∣ exponent G :=
orderOf_dvd_of_pow_eq_one <| pow_exponent_eq_one g
#align monoid.order_dvd_exponent Monoid.order_dvd_exponent
-#align add_monoid.add_order_dvd_exponent AddMonoid.add_order_dvd_exponent
+#align add_monoid.add_order_dvd_exponent AddMonoid.addOrder_dvd_exponent
+-/
variable (G)
+/- warning: monoid.exponent_dvd_of_forall_pow_eq_one -> Monoid.exponent_dvd_of_forall_pow_eq_one is a dubious translation:
+lean 3 declaration is
+ forall (G : Type.{u1}) [_inst_2 : Monoid.{u1} G] (n : Nat), (forall (g : G), Eq.{succ u1} G (HPow.hPow.{u1, 0, u1} G Nat G (instHPow.{u1, 0} G Nat (Monoid.Pow.{u1} G _inst_2)) g n) (OfNat.ofNat.{u1} G 1 (OfNat.mk.{u1} G 1 (One.one.{u1} G (MulOneClass.toHasOne.{u1} G (Monoid.toMulOneClass.{u1} G _inst_2)))))) -> (Dvd.Dvd.{0} Nat Nat.hasDvd (Monoid.exponent.{u1} G _inst_2) n)
+but is expected to have type
+ forall (G : Type.{u1}) [_inst_2 : Monoid.{u1} G] (n : Nat), (forall (g : G), Eq.{succ u1} G (HPow.hPow.{u1, 0, u1} G Nat G (instHPow.{u1, 0} G Nat (Monoid.Pow.{u1} G _inst_2)) g n) (OfNat.ofNat.{u1} G 1 (One.toOfNat1.{u1} G (Monoid.toOne.{u1} G _inst_2)))) -> (Dvd.dvd.{0} Nat Nat.instDvdNat (Monoid.exponent.{u1} G _inst_2) n)
+Case conversion may be inaccurate. Consider using '#align monoid.exponent_dvd_of_forall_pow_eq_one Monoid.exponent_dvd_of_forall_pow_eq_oneₓ'. -/
@[to_additive]
theorem exponent_dvd_of_forall_pow_eq_one (G) [Monoid G] (n : ℕ) (hG : ∀ g : G, g ^ n = 1) :
exponent G ∣ n := by
@@ -183,6 +229,12 @@ theorem exponent_dvd_of_forall_pow_eq_one (G) [Monoid G] (n : ℕ) (hG : ∀ g :
#align monoid.exponent_dvd_of_forall_pow_eq_one Monoid.exponent_dvd_of_forall_pow_eq_one
#align add_monoid.exponent_dvd_of_forall_nsmul_eq_zero AddMonoid.exponent_dvd_of_forall_nsmul_eq_zero
+/- warning: monoid.lcm_order_of_dvd_exponent -> Monoid.lcm_orderOf_dvd_exponent is a dubious translation:
+lean 3 declaration is
+ forall (G : Type.{u1}) [_inst_1 : Monoid.{u1} G] [_inst_2 : Fintype.{u1} G], Dvd.Dvd.{0} Nat Nat.hasDvd (Finset.lcm.{0, u1} Nat G Nat.cancelCommMonoidWithZero Nat.normalizedGcdMonoid (Finset.univ.{u1} G _inst_2) (orderOf.{u1} G _inst_1)) (Monoid.exponent.{u1} G _inst_1)
+but is expected to have type
+ forall (G : Type.{u1}) [_inst_1 : Monoid.{u1} G] [_inst_2 : Fintype.{u1} G], Dvd.dvd.{0} Nat Nat.instDvdNat (Finset.lcm.{0, u1} Nat G Nat.cancelCommMonoidWithZero instNormalizedGCDMonoidNatCancelCommMonoidWithZero (Finset.univ.{u1} G _inst_2) (orderOf.{u1} G _inst_1)) (Monoid.exponent.{u1} G _inst_1)
+Case conversion may be inaccurate. Consider using '#align monoid.lcm_order_of_dvd_exponent Monoid.lcm_orderOf_dvd_exponentₓ'. -/
@[to_additive lcm_add_order_of_dvd_exponent]
theorem lcm_orderOf_dvd_exponent [Fintype G] : (Finset.univ : Finset G).lcm orderOf ∣ exponent G :=
by
@@ -190,8 +242,9 @@ theorem lcm_orderOf_dvd_exponent [Fintype G] : (Finset.univ : Finset G).lcm orde
intro g hg
exact order_dvd_exponent g
#align monoid.lcm_order_of_dvd_exponent Monoid.lcm_orderOf_dvd_exponent
-#align add_monoid.lcm_add_order_of_dvd_exponent AddMonoid.lcm_add_orderOf_dvd_exponent
+#align add_monoid.lcm_add_order_of_dvd_exponent AddMonoid.lcm_addOrderOf_dvd_exponent
+#print Nat.Prime.exists_orderOf_eq_pow_factorization_exponent /-
@[to_additive exists_order_of_eq_pow_padic_val_nat_add_exponent]
theorem Nat.Prime.exists_orderOf_eq_pow_factorization_exponent {p : ℕ} (hp : p.Prime) :
∃ g : G, orderOf g = p ^ (exponent G).factorization p :=
@@ -222,10 +275,12 @@ theorem Nat.Prime.exists_orderOf_eq_pow_factorization_exponent {p : ℕ} (hp : p
· rw [← Nat.succ_eq_add_one, ← ht, ← pow_mul, mul_comm, ← hk]
exact pow_exponent_eq_one g
#align nat.prime.exists_order_of_eq_pow_factorization_exponent Nat.Prime.exists_orderOf_eq_pow_factorization_exponent
-#align nat.prime.exists_order_of_eq_pow_padic_val_nat_add_exponent Nat.Prime.exists_orderOf_eq_pow_padic_val_nat_add_exponent
+#align nat.prime.exists_order_of_eq_pow_padic_val_nat_add_exponent Nat.Prime.exists_addOrderOf_eq_pow_padic_val_nat_add_exponent
+-/
variable {G}
+#print Monoid.exponent_ne_zero_iff_range_orderOf_finite /-
@[to_additive]
theorem exponent_ne_zero_iff_range_orderOf_finite (h : ∀ g : G, 0 < orderOf g) :
exponent G ≠ 0 ↔ (Set.range (orderOf : G → ℕ)).Finite :=
@@ -251,8 +306,10 @@ theorem exponent_ne_zero_iff_range_orderOf_finite (h : ∀ g : G, 0 < orderOf g)
rw [← Finset.mem_coe, ht]
exact Set.mem_range_self g
#align monoid.exponent_ne_zero_iff_range_order_of_finite Monoid.exponent_ne_zero_iff_range_orderOf_finite
-#align add_monoid.exponent_ne_zero_iff_range_order_of_finite AddMonoid.exponent_ne_zero_iff_range_orderOf_finite
+#align add_monoid.exponent_ne_zero_iff_range_order_of_finite AddMonoid.exponent_ne_zero_iff_range_addOrderOf_finite
+-/
+#print Monoid.exponent_eq_zero_iff_range_orderOf_infinite /-
@[to_additive]
theorem exponent_eq_zero_iff_range_orderOf_infinite (h : ∀ g : G, 0 < orderOf g) :
exponent G = 0 ↔ (Set.range (orderOf : G → ℕ)).Infinite :=
@@ -260,8 +317,15 @@ theorem exponent_eq_zero_iff_range_orderOf_infinite (h : ∀ g : G, 0 < orderOf
have := exponent_ne_zero_iff_range_orderOf_finite h
rwa [Ne.def, not_iff_comm, Iff.comm] at this
#align monoid.exponent_eq_zero_iff_range_order_of_infinite Monoid.exponent_eq_zero_iff_range_orderOf_infinite
-#align add_monoid.exponent_eq_zero_iff_range_order_of_infinite AddMonoid.exponent_eq_zero_iff_range_orderOf_infinite
+#align add_monoid.exponent_eq_zero_iff_range_order_of_infinite AddMonoid.exponent_eq_zero_iff_range_addOrderOf_infinite
+-/
+/- warning: monoid.lcm_order_eq_exponent -> Monoid.lcm_order_eq_exponent is a dubious translation:
+lean 3 declaration is
+ forall {G : Type.{u1}} [_inst_1 : Monoid.{u1} G] [_inst_2 : Fintype.{u1} G], Eq.{1} Nat (Finset.lcm.{0, u1} Nat G Nat.cancelCommMonoidWithZero Nat.normalizedGcdMonoid (Finset.univ.{u1} G _inst_2) (orderOf.{u1} G _inst_1)) (Monoid.exponent.{u1} G _inst_1)
+but is expected to have type
+ forall {G : Type.{u1}} [_inst_1 : Monoid.{u1} G] [_inst_2 : Fintype.{u1} G], Eq.{1} Nat (Finset.lcm.{0, u1} Nat G Nat.cancelCommMonoidWithZero instNormalizedGCDMonoidNatCancelCommMonoidWithZero (Finset.univ.{u1} G _inst_2) (orderOf.{u1} G _inst_1)) (Monoid.exponent.{u1} G _inst_1)
+Case conversion may be inaccurate. Consider using '#align monoid.lcm_order_eq_exponent Monoid.lcm_order_eq_exponentₓ'. -/
@[to_additive lcm_add_order_eq_exponent]
theorem lcm_order_eq_exponent [Fintype G] : (Finset.univ : Finset G).lcm orderOf = exponent G :=
by
@@ -270,7 +334,7 @@ theorem lcm_order_eq_exponent [Fintype G] : (Finset.univ : Finset G).lcm orderOf
obtain ⟨m, hm⟩ : orderOf g ∣ finset.univ.lcm orderOf := Finset.dvd_lcm (Finset.mem_univ g)
rw [hm, pow_mul, pow_orderOf_eq_one, one_pow]
#align monoid.lcm_order_eq_exponent Monoid.lcm_order_eq_exponent
-#align add_monoid.lcm_add_order_eq_exponent AddMonoid.lcm_add_order_eq_exponent
+#align add_monoid.lcm_add_order_eq_exponent AddMonoid.lcm_addOrder_eq_exponent
end Monoid
@@ -278,6 +342,7 @@ section LeftCancelMonoid
variable [LeftCancelMonoid G]
+#print Monoid.exponent_ne_zero_of_finite /-
@[to_additive]
theorem exponent_ne_zero_of_finite [Finite G] : exponent G ≠ 0 :=
by
@@ -285,6 +350,7 @@ theorem exponent_ne_zero_of_finite [Finite G] : exponent G ≠ 0 :=
simpa [← lcm_order_eq_exponent, Finset.lcm_eq_zero_iff] using fun x => (orderOf_pos x).ne'
#align monoid.exponent_ne_zero_of_finite Monoid.exponent_ne_zero_of_finite
#align add_monoid.exponent_ne_zero_of_finite AddMonoid.exponent_ne_zero_of_finite
+-/
end LeftCancelMonoid
@@ -292,6 +358,7 @@ section CommMonoid
variable [CommMonoid G]
+#print Monoid.exponent_eq_iSup_orderOf /-
@[to_additive]
theorem exponent_eq_iSup_orderOf (h : ∀ g : G, 0 < orderOf g) : exponent G = ⨆ g : G, orderOf g :=
by
@@ -335,10 +402,12 @@ theorem exponent_eq_iSup_orderOf (h : ∀ g : G, 0 < orderOf g) : exponent G =
exact one_lt_pow hp.one_lt a.succ_ne_zero
exact hpk
#align monoid.exponent_eq_supr_order_of Monoid.exponent_eq_iSup_orderOf
-#align add_monoid.exponent_eq_supr_order_of AddMonoid.exponent_eq_iSup_orderOf
+#align add_monoid.exponent_eq_supr_order_of AddMonoid.exponent_eq_iSup_addOrderOf
+-/
+#print Monoid.exponent_eq_iSup_orderOf' /-
@[to_additive]
-theorem exponent_eq_iSup_order_of' :
+theorem exponent_eq_iSup_orderOf' :
exponent G = if ∃ g : G, orderOf g = 0 then 0 else ⨆ g : G, orderOf g :=
by
split_ifs
@@ -346,8 +415,9 @@ theorem exponent_eq_iSup_order_of' :
exact exponent_eq_zero_of_order_zero hg
· have := not_exists.mp h
exact exponent_eq_supr_order_of fun g => Ne.bot_lt <| this g
-#align monoid.exponent_eq_supr_order_of' Monoid.exponent_eq_iSup_order_of'
-#align add_monoid.exponent_eq_supr_order_of' AddMonoid.exponent_eq_iSup_order_of'
+#align monoid.exponent_eq_supr_order_of' Monoid.exponent_eq_iSup_orderOf'
+#align add_monoid.exponent_eq_supr_order_of' AddMonoid.exponent_eq_iSup_addOrderOf'
+-/
end CommMonoid
@@ -355,6 +425,12 @@ section CancelCommMonoid
variable [CancelCommMonoid G]
+/- warning: monoid.exponent_eq_max'_order_of -> Monoid.exponent_eq_max'_orderOf is a dubious translation:
+lean 3 declaration is
+ forall {G : Type.{u1}} [_inst_1 : CancelCommMonoid.{u1} G] [_inst_2 : Fintype.{u1} G], Eq.{1} Nat (Monoid.exponent.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1)))) (Finset.max'.{0} Nat Nat.linearOrder (Finset.image.{u1, 0} G Nat (fun (a : Nat) (b : Nat) => Nat.decidableEq a b) (orderOf.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1)))) (Finset.univ.{u1} G _inst_2)) (Exists.intro.{1} Nat (fun (x : Nat) => Membership.Mem.{0, 0} Nat (Finset.{0} Nat) (Finset.hasMem.{0} Nat) x (Finset.image.{u1, 0} G Nat (fun (a : Nat) (b : Nat) => Nat.decidableEq a b) (orderOf.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1)))) (Finset.univ.{u1} G _inst_2))) (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne))) (Eq.mpr.{0} (Membership.Mem.{0, 0} Nat (Finset.{0} Nat) (Finset.hasMem.{0} Nat) (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne))) (Finset.image.{u1, 0} G Nat (fun (a : Nat) (b : Nat) => Nat.decidableEq a b) (orderOf.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1)))) (Finset.univ.{u1} G _inst_2))) True (id_tag Tactic.IdTag.simp (Eq.{1} Prop (Membership.Mem.{0, 0} Nat (Finset.{0} Nat) (Finset.hasMem.{0} Nat) (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne))) (Finset.image.{u1, 0} G Nat (fun (a : Nat) (b : Nat) => Nat.decidableEq a b) (orderOf.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1)))) (Finset.univ.{u1} G _inst_2))) True) (Eq.trans.{1} Prop (Membership.Mem.{0, 0} Nat (Finset.{0} Nat) (Finset.hasMem.{0} Nat) (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne))) (Finset.image.{u1, 0} G Nat (fun (a : Nat) (b : Nat) => (fun (a : Nat) (b : Nat) => Nat.decidableEq a b) a b) (orderOf.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1)))) (Finset.univ.{u1} G _inst_2))) (Exists.{succ u1} G (fun (a : G) => Eq.{succ u1} G a (OfNat.ofNat.{u1} G 1 (OfNat.mk.{u1} G 1 (One.one.{u1} G (MulOneClass.toHasOne.{u1} G (Monoid.toMulOneClass.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1)))))))))) True (Eq.trans.{1} Prop (Membership.Mem.{0, 0} Nat (Finset.{0} Nat) (Finset.hasMem.{0} Nat) (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne))) (Finset.image.{u1, 0} G Nat (fun (a : Nat) (b : Nat) => (fun (a : Nat) (b : Nat) => Nat.decidableEq a b) a b) (orderOf.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1)))) (Finset.univ.{u1} G _inst_2))) (Exists.{succ u1} G (fun (a : G) => Exists.{0} (Membership.Mem.{u1, u1} G (Finset.{u1} G) (Finset.hasMem.{u1} G) a (Finset.univ.{u1} G _inst_2)) (fun (H : Membership.Mem.{u1, u1} G (Finset.{u1} G) (Finset.hasMem.{u1} G) a (Finset.univ.{u1} G _inst_2)) => Eq.{1} Nat (orderOf.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1))) a) (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne)))))) (Exists.{succ u1} G (fun (a : G) => Eq.{succ u1} G a (OfNat.ofNat.{u1} G 1 (OfNat.mk.{u1} G 1 (One.one.{u1} G (MulOneClass.toHasOne.{u1} G (Monoid.toMulOneClass.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1)))))))))) (propext (Membership.Mem.{0, 0} Nat (Finset.{0} Nat) (Finset.hasMem.{0} Nat) (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne))) (Finset.image.{u1, 0} G Nat (fun (a : Nat) (b : Nat) => (fun (a : Nat) (b : Nat) => Nat.decidableEq a b) a b) (orderOf.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1)))) (Finset.univ.{u1} G _inst_2))) (Exists.{succ u1} G (fun (a : G) => Exists.{0} (Membership.Mem.{u1, u1} G (Finset.{u1} G) (Finset.hasMem.{u1} G) a (Finset.univ.{u1} G _inst_2)) (fun (H : Membership.Mem.{u1, u1} G (Finset.{u1} G) (Finset.hasMem.{u1} G) a (Finset.univ.{u1} G _inst_2)) => Eq.{1} Nat (orderOf.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1))) a) (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne)))))) (Finset.mem_image.{u1, 0} G Nat (fun (a : Nat) (b : Nat) => Nat.decidableEq a b) (orderOf.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1)))) (Finset.univ.{u1} G _inst_2) (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne))))) ((fun (p : G -> Prop) (p_1 : G -> Prop) (e_1 : Eq.{succ u1} (G -> Prop) p p_1) => congr_arg.{succ u1, 1} (G -> Prop) Prop p p_1 (Exists.{succ u1} G) e_1) (fun (a : G) => Exists.{0} (Membership.Mem.{u1, u1} G (Finset.{u1} G) (Finset.hasMem.{u1} G) a (Finset.univ.{u1} G _inst_2)) (fun (H : Membership.Mem.{u1, u1} G (Finset.{u1} G) (Finset.hasMem.{u1} G) a (Finset.univ.{u1} G _inst_2)) => Eq.{1} Nat (orderOf.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1))) a) (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne))))) (fun (a : G) => Eq.{succ u1} G a (OfNat.ofNat.{u1} G 1 (OfNat.mk.{u1} G 1 (One.one.{u1} G (MulOneClass.toHasOne.{u1} G (Monoid.toMulOneClass.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1))))))))) (funext.{succ u1, 1} G (fun (x : G) => Prop) (fun (x : G) => Exists.{0} (Membership.Mem.{u1, u1} G (Finset.{u1} G) (Finset.hasMem.{u1} G) x (Finset.univ.{u1} G _inst_2)) (fun (H : Membership.Mem.{u1, u1} G (Finset.{u1} G) (Finset.hasMem.{u1} G) x (Finset.univ.{u1} G _inst_2)) => Eq.{1} Nat (orderOf.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1))) x) (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne))))) (fun (x : G) => (fun (x_1 : True) => Eq.{succ u1} G x (OfNat.ofNat.{u1} G 1 (OfNat.mk.{u1} G 1 (One.one.{u1} G (MulOneClass.toHasOne.{u1} G (Monoid.toMulOneClass.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1))))))))) True.intro) (fun (a : G) => Eq.trans.{1} Prop (Exists.{0} (Membership.Mem.{u1, u1} G (Finset.{u1} G) (Finset.hasMem.{u1} G) a (Finset.univ.{u1} G _inst_2)) (fun (H : Membership.Mem.{u1, u1} G (Finset.{u1} G) (Finset.hasMem.{u1} G) a (Finset.univ.{u1} G _inst_2)) => Eq.{1} Nat (orderOf.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1))) a) (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne))))) (Exists.{0} True (fun (h : True) => (fun (h : Membership.Mem.{u1, u1} G (Finset.{u1} G) (Finset.hasMem.{u1} G) a (Finset.univ.{u1} G _inst_2)) => Eq.{succ u1} G a (OfNat.ofNat.{u1} G 1 (OfNat.mk.{u1} G 1 (One.one.{u1} G (MulOneClass.toHasOne.{u1} G (Monoid.toMulOneClass.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1))))))))) (Iff.mpr (Membership.Mem.{u1, u1} G (Finset.{u1} G) (Finset.hasMem.{u1} G) a (Finset.univ.{u1} G _inst_2)) True ((fun {α : Type.{u1}} [_inst_1 : Fintype.{u1} α] (x : α) => iff_true_intro (Membership.Mem.{u1, u1} α (Finset.{u1} α) (Finset.hasMem.{u1} α) x (Finset.univ.{u1} α _inst_1)) (Finset.mem_univ.{u1} α _inst_1 x)) G _inst_2 a) h))) ((fun (x : True) => Eq.{succ u1} G a (OfNat.ofNat.{u1} G 1 (OfNat.mk.{u1} G 1 (One.one.{u1} G (MulOneClass.toHasOne.{u1} G (Monoid.toMulOneClass.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1))))))))) True.intro) (exists_prop_congr' (Membership.Mem.{u1, u1} G (Finset.{u1} G) (Finset.hasMem.{u1} G) a (Finset.univ.{u1} G _inst_2)) True (fun (H : Membership.Mem.{u1, u1} G (Finset.{u1} G) (Finset.hasMem.{u1} G) a (Finset.univ.{u1} G _inst_2)) => Eq.{1} Nat (orderOf.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1))) a) (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne)))) (fun (h : Membership.Mem.{u1, u1} G (Finset.{u1} G) (Finset.hasMem.{u1} G) a (Finset.univ.{u1} G _inst_2)) => Eq.{succ u1} G a (OfNat.ofNat.{u1} G 1 (OfNat.mk.{u1} G 1 (One.one.{u1} G (MulOneClass.toHasOne.{u1} G (Monoid.toMulOneClass.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1))))))))) (fun (h : Membership.Mem.{u1, u1} G (Finset.{u1} G) (Finset.hasMem.{u1} G) a (Finset.univ.{u1} G _inst_2)) => orderOf_eq_one_iff.{u1} G a (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1)))) ((fun {α : Type.{u1}} [_inst_1 : Fintype.{u1} α] (x : α) => iff_true_intro (Membership.Mem.{u1, u1} α (Finset.{u1} α) (Finset.hasMem.{u1} α) x (Finset.univ.{u1} α _inst_1)) (Finset.mem_univ.{u1} α _inst_1 x)) G _inst_2 a)) (propext (Exists.{0} True (fun (x : True) => (fun (x : True) => Eq.{succ u1} G a (OfNat.ofNat.{u1} G 1 (OfNat.mk.{u1} G 1 (One.one.{u1} G (MulOneClass.toHasOne.{u1} G (Monoid.toMulOneClass.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1))))))))) x)) ((fun (x : True) => Eq.{succ u1} G a (OfNat.ofNat.{u1} G 1 (OfNat.mk.{u1} G 1 (One.one.{u1} G (MulOneClass.toHasOne.{u1} G (Monoid.toMulOneClass.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1))))))))) True.intro) (exists_true_left (fun (x : True) => Eq.{succ u1} G a (OfNat.ofNat.{u1} G 1 (OfNat.mk.{u1} G 1 (One.one.{u1} G (MulOneClass.toHasOne.{u1} G (Monoid.toMulOneClass.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1))))))))))))))) (propext (Exists.{succ u1} G (fun (a : G) => Eq.{succ u1} G ((fun (a : G) => a) a) ((fun (a : G) => a) (OfNat.ofNat.{u1} G 1 (OfNat.mk.{u1} G 1 (One.one.{u1} G (MulOneClass.toHasOne.{u1} G (Monoid.toMulOneClass.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1))))))))))) True ((fun {α : Type.{u1}} {β : Type.{u1}} (f : α -> β) (a' : α) => iff_true_intro (Exists.{succ u1} α (fun (a : α) => Eq.{succ u1} β (f a) (f a'))) (exists_apply_eq_apply.{succ u1, succ u1} α β f a')) G G (fun (a : G) => a) (OfNat.ofNat.{u1} G 1 (OfNat.mk.{u1} G 1 (One.one.{u1} G (MulOneClass.toHasOne.{u1} G (Monoid.toMulOneClass.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1)))))))))))) trivial)))
+but is expected to have type
+ forall {G : Type.{u1}} [_inst_1 : CancelCommMonoid.{u1} G] [_inst_2 : Fintype.{u1} G], Eq.{1} Nat (Monoid.exponent.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1)))) (Finset.max'.{0} Nat Nat.linearOrder (Finset.image.{u1, 0} G Nat (fun (a : Nat) (b : Nat) => instDecidableEqNat a b) (orderOf.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1)))) (Finset.univ.{u1} G _inst_2)) (Exists.intro.{1} Nat (fun (x : Nat) => Membership.mem.{0, 0} Nat (Finset.{0} Nat) (Finset.instMembershipFinset.{0} Nat) x (Finset.image.{u1, 0} G Nat (fun (a : Nat) (b : Nat) => instDecidableEqNat a b) (orderOf.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1)))) (Finset.univ.{u1} G _inst_2))) (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1)) (of_eq_true (Membership.mem.{0, 0} Nat (Finset.{0} Nat) (Finset.instMembershipFinset.{0} Nat) (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1)) (Finset.image.{u1, 0} G Nat (fun (a : Nat) (b : Nat) => instDecidableEqNat a b) (orderOf.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1)))) (Finset.univ.{u1} G _inst_2))) (Eq.trans.{1} Prop (Membership.mem.{0, 0} Nat (Finset.{0} Nat) (Finset.instMembershipFinset.{0} Nat) (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1)) (Finset.image.{u1, 0} G Nat (fun (a : Nat) (b : Nat) => instDecidableEqNat a b) (orderOf.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1)))) (Finset.univ.{u1} G _inst_2))) (Exists.{succ u1} G (fun (x : G) => Eq.{succ u1} G x (OfNat.ofNat.{u1} G 1 (One.toOfNat1.{u1} G (Monoid.toOne.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1)))))))) True (Eq.trans.{1} Prop (Membership.mem.{0, 0} Nat (Finset.{0} Nat) (Finset.instMembershipFinset.{0} Nat) (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1)) (Finset.image.{u1, 0} G Nat (fun (a : Nat) (b : Nat) => instDecidableEqNat a b) (orderOf.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1)))) (Finset.univ.{u1} G _inst_2))) (Exists.{succ u1} G (fun (a : G) => And (Membership.mem.{u1, u1} G (Finset.{u1} G) (Finset.instMembershipFinset.{u1} G) a (Finset.univ.{u1} G _inst_2)) (Eq.{1} Nat (orderOf.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1))) a) (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1))))) (Exists.{succ u1} G (fun (x : G) => Eq.{succ u1} G x (OfNat.ofNat.{u1} G 1 (One.toOfNat1.{u1} G (Monoid.toOne.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1)))))))) (Mathlib.Data.Finset.Image._auxLemma.23.{u1, 0} G Nat (fun (a : Nat) (b : Nat) => instDecidableEqNat a b) (orderOf.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1)))) (Finset.univ.{u1} G _inst_2) (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1))) (congrArg.{succ u1, 1} (G -> Prop) Prop (fun (x : G) => And (Membership.mem.{u1, u1} G (Finset.{u1} G) (Finset.instMembershipFinset.{u1} G) x (Finset.univ.{u1} G _inst_2)) (Eq.{1} Nat (orderOf.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1))) x) (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1)))) (fun (x : G) => Eq.{succ u1} G x (OfNat.ofNat.{u1} G 1 (One.toOfNat1.{u1} G (Monoid.toOne.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1))))))) (Exists.{succ u1} G) (funext.{succ u1, 1} G (fun (x : G) => Prop) (fun (x : G) => And (Membership.mem.{u1, u1} G (Finset.{u1} G) (Finset.instMembershipFinset.{u1} G) x (Finset.univ.{u1} G _inst_2)) (Eq.{1} Nat (orderOf.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1))) x) (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1)))) (fun (x : G) => Eq.{succ u1} G x (OfNat.ofNat.{u1} G 1 (One.toOfNat1.{u1} G (Monoid.toOne.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1))))))) (fun (a : G) => Eq.trans.{1} Prop (And (Membership.mem.{u1, u1} G (Finset.{u1} G) (Finset.instMembershipFinset.{u1} G) a (Finset.univ.{u1} G _inst_2)) (Eq.{1} Nat (orderOf.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1))) a) (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1)))) (And True (Eq.{succ u1} G a (OfNat.ofNat.{u1} G 1 (One.toOfNat1.{u1} G (Monoid.toOne.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1)))))))) (Eq.{succ u1} G a (OfNat.ofNat.{u1} G 1 (One.toOfNat1.{u1} G (Monoid.toOne.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1))))))) (congr.{1, 1} Prop Prop (And (Membership.mem.{u1, u1} G (Finset.{u1} G) (Finset.instMembershipFinset.{u1} G) a (Finset.univ.{u1} G _inst_2))) (And True) (Eq.{1} Nat (orderOf.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1))) a) (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1))) (Eq.{succ u1} G a (OfNat.ofNat.{u1} G 1 (One.toOfNat1.{u1} G (Monoid.toOne.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1))))))) (congrArg.{1, 1} Prop (Prop -> Prop) (Membership.mem.{u1, u1} G (Finset.{u1} G) (Finset.instMembershipFinset.{u1} G) a (Finset.univ.{u1} G _inst_2)) True And (Mathlib.Data.Fintype.Basic._auxLemma.1.{u1} G _inst_2 a)) (Mathlib.GroupTheory.OrderOfElement._auxLemma.8.{u1} G a (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1))))) (true_and (Eq.{succ u1} G a (OfNat.ofNat.{u1} G 1 (One.toOfNat1.{u1} G (Monoid.toOne.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1)))))))))))) (Std.Logic._auxLemma.35.{succ u1} G (OfNat.ofNat.{u1} G 1 (One.toOfNat1.{u1} G (Monoid.toOne.{u1} G (RightCancelMonoid.toMonoid.{u1} G (CancelMonoid.toRightCancelMonoid.{u1} G (CancelCommMonoid.toCancelMonoid.{u1} G _inst_1)))))))))))
+Case conversion may be inaccurate. Consider using '#align monoid.exponent_eq_max'_order_of Monoid.exponent_eq_max'_orderOfₓ'. -/
@[to_additive]
theorem exponent_eq_max'_orderOf [Fintype G] :
exponent G = ((@Finset.univ G _).image orderOf).max' ⟨1, by simp⟩ :=
@@ -362,7 +438,7 @@ theorem exponent_eq_max'_orderOf [Fintype G] :
rw [← Finset.Nonempty.cSup_eq_max', Finset.coe_image, Finset.coe_univ, Set.image_univ, ← iSup]
exact exponent_eq_supr_order_of orderOf_pos
#align monoid.exponent_eq_max'_order_of Monoid.exponent_eq_max'_orderOf
-#align add_monoid.exponent_eq_max'_order_of AddMonoid.exponent_eq_max'_order_of
+#align add_monoid.exponent_eq_max'_order_of AddMonoid.exponent_eq_max'_addOrderOf
end CancelCommMonoid
@@ -376,6 +452,7 @@ open BigOperators
variable (G) [CommGroup G] [Group.FG G]
+#print card_dvd_exponent_pow_rank /-
@[to_additive]
theorem card_dvd_exponent_pow_rank : Nat.card G ∣ Monoid.exponent G ^ Group.rank G :=
by
@@ -393,7 +470,14 @@ theorem card_dvd_exponent_pow_rank : Nat.card G ∣ Monoid.exponent G ^ Group.ra
exact Monoid.order_dvd_exponent (g : G)
#align card_dvd_exponent_pow_rank card_dvd_exponent_pow_rank
#align card_dvd_exponent_nsmul_rank card_dvd_exponent_nsmul_rank
+-/
+/- warning: card_dvd_exponent_pow_rank' -> card_dvd_exponent_pow_rank' is a dubious translation:
+lean 3 declaration is
+ forall (G : Type.{u1}) [_inst_1 : CommGroup.{u1} G] [_inst_2 : Group.FG.{u1} G (CommGroup.toGroup.{u1} G _inst_1)] {n : Nat}, (forall (g : G), Eq.{succ u1} G (HPow.hPow.{u1, 0, u1} G Nat G (instHPow.{u1, 0} G Nat (Monoid.Pow.{u1} G (DivInvMonoid.toMonoid.{u1} G (Group.toDivInvMonoid.{u1} G (CommGroup.toGroup.{u1} G _inst_1))))) g n) (OfNat.ofNat.{u1} G 1 (OfNat.mk.{u1} G 1 (One.one.{u1} G (MulOneClass.toHasOne.{u1} G (Monoid.toMulOneClass.{u1} G (DivInvMonoid.toMonoid.{u1} G (Group.toDivInvMonoid.{u1} G (CommGroup.toGroup.{u1} G _inst_1))))))))) -> (Dvd.Dvd.{0} Nat Nat.hasDvd (Nat.card.{u1} G) (HPow.hPow.{0, 0, 0} Nat Nat Nat (instHPow.{0, 0} Nat Nat (Monoid.Pow.{0} Nat Nat.monoid)) n (Group.rank.{u1} G (CommGroup.toGroup.{u1} G _inst_1) _inst_2)))
+but is expected to have type
+ forall (G : Type.{u1}) [_inst_1 : CommGroup.{u1} G] [_inst_2 : Group.FG.{u1} G (CommGroup.toGroup.{u1} G _inst_1)] {n : Nat}, (forall (g : G), Eq.{succ u1} G (HPow.hPow.{u1, 0, u1} G Nat G (instHPow.{u1, 0} G Nat (Monoid.Pow.{u1} G (DivInvMonoid.toMonoid.{u1} G (Group.toDivInvMonoid.{u1} G (CommGroup.toGroup.{u1} G _inst_1))))) g n) (OfNat.ofNat.{u1} G 1 (One.toOfNat1.{u1} G (InvOneClass.toOne.{u1} G (DivInvOneMonoid.toInvOneClass.{u1} G (DivisionMonoid.toDivInvOneMonoid.{u1} G (DivisionCommMonoid.toDivisionMonoid.{u1} G (CommGroup.toDivisionCommMonoid.{u1} G _inst_1)))))))) -> (Dvd.dvd.{0} Nat Nat.instDvdNat (Nat.card.{u1} G) (HPow.hPow.{0, 0, 0} Nat Nat Nat (instHPow.{0, 0} Nat Nat instPowNat) n (Group.rank.{u1} G (CommGroup.toGroup.{u1} G _inst_1) _inst_2)))
+Case conversion may be inaccurate. Consider using '#align card_dvd_exponent_pow_rank' card_dvd_exponent_pow_rank'ₓ'. -/
@[to_additive]
theorem card_dvd_exponent_pow_rank' {n : ℕ} (hG : ∀ g : G, g ^ n = 1) :
Nat.card G ∣ n ^ Group.rank G :=
mathlib commit https://github.com/leanprover-community/mathlib/commit/8d33f09cd7089ecf074b4791907588245aec5d1b
@@ -234,7 +234,7 @@ theorem exponent_ne_zero_iff_range_orderOf_finite (h : ∀ g : G, 0 < orderOf g)
· by_contra h
obtain ⟨m, ⟨t, rfl⟩, het⟩ := Set.Infinite.exists_gt h (exponent G)
exact pow_ne_one_of_lt_orderOf' he het (pow_exponent_eq_one t)
- · lift Set.range orderOf to Finset ℕ using he
+ · lift Set.range orderOf to Finset ℕ using he with t ht
have htpos : 0 < t.prod id :=
by
refine' Finset.prod_pos fun a ha => _
mathlib commit https://github.com/leanprover-community/mathlib/commit/75e7fca56381d056096ce5d05e938f63a6567828
@@ -234,7 +234,7 @@ theorem exponent_ne_zero_iff_range_orderOf_finite (h : ∀ g : G, 0 < orderOf g)
· by_contra h
obtain ⟨m, ⟨t, rfl⟩, het⟩ := Set.Infinite.exists_gt h (exponent G)
exact pow_ne_one_of_lt_orderOf' he het (pow_exponent_eq_one t)
- · lift Set.range orderOf to Finset ℕ using he with t ht
+ · lift Set.range orderOf to Finset ℕ using he
have htpos : 0 < t.prod id :=
by
refine' Finset.prod_pos fun a ha => _
mathlib commit https://github.com/leanprover-community/mathlib/commit/0b9eaaa7686280fad8cce467f5c3c57ee6ce77f8
@@ -374,7 +374,7 @@ open Subgroup
open BigOperators
-variable (G) [CommGroup G] [Group.Fg G]
+variable (G) [CommGroup G] [Group.FG G]
@[to_additive]
theorem card_dvd_exponent_pow_rank : Nat.card G ∣ Monoid.exponent G ^ Group.rank G :=
mathlib commit https://github.com/leanprover-community/mathlib/commit/e3fb84046afd187b710170887195d50bada934ee
@@ -293,11 +293,11 @@ section CommMonoid
variable [CommMonoid G]
@[to_additive]
-theorem exponent_eq_supᵢ_orderOf (h : ∀ g : G, 0 < orderOf g) : exponent G = ⨆ g : G, orderOf g :=
+theorem exponent_eq_iSup_orderOf (h : ∀ g : G, 0 < orderOf g) : exponent G = ⨆ g : G, orderOf g :=
by
- rw [supᵢ]
+ rw [iSup]
rcases eq_or_ne (exponent G) 0 with (he | he)
- · rw [he, Set.Infinite.Nat.supₛ_eq_zero <| (exponent_eq_zero_iff_range_order_of_infinite h).1 he]
+ · rw [he, Set.Infinite.Nat.sSup_eq_zero <| (exponent_eq_zero_iff_range_order_of_infinite h).1 he]
have hne : (Set.range (orderOf : G → ℕ)).Nonempty := ⟨1, 1, orderOf_one⟩
have hfin : (Set.range (orderOf : G → ℕ)).Finite := by
rwa [← exponent_ne_zero_iff_range_order_of_finite h]
@@ -316,7 +316,7 @@ theorem exponent_eq_supᵢ_orderOf (h : ∀ g : G, 0 < orderOf g) : exponent G =
suffices orderOf t < orderOf (t ^ p ^ k * g)
by
rw [ht] at this
- exact this.not_le (le_csupₛ hfin.bdd_above <| Set.mem_range_self _)
+ exact this.not_le (le_csSup hfin.bdd_above <| Set.mem_range_self _)
have hpk : p ^ k ∣ orderOf t := Nat.ord_proj_dvd _ _
have hpk' : orderOf (t ^ p ^ k) = orderOf t / p ^ k := by
rw [orderOf_pow' t (pow_ne_zero k hp.ne_zero), Nat.gcd_eq_right hpk]
@@ -334,11 +334,11 @@ theorem exponent_eq_supᵢ_orderOf (h : ∀ g : G, 0 < orderOf g) : exponent G =
lt_mul_iff_one_lt_right <| h t, ← pow_succ']
exact one_lt_pow hp.one_lt a.succ_ne_zero
exact hpk
-#align monoid.exponent_eq_supr_order_of Monoid.exponent_eq_supᵢ_orderOf
-#align add_monoid.exponent_eq_supr_order_of AddMonoid.exponent_eq_supᵢ_orderOf
+#align monoid.exponent_eq_supr_order_of Monoid.exponent_eq_iSup_orderOf
+#align add_monoid.exponent_eq_supr_order_of AddMonoid.exponent_eq_iSup_orderOf
@[to_additive]
-theorem exponent_eq_supᵢ_order_of' :
+theorem exponent_eq_iSup_order_of' :
exponent G = if ∃ g : G, orderOf g = 0 then 0 else ⨆ g : G, orderOf g :=
by
split_ifs
@@ -346,8 +346,8 @@ theorem exponent_eq_supᵢ_order_of' :
exact exponent_eq_zero_of_order_zero hg
· have := not_exists.mp h
exact exponent_eq_supr_order_of fun g => Ne.bot_lt <| this g
-#align monoid.exponent_eq_supr_order_of' Monoid.exponent_eq_supᵢ_order_of'
-#align add_monoid.exponent_eq_supr_order_of' AddMonoid.exponent_eq_supᵢ_order_of'
+#align monoid.exponent_eq_supr_order_of' Monoid.exponent_eq_iSup_order_of'
+#align add_monoid.exponent_eq_supr_order_of' AddMonoid.exponent_eq_iSup_order_of'
end CommMonoid
@@ -359,7 +359,7 @@ variable [CancelCommMonoid G]
theorem exponent_eq_max'_orderOf [Fintype G] :
exponent G = ((@Finset.univ G _).image orderOf).max' ⟨1, by simp⟩ :=
by
- rw [← Finset.Nonempty.cSup_eq_max', Finset.coe_image, Finset.coe_univ, Set.image_univ, ← supᵢ]
+ rw [← Finset.Nonempty.cSup_eq_max', Finset.coe_image, Finset.coe_univ, Set.image_univ, ← iSup]
exact exponent_eq_supr_order_of orderOf_pos
#align monoid.exponent_eq_max'_order_of Monoid.exponent_eq_max'_orderOf
#align add_monoid.exponent_eq_max'_order_of AddMonoid.exponent_eq_max'_order_of
mathlib commit https://github.com/leanprover-community/mathlib/commit/9b2b58d6b14b895b2f375108e765cb47de71aebd
@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
Authors: Julian Kuelshammer
! This file was ported from Lean 3 source module group_theory.exponent
-! leanprover-community/mathlib commit 70fd9563a21e7b963887c9360bd29b2393e6225a
+! leanprover-community/mathlib commit 52fa514ec337dd970d71d8de8d0fd68b455a1e54
! Please do not edit these lines, except to modify the commit id
! if you have ported upstream changes.
-/
@@ -232,7 +232,7 @@ theorem exponent_ne_zero_iff_range_orderOf_finite (h : ∀ g : G, 0 < orderOf g)
by
refine' ⟨fun he => _, fun he => _⟩
· by_contra h
- obtain ⟨m, ⟨t, rfl⟩, het⟩ := Set.Infinite.exists_nat_lt h (exponent G)
+ obtain ⟨m, ⟨t, rfl⟩, het⟩ := Set.Infinite.exists_gt h (exponent G)
exact pow_ne_one_of_lt_orderOf' he het (pow_exponent_eq_one t)
· lift Set.range orderOf to Finset ℕ using he with t ht
have htpos : 0 < t.prod id :=
mathlib commit https://github.com/leanprover-community/mathlib/commit/2651125b48fc5c170ab1111afd0817c903b1fc6c
@@ -297,9 +297,7 @@ theorem exponent_eq_supᵢ_orderOf (h : ∀ g : G, 0 < orderOf g) : exponent G =
by
rw [supᵢ]
rcases eq_or_ne (exponent G) 0 with (he | he)
- ·
- rw [he,
- Nat.Set.Infinite.Nat.supₛ_eq_zero <| (exponent_eq_zero_iff_range_order_of_infinite h).1 he]
+ · rw [he, Set.Infinite.Nat.supₛ_eq_zero <| (exponent_eq_zero_iff_range_order_of_infinite h).1 he]
have hne : (Set.range (orderOf : G → ℕ)).Nonempty := ⟨1, 1, orderOf_one⟩
have hfin : (Set.range (orderOf : G → ℕ)).Finite := by
rwa [← exponent_ne_zero_iff_range_order_of_finite h]
mathlib commit https://github.com/leanprover-community/mathlib/commit/bd9851ca476957ea4549eb19b40e7b5ade9428cc
@@ -233,7 +233,7 @@ theorem exponent_ne_zero_iff_range_orderOf_finite (h : ∀ g : G, 0 < orderOf g)
refine' ⟨fun he => _, fun he => _⟩
· by_contra h
obtain ⟨m, ⟨t, rfl⟩, het⟩ := Set.Infinite.exists_nat_lt h (exponent G)
- exact pow_ne_one_of_lt_order_of' he het (pow_exponent_eq_one t)
+ exact pow_ne_one_of_lt_orderOf' he het (pow_exponent_eq_one t)
· lift Set.range orderOf to Finset ℕ using he with t ht
have htpos : 0 < t.prod id :=
by
mathlib commit https://github.com/leanprover-community/mathlib/commit/bd9851ca476957ea4549eb19b40e7b5ade9428cc
@@ -495,8 +495,8 @@ theorem exists_orderOf_eq_exponent (hG : ExponentExists G) : ∃ g : G, orderOf
rw [(Commute.all _ g).orderOf_mul_eq_mul_orderOf_of_coprime hcoprime, hpk',
hg, ha, hk, pow_add, pow_add, pow_one, ← mul_assoc, ← mul_assoc,
Nat.div_mul_cancel, mul_assoc, lt_mul_iff_one_lt_right <| hG.orderOf_pos t, ← pow_succ]
- exact one_lt_pow hp.one_lt a.succ_ne_zero
- exact hpk
+ · exact one_lt_pow hp.one_lt a.succ_ne_zero
+ · exact hpk
@[to_additive]
theorem exponent_eq_iSup_orderOf (h : ∀ g : G, 0 < orderOf g) :
Try to have the date on the same line as the attribute: this makes it easier to rewrite these into machine-readable form. One date is was added: the deprecation was in the same PR as nearby lemmas.
@@ -244,7 +244,7 @@ theorem exponent_dvd {n : ℕ} : exponent G ∣ n ↔ ∀ g : G, orderOf g ∣ n
variable (G)
-@[to_additive (attr := deprecated)]
+@[to_additive (attr := deprecated)] -- 2024-02-17
theorem exponent_dvd_of_forall_orderOf_dvd (n : ℕ) (h : ∀ g : G, orderOf g ∣ n) : exponent G ∣ n :=
exponent_dvd.mpr h
@@ -551,8 +551,7 @@ section Group
variable [Group G]
--- Deprecated: 2024-02-17
-@[to_additive (attr := deprecated Monoid.one_lt_exponent) AddGroup.one_lt_exponent]
+@[to_additive (attr := deprecated Monoid.one_lt_exponent) AddGroup.one_lt_exponent] -- 2024-02-17
lemma Group.one_lt_exponent [Finite G] [Nontrivial G] : 1 < Monoid.exponent G :=
Monoid.one_lt_exponent
@@ -719,7 +718,7 @@ lemma inv_eq_self_of_orderOf_eq_two {x : G} (hx : orderOf x = 2) :
x⁻¹ = x :=
inv_eq_of_mul_eq_one_left <| pow_two (a := x) ▸ hx ▸ pow_orderOf_eq_one x
--- TODO: Delete
+-- TODO: Delete; deprecated on 2024-02-17
/-- Any group of exponent two is abelian. -/
@[to_additive (attr := reducible, deprecated) "Any additive group of exponent two is abelian."]
def instCommGroupOfExponentTwo (hG : Monoid.exponent G = 2) : CommGroup G where
Previously Mathlib.GroupTheory.Perm.Fin
knew about LinearMap
for no good reason, because it relied on Mathlib.RingTheory.Int.Basic
for some basic things, but that file also has heavy imports.
Co-authored-by: Scott Morrison <scott.morrison@gmail.com>
@@ -7,6 +7,7 @@ import Mathlib.Data.ZMod.Quotient
import Mathlib.GroupTheory.NoncommPiCoprod
import Mathlib.GroupTheory.OrderOfElement
import Mathlib.Algebra.GCDMonoid.Finset
+import Mathlib.Algebra.GCDMonoid.Nat
import Mathlib.Data.Nat.Factorization.Basic
import Mathlib.Tactic.ByContra
import Mathlib.Tactic.Peel
@@ -93,7 +93,7 @@ open MulOpposite in
theorem _root_.MulOpposite.exponent : exponent (MulOpposite G) = exponent G := by
simp only [Monoid.exponent, ExponentExists]
congr!
- all_goals exact ⟨(op_injective <| · <| op ·), (unop_injective <| . <| unop .)⟩
+ all_goals exact ⟨(op_injective <| · <| op ·), (unop_injective <| · <| unop ·)⟩
@[to_additive]
theorem ExponentExists.isOfFinOrder (h : ExponentExists G) {g : G} : IsOfFinOrder g :=
Purely automatic replacement. If this is in any way controversial; I'm happy to just close this PR.
@@ -59,7 +59,7 @@ section Monoid
variable (G) [Monoid G]
/-- A predicate on a monoid saying that there is a positive integer `n` such that `g ^ n = 1`
- for all `g`.-/
+ for all `g`. -/
@[to_additive
"A predicate on an additive monoid saying that there is a positive integer `n` such\n
that `n • g = 0` for all `g`."]
@@ -69,7 +69,7 @@ def ExponentExists :=
#align add_monoid.exponent_exists AddMonoid.ExponentExists
/-- The exponent of a group is the smallest positive integer `n` such that `g ^ n = 1` for all
- `g ∈ G` if it exists, otherwise it is zero by convention.-/
+ `g ∈ G` if it exists, otherwise it is zero by convention. -/
@[to_additive
"The exponent of an additive group is the smallest positive integer `n` such that\n
`n • g = 0` for all `g ∈ G` if it exists, otherwise it is zero by convention."]
@@ -327,7 +327,7 @@ order `p`. -/
lemma exponent_eq_prime_iff {G : Type*} [Monoid G] [Nontrivial G] {p : ℕ} (hp : p.Prime) :
Monoid.exponent G = p ↔ ∀ g : G, g ≠ 1 → orderOf g = p := by
refine ⟨fun hG g hg ↦ ?_, fun h ↦ dvd_antisymm ?_ ?_⟩
- · rw [Ne.def, ← orderOf_eq_one_iff] at hg
+ · rw [Ne, ← orderOf_eq_one_iff] at hg
exact Eq.symm <| (hp.dvd_iff_eq hg).mp <| hG ▸ Monoid.order_dvd_exponent g
· rw [exponent_dvd]
intro g
@@ -368,7 +368,7 @@ theorem exponent_ne_zero_iff_range_orderOf_finite (h : ∀ g : G, 0 < orderOf g)
theorem exponent_eq_zero_iff_range_orderOf_infinite (h : ∀ g : G, 0 < orderOf g) :
exponent G = 0 ↔ (Set.range (orderOf : G → ℕ)).Infinite := by
have := exponent_ne_zero_iff_range_orderOf_finite h
- rwa [Ne.def, not_iff_comm, Iff.comm] at this
+ rwa [Ne, not_iff_comm, Iff.comm] at this
#align monoid.exponent_eq_zero_iff_range_order_of_infinite Monoid.exponent_eq_zero_iff_range_orderOf_infinite
#align add_monoid.exponent_eq_zero_iff_range_order_of_infinite AddMonoid.exponent_eq_zero_iff_range_addOrderOf_infinite
We change the following field in the definition of an additive commutative monoid:
nsmul_succ : ∀ (n : ℕ) (x : G),
- AddMonoid.nsmul (n + 1) x = x + AddMonoid.nsmul n x
+ AddMonoid.nsmul (n + 1) x = AddMonoid.nsmul n x + x
where the latter is more natural
We adjust the definitions of ^
in monoids, groups, etc.
Originally there was a warning comment about why this natural order was preferred
use
x * npowRec n x
and notnpowRec n x * x
in the definition to make sure that definitional unfolding ofnpowRec
is blocked, to avoid deep recursion issues.
but it seems to no longer apply.
Remarks on the PR :
pow_succ
and pow_succ'
have switched their meanings.Ideal.IsPrime.mul_mem_pow
which is defined in [Mathlib/RingTheory/DedekindDomain/Ideal.lean]. Changing the order of operation forced me to add the symmetric lemma Ideal.IsPrime.mem_pow_mul
.@@ -280,7 +280,7 @@ theorem _root_.Nat.Prime.exists_orderOf_eq_pow_factorization_exponent {p : ℕ}
refine' ⟨g ^ k, _⟩
rw [ht]
apply orderOf_eq_prime_pow
- · rwa [hk, mul_comm, ht, pow_succ', ← mul_assoc, Nat.mul_div_cancel _ hp.pos, pow_mul] at hg
+ · rwa [hk, mul_comm, ht, pow_succ, ← mul_assoc, Nat.mul_div_cancel _ hp.pos, pow_mul] at hg
· rw [← Nat.succ_eq_add_one, ← ht, ← pow_mul, mul_comm, ← hk]
exact pow_exponent_eq_one g
#align nat.prime.exists_order_of_eq_pow_factorization_exponent Nat.Prime.exists_orderOf_eq_pow_factorization_exponent
@@ -493,7 +493,7 @@ theorem exists_orderOf_eq_exponent (hG : ExponentExists G) : ∃ g : G, orderOf
apply Nat.pow_succ_factorization_not_dvd (hG.orderOf_pos <| t ^ p ^ k).ne' hp
rw [(Commute.all _ g).orderOf_mul_eq_mul_orderOf_of_coprime hcoprime, hpk',
hg, ha, hk, pow_add, pow_add, pow_one, ← mul_assoc, ← mul_assoc,
- Nat.div_mul_cancel, mul_assoc, lt_mul_iff_one_lt_right <| hG.orderOf_pos t, ← pow_succ']
+ Nat.div_mul_cancel, mul_assoc, lt_mul_iff_one_lt_right <| hG.orderOf_pos t, ← pow_succ]
exact one_lt_pow hp.one_lt a.succ_ne_zero
exact hpk
I removed some redundant instance arguments throughout Mathlib. To do this, I used VS Code's regex search. See https://leanprover.zulipchat.com/#narrow/stream/287929-mathlib4/topic/repeating.20instances.20from.20variable.20command I closed the previous PR for this and reopened it.
@@ -429,10 +429,10 @@ end Submonoid
section LeftCancelMonoid
-variable [LeftCancelMonoid G]
+variable [LeftCancelMonoid G] [Finite G]
@[to_additive]
-theorem ExponentExists.of_finite [Finite G] : ExponentExists G := by
+theorem ExponentExists.of_finite : ExponentExists G := by
let _inst := Fintype.ofFinite G
simp only [Monoid.ExponentExists]
refine ⟨(Finset.univ : Finset G).lcm orderOf, ?_, fun g => ?_⟩
@@ -441,14 +441,13 @@ theorem ExponentExists.of_finite [Finite G] : ExponentExists G := by
exact order_dvd_exponent g
@[to_additive]
-theorem exponent_ne_zero_of_finite [Finite G] : exponent G ≠ 0 :=
+theorem exponent_ne_zero_of_finite : exponent G ≠ 0 :=
ExponentExists.of_finite.exponent_ne_zero
#align monoid.exponent_ne_zero_of_finite Monoid.exponent_ne_zero_of_finite
#align add_monoid.exponent_ne_zero_of_finite AddMonoid.exponent_ne_zero_of_finite
@[to_additive AddMonoid.one_lt_exponent]
-lemma one_lt_exponent [LeftCancelMonoid G] [Finite G] [Nontrivial G] :
- 1 < Monoid.exponent G := by
+lemma one_lt_exponent [Nontrivial G] : 1 < Monoid.exponent G := by
rw [Nat.one_lt_iff_ne_zero_and_ne_one]
exact ⟨exponent_ne_zero_of_finite, mt exp_eq_one_iff.mp (not_subsingleton G)⟩
We add Commute.orderOf_mul_pow_eq_lcm
: if two commuting elements x
and y
of a monoid have order n
and m
, there is an element of order lcm n m
. The result actually gives an explicit (computable) element, written as the product of a power of x
and a power of y
.
Co-authored-by: Junyan Xu <[junyanxu.math@gmail.com](mailto:junyanxu.math@gmail.com)>
@@ -286,6 +286,41 @@ theorem _root_.Nat.Prime.exists_orderOf_eq_pow_factorization_exponent {p : ℕ}
#align nat.prime.exists_order_of_eq_pow_factorization_exponent Nat.Prime.exists_orderOf_eq_pow_factorization_exponent
#align nat.prime.exists_order_of_eq_pow_padic_val_nat_add_exponent Nat.Prime.exists_addOrderOf_eq_pow_padic_val_nat_add_exponent
+variable {G} in
+open Nat in
+/-- If two commuting elements `x` and `y` of a monoid have order `n` and `m`, there is an element
+of order `lcm n m`. The result actually gives an explicit (computable) element, written as the
+product of a power of `x` and a power of `y`. See also the result below if you don't need the
+explicit formula. -/
+@[to_additive "If two commuting elements `x` and `y` of an additive monoid have order `n` and `m`,
+there is an element of order `lcm n m`. The result actually gives an explicit (computable) element,
+written as the sum of a multiple of `x` and a multiple of `y`. See also the result below if you
+don't need the explicit formula."]
+lemma _root_.Commute.orderOf_mul_pow_eq_lcm {x y : G} (h : Commute x y) (hx : orderOf x ≠ 0)
+ (hy : orderOf y ≠ 0) :
+ orderOf (x ^ (orderOf x / (factorizationLCMLeft (orderOf x) (orderOf y))) *
+ y ^ (orderOf y / factorizationLCMRight (orderOf x) (orderOf y))) =
+ Nat.lcm (orderOf x) (orderOf y) := by
+ rw [(h.pow_pow _ _).orderOf_mul_eq_mul_orderOf_of_coprime]
+ all_goals iterate 2 rw [orderOf_pow_orderOf_div]; try rw [Coprime]
+ all_goals simp [factorizationLCMLeft_mul_factorizationLCMRight, factorizationLCMLeft_dvd_left,
+ factorizationLCMRight_dvd_right, coprime_factorizationLCMLeft_factorizationLCMRight, hx, hy]
+
+open Submonoid in
+/-- If two commuting elements `x` and `y` of a monoid have order `n` and `m`, then there is an
+element of order `lcm n m` that lies in the subgroup generated by `x` and `y`. -/
+@[to_additive "If two commuting elements `x` and `y` of an additive monoid have order `n` and `m`,
+then there is an element of order `lcm n m` that lies in the additive subgroup generated by `x`
+and `y`."]
+theorem _root_.Commute.exists_orderOf_eq_lcm {x y : G} (h : Commute x y) :
+ ∃ z ∈ closure {x, y}, orderOf z = Nat.lcm (orderOf x) (orderOf y) := by
+ by_cases hx : orderOf x = 0 <;> by_cases hy : orderOf y = 0
+ · exact ⟨x, subset_closure (by simp), by simp [hx]⟩
+ · exact ⟨x, subset_closure (by simp), by simp [hx]⟩
+ · exact ⟨y, subset_closure (by simp), by simp [hy]⟩
+ · exact ⟨_, mul_mem (pow_mem (subset_closure (by simp)) _) (pow_mem (subset_closure (by simp)) _),
+ h.orderOf_mul_pow_eq_lcm hx hy⟩
+
/-- A nontrivial monoid has prime exponent `p` if and only if every non-identity element has
order `p`. -/
@[to_additive]
open Classical
(#11199)
We remove all but one open Classical
s, instead preferring to use open scoped Classical
. The only real side-effect this led to is moving a couple declarations to use Exists.choose
instead of Classical.choose
.
The first few commits are explicitly labelled regex replaces for ease of review.
@@ -50,7 +50,7 @@ universe u
variable {G : Type u}
-open Classical
+open scoped Classical
namespace Monoid
Does the following renames:
cSup_eq_max'
-> csSup_eq_max'
cInf_eq_min'
-> csInf_eq_min'
cSup_mem
-> csSup_mem
cInf_mem
-> csInf_mem
cSup_lt_iff
-> csSup_lt_iff
lt_cInf_iff
-> lt_csInf_iff
@@ -429,7 +429,7 @@ theorem exists_orderOf_eq_exponent (hG : ExponentExists G) : ∃ g : G, orderOf
have hne : (Set.range (orderOf : G → ℕ)).Nonempty := ⟨1, 1, orderOf_one⟩
have hfin : (Set.range (orderOf : G → ℕ)).Finite := by
rwa [← exponent_ne_zero_iff_range_orderOf_finite hG.orderOf_pos]
- obtain ⟨t, ht⟩ := hne.cSup_mem hfin
+ obtain ⟨t, ht⟩ := hne.csSup_mem hfin
use t
apply Nat.dvd_antisymm (order_dvd_exponent _)
refine' Nat.dvd_of_factors_subperm he _
@@ -503,7 +503,7 @@ variable [CancelCommMonoid G]
@[to_additive]
theorem exponent_eq_max'_orderOf [Fintype G] :
exponent G = ((@Finset.univ G _).image orderOf).max' ⟨1, by simp⟩ := by
- rw [← Finset.Nonempty.cSup_eq_max', Finset.coe_image, Finset.coe_univ, Set.image_univ, ← iSup]
+ rw [← Finset.Nonempty.csSup_eq_max', Finset.coe_image, Finset.coe_univ, Set.image_univ, ← iSup]
exact exponent_eq_iSup_orderOf orderOf_pos
#align monoid.exponent_eq_max'_order_of Monoid.exponent_eq_max'_orderOf
#align add_monoid.exponent_eq_max'_order_of AddMonoid.exponent_eq_max'_addOrderOf
I ran tryAtEachStep on all files under Mathlib
to find all locations where omega
succeeds. For each that was a linarith
without an only
, I tried replacing it with omega
, and I verified that elaboration time got smaller. (In almost all cases, there was a noticeable speedup.) I also replaced some slow aesop
s along the way.
@@ -184,7 +184,7 @@ theorem exponent_min' (n : ℕ) (hpos : 0 < n) (hG : ∀ g : G, g ^ n = 1) : exp
theorem exponent_min (m : ℕ) (hpos : 0 < m) (hm : m < exponent G) : ∃ g : G, g ^ m ≠ 1 := by
by_contra! h
have hcon : exponent G ≤ m := exponent_min' m hpos h
- linarith
+ omega
#align monoid.exponent_min Monoid.exponent_min
#align add_monoid.exponent_min AddMonoid.exponent_min
Proves some helpful properties of Monoid.exponent
on Submonoid G
and Subgroup G
:
G
divides the exponent of H
if there exists a multiplication-preserving injection from G
to H
Monoid.exponent G = Monoid.exponent H
if G ≃* H
Monoid.exponent ⊤ = Monoid.exponent G
g ^ Monoid.exponent H = 1
if g ∈ H
one_lt_exponent
to LeftCancelMonoid
@@ -138,6 +138,14 @@ theorem exponent_eq_zero_of_order_zero {g : G} (hg : orderOf g = 0) : exponent G
#align monoid.exponent_eq_zero_of_order_zero Monoid.exponent_eq_zero_of_order_zero
#align add_monoid.exponent_eq_zero_of_order_zero AddMonoid.exponent_eq_zero_addOrder_zero
+/-- The exponent is zero iff for all nonzero `n`, one can find a `g` such that `g ^ n ≠ 1`. -/
+@[to_additive "The exponent is zero iff for all nonzero `n`, one can find a `g` such that
+`n • g ≠ 0`."]
+theorem exponent_eq_zero_iff_forall : exponent G = 0 ↔ ∀ n > 0, ∃ g : G, g ^ n ≠ 1 := by
+ rw [exponent_eq_zero_iff, ExponentExists]
+ push_neg
+ rfl
+
@[to_additive exponent_nsmul_eq_zero]
theorem pow_exponent_eq_one (g : G) : g ^ exponent G = 1 := by
by_cases h : ExponentExists G
@@ -180,16 +188,21 @@ theorem exponent_min (m : ℕ) (hpos : 0 < m) (hm : m < exponent G) : ∃ g : G,
#align monoid.exponent_min Monoid.exponent_min
#align add_monoid.exponent_min AddMonoid.exponent_min
-@[to_additive (attr := simp)]
-theorem exp_eq_one_of_subsingleton [Subsingleton G] : exponent G = 1 := by
- apply le_antisymm
+@[to_additive AddMonoid.exp_eq_one_iff]
+theorem exp_eq_one_iff : exponent G = 1 ↔ Subsingleton G := by
+ refine ⟨fun eq_one => ⟨fun a b => ?a_eq_b⟩, fun h => le_antisymm ?le ?ge⟩
+ · rw [← pow_one a, ← pow_one b, ← eq_one, Monoid.pow_exponent_eq_one, Monoid.pow_exponent_eq_one]
· apply exponent_min' _ Nat.one_pos
simp [eq_iff_true_of_subsingleton]
· apply Nat.succ_le_of_lt
apply exponent_pos_of_exists 1 Nat.one_pos
simp [eq_iff_true_of_subsingleton]
+
+@[to_additive (attr := simp) AddMonoid.exp_eq_one_of_subsingleton]
+theorem exp_eq_one_of_subsingleton [hs : Subsingleton G] : exponent G = 1 :=
+ exp_eq_one_iff.mpr hs
#align monoid.exp_eq_one_of_subsingleton Monoid.exp_eq_one_of_subsingleton
-#align add_monoid.exp_eq_zero_of_subsingleton AddMonoid.exp_eq_zero_of_subsingleton
+#align add_monoid.exp_eq_zero_of_subsingleton AddMonoid.exp_eq_one_of_subsingleton
@[to_additive addOrder_dvd_exponent]
theorem order_dvd_exponent (g : G) : orderOf g ∣ exponent G :=
@@ -335,8 +348,50 @@ theorem lcm_orderOf_eq_exponent [Fintype G] : (Finset.univ : Finset G).lcm order
@[to_additive (attr := deprecated) AddMonoid.lcm_addOrder_eq_exponent] -- 2024-01-26
alias lcm_order_eq_exponent := lcm_orderOf_eq_exponent
+variable {H : Type*} [Monoid H]
+
+/--
+If there exists an injective, multiplication-preserving map from `G` to `H`,
+then the exponent of `G` divides the exponent of `H`.
+-/
+@[to_additive "If there exists an injective, addition-preserving map from `G` to `H`,
+then the exponent of `G` divides the exponent of `H`."]
+theorem exponent_dvd_of_monoidHom (e : G →* H) (e_inj : Function.Injective e) :
+ Monoid.exponent G ∣ Monoid.exponent H :=
+ exponent_dvd_of_forall_pow_eq_one fun g => e_inj (by
+ rw [map_pow, pow_exponent_eq_one, map_one])
+
+/--
+If there exists a multiplication-preserving equivalence between `G` and `H`,
+then the exponent of `G` is equal to the exponent of `H`.
+-/
+@[to_additive "If there exists a addition-preserving equivalence between `G` and `H`,
+then the exponent of `G` is equal to the exponent of `H`."]
+theorem exponent_eq_of_mulEquiv (e : G ≃* H) : Monoid.exponent G = Monoid.exponent H :=
+ Nat.dvd_antisymm
+ (exponent_dvd_of_monoidHom e e.injective)
+ (exponent_dvd_of_monoidHom e.symm e.symm.injective)
+
end Monoid
+section Submonoid
+
+variable [Monoid G]
+
+variable (G) in
+@[to_additive (attr := simp)]
+theorem _root_.Submonoid.exponent_top :
+ Monoid.exponent (⊤ : Submonoid G) = Monoid.exponent G :=
+ exponent_eq_of_mulEquiv Submonoid.topEquiv
+
+@[to_additive]
+theorem _root_.Submonoid.pow_exponent_eq_one {S : Submonoid G} {g : G} (g_in_s : g ∈ S) :
+ g ^ (Monoid.exponent S) = 1 := by
+ have := Monoid.pow_exponent_eq_one (⟨g, g_in_s⟩ : S)
+ rwa [SubmonoidClass.mk_pow, ← OneMemClass.coe_eq_one] at this
+
+end Submonoid
+
section LeftCancelMonoid
variable [LeftCancelMonoid G]
@@ -356,6 +411,12 @@ theorem exponent_ne_zero_of_finite [Finite G] : exponent G ≠ 0 :=
#align monoid.exponent_ne_zero_of_finite Monoid.exponent_ne_zero_of_finite
#align add_monoid.exponent_ne_zero_of_finite AddMonoid.exponent_ne_zero_of_finite
+@[to_additive AddMonoid.one_lt_exponent]
+lemma one_lt_exponent [LeftCancelMonoid G] [Finite G] [Nontrivial G] :
+ 1 < Monoid.exponent G := by
+ rw [Nat.one_lt_iff_ne_zero_and_ne_one]
+ exact ⟨exponent_ne_zero_of_finite, mt exp_eq_one_iff.mp (not_subsingleton G)⟩
+
end LeftCancelMonoid
section CommMonoid
@@ -455,17 +516,10 @@ section Group
variable [Group G]
-@[to_additive AddGroup.one_lt_exponent]
-lemma Group.one_lt_exponent [Finite G] [Nontrivial G] : 1 < Monoid.exponent G := by
- let _inst := Fintype.ofFinite G
- obtain ⟨g, hg⟩ := exists_ne (1 : G)
- rw [← Monoid.lcm_orderOf_eq_exponent]
- have hg' : 2 ≤ orderOf g := Nat.lt_of_le_of_ne (orderOf_pos g) <| by
- simpa [eq_comm, orderOf_eq_one_iff] using hg
- refine hg'.trans <| Nat.le_of_dvd ?_ <| Finset.dvd_lcm (by simp)
- rw [Nat.pos_iff_ne_zero, Ne.def, Finset.lcm_eq_zero_iff]
- rintro ⟨x, -, hx⟩
- exact (orderOf_pos x).ne' hx
+-- Deprecated: 2024-02-17
+@[to_additive (attr := deprecated Monoid.one_lt_exponent) AddGroup.one_lt_exponent]
+lemma Group.one_lt_exponent [Finite G] [Nontrivial G] : 1 < Monoid.exponent G :=
+ Monoid.one_lt_exponent
theorem Group.exponent_dvd_card [Fintype G] : Monoid.exponent G ∣ Fintype.card G :=
Monoid.exponent_dvd.mpr <| fun _ => orderOf_dvd_card
@@ -473,6 +527,19 @@ theorem Group.exponent_dvd_card [Fintype G] : Monoid.exponent G ∣ Fintype.card
theorem Group.exponent_dvd_nat_card : Monoid.exponent G ∣ Nat.card G :=
Monoid.exponent_dvd.mpr orderOf_dvd_natCard
+@[to_additive]
+theorem Subgroup.exponent_toSubmonoid (H : Subgroup G) :
+ Monoid.exponent H.toSubmonoid = Monoid.exponent H :=
+ Monoid.exponent_eq_of_mulEquiv (MulEquiv.subgroupCongr rfl)
+
+@[to_additive (attr := simp)]
+theorem Subgroup.exponent_top : Monoid.exponent (⊤ : Subgroup G) = Monoid.exponent G :=
+ Monoid.exponent_eq_of_mulEquiv topEquiv
+
+@[to_additive]
+theorem Subgroup.pow_exponent_eq_one {H : Subgroup G} {g : G} (g_in_H : g ∈ H) :
+ g ^ Monoid.exponent H = 1 := exponent_toSubmonoid H ▸ Submonoid.pow_exponent_eq_one g_in_H
+
end Group
section CommGroup
have
, replace
and suffices
(#10640)
No changes to tactic file, it's just boring fixes throughout the library.
This follows on from #6964.
Co-authored-by: sgouezel <sebastien.gouezel@univ-rennes1.fr> Co-authored-by: Eric Wieser <wieser.eric@gmail.com>
@@ -256,8 +256,8 @@ theorem _root_.Nat.Prime.exists_orderOf_eq_pow_factorization_exponent {p : ℕ}
rw [bot_eq_zero, Nat.factorization_zero, Finsupp.zero_apply]
rw [← Finsupp.mem_support_iff] at h
obtain ⟨g, hg⟩ : ∃ g : G, g ^ (exponent G / p) ≠ 1 := by
- suffices key : ¬exponent G ∣ exponent G / p
- · rwa [exponent_dvd_iff_forall_pow_eq_one, not_forall] at key
+ suffices key : ¬exponent G ∣ exponent G / p by
+ rwa [exponent_dvd_iff_forall_pow_eq_one, not_forall] at key
exact fun hd =>
hp.one_lt.not_le
((mul_le_iff_le_one_left he).mp <|
@@ -96,24 +96,45 @@ theorem _root_.MulOpposite.exponent : exponent (MulOpposite G) = exponent G := b
all_goals exact ⟨(op_injective <| · <| op ·), (unop_injective <| . <| unop .)⟩
@[to_additive]
-theorem exponentExists_iff_ne_zero : ExponentExists G ↔ exponent G ≠ 0 := by
+theorem ExponentExists.isOfFinOrder (h : ExponentExists G) {g : G} : IsOfFinOrder g :=
+ isOfFinOrder_iff_pow_eq_one.mpr <| by peel 2 h; exact this g
+
+@[to_additive]
+theorem ExponentExists.orderOf_pos (h : ExponentExists G) (g : G) : 0 < orderOf g :=
+ h.isOfFinOrder.orderOf_pos
+
+@[to_additive]
+theorem exponent_ne_zero : exponent G ≠ 0 ↔ ExponentExists G := by
rw [exponent]
split_ifs with h
· simp [h, @not_lt_zero' ℕ]
--if this isn't done this way, `to_additive` freaks
· tauto
-#align monoid.exponent_exists_iff_ne_zero Monoid.exponentExists_iff_ne_zero
-#align add_monoid.exponent_exists_iff_ne_zero AddMonoid.exponentExists_iff_ne_zero
+#align monoid.exponent_exists_iff_ne_zero Monoid.exponent_ne_zero
+#align add_monoid.exponent_exists_iff_ne_zero AddMonoid.exponent_ne_zero
+
+@[to_additive]
+protected alias ⟨_, ExponentExists.exponent_ne_zero⟩ := exponent_ne_zero
+
+@[to_additive (attr := deprecated)] -- 2024-01-27
+theorem exponentExists_iff_ne_zero : ExponentExists G ↔ exponent G ≠ 0 := exponent_ne_zero.symm
+
+@[to_additive]
+theorem exponent_pos : 0 < exponent G ↔ ExponentExists G :=
+ pos_iff_ne_zero.trans exponent_ne_zero
@[to_additive]
-theorem exponent_eq_zero_iff : exponent G = 0 ↔ ¬ExponentExists G := by
- simp only [exponentExists_iff_ne_zero, Classical.not_not]
+protected alias ⟨_, ExponentExists.exponent_pos⟩ := exponent_pos
+
+@[to_additive]
+theorem exponent_eq_zero_iff : exponent G = 0 ↔ ¬ExponentExists G :=
+ exponent_ne_zero.not_right
#align monoid.exponent_eq_zero_iff Monoid.exponent_eq_zero_iff
#align add_monoid.exponent_eq_zero_iff AddMonoid.exponent_eq_zero_iff
@[to_additive exponent_eq_zero_addOrder_zero]
theorem exponent_eq_zero_of_order_zero {g : G} (hg : orderOf g = 0) : exponent G = 0 :=
- exponent_eq_zero_iff.mpr fun ⟨n, hn, hgn⟩ => orderOf_eq_zero_iff'.mp hg n hn <| hgn g
+ exponent_eq_zero_iff.mpr fun h ↦ h.orderOf_pos g |>.ne' hg
#align monoid.exponent_eq_zero_of_order_zero Monoid.exponent_eq_zero_of_order_zero
#align add_monoid.exponent_eq_zero_of_order_zero AddMonoid.exponent_eq_zero_addOrder_zero
@@ -137,10 +158,8 @@ theorem pow_eq_mod_exponent {n : ℕ} (g : G) : g ^ n = g ^ (n % exponent G) :=
@[to_additive]
theorem exponent_pos_of_exists (n : ℕ) (hpos : 0 < n) (hG : ∀ g : G, g ^ n = 1) :
- 0 < exponent G := by
- have h : ∃ n, 0 < n ∧ ∀ g : G, g ^ n = 1 := ⟨n, hpos, hG⟩
- rw [exponent, dif_pos]
- exact (Nat.find_spec h).1
+ 0 < exponent G :=
+ ExponentExists.exponent_pos ⟨n, hpos, hG⟩
#align monoid.exponent_pos_of_exists Monoid.exponent_pos_of_exists
#align add_monoid.exponent_pos_of_exists AddMonoid.exponent_pos_of_exists
@@ -178,25 +197,43 @@ theorem order_dvd_exponent (g : G) : orderOf g ∣ exponent G :=
#align monoid.order_dvd_exponent Monoid.order_dvd_exponent
#align add_monoid.add_order_dvd_exponent AddMonoid.addOrder_dvd_exponent
-variable (G)
+@[to_additive]
+theorem orderOf_le_exponent (h : ExponentExists G) (g : G) : orderOf g ≤ exponent G :=
+ Nat.le_of_dvd h.exponent_pos (order_dvd_exponent g)
@[to_additive]
-theorem exponent_dvd_of_forall_pow_eq_one (G) [Monoid G] (n : ℕ) (hG : ∀ g : G, g ^ n = 1) :
- exponent G ∣ n := by
+theorem exponent_dvd_iff_forall_pow_eq_one {n : ℕ} : exponent G ∣ n ↔ ∀ g : G, g ^ n = 1 := by
rcases n.eq_zero_or_pos with (rfl | hpos)
- · exact dvd_zero _
- apply Nat.dvd_of_mod_eq_zero
- by_contra h
- have h₁ := Nat.pos_of_ne_zero h
- have h₂ : n % exponent G < exponent G := Nat.mod_lt _ (exponent_pos_of_exists n hpos hG)
- have h₃ : exponent G ≤ n % exponent G := by
- apply exponent_min' _ h₁
- simp_rw [← pow_eq_mod_exponent]
- exact hG
- linarith
+ · simp
+ constructor
+ · intro h g
+ rw [Nat.dvd_iff_mod_eq_zero] at h
+ rw [pow_eq_mod_exponent, h, pow_zero]
+ · intro hG
+ by_contra h
+ rw [Nat.dvd_iff_mod_eq_zero, ← Ne, ← pos_iff_ne_zero] at h
+ have h₂ : n % exponent G < exponent G := Nat.mod_lt _ (exponent_pos_of_exists n hpos hG)
+ have h₃ : exponent G ≤ n % exponent G := by
+ apply exponent_min' _ h
+ simp_rw [← pow_eq_mod_exponent]
+ exact hG
+ exact h₂.not_le h₃
+
+@[to_additive]
+alias ⟨_, exponent_dvd_of_forall_pow_eq_one⟩ := exponent_dvd_iff_forall_pow_eq_one
#align monoid.exponent_dvd_of_forall_pow_eq_one Monoid.exponent_dvd_of_forall_pow_eq_one
#align add_monoid.exponent_dvd_of_forall_nsmul_eq_zero AddMonoid.exponent_dvd_of_forall_nsmul_eq_zero
+@[to_additive]
+theorem exponent_dvd {n : ℕ} : exponent G ∣ n ↔ ∀ g : G, orderOf g ∣ n := by
+ simp_rw [exponent_dvd_iff_forall_pow_eq_one, orderOf_dvd_iff_pow_eq_one]
+
+variable (G)
+
+@[to_additive (attr := deprecated)]
+theorem exponent_dvd_of_forall_orderOf_dvd (n : ℕ) (h : ∀ g : G, orderOf g ∣ n) : exponent G ∣ n :=
+ exponent_dvd.mpr h
+
@[to_additive]
theorem lcm_orderOf_dvd_exponent [Fintype G] :
(Finset.univ : Finset G).lcm orderOf ∣ exponent G := by
@@ -220,7 +257,7 @@ theorem _root_.Nat.Prime.exists_orderOf_eq_pow_factorization_exponent {p : ℕ}
rw [← Finsupp.mem_support_iff] at h
obtain ⟨g, hg⟩ : ∃ g : G, g ^ (exponent G / p) ≠ 1 := by
suffices key : ¬exponent G ∣ exponent G / p
- · simpa using mt (exponent_dvd_of_forall_pow_eq_one G (exponent G / p)) key
+ · rwa [exponent_dvd_iff_forall_pow_eq_one, not_forall] at key
exact fun hd =>
hp.one_lt.not_le
((mul_le_iff_le_one_left he).mp <|
@@ -244,10 +281,11 @@ lemma exponent_eq_prime_iff {G : Type*} [Monoid G] [Nontrivial G] {p : ℕ} (hp
refine ⟨fun hG g hg ↦ ?_, fun h ↦ dvd_antisymm ?_ ?_⟩
· rw [Ne.def, ← orderOf_eq_one_iff] at hg
exact Eq.symm <| (hp.dvd_iff_eq hg).mp <| hG ▸ Monoid.order_dvd_exponent g
- · apply Monoid.exponent_dvd_of_forall_pow_eq_one G p fun g ↦ ?_
+ · rw [exponent_dvd]
+ intro g
by_cases hg : g = 1
· simp [hg]
- · simpa [h g hg] using pow_orderOf_eq_one g
+ · rw [h g hg]
· obtain ⟨g, hg⟩ := exists_ne (1 : G)
simpa [h g hg] using Monoid.order_dvd_exponent g
@@ -270,9 +308,9 @@ theorem exponent_ne_zero_iff_range_orderOf_finite (h : ∀ g : G, 0 < orderOf g)
intro h
rw [h, zero_dvd_iff] at this
exact htpos.ne' this
- refine' exponent_dvd_of_forall_pow_eq_one _ _ fun g => _
- rw [← pow_mod_orderOf, Nat.mod_eq_zero_of_dvd, pow_zero g]
- apply Finset.dvd_prod_of_mem
+ rw [exponent_dvd]
+ intro g
+ apply Finset.dvd_prod_of_mem id (?_ : orderOf g ∈ _)
rw [← Finset.mem_coe, ht]
exact Set.mem_range_self g
#align monoid.exponent_ne_zero_iff_range_order_of_finite Monoid.exponent_ne_zero_iff_range_orderOf_finite
@@ -286,14 +324,16 @@ theorem exponent_eq_zero_iff_range_orderOf_infinite (h : ∀ g : G, 0 < orderOf
#align monoid.exponent_eq_zero_iff_range_order_of_infinite Monoid.exponent_eq_zero_iff_range_orderOf_infinite
#align add_monoid.exponent_eq_zero_iff_range_order_of_infinite AddMonoid.exponent_eq_zero_iff_range_addOrderOf_infinite
-@[to_additive lcm_addOrder_eq_exponent]
-theorem lcm_order_eq_exponent [Fintype G] : (Finset.univ : Finset G).lcm orderOf = exponent G := by
- apply Nat.dvd_antisymm (lcm_orderOf_dvd_exponent G)
- refine' exponent_dvd_of_forall_pow_eq_one G _ fun g => _
- obtain ⟨m, hm⟩ : orderOf g ∣ Finset.univ.lcm orderOf := Finset.dvd_lcm (Finset.mem_univ g)
- rw [hm, pow_mul, pow_orderOf_eq_one, one_pow]
-#align monoid.lcm_order_eq_exponent Monoid.lcm_order_eq_exponent
-#align add_monoid.lcm_add_order_eq_exponent AddMonoid.lcm_addOrder_eq_exponent
+@[to_additive]
+theorem lcm_orderOf_eq_exponent [Fintype G] : (Finset.univ : Finset G).lcm orderOf = exponent G :=
+ Nat.dvd_antisymm
+ (lcm_orderOf_dvd_exponent G)
+ (exponent_dvd.mpr fun g => Finset.dvd_lcm (Finset.mem_univ g))
+#align monoid.lcm_order_eq_exponent Monoid.lcm_orderOf_eq_exponent
+#align add_monoid.lcm_add_order_eq_exponent AddMonoid.lcm_addOrderOf_eq_exponent
+
+@[to_additive (attr := deprecated) AddMonoid.lcm_addOrder_eq_exponent] -- 2024-01-26
+alias lcm_order_eq_exponent := lcm_orderOf_eq_exponent
end Monoid
@@ -302,9 +342,17 @@ section LeftCancelMonoid
variable [LeftCancelMonoid G]
@[to_additive]
-theorem exponent_ne_zero_of_finite [Finite G] : exponent G ≠ 0 := by
- cases nonempty_fintype G
- simpa [← lcm_order_eq_exponent, Finset.lcm_eq_zero_iff] using fun x => (orderOf_pos x).ne'
+theorem ExponentExists.of_finite [Finite G] : ExponentExists G := by
+ let _inst := Fintype.ofFinite G
+ simp only [Monoid.ExponentExists]
+ refine ⟨(Finset.univ : Finset G).lcm orderOf, ?_, fun g => ?_⟩
+ · simpa [pos_iff_ne_zero, Finset.lcm_eq_zero_iff] using fun x => (_root_.orderOf_pos x).ne'
+ · rw [← orderOf_dvd_iff_pow_eq_one, lcm_orderOf_eq_exponent]
+ exact order_dvd_exponent g
+
+@[to_additive]
+theorem exponent_ne_zero_of_finite [Finite G] : exponent G ≠ 0 :=
+ ExponentExists.of_finite.exponent_ne_zero
#align monoid.exponent_ne_zero_of_finite Monoid.exponent_ne_zero_of_finite
#align add_monoid.exponent_ne_zero_of_finite AddMonoid.exponent_ne_zero_of_finite
@@ -315,18 +363,14 @@ section CommMonoid
variable [CommMonoid G]
@[to_additive]
-theorem exponent_eq_iSup_orderOf (h : ∀ g : G, 0 < orderOf g) :
- exponent G = ⨆ g : G, orderOf g := by
- rw [iSup]
- rcases eq_or_ne (exponent G) 0 with (he | he)
- · rw [he, Set.Infinite.Nat.sSup_eq_zero <| (exponent_eq_zero_iff_range_orderOf_infinite h).1 he]
+theorem exists_orderOf_eq_exponent (hG : ExponentExists G) : ∃ g : G, orderOf g = exponent G := by
+ have he := hG.exponent_ne_zero
have hne : (Set.range (orderOf : G → ℕ)).Nonempty := ⟨1, 1, orderOf_one⟩
have hfin : (Set.range (orderOf : G → ℕ)).Finite := by
- rwa [← exponent_ne_zero_iff_range_orderOf_finite h]
+ rwa [← exponent_ne_zero_iff_range_orderOf_finite hG.orderOf_pos]
obtain ⟨t, ht⟩ := hne.cSup_mem hfin
- apply Nat.dvd_antisymm _
- · rw [← ht]
- apply order_dvd_exponent
+ use t
+ apply Nat.dvd_antisymm (order_dvd_exponent _)
refine' Nat.dvd_of_factors_subperm he _
rw [List.subperm_ext_iff]
by_contra! h
@@ -351,12 +395,30 @@ theorem exponent_eq_iSup_orderOf (h : ∀ g : G, 0 < orderOf g) :
simp [hp]
rw [this]
-- Porting note: convert made to_additive complain
- apply Nat.pow_succ_factorization_not_dvd (h <| t ^ p ^ k).ne' hp
+ apply Nat.pow_succ_factorization_not_dvd (hG.orderOf_pos <| t ^ p ^ k).ne' hp
rw [(Commute.all _ g).orderOf_mul_eq_mul_orderOf_of_coprime hcoprime, hpk',
- hg, ha, ← ht, ← hk, pow_add, pow_add, pow_one, ← mul_assoc, ← mul_assoc,
- Nat.div_mul_cancel, mul_assoc, lt_mul_iff_one_lt_right <| h t, ← pow_succ']
+ hg, ha, hk, pow_add, pow_add, pow_one, ← mul_assoc, ← mul_assoc,
+ Nat.div_mul_cancel, mul_assoc, lt_mul_iff_one_lt_right <| hG.orderOf_pos t, ← pow_succ']
exact one_lt_pow hp.one_lt a.succ_ne_zero
exact hpk
+
+@[to_additive]
+theorem exponent_eq_iSup_orderOf (h : ∀ g : G, 0 < orderOf g) :
+ exponent G = ⨆ g : G, orderOf g := by
+ rw [iSup]
+ by_cases ExponentExists G
+ case neg he =>
+ rw [← exponent_eq_zero_iff] at he
+ rw [he, Set.Infinite.Nat.sSup_eq_zero <| (exponent_eq_zero_iff_range_orderOf_infinite h).1 he]
+ case pos he =>
+ rw [csSup_eq_of_forall_le_of_forall_lt_exists_gt (Set.range_nonempty _)]
+ · simp_rw [Set.mem_range, forall_exists_index, forall_apply_eq_imp_iff]
+ exact orderOf_le_exponent he
+ intro x hx
+ obtain ⟨g, hg⟩ := exists_orderOf_eq_exponent he
+ rw [← hg] at hx
+ simp_rw [Set.mem_range, exists_exists_eq_and]
+ exact ⟨g, hx⟩
#align monoid.exponent_eq_supr_order_of Monoid.exponent_eq_iSup_orderOf
#align add_monoid.exponent_eq_supr_order_of AddMonoid.exponent_eq_iSup_addOrderOf
@@ -391,12 +453,13 @@ end Monoid
section Group
+variable [Group G]
+
@[to_additive AddGroup.one_lt_exponent]
-lemma Group.one_lt_exponent [Group G] [Finite G] [Nontrivial G] :
- 1 < Monoid.exponent G := by
+lemma Group.one_lt_exponent [Finite G] [Nontrivial G] : 1 < Monoid.exponent G := by
let _inst := Fintype.ofFinite G
obtain ⟨g, hg⟩ := exists_ne (1 : G)
- rw [← Monoid.lcm_order_eq_exponent]
+ rw [← Monoid.lcm_orderOf_eq_exponent]
have hg' : 2 ≤ orderOf g := Nat.lt_of_le_of_ne (orderOf_pos g) <| by
simpa [eq_comm, orderOf_eq_one_iff] using hg
refine hg'.trans <| Nat.le_of_dvd ?_ <| Finset.dvd_lcm (by simp)
@@ -404,6 +467,12 @@ lemma Group.one_lt_exponent [Group G] [Finite G] [Nontrivial G] :
rintro ⟨x, -, hx⟩
exact (orderOf_pos x).ne' hx
+theorem Group.exponent_dvd_card [Fintype G] : Monoid.exponent G ∣ Fintype.card G :=
+ Monoid.exponent_dvd.mpr <| fun _ => orderOf_dvd_card
+
+theorem Group.exponent_dvd_nat_card : Monoid.exponent G ∣ Nat.card G :=
+ Monoid.exponent_dvd.mpr orderOf_dvd_natCard
+
end Group
section CommGroup
@@ -434,7 +503,7 @@ theorem card_dvd_exponent_pow_rank : Nat.card G ∣ Monoid.exponent G ^ Group.ra
theorem card_dvd_exponent_pow_rank' {n : ℕ} (hG : ∀ g : G, g ^ n = 1) :
Nat.card G ∣ n ^ Group.rank G :=
(card_dvd_exponent_pow_rank G).trans
- (pow_dvd_pow_of_dvd (Monoid.exponent_dvd_of_forall_pow_eq_one G n hG) (Group.rank G))
+ (pow_dvd_pow_of_dvd (Monoid.exponent_dvd_of_forall_pow_eq_one hG) (Group.rank G))
#align card_dvd_exponent_pow_rank' card_dvd_exponent_pow_rank'
#align card_dvd_exponent_nsmul_rank' card_dvd_exponent_nsmul_rank'
@@ -459,7 +528,7 @@ theorem Monoid.exponent_pi_eq_zero {ι : Type*} {M : ι → Type*} [∀ i, Monoi
theorem MonoidHom.exponent_dvd {F M₁ M₂ : Type*} [Monoid M₁] [Monoid M₂]
[FunLike F M₁ M₂] [MonoidHomClass F M₁ M₂]
{f : F} (hf : Function.Surjective f) : exponent M₂ ∣ exponent M₁ := by
- refine Monoid.exponent_dvd_of_forall_pow_eq_one M₂ _ fun m₂ ↦ ?_
+ refine Monoid.exponent_dvd_of_forall_pow_eq_one fun m₂ ↦ ?_
obtain ⟨m₁, rfl⟩ := hf m₂
rw [← map_pow, pow_exponent_eq_one, map_one]
@@ -470,7 +539,7 @@ exponents of the constituent additive monoids."]
theorem Monoid.exponent_pi {ι : Type*} [Fintype ι] {M : ι → Type*} [∀ i, Monoid (M i)] :
exponent ((i : ι) → M i) = lcm univ (exponent <| M ·) := by
refine dvd_antisymm ?_ ?_
- · refine exponent_dvd_of_forall_pow_eq_one _ _ fun m ↦ ?_
+ · refine exponent_dvd_of_forall_pow_eq_one fun m ↦ ?_
ext i
rw [Pi.pow_apply, Pi.one_apply, ← orderOf_dvd_iff_pow_eq_one]
apply dvd_trans (Monoid.order_dvd_exponent (m i))
@@ -485,7 +554,7 @@ of the exponents of the individuaul additive monoids."]
theorem Monoid.exponent_prod {M₁ M₂ : Type*} [Monoid M₁] [Monoid M₂] :
exponent (M₁ × M₂) = lcm (exponent M₁) (exponent M₂) := by
refine dvd_antisymm ?_ (lcm_dvd ?_ ?_)
- · refine exponent_dvd_of_forall_pow_eq_one _ _ fun g ↦ ?_
+ · refine exponent_dvd_of_forall_pow_eq_one fun g ↦ ?_
ext1
· rw [Prod.pow_fst, Prod.fst_one, ← orderOf_dvd_iff_pow_eq_one]
exact dvd_trans (Monoid.order_dvd_exponent (g.1)) <| dvd_lcm_left _ _
@@ -495,3 +564,78 @@ theorem Monoid.exponent_prod {M₁ M₂ : Type*} [Monoid M₁] [Monoid M₂] :
· exact MonoidHom.exponent_dvd (f := MonoidHom.snd M₁ M₂) Prod.snd_surjective
end PiProd
+
+/-! # Properties of monoids with exponent two -/
+
+section ExponentTwo
+
+section Monoid
+
+variable [Monoid G]
+
+@[to_additive]
+lemma orderOf_eq_two_iff (hG : Monoid.exponent G = 2) {x : G} :
+ orderOf x = 2 ↔ x ≠ 1 :=
+ ⟨by rintro hx rfl; norm_num at hx, orderOf_eq_prime (hG ▸ Monoid.pow_exponent_eq_one x)⟩
+
+@[to_additive]
+theorem Commute.of_orderOf_dvd_two [IsCancelMul G] (h : ∀ g : G, orderOf g ∣ 2) (a b : G) :
+ Commute a b := by
+ simp_rw [orderOf_dvd_iff_pow_eq_one] at h
+ rw [commute_iff_eq, ← mul_right_inj a, ← mul_left_inj b]
+ calc
+ a * (a * b) * b = a ^ 2 * b ^ 2 := by simp only [pow_two]; group
+ _ = 1 := by rw [h, h, mul_one]
+ _ = (a * b) ^ 2 := by rw [h]
+ _ = a * (b * a) * b := by simp only [pow_two]; group
+
+/-- In a cancellative monoid of exponent two, all elements commute. -/
+@[to_additive]
+lemma mul_comm_of_exponent_two [IsCancelMul G] (hG : Monoid.exponent G = 2) (a b : G) :
+ a * b = b * a :=
+ Commute.of_orderOf_dvd_two (fun g => hG ▸ Monoid.order_dvd_exponent g) a b
+
+/-- Any cancellative monoid of exponent two is abelian. -/
+@[to_additive (attr := reducible) "Any additive group of exponent two is abelian."]
+def commMonoidOfExponentTwo [IsCancelMul G] (hG : Monoid.exponent G = 2) : CommMonoid G where
+ mul_comm := mul_comm_of_exponent_two hG
+
+end Monoid
+
+section Group
+
+variable [Group G]
+/-- In a group of exponent two, every element is its own inverse. -/
+@[to_additive]
+lemma inv_eq_self_of_exponent_two (hG : Monoid.exponent G = 2) (x : G) :
+ x⁻¹ = x :=
+ inv_eq_of_mul_eq_one_left <| pow_two (a := x) ▸ hG ▸ Monoid.pow_exponent_eq_one x
+
+/-- If an element in a group has order two, then it is its own inverse. -/
+@[to_additive]
+lemma inv_eq_self_of_orderOf_eq_two {x : G} (hx : orderOf x = 2) :
+ x⁻¹ = x :=
+ inv_eq_of_mul_eq_one_left <| pow_two (a := x) ▸ hx ▸ pow_orderOf_eq_one x
+
+-- TODO: Delete
+/-- Any group of exponent two is abelian. -/
+@[to_additive (attr := reducible, deprecated) "Any additive group of exponent two is abelian."]
+def instCommGroupOfExponentTwo (hG : Monoid.exponent G = 2) : CommGroup G where
+ mul_comm := mul_comm_of_exponent_two hG
+
+@[to_additive]
+lemma mul_not_mem_of_orderOf_eq_two {x y : G} (hx : orderOf x = 2)
+ (hy : orderOf y = 2) (hxy : x ≠ y) : x * y ∉ ({x, y, 1} : Set G) := by
+ simp only [Set.mem_singleton_iff, Set.mem_insert_iff, mul_right_eq_self, mul_left_eq_self,
+ mul_eq_one_iff_eq_inv, inv_eq_self_of_orderOf_eq_two hy, not_or]
+ aesop
+
+@[to_additive]
+lemma mul_not_mem_of_exponent_two (h : Monoid.exponent G = 2) {x y : G}
+ (hx : x ≠ 1) (hy : y ≠ 1) (hxy : x ≠ y) : x * y ∉ ({x, y, 1} : Set G) :=
+ mul_not_mem_of_orderOf_eq_two (orderOf_eq_prime (h ▸ Monoid.pow_exponent_eq_one x) hx)
+ (orderOf_eq_prime (h ▸ Monoid.pow_exponent_eq_one y) hy) hxy
+
+end Group
+
+end ExponentTwo
The FunLike hierarchy is very big and gets scanned through each time we need a coercion (via the CoeFun
instance). It looks like unbundled inheritance suits Lean 4 better here. The only class that still extends FunLike
is EquivLike
, since that has a custom coe_injective'
field that is easier to implement. All other classes should take FunLike
or EquivLike
as a parameter.
Previously, morphism classes would be Type
-valued and extend FunLike
:
/-- `MyHomClass F A B` states that `F` is a type of `MyClass.op`-preserving morphisms.
You should extend this class when you extend `MyHom`. -/
class MyHomClass (F : Type*) (A B : outParam <| Type*) [MyClass A] [MyClass B]
extends FunLike F A B :=
(map_op : ∀ (f : F) (x y : A), f (MyClass.op x y) = MyClass.op (f x) (f y))
After this PR, they should be Prop
-valued and take FunLike
as a parameter:
/-- `MyHomClass F A B` states that `F` is a type of `MyClass.op`-preserving morphisms.
You should extend this class when you extend `MyHom`. -/
class MyHomClass (F : Type*) (A B : outParam <| Type*) [MyClass A] [MyClass B]
[FunLike F A B] : Prop :=
(map_op : ∀ (f : F) (x y : A), f (MyClass.op x y) = MyClass.op (f x) (f y))
(Note that A B
stay marked as outParam
even though they are not purely required to be so due to the FunLike
parameter already filling them in. This is required to see through type synonyms, which is important in the category theory library. Also, I think keeping them as outParam
is slightly faster.)
Similarly, MyEquivClass
should take EquivLike
as a parameter.
As a result, every mention of [MyHomClass F A B]
should become [FunLike F A B] [MyHomClass F A B]
.
While overall this gives some great speedups, there are some cases that are noticeably slower. In particular, a failing application of a lemma such as map_mul
is more expensive. This is due to suboptimal processing of arguments. For example:
variable [FunLike F M N] [Mul M] [Mul N] (f : F) (x : M) (y : M)
theorem map_mul [MulHomClass F M N] : f (x * y) = f x * f y
example [AddHomClass F A B] : f (x * y) = f x * f y := map_mul f _ _
Before this PR, applying map_mul f
gives the goals [Mul ?M] [Mul ?N] [MulHomClass F ?M ?N]
. Since M
and N
are out_param
s, [MulHomClass F ?M ?N]
is synthesized first, supplies values for ?M
and ?N
and then the Mul M
and Mul N
instances can be found.
After this PR, the goals become [FunLike F ?M ?N] [Mul ?M] [Mul ?N] [MulHomClass F ?M ?N]
. Now [FunLike F ?M ?N]
is synthesized first, supplies values for ?M
and ?N
and then the Mul M
and Mul N
instances can be found, before trying MulHomClass F M N
which fails. Since the Mul
hierarchy is very big, this can be slow to fail, especially when there is no such Mul
instance.
A long-term but harder to achieve solution would be to specify the order in which instance goals get solved. For example, we'd like to change the arguments to map_mul
to look like [FunLike F M N] [Mul M] [Mul N] [highPriority <| MulHomClass F M N]
because MulHomClass
fails or succeeds much faster than the others.
As a consequence, the simpNF
linter is much slower since by design it tries and fails to apply many map_
lemmas. The same issue occurs a few times in existing calls to simp [map_mul]
, where map_mul
is tried "too soon" and fails. Thanks to the speedup of leanprover/lean4#2478 the impact is very limited, only in files that already were close to the timeout.
simp
not firing sometimesThis affects map_smulₛₗ
and related definitions. For simp
lemmas Lean apparently uses a slightly different mechanism to find instances, so that rw
can find every argument to map_smulₛₗ
successfully but simp
can't: leanprover/lean4#3701.
Especially in the category theory library, we might sometimes have a type A
which is also accessible as a synonym (Bundled A hA).1
. Instance synthesis doesn't always work if we have f : A →* B
but x * y : (Bundled A hA).1
or vice versa. This seems to be mostly fixed by keeping A B
as outParam
s in MulHomClass F A B
. (Presumably because Lean will do a definitional check A =?= (Bundled A hA).1
instead of using the syntax in the discrimination tree.)
The timeouts can be worked around for now by specifying which map_mul
we mean, either as map_mul f
for some explicit f
, or as e.g. MonoidHomClass.map_mul
.
map_smulₛₗ
not firing as simp
lemma can be worked around by going back to the pre-FunLike situation and making LinearMap.map_smulₛₗ
a simp
lemma instead of the generic map_smulₛₗ
. Writing simp [map_smulₛₗ _]
also works.
Co-authored-by: Matthew Ballard <matt@mrb.email> Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Scott Morrison <scott@tqft.net> Co-authored-by: Anne Baanen <Vierkantor@users.noreply.github.com>
@@ -456,7 +456,8 @@ theorem Monoid.exponent_pi_eq_zero {ι : Type*} {M : ι → Type*} [∀ i, Monoi
/-- If `f : M₁ →⋆ M₂` is surjective, then the exponent of `M₂` divides the exponent of `M₁`. -/
@[to_additive]
-theorem MonoidHom.exponent_dvd {F M₁ M₂ : Type*} [Monoid M₁] [Monoid M₂] [MonoidHomClass F M₁ M₂]
+theorem MonoidHom.exponent_dvd {F M₁ M₂ : Type*} [Monoid M₁] [Monoid M₂]
+ [FunLike F M₁ M₂] [MonoidHomClass F M₁ M₂]
{f : F} (hf : Function.Surjective f) : exponent M₂ ∣ exponent M₁ := by
refine Monoid.exponent_dvd_of_forall_pow_eq_one M₂ _ fun m₂ ↦ ?_
obtain ⟨m₁, rfl⟩ := hf m₂
with
clause of peel
tactic (#9413)
Per this Zulip thread, this changes the argument order of peel h with h_peel x y z ...
to peel h with x y z ... h_peel
, as the former behavior was deemed confusing.
@@ -449,7 +449,7 @@ theorem Monoid.exponent_pi_eq_zero {ι : Type*} {M : ι → Type*} [∀ i, Monoi
(hj : exponent (M j) = 0) : exponent ((i : ι) → M i) = 0 := by
rw [@exponent_eq_zero_iff, ExponentExists] at hj ⊢
push_neg at hj ⊢
- peel hj with _ n hn
+ peel hj with n hn _
obtain ⟨m, hm⟩ := this
refine ⟨Pi.mulSingle j m, fun h ↦ hm ?_⟩
simpa using congr_fun h j
Monoid.exponent
(#8723)
This PR shows a few facts related to Monoid.exponent
, especially when it is prime:
p
if and only if every non-identity element has order p
.p ^ 2
with p
prime is not cyclic if and only if it has exponent p
.@@ -236,6 +236,21 @@ theorem _root_.Nat.Prime.exists_orderOf_eq_pow_factorization_exponent {p : ℕ}
#align nat.prime.exists_order_of_eq_pow_factorization_exponent Nat.Prime.exists_orderOf_eq_pow_factorization_exponent
#align nat.prime.exists_order_of_eq_pow_padic_val_nat_add_exponent Nat.Prime.exists_addOrderOf_eq_pow_padic_val_nat_add_exponent
+/-- A nontrivial monoid has prime exponent `p` if and only if every non-identity element has
+order `p`. -/
+@[to_additive]
+lemma exponent_eq_prime_iff {G : Type*} [Monoid G] [Nontrivial G] {p : ℕ} (hp : p.Prime) :
+ Monoid.exponent G = p ↔ ∀ g : G, g ≠ 1 → orderOf g = p := by
+ refine ⟨fun hG g hg ↦ ?_, fun h ↦ dvd_antisymm ?_ ?_⟩
+ · rw [Ne.def, ← orderOf_eq_one_iff] at hg
+ exact Eq.symm <| (hp.dvd_iff_eq hg).mp <| hG ▸ Monoid.order_dvd_exponent g
+ · apply Monoid.exponent_dvd_of_forall_pow_eq_one G p fun g ↦ ?_
+ by_cases hg : g = 1
+ · simp [hg]
+ · simpa [h g hg] using pow_orderOf_eq_one g
+ · obtain ⟨g, hg⟩ := exists_ne (1 : G)
+ simpa [h g hg] using Monoid.order_dvd_exponent g
+
variable {G}
@[to_additive]
@@ -374,6 +389,23 @@ end CancelCommMonoid
end Monoid
+section Group
+
+@[to_additive AddGroup.one_lt_exponent]
+lemma Group.one_lt_exponent [Group G] [Finite G] [Nontrivial G] :
+ 1 < Monoid.exponent G := by
+ let _inst := Fintype.ofFinite G
+ obtain ⟨g, hg⟩ := exists_ne (1 : G)
+ rw [← Monoid.lcm_order_eq_exponent]
+ have hg' : 2 ≤ orderOf g := Nat.lt_of_le_of_ne (orderOf_pos g) <| by
+ simpa [eq_comm, orderOf_eq_one_iff] using hg
+ refine hg'.trans <| Nat.le_of_dvd ?_ <| Finset.dvd_lcm (by simp)
+ rw [Nat.pos_iff_ne_zero, Ne.def, Finset.lcm_eq_zero_iff]
+ rintro ⟨x, -, hx⟩
+ exact (orderOf_pos x).ne' hx
+
+end Group
+
section CommGroup
open Subgroup
@@ -155,7 +155,7 @@ theorem exponent_min' (n : ℕ) (hpos : 0 < n) (hG : ∀ g : G, g ^ n = 1) : exp
@[to_additive]
theorem exponent_min (m : ℕ) (hpos : 0 < m) (hm : m < exponent G) : ∃ g : G, g ^ m ≠ 1 := by
- by_contra' h
+ by_contra! h
have hcon : exponent G ≤ m := exponent_min' m hpos h
linarith
#align monoid.exponent_min Monoid.exponent_min
@@ -314,7 +314,7 @@ theorem exponent_eq_iSup_orderOf (h : ∀ g : G, 0 < orderOf g) :
apply order_dvd_exponent
refine' Nat.dvd_of_factors_subperm he _
rw [List.subperm_ext_iff]
- by_contra' h
+ by_contra! h
obtain ⟨p, hp, hpe⟩ := h
replace hp := Nat.prime_of_mem_factors hp
simp only [Nat.factors_count_eq] at hpe
@@ -256,7 +256,7 @@ theorem exponent_ne_zero_iff_range_orderOf_finite (h : ∀ g : G, 0 < orderOf g)
rw [h, zero_dvd_iff] at this
exact htpos.ne' this
refine' exponent_dvd_of_forall_pow_eq_one _ _ fun g => _
- rw [←pow_mod_orderOf, Nat.mod_eq_zero_of_dvd, pow_zero g]
+ rw [← pow_mod_orderOf, Nat.mod_eq_zero_of_dvd, pow_zero g]
apply Finset.dvd_prod_of_mem
rw [← Finset.mem_coe, ht]
exact Set.mem_range_self g
@@ -428,7 +428,7 @@ theorem MonoidHom.exponent_dvd {F M₁ M₂ : Type*} [Monoid M₁] [Monoid M₂]
{f : F} (hf : Function.Surjective f) : exponent M₂ ∣ exponent M₁ := by
refine Monoid.exponent_dvd_of_forall_pow_eq_one M₂ _ fun m₂ ↦ ?_
obtain ⟨m₁, rfl⟩ := hf m₂
- rw [←map_pow, pow_exponent_eq_one, map_one]
+ rw [← map_pow, pow_exponent_eq_one, map_one]
/-- The exponent of finite product of monoids is the `Finset.lcm` of the exponents of the
constituent monoids. -/
I've also got a change to make this required, but I'd like to land this first.
@@ -119,7 +119,7 @@ theorem exponent_eq_zero_of_order_zero {g : G} (hg : orderOf g = 0) : exponent G
@[to_additive exponent_nsmul_eq_zero]
theorem pow_exponent_eq_one (g : G) : g ^ exponent G = 1 := by
- by_cases ExponentExists G
+ by_cases h : ExponentExists G
· simp_rw [exponent, dif_pos h]
exact (Nat.find_spec h).2 g
· simp_rw [exponent, dif_neg h, pow_zero]
The cardinality of a subgroup is greater than the order of any of its elements.
Rename
order_eq_card_zpowers
→ Fintype.card_zpowers
order_eq_card_zpowers'
→ Nat.card_zpowers
(and turn it around to match Nat.card_subgroupPowers
)Submonoid.powers_subset
→ Submonoid.powers_le
orderOf_dvd_card_univ
→ orderOf_dvd_card
orderOf_subgroup
→ Subgroup.orderOf
Subgroup.nonempty
→ Subgroup.coe_nonempty
@@ -393,7 +393,7 @@ theorem card_dvd_exponent_pow_rank : Nat.card G ∣ Monoid.exponent G ^ Group.ra
replace hf := nat_card_dvd_of_surjective f hf
rw [Nat.card_pi] at hf
refine' hf.trans (Finset.prod_dvd_prod_of_dvd _ _ fun g _ => _)
- rw [← order_eq_card_zpowers']
+ rw [Nat.card_zpowers]
exact Monoid.order_dvd_exponent (g : G)
#align card_dvd_exponent_pow_rank card_dvd_exponent_pow_rank
#align card_dvd_exponent_nsmul_rank card_dvd_exponent_nsmul_rank
Many lemmas in GroupTheory.OrderOfElement
were stated for elements of finite groups even though they work more generally for torsion elements of possibly infinite groups. This PR generalises those lemmas (and leaves convenience lemmas stated for finite groups), and fixes a bunch of names to use dot notation.
Function.eq_of_lt_minimalPeriod_of_iterate_eq
→ Function.iterate_injOn_Iio_minimalPeriod
Function.eq_iff_lt_minimalPeriod_of_iterate_eq
→ Function.iterate_eq_iterate_iff_of_lt_minimalPeriod
isOfFinOrder_iff_coe
→ Submonoid.isOfFinOrder_coe
orderOf_pos'
→ IsOfFinOrder.orderOf_pos
pow_eq_mod_orderOf
→ pow_mod_orderOf
(and turned around)pow_injective_of_lt_orderOf
→ pow_injOn_Iio_orderOf
mem_powers_iff_mem_range_order_of'
→ IsOfFinOrder.mem_powers_iff_mem_range_orderOf
orderOf_pow''
→ IsOfFinOrder.orderOf_pow
orderOf_pow_coprime
→ Nat.Coprime.orderOf_pow
zpow_eq_mod_orderOf
→ zpow_mod_orderOf
(and turned around)exists_pow_eq_one
→ isOfFinOrder_of_finite
pow_apply_eq_pow_mod_orderOf_cycleOf_apply
→ pow_mod_orderOf_cycleOf_apply
IsOfFinOrder.powers_eq_image_range_orderOf
IsOfFinOrder.natCard_powers_le_orderOf
IsOfFinOrder.finite_powers
finite_powers
infinite_powers
Nat.card_submonoidPowers
IsOfFinOrder.mem_powers_iff_mem_zpowers
IsOfFinOrder.powers_eq_zpowers
IsOfFinOrder.mem_zpowers_iff_mem_range_orderOf
IsOfFinOrder.exists_pow_eq_one
decidableMemPowers
/fintypePowers
to GroupTheory.Submonoid.Membership
and decidableMemZpowers
/fintypeZpowers
to GroupTheory.Subgroup.ZPowers
.finEquivPowers
, finEquivZpowers
, powersEquivPowers
and zpowersEquivZpowers
now assume IsOfFinTorsion x
instead of Finite G
.isOfFinOrder_iff_pow_eq_one
now takes one less explicit argument.Equiv.Perm.IsCycle.exists_pow_eq_one
since it was saying that a permutation over a finite type is torsion, but this is trivial since the group of permutation is itself finite, so we can use isOfFinOrder_of_finite
instead.@@ -256,7 +256,7 @@ theorem exponent_ne_zero_iff_range_orderOf_finite (h : ∀ g : G, 0 < orderOf g)
rw [h, zero_dvd_iff] at this
exact htpos.ne' this
refine' exponent_dvd_of_forall_pow_eq_one _ _ fun g => _
- rw [pow_eq_mod_orderOf, Nat.mod_eq_zero_of_dvd, pow_zero g]
+ rw [←pow_mod_orderOf, Nat.mod_eq_zero_of_dvd, pow_zero g]
apply Finset.dvd_prod_of_mem
rw [← Finset.mem_coe, ht]
exact Set.mem_range_self g
attribute [simp] ... in
-> attribute [local simp] ... in
(#7678)
Mathlib.Logic.Unique contains the line attribute [simp] eq_iff_true_of_subsingleton in ...
:
Despite what the in
part may imply, this adds the lemma to the simp set "globally", including for downstream files; it is likely that attribute [local simp] eq_iff_true_of_subsingleton in ...
was meant instead (or maybe scoped simp
, but I think "scoped" refers to the current namespace). Indeed, the relevant lemma is not marked with @[simp]
for possible slowness: https://github.com/leanprover/std4/blob/846e9e1d6bb534774d1acd2dc430e70987da3c18/Std/Logic.lean#L749. Adding it to the simp set causes the example at https://leanprover.zulipchat.com/#narrow/stream/287929-mathlib4/topic/Regression.20in.20simp to slow down.
This PR changes this and fixes the relevant downstream simp
s. There was also one ocurrence of attribute [simp] FullSubcategory.comp_def FullSubcategory.id_def in
in Mathlib.CategoryTheory.Monoidal.Subcategory but that was much easier to fix.
@@ -165,10 +165,10 @@ theorem exponent_min (m : ℕ) (hpos : 0 < m) (hm : m < exponent G) : ∃ g : G,
theorem exp_eq_one_of_subsingleton [Subsingleton G] : exponent G = 1 := by
apply le_antisymm
· apply exponent_min' _ Nat.one_pos
- simp
+ simp [eq_iff_true_of_subsingleton]
· apply Nat.succ_le_of_lt
apply exponent_pos_of_exists 1 Nat.one_pos
- simp
+ simp [eq_iff_true_of_subsingleton]
#align monoid.exp_eq_one_of_subsingleton Monoid.exp_eq_one_of_subsingleton
#align add_monoid.exp_eq_zero_of_subsingleton AddMonoid.exp_eq_zero_of_subsingleton
mathlib can't make up its mind on whether to spell "the prime factors of n
" as n.factors.toFinset
or n.factorization.support
, even though those two are defeq. This PR proposes to unify everything to a new definition Nat.primeFactors
, and streamline the existing scattered API about n.factors.toFinset
and n.factorization.support
to Nat.primeFactors
. We also get to write a bit more API that didn't make sense before, eg primeFactors_mono
.
@@ -224,7 +224,7 @@ theorem _root_.Nat.Prime.exists_orderOf_eq_pow_factorization_exponent {p : ℕ}
exact fun hd =>
hp.one_lt.not_le
((mul_le_iff_le_one_left he).mp <|
- Nat.le_of_dvd he <| Nat.mul_dvd_of_dvd_div (Nat.dvd_of_mem_factorization h) hd)
+ Nat.le_of_dvd he <| Nat.mul_dvd_of_dvd_div (Nat.dvd_of_mem_primeFactors h) hd)
obtain ⟨k, hk : exponent G = p ^ _ * k⟩ := Nat.ord_proj_dvd _ _
obtain ⟨t, ht⟩ := Nat.exists_eq_succ_of_ne_zero (Finsupp.mem_support_iff.mp h)
refine' ⟨g ^ k, _⟩
Monoid.exponent (Multiplicative G)
(#8093)
This also fixes a to_additive
naming error
@@ -80,6 +80,21 @@ noncomputable def exponent :=
variable {G}
+@[simp]
+theorem _root_.AddMonoid.exponent_additive :
+ AddMonoid.exponent (Additive G) = exponent G := rfl
+
+@[simp]
+theorem exponent_multiplicative {G : Type*} [AddMonoid G] :
+ exponent (Multiplicative G) = AddMonoid.exponent G := rfl
+
+open MulOpposite in
+@[to_additive (attr := simp)]
+theorem _root_.MulOpposite.exponent : exponent (MulOpposite G) = exponent G := by
+ simp only [Monoid.exponent, ExponentExists]
+ congr!
+ all_goals exact ⟨(op_injective <| · <| op ·), (unop_injective <| . <| unop .)⟩
+
@[to_additive]
theorem exponentExists_iff_ne_zero : ExponentExists G ↔ exponent G ≠ 0 := by
rw [exponent]
@@ -432,8 +447,8 @@ theorem Monoid.exponent_pi {ι : Type*} [Fintype ι] {M : ι → Type*} [∀ i,
/-- The exponent of product of two monoids is the `lcm` of the exponents of the
individuaul monoids. -/
-@[to_additive "The exponent of product of two additive monoids is the `lcm` of the exponents of the
-individuaul additive monoids."]
+@[to_additive AddMonoid.exponent_prod "The exponent of product of two additive monoids is the `lcm`
+of the exponents of the individuaul additive monoids."]
theorem Monoid.exponent_prod {M₁ M₂ : Type*} [Monoid M₁] [Monoid M₂] :
exponent (M₁ × M₂) = lcm (exponent M₁) (exponent M₂) := by
refine dvd_antisymm ?_ (lcm_dvd ?_ ?_)
@@ -9,6 +9,7 @@ import Mathlib.GroupTheory.OrderOfElement
import Mathlib.Algebra.GCDMonoid.Finset
import Mathlib.Data.Nat.Factorization.Basic
import Mathlib.Tactic.ByContra
+import Mathlib.Tactic.Peel
#align_import group_theory.exponent from "leanprover-community/mathlib"@"52fa514ec337dd970d71d8de8d0fd68b455a1e54"
@@ -34,6 +35,11 @@ it is equal to the lowest common multiple of the order of all elements of the gr
`Finset.lcm` of the order of its elements.
* `Monoid.exponent_eq_iSup_orderOf(')`: For a commutative cancel monoid, the exponent is
equal to `⨆ g : G, orderOf g` (or zero if it has any order-zero elements).
+* `Monoid.exponent_pi` and `Monoid.exponent_prod`: The exponent of a finite product of monoids is
+ the least common multiple (`Finset.lcm` and `lcm`, respectively) of the exponents of the
+ constituent monoids.
+* `MonoidHom.exponent_dvd`: If `f : M₁ →⋆ M₂` is surjective, then the exponent of `M₂` divides the
+ exponent of `M₁`.
## TODO
* Refactor the characteristic of a ring to be the exponent of its underlying additive group.
@@ -386,3 +392,58 @@ theorem card_dvd_exponent_pow_rank' {n : ℕ} (hG : ∀ g : G, g ^ n = 1) :
#align card_dvd_exponent_nsmul_rank' card_dvd_exponent_nsmul_rank'
end CommGroup
+
+section PiProd
+
+open Finset Monoid
+
+@[to_additive]
+theorem Monoid.exponent_pi_eq_zero {ι : Type*} {M : ι → Type*} [∀ i, Monoid (M i)] {j : ι}
+ (hj : exponent (M j) = 0) : exponent ((i : ι) → M i) = 0 := by
+ rw [@exponent_eq_zero_iff, ExponentExists] at hj ⊢
+ push_neg at hj ⊢
+ peel hj with _ n hn
+ obtain ⟨m, hm⟩ := this
+ refine ⟨Pi.mulSingle j m, fun h ↦ hm ?_⟩
+ simpa using congr_fun h j
+
+/-- If `f : M₁ →⋆ M₂` is surjective, then the exponent of `M₂` divides the exponent of `M₁`. -/
+@[to_additive]
+theorem MonoidHom.exponent_dvd {F M₁ M₂ : Type*} [Monoid M₁] [Monoid M₂] [MonoidHomClass F M₁ M₂]
+ {f : F} (hf : Function.Surjective f) : exponent M₂ ∣ exponent M₁ := by
+ refine Monoid.exponent_dvd_of_forall_pow_eq_one M₂ _ fun m₂ ↦ ?_
+ obtain ⟨m₁, rfl⟩ := hf m₂
+ rw [←map_pow, pow_exponent_eq_one, map_one]
+
+/-- The exponent of finite product of monoids is the `Finset.lcm` of the exponents of the
+constituent monoids. -/
+@[to_additive "The exponent of finite product of additive monoids is the `Finset.lcm` of the
+exponents of the constituent additive monoids."]
+theorem Monoid.exponent_pi {ι : Type*} [Fintype ι] {M : ι → Type*} [∀ i, Monoid (M i)] :
+ exponent ((i : ι) → M i) = lcm univ (exponent <| M ·) := by
+ refine dvd_antisymm ?_ ?_
+ · refine exponent_dvd_of_forall_pow_eq_one _ _ fun m ↦ ?_
+ ext i
+ rw [Pi.pow_apply, Pi.one_apply, ← orderOf_dvd_iff_pow_eq_one]
+ apply dvd_trans (Monoid.order_dvd_exponent (m i))
+ exact Finset.dvd_lcm (mem_univ i)
+ · apply Finset.lcm_dvd fun i _ ↦ ?_
+ exact MonoidHom.exponent_dvd (f := Pi.evalMonoidHom (M ·) i) (Function.surjective_eval i)
+
+/-- The exponent of product of two monoids is the `lcm` of the exponents of the
+individuaul monoids. -/
+@[to_additive "The exponent of product of two additive monoids is the `lcm` of the exponents of the
+individuaul additive monoids."]
+theorem Monoid.exponent_prod {M₁ M₂ : Type*} [Monoid M₁] [Monoid M₂] :
+ exponent (M₁ × M₂) = lcm (exponent M₁) (exponent M₂) := by
+ refine dvd_antisymm ?_ (lcm_dvd ?_ ?_)
+ · refine exponent_dvd_of_forall_pow_eq_one _ _ fun g ↦ ?_
+ ext1
+ · rw [Prod.pow_fst, Prod.fst_one, ← orderOf_dvd_iff_pow_eq_one]
+ exact dvd_trans (Monoid.order_dvd_exponent (g.1)) <| dvd_lcm_left _ _
+ · rw [Prod.pow_snd, Prod.snd_one, ← orderOf_dvd_iff_pow_eq_one]
+ exact dvd_trans (Monoid.order_dvd_exponent (g.2)) <| dvd_lcm_right _ _
+ · exact MonoidHom.exponent_dvd (f := MonoidHom.fst M₁ M₂) Prod.fst_surjective
+ · exact MonoidHom.exponent_dvd (f := MonoidHom.snd M₁ M₂) Prod.snd_surjective
+
+end PiProd
@@ -306,7 +306,7 @@ theorem exponent_eq_iSup_orderOf (h : ∀ g : G, 0 < orderOf g) :
have hpk' : orderOf (t ^ p ^ k) = orderOf t / p ^ k := by
rw [orderOf_pow' t (pow_ne_zero k hp.ne_zero), Nat.gcd_eq_right hpk]
obtain ⟨a, ha⟩ := Nat.exists_eq_add_of_lt hpe
- have hcoprime : (orderOf (t ^ p ^ k)).coprime (orderOf g) := by
+ have hcoprime : (orderOf (t ^ p ^ k)).Coprime (orderOf g) := by
rw [hg, Nat.coprime_pow_right_iff (pos_of_gt hpe), Nat.coprime_comm]
apply Or.resolve_right (Nat.coprime_or_dvd_of_prime hp _)
nth_rw 1 [← pow_one p]
@@ -386,4 +386,3 @@ theorem card_dvd_exponent_pow_rank' {n : ℕ} (hG : ∀ g : G, g ^ n = 1) :
#align card_dvd_exponent_nsmul_rank' card_dvd_exponent_nsmul_rank'
end CommGroup
-
@@ -306,7 +306,7 @@ theorem exponent_eq_iSup_orderOf (h : ∀ g : G, 0 < orderOf g) :
have hpk' : orderOf (t ^ p ^ k) = orderOf t / p ^ k := by
rw [orderOf_pow' t (pow_ne_zero k hp.ne_zero), Nat.gcd_eq_right hpk]
obtain ⟨a, ha⟩ := Nat.exists_eq_add_of_lt hpe
- have hcoprime : (orderOf (t ^ p ^ k)).Coprime (orderOf g) := by
+ have hcoprime : (orderOf (t ^ p ^ k)).coprime (orderOf g) := by
rw [hg, Nat.coprime_pow_right_iff (pos_of_gt hpe), Nat.coprime_comm]
apply Or.resolve_right (Nat.coprime_or_dvd_of_prime hp _)
nth_rw 1 [← pow_one p]
@@ -386,3 +386,4 @@ theorem card_dvd_exponent_pow_rank' {n : ℕ} (hG : ∀ g : G, g ^ n = 1) :
#align card_dvd_exponent_nsmul_rank' card_dvd_exponent_nsmul_rank'
end CommGroup
+
Some changes have already been review and delegated in #6910 and #7148.
The diff that needs looking at is https://github.com/leanprover-community/mathlib4/pull/7174/commits/64d6d07ee18163627c8f517eb31455411921c5ac
The std bump PR was insta-merged already!
Co-authored-by: leanprover-community-mathlib4-bot <leanprover-community-mathlib4-bot@users.noreply.github.com> Co-authored-by: Scott Morrison <scott.morrison@gmail.com>
@@ -306,7 +306,7 @@ theorem exponent_eq_iSup_orderOf (h : ∀ g : G, 0 < orderOf g) :
have hpk' : orderOf (t ^ p ^ k) = orderOf t / p ^ k := by
rw [orderOf_pow' t (pow_ne_zero k hp.ne_zero), Nat.gcd_eq_right hpk]
obtain ⟨a, ha⟩ := Nat.exists_eq_add_of_lt hpe
- have hcoprime : (orderOf (t ^ p ^ k)).coprime (orderOf g) := by
+ have hcoprime : (orderOf (t ^ p ^ k)).Coprime (orderOf g) := by
rw [hg, Nat.coprime_pow_right_iff (pos_of_gt hpe), Nat.coprime_comm]
apply Or.resolve_right (Nat.coprime_or_dvd_of_prime hp _)
nth_rw 1 [← pow_one p]
@@ -386,4 +386,3 @@ theorem card_dvd_exponent_pow_rank' {n : ℕ} (hG : ∀ g : G, g ^ n = 1) :
#align card_dvd_exponent_nsmul_rank' card_dvd_exponent_nsmul_rank'
end CommGroup
-
@@ -2,11 +2,6 @@
Copyright (c) 2021 Julian Kuelshammer. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Julian Kuelshammer
-
-! This file was ported from Lean 3 source module group_theory.exponent
-! leanprover-community/mathlib commit 52fa514ec337dd970d71d8de8d0fd68b455a1e54
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
-/
import Mathlib.Data.ZMod.Quotient
import Mathlib.GroupTheory.NoncommPiCoprod
@@ -15,6 +10,8 @@ import Mathlib.Algebra.GCDMonoid.Finset
import Mathlib.Data.Nat.Factorization.Basic
import Mathlib.Tactic.ByContra
+#align_import group_theory.exponent from "leanprover-community/mathlib"@"52fa514ec337dd970d71d8de8d0fd68b455a1e54"
+
/-!
# Exponent of a group
The unported dependencies are