Project topics and materials
Get Complete Project Material File(s) Now! »
Bounds from derivation of the Chow form
The first application of this technique is to obtain bounds for primitive element representa-tion (see Subsection 2.1.2) using the analogy of the Chow form and the primitive element, as seen in Subsection 1.2.1. Then we extend the result to triangular sets; as it is more tedious, all the technical results are gathered in the following subsection.
Formulas of derivations
We aim at proving the following result (Proposition 2.3) in this subsection. It will be central in the proof of our main result (Theorem 2.4) about the invertibilty of the leading coefficient of polynomial Mℓ+1 in Section 2.1.3 Let V be an equiprojectable variety defined by a triangular set T1, . . . , Tn over K, with degrees d1, . . . , dn. The Chow form of πin(V ) is denoted by Ci instead of Cπin(V ). Proposition. Let 1 ≤ ℓ ≤ s be two integers and set d≥ℓ := d1 . . . dℓ−1. Consider also some integers nℓ, . . . , ns, nT , satisfying Then the derivation ∂ := ∂nℓ ∂nℓ +1 . . . ∂ns ∂nT , Uℓ Uℓ+1 Us T verifies the following property: dℓdℓ+1 . . . ds, and d<ℓ = s ni +nT = S ≤ d≥ℓ −1. i=ℓ Cℓ−1(U1, . . . , Uℓ−1, T ) | ∂(Cs)(U1, . . . , Uℓ−1, 0, . . . , 0, T ). We prove a series of results involving derivations. We recall their definition: Definition 2.1 (Derivation). Let K be a field and R a commutative K-algebra. A K-linear map d : R → R is a derivation of order 1 if: for all x, y ∈ R, d(xy) = xd(y) + d(x)y. Recursively, we define a derivation of order n by saying that it is a K-linear map D : R → R such that ∀ x, y ∈ R, y D(xy) − xD(y) − yD(x) is a derivation of order n − 1. The set of K-derivations over R is denoted by DerK (R), and it is a (non-commutative) K-algebra. Example 2.1: If R = K[X1, . . . , Xn] we define derivations of order 1: for i = 1, . . . , n∂X (Xα1 Xαn ) := αiXα1 Xαi−1 Xαn . i 1 n 1 i n They commute each other. The sub-K-algebra An(K) of DerK (K[X1, . . . , Xn]) they gener-ate is called the n-th Weyl algebra. It is isomorphic to K[X1, . . . , Xn, Y1, . . . , Yn]/R, where R is the ideal of relations generated by [Xi, Xj ] = [Xi, Yj ] = [Yi, Yj ] = 0 if i = j and [Xi, Yi] = 1 ([., .] is the usual Lie product). ∂Xi is then identified to Yi. The following lemma is not of use for this paragraph, but as it deals with derivations, we state it here: Lemma 2.1. Let A ∈ K[U1, . . . , Ui][T , X1, . . . , Xi−1] and ∂i be the derivation of order 1 equal to ∂Ui + Xi∂T . Then: ∀ k ∈ N ∂Xi ∂ik (A) = k ∂T ∂ik−1(A).
Bounds for primitive element representations
In this paragraph, we are interested in proving the estimate in Theorem 2.2. Previous estimates are given in terms of a suitable multiplication tensor in [3, 101], and polynomial-type bounds are also given for such representations in [47, 109, 102]. We consider a zero-dimensional variety V of a polynomial system over K. As usual, its vanishing ideal verifies the Separability Assumption. We are interested in recovering its primitive element representation by differentiating and specializing its Chow form (Theo-rem 2.1). It does not use the previous technical results, but deals also with derivations. In this section, D is the degree deg(V ) of V . The following lemma shows an important cancellation identity of the Chow form when specialized at a generic linear form. Lemma 2.3. For an integer i ≥ 1, consider a derivation ∂ in a Weyl algebra Ai+1(K[X1, . . . , Xn]) ⊂ DerK[X1,…,Xn ](K[X1, . . . , Xn][U1, . . . , Ui, T ]), such that ∂ is product of N derivations among {∂1, . . . , ∂i}. Consider also a polynomial A in K[U1, . . . , Ui, T ]. Then, ∂(A C i)(U1, . . . , Ui, Uk Xk ) ≡ 0 mod I(πin(V )) ⊗ K[U1, . . . , Ui]. 1≤k≤i Proof. Let us prove it by induction on N . The case N = 0 corresponds to Lemma 1.2 applied for each projection πin(V ). Assume that the result is true for every derivation of Ai+1(K) of order N − 1. By definition, the K-linear map: L : K[X1, . . . , Xn, U1, . . . , Ui, T ] −→ K[X1, . . . , Xn, U1, . . . , Ui, T ]
Table of contents :
Introduction
1 Preliminaries
1.1 Polynomial systems representations
1.1.1 Hypotheses – Presentation
1.1.2 Primitive element representation
1.1.3 Triangular systems
1.2 Chow form and height
1.2.1 Chow form
1.2.2 Height theory
1.3 Basic algorithmic
1.3.1 Generalities
1.3.2 Basic operations
1.4 Lifting techniques
1.4.1 Triangular Newton-Hensel operator
1.4.2 Rational reconstruction
1.4.3 Probabilistic aspects
2 Height bounds for polynomial representations
2.1 Bounds from derivation of the Chow form
2.1.1 Formulas of derivations
2.1.2 Bounds for primitive element representations
2.1.3 A link between Chow forms and triangular polynomials
2.1.4 Height of coefficients
2.1.5 Attempt of bounds for (Ti)i from (Mi)i
2.2 Bounds from interpolation formulas
2.2.1 Interpolation formulas
2.2.2 Links with Chow forms
2.2.3 From interpolation to height bounds
3 Change of order for regular chains
3.1 Introduction
3.2 Preliminaries
3.2.1 Additional results on regular chains
3.2.2 Algorithmic prerequisites
3.3 Matroids
3.3.1 Definition and examples
3.3.2 A greedy optimization algorithm
3.4 Computing the exchange data
3.4.1 Characterization of the target set of algebraic variables
3.4.2 Linearization
3.4.3 Computing the initial specialization
3.4.4 Computing the exchange data
3.5 Changing the lifting fiber
3.5.1 Setup and preliminaries
3.5.2 Finding the new lifting fiber
3.5.3 Proof of Proposition 3.14
3.6 Proof of Theorem 3.1
3.7 Conclusions and future work
4 Lifting techniques for triangular decompositions
4.1 Introduction
4.2 Split-and-Merge algorithm
4.3 proof of Theorem 4.1
4.4 Proof of Theorem 4.2
4.5 Experimentation
4.6 Conclusions
5 On the complexity of the D5 principle
5.1 Introduction
5.2 Basic complexity results: multiplication and splitting
5.3 Fast GCD computations modulo a triangular set
5.4 Fast computation of quasi-inverses
5.5 Coprime factorization
5.5.1 Computing multiple gcd’s
5.5.2 Computing all pairs of gcd’s
5.5.3 A special case of coprime factorization
5.5.4 Conclusion: Proof of the main result
5.6 Removing critical pairs
5.7 Concluding the proof
Appendix: merging triangular sets for inversion
Conclusion
