Size of coefficients of lexicographical Groöbner bases: The zero-dimensional, radical and bivariate case

Xavier Dahan

doi:10.1145/1576702.1576721

Size of coefficients of lexicographical Groöbner bases: The zero-dimensional, radical and bivariate case

Xavier Dahan

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

2 Citations (Scopus)

Abstract

This work is limited to the zero-dimensional, radical, and bivariate case. A lexicographical Gröbner basis can be simply viewed as Lagrange interpolation polynomials. In the same way the Chinese remaindering theorem generalizes Lagrange interpolation, we show how a triangular decomposition is linked to a specific Gröbner basis (not the reduced one). A bound on the size of the coefficients of this specific Gröbner basis is proved using height theory, then a bound is deduced for the reduced Gröbner basis. Besides, the link revealed between the Gröbner basis and the triangular decomposition gives straightforwardly a numerical estimate to help finding a lucky prime in the context of modular methods.

Original language	English
Title of host publication	ISSAC 2009 - Proceedings of the 2009 International Symposium on Symbolic and Algebraic Computation
Pages	119-126
Number of pages	8
DOIs	https://doi.org/10.1145/1576702.1576721
Publication status	Published - 2009
Externally published	Yes
Event	2009 International Symposium on Symbolic and Algebraic Computation, ISSAC 2009 - Seoul, Korea, Republic of Duration: 2009 Jul 28 → 2009 Jul 31

Publication series

Name	Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC

Conference

Conference	2009 International Symposium on Symbolic and Algebraic Computation, ISSAC 2009
Country/Territory	Korea, Republic of
City	Seoul
Period	09/7/28 → 09/7/31

Keywords

Gröbner bases
Space complexity
Triangular sets

ASJC Scopus subject areas

Mathematics(all)

Access to Document

10.1145/1576702.1576721

Cite this

Dahan, X. (2009). Size of coefficients of lexicographical Groöbner bases: The zero-dimensional, radical and bivariate case. In ISSAC 2009 - Proceedings of the 2009 International Symposium on Symbolic and Algebraic Computation (pp. 119-126). (Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC). https://doi.org/10.1145/1576702.1576721

Size of coefficients of lexicographical Groöbner bases : The zero-dimensional, radical and bivariate case. / Dahan, Xavier.

ISSAC 2009 - Proceedings of the 2009 International Symposium on Symbolic and Algebraic Computation. 2009. p. 119-126 (Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Dahan, X 2009, Size of coefficients of lexicographical Groöbner bases: The zero-dimensional, radical and bivariate case. in ISSAC 2009 - Proceedings of the 2009 International Symposium on Symbolic and Algebraic Computation. Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC, pp. 119-126, 2009 International Symposium on Symbolic and Algebraic Computation, ISSAC 2009, Seoul, Korea, Republic of, 09/7/28. https://doi.org/10.1145/1576702.1576721

@inproceedings{3126a001d51544cd89ef5e0c15719c74,

title = "Size of coefficients of lexicographical Gro{\"o}bner bases: The zero-dimensional, radical and bivariate case",

abstract = "This work is limited to the zero-dimensional, radical, and bivariate case. A lexicographical Gr{\"o}bner basis can be simply viewed as Lagrange interpolation polynomials. In the same way the Chinese remaindering theorem generalizes Lagrange interpolation, we show how a triangular decomposition is linked to a specific Gr{\"o}bner basis (not the reduced one). A bound on the size of the coefficients of this specific Gr{\"o}bner basis is proved using height theory, then a bound is deduced for the reduced Gr{\"o}bner basis. Besides, the link revealed between the Gr{\"o}bner basis and the triangular decomposition gives straightforwardly a numerical estimate to help finding a lucky prime in the context of modular methods.",

keywords = "Gr{\"o}bner bases, Space complexity, Triangular sets",

author = "Xavier Dahan",

year = "2009",

doi = "10.1145/1576702.1576721",

language = "English",

isbn = "9781605586090",

series = "Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC",

pages = "119--126",

booktitle = "ISSAC 2009 - Proceedings of the 2009 International Symposium on Symbolic and Algebraic Computation",

note = "2009 International Symposium on Symbolic and Algebraic Computation, ISSAC 2009 ; Conference date: 28-07-2009 Through 31-07-2009",

}

TY - GEN

T1 - Size of coefficients of lexicographical Groöbner bases

T2 - 2009 International Symposium on Symbolic and Algebraic Computation, ISSAC 2009

AU - Dahan, Xavier

PY - 2009

Y1 - 2009

N2 - This work is limited to the zero-dimensional, radical, and bivariate case. A lexicographical Gröbner basis can be simply viewed as Lagrange interpolation polynomials. In the same way the Chinese remaindering theorem generalizes Lagrange interpolation, we show how a triangular decomposition is linked to a specific Gröbner basis (not the reduced one). A bound on the size of the coefficients of this specific Gröbner basis is proved using height theory, then a bound is deduced for the reduced Gröbner basis. Besides, the link revealed between the Gröbner basis and the triangular decomposition gives straightforwardly a numerical estimate to help finding a lucky prime in the context of modular methods.

AB - This work is limited to the zero-dimensional, radical, and bivariate case. A lexicographical Gröbner basis can be simply viewed as Lagrange interpolation polynomials. In the same way the Chinese remaindering theorem generalizes Lagrange interpolation, we show how a triangular decomposition is linked to a specific Gröbner basis (not the reduced one). A bound on the size of the coefficients of this specific Gröbner basis is proved using height theory, then a bound is deduced for the reduced Gröbner basis. Besides, the link revealed between the Gröbner basis and the triangular decomposition gives straightforwardly a numerical estimate to help finding a lucky prime in the context of modular methods.

KW - Gröbner bases

KW - Space complexity

KW - Triangular sets

UR - http://www.scopus.com/inward/record.url?scp=77950405026&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77950405026&partnerID=8YFLogxK

U2 - 10.1145/1576702.1576721

DO - 10.1145/1576702.1576721

M3 - Conference contribution

AN - SCOPUS:77950405026

SN - 9781605586090

T3 - Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC

SP - 119

EP - 126

BT - ISSAC 2009 - Proceedings of the 2009 International Symposium on Symbolic and Algebraic Computation

Y2 - 28 July 2009 through 31 July 2009

ER -

Size of coefficients of lexicographical Groöbner bases: The zero-dimensional, radical and bivariate case

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this