group_theory.perm.cycle.concrete
⟷
Mathlib.GroupTheory.Perm.Cycle.Concrete
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)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(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
@@ -91,7 +91,7 @@ theorem isCycle_formPerm (hl : Nodup l) (hn : 2 ≤ l.length) : IsCycle (formPer
have : w ∈ x::y::l := mem_of_form_perm_ne_self _ _ hw
obtain ⟨k, hk, rfl⟩ := nth_le_of_mem this
use k
- simp only [zpow_coe_nat, form_perm_pow_apply_head _ _ hl k, Nat.mod_eq_of_lt hk]
+ simp only [zpow_natCast, form_perm_pow_apply_head _ _ hl k, Nat.mod_eq_of_lt hk]
#align list.is_cycle_form_perm List.isCycle_formPerm
-/
@@ -369,7 +369,7 @@ theorem next_toList_eq_apply (p : Perm α) (x y : α) (hy : y ∈ toList p x) :
obtain ⟨k, hk, hk'⟩ := hy.left.exists_pow_eq_of_mem_support hy.right
rw [← nth_le_to_list p x k (by simpa using hk)] at hk'
simp_rw [← hk']
- rw [next_nth_le _ (nodup_to_list _ _), nth_le_to_list, nth_le_to_list, ← mul_apply, ← pow_succ,
+ rw [next_nth_le _ (nodup_to_list _ _), nth_le_to_list, nth_le_to_list, ← mul_apply, ← pow_succ',
length_to_list, pow_apply_eq_pow_mod_order_of_cycle_of_apply p (k + 1), is_cycle.order_of]
exact is_cycle_cycle_of _ (mem_support.mp hy.right)
#align equiv.perm.next_to_list_eq_apply Equiv.Perm.next_toList_eq_apply
@@ -464,7 +464,7 @@ theorem formPerm_toList (f : Perm α) (x : α) : formPerm (toList f x) = f.cycle
by_cases hy : same_cycle f x y
· obtain ⟨k, hk, rfl⟩ := hy.exists_pow_eq_of_mem_support (mem_support.mpr hx)
rw [cycle_of_apply_apply_pow_self, List.formPerm_apply_mem_eq_next (nodup_to_list f x),
- next_to_list_eq_apply, pow_succ, mul_apply]
+ next_to_list_eq_apply, pow_succ', mul_apply]
rw [mem_to_list_iff]
exact ⟨⟨k, rfl⟩, mem_support.mpr hx⟩
· rw [cycle_of_apply_of_not_same_cycle hy, form_perm_apply_of_not_mem]
mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83
@@ -66,7 +66,7 @@ theorem formPerm_disjoint_iff (hl : Nodup l) (hl' : Nodup l') (hn : 2 ≤ l.leng
constructor
· rintro h x hx hx'
specialize h x
- rw [form_perm_apply_mem_eq_self_iff _ hl _ hx, form_perm_apply_mem_eq_self_iff _ hl' _ hx'] at h
+ rw [form_perm_apply_mem_eq_self_iff _ hl _ hx, form_perm_apply_mem_eq_self_iff _ hl' _ hx'] at h
rcases h with (hl | hl') <;> linarith
· intro h x
by_cases hx : x ∈ l; by_cases hx' : x ∈ l'
@@ -81,9 +81,9 @@ theorem formPerm_disjoint_iff (hl : Nodup l) (hl' : Nodup l') (hn : 2 ≤ l.leng
theorem isCycle_formPerm (hl : Nodup l) (hn : 2 ≤ l.length) : IsCycle (formPerm l) :=
by
cases' l with x l
- · norm_num at hn
+ · norm_num at hn
induction' l with y l IH generalizing x
- · norm_num at hn
+ · norm_num at hn
· use x
constructor
· rwa [form_perm_apply_mem_ne_self_iff _ hl _ (mem_cons_self _ _)]
@@ -108,8 +108,8 @@ theorem pairwise_sameCycle_formPerm (hl : Nodup l) (hn : 2 ≤ l.length) :
#print List.cycleOf_formPerm /-
theorem cycleOf_formPerm (hl : Nodup l) (hn : 2 ≤ l.length) (x) :
cycleOf l.attach.formPerm x = l.attach.formPerm :=
- have hn : 2 ≤ l.attach.length := by rwa [← length_attach] at hn
- have hl : l.attach.Nodup := by rwa [← nodup_attach] at hl
+ have hn : 2 ≤ l.attach.length := by rwa [← length_attach] at hn
+ have hl : l.attach.Nodup := by rwa [← nodup_attach] at hl
(isCycle_formPerm hl hn).cycleOf_eq
((formPerm_apply_mem_ne_self_iff _ hl _ (mem_attach _ _)).mpr hn)
#align list.cycle_of_form_perm List.cycleOf_formPerm
@@ -119,8 +119,8 @@ theorem cycleOf_formPerm (hl : Nodup l) (hn : 2 ≤ l.length) (x) :
theorem cycleType_formPerm (hl : Nodup l) (hn : 2 ≤ l.length) :
cycleType l.attach.formPerm = {l.length} :=
by
- rw [← length_attach] at hn
- rw [← nodup_attach] at hl
+ rw [← length_attach] at hn
+ rw [← nodup_attach] at hl
rw [cycle_type_eq [l.attach.form_perm]]
· simp only [map, Function.comp_apply]
rw [support_form_perm_of_nodup _ hl, card_to_finset, dedup_eq_self.mpr hl]
@@ -174,10 +174,10 @@ theorem formPerm_subsingleton (s : Cycle α) (h : Subsingleton s) : formPerm s h
by
induction s using Quot.inductionOn
simp only [form_perm_coe, mk_eq_coe]
- simp only [length_subsingleton_iff, length_coe, mk_eq_coe] at h
+ simp only [length_subsingleton_iff, length_coe, mk_eq_coe] at h
cases' s with hd tl
· simp
- · simp only [length_eq_zero, add_le_iff_nonpos_left, List.length, nonpos_iff_eq_zero] at h
+ · simp only [length_eq_zero, add_le_iff_nonpos_left, List.length, nonpos_iff_eq_zero] at h
simp [h]
#align cycle.form_perm_subsingleton Cycle.formPerm_subsingleton
-/
@@ -318,7 +318,7 @@ theorem mem_toList_iff {y : α} : y ∈ toList p x ↔ SameCycle p x y ∧ x ∈
· rintro ⟨n, hx, rfl⟩
refine' ⟨⟨n, rfl⟩, _⟩
contrapose! hx
- rw [← support_cycle_of_eq_nil_iff] at hx
+ rw [← support_cycle_of_eq_nil_iff] at hx
simp [hx]
· rintro ⟨h, hx⟩
simpa using h.exists_pow_eq_of_mem_support hx
@@ -329,27 +329,27 @@ theorem mem_toList_iff {y : α} : y ∈ toList p x ↔ SameCycle p x y ∧ x ∈
theorem nodup_toList (p : Perm α) (x : α) : Nodup (toList p x) :=
by
by_cases hx : p x = x
- · rw [← not_mem_support, ← to_list_eq_nil_iff] at hx
+ · rw [← not_mem_support, ← to_list_eq_nil_iff] at hx
simp [hx]
have hc : is_cycle (cycle_of p x) := is_cycle_cycle_of p hx
rw [nodup_iff_nth_le_inj]
rintro n m hn hm
- rw [length_to_list, ← hc.order_of] at hm hn
- rw [← cycle_of_apply_self, ← Ne.def, ← mem_support] at hx
+ rw [length_to_list, ← hc.order_of] at hm hn
+ rw [← cycle_of_apply_self, ← Ne.def, ← mem_support] at hx
rw [nth_le_to_list, nth_le_to_list, ← cycle_of_pow_apply_self p x n, ←
cycle_of_pow_apply_self p x m]
cases n <;> cases m
· simp
· rw [← hc.support_pow_of_pos_of_lt_order_of m.zero_lt_succ hm, mem_support,
- cycle_of_pow_apply_self] at hx
+ cycle_of_pow_apply_self] at hx
simp [hx.symm]
· rw [← hc.support_pow_of_pos_of_lt_order_of n.zero_lt_succ hn, mem_support,
- cycle_of_pow_apply_self] at hx
+ cycle_of_pow_apply_self] at hx
simp [hx]
intro h
have hn' : ¬orderOf (p.cycle_of x) ∣ n.succ := Nat.not_dvd_of_pos_of_lt n.zero_lt_succ hn
have hm' : ¬orderOf (p.cycle_of x) ∣ m.succ := Nat.not_dvd_of_pos_of_lt m.zero_lt_succ hm
- rw [← hc.support_pow_eq_iff] at hn' hm'
+ rw [← hc.support_pow_eq_iff] at hn' hm'
rw [← Nat.mod_eq_of_lt hn, ← Nat.mod_eq_of_lt hm, ← pow_inj_mod]
refine' support_congr _ _
· rw [hm', hn']
@@ -365,9 +365,9 @@ theorem nodup_toList (p : Perm α) (x : α) : Nodup (toList p x) :=
#print Equiv.Perm.next_toList_eq_apply /-
theorem next_toList_eq_apply (p : Perm α) (x y : α) (hy : y ∈ toList p x) :
next (toList p x) y hy = p y := by
- rw [mem_to_list_iff] at hy
+ rw [mem_to_list_iff] at hy
obtain ⟨k, hk, hk'⟩ := hy.left.exists_pow_eq_of_mem_support hy.right
- rw [← nth_le_to_list p x k (by simpa using hk)] at hk'
+ rw [← nth_le_to_list p x k (by simpa using hk)] at hk'
simp_rw [← hk']
rw [next_nth_le _ (nodup_to_list _ _), nth_le_to_list, nth_le_to_list, ← mul_apply, ← pow_succ,
length_to_list, pow_apply_eq_pow_mod_order_of_cycle_of_apply p (k + 1), is_cycle.order_of]
@@ -392,7 +392,7 @@ theorem SameCycle.toList_isRotated {f : Perm α} {x y : α} (h : SameCycle f x y
toList f x ~r toList f y := by
by_cases hx : x ∈ f.support
· obtain ⟨_ | k, hk, hy⟩ := h.exists_pow_eq_of_mem_support hx
- · simp only [coe_one, id.def, pow_zero] at hy
+ · simp only [coe_one, id.def, pow_zero] at hy
simp [hy]
use k.succ
rw [← to_list_pow_apply_eq_rotate, hy]
mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83
@@ -91,7 +91,7 @@ theorem isCycle_formPerm (hl : Nodup l) (hn : 2 ≤ l.length) : IsCycle (formPer
have : w ∈ x::y::l := mem_of_form_perm_ne_self _ _ hw
obtain ⟨k, hk, rfl⟩ := nth_le_of_mem this
use k
- simp only [zpow_ofNat, form_perm_pow_apply_head _ _ hl k, Nat.mod_eq_of_lt hk]
+ simp only [zpow_coe_nat, form_perm_pow_apply_head _ _ hl k, Nat.mod_eq_of_lt hk]
#align list.is_cycle_form_perm List.isCycle_formPerm
-/
mathlib commit https://github.com/leanprover-community/mathlib/commit/ce64cd319bb6b3e82f31c2d38e79080d377be451
@@ -3,9 +3,9 @@ Copyright (c) 2021 Yakov Pechersky. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Yakov Pechersky
-/
-import Mathbin.Data.List.Cycle
-import Mathbin.GroupTheory.Perm.Cycle.Type
-import Mathbin.GroupTheory.Perm.List
+import Data.List.Cycle
+import GroupTheory.Perm.Cycle.Type
+import GroupTheory.Perm.List
#align_import group_theory.perm.cycle.concrete from "leanprover-community/mathlib"@"38df578a6450a8c5142b3727e3ae894c2300cae0"
mathlib commit https://github.com/leanprover-community/mathlib/commit/8ea5598db6caeddde6cb734aa179cc2408dbd345
@@ -2,16 +2,13 @@
Copyright (c) 2021 Yakov Pechersky. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Yakov Pechersky
-
-! This file was ported from Lean 3 source module group_theory.perm.cycle.concrete
-! leanprover-community/mathlib commit 38df578a6450a8c5142b3727e3ae894c2300cae0
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
-/
import Mathbin.Data.List.Cycle
import Mathbin.GroupTheory.Perm.Cycle.Type
import Mathbin.GroupTheory.Perm.List
+#align_import group_theory.perm.cycle.concrete from "leanprover-community/mathlib"@"38df578a6450a8c5142b3727e3ae894c2300cae0"
+
/-!
# Properties of cyclic permutations constructed from lists/cycles
mathlib commit https://github.com/leanprover-community/mathlib/commit/9fb8964792b4237dac6200193a0d533f1b3f7423
@@ -172,6 +172,7 @@ theorem formPerm_coe (l : List α) (hl : l.Nodup) : formPerm (l : Cycle α) hl =
#align cycle.form_perm_coe Cycle.formPerm_coe
-/
+#print Cycle.formPerm_subsingleton /-
theorem formPerm_subsingleton (s : Cycle α) (h : Subsingleton s) : formPerm s h.Nodup = 1 :=
by
induction s using Quot.inductionOn
@@ -182,6 +183,7 @@ theorem formPerm_subsingleton (s : Cycle α) (h : Subsingleton s) : formPerm s h
· simp only [length_eq_zero, add_le_iff_nonpos_left, List.length, nonpos_iff_eq_zero] at h
simp [h]
#align cycle.form_perm_subsingleton Cycle.formPerm_subsingleton
+-/
#print Cycle.isCycle_formPerm /-
theorem isCycle_formPerm (s : Cycle α) (h : Nodup s) (hn : Nontrivial s) : IsCycle (formPerm s h) :=
@@ -219,12 +221,14 @@ theorem formPerm_apply_mem_eq_next (s : Cycle α) (h : Nodup s) (x : α) (hx : x
#align cycle.form_perm_apply_mem_eq_next Cycle.formPerm_apply_mem_eq_next
-/
+#print Cycle.formPerm_reverse /-
theorem formPerm_reverse (s : Cycle α) (h : Nodup s) :
formPerm s.reverse (nodup_reverse_iff.mpr h) = (formPerm s h)⁻¹ :=
by
induction s using Quot.inductionOn
simpa using form_perm_reverse _ h
#align cycle.form_perm_reverse Cycle.formPerm_reverse
+-/
#print Cycle.formPerm_eq_formPerm_iff /-
theorem formPerm_eq_formPerm_iff {α : Type _} [DecidableEq α] {s s' : Cycle α} {hs : s.Nodup}
@@ -257,9 +261,11 @@ def toList : List α :=
#align equiv.perm.to_list Equiv.Perm.toList
-/
+#print Equiv.Perm.toList_one /-
@[simp]
theorem toList_one : toList (1 : Perm α) x = [] := by simp [to_list, cycle_of_one]
#align equiv.perm.to_list_one Equiv.Perm.toList_one
+-/
#print Equiv.Perm.toList_eq_nil_iff /-
@[simp]
@@ -417,6 +423,7 @@ theorem toList_formPerm_singleton (x y : α) : toList (formPerm [x]) y = [] := b
#align equiv.perm.to_list_form_perm_singleton Equiv.Perm.toList_formPerm_singleton
-/
+#print Equiv.Perm.toList_formPerm_nontrivial /-
theorem toList_formPerm_nontrivial (l : List α) (hl : 2 ≤ l.length) (hn : Nodup l) :
toList (formPerm l) (l.nthLe 0 (zero_lt_two.trans_le hl)) = l :=
by
@@ -431,6 +438,7 @@ theorem toList_formPerm_nontrivial (l : List α) (hl : 2 ≤ l.length) (hn : Nod
simp [form_perm_pow_apply_nth_le _ hn, Nat.mod_eq_of_lt hk']
· simpa [hs] using nth_le_mem _ _ _
#align equiv.perm.to_list_form_perm_nontrivial Equiv.Perm.toList_formPerm_nontrivial
+-/
#print Equiv.Perm.toList_formPerm_isRotated_self /-
theorem toList_formPerm_isRotated_self (l : List α) (hl : 2 ≤ l.length) (hn : Nodup l) (x : α)
@@ -620,7 +628,6 @@ def isoCycle' : { f : Perm α // IsCycle f } ≃ { s : Cycle α // s.Nodup ∧ s
#align equiv.perm.iso_cycle' Equiv.Perm.isoCycle'
-/
--- mathport name: «exprc[ ,]»
notation3"c["(l ", "* => foldr (h t => List.cons h t) List.nil)"]" =>
Cycle.formPerm (↑l) (Cycle.nodup_coe_iff.mpr (by decide))
mathlib commit https://github.com/leanprover-community/mathlib/commit/5f25c089cb34db4db112556f23c50d12da81b297
@@ -621,7 +621,7 @@ def isoCycle' : { f : Perm α // IsCycle f } ≃ { s : Cycle α // s.Nodup ∧ s
-/
-- mathport name: «exprc[ ,]»
-notation3"c["(l", "* => foldr (h t => List.cons h t) List.nil)"]" =>
+notation3"c["(l ", "* => foldr (h t => List.cons h t) List.nil)"]" =>
Cycle.formPerm (↑l) (Cycle.nodup_coe_iff.mpr (by decide))
#print Equiv.Perm.repr_perm /-
mathlib commit https://github.com/leanprover-community/mathlib/commit/cca40788df1b8755d5baf17ab2f27dacc2e17acb
@@ -69,7 +69,7 @@ theorem formPerm_disjoint_iff (hl : Nodup l) (hl' : Nodup l') (hn : 2 ≤ l.leng
constructor
· rintro h x hx hx'
specialize h x
- rw [form_perm_apply_mem_eq_self_iff _ hl _ hx, form_perm_apply_mem_eq_self_iff _ hl' _ hx'] at h
+ rw [form_perm_apply_mem_eq_self_iff _ hl _ hx, form_perm_apply_mem_eq_self_iff _ hl' _ hx'] at h
rcases h with (hl | hl') <;> linarith
· intro h x
by_cases hx : x ∈ l; by_cases hx' : x ∈ l'
@@ -84,9 +84,9 @@ theorem formPerm_disjoint_iff (hl : Nodup l) (hl' : Nodup l') (hn : 2 ≤ l.leng
theorem isCycle_formPerm (hl : Nodup l) (hn : 2 ≤ l.length) : IsCycle (formPerm l) :=
by
cases' l with x l
- · norm_num at hn
+ · norm_num at hn
induction' l with y l IH generalizing x
- · norm_num at hn
+ · norm_num at hn
· use x
constructor
· rwa [form_perm_apply_mem_ne_self_iff _ hl _ (mem_cons_self _ _)]
@@ -111,8 +111,8 @@ theorem pairwise_sameCycle_formPerm (hl : Nodup l) (hn : 2 ≤ l.length) :
#print List.cycleOf_formPerm /-
theorem cycleOf_formPerm (hl : Nodup l) (hn : 2 ≤ l.length) (x) :
cycleOf l.attach.formPerm x = l.attach.formPerm :=
- have hn : 2 ≤ l.attach.length := by rwa [← length_attach] at hn
- have hl : l.attach.Nodup := by rwa [← nodup_attach] at hl
+ have hn : 2 ≤ l.attach.length := by rwa [← length_attach] at hn
+ have hl : l.attach.Nodup := by rwa [← nodup_attach] at hl
(isCycle_formPerm hl hn).cycleOf_eq
((formPerm_apply_mem_ne_self_iff _ hl _ (mem_attach _ _)).mpr hn)
#align list.cycle_of_form_perm List.cycleOf_formPerm
@@ -122,8 +122,8 @@ theorem cycleOf_formPerm (hl : Nodup l) (hn : 2 ≤ l.length) (x) :
theorem cycleType_formPerm (hl : Nodup l) (hn : 2 ≤ l.length) :
cycleType l.attach.formPerm = {l.length} :=
by
- rw [← length_attach] at hn
- rw [← nodup_attach] at hl
+ rw [← length_attach] at hn
+ rw [← nodup_attach] at hl
rw [cycle_type_eq [l.attach.form_perm]]
· simp only [map, Function.comp_apply]
rw [support_form_perm_of_nodup _ hl, card_to_finset, dedup_eq_self.mpr hl]
@@ -176,10 +176,10 @@ theorem formPerm_subsingleton (s : Cycle α) (h : Subsingleton s) : formPerm s h
by
induction s using Quot.inductionOn
simp only [form_perm_coe, mk_eq_coe]
- simp only [length_subsingleton_iff, length_coe, mk_eq_coe] at h
+ simp only [length_subsingleton_iff, length_coe, mk_eq_coe] at h
cases' s with hd tl
· simp
- · simp only [length_eq_zero, add_le_iff_nonpos_left, List.length, nonpos_iff_eq_zero] at h
+ · simp only [length_eq_zero, add_le_iff_nonpos_left, List.length, nonpos_iff_eq_zero] at h
simp [h]
#align cycle.form_perm_subsingleton Cycle.formPerm_subsingleton
@@ -315,7 +315,7 @@ theorem mem_toList_iff {y : α} : y ∈ toList p x ↔ SameCycle p x y ∧ x ∈
· rintro ⟨n, hx, rfl⟩
refine' ⟨⟨n, rfl⟩, _⟩
contrapose! hx
- rw [← support_cycle_of_eq_nil_iff] at hx
+ rw [← support_cycle_of_eq_nil_iff] at hx
simp [hx]
· rintro ⟨h, hx⟩
simpa using h.exists_pow_eq_of_mem_support hx
@@ -326,27 +326,27 @@ theorem mem_toList_iff {y : α} : y ∈ toList p x ↔ SameCycle p x y ∧ x ∈
theorem nodup_toList (p : Perm α) (x : α) : Nodup (toList p x) :=
by
by_cases hx : p x = x
- · rw [← not_mem_support, ← to_list_eq_nil_iff] at hx
+ · rw [← not_mem_support, ← to_list_eq_nil_iff] at hx
simp [hx]
have hc : is_cycle (cycle_of p x) := is_cycle_cycle_of p hx
rw [nodup_iff_nth_le_inj]
rintro n m hn hm
- rw [length_to_list, ← hc.order_of] at hm hn
- rw [← cycle_of_apply_self, ← Ne.def, ← mem_support] at hx
+ rw [length_to_list, ← hc.order_of] at hm hn
+ rw [← cycle_of_apply_self, ← Ne.def, ← mem_support] at hx
rw [nth_le_to_list, nth_le_to_list, ← cycle_of_pow_apply_self p x n, ←
cycle_of_pow_apply_self p x m]
cases n <;> cases m
· simp
· rw [← hc.support_pow_of_pos_of_lt_order_of m.zero_lt_succ hm, mem_support,
- cycle_of_pow_apply_self] at hx
+ cycle_of_pow_apply_self] at hx
simp [hx.symm]
· rw [← hc.support_pow_of_pos_of_lt_order_of n.zero_lt_succ hn, mem_support,
- cycle_of_pow_apply_self] at hx
+ cycle_of_pow_apply_self] at hx
simp [hx]
intro h
have hn' : ¬orderOf (p.cycle_of x) ∣ n.succ := Nat.not_dvd_of_pos_of_lt n.zero_lt_succ hn
have hm' : ¬orderOf (p.cycle_of x) ∣ m.succ := Nat.not_dvd_of_pos_of_lt m.zero_lt_succ hm
- rw [← hc.support_pow_eq_iff] at hn' hm'
+ rw [← hc.support_pow_eq_iff] at hn' hm'
rw [← Nat.mod_eq_of_lt hn, ← Nat.mod_eq_of_lt hm, ← pow_inj_mod]
refine' support_congr _ _
· rw [hm', hn']
@@ -362,9 +362,9 @@ theorem nodup_toList (p : Perm α) (x : α) : Nodup (toList p x) :=
#print Equiv.Perm.next_toList_eq_apply /-
theorem next_toList_eq_apply (p : Perm α) (x y : α) (hy : y ∈ toList p x) :
next (toList p x) y hy = p y := by
- rw [mem_to_list_iff] at hy
+ rw [mem_to_list_iff] at hy
obtain ⟨k, hk, hk'⟩ := hy.left.exists_pow_eq_of_mem_support hy.right
- rw [← nth_le_to_list p x k (by simpa using hk)] at hk'
+ rw [← nth_le_to_list p x k (by simpa using hk)] at hk'
simp_rw [← hk']
rw [next_nth_le _ (nodup_to_list _ _), nth_le_to_list, nth_le_to_list, ← mul_apply, ← pow_succ,
length_to_list, pow_apply_eq_pow_mod_order_of_cycle_of_apply p (k + 1), is_cycle.order_of]
@@ -389,7 +389,7 @@ theorem SameCycle.toList_isRotated {f : Perm α} {x y : α} (h : SameCycle f x y
toList f x ~r toList f y := by
by_cases hx : x ∈ f.support
· obtain ⟨_ | k, hk, hy⟩ := h.exists_pow_eq_of_mem_support hx
- · simp only [coe_one, id.def, pow_zero] at hy
+ · simp only [coe_one, id.def, pow_zero] at hy
simp [hy]
use k.succ
rw [← to_list_pow_apply_eq_rotate, hy]
@@ -529,7 +529,7 @@ def isoCycle : { f : Perm α // IsCycle f } ≃ { s : Cycle α // s.Nodup ∧ s.
obtain ⟨x, -, -, hx, -⟩ := id ht
have hl : 2 ≤ s.length := by simpa using Cycle.length_nontrivial ht
simp only [Cycle.mk_eq_coe, Cycle.nodup_coe_iff, Cycle.mem_coe_iff, Subtype.coe_mk,
- Cycle.formPerm_coe] at hn hx⊢
+ Cycle.formPerm_coe] at hn hx ⊢
rw [to_cycle_eq_to_list _ _ x]
· refine' Quotient.sound' _
exact to_list_form_perm_is_rotated_self _ hl hn _ hx
mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb
@@ -172,12 +172,6 @@ theorem formPerm_coe (l : List α) (hl : l.Nodup) : formPerm (l : Cycle α) hl =
#align cycle.form_perm_coe Cycle.formPerm_coe
-/
-/- warning: cycle.form_perm_subsingleton -> Cycle.formPerm_subsingleton is a dubious translation:
-lean 3 declaration is
- forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] (s : Cycle.{u1} α) (h : Cycle.Subsingleton.{u1} α s), Eq.{succ u1} (Equiv.Perm.{succ u1} α) (Cycle.formPerm.{u1} α (fun (a : α) (b : α) => _inst_1 a b) s (Cycle.Subsingleton.nodup.{u1} α s h)) (OfNat.ofNat.{u1} (Equiv.Perm.{succ u1} α) 1 (OfNat.mk.{u1} (Equiv.Perm.{succ u1} α) 1 (One.one.{u1} (Equiv.Perm.{succ u1} α) (MulOneClass.toHasOne.{u1} (Equiv.Perm.{succ u1} α) (Monoid.toMulOneClass.{u1} (Equiv.Perm.{succ u1} α) (DivInvMonoid.toMonoid.{u1} (Equiv.Perm.{succ u1} α) (Group.toDivInvMonoid.{u1} (Equiv.Perm.{succ u1} α) (Equiv.Perm.permGroup.{u1} α))))))))
-but is expected to have type
- forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] (s : Cycle.{u1} α) (h : Cycle.Subsingleton.{u1} α s), Eq.{succ u1} (Equiv.Perm.{succ u1} α) (Cycle.formPerm.{u1} α (fun (a : α) (b : α) => _inst_1 a b) s (Cycle.Subsingleton.nodup.{u1} α s h)) (OfNat.ofNat.{u1} (Equiv.Perm.{succ u1} α) 1 (One.toOfNat1.{u1} (Equiv.Perm.{succ u1} α) (InvOneClass.toOne.{u1} (Equiv.Perm.{succ u1} α) (DivInvOneMonoid.toInvOneClass.{u1} (Equiv.Perm.{succ u1} α) (DivisionMonoid.toDivInvOneMonoid.{u1} (Equiv.Perm.{succ u1} α) (Group.toDivisionMonoid.{u1} (Equiv.Perm.{succ u1} α) (Equiv.Perm.permGroup.{u1} α)))))))
-Case conversion may be inaccurate. Consider using '#align cycle.form_perm_subsingleton Cycle.formPerm_subsingletonₓ'. -/
theorem formPerm_subsingleton (s : Cycle α) (h : Subsingleton s) : formPerm s h.Nodup = 1 :=
by
induction s using Quot.inductionOn
@@ -225,12 +219,6 @@ theorem formPerm_apply_mem_eq_next (s : Cycle α) (h : Nodup s) (x : α) (hx : x
#align cycle.form_perm_apply_mem_eq_next Cycle.formPerm_apply_mem_eq_next
-/
-/- warning: cycle.form_perm_reverse -> Cycle.formPerm_reverse is a dubious translation:
-lean 3 declaration is
- forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] (s : Cycle.{u1} α) (h : Cycle.Nodup.{u1} α s), Eq.{succ u1} (Equiv.Perm.{succ u1} α) (Cycle.formPerm.{u1} α (fun (a : α) (b : α) => _inst_1 a b) (Cycle.reverse.{u1} α s) (Iff.mpr (Cycle.Nodup.{u1} α (Cycle.reverse.{u1} α s)) (Cycle.Nodup.{u1} α s) (Cycle.nodup_reverse_iff.{u1} α s) h)) (Inv.inv.{u1} (Equiv.Perm.{succ u1} α) (DivInvMonoid.toHasInv.{u1} (Equiv.Perm.{succ u1} α) (Group.toDivInvMonoid.{u1} (Equiv.Perm.{succ u1} α) (Equiv.Perm.permGroup.{u1} α))) (Cycle.formPerm.{u1} α (fun (a : α) (b : α) => _inst_1 a b) s h))
-but is expected to have type
- forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] (s : Cycle.{u1} α) (h : Cycle.Nodup.{u1} α s), Eq.{succ u1} (Equiv.Perm.{succ u1} α) (Cycle.formPerm.{u1} α (fun (a : α) (b : α) => _inst_1 a b) (Cycle.reverse.{u1} α s) (Iff.mpr (Cycle.Nodup.{u1} α (Cycle.reverse.{u1} α s)) (Cycle.Nodup.{u1} α s) (Cycle.nodup_reverse_iff.{u1} α s) h)) (Inv.inv.{u1} (Equiv.Perm.{succ u1} α) (InvOneClass.toInv.{u1} (Equiv.Perm.{succ u1} α) (DivInvOneMonoid.toInvOneClass.{u1} (Equiv.Perm.{succ u1} α) (DivisionMonoid.toDivInvOneMonoid.{u1} (Equiv.Perm.{succ u1} α) (Group.toDivisionMonoid.{u1} (Equiv.Perm.{succ u1} α) (Equiv.Perm.permGroup.{u1} α))))) (Cycle.formPerm.{u1} α (fun (a : α) (b : α) => _inst_1 a b) s h))
-Case conversion may be inaccurate. Consider using '#align cycle.form_perm_reverse Cycle.formPerm_reverseₓ'. -/
theorem formPerm_reverse (s : Cycle α) (h : Nodup s) :
formPerm s.reverse (nodup_reverse_iff.mpr h) = (formPerm s h)⁻¹ :=
by
@@ -269,12 +257,6 @@ def toList : List α :=
#align equiv.perm.to_list Equiv.Perm.toList
-/
-/- warning: equiv.perm.to_list_one -> Equiv.Perm.toList_one is a dubious translation:
-lean 3 declaration is
- forall {α : Type.{u1}} [_inst_1 : Fintype.{u1} α] [_inst_2 : DecidableEq.{succ u1} α] (x : α), Eq.{succ u1} (List.{u1} α) (Equiv.Perm.toList.{u1} α _inst_1 (fun (a : α) (b : α) => _inst_2 a b) (OfNat.ofNat.{u1} (Equiv.Perm.{succ u1} α) 1 (OfNat.mk.{u1} (Equiv.Perm.{succ u1} α) 1 (One.one.{u1} (Equiv.Perm.{succ u1} α) (MulOneClass.toHasOne.{u1} (Equiv.Perm.{succ u1} α) (Monoid.toMulOneClass.{u1} (Equiv.Perm.{succ u1} α) (DivInvMonoid.toMonoid.{u1} (Equiv.Perm.{succ u1} α) (Group.toDivInvMonoid.{u1} (Equiv.Perm.{succ u1} α) (Equiv.Perm.permGroup.{u1} α)))))))) x) (List.nil.{u1} α)
-but is expected to have type
- forall {α : Type.{u1}} [_inst_1 : Fintype.{u1} α] [_inst_2 : DecidableEq.{succ u1} α] (x : α), Eq.{succ u1} (List.{u1} α) (Equiv.Perm.toList.{u1} α _inst_1 (fun (a : α) (b : α) => _inst_2 a b) (OfNat.ofNat.{u1} (Equiv.Perm.{succ u1} α) 1 (One.toOfNat1.{u1} (Equiv.Perm.{succ u1} α) (InvOneClass.toOne.{u1} (Equiv.Perm.{succ u1} α) (DivInvOneMonoid.toInvOneClass.{u1} (Equiv.Perm.{succ u1} α) (DivisionMonoid.toDivInvOneMonoid.{u1} (Equiv.Perm.{succ u1} α) (Group.toDivisionMonoid.{u1} (Equiv.Perm.{succ u1} α) (Equiv.Perm.permGroup.{u1} α))))))) x) (List.nil.{u1} α)
-Case conversion may be inaccurate. Consider using '#align equiv.perm.to_list_one Equiv.Perm.toList_oneₓ'. -/
@[simp]
theorem toList_one : toList (1 : Perm α) x = [] := by simp [to_list, cycle_of_one]
#align equiv.perm.to_list_one Equiv.Perm.toList_one
@@ -435,12 +417,6 @@ theorem toList_formPerm_singleton (x y : α) : toList (formPerm [x]) y = [] := b
#align equiv.perm.to_list_form_perm_singleton Equiv.Perm.toList_formPerm_singleton
-/
-/- warning: equiv.perm.to_list_form_perm_nontrivial -> Equiv.Perm.toList_formPerm_nontrivial is a dubious translation:
-lean 3 declaration is
- forall {α : Type.{u1}} [_inst_1 : Fintype.{u1} α] [_inst_2 : DecidableEq.{succ u1} α] (l : List.{u1} α) (hl : LE.le.{0} Nat Nat.hasLe (OfNat.ofNat.{0} Nat 2 (OfNat.mk.{0} Nat 2 (bit0.{0} Nat Nat.hasAdd (One.one.{0} Nat Nat.hasOne)))) (List.length.{u1} α l)), (List.Nodup.{u1} α l) -> (Eq.{succ u1} (List.{u1} α) (Equiv.Perm.toList.{u1} α _inst_1 (fun (a : α) (b : α) => _inst_2 a b) (List.formPerm.{u1} α (fun (a : α) (b : α) => _inst_2 a b) l) (List.nthLe.{u1} α l (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero))) (LT.lt.trans_le.{0} Nat (PartialOrder.toPreorder.{0} Nat (OrderedCancelAddCommMonoid.toPartialOrder.{0} Nat (StrictOrderedSemiring.toOrderedCancelAddCommMonoid.{0} Nat Nat.strictOrderedSemiring))) (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat (AddZeroClass.toHasZero.{0} Nat (AddMonoid.toAddZeroClass.{0} Nat (AddMonoidWithOne.toAddMonoid.{0} Nat (AddCommMonoidWithOne.toAddMonoidWithOne.{0} Nat (NonAssocSemiring.toAddCommMonoidWithOne.{0} Nat (Semiring.toNonAssocSemiring.{0} Nat Nat.semiring))))))))) (OfNat.ofNat.{0} Nat 2 (OfNat.mk.{0} Nat 2 (bit0.{0} Nat (AddZeroClass.toHasAdd.{0} Nat (AddMonoid.toAddZeroClass.{0} Nat (AddMonoidWithOne.toAddMonoid.{0} Nat (AddCommMonoidWithOne.toAddMonoidWithOne.{0} Nat (NonAssocSemiring.toAddCommMonoidWithOne.{0} Nat (Semiring.toNonAssocSemiring.{0} Nat Nat.semiring)))))) (One.one.{0} Nat (AddMonoidWithOne.toOne.{0} Nat (AddCommMonoidWithOne.toAddMonoidWithOne.{0} Nat (NonAssocSemiring.toAddCommMonoidWithOne.{0} Nat (Semiring.toNonAssocSemiring.{0} Nat Nat.semiring)))))))) (List.length.{u1} α l) (zero_lt_two.{0} Nat (AddCommMonoidWithOne.toAddMonoidWithOne.{0} Nat (NonAssocSemiring.toAddCommMonoidWithOne.{0} Nat (Semiring.toNonAssocSemiring.{0} Nat Nat.semiring))) (OrderedCancelAddCommMonoid.toPartialOrder.{0} Nat (StrictOrderedSemiring.toOrderedCancelAddCommMonoid.{0} Nat Nat.strictOrderedSemiring)) (OrderedSemiring.zeroLEOneClass.{0} Nat Nat.orderedSemiring) (NeZero.one.{0} Nat (NonAssocSemiring.toMulZeroOneClass.{0} Nat (Semiring.toNonAssocSemiring.{0} Nat Nat.semiring)) Nat.nontrivial) (OrderedAddCommMonoid.to_covariantClass_left.{0} Nat (OrderedSemiring.toOrderedAddCommMonoid.{0} Nat Nat.orderedSemiring))) hl))) l)
-but is expected to have type
- forall {α : Type.{u1}} [_inst_1 : Fintype.{u1} α] [_inst_2 : DecidableEq.{succ u1} α] (l : List.{u1} α) (hl : LE.le.{0} Nat instLENat (OfNat.ofNat.{0} Nat 2 (instOfNatNat 2)) (List.length.{u1} α l)), (List.Nodup.{u1} α l) -> (Eq.{succ u1} (List.{u1} α) (Equiv.Perm.toList.{u1} α _inst_1 (fun (a : α) (b : α) => _inst_2 a b) (List.formPerm.{u1} α (fun (a : α) (b : α) => _inst_2 a b) l) (List.nthLe.{u1} α l (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0)) (LT.lt.trans_le.{0} Nat (PartialOrder.toPreorder.{0} Nat (StrictOrderedSemiring.toPartialOrder.{0} Nat Nat.strictOrderedSemiring)) (OfNat.ofNat.{0} Nat 0 (Zero.toOfNat0.{0} Nat (AddMonoid.toZero.{0} Nat (AddMonoidWithOne.toAddMonoid.{0} Nat (AddCommMonoidWithOne.toAddMonoidWithOne.{0} Nat (NonAssocSemiring.toAddCommMonoidWithOne.{0} Nat (Semiring.toNonAssocSemiring.{0} Nat Nat.semiring))))))) (OfNat.ofNat.{0} Nat 2 (instOfNat.{0} Nat 2 (AddMonoidWithOne.toNatCast.{0} Nat (AddCommMonoidWithOne.toAddMonoidWithOne.{0} Nat (NonAssocSemiring.toAddCommMonoidWithOne.{0} Nat (Semiring.toNonAssocSemiring.{0} Nat Nat.semiring)))) (instAtLeastTwoHAddNatInstHAddInstAddNatOfNat (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0))))) (List.length.{u1} α l) (zero_lt_two.{0} Nat (AddCommMonoidWithOne.toAddMonoidWithOne.{0} Nat (NonAssocSemiring.toAddCommMonoidWithOne.{0} Nat (Semiring.toNonAssocSemiring.{0} Nat Nat.semiring))) (StrictOrderedSemiring.toPartialOrder.{0} Nat Nat.strictOrderedSemiring) (OrderedSemiring.zeroLEOneClass.{0} Nat Nat.orderedSemiring) (NeZero.succ Nat.zero) (OrderedAddCommMonoid.to_covariantClass_left.{0} Nat (OrderedSemiring.toOrderedAddCommMonoid.{0} Nat Nat.orderedSemiring))) hl))) l)
-Case conversion may be inaccurate. Consider using '#align equiv.perm.to_list_form_perm_nontrivial Equiv.Perm.toList_formPerm_nontrivialₓ'. -/
theorem toList_formPerm_nontrivial (l : List α) (hl : 2 ≤ l.length) (hn : Nodup l) :
toList (formPerm l) (l.nthLe 0 (zero_lt_two.trans_le hl)) = l :=
by
mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb
@@ -72,8 +72,7 @@ theorem formPerm_disjoint_iff (hl : Nodup l) (hl' : Nodup l') (hn : 2 ≤ l.leng
rw [form_perm_apply_mem_eq_self_iff _ hl _ hx, form_perm_apply_mem_eq_self_iff _ hl' _ hx'] at h
rcases h with (hl | hl') <;> linarith
· intro h x
- by_cases hx : x ∈ l
- by_cases hx' : x ∈ l'
+ by_cases hx : x ∈ l; by_cases hx' : x ∈ l'
· exact (h hx hx').elim
all_goals have := form_perm_eq_self_of_not_mem _ _ ‹_›; tauto
#align list.form_perm_disjoint_iff List.formPerm_disjoint_iff
mathlib commit https://github.com/leanprover-community/mathlib/commit/8d33f09cd7089ecf074b4791907588245aec5d1b
@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
Authors: Yakov Pechersky
! This file was ported from Lean 3 source module group_theory.perm.cycle.concrete
-! leanprover-community/mathlib commit 00638177efd1b2534fc5269363ebf42a7871df9a
+! leanprover-community/mathlib commit 38df578a6450a8c5142b3727e3ae894c2300cae0
! Please do not edit these lines, except to modify the commit id
! if you have ported upstream changes.
-/
@@ -16,6 +16,9 @@ import Mathbin.GroupTheory.Perm.List
# Properties of cyclic permutations constructed from lists/cycles
+> THIS FILE IS SYNCHRONIZED WITH MATHLIB4.
+> Any changes to this file require a corresponding PR to mathlib4.
+
In the following, `{α : Type*} [fintype α] [decidable_eq α]`.
## Main definitions
mathlib commit https://github.com/leanprover-community/mathlib/commit/1b0a28e1c93409dbf6d69526863cd9984ef652ce
@@ -58,6 +58,7 @@ namespace List
variable [DecidableEq α] {l l' : List α}
+#print List.formPerm_disjoint_iff /-
theorem formPerm_disjoint_iff (hl : Nodup l) (hl' : Nodup l') (hn : 2 ≤ l.length)
(hn' : 2 ≤ l'.length) : Perm.Disjoint (formPerm l) (formPerm l') ↔ l.Disjoint l' :=
by
@@ -73,9 +74,11 @@ theorem formPerm_disjoint_iff (hl : Nodup l) (hl' : Nodup l') (hn : 2 ≤ l.leng
· exact (h hx hx').elim
all_goals have := form_perm_eq_self_of_not_mem _ _ ‹_›; tauto
#align list.form_perm_disjoint_iff List.formPerm_disjoint_iff
+-/
/- ./././Mathport/Syntax/Translate/Expr.lean:177:8: unsupported: ambiguous notation -/
/- ./././Mathport/Syntax/Translate/Expr.lean:177:8: unsupported: ambiguous notation -/
+#print List.isCycle_formPerm /-
theorem isCycle_formPerm (hl : Nodup l) (hn : 2 ≤ l.length) : IsCycle (formPerm l) :=
by
cases' l with x l
@@ -91,7 +94,9 @@ theorem isCycle_formPerm (hl : Nodup l) (hn : 2 ≤ l.length) : IsCycle (formPer
use k
simp only [zpow_ofNat, form_perm_pow_apply_head _ _ hl k, Nat.mod_eq_of_lt hk]
#align list.is_cycle_form_perm List.isCycle_formPerm
+-/
+#print List.pairwise_sameCycle_formPerm /-
theorem pairwise_sameCycle_formPerm (hl : Nodup l) (hn : 2 ≤ l.length) :
Pairwise l.formPerm.SameCycle l :=
Pairwise.imp_mem.mpr
@@ -99,7 +104,9 @@ theorem pairwise_sameCycle_formPerm (hl : Nodup l) (hn : 2 ≤ l.length) :
(isCycle_formPerm hl hn).SameCycle ((formPerm_apply_mem_ne_self_iff _ hl _ hx).mpr hn)
((formPerm_apply_mem_ne_self_iff _ hl _ hy).mpr hn))
#align list.pairwise_same_cycle_form_perm List.pairwise_sameCycle_formPerm
+-/
+#print List.cycleOf_formPerm /-
theorem cycleOf_formPerm (hl : Nodup l) (hn : 2 ≤ l.length) (x) :
cycleOf l.attach.formPerm x = l.attach.formPerm :=
have hn : 2 ≤ l.attach.length := by rwa [← length_attach] at hn
@@ -107,7 +114,9 @@ theorem cycleOf_formPerm (hl : Nodup l) (hn : 2 ≤ l.length) (x) :
(isCycle_formPerm hl hn).cycleOf_eq
((formPerm_apply_mem_ne_self_iff _ hl _ (mem_attach _ _)).mpr hn)
#align list.cycle_of_form_perm List.cycleOf_formPerm
+-/
+#print List.cycleType_formPerm /-
theorem cycleType_formPerm (hl : Nodup l) (hn : 2 ≤ l.length) :
cycleType l.attach.formPerm = {l.length} :=
by
@@ -123,13 +132,16 @@ theorem cycleType_formPerm (hl : Nodup l) (hn : 2 ≤ l.length) :
· simpa using is_cycle_form_perm hl hn
· simp
#align list.cycle_type_form_perm List.cycleType_formPerm
+-/
+#print List.formPerm_apply_mem_eq_next /-
theorem formPerm_apply_mem_eq_next (hl : Nodup l) (x : α) (hx : x ∈ l) :
formPerm l x = next l x hx :=
by
obtain ⟨k, hk, rfl⟩ := nth_le_of_mem hx
rw [next_nth_le _ hl, form_perm_apply_nth_le _ hl]
#align list.form_perm_apply_mem_eq_next List.formPerm_apply_mem_eq_next
+-/
end List
@@ -137,6 +149,7 @@ namespace Cycle
variable [DecidableEq α] (s s' : Cycle α)
+#print Cycle.formPerm /-
/-- A cycle `s : cycle α` , given `nodup s` can be interpreted as a `equiv.perm α`
where each element in the list is permuted to the next one, defined as `form_perm`.
-/
@@ -148,12 +161,21 @@ def formPerm : ∀ (s : Cycle α) (h : Nodup s), Equiv.Perm α := fun s =>
· intro h₁ h₂ _
exact hEq_of_eq (form_perm_eq_of_is_rotated h₁ h)
#align cycle.form_perm Cycle.formPerm
+-/
+#print Cycle.formPerm_coe /-
@[simp]
theorem formPerm_coe (l : List α) (hl : l.Nodup) : formPerm (l : Cycle α) hl = l.formPerm :=
rfl
#align cycle.form_perm_coe Cycle.formPerm_coe
+-/
+/- warning: cycle.form_perm_subsingleton -> Cycle.formPerm_subsingleton is a dubious translation:
+lean 3 declaration is
+ forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] (s : Cycle.{u1} α) (h : Cycle.Subsingleton.{u1} α s), Eq.{succ u1} (Equiv.Perm.{succ u1} α) (Cycle.formPerm.{u1} α (fun (a : α) (b : α) => _inst_1 a b) s (Cycle.Subsingleton.nodup.{u1} α s h)) (OfNat.ofNat.{u1} (Equiv.Perm.{succ u1} α) 1 (OfNat.mk.{u1} (Equiv.Perm.{succ u1} α) 1 (One.one.{u1} (Equiv.Perm.{succ u1} α) (MulOneClass.toHasOne.{u1} (Equiv.Perm.{succ u1} α) (Monoid.toMulOneClass.{u1} (Equiv.Perm.{succ u1} α) (DivInvMonoid.toMonoid.{u1} (Equiv.Perm.{succ u1} α) (Group.toDivInvMonoid.{u1} (Equiv.Perm.{succ u1} α) (Equiv.Perm.permGroup.{u1} α))))))))
+but is expected to have type
+ forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] (s : Cycle.{u1} α) (h : Cycle.Subsingleton.{u1} α s), Eq.{succ u1} (Equiv.Perm.{succ u1} α) (Cycle.formPerm.{u1} α (fun (a : α) (b : α) => _inst_1 a b) s (Cycle.Subsingleton.nodup.{u1} α s h)) (OfNat.ofNat.{u1} (Equiv.Perm.{succ u1} α) 1 (One.toOfNat1.{u1} (Equiv.Perm.{succ u1} α) (InvOneClass.toOne.{u1} (Equiv.Perm.{succ u1} α) (DivInvOneMonoid.toInvOneClass.{u1} (Equiv.Perm.{succ u1} α) (DivisionMonoid.toDivInvOneMonoid.{u1} (Equiv.Perm.{succ u1} α) (Group.toDivisionMonoid.{u1} (Equiv.Perm.{succ u1} α) (Equiv.Perm.permGroup.{u1} α)))))))
+Case conversion may be inaccurate. Consider using '#align cycle.form_perm_subsingleton Cycle.formPerm_subsingletonₓ'. -/
theorem formPerm_subsingleton (s : Cycle α) (h : Subsingleton s) : formPerm s h.Nodup = 1 :=
by
induction s using Quot.inductionOn
@@ -165,12 +187,15 @@ theorem formPerm_subsingleton (s : Cycle α) (h : Subsingleton s) : formPerm s h
simp [h]
#align cycle.form_perm_subsingleton Cycle.formPerm_subsingleton
+#print Cycle.isCycle_formPerm /-
theorem isCycle_formPerm (s : Cycle α) (h : Nodup s) (hn : Nontrivial s) : IsCycle (formPerm s h) :=
by
induction s using Quot.inductionOn
exact List.isCycle_formPerm h (length_nontrivial hn)
#align cycle.is_cycle_form_perm Cycle.isCycle_formPerm
+-/
+#print Cycle.support_formPerm /-
theorem support_formPerm [Fintype α] (s : Cycle α) (h : Nodup s) (hn : Nontrivial s) :
support (formPerm s h) = s.toFinset :=
by
@@ -179,20 +204,31 @@ theorem support_formPerm [Fintype α] (s : Cycle α) (h : Nodup s) (hn : Nontriv
rintro _ rfl
simpa [Nat.succ_le_succ_iff] using length_nontrivial hn
#align cycle.support_form_perm Cycle.support_formPerm
+-/
+#print Cycle.formPerm_eq_self_of_not_mem /-
theorem formPerm_eq_self_of_not_mem (s : Cycle α) (h : Nodup s) (x : α) (hx : x ∉ s) :
formPerm s h x = x := by
induction s using Quot.inductionOn
simpa using List.formPerm_eq_self_of_not_mem _ _ hx
#align cycle.form_perm_eq_self_of_not_mem Cycle.formPerm_eq_self_of_not_mem
+-/
+#print Cycle.formPerm_apply_mem_eq_next /-
theorem formPerm_apply_mem_eq_next (s : Cycle α) (h : Nodup s) (x : α) (hx : x ∈ s) :
formPerm s h x = next s h x hx :=
by
induction s using Quot.inductionOn
simpa using List.formPerm_apply_mem_eq_next h _ _
#align cycle.form_perm_apply_mem_eq_next Cycle.formPerm_apply_mem_eq_next
+-/
+/- warning: cycle.form_perm_reverse -> Cycle.formPerm_reverse is a dubious translation:
+lean 3 declaration is
+ forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] (s : Cycle.{u1} α) (h : Cycle.Nodup.{u1} α s), Eq.{succ u1} (Equiv.Perm.{succ u1} α) (Cycle.formPerm.{u1} α (fun (a : α) (b : α) => _inst_1 a b) (Cycle.reverse.{u1} α s) (Iff.mpr (Cycle.Nodup.{u1} α (Cycle.reverse.{u1} α s)) (Cycle.Nodup.{u1} α s) (Cycle.nodup_reverse_iff.{u1} α s) h)) (Inv.inv.{u1} (Equiv.Perm.{succ u1} α) (DivInvMonoid.toHasInv.{u1} (Equiv.Perm.{succ u1} α) (Group.toDivInvMonoid.{u1} (Equiv.Perm.{succ u1} α) (Equiv.Perm.permGroup.{u1} α))) (Cycle.formPerm.{u1} α (fun (a : α) (b : α) => _inst_1 a b) s h))
+but is expected to have type
+ forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] (s : Cycle.{u1} α) (h : Cycle.Nodup.{u1} α s), Eq.{succ u1} (Equiv.Perm.{succ u1} α) (Cycle.formPerm.{u1} α (fun (a : α) (b : α) => _inst_1 a b) (Cycle.reverse.{u1} α s) (Iff.mpr (Cycle.Nodup.{u1} α (Cycle.reverse.{u1} α s)) (Cycle.Nodup.{u1} α s) (Cycle.nodup_reverse_iff.{u1} α s) h)) (Inv.inv.{u1} (Equiv.Perm.{succ u1} α) (InvOneClass.toInv.{u1} (Equiv.Perm.{succ u1} α) (DivInvOneMonoid.toInvOneClass.{u1} (Equiv.Perm.{succ u1} α) (DivisionMonoid.toDivInvOneMonoid.{u1} (Equiv.Perm.{succ u1} α) (Group.toDivisionMonoid.{u1} (Equiv.Perm.{succ u1} α) (Equiv.Perm.permGroup.{u1} α))))) (Cycle.formPerm.{u1} α (fun (a : α) (b : α) => _inst_1 a b) s h))
+Case conversion may be inaccurate. Consider using '#align cycle.form_perm_reverse Cycle.formPerm_reverseₓ'. -/
theorem formPerm_reverse (s : Cycle α) (h : Nodup s) :
formPerm s.reverse (nodup_reverse_iff.mpr h) = (formPerm s h)⁻¹ :=
by
@@ -200,6 +236,7 @@ theorem formPerm_reverse (s : Cycle α) (h : Nodup s) :
simpa using form_perm_reverse _ h
#align cycle.form_perm_reverse Cycle.formPerm_reverse
+#print Cycle.formPerm_eq_formPerm_iff /-
theorem formPerm_eq_formPerm_iff {α : Type _} [DecidableEq α] {s s' : Cycle α} {hs : s.Nodup}
{hs' : s'.Nodup} :
s.formPerm hs = s'.formPerm hs' ↔ s = s' ∨ s.Subsingleton ∧ s'.Subsingleton :=
@@ -211,6 +248,7 @@ theorem formPerm_eq_formPerm_iff {α : Type _} [DecidableEq α] {s s' : Cycle α
intro l l'
simpa using form_perm_eq_form_perm_iff
#align cycle.form_perm_eq_form_perm_iff Cycle.formPerm_eq_formPerm_iff
+-/
end Cycle
@@ -220,49 +258,72 @@ section Fintype
variable [Fintype α] [DecidableEq α] (p : Equiv.Perm α) (x : α)
+#print Equiv.Perm.toList /-
/-- `equiv.perm.to_list (f : perm α) (x : α)` generates the list `[x, f x, f (f x), ...]`
until looping. That means when `f x = x`, `to_list f x = []`.
-/
def toList : List α :=
(List.range (cycleOf p x).support.card).map fun k => (p ^ k) x
#align equiv.perm.to_list Equiv.Perm.toList
+-/
+/- warning: equiv.perm.to_list_one -> Equiv.Perm.toList_one is a dubious translation:
+lean 3 declaration is
+ forall {α : Type.{u1}} [_inst_1 : Fintype.{u1} α] [_inst_2 : DecidableEq.{succ u1} α] (x : α), Eq.{succ u1} (List.{u1} α) (Equiv.Perm.toList.{u1} α _inst_1 (fun (a : α) (b : α) => _inst_2 a b) (OfNat.ofNat.{u1} (Equiv.Perm.{succ u1} α) 1 (OfNat.mk.{u1} (Equiv.Perm.{succ u1} α) 1 (One.one.{u1} (Equiv.Perm.{succ u1} α) (MulOneClass.toHasOne.{u1} (Equiv.Perm.{succ u1} α) (Monoid.toMulOneClass.{u1} (Equiv.Perm.{succ u1} α) (DivInvMonoid.toMonoid.{u1} (Equiv.Perm.{succ u1} α) (Group.toDivInvMonoid.{u1} (Equiv.Perm.{succ u1} α) (Equiv.Perm.permGroup.{u1} α)))))))) x) (List.nil.{u1} α)
+but is expected to have type
+ forall {α : Type.{u1}} [_inst_1 : Fintype.{u1} α] [_inst_2 : DecidableEq.{succ u1} α] (x : α), Eq.{succ u1} (List.{u1} α) (Equiv.Perm.toList.{u1} α _inst_1 (fun (a : α) (b : α) => _inst_2 a b) (OfNat.ofNat.{u1} (Equiv.Perm.{succ u1} α) 1 (One.toOfNat1.{u1} (Equiv.Perm.{succ u1} α) (InvOneClass.toOne.{u1} (Equiv.Perm.{succ u1} α) (DivInvOneMonoid.toInvOneClass.{u1} (Equiv.Perm.{succ u1} α) (DivisionMonoid.toDivInvOneMonoid.{u1} (Equiv.Perm.{succ u1} α) (Group.toDivisionMonoid.{u1} (Equiv.Perm.{succ u1} α) (Equiv.Perm.permGroup.{u1} α))))))) x) (List.nil.{u1} α)
+Case conversion may be inaccurate. Consider using '#align equiv.perm.to_list_one Equiv.Perm.toList_oneₓ'. -/
@[simp]
theorem toList_one : toList (1 : Perm α) x = [] := by simp [to_list, cycle_of_one]
#align equiv.perm.to_list_one Equiv.Perm.toList_one
+#print Equiv.Perm.toList_eq_nil_iff /-
@[simp]
theorem toList_eq_nil_iff {p : Perm α} {x} : toList p x = [] ↔ x ∉ p.support := by simp [to_list]
#align equiv.perm.to_list_eq_nil_iff Equiv.Perm.toList_eq_nil_iff
+-/
+#print Equiv.Perm.length_toList /-
@[simp]
theorem length_toList : length (toList p x) = (cycleOf p x).support.card := by simp [to_list]
#align equiv.perm.length_to_list Equiv.Perm.length_toList
+-/
+#print Equiv.Perm.toList_ne_singleton /-
theorem toList_ne_singleton (y : α) : toList p x ≠ [y] :=
by
intro H
simpa [card_support_ne_one] using congr_arg length H
#align equiv.perm.to_list_ne_singleton Equiv.Perm.toList_ne_singleton
+-/
+#print Equiv.Perm.two_le_length_toList_iff_mem_support /-
theorem two_le_length_toList_iff_mem_support {p : Perm α} {x : α} :
2 ≤ length (toList p x) ↔ x ∈ p.support := by simp
#align equiv.perm.two_le_length_to_list_iff_mem_support Equiv.Perm.two_le_length_toList_iff_mem_support
+-/
+#print Equiv.Perm.length_toList_pos_of_mem_support /-
theorem length_toList_pos_of_mem_support (h : x ∈ p.support) : 0 < length (toList p x) :=
zero_lt_two.trans_le (two_le_length_toList_iff_mem_support.mpr h)
#align equiv.perm.length_to_list_pos_of_mem_support Equiv.Perm.length_toList_pos_of_mem_support
+-/
+#print Equiv.Perm.nthLe_toList /-
theorem nthLe_toList (n : ℕ) (hn : n < length (toList p x)) : nthLe (toList p x) n hn = (p ^ n) x :=
by simp [to_list]
#align equiv.perm.nth_le_to_list Equiv.Perm.nthLe_toList
+-/
+#print Equiv.Perm.toList_nthLe_zero /-
theorem toList_nthLe_zero (h : x ∈ p.support) :
(toList p x).nthLe 0 (length_toList_pos_of_mem_support _ _ h) = x := by simp [to_list]
#align equiv.perm.to_list_nth_le_zero Equiv.Perm.toList_nthLe_zero
+-/
variable {p} {x}
+#print Equiv.Perm.mem_toList_iff /-
theorem mem_toList_iff {y : α} : y ∈ toList p x ↔ SameCycle p x y ∧ x ∈ p.support :=
by
simp only [to_list, mem_range, mem_map]
@@ -275,7 +336,9 @@ theorem mem_toList_iff {y : α} : y ∈ toList p x ↔ SameCycle p x y ∧ x ∈
· rintro ⟨h, hx⟩
simpa using h.exists_pow_eq_of_mem_support hx
#align equiv.perm.mem_to_list_iff Equiv.Perm.mem_toList_iff
+-/
+#print Equiv.Perm.nodup_toList /-
theorem nodup_toList (p : Perm α) (x : α) : Nodup (toList p x) :=
by
by_cases hx : p x = x
@@ -310,7 +373,9 @@ theorem nodup_toList (p : Perm α) (x : α) : Nodup (toList p x) :=
rw [← mul_apply, (Commute.pow_pow_self _ _ _).Eq, mul_apply, h, ← mul_apply, ← mul_apply,
(Commute.pow_pow_self _ _ _).Eq]
#align equiv.perm.nodup_to_list Equiv.Perm.nodup_toList
+-/
+#print Equiv.Perm.next_toList_eq_apply /-
theorem next_toList_eq_apply (p : Perm α) (x y : α) (hy : y ∈ toList p x) :
next (toList p x) y hy = p y := by
rw [mem_to_list_iff] at hy
@@ -321,7 +386,9 @@ theorem next_toList_eq_apply (p : Perm α) (x y : α) (hy : y ∈ toList p x) :
length_to_list, pow_apply_eq_pow_mod_order_of_cycle_of_apply p (k + 1), is_cycle.order_of]
exact is_cycle_cycle_of _ (mem_support.mp hy.right)
#align equiv.perm.next_to_list_eq_apply Equiv.Perm.next_toList_eq_apply
+-/
+#print Equiv.Perm.toList_pow_apply_eq_rotate /-
theorem toList_pow_apply_eq_rotate (p : Perm α) (x : α) (k : ℕ) :
p.toList ((p ^ k) x) = (p.toList x).rotate k :=
by
@@ -331,7 +398,9 @@ theorem toList_pow_apply_eq_rotate (p : Perm α) (x : α) (k : ℕ) :
rw [nth_le_to_list, nth_le_rotate, nth_le_to_list, length_to_list,
pow_mod_card_support_cycle_of_self_apply, pow_add, mul_apply]
#align equiv.perm.to_list_pow_apply_eq_rotate Equiv.Perm.toList_pow_apply_eq_rotate
+-/
+#print Equiv.Perm.SameCycle.toList_isRotated /-
theorem SameCycle.toList_isRotated {f : Perm α} {x y : α} (h : SameCycle f x y) :
toList f x ~r toList f y := by
by_cases hx : x ∈ f.support
@@ -343,20 +412,33 @@ theorem SameCycle.toList_isRotated {f : Perm α} {x y : α} (h : SameCycle f x y
· rw [to_list_eq_nil_iff.mpr hx, is_rotated_nil_iff', eq_comm, to_list_eq_nil_iff]
rwa [← h.mem_support_iff]
#align equiv.perm.same_cycle.to_list_is_rotated Equiv.Perm.SameCycle.toList_isRotated
+-/
+#print Equiv.Perm.pow_apply_mem_toList_iff_mem_support /-
theorem pow_apply_mem_toList_iff_mem_support {n : ℕ} : (p ^ n) x ∈ p.toList x ↔ x ∈ p.support :=
by
rw [mem_to_list_iff, and_iff_right_iff_imp]
refine' fun _ => same_cycle.symm _
rw [same_cycle_pow_left]
#align equiv.perm.pow_apply_mem_to_list_iff_mem_support Equiv.Perm.pow_apply_mem_toList_iff_mem_support
+-/
+#print Equiv.Perm.toList_formPerm_nil /-
theorem toList_formPerm_nil (x : α) : toList (formPerm ([] : List α)) x = [] := by simp
#align equiv.perm.to_list_form_perm_nil Equiv.Perm.toList_formPerm_nil
+-/
+#print Equiv.Perm.toList_formPerm_singleton /-
theorem toList_formPerm_singleton (x y : α) : toList (formPerm [x]) y = [] := by simp
#align equiv.perm.to_list_form_perm_singleton Equiv.Perm.toList_formPerm_singleton
+-/
+/- warning: equiv.perm.to_list_form_perm_nontrivial -> Equiv.Perm.toList_formPerm_nontrivial is a dubious translation:
+lean 3 declaration is
+ forall {α : Type.{u1}} [_inst_1 : Fintype.{u1} α] [_inst_2 : DecidableEq.{succ u1} α] (l : List.{u1} α) (hl : LE.le.{0} Nat Nat.hasLe (OfNat.ofNat.{0} Nat 2 (OfNat.mk.{0} Nat 2 (bit0.{0} Nat Nat.hasAdd (One.one.{0} Nat Nat.hasOne)))) (List.length.{u1} α l)), (List.Nodup.{u1} α l) -> (Eq.{succ u1} (List.{u1} α) (Equiv.Perm.toList.{u1} α _inst_1 (fun (a : α) (b : α) => _inst_2 a b) (List.formPerm.{u1} α (fun (a : α) (b : α) => _inst_2 a b) l) (List.nthLe.{u1} α l (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero))) (LT.lt.trans_le.{0} Nat (PartialOrder.toPreorder.{0} Nat (OrderedCancelAddCommMonoid.toPartialOrder.{0} Nat (StrictOrderedSemiring.toOrderedCancelAddCommMonoid.{0} Nat Nat.strictOrderedSemiring))) (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat (AddZeroClass.toHasZero.{0} Nat (AddMonoid.toAddZeroClass.{0} Nat (AddMonoidWithOne.toAddMonoid.{0} Nat (AddCommMonoidWithOne.toAddMonoidWithOne.{0} Nat (NonAssocSemiring.toAddCommMonoidWithOne.{0} Nat (Semiring.toNonAssocSemiring.{0} Nat Nat.semiring))))))))) (OfNat.ofNat.{0} Nat 2 (OfNat.mk.{0} Nat 2 (bit0.{0} Nat (AddZeroClass.toHasAdd.{0} Nat (AddMonoid.toAddZeroClass.{0} Nat (AddMonoidWithOne.toAddMonoid.{0} Nat (AddCommMonoidWithOne.toAddMonoidWithOne.{0} Nat (NonAssocSemiring.toAddCommMonoidWithOne.{0} Nat (Semiring.toNonAssocSemiring.{0} Nat Nat.semiring)))))) (One.one.{0} Nat (AddMonoidWithOne.toOne.{0} Nat (AddCommMonoidWithOne.toAddMonoidWithOne.{0} Nat (NonAssocSemiring.toAddCommMonoidWithOne.{0} Nat (Semiring.toNonAssocSemiring.{0} Nat Nat.semiring)))))))) (List.length.{u1} α l) (zero_lt_two.{0} Nat (AddCommMonoidWithOne.toAddMonoidWithOne.{0} Nat (NonAssocSemiring.toAddCommMonoidWithOne.{0} Nat (Semiring.toNonAssocSemiring.{0} Nat Nat.semiring))) (OrderedCancelAddCommMonoid.toPartialOrder.{0} Nat (StrictOrderedSemiring.toOrderedCancelAddCommMonoid.{0} Nat Nat.strictOrderedSemiring)) (OrderedSemiring.zeroLEOneClass.{0} Nat Nat.orderedSemiring) (NeZero.one.{0} Nat (NonAssocSemiring.toMulZeroOneClass.{0} Nat (Semiring.toNonAssocSemiring.{0} Nat Nat.semiring)) Nat.nontrivial) (OrderedAddCommMonoid.to_covariantClass_left.{0} Nat (OrderedSemiring.toOrderedAddCommMonoid.{0} Nat Nat.orderedSemiring))) hl))) l)
+but is expected to have type
+ forall {α : Type.{u1}} [_inst_1 : Fintype.{u1} α] [_inst_2 : DecidableEq.{succ u1} α] (l : List.{u1} α) (hl : LE.le.{0} Nat instLENat (OfNat.ofNat.{0} Nat 2 (instOfNatNat 2)) (List.length.{u1} α l)), (List.Nodup.{u1} α l) -> (Eq.{succ u1} (List.{u1} α) (Equiv.Perm.toList.{u1} α _inst_1 (fun (a : α) (b : α) => _inst_2 a b) (List.formPerm.{u1} α (fun (a : α) (b : α) => _inst_2 a b) l) (List.nthLe.{u1} α l (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0)) (LT.lt.trans_le.{0} Nat (PartialOrder.toPreorder.{0} Nat (StrictOrderedSemiring.toPartialOrder.{0} Nat Nat.strictOrderedSemiring)) (OfNat.ofNat.{0} Nat 0 (Zero.toOfNat0.{0} Nat (AddMonoid.toZero.{0} Nat (AddMonoidWithOne.toAddMonoid.{0} Nat (AddCommMonoidWithOne.toAddMonoidWithOne.{0} Nat (NonAssocSemiring.toAddCommMonoidWithOne.{0} Nat (Semiring.toNonAssocSemiring.{0} Nat Nat.semiring))))))) (OfNat.ofNat.{0} Nat 2 (instOfNat.{0} Nat 2 (AddMonoidWithOne.toNatCast.{0} Nat (AddCommMonoidWithOne.toAddMonoidWithOne.{0} Nat (NonAssocSemiring.toAddCommMonoidWithOne.{0} Nat (Semiring.toNonAssocSemiring.{0} Nat Nat.semiring)))) (instAtLeastTwoHAddNatInstHAddInstAddNatOfNat (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0))))) (List.length.{u1} α l) (zero_lt_two.{0} Nat (AddCommMonoidWithOne.toAddMonoidWithOne.{0} Nat (NonAssocSemiring.toAddCommMonoidWithOne.{0} Nat (Semiring.toNonAssocSemiring.{0} Nat Nat.semiring))) (StrictOrderedSemiring.toPartialOrder.{0} Nat Nat.strictOrderedSemiring) (OrderedSemiring.zeroLEOneClass.{0} Nat Nat.orderedSemiring) (NeZero.succ Nat.zero) (OrderedAddCommMonoid.to_covariantClass_left.{0} Nat (OrderedSemiring.toOrderedAddCommMonoid.{0} Nat Nat.orderedSemiring))) hl))) l)
+Case conversion may be inaccurate. Consider using '#align equiv.perm.to_list_form_perm_nontrivial Equiv.Perm.toList_formPerm_nontrivialₓ'. -/
theorem toList_formPerm_nontrivial (l : List α) (hl : 2 ≤ l.length) (hn : Nodup l) :
toList (formPerm l) (l.nthLe 0 (zero_lt_two.trans_le hl)) = l :=
by
@@ -372,6 +454,7 @@ theorem toList_formPerm_nontrivial (l : List α) (hl : 2 ≤ l.length) (hn : Nod
· simpa [hs] using nth_le_mem _ _ _
#align equiv.perm.to_list_form_perm_nontrivial Equiv.Perm.toList_formPerm_nontrivial
+#print Equiv.Perm.toList_formPerm_isRotated_self /-
theorem toList_formPerm_isRotated_self (l : List α) (hl : 2 ≤ l.length) (hn : Nodup l) (x : α)
(hx : x ∈ l) : toList (formPerm l) x ~r l :=
by
@@ -385,7 +468,9 @@ theorem toList_formPerm_isRotated_self (l : List α) (hl : 2 ≤ l.length) (hn :
· simpa using hl
· simpa using hn
#align equiv.perm.to_list_form_perm_is_rotated_self Equiv.Perm.toList_formPerm_isRotated_self
+-/
+#print Equiv.Perm.formPerm_toList /-
theorem formPerm_toList (f : Perm α) (x : α) : formPerm (toList f x) = f.cycleOf x :=
by
by_cases hx : f x = x
@@ -402,7 +487,9 @@ theorem formPerm_toList (f : Perm α) (x : α) : formPerm (toList f x) = f.cycle
· rw [cycle_of_apply_of_not_same_cycle hy, form_perm_apply_of_not_mem]
simp [mem_to_list_iff, hy]
#align equiv.perm.form_perm_to_list Equiv.Perm.formPerm_toList
+-/
+#print Equiv.Perm.toCycle /-
/-- Given a cyclic `f : perm α`, generate the `cycle α` in the order
of application of `f`. Implemented by finding an element `x : α`
in the support of `f` in `finset.univ`, and iterating on using
@@ -418,7 +505,9 @@ def toCycle (f : Perm α) (hf : IsCycle f) : Cycle α :=
· have hc : same_cycle f x y := is_cycle.same_cycle hf hx hy
exact Quotient.sound' hc.to_list_is_rotated)
#align equiv.perm.to_cycle Equiv.Perm.toCycle
+-/
+#print Equiv.Perm.toCycle_eq_toList /-
theorem toCycle_eq_toList (f : Perm α) (hf : IsCycle f) (x : α) (hx : f x ≠ x) :
toCycle f hf = toList f x :=
by
@@ -426,19 +515,25 @@ theorem toCycle_eq_toList (f : Perm α) (hf : IsCycle f) (x : α) (hx : f x ≠
rw [to_cycle, key]
simp [hx]
#align equiv.perm.to_cycle_eq_to_list Equiv.Perm.toCycle_eq_toList
+-/
+#print Equiv.Perm.nodup_toCycle /-
theorem nodup_toCycle (f : Perm α) (hf : IsCycle f) : (toCycle f hf).Nodup :=
by
obtain ⟨x, hx, -⟩ := id hf
simpa [to_cycle_eq_to_list f hf x hx] using nodup_to_list _ _
#align equiv.perm.nodup_to_cycle Equiv.Perm.nodup_toCycle
+-/
+#print Equiv.Perm.nontrivial_toCycle /-
theorem nontrivial_toCycle (f : Perm α) (hf : IsCycle f) : (toCycle f hf).Nontrivial :=
by
obtain ⟨x, hx, -⟩ := id hf
simp [to_cycle_eq_to_list f hf x hx, hx, Cycle.nontrivial_coe_nodup_iff (nodup_to_list _ _)]
#align equiv.perm.nontrivial_to_cycle Equiv.Perm.nontrivial_toCycle
+-/
+#print Equiv.Perm.isoCycle /-
/-- Any cyclic `f : perm α` is isomorphic to the nontrivial `cycle α`
that corresponds to repeated application of `f`.
The forward direction is implemented by `equiv.perm.to_cycle`.
@@ -465,6 +560,7 @@ def isoCycle : { f : Perm α // IsCycle f } ≃ { s : Cycle α // s.Nodup ∧ s.
· rintro _ rfl
simpa [Nat.succ_le_succ_iff] using hl
#align equiv.perm.iso_cycle Equiv.Perm.isoCycle
+-/
end Fintype
@@ -472,6 +568,7 @@ section Finite
variable [Finite α] [DecidableEq α]
+#print Equiv.Perm.IsCycle.existsUnique_cycle /-
theorem IsCycle.existsUnique_cycle {f : Perm α} (hf : IsCycle f) :
∃! s : Cycle α, ∃ h : s.Nodup, s.formPerm h = f :=
by
@@ -490,7 +587,9 @@ theorem IsCycle.existsUnique_cycle {f : Perm α} (hf : IsCycle f) :
refine' support_form_perm_le l _
simpa using hx
#align equiv.perm.is_cycle.exists_unique_cycle Equiv.Perm.IsCycle.existsUnique_cycle
+-/
+#print Equiv.Perm.IsCycle.existsUnique_cycle_subtype /-
theorem IsCycle.existsUnique_cycle_subtype {f : Perm α} (hf : IsCycle f) :
∃! s : { s : Cycle α // s.Nodup }, (s : Cycle α).formPerm s.Prop = f :=
by
@@ -499,7 +598,9 @@ theorem IsCycle.existsUnique_cycle_subtype {f : Perm α} (hf : IsCycle f) :
rintro ⟨t, ht⟩ ht'
simpa using hs' _ ⟨ht, ht'⟩
#align equiv.perm.is_cycle.exists_unique_cycle_subtype Equiv.Perm.IsCycle.existsUnique_cycle_subtype
+-/
+#print Equiv.Perm.IsCycle.existsUnique_cycle_nontrivial_subtype /-
theorem IsCycle.existsUnique_cycle_nontrivial_subtype {f : Perm α} (hf : IsCycle f) :
∃! s : { s : Cycle α // s.Nodup ∧ s.Nontrivial }, (s : Cycle α).formPerm s.Prop.left = f :=
by
@@ -514,11 +615,13 @@ theorem IsCycle.existsUnique_cycle_nontrivial_subtype {f : Perm α} (hf : IsCycl
· rintro ⟨t, ht, ht'⟩ ht''
simpa using hs' ⟨t, ht⟩ ht''
#align equiv.perm.is_cycle.exists_unique_cycle_nontrivial_subtype Equiv.Perm.IsCycle.existsUnique_cycle_nontrivial_subtype
+-/
end Finite
variable [Fintype α] [DecidableEq α]
+#print Equiv.Perm.isoCycle' /-
/-- Any cyclic `f : perm α` is isomorphic to the nontrivial `cycle α`
that corresponds to repeated application of `f`.
The forward direction is implemented by finding this `cycle α` using `fintype.choose`.
@@ -537,11 +640,13 @@ def isoCycle' : { f : Perm α // IsCycle f } ≃ { s : Cycle α // s.Nodup ∧ s
simp [Cycle.formPerm_eq_formPerm_iff, iff_not_comm.mp hs.nontrivial_iff,
iff_not_comm.mp hs'.nontrivial_iff, ht]
#align equiv.perm.iso_cycle' Equiv.Perm.isoCycle'
+-/
-- mathport name: «exprc[ ,]»
notation3"c["(l", "* => foldr (h t => List.cons h t) List.nil)"]" =>
Cycle.formPerm (↑l) (Cycle.nodup_coe_iff.mpr (by decide))
+#print Equiv.Perm.repr_perm /-
unsafe instance repr_perm [Repr α] : Repr (Perm α) :=
⟨fun f =>
repr
@@ -550,7 +655,8 @@ unsafe instance repr_perm [Repr α] : Repr (Perm α) :=
Perm.cycleFactorsFinset
f).val
fun g hg => (mem_cycleFactorsFinset_iff.mp (Finset.mem_def.mpr hg)).left)⟩
-#align equiv.perm.repr_perm equiv.perm.repr_perm
+#align equiv.perm.repr_perm Equiv.Perm.repr_perm
+-/
end Equiv.Perm
mathlib commit https://github.com/leanprover-community/mathlib/commit/da3fc4a33ff6bc75f077f691dc94c217b8d41559
@@ -172,7 +172,7 @@ theorem isCycle_formPerm (s : Cycle α) (h : Nodup s) (hn : Nontrivial s) : IsCy
#align cycle.is_cycle_form_perm Cycle.isCycle_formPerm
theorem support_formPerm [Fintype α] (s : Cycle α) (h : Nodup s) (hn : Nontrivial s) :
- Support (formPerm s h) = s.toFinset :=
+ support (formPerm s h) = s.toFinset :=
by
induction s using Quot.inductionOn
refine' support_form_perm_of_nodup s h _
@@ -224,7 +224,7 @@ variable [Fintype α] [DecidableEq α] (p : Equiv.Perm α) (x : α)
until looping. That means when `f x = x`, `to_list f x = []`.
-/
def toList : List α :=
- (List.range (cycleOf p x).Support.card).map fun k => (p ^ k) x
+ (List.range (cycleOf p x).support.card).map fun k => (p ^ k) x
#align equiv.perm.to_list Equiv.Perm.toList
@[simp]
@@ -232,11 +232,11 @@ theorem toList_one : toList (1 : Perm α) x = [] := by simp [to_list, cycle_of_o
#align equiv.perm.to_list_one Equiv.Perm.toList_one
@[simp]
-theorem toList_eq_nil_iff {p : Perm α} {x} : toList p x = [] ↔ x ∉ p.Support := by simp [to_list]
+theorem toList_eq_nil_iff {p : Perm α} {x} : toList p x = [] ↔ x ∉ p.support := by simp [to_list]
#align equiv.perm.to_list_eq_nil_iff Equiv.Perm.toList_eq_nil_iff
@[simp]
-theorem length_toList : length (toList p x) = (cycleOf p x).Support.card := by simp [to_list]
+theorem length_toList : length (toList p x) = (cycleOf p x).support.card := by simp [to_list]
#align equiv.perm.length_to_list Equiv.Perm.length_toList
theorem toList_ne_singleton (y : α) : toList p x ≠ [y] :=
@@ -246,10 +246,10 @@ theorem toList_ne_singleton (y : α) : toList p x ≠ [y] :=
#align equiv.perm.to_list_ne_singleton Equiv.Perm.toList_ne_singleton
theorem two_le_length_toList_iff_mem_support {p : Perm α} {x : α} :
- 2 ≤ length (toList p x) ↔ x ∈ p.Support := by simp
+ 2 ≤ length (toList p x) ↔ x ∈ p.support := by simp
#align equiv.perm.two_le_length_to_list_iff_mem_support Equiv.Perm.two_le_length_toList_iff_mem_support
-theorem length_toList_pos_of_mem_support (h : x ∈ p.Support) : 0 < length (toList p x) :=
+theorem length_toList_pos_of_mem_support (h : x ∈ p.support) : 0 < length (toList p x) :=
zero_lt_two.trans_le (two_le_length_toList_iff_mem_support.mpr h)
#align equiv.perm.length_to_list_pos_of_mem_support Equiv.Perm.length_toList_pos_of_mem_support
@@ -257,13 +257,13 @@ theorem nthLe_toList (n : ℕ) (hn : n < length (toList p x)) : nthLe (toList p
by simp [to_list]
#align equiv.perm.nth_le_to_list Equiv.Perm.nthLe_toList
-theorem toList_nthLe_zero (h : x ∈ p.Support) :
+theorem toList_nthLe_zero (h : x ∈ p.support) :
(toList p x).nthLe 0 (length_toList_pos_of_mem_support _ _ h) = x := by simp [to_list]
#align equiv.perm.to_list_nth_le_zero Equiv.Perm.toList_nthLe_zero
variable {p} {x}
-theorem mem_toList_iff {y : α} : y ∈ toList p x ↔ SameCycle p x y ∧ x ∈ p.Support :=
+theorem mem_toList_iff {y : α} : y ∈ toList p x ↔ SameCycle p x y ∧ x ∈ p.support :=
by
simp only [to_list, mem_range, mem_map]
constructor
@@ -344,7 +344,7 @@ theorem SameCycle.toList_isRotated {f : Perm α} {x y : α} (h : SameCycle f x y
rwa [← h.mem_support_iff]
#align equiv.perm.same_cycle.to_list_is_rotated Equiv.Perm.SameCycle.toList_isRotated
-theorem pow_apply_mem_toList_iff_mem_support {n : ℕ} : (p ^ n) x ∈ p.toList x ↔ x ∈ p.Support :=
+theorem pow_apply_mem_toList_iff_mem_support {n : ℕ} : (p ^ n) x ∈ p.toList x ↔ x ∈ p.support :=
by
rw [mem_to_list_iff, and_iff_right_iff_imp]
refine' fun _ => same_cycle.symm _
mathlib commit https://github.com/leanprover-community/mathlib/commit/bd9851ca476957ea4549eb19b40e7b5ade9428cc
@@ -65,7 +65,7 @@ theorem formPerm_disjoint_iff (hl : Nodup l) (hl' : Nodup l') (hn : 2 ≤ l.leng
omega
· intro h x
by_cases hx : x ∈ l
- by_cases hx' : x ∈ l'
+ on_goal 1 => by_cases hx' : x ∈ l'
· exact (h hx hx').elim
all_goals have := formPerm_eq_self_of_not_mem _ _ ‹_›; tauto
#align list.form_perm_disjoint_iff List.formPerm_disjoint_iff
@@ -135,8 +135,8 @@ where each element in the list is permuted to the next one, defined as `formPerm
def formPerm : ∀ s : Cycle α, Nodup s → Equiv.Perm α :=
fun s => Quotient.hrecOn s (fun l _ => List.formPerm l) fun l₁ l₂ (h : l₁ ~r l₂) => by
apply Function.hfunext
- ext
- · exact h.nodup_iff
+ · ext
+ exact h.nodup_iff
· intro h₁ h₂ _
exact heq_of_eq (formPerm_eq_of_isRotated h₁ h)
#align cycle.form_perm Cycle.formPerm
mem_or_mem_of_zipWith_swap_prod_ne
, a version of zipWith_swap_prod_support'
without any Finset
s; formPerm
;formPerm_reverse
doesn't need Nodup
@@ -185,7 +185,7 @@ theorem formPerm_apply_mem_eq_next (s : Cycle α) (h : Nodup s) (x : α) (hx : x
nonrec theorem formPerm_reverse (s : Cycle α) (h : Nodup s) :
formPerm s.reverse (nodup_reverse_iff.mpr h) = (formPerm s h)⁻¹ := by
induction s using Quot.inductionOn
- simpa using formPerm_reverse _ h
+ simpa using formPerm_reverse _
#align cycle.form_perm_reverse Cycle.formPerm_reverse
nonrec theorem formPerm_eq_formPerm_iff {α : Type*} [DecidableEq α] {s s' : Cycle α} {hs : s.Nodup}
@@ -70,7 +70,6 @@ theorem formPerm_disjoint_iff (hl : Nodup l) (hl' : Nodup l') (hn : 2 ≤ l.leng
all_goals have := formPerm_eq_self_of_not_mem _ _ ‹_›; tauto
#align list.form_perm_disjoint_iff List.formPerm_disjoint_iff
-set_option linter.deprecated false in
theorem isCycle_formPerm (hl : Nodup l) (hn : 2 ≤ l.length) : IsCycle (formPerm l) := by
cases' l with x l
· set_option tactic.skipAssignedInstances false in norm_num at hn
@@ -81,9 +80,10 @@ theorem isCycle_formPerm (hl : Nodup l) (hn : 2 ≤ l.length) : IsCycle (formPer
· rwa [formPerm_apply_mem_ne_self_iff _ hl _ (mem_cons_self _ _)]
· intro w hw
have : w ∈ x::y::l := mem_of_formPerm_ne_self _ _ hw
- obtain ⟨k, hk, rfl⟩ := nthLe_of_mem this
+ obtain ⟨k, hk⟩ := get_of_mem this
use k
- simp only [zpow_natCast, formPerm_pow_apply_head _ _ hl k, Nat.mod_eq_of_lt hk]
+ rw [← hk]
+ simp only [zpow_natCast, formPerm_pow_apply_head _ _ hl k, Nat.mod_eq_of_lt k.isLt]
#align list.is_cycle_form_perm List.isCycle_formPerm
theorem pairwise_sameCycle_formPerm (hl : Nodup l) (hn : 2 ≤ l.length) :
@@ -117,11 +117,10 @@ theorem cycleType_formPerm (hl : Nodup l) (hn : 2 ≤ l.length) :
· simp
#align list.cycle_type_form_perm List.cycleType_formPerm
-set_option linter.deprecated false in
theorem formPerm_apply_mem_eq_next (hl : Nodup l) (x : α) (hx : x ∈ l) :
formPerm l x = next l x hx := by
- obtain ⟨k, hk, rfl⟩ := nthLe_of_mem hx
- rw [next_nthLe _ hl, formPerm_apply_nthLe _ hl]
+ obtain ⟨k, rfl⟩ := get_of_mem hx
+ rw [next_get _ hl, formPerm_apply_get _ hl]
#align list.form_perm_apply_mem_eq_next List.formPerm_apply_mem_eq_next
end List
@@ -346,9 +345,8 @@ theorem toList_formPerm_nil (x : α) : toList (formPerm ([] : List α)) x = [] :
theorem toList_formPerm_singleton (x y : α) : toList (formPerm [x]) y = [] := by simp
#align equiv.perm.to_list_form_perm_singleton Equiv.Perm.toList_formPerm_singleton
-set_option linter.deprecated false in
theorem toList_formPerm_nontrivial (l : List α) (hl : 2 ≤ l.length) (hn : Nodup l) :
- toList (formPerm l) (l.nthLe 0 (zero_lt_two.trans_le hl)) = l := by
+ toList (formPerm l) (l.get ⟨0, (zero_lt_two.trans_le hl)⟩) = l := by
have hc : l.formPerm.IsCycle := List.isCycle_formPerm hn hl
have hs : l.formPerm.support = l.toFinset := by
refine' support_formPerm_of_nodup _ hn _
@@ -356,9 +354,8 @@ theorem toList_formPerm_nontrivial (l : List α) (hl : 2 ≤ l.length) (hn : Nod
simp [Nat.succ_le_succ_iff] at hl
rw [toList, hc.cycleOf_eq (mem_support.mp _), hs, card_toFinset, dedup_eq_self.mpr hn]
· refine' ext_get (by simp) fun k hk hk' => _
- simp only [Nat.zero_eq, get_map, get_range, formPerm_pow_apply_nthLe _ hn, zero_add,
+ simp only [Nat.zero_eq, get_map, get_range, formPerm_pow_apply_get _ hn, zero_add,
Nat.mod_eq_of_lt hk']
- rw [nthLe_eq]
· simpa [hs] using get_mem _ _ _
#align equiv.perm.to_list_form_perm_nontrivial Equiv.Perm.toList_formPerm_nontrivial
These are changes from #11997, the latest adaptation PR for nightly-2024-04-07, which can be made directly on master.
Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Ruben Van de Velde <65514131+Ruben-VandeVelde@users.noreply.github.com>
@@ -274,7 +274,7 @@ theorem nodup_toList (p : Perm α) (x : α) : Nodup (toList p x) := by
rw [nodup_iff_nthLe_inj]
rintro n m hn hm
rw [length_toList, ← hc.orderOf] at hm hn
- rw [← cycleOf_apply_self, ← Ne.def, ← mem_support] at hx
+ rw [← cycleOf_apply_self, ← Ne, ← mem_support] at hx
rw [nthLe_toList, nthLe_toList, ← cycleOf_pow_apply_self p x n, ←
cycleOf_pow_apply_self p x m]
cases' n with n <;> cases' m with m
@@ -325,7 +325,7 @@ theorem SameCycle.toList_isRotated {f : Perm α} {x y : α} (h : SameCycle f x y
toList f x ~r toList f y := by
by_cases hx : x ∈ f.support
· obtain ⟨_ | k, _, hy⟩ := h.exists_pow_eq_of_mem_support hx
- · simp only [coe_one, id.def, pow_zero, Nat.zero_eq] at hy
+ · simp only [coe_one, id, pow_zero, Nat.zero_eq] at hy
-- Porting note: added `IsRotated.refl`
simp [hy, IsRotated.refl]
use k.succ
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
.@@ -306,7 +306,7 @@ theorem next_toList_eq_apply (p : Perm α) (x y : α) (hy : y ∈ toList p x) :
obtain ⟨k, hk, hk'⟩ := hy.left.exists_pow_eq_of_mem_support hy.right
rw [← nthLe_toList p x k (by simpa using hk)] at hk'
simp_rw [← hk']
- rw [next_nthLe _ (nodup_toList _ _), nthLe_toList, nthLe_toList, ← mul_apply, ← pow_succ,
+ rw [next_nthLe _ (nodup_toList _ _), nthLe_toList, nthLe_toList, ← mul_apply, ← pow_succ',
length_toList, ← pow_mod_orderOf_cycleOf_apply p (k + 1), IsCycle.orderOf]
exact isCycle_cycleOf _ (mem_support.mp hy.right)
#align equiv.perm.next_to_list_eq_apply Equiv.Perm.next_toList_eq_apply
@@ -383,7 +383,7 @@ theorem formPerm_toList (f : Perm α) (x : α) : formPerm (toList f x) = f.cycle
by_cases hy : SameCycle f x y
· obtain ⟨k, _, rfl⟩ := hy.exists_pow_eq_of_mem_support (mem_support.mpr hx)
rw [cycleOf_apply_apply_pow_self, List.formPerm_apply_mem_eq_next (nodup_toList f x),
- next_toList_eq_apply, pow_succ, mul_apply]
+ next_toList_eq_apply, pow_succ', mul_apply]
rw [mem_toList_iff]
exact ⟨⟨k, rfl⟩, mem_support.mpr hx⟩
· rw [cycleOf_apply_of_not_sameCycle hy, formPerm_apply_of_not_mem]
zpow_coe_nat
to zpow_natCast
(#11528)
... and add a deprecated alias for the old name. This is mostly just me discovering the power of F2
@@ -83,7 +83,7 @@ theorem isCycle_formPerm (hl : Nodup l) (hn : 2 ≤ l.length) : IsCycle (formPer
have : w ∈ x::y::l := mem_of_formPerm_ne_self _ _ hw
obtain ⟨k, hk, rfl⟩ := nthLe_of_mem this
use k
- simp only [zpow_coe_nat, formPerm_pow_apply_head _ _ hl k, Nat.mod_eq_of_lt hk]
+ simp only [zpow_natCast, formPerm_pow_apply_head _ _ hl k, Nat.mod_eq_of_lt hk]
#align list.is_cycle_form_perm List.isCycle_formPerm
theorem pairwise_sameCycle_formPerm (hl : Nodup l) (hn : 2 ≤ l.length) :
This is a very large PR, but it has been reviewed piecemeal already in PRs to the bump/v4.7.0
branch as we update to intermediate nightlies.
Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Kyle Miller <kmill31415@gmail.com> Co-authored-by: damiano <adomani@gmail.com>
@@ -73,9 +73,9 @@ theorem formPerm_disjoint_iff (hl : Nodup l) (hl' : Nodup l') (hn : 2 ≤ l.leng
set_option linter.deprecated false in
theorem isCycle_formPerm (hl : Nodup l) (hn : 2 ≤ l.length) : IsCycle (formPerm l) := by
cases' l with x l
- · norm_num at hn
+ · set_option tactic.skipAssignedInstances false in norm_num at hn
induction' l with y l generalizing x
- · norm_num at hn
+ · set_option tactic.skipAssignedInstances false in norm_num at hn
· use x
constructor
· rwa [formPerm_apply_mem_ne_self_iff _ hl _ (mem_cons_self _ _)]
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.
@@ -62,7 +62,7 @@ theorem formPerm_disjoint_iff (hl : Nodup l) (hl' : Nodup l') (hn : 2 ≤ l.leng
· rintro h x hx hx'
specialize h x
rw [formPerm_apply_mem_eq_self_iff _ hl _ hx, formPerm_apply_mem_eq_self_iff _ hl' _ hx'] at h
- rcases h with (hl | hl') <;> linarith
+ omega
· intro h x
by_cases hx : x ∈ l
by_cases hx' : x ∈ l'
zpow_ofNat
and ofNat_zsmul
(#10969)
Previously these were syntactically identical to the corresponding zpow_coe_nat
and coe_nat_zsmul
lemmas, now they are about OfNat.ofNat
.
Unfortunately, almost every call site uses the ofNat
name to refer to Nat.cast
, so the downstream proofs had to be adjusted too.
@@ -83,7 +83,7 @@ theorem isCycle_formPerm (hl : Nodup l) (hn : 2 ≤ l.length) : IsCycle (formPer
have : w ∈ x::y::l := mem_of_formPerm_ne_self _ _ hw
obtain ⟨k, hk, rfl⟩ := nthLe_of_mem this
use k
- simp only [zpow_ofNat, formPerm_pow_apply_head _ _ hl k, Nat.mod_eq_of_lt hk]
+ simp only [zpow_coe_nat, formPerm_pow_apply_head _ _ hl k, Nat.mod_eq_of_lt hk]
#align list.is_cycle_form_perm List.isCycle_formPerm
theorem pairwise_sameCycle_formPerm (hl : Nodup l) (hn : 2 ≤ l.length) :
∃ x ∈ s, _
instead of ∃ (x) (_ : x ∈ s), _
(#9184)
Search for [∀∃].*(_
and manually replace some occurrences with more readable versions.
In case of ∀
, the new expressions are defeq to the old ones.
In case of ∃
, they differ by exists_prop
.
In some rare cases, golf proofs that needed fixing.
@@ -133,7 +133,7 @@ variable [DecidableEq α] (s s' : Cycle α)
/-- A cycle `s : Cycle α`, given `Nodup s` can be interpreted as an `Equiv.Perm α`
where each element in the list is permuted to the next one, defined as `formPerm`.
-/
-def formPerm : ∀ (s : Cycle α) (_ : Nodup s), Equiv.Perm α :=
+def formPerm : ∀ s : Cycle α, Nodup s → Equiv.Perm α :=
fun s => Quotient.hrecOn s (fun l _ => List.formPerm l) fun l₁ l₂ (h : l₁ ~r l₂) => by
apply Function.hfunext
ext
@@ -307,7 +307,7 @@ theorem next_toList_eq_apply (p : Perm α) (x y : α) (hy : y ∈ toList p x) :
rw [← nthLe_toList p x k (by simpa using hk)] at hk'
simp_rw [← hk']
rw [next_nthLe _ (nodup_toList _ _), nthLe_toList, nthLe_toList, ← mul_apply, ← pow_succ,
- length_toList, ←pow_mod_orderOf_cycleOf_apply p (k + 1), IsCycle.orderOf]
+ length_toList, ← pow_mod_orderOf_cycleOf_apply p (k + 1), IsCycle.orderOf]
exact isCycle_cycleOf _ (mem_support.mp hy.right)
#align equiv.perm.next_to_list_eq_apply Equiv.Perm.next_toList_eq_apply
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.@@ -307,7 +307,7 @@ theorem next_toList_eq_apply (p : Perm α) (x y : α) (hy : y ∈ toList p x) :
rw [← nthLe_toList p x k (by simpa using hk)] at hk'
simp_rw [← hk']
rw [next_nthLe _ (nodup_toList _ _), nthLe_toList, nthLe_toList, ← mul_apply, ← pow_succ,
- length_toList, pow_apply_eq_pow_mod_orderOf_cycleOf_apply p (k + 1), IsCycle.orderOf]
+ length_toList, ←pow_mod_orderOf_cycleOf_apply p (k + 1), IsCycle.orderOf]
exact isCycle_cycleOf _ (mem_support.mp hy.right)
#align equiv.perm.next_to_list_eq_apply Equiv.Perm.next_toList_eq_apply
Removes nonterminal simps on lines looking like simp [...]
@@ -356,7 +356,8 @@ theorem toList_formPerm_nontrivial (l : List α) (hl : 2 ≤ l.length) (hn : Nod
simp [Nat.succ_le_succ_iff] at hl
rw [toList, hc.cycleOf_eq (mem_support.mp _), hs, card_toFinset, dedup_eq_self.mpr hn]
· refine' ext_get (by simp) fun k hk hk' => _
- simp [formPerm_pow_apply_nthLe _ hn, Nat.mod_eq_of_lt hk']
+ simp only [Nat.zero_eq, get_map, get_range, formPerm_pow_apply_nthLe _ hn, zero_add,
+ Nat.mod_eq_of_lt hk']
rw [nthLe_eq]
· simpa [hs] using get_mem _ _ _
#align equiv.perm.to_list_form_perm_nontrivial Equiv.Perm.toList_formPerm_nontrivial
@@ -517,8 +517,8 @@ def isoCycle' : { f : Perm α // IsCycle f } ≃ { s : Cycle α // s.Nodup ∧ s
right_inv := Fintype.leftInverse_bijInv _ }
#align equiv.perm.iso_cycle' Equiv.Perm.isoCycle'
-notation3 "c["(l", "* => foldr (h t => List.cons h t) List.nil)"]" =>
- Cycle.formPerm (Cycle.ofList l) (Iff.mpr Cycle.nodup_coe_iff _)
+notation3 (prettyPrint := false) "c["(l", "* => foldr (h t => List.cons h t) List.nil)"]" =>
+ Cycle.formPerm (Cycle.ofList l) (Iff.mpr Cycle.nodup_coe_iff (by decide))
unsafe instance repr_perm [Repr α] : Repr (Perm α) :=
⟨fun f _ => repr (Multiset.pmap (fun (g : Perm α) (hg : g.IsCycle) => isoCycle ⟨g, hg⟩)
Type _
and Sort _
(#6499)
We remove all possible occurences of Type _
and Sort _
in favor of Type*
and Sort*
.
This has nice performance benefits.
@@ -13,7 +13,7 @@ import Mathlib.GroupTheory.Perm.List
# Properties of cyclic permutations constructed from lists/cycles
-In the following, `{α : Type _} [Fintype α] [DecidableEq α]`.
+In the following, `{α : Type*} [Fintype α] [DecidableEq α]`.
## Main definitions
@@ -49,7 +49,7 @@ to show it takes a long time. TODO: is this because computing the cycle factors
open Equiv Equiv.Perm List
-variable {α : Type _}
+variable {α : Type*}
namespace List
@@ -189,7 +189,7 @@ nonrec theorem formPerm_reverse (s : Cycle α) (h : Nodup s) :
simpa using formPerm_reverse _ h
#align cycle.form_perm_reverse Cycle.formPerm_reverse
-nonrec theorem formPerm_eq_formPerm_iff {α : Type _} [DecidableEq α] {s s' : Cycle α} {hs : s.Nodup}
+nonrec theorem formPerm_eq_formPerm_iff {α : Type*} [DecidableEq α] {s s' : Cycle α} {hs : s.Nodup}
{hs' : s'.Nodup} :
s.formPerm hs = s'.formPerm hs' ↔ s = s' ∨ s.Subsingleton ∧ s'.Subsingleton := by
rw [Cycle.length_subsingleton_iff, Cycle.length_subsingleton_iff]
@@ -2,16 +2,13 @@
Copyright (c) 2021 Yakov Pechersky. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Yakov Pechersky
-
-! This file was ported from Lean 3 source module group_theory.perm.cycle.concrete
-! leanprover-community/mathlib commit 00638177efd1b2534fc5269363ebf42a7871df9a
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
-/
import Mathlib.Data.List.Cycle
import Mathlib.GroupTheory.Perm.Cycle.Type
import Mathlib.GroupTheory.Perm.List
+#align_import group_theory.perm.cycle.concrete from "leanprover-community/mathlib"@"00638177efd1b2534fc5269363ebf42a7871df9a"
+
/-!
# Properties of cyclic permutations constructed from lists/cycles
at
and goals (#5387)
Changes are of the form
some_tactic at h⊢
-> some_tactic at h ⊢
some_tactic at h
-> some_tactic at h
@@ -441,7 +441,7 @@ def isoCycle : { f : Perm α // IsCycle f } ≃ { s : Cycle α // s.Nodup ∧ s.
obtain ⟨x, -, -, hx, -⟩ := id ht
have hl : 2 ≤ s.length := by simpa using Cycle.length_nontrivial ht
simp only [Cycle.mk_eq_coe, Cycle.nodup_coe_iff, Cycle.mem_coe_iff, Subtype.coe_mk,
- Cycle.formPerm_coe] at hn hx⊢
+ Cycle.formPerm_coe] at hn hx ⊢
apply Subtype.ext
dsimp
rw [toCycle_eq_toList _ _ x]
@@ -133,7 +133,7 @@ namespace Cycle
variable [DecidableEq α] (s s' : Cycle α)
-/-- A cycle `s : Cycle α`, given `Nodup s` can be interpreted as a `Equiv.Perm α`
+/-- A cycle `s : Cycle α`, given `Nodup s` can be interpreted as an `Equiv.Perm α`
where each element in the list is permuted to the next one, defined as `formPerm`.
-/
def formPerm : ∀ (s : Cycle α) (_ : Nodup s), Equiv.Perm α :=
@@ -162,14 +162,13 @@ theorem formPerm_subsingleton (s : Cycle α) (h : Subsingleton s) : formPerm s h
theorem isCycle_formPerm (s : Cycle α) (h : Nodup s) (hn : Nontrivial s) :
IsCycle (formPerm s h) := by
- induction s using Quot.inductionOn; simp
- --apply List.isCycle_formPerm
+ induction s using Quot.inductionOn
exact List.isCycle_formPerm h (length_nontrivial hn)
#align cycle.is_cycle_form_perm Cycle.isCycle_formPerm
theorem support_formPerm [Fintype α] (s : Cycle α) (h : Nodup s) (hn : Nontrivial s) :
support (formPerm s h) = s.toFinset := by
- induction' s using Quot.inductionOn with s; simp
+ induction' s using Quot.inductionOn with s
refine' support_formPerm_of_nodup s h _
rintro _ rfl
simpa [Nat.succ_le_succ_iff] using length_nontrivial hn
@@ -330,9 +329,8 @@ theorem SameCycle.toList_isRotated {f : Perm α} {x y : α} (h : SameCycle f x y
by_cases hx : x ∈ f.support
· obtain ⟨_ | k, _, hy⟩ := h.exists_pow_eq_of_mem_support hx
· simp only [coe_one, id.def, pow_zero, Nat.zero_eq] at hy
- simp [hy]
- exists 0
- simp only [rotate_zero]
+ -- Porting note: added `IsRotated.refl`
+ simp [hy, IsRotated.refl]
use k.succ
rw [← toList_pow_apply_eq_rotate, hy]
· rw [toList_eq_nil_iff.mpr hx, isRotated_nil_iff', eq_comm, toList_eq_nil_iff]
@@ -351,6 +349,7 @@ theorem toList_formPerm_nil (x : α) : toList (formPerm ([] : List α)) x = [] :
theorem toList_formPerm_singleton (x y : α) : toList (formPerm [x]) y = [] := by simp
#align equiv.perm.to_list_form_perm_singleton Equiv.Perm.toList_formPerm_singleton
+set_option linter.deprecated false in
theorem toList_formPerm_nontrivial (l : List α) (hl : 2 ≤ l.length) (hn : Nodup l) :
toList (formPerm l) (l.nthLe 0 (zero_lt_two.trans_le hl)) = l := by
have hc : l.formPerm.IsCycle := List.isCycle_formPerm hn hl
@@ -361,7 +360,7 @@ theorem toList_formPerm_nontrivial (l : List α) (hl : 2 ≤ l.length) (hn : Nod
rw [toList, hc.cycleOf_eq (mem_support.mp _), hs, card_toFinset, dedup_eq_self.mpr hn]
· refine' ext_get (by simp) fun k hk hk' => _
simp [formPerm_pow_apply_nthLe _ hn, Nat.mod_eq_of_lt hk']
- rfl -- Porting note: not needed in Lean 3
+ rw [nthLe_eq]
· simpa [hs] using get_mem _ _ _
#align equiv.perm.to_list_form_perm_nontrivial Equiv.Perm.toList_formPerm_nontrivial
notation3
delaborator generation (#4533)
Gives the notation3
command the ability to generate a delaborator in most common situations. When it succeeds, notation3
-defined syntax is pretty printable.
Examples:
(⋃ (i : ι) (i' : ι'), s i i') = ⋃ (i' : ι') (i : ι), s i i'
(⨆ (g : α → ℝ≥0∞) (_ : Measurable g) (_ : g ≤ f), ∫⁻ (a : α), g a ∂μ) = ∫⁻ (a : α), f a ∂μ
Co-authored-by: Mario Carneiro <di.gama@gmail.com>
@@ -522,7 +522,7 @@ def isoCycle' : { f : Perm α // IsCycle f } ≃ { s : Cycle α // s.Nodup ∧ s
#align equiv.perm.iso_cycle' Equiv.Perm.isoCycle'
notation3 "c["(l", "* => foldr (h t => List.cons h t) List.nil)"]" =>
- Cycle.formPerm (↑l) (Cycle.nodup_coe_iff.mpr _)
+ Cycle.formPerm (Cycle.ofList l) (Iff.mpr Cycle.nodup_coe_iff _)
unsafe instance repr_perm [Repr α] : Repr (Perm α) :=
⟨fun f _ => repr (Multiset.pmap (fun (g : Perm α) (hg : g.IsCycle) => isoCycle ⟨g, hg⟩)
This fixes a bunch of spacing bugs in tactics. Mathlib counterpart of:
@@ -521,7 +521,7 @@ def isoCycle' : { f : Perm α // IsCycle f } ≃ { s : Cycle α // s.Nodup ∧ s
right_inv := Fintype.leftInverse_bijInv _ }
#align equiv.perm.iso_cycle' Equiv.Perm.isoCycle'
-notation3"c["(l", "* => foldr (h t => List.cons h t) List.nil)"]" =>
+notation3 "c["(l", "* => foldr (h t => List.cons h t) List.nil)"]" =>
Cycle.formPerm (↑l) (Cycle.nodup_coe_iff.mpr _)
unsafe instance repr_perm [Repr α] : Repr (Perm α) :=
fix-comments.py
on all files.@@ -28,7 +28,7 @@ In the following, `{α : Type _} [Fintype α] [DecidableEq α]`.
* `Equiv.Perm.isoCycle'`: the same equivalence as `Equiv.Perm.isoCycle`
but with evaluation via choosing over fintypes
* The notation `c[1, 2, 3]` to emulate notation of cyclic permutations `(1 2 3)`
-* A `has_repr` instance for any `Perm α`, by representing the `Finset` of
+* A `Repr` instance for any `Perm α`, by representing the `Finset` of
`Cycle α` that correspond to the cycle factors.
## Main results
@@ -44,7 +44,7 @@ The forward direction of `Equiv.Perm.isoCycle'` uses `Fintype.choose` of the uni
result, relying on the `Fintype` instance of a `Cycle.nodup` subtype.
It is unclear if this works faster than the `Equiv.Perm.toCycle`, which relies
on recursion over `Finset.univ`.
-Running `#eval` on even a simple noncyclic permutation `c[(1 : fin 7), 2, 3] * c[0, 5]`
+Running `#eval` on even a simple noncyclic permutation `c[(1 : Fin 7), 2, 3] * c[0, 5]`
to show it takes a long time. TODO: is this because computing the cycle factors is slow?
-/
The unported dependencies are