support of a permutation #
Main definitions #
In the following, f g : Equiv.Perm α
.
Equiv.Perm.Disjoint
: two permutationsf
andg
areDisjoint
if every element is fixed either byf
, or byg
. Equivalently,f
andg
areDisjoint
iff theirsupport
are disjoint.Equiv.Perm.IsSwap
:f = swap x y
forx ≠ y
.Equiv.Perm.support
: the elementsx : α
that are not fixed byf
.
Assume α
is a Fintype:
Equiv.Perm.fixed_point_card_lt_of_ne_one f
says thatf
has strictly less thanFintype.card α - 1
fixed points, unlessf = 1
. (Equivalently,f.support
has at least 2 elements.)
theorem
Equiv.Perm.Disjoint.symm
{α : Type u_1}
{f : Equiv.Perm α}
{g : Equiv.Perm α}
:
Equiv.Perm.Disjoint f g → Equiv.Perm.Disjoint g f
instance
Equiv.Perm.instIsSymmPermDisjoint
{α : Type u_1}
:
IsSymm (Equiv.Perm α) Equiv.Perm.Disjoint
Equations
- ⋯ = ⋯
theorem
Equiv.Perm.disjoint_comm
{α : Type u_1}
{f : Equiv.Perm α}
{g : Equiv.Perm α}
:
Equiv.Perm.Disjoint f g ↔ Equiv.Perm.Disjoint g f
theorem
Equiv.Perm.Disjoint.commute
{α : Type u_1}
{f : Equiv.Perm α}
{g : Equiv.Perm α}
(h : Equiv.Perm.Disjoint f g)
:
Commute f g
@[simp]
@[simp]
theorem
Equiv.Perm.disjoint_iff_eq_or_eq
{α : Type u_1}
{f : Equiv.Perm α}
{g : Equiv.Perm α}
:
Equiv.Perm.Disjoint f g ↔ ∀ (x : α), f x = x ∨ g x = x
@[simp]
theorem
Equiv.Perm.disjoint_refl_iff
{α : Type u_1}
{f : Equiv.Perm α}
:
Equiv.Perm.Disjoint f f ↔ f = 1
theorem
Equiv.Perm.Disjoint.inv_left
{α : Type u_1}
{f : Equiv.Perm α}
{g : Equiv.Perm α}
(h : Equiv.Perm.Disjoint f g)
:
theorem
Equiv.Perm.Disjoint.inv_right
{α : Type u_1}
{f : Equiv.Perm α}
{g : Equiv.Perm α}
(h : Equiv.Perm.Disjoint f g)
:
@[simp]
@[simp]
theorem
Equiv.Perm.Disjoint.mul_left
{α : Type u_1}
{f : Equiv.Perm α}
{g : Equiv.Perm α}
{h : Equiv.Perm α}
(H1 : Equiv.Perm.Disjoint f h)
(H2 : Equiv.Perm.Disjoint g h)
:
Equiv.Perm.Disjoint (f * g) h
theorem
Equiv.Perm.Disjoint.mul_right
{α : Type u_1}
{f : Equiv.Perm α}
{g : Equiv.Perm α}
{h : Equiv.Perm α}
(H1 : Equiv.Perm.Disjoint f g)
(H2 : Equiv.Perm.Disjoint f h)
:
Equiv.Perm.Disjoint f (g * h)
theorem
Equiv.Perm.disjoint_conj
{α : Type u_1}
{f : Equiv.Perm α}
{g : Equiv.Perm α}
(h : Equiv.Perm α)
:
Equiv.Perm.Disjoint (h * f * h⁻¹) (h * g * h⁻¹) ↔ Equiv.Perm.Disjoint f g
theorem
Equiv.Perm.Disjoint.conj
{α : Type u_1}
{f : Equiv.Perm α}
{g : Equiv.Perm α}
(H : Equiv.Perm.Disjoint f g)
(h : Equiv.Perm α)
:
theorem
Equiv.Perm.disjoint_prod_right
{α : Type u_1}
{f : Equiv.Perm α}
(l : List (Equiv.Perm α))
(h : ∀ g ∈ l, Equiv.Perm.Disjoint f g)
:
Equiv.Perm.Disjoint f (List.prod l)
theorem
Equiv.Perm.disjoint_prod_perm
{α : Type u_1}
{l₁ : List (Equiv.Perm α)}
{l₂ : List (Equiv.Perm α)}
(hl : List.Pairwise Equiv.Perm.Disjoint l₁)
(hp : List.Perm l₁ l₂)
:
theorem
Equiv.Perm.nodup_of_pairwise_disjoint
{α : Type u_1}
{l : List (Equiv.Perm α)}
(h1 : 1 ∉ l)
(h2 : List.Pairwise Equiv.Perm.Disjoint l)
:
theorem
Equiv.Perm.pow_apply_eq_self_of_apply_eq_self
{α : Type u_1}
{f : Equiv.Perm α}
{x : α}
(hfx : f x = x)
(n : ℕ)
:
theorem
Equiv.Perm.zpow_apply_eq_self_of_apply_eq_self
{α : Type u_1}
{f : Equiv.Perm α}
{x : α}
(hfx : f x = x)
(n : ℤ)
:
theorem
Equiv.Perm.Disjoint.mul_apply_eq_iff
{α : Type u_1}
{σ : Equiv.Perm α}
{τ : Equiv.Perm α}
(hστ : Equiv.Perm.Disjoint σ τ)
{a : α}
:
theorem
Equiv.Perm.Disjoint.mul_eq_one_iff
{α : Type u_1}
{σ : Equiv.Perm α}
{τ : Equiv.Perm α}
(hστ : Equiv.Perm.Disjoint σ τ)
:
theorem
Equiv.Perm.Disjoint.zpow_disjoint_zpow
{α : Type u_1}
{σ : Equiv.Perm α}
{τ : Equiv.Perm α}
(hστ : Equiv.Perm.Disjoint σ τ)
(m : ℤ)
(n : ℤ)
:
Equiv.Perm.Disjoint (σ ^ m) (τ ^ n)
theorem
Equiv.Perm.Disjoint.pow_disjoint_pow
{α : Type u_1}
{σ : Equiv.Perm α}
{τ : Equiv.Perm α}
(hστ : Equiv.Perm.Disjoint σ τ)
(m : ℕ)
(n : ℕ)
:
Equiv.Perm.Disjoint (σ ^ m) (τ ^ n)
f.IsSwap
indicates that the permutation f
is a transposition of two elements.
Equations
- Equiv.Perm.IsSwap f = ∃ (x : α) (y : α), x ≠ y ∧ f = Equiv.swap x y
Instances For
@[simp]
theorem
Equiv.Perm.ofSubtype_swap_eq
{α : Type u_1}
[DecidableEq α]
{p : α → Prop}
[DecidablePred p]
(x : Subtype p)
(y : Subtype p)
:
Equiv.Perm.ofSubtype (Equiv.swap x y) = Equiv.swap ↑x ↑y
theorem
Equiv.Perm.IsSwap.of_subtype_isSwap
{α : Type u_1}
[DecidableEq α]
{p : α → Prop}
[DecidablePred p]
{f : Equiv.Perm (Subtype p)}
(h : Equiv.Perm.IsSwap f)
:
Equiv.Perm.IsSwap (Equiv.Perm.ofSubtype f)
theorem
Equiv.Perm.ne_and_ne_of_swap_mul_apply_ne_self
{α : Type u_1}
[DecidableEq α]
{f : Equiv.Perm α}
{x : α}
{y : α}
(hy : (Equiv.swap x (f x) * f) y ≠ y)
:
The Finset
of nonfixed points of a permutation.
Equations
- Equiv.Perm.support f = Finset.filter (fun (x : α) => f x ≠ x) Finset.univ
Instances For
@[simp]
theorem
Equiv.Perm.mem_support
{α : Type u_1}
[DecidableEq α]
[Fintype α]
{f : Equiv.Perm α}
{x : α}
:
x ∈ Equiv.Perm.support f ↔ f x ≠ x
theorem
Equiv.Perm.not_mem_support
{α : Type u_1}
[DecidableEq α]
[Fintype α]
{f : Equiv.Perm α}
{x : α}
:
x ∉ Equiv.Perm.support f ↔ f x = x
theorem
Equiv.Perm.coe_support_eq_set_support
{α : Type u_1}
[DecidableEq α]
[Fintype α]
(f : Equiv.Perm α)
:
↑(Equiv.Perm.support f) = {x : α | f x ≠ x}
@[simp]
theorem
Equiv.Perm.support_eq_empty_iff
{α : Type u_1}
[DecidableEq α]
[Fintype α]
{σ : Equiv.Perm α}
:
Equiv.Perm.support σ = ∅ ↔ σ = 1
@[simp]
@[simp]
theorem
Equiv.Perm.support_congr
{α : Type u_1}
[DecidableEq α]
[Fintype α]
{f : Equiv.Perm α}
{g : Equiv.Perm α}
(h : Equiv.Perm.support f ⊆ Equiv.Perm.support g)
(h' : ∀ x ∈ Equiv.Perm.support g, f x = g x)
:
f = g
theorem
Equiv.Perm.support_mul_le
{α : Type u_1}
[DecidableEq α]
[Fintype α]
(f : Equiv.Perm α)
(g : Equiv.Perm α)
:
Equiv.Perm.support (f * g) ≤ Equiv.Perm.support f ⊔ Equiv.Perm.support g
theorem
Equiv.Perm.exists_mem_support_of_mem_support_prod
{α : Type u_1}
[DecidableEq α]
[Fintype α]
{l : List (Equiv.Perm α)}
{x : α}
(hx : x ∈ Equiv.Perm.support (List.prod l))
:
∃ f ∈ l, x ∈ Equiv.Perm.support f
theorem
Equiv.Perm.support_pow_le
{α : Type u_1}
[DecidableEq α]
[Fintype α]
(σ : Equiv.Perm α)
(n : ℕ)
:
Equiv.Perm.support (σ ^ n) ≤ Equiv.Perm.support σ
@[simp]
theorem
Equiv.Perm.apply_mem_support
{α : Type u_1}
[DecidableEq α]
[Fintype α]
{f : Equiv.Perm α}
{x : α}
:
f x ∈ Equiv.Perm.support f ↔ x ∈ Equiv.Perm.support f
@[simp]
theorem
Equiv.Perm.pow_apply_mem_support
{α : Type u_1}
[DecidableEq α]
[Fintype α]
{f : Equiv.Perm α}
{n : ℕ}
{x : α}
:
(f ^ n) x ∈ Equiv.Perm.support f ↔ x ∈ Equiv.Perm.support f
@[simp]
theorem
Equiv.Perm.zpow_apply_mem_support
{α : Type u_1}
[DecidableEq α]
[Fintype α]
{f : Equiv.Perm α}
{n : ℤ}
{x : α}
:
(f ^ n) x ∈ Equiv.Perm.support f ↔ x ∈ Equiv.Perm.support f
theorem
Equiv.Perm.pow_eq_on_of_mem_support
{α : Type u_1}
[DecidableEq α]
[Fintype α]
{f : Equiv.Perm α}
{g : Equiv.Perm α}
(h : ∀ x ∈ Equiv.Perm.support f ∩ Equiv.Perm.support g, f x = g x)
(k : ℕ)
(x : α)
:
x ∈ Equiv.Perm.support f ∩ Equiv.Perm.support g → (f ^ k) x = (g ^ k) x
theorem
Equiv.Perm.disjoint_iff_disjoint_support
{α : Type u_1}
[DecidableEq α]
[Fintype α]
{f : Equiv.Perm α}
{g : Equiv.Perm α}
:
Equiv.Perm.Disjoint f g ↔ Disjoint (Equiv.Perm.support f) (Equiv.Perm.support g)
theorem
Equiv.Perm.Disjoint.disjoint_support
{α : Type u_1}
[DecidableEq α]
[Fintype α]
{f : Equiv.Perm α}
{g : Equiv.Perm α}
(h : Equiv.Perm.Disjoint f g)
:
theorem
Equiv.Perm.Disjoint.support_mul
{α : Type u_1}
[DecidableEq α]
[Fintype α]
{f : Equiv.Perm α}
{g : Equiv.Perm α}
(h : Equiv.Perm.Disjoint f g)
:
Equiv.Perm.support (f * g) = Equiv.Perm.support f ∪ Equiv.Perm.support g
theorem
Equiv.Perm.support_prod_of_pairwise_disjoint
{α : Type u_1}
[DecidableEq α]
[Fintype α]
(l : List (Equiv.Perm α))
(h : List.Pairwise Equiv.Perm.Disjoint l)
:
Equiv.Perm.support (List.prod l) = List.foldr (fun (x x_1 : Finset α) => x ⊔ x_1) ⊥ (List.map Equiv.Perm.support l)
theorem
Equiv.Perm.support_prod_le
{α : Type u_1}
[DecidableEq α]
[Fintype α]
(l : List (Equiv.Perm α))
:
Equiv.Perm.support (List.prod l) ≤ List.foldr (fun (x x_1 : Finset α) => x ⊔ x_1) ⊥ (List.map Equiv.Perm.support l)
theorem
Equiv.Perm.support_zpow_le
{α : Type u_1}
[DecidableEq α]
[Fintype α]
(σ : Equiv.Perm α)
(n : ℤ)
:
Equiv.Perm.support (σ ^ n) ≤ Equiv.Perm.support σ
@[simp]
theorem
Equiv.Perm.support_swap
{α : Type u_1}
[DecidableEq α]
[Fintype α]
{x : α}
{y : α}
(h : x ≠ y)
:
Equiv.Perm.support (Equiv.swap x y) = {x, y}
theorem
Equiv.Perm.support_swap_iff
{α : Type u_1}
[DecidableEq α]
[Fintype α]
(x : α)
(y : α)
:
Equiv.Perm.support (Equiv.swap x y) = {x, y} ↔ x ≠ y
theorem
Equiv.Perm.support_swap_mul_swap
{α : Type u_1}
[DecidableEq α]
[Fintype α]
{x : α}
{y : α}
{z : α}
(h : List.Nodup [x, y, z])
:
Equiv.Perm.support (Equiv.swap x y * Equiv.swap y z) = {x, y, z}
theorem
Equiv.Perm.support_swap_mul_ge_support_diff
{α : Type u_1}
[DecidableEq α]
[Fintype α]
(f : Equiv.Perm α)
(x : α)
(y : α)
:
Equiv.Perm.support f \ {x, y} ≤ Equiv.Perm.support (Equiv.swap x y * f)
theorem
Equiv.Perm.support_swap_mul_eq
{α : Type u_1}
[DecidableEq α]
[Fintype α]
(f : Equiv.Perm α)
(x : α)
(h : f (f x) ≠ x)
:
Equiv.Perm.support (Equiv.swap x (f x) * f) = Equiv.Perm.support f \ {x}
theorem
Equiv.Perm.mem_support_swap_mul_imp_mem_support_ne
{α : Type u_1}
[DecidableEq α]
[Fintype α]
{f : Equiv.Perm α}
{x : α}
{y : α}
(hy : y ∈ Equiv.Perm.support (Equiv.swap x (f x) * f))
:
y ∈ Equiv.Perm.support f ∧ y ≠ x
theorem
Equiv.Perm.Disjoint.mem_imp
{α : Type u_1}
[DecidableEq α]
[Fintype α]
{f : Equiv.Perm α}
{g : Equiv.Perm α}
(h : Equiv.Perm.Disjoint f g)
{x : α}
(hx : x ∈ Equiv.Perm.support f)
:
x ∉ Equiv.Perm.support g
theorem
Equiv.Perm.eq_on_support_mem_disjoint
{α : Type u_1}
[DecidableEq α]
[Fintype α]
{f : Equiv.Perm α}
{l : List (Equiv.Perm α)}
(h : f ∈ l)
(hl : List.Pairwise Equiv.Perm.Disjoint l)
(x : α)
:
x ∈ Equiv.Perm.support f → f x = (List.prod l) x
theorem
Equiv.Perm.Disjoint.mono
{α : Type u_1}
[DecidableEq α]
[Fintype α]
{f : Equiv.Perm α}
{g : Equiv.Perm α}
{x : Equiv.Perm α}
{y : Equiv.Perm α}
(h : Equiv.Perm.Disjoint f g)
(hf : Equiv.Perm.support x ≤ Equiv.Perm.support f)
(hg : Equiv.Perm.support y ≤ Equiv.Perm.support g)
:
theorem
Equiv.Perm.support_le_prod_of_mem
{α : Type u_1}
[DecidableEq α]
[Fintype α]
{f : Equiv.Perm α}
{l : List (Equiv.Perm α)}
(h : f ∈ l)
(hl : List.Pairwise Equiv.Perm.Disjoint l)
:
@[simp]
theorem
Equiv.Perm.support_extend_domain
{α : Type u_1}
[DecidableEq α]
[Fintype α]
{β : Type u_2}
[DecidableEq β]
[Fintype β]
{p : β → Prop}
[DecidablePred p]
(f : α ≃ Subtype p)
{g : Equiv.Perm α}
:
theorem
Equiv.Perm.card_support_extend_domain
{α : Type u_1}
[DecidableEq α]
[Fintype α]
{β : Type u_2}
[DecidableEq β]
[Fintype β]
{p : β → Prop}
[DecidablePred p]
(f : α ≃ Subtype p)
{g : Equiv.Perm α}
:
(Equiv.Perm.support (Equiv.Perm.extendDomain g f)).card = (Equiv.Perm.support g).card
theorem
Equiv.Perm.card_support_eq_zero
{α : Type u_1}
[DecidableEq α]
[Fintype α]
{f : Equiv.Perm α}
:
(Equiv.Perm.support f).card = 0 ↔ f = 1
theorem
Equiv.Perm.one_lt_card_support_of_ne_one
{α : Type u_1}
[DecidableEq α]
[Fintype α]
{f : Equiv.Perm α}
(h : f ≠ 1)
:
1 < (Equiv.Perm.support f).card
theorem
Equiv.Perm.card_support_ne_one
{α : Type u_1}
[DecidableEq α]
[Fintype α]
(f : Equiv.Perm α)
:
(Equiv.Perm.support f).card ≠ 1
@[simp]
theorem
Equiv.Perm.card_support_le_one
{α : Type u_1}
[DecidableEq α]
[Fintype α]
{f : Equiv.Perm α}
:
(Equiv.Perm.support f).card ≤ 1 ↔ f = 1
theorem
Equiv.Perm.two_le_card_support_of_ne_one
{α : Type u_1}
[DecidableEq α]
[Fintype α]
{f : Equiv.Perm α}
(h : f ≠ 1)
:
2 ≤ (Equiv.Perm.support f).card
theorem
Equiv.Perm.card_support_swap_mul
{α : Type u_1}
[DecidableEq α]
[Fintype α]
{f : Equiv.Perm α}
{x : α}
(hx : f x ≠ x)
:
(Equiv.Perm.support (Equiv.swap x (f x) * f)).card < (Equiv.Perm.support f).card
theorem
Equiv.Perm.card_support_swap
{α : Type u_1}
[DecidableEq α]
[Fintype α]
{x : α}
{y : α}
(hxy : x ≠ y)
:
(Equiv.Perm.support (Equiv.swap x y)).card = 2
@[simp]
theorem
Equiv.Perm.card_support_eq_two
{α : Type u_1}
[DecidableEq α]
[Fintype α]
{f : Equiv.Perm α}
:
(Equiv.Perm.support f).card = 2 ↔ Equiv.Perm.IsSwap f
theorem
Equiv.Perm.Disjoint.card_support_mul
{α : Type u_1}
[DecidableEq α]
[Fintype α]
{f : Equiv.Perm α}
{g : Equiv.Perm α}
(h : Equiv.Perm.Disjoint f g)
:
(Equiv.Perm.support (f * g)).card = (Equiv.Perm.support f).card + (Equiv.Perm.support g).card
theorem
Equiv.Perm.card_support_prod_list_of_pairwise_disjoint
{α : Type u_1}
[DecidableEq α]
[Fintype α]
{l : List (Equiv.Perm α)}
(h : List.Pairwise Equiv.Perm.Disjoint l)
:
@[simp]
theorem
Equiv.Perm.support_subtype_perm
{α : Type u_1}
[DecidableEq α]
{s : Finset α}
(f : Equiv.Perm α)
(h : ∀ (x : α), x ∈ s ↔ f x ∈ s)
:
Equiv.Perm.support (Equiv.Perm.subtypePerm f h) = Finset.filter (fun (x : { x : α // x ∈ s }) => decide (f ↑x ≠ ↑x) = true) (Finset.attach s)
Fixed points #
theorem
Equiv.Perm.fixed_point_card_lt_of_ne_one
{α : Type u_1}
[DecidableEq α]
[Fintype α]
{σ : Equiv.Perm α}
(h : σ ≠ 1)
:
(Finset.filter (fun (x : α) => σ x = x) Finset.univ).card < Fintype.card α - 1
@[simp]
theorem
Equiv.Perm.support_conj
{α : Type u_1}
[Fintype α]
[DecidableEq α]
{σ : Equiv.Perm α}
{τ : Equiv.Perm α}
:
Equiv.Perm.support (σ * τ * σ⁻¹) = Finset.map (Equiv.toEmbedding σ) (Equiv.Perm.support τ)
theorem
Equiv.Perm.card_support_conj
{α : Type u_1}
[Fintype α]
[DecidableEq α]
{σ : Equiv.Perm α}
{τ : Equiv.Perm α}
:
(Equiv.Perm.support (σ * τ * σ⁻¹)).card = (Equiv.Perm.support τ).card