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