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