Stafford38/EvolutionaryCertificate.lean

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