AlgebraicAnalysis/Ore/Associativity.lean

AlgebraicAnalysis library · bbbbf3fc358ca8100b158cec4cf47f336ab70163

1 module
2 public import AlgebraicAnalysis.Ore.RightDivision
3 public import Mathlib.Algebra.Ring.Subring.Basic
4 
5 @[expose] public section
6 
7 /-!
8 # Associativity of derivation Ore normal forms over a noncommutative ring
9 
10 This removes the commutativity assumption from the faithful-operator proof of
11 associativity for `Stafford.OreDivision.rightMul`.
12 -/
13 
14 namespace AlgebraicAnalysis.OreAssociativity
15 
16 open Polynomial
17 open AlgebraicAnalysis
18 open AlgebraicAnalysis.OreDivision
19 
20 noncomputable section
21 
22 variable {B : Type*} [Ring B]
23 
24 lemma derivation_one (D : OreDivisionDerivation B) : D 1 = 0 := by
25   have h := D.leibniz 1 1
26   simp only [one_mul, mul_one] at h
27   symm
28   calc
29     0 = D 1 - D 1 := (sub_self _).symm
30     _ = (D 1 + D 1) - D 1 := by rw [← h]
31     _ = D 1 := by abel
32 
33 /-- Apply the coefficient derivation to every coefficient. -/
34 def coefficientDerivation (D : OreDivisionDerivation B) :
35     Polynomial B →+ Polynomial B where
36   toFun p := p.sum fun i b => monomial i (D b)
37   map_zero' := by simp [Polynomial.sum_def]
38   map_add' p q := by
39     change (p + q).sum (fun i b => monomial i (D b)) =
40       p.sum (fun i b => monomial i (D b)) +
41         q.sum (fun i b => monomial i (D b))
42     apply Polynomial.sum_add_index
43     · intro i
44       simp [D.map_zero]
45     · intro i a b
46       simp [D.map_add]
47 
48 @[simp] lemma coefficientDerivation_monomial
49     (D : OreDivisionDerivation B) (i : ℕ) (b : B) :
50     coefficientDerivation D (monomial i b) = monomial i (D b) := by
51   by_cases hb : b = 0
52   · subst b
53     simp [D.map_zero]
54   · simp [coefficientDerivation, hb, D.map_zero]
55 
56 @[simp] lemma coefficientDerivation_C_mul
57     (D : OreDivisionDerivation B) (b : B) (p : Polynomial B) :
58     coefficientDerivation D (C b * p) =
59       C b * coefficientDerivation D p + C (D b) * p := by
60   induction p using Polynomial.induction_on' with
61   | add p q hp hq =>
62       simp [map_add, hp, hq, mul_add, add_mul, add_assoc, add_left_comm,
63         add_comm]
64   | monomial n a =>
65       simp [D.leibniz, mul_add, add_mul, mul_assoc]
66 
67 /-- Coefficients act by ordinary left multiplication. -/
68 def coefficientLeft : B →+* AddMonoid.End (Polynomial B) where
69   toFun b :=
70     { toFun := fun p => C b * p
71       map_zero' := by simp
72       map_add' := by intro p q; simp [mul_add] }
73   map_one' := by
74     apply AddMonoidHom.ext
75     intro p
76     change C (1 : B) * p = p
77     simp
78   map_mul' b c := by
79     apply AddMonoidHom.ext
80     intro p
81     change C (b * c) * p = C b * (C c * p)
82     simp [mul_assoc]
83   map_zero' := by
84     apply AddMonoidHom.ext
85     intro p
86     change C (0 : B) * p = 0
87     simp
88   map_add' b c := by
89     apply AddMonoidHom.ext
90     intro p
91     change C (b + c) * p = C b * p + C c * p
92     simp [add_mul]
93 
94 /-- Left multiplication by the Ore variable on normal forms. -/
95 def leftOreShift (D : OreDivisionDerivation B) :
96     AddMonoid.End (Polynomial B) where
97   toFun p := p * X + coefficientDerivation D p
98   map_zero' := by simp
99   map_add' p q := by
100     simp only [add_mul, map_add]
101     abel
102 
103 /-- The faithful left-regular representation of the one-variable Ore model. -/
104 def faithfulAmbient (D : OreDivisionDerivation B) :
105     OreAmbient B (AddMonoid.End (Polynomial B)) D where
106   embed := coefficientLeft
107   x := leftOreShift D
108   relation := by
109     intro b
110     apply AddMonoidHom.ext
111     intro p
112     change (C b * p) * X + coefficientDerivation D (C b * p) =
113       C b * (p * X + coefficientDerivation D p) + C (D b) * p
114     rw [coefficientDerivation_C_mul]
115     noncomm_ring
116 
117 @[simp] lemma coefficientDerivation_X_pow
118     (D : OreDivisionDerivation B) (n : ℕ) :
119     coefficientDerivation D (X ^ n) = 0 := by
120   rw [Polynomial.X_pow_eq_monomial, coefficientDerivation_monomial,
121     derivation_one, monomial_zero_right]
122 
123 @[simp] lemma leftOreShift_X_pow (D : OreDivisionDerivation B) (n : ℕ) :
124     leftOreShift D (X ^ n) = X ^ (n + 1) := by
125   change X ^ n * X + coefficientDerivation D (X ^ n) = X ^ (n + 1)
126   rw [coefficientDerivation_X_pow, add_zero, pow_succ]
127 
128 lemma leftOreShift_pow_apply_one (D : OreDivisionDerivation B) (n : ℕ) :
129     ((leftOreShift D) ^ n) (1 : Polynomial B) = X ^ n := by
130   induction n with
131   | zero => simp
132   | succ n ih =>
133       rw [pow_succ']
134       change leftOreShift D (((leftOreShift D) ^ n) 1) = X ^ (n + 1)
135       rw [ih]
136       exact leftOreShift_X_pow D n
137 
138 lemma faithful_eval_apply_one (D : OreDivisionDerivation B)
139     (p : Polynomial B) :
140     OreAmbient.eval D (faithfulAmbient D) p (1 : Polynomial B) = p := by
141   rw [OreAmbient.eval]
142   change (p.sum fun i b =>
143     coefficientLeft b * (leftOreShift D) ^ i) 1 = p
144   rw [Polynomial.sum_def]
145   calc
146     (∑ n ∈ p.support,
147         coefficientLeft (p.coeff n) * (leftOreShift D) ^ n) 1 =
148         (∑ n ∈ p.support,
149           ⇑(coefficientLeft (p.coeff n) * (leftOreShift D) ^ n)) 1 := by
150       exact congrFun
151         (AddMonoidHom.coe_finsetSum
152           (fun n => coefficientLeft (p.coeff n) * (leftOreShift D) ^ n)
153           p.support) (1 : Polynomial B)
154     _ = ∑ n ∈ p.support,
155         (coefficientLeft (p.coeff n) * (leftOreShift D) ^ n) 1 := by
156       exact Finset.sum_apply (1 : Polynomial B) p.support
157         (fun n => ⇑(coefficientLeft (p.coeff n) * (leftOreShift D) ^ n))
158     _ = ∑ n ∈ p.support,
159         C (p.coeff n) * (((leftOreShift D) ^ n) 1) := by rfl
160     _ = p := by
161       simp_rw [leftOreShift_pow_apply_one]
162       simpa only [Polynomial.sum_def] using Polynomial.sum_C_mul_X_pow_eq p
163 
164 theorem faithful_eval_injective (D : OreDivisionDerivation B) :
165     Function.Injective (OreAmbient.eval D (faithfulAmbient D)) := by
166   intro p q hpq
167   have h := DFunLike.congr_fun hpq (1 : Polynomial B)
168   simpa [faithful_eval_apply_one] using h
169 
170 lemma faithful_eval_one (D : OreDivisionDerivation B) :
171     OreAmbient.eval D (faithfulAmbient D) (1 : Polynomial B) = 1 := by
172   rw [show (1 : Polynomial B) = C (1 : B) by simp, OreAmbient.eval]
173   rw [Polynomial.sum_C_index]
174   · simp [faithfulAmbient]
175   · simp [faithfulAmbient]
176 
177 lemma faithful_eval_C (D : OreDivisionDerivation B) (b : B) :
178     OreAmbient.eval D (faithfulAmbient D) (C b) = coefficientLeft b := by
179   rw [OreAmbient.eval, Polynomial.sum_C_index]
180   · simp [faithfulAmbient]
181   · simp [faithfulAmbient]
182 
183 lemma faithful_eval_X (D : OreDivisionDerivation B) :
184     OreAmbient.eval D (faithfulAmbient D) X = leftOreShift D := by
185   rw [← Polynomial.monomial_one_one_eq_X]
186   rw [OreAmbient.eval_monomial]
187   simp [faithfulAmbient]
188 
189 /-- Associativity of the derivation-corrected normal-form product. -/
190 theorem rightMul_assoc_of_ring
191     (D : OreDivisionDerivation B) (p q r : Polynomial B) :
192     rightMul D (rightMul D p q) r =
193       rightMul D p (rightMul D q r) := by
194   apply faithful_eval_injective D
195   rw [OreAmbient.eval_rightMul, OreAmbient.eval_rightMul,
196     OreAmbient.eval_rightMul, OreAmbient.eval_rightMul]
197   exact mul_assoc _ _ _
198 
199 /-! ## The concrete associative Ore ring -/
200 
201 /-- The image of the faithful normal-form representation. -/
202 def faithfulRange (D : OreDivisionDerivation B) :
203     Subring (AddMonoid.End (Polynomial B)) where
204   carrier := Set.range (OreAmbient.eval D (faithfulAmbient D))
205   zero_mem' := ⟨0, OreAmbient.eval_zero D (faithfulAmbient D)⟩
206   one_mem' := ⟨1, faithful_eval_one D⟩
207   add_mem' := by
208     rintro _ _ ⟨p, rfl⟩ ⟨q, rfl⟩
209     exact ⟨p + q, OreAmbient.eval_add D (faithfulAmbient D) p q⟩
210   neg_mem' := by
211     rintro _ ⟨p, rfl⟩
212     exact ⟨-p, map_neg (OreAmbient.evalAddHom D (faithfulAmbient D)) p⟩
213   mul_mem' := by
214     rintro _ _ ⟨p, rfl⟩ ⟨q, rfl⟩
215     exact ⟨rightMul D p q, OreAmbient.eval_rightMul D (faithfulAmbient D) p q⟩
216 
217 /-- The one-variable derivation Ore extension, represented faithfully by its
218 left-regular action on normal polynomials. -/
219 abbrev NormalOre (D : OreDivisionDerivation B) := faithfulRange D
220 
221 /-- A coefficient-left polynomial regarded as an element of the Ore ring. -/
222 def normalForm (D : OreDivisionDerivation B) (p : Polynomial B) : NormalOre D :=
223   ⟨OreAmbient.eval D (faithfulAmbient D) p, ⟨p, rfl⟩⟩
224 
225 @[simp] theorem normalForm_injective (D : OreDivisionDerivation B) :
226     Function.Injective (normalForm D) := by
227   intro p q h
228   apply faithful_eval_injective D
229   exact Subtype.ext_iff.mp h
230 
231 theorem normalForm_surjective (D : OreDivisionDerivation B) :
232     Function.Surjective (normalForm D) := by
233   rintro ⟨_, p, rfl⟩
234   exact ⟨p, rfl⟩
235 
236 @[simp] theorem normalForm_zero (D : OreDivisionDerivation B) :
237     normalForm D 0 = 0 := by
238   apply Subtype.ext
239   exact OreAmbient.eval_zero D (faithfulAmbient D)
240 
241 @[simp] theorem normalForm_one (D : OreDivisionDerivation B) :
242     normalForm D 1 = 1 := by
243   apply Subtype.ext
244   exact faithful_eval_one D
245 
246 @[simp] theorem normalForm_add (D : OreDivisionDerivation B)
247     (p q : Polynomial B) :
248     normalForm D (p + q) = normalForm D p + normalForm D q := by
249   apply Subtype.ext
250   exact OreAmbient.eval_add D (faithfulAmbient D) p q
251 
252 @[simp] theorem normalForm_neg (D : OreDivisionDerivation B)
253     (p : Polynomial B) : normalForm D (-p) = -normalForm D p := by
254   apply Subtype.ext
255   exact map_neg (OreAmbient.evalAddHom D (faithfulAmbient D)) p
256 
257 @[simp] theorem normalForm_mul (D : OreDivisionDerivation B)
258     (p q : Polynomial B) :
259     normalForm D (rightMul D p q) = normalForm D p * normalForm D q := by
260   apply Subtype.ext
261   exact OreAmbient.eval_rightMul D (faithfulAmbient D) p q
262 
263 /-- The normal-form map as an additive homomorphism. -/
264 def normalFormAddHom (D : OreDivisionDerivation B) :
265     Polynomial B →+ NormalOre D where
266   toFun := normalForm D
267   map_zero' := normalForm_zero D
268   map_add' := normalForm_add D
269 
270 /-- Normal forms are additively equivalent to ordinary coefficient-left
271 polynomials. -/
272 def normalFormAddEquiv (D : OreDivisionDerivation B) :
273     Polynomial B ≃+ NormalOre D :=
274   AddEquiv.ofBijective (normalFormAddHom D)
275     ⟨normalForm_injective D, normalForm_surjective D⟩
276 
277 /-- The canonical coefficient embedding. -/
278 def normalCoefficient (D : OreDivisionDerivation B) : B →+* NormalOre D :=
279   coefficientLeft.codRestrict (faithfulRange D) fun b => by
280     exact ⟨C b, faithful_eval_C D b⟩
281 
282 @[simp] theorem normalForm_C (D : OreDivisionDerivation B) (b : B) :
283     normalForm D (C b) = normalCoefficient D b := by
284   apply Subtype.ext
285   exact faithful_eval_C D b
286 
287 /-- The canonical Ore variable. -/
288 def normalVariable (D : OreDivisionDerivation B) : NormalOre D :=
289   normalForm D X
290 
291 theorem normalForm_monomial (D : OreDivisionDerivation B) (n : ℕ) (b : B) :
292     normalForm D (monomial n b) =
293       normalCoefficient D b * normalVariable D ^ n := by
294   apply Subtype.ext
295   change OreAmbient.eval D (faithfulAmbient D) (monomial n b) =
296     coefficientLeft b * OreAmbient.eval D (faithfulAmbient D) X ^ n
297   rw [OreAmbient.eval_monomial, faithful_eval_X]
298   rfl
299 
300 /-- The defining derivation relation `X b = b X + D(b)`. -/
301 theorem normalVariable_mul_coefficient (D : OreDivisionDerivation B) (b : B) :
302     normalVariable D * normalCoefficient D b =
303       normalCoefficient D b * normalVariable D + normalCoefficient D (D b) := by
304   apply Subtype.ext
305   change
306     OreAmbient.eval D (faithfulAmbient D) X * coefficientLeft b =
307       coefficientLeft b * OreAmbient.eval D (faithfulAmbient D) X +
308         coefficientLeft (D b)
309   rw [faithful_eval_X]
310   exact (faithfulAmbient D).relation b
311 
312 /-! ## Universal property -/
313 
314 variable {A : Type*} [Ring A]
315 
316 lemma ambient_eval_one (D : OreDivisionDerivation B) (O : OreAmbient B A D) :
317     OreAmbient.eval D O (1 : Polynomial B) = 1 := by
318   rw [show (1 : Polynomial B) = C (1 : B) by simp, OreAmbient.eval]
319   rw [Polynomial.sum_C_index]
320   · simp
321   · simp
322 
323 lemma ambient_eval_C (D : OreDivisionDerivation B) (O : OreAmbient B A D)
324     (b : B) : OreAmbient.eval D O (C b) = O.embed b := by
325   rw [OreAmbient.eval, Polynomial.sum_C_index]
326   · simp
327   · simp
328 
329 lemma ambient_eval_X (D : OreDivisionDerivation B) (O : OreAmbient B A D) :
330     OreAmbient.eval D O X = O.x := by
331   rw [← Polynomial.monomial_one_one_eq_X, OreAmbient.eval_monomial]
332   simp
333 
334 /-- The universal map out of the concrete Ore ring. -/
335 def oreLift (D : OreDivisionDerivation B) (O : OreAmbient B A D) :
336     NormalOre D →+* A where
337   toFun z := OreAmbient.eval D O ((normalFormAddEquiv D).symm z)
338   map_zero' := by
339     change OreAmbient.eval D O ((normalFormAddEquiv D).symm 0) = 0
340     rw [(normalFormAddEquiv D).symm.map_zero]
341     exact OreAmbient.eval_zero D O
342   map_one' := by
343     have h : (normalFormAddEquiv D).symm (1 : NormalOre D) = 1 := by
344       apply (normalFormAddEquiv D).injective
345       simp [normalFormAddEquiv, normalFormAddHom]
346     change OreAmbient.eval D O ((normalFormAddEquiv D).symm 1) = 1
347     rw [h]
348     exact ambient_eval_one D O
349   map_add' z w := by
350     change OreAmbient.eval D O ((normalFormAddEquiv D).symm (z + w)) =
351       OreAmbient.eval D O ((normalFormAddEquiv D).symm z) +
352         OreAmbient.eval D O ((normalFormAddEquiv D).symm w)
353     have h := (normalFormAddEquiv D).symm.toAddHom.map_add z w
354     change (normalFormAddEquiv D).symm (z + w) =
355       (normalFormAddEquiv D).symm z + (normalFormAddEquiv D).symm w at h
356     rw [h]
357     exact OreAmbient.eval_add D O _ _
358   map_mul' z w := by
359     let p := (normalFormAddEquiv D).symm z
360     let q := (normalFormAddEquiv D).symm w
361     have hz : normalForm D p = z := by
362       change (normalFormAddEquiv D) p = z
363       exact (normalFormAddEquiv D).apply_symm_apply z
364     have hw : normalForm D q = w := by
365       change (normalFormAddEquiv D) q = w
366       exact (normalFormAddEquiv D).apply_symm_apply w
367     have hpq : (normalFormAddEquiv D).symm (z * w) = rightMul D p q := by
368       apply (normalFormAddEquiv D).injective
369       rw [(normalFormAddEquiv D).apply_symm_apply]
370       symm
371       change normalForm D (rightMul D p q) = z * w
372       rw [normalForm_mul, hz, hw]
373     change OreAmbient.eval D O ((normalFormAddEquiv D).symm (z * w)) =
374       OreAmbient.eval D O p * OreAmbient.eval D O q
375     rw [hpq]
376     exact OreAmbient.eval_rightMul D O p q
377 
378 @[simp] theorem oreLift_normalForm (D : OreDivisionDerivation B)
379     (O : OreAmbient B A D) (p : Polynomial B) :
380     oreLift D O (normalForm D p) = OreAmbient.eval D O p := by
381   change OreAmbient.eval D O ((normalFormAddEquiv D).symm (normalForm D p)) = _
382   rw [show normalForm D p = (normalFormAddEquiv D) p by rfl]
383   rw [(normalFormAddEquiv D).symm_apply_apply]
384 
385 @[simp] theorem oreLift_coefficient (D : OreDivisionDerivation B)
386     (O : OreAmbient B A D) (b : B) :
387     oreLift D O (normalCoefficient D b) = O.embed b := by
388   rw [← normalForm_C, oreLift_normalForm, ambient_eval_C]
389 
390 @[simp] theorem oreLift_variable (D : OreDivisionDerivation B)
391     (O : OreAmbient B A D) : oreLift D O (normalVariable D) = O.x := by
392   rw [normalVariable, oreLift_normalForm, ambient_eval_X]
393 
394 /-- A ring map out of `NormalOre D` is uniquely determined by the coefficient
395 map and the image of the Ore variable. -/
396 theorem oreLift_unique (D : OreDivisionDerivation B) (O : OreAmbient B A D)
397     (g : NormalOre D →+* A)
398     (hCoefficient : ∀ b, g (normalCoefficient D b) = O.embed b)
399     (hVariable : g (normalVariable D) = O.x) :
400     g = oreLift D O := by
401   ext z
402   rcases normalForm_surjective D z with ⟨p, rfl⟩
403   rw [oreLift_normalForm]
404   induction p using Polynomial.induction_on' with
405   | add p q hp hq =>
406       rw [normalForm_add, g.map_add, OreAmbient.eval_add, hp, hq]
407   | monomial n b =>
408       rw [normalForm_monomial, g.map_mul, g.map_pow, hCoefficient, hVariable,
409         OreAmbient.eval_monomial]
410 
411 #print axioms rightMul_assoc_of_ring
412 #print axioms normalVariable_mul_coefficient
413 #print axioms oreLift
414 #print axioms oreLift_unique
415 
416 end
417 end AlgebraicAnalysis.OreAssociativity
418