𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Complexity results for triangular sets

✍ Scribed by Éric Schost

Book ID
104344876
Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
510 KB
Volume
36
Category
Article
ISSN
0747-7171

No coin nor oath required. For personal study only.

✦ Synopsis

We study the representation of the solutions of a polynomial system by triangular sets, and concentrate on the positive-dimensional case. We reduce to dimension zero by placing the free variables in the base field, so the solutions can be represented by triangular sets with coefficients in a rational function field.

We give intrinsic-type bounds on the degree of the coefficients in such a triangular set, and on the degree of an associated degeneracy hypersurface. Then we show how to apply lifting techniques in this context, and point out the role played by the evaluation properties of the input system.

Our algorithms are implemented in Magma; we present three applications, relevant to geometry and number theory.

📜 SIMILAR VOLUMES

Some results on the complexity of famili
Some results on the complexity of families of sets
✍ Daniel Grieser 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 872 KB

Grieser, D., Some results on the complexity of families of sets, Discrete Mathematics 88 (1991) 179-192. Let 'Y be a property of graphs on a fixed n-element vertex set V. The complexity c(P) is the minimal number of edges whose existence in a previously unknown graph H has to be tested such that it