This project (Stafford38) · 1029fdb382eee06e7b59bcf32801f40931e2079a
1 module 2 public import Mathlib.Algebra.Polynomial.Eval.Defs 3 public import Mathlib.Algebra.Polynomial.AlgebraMap 4 public import Mathlib.Algebra.Module.NatInt 5 public import Mathlib.Tactic.NoncommRing 6 public import Mathlib.Tactic.Push 7 8 @[expose] public section 9 10 /-! 11 # The evolutionary Stafford certificate 12 13 Let `D` be a ring containing a Weyl pair `p * x - x * p = 1`, let `B` be any set 14 of elements commuting with both `x` and `p`, and let 15 16 d = p ^ r - ∑ⱼ aⱼ * x ^ j, aⱼ ∈ B. 17 18 This file machine-checks that the right ideal generated by `d` and `x ^ r * d` 19 is the whole ring, with the Stafford cofactor fixed to `x ^ r` independently of 20 `B`, of the coefficients `aⱼ`, and of the size of the support. 21 22 The proof has three separated layers. 23 24 * `stafford_of_bezout` is a pure ring identity: it consumes a corner 25 commutator, an elimination identity, and a Bézout identity, and produces the 26 certificate. No Weyl structure is used. 27 * The `Weyl` section proves the Euler shift calculus and the two factorial 28 identities `p ^ r * x ^ r = rising E r`, `x ^ r * p ^ r = falling E r`, where 29 `E = x * p`. 30 * `potential_elimination` performs the simultaneous shifted cancellation that 31 removes every potential coefficient at once. 32 33 `evolution_stafford_certificate` assembles the three. The Bézout identity it 34 consumes is discharged in `Stafford38.EulerRootSeparation`, which proves the 35 needed polynomial coprimality under every positive integer shift. 36 37 Convention: all ideals here are **right** ideals, matching the repository 38 convention. Statements are written as `d * R + x ^ r * d * S = 1`. 39 -/ 40 41 namespace Stafford38.Evolution 42 43 open Polynomial 44 45 /-! ## Layer 1: the pure ring assembly -/ 46 47 section Assembly 48 49 variable {D : Type*} [Ring D] 50 51 /-- The certificate assembly. `c` is the corner commutator `d * F - F * d`, 52 `h` is the eliminated polynomial, `q` the elimination cofactor, and `a`, `b` a 53 Bézout pair for `c` and `h`. Nothing about `D` beyond ring axioms is used. -/ 54 theorem stafford_of_bezout (d F c h l q a b : D) 55 (hcorner : d * F - F * d = c) 56 (helim : d * F * l = h - c * q) 57 (hbezout : c * a + h * b = 1) : 58 d * (F * a + F * (l + q) * b) + F * d * (-a - q * b) = 1 := by 59 have expand : 60 d * (F * a + F * (l + q) * b) + F * d * (-a - q * b) 61 = (d * F - F * d) * a + (d * F * l) * b + (d * F - F * d) * (q * b) := by 62 noncomm_ring 63 rw [expand, hcorner, helim] 64 have : (h - c * q) * b + c * (q * b) = h * b := by noncomm_ring 65 rw [show c * a + (h - c * q) * b + c * (q * b) = c * a + ((h - c * q) * b + c * (q * b)) by 66 noncomm_ring, this, hbezout] 67 68 end Assembly 69 70 /-! ## Layer 2: the Euler shift calculus -/ 71 72 section Weyl 73 74 variable {D : Type*} [Ring D] {x p : D} 75 76 /-- The Euler operator. -/ 77 def euler (x p : D) : D := x * p 78 79 /-- `(E + 1)(E + 2) ⋯ (E + n)`. -/ 80 def rising (E : D) : ℕ → D 81 | 0 => 1 82 | (n + 1) => rising E n * (E + ((n : D) + 1)) 83 84 /-- `E (E - 1) ⋯ (E - (n-1))`. -/ 85 def falling (E : D) : ℕ → D 86 | 0 => 1 87 | (n + 1) => falling E n * (E - (n : D)) 88 89 @[simp] lemma rising_zero (E : D) : rising E 0 = 1 := rfl 90 @[simp] lemma falling_zero (E : D) : falling E 0 = 1 := rfl 91 92 lemma rising_succ (E : D) (n : ℕ) : 93 rising E (n + 1) = rising E n * (E + ((n : D) + 1)) := rfl 94 95 lemma falling_succ (E : D) (n : ℕ) : 96 falling E (n + 1) = falling E n * (E - (n : D)) := rfl 97 98 variable (hw : p * x = x * p + 1) 99 100 include hw 101 102 /-- `E * x = x * (E + 1)`. -/ 103 lemma euler_mul_x : euler x p * x = x * (euler x p + 1) := by 104 simp only [euler] 105 rw [mul_assoc, hw] 106 107 /-- `E * p = p * (E - 1)`. -/ 108 lemma euler_mul_p : euler x p * p = p * (euler x p - 1) := by 109 simp only [euler] 110 rw [mul_sub, ← mul_assoc, hw] 111 noncomm_ring 112 113 /-- `E * x ^ n = x ^ n * (E + n)`. -/ 114 lemma euler_mul_x_pow (n : ℕ) : 115 euler x p * x ^ n = x ^ n * (euler x p + (n : D)) := by 116 induction n with 117 | zero => simp 118 | succ n ih => 119 have hcast : ((n : D)) * x = x * (n : D) := (Nat.cast_commute n x).eq 120 rw [pow_succ, ← mul_assoc, ih, mul_assoc, add_mul, euler_mul_x hw, hcast] 121 push_cast 122 noncomm_ring 123 124 /-- `E * p ^ n = p ^ n * (E - n)`. -/ 125 lemma euler_mul_p_pow (n : ℕ) : 126 euler x p * p ^ n = p ^ n * (euler x p - (n : D)) := by 127 induction n with 128 | zero => simp 129 | succ n ih => 130 have hcast : ((n : D)) * p = p * (n : D) := (Nat.cast_commute n p).eq 131 rw [pow_succ, ← mul_assoc, ih, mul_assoc, sub_mul, euler_mul_p hw, hcast] 132 push_cast 133 noncomm_ring 134 135 /-- `E ^ m * x ^ n = x ^ n * (E + n) ^ m`. -/ 136 lemma euler_pow_mul_x_pow (m n : ℕ) : 137 euler x p ^ m * x ^ n = x ^ n * (euler x p + (n : D)) ^ m := by 138 induction m with 139 | zero => simp 140 | succ m ih => 141 rw [pow_succ, mul_assoc, euler_mul_x_pow hw, ← mul_assoc, ih, mul_assoc, ← pow_succ] 142 143 /-- The rising factorial identity `p ^ n * x ^ n = (E+1) ⋯ (E+n)`. -/ 144 lemma pow_mul_pow_eq_rising (n : ℕ) : p ^ n * x ^ n = rising (euler x p) n := by 145 induction n with 146 | zero => simp 147 | succ n ih => 148 have hstep : p ^ (n + 1) * x ^ (n + 1) = p ^ n * (euler x p + 1) * x ^ n := by 149 rw [pow_succ, pow_succ' x n, mul_assoc, ← mul_assoc p x, hw] 150 simp only [euler] 151 noncomm_ring 152 rw [hstep, mul_assoc, add_mul, one_mul, euler_mul_x_pow hw, 153 show x ^ n * (euler x p + (n : D)) + x ^ n 154 = x ^ n * (euler x p + ((n : D) + 1)) by noncomm_ring, 155 ← mul_assoc, ih, rising_succ] 156 157 /-- The falling factorial identity `x ^ n * p ^ n = E (E-1) ⋯ (E-(n-1))`. -/ 158 lemma pow_mul_pow_eq_falling (n : ℕ) : x ^ n * p ^ n = falling (euler x p) n := by 159 induction n with 160 | zero => simp 161 | succ n ih => 162 have hstep : x ^ (n + 1) * p ^ (n + 1) = x ^ n * euler x p * p ^ n := by 163 rw [pow_succ x n, pow_succ' p n, mul_assoc] 164 simp only [euler] 165 noncomm_ring 166 rw [hstep, mul_assoc, euler_mul_p_pow hw, ← mul_assoc, ih, falling_succ] 167 168 end Weyl 169 170 section Elimination 171 172 variable {D : Type*} [Ring D] {x p : D} 173 174 /-! ### Polynomial shift calculus -/ 175 176 variable {k : Type*} [CommRing k] [Algebra k D] 177 178 /-- `f(E) * x ^ n = x ^ n * f(E + n)` for every polynomial `f`. -/ 179 lemma aeval_euler_mul_x_pow (hw : p * x = x * p + 1) (n : ℕ) (f : k[X]) : 180 aeval (euler x p) f * x ^ n = x ^ n * aeval (euler x p + (n : D)) f := by 181 induction f using Polynomial.induction_on' with 182 | add f g hf hg => simp only [map_add, add_mul, mul_add, hf, hg] 183 | monomial m a => 184 simp only [aeval_monomial] 185 rw [mul_assoc, euler_pow_mul_x_pow hw, ← mul_assoc, ← mul_assoc, 186 (Algebra.commutes a (x ^ n)).symm] 187 188 /-- An element commuting with `E` commutes with every polynomial in `E`. -/ 189 lemma commute_aeval_euler {a E : D} (h : a * E = E * a) (f : k[X]) : 190 a * aeval E f = aeval E f * a := by 191 have hc : Commute a E := h 192 induction f using Polynomial.induction_on' with 193 | add f g hf hg => simp only [map_add, mul_add, add_mul, hf, hg] 194 | monomial m b => 195 simp only [aeval_monomial] 196 have c1 : Commute a (algebraMap k D b) := (Algebra.commutes b a).symm 197 exact (c1.mul_right (hc.pow_right m)).eq 198 199 /-- The rising factorial as a polynomial. -/ 200 noncomputable def risingPoly (k : Type*) [CommRing k] : ℕ → k[X] 201 | 0 => 1 202 | (n + 1) => risingPoly k n * (X + Polynomial.C ((n : k) + 1)) 203 204 /-- The falling factorial as a polynomial. -/ 205 noncomputable def fallingPoly (k : Type*) [CommRing k] : ℕ → k[X] 206 | 0 => 1 207 | (n + 1) => fallingPoly k n * (X - Polynomial.C (n : k)) 208 209 /-- The Euler corner polynomial `C_r = R₊ - R₋`; its evaluation at `E` is the 210 commutator `p ^ r x ^ r - x ^ r p ^ r`. -/ 211 noncomputable def cornerPoly (k : Type*) [CommRing k] (r : ℕ) : k[X] := 212 risingPoly k r - fallingPoly k r 213 214 @[simp] lemma risingPoly_zero : risingPoly k 0 = 1 := rfl 215 216 lemma risingPoly_succ (n : ℕ) : 217 risingPoly k (n + 1) = risingPoly k n * (X + Polynomial.C ((n : k) + 1)) := rfl 218 219 @[simp] lemma fallingPoly_zero : fallingPoly k 0 = 1 := rfl 220 221 lemma fallingPoly_succ (n : ℕ) : 222 fallingPoly k (n + 1) = fallingPoly k n * (X - Polynomial.C (n : k)) := rfl 223 224 lemma aeval_risingPoly (E : D) (n : ℕ) : 225 aeval E (risingPoly k n) = rising E n := by 226 induction n with 227 | zero => simp [risingPoly_zero] 228 | succ n ih => simp [risingPoly_succ, rising_succ, ih] 229 230 lemma aeval_fallingPoly (E : D) (n : ℕ) : 231 aeval E (fallingPoly k n) = falling E n := by 232 induction n with 233 | zero => simp [fallingPoly_zero] 234 | succ n ih => simp [fallingPoly_succ, falling_succ, ih] 235 236 lemma aeval_cornerPoly (E : D) (r : ℕ) : 237 aeval E (cornerPoly k r) = rising E r - falling E r := by 238 simp [cornerPoly, aeval_risingPoly, aeval_fallingPoly] 239 240 /-! ### Simultaneous elimination of every potential coefficient -/ 241 242 /-- `∑ⱼ aⱼ * x ^ nⱼ`, the potential written in the given support. -/ 243 def potentialSum (x : D) : List (D × ℕ) → D 244 | [] => 0 245 | (t :: ts) => t.1 * x ^ t.2 + potentialSum x ts 246 247 /-- `∏ⱼ C(X + nⱼ)`, one shift of the corner polynomial per potential term. -/ 248 noncomputable def shiftedProd (C : k[X]) : List (D × ℕ) → k[X] 249 | [] => 1 250 | (t :: ts) => C.comp (X + Polynomial.C ((t.2 : ℕ) : k)) * shiftedProd C ts 251 252 omit [Ring D] [Algebra k D] in 253 @[simp] lemma shiftedProd_nil (C : k[X]) : shiftedProd C ([] : List (D × ℕ)) = 1 := rfl 254 255 omit [Ring D] [Algebra k D] in 256 lemma shiftedProd_cons (C : k[X]) (t : D × ℕ) (ts : List (D × ℕ)) : 257 shiftedProd C (t :: ts) 258 = C.comp (X + Polynomial.C ((t.2 : ℕ) : k)) * shiftedProd C ts := rfl 259 260 lemma aeval_comp_shift (E : D) (C : k[X]) (n : ℕ) : 261 aeval E (C.comp (X + Polynomial.C ((n : ℕ) : k))) = aeval (E + (n : D)) C := by 262 simp [aeval_comp] 263 264 /-- **Simultaneous shifted cancellation.** Multiplying the potential on the 265 right by one shift of the corner polynomial per term turns the whole potential 266 into a left multiple of the corner polynomial. Every coefficient is eliminated 267 at once, and the coefficients are never assumed to commute with one another. -/ 268 theorem potential_elimination (hw : p * x = x * p + 1) (C : k[X]) 269 (terms : List (D × ℕ)) (hcomm : ∀ t ∈ terms, t.1 * euler x p = euler x p * t.1) : 270 ∃ q : D, potentialSum x terms * aeval (euler x p) (shiftedProd C terms) 271 = aeval (euler x p) C * q := by 272 induction terms with 273 | nil => exact ⟨0, by simp [potentialSum, shiftedProd]⟩ 274 | cons t ts ih => 275 obtain ⟨q, hq⟩ := ih fun s hs => hcomm s (List.mem_cons_of_mem _ hs) 276 have ht : t.1 * euler x p = euler x p * t.1 := hcomm t List.mem_cons_self 277 set E := euler x p with hE 278 set Cs : k[X] := C.comp (X + Polynomial.C ((t.2 : ℕ) : k)) with hCs 279 set L : k[X] := shiftedProd C ts with hL 280 -- the key exchange: `x ^ n * C(E + n) = C(E) * x ^ n` 281 have hswap : x ^ t.2 * aeval E Cs = aeval E C * x ^ t.2 := by 282 rw [hCs, aeval_comp_shift, ← aeval_euler_mul_x_pow hw] 283 refine ⟨t.1 * x ^ t.2 * aeval E L + q * aeval E Cs, ?_⟩ 284 have hprod : shiftedProd C (t :: ts) = Cs * L := rfl 285 rw [potentialSum, hprod, map_mul, add_mul, mul_add] 286 congr 1 287 · calc t.1 * x ^ t.2 * (aeval E Cs * aeval E L) 288 = t.1 * (x ^ t.2 * aeval E Cs) * aeval E L := by noncomm_ring 289 _ = t.1 * (aeval E C * x ^ t.2) * aeval E L := by rw [hswap] 290 _ = (t.1 * aeval E C) * (x ^ t.2 * aeval E L) := by noncomm_ring 291 _ = aeval E C * (t.1 * x ^ t.2 * aeval E L) := by 292 rw [commute_aeval_euler ht C]; noncomm_ring 293 · calc potentialSum x ts * (aeval E Cs * aeval E L) 294 = potentialSum x ts * (aeval E L * aeval E Cs) := by 295 rw [← map_mul, ← map_mul, mul_comm] 296 _ = (potentialSum x ts * aeval E L) * aeval E Cs := by noncomm_ring 297 _ = aeval E C * q * aeval E Cs := by rw [hq] 298 _ = aeval E C * (q * aeval E Cs) := by noncomm_ring 299 300 /-! ### The main theorem -/ 301 302 /-- Shifting every exponent of the potential support by `r`. -/ 303 def shiftSupport (terms : List (D × ℕ)) (r : ℕ) : List (D × ℕ) := 304 terms.map fun t => (t.1, t.2 + r) 305 306 lemma potentialSum_mul_pow (x : D) (terms : List (D × ℕ)) (r : ℕ) : 307 potentialSum x terms * x ^ r = potentialSum x (shiftSupport terms r) := by 308 induction terms with 309 | nil => simp [potentialSum, shiftSupport] 310 | cons t ts ih => 311 simp only [shiftSupport, List.map_cons, potentialSum, add_mul] 312 rw [mul_assoc, ← pow_add] 313 congr 1 314 315 lemma commute_potentialSum_x {terms : List (D × ℕ)} 316 (h : ∀ t ∈ terms, t.1 * x = x * t.1) : 317 potentialSum x terms * x = x * potentialSum x terms := by 318 induction terms with 319 | nil => simp [potentialSum] 320 | cons t ts ih => 321 have ht := h t List.mem_cons_self 322 rw [potentialSum, add_mul, mul_add, ih fun s hs => h s (List.mem_cons_of_mem _ hs)] 323 congr 1 324 calc t.1 * x ^ t.2 * x = t.1 * x * x ^ t.2 := by rw [mul_assoc, mul_assoc, ← pow_succ, 325 ← pow_succ'] 326 _ = x * (t.1 * x ^ t.2) := by rw [ht, mul_assoc] 327 328 lemma commute_potentialSum_x_pow {terms : List (D × ℕ)} 329 (h : ∀ t ∈ terms, t.1 * x = x * t.1) (r : ℕ) : 330 potentialSum x terms * x ^ r = x ^ r * potentialSum x terms := by 331 induction r with 332 | zero => simp 333 | succ r ih => 334 rw [pow_succ, ← mul_assoc, ih, mul_assoc, commute_potentialSum_x h, ← mul_assoc] 335 336 /-- **Aggregate-commutation evolutionary Stafford theorem.** 337 338 Let `D` be any ring carrying a Weyl pair `p * x - x * p = 1`, let the potential 339 `A = ∑ⱼ aⱼ * x ^ j` be a displayed finite potential. Assume directly that 340 the shifted coefficients commute with the Euler operator and that the 341 aggregate potential commutes with `x ^ r`; no coefficientwise commutation with 342 `x` or `p` is required. Put 343 344 d = p ^ r - A. 345 346 Given a Bézout identity for the corner polynomial `C_r` against 347 `R₊ · ∏ⱼ C_r(X + r + j)` (supplied by `Stafford38.EulerRootSeparation`), the right ideal 348 generated by `d` and `x ^ r * d` is the whole ring, with the explicit 349 certificate below. -/ 350 theorem evolution_stafford_certificate_of_aggregate_commutation 351 (hw : p * x = x * p + 1) (r : ℕ) (terms : List (D × ℕ)) 352 (hcommE : ∀ t ∈ shiftSupport terms r, 353 t.1 * euler x p = euler x p * t.1) 354 (hAxr : potentialSum x terms * x ^ r = 355 x ^ r * potentialSum x terms) 356 (α β : k[X]) 357 (hbezout : cornerPoly k r * α 358 + (risingPoly k r * shiftedProd (cornerPoly k r) (shiftSupport terms r)) * β = 1) : 359 ∃ R S : D, (p ^ r - potentialSum x terms) * R 360 + x ^ r * (p ^ r - potentialSum x terms) * S = 1 := by 361 set E := euler x p with hE 362 set A := potentialSum x terms with hA 363 set d := p ^ r - A with hd 364 set C : k[X] := cornerPoly k r with hC 365 set L : k[X] := shiftedProd C (shiftSupport terms r) with hL 366 have hcommE' : ∀ t ∈ shiftSupport terms r, t.1 * E = E * t.1 := by 367 simpa [hE] using hcommE 368 -- the corner commutator 369 have hcorner : d * x ^ r - x ^ r * d = aeval E C := by 370 rw [hd, sub_mul, mul_sub, hAxr, aeval_cornerPoly, pow_mul_pow_eq_rising hw, 371 pow_mul_pow_eq_falling hw] 372 abel 373 -- simultaneous elimination 374 obtain ⟨q, hq⟩ := potential_elimination hw C (shiftSupport terms r) hcommE' 375 have helim : d * x ^ r * aeval E L 376 = aeval E (risingPoly k r * L) - aeval E C * q := by 377 have hAxr : A * x ^ r = potentialSum x (shiftSupport terms r) := 378 potentialSum_mul_pow x terms r 379 rw [hd, sub_mul, hAxr, pow_mul_pow_eq_rising hw, sub_mul, hq, map_mul, 380 aeval_risingPoly] 381 -- Bézout, transported into `D` 382 have hbez : aeval E C * aeval E α + aeval E (risingPoly k r * L) * aeval E β = 1 := by 383 have := congrArg (aeval (R := k) E) hbezout 384 simpa [map_add, map_mul] using this 385 exact ⟨_, _, stafford_of_bezout d (x ^ r) (aeval E C) (aeval E (risingPoly k r * L)) 386 (aeval E L) q (aeval E α) (aeval E β) hcorner helim hbez⟩ 387 388 /-! The original coefficientwise theorem is a corollary of the aggregate 389 interface. Keeping it explicit preserves the existing API while exposing 390 the strictly weaker hypotheses as a reusable producer contract. -/ 391 theorem evolution_stafford_certificate 392 (hw : p * x = x * p + 1) (r : ℕ) (terms : List (D × ℕ)) 393 (hx : ∀ t ∈ terms, t.1 * x = x * t.1) 394 (hp : ∀ t ∈ terms, t.1 * p = p * t.1) 395 (α β : k[X]) 396 (hbezout : cornerPoly k r * α 397 + (risingPoly k r * shiftedProd (cornerPoly k r) (shiftSupport terms r)) * β = 1) : 398 ∃ R S : D, (p ^ r - potentialSum x terms) * R 399 + x ^ r * (p ^ r - potentialSum x terms) * S = 1 := by 400 have hcommE : ∀ t ∈ shiftSupport terms r, 401 t.1 * euler x p = euler x p * t.1 := by 402 rintro ⟨a, n⟩ hmem 403 simp only [shiftSupport, List.mem_map] at hmem 404 obtain ⟨⟨b, m⟩, hb, heq⟩ := hmem 405 have hba : b = a := congrArg Prod.fst heq 406 subst hba 407 have h1 : b * x = x * b := hx _ hb 408 have h2 : b * p = p * b := hp _ hb 409 simp only [euler] 410 rw [← mul_assoc, h1, mul_assoc, h2, mul_assoc] 411 have hAxr : potentialSum x terms * x ^ r = 412 x ^ r * potentialSum x terms := commute_potentialSum_x_pow hx r 413 exact evolution_stafford_certificate_of_aggregate_commutation 414 hw r terms hcommE hAxr α β hbezout 415 416 end Elimination 417 418 end Stafford38.Evolution 419