On the degrees of bases of free modules over a polynomial ring

Marcela Almeida^{∗} Lisi D’Alfonso^{∗}

Departamento de Matemática. Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires. -1428- Buenos Aires. ARGENTINA.

                    malmeida@dm.uba.ar          lisi@dm.uba.ar

Pablo Solernó^{∗}

Departamento de Economía y Matemática. Universidad de San Andrés. Vito Dumas 284. -1644- Victoria, Buenos Aires. ARGENTINA.

                                psolerno@dm.uba.ar

Fax : 54-1-746-50-90

May 28, 1997

Abstract. Let k be an infinite field, A the polynomial ring k[x_{1}, ..., x_{n}] and F ∈ A^{N×M} a matrix such that Im F ⊂ A^{N} is A -free (in particular, Quillen-Suslin Theorem implies that Ker F is also free). Let D be the maximum of the degrees of the entries of F and s the rank of F . We show that there exists a basis {v_{1}, …, v_{M}} of A^{M} such that {v_{1}, …, v_{M−s}} is a basis of Ker F , {F (v_{M−s+1}), …, F (v_{M})} is a basis of Im F and the degrees of their coordinates are of order ((M − s)sD)^{O(n^{4})} . This result allows to obtain a single exponential degree upper bound for a basis of the coordinate ring of a reduced complete intersection variety in Noether position.

Keywords. Linear equation systems over polynomial rings. Quillen-Suslin Theorem. Effective Nullstellensatz. Complete intersection polynomial ideals. Duality theory in Gorenstein Rings.

∗Partially supported by UBACYT and PID-CONICET.

1 Introduction

This article deals with the computation of the solutions of linear equation systems over a polynomial ring. After the seminal paper by E.Mayr and A.Meyer [20], it is well known the constraints of linear algebra methods as a tool in effective commutative algebra. In particular, Mayr-Meyer’s monoid leads to an intrinsic hyperexponential growth of the degrees of the syzygies. In terms of linear equation systems this fact can be restated saying that there exist families of polynomial matrices such that every system of generators of their kernels contains a vector with at least one coordinate of double exponential degree. More precisely, in [7, Corollaire, pag.10] the following result is shown : Let ε > 0 . Let n and D be integers such that n ≥ 10 , D ≥ 3 , D ≥ 2 + \frac{1}{32ε} . There exists a polynomial sequence P_{1}, …, P_{n} of degree bounded by D in A := k[x_{1}, …, x_{n}] (where P_{1} := x_{1} , P_{2} := x_{2} ) such that any system of generators of the A -submodule of A^{n} consisting of all the sequences U_{i} with ∑_{i} U_{i}P_{i} = 0 , contains at least one vector whose first coordinate has degree ≥ N , where log_{2} log_{2} N > (\frac{1}{8} − ε)n + log_{2} log_{2} D − \frac{9}{4}.

However, under certain additional hypothesis on the matrix associated to the linear system, more precise estimations can be done. For example, if the matrix is unimodular (i.e. the rows can be extended to a basis of the whole space), a single exponential upper bound for the degree of a basis of its kernel is given in [5, Corollary 3.2]. In the present paper we treat the more general case where the columns of the matrix generate a free A -module (in particular, Quillen-Suslin Theorem assures that the kernel is also free). In this case it is not too difficult to show a polynomial upper bound for the degree of a system of generators of the kernel (see [2, Corollary 10] or Lemma 1 below). Nevertheless our purpose here is to find bases of low degree for the kernel and the image.

More precisely, let k be an infinite field, A := k[x_{1}, ..., x_{n}] be the polynomial ring in the indeterminates x_{1}, …, x_{n} and F ∈ A^{N×M} be a matrix such that Im F is A -free. Denote by D the maximum of the degrees of the entries of F and by s the rank of F . Therefore we have (see Theorem 19 below) :

Theorem There exists a basis {v_{1}, …, v_{M}} of A^{M} such that :

• {v_{1}, …, v_{M−s}} is a basis of Ker F ;

• the coordinates of the vectors v_{j} have degrees of order ((M − s)sD)^{O(n^{3})} for j = 1, …, M − s.

• {F (v_{M−s+1}), …, F (v_{M})} is a basis of Im F .

• the coordinates of the vectors v_{j} have degrees of order ((M − s)sD)^{O(n^{4})} for j = M − s + 1, …, M .

Under suitable stronger conditions (for instance, if F corresponds to the matrix of a linear projection) the degree upper bounds of the Theorem can be slightly improved (see Section 6).

The methods we use in order to prove the main theorem (developed in Sections 2 to 5) are strongly inspired on the works of D.Quillen, A.Suslin, L.Vaserstein and M.Hochster related to the resolution of the so called “Serre’s Conjecture” (on this subject let us mention the remarkable books of T.Y.Lam [17] and E.Kunz [15]). We combine this approach with the effective version of Hilbert Nullstellensatz (see [13], [9] and the references given in [3] and [23]) and its consequences in the quantitative study of polynomial unimodular matrices following [5]. Other approaches on effective Quillen-Suslin Theorem may be found in [18] and [19].

The last section is devoted to an application of the mentioned theorem in the frame of effective commutative algebra : let k be an infinite field and f_{1}, …, f_{n−r} be a regular sequence in k[x_{1}, …, x_{n}] of degrees bounded by an integer d. Suppose that the variables x_{1}, …, x_{n} are in Noether position with respect to the polynomials f_{i} (i.e. the natural map k[x_{1}, …, x_{r}] → k[x_{1}, …, x_{n}]/(f_{1}, …, f_{n−r}) is an injective and integral morphism). Write R := k[x_{1}, …, x_{r}] and S := k[x_{1}, …, x_{n}]/(f_{1}, …, f_{n−r}) . It is well known (see for example [8, Corollary 18.17] or [12, Lemma 3.3.1]) that, under these conditions, S is a locally free R -module of finite rank (bounded by d^{n−r} following Bezout’s Inequality) and hence free (Quillen-Suslin Theorem). This situation appears frequently in problems related to effective elimination theory (see [21], [12], [6], [1], [14], [11]). In this context it is natural to ask about quantitative properties of bases of the module S. To our knowledge the only significative result for this problem deals with the homogeneous case, where a basis whose coordinates have single exponential degree is obtained with the aid of elementary properties of Gröbner bases. In this sense we obtain the following result (see Theorem 27 below) :

Theorem Suppose that S is a reduced ring. Then, there exist a basis of S over R formed by polynomials of degrees of order d^{O((n−r)r^{4}))} .

The proof of this theorem combines the previous results of linear algebra over the polynomial ring with consequences of Gorenstein duality theory.

The methods of the proofs of both theorems are explicit and they can be easily transformed into algorithmic procedures; however their complexity bounds are too bad, even for theoretical purposes. Therefore the problem of how to find single exponential algorithms remains open.

Aknowledgements: The third author (P.S.) thanks the Laboratoire GAGE, Ecole Polytechnique, Palaiseau, specially Prof. Marc Giusti, for its hospitality during the winter season 96-97.

2 A system of generators for the kernel of F

Let k be an infinite field, A := k[x_{1}, ..., x_{n}] and F ∈ A^{N×M} a matrix verifying that Im F is a free A -module. In this case, Quillen-Suslin Theorem (see for instance [15, Ch.IV, Th.3.15.]) implies that Ker F is also free. Denote by D the maximum of the degrees of the entries of F and by s the rank of F . The columns of F will be denoted by C_{1}, …, C_{M} .

With these notations we are able to estimate a system of generators of Ker F of low degree (see also [2, Corollary 10]) :

Lemma 1 The kernel of the matrix F can be generated as an A -module by 3(M − s)(sD)^{n} polynomial vectors with degrees bounded by sD.

Proof.- Since s = rkF there exists at least one non zero s × s minor; without loss of generality, let us suppose that the first s × s principal minor δ is non zero (in particular, the first s columns are linearly independent). Therefore, by Cramer’s rule, we have for i = 1, ..., M − s:

δ C_{s+i} = b_{1i}C_{1} + ⋯ + b_{si}C_{s} ,  (1)

where b_{ji} are polynomials in A uniquely determined, whose degrees are bounded by sD. Dividing relation (1) by the GCD of b_{1i}, …, b_{si}, δ we obtain new relations

δ_{i} C_{s+i} = b′_{1i}C_{1} + ⋯ + b′_{si}C_{s}.  (2)

Clearly, the vectors

w_{i} := (b′_{1i}, …, b′_{si}, 0, …, −δ_{i}, …, 0),

where −δ_{i} occurs in the coordinate s + i, belong to Ker F . Repeating this construction for all the s × s non zero minors of F , we get a family of vectors lying in the kernel. We claim that this family generates Ker F . For this it is enough to show that for any maximal ideal M ⊂ A these vectors span the kernel of the corresponding localized application F : A_{M}^{M} → A_{M}^{N}. Clearly, the columns C_{1}, …, C_{M} generate Im F_{M}; by Nakayama’s Lemma, since Im F_{M}/MIm F_{M} is a s -dimensional vector space, we deduce that there exists a basis of Im F_{M} consisting of s suitable columns of the matrix F . Without loss of generality, we may suppose that C_{1}, …, C_{s} is an A_{M} -basis of Im F_{M} and therefore, there exist p_{1i}, …, p_{si} ∈ A and q_{i} ∈ A \ M, such that

q_{i}C_{s+i} = p_{1i}C_{1} + … + p_{si}C_{s},  (3)

for i = 1, …, M − s. We now show that no δ_{i} in (2) belongs to M : suppose on the contrary that δ_{j} ∈ M, from the relations (2) and (3) we deduce :

q_{j}b′_{kj} = p_{kj}δ_{j}

for k = 1, …, M − s. In particular, since q_{j} ∉ M, all the irreducible factors of δ_{j} which belong to M are also factors of all the b′_{kj} ’s. This contradicts the coprimality of b′_{1j}, …, b′_{sj}, δ_{j}. We finish the claim remarking that the vectors w_{i} are an A_{M} -basis of Ker F_{M} because they are a basis of the vector space Ker F_{M}/MKer F_{M} (they are M − s linearly independent vectors).

In order to shrink the obtained system of generators, for every non zero minor δ we modify slightly the vectors w_{i} in the following way: let g_{δ} := mcm(δ_{1}, …, δ_{M−s}) and set

w̃_{i} := \frac{g_{δ}}{δ_{i}} w_{i}.

Let us observe that:

• w̃_{i} ∈ A^{M} .

• The coordinates of w̃_{i} have degrees bounded by sD (observe that g_{δ} divides δ).

• If δ_{i} ∉ M for i = 1, … M − s, then g_{δ} ∉ M. In particular the vectors w̃_{i} are a system of generators of Ker F_{M} and the ideal generated by the polynomials g_{δ} is A.

• If δ runs over all the non zero s × s minors, the corresponding vectors w̃_{i} generate Ker F .

Since g_{δ} divides δ, the degrees of the polynomials g_{δ} are bounded by sD and then they

span a k vector space of dimension smaller than ( \begin{matrix}n + sD \\ sD \end{matrix} ) ≤ e(sD)^{n}.

Fix a maximal k -linearly independent family of g_{δ} ’s; for each one of these g_{δ} ’s consider the M − s vectors associated to it. The collection of all these vectors is also a system of generators of Ker F .

3 A free k[x_{1}, …, x_{n−1}]-module related to Im F

From now on we write B for the polynomial ring k[x_{1}, …, x_{n−1}] .

Since Im F is a free A -module of rank s > 0 , there is a non zero s × s minor of F ; after a linear change of coordinates, we may assume that the first s × s principal minor, μ, is monic with respect to each variable x_{1}, …, x_{n}.

Remark 2 Under this assumption the image of the matrix F (0) ∈ B^{N×M} , obtained by replacing x_{n} by 0 in F , is B -free. Moreover, let h_{1}, …, h_{s} ∈ A^{N} be a basis of Im F and w_{1}, …, w_{t} ∈ A^{M} be the system of generators of Ker F constructed in Lemma 1. Then the corresponding vectors h_{1}(0), …, h_{s}(0) and w_{1}(0), …, w_{t}(0) are a B -basis of Im F (0) and a B -system of generators of Ker F (0) respectively. In fact, let v ∈ Im F (0) and v′ ∈ B^{M} be such that F (0)(v′) = v; since F (v′) is an A -linear combination of the vectors h_{1}, …, h_{s}, replacing x_{n} by 0 , one deduces that v is a B -linear combination of the vectors h_{j}(0) ’s. The assumption about the s × s minor μ implies that the rank of Im F (0) over the fraction field of B is also s. Therefore h_{1}(0), …, h_{s}(0) are B -linearly independent. In a similar way the assertion about the generators of Ker F (0) follows.

Let L be the free submodule of A^{N} generated by the first s columns C_{1}, …, C_{s}. Consider the exact sequence

0 → L → Im F → Q → 0  (4)

where Q := Im F/L.

Clearly, Q is generated by the images of the columns C_{s+1}, …, C_{M} and then μQ = 0 (due to the relations (1) for δ = μ). We write d := deg_{x_{n}} μ − 1 (note that d ≤ sD − 1 ). Since μ is monic in x_{n}, Q admits a natural B -module structure of finite type generated by the images of the elements x_{n}^{j}C_{i} with j = 0, …, d and i = s + 1, …, M .

Proposition 3 The B -module Q is free of finite rank.

Proof.- Let ℘ ⊂ B be a maximal ideal; tensoring the exact sequence (4) (as a sequence of B -modules) by B/℘, we claim that the sequence of B/℘ -vector spaces

0 → L/℘L → Im F/℘Im F → Q/℘Q → 0  (5)

is exact. To prove our claim it is enough to show that the injection L ↪ Im F is preserved after tensoring. In fact, let w := α_{1}C_{1} + ⋯ + α_{s}C_{s} be an element in L ∩ ℘Im F . Then w may be written as a linear combination of the columns C_{1}, …, C_{M} with coefficients in ℘A. Then we have :

α_{1}C_{1} + ⋯ + α_{s}C_{s} = w = β_{1}C_{1} + ⋯ + β_{M}C_{M}

with α_{j} ∈ A and β_{i} ∈ ℘A. Multiplying this equality by μ and using (1) we deduce the relations :

μα_{j} = μβ_{j} + ∑_{i=1}^{M−s} β_{s+i}b_{ji}

for j = 1, ..., s. Regarding this formula as a polynomial identity in B[x_{n}] and comparing coefficients (recall μ is monic) we observe that the α_{j} ’s belong to ℘A and then w ∈ ℘L, i.e. w = 0 in L/℘L. From the exactness of (5) we deduce that Q is a locally projective B -module and then projective (see [15, Ch.IV, Prop.3.4]). Therefore it is a free B -module of finite type, by Quillen-Suslin.

Definition 4 For k = 0, …, d and i = s + 1, …, M , let \overline{x_{n}^{k}C_{i}} be the canonical system of generators of Q over B, and let m := (d + 1)(M − s) . Let e_{0,s+1}, e_{1,s+1}, …, e_{d,s+1}, …, e_{d,M} be the canonical basis of B^{m}. Therefore, we have a surjective map φ : B^{m} → Q, defined as φ(e_{ki}) := \overline{x_{n}^{k}C_{i}} (observe that Ker φ is B -free).

We are interested now in the computation of a system of generators for Ker φ of low degree.

Let w_{1}, …, w_{t} be a system of generators of Ker F as in Lemma 1 (in particular, t ≤ e(M −s)(sD)^{n}). Since μ is monic in x_{n}, we can compute the euclidean division in B[x_{n}] for each coordinate, and we write :

w_{j} = μq_{j} + r_{j}  (6)

where q_{j} and r_{j} are in A^{M} and the degree in x_{n} of each coordinate of r_{j} is bounded by d, meanwhile, the total degree is bounded by (sD)^{2} .

For each x_{n}^{k}r_{j} ∈ A^{M} with j = 1, …, t and k = 0, …, d, we compute again the euclidean division :

x_{n}^{k}r_{j} = μq_{kj} + r_{kj}  (7)

where r_{kj} ∈ A^{M} , deg r_{kj} = 2(sD)^{3} and deg_{x_{n}} r_{kj} ≤ d.

For each vector r_{kj}, we consider the vector V_{kj} consisting of the M − s last coordinates. We replace the multi-index kj by h = 1, …, t(d + 1) . For each h, V_{h} can be decomposed :

V_{h} = V_{h,0} + x_{n}V_{h,1} + ⋯ + x_{n}^{d}V_{h,d}

and each V_{h,k}, being a vector in B^{M−s}, can be written

V_{h,k} = (V_{h,k,s+1}, …, V_{h,k,M}).

Proposition 5 The vectors (V_{h,0,s+1}, V_{h,1,s+1}, …, V_{h,d,s+1}, …, V_{h,d,M}) ∈ B^{(d+1)(M−s)} , with h = 1, …, t(d + 1) , are a system of generators of Ker φ.

Proof.- First, we show that these vectors belong to Ker φ. Applying the definition of φ, we have

φ(V_{h,0,s+1}, V_{h,1,s+1}, …, V_{h,d,s+1}, …, V_{h,d,M}) = ∑_{i,k} V_{h,k,i}\overline{x_{n}^{k}C_{i}} = ∑_{i=s+1}^{N} Q_{h,i}\overline{C_{i}}.

with Q_{h,i} := ∑_{k} V_{h,k,i}x_{n}^{k}. It suffices to show that ∑_{i=s+1}^{M} Q_{h,i}C_{i} ∈ L. With the notations above; V_{h} = (Q_{h,s+1}, …, Q_{h,M}) , and then, reversing the euclidean divisions (7) and (6), there exist P_{1}, …, P_{s} ∈ A such that :

(P_{1}, …, P_{s}, Q_{h,s+1}, …, Q_{h,M}) = x_{n}^{k}w + μr

where k ∈ IN , w ∈ Ker F and r ∈ A^{M} . Multiplying this identity by the “column vector” (C_{1}, …, C_{M}) we obtain :

∑_{i=1}^{s} P_{i}C_{i} + ∑_{i=s+1}^{M} Q_{h,i}C_{i} = μ ∑_{i=1}^{M} r_{i}C_{i},

because w ∈ Ker F .

Since μC_{i} ∈ L for all i = 1, …, M , we deduce that ∑_{i} Q_{h,i}C_{i} ∈ L, and so, the vectors are in Ker φ.

Now, we will show that they are a system of generators of Ker φ. Let (q_{0,s+1}, q_{1,s+1}, …, q_{d,M}) be an element in Ker φ ⊂ B^{(d+1)(M−s)} ; that is to say

q_{0,s+1}C_{s+1} + q_{1,s+1}x_{n}C_{s+1} + … + q_{d,M}x_{n}^{d}C_{M} ∈ L.

Writing Q_{i} := ∑_{k} q_{k,i}x_{n}^{k}, we know that there exist P_{1}, …, P_{s} ∈ A such that

Q_{s+1}C_{s+1} + ⋯ + Q_{M}C_{M} = P_{1}C_{1} + ⋯ + P_{s}C_{s}.

This means that the vector (−P_{1}, …, −P_{s}, Q_{s+1}, …, Q_{M}) ∈ A^{M} belong to Ker F , and then, if {w_{1}, …, w_{t}} is the system of generators of Ker F constructed in Lemma 1, there exist α_{1}, … α_{t} ∈ A such that

(−P_{1}, …, −P_{s}, Q_{s+1}, …, Q_{N}) = ∑ α_{j}w_{j}.

Dividing the α_{j} ’s and w_{j} ’s by μ, we can write, for a certain w ∈ A^{M}

(−P_{1}, …, −P_{s}, Q_{s+1}, …, Q_{M}) = μw + ∑ β_{j}r_{j}

where deg_{x_{n}} β_{j} ≤ d and r_{j} are the ones defined in (6). Repeating the division (7) we obtain

(−P_{1}, …, −P_{s}, Q_{s+1}, …, Q_{M}) = μw′ + ∑ β_{kj}r_{kj}

with β_{kj} ∈ B (see (7)). Comparing the last M − s coordinates, and simplifying the notation, we have

(Q_{s+1}, …, Q_{M}) = μv + ∑ β_{h}V_{h}

for a certain v ∈ A^{M−s}. Since β_{h} ∈ B for all index h, and since deg_{x_{n}} Q_{i} and deg_{x_{n}} V_{h} are strictly lower than deg_{x_{n}} μ, we obtain that v is zero from the uniqueness of the euclidean algorithm in B[x_{n}] . Then

(Q_{s+1}, …, Q_{M}) ∈ BV_{1} + ⋯ + BV_{t(d+1)}.

The proof finishes developing this identity in powers of x_{n}.

With the notations above, we observe that t ≤ e(M − s)(sD)^{n}, d ≤ sD and deg V_{h} = 2(sD)^{3} , and then we have the following result:

Lemma 6 There exists a matrix G ∈ B^{m×p}, where m := (M −s)(d+1) , p := t(d+1) ≤ e(M − s)(sD)^{n+1} and deg G = 2(sD)^{3} , such that Im G = Ker φ.

Proof.- Take G as the matrix whose columns are the vectors (V_{h,0,s+1}, V_{h,1,s+1}, …, V_{h,d,s+1}, …, V_{h,d,M}) , h = 1, …, p.

Observe that m ≤ p since M − s = rk (Ker F) ≤ t.

4 Another local presentation for Im F

This section is devoted to exhibit a presentation of Im F under a suitable localization in an element of the ring B (Lemma 14 below).

Let G ∈ B^{m×p} be the matrix from Lemma 6 and let q ≤ m be the rank of the B -module Ker φ (which is free because Q is free and B is a polynomial ring). The q × q minors of G generate the ring B (since Im G = Ker φ is a direct summand of B^{m}) and their degrees are bounded by 2q(sD)^{3} (therefore by 2(M − s)(sD)^{4} ). Let ξ be a non zero q × q minor. Without loss of generality we may suppose that ξ involves the first q columns of G that we will denote by K_{1}, …, K_{q}.

For the m − q rows not used in the construction of the minor ξ, let e_{k_{1},i_{1}}, …, e_{k_{m−q},i_{m−q}} be the corresponding m − q vectors of the canonical basis of B^{m} (see Definition 4). For the sake of simplicity we will denote e_{k_{j},i_{j}} by u_{j}, j = 1, …, m − q. Clearly K_{1}, …, K_{q}, u_{1}, …, u_{m−q} are a basis of B_{ξ}^{m} since the determinant of the corresponding m × m matrix Z is ±ξ. Then we have

Proposition 7 The vectors φ(e_{k_{j},i_{j}}) = \overline{x_{n}^{k_{j}}C_{i_{j}}} , j = 1, …, m − q, are a basis of the B_{ξ} -module Q_{ξ}.

Meanwhile consider the vectors x_{n}^{k_{1}}C_{i_{1}}, …, x_{n}^{k_{m−q}}C_{i_{m−q}}, C_{1}, …, C_{s}. From Proposition 7 and the definition of the B -module Q (see (4)), for each index ℓ, ℓ = 1, …, m−q, there exist unique β̃_{1}^{(ℓ)}, …, β̃_{m−q}^{(ℓ)} ∈ B_{ξ} and α̃_{1}^{(ℓ)}, …, α̃_{s}^{(ℓ)} ∈ A_{ξ} such that

−x_{n} x_{n}^{k_{ℓ}}C_{i_{ℓ}} = ∑_{j=1}^{m−q} β̃_{j}^{(ℓ)} x_{n}^{k_{j}}C_{i_{j}} + ∑_{i=1}^{s} α̃_{i}^{(ℓ)}C_{i}.  (8)

We will analize this relations more deeply.

First assume k_{ℓ} < d : then −\overline{x_{n}^{1+k_{ℓ}}C_{i_{ℓ}}} = −φ(e) for a certain vector e of the canonical basis of B^{m} (see Definition 4). On the other hand we can write in B_{ξ}^{m} :

−e = λ_{1}K_{1} + ⋯ + λ_{q}K_{q} + λ_{q+1}u_{1} + ⋯ + λ_{m}u_{m−q}  (9)

for certain (λ_{1}, …, λ_{m}) ∈ B_{ξ}^{m}. Hence, applying φ we have

−φ(e) = −\overline{x_{n}^{1+k_{ℓ}}C_{i_{ℓ}}} = −x_{n}φ(u_{ℓ}) = ∑_{j=1}^{m−q} λ_{q+j}φ(u_{j})

(recall that φ(K_{l}) = 0 for all l). Therefore in (8) we can take β̃_{j}^{(ℓ)} := λ_{q+j}, for all j. In order to estimate the degree of λ_{q+j} we consider the product of (9) by the matrix Z^{−1} :

−Z^{−1} e = ( λ_{1} ; ⋮ ; λ_{m} ) .

In particular, the λ_{q+j} ’s are the last m − q entries of a column of the matrix −Z^{−1} . Since Z belongs to B^{m×m} and det(Z) = ±ξ we can write

β̃_{j}^{(ℓ)} = \frac{β_{j}^{(ℓ)}}{ξ}  (10)

where, by Cramer’s rule, the β_{j}^{(ℓ)} ’s are polynomials in B whose degrees are bounded by (m − 1)2(sD)^{3} ≤ 2m(sD)^{3} . For the case k_{ℓ} = d, instead of −x_{n}^{1+k_{ℓ}}C_{i_{ℓ}}, we write (x_{n}^{d+1} − μ)C_{i_{ℓ}} and the argument runs similarly. Here the upper bound for the polynomials β_{j}^{(ℓ)} is 2(m − 1)(sD)^{3} + (sD) ≤ 2m(sD)^{3} .

In order to obtain an estimation for the degrees in (8) it remains only to bound the degrees of the α̃_{i}^{(ℓ)} ’s. Rewriting formula (8), we construct Q_{1}, …, Q_{M−s} ∈ B_{ξ}[x_{n}] such that the equality

Q_{1}C_{s+1} + ⋯ + Q_{M−s}C_{M} = ∑_{i=1}^{s} α̃_{i}^{(ℓ)}C_{i}

holds in A_{ξ}^{N} and ξQ_{l} ∈ A for all l = 1, …, M − s are polynomials of degree bounded by d + 2m(sD)^{3} . On the other hand, relation (1) for the first s × s minor μ of the matrix F yields the equality :

Q_{1}C_{s+1} + ⋯ + Q_{M−s}C_{M} = Q_{1} ∑_{r=1}^{s} \frac{b_{r1}}{μ} C_{r} + ⋯ + Q_{M−s} ∑_{r=1}^{s} \frac{b_{r,M−s}}{μ} C_{r}.

Taking into account that the columns C_{1}, …, C_{s} are linearly independent, we deduce :

α̃_{i}^{(ℓ)} = \frac{∑_{l=1}^{M−s} b_{il}Q_{l}}{μ} .

Let h be the minimal exponent such that ξ^{h}α_{i}^{(ℓ)} ∈ A. Since ξQ_{l} ∈ A for all l and the polynomials μ and ξ are relatively primes (because μ is monic in all the variables and ξ belongs to B), we deduce that h ≤ 1 , and then

ξα̃_{i}^{(ℓ)} ∈ A  and  μ divides ξ ∑_{l=1}^{M−s} b_{il}Q_{l} in A.  (11)

Therefore, by (1) , (10) and (11) :

deg(ξα̃_{i}^{(ℓ)}) ≤ max_{l}{deg(b_{il}ξQ_{l})} ≤ (sD) + max_{j}{deg β_{j}^{(ℓ)}} + d ≤ (sD) + 2m(sD)^{3} + d.

Since m ≤ (M − s)sD, we are able to rewrite (8) as follows :

−x_{n} x_{n}^{k_{ℓ}}C_{i_{ℓ}} = ∑_{j=1}^{m−q} \frac{β_{j}^{(ℓ)}}{ξ} x_{n}^{k_{j}}C_{i_{j}} + ∑_{i=1}^{s} \frac{α_{i}^{(ℓ)}}{ξ} C_{i} ,  (12)

where β_{j}^{(ℓ)} ∈ B, α_{i}^{(ℓ)} ∈ A and deg β_{j}^{(ℓ)}, deg α_{i}^{(ℓ)} ≤ 4(M − s)(sD)^{4} for all indices j, i and ℓ.

The following definition allows to show a new local presentation of Im F which we will consider in the sequel.

Definition 8 Let ψ : A^{m−q+s} → Im F be the linear application defined by :

– ψ(e_{j}) = x_{n}^{k_{j}}C_{i_{j}} , for all j = 1, …, m − q,

– ψ(e_{j}) = C_{j−m+q}, for all j = m − q + 1, …, m − q + s. Observe that ψ depends on the choice of the minor ξ. The localized morphism ψ_{ξ} is surjective (Proposition 7 and the definition of Q), and then Ker ψ_{ξ} is a projective A_{ξ} -module because Im F_{ξ} is A_{ξ} -free

With the notations above we have the following result borrowed from [15, Ch.IV, page 115]:

Proposition 9 The matrix U ∈ A_{ξ}^{(m−q)×(m−q+s)} , where the ℓ -th row is the vector

(\frac{β_{1}^{(ℓ)}}{ξ} , …, \frac{β_{m−q}^{(ℓ)}}{ξ} , \frac{α_{1}^{(ℓ)}}{ξ} , …, \frac{α_{s}^{(ℓ)}}{ξ}) + x_{n}e_{ℓ}

( e_{ℓ} is the ℓ -th vector of the canonical basis of A^{m−q}), is a unimodular matrix in A_{ξ} (i.e. the (m−q)×(m−q) minors generate the ring A_{ξ}) and its rows are a basis of Ker ψ_{ξ} (in particular Ker ψ_{ξ} is free). Moreover ξU ∈ A^{(m−q)×(m−q+s)} and deg ξU ≤ 4(M −s)(sD)^{4} .

Proof.- Let S ⊂ A_{ξ}^{m−q+s} be the submodule generated by the rows of the matrix U . From the relations (12) it is clear that S ⊂ Ker ψ_{ξ}. In order to see the other inclusion, we observe the following : for all ℓ = 1, …, m − q and for all p ∈ A_{ξ} there exist γ_{1}, …, γ_{m−q} ∈ B_{ξ} and γ_{m−q+1}, …, γ_{m−q+s} ∈ A_{ξ} (depending on ℓ and p) such that

pe_{ℓ} − ∑_{j=1}^{m−q+s} γ_{j}e_{j} ∈ S.

This can be done developing p in powers of the variable x_{n}. Therefore, if (p_{1}, …, p_{m−q+s}) ∈ Ker ψ_{ξ}, we can rewrite it as follows

(p_{1}, …, p_{m−q+s}) = w + ∑_{j=1}^{m−q+s} γ_{j}e_{j}

where w ∈ S, γ_{1}, …, γ_{m−q} ∈ B_{ξ} and γ_{m−q+1}, …, γ_{m−q+s} ∈ A_{ξ}. Applying ψ we have the following identity in Im F_{ξ} :

0 = ∑_{j=1}^{m−q} γ_{j} x_{n}^{k_{j}}C_{i_{j}} + ∑_{j=m−q+1}^{m−q+s} γ_{j}C_{j−m+q}.  (13)

Looking this equality modulo the free A_{ξ} -module L_{ξ} (see (4) in Section 3) one deduces the relation in Q_{ξ} :

0 = ∑_{j=1}^{m−q} γ_{j} \overline{x_{n}^{k_{j}}C_{i_{j}}},

and, since the elements \overline{x_{n}^{k_{j}}C_{i_{j}}} , j = 1, …, m − q, are a B_{ξ} -basis of Q_{ξ} (see Proposition 7), we have γ_{j} = 0 for j = 1, …, m − q. Thus, the linear combination (13) can be reduced to

0 = ∑_{j=m−q+1}^{m−q+s} γ_{j}C_{j−m+q}.

Since the vectors C_{1}, …, C_{s} are linearly independent we have also γ_{j} = 0 for j = m − q + 1, …, m − q + s. Then (p_{1}, …, p_{m−q+s}) ∈ S and therefore S = Ker ψ_{ξ}. Moreover, the rows of the matrix U are a A_{ξ} -basis of Ker ψ_{ξ} : Im F_{ξ} is A_{ξ} -free of rank s and then Ker ψ_{ξ} is locally free of rank m − q; since the rows of the matrix U generate Ker ψ_{ξ}, by Nakayama’s Lemma, they are a basis for the localization in any maximal ideal of A_{ξ} and then they are A_{ξ} -linearly independent. The unimodularity of the matrix U follows from the decomposition A_{ξ}^{m−q+s} ≃ Ker ψ_{ξ} ⊕ Im F_{ξ}.

Following [15, Ch.IV, Lemma 3.12] we are able to simplify the matrix U using “ x_{n} - division with remainder” between the matrix formed by the last s columns of U and the matrix consisting of the first m − q columns of U in the obvious way :

Proposition 10 There exists an invertible matrix C ∈ A_{ξ}^{(m−q+s)×(m−q+s)} verifying

UC = ( \begin{matrix}& | \\ x_{n}Id_{m−q} + U_{1} & | & U_{2} \\ & | \end{matrix} )

where ξU_{1} ∈ B^{(m−q)×(m−q)} , ξ^{4(M−s)(sD)^{4}}U_{2} ∈ B^{(m−q)×s}, et ξ^{4(M−s)(sD)^{4}}C ∈ A^{(m−q+s)×(m−q+s)} are matrices whose entries have degrees bounded by 16(M − s)^{2}(sD)^{8} .

The matrix U can be modified by another change of coordinates in such a way that all its entries belong to a suitable localization of the ring B. For this purpose it is convenient to consider the matrix UC in Proposition 10 as a k(x_{1}, …, x_{n−1})[x_{n}] -unimodular matrix in order to apply Suslin’s reduction procedure following [17] and [5] (see the next two lemmas). Unfortunately this approach requires the introduction of certain polynomials in B playing the rôle of the ξ ’s. Fortunately their amount and degrees can be appropriately controlled (Corollary 13 below).

In the following two lemmas V will denote the matrix UC from Proposition 10.

Lemma 11 (cf. [5, Lemma 4.4]) For each z ∈ IA^{n−1} \ {ξ = 0} there exists an invertible matrix Λ_{z} ∈ k^{(m−q+s)×(m−q+s)} such that: if V′ := V Λ_{z}, Δ_{1} := det[V′_{1}, …, V′_{m−q}] , (the (m − q) × (m − q) minor built from the first m − q columns of V′), Δ_{2} := det[V′_{1}, …, V′_{m−q−1}, V′_{m−q+1}] and c_{z} := Res_{x_{n}}(Δ_{1}, Δ_{2}) the resultant of Δ_{1} and Δ_{2} with respect to the indeterminate x_{n}, then c_{z}(z) ≠ 0 .

Proof.- Let z = (z_{1}, …, z_{n−1}) ∈ IA^{n−1} \ {ξ = 0} be given; let k[y_{ij}; 1 ≤ i, j ≤ m − q + s] be the polynomial ring in (m − q + s)^{2} new indeterminates over k. By Y we denote the m − q + s square matrix [y_{ij}] with columns Y_{1}, …, Y_{m−q+s}. We write Y′ and Y′′ for the (m − q + s) × (m − q) matrices [Y_{1}, …, Y_{m−q}] and [Y_{1}, …, Y_{m−q−1}, Y_{m−q+1}] respectively. Let V′ := V Y . From the Binet-Cauchy formula ([10, Ch.2]) we see that:

Δ_{1} := det[V′_{1}, …, V′_{m−q}] = ∑_{I} det(V_{I}) det((^{t}Y′)_{I})  (14)

Δ_{2} := det[V′_{1}, …, V′_{m−q−1}, V′_{m−q+1}] = ∑_{I} det(V_{I}) det((^{t}Y′′)_{I})

where I runs through all sequences (i_{1}, …, i_{m−q}) such that 1 ≤ i_{1} < ⋯ < i_{m−q} ≤ m − q + s. Let c := c(x_{1}, …, x_{n−1}, Y) := Res_{x_{n}}(Δ_{1}, Δ_{2}) be the resultant of Δ_{1} and Δ_{2} with respect to the indeterminate x_{n}. Claim.- c(z, Y) = c(z_{1}, …, z_{n−1}, Y) ≠ 0 . Proof of the claim. From Proposition 10 we have that the polynomial det[V_{1}, …, V_{m−q}] is monic in x_{n} and m − q = deg_{x_{n}}(det[V_{1}, …, V_{m−q}]) > deg_{x_{n}}(det(V_{I})) for all sequences of natural numbers I = (i_{1}, …, i_{m−q}) with 1 ≤ i_{1} < ⋯ < i_{m−q} ≤ m − q + s and I ≠ (1, …, m − q) . Thus (14) implies that c(z, Y) = c(z_{1}, …, z_{n−1}, Y) = Res_{x_{n}}(Δ_{1}(z, x_{n}, Y′), Δ_{2}(z, x_{n}, Y′′)) . Suppose now that c(z, Y) = 0 . Then there exists p ∈ \overline{k}[x_{n}, Y] with deg_{x_{n}}(p) ≥ 1 such that p divides both Δ_{1}(z, x_{n}, Y′) and Δ_{2}(z, x_{n}, Y′′) . In particular we have p ∈ \overline{k}[x_{n}, Y_{1}, …, Y_{m−q−1}] . Let h ∈\overline{k}[x_{n}, Y′] be such that

ph = Δ_{1} = ∑_{I} det(V_{I}(z, x_{n})) det((^{t}Y′)_{I}).  (15)

Let I ⊂ \overline{k}[x_{n}][Y′] be the ideal generated by all the determinants det((^{t}Y′)_{I}) ; I is a homogeneous prime ideal (see [4, Ch.2, Th.2.10]). From (15) we see that p and h must be homogeneous in Y′ and that deg_{Y′}(p) + deg_{Y′}(h) = m − q. The polynomial p doesn’t belong to I since it is independent from Y_{m−q}. Since Δ_{1} ∈ I by (15) and I is prime we conclude h ∈ I and deg_{Y′}(h) ≥ m − q. Thus deg_{Y′}(p) = 0 , i.e. p ∈\overline{k}[x_{n}] . Now, again by (15), we see that p divides all det(V_{I}(z, x_{n})) . The unimodularity of V (Propositions 9 and 10) implies that the ideal generated by all polynomials det(V_{I}(z, x_{n})) is trivial in k[x_{n}] . Therefore p ∈ \overline{k}, which contradicts deg_{x_{n}}(p) ≥ 1 . This finishes the proof of the claim. Since k is infinite and since c(z, Y) ≠ 0 there exists Λ_{z} ∈ GL_{m−q+s}(k) such that c(z, Λ_{z}) ≠ 0 .

Lemma 12 (cf. [5, Lemma 4.5]) Let z ∈ IA^{n−1} \ {ξ = 0}, Λ_{z} ∈ GL_{m−q+s}(k) , V′ = V Λ_{z}, Δ_{1} , Δ_{2} and c_{z} ∈ B_{ξ} be as in Lemma 11. Then there exists an invertible matrix Ω ∈ A_{c_{z}ξ}^{(m−q+s)×(m−q+s)} such that V Ω = V (0) (where V (0) denotes the matrix V after the evaluation x_{n} ↦ 0 ) and (c_{z}ξ^{u})^{l}Ω is a polynomial matrix in A^{(m−q+s)×(m−q+s)} . The degrees of the entries of (c_{z}ξ^{u})^{l}Ω and the integers u and l are of order ((M −s)sD)^{O(1)} , independently of z.

Proof.- Let z ∈ IA^{n−1} \ { ξ = 0 }, c := c_{z} and g, h ∈ B_{ξ}[x_{n}] be such that c = gΔ_{1} + hΔ_{2}. From Proposition 10, without loss of generality, we may assume that there exists a constant η ∈ IN independent of z, of order ((M −s)sD)^{O(1)} , such that ξ^{η}g, ξ^{η}h are polynomials in A, ξ^{η}c belongs to B, and the total degrees of these polynomials are bounded by another constant of size ((M − s)sD)^{O(1)} . For each j, m − q + 2 ≤ j ≤ m − q + s, there exists a column vector G_{j} ∈ A_{cξ}^{(m−q)×1} with controlled degrees such that V′_{j}(0) − V′_{j} = cG_{j}. Therefore V′_{j}(0) − V′_{j} = gΔ_{1}G_{j} + hΔ_{2}G_{j}. Let B_{1} := adj[V′_{1}, …, V′_{m−q}] be the adjoint matrix of the (m − q) × (m − q) matrix [V′_{1}, …, V′_{m−q}] . Simmilarly, let B_{2} be the adjoint of the matrix [V′_{1}, …, V′_{m−q−1}, V′_{m−q+1}] . Thus:

Δ_{1}gG_{j} = [V′_{1}, …, V′_{m−q}](B_{1}gG_{j})

and

Δ_{2}hG_{j} = [V′_{1}, …, V′_{m−q−1}, V′_{m−q+1}](B_{2}hG_{j}) .

From these equalities we conclude that

V′_{j}(0) − V′_{j} = g_{1}V′_{1} + ⋯ + g_{m−q+1}V′_{m−q+1}

for suitable g_{1}, …, g_{m−q+1} ∈ A_{cξ}. This holds for all m − q + 2 ≤ j ≤ m − q + s. Therefore there exists a unimodular matrix Ω′ in A_{cξ} which is a product of (m − q + 1)(s − 1) elementary matrices and such that:

V Ω′ = [V′_{1}, …, V′_{m−q+1}, V′_{m−q+2}(0), …, V′_{m−q+s}(0)].

Let T be the (m − q + 1) × (m − q + 1) matrix defined by

T := \frac{1}{c}adj\{( \begin{matrix}V′_{1} & .... & V′_{m−q} & V′_{m−q+1} \\ 0 & .... & −h & g \end{matrix} )\} ( \begin{matrix}V′_{1}(0) & .... & V′_{m−q}(0) & V′_{m−q+1}(0) \\ 0 & .... & −h(0) & g(0) \end{matrix} ) .

Since c does not depend on x_{n} it is easy to see that T ∈ A_{cξ}^{(m−q+1)×(m−q+1)} and det(T) = 1 . Therefore T ∈ SL_{m−q+1}(A_{cξ}) . Moreover, we have

[V′_{1}, …, V′_{m−q+1}] T = [V′_{1}(0), …, V′_{m−q+1}(0)].

One easily checks now that Ω := Ω′ ( \begin{matrix}T & 0 \\ 0 & Id_{s−1} \end{matrix} ) verifies the assertion.

From Lemma 11 and Lemma 12 one deduces:

Corollary 13 For each non zero q × q minor ξ of the matrix G (see Lemma 6) there exist polynomials ξ_{1}, …, ξ_{L} ∈ B whose degrees are of order ((M − s)sD)^{O(1)} and L = ((M − s)sD)^{O(n)} , such that 1. The ring B is generated by the polynomials ξξ_{j} where ξ runs over all the non zero

q × q minors of G and j = 1, …, L.

2. The image of the localized map ψ_{ξξ_{j}} (Definition 8) is Im F_{ξξ_{j}} .

3. The kernel of ψ_{ξξ_{j}} is a free module generated by m−q polynomial vectors in B^{m−q+s} of degrees of order ((M − s)sD)^{O(1)} .

Proof.- For each minor ξ we construct the polynomials ξ_{j} as follows : consider the k - linear space generated by the polynomials c_{z}ξ^{u} ∈ B of Lemma 12, where z runs in the set IA^{n−1} \ {ξ = 0}; since deg(c_{z}ξ^{u}) = ((M − s)sD)^{O(1)} , the dimension of this space is bounded by ((M − s)sD)^{O(n)} . The polynomials ξ_{j} ’s are chosen as a basis of this space. From Lemma 11 and Hilbert Nullstellensatz one deduces that the polynomials ξξ_{j} generate B_{ξ}; on the other hand the minors ξ generate the ring B (recall that Im G is a direct summand of B^{m}) and then the first condition is verified. The second condition follows from Definition 8. Fix ξξ_{j} and let z ∈ IA^{n−1} be such that ξ_{j} = c_{z}ξ^{u}. Let Ω ∈ A_{ξξ_{j}}^{(m−q+s)×(m−q+s)} be the matrix from Lemma 12 associated to z. Therefore the rows of V Ω = V (0) form a basis of Ker ψ_{ξξ_{j}} . Multiplying these vectors by a suitable power of ξ as in Proposition 10 we finish the proof.

Consider now a polynomial ξξ_{j} and let W ∈ B^{(m−q)×(m−q+s)} be the matrix whose rows are a basis of Ker ψ_{ξξ_{j}} as in the previous corollary. Since W is B_{ξξ_{j}} -unimodular (because Im ψ_{ξξ_{j}} is free) its (m−q)×(m−q) minors γ_{i}, i ∈ I, generate the ring B_{ξξ_{j}} . The degrees of these minors are clearly bounded by ((M −s)sD)^{O(1)} , and then, we may consider again only ((M − s)sD)^{O(n−1)} of them. For each γ_{i} it is easy to exhibit a basis of the image of the map ψ localized in the polynomial γ_{i}ξξ_{j} : it suffices to take the image by ψ of those vectors e_{k} of the canonical basis, where the k -th column of W is not considered in the construction of γ_{i}. In this way we obtain a basis for the image of F localized in γ_{i}ξξ_{j} of degrees bounded by ((M −s)sD)^{O(1)} .

Summarizing, we are able to show local estimations for the degree of a basis of the image of F . We emphasize the fact that the localizing polynomials involve only the variables x_{1}, …, x_{n−1} .

Lemma 14 There exist polynomials π_{1}, …, π_{H} ∈ B such that

1. 1 ∈ (π_{1}, …, π_{H}) .

2. deg π_{j} = ((M − s)sD)^{O(1)} .

3. H = ((M − s)sD)^{O(n)} .

4. for all j = 1, …, H there exists a basis of Im F_{π_{j}} formed by polynomial vectors of degree ((M − s)sD)^{O(1)} .

Proof.- Take the polynomials π_{k} as the polynomials γ_{i}ξξ_{j} where ξ runs over all the q × q minors of G, ξ_{j} as in Corollary 13, and γ_{i} as in the previous argument.

Definition 15 Let F̃ ∈ A^{_{N}×_{M}} be the matrix whose columns are the generators of Ker F constructed in Lemma 1. Therefore we have :

– deg F̃ ≤ sD.

– Ñ := M .

– M̃ ≤ 3(M − s)(sD)^{n}.

– Im F̃ is A -free.

– s̃:= the rank of F̃ (we have s̃ = M − s). Analogously, let F̂ ∈ A^{_{N}×_{M}} be the matrix whose columns are the generators of Ker F̃ constructed applying Lemma 1 to F̃.

– deg F̂ ≤ (M − s)sD.

– N̂ ≤ 3(M − s)(sD)^{n}.

– M̂ = ((M − s)sD)^{O(n^{2})} .

– Im F̂ is A -free.

– ŝ:= the rank of F̂ (where ŝ = M̃ − s̃).

For technical reasons we need a similar lemma for F̃ and F̂. This can be done repeating the arguments used for F . We note that the change of coordinates in Section 3 that assures the existence of a minor monic in all the variables can be made simultaneously for the three matrices F , F̃ and F̂.

Lemma 16 There exist polynomials π̃_{1}, …, π̃_{H} ∈ B such that

1. 1 ∈ (π̃_{1}, …, π̃_{H}) .

2. deg π̃_{j} = ((M − s)sD)^{O(n)} .

3. H̃ = ((M − s)sD)^{O(n^{2})} .

4. for all j = 1, …, H̃ there exists a basis of Im F̃_{π_{j}} = Ker F_{π_{j}} formed by polynomial vectors of degree ((M − s)sD)^{O(n)} .

Lemma 17 There exist polynomials π̂_{1}, …, π̂_{H} ∈ B such that

1. 1 ∈ (π̂_{1}, …, π̂_{H}) .

2. deg π̂_{j} = ((M − s)sD)^{O(n^{2})} .

3. Ĥ = ((M − s)sD)^{O(n^{3})} .

4. for all j = 1, …, Ĥ there exists a basis of Im F̂_{π_{j}} = Ker F̃_{π_{j}} formed by polynomial vectors of degree ((M − s)sD)^{O(n^{2})} .

Remark 18 Taking the products π_{i}π̃_{j}π̂_{k}, we will suppose that the polynomials π_{j}, π̃_{j} and π̂_{j} are the same in Lemma 14, 16 and 17, with the last estimations for the degree and the number of the polynomials.

5 The main Theorem

This section is devoted to the proof of our main result :

Theorem 19 Let F ∈ A^{N×M} be a polynomial matrix whose image is an A -free module of rank s and whose entries have total degrees bounded by an integer D. Then there exists a basis {v_{1}, …, v_{M}} of A^{M} such that:

• {v_{1}, …, v_{M−s}} is a basis of Ker F .

• the coordinates of the vectors v_{j}, for j = 1, …, M − s, have degree of order ((M − s)sD)^{O(n^{3})} .

• {F (v_{M−s+1}), …, F (v_{M})} is a basis of Im F .

• the coordinates of the vectors v_{j}, for j = M − s + 1, …, M , have degree of order ((M − s)sD)^{O(n^{4})} .

On our way to prove this theorem, we will make use mutatis mutandis of the local-global techniques due to Vaserstein (see for example [15, Ch.IV, Th.1.18.]) in combination with the effective version of Quillen-Suslin Theorem given in [5].

Recall that for any matrix G with entries in a polynomial ring, G(0) denotes the new matrix obtained by replacing the last variable by 0 .

With the notations introduced in the previous section, we will prove the following local result :

Proposition 20 For all π_{j} ∈ B chosen after Remark 18 (for j = 1, …, H), there exist a non negative integer η and invertible matrices P_{j} ∈ A_{π_{j}}^{M×M} and Q_{j} ∈ A_{π_{j}}^{_{M}×_{M}} such that :

1. η = ((M − s)sD)^{O(n^{2})} .

2. π_{j}^{η}P_{j} ∈ A^{M×M} and deg(π_{j}^{η}P_{j}) = ((M − s)sD)^{O(n^{2})} .

3. π_{j}^{η}Q_{j} ∈ A^{_{M}×_{M}} and deg(π_{j}^{η}Q_{j}) = ((M − s)sD)^{O(n^{2})} .

4. F̃ = P_{j}F̃(0)Q_{j}.

Proof.- Fix an index j. From Remark 18 one can take the polynomials π_{j} unifying the Lemmas 14, 16 and 17 and obtains bases for Im F_{π_{j}} , Im F̃_{π_{j}} , and Im F̂_{π_{j}} of appropriate degrees. Consider now the exact sequences associated to the matrices F and F̃ :

0 → Im F̃_{π_{j}} → A_{π_{j}}^{M} → Im F_{π_{j}} → 0

0 → Im F̂_{π_{j}} → A_{M} ; π_{j} → Im F̃_{π_{j}} → 0

From the first sequence, one obtains a basis of A_{π_{j}}^{M} lifting the s vectors of the basis of Im F_{π_{j}} and adding the M − s vectors of the basis of Im F̃_{π_{j}} . Write B_{j} for this basis. In the same way one obtains a basis C_{j} of A_{M} ; π_{j} from the second exact sequence completing

the basis of Im F̂_{π_{j}} with the preimages of the basis of Im F̃_{π_{j}} in A_{M} ; π_{j} . From the previous results one infers that all the polynomial vectors of B_{j} and C_{j} have degree bounded by ((M − s)sD)^{O(n^{2})} . For all integer q, denote by E_{q} the canonical basis of A^{q}. Then, we have

F̃ = P C Q,

where

• P := [ Id ]_{B_{j}E_{M}} ∈ A_{π_{j}}^{M×M} ,

• Q := [ Id ]_{E_{M}C_{j}} ∈ A_{π_{j}}^{_{M}×_{M}}

• C is the diagonal matrix : ( \begin{matrix}Id_{M−s} & 0 \\ 0 & 0 \end{matrix} ).

Moreover, the matrices π_{j}^{η}P and π_{j}^{η}Q have all their entries in A and their degrees of order ((M − s)(sD))^{O(n^{2})} , for a certain η ∈ IN of order ((M − s)sD)^{O(n^{2})} . Finally, replacing x_{n} by 0 , one has :

F̃(0) = P (0) C Q(0).

And then :

F̃ = P_{j} F̃(0) Q_{j}

where P_{j} := P P^{−1}(0) and Q_{j} := Q^{−1}(0)Q are invertible matrices in A_{π_{j}} , with controlled degrees (recall that π_{j} ∈ B).

Now we make use of the argument of [15, Ch.IV, Th.1.18.] in order to “glue” the matrices P_{j} ’s and the matrices Q_{j} ’s.

Lemma 21 There exist two invertible matrices P ∈ A^{M×M} and Q ∈ A^{_{M}×_{M}} of degrees of order ((M − s)sD)^{O(n^{3})} such that F̃ = P F̃(0)Q.

Proof.- Fix an index j, j = 1, …, H, and let y be a new variable. Consider the matrices with entries in A_{π_{j}}[y] :

P_{j}(x_{n} + y)P_{j}^{−1} , P_{j}P_{j}^{−1}(x_{n} + y) , Q_{j}^{−1}(x_{n} + y)Q_{j} , Q_{j}^{−1}Q_{j}(x_{n} + y).

From Proposition 20 (modifying slightly η, if necessary), we may suppose that the matrices

P_{j}(x_{n} + π_{j}^{η}y)P_{j}^{−1} , P_{j}P_{j}^{−1}(x_{n} + π_{j}^{η}y) , Q_{j}^{−1}(x_{n} + yπ_{j}^{η})Q_{j} , Q_{j}^{−1}Q_{j}(x_{n} + π_{j}^{η}y)

have all the entries in A[y] (it suffices to take an appropriate power of π_{j} in order to eliminate the denominators).

Then, the matrices

Γ_{j} := P_{j}(x_{n} + π_{j}^{η}y)P_{j}^{−1} and Λ_{j} := Q_{j}^{−1}Q_{j}(x_{n} + π_{j}^{η}y)

are invertible in A[y]^{M×M} and A[y]^{_{M}×_{M}} respectively, with entries of degree of order ((M − s)sD)^{O(n^{2})} . Again after Proposition 20 we have the relation :

F̃(x_{n} + π_{j}^{η}y) = Γ_{j} F̃ Λ_{j}  (16)

for j = 1, …, H. From item 1 of Lemmas 14-17 and Remark 18, we have 1 ∈ (π_{1}^{η}, …, π_{H}^{η}) and, applying the effective Nullstellensatz (see [13] or [9]), there exist α_{1}, …, α_{H} ∈ x_{n}B such that :

x_{n} = α_{1}π_{1}^{η} + ⋯ + α_{H}π_{H}^{η} and deg α_{j} = ((M − s)sD)^{O(n^{3})} ∀j.

Considering the identity (16) for j := H and replacing x_{n} ↦ ∑_{q=1}^{H−1} α_{q}π_{q}^{η} and y ↦ α_{H}, we

get :

F̃ = Γ_{H}( ∑_{q=1}^{H−1} α_{q}π_{q}^{η}, α_{H}) F̃( ∑_{q=1}^{H−1} α_{q}π_{q}^{η}) Λ_{H}( ∑_{q=1}^{H−1} α_{q}π_{q}^{η}, α_{H}).

Applying once again the formula (16), with j := H − 1 , and replacing x_{n} ↦ ∑_{q=1}^{H−2} α_{q}π_{q}^{η}

and y ↦ α_{H−1}, we have

F̃( ∑_{q=1}^{H−1} α_{q}π_{q}^{η}) = Γ_{H−1}( ∑_{q=1}^{H−2} α_{q}π_{q}^{η}, α_{H−1}) F̃( ∑_{q=1}^{H−2} α_{q}π_{q}^{η}) Λ_{H−1}( ∑_{q=1}^{H−2} α_{q}π_{q}^{η}, α_{H−1}),

and then F̃ can be written

Γ_{H}( ∑_{q=1}^{H−1} α_{q}π_{q}^{η}, α_{H})Γ_{H−1}( ∑_{q=1}^{H−2} α_{q}π_{q}^{η}, α_{H−1}) F̃( ∑_{q=1}^{H−2} α_{q}π_{q}^{η}) Λ_{H−1}( ∑_{q=1}^{H−2} α_{q}π_{q}^{η}, α_{H−1})Λ_{H}( ∑_{q=1}^{H−1} α_{q}π_{q}^{η}, α_{H}).

Thus, we obtain for all index u, u = 0, …, j, where j = 1, …, H a relation of the type :

F̃ = [ ∏_{u=0}^{j} Γ_{H−u}( ∑_{q=1}^{H−u−1} α_{q}π_{q}^{η}, α_{H−u})] F̃( ∑_{u=1}^{H−j} α_{q}π_{q}^{η}) [ ∏_{u=0}^{j} Λ_{H−u}( ∑_{q=1}^{H−u−1} α_{q}π_{q}^{η}, α_{H−u})].

In particular, for j = H, the assertion follows.

Applying the same argument in a recurrent way on the number of variables, one deduces :

Corollary 22 There exist two invertible matrices V ∈ A^{M×M} and W ∈ A^{_{M}×_{M}} of degrees of order ((M − s)sD)^{O(n^{3})} such that

F̃ = V F̃(0, …, 0)W.

In particular, there exists a basis of Im F̃ formed by vectors of degree of order ((M − s)sD)^{O(n^{3})} .

Proof.- From Remark 2 we have that F (0) verifies the same conditions as F and that F̃ (0) = F̃(0) (since the vectors w_{j}(0) are a system of generators of Ker F (0) ). Therefore we can apply again the same argument as in Lemma 21 to the matrix F̃(0) .

Now, we are able to prove Theorem 19.

\underline{Proof of Theorem 19.-} Since Im F̃ = Ker F , Corollary 22 allows us to estimate the degrees of a certain basis v_{1}, …, v_{M−s} of Ker F . Applying [5, Th.3.1.] for the unimodular matrix in A^{(M−s)×M} formed by these vectors, we infer the existence of s vectors v_{M−s+1}, …, v_{M} in A^{M} such that {v_{1}, … v_{M}} is a basis of A^{M} and deg v_{i} ≤ ((M − s)sD)^{O(n^{4})} , for i = M − s + 1, …, M . Clearly {F (v_{M−s+1}), …, F (v_{M})} is a basis of Im F and the theorem is proved.

6 The case of the matrix of a projection map

In this section F ∈ A^{M×M} denotes a polynomial matrix such that F^{2} = F (i.e. F is the matrix of a projection map of A^{M} ). It is well known that in this case A^{M} = Ker F ⊕Im F and, in particular, Im F and Ker F are both A -free. Since F′ := Id − F corresponds also to a projection map and since the bases of Ker F and Im F form a basis of A^{M} , several arguments of the last two sections can be simplified and the degree bounds in Theorem 19 may be improved. We observe first that the Lemmas 14, 16 and 17 can be replaced by the following result (which doesn’t involve neither the auxiliar matrix F̃ nor the matrix F̂) :

Lemma 23 Let F ∈ A^{M×M} be the matrix of a projection map whose entries are polynomials with total degrees bounded by an integer D and let s be the rank of F . Then there exist polynomials π_{1}, …, π_{H} ∈ B such that :

1. 1 ∈ (π_{1}, …, π_{H}) .

2. deg π_{j} = ((M − s)sD)^{O(1)} .

3. H = ((M − s)sD)^{O(n)} .

4. for all index j = 1, …, H, there exist bases of Im F_{π_{j}} and Ker F_{π_{j}} consisting of polynomial vectors of degrees of order ((M − s)sD)^{O(1)} .

Proof.- Applying Lemma 14 to F and F′ one obtains a family of polynomials π_{j} ∈ B and bases for Im F_{π_{j}} and Im F′_{π_{j}} with appropriate degrees (indeed, the polynomials π_{j} for F and F′ are different but this constraint can be avoided multiplying them as in Remark 18). Since Im F′_{π_{j}} = Ker F_{π_{j}} the lemma follows.

With the aid of this lemma, we are able to simplify the proof of Proposition 20 observing that the join of a basis of Im F and a basis of Im F′ gives a basis of the whole space A^{M} . Since Lemma 21 and Corollary 22 follow directly from Proposition 20, we obtain analougous results for the matrix F instead of the matrix F̃. The improvement of the degree upper bounds in this case is due to the fact that the introduction of the matrices F̃ and F̂ is unnecessary. We can summarize these facts in the following more precise statement of Theorem 19 :

Theorem 24 Let F ∈ A^{M×M} be the matrix of a projection map involving polynomials whose degrees are bounded by an integer D and let s be the rank of F . Then there exists a basis {v_{1}, …, v_{M}} of A^{M} , such that the first M − s vectors form a basis of Ker F , the last s vectors are a basis of Im F and the degrees of the coordinates of these vectors are of order ((M − s)sD)^{O(n)} .

We observe that if the matrix F does not correspond to a projection map, but the space A^{M} is decomposed as Ker F ⊕ Im F , the arguments of the last two sections can be also simplified. In this case it is enough to consider the Lemmas 14 and 16, in order to obtain Proposition 20, Lemma 21 and Corollary 22 for the matrix F . In fact, for these three results it is only necessary to know how to complete the bases of the image and the kernel to bases of the whole space under a suitable localization; the matrix F̃ must be introduced in order to obtain a basis of a localization of Ker F and then the bases of the kernel and the image can be completed. In other words we have :

Theorem 25 Let F ∈ A^{M×M} be a matrix such that A^{M} = Ker F ⊕ Im F . Suppose that F involves polynomials whose degrees are bounded by an integer D and that s is the rank of F . Then there exists a basis {v_{1}, …, v_{M}} of A^{M} , such that the first M − s vectors form a basis of Ker F and have degrees of order ((M −s)sD)^{O(n^{2})} , and the last s vectors are a basis of Im F and have degrees of order ((M − s)sD)^{O(n^{3})} .

7 An application to reduced complete intersections

Let k be an infinite field and f_{1}, …, f_{n−r} be a regular sequence in k[x_{1}, …, x_{n}] of degrees bounded by an integer d > 1 . Suppose that the variables x_{1}, …, x_{n} are in Noether position with respect to the polynomials f_{i}. More precisely, the natural map k[x_{1}, …, x_{r}] → k[x_{1}, …, x_{n}]/(f_{1}, …, f_{n−r}) is an injective and integral morphism.

Write R := k[x_{1}, …, x_{r}] and S := k[x_{1}, …, x_{n}]/(f_{1}, …, f_{n−r}) . It is well known (see for example [8, Corollary 18.17] or [12, Lemma 3.3.1]) that, under these conditions, S is a locally free R -module of finite rank (bounded by d^{n−r} following Bezout’s Inequality) and hence free (Quillen-Suslin Theorem).

This context (“polynomial regular sequence + Noether position”) appears frequently in several approaches related to effectivity problems in Computer Algebra, even in the positive dimensional case (see for instance [21], [11], [22]). At this point it is quite natural to look for properties of R -bases of S (degree bounds, algorithms to compute them, etc.), but we have been unable to find any significative result related to this subject in the literature. In this frame we are interested in the study of the existence of a basis consisting of polynomials with single exponential degrees, in the case where the ring S is reduced. For this purpose we combine our previous results with quantitative facts about duality in complete intersection rings (following [16] and [22]).

We start by recalling some known facts about duality theory. We denote by S^{∗} the dual space Hom_{R}(S, R) . The R -module S^{∗} admits a natural structure of S -module in the following way : for any pair (b, β) in S × S^{∗} the product b.β is the R -linear application of S^{∗} defined by (b.β)(x) := β(bx) , for each x in S. Our assumptions about R and S allow to show that the S -modules S and S^{∗} are isomorphic (see [16, Example F.19 and Corollary F.10]) and therefore S^{∗} can be generated by a single element. A generator σ of S^{∗} is called a trace of S over R. If char( k)=0 it is well known that, under our hypothesis, the application b ↦ Tr(η_{b}) is a trace of S over R (where η_{b} is the endomorphism induced by the multiplication by b ∈ B and Tr is the usual trace). Therefore we have the following :

Proposition 26 (see [22, Proposition 3]) There exist a trace σ ∈ S^{∗} and polynomials a_{m} and c_{m} in k[x_{1}, …, x_{n}], 1 ≤ m ≤ M , such that :

– deg(a_{m}) + deg(c_{m}) ≤ (n − r)(d − 1) ;

– M ≤ 3(n − r)(d − 1)^{n−r};

– the “trace formula” : b = ∑_{m} σ(b\overline{c}_{m})\overline{a}_{m} holds for all b ∈ S.

From this proposition we infer that the classes of the polynomials a_{m}, 1 ≤ m ≤ M , are a system of generators of S over R and that the R -bilinear form Φ : S × S → R defined by Φ(b, b′) := σ(bb′) is non degenerate.

By means of Proposition 26 we are able to apply our previous results about polynomial matrices in order to obtain the following :

Theorem 27 There exists a basis of S over R formed by polynomials of degrees of order d^{O((n−r)r^{4}))} .

Proof.- Let F : R^{M} → R^{M} be the linear map defined by the matrix (Φ(\overline{a}_{i}, \overline{a}_{j}))_{ij} and let G : R^{M} → S be the map defined by e_{j} ↦ \overline{a}_{j}. Since S is free, Ker G is a free R -submodule of R^{M} . From the fact that Φ is non degenerate, it is easy to see that Ker F = Ker G and that the following diagram is commutative :

0 ⟶ Ker F ⟶ R^{M} ⟶^{F} Im F ⟶ 0
id ↓  id ↓  φ ↓
0 ⟶ Ker G ⟶ R^{M} ⟶^{G} S ⟶ 0

where φ is an isomorphism. In particular, Im F is also a free R -module. From [22, Theorem 13], one has

deg Φ(\overline{a}_{i}, \overline{a}_{j}) = deg σ(\overline{a}_{i}\overline{a}_{j}) ≤ deg(V)(1+max\{deg(a_{i}a_{j}), (n−r)d\}) ≤ deg(V)(1+2(n−r)(d−1))

(where V is the set of all the common zeros of f_{1}, …, f_{n−r}). By means of Bezout Inequality we deduce :

deg(F) = max_{i,j}\{deg Φ(\overline{a}_{i}, \overline{a}_{j})\} ≤ d^{n−r}(1 + 2(n − r)(d − 1)).

Applying Theorem 19 to the matrix F we obtain a basis for Ker F of degrees of order d^{O((n−r)r^{3})} and then, a basis for Im F of degrees of order d^{O((n−r)r^{4})} . Through φ we get a basis for S with the same degree upper bounds.

References

[1] Alonso M., Becker E., Roy M.-F., Wörmann T. : Zeros, Multiplicities and Idempotents for Zerodimensional Systems.- Effective Methods in Alg. Geom. (MEGA ’94), Progress in Math. 143, Birkhäuser Verlag (1996)

[2] Armendáriz I., Solernó P. : On the computation of the radical of polynomial complete intersection ideals.- Appl. Algebra, Algebraic Algorithms and Error-Correcting Codes (G.Cohen, M.Giusti & T.Mora, eds.), Lect. Notes Comp. Sci. 948 Springer-Verlag (1995) 106-119.

[3] Berenstein C., Struppa D. : Recent improvements in the Complexity of the Effective Nullstellensatz.- Linear Algebra and its Appl. 157 (1991) 203-215.

[4] Bruns W., Vetter U. : Determinantal Rings.- Springer Lect. Notes in Math. 1327 (1988).

[5] Caniglia L., Cortiñas G., Danón S., Heintz J., Krick T., Solernó P. : Algorithmic aspects of Suslin’s Proof of Serre’s Conjecture.- Comput. Complexity 3, Birkhäuser (1993) 31-55.

[6] Cardinal J.-P. : Dualité et algorithmes itératifs pour la résolution de systèmes polynomiaux.- Thesis Université de Rennes (1993).

[7] Demazure M. : Le monoïde Mayr et Meyer.- Notes Informelles de Calcul Formel, Ecole Polytechnique, Palaiseau (1984).

[8] Eisenbud D. : Commutative Algebra with a view toward Algebraic Geometry.- Graduate Texts in Math. 150, Springer-Verlag (1994).

[9] Fitchas N., Galligo A. : Nullstellensatz effectif et Conjecture de Serre (théorème de Quillen-Suslin) pour le Calcul Formel.- Math. Nachr. 149 (1990) 231-253.

[10] Gantmacher F. : Matrix Theory, Vol.I .- Chelsea Publ. Co., New York (1960).

[11] Giusti M., Heintz J., Morais J., Morgenstern J., Pardo L. : Straight-line Programs in Geometric Elimination Theory.- J. Pure and Appl. Algebra (1997).

[12] Giusti M., Heintz J., Sabia J. : On the efficiency of effective Nullstellensatz.- Comput. Complexity 3 Birkhäuser (1993) 56-95.

[13] Kollár J. : Sharp effective Nullstellensatz.- J. Am. Math. Soc. 1 (1988) 963-975.

[14] Krick T., Pardo L. : A computational Method for Diophantine Approximation.- Effective Methods in Alg. Geom. (MEGA ’94), Progress in Math. 143, Birkhäuser Verlag (1996) 193-253.

[15] Kunz E. : Introduction to Commutative Algebra and Algebraic Geometry.- Birkhäuser (1985).

[16] Kunz E. : Kähler Differentials.- Adv.Lect. in Math. Vieweg Verlag (1986).

[17] Lam T. : Serre’s Conjecture.- Springer LN Math. 635 Springer-Verlag (1978).

[18] Logar A., Sturmfels B. : Algorithms for Quillen-Suslin Theorem.- J. Algebra 145 (1992) 231-239.

[19] Lombardi H. : La structure d’un module projectif de type fini et le contenu constructif d’un principe local-global.- Preprint (1996).

[20] Mayr E., Meyer A. : The complexity of the word problem for commutative semigroups and polynomial ideals.- Adv. in Math. 46 (1982) 305-329.

[21] Rossi F., Spangher W. : Some effective methods in the openness of loci for Cohen-Macaulay and Gorenstein properties.- Effective Methods in Alg. Geom. (MEGA ’90) (T.Mora & C.Traverso, eds.), Progress in Math. 94, Birkhäuser (1990) 441-455.

[22] Sabia J., Solernó P. : Bounds for traces in Complete Intersections and Degrees in the Nullstellensatz.- AAECC Journal 6, No.6, Springer-Verlag (1995) 353-376.

[23] Teissier B.: Résultats récents d’algèbre commutative effective.- Séminaire Bourbaki 1989-1990, Astérisque vol 189-190 (1991) 107-131.