Correction To: The Complexity of Factors of Multivariate Polynomials
- PDF / 298,441 Bytes
- 2 Pages / 439.37 x 666.142 pts Page_size
- 59 Downloads / 174 Views
Correction To: The Complexity of Factors of Multivariate Polynomials Published in Foundations of Computational Mathematics 4(4): 369–396, 2004 Peter Bürgisser1 © SFoCM 2020
Correction To: Found Comput Math https://doi.org/10.1007/s10208-002-0059-5 Vladimir Lysikov kindly pointed out an error in the proof of Theorem 5.7. We provide here a corrected statement and its proof. Theorem 5.7 For polynomials f over an algebraically closed field k, we have L q ( f ) ≤ 2L( f ) with q ≤ 2 L( f ) . 2
Proof We proceed as in Lehmkuhl and Lickteig [2], who proved a similar bound on the order of approximation for border rank (approximative bilinear complexity). The proof is based on the following geometric description of the set { f ∈ An | L( f ) ≤ r }. The field k is assumed to be algebraically closed. A straight-line program is a description for a computation of a polynomial from constants z 1 , . . . , z m and variables X 1 , . . . , X n (recall that we do not allow divisions). Let φ (z) denote the polynomial in An := k[X 1 , . . . , X n ] computed by from the list of constants z ∈ k m . Let r∗ denote the number of multiplication instructions of . Then, we have φ (z) =
φ,μ (z)X μ ,
μ
where the sum runs over all μ ∈ Nn with μ1 + . . . + μn ≤ 2r∗ . Moreover, the coefficient polynomials φ,μ (z) have degree at most 2r∗ . We interpret φ as a morphism k m → { f ∈ An | deg f ≤ 2r∗ } of affine varieties. Applying [1, Theorem 8.48] to
The original article can be found online at https://doi.org/10.1007/s10208-002-0059-5.
B 1
Peter Bürgisser [email protected] Institut für Mathematik, MA 3-2, Technische Universität Berlin, D-10623 Berlin, Germany
123
Foundations of Computational Mathematics
m the polynomial map z → (z, φ (z)), we see that deg graph(φ ) ≤ 2r∗ =: D. The image C of φ is an irreducible, constructible set. We have for fixed r that { f ∈ An | L( f ) ≤ r } =
C ,
where the union is over all straight-line programs of length r . Assume now that f is in the Zariski-closure of the set on the left-hand side. Then, we have f ∈ C for some . (We remark that in the case k = C the Zariski-closure of constructible sets coincides with the closure with respect to the Euclidean topology (cf. [3, Theorem 2.33]). We apply now two results proven in Lehmkuhl and Lickteig [2] to the morphism φ . Proposition 1 of [2] claims that there exists an irreducible curve C ⊆ k m such that f ∈ φ (C) and deg C ≤ deg graph(φ ). The Corollary to Proposition 3 in [2] states that there exists a point ζ = (ζ1 , . . . , ζm ) ∈ k(())m such that F := φ (ζ ) is defined over k[[]], satisfies F=0 = f and such that all formal Laurent series ζi have order at least − deg C. We conclude with Lemma 5.6(2) that L(F) ≤ r and hence L( f ) ≤ r , which proves the nontrivial direction of Theorem 2.4. Moreover, we have shown that there is a straight-line program of length r , which computes F in k(())[X ] from the X -variables and constants ζi having order at least − deg C ≥ −D. By a similar reasoning as in the proof of Lem
Data Loading...
