On the Bit-Size of Non-radical Triangular Sets

DOI10.1007/978-3-319-72453-9_19zbMATH Open1497.13048arXiv1710.06396OpenAlexW2766035871MaRDI QIDQ4628495FDOQ4628495

Authors: Xavier Dahan 

Publication date: 14 March 2019

Published in: Mathematical Aspects of Computer and Information Sciences (Search for Journal in Brave)

Abstract: We present upper bounds on the bit-size of coefficients of non-radical lexicographical Groebner bases in purely triangular form (triangular sets) of dimension zero. This extends a previous work [Dahan-Schost, Issac'2004], constrained to radical triangular sets; it follows the same technical steps, based on interpolation. However, key notion of height of varieties is not available for points with multiplicities; therefore the bounds obtained are less universal and depend on some input data. We also introduce a related family of non- monic polynomials that have smaller coefficients, and smaller bounds. It is not obvious to compute them from the initial triangular set though.

Full work available at URL: https://arxiv.org/abs/1710.06396

Recommendations

• Bit-size estimates for triangular sets in positive dimension
• On the complexity of computing with zero-dimensional triangular sets
• Complexity results for triangular sets
• scientific article; zbMATH DE number 2151241
• scientific article; zbMATH DE number 1066154
• Large sets and overlarge sets of triangle-decomposition
• Complexity of triangular representations of algebraic sets
• On large set and overlarge set of a triangle-decomposition
• On the theories of triangular sets
• Large sum-free sets in ternary spaces

Mathematics Subject Classification ID

Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10)

Cited In (5)

• Complexity results for triangular sets
• Bit-size estimates for triangular sets in positive dimension
• On the complexity of computing with zero-dimensional triangular sets
• Size of coefficients of lexicographical Gröbner bases: the zero-dimensional, radical and bivariate case
• Lexicographic Gröbner bases of bivariate polynomials modulo a univariate one

This page was built for publication: On the Bit-Size of Non-radical Triangular Sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4628495)