Bit-size estimates for triangular sets in positive dimension

Xavier Dahan; Abdulilah Kadri; Eric Schost

doi:10.1016/j.jco.2011.05.001

Bit-size estimates for triangular sets in positive dimension

Xavier Dahan
, Abdulilah Kadri
, Eric Schost^*

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

7 Scopus citations

Abstract

We give bit-size estimates for the coefficients appearing in triangular sets describing positive-dimensional algebraic sets defined over ℚ. These estimates are worst case upper bounds; they depend only on the degree and height of the underlying algebraic sets. We illustrate the use of these results in the context of a modular algorithm. This extends the results by the first and the last author, which were confined to the case of dimension 0. Our strategy is to get back to dimension 0 by evaluation and interpolation techniques. Even though the main tool (height theory) remains the same, new difficulties arise to control the growth of the coefficients during the interpolation process.

Original language	English
Pages (from-to)	109-135
Number of pages	27
Journal	Journal of Complexity
Volume	28
Issue number	1
DOIs	https://doi.org/10.1016/j.jco.2011.05.001
State	Published - Feb 2012
Externally published	Yes

Bibliographical note

Funding Information:
We acknowledge the support of NSERC , the Canada Research Chairs Program and MITACS, and of the Japanese Society for the Promotion of Science (Global-COE program “Maths-for-Industry”). We thank the reviewers for their useful remarks.

Keywords

Bit size
Chow form
Height function
Regular chain
Triangular set

ASJC Scopus subject areas

Algebra and Number Theory
Statistics and Probability
Numerical Analysis
General Mathematics
Control and Optimization
Applied Mathematics

Access to Document

10.1016/j.jco.2011.05.001

Cite this

@article{bc464a58b97247b1bc5c806c43064e66,

title = "Bit-size estimates for triangular sets in positive dimension",

abstract = "We give bit-size estimates for the coefficients appearing in triangular sets describing positive-dimensional algebraic sets defined over ℚ. These estimates are worst case upper bounds; they depend only on the degree and height of the underlying algebraic sets. We illustrate the use of these results in the context of a modular algorithm. This extends the results by the first and the last author, which were confined to the case of dimension 0. Our strategy is to get back to dimension 0 by evaluation and interpolation techniques. Even though the main tool (height theory) remains the same, new difficulties arise to control the growth of the coefficients during the interpolation process.",

keywords = "Bit size, Chow form, Height function, Regular chain, Triangular set",

author = "Xavier Dahan and Abdulilah Kadri and Eric Schost",

note = "Funding Information: We acknowledge the support of NSERC , the Canada Research Chairs Program and MITACS, and of the Japanese Society for the Promotion of Science (Global-COE program “Maths-for-Industry”). We thank the reviewers for their useful remarks.",

year = "2012",

month = feb,

doi = "10.1016/j.jco.2011.05.001",

language = "English",

volume = "28",

pages = "109--135",

journal = "Journal of Complexity",

issn = "0885-064X",

publisher = "Academic Press Inc.",

number = "1",

}

TY - JOUR

T1 - Bit-size estimates for triangular sets in positive dimension

AU - Dahan, Xavier

AU - Kadri, Abdulilah

AU - Schost, Eric

N1 - Funding Information: We acknowledge the support of NSERC , the Canada Research Chairs Program and MITACS, and of the Japanese Society for the Promotion of Science (Global-COE program “Maths-for-Industry”). We thank the reviewers for their useful remarks.

PY - 2012/2

Y1 - 2012/2

N2 - We give bit-size estimates for the coefficients appearing in triangular sets describing positive-dimensional algebraic sets defined over ℚ. These estimates are worst case upper bounds; they depend only on the degree and height of the underlying algebraic sets. We illustrate the use of these results in the context of a modular algorithm. This extends the results by the first and the last author, which were confined to the case of dimension 0. Our strategy is to get back to dimension 0 by evaluation and interpolation techniques. Even though the main tool (height theory) remains the same, new difficulties arise to control the growth of the coefficients during the interpolation process.

AB - We give bit-size estimates for the coefficients appearing in triangular sets describing positive-dimensional algebraic sets defined over ℚ. These estimates are worst case upper bounds; they depend only on the degree and height of the underlying algebraic sets. We illustrate the use of these results in the context of a modular algorithm. This extends the results by the first and the last author, which were confined to the case of dimension 0. Our strategy is to get back to dimension 0 by evaluation and interpolation techniques. Even though the main tool (height theory) remains the same, new difficulties arise to control the growth of the coefficients during the interpolation process.

KW - Bit size

KW - Chow form

KW - Height function

KW - Regular chain

KW - Triangular set

UR - https://www.scopus.com/pages/publications/82555174386

U2 - 10.1016/j.jco.2011.05.001

DO - 10.1016/j.jco.2011.05.001

M3 - Article

AN - SCOPUS:82555174386

SN - 0885-064X

VL - 28

SP - 109

EP - 135

JO - Journal of Complexity

JF - Journal of Complexity

IS - 1

ER -

Bit-size estimates for triangular sets in positive dimension

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this