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

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.     

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.     

One-Point Extensions of t-Koszul Algebras

We introduce the category of t-fold modules which is a full subcategory of graded modules over a graded algebra. We show that this subcategory and hence the subcategory of t-Koszul modules are both closed under extensions and cokernels of monomorphisms. We study the one-point extension algebras, and a necessary and sufficient condition for such an algebra to be t-Koszul is given. We also consider the conditions such that the category of t-Koszul modules and the category of quadratic modules coincide.     

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.     

Pivoting in Extended Rings for Computing Approximate Gr?bner Bases

It is well known that in the computation of Gr?bner bases arbitrarily small perturbations in the coefficients of polynomials may lead to a completely different staircase, even if the solutions of the polynomial system change continuously. This phenomenon is called artificial discontinuity in Kondratyev’s Ph.D. thesis. We show how such phenomenon may be detected and even “repaired” by using a new variable to rename the leading term each time we detect a “problem”. We call such strategy the TSV (Term Substitutions with Variables) strategy. For a zero-dimensional polynomial ideal, any monomial basis (containing 1) of the quotient ring can be found with the TSV strategy. Hence we can use TSV strategy to relax term order while keeping the framework of Gr?bner basis method so that we can use existing efficient algorithms (for instance the F ₅ algorithm) to compute an approximate Gr?bner basis. Our main algorithms, named TSVn and TSVh, can be used to repair artificial e{\epsilon}-discontinuities. Experiments show that these algorithms are effective for some nontrivial problems.     

Gr?bner bases of contraction ideals

We investigate Gr?bner bases of contraction ideals under monomial homomorphisms. As an application, we generalize the result of Aoki?CHibi?COhsugi?CTakemura and Ohsugi?CHibi for toric ideals of nested configurations.     

Hilbert Series of Group Representations and Gröbner Bases for Generic Modules

Each matrix representation :G GL_n() of a finite Group G over a field induces an action of G on the module ⁿ over the polynomial algebra The graded -submodule M() of _n generated by the orbit of is studied. A decomposition of M() into generic modules is given. Relations between the numerical invariants of and those of M(), the latter being efficiently computable by Gröbner bases methods, are examined. It is shown that if is multiplicity-free, then the dimensions of the irreducible constituents of can be read off from the Hilbert series of M(Pi;). It is proved that determinantal relations form Gröbner bases for the syzygies on generic matrices with respect to any lexicographic order. Gröbner bases for generic modules are also constructed, and their Hilbert series are derived. Consequently, the Hilbert series of M(Pi;) is obtained for an arbitrary representation.     

Reduced Gröbner Bases of Certain Toric Varieties; A New Short Proof

We prove that every additively-idempotent semiring can be embedded in a finitary complete semiring. From this we obtain, among other results, that the classical identities of Kleene semirings over idempotent semirings are independent.     

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.     

Characteristic Modules of Dual Extensions and Groebner Bases

Let C be a finite dimensional directed algebra over an algebraically closed field k and A=A(C) the dual extension of C. The characteristic modules of A are constructed explicitly for a class of directed algebras, which generalizes the results of Xi. Furthermore, it is shown that the characteristic modules of dual extensions of a certain class of directed algebras admit the left Groebner basis theory in the sense of E. L. Green.     

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–Shirshov Basis for HNN Extensions of Groups and for the Alternating Group

In this article, we generalize the Shirshov's Composition Lemma by replacing the monomial order for others. By using Gröbner–Shirshov bases, the normal forms of HNN extension of a group and the alternating group are obtained.     

Computing polynomial univariate representations of zero-dimensional ideals by Grbner basis

Rational Univariate Representation(RUR) of zero-dimensional ideals is used to describe the zeros of zero-dimensional ideals and RUR has been studied extensively.In 1999,Roullier proposed an efficient algorithm to compute RUR of zero-dimensional ideals.In this paper,we will present a new algorithm to compute Polynomial Univariate Representation(PUR) of zero-dimensional ideals.The new algorithm is based on some interesting properties of Grbner basis.The new algorithm also provides a method for testing separating elements.     

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.     

Gr?bner–Shirshov Basis of Derived Hall Algebra of Type A_n

We know that in Ringel–Hall algebra of Dynkin type, the set of all skew commutator relations between the iso-classes of indecomposable modules forms a minimal Gr?bner–Shirshov basis,and the corresponding irreducible elements forms a PBW type basis of the Ringel–Hall algebra. We aim to generalize this result to the derived Hall algebra DH(A_n) of type A_n. First, we compute all skew commutator relations between the iso-classes of indecomposable objects in the bounded derived category D~b(A_n) using the Auslander–Reiten quiver of D~b(A_n), and then we prove that all possible compositions between these skew commutator relations are trivial. As an application, we give a PBW type basis of DH(A_n).