AlgebraicAnalysis/Ore/RightDivision.lean

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