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