AlgebraicAnalysis/LinearAlgebra/FiniteTaylorReconstruction.lean

AlgebraicAnalysis library Β· bbbbf3fc358ca8100b158cec4cf47f336ab70163

1 module
2 public import Mathlib.Algebra.Module.LinearMap.End
3 public import Mathlib.Data.Nat.Factorial.Cast
4 public import Mathlib.Data.Nat.Choose.Basic
5 public import Mathlib.Tactic
6 
7 @[expose] public section
8 
9 /-!
10 # Finite Taylor reconstruction
11 
12 Application-independent finite Taylor reconstruction for a nilpotent
13 endomorphism. Extracted from Stafford38 commit c8a513d553b24c7c08da82f496c44dbbaeb1f2fc.
14 -/
15 
16 namespace AlgebraicAnalysis.FiniteTaylorReconstruction
17 
18 open scoped BigOperators
19 
20 variable {π•œ : Type*} [Field π•œ] [CharZero π•œ]
21 variable {V : Type*} [AddCommGroup V] [Module π•œ V]
22 
23 /-- The finite alternating Taylor projector associated with two endomorphisms. -/
24 def projectorMapG (K : β„•) (S D : V β†’β‚—[π•œ] V) : V β†’β‚—[π•œ] V :=
25   βˆ‘ r ∈ Finset.range (K + 1),
26     ((-1 : π•œ) ^ r / (r.factorial : π•œ)) β€’ (S ^ r * D ^ r)
27 
28 omit [CharZero π•œ] in
29 private lemma projectorMap_term_all
30     (K j : β„•) (S D : V β†’β‚—[π•œ] V) (x : V) :
31     ((S ^ j * projectorMapG K S D * D ^ j) x) =
32       βˆ‘ r ∈ Finset.range (K + 1),
33         ((-1 : π•œ) ^ r / (r.factorial : π•œ)) β€’
34           ((S ^ (j + r) * D ^ (j + r)) x) := by
35   unfold projectorMapG
36   simp only [Finset.mul_sum, Finset.sum_mul, Finset.sum_apply,
37     smul_mul_assoc, mul_smul_comm, smul_add, Module.End.mul_apply]
38   rw [LinearMap.sum_apply]
39   apply Finset.sum_congr rfl
40   intro r hr
41   change ((-1 : π•œ) ^ r / (r.factorial : π•œ)) β€’
42       ((S ^ j * (S ^ r * D ^ r) * D ^ j) x) =
43     ((-1 : π•œ) ^ r / (r.factorial : π•œ)) β€’
44       ((S ^ (j + r) * D ^ (j + r)) x)
45   congr 1
46   change ((S ^ j * (S ^ r * D ^ r) * D ^ j) x) = _
47   calc
48     (S ^ j * (S ^ r * D ^ r) * D ^ j) x =
49         ((S ^ j * S ^ r) * (D ^ r * D ^ j)) x := by
50           congr 1
51     _ = (S ^ (j + r) * D ^ (r + j)) x := by
52           rw [← pow_add, ← pow_add]
53     _ = (S ^ (j + r) * D ^ (j + r)) x := by
54           rw [Nat.add_comm r j]
55 
56 private lemma triangular_reindex_all {Ξ± : Type*} [AddCommMonoid Ξ±]
57     (K : β„•) (f : β„• β†’ β„• β†’ Ξ±) :
58     (βˆ‘ j ∈ Finset.range (K + 1),
59       βˆ‘ r ∈ Finset.range (K + 1 - j), f j r) =
60       βˆ‘ q ∈ Finset.range (K + 1),
61         βˆ‘ j ∈ Finset.range (q + 1), f j (q - j) := by
62   let s : Finset (Ξ£ _ : β„•, β„•) :=
63     (Finset.range (K + 1)).sigma (fun j => Finset.range (K + 1 - j))
64   let t : Finset (Ξ£ _ : β„•, β„•) :=
65     (Finset.range (K + 1)).sigma (fun q => Finset.range (q + 1))
66   have hs :
67       (βˆ‘ j ∈ Finset.range (K + 1),
68         βˆ‘ r ∈ Finset.range (K + 1 - j), f j r) =
69         βˆ‘ a ∈ s, f a.1 a.2 := by
70     dsimp [s]
71     rw [Finset.sum_sigma']
72   have ht :
73       (βˆ‘ q ∈ Finset.range (K + 1),
74         βˆ‘ j ∈ Finset.range (q + 1), f j (q - j)) =
75         βˆ‘ a ∈ t, f a.2 (a.1 - a.2) := by
76     dsimp [t]
77     rw [Finset.sum_sigma']
78   rw [hs, ht]
79   apply Finset.sum_bij (fun a ha => ⟨a.1 + a.2, a.1⟩) ?_ ?_ ?_ ?_
80   Β· intro a ha
81     rw [Finset.mem_sigma] at ha ⊒
82     constructor
83     Β· simp only [Finset.mem_range]
84       have ha1 : a.1 < K + 1 := Finset.mem_range.mp ha.1
85       have ha2 : a.2 < K + 1 - a.1 := Finset.mem_range.mp ha.2
86       omega
87     Β· simp only [Finset.mem_range]
88       omega
89   Β· intro a₁ ha₁ aβ‚‚ haβ‚‚ h
90     simp only [Sigma.mk.inj_iff] at h
91     rcases h with ⟨hsum, hfirst⟩
92     have hfirst' : a₁.1 = aβ‚‚.1 := eq_of_heq hfirst
93     apply Sigma.ext
94     Β· exact hfirst'
95     Β· simpa [hfirst'] using (show a₁.2 = aβ‚‚.2 from by omega)
96   Β· intro b hb
97     rw [Finset.mem_sigma] at hb
98     use ⟨b.2, b.1 - b.2⟩
99     have hsrc : (⟨b.2, b.1 - b.2⟩ : Ξ£ _ : β„•, β„•) ∈ s := by
100       rw [Finset.mem_sigma]
101       constructor
102       Β· have hbq : b.1 < K + 1 := Finset.mem_range.mp hb.1
103         have hbj : b.2 < b.1 + 1 := Finset.mem_range.mp hb.2
104         simpa only [Finset.mem_range] using (show b.2 < K + 1 by omega)
105       Β· simp only [Finset.mem_range]
106         have hbq : b.1 < K + 1 := Finset.mem_range.mp hb.1
107         have hbj : b.2 < b.1 + 1 := Finset.mem_range.mp hb.2
108         omega
109     refine ⟨hsrc, ?_⟩
110     apply Sigma.ext
111     Β· change b.2 + (b.1 - b.2) = b.1
112       have hbj : b.2 ≀ b.1 := Nat.le_of_lt_succ (Finset.mem_range.mp hb.2)
113       omega
114     Β· simp
115   Β· intro a ha
116     simp
117 
118 omit [CharZero π•œ] in
119 private lemma alternating_choose_sum (q : β„•) :
120     (βˆ‘ j ∈ Finset.range (q + 1),
121       ((-1 : π•œ) ^ (q - j) * (q.choose j : π•œ))) =
122       if q = 0 then 1 else 0 := by
123   have h := add_pow (1 : π•œ) (-1 : π•œ) q
124   rw [show (1 : π•œ) + (-1 : π•œ) = 0 by norm_num] at h
125   simp only [one_pow, one_mul] at h
126   by_cases hq : q = 0
127   Β· subst q
128     norm_num at h ⊒
129   · simp [hq] at h ⊒
130     simpa [mul_comm] using h.symm
131 
132 private lemma reciprocal_binomial_term (q j : β„•) (hjq : j ≀ q) :
133     (1 / (j.factorial : π•œ)) *
134         ((-1 : π•œ) ^ (q - j) / ((q - j).factorial : π•œ)) =
135       (1 / (q.factorial : π•œ)) *
136         ((-1 : π•œ) ^ (q - j) * (q.choose j : π•œ)) := by
137   have hfac : q.choose j * j.factorial * (q - j).factorial = q.factorial :=
138     Nat.choose_mul_factorial_mul_factorial hjq
139   have hfacQ : (q.choose j : π•œ) * (j.factorial : π•œ) *
140       ((q - j).factorial : π•œ) = (q.factorial : π•œ) := by
141     exact_mod_cast hfac
142   have hjfac : (j.factorial : π•œ) β‰  0 := by
143     exact_mod_cast Nat.factorial_ne_zero j
144   have hqfac : (q.factorial : π•œ) β‰  0 := by
145     exact_mod_cast Nat.factorial_ne_zero q
146   have hqjfac : ((q - j).factorial : π•œ) β‰  0 := by
147     exact_mod_cast Nat.factorial_ne_zero (q - j)
148   have hrec :
149       (1 / (j.factorial : π•œ)) * (1 / ((q - j).factorial : π•œ)) =
150         (q.choose j : π•œ) / (q.factorial : π•œ) := by
151     field_simp
152     rw [← hfacQ]
153     ring
154   calc
155     (1 / (j.factorial : π•œ)) *
156         ((-1 : π•œ) ^ (q - j) / ((q - j).factorial : π•œ)) =
157         ((-1 : π•œ) ^ (q - j)) *
158           ((1 / (j.factorial : π•œ)) * (1 / ((q - j).factorial : π•œ))) := by
159             ring
160     _ = ((-1 : π•œ) ^ (q - j)) *
161           ((q.choose j : π•œ) / (q.factorial : π•œ)) := by rw [hrec]
162     _ = (1 / (q.factorial : π•œ)) *
163           ((-1 : π•œ) ^ (q - j) * (q.choose j : π•œ)) := by ring
164 
165 private lemma reciprocal_binomial_sum (q : β„•) :
166     (βˆ‘ j ∈ Finset.range (q + 1),
167       (1 / (j.factorial : π•œ)) *
168         ((-1 : π•œ) ^ (q - j) / ((q - j).factorial : π•œ))) =
169       if q = 0 then 1 else 0 := by
170   rw [show (βˆ‘ j ∈ Finset.range (q + 1),
171       (1 / (j.factorial : π•œ)) *
172         ((-1 : π•œ) ^ (q - j) / ((q - j).factorial : π•œ))) =
173       βˆ‘ j ∈ Finset.range (q + 1),
174         (1 / (q.factorial : π•œ)) *
175           ((-1 : π•œ) ^ (q - j) * (q.choose j : π•œ)) by
176     apply Finset.sum_congr rfl
177     intro j hj
178     exact reciprocal_binomial_term q j
179       (Nat.le_of_lt_succ (Finset.mem_range.mp hj))]
180   rw [← Finset.mul_sum]
181   rw [alternating_choose_sum]
182   by_cases hq : q = 0
183   Β· simp [hq]
184   Β· simp [hq]
185 
186 omit [CharZero π•œ] in
187 private lemma projectorMap_term_trim
188     (K j : β„•) (S D : V β†’β‚—[π•œ] V) (x : V)
189     (hj : j ≀ K) (hnil : (D ^ (K + 1)) x = 0) :
190     ((S ^ j * projectorMapG K S D * D ^ j) x) =
191       βˆ‘ r ∈ Finset.range (K + 1 - j),
192         ((-1 : π•œ) ^ r / (r.factorial : π•œ)) β€’
193           ((S ^ (j + r) * D ^ (j + r)) x) := by
194   rw [projectorMap_term_all]
195   symm
196   apply Finset.sum_subset
197   Β· intro r hr
198     exact Finset.mem_range.mpr (by
199       have hr' := Finset.mem_range.mp hr
200       omega)
201   Β· intro r hrbig hrsmall
202     have hrbig' := Finset.mem_range.mp hrbig
203     have hrsmall' : K + 1 - j ≀ r := by
204       exact Nat.le_of_not_gt (fun hlt => hrsmall (Finset.mem_range.mpr hlt))
205     have hpow : (D ^ (j + r)) x = 0 := by
206       apply Module.End.pow_map_zero_of_le (m := x) (k := K + 1) (l := j + r)
207       Β· omega
208       Β· exact hnil
209     simp [Module.End.mul_apply, hpow]
210 
211 /-- The all-order finite Taylor reconstruction for a nilpotent derivative. -/
212 theorem reconstruction_all
213     (K : β„•) (S D : V β†’β‚—[π•œ] V) (x : V)
214     (hnil : (D ^ (K + 1)) x = 0) :
215     x =
216       βˆ‘ j ∈ Finset.range (K + 1),
217         ((1 : π•œ) / (j.factorial : π•œ)) β€’
218           ((S ^ j * projectorMapG K S D * D ^ j) x) := by
219   have hexpand :
220       (βˆ‘ j ∈ Finset.range (K + 1),
221         ((1 : π•œ) / (j.factorial : π•œ)) β€’
222           ((S ^ j * projectorMapG K S D * D ^ j) x)) =
223       βˆ‘ j ∈ Finset.range (K + 1),
224         βˆ‘ r ∈ Finset.range (K + 1 - j),
225           (((1 : π•œ) / (j.factorial : π•œ)) *
226               ((-1 : π•œ) ^ r / (r.factorial : π•œ))) β€’
227             ((S ^ (j + r) * D ^ (j + r)) x) := by
228     apply Finset.sum_congr rfl
229     intro j hj
230     have hjK : j ≀ K := Nat.le_of_lt_succ (Finset.mem_range.mp hj)
231     rw [projectorMap_term_trim K j S D x hjK hnil]
232     rw [Finset.smul_sum]
233     apply Finset.sum_congr rfl
234     intro r hr
235     rw [smul_smul]
236   rw [hexpand, triangular_reindex_all]
237   have hreindex :
238       (βˆ‘ q ∈ Finset.range (K + 1),
239         βˆ‘ j ∈ Finset.range (q + 1),
240           (((1 : π•œ) / (j.factorial : π•œ)) *
241               ((-1 : π•œ) ^ (q - j) / ((q - j).factorial : π•œ))) β€’
242             ((S ^ (j + (q - j)) * D ^ (j + (q - j))) x)) =
243       βˆ‘ q ∈ Finset.range (K + 1),
244         βˆ‘ j ∈ Finset.range (q + 1),
245           (((1 : π•œ) / (j.factorial : π•œ)) *
246               ((-1 : π•œ) ^ (q - j) / ((q - j).factorial : π•œ))) β€’
247             ((S ^ q * D ^ q) x) := by
248     apply Finset.sum_congr rfl
249     intro q hq
250     apply Finset.sum_congr rfl
251     intro j hj
252     have hjq : j ≀ q := Nat.le_of_lt_succ (Finset.mem_range.mp hj)
253     rw [Nat.add_sub_of_le hjq]
254   rw [hreindex]
255   have hcollapse :
256       (βˆ‘ q ∈ Finset.range (K + 1),
257         βˆ‘ j ∈ Finset.range (q + 1),
258           (((1 : π•œ) / (j.factorial : π•œ)) *
259               ((-1 : π•œ) ^ (q - j) / ((q - j).factorial : π•œ))) β€’
260             ((S ^ q * D ^ q) x)) = x := by
261     -- The inner scalar convolution is the inverse factorial binomial sum.
262     -- The remaining q=0 term is exactly x; all q>0 terms are zero.
263     have hterm (q : β„•) :
264         (βˆ‘ j ∈ Finset.range (q + 1),
265           (((1 : π•œ) / (j.factorial : π•œ)) *
266               ((-1 : π•œ) ^ (q - j) / ((q - j).factorial : π•œ))) β€’
267             ((S ^ q * D ^ q) x)) =
268           (if q = 0 then (1 : π•œ) else 0) β€’ ((S ^ q * D ^ q) x) := by
269       rw [← Finset.sum_smul]
270       rw [reciprocal_binomial_sum]
271     simp_rw [hterm]
272     simp
273   exact hcollapse.symm
274 
275 /-!
276 The following wrapper turns the endomorphism statement into the concrete
277 algebraic form used in a Weyl chart.  It deliberately stops at the abstract
278 ring/module interface: the Aβ‚‚-specific work of constructing `s`, proving
279 `D s = 1`, and proving nilpotence on the chosen element remains external.
280 -/
281 end AlgebraicAnalysis.FiniteTaylorReconstruction
282