A combinatorial complexity of Gröbner bases (Q1592198): Difference between revisions

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)].