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.     

Automatic deduction in (dynamic) geometry: Loci computation

A symbolic tool based on open source software that provides robust algebraic methods to handle automatic deduction tasks for a dynamic geometry construction is presented. The prototype has been developed as two different worksheets for the open source computer algebra system Sage, corresponding to two different ways of coding a geometric construction, namely with the open source dynamic geometry system GeoGebra or using the common file format for dynamic geometry developed by the Intergeo project. Locus computation algorithms based on Automatic Deduction techniques are recalled and presented as basic for an efficient treatment of advanced methods in dynamic geometry. Moreover, an algorithm to eliminate extraneous parts in symbolically computed loci is discussed. The algorithm, based on a recent work on the Gröbner cover of parametric systems, identifies degenerate components and extraneous adherence points in loci, both natural byproducts of general polynomial algebraic methods. Several examples are shown in detail.     

NON-COMMUTATIVE GRÖBNER BASES UNDER COMPOSITION

Polynomial composition is the operation of replacing the variables in a polynomial with other polynomials. In this paper we give sufficient and necessary conditions on a set Θ of non-commutative polynomials to assure that the set G ○ Θ of composed polynomials is a Gröbner basis in the free associative algebra whenever G is. The subject was initiated by Hong, treating the commutative analogue in (1998, J. Symb. Comput. 25, 643–663).     

Amortized multi-point evaluation of multivariate polynomials

The evaluation of a polynomial at several points is called the problem of multi-point evaluation. Sometimes, the set of evaluation points is fixed and several polynomials need to be evaluated at this set of points. Several efficient algorithms for this kind of “amortized” multi-point evaluation have been developed recently for the special cases of bivariate polynomials or when the set of evaluation points is generic. In this paper, we extend these results to the evaluation of polynomials in an arbitrary number of variables at an arbitrary set of points. We prove a softly linear complexity bound when the number of variables is fixed. Our method relies on a novel quasi-reduction algorithm for multivariate polynomials, that operates simultaneously with respect to several orderings on the monomials.     

IDEALS OF MINORS DEFINING GENERIC SINGULARITIES AND THEIR GRöBNER BASES

In this article, using the local parametric equations of a generic projection π of a smooth projective variety X, at an analytically irreducible singular point y of X′ = π(X), the defining ideals J and J′ of X′ and its singular locus at y are expressed as ideals of maximal and sub-maximal minors of certain Sylvester matrix @. The proof is obtained by a convenient reduction of @ to a “generic pluri-circulant matrix” P and the construction of minimal Gröbner bases for the ideal of t-minors of P and for the ideals J and J′. The depth of local rings of X′ and Sing (X′) at y are also computed in terms of the multiplicity at y.     

Gröbner deformations and F-singularities

For polynomial ideals in positive characteristic, defining F-split rings and admitting a squarefree monomial initial ideal are different notions. In this note, we show that, however, there are strong interactions in both directions. Moreover, we provide an overview on which F-singularities are Gröbner deforming. Also, we prove the following characteristic-free statement: If $\mathfrak{p}$ is a height h prime ideal such that $\mathrm{in}({\mathfrak{p}}^{(h)})$ contains at least one squarefree monomial, then $\mathrm{in}(\mathfrak{p})$ is a squarefree monomial ideal.     

An improvement over the GVW algorithm for inhomogeneous polynomial systems

The GVW algorithm provides a new framework for computing Gröbner bases efficiently. If the input system is not homogeneous, some J-pairs with larger signatures but lower degrees may be rejected by GVW's criteria, and instead, GVW has to compute some J-pairs with smaller signatures but higher degrees. Consequently, degrees of polynomials appearing during the computations may unnecessarily grow up higher, and hence, the total computations become more expensive. This phenomenon happens more frequently when the coefficient field is a finite field and the field polynomials are involved in the computations. In this paper, a variant of the GVW algorithm, called M-GVW, is proposed. The concept of mutant pairs is introduced to overcome the inconveniences brought by inhomogeneous inputs. In aspects of implementations, to obtain efficient implementations of GVW/M-GVW over boolean polynomial rings, we take advantages of the famous library M4RI. We propose a new rotating swap method of adapting efficient routines in M4RI to deal with the one-direction reductions in GVW/M-GVW. Our implementations are tested with many examples from Boolean polynomial rings, and the timings show M-GVW usually performs much better than the original GVW algorithm if mutant pairs are found.     

Ideals Generated by Diagonal 2-Minors

With a simple graph G on [n], we associate a binomial ideal P_G generated by diagonal minors of an n × n matrix X = (x_ij) of variables. We show that for any graph G, P_G is a prime complete intersection ideal and determine the divisor class group of K[X]/P_G. By using these ideals, one may find a normal domain with free divisor class group of any given rank.     

Symbolic Differential Elimination for Symmetry Analysis

Differential problems are ubiquitous in mathematical modeling of physical and scientific problems. Algebraic analysis of differential systems can help in determining qualitative and quantitative properties of solutions of such systems. In this tutorial paper we describe several algebraic methods for investigating differential systems.     

On generator and parity-check polynomial matrices of generalized quasi-cyclic codes

Generalized quasi-cyclic (GQC) codes have been investigated as well as quasi-cyclic (QC) codes, e.g., on the construction of efficient low-density parity-check codes. While QC codes have the same length of cyclic intervals, GQC codes have different lengths of cyclic intervals. Similarly to QC codes, each GQC code can be described by an upper triangular generator polynomial matrix, from which the systematic encoder is constructed. In this paper, a complete theory of generator polynomial matrices of GQC codes, including a relation formula between generator polynomial matrices and parity-check polynomial matrices through their equations, is provided. This relation generalizes those of cyclic codes and QC codes. While the previous researches on GQC codes are mainly concerned with 1-generator case or linear algebraic approach, our argument covers the general case and shows the complete analogy of QC case. We do not use Gröbner basis theory explicitly in order that all arguments of this paper are self-contained. Numerical examples are attached to the dual procedure that extracts one from each other. Finally, we provide an efficient algorithm which calculates all generator polynomial matrices with given cyclic intervals.     

求鳞状循环因子矩阵的极小多项式的算法

提出了任意域上鳞状循环因子矩阵 ,利用多项式环的理想的Go bner基的算法给出了任意域上鳞状循环因子矩阵的极小多项式和公共极小多项式的一种算法 .同时给出了这类矩阵逆矩阵的一种求法 .在有理数域或模素数剩余类域上 ,这一算法可由代数系统软件Co CoA4 .0实现 .数值例子说明了算法的有效性     

求首尾和r-循环矩阵的极小多项式的算法

研究了域上首尾和r-循环矩阵，利用多项式环的理想的Groebner基的算法给出了任意域上首尾和r-循环矩阵的极小多项式和公共极小多项式的一种算法.同时给出了这类矩阵逆矩阵的一种求法。     

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

Resolutions of 2 and 3 Dimensional Rings of Invariants for Cyclic Groups

Let G be the cyclic group of order n, and suppose F is a field containing a primitive nth root of unity. We consider the ring of invariants F[W] ^G of a three dimensional representation W of G where G ? SL(W). We describe minimal generators and relations for this ring and prove that the lead terms of the relations are quadratic. These minimal generators for the relations form a Gröbner basis with a surprisingly simple combinatorial structure. We describe the graded Betti numbers for a minimal free resolution of F[W] ^G . The case where W is any two dimensional representation of G is also handled.