This project (Stafford38) · 1029fdb382eee06e7b59bcf32801f40931e2079a
1 module 2 public import Stafford38.EvolutionaryCertificate 3 public import Mathlib.Algebra.Polynomial.RingDivision 4 public import Mathlib.RingTheory.Coprime.Lemmas 5 public import Mathlib.RingTheory.Nilpotent.Defs 6 public import Mathlib.Algebra.Ring.GeomSum 7 8 @[expose] public section 9 10 /-! 11 # Pure-power Weyl certificates 12 13 This file formalizes the all-degree part of the one-variable Weyl--Bézout 14 calculation. It works in an arbitrary ring containing a Weyl pair 15 `d * x - x * d = 1`; the only coefficient input is the ordinary polynomial 16 Bézout relation between the two disjoint Euler products. 17 18 The remaining universal monic problem is not hidden here: it is the passage 19 from a pure power to a general monic polynomial. 20 -/ 21 22 namespace Stafford 23 24 noncomputable section 25 26 variable {A : Type*} [Ring A] [Algebra ℚ A] 27 28 abbrev theta (x d : A) : A := Stafford38.Evolution.euler x d 29 30 abbrev falling (x d : A) : ℕ → A := 31 Stafford38.Evolution.falling (theta x d) 32 33 abbrev rising (x d : A) : ℕ → A := 34 Stafford38.Evolution.rising (theta x d) 35 36 abbrev fallingPoly : ℕ → Polynomial ℚ := Stafford38.Evolution.fallingPoly ℚ 37 38 abbrev risingPoly : ℕ → Polynomial ℚ := Stafford38.Evolution.risingPoly ℚ 39 40 private lemma fallingPoly_eq_prod (n : ℕ) : 41 fallingPoly n = ∏ i ∈ Finset.range n, 42 (Polynomial.X - Polynomial.C (i : ℚ)) := by 43 change Stafford38.Evolution.fallingPoly ℚ n = _ 44 induction n with 45 | zero => simp [Stafford38.Evolution.fallingPoly] 46 | succ n ih => 47 rw [Stafford38.Evolution.fallingPoly_succ, ih, Finset.prod_range_succ] 48 49 private lemma risingPoly_eq_prod (n : ℕ) : 50 risingPoly n = ∏ i ∈ Finset.range n, 51 (Polynomial.X + Polynomial.C ((i + 1 : ℕ) : ℚ)) := by 52 change Stafford38.Evolution.risingPoly ℚ n = _ 53 induction n with 54 | zero => simp [Stafford38.Evolution.risingPoly] 55 | succ n ih => 56 rw [Stafford38.Evolution.risingPoly_succ, ih, Finset.prod_range_succ] 57 congr 1 58 congr 1 59 push_cast 60 rfl 61 62 private lemma falling_factor_coprime_rising_factor (i j : ℕ) : 63 IsCoprime (Polynomial.X - Polynomial.C (i : ℚ)) 64 (Polynomial.X + Polynomial.C ((j + 1 : ℕ) : ℚ)) := by 65 have hunit : IsUnit ((i : ℚ) - -((j + 1 : ℕ) : ℚ)) := by 66 apply isUnit_iff_ne_zero.mpr 67 have hi : 0 ≤ (i : ℚ) := by positivity 68 have hj : 0 < ((j + 1 : ℕ) : ℚ) := by 69 exact_mod_cast Nat.succ_pos j 70 have hpos : 0 < (i : ℚ) - -((j + 1 : ℕ) : ℚ) := by linarith 71 exact ne_of_gt hpos 72 convert Polynomial.isCoprime_X_sub_C_of_isUnit_sub hunit using 1 73 · simp [sub_eq_add_neg] 74 75 private lemma fallingPoly_isCoprime_risingPoly (n : ℕ) : 76 IsCoprime (fallingPoly n) (risingPoly n) := by 77 rw [fallingPoly_eq_prod, risingPoly_eq_prod] 78 apply IsCoprime.prod_left 79 intro i hi 80 apply IsCoprime.prod_right 81 intro j hj 82 exact falling_factor_coprime_rising_factor i j 83 84 private lemma x_pow_mul_d_pow 85 (x d : A) (h : d * x = x * d + 1) : ∀ n : ℕ, 86 x ^ n * d ^ n = falling x d n := by 87 intro n 88 simpa [falling, theta] using 89 (Stafford38.Evolution.pow_mul_pow_eq_falling (x := x) (p := d) h n) 90 91 private lemma d_pow_mul_x_pow 92 (x d : A) (h : d * x = x * d + 1) : ∀ n : ℕ, 93 d ^ n * x ^ n = rising x d n := by 94 intro n 95 simpa [rising, theta] using 96 (Stafford38.Evolution.pow_mul_pow_eq_rising (x := x) (p := d) h n) 97 98 private lemma eval_fallingPoly 99 (x d : A) 100 (ev : Polynomial ℚ →+* A) 101 (hev : ev Polynomial.X = theta x d) 102 (hC : ∀ q : ℚ, ev (Polynomial.C q) = (algebraMap ℚ A) q) : 103 ev (fallingPoly n) = falling x d n := by 104 induction n with 105 | zero => simp [fallingPoly, falling] 106 | succ n ih => 107 change ev (Stafford38.Evolution.fallingPoly ℚ (n + 1)) = 108 Stafford38.Evolution.falling (Stafford38.Evolution.euler x d) (n + 1) 109 rw [Stafford38.Evolution.fallingPoly_succ, map_mul, map_sub, hev, hC] 110 push_cast 111 rw [ih] 112 simp [falling, theta, Stafford38.Evolution.falling_succ] 113 114 private lemma eval_risingPoly 115 (x d : A) 116 (ev : Polynomial ℚ →+* A) 117 (hev : ev Polynomial.X = theta x d) 118 (hC : ∀ q : ℚ, ev (Polynomial.C q) = (algebraMap ℚ A) q) : 119 ev (risingPoly n) = rising x d n := by 120 induction n with 121 | zero => simp [risingPoly, rising] 122 | succ n ih => 123 change ev (Stafford38.Evolution.risingPoly ℚ (n + 1)) = 124 Stafford38.Evolution.rising (Stafford38.Evolution.euler x d) (n + 1) 125 rw [Stafford38.Evolution.risingPoly_succ, map_mul, map_add, hev, hC] 126 push_cast 127 rw [ih] 128 simp [rising, theta, Stafford38.Evolution.rising_succ] 129 130 /-- Evaluation of a rational polynomial at the Euler element `x*d`. -/ 131 def eulerPolynomialEval (x d : A) : Polynomial ℚ →+* A := 132 Polynomial.eval₂RingHom' (algebraMap ℚ A) (theta x d) 133 (fun q => Algebra.commutes q (theta x d)) 134 135 @[simp] theorem eulerPolynomialEval_X (x d : A) : 136 eulerPolynomialEval x d Polynomial.X = x * d := by 137 change Polynomial.eval₂ (algebraMap ℚ A) (theta x d) Polynomial.X = x * d 138 rw [Polynomial.eval₂_X (algebraMap ℚ A) (theta x d)] 139 rfl 140 141 @[simp] theorem eulerPolynomialEval_C (x d : A) (q : ℚ) : 142 eulerPolynomialEval x d (Polynomial.C q) = algebraMap ℚ A q := by 143 change Polynomial.eval₂ (algebraMap ℚ A) (theta x d) (Polynomial.C q) = 144 algebraMap ℚ A q 145 exact Polynomial.eval₂_C (algebraMap ℚ A) (theta x d) 146 147 /-- Equal powers `x^n*d^n` are a rational polynomial in the Euler element. -/ 148 theorem exists_eulerPolynomial_x_pow_mul_d_pow 149 (x d : A) (h : d * x = x * d + 1) (n : ℕ) : 150 ∃ f : Polynomial ℚ, 151 eulerPolynomialEval x d f = x ^ n * d ^ n := by 152 refine ⟨fallingPoly n, ?_⟩ 153 rw [eval_fallingPoly x d (eulerPolynomialEval x d) 154 (by rw [eulerPolynomialEval_X]; rfl) (by intro q; simp)] 155 exact (x_pow_mul_d_pow x d h n).symm 156 157 /-- Equal powers `d^n*x^n` are also a rational polynomial in `x*d`. -/ 158 theorem exists_eulerPolynomial_d_pow_mul_x_pow 159 (x d : A) (h : d * x = x * d + 1) (n : ℕ) : 160 ∃ f : Polynomial ℚ, 161 eulerPolynomialEval x d f = d ^ n * x ^ n := by 162 refine ⟨risingPoly n, ?_⟩ 163 rw [eval_risingPoly x d (eulerPolynomialEval x d) 164 (by rw [eulerPolynomialEval_X]; rfl) (by intro q; simp)] 165 exact (d_pow_mul_x_pow x d h n).symm 166 167 /-- The pure-power certificate, assuming the ordinary Euler products are 168 coprime in the coefficient polynomial ring. -/ 169 theorem pure_power_weyl_certificate 170 (x d : A) (h : d * x = x * d + 1) (n : ℕ) 171 (a b : Polynomial ℚ) 172 (hab : a * fallingPoly n + b * risingPoly n = 1) : 173 ∃ p q : A, 1 = p * (x ^ n) + q * (x ^ n * d ^ n) := by 174 let θ : A := theta x d 175 let ev : Polynomial ℚ →+* A := 176 Polynomial.eval₂RingHom' (algebraMap ℚ A) θ (fun q => Algebra.commutes q θ) 177 have hfall : ev (fallingPoly n) = x ^ n * d ^ n := by 178 rw [eval_fallingPoly x d ev 179 (by change Polynomial.eval₂ (algebraMap ℚ A) θ Polynomial.X = _ 180 exact Polynomial.eval₂_X (algebraMap ℚ A) θ) 181 (by intro q 182 change Polynomial.eval₂ (algebraMap ℚ A) θ (Polynomial.C q) = _ 183 exact Polynomial.eval₂_C (algebraMap ℚ A) θ)] 184 exact (x_pow_mul_d_pow x d h n).symm 185 have hrise : ev (risingPoly n) = d ^ n * x ^ n := by 186 rw [eval_risingPoly x d ev 187 (by change Polynomial.eval₂ (algebraMap ℚ A) θ Polynomial.X = _ 188 exact Polynomial.eval₂_X (algebraMap ℚ A) θ) 189 (by intro q 190 change Polynomial.eval₂ (algebraMap ℚ A) θ (Polynomial.C q) = _ 191 exact Polynomial.eval₂_C (algebraMap ℚ A) θ)] 192 exact (d_pow_mul_x_pow x d h n).symm 193 have hev := congrArg ev hab 194 rw [map_add, map_mul, map_mul, hfall, hrise, map_one] at hev 195 refine ⟨ev b * d ^ n, ev a, ?_⟩ 196 rw [mul_assoc] 197 rw [add_comm] at hev 198 exact hev.symm 199 200 /- The Euler products are coprime over `ℚ`, so the coefficient hypothesis in 201 the transfer theorem is available in every degree. -/ 202 theorem pure_power_weyl_certificate_exists 203 (x d : A) (h : d * x = x * d + 1) (n : ℕ) : 204 ∃ p q : A, 1 = p * (x ^ n) + q * (x ^ n * d ^ n) := by 205 rcases fallingPoly_isCoprime_risingPoly n with ⟨a, b, hab⟩ 206 exact pure_power_weyl_certificate x d h n a b hab 207 208 /-- The two Euler products admit a Bezout identity with right cofactors. 209 This is the orientation used by the canonical right quotient. -/ 210 theorem euler_products_right_bezout_exists 211 (x d : A) (h : d * x = x * d + 1) (n : ℕ) : 212 ∃ u v : A, 213 (d ^ n * x ^ n) * u + (x ^ n * d ^ n) * v = 1 := by 214 rcases fallingPoly_isCoprime_risingPoly n with ⟨a, b, hab⟩ 215 let θ : A := theta x d 216 let ev : Polynomial ℚ →+* A := 217 Polynomial.eval₂RingHom' (algebraMap ℚ A) θ 218 (fun q => Algebra.commutes q θ) 219 have hfall : ev (fallingPoly n) = x ^ n * d ^ n := by 220 rw [eval_fallingPoly x d ev 221 (by change Polynomial.eval₂ (algebraMap ℚ A) θ Polynomial.X = _ 222 exact Polynomial.eval₂_X (algebraMap ℚ A) θ) 223 (by intro q 224 change Polynomial.eval₂ (algebraMap ℚ A) θ (Polynomial.C q) = _ 225 exact Polynomial.eval₂_C (algebraMap ℚ A) θ)] 226 exact (x_pow_mul_d_pow x d h n).symm 227 have hrise : ev (risingPoly n) = d ^ n * x ^ n := by 228 rw [eval_risingPoly x d ev 229 (by change Polynomial.eval₂ (algebraMap ℚ A) θ Polynomial.X = _ 230 exact Polynomial.eval₂_X (algebraMap ℚ A) θ) 231 (by intro q 232 change Polynomial.eval₂ (algebraMap ℚ A) θ (Polynomial.C q) = _ 233 exact Polynomial.eval₂_C (algebraMap ℚ A) θ)] 234 exact (d_pow_mul_x_pow x d h n).symm 235 have hpoly : risingPoly n * b + fallingPoly n * a = 1 := by 236 rw [mul_comm (risingPoly n) b, mul_comm (fallingPoly n) a, add_comm] 237 exact hab 238 have hev := congrArg ev hpoly 239 rw [map_add, map_mul, map_mul, hrise, hfall, map_one] at hev 240 exact ⟨ev b, ev a, hev⟩ 241 242 #print axioms euler_products_right_bezout_exists 243 244 /-- The right Bezout cofactors may be retained as rational polynomials in the 245 Euler element. -/ 246 theorem euler_products_polynomial_right_bezout_exists 247 (x d : A) (h : d * x = x * d + 1) (n : ℕ) : 248 ∃ u v : Polynomial ℚ, 249 (d ^ n * x ^ n) * eulerPolynomialEval x d u + 250 (x ^ n * d ^ n) * eulerPolynomialEval x d v = 1 := by 251 rcases fallingPoly_isCoprime_risingPoly n with ⟨a, b, hab⟩ 252 have hfall : eulerPolynomialEval x d (fallingPoly n) = 253 x ^ n * d ^ n := by 254 rw [eval_fallingPoly x d (eulerPolynomialEval x d) 255 (by rw [eulerPolynomialEval_X]; rfl) (by intro q; simp)] 256 exact (x_pow_mul_d_pow x d h n).symm 257 have hrise : eulerPolynomialEval x d (risingPoly n) = 258 d ^ n * x ^ n := by 259 rw [eval_risingPoly x d (eulerPolynomialEval x d) 260 (by rw [eulerPolynomialEval_X]; rfl) (by intro q; simp)] 261 exact (d_pow_mul_x_pow x d h n).symm 262 have hpoly : risingPoly n * b + fallingPoly n * a = 1 := by 263 rw [mul_comm (risingPoly n) b, mul_comm (fallingPoly n) a, add_comm] 264 exact hab 265 have hev := congrArg (eulerPolynomialEval x d) hpoly 266 rw [map_add, map_mul, map_mul, hrise, hfall, map_one] at hev 267 exact ⟨b, a, hev⟩ 268 269 #print axioms euler_products_polynomial_right_bezout_exists 270 271 theorem pure_power_translate_weyl_certificate_exists 272 (x d c : A) (h : d * x = x * d + 1) 273 (hcd : Commute c d) (n : ℕ) : 274 ∃ p q : A, 1 = p * ((x - c) ^ n) + q * ((x - c) ^ n * d ^ n) := by 275 have hshift : d * (x - c) = (x - c) * d + 1 := by 276 calc 277 d * (x - c) = d * x - d * c := by rw [mul_sub] 278 _ = x * d + 1 - c * d := by rw [h, ← hcd.eq] 279 _ = (x - c) * d + 1 := by rw [sub_mul]; noncomm_ring 280 exact pure_power_weyl_certificate_exists (x - c) d hshift n 281 282 /-- A nilpotent central constant can be added to a pure power without losing 283 the Weyl--Bézout certificate. This is the formal constant-coefficient 284 instance of the nilpotent thickening step; the general nilpotent coefficient 285 ideal is deliberately not hidden in this statement. -/ 286 theorem nilpotent_constant_weyl_certificate_exists 287 (x d e : A) (h : d * x = x * d + 1) 288 (he : IsNilpotent e) (hcentral : ∀ a : A, Commute e a) (n : ℕ) : 289 ∃ p q : A, 290 1 = p * (x ^ n - e) + q * ((x ^ n - e) * d ^ n) := by 291 rcases fallingPoly_isCoprime_risingPoly n with ⟨a, b, hab⟩ 292 have hpow := pure_power_weyl_certificate x d h n a b hab 293 rcases hpow with ⟨p0, q0, hpow⟩ 294 let H : A := x ^ n - e 295 let r : A := p0 * e + q0 * (e * d ^ n) 296 have hrewrite : 297 1 - r = p0 * H + q0 * (H * d ^ n) := by 298 dsimp [r, H] 299 have hx : x ^ n = (x ^ n - e) + e := by noncomm_ring 300 rw [hpow, hx] 301 noncomm_ring 302 have hcomm : Commute e (p0 + q0 * d ^ n) := hcentral _ 303 have hr : r = e * (p0 + q0 * d ^ n) := by 304 dsimp [r] 305 calc 306 p0 * e + q0 * (e * d ^ n) = e * p0 + (q0 * e) * d ^ n := by 307 rw [← hcentral p0 |>.eq] 308 noncomm_ring 309 _ = e * p0 + (e * q0) * d ^ n := by rw [hcentral q0 |>.eq] 310 _ = e * (p0 + q0 * d ^ n) := by noncomm_ring 311 have hrnil : IsNilpotent r := by 312 rw [hr] 313 exact hcomm.isNilpotent_mul_right he 314 rcases hrnil with ⟨N, hN⟩ 315 let g : A := ∑ i ∈ Finset.range N, r ^ i 316 have hgeom : g * (1 - r) = 1 - r ^ N := by 317 dsimp [g] 318 rw [show (1 : A) - r = -(r - 1) by noncomm_ring, mul_neg] 319 rw [geom_sum_mul] 320 noncomm_ring 321 have hone : (1 : A) = g * (1 - r) := by 322 rw [hgeom, hN, sub_zero] 323 have hfinal : 324 1 = (g * p0) * H + (g * q0) * (H * d ^ n) := by 325 calc 326 1 = g * (1 - r) := hone 327 _ = g * (p0 * H + q0 * (H * d ^ n)) := by rw [hrewrite] 328 _ = (g * p0) * H + (g * q0) * (H * d ^ n) := by noncomm_ring 329 refine ⟨g * p0, g * q0, ?_⟩ 330 simpa [H] using hfinal 331 332 end 333 end Stafford 334