Stafford38/LinearAlgebra/PairReplacement.lean

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