Fast Algorithms for Zero-Dimensional Polynomial Systems using Duality

Alin Bostan^{1}, Bruno Salvy^{2}, Éric Schost^{3}

1 Laboratoire STIX, École polytechnique, France and IMAR, Romania

              Alin.Bostan@stix.polytechnique.fr

2 Projet Algorithmes, Inria Rocquencourt, France

                     Bruno.Salvy@inria.fr

3 Laboratoire STIX, École polytechnique, France

              Eric.Schost@stix.polytechnique.fr

Abstract. Many questions concerning a zero-dimensional polynomial system can be reduced to linear algebra operations in the quotient algebra A = k[X_{1}, …, X_{n}]/I, where I is the ideal generated by the input system. Assuming that the multiplicative structure of the algebra A is (partly) known, we address the question of speeding up the linear algebra phase for the computation of minimal polynomials and rational parametrizations in A. We present new formulæ for the rational parametrizations, extending those of Rouillier, and algorithms extending ideas introduced by Shoup in the univariate case. Our approach is based on the A-module structure of the dual space Â. An important feature of our algorithms is that we do not require Â to be free and of rank 1. The complexity of our algorithms for computing the minimal polynomial and the rational parametrizations are O(2^{n}D^{5/2}) and O(n2^{n}D^{5/2}) respectively, where D is the dimension of A. For fixed n, this is better than algorithms based on linear algebra except when the complexity of the available matrix product has exponent less than 5/2.

Key words: Duality, polynomial system solving, linear recurrent sequences.

1 Introduction

Many questions concerning zero-dimensional polynomial systems can be reduced to linear algebra operations in some quotient algebra. Assuming that the multiplicative structure of this algebra is (partly) known, we address the question of speeding up the linear algebra phase for two questions.

Specifically, let k be a field, \overline{k} its algebraic closure and I a zero-dimensional ideal of k[X_{1}, …, X_{n}]. Let V(I) ⊂ \overline{k}^{n} be the zero-set of the polynomial system defined by I. Given an element u of A = k[X_{1}, …, X_{n}]/I, we consider the following problems:

1. compute its minimal polynomial m_{u}, that is, the (unique) monic univariate polynomial of minimal degree such that m_{u}(u) = 0 in A; 2. if u separates the points of V(I) (see definition below), compute parametriza-

tions expressing the coordinates of these points in terms of u.

We suppose that k is a perfect field. This discards many pathologies such as algebraic field extensions of k without a primitive element. In most applications we have in mind, k is finite or of characteristic zero, so this assumption is satisfied.

The computation of minimal polynomials of elements in such quotient algebras is of particular interest when A is a field or a product of fields. This question appears as a basic subroutine for the computation of triangular sets [40], for the study of the intermediate fields between k and A [41], in Galois theory [3], … For instance, starting from a description of a quotient algebra by means of a Gröbner basis, Lazard’s algorithm Triangular [40] produces a “triangular description” of the input ideal through repeated minimal polynomial computations.

In the noncommutative setting of the effective theory of D-modules, an important role is played by the b-function of a holonomic system of linear partial differential equations. Algorithm 5.1.5 in [61] reduces the computation of the b-function to that of the minimal polynomial of an element in a quotient algebra of the type we consider here.

Another of our initial motivations is the study of algebraic curves and cryptosystems built upon them. Factorization patterns of the minimal polynomials of well-chosen elements help determine the cardinality of the Jacobian of hyperelliptic curves over finite fields, see [15, 23, 64, 24]. In such situations, the element u will typically not be primitive for k → A. The polynomial m_{u} has degree less than the dimension of A, and of course we want to make use of this fact.

Our second interest is the determination of a parametrization of the coordinates of the solutions of I. To this effect, we say that u ∈ A separates the points of V(I), or is a separating element for I, if for all points P ≠ P′ in V(I), u takes distinct values on P and P′ (see [1, 60]). Since k is a perfect field, this is the case if and only if u is a primitive element of the reduced algebra A_{red} = k[X_{1}, …, X_{n}]/\sqrt{I}, where \sqrt{I} is the radical of I, see [5]. In this situation, the coordinates of the points in V(I) can be expressed as rational functions of u. We call rational parametrization of the coordinates of the points in the zero-set V(I) the data of a separating element u, its minimal polynomial m_{u}, and rational functions f_{1}, …, f_{n} such that X_{i} = f_{i}(u) holds in A_{red}.

Such representations, which go back to Kronecker [35], are well suited to many purposes such as effective computation in the reduced algebra A_{red} or counting and isolation of real or complex roots. This representation bears the name Geometric Resolution in [26, 25, 27, 42]. Using the characteristic polynomial of u instead of its minimal polynomial, this representation is called a Rational Univariate Representation of the roots of I, using the denomination introduced in [60].

In this article, we present some structure theorems related to the two questions mentioned above, then show how algorithmic ideas introduced in the univariate case by Shoup [66, 67] fit into this context. Our algorithms require precomputations, either of some multiplication matrices in A, or of the whole multiplication table. These objects may be obtained from the computation of a Gröbner basis [13, 20, 19]. We do not address the difficult question of the complexity of these precomputations.

Computing a minimal polynomial. Let u be an element in A and δ a bound on the degree of its minimal polynomial m_{u}. A natural algorithm for the computation of m_{u} consists in expressing the first δ powers of u on a basis of the k vector space A and then looking for a linear dependency between them. This last step has complexity O(D^{ω}), where ω is the exponent of the complexity of matrix multiplication, and D is the dimension of A over k [14, Chapter 16]. Thus ω = 3 for the naive product, and the best result known to this date is ω < 2.376 [16]. However, the fastest widely available implementation we are aware of is based on Strassen’s algorithm [68] of exponent log_{2}(7) ≃ 2.808, in the computer algebra system Magma [10].

A first improvement consists in considering the values taken by a linear form ℓ on the powers of u. The sequence (ℓ(u^{i}))_{i≥0} admits a minimal linear recurrence relation, which coincides, for a random choice of ℓ, with the minimal polynomial of u, and which can be computed efficiently. This suggests the following algorithm: compute the powers of u, evaluate ℓ on them, and recover the minimal polynomial. This requires the ability to multiply by u. The input of this first algorithm will thus be the multiplication matrix of u in A.

In the context of polynomial factorization over finite fields, Shoup showed in [66, 67] how to speed up these computations in the univariate case when A = k[X]/(f). His idea is to adapt Paterson and Stockmeyer’s fast evaluation algorithm [58] using an A-module structure on the dual space Â. The clever use of this structure avoids the computation of all the powers of the element u.

We demonstrate here that this idea extends to multivariate situations, and yields another method for computing a minimal polynomial. The main difficulty lies in obtaining an efficient implementation of the operations in Â. For the moment, our solution requires a stronger input than above: the whole multiplication table of A. This input is also used for instance in the algorithms of [1, 60].

These results are presented in a precise fashion in the following theorem. The algorithms require an a priori bound δ on the degree of the minimal polynomial we want to compute. A trivial bound is the dimension D of A. Problem-specific bounds are often available, as for instance in [15, 23, 24, 64].

Theorem 1 Let D be the dimension of A as a k-vector space, and let u be in A, with minimal polynomial m_{u}. Suppose that δ is an a priori bound on the degree of m_{u}.

1. If the matrix of multiplication by u is known, then m_{u} can be computed in O(δD^{2}) operations in k.

2. If the multiplication table of A is known, then m_{u} can be computed in O(2^{n}δ^{1/2}D^{2}) operations in k.

In both cases, the algorithm chooses D values in k. If these values are chosen in a finite subset Γ of k, all choices except at most δ|Γ |^{D−1} assure success.

For δ ≈ D, the complexity is O(D^{3}) in the first case and O(2^{n}D^{5/2}) in the second case. If the number of variables n is fixed, the gain in complexity is of order \sqrt{D}, typical of the baby step/giant step techniques which underlie the second approach.

The probabilistic aspect comes from the choice of a linear form over A. For unlucky choices, the output of our algorithms is a strict divisor of the actual minimal polynomial. If the degree of the output coincides with the upper bound δ, then this output is necessarily correct. Otherwise, we can either estimate the probability of an unlucky choice, or evaluate the candidate minimal polynomial on u.

Computing parametrizations. In the discussion leading to the proof of Theorem 1, we introduce some generating series, depending on both the element u and a linear form over A. If u is separating, we show that such series allow to compute rational parametrizations of the points of V(I). This yields our formulæ in Proposition 3, that extend those of Rouillier [60].

Our formulæ are satisfied if I is a radical ideal. In the general case, they remain valid under an additional hypothesis, given in Theorem 2 below, and explained in more detail in §3.2. In short, the minimal polynomial of u must have the maximal possible degree, and the characteristic of the base field must be zero or large enough.

To use these formulæ in practice, the computational task is quite similar to that required to compute a minimal polynomial: evaluating some linear forms on the powers of u. So in a similar fashion, we propose two methods: the direct approach, which requires only multiplication matrices, or its refinement based on Shoup’s idea, using the whole multiplication table.

The first approach has the same complexity as the algorithm of [60], at most O(D^{3}), but our input is weaker. The second approach takes the same input as [60]. Its complexity is at most O(n2^{n}D^{5/2}). This becomes better when the number n of variables is kept constant, whereas the dimension of the quotient algebra becomes large. As above, the gain is then of order \sqrt{D}.

Theorem 2 Let D be the dimension of A = k[X_{1}, …, X_{n}]/I as a k-vector space, and let u be a separating element in A, with minimal polynomial m_{u}. Assume that

– the characteristic of k is zero or greater than min\{s | \sqrt{I} ^{s} ⊂ I\};

– the degree of the minimal polynomial of u is the degree of the minimal polynomial of a generic element in A.

If δ is an a priori bound on the degree of m_{u}, then the following holds:

1. If the matrices of multiplication by u and x_{1}, …, x_{n} are known, then a rational parametrization of the zero-set V(I) can be computed in O(δD^{2} + nD^{2}) operations in k.

2. If the multiplication table of A is known, then a parametrization can be computed in O(n2^{n}δ^{1/2}D^{2}) operations in k.

The algorithms are probabilistic. In both cases, the algorithm chooses D values in k. If these values are chosen in a finite subset Γ of k, all choices except at most δ|Γ |^{D−1} assure success.

The probabilistic aspect lies, as in Theorem 1, in the choice of a linear form over A. If I is a radical ideal, it is straightforward to check the correctness of the output, see Section 3.1. Otherwise, the last assertion in the theorem makes it possible to estimate the probability of choosing an unlucky linear form.

The algorithms mentioned in Theorems 1 and 2 are easily implemented in a computer algebra system such as Magma [10]. Our experiments show their good practical behavior (see Section 5).

Related results. The A-module Â is called the canonical module [63, 36, 18], and has been used in a variety of applications. In particular, the case when the dual Â is a free A-module of rank 1 has led to new geometric and arithmetic forms of the Nullstellensatz [26, 25], a new proof of the Eisenbud-Levine formula [4], or fast algorithms for isolating roots of complete intersection multivariate systems [51–54].

One of our main contributions is to propose algorithms using this module structure whenever the operations in A and Â are effective, even if the dual is not free and of rank 1.

We have focused on the case when the structure of the algebra A is explicitly given. Our ideas also apply if I is given by n generators without zeros at infinity. Indeed, in this context, the basis of the results in [52–54] are fast multiplication algorithms in A. It might be possible to extend these results so as to obtain similar complexity estimates for the operations in Â, which would lead to improved complexity algorithms in this case. More generally, any efficient algorithm for the operations in A and Â can be used in conjunction with the ideas presented here.

In a different context, the geometric resolution algorithm of [27] solves polynomial systems of dimension zero without multiplicities. Its complexity is quadratic in a geometric quantity attached to the input system, and linear in its complexity of evaluation, that is, the number of arithmetic operations necessary to evaluate the system. Recently, this algorithm has been extended so as to handle arbitrary systems, see [42–44]. An important issue is to extend our algorithmic ideas to this context.

Finally, let us mention that F. Rouillier informed us of an improvement of the second result given in Theorem 2, where a factor of order n is saved.

Outline of the paper. In Section 2, we define the module structure on the dual of A, and some useful generating series. In Section 3, we show how both a minimal polynomial and some parametrizations can be read out from such series.

A direct approach to compute these series yields at once the first assertions in Theorems 1 and 2. In Section 4, we show how to improve the crucial step: the evaluation of a linear form on the successive powers of an element in A. This will prove the second parts of Theorems 1 and 2. In Section 5 we present the experimental behavior of our algorithms. The last section gives the proof of a key proposition in Section 3.

Notation. We use the following notation:

– The radical of an ideal I of k[X_{1}, …, X_{n}] is denoted by \sqrt{I}.

– The algebra A is the quotient k[X_{1}, …, X_{n}]/I; the images of the variables X_{1}, …, X_{n} in A are denoted by x_{1}, …, x_{n}. We denote by D the dimension of the k-vector space A, by Ω = {ω_{i}}_{i=1,...,D} a monomial basis of A and by E ⊂ ℕ^{n} the set of exponents of the elements in Ω.

– Given α = (α_{1}, …, α_{n}) in ℕ^{n}, we write X^{α} for the monomial X_{1}^{α_{1}} ⋯ X_{n}^{α_{n}}, and x^{α} for the product x_{1}^{α_{1}} ⋯ x_{n}^{α_{n}}.

– The minimal polynomial of any element t in a finite-dimensional algebra is denoted by m_{t}.

– For two subsets E ⊂ ℕ^{n} and F ⊂ ℕ^{n}, we let E + F be their Minkowski sum, that is, the set {e + f, e ∈ E, f ∈ F }. We use the abbreviation 2E for E + E ⊂ ℕ^{n}.

– Â designates the dual space Hom_{k}(A, k) of the k-linear forms on A. The set Ω̂ = {ω̂_{i}}_{i=1,...,D} represents the dual basis of Ω.

– For a polynomial P ∈ k[U], we write rec(P) for its reciprocal U^{deg(P)}P (\frac{1}{U}).

2 On the Dual of the Quotient Algebra

Most results in this article involve linear forms defined over the algebra A. We frequently use the following operation, which makes the dual Â a A-module:

∘ : A × Â → Â
(u, ℓ) ↦ u ∘ ℓ : v ↦ ℓ(vu).

This section is devoted to basic results related to this operation. As mentioned in the introduction, the case when Â is a free A-module of rank 1 is of particular interest, but this assumption is not required here.

The following lemma (see also [67, 53]) justifies the terminology transposed product for the A-module operation on Â.

Lemma 1 Let u be in A. The matrix of the linear operator

Â → Â
ℓ ↦ u ∘ ℓ

in the dual basis Ω̂ is the transposed of the matrix of multiplication by u in the basis Ω.

Proof. Let ω be in Ω. The value (u ∘ ℓ)(ω) is ℓ(ωu). It is given by the product between the row-vector of the coefficients of ωu on the basis Ω and the vector representing ℓ on the dual basis. This implies that the vector representing u ∘ ℓ is the product M_{u}^{t}ℓ, where M_{u}^{t} is the transposed of the matrix M_{u} representing the multiplication by u in the basis Ω. □

This result has a strong consequence in terms of complexity, based on the transposition principle, or Tellegen’s principle. This principle is actually a theorem about arithmetic circuits, which originates from linear circuit design and analysis [69, 9, 59, 2] and was introduced in computer algebra in [21, 22, 30, 33]. The proof can be found in [14, Theorem 13.20], see also [32, Problem 6] for more comments.

Transposition principle. Let M be a n × n matrix, with no zero row nor column, and suppose that the product v ↦ Mv can be computed by an arithmetic circuit of size C. Then there exists an arithmetic circuit of size C that computes the transposed product w ↦ M^{t}w.

In most applications, the multiplication matrix M_{u} is not known, and its determination might be quite costly. Nevertheless, the transposition principle implies that, whatever the algorithm used for multiplication, there exists an algorithm for transposed multiplication with the same cost, as long as arithmetic circuits are used.

Yet, the algorithms used for (fast) multiplication may not be given by arithmetic circuits. Moreover, even if the proof of the transposition principle is constructive, it is far from obvious how to put it to practice in a computer algebra environment. Therefore, particular attention must be given to design explicit versions of transposed algorithms. In [11], the transposes of some basic algorithms for univariate polynomials are described. In what follows, we will give algorithms for the transposed product in the algebra A.

Generating series. We associate to every element ℓ of Â a multivariate formal power series, denoted S(ℓ). For a subset F ⊂ ℕ^{n} we also define a truncated series S(ℓ, F). These series are given by:

S(ℓ) := ∑_{α∈ℕ^{n}} ℓ(x^{α})X^{α}, S(ℓ, F) := ∑_{α∈F} ℓ(x^{α})X^{α}.

Since E is the set of exponents of the monomial basis Ω, a linear form ℓ in Â is uniquely determined by S(ℓ, E). Given u in A and ℓ in Â, we also introduce the univariate Laurent series

R(u, ℓ) := ∑_{i≥0} \frac{ℓ(u^{i})}{U^{i+1}} .

The series S(ℓ) and particularly R(u, ℓ) are used repeatedly in this article. Similar representations appear in [67, 52, 53], and in [60] for specific linear forms. The following proposition gathers the results we will need when using these generating series. The first point is folklore, similar arguments can be found in [52, 53] and [67]. Let us also mention that results very similar to the second point below can be found in [45], which describes the use of duality-based techniques in coding theory.

Proposition 1 Let ℓ be in Â.

– Let u = ∑_{α∈E} u_{α}x^{α} be in A, let F be a subset of ℕ^{n} and let T be the Laurent series

T = ∑_{α∈ℤ^{n}} t_{α}X^{α} := (∑_{α∈E} \frac{u_{α}}{X^{α}} ) · S(ℓ, E + F).

Then the series S(u ∘ ℓ, F) is ∑_{α∈F} t_{α}X^{α}.

– For i in 1, …, n, let m_{i} ∈ k[X_{i}] be the minimal polynomial of x_{i}, and let δ_{i} be its degree. Then there exists a polynomial H_{ℓ} ∈ k[X_{1}, …, X_{n}] of partial degree in each variable X_{i} less than δ_{i}, such that the following holds:

S(ℓ) = \frac{H_{ℓ}}{rec(m_{1}) ⋯ rec(m_{n})}.

– Let u be in A, with minimal polynomial m_{u} ∈ k[U] of degree δ_{u}. Then there exists a polynomial G_{u,ℓ} ∈ k[U] of degree less than δ_{u} such that the following holds:

R(u, ℓ) = \frac{G_{u,ℓ}}{m_{u}} .

Moreover, G_{u,ℓ} is the quotient of m_{u} ∑_{i=0}^{δ_{u}−1} ℓ(u^{i})U^{δ_{u}−i−1} by U^{δ_{u}}.

– There exists a nonzero polynomial r_{u} ∈ k[L_{1}, …, L_{D}] of total degree at most δ_{u}, such that G_{u,ℓ} is coprime to m_{u} if and only if r_{u}(ℓ_{1}, …, ℓ_{D}) ≠ 0, where (ℓ_{1}, …, ℓ_{D}) are the coordinates of ℓ on the dual basis Ω̂.

Proof. For α′ in F, the value (u ∘ ℓ)(x^{α′}) is ℓ(ux^{α′}) = ∑_{α∈E} u_{α}ℓ(x^{α+α′}). The series T can be written

T = (∑_{α∈E} u_{α}X^{−α}) ( ∑_{β∈E+F} ℓ(x^{β})X^{β}) = ∑_{α′∈E+F −E} (∑_{α∈E} u_{α}ℓ(x^{α+α′})) X^{α′}.

The coefficient of X^{α′} in T coincides with ℓ(ux^{α′}), which proves the first point.

We turn to the second point. Taking F = ℕ^{n} shows that for any u in A, the series S(u∘ℓ) is the restriction of u(1/X_{1}, …, 1/X_{n})S(ℓ) to the set of monomials with exponent in ℕ^{n}.

Let i be in 1, …, n. Since m_{i}(X_{i}) is zero in A, the series S(m_{i}(x_{i})∘ℓ) is zero. Consequently, all the monomials in m_{i}(1/X_{i})S(ℓ) have degree in X_{i} between −δ_{i} and −1. This means that all monomials in rec(m_{i})(X_{i})S(ℓ) = X_{i}^{δ_{i}}m_{i}(1/X_{i})S(ℓ) have degree in X_{i} between 0 and δ_{i} − 1. Taking all i into account shows that the series rec(m_{1})(X_{1}) ⋯ rec(m_{n})(X_{n})S(ℓ) is a polynomial, whose partial degree in each variable X_{i} is less than δ_{i}.

Next, we prove the third part. The linear form ℓ induces a linear form on the algebra k[U]/m_{u}. The previous point shows that rec(m_{u}) ∑_{i≥0} ℓ(u^{i})U^{i} is a polynomial of degree less than δ_{u}. Evaluating it at 1/U and multiplying the result by U^{δ_{u}−1} shows that m_{u}R(u, ℓ) = m_{u} ∑_{i≥0} ℓ(u^{i})/U^{i+1} is also a polynomial of degree less than δ_{u}, denoted by G_{u,ℓ}. For degree reasons, only a finite number of terms in R(u, ℓ) contribute at the product m_{u}R(u, ℓ) defining G_{u,ℓ}. More exactly, the polynomial G_{u,ℓ} equals the polynomial part of the series m_{u} ∑_{i=0}^{δ_{u}−1} ℓ(u^{i})/U^{i+1} containing only nonnegative powers of U; on the other hand, this polynomial part is obviously the quotient of the division of m_{u} ∑_{i=0}^{δ_{u}−1} ℓ(u^{i})U^{δ_{u}−i−1} by U^{δ_{u}}.

Let us finally prove the last point. For ω_{i} in Ω, we let G_{u,i} ∈ k[U] be m_{u}R(u, ω̂_{i}). If ℓ_{1}, …, ℓ_{D} are the coordinates of ℓ on the dual basis, then G_{u,ℓ} is ∑_{1≤i≤D} ℓ_{i}G_{u,i}. Let now r_{u} ∈ k[L_{1}, …, L_{D}] be the resultant of ∑_{1≤i≤D} L_{i}G_{u,i} and m_{u} with respect to U. Then, using [71, Lemma 6.25], we see that G_{u,ℓ} and m_{u} are coprime if and only if r_{u}(ℓ_{1}, …, ℓ_{D}) ≠ 0.

For any polynomial G of degree less than δ_{u}, we now prove that there exists ℓ ∈ Â such that G = G_{u,ℓ}. This suffices to show that r_{u} is a nonzero polynomial. Since r_{u} has total degree at most δ_{u}, this will prove the proposition.

The system m_{u}R(u, ℓ) = G is linear in (ℓ(1), …, ℓ(u^{δ_{u}−1})), of triangular form with diagonal entries equal to 1 as m_{u} is monic. Since (1, …, u^{δ_{u}−1}) are linearly independent, it is always possible to find ℓ which takes prescribed values on these powers of u. □

This proposition shows that for a generic choice of ℓ, the irreducible form of the rational series R(u, ℓ) has the minimal polynomial m_{u} for denominator. This will be used repeatedly in the rest of this article.

An algorithm for the transposed product. The first point in the previous proposition suggests the following algorithm for the transposed product: given ℓ and u, first compute S(ℓ, 2E), taking F = E; then perform a power series multiplication, and read off the coefficients of S(u ∘ ℓ, E).

The main difficulty lies in determining the truncated series S(ℓ, 2E) from its first terms S(ℓ, E). The second point of Proposition 1 shows that the series S(ℓ) is rational. When there is only one variable, the quotient A is given as k[X]/(f), so the denominator of S(ℓ) is known a priori, as it is the reciprocal polynomial of f. It is then straightforward to recover the numerator from the first terms S(ℓ, E), which in turns gives the next terms of S(ℓ, 2E) by Taylor expansion. This is the basis of Shoup’s algorithm for the univariate transposed product [67].

In the general case, the denominator is not known in advance. At the moment, we are unable to make an algorithmic use with good complexity of the rationality of the series S(ℓ), or even of the stronger form given in the second part of Proposition 1.

3 Computing Minimal Polynomials and Rational Parametrizations

We now describe our first algorithms solving the questions mentioned in the introduction: computing the minimal polynomial of an element u in A, and the corresponding parametrization, if u is separating. These algorithms are derived from the study of the generating series introduced in the previous section, and yield the first parts of Theorems 1 and 2.

Similar considerations to those presented in Subsection 3.1 can be found in the literature, for instance in [72, 66, 67, 31]. The main new result is Proposition 3 in Subsection 3.2: it provides a generalization of Rouillier’s formulæ [60], which does not require the use of a specific linear form to compute parametrizations. In [60], this specific form, the trace, is computed from the multiplication table of A. Here, we avoid this precomputation, as we show that almost any form can be used. Consequently, the algorithms presented in Subsection 3.3 only require multiplication matrices as input.

All these algorithms are based on the same basic subroutine, the evaluation of a linear form on the successive powers of an element in A. Thus their complexity is fundamentally dependent on the cost of this particular task; reducing this cost will be the object of Section 4.

3.1 Computing a minimal polynomial

Our method to compute a minimal polynomial in A is based on the following property: if ℓ is an arbitrary linear form on A, then the scalar sequence (ℓ(u^{i}))_{i≥0} is linearly recurrent, that is, it can be defined by a linear recurrence relation with constant coefficients. The relation of minimal degree is called its minimal polynomial; if ℓ is a “generic” linear form, then this polynomial equals the the minimal polynomial of u.

This principle has been used in a variety of settings. It underlies Wiedemann’s algorithm [72] for solving sparse — or rather, easy-to-evaluate — linear systems, and is the basis of Thiong Ly’s and Shoup’s algorithms [70, 66, 67] to compute minimal polynomials in the univariate case A = k[X]/(f).

Given an upper bound δ on its degree, the minimal polynomial of a sequence of scalars L satisfying a linear recurrence can be computed by Berlekamp-Massey’s algorithm, see [6, 49] and [71, chapter 12.3]. This algorithm requires the first 2δ values of L, and amounts to the computation of a (δ, δ) Padé approximant for the generating series ∑_{i≥0} L_{i}U^{i}. This is denoted by MinimalPolynomial(L) in the algorithm below.

Computing the minimal polynomial

Input: u in A, ℓ in Â, a bound δ on the degree of m_{u}.

Output: a polynomial m_{u,ℓ} in k[U].

L ← [ℓ(1), ℓ(u), …, ℓ(u^{2δ−1})];

      m_{u,ℓ} ← MinimalPolynomial(L);

return(m_{u,ℓ});

The next proposition encapsulates the cost and correctness analysis of this algorithm. Similar considerations for Wiedemann’s algorithm can be found in [31].

Proposition 2 Let u be in A and let m_{u} be its minimal polynomial. If δ is a bound on the degree of m_{u}, then besides the evaluation of the sequence [ℓ(1), ℓ(u), …, ℓ(u^{2δ−1})], the previous algorithm requires O(δ^{2}) operations in k. Its output is the polynomial m_{u} if and only if the polynomial G_{u,ℓ} from Proposition 1 and m_{u} are coprime. Otherwise, the output m_{u,ℓ} is a strict divisor of m_{u}.

Proof. Using a naive version of the extended Euclidean algorithm, the running time of Berlekamp-Massey’s algorithm is quadratic in δ [71, Theorem 12. 10]. This proves the complexity estimate.

Let m_{u,ℓ} be the (monic) minimal polynomial of the sequence (ℓ(u^{i}))_{i≥0}. The polynomial m_{u} cancels this sequence, since ∑_{i} a_{i}u^{i} = 0 implies that the equality ∑_{i} a_{i}ℓ(u^{i+j}) = 0 holds for all j. Consequently, m_{u,ℓ} divides m_{u}. Let us show that they coincide if and only if the polynomials G_{u,ℓ} and m_{u} are coprime, where G_{u,ℓ} is defined in Proposition 1:

R(u, ℓ) := ∑_{i≥0} \frac{ℓ(u^{i})}{U^{i+1}} = \frac{G_{u,ℓ}}{m_{u}} .  (1)

To this effect, we recall the following result from [28, Lemma 1]: the generating series R(u, ℓ) has the rational form

R(u, ℓ) = \frac{H_{u,ℓ}}{m_{u,ℓ}} ,  (2)

the polynomials H_{u,ℓ} and m_{u,ℓ} being coprime.

The two rational expressions of R(u, ℓ) in equations (1) and (2) show that if m_{u,ℓ} and m_{u} coincide, then G_{u,ℓ} and H_{u,ℓ} coincide, so G_{u,ℓ} and m_{u} are coprime. For the converse direction, we first notice that, by equations (1) and (2), m_{u} divides m_{u,ℓ}G_{u,ℓ}. Therefore, if G_{u,ℓ} and m_{u} are coprime, then m_{u} divides m_{u,ℓ}. Since m_{u,ℓ} always divides m_{u}, it follows that m_{u,ℓ} and m_{u} coincide. This finishes the proof. □

Using a fast extended Euclidean algorithm [71, chapter 11.1], the complexity of Berlekamp-Massey’s algorithm drops to O(δ log^{2} δ log log δ). The polynomial G_{u,ℓ} can be computed as a byproduct without affecting the complexity. In any case, the limiting factor in this algorithm is the computation of the sequence [ℓ(1), ℓ(u), …, ℓ(u^{2δ−1})].

If the degree of the output coincides with the known upper bound for deg m_{u}, the output is necessarily correct. A trivial upper bound is the dimension of A: if the degree of the output reaches this upper bound, then u is primitive for k → A, and the result of the algorithm is correct. Otherwise, Proposition 2 states that the output m_{u,ℓ} is correct if and only if m_{u,ℓ}(u) is zero.

3.2 Computing parametrizations

If u is a separating element for I, we want to compute parametrizations giving the values of the variables X_{j} on V(I) as functions of u, that is, rational functions f_{j}(u) such that the relations x_{j} = f_{j}(u) hold in the reduced algebra A_{red} = k[X_{1}, …, X_{n}]/\sqrt{I}. Following the ideas of Kronecker [35] and Macaulay [46], we propose a method to compute rational parametrizations of the form

x_{j} = \frac{g_{j}(u)}{g(u)}.

Our method requires the following assumptions:

1. the characteristic of k is zero or larger than min\{s, \sqrt{I} ^{s} ⊂ I\};

2. the degree of the minimal polynomial m_{u} of u is the degree of the minimal polynomial of a generic element in A.

A generic element in A is defined as ∑_{i=1}^{D} T_{i}ω_{i} in A ⊗_{k} k(T_{1}, …, T_{D}). This element depends on the choice of the basis Ω, but the degree of its minimal polynomial over k(T_{1}, …, T_{D}) depends only on A, as a standard linear algebra fact [37, Section 62] ensures that two similar matrices have the same minimal polynomial. As an illustration, consider the case A = ℚ[X_{1}, X_{2}]/(X_{1}^{2}, X_{2}^{2}). The minimal polynomial of a generic element has degree 3, but x_{1}, even though separating, has U^{2} for minimal polynomial. The possible defects can be measured using the nil-indices of the local factors of A, see Section 6.

If I is a radical ideal, assumption 1 is obviously satisfied. Since k is perfect, a separating element is also primitive, so assumption 2 is also satisfied in this case.

Taking the above assumptions for granted, our main result is the following proposition:

Proposition 3 Let u in A be a separating element of I, such that the above assumptions are satisfied. Let v be in A, ℓ in Â, and let G_{u,ℓ} and G_{u,v∘ℓ} be the polynomials in k[U] of degree less than that of m_{u} such that

R(u, ℓ) = \frac{G_{u,ℓ}}{m_{u}} , R(u, v ∘ ℓ) = \frac{G_{u,v∘ℓ}}{m_{u}} .

Then if m_{u} and G_{u,ℓ} are coprime, the following equality holds:

v = \frac{G_{u,v∘ℓ}(u)}{G_{u,ℓ}(u)} in A_{red}.

This proposition requires a few comments:

– If the condition on the degree of m_{u} is not satisfied, then the conclusion may become false for a generic linear form. Consider again A = ℚ[X_{1}, X_{2}]/(X_{1}^{2}, X_{2}^{2}) with basis (1, x_{1}, x_{2}, x_{1}x_{2}), u = x_{1}, v = x_{2}, and let ℓ_{1}, ℓ_{x_{1}}, ℓ_{x_{2}}, ℓ_{x_{1}x_{2}} be the coordinates of ℓ on the dual basis. A short calculation shows that

m_{u} = U^{2}, R(x_{1}, ℓ) = \frac{ℓ_{1}U + ℓ_{x_{1}}}{U^{2}} , R(x_{1}, x_{2} ∘ ℓ) = \frac{ℓ_{x_{2}}U + ℓ_{x_{1}x_{2}}}{U^{2}} ;

so our formulæ would wrongly give the value ℓ_{x_{1}x_{2}}/ℓ_{x_{2}} for x_{2} instead of 0.

– In [60, Theorem 3.1], a similar result is proved for a particular linear form, the trace, which associates to any element v in A the trace of the multiplication map by v. For this particular form, the hypothesis on the degree of m_{u} is not required.

– If I is a radical ideal, a direct proof of Proposition 3 is the following: since k is a perfect field, the trace form generates Â as a A-module [4, 62]. The conclusion follows from [60, Theorem 3.1].

We defer the somewhat lengthy proof of Proposition 3 to the last section of the paper and we directly present our algorithm for computing rational parametrizations. It takes as input a linear form ℓ on A, an element u in A, its minimal polynomial m_{u} of degree δ_{u}, as well as the polynomial G_{u,ℓ} defined in Proposition 1.

Computing the parametrizations

Input: u in A, ℓ in Â, m_{u} and G_{u,ℓ} in k[U].

Output: a rational parametrization of the coordinates.

for j in 1, …, n do

c^{(j)} ← [(x_{j} ∘ ℓ)(1), (x_{j} ∘ ℓ)(u), …, (x_{j} ∘ ℓ)(u^{δ_{u}−1})];
C_{j} ← ∑_{i=0}^{δ_{u}−1} c_{i}^{(j)}U^{δ_{u}−i−1};
G_{u,x_{j}∘ℓ} ← m_{u} · C_{j} quo U^{δ_{u}};

return [\frac{G_{u,x_{1}∘ℓ}}{G_{u,ℓ}} , …, \frac{G_{u,xn∘ℓ}}{G_{u,ℓ}}];

Proposition 4 Under the hypotheses of Proposition 3, the output of the previous algorithm is a rational parametrization of the points in V(I). Besides the evaluation of the sequences

[(x_{j} ∘ ℓ)(1), (x_{j} ∘ ℓ)(u), …, (x_{j} ∘ ℓ)(u^{δ_{u}−1})], j ∈ {1, …, n},

this algorithm requires at most O(nD^{2}) additional operations in k.

Proof. We begin by recalling that the polynomial G_{u,x_{j}∘ℓ} can be obtained as the quotient of m_{u} ∑_{i=0}^{δ_{u}−1}(x_{j} ∘ ℓ)(u^{i})U^{δ_{u}−i−1} by U^{δ_{u}}, where δ_{u} is the degree of m_{u}. We proved this fact in the third part of Proposition 1. The correctness of the above algorithm then follows from the formulæ in Proposition 3, applied to v = x_{j}, for j = 1, …, n. The cost analysis is straightforward, since each polynomial multiplication has complexity at most quadratic in the degree δ_{u} ≤ D. □

We point out that fast algorithms for polynomial multiplication would yield a linear complexity in D, up to logarithmic factors, but the bottleneck of this algorithm is the computation of the sequences [(x_{j} ∘ ℓ)(1), (x_{j} ∘ ℓ)(u), …, (x_{j} ∘ ℓ)(u^{δ_{u}−1})]. We stress the fact that the probabilistic aspect of the output relies only on the correct computation of the minimal polynomial of u; see the previous subsection for more comments on this point.

3.3 Complexity estimates for the first approach

To put the algorithms of the previous subsections to practice, we must specify the operations in A. In this subsection, we assume that the matrices of multiplication by u and x_{1}, …, x_{n} are known and prove the first parts of Theorems 1 and 2.

The algorithm for a minimal polynomial is given in Subsection 3.1. The main task lies in computing the values

[ℓ(1), ℓ(u), …, ℓ(u^{2δ−1})],

δ being an a priori bound on the degree of m_{u} and ℓ a linear form on A. To compute the parametrizations corresponding to a separating element u, we first compute its minimal polynomial as above, then evaluate

[(x_{j} ∘ ℓ)(1), (x_{j} ∘ ℓ)(u), …, (x_{j} ∘ ℓ)(u^{δ_{u}−1})], j = 1, …, n,

where δ_{u} ≤ δ is the degree of the minimal polynomial of u.

The other necessary operations and their complexity are given in Propositions 2 and 4, so we just need to detail the cost of the successive evaluations of respectively ℓ and x_{1} ∘ℓ, …, x_{n} ∘ℓ. For the moment, we follow a direct approach. All powers of u are computed, then the linear forms are evaluated on all of them. A more refined method is introduced in the next section.

– Using its multiplication matrix, one multiplication by u has cost O(D^{2}) operations in k. Consequently, all the requested powers of u can be computed within O(δD^{2}) operations in k.

– Given the linear form ℓ, each linear form x_{j} ∘ ℓ can be computed using Lemma 1 since the matrix of multiplication by x_{j} is known. The total cost is thus within O(nD^{2}) operations in k.

– The evaluation of a single linear form takes O(D) operations in k. Evaluating all the linear forms on the powers of u requires respectively O(δD) or O(nδ_{u}D) operations in k.

This gives respectively O(δD^{2}) operations in k for the minimal polynomial, and O(δD^{2} + nD^{2}) for the parametrizations. The additional costs are given in Propositions 2 and 4. They fit into the complexity bounds O(δD^{2}) and O(δD^{2} + nD^{2}). This concludes the complexity analysis.

Propositions 2 and 4 show that the output is correct whenever the polynomials G_{u,ℓ} and m_{u} are coprime. The last point in Proposition 1 shows that this is the case if and only if the coefficients of ℓ on the dual basis cancel a nonzero polynomial r_{u} of degree at most δ_{u}. Zippel-Schwartz’s lemma (see [73, 65] and [71, Lemma 6.44]) concludes the probability analysis.

4 Speeding up the Power Projection

The algorithms presented in the previous section share the same basic subroutine: the evaluation of a linear form on the successive powers of an element in A. Their complexity fundamentally relies on the cost of this particular operation, called power projection.

Power Projection Problem. Let u be in A, ℓ in Â and N > 0. Compute the sequence [ℓ(1), ℓ(u), …, ℓ(u^{N−1})].

The naive solution to this question used in the previous section requires to evaluate all the powers of u. In this section, we present a result given by Shoup in the univariate case [66, 67], which shows how to avoid the computations of all those powers, by a “transposition” of Paterson and Stockmeyer’s fast evaluation algorithm [58]. This brings a speed-up of order \sqrt{N} over the naive version.

This approach requires other operations than mere multiplications by u or x_{i}. Thus, we first state the complexity results in terms of the cost of product and transposed product in A, denoted respectively by M(A) and M^{t}(A). Next, we put these ideas to practice. For the time being, our effective version of the transposed product requires the whole multiplication table of the algebra A.

4.1 Baby step / giant step techniques

It is noted in [66, 67, 32] that the power projection problem itself is a transposition of the question of polynomial evaluation in A:

Polynomial Evaluation Problem. Let p be a polynomial in k[T] of degree N − 1, and u in A. Compute p(u).

For both questions, the point is to avoid the computation of all powers u^{i}, which would lead to a complexity of O(NM(A)) operations in k. In [58], Paterson and Stockmeyer propose an algorithm for the polynomial evaluation problem (see also [12]) which saves a factor \sqrt{N} using a baby step / giant step technique.

The idea underlying this process also applies to the power projection problem and yields the following algorithm, initially presented in [66] for the case A = k[X]/(f). As in Paterson and Stockmeyer’s, this algorithm takes as input two parameters k and k′, which must satisfy kk′ ≥ N.

Power projection

Input: u in A, ℓ in Â, N, k, k′.
Output: the sequence [ℓ(1), ℓ(u), …, ℓ(u^{N−1})].
u_{i} ← u^{i}, i = 0, …, k
for i ← 0, …, k′ − 1 do
c_{ik+j} ← ℓ(u_{j}), j = 0, …, k − 1
ℓ ← u_{k} ∘ ℓ
return [c_{0}, …, c_{N−1}];

We encapsulate the complexity of this algorithm in the following proposition. A similar result is presented in [67].

Proposition 5 Let u be in A, let ℓ be in Â and let N > 0. Then, the sequence

[ℓ(1), ℓ(u), …, ℓ(u^{N−1})]

can be computed within O (N^{1/2}(M(A) + M^{t}(A)) + ND) operations in k.

Proof. We take k and k′ of the same magnitude, that is

k = ⌊\sqrt{N}⌋, k′ = ⌈N/k⌉,

where ⌊x⌋ and ⌈x⌉ respectively denote the largest integer less than or equal to x, and the smallest integer larger than or equal to x.

The precomputation of the first k powers of u requires O(N^{1/2}) multiplications in A. Each of the k′ passes through the for loop requires the evaluation of k linear forms, plus a transposed multiplication. Since kk′ = O(N), the overall cost is thus O(ND) operations for the evaluation of the linear forms and O(N^{1/2}) transposed multiplications. This proves the proposition. □

Corollary 1 Let D be the dimension of A as a k-vector space, and let u be in A. Let δ be a bound on the degree of the minimal polynomial of u. Then:

– The minimal polynomial of u can be computed by a probabilistic algorithm in O (δ^{1/2}(M(A) + M^{t}(A)) + δD) operations in k.

– If u is a separating element of V(I) such that the assumptions of Subsection 3.2 are satisfied, a parametrization of the algebraic variables can be computed in

O (nδ^{1/2}(M(A) + M^{t}(A)) + nD^{2})

operations in k.

In both cases, the algorithm chooses D values in k. If these values are chosen in a finite subset Γ of k, all choices except at most δ|Γ |^{D−1} assure success.

Proof. The proof is similar to that of Subsection 3.3, the difference lies in the complexity analysis of the power projection. Proposition 5 brings the result, taking respectively N = 2δ for the minimal polynomial computation, and N = δ_{u} ≤ δ for the parametrizations. □

Using the transposition principle, these complexity results could be rewritten in terms of M(A) only, but our explicit version reflects the underlying algorithm more closely.

4.2 Complexity estimates for the second approach

To put such algorithms to practice, we need an effective version of the transposed product. To this effect we suppose that the structure of the algebra A is given by a monomial basis and the corresponding multiplication tensor. This makes it possible to estimate the cost of the product and transposed product, which will conclude the proofs of Theorems 1 and 2.

More precisely, in the following paragraphs, we show that the costs of multiplication and transposed multiplication, denoted by M(A) and M^{t}(A) up to now, are in O(2^{n}D^{2}) operations in k. With these results, the complexity estimates of Corollary 1 become respectively O(2^{n}δ^{1/2}D^{2}) and O(n2^{n}δ^{1/2}D^{2}) operations in k, which concludes the proof of Theorems 1 and 2.

A note on Rouillier’s algorithm. The input is now the same as that of [60]. Yet, Rouillier’s algorithm uses a particular linear form, the trace. In the present context, computing the trace is straightforward, since we have precomputed the whole multiplication table. Thus, we can apply our baby step/giant step techniques to speed up the deterministic algorithm of [60]. Still, using random linear forms has its benefits; for instance, we may choose forms with many coefficients equal to zero.

To prove the estimates on the complexity of the operations in A and Â, we recall and introduce some notation.

– We recall that Ω = {ω_{i}}_{i=1,...,D} is a monomial basis of A, and that E ⊂ ℕ^{n} is the corresponding set of exponents, so that Ω = x^{E}.

– We denote by Ω · Ω the set of products {ω_{i}ω_{j} | ω_{i} ∈ Ω, ω_{j} ∈ Ω}. The corresponding set of exponents is denoted by 2E, and is the Minkowski sum E + E ⊂ ℕ^{n}. Its cardinality is bounded by 2^{n}|E| = 2^{n}D.

– We assume that the sets Ω and Ω · Ω are ordered; the elements of A will be given by their coefficients on the basis Ω. The multiplication tensor in A is given by a |E| × |2E| matrix M, with rows indexed by the elements in Ω and columns indexed by the elements of Ω · Ω. The columns of M give the coordinates of the element in Ω · Ω on the basis Ω.

Introducing the matrix M is a convenient way to describe the operations in A and Â and bound their complexity.

Multiplication in the quotient. We first give the cost of the multiplication in A. This operation is done in a straightforward manner. Two elements u and v in A are multiplied as polynomials in k[X_{1}, …, X_{n}], then reduced using the matrix M.

In the algorithm below, u and v are given by the vectors u and v of their coefficients on the basis Ω. Given a vector u of size D and a monomial ω in Ω, u[ω] denotes the entry of u corresponding to ω. The function Coefficients(W, Ω·Ω) returns the vector of the coefficients of W on the monomial family Ω · Ω.

Multiplication in the quotient

Input: the coefficients of u, v in A, the matrix M. Output: the coefficients of the product uv in A.

U ← ∑_{ω∈Ω} u[ω]ω; V ← ∑_{ω∈Ω} v[ω]ω; R ← UV; # the multiplication is done in k[X_{1}, …, X_{n}]

      c_{W} ← Coefficients(W, Ω · Ω);
      return Mc_{W};

Given u and v in A, the previous algorithm computes the product uv in A within O(2^{n}D^{2}) operations in k. Indeed, the naive multiplication of two polynomials with support in E requires O(D^{2}) operations. The reduction of the product is done by the matrix-vector product, which requires |E||2E| ≤ 2^{n}|E|^{2} = 2^{n}D^{2} operations in k.

Transposed multiplication. Our effective version of the transposed product was described at the end of Section 2. There, we reduced the transposed multiplication u ∘ ℓ to two steps. First computing S(ℓ, 2E), that is, the values of ℓ on the elements of Ω · Ω, then performing a multivariate series multiplication and extracting the required coefficients.

For any η in Ω · Ω, the value ℓ(η) is the product between the row c_{ℓ} of the coefficients of ℓ on the dual basis and the column of the coefficients of η on the basis Ω. In other words, the coefficients of S(ℓ, 2E) are the entries of the product c_{ℓ}M.

This property yields the following algorithm for the transposed product. The linear form ℓ is given as the row-vector c_{ℓ} of its coefficients on the dual basis. The other notation was introduced above.

Transposed multiplication in the quotient

Input: u in A, ℓ in Â, the matrix M. Output: u ∘ ℓ in Â.

d_{ℓ} ← c_{ℓ}M; S ← ∑_{η∈Ω·Ω} d_{ℓ}[η]X^{η}; T ← u(1/X_{1}, …, 1/X_{n}) · S;

return Coefficients(T, Ω);

Given u in A and ℓ in Â, the previous algorithm computes the transposed product u∘ℓ within O(2^{n}D^{2}) operations in k. Indeed, the matrix-vector product requires |E||2E| ≤ 2^{n}D^{2} operations in k. Using a naive series multiplication routine, the Laurent series product also requires 2^{n}D^{2} operations in k.

5 Experimental Results

System  1 2 3 4 5 6 7 8
Variables  3 4 6 7 3 4 3 4
Max. Degree 12 12 6 7 12 6 12 6
Solutions  30 192 156 962 1728 1296 1728 1296
Gröbner basis 1 4 4.5 309 0.2 0.2 6.2 170
Reconstruction 0.2 0.1 0.1 0.5 4 6 7 8

Algorithms of Section 3.3:

Mult. Matrices 0.1 2 1 6 3 4 5 30
Power Projection 0.4 3.6 3 57 695 763 700 1220
Total  0.5 5.6 4 63 698 767 705 1250

Algorithms of Section 4.2:

Mult. Table 0.2 2.5 1.5 80 24 54 403 1330
Power Projection 0.3 2.1 2.2 20 164 250 290 370
Total  0.5 4.6 3.7 100 188 304 693 1700

Fig. 1. Experimental Data; times are given in seconds

The algorithms underlying Theorems 1 and 2 have been implemented in the Magma computer algebra system [10]. In this section, we compare the methods presented respectively in Subsections 3.3 and 4.2, for the computation of a parametrization of the solutions of a polynomial system. Recall that the two methods differ by their input, respectively some multiplication matrices or the whole multiplication table, and by the computation of the power projection.

Since our complexity estimates are stated in terms of operations in the base field, we insist on computations on a finite field, where such operations have almost constant cost. Our base field is thus the finite field with 9001 elements.

The systems we have chosen are presented in Figure 1. All of them are complete intersection zero-dimensional systems. Systems 1 and 2 were proposed by S. Mallat for the design of foveal wavelets [47]. Systems 3 and 4 are the Cyclic systems [7] for n = 6 and n = 7. Systems 5 and 6 are sparse systems, with about 10 monomials of degree at most 4 per equation, and a single higher-degree monomial. Systems 7 and 8 are obtained by applying a linear change of variables on the previous systems.

– The first lines indicate the number of variables and the maximum degree of the input equations, then the dimension of the quotient algebra, that is the number of solutions counted with multiplicities.

– For all systems, the separating element is a randomly chosen linear combination of the variables, and the linear form has only 5 nonzero coefficients on the dual basis. In all cases, we find a minimal polynomial of degree the dimension of the quotient, so the output is correct.

– A basis for the quotient algebra is computed using Magma’s GroebnerBasis function for a Graded Reverse Lexicographical order. Its computation time is given in the line labelled “Gröbner Basis”. The line labelled “Reconstruction” gives the time necessary to perform all reconstruction operations, that is, Berlekamp Massey’s algorithm and univariate polynomial multiplications. Their cost is detailed in Propositions 2 and 4, and is the same for both approaches.

– The computation times are next given for both approaches. For the algorithm of Section 3.3, this includes the computation of some multiplication matrices (using Magma’s RepresentationMatrix function), then the naive version of the power projection. For the algorithm of Section 4.2, this includes the computation of the whole multiplication table, which enables a faster version of the power projection.

As was to be expected, the baby steps/giant steps techniques bring a consequent speed up over the naive version of the power projection. On the other hand, the precomputation of the whole multiplication table obviously affects this speed-up.

Systems 5 and 6 were chosen such that the Gröbner basis and the multiplication table were fast to compute. The advantage of using baby step/giant step techniques appears clearly for such examples.

Remark that the algorithm in [60] first requires to compute the whole multiplication table, then computes a power projection using the slower technique, i.e. without using the baby steps / giant steps techniques. The solutions we present here are certainly competitive with this approach.

6 Proof of Proposition 3

In this section, we prove Proposition 3. The data is a finite dimensional quotient algebra A = k[X_{1}, …, X_{n}]/I over a perfect field k, a separating element u in A and a linear form ℓ in Â. Our assumptions are as follows:

Assumption 1 The following conditions hold:

– the characteristic of k is zero or greater than min\{s, \sqrt{I} ^{s} ⊂ I\};

– the degree of the minimal polynomial m_{u} of u equals the degree of the minimal polynomial of a generic element in A (see definition below);

– ℓ and u are such that

R(u, ℓ) := ∑_{i≥0} \frac{ℓ(u^{i})}{U^{i+1}} = \frac{G_{u,ℓ}}{m_{u}} ,

with G_{u,ℓ} and m_{u} coprime (the definitions of the series R and the polynomial G_{u,ℓ} are given in Section 2).

Note that if I is a radical ideal, then the first two assumptions are satisfied as soon as u is a separating element, since in this case the degree of the minimal polynomial of u equals the dimension D of A. The number min\{s, \sqrt{I} ^{s} ⊂ I\} is called the exponent of I; it equals 1 if I is radical.

Our goal is to show that for every v in A and for every α ∈ V(I),

(\frac{G_{u,v∘ℓ}}{G_{u,ℓ}} ) (u(α)) = v(α).

Recall the in the particular case when I is radical, we indicated, in the comments following Proposition 3, a quick proof of these formulæ. The rest of the paper is devoted to the proof in the general case. Since the arguments are a little involved, we divide their exposition in three parts. In Subsection 6.1 we relate the factorization of m_{u} and the exponents of the primary components of I; the main result is Proposition 6, which is an analogue for minimal polynomials of a classical result on characteristic polynomials, sometimes referred to as Stickelberger’s theorem [17, Proposition 2.7].

In Subsection 6.2 we rewrite the series R(u, v ∘ ℓ) using a description of Â by differential conditions on the local factors of A. Finally, our knowledge of the factorization of m_{u} will make it possible to read out the required result on the new expression of R(u, v ∘ ℓ) and to conclude in Subsection 6.3 the proof of Proposition 3.

6.1 Minimal polynomials of generic elements and local factors

Given the k-algebra A = k[X_{1}, …, X_{n}]/I and its basis Ω = (ω_{1}, …, ω_{D}), we recall that we call the generic element in A the element T := ∑_{i=1}^{D} T_{i}ω_{i} in A⊗_{k} k(T_{1}, …, T_{D}). We denote by m_{T} the minimal polynomial of T and by δ(A) the degree of m_{T}. The polynomial m_{T} depends on the choice of the basis Ω, but its degree depends only on A. The numbers δ(A_{α}) will be used in the next paragraph, for some algebras A_{α} to be introduced. They are defined in the same manner.

Reduction to the case k algebraically closed. This first section encloses a result on transfer properties of ideals in polynomial algebras under extension from k to its algebraic closure \overline{k}. This result will serve to reduce the proof of Proposition 3 to the case when k algebraically closed.

In the lemma below, if J is an ideal in k[X_{1}, …, X_{n}], we denote by \overline{J} the ideal it generates in \overline{k}[X_{1}, …, X_{n}], that is, the set of all finite sums ∑ a_{i}f_{i}, where a_{i} ∈ \overline{k}[X_{1}, …, X_{n}] and f_{i} ∈ J. We will particularly focus on the ideal \overline{I}, and we will denote \overline{A} = \overline{k}[X_{1}, …, X_{n}]/\overline{I}.

Lemma 2 The following results hold:

– The ideal \overline{I} is zero-dimensional in \overline{k}[X_{1}, …, X_{n}] and dim_{k} A equals dim\overline{k} \overline{A}.

– The minimal polynomial over k of an element u in A coincides with the minimal polynomial of u as an element of \overline{A} over \overline{k}.

– The degree of the minimal polynomial of a generic element in A equals the degree of the minimal polynomial of a generic element in \overline{A}.

– The exponent of \overline{I} equals the exponent of I.

Before starting the proof, we stress the fact that the first three points do not require that k is a perfect field, while for the last point, this hypothesis is crucial, as showed by the following example. Let k be the field 𝔽_{p}(Y) of rational functions over the finite field with p elements; then the polynomial X^{p} − Y is square-free over k but not over \overline{k}, therefore the ideal it generates in k[X] is radical, while its extension to \overline{k}[X] is not.

Proof. The first assertion is a classical one, we refer to [34, Corollary 3.7.3] for a proof. The second and the third assertions are direct consequences of the fact that minimal polynomials are invariant under change of base ring, see for instance [39, Chapter XIV, Corollary 2.2].

It remains to prove the last assertion. We begin by showing that the operations of extending an ideal and taking the radical of an ideal commute, that is the ideals \overline{\sqrt{I}} and \sqrt{\overline{I}} are equal. Since \sqrt{I} contains I and extending ideals preserves inclusion, we have that \overline{I} ⊂ \overline{\sqrt{I}}. Since k is a perfect field, and \sqrt{I} is radical, [34, Proposition 3.7.18] shows that its extension \overline{\sqrt{I}} is also radical, so taking again radicals in \overline{I} ⊂ \overline{\sqrt{I}}, we obtain the first inclusion \sqrt{\overline{I}} ⊂ \overline{\sqrt{I}}. Let us now justify the converse inclusion \overline{\sqrt{I}} ⊂ \sqrt{\overline{I}}. Since \overline{I} contains I and taking radicals preserves inclusion, we have that \sqrt{I} ⊂ \sqrt{\overline{I}}. Thus any element y in \overline{\sqrt{I}} may be written as a finite sum ∑_{i} a_{i}f_{i}, for some polynomials a_{i} with coefficients in \overline{k} and some f_{i} belonging to \sqrt{\overline{I}}, so y ∈ \sqrt{\overline{I}}. Thus, the equality of \overline{\sqrt{I}} and \sqrt{\overline{I}} is proved.

We finally prove the last assertion concerning the exponent preservation under extension to \overline{k}. By definition of the exponent, it is enough to show that \sqrt{I} ^{s} ⊂ I if and only if \sqrt{\overline{I}} ^{s} ⊂ \overline{I}. For the direct assertion, suppose that \sqrt{I} ^{s} ⊂ I. Taking extensions and using the property proved in the previous paragraph, we deduce \sqrt{\overline{I}} ^{s} ⊂ \overline{I}. Conversely, suppose that \sqrt{\overline{I}} ^{s} ⊂ \overline{I}. Intersecting both sides with k[X_{1}, …, X_{n}] (this operation is called contraction), we assert that we recover \sqrt{I} ^{s} ⊂ I. In order to justify this, we use the fact that in polynomial algebras, extension followed by contraction of an ideal returns the initial ideal, see for instance [38, Chapter III, Proposition 7]. Indeed, this fact, in conjunction with the previous arguments implies the equalities I = k[X_{1}, …, X_{n}]∩\overline{I} and \sqrt{I} ^{s} = \sqrt{\overline{I}} ^{s} ∩ k[X_{1}, …, X_{n}], and this concludes the proof of our lemma. □

In view of the previous lemma, we legitimately suppose, from now on, that k is algebraically closed.

Minimal polynomials of generic elements. The following lemma shows that over an algebraically closed field, the degree of the minimal polynomial of a generic element in A equals the maximal degree of all minimal polynomials of elements in A. We point out that this result applies to any algebra of finite dimension, and will be used for the algebras A_{α} introduced in the next paragraph.

Lemma 3 For every t in A, deg m_{t} ≤ δ(A), and there exists t in A such that deg m_{t} = δ(A). In other words, δ(A) = max_{t∈A}(deg m_{t}).

Proof. Let B be A⊗_{k}k(T_{1}, …, T_{D}) and let T ∈ B be ∑_{i=1}^{D} T_{i}ω_{i}. The k-basis Ω of A is also a k(T_{1}, …, T_{D})-basis of B. We define M_{T} as the matrix of multiplication by T in this basis; then m_{T} (M_{T}) = 0.

Let t be in A; t can be written ∑_{i=1}^{D} t_{i}ω_{i}. Both M_{T} and m_{T} have their coefficients in k[T_{1}, …, T_{D}], so the equality m_{T} (M_{T}) = 0 can be specialized at (t_{1}, …, t_{D}). The matrix M_{T} specializes into the multiplication matrix of t in A, which shows that deg m_{t} ≤ deg m_{T} = δ(A).

Consider now the D × δ(A) matrix whose columns contain the coefficients of T^{0}, …, T^{δ(A)−1} on the basis Ω. This matrix has entries that are polynomial in (T_{1}, …, T_{D}), and has maximal rank, so admits a δ(A) × δ(A) submatrix with nonzero determinant D ∈ k[T_{1}, …, T_{D}].

Since k is algebraically closed, there exists a D-tuple (t_{1}, …, t_{D}) which does not cancel D. Then the first δ(A) − 1 powers of t = ∑_{i=1}^{D} t_{i}ω_{i} are independent over k, so the minimal polynomial of t has degree δ(A). □

Minimal polynomials and local factors. Let u ∈ A be an element of A, whose minimal polynomial m_{u} has degree δ(A), the degree of the minimal polynomial of a generic element in A. The aim of the rest of this section is to describe the factorization properties of the polynomial m_{u}.

Since k is algebraically closed, each zero α of I is in k^{n}. Moreover, if we let 𝔪_{α} ⊂ k[X_{1}, …, X_{n}] be the maximal ideal at α, then the primary decomposition of the zero-dimensional ideal I has the form:

I = ⋂_{α∈V(I)} I_{α},

where I_{α} is a 𝔪_{α}-primary ideal.

We write A_{α} for the local algebra k[X_{1}, …, X_{n}]/I_{α} and denote by N_{α} the exponent of I_{α}, that is the minimal s such that 𝔪_{α}^{s} ⊂ I_{α}. This is also the nil-index of the local algebra A_{α}.

The main result of this section shows that under Assumption 1, the minimal polynomial of u equals

m_{u} = ∏_{α∈V(I)} (U − u(α))^{N_{α}}.

This fact is crucial in proving Proposition 3; we divide its proof into several lemmas.

Lemma 4 Suppose u ∈ A has minimal polynomial m_{u} of degree δ(A). Then the minimal polynomial of u is given by

m_{u} = ∏_{α∈V(I)} (U − u(α))^{δ(A_{α})}.

Proof. By the Chinese Remainder Theorem, A is isomorphic to the product ∏_{α} A_{α}. We denote by u_{α} the images of u in A_{α} under this isomorphism. Let us show that the minimal polynomial of u equals the least common multiple of the minimal polynomials m_{u_{α}}.

For any polynomial P, the image in A_{α} of the element P (u) under the Chinese isomorphism is P (u_{α}). Since m_{u}(u) = 0, this implies that m_{u}(u_{α}) = 0 for all α, therefore all m_{u_{α}} divide m_{u}. Conversely, let m be a polynomial divisible by all m_{u_{α}}. It follows that m(u_{α}) = 0 for all α, so m(u) = 0. Thus, m_{u} divides m and this proves that m_{u} is the lcm of m_{u_{α}}. As a consequence, we have the inequality

δ(A) ≤ ∑_{α} deg m_{u_{α}} ≤ ∑_{α} δ(A_{α}).  (3)

We next show that for all α, the polynomial m_{u_{α}} has the form (T − u(α))^{s_{α}}, for some integer 1 ≤ s_{α} ≤ N_{α}. Since it vanishes on α, the element u_{α} − u(α) belongs to the radical 𝔪_{α} of I_{α}. It follows that the element (u_{α}−u(α))^{N_{α}} belongs to I_{α}, thus is zero in the quotient A_{α}. Therefore, m_{u_{α}} divides (T − u(α))^{N_{α}}, hence it has the form (U − u(α))^{s_{α}}. Since m_{u} equals their lcm, it has the form m_{u} = ∏_{α} (U − u(α))^{r_{α}}.

We show now that r_{α} = δ(A_{α}), for all α. Using Lemma 3 for each α in V(I), we choose elements t_{α} in A_{α} such that the degree of the minimal polynomial of t_{α} is δ(A_{α}). The previous paragraph shows that, up to adding well-chosen constants to the t_{α}, we can assure that their minimal polynomials are pairwise coprime. Let t ∈ A be such that its images in the local algebras A_{α} are the elements t_{α}. Then the minimal polynomial of t is the product ∏_{α} m_{t_{α}}, so its degree is ∑_{α} δ(A_{α}). Thus:

∑_{α} δ(A_{α}) ≤ δ(A).  (4)

Combining the inequalities (3) and (4) with the fact that δ(A) = deg m_{u} equals ∑_{α} r_{α}, we conclude that r_{α} = δ(A_{α}), for all α, so m_{u} has the desired form. □

The next lemma relates the degree δ(A_{α}) to the local exponents N_{α}. We point out that this result depends on the characteristic of the base field k.

Lemma 5 Let a = (a_{1}, …, a_{n}) ∈ k^{n}, let J be a (X_{1} − a_{1}, …, X_{n} − a_{n})- primary ideal of k[X_{1}, …, X_{n}], let N_{J} be the exponent of J and let A_{J} be k[X_{1}, …, X_{n}]/J. If the characteristic of k is zero or greater than N_{J} − 1 then δ(A_{J}) = N_{J}.

Proof. Up to a translation, we may assume that the point a is the origin of k^{n} and that the ideal J is (X_{1}, …, X_{n})-primary.

Let D_{J} be the dimension of A_{J} and β_{1}, …, β_{D_{J}} be a monomial basis of A_{J}. We suppose that β_{1} = 1. By Lemma 3, we can choose t := ∑_{i=1}^{D_{J}} t_{i}β_{i} such that deg m_{t} = δ(A_{J}). Then t − t_{1} is in (X_{1}, …, X_{n}), so (t − t_{1})^{N_{J}} = 0. This shows that the degree of the minimal polynomial of t is at most N_{J}, i.e. δ(A_{J}) ≤ N_{J}.

By assumption, there exists a monomial M of total degree N_{J} − 1 which is not in J. Without loss of generality, M can be written ∏_{i=1}^{d} X_{i}^{α_{i}} for some integer 1 ≤ d ≤ D_{J} and some positive integers α_{i}, of sum N_{J} − 1. We let t be ∑_{i=1}^{d} X_{i}. The coefficient of M in t^{N_{J} −1} is

\frac{(N_{J} − 1)!}{α_{1}! ⋯ α_{d}!},

which is well-defined and nonzero since the characteristic of k is either zero or greater than N_{J} −1. Consequently, t^{N_{J} −1} is not zero, so the minimal polynomial of t is T^{N_{J}}. This shows that N_{J} ≤ δ(A_{J}). The converse inequality follows from the first part of Lemma 4. This concludes the proof. □

To apply this result to each local factor, we need to ensure that the characteristic of k is indeed greater than the exponents of the local factors. This is the objective of the next lemma.

Lemma 6 The exponent of I equals max_{α∈V(I)} N_{α}.

Proof. Let S be the exponent of I and N be max_{α∈V(I)} N_{α}. Then \sqrt{I}^{N} is ∏_{α} 𝔪_{α}^{N}, which is contained in ∏_{α} I_{α} = I, so S ≤ N. Conversely, for any α in V(I), we have

I_{α} + ∏_{α′≠α} 𝔪_{α′}^{S} = (1).

Multiplying both sides by 𝔪_{α}^{S} yields

𝔪_{α}^{S}I_{α} + ∏_{α′∈V(I)} 𝔪_{α′}^{S} = 𝔪_{α}^{S}.

Now S is such that \sqrt{I}^{S} ⊂ I, so ∏_{α′∈V(I)} 𝔪_{α′}^{S} ⊂ I ⊂ I_{α}. The previous equality then shows that 𝔪_{α}^{S} ⊂ I_{α}, for each α, hence S ≥ N. □

The following proposition summarizes the results of this section.

Proposition 6 Let u be in A, such that the degree of its minimal polynomial m_{u} equals the degree of the minimal polynomial of a generic element in A. If furthermore the characteristic of k is zero or greater than the exponent of I, then the polynomial m_{u} factorizes as

m_{u} = ∏_{α∈V(I)} (U − u(α))^{N_{α}}.

Proof. By assumption and using Lemma 6, we are in position to apply Lemma 5 on each local factor A_{α}. Together with Lemma 4, this gives the result. □

6.2 High order derivations, dual spaces and generating series

In this section, we recall the notion of high order derivations and exhibit their connection with the dual spaces of quotient algebras. We also give a description of some generating series of the type R(u, ℓ) which are built upon such derivations.

Basic facts. We start by recalling the notion of high order derivation over an algebra, introduced in [57, 55]. Let k be an arbitrary field and R be a kalgebra. A k-linear map d : R → R is called a k-derivation of order 1 if d(xy) = xd(y)+yd(x), for all x and y in R. High order derivations are defined recursively. A k-linear map d : R → R is called a k-derivation of order N > 1 if the map [d, x] : y ↦ d(xy) − xd(y) − yd(x) is a k-derivation of order N − 1 for all x ∈ R. For N ≥ 1, we write Der_{k}^{N}(R) for the k-vector space of all k-derivations of order N, and we take Der_{k}^{0}(R) = k · 1_{R}. One can easily show that d(1) = 0 for any derivation d of order at least 1 and that Der_{k}^{N}(R) ⊂ Der_{k}^{N+1}(R) for all N ≥ 1, see [8, Section 1]. These two basic properties will be implicitly used in the proofs below.

In the particular case R = k[X_{1}, …, X_{n}], the k-linear map δ^{v} : R → R defined on the monomial basis by:

δ^{v} : X_{1}^{μ_{1}} ⋯ X_{n}^{μ_{n}} ↦ \binom{μ_{1}}{v_{1}} ⋯ \binom{μ_{n}}{v_{n}}X_{1}^{μ_{1}−v_{1}} ⋯ X_{n}^{μ_{n}−v_{n}}

is a k-derivation in Der^{|v|}(R), with |v| = v_{1} +⋯+v_{n}. Remark that the binomial coefficient \binom{β}{α} is defined over any field, for instance as the coefficient of Y^{α} in (1 + Y)^{β}. If k has characteristic zero, then we recover the well-known definition of differential operators:

δ^{v}(P) = \frac{1}{v_{1}! ⋯ v_{n}!} \frac{∂^{v_{1}+···+v_{n}}(P)}{∂_{X_{1}}^{v_{1}} ⋯ ∂_{X_{n}}^{v_{n}}}.

Dual spaces and high order derivations. We next exhibit the connection between high order derivations and dual spaces of quotient algebras. The idea to characterize primary ideals by differential conditions in characteristic zero is due to Gröbner [29]. Similar or more general treatment can be found in [48, 50, 8, 56]. For the sake of completeness, we gather in the following lemma the needed facts, in arbitrary characteristic. Our proof is inspired by that of [8, Proposition 3.2].

Lemma 7 Let a = (a_{1}, …, a_{n}) ∈ k^{n}, let J be a (X_{1} −a_{1}, …, X_{n} −a_{n})-primary ideal of R = k[X_{1}, …, X_{n}] and let N_{J} be the exponent of J. Then there exists a k-basis of the dual { \atop R/J} consisting of elements

L_{i} : P + J ⟼ (D_{i}P)(a),

where D_{1} is the identity map and with D_{i} in Der_{k}^{N_{J} −1}(R) for i > 1.

Proof. Up to a translation, we assume, without loss of generality, that the point a is the origin of k^{n} and that the ideal J is (X_{1}, …, X_{n})-primary. If v is a multiindex with |v| < N_{J}, the k-linear map R → k given by P ↦ (δ^{v}P)(0) factors to a k-linear map δ_{∗}^{v} : R/(X_{1}, …, X_{n})^{N_{J}} → k and the induced maps {δ_{∗}^{v}}_{|v|<N_{J}} form the dual k-basis of the monomial basis {x^{μ}}_{|μ|<N_{J}} of R/(X_{1}, …, X_{n})^{N_{J}}.

The dual of R/J is a k-linear subspace of the dual of R/(X_{1}, …, X_{n})^{N_{J}}, which contains δ_{∗}^{0}. Thus, it admits a k-basis whose elements are of the form L_{1} = δ_{∗}^{0} and L_{i} = ∑_{0<|v|<N_{J}} b_{v}^{(i)}δ_{∗}^{v} for i > 1. We take D_{1} as the identity map

and, for i > 1, D_{i} = ∑_{0<|v|<N_{J}} b_{v}^{(i)}δ^{v}, so that D_{i} ∈ Der_{k}^{N_{J} −1}(R). This proves the lemma. □

High order derivations and generating series. The following result makes a link between the poles of the rational series R(u, ℓ) introduced in Proposition 1 and the order of a derivation.

Lemma 8 Let N ≥ 0, R be a k-algebra, u ∈ R and D in Der^{N}(R). Then there exists c in R such that, for every v ∈ R, there exist N elements c_{j} in R such that the following equality holds in R[[U^{−1}]]:

∑_{i≥0} \frac{D(vu^{i})}{U^{i+1}} = \frac{cv}{(U − u)^{N+1}} + ∑_{j=1}^{N} \frac{c_{j}}{(U − u)^{j}} .

Proof. We proceed by induction on N. We begin by considering the case N = 0, that is, D is the multiplication map by a certain element r in R. We have that

∑_{i≥0} \frac{D(vu^{i})}{U^{i+1}} = rv ∑_{i≥0} \frac{u^{i}}{U^{i+1}} = \frac{rv}{U − u},

so this series has the desired form.

We treat now the inductive step. Let N ≥ 1; we suppose the lemma is true for index N − 1 and we prove it for index N. Let thus D be an arbitrary derivation in Der^{N}(R). By definition, we have the formula D(vu^{i}) = [D, v](u^{i}) + vD(u^{i}) + u^{i}D(v), so

∑_{i≥0} \frac{D(vu^{i})}{U^{i+1}} = ∑_{i≥0} \frac{[D, v](u^{i})}{U^{i+1}} + v ∑_{i≥0} \frac{D(u^{i})}{U^{i+1}} + D(v) ∑_{i≥0} \frac{u^{i}}{U^{i+1}} .  (5)

We analyze each term in this sum separately. Since [D, v] belongs to Der^{N−1}(R), the induction hypothesis shows that

∑_{i≥0} \frac{[D, v](u^{i})}{U^{i+1}} = \frac{c′}{(U − u)^{N}} + ∑_{j=1}^{N−1} \frac{c′_{j}}{(U − u)^{j}}

for some elements c′ and c′_{j} in R. Using the fact that D(u^{i}) = [D, u](u^{i−1}) + uD(u^{i−1}) + u^{i−1}D(u), it is easy to derive the formula

∑_{i≥0} \frac{D(u^{i})}{U^{i+1}} = \frac{1}{U − u} ∑_{i≥0} \frac{[D, u](u^{i})}{U^{i+1}} + \frac{D(u)}{(U − u)^{2}} .

By the inductive hypothesis, the second term in the sum (5) is thus equal to

\frac{v}{U − u} (\frac{c′′}{(U − u)^{N}} + ∑_{j=1}^{N−1} \frac{c′′_{j}}{(U − u)^{j}} + \frac{D(u)}{(U − u)}) ,

for some elements c′′ and c′′_{j} in R depending only on D and u. Finally, the third term in the sum (5) obviously equals

D(v) ∑_{i≥0} \frac{u^{i}}{U^{i+1}} = \frac{D(v)}{U − u}.

Putting these pieces all together in sum (5) completes the proof. □

6.3 Conclusion

The final step of the proof consists in rewriting the series R(u, v ∘ ℓ) so as to exhibit its dependence with respect to v. Lemma 7 shows that for each α ∈ V(I) there exists a family of derivations Δ^{α} = {D_{j}^{α}}_{j=1,...,dim_{k}(A_{α})}, such that the functionals

L_{j}^{α} : P + I_{α} ↦ D_{j}^{α}(P)(α)

form a k-basis of Â_{α}. Furthermore, D_{1}^{α} = 1 and for j > 1, D_{j}^{α} belongs in Der^{N_{α}−1}(k[X_{1}, …, X_{n}]). Using Lemma 8 and evaluating at α, we see that there exist c_{j}^{α} in k, and, for every v ∈ k[X_{1}, …, X_{n}], some elements (c_{j,i}^{α})_{1≤i<N} in k such that

R(u, v ∘ L_{1}^{α}) = ∑_{i≥0} \frac{(vu^{i})(α)}{U^{i+1}} = \frac{v(α)}{U − u(α)}  (6)

and, for j > 1,

R(u, v ∘ L_{j}^{α}) = ∑_{i≥0} \frac{D_{j}^{α}(vu^{i})(α)}{U^{i+1}} = \frac{v(α)c_{j}^{α}}{(U − u(α))^{N_{α}}} + ∑_{i=1}^{N_{α}−1} \frac{c_{j,i}^{α}}{(U − u(α))^{j}} (7)

hold in k[[U^{−1}]].

Let now ℓ be in Â. Since the union ∪_{α}Δ^{α} forms a k-basis of Â, and using the linearity of R(u, v ∘ ℓ) with respect to ℓ, equations (6) and (7) show that for every v the equality

R(u, v ∘ ℓ) = ∑_{α∈V(I)} \frac{v(α)c_{α}}{(U − u(α))^{N_{α}}} + ∑_{α∈V(I)} ∑_{j=1}^{N_{α}−1} \frac{c_{j}^{α}}{(U − u(α))^{j}}  (8)

holds, where c_{α} and c_{j}^{α} belong to k, and c_{α} does not depend on v. If one of the coefficients c_{α} were zero, then for any v, R(u, v ∘ ℓ) could be written with a denominator of degree less than ∑_{α} N_{α}, that is, of degree less than deg m_{u}, by Proposition 6. In particular, for v = 1, R(u, ℓ) would admit a denominator of degree less than deg m_{u}. Since, by Assumption 1, ℓ is such that

R(u, ℓ) = \frac{G_{u,ℓ}}{m_{u}} ,

with G_{u,ℓ} and m_{u} coprime, none of the coefficients c_{α} can be zero.

Recall that by Proposition 6, the polynomial m_{u} writes as

m_{u} = ∏_{α∈V(I)} (U − u(α))^{N_{α}}.

Let Q_{α} be the quotient of m_{u} by (U −u(α))^{N_{α}}, so that Q_{α} takes a nonzero value on u(α). Using equation (8), we deduce that for any v, there exists a polynomial V_{v} ∈ k[U] such that

G_{u,v∘ℓ} = m_{u}R(u, v ∘ ℓ) = ∑_{α∈V(I)} v(α)c_{α}Q_{α}(U) + V_{v}(U) ∏_{α∈V(I)}(U − u(α)).

This implies that G_{u,v∘ℓ}(u(α)) equals v(α)c_{α}Q_{α}(u(α)). Since c_{α}Q_{α}(u(α)) is not zero and is independent from v, this shows that \frac{G_{u,v∘ℓ}}{G_{u,ℓ}} takes the value v(α) at u(α). This proves the proposition.

References

1. M.-E. Alonso, E. Becker, M.-F. Roy, and T. Wörmann. Zeros, multiplicities, and idempotents for zero-dimensional systems. In Algorithms in algebraic geometry and applications (Santander, 1994), pages 1–15. Birkhäuser, Basel, 1996.

2. A. Antoniou. Digital Filters: Analysis and Design. McGraw-Hill Book Co., 1979.

3. J.-M. Arnaudiès and A. Valibouze. Lagrange resolvents. Journal of Pure and Applied Algebra, 117/118:23–40, 1997. Algorithms for algebra (Eindhoven, 1996).

4. E. Becker, J. P. Cardinal, M.-F. Roy, and Z. Szafraniec. Multivariate Bezoutians, Kronecker symbol and Eisenbud-Levine formula. In Algorithms in algebraic geometry and applications (Santander, 1994), pages 79–104. Birkhäuser, Basel, 1996.

5. E. Becker and T. Wörmann. Radical computations of zero-dimensional ideals and real root counting. Mathematics and Computers in Simulation, 42(4-6):561–569, 1996. Symbolic computation, new trends and developments (Lille, 1993).

6. E. R. Berlekamp. Algebraic coding theory. McGraw-Hill Book Co., New York, 1968.

7. G. Björck. Functions of modulus 1 on Z_{n} whose Fourier transforms have constant modulus, and “cyclic n-roots”. In Recent advances in Fourier analysis and its applications (Il Ciocco, 1989), volume 315 of NATO Advance Science Institutes Series C: Mathematical and Physical Sciences, pages 131–140. Kluwer Academic Publishers, Dordrecht, 1990.

8. R. Bommer. High order derivations and primary ideals to regular prime ideals. Archiv der Mathematik, 46(6):511–521, 1986.

9. J. L. Bordewijk. Inter-reciprocity applied to electrical networks. Appl. Sci. Res. B, 1:1–74, 1956.

10. W. Bosma, J. Cannon, and C. Playoust. The Magma algebra system. I. The user language. Journal of Symbolic Computation, 24(3-4):235–265, 1997. See also

http://www.maths.usyd.edu.au:8000/u/magma/.

11. A. Bostan, G. Lecerf, and É. Schost. Tellegen’s principle into practice. In Symbolic and Algebraic Computation, 2003. Proceedings ISSAC’03, Philadelphia, August 2003. To appear.

12. R. P. Brent and H. T. Kung. Fast algorithms for manipulating formal power series. Journal of the ACM, 25(4):581–595, October 1978.

13. B. Buchberger. Gröbner bases: An algorithmic method in polynomial ideal theory. In Multidimensional System Theory, pages 374–383. Reidel, Dordrecht, 1985.

14. P. Bürgisser, M. Clausen, and A. Shokrollahi. Algebraic Complexity Theory. Springer, 1997.

15. L. S. Charlap, R. Coley, and D. Robbins. Enumeration of rational points on elliptic curves over finite fields. Preprint, 1991.

16. D. Coppersmith and S. Winograd. Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation, 9(3):251–280, March 1990.

17. D. Cox, J. Little, and D. O’Shea. Using algebraic geometry. Springer-Verlag, New York, 1998.

18. D. Eisenbud. Commutative algebra, with a view toward algebraic geometry. Graduate Texts in Mathematics. Springer-Verlag, New York, 1995.

19. J.-C. Faugère. A new efficient algorithm for computing Gröbner bases (F_{4}). Journal of Pure and Applied Algebra, 139(1-3):61–88, 1999. Proceedinds of MEGA’98.

20. J.-C. Faugère, P. Gianni, D. Lazard, and T. Mora. Efficient computation of zerodimensional Gröbner bases by change of ordering. Journal of Symbolic Computation, 16(4):329–344, 1993.

21. C. M. Fiduccia. On obtaining upper bounds on the complexity of matrix multiplication. In Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972), pages 31–40, 187–212. Plenum, New York, 1972.

22. C. M. Fiduccia. On the algebraic complexity of matrix multiplication. PhD thesis, Brown Univ., Providence, RI, Center Comput. Inform. Sci., Div. Engin., 1973.

23. P. Gaudry. Algorithmique des courbes hyperelliptiques et applications à la cryptologie. PhD thesis, École polytechnique, 2000.

24. P. Gaudry and É. Schost. Modular equations for hyperelliptic curves. Technical report, École polytechnique, 2002.

25. M. Giusti, J. Heintz, K. Hägele, J. E. Morais, L. M. Pardo, and J. L. Montaña. Lower bounds for Diophantine approximations. Journal of Pure and Applied Algebra, 117/118:277–317, 1997. Algorithms for algebra (Eindhoven, 1996).

26. M. Giusti, J. Heintz, J. E. Morais, J. Morgenstern, and L. M. Pardo. Straight-line programs in geometric elimination theory. Journal of Pure and Applied Algebra, 124:101–146, 1998.

27. M. Giusti, G. Lecerf, and B. Salvy. A Gröbner free alternative for polynomial system solving. Journal of Complexity, 17(1):154–211, 2001.

28. R. Göttfert and H. Niederreiter. On the minimal polynomial of the product of linear recurring sequences. Finite Fields and their Applications, 1(2):204–218, 1995. Special issue dedicated to Leonard Carlitz.

29. W. Gröbner. La théorie des idéaux et la géométrie algébrique. In Deuxième Colloque de Géométrie Algébrique, Liège, 1952, pages 129–144. Georges Thone, Liège, 1952.

30. J. Hopcroft and J. Musinski. Duality applied to the complexity of matrix multiplication and other bilinear forms. SIAM Journal on Computing, 2, 1973.

31. E. Kaltofen. Analysis of Coppersmith’s block Wiedemann algorithm for the parallel solution of sparse linear systems. Mathematics of Computation, 64(210):777–806, 1995.

32. E. Kaltofen, R. M. Corless, and D. J. Jeffrey. Challenges of symbolic computation: my favorite open problems. Journal of Symbolic Computation, 29(6):891–919, 2000.

33. M. Kaminski, D.G. Kirkpatrick, and N.H. Bshouty. Addition requirements for matrix and transposed matrix products. J. Algorithms, 9(3):354–364, 1988.

34. M. Kreuzer and L. Robbiano. Computational commutative algebra. 1. Springer-Verlag, Berlin, 2000.

35. L. Kronecker. Grundzüge einer arithmetischen Theorie der algebraischen Grössen. Journal für die reine und angewandte Mathematik, 92:1–122, 1882.

36. E. Kunz. Kähler differentials. Vieweg advanced lectures in Mathematics. Friedr. Vieweg & Sohn, Braunschweig, 1986.

37. A. Kurosh. Cours d’algèbre supérieure. Éditions Mir, Moscou, 1973.

38. S. Lang. Introduction to algebraic geometry. Interscience Publishers, New York, 1958.

39. Serge Lang. Algebra, volume 211 of Graduate Texts in Mathematics. Springer-Verlag, New York, third edition, 2002.

40. D. Lazard. Solving zero-dimensional algebraic systems. Journal of Symbolic Computation, 13:117–133, 1992.

41. D. Lazard and A. Valibouze. Computing subfields: reverse of the primitive element problem. In Computational algebraic geometry (Nice, 1992), pages 163–176. Birkhäuser Boston, Boston, MA, 1993.

42. G. Lecerf. Une alternative aux méthodes de réécriture pour la résolution des systèmes algébriques. PhD thesis, École polytechnique, 2001.

43. G. Lecerf. Quadratic Newton iteration for systems with multiplicity. Journal of FoCM, 2(3):247–293, 2002.

44. G. Lecerf. Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers. Journal of Complexity, 2003. To appear.

45. J. Little. A key equation and the computation of error values for codes from order domains. Available at http://arXiv.org/math.AC/0303299, 2003.

46. F. S. Macaulay. The Algebraic Theory of Modular Systems. Cambridge University Press, 1916.

47. S. Mallat. Foveal detection and approximation for singularities. Applied and Computational Harmonic Analysis, 2003. To appear.

48. M. G. Marinari, T. Mora, and H. M. Möller. Gröbner bases of ideals defined by functionals with an application to ideals of projective points. Applicable Algebra in Engineering, Communication and Computing, 4(103–145), 1993.

49. J. L. Massey. Shift-register synthesis and BCH decoding. IEEE Transactions on Information Theory, IT-15:122–127, 1969.

50. B. Mourrain. Isolated points, duality and residues. Journal of Pure and Applied Algebra, 117/118:469–493, 1997. Algorithms for algebra (Eindhoven, 1996).

51. B. Mourrain and V. Y. Pan. Solving special polynomial systems by using structured matrices and algebraic residues. In Foundations of computational mathematics (Rio de Janeiro, 1997), pages 287–304. Springer, Berlin, 1997.

52. B. Mourrain and V. Y. Pan. Asymptotic acceleration of solving multivariate polynomial systems of equations. In Proceedings STOC, pages 488–496. ACM Press, 1998.

53. B. Mourrain and V. Y. Pan. Multivariate polynomials, duality, and structured matrices. Journal of Complexity, 16(1):110–180, 2000.

54. B. Mourrain, V. Y. Pan, and O. Ruatta. Accelerated solution of multivariate polynomial systems of equations. SIAM Journal on Computing, 32(2):435–454, 2003.

55. Y. Nakai. High order derivations. I. Osaka Journal of Mathematics, 7:1–27, 1970.

56. U. Oberst. The construction of Noetherian operators. Journal of Algebra, 222(2):595–620, 1999.

57. H. Osborn. Modules of differentials. II. Mathematische Annalen, 175:146–158, 1968.

58. M. S. Paterson and L. J. Stockmeyer. On the number of nonscalar multiplications necessary to evaluate polynomials. SIAM Journal on Computing, 2(1):60–66, March 1973.

59. P. Penfield, Jr., R. Spencer, and S. Duinker. Tellegen’s theorem and electrical networks. The M.I.T. Press, Cambridge, Mass.-London, 1970.

60. F. Rouillier. Solving zero-dimensional systems through the Rational Univariate Representation. Applicable Algebra in Engineering, Communication and Computing, 9(5):433–461, 1999.

61. M. Saito, B. Sturmfels, and N. Takayama. Gröbner deformations of hypergeometric differential equations. Springer-Verlag, Berlin, 2000.

62. P. Samuel. Théorie algébrique des nombres. Hermann, 1971.

63. G. Scheja and U. Storch. Über Spurfunktionen bei vollständigen Durchschnitten. Journal für die reine und angewandte Mathematik, 278-279:174–190, 1975.

64. É. Schost. Sur la résolution des systèmes polynomiaux à paramètres. PhD thesis, École polytechnique, 2000.

65. J. T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM, 27(4):701–717, October 1980.

66. V. Shoup. Fast construction of irreducible polynomials over finite fields. Journal of Symbolic Computation, 17(5):371–391, 1994.

67. V. Shoup. Efficient computation of minimal polynomials in algebraic extensions of finite fields. In Proceedings of the 1999 International Symposium on Symbolic and Algebraic Computation (Vancouver, BC), pages 53–58, New York, 1999. ACM.

68. V. Strassen. Gaussian elimination is not optimal. Numerische Mathematik, 13:354– 356, 1969.

69. B. Tellegen. A general network theorem, with applications. Philips Research Reports, (7):259–269, 1952.

70. J.-A. Thiong Ly. Note for computing the minimum polynomial of elements in large finite fields. In Coding theory and applications (Toulon, 1988), volume 388 of Lecture Notes in Comput. Sci., pages 185–192. Springer, New York, 1989.

71. J. von zur Gathen and J. Gerhard. Modern computer algebra. Cambridge University Press, New York, 1999.

72. D. Wiedemann. Solving sparse linear equations over finite fields. IEEE Transactions on informations theory, IT-32:54–62, 1986.

73. R. Zippel. Probabilistic algorithms for sparse polynomials. In Symbolic and algebraic computation, number 72 in Lecture Notes in Computer Science, pages 216– 226, Berlin, 1979. Springer. Proceedings EUROSAM ’79, Marseille, 1979.