Search

We propose a counterexample to the Grobner ring conjecture in the irrational case. More precisely, we construct a valuation domain V of Krull dimension 1 and a finitely generated ideal J of V [ X , Y ] equipped with some irrational monomial order LT ( J ) generated by the leading terms of the elements of J is not finitely generated.

The methods most commonly used to synthesize the Inverse Kinematic Model (IKM) of open-chain robotic systems strongly depend on the robot’s geometry, which make them difficult to systematize. In a ...

We introduce a new class of polynomial ideals associated to a simple graph, G. Let K [ E G ] be the polynomial ring on the edges of G and K [ V G ] the polynomial ring on the vertices of G. We associate to G an ideal, I ( X G ) , defined as the preimage of ( x i 2 − x j 2 : i , j ∈ V G ) ⊆ K [ V G ] by the map K [ E G ] → K [ V G ] which sends a variable, t e , associated to an edge e = { i , j } , to the product x i x j of the variables associated to its vertices. We show that K [ E G ] / I ( X G ) is a one-dimensional, Cohen–Macaulay, graded ring and we relate its degree with the number of vertices and connected components of the graph. We show that I ( X G ) is a binomial ideal and that, with respect to a fixed monomial order, its initial ideal has a generating set independent of the field K. We focus on the Castelnuovo–Mumford regularity of I ( X G ) providing the following sharp upper and lower bounds: μ ( G ) ≤ reg I ( X G ) ≤ | V G | − b 0 ( G ) + 1 , where μ ( G ) is the maximum vertex join number of the graph and b 0 ( G ) is the number of its connected components. We show that the lower bound is attained for a bipartite graph and use this to derive a new combinatorial result on the number of even length ears of nested ear decomposition.

We present a full list of all representations of the special linear group SLnover the complex numbers with complete intersection invariant ring of homological dimension greater than or equal to two, completing the classification of Shmelkin. For this task, we combine three techniques. Firstly, the graph method for invariants of SLndeveloped by the author to compute invariants, covariants and explicit forms of syzygies. Secondly, a new algorithm for finding a monomial order such that a certain basis of an ideal is a Gröbner basis with respect to this order, in between usual Gröbner basis computation and computation of the Gröbner fan. Lastly, a modification of an algorithm by Xin for MacMahon partition analysis to compute Hilbert series.

International audience; We introduce an improved Gröbner basis completion algorithm for operads. To this end, we define operadic rewriting systems as a machinery to rewrite in operads, whose rewriting rules do not necessarily depend on an ambient monomial order. A Gröbner basis of an operadic ideal can be seen as a confluent and terminating operadic rewriting system; thus, the completion of a Gröbner basis is equivalent to the completion of a rewriting system. We improve the completion algorithm by filtering out redundant S-polynomials and testing only essential ones. Finally, we show how the notion of essential S-polynomials can be used to compute Gröbner bases for syzygy bimodules. This work is motivated by the computation of minimal models of associative algebras and symmetric operads. In this direction, we show how our completion algorithm extends to the case of shuffle operads. CCS Concepts • Computing methodologies → Combinatorial algorithms; Algebraic algorithms.

International audience; We provide constructive versions of Hilbert's syzygy theorem for Z and Z/nZ following Schreyer's method. Moreover, we extend these results to arbitrary coherent strict Bézout rings with a divisibility test for the case of finitely generated modules whose module of leading terms is finitely generated.

Let [math] be the standard graded polynomial ring over a field [math] . We’ll study the Lyubeznik numbers of two homogeneous ideals of [math] whose initial ideals are linked for some monomial order over [math] . We’ll also investigate some relations between Lyubeznik and Betti numbers of homogeneous ideals.

Let R ( h ) denote the polynomial ring in variables x 1 , … , x h over a specified field K. We consider all of these rings simultaneously, and in each use lexicographic (lex) monomial order with x 1 > ⋯ > x h . Given a fixed homogeneous ideal I in R ( h ) , for each d there is unique lex ideal generated in degree at most d whose Hilbert function agrees with the Hilbert function of I up to degree d. When we consider I R ( N ) for N ≥ h , the set B d ( I , N ) of minimal generators for this lex ideal in degree at most d may change, but B d ( I , N ) is constant for all N ≫ 0 . We let B d ( I ) denote the set of generators one obtains for all N ≫ 0 , and we let b d = b d ( I ) be its cardinality. The sequences b 1 , … , b d , … obtained in this way may grow very fast. Remarkably, even when I = ( x 1 2 , x 2 2 ) , one obtains a very interesting sequence, 0 , 2 , 3 , 4 , 6 , 12 , 924 , 409620 , … . This sequence is the same as H d − 1 + 1 for d ≥ 2 , where H d is the dth Hamilton number. The Hamilton numbers were studied by Hamilton and by Hammond and Sylvester because of their occurrence in a counting problem connected with the use of Tschirnhaus transformations in manipulating polynomial equations.

The aim of this chapter is to provide a summary of the theory of linear rewriting and the application of this theory to the construction of free resolutions for associative algebras. In Sect. 2, we present linear polygraphs as an algebraic setting for linear rewriting without a monomial order, and we review the fundamental notion of linear polygraphs. In Sect. 3, we recall several historical constructions on linear rewriting systems for associative algebras, and we show how the confluence properties are studied in these different approaches. We relate the notion of convergent linear polygraph with the notion of noncommutative Grobner basis. In Sect. 4, we describe an algorithmic way to compute free resolutions for algebras using a method introduced by Anick. Section 5 deals with extension of linear polygraphs, seen as higher dimensional linear rewriting systems, into polygraphic resolutions for algebras. We show how to construct such a resolution starting from a convergent presentation. In the last section, we show how to relate Koszulness for algebras with the property of confluence.

Given an arbitrary integer \(d>0\), we construct a homogeneous ideal I of the polynomial ring \(S = K[x_1, \ldots , x_{3d}]\) in 3d variables over a field K for which S/I is a Cohen–Macaulay ring of dimension d with the property that, for each of the integers \(0 \le r \le d\), there exists a monomial order \(

Commutative and non commutative Grobner–Shirshov bases were first studied over fields and after extended to some particular rings. In theses works, the monomials are in a monoid. Recently, Bokut and al. gave a new extension of Grobner–Shirshov bases over a field by choosing the monomials in a semi-ring rather in a monoid. In this paper, we study Grobner–Shirshov bases where the monomials are in a semi-ring and the coefficients are in a noetherian valuation ring and we establish the relation between weak and strong Grobner bases.

We present an algorithm to decide whether a given ideal in the polynomial ring contains a monomial without using Gr\"obner bases, factorization or sub-resultant computations., Comment: 15 pages

A set system F ⊆ 2 [ n ] shatters a given set S ⊆ [ n ] if 2 S = { F ∩ S : F ∈ F } . The Sauer-Shelah lemma states that in general, F shatters at least | F | sets. A set sytstem is called shattering-extremal if it shatters exactly | F | sets. In [Meszaros, T., “S-extremal set systems and Grobner bases”, Diploma Thesis, Budapest University of Technology and Economics, 2010] and [Meszaros, T., L. Ronyai, “Some combinatorial application of Grobner bases”, In: F. Winkler, Algebraic Informatics, CAI 2011, Lecture Notes in Computer Science 6742, Springer 2011, 64–83] an algebraic characterization of shattering-extremal set systems was given, which offered the possibility to generalize the notion of extremality to general finite vector systems. Here we generalize the results obtained for set systems to this more general setting, and as an application, strengthen a result of Dong, Li and Zhang from [Dong, T., Z. Li, S. Zhang, Finite sets of affine points with unique associated monomial order quotient bases, Journal of Algebra and its Applications 11(2) (2012), 1250025].

We study holomorphic foliations on $$\mathbb {CP}^2$$ of degree d with a singular point with Milnor number $$d^2+d+1$$ and non-zero linear part. Given a foliation, using the singular scheme of the foliation and the lexicographical monomial order, we give necessary and sufficient conditions to have this kind of singularities. We show that if the singularity is nilpotent, the Grobner basis with respect to this order gives us the normal form around the singular point. Finally, we prove that these foliations have no invariant lines and we exhibit a family of foliations with a nilpotent singularity with Milnor number $$d^2+d+1$$ , for d odd.

We consider the computation of syzygies of multivariate polynomials in a finite-dimensional setting: for a $\mathbb{K}[X_1,\dots,X_r]$-module $\mathcal{M}$ of finite dimension $D$ as a $\mathbb{K}$-vector space, and given elements $f_1,\dots,f_m$ in $\mathcal{M}$, the problem is to compute syzygies between the $f_i$'s, that is, polynomials $(p_1,\dots,p_m)$ in $\mathbb{K}[X_1,\dots,X_r]^m$ such that $p_1 f_1 + \dots + p_m f_m = 0$ in $\mathcal{M}$. Assuming that the multiplication matrices of the $r$ variables with respect to some basis of $\mathcal{M}$ are known, we give an algorithm which computes the reduced Gr\"obner basis of the module of these syzygies, for any monomial order, using $O(m D^{\omega-1} + r D^\omega \log(D))$ operations in the base field $\mathbb{K}$, where $\omega$ is the exponent of matrix multiplication. Furthermore, assuming that $\mathcal{M}$ is itself given as $\mathcal{M} = \mathbb{K}[X_1,\dots,X_r]^n/\mathcal{N}$, under some assumptions on $\mathcal{N}$ we show that these multiplication matrices can be computed from a Gr\"obner basis of $\mathcal{N}$ within the same complexity bound. In particular, taking $n=1$, $m=1$ and $f_1=1$ in $\mathcal{M}$, this yields a change of monomial order algorithm along the lines of the FGLM algorithm with a complexity bound which is sub-cubic in $D$., Comment: 34 pages, 7 algorithms, Journal of Complexity

The main result from this note provides a constructive characterization of the valuative dimension, which bears a strong analogy to Lombardi's constructive characterization of the Krull dimension. While Lombardi's characterization uses the lexicographic monomial order, ours uses the graded (reverse) lexicographic order or, in fact, any graded rational monomial order. Apart from this, the paper contains some related results and some examples which readers may find illuminating., 7 pages

In the last decade, the approximate vanishing ideal and its basis construction algorithms have been extensively studied in computer algebra and machine learning as a general model to reconstruct the algebraic variety on which noisy data approximately lie. In particular, the basis construction algorithms developed in machine learning are widely used in applications across many fields because of their monomial-order-free property; however, they lose many of the theoretical properties of computer-algebraic algorithms. In this paper, we propose general methods that equip monomial-order-free algorithms with several advantageous theoretical properties. Specifically, we exploit the gradient to (i) sidestep the spurious vanishing problem in polynomial time to remove symbolically trivial redundant bases, (ii) achieve consistent output with respect to the translation and scaling of input, and (iii) remove nontrivially redundant bases. The proposed methods work in a fully numerical manner, whereas existing algorithms require the awkward monomial order or exponentially costly (and mostly symbolic) computation to realize properties (i) and (iii). To our knowledge, property (ii) has not been achieved by any existing basis construction algorithm of the approximate vanishing ideal., Comment: 9+10 pages, 1+4 figures, AAAI'20

Let $\mathbb{N}^{d}$ be the $d$-dimensional monoid of non-negative integers. A generalized numerical semigroup is a submonoid $ S\subseteq \mathbb{N}^d$ such that $H(S)=\mathbb{N}^d \setminus S$ is a finite set. We introduce irreducible generalized numerical semigroups and characterize them in terms of the cardinality of a special subset of $H(S)$. In particular, we describe relaxed monomial orders on $\mathbb N^d$, define the Frobenius element of $S$ with respect to a given relaxed monomial order, and show that the Frobenius element of $S$ is independent of the order if the generalized numerical semigroup is irreducible., Comment: 15 pages

El objetivo de esta memoria es introducir al lector a la Teor´ıa de Semigrupos Num´ericos y de Bases de Gr¨obner, mostrando alguna interacci´on entre ellas. En primer lugar estudiamos la estructura de semigrupo num´erico. Demostramos que todo semigrupo num´erico est´a finitamente generado y tiene un ´unico sistema minimal de generadores. Tambi´en estudiamos diversos conjuntos notables asociados como el conjunto de Ap´ery y el de huecos. En el segundo cap´ıtulo estudiamos la teor´ıa cl´asica de Bases de Gr¨obner. Comenzamos introduciendo un orden monomial en el anillo de polinomios sobre un cuerpo, lo que nos permite descubrir un algoritmo de divisi´on que generaliza la divisi´on eucl´ıdea y, haciendo uso del mismo, hallar sistemas generadores de ideales con propiedades deseables. Finalmente, afrontamos dos problemas de la Teor´ıa de Semigrupos: el de pertenencia a un semigrupo y el de obtenci´on del conjunto de Ap´ery, ambos empleando las herramientas que brindan las bases de Gr¨obner. This manuscript aims to introduce the reader to both Numerical Semigroups and Gr¨obner Bases theories, showing some interactions between them. In the first chapter, we study the structure of numerical semigroup. We prove that every numerical semigroup is finitely generated and has a unique minimal set of generators. We also study several relevant sets associated to the semigroup as the Ap´ery set and the set of gaps. In the second chapter, we study classical Gr¨obner Bases theory defining a monomial order in the polynomial ring over a field. We describe a division algorithm which allows us to generalise the Euclidean division and we use this tool to find generating systems for ideals with reasonably good properties. Finally, we approach two problems of Numerical Semigroups theory: the semigroup membership problem and the computation of the Ap´ery set, both of them applying tools given by Gr¨obner bases.

In this work we consider the computation of Grobner bases of the steady state ideal of reaction networks equipped with mass-action kinetics. Specifically, we focus on the role of intermediate species and the relation between the extended network (with intermediate species) and the core network (without intermediate species). We show that a Grobner basis of the steady state ideal of the core network always lifts to a Grobner basis of the steady state ideal of the extended network by means of linear algebra, with a suitable choice of monomial order. As illustrated with examples, this contributes to a substantial reduction of the computation time, due mainly to the reduction in the number of variables and polynomials. We further show that if the steady state ideal of the core network is binomial, then so is the case for the extended network, as long as an extra condition is fulfilled. For standard networks, this extra condition can be visually explored from the network structure alone.

Bayer-Stillman showed that $reg(I) = reg(gin_\tau(I))$ when $\tau$ is the graded reverse lexicographic order. We show that the reverse lexicographic order is the unique monomial order $\tau$ satisfying $reg(I) = reg(gin_\tau(I))$ for all ideals $I$. We also show that if $gin_{\tau_1}(I) = gin_{\tau_2}(I)$ for all $I$, then $\tau_1 = \tau_2$., Comment: 10 pages

In this paper taking a question in [1] into background we investigate the uniqueness of a non-constant polynomial with the differential monomial generated by a non-constant mermorphic function f. Our result will also extend a result of Banerjee-Majumder[2] given earlier. An open question is also posed, in the paper, for future investigation.