A combinatorial complexity of Gröbner bases (Q1592198): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(4 intermediate revisions by 3 users not shown) | |||
Property / author | |||
Property / author: Victor N. Latyshev / rank | |||
Property / author | |||
Property / author: Victor N. Latyshev / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4305609 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4693774 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The Structure of Polynomial Ideals and Gröbner Bases / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3992576 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 12:18, 3 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A combinatorial complexity of Gröbner bases |
scientific article |
Statements
A combinatorial complexity of Gröbner bases (English)
0 references
17 January 2001
0 references
Let \(\mathbb Z^n_+\) be the monoid of \(n\)-tuples of non-negative integer numbers. If \(\overline{\alpha} \in \mathbb Z^n_+\), then \(\deg(\overline{\alpha})\) denotes the sum of the \(n\) components of \(\overline{\alpha}\). A sequence \(\overline{\alpha}_1,\dots, \overline{\alpha}_m,\dots\) of elements of \(\mathbb Z^n_+\) is called an ``anti-chain'' if both \(\overline{\alpha}_i-\overline{\alpha}_j\) and \(\overline{\alpha}_j-\overline{\alpha}_i\) have some negative components. The author considers the following question: Let \(\overline{\alpha}_1,\dots,\overline{\alpha}_m,\dots\) be an anti-chain and put \(d=\deg(\overline{\alpha}_1)\); call a mapping \(\varphi : \mathbb Z_+ \longrightarrow \mathbb Z_+\) a ``restraining function'' of the sequence if \(\deg (\overline {\alpha}_{i+1}) \leq \varphi(\deg (\overline {\alpha}_i))\), \(i=1, 2,\dots \). Is it possible to find an upper bound \(B(d,n,\varphi)\) of the number of members depending on \(d\), \(n\) and \(\varphi\) in any above sequence? The aim of the paper is to give a positive answer to the above question. As a corollary, the author obtains in a different way the known fact that the number of elements of the reduced Gröbner basis of an ideal \(I\subseteq k[x_1,\dots,x_n]\) is bounded by a function depending only on \(n\) and \(d\) (where \(d\) is an upper bound for the degree of the generators of \(I\)) [see also \textit{H. M. Möller} and \textit{F. Mora}, EUROSAM 84, Symbolic and algebraic computation, Proc. int. Symp., Cambridge/Engl. 1984, Lect. Notes Comput. Sci. 174, 172-183 (1984; Zbl 0564.68030)].
0 references
complexity
0 references
number of elements of the reduced Gröbner basis
0 references