On the Bit-Size of Non-radical Triangular Sets

DOI10.1007/978-3-319-72453-9_19MaRDI QIDQ4628495zbMATH OpenOpenAlexFDO

Authors Xavier Dahan

Publication date 14 March 2019

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

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

Mathematics Subject Classification ID

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

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.

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

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)