A combinatorial complexity of Gröbner bases (Q1592198): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claim: author (P16): Item:Q1115180 |
||
Property / author | |||
Property / author: Victor N. Latyshev / rank | |||
Revision as of 13:35, 22 February 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