This project (Stafford38) · 1029fdb382eee06e7b59bcf32801f40931e2079a
1 module 2 public import Stafford38.MathlibCompat.MvPolynomialCoeff 3 public import Mathlib.RingTheory.MvPowerSeries.Order 4 public import Mathlib.RingTheory.MvPowerSeries.Trunc 5 public import Mathlib.RingTheory.MvPowerSeries.Substitution 6 public import Mathlib.RingTheory.MvPolynomial.Homogeneous 7 public import Mathlib.Algebra.Polynomial.Roots 8 9 @[expose] public section 10 11 open MvPolynomial 12 13 14 namespace Stafford38.Geometry.TiltedArcAvoidance 15 16 set_option autoImplicit false 17 18 variable {k : Type*} [Field k] [Infinite k] 19 20 /-- Over an infinite field, a nonzero polynomial has a nonzero value somewhere. -/ 21 theorem exists_eval_ne_zero {n : ℕ} (p : MvPolynomial (Fin n) k) (hp : p ≠ 0) : 22 ∃ x : Fin n → k, MvPolynomial.eval x p ≠ 0 := by 23 induction n with 24 | zero => 25 let x : Fin 0 → k := Fin.elim0 26 refine ⟨x, ?_⟩ 27 have hcoeff : p.coeff 0 ≠ 0 := by 28 intro hz 29 apply hp 30 ext d 31 have hd : d = 0 := Subsingleton.elim _ _ 32 subst d 33 simpa using hz 34 have hx0 : x = (0 : Fin 0 → k) := Subsingleton.elim _ _ 35 rw [hx0, MvPolynomial.eval_zero, MvPolynomial.constantCoeff_eq] 36 exact hcoeff 37 | succ n ih => 38 let P : Polynomial (MvPolynomial (Fin n) k) := MvPolynomial.finSuccEquiv k n p 39 have hP : P ≠ 0 := by 40 intro h 41 apply hp 42 exact (MvPolynomial.finSuccEquiv k n).injective h 43 obtain ⟨i, hi⟩ : ∃ i, P.coeff i ≠ 0 := by 44 by_contra h 45 push Not at h 46 exact hP (Polynomial.ext fun i => h i) 47 obtain ⟨y, hy⟩ := ih (P.coeff i) hi 48 let Q : Polynomial k := Polynomial.map (MvPolynomial.eval y) P 49 have hQ : Q ≠ 0 := by 50 intro h 51 apply hy 52 have hc := congrArg (fun q : Polynomial k => q.coeff i) h 53 simpa [Q, Polynomial.coeff_map] using hc 54 have hdeg : Q.natDegree < Cardinal.mk k := by 55 calc 56 (Q.natDegree : Cardinal) < Cardinal.aleph0 := Cardinal.natCast_lt_aleph0 57 _ ≤ Cardinal.mk k := Cardinal.infinite_iff.mp ‹Infinite k› 58 obtain ⟨x₀, hx₀⟩ := Q.exists_eval_ne_zero_of_natDegree_lt_card hQ hdeg 59 refine ⟨Fin.cons x₀ y, ?_⟩ 60 rw [MvPolynomial.eval_eq_eval_mv_eval' y x₀ p] 61 simpa [Q] using hx₀ 62 63 /-- A nonzero homogeneous polynomial is nonzero somewhere with its first coordinate fixed to 1. 64 The distinguished coordinate represents the original t-axis. -/ 65 theorem exists_eval_ne_zero_first_one {n r : ℕ} 66 (p : MvPolynomial (Fin (n + 1)) k) (hp : p.IsHomogeneous r) (hp0 : p ≠ 0) : 67 ∃ x : Fin n → k, MvPolynomial.eval (Fin.cons 1 x) p ≠ 0 := by 68 let P : Polynomial (MvPolynomial (Fin n) k) := MvPolynomial.finSuccEquiv k n p 69 have hP : P ≠ 0 := by 70 intro h 71 apply hp0 72 exact (MvPolynomial.finSuccEquiv k n).injective h 73 obtain ⟨i, hi⟩ : ∃ i, P.coeff i ≠ 0 := by 74 by_contra h 75 push Not at h 76 exact hP (Polynomial.ext fun i => h i) 77 have hir : i ≤ r := by 78 have hbound : P.natDegree ≤ r := by 79 rw [MvPolynomial.natDegree_finSuccEquiv] 80 calc 81 MvPolynomial.degreeOf 0 p ≤ p.totalDegree := MvPolynomial.degreeOf_le_totalDegree p 0 82 _ = r := hp.totalDegree hp0 83 by_contra h 84 have hlt : P.natDegree < i := lt_of_le_of_lt hbound (Nat.lt_of_not_ge h) 85 exact hi (Polynomial.coeff_eq_zero_of_natDegree_lt hlt) 86 have hhom (j : ℕ) (hj : j ∈ Finset.range (r + 1)) : 87 (P.coeff j).IsHomogeneous (r - j) := by 88 apply hp.finSuccEquiv_coeff_isHomogeneous 89 have hjle : j ≤ r := Nat.le_of_lt_succ (Finset.mem_range.mp hj) 90 omega 91 let q : MvPolynomial (Fin n) k := ∑ j ∈ Finset.range (r + 1), P.coeff j 92 have hcomp : MvPolynomial.homogeneousComponent (r - i) q = P.coeff i := by 93 dsimp [q] 94 rw [map_sum, Finset.sum_eq_single i] 95 · rw [MvPolynomial.homogeneousComponent_of_mem (hhom i (Finset.mem_range.mpr (Nat.lt_succ_of_le hir)))] 96 simp 97 · intro j hj hji 98 rw [MvPolynomial.homogeneousComponent_of_mem (hhom j hj)] 99 have hjle : j ≤ r := Nat.le_of_lt_succ (Finset.mem_range.mp hj) 100 have hne : r - i ≠ r - j := by omega 101 simp [hne] 102 · intro hi' 103 exact (hi' (Finset.mem_range.mpr (Nat.lt_succ_of_le hir))).elim 104 have hq : q ≠ 0 := by 105 intro hq 106 have := congrArg (MvPolynomial.homogeneousComponent (r - i)) hq 107 rw [hcomp] at this 108 exact hi (by simpa using this) 109 obtain ⟨x, hx⟩ := exists_eval_ne_zero q hq 110 refine ⟨x, ?_⟩ 111 rw [MvPolynomial.eval_eq_eval_mv_eval' x 1 p] 112 have hPdeg : P.natDegree ≤ r := by 113 rw [MvPolynomial.natDegree_finSuccEquiv] 114 calc 115 MvPolynomial.degreeOf 0 p ≤ p.totalDegree := MvPolynomial.degreeOf_le_totalDegree p 0 116 _ = r := hp.totalDegree hp0 117 have hQdeg : (Polynomial.map (MvPolynomial.eval x) P).natDegree ≤ r := 118 (Polynomial.natDegree_map_le).trans hPdeg 119 rw [Polynomial.eval_eq_sum_range' (Nat.lt_succ_of_le hQdeg)] 120 simp [Polynomial.coeff_map, ← map_sum] 121 exact hx 122 123 private def alphaProduct {n : ℕ} (α : Fin n → k) (d : Fin n →₀ ℕ) : k := 124 ∏ i ∈ d.support, α i ^ d i 125 126 omit [Infinite k] in 127 private theorem tilt_prod {n : ℕ} (α : Fin n → k) (d : Fin n →₀ ℕ) : 128 d.prod (fun i e => 129 (MvPowerSeries.C (α i) * MvPowerSeries.X (PUnit.unit : PUnit)) ^ e) = 130 MvPowerSeries.C (alphaProduct α d) * MvPowerSeries.X PUnit.unit ^ d.degree := by 131 classical 132 rw [Finsupp.prod] 133 simp only [mul_pow] 134 rw [Finset.prod_mul_distrib] 135 congr 1 136 · dsimp [alphaProduct] 137 calc 138 (∏ i ∈ d.support, MvPowerSeries.C (α i) ^ d i) = 139 ∏ i ∈ d.support, MvPowerSeries.C ((α i) ^ d i) := by simp 140 _ = MvPowerSeries.C (∏ i ∈ d.support, (α i) ^ d i) := by 141 exact (map_prod (MvPowerSeries.C : k →+* MvPowerSeries PUnit k) 142 (fun i => (α i) ^ d i) d.support).symm 143 · rw [Finset.prod_pow_eq_pow_sum, Finsupp.degree_apply] 144 145 omit [Infinite k] in 146 /-- Substituting a linear t-axis into a homogeneous polynomial gives its value at the direction 147 vector, times the corresponding t-monomial. -/ 148 private theorem subst_homogeneous_polynomial {n r : ℕ} 149 (p : MvPolynomial (Fin n) k) (hp : p.IsHomogeneous r) (α : Fin n → k) : 150 MvPowerSeries.subst 151 (fun i => MvPowerSeries.C (α i) * MvPowerSeries.X (PUnit.unit : PUnit)) 152 (p : MvPowerSeries (Fin n) k) = 153 MvPowerSeries.C (MvPolynomial.eval α p) * MvPowerSeries.X PUnit.unit ^ r := by 154 classical 155 let a := fun i : Fin n => MvPowerSeries.C (α i) * MvPowerSeries.X (PUnit.unit : PUnit) 156 have ha : MvPowerSeries.HasSubst a := 157 MvPowerSeries.hasSubst_of_constantCoeff_zero (fun i => by simp [a]) 158 have hmono (d : Fin n →₀ ℕ) (c : k) : 159 MvPolynomial.aeval a (MvPolynomial.monomial d c : MvPolynomial (Fin n) k) = 160 MvPowerSeries.C c * d.prod (fun i e => a i ^ e) := 161 MvPolynomial.aeval_monomial a d c 162 rw [← MvPowerSeries.substAlgHom_apply ha, MvPowerSeries.substAlgHom_coe ha] 163 conv_lhs => rw [p.as_sum, map_sum] 164 have hdeg (d : Fin n →₀ ℕ) (hd : d ∈ p.support) : d.degree = r := by 165 by_contra h 166 exact (Finsupp.mem_support_iff.mp hd) (hp.coeff_eq_zero h) 167 calc 168 (∑ d ∈ p.support, 169 MvPolynomial.aeval a (MvPolynomial.monomial d (p.coeff d))) = 170 ∑ d ∈ p.support, 171 MvPowerSeries.C (p.coeff d) * d.prod (fun i e => a i ^ e) := by 172 apply Finset.sum_congr rfl 173 intro d hd 174 exact hmono d (p.coeff d) 175 _ = 176 ∑ d ∈ p.support, 177 MvPowerSeries.C (p.coeff d * alphaProduct α d) * 178 MvPowerSeries.X PUnit.unit ^ r := by 179 apply Finset.sum_congr rfl 180 intro d hd 181 rw [tilt_prod, hdeg d hd] 182 rw [map_mul] 183 simp [alphaProduct, mul_assoc] 184 _ = MvPowerSeries.C 185 (∑ d ∈ p.support, p.coeff d * alphaProduct α d) * 186 MvPowerSeries.X PUnit.unit ^ r := by 187 rw [← Finset.sum_mul, ← map_sum] 188 _ = MvPowerSeries.C (MvPolynomial.eval α p) * MvPowerSeries.X PUnit.unit ^ r := by 189 rw [MvPolynomial.eval_eq] 190 simp [alphaProduct] 191 192 /-- A nonzero formal series remains nonzero on some tilted t-axis. The first input variable is 193 fixed to `t`; only the transverse variables are tilted by constants. -/ 194 theorem exists_tilt_subst_ne_zero {n : ℕ} 195 (f : MvPowerSeries (Fin (n + 1)) k) (hf : f ≠ 0) : 196 ∃ α : Fin n → k, 197 MvPowerSeries.subst 198 (fun i => MvPowerSeries.C ((Fin.cons 1 α : Fin (n + 1) → k) i) * 199 MvPowerSeries.X (PUnit.unit : PUnit)) f ≠ 0 := by 200 have hfinite : f.order.toNat = f.order := MvPowerSeries.ne_zero_iff_order_finite.mp hf 201 let r : ℕ := f.order.toNat 202 have hr : f.order = (r : ℕ∞) := hfinite.symm 203 have horderCoeff := f.exists_coeff_ne_zero_and_order hfinite 204 obtain ⟨d, hcoeff, hdegree⟩ := horderCoeff 205 have hdegreeR : d.degree = r := by 206 rw [hr] at hdegree 207 exact_mod_cast hdegree 208 let h : MvPowerSeries (Fin (n + 1)) k := f.homogeneousComponent r 209 have hh : h.IsHomogeneous r := by 210 exact MvPowerSeries.isHomogeneous_homogeneousComponent f r 211 let q : MvPolynomial (Fin (n + 1)) k := h.truncTotal (r + 1) 212 let p : MvPolynomial (Fin (n + 1)) k := MvPolynomial.homogeneousComponent r q 213 have hp : p.IsHomogeneous r := MvPolynomial.homogeneousComponent_isHomogeneous r q 214 have hqcoeff : q.coeff d ≠ 0 := by 215 dsimp [q] 216 have hd : d.degree < r + 1 := by rw [hdegreeR]; omega 217 have htrunc : MvPolynomial.coeff d (MvPowerSeries.truncTotal (r + 1) h) = 218 MvPowerSeries.coeff d h := by 219 simpa [MvPolynomial.coeff] using 220 (MvPowerSeries.coeff_truncTotal (p := h) hd) 221 rw [htrunc] 222 simpa [h, MvPowerSeries.coeff_homogeneousComponent, hdegreeR] using hcoeff 223 have hp0 : p ≠ 0 := by 224 intro hzero 225 have hz := congrArg (fun z : MvPolynomial (Fin (n + 1)) k => z.coeff d) hzero 226 apply hqcoeff 227 dsimp [p] at hz 228 have hz' : AddMonoidAlgebra.coeff (MvPolynomial.homogeneousComponent r q) d = 0 := by 229 simpa [MvPolynomial.coeff] using hz 230 rw [MvPolynomial.coeff_homogeneousComponent r q d, ite_eq_left hdegreeR] at hz' 231 change MvPolynomial.coeff d q = 0 at hz' 232 exact hz' 233 have hpseries : h = (p : MvPowerSeries (Fin (n + 1)) k) := by 234 ext e 235 by_cases he : e.degree = r 236 · 237 simp [p, q, MvPolynomial.coeff_coe, MvPolynomial.coeff_homogeneousComponent, 238 MvPowerSeries.coeff_truncTotal, he] 239 · have hz : MvPowerSeries.coeff e h = 0 := hh.coeff_eq_zero he 240 simp [p, MvPolynomial.coeff_coe, MvPolynomial.coeff_homogeneousComponent, he, hz] 241 obtain ⟨α, hEval⟩ := exists_eval_ne_zero_first_one p hp hp0 242 let a : Fin (n + 1) → MvPowerSeries PUnit k := fun i => 243 MvPowerSeries.C ((Fin.cons 1 α : Fin (n + 1) → k) i) * 244 MvPowerSeries.X (PUnit.unit : PUnit) 245 have hconst : ∀ i, MvPowerSeries.constantCoeff (a i) = 0 := by 246 intro i 247 simp [a] 248 have ha : MvPowerSeries.HasSubst a := MvPowerSeries.hasSubst_of_constantCoeff_zero hconst 249 have hlow (i : ℕ) (hi : i < r) : f.homogeneousComponent i = 0 := by 250 apply f.homogeneousComponent_of_lt_order_eq_zero 251 rw [hr] 252 exact_mod_cast hi 253 have hsum : 254 (∑ i ∈ Finset.range (r + 1), (f.homogeneousComponent i).subst a) = 255 (f.homogeneousComponent r).subst a := by 256 rw [Finset.sum_eq_single r] 257 · intro i hi hir 258 have hi' : i < r + 1 := Finset.mem_range.mp hi 259 have hil : i < r := by omega 260 rw [hlow i hil] 261 rw [← MvPowerSeries.substAlgHom_apply ha] 262 exact (MvPowerSeries.substAlgHom ha).map_zero 263 · intro hnot 264 exact (hnot (Finset.mem_range.mpr (Nat.lt_succ_self r))).elim 265 have htrunc : 266 MvPowerSeries.truncTotal (r + 1) (f.subst a) = 267 ((f.homogeneousComponent r).subst a).truncTotal (r + 1) := by 268 rw [MvPowerSeries.truncTotal_subst_eq_truncTotal_sum_subst ha hconst, hsum] 269 let e : PUnit →₀ ℕ := Finsupp.single PUnit.unit r 270 have hedegree : e.degree = r := by simp [e, Finsupp.degree_single] 271 have hebelow : e.degree < r + 1 := by omega 272 have hcoefTrunc := congrArg 273 (fun z : MvPolynomial PUnit k => AddMonoidAlgebra.coeff z e) htrunc 274 rw [MvPowerSeries.coeff_truncTotal (p := f.subst a) hebelow, 275 MvPowerSeries.coeff_truncTotal (p := (f.homogeneousComponent r).subst a) hebelow] 276 at hcoefTrunc 277 have hsub : (f.homogeneousComponent r).subst a = (p : MvPowerSeries (Fin (n + 1)) k).subst a := 278 congrArg (fun z : MvPowerSeries (Fin (n + 1)) k => MvPowerSeries.subst a z) hpseries 279 have hcoefEval : 280 MvPowerSeries.coeff e ((f.homogeneousComponent r).subst a) = 281 MvPolynomial.eval (Fin.cons 1 α : Fin (n + 1) → k) p := by 282 rw [hsub, subst_homogeneous_polynomial p hp (Fin.cons 1 α)] 283 simp [e, MvPowerSeries.coeff_C_mul, MvPowerSeries.coeff_X_pow] 284 refine ⟨α, ?_⟩ 285 intro hzero 286 apply hEval 287 rw [← hcoefEval, ← hcoefTrunc, hzero] 288 simp 289 290 #print axioms exists_tilt_subst_ne_zero 291 292 end Stafford38.Geometry.TiltedArcAvoidance 293