Toric rings generated by special stable sets of monomials

In this paper we consider some subalgebras of the d-th Veronese subring of a polynomial ring, generated by stable subsets of monomials. We prove that these algebras are Koszul, showing that the presentation ideals have Gröbner bases of quadrics with respect to suitable term orders. Since the initial monomials of the elements of these Gröbner bases are square- free, it follows by a result of STURMFELS [S, 13.15], that the algebras under consideration are normal, and thus Cohen-Macaulay.     

Relative Reduction and Buchberger’s Algorithm in Filtered Free Modules

In this paper we develop a relative Gröbner basis method for a wide class of filtered modules. Our general setting covers the cases of modules over rings of differential, difference, inversive difference and difference–differential operators, Weyl algebras and multiparameter twisted Weyl algebras (the last class of rings includes the classes of quantized Weyl algebras and twisted generalized Weyl algebras). In particular, we obtain a Buchberger-type algorithm for constructing relative Gröbner bases of filtered free modules.     

Algebras of quasi-Plücker coordinates are Koszul

Motivated by the theory of quasi-determinants, we study non-commutative algebras of quasi-Plücker coordinates. We prove that these algebras provide new examples of non-homogeneous quadratic Koszul algebras by showing that their quadratic duals have quadratic Gröbner bases.     

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.     

Rees algebras and gröbner bases

This paper deals with the following problem. Robbiano showed in [9] that standard bases, Gröbner bases, Macaulay bases are all instances of the same general situation. In this paper, we develop this philosophy from the point of view of the Rees algebra R of a ring A w.r.t. a filtration F given on A. The ring R plays a fine job between A and the graded ring G associated to A, F. The use of R and the properties of termorderings and their relate Gröbner bases led naturally to the definition of Gröbnerfiltrations ingeneral commutative rings.     

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.     

Embedding into 2-generated simple associative (Lie) algebras

In this paper, by using Gröbner–Shirshov bases theories, we prove that each countably generated associative algebra (Lie algebra) can be embedded into a simple two-generated associative algebra (Lie algebra).     

Invariant G2V algorithm for computing SAGBI-Gröbner bases

Faugère and Rahmany have presented the invariant F5 algorithm to compute SAGBI-Grbner bases of ideals of invariant rings. This algorithm has an incremental structure, and it is based on the matrix version of F5 algorithm to use F5 criterion to remove a part of useless reductions. Although this algorithm is more efficient than the Buchberger-like algorithm, however it does not use all the existing criteria (for an incremental structure) to detect superfluous reductions. In this paper, we consider a new algorithm, namely, invariant G2V algorithm, to compute SAGBI-Grbner bases of ideals of invariant rings using more criteria. This algorithm has a new structure and it is based on the G2V algorithm; a variant of the F5 algorithm to compute Grbner bases. We have implemented our new algorithm in Maple , and we give experimental comparison, via some examples, of performance of this algorithm with the invariant F5 algorithm.     

Finite lattices and Gröbner bases

Gröbner bases of binomial ideals arising from finite lattices will be studied. In terms of Gröbner bases and initial ideals, a characterization of finite distributive lattices as well as planar distributive lattices will be given.     

Minimal invariant Markov basis for sampling contingency tables with fixed marginals

In this paper we define an invariant Markov basis for a connected Markov chain over the set of contingency tables with fixed marginals and derive some characterizations of minimality of the invariant basis. We also give a necessary and sufficient condition for uniqueness of minimal invariant Markov bases. By considering the invariance, Markov bases can be presented very concisely. As an example, we present minimal invariant Markov bases for all 2 × 2 × 2 × 2 hierarchical models. The invariance here refers to permutation of indices of each axis of the contingency tables. If the categories of each axis do not have any order relations among them, it is natural to consider the action of the symmetric group on each axis of the contingency table. A general algebraic algorithm for obtaining a Markov basis was given by Diaconis and Sturmfels (The Annals of Statistics, 26, 363–397, 1998). Their algorithm is based on computing Gröbner basis of a well-specified polynomial ideal. However, the reduced Gröbner basis depends on the particular term order and is not symmetric. Therefore, it is of interest to consider the properties of invariant Markov basis.     

Parallel algorithms for Gröbner-basis construction

The problem of the Gröbner-basis construction is important both from the theoretical and applied points of view. As examples of applications of Gröbner bases, one can mention the consistency problem for systems of nonlinear algebraic equations and the determination of the number of solutions to a system of nonlinear algebraic equations. The Gröbner bases are actively used in the constructive theory of polynomial ideals and at the preliminary stage of numerical solution of systems of nonlinear algebraic equations. Unfortunately, many real examples cannot be processed due to the high computational complexity of known algorithms for computing the Gröbner bases. However, the efficiency of the standard basis construction can be significantly increased in practice. In this paper, we analyze the known algorithms for constructing the standard bases and consider some methods for increasing their efficiency. We describe a technique for estimating the efficiency of paralleling the algorithms and present some estimates.     

On the robust hardness of Gröbner basis computation

The computation of Gröbner bases is an established hard problem. By contrast with many other problems, however, there has been little investigation of whether this hardness is robust. In this paper, we frame and present results on the problem of approximate computation of Gröbner bases. We show that it is NP-hard to construct a Gröbner basis of the ideal generated by a set of polynomials, even when the algorithm is allowed to discard a $1??$ fraction of the generators, and likewise when the algorithm is allowed to discard variables (and the generators containing them). Our results show that computation of Gröbner bases is robustly hard even for simple polynomial systems (e.g. maximum degree 2, with at most 3 variables per generator). We conclude by greatly strengthening results for the Strong c-Partial Gröbner problem posed by De Loera et al. [10]. Our proofs also establish interesting connections between the robust hardness of Gröbner bases and that of SAT variants and graph-coloring.     

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

On the Structure of Order Domains

The notion of an order domain is generalized. The behaviour of an order domain by taking a subalgebra, the extension of scalars, and the tensor product is studied. The relation of an order domain with valuation theory, Gröbner algebras, and graded structures is given. The theory of Gröbner bases for order domains is developed and used to show that the factor ring theorem and its converse, the presentation theorem, hold. The dimension of an order domain is related to the rank of its value semigroup.     

Gröbner–Shirshov bases for Vinberg–Koszul–Gerstenhaber right-symmetric algebras

In this paper, we establish the composition-diamond lemma for right-symmetric algebras. As an application, we give a Gröbner–Shirshov basis for the universal enveloping right-symmetric algebra of a Lie algebra.     

Gröbner–Shirshov basis for the Braid group in the Birman–Ko–Lee generators

In this paper, we obtain Gröbner–Shirshov (non-commutative Gröbner) bases for braid groups in the Birman–Ko–Lee generators enriched by “Garside word” δ [J. Birman, K.H. Ko, S.J. Lee, A new approach to the word and conjugacy problems for the braid groups, Adv. Math. 139 (1998) 322–353]. It gives a new algorithm for getting the Birman–Ko–Lee normal forms in braid groups, and thus a new algorithm for solving the word problem in these groups.     

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.     

Differential standard bases under composition

We generalize Hoon Hong’s theorem on Gröbner bases under composition to the case of differential standard bases in the ordinary ring of differential polynomials {ie4152-01}. In particular, we prove that some ideals have finite differential standard bases. We construct special orderings on differential monomials such that ideals generated by some power of a quasi-linear polynomial acquire finite differential standard bases.     

Universal Associative Envelopes of Nonassociative Triple Systems

We construct universal associative envelopes for the nonassociative triple systems arising from the trilinear operations of Bremner and Peresi applied to the 2-dimensional simple associative triple system. We use noncommutative Gröbner bases to determine monomial bases, structure constants, and centers of the universal envelopes. We show that the infinite dimensional envelopes are closely related to the down-up algebras of Benkart and Roby. For the finite dimensional envelopes, we determine the Wedderburn decompositions and classify the irreducible representations.