AlgebraicAnalysis/Ore/RightPBW.lean

AlgebraicAnalysis library · bbbbf3fc358ca8100b158cec4cf47f336ab70163

1 module
2 public import AlgebraicAnalysis.Ore.RightHilbertBasis
3 public import Mathlib.LinearAlgebra.Basis.Basic
4 public import Mathlib.LinearAlgebra.Finsupp.LinearCombination
5 
6 @[expose] public section
7 
8 /-!
9 # Right-coefficient PBW data for one derivation-Ore stage
10 
11 The checked Ore interface gives the opposite-ring right action and the
12 triangular coefficient identities.  We prove directly that the candidate
13 monomials form a genuine right basis; the proof uses finite-support maximal
14 degree induction, so no freeness or flatness assumption is introduced.
15 -/
16 
17 namespace AlgebraicAnalysis.OreRightPBW
18 
19 open Polynomial
20 open Module
21 open AlgebraicAnalysis
22 open AlgebraicAnalysis.OreDivision
23 open AlgebraicAnalysis.OreAssociativity
24 open AlgebraicAnalysis.OreRightQuotient
25 open AlgebraicAnalysis.OreDerivationRightHilbertBasis
26 
27 noncomputable section
28 
29 universe u
30 
31 variable {B : Type u} [Ring B]
32 
33 /-- The candidate right-coefficient PBW monomial of order `n`. -/
34 def rightPBWMonomial (D : OreDivisionDerivation B) (n : ℕ) : NormalOre D :=
35   normalForm D (Polynomial.X ^ n)
36 
37 /-- The finitely supported right-coefficient combination of PBW monomials. -/
38 def rightPBWCombination (D : OreDivisionDerivation B) :
39     (ℕ →₀ Bᵐᵒᵖ) →ₗ[Bᵐᵒᵖ] NormalOre D :=
40   Finsupp.linearCombination Bᵐᵒᵖ (rightPBWMonomial D)
41 
42 lemma rightPBWCombination_single (D : OreDivisionDerivation B)
43     (n : ℕ) (b : Bᵐᵒᵖ) :
44     rightPBWCombination D (Finsupp.single n b) =
45       b • rightPBWMonomial D n := by
46   simp [rightPBWCombination]
47 
48 lemma rightPBWCombination_term_as_normalForm
49     (D : OreDivisionDerivation B) (n : ℕ) (b : Bᵐᵒᵖ) :
50     b • rightPBWMonomial D n =
51       normalForm D (OreDivision.rightMul D (Polynomial.X ^ n)
52         (Polynomial.C b.unop)) := by
53   rw [rightPBWMonomial, normalOre_op_smul_def, ← normalForm_C,
54     ← normalForm_mul]
55 
56 @[nolint unusedArguments]
57 lemma rightPBWCombination_finsupp_as_normalForm
58     [Nontrivial B] (D : OreDivisionDerivation B) (c : ℕ →₀ Bᵐᵒᵖ) :
59     rightPBWCombination D c =
60       normalForm D
61         (c.sum fun n b => OreDivision.rightMul D (Polynomial.X ^ n)
62           (Polynomial.C b.unop)) := by
63   rw [rightPBWCombination, Finsupp.linearCombination_apply]
64   rw [Finsupp.sum]
65   rw [Finsupp.sum]
66   change _ = normalFormAddHom D
67     (∑ a ∈ c.support,
68       OreDivision.rightMul D (Polynomial.X ^ a)
69         (Polynomial.C (c a).unop))
70   rw [map_sum]
71   apply Finset.sum_congr rfl
72   intro n b
73   exact rightPBWCombination_term_as_normalForm D n (c n)
74 
75 lemma rightPBWCombination_eq_zero
76     [Nontrivial B] (D : OreDivisionDerivation B) (c : ℕ →₀ Bᵐᵒᵖ)
77     (hc : rightPBWCombination D c = 0) : c = 0 := by
78   classical
79   by_contra hcz
80   have hne : c.support.Nonempty := Finsupp.support_nonempty_iff.mpr hcz
81   let m : ℕ := c.support.max' hne
82   have hm : m ∈ c.support := c.support.max'_mem hne
83   have hle : ∀ a ∈ c.support, a ≤ m := by
84     intro a ha
85     exact Finset.le_max' c.support a ha
86   have hpoly :
87       c.sum (fun n b => OreDivision.rightMul D (Polynomial.X ^ n)
88         (Polynomial.C b.unop)) = 0 := by
89     have hnf :
90         normalForm D
91             (c.sum (fun n b => OreDivision.rightMul D (Polynomial.X ^ n)
92               (Polynomial.C b.unop))) = 0 := by
93       rw [← rightPBWCombination_finsupp_as_normalForm D c]
94       exact hc
95     apply normalForm_injective D
96     simpa using hnf
97   have hcoeff := congrArg (fun p : Polynomial B => p.coeff m) hpoly
98   simp only [Finsupp.sum] at hcoeff
99   dsimp at hcoeff
100   rw [← Polynomial.lcoeff_apply, map_sum] at hcoeff
101   have hterm : ∀ a ∈ c.support,
102       (OreDivision.rightMul D (Polynomial.X ^ a)
103         (Polynomial.C (c a).unop)).coeff m =
104         if a = m then (c a).unop else 0 := by
105     intro a ha
106     have ha_le := hle a ha
107     have hdeg : (Polynomial.X ^ a : Polynomial B).degree ≤
108         (m : WithBot ℕ) := by
109       rw [Polynomial.degree_X_pow]
110       exact_mod_cast ha_le
111     have htop := rightMul_coeff_C_of_degree_le D
112       (Polynomial.X ^ a) (c a).unop m hdeg
113     by_cases ham : a = m
114     · subst a
115       simpa using htop
116     · rw [htop]
117       have hcoeffX : (Polynomial.X ^ a : Polynomial B).coeff m = 0 := by
118         rw [Polynomial.coeff_X_pow]
119         split_ifs with h
120         · exact False.elim (ham h.symm)
121         · rfl
122       rw [hcoeffX, zero_mul]
123       simp [ham]
124   rw [Finset.sum_eq_single m (fun a ha hneam => by
125     exact hterm a ha |>.trans (by simp [hneam]))
126     (by intro hnot; exact False.elim (hnot hm))] at hcoeff
127   have hcm' :
128       (OreDivision.rightMul D (Polynomial.X ^ m)
129         (Polynomial.C (c m).unop)).coeff m = 0 := by
130     simpa [Polynomial.lcoeff_apply] using hcoeff
131   have hcm : c m = 0 := by
132     have htop := hterm m hm
133     rw [if_pos rfl] at htop
134     have hcm'' : (c m).unop = 0 := by simpa [htop] using hcm'
135     exact MulOpposite.opEquiv.symm.injective hcm''
136   exact (Finsupp.mem_support_iff.mp hm) hcm
137 
138 theorem rightPBWCombination_injective
139     [Nontrivial B] (D : OreDivisionDerivation B) :
140     Function.Injective (rightPBWCombination D) := by
141   intro c d h
142   have hz : rightPBWCombination D (c - d) = 0 := by
143     rw [map_sub, h, sub_self]
144   have hcd := rightPBWCombination_eq_zero D (c - d) hz
145   exact sub_eq_zero.mp hcd
146 
147 lemma rightPBWMonomial_mem_span (D : OreDivisionDerivation B)
148     (b : B) (n : ℕ) :
149     normalForm D (Polynomial.monomial n b) ∈
150       Submodule.span Bᵐᵒᵖ (Set.range (rightPBWMonomial D)) := by
151   rw [normalForm_monomial_reverse]
152   apply Submodule.sum_mem
153   intro ij hij
154   rw [← Nat.cast_smul_eq_nsmul Bᵐᵒᵖ]
155   apply Submodule.smul_mem
156   have hpow : rightPBWMonomial D ij.2 ∈
157       Submodule.span Bᵐᵒᵖ (Set.range (rightPBWMonomial D)) := by
158     apply Submodule.subset_span
159     exact ⟨ij.2, rfl⟩
160   have hscalar : (MulOpposite.op ((D^[ij.1]) b)) •
161       rightPBWMonomial D ij.2 ∈
162       Submodule.span Bᵐᵒᵖ (Set.range (rightPBWMonomial D)) :=
163     Submodule.smul_mem _ _ hpow
164   by_cases heven : Even ij.1
165   · rw [heven.neg_one_pow]
166     simpa only [one_mul, rightPBWMonomial] using hscalar
167   · have hodd : Odd ij.1 := Nat.not_even_iff_odd.mp heven
168     rw [hodd.neg_one_pow]
169     simpa only [neg_one_mul, rightPBWMonomial] using
170       (Submodule.span Bᵐᵒᵖ (Set.range (rightPBWMonomial D))).neg_mem hscalar
171 
172 theorem rightPBW_span_eq_top (D : OreDivisionDerivation B) :
173     Submodule.span Bᵐᵒᵖ (Set.range (rightPBWMonomial D)) = ⊤ := by
174   apply top_unique
175   intro z hz
176   obtain ⟨p, rfl⟩ := normalForm_surjective D z
177   change normalFormAddHom D p ∈ _
178   rw [← Polynomial.sum_monomial_eq p, Polynomial.sum_def,
179     map_sum (normalFormAddHom D)]
180   apply Submodule.sum_mem
181   intro n hn
182   exact rightPBWMonomial_mem_span D (p.coeff n) n
183 
184 theorem rightOrePBW_linearIndependent
185     [Nontrivial B] (D : OreDivisionDerivation B) :
186     LinearIndependent Bᵐᵒᵖ (rightPBWMonomial D) :=
187   (linearIndependent_iff_injective_finsuppLinearCombination).2
188     (rightPBWCombination_injective D)
189 
190 /-- The right PBW basis of a one-stage derivation-Ore extension. -/
191 def rightOrePBWBasis [Nontrivial B] (D : OreDivisionDerivation B) :
192     Basis ℕ Bᵐᵒᵖ (NormalOre D) :=
193   Basis.mk (rightOrePBW_linearIndependent D)
194     (rightPBW_span_eq_top D).ge
195 
196 @[simp] theorem rightOrePBWBasis_apply [Nontrivial B]
197     (D : OreDivisionDerivation B) (n : ℕ) :
198     rightOrePBWBasis D n = rightPBWMonomial D n := by
199   exact Basis.mk_apply _ _ _
200 
201 theorem rightOrePBWBasis_repr_symm_single [Nontrivial B]
202     (D : OreDivisionDerivation B) (n : ℕ) (b : Bᵐᵒᵖ) :
203     (rightOrePBWBasis D).repr.symm (Finsupp.single n b) =
204       b • rightPBWMonomial D n := by
205   rw [(rightOrePBWBasis D).repr_symm_single, rightOrePBWBasis_apply]
206 
207 @[simp, nolint simpNF] theorem rightPBWMonomial_zero (D : OreDivisionDerivation B) :
208     rightPBWMonomial D 0 = 1 := by
209   simp [rightPBWMonomial, normalForm_one]
210 
211 @[simp, nolint simpNF] theorem rightPBWMonomial_op_smul
212     (D : OreDivisionDerivation B) (b : Bᵐᵒᵖ) (n : ℕ) :
213     b • rightPBWMonomial D n =
214       normalForm D (Polynomial.X ^ n) * normalCoefficient D b.unop := by
215   exact normalOre_op_smul_def D b (rightPBWMonomial D n)
216 
217 /-- The finite window generated by the candidate right PBW monomials. -/
218 def rightPBWWindow (D : OreDivisionDerivation B) (n : ℕ) :
219     Submodule Bᵐᵒᵖ (NormalOre D) :=
220   Submodule.span Bᵐᵒᵖ
221     (Set.range fun j : Fin n => rightPBWMonomial D (j : ℕ))
222 
223 theorem normalForm_mem_rightPBWWindow_of_degree_lt
224     (D : OreDivisionDerivation B) (p : Polynomial B) (n : ℕ)
225     (hp : p = 0 ∨ p.natDegree < n) :
226     normalForm D p ∈ rightPBWWindow D n := by
227   simpa [rightPBWWindow, rightPBWMonomial, rightCoefficientWindow] using
228     (normalForm_mem_rightCoefficientWindow_of_degree_lt D p n hp)
229 
230 @[nolint unusedArguments]
231 theorem rightPBWWindow_finite
232     [Nontrivial B] (D : OreDivisionDerivation B) (n : ℕ) :
233     Module.Finite Bᵐᵒᵖ (rightPBWWindow D n) := by
234   exact Module.Finite.span_of_finite Bᵐᵒᵖ
235     (Set.finite_range (fun j : Fin n => rightPBWMonomial D (j : ℕ)))
236 
237 @[simp, nolint simpNF] theorem rightPBWMonomial_apply (D : OreDivisionDerivation B) (n : ℕ) :
238     rightPBWMonomial D n = normalForm D (Polynomial.X ^ n) := rfl
239 
240 /-- Right multiplication by a PBW monomial has the expected top coefficient.
241 This is the triangular input for an eventual basis proof. -/
242 theorem rightMul_Xpow_top_coefficient
243     [Nontrivial B] (D : OreDivisionDerivation B) (p : Polynomial B)
244     (n j : ℕ) (hp : p.degree ≤ (n : WithBot ℕ)) :
245     (rightMul D p (Polynomial.X ^ j)).coeff (n + j) = p.coeff n := by
246   exact rightMul_Xpow_coeff_of_degree_le D p n j hp
247 
248 theorem rightMul_Xpow_degree_le
249     [Nontrivial B]
250     (D : OreDivisionDerivation B) (p : Polynomial B) (j : ℕ) :
251       (rightMul D p (Polynomial.X ^ j)).degree ≤
252       (p.natDegree + j : WithBot ℕ) := by
253   have h := rightMul_degree_le D p (Polynomial.X ^ j)
254   have hX : (Polynomial.X ^ j : Polynomial B).natDegree = j := by
255     exact Polynomial.natDegree_X_pow _
256   rw [hX] at h
257   exact h
258 
259 /-! ## Monic principal quotients -/
260 
261 /-- A vector in the first `N` right-PBW slots has a coefficient-left normal
262 form of degree strictly less than `N`.  This is the converse, at the level
263 needed for division, of `normalForm_mem_rightPBWWindow_of_degree_lt`. -/
264 theorem exists_lowDegreePolynomial_eq_of_mem_rightPBWWindow
265     [Nontrivial B] (D : OreDivisionDerivation B) (N : ℕ)
266     {z : NormalOre D} (hz : z ∈ rightPBWWindow D N) :
267     ∃ r : Polynomial B,
268       (r = 0 ∨ r.natDegree < N) ∧ normalForm D r = z := by
269   change z ∈ Submodule.span Bᵐᵒᵖ
270     (Set.range fun j : Fin N ↦ normalForm D (Polynomial.X ^ (j : ℕ))) at hz
271   obtain ⟨c, hc⟩ := (Submodule.mem_span_range_iff_exists_fun Bᵐᵒᵖ).mp hz
272   let r : Polynomial B := ∑ j : Fin N,
273     rightMul D (Polynomial.X ^ (j : ℕ)) (Polynomial.C (c j).unop)
274   refine ⟨r, ?_, ?_⟩
275   · by_cases hr : r = 0
276     · exact Or.inl hr
277     · exact Or.inr ((Polynomial.natDegree_lt_iff_degree_lt hr).mpr (by
278         rw [Polynomial.degree_lt_iff_coeff_zero]
279         intro m hm
280         change (Polynomial.lcoeff B m) (∑ j : Fin N,
281           rightMul D (Polynomial.X ^ (j : ℕ))
282             (Polynomial.C (c j).unop)) = 0
283         rw [map_sum]
284         apply Finset.sum_eq_zero
285         intro j hj
286         apply Polynomial.coeff_eq_zero_of_degree_lt
287         have hdeg := rightMul_degree_le D
288           (Polynomial.X ^ (j : ℕ)) (Polynomial.C (c j).unop)
289         rw [Polynomial.natDegree_X_pow, Polynomial.natDegree_C] at hdeg
290         exact lt_of_le_of_lt hdeg (by exact_mod_cast j.isLt.trans_le hm)))
291   · change normalFormAddHom D (∑ j : Fin N,
292       rightMul D (Polynomial.X ^ (j : ℕ))
293         (Polynomial.C (c j).unop)) = z
294     rw [map_sum, ← hc]
295     apply Finset.sum_congr rfl
296     intro j hj
297     change normalForm D (rightMul D (Polynomial.X ^ (j : ℕ))
298       (Polynomial.C (c j).unop)) = _
299     rw [normalForm_mul]
300     simp only [normalForm_C, normalOre_op_smul_def]
301 
302 /-- Monic right multiples and the finite right-PBW remainder window are exact
303 complements.  Equivalently, monic right division is both exhaustive and
304 unique as a decomposition over the opposite coefficient ring. -/
305 theorem monicPrincipalRightIdeal_isCompl_rightPBWWindow
306     [Nontrivial B] (D : OreDivisionDerivation B)
307     (H : Polynomial B) (hH : H.Monic) :
308     IsCompl (twoGeneratorCoeffSubmodule D H 0)
309       (rightPBWWindow D H.natDegree) := by
310   apply IsCompl.of_le
311   · intro z hz
312     have hzI := hz.1
313     have hzW := hz.2
314     change z ∈ twoGeneratorRightIdeal D H 0 at hzI
315     rw [twoGeneratorRightIdeal, Submodule.mem_span_pair] at hzI
316     obtain ⟨a, b, hab⟩ := hzI
317     have hzeroTerm : b • normalForm D (0 : Polynomial B) = 0 := by
318       rw [normalForm_zero, smul_zero]
319     rw [hzeroTerm, add_zero] at hab
320     change normalForm D H * a.unop = z at hab
321     obtain ⟨q, hq⟩ := normalForm_surjective D a.unop
322     obtain ⟨r, hrsmall, hrz⟩ :=
323       exists_lowDegreePolynomial_eq_of_mem_rightPBWWindow D H.natDegree hzW
324     have hdecomp : r = rightMul D H q + 0 := by
325       apply normalForm_injective D
326       rw [normalForm_add, normalForm_zero, normalForm_mul, add_zero, hq]
327       exact hrz.trans hab.symm
328     have hzero := (right_division_unique D H r q 0 0 r hH
329       hdecomp (by simp [rightMul_zero]) (Or.inl rfl) hrsmall).2
330     have hr0 : r = 0 := hzero.symm
331     rw [← hrz, hr0, normalForm_zero]
332     exact Submodule.zero_mem _
333   · intro z hz
334     obtain ⟨p, rfl⟩ := normalForm_surjective D z
335     obtain ⟨q, r, hdecomp, hrsmall⟩ := right_division_exists D H p hH
336     rw [Submodule.mem_sup]
337     refine ⟨normalForm D (rightMul D H q),
338       normalForm_rightMul_H_mem_twoGeneratorCoeffSubmodule D H 0 q,
339       normalForm D r,
340       normalForm_mem_rightPBWWindow_of_degree_lt D r H.natDegree hrsmall,
341       ?_⟩
342     rw [← normalForm_add, ← hdecomp]
343 
344 /-- The basis of the finite right-PBW remainder window. -/
345 def rightPBWWindowBasis [Nontrivial B]
346     (D : OreDivisionDerivation B) (N : ℕ) :
347     Basis (Fin N) Bᵐᵒᵖ (rightPBWWindow D N) :=
348   Basis.span ((rightOrePBW_linearIndependent D).comp
349     (fun j : Fin N ↦ (j : ℕ)) Fin.val_injective)
350 
351 /-- A monic principal right quotient of a derivation-Ore extension is free of
352 rank `H.natDegree` over the opposite coefficient ring, with basis represented
353 by `1, X, …, X^(H.natDegree-1)`.  The `0` second generator is only a literal
354 encoding of the principal right ideal inside the existing quotient API. -/
355 def monicPrincipalRightQuotientBasis [Nontrivial B]
356     (D : OreDivisionDerivation B) (H : Polynomial B) (hH : H.Monic) :
357     Basis (Fin H.natDegree) Bᵐᵒᵖ (TwoGeneratorQuotient D H 0) :=
358   (rightPBWWindowBasis D H.natDegree).map
359     (Submodule.quotientEquivOfIsCompl
360       (twoGeneratorCoeffSubmodule D H 0)
361       (rightPBWWindow D H.natDegree)
362       (monicPrincipalRightIdeal_isCompl_rightPBWWindow D H hH)).symm
363 
364 @[simp] theorem monicPrincipalRightQuotientBasis_apply [Nontrivial B]
365     (D : OreDivisionDerivation B) (H : Polynomial B) (hH : H.Monic)
366     (j : Fin H.natDegree) :
367     monicPrincipalRightQuotientBasis D H hH j =
368       Submodule.Quotient.mk (normalForm D (Polynomial.X ^ (j : ℕ))) := by
369   rw [monicPrincipalRightQuotientBasis, Basis.map_apply,
370     Submodule.quotientEquivOfIsCompl_symm_apply]
371   congr 1
372   change (((rightPBWWindowBasis D H.natDegree) j :
373     rightPBWWindow D H.natDegree) : NormalOre D) =
374       normalForm D (Polynomial.X ^ (j : ℕ))
375   exact congrArg Subtype.val
376     (Basis.span_apply ((rightOrePBW_linearIndependent D).comp
377       (fun j : Fin H.natDegree ↦ (j : ℕ)) Fin.val_injective) j)
378 
379 #print axioms rightPBWMonomial_op_smul
380 #print axioms normalForm_mem_rightPBWWindow_of_degree_lt
381 #print axioms rightPBWWindow_finite
382 #print axioms rightMul_Xpow_top_coefficient
383 #print axioms monicPrincipalRightIdeal_isCompl_rightPBWWindow
384 #print axioms monicPrincipalRightQuotientBasis
385 #print axioms monicPrincipalRightQuotientBasis_apply
386 #print axioms rightPBWCombination_eq_zero
387 #print axioms rightPBWCombination_injective
388 #print axioms rightPBWMonomial_mem_span
389 #print axioms rightPBW_span_eq_top
390 #print axioms rightOrePBW_linearIndependent
391 #print axioms rightOrePBWBasis
392 #print axioms rightOrePBWBasis_repr_symm_single
393 
394 end
395 end AlgebraicAnalysis.OreRightPBW
396