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.     

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.     

Combinatorial symbolic powers

Symbolic powers are studied in the combinatorial context of monomial ideals. When the ideals are generated by quadratic squarefree monomials, the generators of the symbolic powers are obstructions to vertex covering in the associated graph and its blowups. As a result, perfect graphs play an important role in the theory, dual to the role played by perfect graphs in the theory of secants of monomial ideals. We use Gröbner degenerations as a tool to reduce questions about symbolic powers of arbitrary ideals to the monomial case. Among the applications are a new, unified approach to the Gröbner bases of symbolic powers of determinantal and Pfaffian ideals.     

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.     

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.     

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.     

Distortion Varieties

The distortion varieties of a given projective variety are parametrized by duplicating coordinates and multiplying them with monomials. We study their degrees and defining equations. Exact formulas are obtained for the case of one-parameter distortions. These are based on Chow polytopes and Gröbner bases. Multi-parameter distortions are studied using tropical geometry. The motivation for distortion varieties comes from multi-view geometry in computer vision. Our theory furnishes a new framework for formulating and solving minimal problems for camera models with image distortion.     

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.     

On standard bases in rings of differential polynomials

We consider Ollivier’s standard bases (also known as differential Gröbner bases) in an ordinary ring of differential polynomials in one indeterminate. We establish a link between these bases and Levi’s reduction process. We prove that the ideal [x ^p ] has a finite standard basis (w.r.t. the so-called β-orderings) that contains only one element. Various properties of admissible orderings on differential monomials are studied. We bring up the question of whether there is a finitely generated differential ideal that does not admit a finite standard basis w.r.t. any ordering.     

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.     

Variation of cost functions in integer programming

We study the problem of minimizingc · x subject toA · x =b. x ≥ 0 andx integral, for a fixed matrixA. Two cost functionsc andc′ are considered equivalent if they give the same optimal solutions for eachb. We construct a polytopeSt(A) whose normal cones are the equivalence classes. Explicit inequality presentations of these cones are given by the reduced Gröbner bases associated withA. The union of the reduced Gröbner bases asc varies (called the universal Gröbner basis) consists precisely of the edge directions ofSt(A). We present geometric algorithms for computingSt(A), the Graver basis, and the universal Gröbner basis.     

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.     

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.     

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.     

The Behaviors of Expansion Functor on Monomial Ideals and Toric Rings

In this article, we study some algebraic and combinatorial behaviors of expansion functor. We show that on monomial ideals some properties like polymatroidalness, weakly polymatroidalness, and having linear quotients are preserved under taking the expansion functor.

The main part of the article is devoted to study of toric ideals associated to the expansion of subsets of monomials which are minimal with respect to divisibility. It is shown that, for a given discrete polymatroid P, if toric ideal of P is generated by double swaps, then toric ideal of any expansion of P has such a property. This result, in a special case, says that White's conjecture is preserved under taking the expansion functor. Finally, the construction of Gröbner bases and some homological properties of toric ideals associated to expansions of subsets of monomials is investigated.     

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 bases of characteristic ideals of LRS over UFD

LetR be a unique factorization domain (UFD). A method of Gröbner bases and localization in commutative algebra is applied to compute and analyze the characteristic ideals of semi-infinite linear recurring sequences (lrs), infinite linear recurring sequences (LRS), and finite lrs over UFD. The canonical form of a minimal Gröbner basis of the homogeneous characteristic ideal is described for a finite segment of an lrs, from which a precise relation between every step in the classical Berlekamp-Massey algorithm and every member of the Gröbner basis is derived.     

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.     

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