Artificial discontinuities of single-parametric Gröbner bases

Artificial discontinuity is a kind of singularity at a parametric point in computing the Gröbner basis of a specialized parametric ideal w.r.t. a certain term order. When it occurs, though parameters change continuously at the point and the properties of the parametric ideal have no sudden changes, the Gröbner basis will still have a jump at the parametric point. This phenomenon can cause instabilities in computing approximate Gröbner bases.In this paper, we study artificial discontinuities in single-parametric case by proposing a solid theoretical foundation for them. We provide a criterion to recognize artificial discontinuities by comparing the zero point numbers of specialized parametric ideals. Moreover, we prove that for a single-parametric polynomial ideal with some restrictions, its artificially discontinuous specializations (ADS) can be locally repaired to continuous specializations (CS) by the TSV (Term Substitution with Variables) strategy.     

The Gröbner basis of the ideal of vanishing polynomials

We construct an explicit minimal strong Gröbner basis of the ideal of vanishing polynomials in the polynomial ring over Z/m for m≥2. The proof is done in a purely combinatorial way. It is a remarkable fact that the constructed Gröbner basis is independent of the monomial order and that the set of leading terms of the constructed Gröbner basis is unique, up to multiplication by units. We also present a fast algorithm to compute reduced normal forms, and furthermore, we give a recursive algorithm for building a Gröbner basis in Z/m[x₁,x₂,…,x_n] along the prime factorization of m. The obtained results are not only of mathematical interest but have immediate applications in formal verification of data paths for microelectronic systems-on-chip.     

Computing minimal associated primes in polynomial rings over the integers

An algorithm is presented to compute the minimal associated primes of an ideal in a polynomial ring over the integers. It differs from the known algorithms insofar as it avoids having to compute Gröbner bases over the integers until the very end, thereby eliminating one of the bottlenecks of those algorithms.     

Gröbner bases for polynomial systems with parameters

Gröbner bases are the computational method par excellence for studying polynomial systems. In the case of parametric polynomial systems one has to determine the reduced Gröbner basis in dependence of the values of the parameters. In this article, we present the algorithm GröbnerCover which has as inputs a finite set of parametric polynomials, and outputs a finite partition of the parameter space into locally closed subsets together with polynomial data, from which the reduced Gröbner basis for a given parameter point can immediately be determined. The partition of the parameter space is intrinsic and particularly simple if the system is homogeneous.     

Reduced Gröbner Bases,Free Difference–Differential Modules and Difference–Differential Dimension Polynomials

We define a special type of reduction in a free left module over a ring of difference–differential operators and use the idea of the Gröbner basis method to develop a technique that allows us to determine the Hilbert function of a finitely generated difference–differential module equipped with the natural double filtration. The results obtained are applied to the study of difference–differential field extensions and systems of difference–differential equations. We prove a theorem on difference–differential dimension polynomial that generalizes both the classical Kolchin’s theorem on dimension polynomial of a differential field extension and the corresponding author’s result for difference fields. We also determine invariants of a difference–differential dimension polynomial and consider a method of computation of the dimension polynomial associated with a system of linear difference–differential equations.     

Boolean Gröbner bases

In recent years, Boolean Gröbner bases have attracted the attention of many researchers, mainly in connection with cryptography. Several sophisticated methods have been developed for the computation of Boolean Gröbner bases. However, most of them only deal with Boolean polynomial rings over the simplest coefficient Boolean ring GF₂. Boolean Gröbner bases for arbitrary coefficient Boolean rings were first introduced by two of the authors almost two decades ago. While the work is not well-known among computer algebra researchers, recent active work on Boolean Gröbner bases inspired us to return to their development. In this paper, we introduce our work on Boolean Gröbner bases with arbitrary coefficient Boolean rings.     

Gröbner basis of the alternating galoisian ideal

This article proposes an efficient and simple algebraic method of computation of a Gröbner basis generating the alternating galoisian ideal of a univariate separable polynomial. We named this method “the descent of the Vandermonde determinants”.     

Lattice Polly Cracker cryptosystems

Using Gröbner bases for the construction of public key cryptosystems has been often attempted, but has always failed.We review the reason for these failures, and show that only ideals generated by binomials may give a successful cryptosystem.As a consequence, we concentrate on binomial ideals that correspond to Euclidean lattices. We show how to build a cryptosystem based on lattice ideals and their Gröbner bases, and, after breaking a simple variant, we construct a more elaborate one. In this variant the trapdoor information consists in a “small” change of coordinates that allows one to recover a “fat” Gröbner basis. While finding a change of coordinates giving a fat Gröbner basis is a relatively easy problem, finding a small one seems to be a hard optimization problem.This paper develops the details and proofs related to computer algebra, the cryptographic details related to security, the comparison with other lattice cryptosystems and discusses the implementation.     

Generating all polynomial invariants in simple loops

This paper presents a method for automatically generating all polynomial invariants in simple loops. It is first shown that the set of polynomials serving as loop invariants has the algebraic structure of an ideal. Based on this connection, a fixpoint procedure using operations on ideals and Gröbner basis constructions is proposed for finding all polynomial invariants. Most importantly, it is proved that the procedure terminates in at most m+1$m+1$ iterations, where m$m$ is the number of program variables. The proof relies on showing that the irreducible components of the varieties associated with the ideals generated by the procedure either remain the same or increase their dimension at every iteration of the fixpoint procedure. This yields a correct and complete algorithm for inferring conjunctions of polynomial equalities as invariants. The method has been implemented in Maple using the Groebner package. The implementation has been used to automatically discover non-trivial invariants for several examples to illustrate the power of the technique.     

An Algorithm To Compute The Invariant Ring Of A Ga-action On An Affine Variety

We describe an algorithm which computes the invariants of all Ga-actions on affine varieties, in case the invariant ring is finitely generated.The algorithm is based on a study of the kernel of a locally nilpotent derivation and some algorithms from the theory of Gröbner bases.     

Parallel computation of Janet and Gröbner bases over rational numbers

In this paper, a parallel algorithm for computation of polynomial Janet bases is considered. After construction of a Janet basis, a reduced Gröbner basis (which is a subset of the Janet basis) is extracted from it without any additional reductions. The algorithm discussed is an improved version of an earlier suggested parallel algorithm. The efficiency of a C implementation of the algorithm and its scalability are illustrated by way of the standard test examples that are often used for comparing various algorithms and codes for computing Gröbner bases.Translated from Programmirovanie, Vol. 31, No. 2, 2005.Original Russian Text Copyright © 2005 by Gerdt, Yanovich.     

Computing the algebraic relations of C-finite sequences and multisequences

We present an algorithm for computing generators for the ideal of algebraic relations among sequences which are given by homogeneous linear recurrence equations with constant coefficients. Knowing these generators makes it possible to use Gröbner basis methods for carrying out certain basic operations in the ring of such sequences effectively. In particular, one can answer the question whether a given sequence can be represented in terms of other given sequences.     

Computing restrictions of ideals in finitely generated k-algebras by means of Buchberger’s algorithm

Gröbner bases can be used to solve various algorithmic problems in the context of finitely generated field extensions. One key idea is the computation of a certain kind of restriction of an ideal to a subring. With this restricted ideal many problems concerning function fields reduce to ideal theoretic problems which can be solved by means of Buchberger’s algorithm. In this contribution this approach is generalized to allow the computation of the restriction of an arbitrary ideal to a subring.     

Gröbner bases with respect to several orderings and multivariable dimension polynomials

Let D=K[X]$D=K\left[X\right]$ be a ring of Ore polynomials over a field K$K$ and let a partition of the set of indeterminates into p$p$ disjoint subsets be fixed. Considering D$D$ as a filtered ring with the natural p$p$-dimensional filtration, we introduce a special type of reduction in a free D$D$-module and develop the corresponding Gröbner basis technique (in particular, we obtain a generalization of the Buchberger Algorithm). Using such a modification of the Gröbner basis method, we prove the existence of a Hilbert-type dimension polynomial in p$p$ variables associated with a finitely generated filtered D$D$-module, give a method of computation and describe invariants of such a polynomial. The results obtained are applied in differential algebra where the classical theorems on differential dimension polynomials are generalized to the case of differential structures with several basic sets of derivation operators.     

Design of Marx generators as a structured eigenvalue assignment

We consider the design problem for a Marx generator electrical network, a pulsed power generator. We show that the components design can be conveniently cast as a structured real eigenvalue assignment with significantly lower dimension than the state size of the Marx circuit. Then we present two possible approaches to determine its solutions. A first symbolic approach consists in the use of Gröbner basis representations, which allows us to compute all the (finitely many) solutions. A second approach is based on convexification of a nonconvex optimization problem with polynomial constraints. We also comment on the conjecture that for any number of stages the problem has finitely many solutions, which is a necessary assumption for the proposed methods to converge. We regard the proof of this conjecture as an interesting challenge of general interest in the real algebraic geometry field.     

Flat families by strongly stable ideals and a generalization of Gröbner bases

Let J be a strongly stable monomial ideal in S=K[x₀,…,x_n] and let Mf(J) be the family of all homogeneous ideals I in S such that the set of all terms outside J is a K-vector basis of the quotient S/I. We show that an ideal I belongs to Mf(J) if and only if it is generated by a special set of polynomials, the J-marked basis of I, that in some sense generalizes the notion of reduced Gröbner basis and its constructive capabilities. Indeed, although not every J-marked basis is a Gröbner basis with respect to some term order, a sort of reduced form modulo I∈Mf(J) can be computed for every homogeneous polynomial, so that a J-marked basis can be characterized by a Buchberger-like criterion. Using J-marked bases, we prove that the family Mf(J) can be endowed, in a very natural way, with a structure of an affine scheme that turns out to be homogeneous with respect to a non-standard grading and flat in the origin (the point corresponding to J), thanks to properties ofJ-marked bases analogous to those of Gröbner bases about syzygies.     

A new Gröbner basis conversion method based on stabilization techniques

We propose a new method for converting a Gröbner basis w.r.t. one term order into a Gröbner basis w.r.t. another term order by using the algorithm stabilization techniques proposed by Shirayanagi and Sweedler. First, we guess the support of the desired Gröbner basis from a floating-point Gröbner basis by exploiting the supportwise convergence property of the stabilized Buchberger’s algorithm. Next, assuming this support to be correct, we use linear algebra, namely, the method of indeterminate coefficients to determine the exact values for the coefficients. Related work includes the FGLM algorithm and its modular version. Our method is new in the sense that it can be thought of as a floating-point approach to the linear algebra method. The results of Maple computing experiments indicate that our method can be very effective in the case of non-rational coefficients, especially the ones including transcendental constants.     

Looking for Gröbner basis theory for (almost) skew 2-nomial algebras

In this paper, we introduce (almost) skew 2-nomial algebras and look for a one-sided or two-sided Gröbner basis theory for such algebras at a modest level. That is, we establish the existence of a skew multiplicative K$K$-basis for every skew 2-nomial algebra, and we explore the existence of a (left, right, or two-sided) monomial ordering for an (almost) skew 2-nomial algebra. As distinct from commonly recognized algebras holding a Gröbner basis theory (such as algebras of the solvable type (Kandri-Rody and Weispfenning, 1990) and some of their homomorphic images), a subclass of skew 2-nomial algebras that have a left Gröbner basis theory but may not necessarily have a two-sided Gröbner basis theory, respectively a subclass of skew 2-nomial algebras that have a right Gröbner basis theory but may not necessarily have a two-sided Gröbner basis theory, are determined such that numerous quantum binomial algebras (which provide binomial solutions to the Yang–Baxter equation) and their Koszul dual (Gateva-Ivanova and Van den Bergh, 1998, Laffaille, 2000 and Gateva-Ivanova, 2009) are involved.     

List decoding of Reed–Solomon codes from a Gröbner basis perspective

The interpolation step of Guruswami and Sudan’s list decoding of Reed–Solomon codes poses the problem of finding the minimal polynomial of an ideal with respect to a certain monomial order. An efficient algorithm that solves the problem is presented based on the theory of Gröbner bases of modules. In a special case, this algorithm reduces to a simple Berlekamp–Massey-like decoding algorithm.     

The F5 criterion revised

The purpose of this work is to generalize part of the theory behind Faugère’s “F5” algorithm. This is one of the fastest known algorithms to compute a Gröbner basis of a polynomial ideal I generated by polynomials f₁,…,f_m. A major reason for this is what Faugère called the algorithm’s “new” criterion, and we call “the F5 criterion”; it provides a sufficient condition for a set of polynomials G to be a Gröbner basis. However, the F5 algorithm is difficult to grasp, and there are unresolved questions regarding its termination.This paper introduces some new concepts that place the criterion in a more general setting: S-Gröbner bases and primitive S-irreducible polynomials. We use these to propose a new, simple algorithm based on a revised F5 criterion. The new concepts also enable us to remove various restrictions, such as proving termination without the requirement that f₁,…,f_m be a regular sequence.