This project (Stafford38) · 1029fdb382eee06e7b59bcf32801f40931e2079a
1 module 2 public import Mathlib.LinearAlgebra.Span.Basic 3 public import Mathlib.Algebra.Module.FinitePresentation 4 public import Mathlib.Tactic.NoncommRing 5 6 @[expose] public section 7 8 /-! 9 # Generic pair replacement for right modules 10 11 The matrix calculation behind Stafford's cyclicity argument uses only a ring, 12 a right module, torsion of the two chosen elements, and the coefficient 13 identity `1 = d * R + F * d * S`. These results are kept independent of the 14 Weyl algebra and its application-specific certificate. 15 -/ 16 17 namespace Stafford38.LinearAlgebra.PairReplacement 18 19 universe u v 20 21 variable {A : Type u} [Ring A] 22 23 /-- The two displayed vectors generate the free rank-two right module. Right 24 coordinates are represented as a left module over the opposite ring. -/ 25 theorem matrix_pair_spans (a F : A) : 26 Submodule.span Aᵐᵒᵖ 27 ({(a, 1 - F * a), (1, -F)} : Set (A × A)) = ⊤ := by 28 classical 29 let P : Submodule Aᵐᵒᵖ (A × A) := 30 Submodule.span Aᵐᵒᵖ ({(a, 1 - F * a), (1, -F)} : Set (A × A)) 31 apply top_unique 32 rintro ⟨x, y⟩ _ 33 have h₁ : (a, 1 - F * a) ∈ P := by 34 exact Submodule.subset_span (by simp) 35 have h₂ : (1, -F) ∈ P := by 36 exact Submodule.subset_span (by simp) 37 let u : A := y + F * x 38 let v : A := x - a * u 39 have hz : (x, y) = 40 (MulOpposite.op u : Aᵐᵒᵖ) • (a, 1 - F * a) + 41 (MulOpposite.op v : Aᵐᵒᵖ) • (1, -F) := by 42 simp only [Prod.smul_def, Prod.add_def, MulOpposite.smul_eq_mul_unop, 43 MulOpposite.unop_op, one_mul] 44 change (x, y) = (a * u + v, (1 - F * a) * u + (-F) * v) 45 dsimp [u, v] 46 congr 1 <;> noncomm_ring 47 rw [hz] 48 exact P.add_mem (P.smul_mem _ h₁) (P.smul_mem _ h₂) 49 50 variable {M : Type v} [AddCommGroup M] [Module Aᵐᵒᵖ M] 51 52 /-- Two torsion elements have a common nonzero right annihilator. The product 53 order `d₂*e` is required for the right-module action. -/ 54 theorem common_right_annihilator 55 (htorsion : ∀ m : M, ∃ d : A, d ≠ 0 ∧ 56 (MulOpposite.op d : Aᵐᵒᵖ) • m = 0) 57 (x y : M) 58 (hmul : ∀ a b : A, a ≠ 0 → b ≠ 0 → a * b ≠ 0) : 59 ∃ d : A, d ≠ 0 ∧ 60 (MulOpposite.op d : Aᵐᵒᵖ) • x = 0 ∧ 61 (MulOpposite.op d : Aᵐᵒᵖ) • y = 0 := by 62 obtain ⟨d₂, hd₂, hdy⟩ := htorsion y 63 obtain ⟨e, he, hdx⟩ := htorsion 64 ((MulOpposite.op d₂ : Aᵐᵒᵖ) • x) 65 refine ⟨d₂ * e, hmul d₂ e hd₂ he, ?_, ?_⟩ 66 · change (MulOpposite.op e * MulOpposite.op d₂) • x = 0 67 rw [← smul_smul] 68 exact hdx 69 · change (MulOpposite.op e * MulOpposite.op d₂) • y = 0 70 rw [← smul_smul, hdy, smul_zero] 71 72 /-- The matrix calculation proves pair replacement for any right module over a 73 ring satisfying the displayed coefficient identity. -/ 74 theorem span_adjusted_pair_eq_span_pair 75 (x y : M) (d F R S : A) 76 (hxann : (MulOpposite.op d : Aᵐᵒᵖ) • x = 0) 77 (hyann : (MulOpposite.op d : Aᵐᵒᵖ) • y = 0) 78 (hcert : (1 : A) = d * R + F * d * S) : 79 Submodule.span Aᵐᵒᵖ 80 ({x - (MulOpposite.op F : Aᵐᵒᵖ) • y} : Set M) = 81 Submodule.span Aᵐᵒᵖ ({x, y} : Set M) := by 82 classical 83 let g : M := x - (MulOpposite.op F : Aᵐᵒᵖ) • y 84 let P : Submodule Aᵐᵒᵖ M := Submodule.span Aᵐᵒᵖ ({x, y} : Set M) 85 let phi : (A × A) →ₗ[Aᵐᵒᵖ] M := 86 { toFun := fun z => (MulOpposite.op z.1 : Aᵐᵒᵖ) • x + 87 (MulOpposite.op z.2 : Aᵐᵒᵖ) • y 88 map_add' := by 89 intro z w 90 rcases z with ⟨z₁, z₂⟩ 91 rcases w with ⟨w₁, w₂⟩ 92 simp [Prod.add_def, MulOpposite.op_add, add_smul] 93 abel 94 map_smul' := by 95 intro c z 96 rcases z with ⟨z₁, z₂⟩ 97 simp only [Prod.smul_def, MulOpposite.smul_eq_mul_unop, 98 MulOpposite.op_mul, smul_add, smul_smul] 99 rfl } 100 let U : Submodule Aᵐᵒᵖ (A × A) := 101 Submodule.span Aᵐᵒᵖ 102 ({(d * S, 1 - F * (d * S)), (1, -F)} : Set (A × A)) 103 let H : Submodule Aᵐᵒᵖ M := 104 Submodule.span Aᵐᵒᵖ ({g} : Set M) 105 have hzero₁ : phi (d * S, 1 - F * (d * S)) = 0 := by 106 have hx : (MulOpposite.op (d * S) : Aᵐᵒᵖ) • x = 0 := by 107 change (MulOpposite.op S * MulOpposite.op d) • x = 0 108 rw [← smul_smul, hxann, smul_zero] 109 have hy_dR : (MulOpposite.op (d * R) : Aᵐᵒᵖ) • y = 0 := by 110 change (MulOpposite.op R * MulOpposite.op d) • y = 0 111 rw [← smul_smul, hyann, smul_zero] 112 have hy_FdS : (MulOpposite.op (F * d * S) : Aᵐᵒᵖ) • y = y := by 113 have hsum : y = 114 (MulOpposite.op (d * R) : Aᵐᵒᵖ) • y + 115 (MulOpposite.op (F * d * S) : Aᵐᵒᵖ) • y := by 116 calc 117 y = (MulOpposite.op (1 : A) : Aᵐᵒᵖ) • y := by simp 118 _ = (MulOpposite.op (d * R + F * d * S) : Aᵐᵒᵖ) • y := by 119 rw [hcert] 120 _ = _ := by rw [MulOpposite.op_add, add_smul] 121 simpa only [hy_dR, zero_add] using hsum.symm 122 have hyfactor : (MulOpposite.op (1 - F * (d * S)) : Aᵐᵒᵖ) • y = 0 := by 123 calc 124 _ = (MulOpposite.op (1 : A) : Aᵐᵒᵖ) • y - 125 (MulOpposite.op (F * d * S) : Aᵐᵒᵖ) • y := by 126 rw [MulOpposite.op_sub, sub_smul] 127 congr 1 128 simp [mul_assoc] 129 _ = 0 := by rw [MulOpposite.op_one, one_smul, hy_FdS, sub_self] 130 change (MulOpposite.op (d * S) : Aᵐᵒᵖ) • x + 131 (MulOpposite.op (1 - F * (d * S)) : Aᵐᵒᵖ) • y = 0 132 rw [hx, hyfactor, add_zero] 133 have hzero₂ : phi (1, -F) = g := by 134 change (MulOpposite.op (1 : A) : Aᵐᵒᵖ) • x + 135 (MulOpposite.op (-F) : Aᵐᵒᵖ) • y = _ 136 simp [g, sub_eq_add_neg] 137 have hphi : phi.range = P := by 138 apply le_antisymm 139 · rintro z ⟨w, rfl⟩ 140 rcases w with ⟨a, b⟩ 141 change (MulOpposite.op a : Aᵐᵒᵖ) • x + 142 (MulOpposite.op b : Aᵐᵒᵖ) • y ∈ P 143 exact P.add_mem 144 (P.smul_mem _ (Submodule.subset_span (by simp))) 145 (P.smul_mem _ (Submodule.subset_span (by simp))) 146 · apply Submodule.span_le.2 147 intro z hz 148 simp only [Set.mem_insert_iff, Set.mem_singleton_iff] at hz 149 rcases hz with rfl | rfl 150 · exact ⟨(1, 0), by simp [phi]⟩ 151 · exact ⟨(0, 1), by simp [phi]⟩ 152 have hmatrix := matrix_pair_spans (d * S) F 153 have hgen : P = H := by 154 calc 155 P = phi.range := hphi.symm 156 _ = Submodule.map phi ⊤ := (Submodule.map_top _).symm 157 _ = Submodule.map phi U := by rw [← hmatrix] 158 _ = H := by 159 rw [Submodule.map_span] 160 apply le_antisymm 161 · apply Submodule.span_le.2 162 rintro z ⟨w, hw, rfl⟩ 163 simp only [Set.mem_insert_iff, Set.mem_singleton_iff] at hw 164 rcases hw with rfl | rfl 165 · rw [hzero₁] 166 exact H.zero_mem 167 · rw [hzero₂] 168 exact Submodule.subset_span (by simp) 169 · apply Submodule.span_le.2 170 intro z hz 171 simp only [Set.mem_singleton_iff] at hz 172 subst z 173 rw [← hzero₂] 174 exact Submodule.subset_span (by simp) 175 simpa [P, H, g] using hgen.symm 176 177 /-- A torsion pair can be replaced by one generator. -/ 178 theorem exists_adjusted_pair 179 (hmul : ∀ a b : A, a ≠ 0 → b ≠ 0 → a * b ≠ 0) 180 (hone : ∀ d : A, d ≠ 0 → 181 ∃ F R S : A, (1 : A) = d * R + F * d * S) 182 (htorsion : ∀ m : M, ∃ d : A, d ≠ 0 ∧ 183 (MulOpposite.op d : Aᵐᵒᵖ) • m = 0) (x y : M) : 184 ∃ F : A, Submodule.span Aᵐᵒᵖ 185 ({x - (MulOpposite.op F : Aᵐᵒᵖ) • y} : Set M) = 186 Submodule.span Aᵐᵒᵖ ({x, y} : Set M) := by 187 obtain ⟨d, hd, hx, hy⟩ := common_right_annihilator htorsion x y hmul 188 obtain ⟨F, R, S, hcert⟩ := hone d hd 189 exact ⟨F, span_adjusted_pair_eq_span_pair x y d F R S hx hy hcert⟩ 190 191 /-- Forget the explicit matrix coefficient and retain its generated singleton. -/ 192 theorem exists_singleton_eq_span_pair 193 (hmul : ∀ a b : A, a ≠ 0 → b ≠ 0 → a * b ≠ 0) 194 (hone : ∀ d : A, d ≠ 0 → 195 ∃ F R S : A, (1 : A) = d * R + F * d * S) 196 (htorsion : ∀ m : M, ∃ d : A, d ≠ 0 ∧ 197 (MulOpposite.op d : Aᵐᵒᵖ) • m = 0) (x y : M) : 198 ∃ z : M, Submodule.span Aᵐᵒᵖ ({z} : Set M) = 199 Submodule.span Aᵐᵒᵖ ({x, y} : Set M) := by 200 obtain ⟨F, hF⟩ := exists_adjusted_pair hmul hone htorsion x y 201 exact ⟨x - (MulOpposite.op F : Aᵐᵒᵖ) • y, hF⟩ 202 203 /-- Pair replacement iterated along a finite spanning set makes any finitely 204 generated torsion right module cyclic. -/ 205 theorem finite_torsion_module_is_cyclic 206 (hmul : ∀ a b : A, a ≠ 0 → b ≠ 0 → a * b ≠ 0) 207 (hone : ∀ d : A, d ≠ 0 → 208 ∃ F R S : A, (1 : A) = d * R + F * d * S) 209 (htorsion : ∀ m : M, ∃ d : A, d ≠ 0 ∧ 210 (MulOpposite.op d : Aᵐᵒᵖ) • m = 0) 211 [Module.Finite Aᵐᵒᵖ M] : 212 ∃ z : M, Submodule.span Aᵐᵒᵖ ({z} : Set M) = ⊤ := by 213 classical 214 obtain ⟨s, hs⟩ := (Module.Finite.fg_top : (⊤ : Submodule Aᵐᵒᵖ M).FG) 215 have hcollapse (s : Finset M) : 216 ∃ z : M, Submodule.span Aᵐᵒᵖ (s : Set M) = 217 Submodule.span Aᵐᵒᵖ ({z} : Set M) := by 218 induction s using Finset.induction_on with 219 | empty => exact ⟨0, by simp⟩ 220 | @insert x s hxs ih => 221 obtain ⟨y, hy⟩ := ih 222 obtain ⟨z, hpair⟩ := exists_singleton_eq_span_pair hmul hone htorsion x y 223 refine ⟨z, ?_⟩ 224 have hpairSet : ({x, y} : Set M) = ({x} : Set M) ∪ {y} := by 225 ext w 226 simp [or_comm] 227 calc 228 Submodule.span Aᵐᵒᵖ ((insert x s : Finset M) : Set M) = 229 Submodule.span Aᵐᵒᵖ {x} ⊔ Submodule.span Aᵐᵒᵖ (s : Set M) := by 230 rw [Finset.coe_insert, Submodule.span_insert] 231 _ = Submodule.span Aᵐᵒᵖ {x} ⊔ Submodule.span Aᵐᵒᵖ {y} := by rw [hy] 232 _ = Submodule.span Aᵐᵒᵖ ({x, y} : Set M) := by 233 rw [hpairSet, Submodule.span_union] 234 _ = Submodule.span Aᵐᵒᵖ {z} := hpair.symm 235 obtain ⟨z, hz⟩ := hcollapse s 236 exact ⟨z, hz.symm.trans hs⟩ 237 238 #print axioms matrix_pair_spans 239 #print axioms common_right_annihilator 240 #print axioms span_adjusted_pair_eq_span_pair 241 #print axioms exists_adjusted_pair 242 #print axioms exists_singleton_eq_span_pair 243 #print axioms finite_torsion_module_is_cyclic 244 245 end Stafford38.LinearAlgebra.PairReplacement 246