Search

This paper is concerned with the factorization and equivalence problems of multivariate polynomial matrices. We present some new criteria for the existence of matrix factorizations for a class of multivariate polynomial matrices, and obtain a necessary and sufficient condition for the equivalence of a square polynomial matrix and a diagonal matrix. Based on the constructive proof of the new criteria, we give a factorization algorithm and prove the uniqueness of the factorization. We implement the algorithm on Maple, and two illustrative examples are given to show the effectiveness of the algorithm. [ABSTRACT FROM AUTHOR]

As a fundamental notion, the free differential algebra on a set is concretely constructed as the polynomial algebra on the differential variables. Such a construction is not known for the more general notion of the free differential algebra on an algebra, from the left adjoint functor of the forgetful functor from differential algebras to algebras, instead of sets. In this paper we show that a generator-relation presentation of a base algebra can be extended to the free differential algebra on this base algebra. More precisely, a Gröbner-Shirshov basis property of the base algebra can be extended to the free differential algebra on this base algebra, allowing a Poincaré-Birkhoff-Witt type basis for these more general free differential algebras. Examples are provided as illustrations. [ABSTRACT FROM AUTHOR]

Vizing's conjecture (open since 1968) relates the product of the domination numbers of two graphs to the domination number of their Cartesian product graph. In this paper, we formulate Vizing's conjecture as a Positivstellensatz existence question. In particular, we select classes of graphs according to their number of vertices and their domination number and encode the conjecture as an ideal/polynomial pair such that the polynomial is non-negative on the variety associated with the ideal if and only if the conjecture is true for this graph class. Using semidefinite programming we obtain numeric sum-of-squares certificates, which we then manage to transform into symbolic certificates confirming non-negativity of our polynomials. Specifically, we obtain exact low-degree sparse sum-of-squares certificates for particular classes of graphs. The obtained certificates allow generalizations for larger graph classes. Besides computational verification of these more general certificates, we also present theoretical proofs as well as conjectures and questions for further investigations. [ABSTRACT FROM AUTHOR]

The W-characteristic set of a polynomial ideal is the minimal triangular set contained in the reduced lexicographical Gröbner basis of the ideal. A pair (G , C) of polynomial sets is a strong regular characteristic pair if G is a reduced lexicographical Gröbner basis, C is the W-characteristic set of the ideal 〈 G 〉 , the saturated ideal sat (C) of C is equal to 〈 G 〉 , and C is regular. In this paper, we show that for any polynomial ideal I with given generators one can either detect that I is unit, or construct a strong regular characteristic pair (G , C) by computing Gröbner bases such that I ⊆ sat (C) = 〈 G 〉 and sat (C) divides I , so the ideal I can be split into the saturated ideal sat (C) and the quotient ideal I : sat (C). Based on this strategy of splitting by means of quotient and with Gröbner basis and ideal computations, we devise a simple algorithm to decompose an arbitrary polynomial set F into finitely many strong regular characteristic pairs, from which two representations for the zeros of F are obtained: one in terms of strong regular Gröbner bases and the other in terms of regular triangular sets. We present some properties about strong regular characteristic pairs and characteristic decomposition and illustrate the proposed algorithm and its performance by examples and experimental results. [ABSTRACT FROM AUTHOR]

The famous open Vizing conjecture claims that the domination number of the Cartesian product graph of two graphs G and H is at least the product of the domination numbers of G and H. Recently Gaar, Krenn, Margulies and Wiegele used the graph class G of all graphs with n G vertices and domination number k G and reformulated Vizing's conjecture as the problem that for all graph classes G and H the Vizing polynomial is sum-of-squares (SOS) modulo the Vizing ideal. By solving semidefinite programs (SDPs) and clever guessing they derived SOS-certificates for some values of k G , n G , k H , and n H. In this paper, we consider their approach for k G = k H = 1. For this case we are able to derive the unique reduced Gröbner basis of the Vizing ideal. Based on this, we deduce the minimum degree (n G + n H − 1) / 2 of an SOS-certificate for Vizing's conjecture, which is the first result of this kind. Furthermore, we present a method to find certificates for graph classes G and H with n G + n H − 1 = d for general d , which is again based on solving SDPs, but does not depend on guessing and depends on much smaller SDPs. We implement our new method in SageMath and give new SOS-certificates for all graph classes G and H with k G = k H = 1 and n G + n H ≤ 15. [ABSTRACT FROM AUTHOR]

Given n ⩾ 2 and a 1 , ... , a n ∈ N. Let S = 〈 a 1 , ... , a n 〉 be a semigroup. The aim of this paper is to give an effective pseudo-polynomial algorithm on a 1 , which computes the Apéry set and the Frobenius number of S. We also find the Gröbner basis of the toric ideal defined by S , for the weighted degree reverse lexicographical order ≺ w to x 1 , ... , x n , without using Buchberger's algorithm. As an application we introduce and study some special classes of semigroups. Namely, when S is generated by generalized arithmetic progressions and generalized almost arithmetic progressions with the ratio a positive or a negative number. We determine symmetric and almost symmetric semigroups generated by a generalized arithmetic progression. [ABSTRACT FROM AUTHOR]

We study invariant Einstein metrics on the Stiefel manifold V k R n ≅ SO (n) / SO (n − k) of all orthonormal k -frames in R n. The isotropy representation of this homogeneous space contains equivalent summands, so a complete description of G -invariant metrics is not easy. In this paper we view the manifold V 2 p R n as total space over a classical generalized flag manifold with two isotropy summands and prove for 2 ≤ p ≤ 2 5 n − 1 it admits at least four invariant Einstein metrics determined by Ad (U (p) × SO (n − 2 p)) -invariant scalar products. Two of the metrics are Jensen's metrics and the other two are new Einstein metrics. The Einstein equation reduces to a parametric system of polynomial equations, which we study by combining Gröbner bases and geometrical arguments. [ABSTRACT FROM AUTHOR]

In this paper, an injection from the partition lattice Π n to a zero-dimensional affine algebra over the finite field F 2 is constructed. We study some interesting properties of the injection and present two direct sum decompositions of the zero-dimensional affine algebra. Based upon these, some properties of Π n are revealed in an algebraic manner, for instance, the rank-generating function and characteristic polynomial of Π n can be derived using the symbolic method. [ABSTRACT FROM AUTHOR]

Abstract: A binomial ideal is an ideal of the polynomial ring which is generated by binomials. In a previous paper, we gave a correspondence between pure saturated binomial ideals of and submodules of and we showed that it is possible to construct a theory of Gröbner bases for submodules of . As a consequence, it is possible to follow alternative strategies for the computation of Gröbner bases of submodules of (and hence of binomial ideals) which avoid the use of Buchberger algorithm. In the present paper, we show that a Gröbner basis of a -module of rank lies into a finite set of cones of which cover a half-space of . More precisely, in each of these cones , we can find a suitable subset which has the structure of a finite abelian group and such that a Gröbner basis of the module (and hence of the pure saturated binomial ideal represented by ) is described using the elements of the groups together with the generators of the cones. [Copyright &y& Elsevier]

Abstract In this paper we compute Gröbner bases for determinantal ideals of the form I 1 (X Y) , where X and Y are both matrices whose entries are indeterminates over a field K. We use the Gröbner basis structure to determine Betti numbers for such ideals. [ABSTRACT FROM AUTHOR]

Factorization of polynomials into irreducible factors is an important problem with numerous applications, both over commutative and over non-commutative rings. It has been recently proved by Bell, Heinle and Levandovskyy that a large class of non-commutative algebras are finite factorization domains (FFD for short). This provides a termination criterion for a factorization algorithms of elements in a vast class of finitely presented K -algebras, which includes the ubiquitous G -algebras, encompassing algebras of common linear partial functional operators. In this paper, we contribute an algorithm to find all distinct factorizations of a given element in a G -algebra, with minor assumptions on the underlying field, and establish its complexity. Moreover, the property of being an FFD, in combination with the factorization algorithm, enables us to generalize the factorizing Gröbner basis algorithm for G -algebras. This algorithm is useful for various applications, e.g. in analysis of solution spaces of systems of linear partial functional equations with polynomial coefficients. Additionally, it is possible to include inequality constraints for ideals in the input. The developed algorithms are accompanied by freely available implementations and illustrated by interesting examples. [ABSTRACT FROM AUTHOR]

The paper considers a symbolic approach to Prony's method in several variables and its close connection to multivariate polynomial interpolation. Based on the concept of universal interpolation that can be seen as a weak generalization of univariate Chebychev systems, we can give estimates on the minimal number of evaluations needed to solve Prony's problem. [ABSTRACT FROM AUTHOR]

The main ingredient to construct an O -border basis of an ideal I ⊆ K [ x 1 , … , x n ] is the order ideal O , which is a basis of the K -vector space K [ x 1 , … , x n ] / I . In this paper we give a procedure to find all the possible order ideals associated with a lattice ideal I M (where M is a lattice of Z n ). The construction can be applied to ideals of any dimension (not only zero-dimensional) and shows that the possible order ideals are always in a finite number. For lattice ideals of positive dimension we also show that, although a border basis is infinite, it can be defined in finite terms. Furthermore we give an example which proves that not all border bases of a lattice ideal come from Gröbner bases. Finally, we give a complete and explicit description of all the border bases for ideals I M in case M is a 2-dimensional lattice contained in Z 2 . [ABSTRACT FROM AUTHOR]

Abstract: Code-based cryptography is an interesting alternative to classic number-theoretic public key cryptosystem since it is conjectured to be secure against quantum computer attacks. Many families of codes have been proposed for these cryptosystems such as algebraic geometry codes. In Márquez-Corbella et al. (2012) – for so called very strong algebraic geometry codes , where is an algebraic curve over , is an n-tuple of mutually distinct -rational points of and E is a divisor of with disjoint support from – it was shown that an equivalent representation can be found. The n-tuple of points is obtained directly from a generator matrix of , where the columns are viewed as homogeneous coordinates of these points. The curve is given by , the homogeneous elements of degree 2 of the vanishing ideal . Furthermore, it was shown that can be computed efficiently as the kernel of certain linear map. What was not shown was how to get the divisor F and how to obtain efficiently an adequate decoding algorithm for the new representation. The main result of this paper is an efficient computational approach to the first problem, that is getting F. The security status of the McEliece public key cryptosystem using algebraic geometry codes is still not completely settled and is left as an open problem. [Copyright &y& Elsevier]

This paper shows that for any given polynomial ideal the collection of Gröbner cones corresponding to -specific elimination orders forms a star-shaped region which contrary to first intuition in general is not convex. Moreover we show that the corresponding region may contain Gröbner cones intersecting in the boundary of the Gröbner fan in the origin only. This implies that Gröbner walks aiming for the elimination of variables from a polynomial ideal can be terminated earlier than previously known. We provide a slightly improved stopping criterion for a known Gröbner walk algorithm for the elimination of variables. [ABSTRACT FROM AUTHOR]

The question whether two Riemannian metrics on a certain manifold are isometric is a fundamental and also a challenging problem in differential geometry. In this paper we ask whether two non-Kähler homogeneous Einstein metrics on a certain flag manifold are isometric. We tackle this question by reformulating it into a related question on a parametric system of polynomial equations and answering it by carefully combining Gröbner bases and geometrical arguments. Using this technique, we are able to prove the isometry of such metrics. [ABSTRACT FROM AUTHOR]

Abstract: In computing approximate Gröbner bases, it is not easy to trace precision losses of floating-point coefficients of intermediate approximate polynomials. The measured precision losses are usually much larger than their genuine values. One reason causing this phenomenon is that most existing methods for tracing precision losses do not consider the dependence of such precision losses in any polynomial (as an equation). In this paper, we define an algebraic structure called PL-space (precision loss space) for a polynomial (as an equation) and set up a theory for it. We prove that any PL-space has a finite weak basis and a strong basis and show how they effect on tracing precision losses by an example. Based on the study of minimal strong bases, we propose the concept of dependence number which reveals the complexity of the dependence of precision losses in a polynomial. [Copyright &y& Elsevier]

Abstract: The computation of approximate Gröbner bases is reported to be highly unstable in the literature. Selecting a suitable length of floats is helpful for stabilizing this computation. In this paper, we present a method to compute such a suitable length of floats. We concentrate on a family of polynomial systems sharing the same support and study the relation between the lengths of floats and the coefficients of relevant polynomials. Then we give a reference length of floats for all the polynomial systems in the family. One feature of our method is that it need not utilize numerical algorithms of Gröbner bases. Hence, our method can avoid the influence of the instabilities of the existing numerical algorithms and thus will be helpful for designing stable ones (e.g., stable Shirayanagiʼs algorithm). Experiments show that our method can work out reliable and reasonably large lengths of floats for most of the tested benchmarks. [Copyright &y& Elsevier]

Abstract: A holonomic function is a differentiable or generalized function which satisfies a holonomic system of linear partial or ordinary differential equations with polynomial coefficients. The main purpose of this paper is to present algorithms for computing a holonomic system for the definite integral of a holonomic function with parameters over a domain defined by polynomial inequalities. If the integrand satisfies a holonomic difference–differential system including parameters, then a holonomic difference–differential system for the integral can also be computed. In the algorithms, holonomic distributions (generalized functions in the sense of L. Schwartz) are inevitably involved even if the integrand is a usual function. [Copyright &y& Elsevier]

Abstract: In this paper, a linear univariate representation for the roots of a zero-dimensional polynomial equation system is presented, where the complex roots of the polynomial system are represented as linear combinations of the roots of several univariate polynomial equations. An algorithm is proposed to compute such a representation for a given zero-dimensional polynomial equation system based on Gröbner basis computation. The main advantage of this representation is that the precision of the roots of the system can be easily controlled. In fact, based on the linear univariate representation, we can give the exact precisions needed for isolating the roots of the univariate equations in order to obtain roots of the polynomial system with a given precision. As a consequence, a root isolating algorithm for a zero-dimensional polynomial equation system can be easily derived from its linear univariate representation. [Copyright &y& Elsevier]

Abstract: 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. [Copyright &y& Elsevier]

Abstract: 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. [ABSTRACT FROM AUTHOR]

Abstract: 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 -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 () 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 () are involved. [Copyright &y& Elsevier]

Abstract: This paper presents an algebraic approach to polynomial spectral factorization, an important mathematical tool in signal processing and control. The approach exploits an intriguing relationship between the theory of Gröbner bases and polynomial spectral factorization which can be observed through the sum of roots, and allows us to perform polynomial spectral factorization in the presence of real parameters. It is discussed that parametric polynomial spectral factorization enables us to express quantities such as the optimal cost in terms of parameters and the sum of roots. Furthermore an optimization method over parameters is suggested that makes use of the results from parametric polynomial spectral factorization and also employs two quantifier elimination techniques. This proposed approach is demonstrated in a numerical example of a particular control problem. [Copyright &y& Elsevier]

Abstract: Lawrence semigroups arise as a tool to compute Graver bases of semigroup ideals. It is known that the minimal free resolution of semigroup ideals is characterized by the reduced homologies of certain simplicial complexes. In this paper we study the minimal degrees of a Lawrence semigroup ideal and its first syzygy given a combinatorial characterization of the nonvanishing cycles in their associated reduced homologies. We specialize the results that appeared in [Briales, E., Campillo, A., Marijuán, C., Pisón, P., 1998. Minimal systems of generators for ideals of semigroups. J. Pure Appl. Algebra, 127, 7–30] and [Pisón-Casares, P., Vigneron-Tenorio, A., 2001. First syzygies of toric varieties and diophantine equations in congruence. Comm. Alg. 29 (4), 1445–1466] to the Lawrence semigroups. [Copyright &y& Elsevier]

Abstract: Latin squares can be seen as multiplication tables of quasigroups, which are, in general, non-commutative and non-associative algebraic structures. The number of Latin squares having a fixed isotopism in their autotopism group is at the moment an open problem. In this paper, we use Gröbner bases to describe an algorithm that allows one to obtain the previous number. Specifically, this algorithm is implemented in Singular to obtain the number of Latin squares related to any autotopism of Latin squares of order up to 7. [Copyright &y& Elsevier]

Abstract: 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 iterations, where 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. [Copyright &y& Elsevier]

Abstract: The problem of finding the global minimum of a so-called Minkowski-norm dominated polynomial can be approached by the matrix method of Stetter and Möller, which reformulates it as a large eigenvalue problem. A drawback of this approach is that the matrix involved is usually very large. However, all that is needed for modern iterative eigenproblem solvers is a routine which computes the action of the matrix on a given vector. This paper focuses on improving the efficiency of computing the action of the matrix on a vector. To avoid building the large matrix one can associate the system of first-order conditions with an system of difference equations. One way to compute the action of the matrix efficiently is by setting up a corresponding shortest path problem and solving it. It turns out that for large the shortest path problem has a high computational complexity, and therefore some heuristic procedures are developed for arriving cheaply at suboptimal paths with acceptable performance. [Copyright &y& Elsevier]

Abstract: One of the main contributions which Volker Weispfenning made to mathematics is related to Gröbner bases theory. In this paper we present an algorithm for computing all algebraic intermediate subfields in a separably generated unirational field extension (which in particular includes the zero characteristic case). One of the main tools is Gröbner bases theory. Our algorithm also requires computing primitive elements and factoring over algebraic extensions. Moreover, the method can be extended to finitely generated -algebras. [Copyright &y& Elsevier]

Abstract: The Hilbert ideal is an ideal generated by invariant polynomials (of strictly positive degree) of a finite group. In this paper, the reduced Gröbner bases and the universal Gröbner bases of Hilbert ideals of alternating groups are studied. [Copyright &y& Elsevier]

Abstract: Seemingly unrelated regressions are statistical regression models based on the Gaussian distribution. They are popular in econometrics but also arise in graphical modeling of multivariate dependencies. In maximum likelihood estimation, the parameters of the model are estimated by maximizing the likelihood function, which maps the parameters to the likelihood of observing the given data. By transforming this optimization problem into a polynomial optimization problem, it was recently shown that the likelihood function of a simple bivariate seemingly unrelated regressions model may have several stationary points. Thus local maxima may complicate maximum likelihood estimation. In this paper, we study several more complicated seemingly unrelated regression models, and show how all stationary points of the likelihood function can be computed using algebraic geometry. [Copyright &y& Elsevier]

Abstract: Let be a field and a finite directed multi-graph. The focus of this paper is to offer a complete description of all path algebras and admissible orders with the property that all of their finitely generated ideals have finite Gröbner bases and of those which contain a finitely generated ideal whose Gröbner bases are all infinite. [Copyright &y& Elsevier]

Abstract: Algebraic function fields of positive characteristic are non-perfect fields, and many standard algorithms for solving some fundamental problems in commutative algebra simply do not work over these fields. This paper presents practical algorithms for the first time for (1) computing the primary decomposition of ideals of polynomial rings defined over such fields and (2) factoring arbitrary multivariate polynomials over such fields. Difficulties involving inseparability and the situation where the transcendence degree is greater than one are completely overcome, while the algorithms avoid explicit construction of any extension of the input base field. As a corollary, the problem of computing the primary decomposition of a positive-dimensional ideal over a finite field is also solved. The algorithms perform very effectively in an implementation within the Magma Computer Algebra System, and an analysis of their practical performance is given. [Copyright &y& Elsevier]