Search

We propose to give an algorithm for computing the $R$-saturation of a finitely-generated submodule of a free module $E$ over a Prüfer domain $R$. To do this, we start with the local case, that is, the case where $R$ is a valuation domain. After that, we consider the global case ($R$ is a Prüfer domain) using the dynamical method. The proposed algorithm is based on an algorithm given by Ducos, Monceur and Yengui in the case $E=R[X]^m$ which is reformulated here in a more general setting in order to reach a wider audience. The last section is devoted to the case where $R$ is a Bézout domain. Particular attention is paid to the case where $R$ is a principal ideal domain ($\mathbb{Z}$ as the main example).

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.

A multiplicative subset of a commutative ring contains the zero element precisely if the set in question meets every prime ideal. While this form of Krull's Lemma takes recourse to transfinite reasoning, it has recently allowed for a crucial reduction to the integral case in Kemper and the third author's novel characterization of the valuative dimension. We present a dynamical solution by which transfinite reasoning can be avoided, and illustrate this constructive method with concrete examples. We further give a combinatorial explanation by relating the Zariski lattice to a certain inductively generated class of finite binary trees. In particular, we make explicit the computational content of Krull's Lemma.

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.

We propose a new version of Noether normalization theorem over Bezout domains of Krull dimension one (the ring Z of integers as main example). We also show that one can avoid branching when computing dynamical Grobner bases over a Bezout domain of Krull dimension one.

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

Recently, Lombardi, Quitte and Yengui have given a Grobner-free algorithm which computes the V-saturation of any finitely generated submodule of V X n , where V is a valuation domain. The goal of this paper is to clarify this algorithm, to give precise complexity bounds, and a complete submodule membership test for the saturation. As application, we give precise degree bounds on syzygies over V X .

In this paper, we address the following question: for a nonzero finitely generated ideal [Formula: see text] of a multivariate polynomial ring [Formula: see text] over a coherent ring [Formula: see text], fixing a monomial order [Formula: see text] on [Formula: see text], is the trailing terms ideal [Formula: see text] of [Formula: see text] (that is, the ideal generated by the trailing terms of the nonzero polynomials in [Formula: see text]) finitely generated? We show that while [Formula: see text] can be nonfinitely generated, it is always countably generated when the monomial order is Noetherian (graded monomial orders as instances).

We give an algorithm for computing the V-saturation of any finitely-generated submodule of V [ X 1 , … , X k ] m ( k ∈ N , m ∈ N ⁎ ), where V is a valuation domain. Our algorithm is based on a notion of “echelon form” which ensures its correctness. The proposed algorithm terminates when two (Hilbert) series on the quotient field and the residue field of V coincide. As application, our algorithm computes syzygies over V [ X 1 , … , X k ] .

Soit V un domaine de valuation. Nous donnons un algorithme pour calculer une base du V-sature d'un sous-module de type fini d'un V-module libre (avec une base eventuellement infinie). Nous l'appliquons pour calculer le V-sature d'un sous-V[X]-module de type fini de V[X] n (n ∈ ℕ*). Ceci permet enfin de calculer un systeme generateur fini pour les syzygies sur V[X] d'une famille finie de vecteurs de V[X] k . We give an algorithm for computing the V-saturation of any finitely generated submodule of V[X] n (n ∈ ℕ*), where V is a valuation domain. This allows us to compute a finite system of generators for the syzygy module of any finitely generated submodule of V[X] k .

We prove that a valuation domain \(\mathbf{V}\) has Krull dimension \(\le \)1 if and only if, for any \(n\), fixing the lexicographic order as monomial order in \(\mathbf{V}[X_1,\ldots ,X_n]\), for every finitely generated ideal \(I\) of \(\mathbf{V}[X_1,\ldots ,X_n]\), the ideal generated by the leading terms of the elements of \(I\) is also finitely generated. This proves the Grobner ring conjecture in the lexicographic order case. The proof we give is both simple and constructive. The same result is valid for Prufer domains. As a “scoop”, contrary to the common idea that Grobner bases can be computed exclusively on Noetherian ground, we prove that computing Grobner bases over \(\mathbf{R}[X_1,\ldots , X_n]\), where \(\mathbf{R}\) is a Prufer domain, has nothing to do with Noetherianity, it is only related to the fact that the Krull dimension of \(\mathbf{R}\) is \(\le \)1.

We construct an example of a finitely generated ideal I of R [ X ] , where R is a one-dimensional domain, whose leading terms ideal is not finitely generated. This gives a negative answer to the open question of whether if R is a domain with Krull dimension ≤1, then for any finitely generated ideal I of R [ X ] , the leading terms ideal of I is also finitely generated. Moreover, as a positive part of our answer, we prove that for any one-dimensional domain R and any a , b ∈ R , the ideal of R [ X ] generated by the leading terms of 〈 1 + a X , b 〉 is finitely generated.

We construct an example of a finitely generated ideal I of V [ X ] , where V is a one-dimensional valuation ring, whose leading terms ideal is not finitely generated. This gives a negative answer to the open question of whether if V is a valuation ring with Krull dimension ⩽1, then for any finitely generated ideal I of V [ X ] , the leading terms ideal of I is also finitely generated. The valuation rings satisfying this latter property will be called 1-Grobner and are studied in this paper.

In this paper, we extend the notion of “dynamical Grobner bases” introduced by the second author to Dedekind rings (with zero divisors). As an application, we dynamically solve the ideal membership problem and compute a generating set for the syzygy module over multivariate polynomial rings with coefficients in Dedekind rings. We also give a partial positive answer to a conjecture about Grobner rings.

We give a constructive proof of the fact that finitely generated projective modules over a polynomial ring with coefficients in a Prufer domain R with Krull dimension ≤ 1 are extended from R. In particular, we obtain constructively that finitely generated projective R[X1, …, Xn ]-modules, where R is a Bezout domain with Krull dimension ≤ 1, are free. Our proof is essentially based on a dynamical method for decreasing the Krull dimension and a constructive rereading of the original proof given by Maroscia and Brewer & Costa. Moreover, we obtain a simple constructive proof of a result due to Lequain and Simis stating that finitely generated modules over R[X1, …, Xn ], n ≥ 2, are extended from R if and only if this holds for n = 1, where R is an arithmetical ring with finite Krull dimension (© 2009 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)

The purpose of the mini-workshop is to bring into the same place different mathematical communities that study constructive homological al- gebra and are motivated by different applications (e.g., constructive algebra, symbolic computation, proof theory, algebraic topology, mathematical sys- tems theory, D-modules, dynamical systems theory) so that they can share their results, techniques, softwares and experiences. Through the develop- ment of a unified terminology, common mathematical problems, which natu- rally appear when making homological algebra constructive, were discussed.

We present a new and simple algorithm for completion of unimodular vectors with entries in a multivariate Laurent polynomial ring R = K [ X 1 ± , … , X k ± ] over an infinite field K . More precisely, given n ⩾ 3 and a unimodular vector V = t ( v 1 , … , v n ) ∈ R n (that is, such that 〈 v 1 , … , v n 〉 = R ), the algorithm computes a matrix M in M n ( R ) whose determinant is a monomial such that M V = t ( 1 , 0 , … , 0 ) , and thus M - 1 is a completion of V to an invertible matrix.

We prove constructively that for any ring R of Krull dimension ⩽1 and n ⩾ 3 , the group E n ( R [ X ] ) acts transitively on Um n ( R [ X ] ) . In particular, we obtain that for any ring R with Krull dimension ⩽1, all finitely generated stably free modules over R [ X ] are free. This settles the long-standing Hermite ring conjecture for rings of Krull dimension ⩽1.

We constructively prove that for any ring R with Krull dimension ⩽d, the ring R〈X〉 locally behaves like the ring R(X) or a localization of a polynomial ring of type (S−1R)[X] with S a multiplicative subset of R such that the Krull dimension of S−1R is ⩽d−1. As an application, we give a simple and constructive proof of the Lequain–Simis Induction Theorem which is an important variation of the Quillen Induction Theorem.

It is folklore (see for example Theorem 7.3.3 in [68]) that if V is a valuation domain, then V[X 1, . . . ,X k ] (k ∈ ℕ) is coherent: that is, syzygy modules of finitely-generated ideals of V[X 1, . . . ,X k ] are finitely-generated. The proof in the above-mentioned reference relies on a profound and difficult result published in a huge paper by Gruson and Raynaud [75]. There is nevertheless no known general algorithm for this remarkable result, and it seems difficult to compute the syzygy module even for small polynomials.

In this paper, we introduce the notion of “dynamical Gröbner bases” of polynomial ideals over a principal ring. As application, we solve dynamically a fundamental algorithmic question in the theory of multivariate polynomials over the integers called “Kronecker's problem,” that is the problem of finding a decision procedure for the ideal membership problem for Z[X1,…,Xn]. The notions of Gröbner bases over Noetherian valuation rings and dynamical Gröbner bases over principal rings have applications in error correcting codes.

A well-known lemma of Suslin says that for a commutative ring A if (v"1(X),...,v"n(X))@?(A[X])^n is unimodular where v"1 is monic and n>=3, then there exist @c"1,...,@c"@?@?E"n"-"1(A[X]) such that the ideal generated by Res(v"1,e"1.@c"1^t(v"2,...,v"n)),...,Res(v"1,e"1.@c"@?^t(v"2,...,v"n)) equals A. This lemma played a central role in the resolution of Serre's Conjecture. In the case where A contains a set E of cardinality greater than degv"1+1 such that y-y^' is invertible for each y y^' in E, we prove that the @c"i can simply correspond to the elementary operations L"1->L"1+y"i@?"j"="2^n^-^1u"j"+"1L"j, 1@?i@?@?=degv"1+1, where u"1v"1+...+u"nv"n=1. These efficient elementary operations enable us to give new and simple algorithms for reducing unimodular rows with entries in K[X"1,...,X"k] to ^t(1,0,...,0) using elementary operations in the case where K is an infinite field. Another feature of this paper is that it shows that the concrete local-global principles can produce competitive complexity bounds.

Gilmer and Heinzer proved that given a reduced ring R, a polynomial f divides a monic polynomial in R[X] if and only if there exists a direct sum decomposition of R = R0 ⊕ … ⊕ Rm (m ≤ deg f), associated to a fundamental system of idempotents e0, … , em, such that the component of f in each Ri[X] has degree coefficient which is a unit of Ri. We propose to give an algorithm to explicitly find such a decomposition. Moreover, we extend this result to divisors of doubly monic Laurent polynomials.

We propose to give positive answers to the open questions: is R(X,Y) strong S when R(X) is strong S? is R stably strong S (resp., universally catenary) when R[X] is strong S (resp., catenary)? in case R is obtained by a (T,I,D) construction. The importance of these results is due to the fact that this type of ring is the principal source of counterexamples. Moreover, we give an answer to the open questions: is R〈X1,…,Xn〉 residually Jaffard (resp., totally Jaffard) when R(X1,…,Xn) is ? We construct a three-dimensional local ring R such that R(X1,…,Xn) is totally Jaffard (and hence, residually Jaffard) whereas R〈X1,…,Xn〉 is not residually Jaffard (and hence, not totally Jaffard).

The purpose of this paper is to find necessary and sufficient conditions for the transfer of the strong S, catenarian, residually Jaffard and totally Jaffard properties between the rings R(1) and R⟨1⟩ for domains R of dimension ≤ 2. Moreover, we give a positive answer to a conjecture of S. Kabbaj in the case of 2-dimensional integrally closed strong S-domains; we prove that if R is a 2-dimensional integrally closed strong S-domain then R[1] is catenarian.

A domainR is called an absolutely S-domain (for short, AS-domain) if each domainT such thatRTqf(R) is an S-domain. We show thatR is an AS-domain if and only if for each valuation overringV ofR and each height one prime idealq ofV , the extensionR/(q \R) �V/q is algebraic. A Noetherian domainR is an AS-domain if and only if dim(R) � 1. In Section 2, we study a class of R-subalgebras of R(X) which share many spectral properties with the polynomial ringR(X) and which we call pseudo-polynomial rings. Section 3 is devoted to an affirmative answer to D. E. Dobbs's question of whether a survival pair must be a lying-over pair in the case of transcendental extension.

We construct two counterexamples to the open questions : is R 〈 n 〉 strong S (resp. catenary) when R ( n ) is ? The first example is a ring R such that R ( n ) is strong S and R 〈 n 〉 is not. The second is a stably strong S -domain R such that for all n ≥1 and n =∞, R ( n ) is catenary and R 〈 n 〉 is not.

We propose to give an answer to two open questions: is R〈X〉 strong S (resp., catenarian) when R(X) is? We construct a ring R such that R(X) is both catenarian and strong S whereas R〈X〉 is neither catenarian nor strong S.

We prove that a valuation domain V has Krull dimension ≤ 1 if and only if for every finitely generated ideal I of V[X] the ideal generated by the leading terms of elements of I is also finitely generated. This proves the Grobner ring conjecture in one variable. The proof we give is both simple and constructive. The same result is valid for semihereditary rings.

We prove that for any finite-dimensional ring R and n > dim R+2, the group E n (R[X]) acts transitively on Um n (R[X]). In particular, we obtain that for any finite-dimensional ring R, all finitely generated stably free modules over R[X] of rank > dim R are free. This result was only known for Noetherian rings. The proof we give is short, simple, and constructive.

We give an algorithm for the well-known result asserting that if R is a polynomial ring in a finite number of variables over a Noetherian ring A of Krull dimension d ∞ , then for n ⩾ max ( 3 , d + 2 ) , SL n ( R ) acts transitively on Um n ( R ) . For technical reasons we demand that the Noetherian ring A has a theory of Grobner bases and contains an infinite set E = { y 1 , y 2 , … } such that y i − y j ∈ A × for each i ≠ j . The most important guiding examples are affine rings K [ x 1 , … , x m ] / I and localizations of polynomial rings S −1 K [ x 1 , … , x m ] , with K an infinite field. Moreover, we give an algorithmic proof of Suslin's stability theorem over these rings. For the purpose to prepare the ground for this algorithmic generalizations of the Quillen–Suslin theorem (corresponding to the particular case A is a field), we will give in the first section a constructive proof of an important lemma of Suslin which is the only nonconstructive step in Suslin's second elementary solution of Serre's conjecture. This lemma says that for a commutative ring A, if 〈 v 1 ( X ) , … , v n ( X ) 〉 = A [ X ] where v 1 is monic and n ⩾ 3 , then there exist γ 1 , … , γ l ∈ E n − 1 ( A [ X ] ) such that 〈 Res ( v 1 , e 1 . γ 1 ( v 2 , … , v n ) ) t , … , Res ( v 1 , e 1 . γ l ( v 2 , … , v n ) ) t 〉 = A . Thanks to this constructive proof, Suslin's second proof of Serre's conjecture becomes fully constructive.

We give a constructive deciphering for a generalization of the Quillen–Suslin theorem due to Maroscia and Brewer & Costa stating that finitely generated projective modules over R[X1,…,Xn], where R is a Prüfer domain with Krull dimension ≤1, are extended from R.