Minimal Gröbner bases and the predictable leading monomial property

We focus on Gröbner bases for modules of univariate polynomial vectors over a ring. We identify a useful property, the “predictable leading monomial (PLM) property” that is shared by minimal Gröbner bases of modules in F[x]^q, no matter what positional term order is used. The PLM property is useful in a range of applications and can be seen as a strengthening of the wellknown predictable degree property (= row reducedness), a terminology introduced by Forney in the 70’s. Because of the presence of zero divisors, minimal Gröbner bases over a finite ring of the type Z_p^r (where p is a prime integer and r is an integer >1) do not necessarily have the PLM property. In this paper we show how to derive, from an ordered minimal Gröbner basis, a so-called “minimal Gröbner p-basis” that does have a PLM property. We demonstrate that minimal Gröbner p-bases lend themselves particularly well to derive minimal realization parametrizations over Z_p^r. Applications are in coding and sequences over Z_p^r.     

On the Gröbner complexity of matrices

In this paper we show that if for an integer matrix A the universal Gröbner basis of the associated toric ideal I_A coincides with the Graver basis of A, then the Gröbner complexity u(A) and the Graver complexity g(A) of its higher Lawrence liftings agree, too. In fact, if the universal Gröbner basis of I_A coincides with the Graver basis of A, then also the more general complexities u(A,B) and g(A,B) agree for arbitrary B. We conclude that for the matrices A_3×3 and A_3×4, defining the 3×3 and 3×4 transportation problems, we have u(A_3×3)=g(A_3×3)=9 and u(A_3×4)=g(A_3×4)≥27. Moreover, we prove that u(A_a,b)=g(A_a,b)=2(a+b)/gcd(a,b) for positive integers a,b and .     

Computing border bases

This paper presents several algorithms that compute border bases of a zero-dimensional ideal. The first relates to the FGLM algorithm as it uses a linear basis transformation. In particular, it is able to compute border bases that do not contain a reduced Gröbner basis. The second algorithm is based on a generic algorithm by Bernard Mourrain originally designed for computing an ideal basis that need not be a border basis. Our fully detailed algorithm computes a border basis of a zero-dimensional ideal from a given set of generators. To obtain concrete instructions we appeal to a degree-compatible term ordering σ and hence compute a border basis that contains the reduced σ-Gröbner basis. We show an example in which this computation actually has advantages over Buchberger's algorithm. Moreover, we formulate and prove two optimizations of the Border Basis Algorithm which reduce the dimensions of the linear algebra subproblems.     

Gröbner Flags and Gorenstein Algebras

The goal of this paper is to study the Koszul property and the property of having a Gröbner basis of quadrics for classical varieties and algebras as canonical curves, finite sets of points and Artinian Gorenstein algebras with socle in low degree. Our approach is based on the notion of Gröbner flags and Koszul filtrations. The main results are the existence of a Gröbner basis of quadrics for the ideal of the canonical curve whenever it is defined by quadrics, the existence of a Gröbner basis of quadrics for the defining ideal of s 2n points in general linear position in P ⁿ , and the Koszul property of the generic Artinian Gorenstein algebra of socle degree 3.     

The F<Subscript>4</Subscript>-algorithm for Euclidean rings

In this short note, we extend Faugére’s F₄-algorithm for computing Gröbner bases to polynomial rings with coefficients in an Euclidean ring. Instead of successively reducing single S-polynomials as in Buchberger’s algorithm, the F₄-algorithm is based on the simultaneous reduction of several polynomials.     

Gröbner-Shirshov bases for the lie algebra <Emphasis Type="Italic">A</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript>

We estimate Gröbner-Shirshov bases for the Lie algebra A_n given arbitrary orders of generators (nodes of a Dynkin graph). Previously, the Gröbner-Shirshov basis was computed in [1] for the particular case where nodes of the Dynkin graph are ordered successively.Supported by RFBR grant Nos. 05-01-00230 and 02-01-00258 and by the Council for Grants (under RF President) and State Aid of Fundamental Science Schools, project NSh-2069.2003.1.__________Translated from Algebra i Logika, Vol. 44, No. 2, pp. 131–147, March–April, 2005.     

Homological Computations in PBW Modules

In this paper the Poincaré–Birkhoff–Witt (PBW) rings are characterized. Gröbner bases techniques are also developed for these rings. An explicit presentation of Ext ⁱ (M,N) is provided when N is a centralizing bimodule.     

Generalized binomial edge ideals

This paper studies a class of binomial ideals associated to graphs with finite vertex sets. They generalize the binomial edge ideals, and they arise in the study of conditional independence ideals. A Gröbner basis can be computed by studying paths in the graph. Since these Gröbner bases are square-free, generalized binomial edge ideals are radical. To find the primary decomposition a combinatorial problem involving the connected components of subgraphs has to be solved. The irreducible components of the solution variety are all rational.     

Computations in differential and difference modules

Constructive methods based on the Gröbner bases theory have been used many times in commutative algebra over the past 20 years, in particular, they allow the computation of such important invariants of manifolds given by systems of algebraic equations as their Hilbert polynomials. In differential and difference algebra, the analogous roles play characteristic sets.In this paper, algorithms for computations in differential and difference modules, which allow for the computation of characteristic sets (Gröbner bases) in differential, difference, and polynomial modules and differential (difference) dimension polynomials, are described. The algorithms are implemented in the algorithmic language REFAL.