Stafford38/EulerRootSeparation.lean

This project (Stafford38) · 1029fdb382eee06e7b59bcf32801f40931e2079a

1 module
2 public import Mathlib.Analysis.Complex.Basic
3 public import Mathlib.Analysis.Complex.Polynomial.Basic
4 public import Mathlib.Algebra.Polynomial.FieldDivision
5 public import Mathlib.Tactic.Ring
6 public import Mathlib.Tactic.Positivity
7 public import Mathlib.Tactic.Linarith
8 public import Mathlib.Tactic.NormNum
9 public import Mathlib.Tactic.LinearCombination
10 public import Stafford38.EvolutionaryCertificate
11 
12 @[expose] public section
13 
14 /-!
15 # The Euler root line and the Bézout hypothesis
16 
17 The evolutionary Stafford certificate of `Stafford38.EvolutionaryCertificate`
18 consumes one Bézout identity: the Euler corner polynomial
19 
20     C_r = R₊ - R₋,   R₊ = (X+1)⋯(X+r),   R₋ = X(X-1)⋯(X-r+1)
21 
22 must be coprime to `R₊` and to each of its own positive integer shifts
23 `C_r(X + n)`, `n ≥ 1`.  This file discharges that hypothesis.
24 
25 The mechanism is a one-dimensional root separation.  For `i ≥ 1`,
26 
27     |z + i|² - |z - (i-1)|² = (2i - 1)(2 Re z + 1),
28 
29 so on `Re z > -1/2` every rising factor strictly dominates the corresponding
30 falling factor and on `Re z < -1/2` every one is strictly dominated.  Hence
31 
32     C_r(z) = 0  ⟹  Re z = -1/2,
33 
34 and all roots of `C_r` lie on a single vertical line.  Coprimality with `R₊`
35 follows because the roots of `R₊` are the negative integers, and coprimality
36 with every positive shift follows because the line `Re z = -1/2` is disjoint
37 from its own translates.
38 
39 Everything is proved over `ℂ`, descended to `ℚ` by `Polynomial.isCoprime_map`,
40 and transported to an arbitrary characteristic-zero field by `IsCoprime.map`.
41 -/
42 
43 namespace Stafford38.Evolution
44 
45 open Polynomial
46 
47 /-- Over `ℂ` regarded as a `ℂ`-algebra, `aeval` is ordinary evaluation. -/
48 lemma aeval_eq_eval_complex (z : ℂ) (f : ℂ[X]) : aeval z f = f.eval z := by
49   rfl
50 
51 /-! ## The factorwise comparison -/
52 
53 /-- The exact difference of squared moduli of one rising and one falling
54 factor.  This single computation drives the whole file. -/
55 lemma normSq_sub_normSq (z : ℂ) (i : ℕ) :
56     Complex.normSq (z + ((i : ℂ) + 1)) - Complex.normSq (z - (i : ℂ))
57       = (2 * (i : ℝ) + 1) * (2 * z.re + 1) := by
58   simp only [Complex.normSq_apply, Complex.add_re, Complex.add_im, Complex.sub_re,
59     Complex.sub_im, Complex.natCast_re, Complex.natCast_im, Complex.one_re, Complex.one_im]
60   ring
61 
62 lemma abs_lt_of_re_pos {z : ℂ} (hz : 0 < 2 * z.re + 1) (i : ℕ) :
63     ‖z - (i : ℂ)‖ < ‖z + ((i : ℂ) + 1)‖ := by
64   have hpos : 0 < (2 * (i : ℝ) + 1) * (2 * z.re + 1) := by positivity
65   have h := normSq_sub_normSq z i
66   have hlt : Complex.normSq (z - (i : ℂ)) < Complex.normSq (z + ((i : ℂ) + 1)) := by linarith
67   simpa [Complex.norm_def] using
68     (Real.sqrt_lt_sqrt (Complex.normSq_nonneg _) hlt)
69 
70 lemma abs_lt_of_re_neg {z : ℂ} (hz : 2 * z.re + 1 < 0) (i : ℕ) :
71     ‖z + ((i : ℂ) + 1)‖ < ‖z - (i : ℂ)‖ := by
72   have hpos : 0 < (2 * (i : ℝ) + 1) := by positivity
73   have h := normSq_sub_normSq z i
74   have hlt : Complex.normSq (z + ((i : ℂ) + 1)) < Complex.normSq (z - (i : ℂ)) := by
75     nlinarith [h, hpos, hz]
76   simpa [Complex.norm_def] using
77     (Real.sqrt_lt_sqrt (Complex.normSq_nonneg _) hlt)
78 
79 /-! ## Strict domination of the whole product -/
80 
81 lemma abs_falling_lt_rising {z : ℂ} (hz : 0 < 2 * z.re + 1) :
82     ∀ r : ℕ, 1 ≤ r → ‖falling z r‖ < ‖rising z r‖
83   | 0, h => absurd h (by norm_num)
84   | 1, _ => by
85       simpa [rising_succ, falling_succ] using abs_lt_of_re_pos hz 0
86   | (r + 2), _ => by
87       have ih := abs_falling_lt_rising hz (r + 1) (by omega)
88       have hfac := abs_lt_of_re_pos hz (r + 1)
89       rw [rising_succ, falling_succ, norm_mul, norm_mul]
90       exact mul_lt_mul'' ih (by simpa using hfac) (by positivity) (by positivity)
91 
92 lemma abs_rising_lt_falling {z : ℂ} (hz : 2 * z.re + 1 < 0) :
93     ∀ r : ℕ, 1 ≤ r → ‖rising z r‖ < ‖falling z r‖
94   | 0, h => absurd h (by norm_num)
95   | 1, _ => by
96       simpa [rising_succ, falling_succ] using abs_lt_of_re_neg hz 0
97   | (r + 2), _ => by
98       have ih := abs_rising_lt_falling hz (r + 1) (by omega)
99       have hfac := abs_lt_of_re_neg hz (r + 1)
100       rw [rising_succ, falling_succ, norm_mul, norm_mul]
101       exact mul_lt_mul'' ih (by simpa using hfac) (by positivity) (by positivity)
102 
103 /-- **The Euler root line.**  Every complex root of the corner polynomial `C_r`
104 has real part `-1/2`. -/
105 theorem re_eq_neg_half_of_isRoot {r : ℕ} (hr : 1 ≤ r) {z : ℂ}
106     (hz : (cornerPoly ℂ r).IsRoot z) : z.re = -(1 / 2) := by
107   have heval : rising z r - falling z r = 0 := by
108     rw [← aeval_cornerPoly (k := ℂ) z r, aeval_eq_eval_complex]
109     exact hz
110   have heq : rising z r = falling z r := sub_eq_zero.mp heval
111   have habs : ‖rising z r‖ = ‖falling z r‖ := by rw [heq]
112   by_contra hne
113   rcases lt_trichotomy (2 * z.re + 1) 0 with h | h | h
114   · exact absurd habs (ne_of_lt (abs_rising_lt_falling h r hr))
115   · exact hne (by linarith)
116   · exact absurd habs.symm (ne_of_lt (abs_falling_lt_rising h r hr))
117 
118 /-! ## The corner polynomial is nonzero, and `R₊` has no root on the line -/
119 
120 lemma falling_zero_eq_zero : ∀ r : ℕ, 1 ≤ r → falling (0 : ℂ) r = 0
121   | 0, h => absurd h (by norm_num)
122   | 1, _ => by simp [falling_succ]
123   | (r + 2), _ => by
124       rw [falling_succ, falling_zero_eq_zero (r + 1) (by omega), zero_mul]
125 
126 lemma rising_ne_zero_of_re_neg_half {z : ℂ} (hz : z.re = -(1 / 2)) :
127     ∀ r : ℕ, rising z r ≠ 0
128   | 0 => by simp
129   | (r + 1) => by
130       rw [rising_succ]
131       refine mul_ne_zero (rising_ne_zero_of_re_neg_half hz r) ?_
132       intro hcon
133       have : (z + ((r : ℂ) + 1)).re = 0 := by rw [hcon]; simp
134       simp only [Complex.add_re, Complex.natCast_re, Complex.one_re, hz] at this
135       have : (0 : ℝ) < (r : ℝ) + 1 := by positivity
136       linarith
137 
138 lemma rising_zero_ne_zero : ∀ r : ℕ, rising (0 : ℂ) r ≠ 0
139   | 0 => by simp
140   | (r + 1) => by
141       rw [rising_succ]
142       refine mul_ne_zero (rising_zero_ne_zero r) ?_
143       have : (0 : ℝ) < (r : ℝ) + 1 := by positivity
144       intro hcon
145       have hre : ((0 : ℂ) + ((r : ℂ) + 1)).re = 0 := by rw [hcon]; simp
146       simp only [Complex.add_re, Complex.zero_re, Complex.natCast_re, Complex.one_re] at hre
147       linarith
148 
149 lemma cornerPoly_ne_zero {r : ℕ} (hr : 1 ≤ r) : cornerPoly ℂ r ≠ 0 := by
150   intro hcon
151   have h0 : aeval (0 : ℂ) (cornerPoly ℂ r) = 0 := by rw [hcon]; simp
152   rw [aeval_cornerPoly, falling_zero_eq_zero r hr, sub_zero] at h0
153   exact rising_zero_ne_zero r h0
154 
155 /-! ## Coprimality over `ℂ` -/
156 
157 lemma isCoprime_of_no_common_root {f g : ℂ[X]} (hf : f ≠ 0)
158     (h : ∀ z : ℂ, f.IsRoot z → g.IsRoot z → False) : IsCoprime f g := by
159   classical
160   rw [← EuclideanDomain.gcd_isUnit_iff]
161   by_contra hu
162   have hg0 : EuclideanDomain.gcd f g ≠ 0 := by
163     intro hcon
164     exact hf (EuclideanDomain.gcd_eq_zero_iff.mp hcon).1
165   have hdeg : 0 < (EuclideanDomain.gcd f g).degree := by
166     have hne : (EuclideanDomain.gcd f g).degree ≠ 0 := fun hcon =>
167       hu (Polynomial.isUnit_iff_degree_eq_zero.mpr hcon)
168     exact lt_of_le_of_ne (Polynomial.zero_le_degree_iff.mpr hg0) (Ne.symm hne)
169   obtain ⟨z, hz⟩ := Complex.exists_root hdeg
170   rw [Polynomial.isRoot_gcd_iff_isRoot_left_right] at hz
171   exact h z hz.1 hz.2
172 
173 /-- `C_r` is coprime to the rising factorial `R₊`: the roots of `R₊` are
174 negative integers, and none of them lies on the line `Re = -1/2`. -/
175 theorem isCoprime_corner_rising_complex {r : ℕ} (hr : 1 ≤ r) :
176     IsCoprime (cornerPoly ℂ r) (risingPoly ℂ r) := by
177   refine isCoprime_of_no_common_root (cornerPoly_ne_zero hr) ?_
178   intro z hzc hzr
179   have hre := re_eq_neg_half_of_isRoot hr hzc
180   have hzero : rising z r = 0 := by
181     rw [← aeval_risingPoly (k := ℂ) z r, aeval_eq_eval_complex]
182     exact hzr
183   exact rising_ne_zero_of_re_neg_half hre r hzero
184 
185 /-- `C_r` is coprime to each of its own positive integer shifts: the line
186 `Re = -1/2` is disjoint from every translate of itself. -/
187 theorem isCoprime_corner_shift_complex {r : ℕ} (hr : 1 ≤ r) {n : ℕ} (hn : 1 ≤ n) :
188     IsCoprime (cornerPoly ℂ r) ((cornerPoly ℂ r).comp (X + Polynomial.C (n : ℂ))) := by
189   refine isCoprime_of_no_common_root (cornerPoly_ne_zero hr) ?_
190   intro z hzc hzs
191   have h1 := re_eq_neg_half_of_isRoot hr hzc
192   have hroot : (cornerPoly ℂ r).IsRoot (z + (n : ℂ)) := by
193     simpa [Polynomial.IsRoot, Polynomial.eval_comp] using hzs
194   have h2 := re_eq_neg_half_of_isRoot hr hroot
195   simp only [Complex.add_re, Complex.natCast_re, h1] at h2
196   have : (1 : ℝ) ≤ (n : ℝ) := by exact_mod_cast hn
197   linarith
198 
199 /-! ## Descent to an arbitrary characteristic-zero field -/
200 
201 section Transport
202 
203 variable {k K : Type*} [CommRing k] [CommRing K]
204 
205 lemma map_risingPoly (φ : k →+* K) : ∀ n : ℕ, (risingPoly k n).map φ = risingPoly K n
206   | 0 => by simp
207   | (n + 1) => by
208       rw [risingPoly_succ, Polynomial.map_mul, map_risingPoly φ n, risingPoly_succ]
209       simp
210 
211 lemma map_fallingPoly (φ : k →+* K) : ∀ n : ℕ, (fallingPoly k n).map φ = fallingPoly K n
212   | 0 => by simp
213   | (n + 1) => by
214       rw [fallingPoly_succ, Polynomial.map_mul, map_fallingPoly φ n, fallingPoly_succ]
215       simp
216 
217 lemma map_cornerPoly (φ : k →+* K) (r : ℕ) :
218     (cornerPoly k r).map φ = cornerPoly K r := by
219   simp [cornerPoly, Polynomial.map_sub, map_risingPoly, map_fallingPoly]
220 
221 end Transport
222 
223 variable {k : Type*} [Field k] [CharZero k]
224 
225 /-- `C_r` and `R₊` are coprime over every characteristic-zero field. -/
226 theorem isCoprime_corner_rising {r : ℕ} (hr : 1 ≤ r) :
227     IsCoprime (cornerPoly k r) (risingPoly k r) := by
228   have hQ : IsCoprime (cornerPoly ℚ r) (risingPoly ℚ r) := by
229     rw [← Polynomial.isCoprime_map (Rat.castHom ℂ), map_cornerPoly, map_risingPoly]
230     exact isCoprime_corner_rising_complex hr
231   have := hQ.map (Polynomial.mapRingHom (Rat.castHom k))
232   simpa [Polynomial.coe_mapRingHom, map_cornerPoly, map_risingPoly] using this
233 
234 /-- `C_r` is coprime to each positive integer shift of itself, over every
235 characteristic-zero field. -/
236 theorem isCoprime_corner_shift {r : ℕ} (hr : 1 ≤ r) {n : ℕ} (hn : 1 ≤ n) :
237     IsCoprime (cornerPoly k r) ((cornerPoly k r).comp (X + Polynomial.C (n : k))) := by
238   have hQ : IsCoprime (cornerPoly ℚ r)
239       ((cornerPoly ℚ r).comp (X + Polynomial.C (n : ℚ))) := by
240     rw [← Polynomial.isCoprime_map (Rat.castHom ℂ), map_cornerPoly, Polynomial.map_comp,
241       map_cornerPoly]
242     simpa using isCoprime_corner_shift_complex hr hn
243   have := hQ.map (Polynomial.mapRingHom (Rat.castHom k))
244   simpa [Polynomial.coe_mapRingHom, map_cornerPoly, Polynomial.map_comp] using this
245 
246 /-! ## The Bézout hypothesis of the main theorem -/
247 
248 variable {D : Type*}
249 
250 /-- The full coprimality statement consumed by `evolution_stafford_certificate`:
251 `C_r` is coprime to `R₊ · ∏ⱼ C_r(X + r + j)`, for every potential support.  The
252 shifts are `r + j ≥ r ≥ 1`, so no shifted factor meets the root line. -/
253 theorem isCoprime_corner_hyper {r : ℕ} (hr : 1 ≤ r) (terms : List (D × ℕ)) :
254     IsCoprime (cornerPoly k r)
255       (risingPoly k r * shiftedProd (cornerPoly k r) (shiftSupport terms r)) := by
256   refine (isCoprime_corner_rising hr).mul_right ?_
257   induction terms with
258   | nil => simpa [shiftSupport] using isCoprime_one_right (x := cornerPoly k r)
259   | cons t ts ih =>
260       have hshift : IsCoprime (cornerPoly k r)
261           ((cornerPoly k r).comp (X + Polynomial.C ((t.2 + r : ℕ) : k))) :=
262         isCoprime_corner_shift hr (by omega)
263       simpa [shiftSupport, shiftedProd_cons] using hshift.mul_right ih
264 
265 /-- **Existence of the Bézout pair.**  This is exactly the hypothesis
266 `hbezout` of `evolution_stafford_certificate`, so the main theorem is
267 unconditional for every `r ≥ 1`. -/
268 theorem exists_bezout {r : ℕ} (hr : 1 ≤ r) (terms : List (D × ℕ)) :
269     ∃ α β : k[X], cornerPoly k r * α
270       + (risingPoly k r * shiftedProd (cornerPoly k r) (shiftSupport terms r)) * β = 1 := by
271   obtain ⟨α, β, hαβ⟩ := isCoprime_corner_hyper (k := k) hr terms
272   exact ⟨α, β, by linear_combination hαβ⟩
273 
274 end Stafford38.Evolution
275