Reduced Gröbner Bases in Polynomial Rings over a Polynomial Ring

We propose a new notion of reduced Gr?bner bases in polynomial rings over a polynomial ring and we show that every ideal has a unique reduced Gr?bner basis. We introduce an algorithm for computing them.     

Gröbner Bases for the Polynomial Ring with Infinite Variables and Their Applications

We develop the theory of Gröbner bases for ideals in a polynomial ring with countably infinite variables over a field. As an application we reconstruct some of the one-to-one correspondences among various sets of partitions by using the division algorithm.     

A Gröbner basis characterization for chordal comparability graphs

In this paper, we study toric ideals associated with multichains of posets. It is shown that the comparability graph of a poset is chordal if and only if there exists a quadratic Gröbner basis of the toric ideal of the poset. Strong perfect elimination orderings of strongly chordal graphs play an important role.     

Gröbner bases in Asymptotic Analysis of Perturbed Polynomial Programs

We consider a perturbed mathematical programming problem where both the objective and the constraint functions are polynomial in all underlying decision variables and in the perturbation parameter $\varepsilon.We consider a perturbed mathematical programming problem where both the objective and the constraint functions are polynomial in all underlying decision variables and in the perturbation parameter We study the behaviour of the solutions of such a perturbed problem as Though the solutions of the programming problems are real, we consider the Karush–Kuhn–Tucker optimality system as a one-dimensional complex algebraic variety in a multi-dimensional complex space. We use the Buchberger’s elimination algorithm of the Gr?bner bases theory to replace the defining equations of the variety by its Gr?bner basis, that has the property that one of its elements is bivariate, that is, a polynomial in and one of the decision variables only. Changing the elimination order in the Buchberger’s algorithm, we obtain such a bivariate polynomial for each of the decision variables. Thus, the solutions of the original system reduces to a number of algebraic functions in that can be represented as a Puiseux series in a neighbourhood of . A detailed analysis of the branching order and the order of the pole is also provided. The latter is estimated via characteristics of these bivariate polynomials of Gr?bner bases.This research was supported by a grant from the Australian Research Council no. DP0343028. We are indebted to K. Avrachenkov, P. Howlett, and V. Gaitsgory for many helpful discussions.     

Solving Linear Boundary Value Problems Via Non-commutative Gröbner Bases

A new approach for symbolically solving linear boundary value problems is presented. Rather than using general-purpose tools for obtaining parametrized solutions of the underlying ODE and fitting them against the specified boundary conditions (which may be quite expensive), the problem is interpreted as an operator inversion problem in a suitable Banach space setting. Using the concept of the oblique Moore—Penrose inverse, it is possible to transform the inversion problem into a system of operator equations that can be attacked by virtue of non-commutative Gröbner bases. The resulting operator solution can be represented as an integral operator having the classical Green’s function as its kernel. Although, at this stage of research, we cannot yet give an algorithmic formulation of the method and its domain of admissible inputs, we do believe that it has promising perspectives of automation and generalization; some of these perspectives are discussed.     

Gröbner Bases for Complete Uniform Families

We describe (reduced) Gröbner bases of the ideal of polynomials over a field, which vanish on the set of characterisic vectors of the complete unifom families . An interesting feature of the results is that they are largely independent of the monomial order selected. The bases depend only on the ordering of the variables. We can thus use past results related to the lex order in the presence of degree-compatible orders, such as deglex. As applications, we give simple proofs of some known results on incidence matrices.     

Gröbner–Shirshov bases for pre-associative algebras

We develop Gröbner–Shirshov bases technique for pre-associative (dendriform) algebras and prove a version of composition-diamond lemma.     

Gröbner–Shirshov bases for brace algebras

Let A be a brace algebra. This structure implies that A is also a pre-Lie algebra. In this paper, we establish Composition-Diamond lemma for brace algebras. For each pre-Lie algebra L, we find a Gröbner–Shirshov basis for its universal brace algebra U_b(L). As applications, we determine an explicit linear basis for U_b(L) and prove that L is a pre-Lie subalgebra of U_b(L).     

Gröbner Bases for Ideals of σ-PBW Extensions

In this article, we introduce the σ-PWB extensions and construct the theory of Gröbner bases for the left ideals of them. We prove the Hilbert's basis theorem and the division algorithm for this more general class of Poincaré–Birkhoff–Witt extensions. For the particular case of bijective and quasi-commutative σ-PWB extensions, we implement the Buchberger's algorithm for computing Gröbner bases of left ideals.     

Gröbner–Shirshov bases for some Lie algebras

Siberian Mathematical Journal - We give Gröbner–Shirshov bases for the Drinfeld–Kohno Lie algebra L n in [1] and the Kukin Lie algebra A P in [2], where P is a semigroup. By way of...     

An Algorithm for Computing a Gröbner Basis of a Polynomial Ideal over a Ring with Zero Divisors

An algorithm for computing a Gr?bner basis of an ideal of polynomials whose coefficients are taken from a ring with zero divisors, is presented; such rings include \mathbb Z_n\mathbb {Z}_n and \mathbb Z_n[i]\mathbb {Z}_n[i], where n is not a prime number. The algorithm is patterned after (1) Buchberger’s algorithm for computing a Gr?bner basis of a polynomial ideal whose coefficients are from a field and (2) its extension developed by Kandri-Rody and Kapur when the coefficients appearing in the polynomials are from a Euclidean domain. The algorithm works as Buchberger’s algorithm when a polynomial ideal is over a field and as Kandri-Rody–Kapur’s algorithm when a polynomial ideal is over a Euclidean domain. The proposed algorithm and the related technical development are quite different from a general framework of reduction rings proposed by Buchberger in 1984 and generalized later by Stifter to handle reduction rings with zero divisors. These different approaches are contrasted along with the obvious approach where for instance, in the case of \mathbb Z_n{\mathbb {Z}}_n, the algorithm for polynomial ideals over \mathbb Z{\mathbb {Z}} could be used by augmenting the original ideal presented by polynomials over \mathbb Z_n{\mathbb {Z}}_n with n (similarly, in the case of \mathbb Z_n[i]{\mathbb {Z}}_n[i], the original ideal is augmented with n and i² + 1).     

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.     

Parametrized Gröbner–Shirshov bases

We consider the problem of describing Gröbner–Shirshov bases for free associative algebras in finite terms. To this end we consider parametrized elements of an algebra and give methods for working with them which under favorable conditions lead to a basis given by finitely many patterns. On the negative side we show that in general there can be no algorithm. We relate our study to the problem of verifying that a given set of words in certain groups yields Bokut’ normal forms (or groups with a standard basis).     

Optimising Gröbner Bases on Bivium

Bivium is a reduced version of the stream cipher Trivium. In this paper we investigate how fast a key recovery attack on Bivium using Gröbner bases is. First we explain the attack scenario and the cryptographic background. Then we identify the factors that have impact on the computation time and show how to optimise them. As a side effect these experiments benchmark several Gröbner basis implementations. The optimised version of the Gröbner attack has an expected running time of 2^39.12 s, beating the attack time of our previous SAT solver attack by a factor of more than 330. Furthermore this approach is faster than an attack based on BDDs, an exhaustive key search, a generic time-memory trade-off attack and a guess-and-determine strategy.     

Gröbner–Shirshov Bases for Schreier Extensions of Groups

In this article, by using the Gröbner–Shirshov bases, we give characterizations of the Schreier extensions of groups when the group is presented by generators and relations. An algorithm to find the conditions of a group to be a Schreier extension is obtained. By introducing a special total order, we obtain the structure of the Schreier extension by an HNN group.     

Quadratic Gröbner bases for smooth 3×3 transportation polytopes

The toric ideals of 3×3 transportation polytopes T_rc\mathsf{T}_{\mathbf{rc}} are quadratically generated. The only exception is the Birkhoff polytope B ₃. If T_rc\mathsf{T}_{\mathbf{rc}} is not a multiple of B ₃, these ideals even have square-free quadratic initial ideals. This class contains all smooth 3×3 transportation polytopes.     

Simple signature based iterative algorithm for calculation of Gröbner bases

The paper presents an algorithm for calculation of Gröbner bases with the use of labeled polynomials from the F5 algorithm. The distinct feature of this algorithm is the simplicity both of the algorithm and the proof of its correctness achieved without loss of efficiency. This leads to a simple implementation whose performance is in par with more complex analogues.