Suslin’s algorithms for reduction of unimodular rows

Henri Lombardi^{a},

aLaboratoire de Mathématiques, UMR CNRS 6623, UFR des Sciences et Techniques, Université de Franche-Comté, 25030 BESANCON cedex, FRANCE

Ihsen Yengui^{b}

bDépartement de Mathématiques, Faculté des Sciences de Sfax, 3018 Sfax, TUNISIA

Abstract

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 γ_{1}, …, γ_{ℓ} ∈ E_{n−1}(A[X]) such that the ideal generated by Res(v_{1}, e_{1}.γ_{1} ^{t}(v_{2}, …, v_{n})), …, Res(v_{1}, e_{1}.γ_{ℓ} ^{t}(v_{2}, …, v_{n})) equals A. This lemma played a central role in the resolution of Serre’s conjecture. In case A contains a set E of cardinality greater than deg v_{1} + 1 such that y − y′ is invertible for each y ≠ y′ in E, we prove that the γ_{i} can simply correspond to the elementary operations L_{1} → L_{1} + y_{i} ∑_{j=2}^{n−1} u_{j+1}L_{j}, 1 ≤ i ≤ ℓ = deg v_{1} + 1, where u_{1}v_{1} + ⋯ + u_{n}v_{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 case 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.

Key words: Quillen-Suslin’s Theorem, Suslin’s Stability Theorem, Constructive Mathematics, Computer Algebra. 1991 MSC: 13C10, 19A13, 14Q20, 03F65

Email addresses: henri.lombardi@univ-fcomte.fr (Henri Lombardi),

ihsen.yengui@fss.rnu.tn. (Ihsen Yengui).
  URL: http://hlombardi.free.fr/ (Henri Lombardi).

Preprint submitted to Elsevier Science 16 January 2005

1 Introduction

One principal motivation is to obtain a constructive proof of a lemma of Suslin which played a central role in the Suslin’s solution of Serre’s conjecture.

Sulsin’s Lemma (Suslin, 1977, Lemma 2.3) Let A be a commutative ring A and (v_{1}(X), …, v_{n}(X)) ∈ (A[X])^{n} a unimodular row with v_{1} monic and n ≥ 3. Then there exist finitely many γ_{i} ∈ E_{n−1}(A[X]) such that

⟨Res(v_{1}, e_{1}.γ_{i} ^{t}(v_{2}, …, v_{n})) | 1 ≤ i ≤ ℓ⟩ = A.

where e_{1}.x is the first coordinate of x ∈ A^{n}.

In case A contains a set E of cardinality greater than deg v_{1}+1 such that y−y′ is invertible for each y ≠ y′ in E, we prove that the γ_{i} can simply correspond to the elementary operations

L_{1} → L_{1} + y_{i} ∑_{j=2}^{n−1} u_{j+1}L_{j}, 1 ≤ i ≤ ℓ = deg v_{1} + 1,

where the u_{j} ∈ A[X] satisfy u_{1}v_{1} + ⋯ + u_{n}v_{n} = 1. These efficient elementary operations enable us to give a new and simple algorithm for reducing unimodular columns with entries in K[X_{1}, …, X_{k}] to ^{t}(1, 0, …, 0) using elementary operations in case K is an infinite field.

We think that this kind of operations may bring useful simplifications to the existing algorithms for the Quillen-Sulin and Suslin’s stability theorems based on unimodular completion and will facilitate their implementation (Fitchas and Galligo, 1990; Logar and Sturmfels, 1992; Park and Woodburn, 1995).

The undefined terminology is standard as in Kunz (1991); Lam (1978).

2 Efficient elementary operations

The following theorem gives under a stronger hypothesis a more precise formulation of Suslin’s lemma.

Theorem 1 (Suslin’s Lemma, particular case) Let A be a commutative ring, V, v, U, u, w ∈ A[X] such that V v + Uu + w = 1 and v is monic. Denote ℓ = deg v + 1 and suppose that A contains a set E = {y_{1}, …, y_{ℓ}} such that y_{i} − y_{j} is invertible for each i ≠ j. For each 1 ≤ i ≤ ℓ, denoting r_{i} = Res(v, u + y_{i}w), then ⟨r_{1}, …, r_{ℓ}⟩ = A, that is, there exist α_{1}, …, α_{ℓ} ∈ A such that α_{1}r_{1} + ⋯ + α_{ℓ}r_{ℓ} = 1.

Furthermore, supposing that A is a polynomial ring in a finite number of variables over a basic ring B and that deg V, deg U ≤ D, 1+deg v, 1+deg u ≤ d (where d ≥ 2) and deg w ≤ d + D, then for each 1 ≤ i ≤ ℓ, deg(α_{i}) ≤ \frac{d^{4}}{4} (\frac{d}{2} + D + 1)^{2} and deg(α_{i}r_{i}) ≤ \frac{d^{4}}{4} (d + D + 1)^{2} (here, by degree we mean total degree).

Proof Let Z_{1}, …, Z_{ℓ} be ℓ indeterminates over A and denote

I = ⟨v(Z_{i}), u(Z_{i}) + y_{i}w(Z_{i}) | 1 ≤ i ≤ ℓ⟩, A_{ℓ} = A[Z_{1}, …, Z_{ℓ}]/I .

First we prove that 1 = 0 in A_{ℓ}.

Observe that for i ≠ j, (y_{i} − y_{j})w(Z_{i}) ∈ ⟨Z_{i} − Z_{j}⟩ + I. Indeed,

(y_{i}−y_{j})w(Z_{i}) = (y_{i}w(Z_{i})+u(Z_{i}))−(y_{j}w(Z_{j})+u(Z_{j}))+(u(Z_{j})−u(Z_{i}))+y_{j}(w(Z_{j})−w(Z_{i})).

Since y_{i} − y_{j} is invertible, w(Z_{i}) ∈ ⟨Z_{i} − Z_{j}⟩ + I. Thus,

u(Z_{i}) = −y_{i} w(Z_{i}) + (u(Z_{i}) + y_{i}w(Z_{i})) ∈ ⟨Z_{i} − Z_{j}⟩ + I.

Since v(Z_{i}) ∈ I and V v +Uu+w = 1, we get 1 ∈ ⟨Z_{i} − Z_{j}⟩+I, that is Z_{i} −Z_{j} is invertible in A_{ℓ}. On the other hand, by clearing the denominators in the Lagrange interpolation formula, we obtain

v(X) (∏_{i≠j}(Z_{i} − Z_{j})) ∈ ⟨v(Z_{1}), …, v(Z_{ℓ})⟩ ⊆ A[Z_{1}, …, Z_{ℓ}][X]

(here we need the hypothesis ℓ = deg v + 1).

In A_{ℓ}, ∏_{i≠j}(Z_{i} − Z_{j}) is invertible, v(Z_{1}) = ⋯ = v(Z_{ℓ}) = 0, thus v(X) = 0 in A_{ℓ}[X]. Since v is monic, we obtain 1 = 0 in A_{ℓ}, that is 1 ∈ I.

For 0 ≤ k ≤ ℓ, denote I_{k} = ⟨v(Z_{i}), u(Z_{i}) + y_{i}w(Z_{i}) | 1 ≤ i ≤ k⟩, J_{k} = I_{k} + ⟨r_{i} | k < i ≤ ℓ⟩ and A_{k} = A[Z_{1}, …, Z_{k}]/I_{k}. Note that I_{ℓ} = I, so 1 ∈ I_{ℓ} = J_{ℓ}. Using Lemma 2 below we get by induction on k from ℓ to 0 that 1 ∈ J_{k}: in order to go from k +1 to k consider the ring B_{k} = A[Z_{1}, …, Z_{k}]/⟨r_{k+2}, …, r_{ℓ}⟩ and apply the lemma with X = Z_{k+1}, a = v(Z_{k+1}), b = u(Z_{k+1})+y_{k+1}w(Z_{k+1}). So 1 ∈ J_{0} = ⟨r_{ℓ}, …, r_{1}⟩.

For the degree bounds, as seen above, for i ≠ j, we can write (y_{i} − y_{j})w(Z_{i}) in the form

(y_{i} − y_{j})w(Z_{i}) = (Z_{i} − Z_{j})A_{i,j} + B_{i,j},

where A_{i,j} ∈ A[Z_{1}, …, Z_{ℓ}], B_{i,j} ∈ I, deg ((Z_{i}−Z_{j})A_{i,j}) ≤ d+D, and deg B_{i,j} ≤ d + D.

In the same way, we can write (y_{i} − y_{j})u(Z_{i}) in the form

(y_{i} − y_{j})u(Z_{i}) = (Z_{i} − Z_{j})C_{i,j} + D_{i,j},

where C_{i,j} ∈ A[Z_{1}, …, Z_{ℓ}], D_{i,j} ∈ I, deg ((Z_{i}−Z_{j})C_{i,j}) ≤ d+D, and deg D_{i,j} ≤ d + D.

Thus, since y_{i} −y_{j} = (y_{i} −y_{j})V (Z_{i})v(Z_{i})+(y_{i} −y_{j})U(Z_{i})u(Z_{i})+(y_{i} −y_{j})w(Z_{i}), we have:

1 = (Z_{i} − Z_{j})E_{i,j} + F_{i,j},

where E_{i,j} ∈ A[Z_{1}, …, Z_{ℓ}], F_{i,j} ∈ I, deg ((Z_{i} − Z_{j})E_{i,j}) ≤ d + 2D, and deg F_{i,j} ≤ d + 2D.

Hence, we have an identity of the form:

(∏_{i≠j}(Z_{i} − Z_{j})) A = 1 + B,

where A ∈ A[Z_{1}, …, Z_{ℓ}], B ∈ I, deg A ≤ \binom{d}{2}(d + 2D) ≤ d^{2}(\frac{d}{2} + D), and

deg B ≤ \binom{d}{2}(d + 2D) ≤ d^{2}(\frac{d}{2} + D).

Multiplying the Lagrange interpolation formula by A, we obtain an identity of the form:

v(X) = −Bv(X) + A (v(Z_{1})g_{1} + ⋯ + v(Z_{ℓ})g_{ℓ}),

where g_{i} ∈ A[Z_{1}, …, Z_{ℓ}, X], and deg g_{i} ≤ d.

By identifying the leading coefficients in both sides, since v is monic and B, v(Z_{1}), …, v(Z_{ℓ}) ∈ I, we obtain an identity of the form:

1 = θ_{1} + ⋯ + θ_{m},

where θ_{i} ∈ I, and deg θ_{i} ≤ 2d + d^{2}(\frac{d}{2} + D) ≤ d^{2}(\frac{d}{2} + D + 1) (d ≥ 2).

Applying Lemma 2 and following the proof above, there exists α_{ℓ} ∈ A_{ℓ−1} and γ_{ℓ} ∈ I_{ℓ−1} such that α_{ℓ}r_{ℓ} + γ_{ℓ} = 1, with deg (α_{ℓ}) ≤ \frac{d^{4}}{4} (\frac{d}{2} + D + 1)^{2}, and so on, we find that for each 1 ≤ i ≤ ℓ, deg (α_{i}) ≤ \frac{d^{4}}{4} (\frac{d}{2} + D + 1)^{2}.

More explicitly, using the equality 1 = θ_{1} + ⋯ + θ_{m}, we can write

1 = v(Z_{ℓ})γ_{1,ℓ} + (u(Z_{ℓ}) + y_{ℓ}w(Z_{ℓ}))γ_{2,ℓ} + γ_{ℓ},

where γ_{i,ℓ} ∈ A[Z_{1}, …, Z_{ℓ}], γ_{ℓ} ∈ I_{ℓ−1}, deg(v(Z_{ℓ})γ_{1,ℓ}), deg((u(Z_{ℓ})+y_{ℓ}w(Z_{ℓ}))γ_{2,ℓ}), deg γ_{ℓ} ≤ d^{2}(\frac{d}{2} + D + 1).

By Lemma 2, we have

r_{ℓ} Res_{Z_{ℓ}}(v(Z_{ℓ}), γ_{2,ℓ}) = Res_{Z_{ℓ}}(v(Z_{ℓ}), 1 − γ_{ℓ}) = 1 − γ_{ℓ}.

Thus, it suffices to take α_{ℓ} = Res_{Z_{ℓ}}(v(Z_{ℓ}), γ_{2,ℓ}) so that r_{ℓ}α_{ℓ} + γ_{ℓ} = 1. Now, let us explain how to pass from step k + 1 to step k. Suppose that we have already found an equality of the form

α_{ℓ}r_{ℓ} + ⋯ + α_{k+1}r_{k+1} + γ_{k+1} = 1,

where γ_{k+1} ∈ I_{k}. Write

γ_{k+1} = v(Z_{k})γ_{1,k} + (u(Z_{k}) + y_{k}w(Z_{k}))γ_{2,k} + γ_{k},

where γ_{i,k} ∈ A[Z_{1}, …, Z_{k}], γ_{k} ∈ I_{k−1}, and deg(v(Z_{k})γ_{1,k}), deg((u(Z_{k}) + y_{k}w(Z_{k}))γ_{2,k}), deg γ_{k} ≤ d^{2}(\frac{d}{2} + D + 1).

Since r_{k} Res_{Z_{k}}(v(Z_{k}), γ_{2,k}) = 1 − α_{ℓ}r_{ℓ} − ⋯ − α_{k+1}r_{k+1} − γ_{k}, it suffices to take α_{k} = Res_{Z_{k}}(v(Z_{k}), γ_{2,k}).

Moreover, since deg r_{i} ≤ d(d + D), then

deg (α_{i}r_{i}) ≤ \frac{d^{4}}{4} (\frac{d}{2} + D + 1)^{2} + d(d + D) ≤ \frac{d^{4}}{4} (d + D + 1)^{2}.

Indeed, \frac{d^{4}}{4} (d + D + 1)^{2} − \frac{d^{4}}{4} (\frac{d}{2} + D + 1)^{2} − d(d + D) = \frac{d}{4}(\frac{3}{4}d^{5} + (d^{4} − 4)D + d(d^{3} − 4)) ≥ 0.

□

Lemma 2 (basic elimination lemma) Let a, b ∈ B[X] with a monic. Then

⟨a, b⟩ = ⟨1⟩ in B[X] ⟺ ⟨Res_{X}(a, b)⟩ = ⟨1⟩ in B

More precisely if ca + db = 1 in B[X] then Res(a, b) Res(a, d) = 1 in B. Furthermore, supposing that B is a polynomial ring in a finite number of variables over a basic ring A, deg(a) ≤ δ and deg(d) ≤ δ_{1}, then deg(Res(a, d)) ≤ δδ_{1}. In particular, if deg(ad) ≤ δ′, then deg(Res(a, d)) ≤ \frac{δ^{′2}}{4} .

Proof Since a is monic, we have Res(a, db) = Res(a, d) Res(a, b) and

Res(a, db) = Res(a, ca + db) = Res(a, 1) = 1.

The fact that deg(Res(a, d)) ≤ δδ_{1} is classical. □

The following formulation of Theorem 1 will be the main key mathematical result used in the algorithm for unimodular reduction.

Corollary 3 Let A be a commutative ring, v_{1}, …, v_{n}, u_{1}, …, u_{n} ∈ A[X] such that u_{1}v_{1} + ⋯ + u_{n}v_{n} = 1, v_{1} is monic and n ≥ 3. Denote ℓ = deg v_{1} + 1 and suppose that A contains a set E = {y_{1}, …, y_{ℓ}} such that y_{i}−y_{j} is invertible for each i ≠ j. For each 1 ≤ i ≤ ℓ, denoting r_{i} = Res(v_{1}, v_{2} + y_{i} ∑_{j=3}^{n} u_{j}v_{j}), then ⟨r_{1}, …, r_{ℓ}⟩ = A, that is, there exist α_{1}, …, α_{ℓ} ∈ A such that α_{1}r_{1}+⋯+α_{ℓ}r_{ℓ} = 1.

Furthermore, supposing that A is a polynomial ring in a finite number of variables over a basic ring B, 1 + max_{1≤i≤n}{deg v_{i}} = d (where d ≥ 2), and max_{1≤i≤n}\{deg u_{i}\} = D, then for each 1 ≤ i ≤ ℓ, deg(α_{i}r_{i}) ≤ \frac{d^{4}}{4} (d + D + 1)^{2}.

Proof Let v = v_{1}, u = v_{2}, w = u_{3}v_{3} + ⋯ + u_{n}v_{n} and apply Theorem 1. □

Remark. The second author has given in Yengui (2004) a general constructive proof of the lemma of Suslin cited in the introduction without any restriction on the ring A. With the degree bounds and notations of Corollary 3, the general constructive proof involves 2^{d} matrices γ_{j} in E_{n−1}(A[X]), the subgroup of SL_{n−1}(A[X]) generated by elementary matrices, instead of d in Corollary 3. Moreover, in the general constructive proof, each γ_{j} is the product of at most 2d elementary matrices while in Corollary 3 it is the product of n − 2 elementary matrices.

3 Reduction of unimodular rows

For any ring A and n ≥ 1, Um_{n}(A) denotes the set of unimodular rows in A, that is Um_{n}(A) = {(x_{1}, …, x_{n}) ∈ A^{n} such that ⟨x_{1}, …, x_{n}⟩ = A}. E_{n}(A) denotes the subgroup of SL_{n}(A) generated by elementary matrices. For i ≠ j, E_{i,j}(a) is the matrix corresponding to the elementary operation L_{i} → L_{i}+aL_{j}.

From now on, we suppose that n is an integer ≥ 3. All the considered matrices are square of size n.

The algorithms are based on Lombardi and Quitté (2003) and on Theorem 1.

An algorithm for unimodular completion: general case.

Input: Two columns V = V(X) = ^{t}(v_{1}(X), …, v_{n}(X)), U = U(X) = t(u_{1}(X), …, u_{n}(X)) ∈ A[X]^{n} such that v_{1} is monic and V^{t}U = 1. We assume the “size” of an element a ∈ A is measured by deg(a) ∈ ℕ, the function deg sharing the usual properties of a total degree function in a polynomial ring: deg(a + b) ≤ max(deg(a), deg(b)), deg(ab) ≤ deg(a) + deg(b). We assume 1 + max_{1≤i≤n}{deg v_{i}} ≤ d (where d ≥ 2) and max_{1≤i≤n}{deg u_{i}} ≤ D. We assume the ring A integral and contains infinitely many y_{i} of degree 0 such that y_{i} − y_{j} is invertible for i ≠ j.

Output: A matrix M in SL_{n}(A[X]) such that MV = ^{t}(1, 0, …, 0).

Step 1: For 1 ≤ i ≤ ℓ = deg_{X} v_{1} + 1, set w_{i} := v_{2} + y_{i}(u_{3}v_{3} + ⋯ + u_{n}v_{n}), compute r_{i} := Res_{X}(v_{1}, w_{i}) and find α_{1}, …, α_{ℓ} ∈ A such that α_{1}r_{1} + ⋯ + α_{ℓ}r_{ℓ} = 1 (here we use the constructive proof of Theorem 1).

For 1 ≤ i ≤ ℓ, compute f_{i}, g_{i} ∈ A[\underline{X}] such that f_{i}v_{1} + g_{i}w_{i} = r_{i}.

Step 2: For 1 ≤ i ≤ ℓ,

\begin{matrix}H_{i} := E_{n,1}(−1)E_{1,n}(1)E_{n−1,n}(−v_{n−1}) ⋯ E_{3,n}(−v_{3})E_{2,n}(−w_{i})E_{1,n}(−v_{1}) \\ E_{n,2}(−r_{i}^{−1}(v_{n} − 1)g_{i})E_{n,1}(−r_{i}^{−1}(v_{n} − 1)f_{i})E_{2,n}(y_{i}u_{n}) ⋯ E_{2,3}(y_{i}u_{3}). \end{matrix}

(Comment: Of course, we consider only the r_{i} which are nonzero and we have H_{i}V = ^{t}(1, 0, …, 0)).

Set H̃_{i} := H_{i}(0)^{−1}H_{i}(X) so that H̃_{i}V(X) = V(0).

Note that the coefficients of H_{i} are in the module A[X]\frac{1}{r_{i}} and those of H̃_{i} are in A[X]\frac{1}{r_{i}^{2}} .

Step 3: For 1 ≤ i ≤ ℓ, find k_{i} ∈ ℕ and G_{i} ∈ SL_{n}(A[X, Y]) such that G_{i}V(X + r_{i}^{k_{i}}Y) = V(X) (see Lombardi and Quitté, 2003, Lemma 15).

In more details,

H̃_{i}(X) V(X) = V(0) = H̃_{i}(X + r_{i}^{2n}Y) V(X + r_{i}^{2n}Y),

and so

H̃_{i}(X)^{−1} H̃_{i}(X + r_{i}^{2n}Y) V(X + r_{i}^{2n}Y) = V(X).

Thus, we take k_{i} = 2n and G_{i} = H̃_{i}(X)^{−1} H̃_{i}(X + r_{i}^{2n}Y).

Moreover, since all the coefficients of r_{i}^{2}H̃_{i} are in A[X, Y] then G_{i} ∈ SL_{n}(A[X, Y]) (see Lemma 4).

To sum up, the main properties of G_{i} are

\{ \begin{matrix}G_{i} ∈ SL_{n}(A[X, Y]) \\ G_{i}V(X + r_{i}^{2n}Y) = V(X). \end{matrix}

Step 4: Find G̃ = G̃(X, Y) ∈ SL_{n}(A[X, Y]) such that G̃V(X + Y) = V(X).

More precisely, let β_{1}, …, β_{ℓ} ∈ A such that β_{1}r_{1}^{2n} + ⋯ + β_{ℓ}r_{ℓ}^{2n} = 1 (β_{1}, …, β_{ℓ} are deduced from the identity (α_{1}r_{1} + ⋯ + α_{ℓ}r_{ℓ})^{2nℓ} = 1).

Set

G̃ = ∏_{i=2}^{ℓ} G_{i}(X + (β_{1}r_{1}^{2n} + ⋯ + β_{i−1}r_{i−1}^{2n})Y, β_{i}Y).

Remark that

G_{ℓ}(X + (β_{1}r_{1}^{2n} + ⋯ + β_{ℓ−1}r_{ℓ−1}^{2n})Y, β_{ℓ}Y) V(X + Y)

= G_{ℓ}(X + (β_{1}r_{1}^{2n} + ⋯ + β_{ℓ−1}r_{ℓ−1}^{2n})Y, β_{ℓ}Y) V(X + (β_{1}r_{1}^{2n} + ⋯ + β_{ℓ−1}r_{ℓ−1}^{2n})Y + β_{ℓ}r_{ℓ}^{2n}Y)

= V(X + (β_{1}r_{1}^{2n} + ⋯ + β_{ℓ−1}r_{ℓ−1}^{2n})Y),

and so on until getting

G̃V(X + Y) = V(X).

Step 5: G := G̃(0, X).

(Comment: Since G̃V(X + Y) = V(X), then GV(X) = V(0)).

For sake of completeness, we add the following lemma which is a more precise formulation of a lemma originally given in Lombardi and Quitté (2003) and was used in Step 3 of the above algorithm.

Lemma 4 (Lombardi and Quitté, 2003, Lemma 15) Let A be an integral domain, b ∈ A, H(X) ∈ SL_{n}(A[\frac{1}{b}][X]) such that b^{m}H(X) ∈ M_{n}(A[X]) for some m ∈ ℕ. Then

H(X + b^{mn}Y)H(X)^{−1} ∈ SL_{n}(A[X, Y]).

So, with the notations of the algorithm for unimodular completion, we get the following complexity bounds.

Proposition 5 (complexity bounds, 1) The matrix G is the product of at most d matrices in SL_{n}(A[X]) obtained as the product of at most 4d(2n + 1) = O(n d) elementary matrices M_{i} ∈ M_{n}(A[X]\frac{1}{r_{i}}) where r_{i} = Res_{X}(v_{1}(X), w_{i}(X)), 1 ≤ i ≤ deg_{X} v_{1} + 1, and w_{i} = v_{2} + y_{i}(u_{3}v_{3} + ⋯ + u_{n}v_{n}). Moreover,

deg G ≤ 2(\frac{1}{2}nd^{5}(d+D+1)^{2} +1)d^{2}(d+D)^{2}(2nd(d+D)+1) = O(n^{2}d^{8}(d+D)^{5})

and the sequential complexity of this algorithm amounts to O(n^{4}d) arithmetic operations in A on elements of degree bounded by O(n^{2}d^{8}(d + D)^{5}).

Proof

In Step 1: deg w_{i} ≤ d + D, deg(α_{i}r_{i}) ≤ \frac{d^{4}}{4} (d + D + 1)^{2} (see Corollary 3), deg f_{i} ≤ d + D and deg g_{i} ≤ d.

In Step 2: H_{i} is the product of 2n + 1 elementary matrices in M_{n}(A[X]\frac{1}{r_{i}}), r_{i}H_{i} ∈ M_{n}(A[X]) and deg(r_{i}H_{i}) ≤ d(d+D)^{2}. Thus, H̃_{i} is the product of 2(2n+ 1) elementary matrices in M_{n}(A[X]\frac{1}{r_{i}}) , r_{i}^{2}H̃_{i} ∈ M_{n}(A[X]) and deg(r_{i}^{2}H̃_{i}) ≤ 2d(d + D)^{2}.

In Step 3: G_{i} is the product of 4(2n + 1) elementary matrices in M_{n}(A[X]\frac{1}{r_{i}}). Moreover,

deg(r_{i}^{2}H̃_{i}(X + r_{i}^{2n}Y)) ≤ 2d(d + D)^{2}(2nd(d + D))

and

deg(r_{i}^{2}H̃_{i}(X))^{−1} ≤ 2d(d + D)^{2}.

Thus,

deg G_{i} ≤ 2d(d + D)^{2}(2nd(d + D) + 1).

In Step 4: deg(β_{i}r_{i}^{2n}) ≤ 2n\frac{d^{5}}{4} (d + D + 1)^{2} = \frac{1}{2}nd^{5}(d + D + 1)^{2},

deg G_{i}(X + (β_{1}r_{1}^{2n} + ⋯ + β_{i−1}r_{i−1}^{2n})Y, β_{i}Y) ≤

(\frac{1}{2}nd^{5}(d + D + 1)^{2} + 1) 2d(d + D)^{2}(2nd(d + D) + 1).

Thus,

deg G̃ ≤ (\frac{1}{2}nd^{5}(d+D+1)^{2}+1)2d^{2}(d+D)^{2}(2nd(d+D)+1) = O(n^{2}d^{8}(d+D)^{5}).

Moreover, G̃ is the product of at most 4d(2n + 1) elementary matrices in M_{n}(A[X]\frac{1}{r_{i}}).

Of course, for the complexity of this algorithm, we did not consider the possibility of a fast matrix multiplication process. □

Note that, contrary to the papers Logar and Sturmfels (1992); Park and Woodburn (1995), our algorithm for unimodular reduction does not use the fact that the basic ring is Noetherian.

An algorithm for unimodular completion: case of K[X_{1}, …, X_{k}] where K is an infinite field.

In the following algorithm K will denote an infinite field (e.g. Char K = 0), with an infinite sequence of pairwise distinct elements (y_{i}).

We also use \underline{X} = (X_{1}, …, X_{k}).

Input: Two columns V = V(\underline{X}) = ^{t}(v_{1}(\underline{X}), …, v_{n}(\underline{X})), U = U(\underline{X}) = t(u_{1}(\underline{X}), …, u_{n}(\underline{X})) ∈ K[\underline{X}]^{n} such that V^{t}U = 1, with 1+max_{1≤i≤n}\{deg v_{i}\} = d (where d ≥ 2) and max_{1≤i≤n}{deg u_{i}} = D.

Output: A matrix M in SL_{n}(K[\underline{X}]) such that MV = ^{t}(1, 0, …, 0).

For j from k to 1 perform steps 1 and 2:

Step 1: Make a linear change of variables so that v_{1} becomes monic at X_{j}.

Step 2 Perform the general algorithm with A = K[X_{1}, …, X_{j−1}] and X = X_{j}. Output the new V and U.

Note that if D is deduced from d by the effective Nullstellensatz Fitchas and Galligo (1990), that is if only V = V(\underline{X}) = ^{t}(v_{1}(\underline{X}), …, v_{n}(\underline{X})) ∈ Um_{n}(K[\underline{X}]) is given as input, then D = d^{k}.

So we get the following complexity bounds. In Proposition 6 we treat the case where both of V and U are given as input as well as the case where only V is given as input.

Proposition 6 (complexity bounds, 2)

(1) The matrix G obtained after the first iteration (that is, after eliminating X_{k}) is the product of at most d matrices in SL_{n}(K[\underline{X}]) obtained as the product of at most 4d(2n + 1) = O(n d) elementary matrices M_{i,k} ∈ M_{n}(K[\underline{X}]\frac{1}{r_{i,k}}) where r_{i,k} = Res_{X_{k}}(v_{1}(\underline{X}), w_{i}(\underline{X})), 1 ≤ i ≤ deg_{X_{k}} v_{1} + 1, and w_{i} = v_{2} + y_{i}(u_{3}v_{3} + ⋯ + u_{n}v_{n}). Moreover,

deg G ≤ 2(\frac{1}{2}nd^{5}(d+D+1)^{2}+1)d^{2}(d+D)^{2}(2nd(d+D)+1) = O(n^{2}d^{8}(d+D)^{5})

and the sequential complexity of this algorithm amounts to (nd(d+D))^{O(k)} = (nd)^{O(k^{2})} field operations in K.

(2) The final matrix M obtained after k iterations is the product of at most dk matrices in SL_{n}(K[\underline{X}]) obtained as the product of at most 4dk(2n + 1) = O(k n d) elementary matrices M_{i,j} ∈ M_{n}(K[\underline{X}]\frac{1}{r_{i,j}}) where

r_{i,j} = Res_{X_{j}}(v_{1}(X_{1}, …, X_{j}, 0, …, 0), w_{i}(X_{1}, …, X_{j}, 0, …, 0)), 1 ≤ i ≤ deg_{X_{j}} v_{1}(X_{1}, …, X_{j}, 0, …, 0) + 1, 1 ≤ j ≤ k and w_{i} = v_{2} + (i − 1)(u_{3}v_{3} + ⋯ + u_{n}v_{n}). Moreover,

deg M ≤ 2k(\frac{1}{2}nd^{5}(d+D+1)^{2}+1)d^{2}(d+D)^{2}(2nd(d+D)+1) = O(kn^{2}d^{8}(d+D)^{5})

and the sequential complexity of this algorithm amounts to (nd(d+D))^{O(k)} = (nd)^{O(k^{2})} field operations in K.

Proof. Note that V(X_{1}, …, X_{j−1}, 0)^{t}U(X_{1}, …, X_{j−1}, 0) = 1,

1 + max_{1≤i≤n}{deg v_{i}(X_{1}, …, X_{j−1}, 0)} ≤ d

and max_{1≤i≤n}{deg u_{i}(X_{1}, …, X_{j−1}, 0)} ≤ D. So it suffices to give the bound for Step 2 and to raise at the power k.

Since the product of two matrices in M_{n}(K[\underline{X}]) of degree ≤ d′ requires O(n^{3}(d′)^{2k}) field operations, we infer from Proposition 5 that the complexity of the algorithm computing G amounts to (nd(d + D))^{O(k)} (d′ = n^{2}d^{8}(d + D)^{5}). □

Remark.

1) As explained in Fitchas and Galligo (1990); Logar and Sturmfels (1992); Park and Woodburn (1995), our algorithm for unimodular completion can be used to obtain an algorithm for the Quillen-Suslin theorem. Precise bounds have been computed by some authors concerning algorithms for the Quillen-Suslin theorem based on Suslin’s proof of Serre’s Conjecture. The best bounds are given in Caniglia et al. (1993) and have been already announced in Fitchas and Galligo (1990). Note that in Caniglia et al. (1993), the authors treat globally unimodular matrices since treating a unimodular matrix column by column produces doubly exponential bounds. So, a comparison between our algorithm and theirs can only be made in the unimodular completion case. As mentioned in Caniglia et al. (1993), the orders of degree and complexity bounds they obtained cannot be improved. Contrary to the algorithms found in Caniglia et al. (1993) and Fitchas and Galligo (1990) which use essentially Suslin’s method Suslin (1977) (A transitivity theorem) and are similar to the formulation given below, our algorithm follows the concrete local-global principle descibed in Lombardi and Quitté (2003) and the form of the obtained factors is different. The main feature of our algorithm is its simplicity which will certainly facilitate its implementation and the fact that it considerably reduces the number of factors occuring in the computation of M. Moreover, by this algorithm, we show that the concrete local-global principles Lombardi and Quitté (2003) can produce competitive complexity bounds.

2) Another alternative would be to follow what Suslin did in Paragraph 2 (A transitivity theorem) of Suslin (1977). This has been explained constructively in Fitchas and Galligo (1990) (Theorem 15). With analogous calculation to what Fitchas and Galligo did in Fitchas and Galligo (1990), we can then obtain the following formulation and bounds (with a number of factors lower than the one obtained in Fitchas and Galligo (1990) and Caniglia et al. (1993), similar degree bound, and slightly better complexity bound):

Let K be an infinite field, V = ^{t}(v_{1}(\underline{X}), …, v_{n}(\underline{X})) ∈ Um_{n}(K[\underline{X}]) such that 1 + max_{1≤i≤n}{deg v_{i}} = d (where d ≥ 2). Then, there exists a matrix M ∈ SL_{n}(K[\underline{X}]) satisfying the following properties

(i) MV = ^{t}(1, 0, …, 0).

(ii) deg M = d^{O(k)}.

(iii) M has a representation M = N_{1} ⋯ N_{p} as a product of p ≤ 2knd matrices N_{h} ∈ K[\underline{X}]^{n×n}

such that for 1 ≤ h ≤ p, deg N_{h} = d^{O(k)}, N_{h} is an elementary matrix or has the form

( \begin{matrix}N′_{h} & 0 & ⋯ & 0 \\ 0 & 1 \\ ⋮ & & ... \\ 0 & & & 1 \end{matrix} )

with N′_{h} ∈ SL_{2}(K[\underline{X}]).

(iv) M can be computed in sequential time n^{3}d^{O(k^{2})}.

3) Using Corollary 3 and some classical steps used in Kunz (1991), Lam (1978), Lombardi and Quitté (2003), Park and Woodburn (1995), or Suslin (1977), we can obtain an algorithm for reducing unimodular rows by elementary matrices. As shown in Park and Woodburn (1995) (Section 4), an algorithm for the Suslin’s stability theorem (SL_{n}(K[\underline{X}]) = E_{n}(K[\underline{X}])) can be obtained by n − 3 iterations of this algorithm coupled with an algorithm for the Suslin’s stability theorem in the particular case the given unimodular matrix has the form

( \begin{matrix}p & q & 0 \\ r & s & 0 \\ 0 & 0 & 1 \end{matrix} ) ∈ SL_{3}(K[\underline{X}]),

where p is monic in the last variable X_{k}. Unfortunately, these iterations produce an explosion of the degree of the considered unimodular matrix and produce a double-exponential complexity.

References

Caniglia, L., Cortinas, G., Danon, S., Heintz, J., Krick, T., Solerno, P., 1993. Algorithmic aspects of Suslin’s proof of Serre’s conjecture. Comput. Complexity 3, 31–55.

Fitchas, N., Galligo, A., 1990. Nullstellensatz effectif et conjecture de Serre (théorème de Quillen-Suslin) pour le calcul formel. Math. Nachr. 149, 231– 253.

Kunz, E., 1991. Introduction to Commutative Algebra and Algebraic Geom-

etry. Birkhäuser. Lam, T., 1978. Serre’s conjecture. Vol. 635 of Lecture Notes in Mathematics.

Springer-Verlag, Berlin-New York. Logar, A., Sturmfels, B., 1992. Algorithms for the Quillen-Suslin Theorem. J.

Algebra 145 (1), 231–239. Lombardi, H., Quitté, C., 2003. Constructions cachées en algèbre abstraite (2)

le principe local-global. In: Fontana, M., Kabbaj, S.-E., Wiegand, S. (Eds.), Commutative ring theory and applications. Vol. 231 of Lecture notes in pure and applied mathematics. M. Dekker, pp. 461–476.

Park, H., Woodburn, C., 1995. An algorithmic proof of Suslin’s stability the-

orem for polynomial rings. J. Algebra 178, 277–298. Suslin, A., 1977. On the structure of the special linear group over polynomial

rings. Math. USSR-Izv. 11, 221–238. Yengui, I., 2004. Making the use of maximal ideals constructive, [preprint].