Stafford38/Geometry/TiltedArcAvoidance.lean

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