proofs/weyl_pure_power.lean

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