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