Applying Gröbner basis techniques to group theory

We apply the machinery of Gröbner bases to finitely presented groups. This allows for computational methods to be developed which prove that a given finitely presented group is not n-linear over a field k assuming some mild conditions. We also present an algorithm which determines whether or not a finitely presented group G is trivial given that an oracle has told us that G is n-linear over an algebraically closed field k.     

Gröbner–Shirshov bases of some monoids

The main goal of this paper is to define Gröbner–Shirshov bases for some monoids. Therefore, after giving some preliminary material, we first give Gröbner–Shirshov bases for graphs and Schützenberger products of monoids in separate sections. In the final section, we further present a Gröbner–Shirshov basis for a Rees matrix semigroup.     

On the critical ideals of graphs

We introduce some determinantal ideals of the generalized Laplacian matrix associated to a digraph G, that we call critical ideals of G. Critical ideals generalize the critical group and the characteristic polynomials of the adjacency and Laplacian matrices of a digraph. The main results of this article are the determination of some minimal generator sets and the reduced Gröbner basis for the critical ideals of the complete graphs, the cycles and the paths. Also, we establish a bound between the number of trivial critical ideals and the stability and clique numbers of a graph.     

The symmetric group given by a Gröbner basis

We present a Gröbner basis associated with the symmetric group of degree n, which is determined by a strong generating set of the symmetric group and is defined by means of a term ordering with the elimination property.     

Gröbner-Shirshov bases for associative algebras with multiple operators and free Rota-Baxter algebras

In this paper, we establish the Composition-Diamond lemma for associative algebras with multiple linear operators. As applications, we obtain Gröbner-Shirshov bases of free Rota-Baxter algebra, free λ-differential algebra and free λ-differential Rota-Baxter algebra, respectively. In particular, linear bases of these three free algebras are respectively obtained, which are essentially the same or similar to the recent results obtained by K. Ebrahimi-Fard-L. Guo, and L. Guo-W. Keigher by using other methods.     

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.     

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 .     

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.     

Gröbner bases of ideals cogenerated by Pfaffians

We characterise the class of one-cogenerated Pfaffian ideals whose natural generators form a Gröbner basis with respect to any anti-diagonal term order. We describe their initial ideals as well as the associated simplicial complexes, which turn out to be shellable and thus Cohen-Macaulay. We also provide a formula for computing their multiplicity.     

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 bases for spaces of quadrics of codimension 3

Let R=⊕_i≥0R_i be an Artinian standard graded K-algebra defined by quadrics. Assume that dimR₂≤3 and that K is algebraically closed, of characteristic ≠2. We show that R is defined by a Gröbner basis of quadrics with, essentially, one exception. The exception is given by K[x,y,z]/I where I is a complete intersection of three quadrics not containing a square of a linear form.     

Gröbner–Shirshov Bases for Universal Enveloping Conformal Algebras of Simple Conformal Lie Superalgebras of Type WN

For simple conformal Lie superalgebras of type W_N, Gröbner–Shirshov bases of their universal enveloping associative conformal algebras are found. The universal enveloping algebras considered correspond to a minimal locality function for which there is an injective embedding.     

Gröbner–Shirshov Bases: From their Incipiency to the Present

In this paper, the history and the main results of the theory of Gröbner–Shirshov bases are given for commutative, noncommutative, Lie, and conformal algebras from the beginning (1962) to the present time. The problem of constructing a base of a free Lie algebra is considered, as well as the problem of studying the structure of free products of Lie algebras, the word problem for Lie algebras, and the problem of embedding an arbitrary Lie algebra into an algebraically closed one. The modern form of the composition-diamond lemma (the CD lemma) is presented. The rewriting systems for groups are considered from the point of view of Gröbner–Shirshov bases. The important role of conformal algebras is treated, the statement of the CD lemma for associative conformal algebras is given, and some examples are considered. An analog of the Hilbert basis theorem for commutative conformalalgebras is stated. Bibliography: 173 titles.     

Degree bounds for Gröbner bases in algebras of solvable type

We establish doubly-exponential degree bounds for Gröbner bases in certain algebras of solvable type over a field (as introduced by Kandri-Rody and Weispfenning). The class of algebras considered here includes commutative polynomial rings, Weyl algebras, and universal enveloping algebras of finite-dimensional Lie algebras. For the computation of these bounds, we adapt a method due to Dubé based on a generalization of Stanley decompositions. Our bounds yield doubly-exponential degree bounds for ideal membership and syzygies, generalizing the classical results of Hermann and Seidenberg (in the commutative case) and Grigoriev (in the case of Weyl algebras).     

Representations of Ariki-Koike Algebras and Grobner-Shirshov Bases

In this paper, we investigate the structure of Ariki–Koikealgebras and their Specht modules using Gröbner–Shirshovbasis theory and combinatorics of Young tableaux. For a multipartition, we find a presentation of the Specht module S given by generatorsand relations, and determine its Gröbner–Shirshovpair. As a consequence, we obtain a linear basis of S consistingof standard monomials with respect to the Gröbner–Shirshovpair. We show that this monomial basis can be canonically identifiedwith the set of cozy tableaux of shape . 2000 Mathematics SubjectClassification 16Gxx, 05Exx.     

Periodic elements in Garside groups

Let G be a Garside group with Garside element Δ, and let Δ^m be the minimal positive central power of Δ. An element g∈G is said to be periodic if some power of it is a power of Δ. In this paper, we study periodic elements in Garside groups and their conjugacy classes.We show that the periodicity of an element does not depend on the choice of a particular Garside structure if and only if the center of G is cyclic; if g^k=Δ^ka for some nonzero integer k, then g is conjugate to Δ^a; every finite subgroup of the quotient group G/〈Δ^m〉 is cyclic.By a classical theorem of Brouwer, Kerékjártó and Eilenberg, an n-braid is periodic if and only if it is conjugate to a power of one of two specific roots of Δ². We generalize this to Garside groups by showing that every periodic element is conjugate to a power of a root of Δ^m.We introduce the notions of slimness and precentrality for periodic elements, and show that the super summit set of a slim, precentral periodic element is closed under any partial cycling. For the conjugacy problem, we may assume the slimness without loss of generality. For the Artin groups of type , , , and the braid group of the complex reflection group of type (e,e,n), endowed with the dual Garside structure, we may further assume the precentrality.     

Groups with a positive law on commutators

Let p be a prime number and let G be a finitely generated group that is residually a finite p-group. We prove that if G satisfies a positive law on all elements of the form [a,b][c,d]ⁱ, a,b,c,d∈G and i?0, then the entire derived subgroup G^′ satisfies a positive law. In fact, G^′ is an extension of a nilpotent group by a locally finite group of finite exponent.     

On Lovász’ lattice reduction and the nearest lattice point problem

Answering a question of Vera Sós, we show how Lovász’ lattice reduction can be used to find a point of a given lattice, nearest within a factor ofc ^d (c = const.) to a given point in R ^d . We prove that each of two straightforward fast heuristic procedures achieves this goal when applied to a lattice given by a Lovász-reduced basis. The verification of one of them requires proving a geometric feature of Lovász-reduced bases: ac ₁ ^d lower bound on the angle between any member of the basis and the hyperplane generated by the other members, wherec ₁ = √2/3. As an application, we obtain a solution to the nonhomogeneous simultaneous diophantine approximation problem, optimal within a factor ofC ^d . In another application, we improve the Grötschel-Lovász-Schrijver version of H. W. Lenstra’s integer linear programming algorithm. The algorithms, when applied to rational input vectors, run in polynomial time.     

Basic deformation theory of smooth formal schemes

We provide the main results of a deformation theory of smooth formal schemes as defined in [L. Alonso Tarrío, A. Jeremías López, M. Pérez Rodríguez, Infinitesimal lifting and Jacobi criterion for smoothness on formal schemes, Comm. Algebra 35 (2007) 1341-1367]. Smoothness is defined by the local existence of infinitesimal liftings. Our first result is the existence of an obstruction in a certain Ext¹ group whose vanishing guarantees the existence of global liftings of morphisms. Next, given a smooth morphism f₀:X₀→Y₀ of noetherian formal schemes and a closed immersion Y₀?Y given by a square zero ideal I, we prove that the set of isomorphism classes of smooth formal schemes lifting X₀ over Y is classified by and that there exists an element in which vanishes if and only if there exists a smooth formal scheme lifting X₀ over Y.     

Some stably tame polynomial automorphisms

We study the structure of length three polynomial automorphisms of R[X,Y] when R is a UFD. These results are used to prove that if SL_m(R[X₁,X₂,…,X_n])=E_m(R[X₁,X₂,…,X_n]) for all n≥0 and for all m≥3 then all length three polynomial automorphisms of R[X,Y] are stably tame.