AlgebraicAnalysis library · bbbbf3fc358ca8100b158cec4cf47f336ab70163
1 module 2 public import Mathlib.LinearAlgebra.Quotient.Defs 3 public import Mathlib.Algebra.Polynomial.BigOperators 4 public import Mathlib.Tactic.NoncommRing 5 6 @[expose] public section 7 8 /-! 9 # Right division in a coefficient-left derivation Ore model 10 11 This file is the next structural layer after `ore_derivation.lean`. It does 12 not identify a presented Weyl algebra with this model. It builds the finite 13 normal-form algebra needed for that identification: the normal form of 14 `x^i * b`, the right product of a normal polynomial by a monomial `b*x^j`, 15 and the leading-term fact which drives right division by a monic polynomial. 16 17 The coefficient ring is allowed to be noncommutative. No commutative 18 polynomial division theorem is used. 19 20 21 ## References and proof context 22 23 [Ore33] Øystein Ore, *Theory of Non-Commutative Polynomials*, Annals of Mathematics (2) 34 (1933), no. 3, 480–508. 24 https://doi.org/10.2307/1968173 25 26 Historical skew-polynomial context. This module implements the derivation case over possibly noncommutative coefficients. See docs/literature.md and docs/provenance.yaml. 27 -/ 28 29 namespace AlgebraicAnalysis 30 31 noncomputable section 32 33 /-- A derivation used to define a coefficient-left Ore normal form. -/ 34 structure OreDivisionDerivation (B : Type*) [Ring B] where 35 /-- The underlying additive derivation map. -/ 36 toFun : B → B 37 /-- The derivation preserves zero. -/ 38 map_zero' : toFun 0 = 0 39 /-- The derivation preserves addition. -/ 40 map_add' : ∀ a b, toFun (a + b) = toFun a + toFun b 41 /-- The Leibniz rule. -/ 42 leibniz' : ∀ a b, toFun (a * b) = a * toFun b + toFun a * b 43 44 instance {B : Type*} [Ring B] : CoeFun (OreDivisionDerivation B) (fun _ => B → B) := 45 ⟨OreDivisionDerivation.toFun⟩ 46 47 namespace OreDivisionDerivation 48 49 variable {B : Type*} [Ring B] (D : OreDivisionDerivation B) 50 51 @[simp] theorem map_zero : D 0 = 0 := D.map_zero' 52 53 @[simp] theorem map_add (a b : B) : D (a + b) = D a + D b := D.map_add' a b 54 55 @[simp] theorem leibniz (a b : B) : D (a * b) = a * D b + D a * b := D.leibniz' a b 56 57 lemma map_nsmul (a : B) (n : ℕ) : D (n • a) = n • D a := by 58 induction n with 59 | zero => simp 60 | succ n ih => simp only [succ_nsmul, map_add, ih] 61 62 end OreDivisionDerivation 63 64 namespace OreDivision 65 66 variable {B : Type*} [Ring B] (D : OreDivisionDerivation B) 67 68 /-- The coefficient-left normal form of `x^i*b` under `x*b=b*x+D(b)`. -/ 69 def push (b : B) (i : ℕ) : Polynomial B := 70 ∑ k ∈ Finset.range (i + 1), 71 Polynomial.monomial (i - k) (Nat.choose i k • (D^[k]) b) 72 73 lemma push_coeff (b : B) (i n : ℕ) : 74 (OreDivision.push D b i).coeff n = 75 ∑ k ∈ Finset.range (i + 1), 76 if i - k = n then Nat.choose i k • (D^[k]) b else 0 := by 77 simp [push, Polynomial.coeff_sum, Polynomial.coeff_monomial] 78 79 lemma push_degree_le (b : B) (i : ℕ) : (OreDivision.push D b i).degree ≤ (i : WithBot ℕ) := by 80 rw [Polynomial.degree_le_iff_coeff_zero] 81 intro n hn 82 rw [push_coeff] 83 apply Finset.sum_eq_zero 84 intro k hk 85 by_cases hki : i - k = n 86 · have hn' : i < n := by exact_mod_cast hn 87 have hle : i - k ≤ i := Nat.sub_le _ _ 88 omega 89 · simp [hki] 90 91 lemma push_coeff_top (b : B) (i : ℕ) : (OreDivision.push D b i).coeff i = b := by 92 rw [push_coeff] 93 rw [Finset.sum_eq_single 0 (by 94 intro k hk hk0 95 have hkpos : 0 < k := Nat.pos_of_ne_zero hk0 96 have hk_lt : k < i + 1 := Finset.mem_range.mp hk 97 have hk_le : k ≤ i := by omega 98 have hi_pos : 0 < i := lt_of_lt_of_le hkpos hk_le 99 have hki : i - k ≠ i := Nat.ne_of_lt (Nat.sub_lt hi_pos hkpos) 100 simp [hki]) (by simp)] 101 simp 102 103 lemma push_eq_zero_of (b : B) (i : ℕ) (h : b = 0) : OreDivision.push D b i = 0 := by 104 subst b 105 have hiter : ∀ n : ℕ, (D^[n]) 0 = 0 := by 106 intro n 107 induction n with 108 | zero => simp 109 | succ n ih => 110 rw [Function.iterate_succ_apply'] 111 simp [ih, OreDivisionDerivation.map_zero] 112 simp [push, hiter] 113 114 /-- Right multiplication of a normal polynomial by the monomial `b*x^j`. 115 116 The definition is coefficientwise and finite. It is deliberately not the 117 ordinary multiplication of `Polynomial B`: the inner `push` expansion is the 118 derivation correction for moving `b` through powers of `x`. 119 -/ 120 def rightTerm (i : ℕ) (a b : B) (j : ℕ) : Polynomial B := 121 ∑ k ∈ Finset.range (i + 1), 122 Polynomial.monomial (i - k + j) 123 (a * (Nat.choose i k • (D^[k]) b)) 124 125 /-- Right multiplication by one coefficient-monomial. -/ 126 def rightMulMonomial (p : Polynomial B) (b : B) (j : ℕ) : Polynomial B := 127 p.sum (fun i a => rightTerm D i a b j) 128 129 lemma rightMulMonomial_coeff (p : Polynomial B) (b : B) (j n : ℕ) : 130 (rightMulMonomial D p b j).coeff n = 131 ∑ i ∈ p.support, ∑ k ∈ Finset.range (i + 1), 132 if i - k + j = n then 133 p.coeff i * (Nat.choose i k • (D^[k]) b) else 0 := by 134 simp [rightMulMonomial, rightTerm, Polynomial.coeff_sum, 135 Polynomial.coeff_monomial, Polynomial.sum_def] 136 137 lemma rightTerm_zero (i : ℕ) (b : B) (j : ℕ) : rightTerm D i 0 b j = 0 := by 138 simp [rightTerm] 139 140 lemma rightTerm_add_left (i : ℕ) (a₁ a₂ b : B) (j : ℕ) : 141 rightTerm D i (a₁ + a₂) b j = 142 rightTerm D i a₁ b j + rightTerm D i a₂ b j := by 143 simp only [rightTerm, add_mul] 144 rw [← Finset.sum_add_distrib] 145 apply Finset.sum_congr rfl 146 intro k hk 147 rw [map_add] 148 149 lemma rightMulMonomial_add_left (p q : Polynomial B) (b : B) (j : ℕ) : 150 rightMulMonomial D (p + q) b j = 151 rightMulMonomial D p b j + rightMulMonomial D q b j := by 152 apply Polynomial.sum_add_index 153 · intro i 154 exact rightTerm_zero D i b j 155 · intro i a₁ a₂ 156 exact rightTerm_add_left D i a₁ a₂ b j 157 158 lemma iterate_add (n : ℕ) (b₁ b₂ : B) : 159 (D^[n]) (b₁ + b₂) = (D^[n]) b₁ + (D^[n]) b₂ := by 160 induction n with 161 | zero => simp 162 | succ n ih => 163 calc 164 (D^[n + 1]) (b₁ + b₂) = D ((D^[n]) (b₁ + b₂)) := 165 Function.iterate_succ_apply' D n (b₁ + b₂) 166 _ = D ((D^[n]) b₁ + (D^[n]) b₂) := by rw [ih] 167 _ = D ((D^[n]) b₁) + D ((D^[n]) b₂) := D.map_add _ _ 168 _ = (D^[n + 1]) b₁ + (D^[n + 1]) b₂ := by 169 rw [Function.iterate_succ_apply', Function.iterate_succ_apply'] 170 171 lemma iterate_zero (n : ℕ) : (D^[n]) 0 = 0 := by 172 induction n with 173 | zero => simp 174 | succ n ih => 175 calc 176 (D^[n + 1]) 0 = D ((D^[n]) 0) := Function.iterate_succ_apply' D n 0 177 _ = D 0 := by rw [ih] 178 _ = 0 := D.map_zero 179 180 lemma rightMulMonomial_add_right (p : Polynomial B) (b₁ b₂ : B) (j : ℕ) : 181 rightMulMonomial D p (b₁ + b₂) j = 182 rightMulMonomial D p b₁ j + rightMulMonomial D p b₂ j := by 183 apply Polynomial.ext 184 intro n 185 rw [rightMulMonomial_coeff, Polynomial.coeff_add, 186 rightMulMonomial_coeff, rightMulMonomial_coeff] 187 rw [← Finset.sum_add_distrib] 188 apply Finset.sum_congr rfl 189 intro i hi 190 rw [← Finset.sum_add_distrib] 191 apply Finset.sum_congr rfl 192 intro k hk 193 by_cases hEq : i - k + j = n 194 · simp only [if_pos hEq, iterate_add, nsmul_add, mul_add] 195 · simp [hEq] 196 197 lemma rightMulMonomial_zero_right (p : Polynomial B) (j : ℕ) : 198 rightMulMonomial D p 0 j = 0 := by 199 apply Polynomial.ext 200 intro n 201 rw [rightMulMonomial_coeff] 202 apply Finset.sum_eq_zero 203 intro i hi 204 apply Finset.sum_eq_zero 205 intro k hk 206 simp [iterate_zero] 207 208 /-- The product `d*q` of a normal polynomial by a normal right quotient. -/ 209 def rightMul (d q : Polynomial B) : Polynomial B := 210 q.sum (fun j c => rightMulMonomial D d c j) 211 212 lemma rightMul_add (d q₁ q₂ : Polynomial B) : 213 rightMul D d (q₁ + q₂) = rightMul D d q₁ + rightMul D d q₂ := by 214 apply Polynomial.sum_add_index 215 · intro j 216 exact rightMulMonomial_zero_right D d j 217 · intro j c₁ c₂ 218 exact rightMulMonomial_add_right D d c₁ c₂ j 219 220 lemma rightMul_zero (d : Polynomial B) : rightMul D d 0 = 0 := by 221 simp [rightMul, Polynomial.sum_def] 222 223 /-- The additive map given by right multiplication by a fixed normal form. -/ 224 def rightMulAddHom (d : Polynomial B) : Polynomial B →+ Polynomial B where 225 toFun := rightMul D d 226 map_zero' := rightMul_zero D d 227 map_add' := rightMul_add D d 228 229 lemma rightMul_sub (d q₁ q₂ : Polynomial B) : 230 rightMul D d (q₁ - q₂) = rightMul D d q₁ - rightMul D d q₂ := by 231 exact map_sub (rightMulAddHom D d) q₁ q₂ 232 233 lemma rightMul_monomial (d : Polynomial B) (c : B) (j : ℕ) : 234 rightMul D d (Polynomial.monomial j c) = 235 rightMulMonomial D d c j := by 236 by_cases hc : c = 0 237 · subst c 238 simp [rightMul, Polynomial.sum_def, rightMulMonomial_zero_right] 239 · unfold rightMul 240 rw [Polynomial.sum_def, Polynomial.support_monomial j hc] 241 simp [Polynomial.coeff_monomial, hc] 242 243 lemma rightMulMonomial_degree_le (p : Polynomial B) (b : B) (j : ℕ) : 244 (rightMulMonomial D p b j).degree ≤ (p.natDegree + j : WithBot ℕ) := by 245 rw [Polynomial.degree_le_iff_coeff_zero] 246 intro n hn 247 rw [rightMulMonomial_coeff] 248 apply Finset.sum_eq_zero 249 intro i hi 250 apply Finset.sum_eq_zero 251 intro k hk 252 by_cases hEq : i - k + j = n 253 · have hn' : p.natDegree + j < n := by exact_mod_cast hn 254 have hi_le : i ≤ p.natDegree := Polynomial.le_natDegree_of_mem_supp i hi 255 have hle : i - k + j ≤ p.natDegree + j := by 256 omega 257 omega 258 · simp [hEq] 259 260 lemma rightMulMonomial_coeff_top (p : Polynomial B) (hp : p ≠ 0) 261 (b : B) (j : ℕ) : 262 (rightMulMonomial D p b j).coeff (p.natDegree + j) = 263 p.leadingCoeff * b := by 264 rw [rightMulMonomial_coeff] 265 have htop : p.natDegree ∈ p.support := 266 Polynomial.natDegree_mem_support_of_nonzero hp 267 rw [Finset.sum_eq_single p.natDegree (by 268 intro i hi hne 269 apply Finset.sum_eq_zero 270 intro k hk 271 have hi_le : i ≤ p.natDegree := Polynomial.le_natDegree_of_mem_supp i hi 272 have hi_lt : i < p.natDegree := lt_of_le_of_ne hi_le hne 273 have hne_sub : i - k ≠ p.natDegree := by omega 274 simp [hne_sub]) (by simp [htop])] 275 rw [Finset.sum_eq_single 0 (by 276 intro k hk hk0 277 have hkpos : 0 < k := Nat.pos_of_ne_zero hk0 278 have hk_lt : k < p.natDegree + 1 := Finset.mem_range.mp hk 279 have hk_le : k ≤ p.natDegree := by omega 280 have hNpos : 0 < p.natDegree := lt_of_lt_of_le hkpos hk_le 281 have hne_sub : p.natDegree - k ≠ p.natDegree := 282 Nat.ne_of_lt (Nat.sub_lt hNpos hkpos) 283 simp [hne_sub]) (by simp)] 284 rw [Nat.sub_zero] 285 simp only [if_true, Nat.choose_zero_right, Function.iterate_zero_apply, 286 one_nsmul, one_mul, Polynomial.leadingCoeff] 287 288 lemma rightMul_degree_le (d q : Polynomial B) : 289 (rightMul D d q).degree ≤ (d.natDegree + q.natDegree : WithBot ℕ) := by 290 rw [Polynomial.degree_le_iff_coeff_zero] 291 intro n hn 292 rw [rightMul, Polynomial.coeff_sum] 293 apply Finset.sum_eq_zero 294 intro j hj 295 apply Polynomial.coeff_eq_zero_of_degree_lt 296 have hj_le : j ≤ q.natDegree := Polynomial.le_natDegree_of_mem_supp j hj 297 have hdeg : (rightMulMonomial D d (q.coeff j) j).degree ≤ 298 (d.natDegree + j : WithBot ℕ) := 299 rightMulMonomial_degree_le D d (q.coeff j) j 300 have hbound : (d.natDegree + j : WithBot ℕ) ≤ 301 (d.natDegree + q.natDegree : WithBot ℕ) := by 302 exact_mod_cast Nat.add_le_add_left hj_le d.natDegree 303 exact lt_of_le_of_lt hdeg (lt_of_le_of_lt hbound hn) 304 305 lemma rightMul_coeff_top [Nontrivial B] (d q : Polynomial B) 306 (hd : d.Monic) (hq : q ≠ 0) : 307 (rightMul D d q).coeff (d.natDegree + q.natDegree) = q.leadingCoeff := by 308 rw [rightMul, Polynomial.coeff_sum] 309 rw [Polynomial.sum_def] 310 have hqtop : q.natDegree ∈ q.support := 311 Polynomial.natDegree_mem_support_of_nonzero hq 312 rw [Finset.sum_eq_single q.natDegree (by 313 intro j hj hne 314 have hj_le : j ≤ q.natDegree := Polynomial.le_natDegree_of_mem_supp j hj 315 have hj_lt : j < q.natDegree := lt_of_le_of_ne hj_le hne 316 have hdeg : (rightMulMonomial D d (q.coeff j) j).degree ≤ 317 (d.natDegree + j : WithBot ℕ) := 318 rightMulMonomial_degree_le D d (q.coeff j) j 319 have hlt : (d.natDegree + j : WithBot ℕ) < 320 (d.natDegree + q.natDegree : WithBot ℕ) := by 321 exact_mod_cast Nat.add_lt_add_left hj_lt d.natDegree 322 have hzero : (rightMulMonomial D d (q.coeff j) j).coeff 323 (d.natDegree + q.natDegree) = 0 := 324 Polynomial.coeff_eq_zero_of_degree_lt (lt_of_le_of_lt hdeg hlt) 325 exact hzero) (by simp [hqtop])] 326 have hd0 : d ≠ 0 := hd.ne_zero 327 rw [rightMulMonomial_coeff_top D d hd0 (q.coeff q.natDegree) q.natDegree, 328 hd.leadingCoeff, one_mul] 329 rfl 330 331 lemma rightMul_degree_eq [Nontrivial B] (d q : Polynomial B) 332 (hd : d.Monic) (hq : q ≠ 0) : 333 (rightMul D d q).degree = (d.natDegree + q.natDegree : WithBot ℕ) := by 334 have hle := rightMul_degree_le D d q 335 have htop : (rightMul D d q).coeff (d.natDegree + q.natDegree) = 336 q.leadingCoeff := rightMul_coeff_top D d q hd hq 337 have hq0 : q.leadingCoeff ≠ 0 := Polynomial.leadingCoeff_ne_zero.mpr hq 338 have hge : (d.natDegree + q.natDegree : WithBot ℕ) ≤ 339 (rightMul D d q).degree := by 340 by_contra hnot 341 have hlt0 : (rightMul D d q).degree < 342 (d.natDegree + q.natDegree : WithBot ℕ) := lt_of_not_ge hnot 343 have hlt : (rightMul D d q).degree < 344 ((d.natDegree + q.natDegree : ℕ) : WithBot ℕ) := by 345 have heq : (d.natDegree + q.natDegree : WithBot ℕ) = 346 ((d.natDegree + q.natDegree : ℕ) : WithBot ℕ) := 347 (WithBot.coe_add d.natDegree q.natDegree).symm 348 rwa [heq] at hlt0 349 have hz := Polynomial.coeff_eq_zero_of_degree_lt hlt 350 exact hq0 (by rw [← htop, hz]) 351 exact le_antisymm hle hge 352 353 theorem rightMul_injective [Nontrivial B] (d : Polynomial B) (hd : d.Monic) : 354 Function.Injective (rightMul D d) := by 355 intro q₁ q₂ hq 356 by_contra hne 357 have hdiff : q₁ - q₂ ≠ 0 := sub_ne_zero.mpr hne 358 have hz : rightMul D d (q₁ - q₂) = 0 := by 359 rw [rightMul_sub, hq, sub_self] 360 have hdeg := rightMul_degree_eq D d (q₁ - q₂) hd hdiff 361 rw [hz] at hdeg 362 have hne : (⊥ : WithBot ℕ) ≠ 363 (d.natDegree + (q₁ - q₂).natDegree : WithBot ℕ) := by 364 have heq : (d.natDegree + (q₁ - q₂).natDegree : WithBot ℕ) = 365 ((d.natDegree + (q₁ - q₂).natDegree : ℕ) : WithBot ℕ) := 366 (WithBot.coe_add d.natDegree (q₁ - q₂).natDegree).symm 367 rw [heq] 368 exact WithBot.bot_ne_coe 369 exact hne hdeg 370 371 /-! The leading-degree theorem packages the strict filtered-intersection 372 property needed by the relative principal-source construction. This is an 373 Ore-polynomial filtration statement; it is deliberately not identified here 374 with the Bernstein filtration on the Weyl algebra. -/ 375 376 theorem rightMul_degree_le_iff [Nontrivial B] (d q : Polynomial B) 377 (hd : d.Monic) (n : ℕ) : 378 (rightMul D d q).degree ≤ (n : WithBot ℕ) ↔ 379 q = 0 ∨ d.natDegree + q.natDegree ≤ n := by 380 constructor 381 · intro h 382 by_cases hq : q = 0 383 · exact Or.inl hq 384 · right 385 have hdeg := rightMul_degree_eq D d q hd hq 386 rw [hdeg] at h 387 exact_mod_cast h 388 · intro h 389 rcases h with hzero | hq 390 · subst q 391 simp [rightMul_zero] 392 · by_cases hq0 : q = 0 393 · subst q 394 simp [rightMul_zero] 395 · have hdeg := rightMul_degree_eq D d q hd hq0 396 rw [hdeg] 397 exact_mod_cast hq 398 399 lemma remainder_degree_lt (d r : Polynomial B) 400 (hr : r = 0 ∨ r.natDegree < d.natDegree) : 401 r.degree < (d.natDegree : WithBot ℕ) := by 402 rcases hr with rfl | hr 403 · exact WithBot.bot_lt_coe _ 404 · by_cases hr0 : r = 0 405 · subst r 406 exact WithBot.bot_lt_coe _ 407 · rw [Polynomial.degree_eq_natDegree hr0] 408 exact_mod_cast hr 409 410 theorem right_division_unique [Nontrivial B] (d p q₁ q₂ r₁ r₂ : Polynomial B) 411 (hd : d.Monic) 412 (h₁ : p = rightMul D d q₁ + r₁) 413 (h₂ : p = rightMul D d q₂ + r₂) 414 (hr₁ : r₁ = 0 ∨ r₁.natDegree < d.natDegree) 415 (hr₂ : r₂ = 0 ∨ r₂.natDegree < d.natDegree) : 416 q₁ = q₂ ∧ r₁ = r₂ := by 417 have heq : rightMul D d q₁ + r₁ = rightMul D d q₂ + r₂ := 418 h₁.symm.trans h₂ 419 have hrel : rightMul D d (q₁ - q₂) = r₂ - r₁ := by 420 rw [rightMul_sub] 421 apply (sub_eq_iff_eq_add).2 422 calc 423 rightMul D d q₁ = 424 (rightMul D d q₂ + r₂) - r₁ := 425 (eq_sub_iff_add_eq).2 heq 426 _ = (r₂ - r₁) + rightMul D d q₂ := by abel 427 have hrdiff : (r₂ - r₁).degree < (d.natDegree : WithBot ℕ) := by 428 have h₁deg := remainder_degree_lt d r₁ hr₁ 429 have h₂deg := remainder_degree_lt d r₂ hr₂ 430 exact lt_of_le_of_lt (Polynomial.degree_sub_le r₂ r₁) (max_lt h₂deg h₁deg) 431 have hqeq : q₁ = q₂ := by 432 by_contra hne 433 have hdiff : q₁ - q₂ ≠ 0 := sub_ne_zero.mpr hne 434 have hleft := rightMul_degree_eq D d (q₁ - q₂) hd hdiff 435 have hleft_ge : (d.natDegree : WithBot ℕ) ≤ 436 (rightMul D d (q₁ - q₂)).degree := by 437 rw [hleft] 438 apply le_add_of_nonneg_right 439 exact_mod_cast (Nat.zero_le (q₁ - q₂).natDegree) 440 have hright_ge : (d.natDegree : WithBot ℕ) ≤ (r₂ - r₁).degree := by 441 rw [← hrel] 442 exact hleft_ge 443 exact (not_le_of_gt hrdiff) hright_ge 444 have hrEq : r₁ = r₂ := by 445 apply add_left_cancel (b := r₁) (a := rightMul D d q₂) 446 simpa [hqeq] using heq 447 exact ⟨hqeq, hrEq⟩ 448 449 lemma cancel_degree_lt [Nontrivial B] (d p : Polynomial B) (hd : d.Monic) 450 (hp : p ≠ 0) (hdeg : d.natDegree ≤ p.natDegree) : 451 (p - rightMulMonomial D d p.leadingCoeff 452 (p.natDegree - d.natDegree)).degree < p.degree := by 453 let c : B := p.leadingCoeff 454 let j : ℕ := p.natDegree - d.natDegree 455 let q : Polynomial B := rightMulMonomial D d c j 456 have hd0 : d ≠ 0 := hd.ne_zero 457 have hc0 : c ≠ 0 := by 458 dsimp [c] 459 exact Polynomial.leadingCoeff_ne_zero.mpr hp 460 have hsum : d.natDegree + j = p.natDegree := by 461 dsimp [j] 462 exact Nat.add_sub_of_le hdeg 463 have hq_le : q.degree ≤ (p.natDegree : WithBot ℕ) := by 464 dsimp [q, c, j] 465 have h := rightMulMonomial_degree_le D d p.leadingCoeff 466 (p.natDegree - d.natDegree) 467 have hcast : (d.natDegree : WithBot ℕ) + 468 (p.natDegree - d.natDegree : WithBot ℕ) = 469 (p.natDegree : WithBot ℕ) := by 470 exact_mod_cast (Nat.add_sub_of_le hdeg) 471 rw [hcast] at h 472 exact h 473 have hq_top : q.coeff p.natDegree = c := by 474 dsimp [q] 475 rw [← hsum, 476 rightMulMonomial_coeff_top D d hd0 c j, hd.leadingCoeff, one_mul] 477 have hq0 : q ≠ 0 := by 478 intro hqzero 479 have hz := congrArg (fun z : Polynomial B => z.coeff p.natDegree) hqzero 480 change q.coeff p.natDegree = 0 at hz 481 rw [hq_top] at hz 482 exact hc0 hz 483 have hq_ge : (p.natDegree : WithBot ℕ) ≤ q.degree := by 484 by_contra hnot 485 have hlt : q.degree < (p.natDegree : WithBot ℕ) := lt_of_not_ge hnot 486 have hz : q.coeff p.natDegree = 0 := 487 Polynomial.coeff_eq_zero_of_degree_lt hlt 488 exact hc0 (by rw [← hq_top, hz]) 489 have hq_degree : q.degree = (p.natDegree : WithBot ℕ) := 490 le_antisymm hq_le hq_ge 491 have hp_degree : p.degree = (p.natDegree : WithBot ℕ) := 492 Polynomial.degree_eq_natDegree hp 493 have hleading : p.leadingCoeff = q.leadingCoeff := by 494 change p.coeff p.natDegree = q.coeff q.natDegree 495 have hq_nat : q.natDegree = p.natDegree := by 496 have hq_degree_nat : (q.natDegree : WithBot ℕ) = 497 (p.natDegree : WithBot ℕ) := by 498 rw [← Polynomial.degree_eq_natDegree hq0] 499 exact hq_degree 500 exact_mod_cast hq_degree_nat 501 rw [hq_nat, hq_top] 502 rfl 503 exact Polynomial.degree_sub_lt (hp_degree.trans hq_degree.symm) hp hleading 504 505 theorem right_division_exists [Nontrivial B] (d p : Polynomial B) (hd : d.Monic) : 506 ∃ q r : Polynomial B, 507 p = rightMul D d q + r ∧ (r = 0 ∨ r.natDegree < d.natDegree) := by 508 let P : ℕ → Prop := fun n => 509 ∀ p : Polynomial B, p.natDegree = n → 510 ∃ q r : Polynomial B, 511 p = rightMul D d q + r ∧ (r = 0 ∨ r.natDegree < d.natDegree) 512 have hall : P p.natDegree := by 513 refine Nat.strong_induction_on p.natDegree ?_ 514 intro n ih 515 dsimp [P] 516 intro p hpN 517 by_cases hp0 : p = 0 518 · subst p 519 exact ⟨0, 0, by simp [rightMul], Or.inl rfl⟩ 520 by_cases hsmall : p.natDegree < d.natDegree 521 · exact ⟨0, p, by simp [rightMul], Or.inr hsmall⟩ 522 · have hlarge : d.natDegree ≤ p.natDegree := Nat.le_of_not_gt hsmall 523 let c : B := p.leadingCoeff 524 let j : ℕ := p.natDegree - d.natDegree 525 let rm : Polynomial B := rightMulMonomial D d c j 526 have hcancel : (p - rm).degree < p.degree := by 527 dsimp [rm, c, j] 528 exact cancel_degree_lt D d p hd hp0 hlarge 529 by_cases hrem0 : p - rm = 0 530 · refine ⟨Polynomial.monomial j c, 0, ?_, Or.inl rfl⟩ 531 rw [rightMul_monomial] 532 dsimp [rm] at hrem0 ⊢ 533 simpa [add_zero] using (sub_eq_zero.mp hrem0) 534 · have hremN : (p - rm).natDegree < p.natDegree := 535 Polynomial.natDegree_lt_natDegree hrem0 hcancel 536 have hremN' : (p - rm).natDegree < n := by 537 rw [← hpN] 538 exact hremN 539 obtain ⟨q, r, hqr, hrr⟩ := 540 ih (p - rm).natDegree hremN' (p - rm) rfl 541 refine ⟨Polynomial.monomial j c + q, r, ?_, hrr⟩ 542 calc 543 p = rm + (p - rm) := by abel 544 _ = rm + (rightMul D d q + r) := by rw [hqr] 545 _ = rightMul D d (Polynomial.monomial j c + q) + r := by 546 rw [rightMul_add, rightMul_monomial] 547 dsimp [rm] 548 abel 549 dsimp [P] at hall 550 exact hall p rfl 551 552 /-- An ambient ring in which the Ore relation is represented. -/ 553 structure OreAmbient (B A : Type*) [Ring B] [Ring A] 554 (D : OreDivisionDerivation B) where 555 /-- The coefficient-ring embedding. -/ 556 embed : B →+* A 557 /-- The element representing the Ore variable. -/ 558 x : A 559 /-- The defining relation in the ambient ring. -/ 560 relation : ∀ b, x * embed b = embed b * x + embed (D b) 561 562 namespace OreAmbient 563 564 variable {B A : Type*} [Ring B] [Ring A] 565 (D : OreDivisionDerivation B) (O : OreAmbient B A D) 566 567 /-- The inner derivation `a ↦ p*a-a*p`, used to formalize the iterated 568 commutator expansion of a power of `p`. -/ 569 def commutatorDerivation (p : A) : OreDivisionDerivation A where 570 toFun a := p * a - a * p 571 map_zero' := by simp 572 map_add' a b := by noncomm_ring 573 leibniz' a b := by noncomm_ring 574 575 /-- The ambient Ore presentation for an inner derivation. -/ 576 def commutatorAmbient (p : A) : 577 OreAmbient A A (commutatorDerivation p) where 578 embed := RingHom.id A 579 x := p 580 relation := by 581 intro a 582 change p * a = a * p + (p * a - a * p) 583 noncomm_ring 584 585 /-- A term in the iterated commutator expansion. -/ 586 def term (b : B) (i j : ℕ) : A := 587 O.embed ((D^[i]) b) * O.x ^ j 588 589 lemma push_term (b : B) (i j : ℕ) : 590 O.x * term D O b i j = term D O b i (j + 1) + term D O b (i + 1) j := by 591 dsimp [term] 592 calc 593 O.x * (O.embed ((D^[i]) b) * O.x ^ j) = 594 (O.x * O.embed ((D^[i]) b)) * O.x ^ j := by rw [mul_assoc] 595 _ = (O.embed ((D^[i]) b) * O.x + 596 O.embed (D ((D^[i]) b))) * O.x ^ j := by rw [O.relation] 597 _ = O.embed ((D^[i]) b) * O.x ^ (j + 1) + 598 O.embed ((D^[i + 1]) b) * O.x ^ j := by 599 rw [add_mul, mul_assoc, ← pow_succ', Function.iterate_succ_apply'] 600 601 lemma mul_nsmul_left (a u : A) (n : ℕ) : 602 a * (n • u) = n • (a * u) := by 603 induction n with 604 | zero => simp 605 | succ n ih => simp only [succ_nsmul, mul_add, ih] 606 607 lemma nsmul_mul_right (a u : A) (n : ℕ) : 608 (n • a) * u = n • (a * u) := by 609 induction n with 610 | zero => simp 611 | succ n ih => simp only [succ_nsmul, add_mul, ih] 612 613 /-- The normal-order expansion of `x^n * embed b`. -/ 614 def expansion (b : B) (n : ℕ) : A := 615 ∑ ij ∈ Finset.HasAntidiagonal.antidiagonal n, 616 n.choose ij.1 • term D O b ij.1 ij.2 617 618 theorem pow_mul (b : B) (n : ℕ) : 619 O.x ^ n * O.embed b = expansion D O b n := by 620 induction n with 621 | zero => 622 simp [expansion, term] 623 | succ n ih => 624 rw [pow_succ', mul_assoc, ih, expansion, Finset.mul_sum] 625 simp_rw [mul_nsmul_left O.x, O.push_term, smul_add] 626 rw [Finset.sum_add_distrib, expansion] 627 rw [Finset.sum_antidiagonal_choose_succ_nsmul] 628 have hsecond : 629 (∑ ij ∈ Finset.HasAntidiagonal.antidiagonal n, 630 n.choose ij.1 • term D O b (ij.1 + 1) ij.2) = 631 ∑ ij ∈ Finset.HasAntidiagonal.antidiagonal n, 632 n.choose ij.2 • term D O b (ij.1 + 1) ij.2 := by 633 apply Finset.sum_congr rfl 634 intro ij hij 635 have hsum : ij.1 + ij.2 = n := 636 Finset.HasAntidiagonal.mem_antidiagonal.mp hij 637 have hi : ij.1 ≤ n := by omega 638 rw [← Nat.choose_symm hi] 639 rw [show n - ij.1 = ij.2 by omega] 640 rw [hsecond] 641 642 /-- A single coefficient moved through a power of the Ore variable. -/ 643 def reverseTerm (b : B) (i j : ℕ) : A := 644 O.x ^ j * O.embed ((D^[i]) b) 645 646 /-- A signed term for the reverse normal-order expansion. -/ 647 def reverseSignedTerm (b : B) (i j : ℕ) : A := 648 (-1 : A) ^ i * reverseTerm D O b i j 649 650 /-- The reverse normal-order expansion of `x^n * embed b`. -/ 651 def reverseExpansion (b : B) (n : ℕ) : A := 652 ∑ ij ∈ Finset.HasAntidiagonal.antidiagonal n, 653 n.choose ij.1 • reverseSignedTerm D O b ij.1 ij.2 654 655 lemma reverseTerm_mul (b : B) (i j : ℕ) : 656 reverseTerm D O b i j * O.x = 657 reverseTerm D O b i (j + 1) - reverseTerm D O b (i + 1) j := by 658 dsimp [reverseTerm] 659 have hmove : O.embed ((D^[i]) b) * O.x = 660 O.x * O.embed ((D^[i]) b) - O.embed (D ((D^[i]) b)) := by 661 rw [O.relation] 662 noncomm_ring 663 rw [show O.x ^ j * O.embed ((D^[i]) b) * O.x = 664 O.x ^ j * (O.embed ((D^[i]) b) * O.x) by rw [mul_assoc], hmove, 665 mul_sub, pow_succ'] 666 rw [← mul_assoc, ← pow_succ, pow_succ'] 667 rw [← Function.iterate_succ_apply' D i b, 668 ← Function.iterate_succ_apply D i b] 669 670 lemma reverseSignedTerm_mul (b : B) (i j : ℕ) : 671 reverseSignedTerm D O b i j * O.x = 672 reverseSignedTerm D O b i (j + 1) + 673 reverseSignedTerm D O b (i + 1) j := by 674 dsimp [reverseSignedTerm] 675 rw [mul_assoc, reverseTerm_mul, mul_sub, pow_succ'] 676 noncomm_ring 677 678 theorem reverse_mul (b : B) (n : ℕ) : 679 O.embed b * O.x ^ n = reverseExpansion D O b n := by 680 induction n with 681 | zero => 682 simp [reverseExpansion, reverseSignedTerm, reverseTerm] 683 | succ n ih => 684 rw [pow_succ, ← mul_assoc, ih, reverseExpansion, Finset.sum_mul] 685 simp_rw [nsmul_mul_right, reverseSignedTerm_mul] 686 simp_rw [nsmul_add] 687 unfold reverseExpansion 688 have hsecond : 689 (∑ ij ∈ Finset.HasAntidiagonal.antidiagonal n, 690 n.choose ij.1 • reverseSignedTerm D O b (ij.1 + 1) ij.2) = 691 ∑ ij ∈ Finset.HasAntidiagonal.antidiagonal n, 692 n.choose ij.2 • reverseSignedTerm D O b (ij.1 + 1) ij.2 := by 693 apply Finset.sum_congr rfl 694 intro ij hij 695 have hsum : ij.1 + ij.2 = n := 696 Finset.HasAntidiagonal.mem_antidiagonal.mp hij 697 have hi : ij.1 ≤ n := by omega 698 rw [← Nat.choose_symm hi] 699 rw [show n - ij.1 = ij.2 by omega] 700 rw [Finset.sum_add_distrib, hsecond] 701 exact (Finset.sum_antidiagonal_choose_succ_nsmul 702 (fun i j => reverseSignedTerm D O b i j) n).symm 703 704 theorem commutator_pow_mul (p a : A) (m : ℕ) : 705 p ^ m * a = 706 OreAmbient.expansion (commutatorDerivation p) (commutatorAmbient p) a m := by 707 exact OreAmbient.pow_mul (commutatorDerivation p) (commutatorAmbient p) a m 708 709 theorem commutator_pow_mul_explicit (p a : A) (m : ℕ) : 710 p ^ m * a = 711 ∑ ij ∈ Finset.HasAntidiagonal.antidiagonal m, 712 m.choose ij.1 • (((commutatorDerivation p)^[ij.1]) a * p ^ ij.2) := by 713 simpa [OreAmbient.expansion, term, commutatorAmbient] using 714 (commutator_pow_mul (A := A) p a m) 715 716 theorem commutator_pow_succ (p x : A) 717 (hpx : p * x - x * p = 1) (r : ℕ) : 718 p * x ^ (r + 1) - x ^ (r + 1) * p = (r + 1) • x ^ r := by 719 induction r with 720 | zero => simpa using hpx 721 | succ r ih => 722 calc 723 p * x ^ (r + 1 + 1) - x ^ (r + 1 + 1) * p = 724 (p * x ^ (r + 1) - x ^ (r + 1) * p) * x + 725 x ^ (r + 1) * (p * x - x * p) := by 726 noncomm_ring 727 _ = ((r + 1) • x ^ r) * x + x ^ (r + 1) * 1 := by rw [ih, hpx] 728 _ = (r + 2) • x ^ (r + 1) := by 729 rw [mul_one, nsmul_mul_right, pow_succ'] 730 have hpow : x ^ r * x = x * x ^ r := by 731 rw [← pow_succ, pow_succ'] 732 rw [hpow] 733 simp only [succ_nsmul] 734 735 theorem commutator_iterate_pow_of_le (p x : A) 736 (hpx : p * x - x * p = 1) (j n : ℕ) (hjn : j ≤ n) : 737 (((commutatorDerivation p)^[j]) (x ^ n)) = 738 n.descFactorial j • x ^ (n - j) := by 739 induction j generalizing n with 740 | zero => simp 741 | succ j ih => 742 have hjn' : j ≤ n := by omega 743 rw [Function.iterate_succ_apply', ih n hjn'] 744 have hpow : x ^ (n - j) = x ^ ((n - j - 1) + 1) := by 745 congr 1 746 omega 747 have hcomm : 748 (commutatorDerivation p) (x ^ (n - j)) = 749 (n - j) • x ^ (n - j - 1) := by 750 change p * x ^ (n - j) - x ^ (n - j) * p = _ 751 rw [hpow] 752 have hsub : n - j - 1 + 1 = n - j := by omega 753 simpa only [hsub] using commutator_pow_succ p x hpx (n - j - 1) 754 rw [OreDivisionDerivation.map_nsmul, hcomm, smul_smul, 755 Nat.descFactorial_succ] 756 rw [show n - (j + 1) = n - j - 1 by omega, Nat.mul_comm] 757 758 theorem commutator_iterate_pow_of_lt (p x : A) 759 (hpx : p * x - x * p = 1) (j n : ℕ) (hnj : n < j) : 760 (((commutatorDerivation p)^[j]) (x ^ n)) = 0 := by 761 induction j with 762 | zero => omega 763 | succ j ih => 764 by_cases hj : n < j 765 · rw [Function.iterate_succ_apply', ih hj] 766 simp [commutatorDerivation] 767 · have hjeq : j = n := by omega 768 rw [Function.iterate_succ_apply', hjeq, 769 commutator_iterate_pow_of_le p x hpx n n le_rfl] 770 simp [commutatorDerivation] 771 rw [Nat.cast_comm] 772 simp 773 774 theorem commutator_iterate_pow (p x : A) 775 (hpx : p * x - x * p = 1) (j n : ℕ) : 776 (((commutatorDerivation p)^[j]) (x ^ n)) = 777 if j ≤ n then n.descFactorial j • x ^ (n - j) else 0 := by 778 by_cases hjn : j ≤ n 779 · simp [hjn, commutator_iterate_pow_of_le p x hpx j n hjn] 780 · have hnj : n < j := Nat.lt_of_not_ge hjn 781 simp [hjn, commutator_iterate_pow_of_lt p x hpx j n hnj] 782 783 theorem commutator_pow_mul_pow (p x : A) 784 (hpx : p * x - x * p = 1) (k r : ℕ) : 785 p ^ k * x ^ r = 786 ∑ i ∈ Finset.range (k + 1), 787 if i ≤ r then 788 (k.choose i * r.descFactorial i) • 789 (x ^ (r - i) * p ^ (k - i)) 790 else 0 := by 791 rw [commutator_pow_mul_explicit] 792 rw [Finset.Nat.sum_antidiagonal_eq_sum_range_succ 793 (fun i j => k.choose i • 794 (((commutatorDerivation p)^[i]) (x ^ r) * p ^ j)) k] 795 apply Finset.sum_congr rfl 796 intro i hi 797 by_cases hir : i ≤ r 798 · rw [commutator_iterate_pow p x hpx i r] 799 simp only [if_pos hir] 800 rw [show k - i = (k - i) by rfl] 801 simp [hir, smul_mul_assoc, smul_smul, Nat.mul_comm, Nat.mul_left_comm, 802 Nat.mul_assoc, mul_assoc] 803 · rw [commutator_iterate_pow p x hpx i r] 804 simp [hir] 805 806 /-! ### p-free monic corner 807 808 The quotient by the image of right multiplication by `p` keeps only the 809 p-free term of the normal-ordering expansion. The following theorem isolates 810 the monic contribution; lower coefficient terms are handled by the separate 811 Newton arithmetic lemmas in `a2_newton_bound.lean`. 812 -/ 813 814 /-- The linear map given by right multiplication by `p`. -/ 815 def pRightMulLinear {k A : Type*} [Field k] [Ring A] [Algebra k A] 816 (p : A) : A →ₗ[k] A where 817 toFun z := z * p 818 map_add' x y := by 819 change (x + y) * p = x * p + y * p 820 rw [add_mul] 821 map_smul' c x := by 822 simp only [Algebra.smul_def, RingHom.id_apply] 823 rw [mul_assoc] 824 825 /-- The range of right multiplication by `p`. -/ 826 def pRightMulRange {k A : Type*} [Field k] [Ring A] [Algebra k A] 827 (p : A) : Submodule k A := 828 LinearMap.range (pRightMulLinear p) 829 830 lemma pRightMulRange_mem_of_mul_p {k A : Type*} [Field k] [Ring A] 831 [Algebra k A] (p z : A) : z * p ∈ pRightMulRange (k := k) p := by 832 exact ⟨z, rfl⟩ 833 834 theorem pfree_power_of_le {k A : Type*} [Field k] [Ring A] 835 [Algebra k A] (p x : A) (hpx : p * x - x * p = 1) 836 (u n : ℕ) (hun : u ≤ n) : 837 Submodule.mkQ (pRightMulRange (k := k) p) (p ^ u * x ^ n) = 838 (n.descFactorial u : k) • 839 Submodule.mkQ (pRightMulRange (k := k) p) (x ^ (n - u)) := by 840 rw [commutator_pow_mul_pow p x hpx u n] 841 rw [map_sum] 842 rw [Finset.sum_eq_single u] 843 · simp only [hun, ↓reduceIte, Nat.choose_self, Nat.cast_one, one_mul, 844 Nat.cast_ofNat, nsmul_eq_mul, map_smul, Nat.sub_self, pow_zero, mul_one] 845 change Submodule.Quotient.mk 846 (↑(n.descFactorial u) * x ^ (n - u)) = 847 (n.descFactorial u : k) • Submodule.Quotient.mk (x ^ (n - u)) 848 rw [← Submodule.Quotient.mk_smul] 849 congr 1 850 simp [Algebra.smul_def] 851 · intro i hi hik 852 simp only [Finset.mem_range] at hi 853 have hlt : i < u := by omega 854 have hpow : p ^ (u - i) = p ^ (u - i - 1) * p := by 855 calc 856 p ^ (u - i) = p ^ ((u - i - 1) + 1) := by congr 1; omega 857 _ = p ^ (u - i - 1) * p := by rw [pow_succ] 858 have hmem : x ^ (n - i) * p ^ (u - i) ∈ 859 pRightMulRange (k := k) p := by 860 rw [hpow] 861 simpa [mul_assoc] using 862 (pRightMulRange_mem_of_mul_p (k := k) p 863 (x ^ (n - i) * p ^ (u - i - 1))) 864 have hzero : Submodule.mkQ (pRightMulRange (k := k) p) 865 (x ^ (n - i) * p ^ (u - i)) = 0 := 866 (Submodule.Quotient.mk_eq_zero (pRightMulRange (k := k) p)).2 hmem 867 simp only [if_pos (by omega : i ≤ n), map_nsmul, hzero, smul_zero] 868 · simp 869 870 theorem pfree_monic_corner {k A : Type*} [Field k] [Ring A] 871 [Algebra k A] (p x : A) (hpx : p * x - x * p = 1) 872 (m r : ℕ) : 873 Submodule.mkQ (pRightMulRange (k := k) p) (p ^ m * x ^ (m + r)) = 874 (Nat.choose m m * (m + r).descFactorial m : k) • 875 Submodule.mkQ (pRightMulRange (k := k) p) (x ^ r) := by 876 rw [commutator_pow_mul_pow p x hpx m (m + r)] 877 rw [map_sum] 878 rw [Finset.sum_eq_single m] 879 · simp only [Nat.choose_self, Nat.le_add_right, ↓reduceIte, Nat.sub_self, 880 Nat.cast_one, one_mul, Nat.cast_ofNat, nsmul_eq_mul, map_smul] 881 simp only [Submodule.mkQ_apply, pow_zero, Nat.add_sub_cancel_left, mul_one] 882 rw [← Submodule.Quotient.mk_smul] 883 congr 1 884 simp [Algebra.smul_def] 885 · intro i hi him 886 simp only [Finset.mem_range] at hi 887 have hpos : 0 < m - i := by omega 888 have hpow : p ^ (m - i) = p ^ (m - i - 1) * p := by 889 calc 890 p ^ (m - i) = p ^ ((m - i - 1) + 1) := by congr 1; omega 891 _ = p ^ (m - i - 1) * p := by rw [pow_succ] 892 have hmem : x ^ (m + r - i) * p ^ (m - i) ∈ 893 pRightMulRange (k := k) p := by 894 rw [hpow] 895 simpa [mul_assoc] using 896 (pRightMulRange_mem_of_mul_p (k := k) p 897 (x ^ (m + r - i) * p ^ (m - i - 1))) 898 have hzero : Submodule.mkQ (pRightMulRange (k := k) p) 899 (x ^ (m + r - i) * p ^ (m - i)) = 0 := 900 (Submodule.Quotient.mk_eq_zero (pRightMulRange (k := k) p)).2 hmem 901 simp only [if_pos (by omega : i ≤ m + r), map_nsmul, hzero, smul_zero] 902 · simp 903 904 lemma commutatorDerivation_mul_left (p b y : A) 905 (hpb : p * b = b * p) : 906 commutatorDerivation p (b * y) = b * commutatorDerivation p y := by 907 change p * (b * y) - (b * y) * p = b * (p * y - y * p) 908 rw [show p * (b * y) - (b * y) * p = (p * b) * y - b * (y * p) by 909 noncomm_ring, hpb] 910 noncomm_ring 911 912 theorem commutator_iterate_mul_left (p b y : A) 913 (hpb : p * b = b * p) (j : ℕ) : 914 ((commutatorDerivation p)^[j]) (b * y) = 915 b * ((commutatorDerivation p)^[j]) y := by 916 induction j with 917 | zero => simp 918 | succ j ih => 919 rw [Function.iterate_succ_apply', ih, 920 commutatorDerivation_mul_left p b _ hpb] 921 congr 1 922 rw [Function.iterate_succ_apply'] 923 924 theorem commutator_iterate_add (p : A) (j : ℕ) (a b : A) : 925 ((commutatorDerivation p)^[j]) (a + b) = 926 ((commutatorDerivation p)^[j]) a + 927 ((commutatorDerivation p)^[j]) b := by 928 induction j with 929 | zero => simp 930 | succ j ih => 931 calc 932 ((commutatorDerivation p)^[j + 1]) (a + b) = 933 (commutatorDerivation p) 934 (((commutatorDerivation p)^[j]) (a + b)) := by 935 rw [Function.iterate_succ_apply'] 936 _ = (commutatorDerivation p) 937 (((commutatorDerivation p)^[j]) a + 938 ((commutatorDerivation p)^[j]) b) := by rw [ih] 939 _ = (commutatorDerivation p) (((commutatorDerivation p)^[j]) a) + 940 (commutatorDerivation p) (((commutatorDerivation p)^[j]) b) := by 941 change p * (((commutatorDerivation p)^[j]) a + 942 ((commutatorDerivation p)^[j]) b) - 943 ((((commutatorDerivation p)^[j]) a + 944 ((commutatorDerivation p)^[j]) b) * p) = _ 945 change p * (((commutatorDerivation p)^[j]) a + 946 ((commutatorDerivation p)^[j]) b) - 947 ((((commutatorDerivation p)^[j]) a + 948 ((commutatorDerivation p)^[j]) b) * p) = 949 (p * ((commutatorDerivation p)^[j]) a - 950 ((commutatorDerivation p)^[j]) a * p) + 951 (p * ((commutatorDerivation p)^[j]) b - 952 ((commutatorDerivation p)^[j]) b * p) 953 noncomm_ring 954 _ = ((commutatorDerivation p)^[j + 1]) a + 955 ((commutatorDerivation p)^[j + 1]) b := by 956 rw [Function.iterate_succ_apply', Function.iterate_succ_apply'] 957 958 theorem commutator_iterate_sum (p : A) (j : ℕ) 959 (s : Finset ℕ) (f : ℕ → A) : 960 ((commutatorDerivation p)^[j]) (∑ i ∈ s, f i) = 961 ∑ i ∈ s, ((commutatorDerivation p)^[j]) (f i) := by 962 induction s using Finset.induction_on with 963 | empty => 964 have hz : ∀ n : ℕ, ((commutatorDerivation p)^[n]) 0 = 0 := by 965 intro n 966 induction n with 967 | zero => simp 968 | succ n ih => 969 rw [Function.iterate_succ_apply'] 970 change p * (((commutatorDerivation p)^[n]) 0) - 971 (((commutatorDerivation p)^[n]) 0) * p = 0 972 rw [ih] 973 simp 974 rw [Finset.sum_empty, Finset.sum_empty] 975 exact hz j 976 | @insert a s ha ih => 977 rw [Finset.sum_insert ha, commutator_iterate_add, ih, 978 Finset.sum_insert ha] 979 980 theorem commutator_iterate_eval_monomial_of_le 981 (p b : B) (n j : ℕ) (hpb : ∀ c : B, 982 O.embed p * O.embed c = O.embed c * O.embed p) 983 (hDp : D p = -1) (hjn : j ≤ n) : 984 (((commutatorDerivation (O.embed p))^[j]) 985 (O.embed b * O.x ^ n)) = 986 O.embed b * (n.descFactorial j • O.x ^ (n - j)) := by 987 have hpx : O.embed p * O.x - O.x * O.embed p = 1 := by 988 rw [O.relation p, hDp] 989 simp 990 calc 991 ((commutatorDerivation (O.embed p))^[j]) 992 (O.embed b * O.x ^ n) = 993 O.embed b * 994 ((commutatorDerivation (O.embed p))^[j]) (O.x ^ n) := by 995 exact commutator_iterate_mul_left (O.embed p) (O.embed b) 996 (O.x ^ n) (hpb b) j 997 _ = O.embed b * (n.descFactorial j • O.x ^ (n - j)) := by 998 rw [commutator_iterate_pow_of_le (O.embed p) O.x hpx j n hjn] 999 1000 theorem commutator_iterate_eval_monomial 1001 (p b : B) (n j : ℕ) (hpb : ∀ c : B, 1002 O.embed p * O.embed c = O.embed c * O.embed p) 1003 (hDp : D p = -1) : 1004 (((commutatorDerivation (O.embed p))^[j]) 1005 (O.embed b * O.x ^ n)) = 1006 if j ≤ n then 1007 O.embed b * (n.descFactorial j • O.x ^ (n - j)) 1008 else 0 := by 1009 have hpx : O.embed p * O.x - O.x * O.embed p = 1 := by 1010 rw [O.relation p, hDp] 1011 simp 1012 rw [commutator_iterate_mul_left (O.embed p) (O.embed b) 1013 (O.x ^ n) (hpb b) j] 1014 rw [commutator_iterate_pow (O.embed p) O.x hpx j n] 1015 by_cases hjn : j ≤ n <;> simp [hjn] 1016 1017 /-- Evaluation of a normal polynomial in an ambient Ore ring. -/ 1018 def eval (p : Polynomial B) : A := 1019 p.sum (fun i b => O.embed b * O.x ^ i) 1020 1021 theorem commutator_iterate_eval (p : A) (q : Polynomial B) (j : ℕ) : 1022 ((commutatorDerivation p)^[j]) (eval D O q) = 1023 ∑ i ∈ q.support, 1024 ((commutatorDerivation p)^[j]) 1025 (O.embed (q.coeff i) * O.x ^ i) := by 1026 unfold eval 1027 rw [Polynomial.sum_def] 1028 exact commutator_iterate_sum p j q.support 1029 (fun i => O.embed (q.coeff i) * O.x ^ i) 1030 1031 lemma eval_zero : eval D O 0 = 0 := by 1032 simp [eval, Polynomial.sum_def] 1033 1034 lemma eval_add (p q : Polynomial B) : 1035 eval D O (p + q) = eval D O p + eval D O q := by 1036 unfold eval 1037 apply Polynomial.sum_add_index 1038 · intro i 1039 simp 1040 · intro i a b 1041 rw [map_add, add_mul] 1042 1043 /-- The additive evaluation homomorphism. -/ 1044 def evalAddHom : Polynomial B →+ A where 1045 toFun := eval D O 1046 map_zero' := eval_zero D O 1047 map_add' := eval_add D O 1048 1049 lemma eval_monomial (b : B) (j : ℕ) : 1050 eval D O (Polynomial.monomial j b) = O.embed b * O.x ^ j := by 1051 by_cases hb : b = 0 1052 · subst b 1053 simp [eval, Polynomial.sum_def] 1054 · unfold eval 1055 rw [Polynomial.sum_def, Polynomial.support_monomial j hb] 1056 simp [Polynomial.coeff_monomial, hb] 1057 1058 /-- The coefficient-left normal form of an iterated commutator. -/ 1059 def commutatorNormal (q : Polynomial B) (j : ℕ) : Polynomial B := 1060 ∑ i ∈ q.support, 1061 if j ≤ i then 1062 Polynomial.monomial (i - j) (i.descFactorial j • q.coeff i) 1063 else 0 1064 1065 lemma commutatorNormal_degree_le (q : Polynomial B) (j : ℕ) : 1066 (commutatorNormal q j).degree ≤ (q.natDegree - j : WithBot ℕ) := by 1067 rw [Polynomial.degree_le_iff_coeff_zero] 1068 intro n hn 1069 have hn' : q.natDegree - j < n := by exact_mod_cast hn 1070 unfold commutatorNormal 1071 change (Polynomial.lcoeff B n) 1072 (∑ i ∈ q.support, 1073 if j ≤ i then 1074 Polynomial.monomial (i - j) (i.descFactorial j • q.coeff i) 1075 else 0) = 0 1076 rw [map_sum] 1077 apply Finset.sum_eq_zero 1078 intro i hi 1079 have hi_le : i ≤ q.natDegree := Polynomial.le_natDegree_of_mem_supp i hi 1080 by_cases hji : j ≤ i 1081 · simp only [if_pos hji] 1082 change (Polynomial.monomial (i - j) 1083 (i.descFactorial j • q.coeff i)).coeff n = 0 1084 rw [Polynomial.coeff_monomial] 1085 simp [show i - j ≠ n by omega] 1086 · simp [hji] 1087 1088 lemma commutatorNormal_coeff_top [Nontrivial B] (q : Polynomial B) (j : ℕ) 1089 (hq : q.Monic) (hjn : j ≤ q.natDegree) : 1090 (commutatorNormal q j).coeff (q.natDegree - j) = 1091 q.natDegree.descFactorial j • (1 : B) := by 1092 unfold commutatorNormal 1093 change (Polynomial.lcoeff B (q.natDegree - j)) 1094 (∑ i ∈ q.support, 1095 if j ≤ i then 1096 Polynomial.monomial (i - j) (i.descFactorial j • q.coeff i) 1097 else 0) = _ 1098 rw [map_sum] 1099 have hq0 : q ≠ 0 := hq.ne_zero 1100 rw [Finset.sum_eq_single q.natDegree (by 1101 intro i hi hne 1102 have hi_le : i ≤ q.natDegree := 1103 Polynomial.le_natDegree_of_mem_supp i hi 1104 have hi_lt : i < q.natDegree := lt_of_le_of_ne hi_le hne 1105 by_cases hji : j ≤ i 1106 · have hneq : i - j ≠ q.natDegree - j := by omega 1107 simp [hji, hneq, Polynomial.coeff_monomial] 1108 · simp [hji]) (by 1109 intro hnot 1110 exact (hnot (Polynomial.natDegree_mem_support_of_nonzero hq0)).elim)] 1111 simp [hjn, Polynomial.coeff_monomial, hq.leadingCoeff] 1112 1113 theorem commutator_iterate_eval_eq_eval_normal 1114 (p : B) (q : Polynomial B) (j : ℕ) 1115 (hpb : ∀ c : B, 1116 O.embed p * O.embed c = O.embed c * O.embed p) 1117 (hDp : D p = -1) : 1118 ((commutatorDerivation (O.embed p))^[j]) (eval D O q) = 1119 eval D O (commutatorNormal q j) := by 1120 rw [commutator_iterate_eval] 1121 change (∑ i ∈ q.support, 1122 ((commutatorDerivation (O.embed p))^[j]) 1123 (O.embed (q.coeff i) * O.x ^ i)) = 1124 (evalAddHom D O) (∑ i ∈ q.support, 1125 if j ≤ i then 1126 Polynomial.monomial (i - j) (i.descFactorial j • q.coeff i) 1127 else 0) 1128 rw [map_sum] 1129 apply Finset.sum_congr rfl 1130 intro i hi 1131 by_cases hji : j ≤ i 1132 · simp only [if_pos hji] 1133 rw [commutator_iterate_eval_monomial D O p (q.coeff i) i j hpb hDp] 1134 rw [if_pos hji] 1135 change O.embed (q.coeff i) * 1136 (i.descFactorial j • O.x ^ (i - j)) = 1137 eval D O (Polynomial.monomial (i - j) 1138 (i.descFactorial j • q.coeff i)) 1139 rw [eval_monomial] 1140 simp [map_nsmul, smul_mul_assoc] 1141 simp [Nat.cast_comm, mul_assoc] 1142 · rw [commutator_iterate_eval_monomial D O p (q.coeff i) i j hpb hDp] 1143 simp [hji] 1144 1145 lemma eval_push_eq_expansion (b : B) (n : ℕ) : 1146 eval D O (OreDivision.push D b n) = expansion D O b n := by 1147 change (evalAddHom D O) (OreDivision.push D b n) = expansion D O b n 1148 unfold OreDivision.push 1149 rw [map_sum] 1150 change (∑ k ∈ Finset.range (n + 1), 1151 eval D O (Polynomial.monomial (n - k) 1152 (Nat.choose n k • (D^[k]) b))) = expansion D O b n 1153 simp_rw [eval_monomial] 1154 simp only [map_nsmul, smul_mul_assoc] 1155 unfold expansion 1156 rw [Finset.Nat.sum_antidiagonal_eq_sum_range_succ 1157 (fun i j => n.choose i • term D O b i j) n] 1158 apply Finset.sum_congr rfl 1159 intro k hk 1160 rfl 1161 1162 theorem eval_push (b : B) (n : ℕ) : 1163 eval D O (OreDivision.push D b n) = O.x ^ n * O.embed b := by 1164 rw [eval_push_eq_expansion, (pow_mul D O b n).symm] 1165 1166 lemma eval_rightTerm (i : ℕ) (a b : B) (j : ℕ) : 1167 eval D O (rightTerm D i a b j) = 1168 (O.embed a * O.x ^ i) * (O.embed b * O.x ^ j) := by 1169 change (evalAddHom D O) (rightTerm D i a b j) = _ 1170 unfold rightTerm 1171 rw [map_sum] 1172 change (∑ k ∈ Finset.range (i + 1), 1173 eval D O (Polynomial.monomial (i - k + j) 1174 (a * (Nat.choose i k • (D^[k]) b)))) = _ 1175 simp_rw [eval_monomial] 1176 simp only [map_nsmul, map_mul] 1177 calc 1178 ∑ k ∈ Finset.range (i + 1), 1179 O.embed a * (Nat.choose i k • O.embed ((D^[k]) b)) * 1180 O.x ^ (i - k + j) = 1181 O.embed a * 1182 (∑ k ∈ Finset.range (i + 1), 1183 Nat.choose i k • 1184 (O.embed ((D^[k]) b) * O.x ^ (i - k)) * O.x ^ j) := by 1185 simp_rw [mul_assoc, smul_mul_assoc] 1186 rw [← Finset.mul_sum] 1187 apply congrArg (fun z => O.embed a * z) 1188 apply Finset.sum_congr rfl 1189 intro k hk 1190 rw [pow_add] 1191 simp only [mul_assoc] 1192 _ = O.embed a * 1193 ((O.x ^ i * O.embed b) * O.x ^ j) := by 1194 rw [← Finset.sum_mul] 1195 congr 1 1196 apply congrArg (fun z => z * O.x ^ j) 1197 change (∑ k ∈ Finset.range (i + 1), 1198 i.choose k • term D O b k (i - k)) = O.x ^ i * O.embed b 1199 rw [← Finset.Nat.sum_antidiagonal_eq_sum_range_succ 1200 (fun u v => i.choose u • term D O b u v) i] 1201 change expansion D O b i = O.x ^ i * O.embed b 1202 exact (pow_mul D O b i).symm 1203 _ = (O.embed a * O.x ^ i) * (O.embed b * O.x ^ j) := by 1204 noncomm_ring 1205 1206 lemma eval_rightMulMonomial (p : Polynomial B) (b : B) (j : ℕ) : 1207 eval D O (rightMulMonomial D p b j) = 1208 eval D O p * (O.embed b * O.x ^ j) := by 1209 change (evalAddHom D O) (rightMulMonomial D p b j) = _ 1210 unfold rightMulMonomial 1211 change (evalAddHom D O) (∑ i ∈ p.support, 1212 rightTerm D i (p.coeff i) b j) = _ 1213 rw [map_sum] 1214 change (∑ i ∈ p.support, 1215 eval D O (rightTerm D i (p.coeff i) b j)) = _ 1216 simp_rw [eval_rightTerm] 1217 unfold eval 1218 rw [Polynomial.sum_def, Finset.sum_mul] 1219 1220 lemma eval_rightMul (d q : Polynomial B) : 1221 eval D O (rightMul D d q) = eval D O d * eval D O q := by 1222 change (evalAddHom D O) (rightMul D d q) = _ 1223 unfold rightMul 1224 change (evalAddHom D O) (∑ j ∈ q.support, 1225 rightMulMonomial D d (q.coeff j) j) = _ 1226 rw [map_sum] 1227 change (∑ j ∈ q.support, 1228 eval D O (rightMulMonomial D d (q.coeff j) j)) = _ 1229 simp_rw [eval_rightMulMonomial] 1230 unfold eval 1231 simp only [Polynomial.sum_def] 1232 rw [Finset.mul_sum] 1233 1234 theorem eval_right_division_sound [Nontrivial B] (d p : Polynomial B) 1235 (hd : d.Monic) : 1236 ∃ q r : Polynomial B, 1237 eval D O p = eval D O d * eval D O q + eval D O r ∧ 1238 (r = 0 ∨ r.natDegree < d.natDegree) := by 1239 obtain ⟨q, r, hdecomp, hrem⟩ := right_division_exists D d p hd 1240 refine ⟨q, r, ?_, hrem⟩ 1241 rw [hdecomp, eval_add D O, eval_rightMul D O] 1242 1243 end OreAmbient 1244 1245 end OreDivision 1246 1247 end 1248 end AlgebraicAnalysis 1249