Families of Estimable Terms

Massimo Caboara Dipartimento di Matematica

Università di Genova

caboara@dima.unige.it

Lorenzo Robbiano Dipartimento di Matematica Università di Genova

robbiano@dima.unige.it

Ancora non resta la villa di dì in dì mandarti de’ frutti suoi più serotini.

(L.B. Alberti)

ABSTRACT

In this paper we present a full solution to an open problem in Design of Experiments, a branch of Statistics, which can equally be seen as a problem in Algebraic Geometry. Given a complete set O of estimable terms, we are able to find all the fractions F of a full factorial design, such that \overline{O} is a basis of P/I(F) as a K -vector space. This fact can be rephrased as a result in the theory of zero-dimensional schemes.

Categories and Subject Descriptors

I.1.2 [Symbolic and Algebraic Manipulation]: Algebraic Algorithms; G.3 [Experimental Design]:

Keywords

Gröbner Bases, Border Bases, Estimable Terms, Statistics

1. INTRODUCTION

The concluding sentence of [9] was: The problem of computing Sol(O) in general is still unsolved. So, what is Sol(O)? What kind of difficulties are related to the computation of Sol(O)? And what has all this stuff to do with statistics and with computational commutative algebra?

To answer these questions and motivate the work described in the present paper, we must go back to the introduction of [9], where all the necessary background is described. It is explained how the pioneering paper [7] introduced the new methods of computational commutative algebra, in particular Gröbner bases, into the realm of design of experiments.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for pro�t or commercial advantage, and that copies bear this notice and the full citation on the �rst page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior speci�c permission and/or a fee. ISSAC 2001, UWO, Canada

\begin{matrix}c \\ ◯ \end{matrix}2001 ACM 1-58113-218-2/ 00/ 0008 $5.00

A more complete description of this new branch of mathematics is contained in [6].

Basically, a full factorial design is a finite grid of points, whose defining ideal is the complete intersection of n univariate polynomials in P = K[x_{1}, …, x_{n}]. In statistical jargon a subset F of a full factorial design is called a fraction and one of the main problems in Design of Experiments (DoE) is to describe the sets of terms (power products), whose residue classes form a basis of P/I(F) as a K -vector space. These are described as the sets of terms identified by F. But even more important is the inverse problem. In other words, suppose we are given a tuple O of power products. We would like to be able to find Sol(O), i.e. the set of all those fractions F such that the residue classes of O form a basis of P/I(F) as a K -vector space. The main achievement of [3] was to find a solution of the inverse problem in the particular case that O is the complement of a leading term ideal, and Gröbner basis theory played the key role. However, it was pointed out that not all the cases fit into this scheme (see Example 2.4).

In this paper we employ a new approach to the problem. It uses the notion of a border basis (see Definition 3.4), which is closely related to a result of Mourrain contained in the paper [5]. In this way we are able to give a full answer to the problem. This paper features five sections.

1) Introduction

2) Estimable Terms and Multiplication Matrices

3) Border Bases and Multiplication Matrices

4) An Inverse Problem in Design of experiments

5) Two Examples

In Section 2 we study the relationship between sets of estimable terms (see Definition 2.3) and multiplication matrices (see Definition 2.6). The main results are Proposition 2.5 and Theorem 2.9, which rephrase and broaden some results of [5] (see also [1]).

Section 3 introduces the notion of a marked polynomial, which is borrowed from the paper [8]. Then, as we said, we give the definition of a border basis (see Definition 3.4) and prove the main Theorem 3.7. Inspired by results in [5], it clarifies the relationship between the fact that suitable matrices are pairwise commuting and the fact that a certain set of polynomials is a border basis.

The theoretical background of the results contained in Sections 2 and 3 is more extensively explained in [10].

In Section 4 we develop an algorithm which constructs the solution to the main problem stated at the beginning of the introduction. Our result is contained in the main Theorem 4.6.

Finally, Section 5 presents two examples fully computed with the help of CoCoA (see [2]).

Throughout the entire paper we adopt the conventions and terminology used in the book [4]. In particular P denotes the multivariate polynomial ring K[x_{1}, …, x_{n}] over a field K, and 𝕋^{n} the monoid of terms (power products) in the indeterminates x_{1}, …, x_{n}.

Another important convention that we are using consistently is the following. Tuples of elements are denoted with calligraphic letters, while their underlying set is denoted with the corresponding roman character. For example, when G = (g_{1}, … g_{r}), then automatically G denotes {g_{1}, … g_{r}}.

The already quoted Example 2.4 is used as a running example to illustrate the various definitions and results.

2. ESTIMABLE TERMS AND MULTIPLI-CATION MATRICES

We start off with a zero-dimensional proper ideal I in P . We let π : P ⟶ P/I be the canonical surjective map and μ = dim_{K}(P/I). Then we let O = (h_{1}, …, h_{μ}) be a tuple of polynomials such that \overline{O} = (\overline{h}_{1}, …, \overline{h}_{μ}) is a basis of P/I as a K -vector space. We denote by V (O) the K -vector subspace of P generated by the set of elements of O. We consider three linear maps

NF_{O,I} : P ⟶ V (O) ϑ : V (O) ⟶ K^{μ}

NFV_{O,I} : P ⟶ K^{μ}

so that NF_{O,I}(f) = ∑_{i=1}^{μ} a_{i}h_{i}, ϑ(∑_{i=1}^{μ} a_{i}h_{i}) = ∑_{i=1}^{μ} a_{i}e_{i}, NFV_{O,I} = ϑ ∘ NF_{O,I}, where e_{1}, …, e_{μ} are the vectors of the canonical basis of K^{μ} and the elements a_{i} are defined by π(f) = ∑_{i=1}^{μ} a_{i}\overline{h}_{i}.

Definition 2.1. With this notation we give the following definitions

a) The polynomial NF_{O,I}(f) is called the normal form of f with respect to (O, I) and the linear map NF_{O,I} is called the normal form map with respect to (O, I).

b) The vector NFV_{O,I}(f) is called the normal form vector of f with respect to (O, I) and the linear map NFV_{O,I} is called the normal form vector map with respect to (O, I).

c) If there exists an algorithm which computes NF_{O,I}(f) and NFV_{O,I}(f) for every f ∈ P , we say that the map NF_{O,I} is an explicit normal form map, and NFV_{O,I} is an explicit normal form vector map.

Remark 2.2. It follows from the above definitions that P is the direct sum of the two vector subspaces I and V (O).

Gröbner basis theory tells us that a typical example of a set of polynomials O such that \overline{O} is a a basis of P/I is given by O = 𝕋^{n} \ LT_{σ}(I). In that case O has the important property defined below.

Definition 2.3. Let O be a finite set of power products such that t ∈ O together with t′|t implies that t′ ∈ O. Then O is called an order ideal of monomials or a standard set of power products or a complete set of estimable terms.

However, there are complete sets of estimable terms which form a basis modulo an ideal I, but they are not the complement of LT_{σ}(I), whatever term ordering σ is chosen. To make it clear we recall the following example from [9].

Example 2.4. Consider the following set

{(0, 0), (0, −1), (1, 0), (1, 1), (−1, 1)}

of five points in 𝔸_{ℚ}^{2}, denote by I ⊂ P = ℚ[x, y] the vanishing ideal of this set, and let O = (1, x, y, x^{2}, y^{2}). The evaluation matrix of the elements of O at the points has determinant −4, hence (\overline{1}, \overline{x}, \overline{y}, \overline{x}^{2}, \overline{y}^{2}) is a ℚ-basis of P/I. Consequently, there is a K -linear surjective map P ⟶ K^{5} which sends every polynomial f to the uniquely defined tuple (a_{1}, a_{2}, a_{3}, a_{4}, a_{5}) such that the residue class of f in P/I is a_{1} + a_{2}\overline{x} + a_{3}\overline{y} + a_{4}\overline{x}^{2} + a_{5}\overline{y}^{2} . However, this map is not induced by a map of the type NF_{σ,I}, since {1, x, y, x^{2}, y^{2}} is not of the form 𝕋^{2} \ LT_{σ}(I) for some term ordering σ. To prove this fact, consider f = x^{2} + xy − x − \frac{1}{2} y^{2} − \frac{1}{2} y. It is in I, since it vanishes at the five points. For any term ordering σ, we have x^{2} >_{σ} x and y^{2} >_{σ} y. If x >_{σ} y, then x^{2} >_{σ} xy >_{σ} y^{2} . If y >_{σ} x, then y^{2} >_{σ} xy >_{σ} x^{2} . This means that there are only two possibilities for the leading term of f: either it is x^{2} or y^{2} . In both cases we get that LT_{σ}(f) ∈ LT_{σ}(I) is an element of O.

The following proposition provides a description of zerodimensional proper ideals in terms of multiplication matrices.

Proposition 2.5. Let μ ≥ 1, let φ : P ⟶ K^{μ} be a surjective K -linear map such that I = Ker(φ) is a proper ideal in P , and let w = φ(1), viewed as a column vector.

a) The ideal I is zero-dimensional. Moreover, if we pick O = (h_{1}, …, h_{μ}) so that φ(h_{i}) = e_{i} for i = 1, …, μ, then φ = NFV_{O,I}.

b) There exists a unique n-tuple of pairwise commuting matrices M_{1}, …, M_{n} in the ring Mat_{μ}(K) such that φ(x_{i}f) = M_{i} · φ(f) for all f ∈ P and all i = 1, …, n

c) We have φ(f) = f(M_{1}, …, M_{n}) · w for all f ∈ P .

Proof. To give a proof of a) it is sufficient to observe that dim_{K}(P/I) < ∞, and then use the definition of NFV_{O,I}. To prove b) let h_{1}, …, h_{μ} be polynomials in P such that φ(h_{k}) = e_{k} for k = 1, …, μ. We define M_{i} to be the matrix whose columns are the vectors φ(x_{i}h_{1}), …, φ(x_{i}h_{μ}). To show that M_{i} is well-defined and unique, we pick other polynomials h′_{1}, …, h′_{μ} such that φ(h′_{k}) = e_{k} for k = 1, …, μ. Then h_{k} − h′_{k} ∈ I yields x_{i}(h_{k} − h′_{k}) ∈ I. Hence we have φ(x_{i}h_{k}) = φ(x_{i}h′_{k}) for all i, k. For f ∈ P , we have φ(f) = ∑_{k=1}^{μ} a_{k}e_{k}. Therefore f − ∑_{k=1}^{μ} a_{k}h_{k} ∈ I, and hence x_{i}f − ∑_{k=1}^{μ} a_{k}x_{i}h_{k} ∈ I. It follows that

φ(x_{i}f) = ∑_{k=1}^{μ} a_{k}φ(x_{i}h_{k}) = ∑_{k=1}^{μ} a_{k}M_{i}e_{k} = M_{i}φ(f)

Now we prove that the matrices M_{i} are pairwise commuting. By what we have seen before

M_{i} · M_{j}e_{k} = φ(x_{i}x_{j}h_{k}) = φ(x_{j}x_{i}h_{k}) = M_{j} · M_{i}e_{k}

Consequently, M_{i} · M_{j} = M_{j} · M_{i} for all i, j.

Finally we prove c). By the linearity of φ it suffices to prove the formula in the case of a power product. The formula is correct for a power product of degree 0, and we proceed by induction. Let f = x_{1}^{a_{1}} ⋯ x_{n}^{a_{n}} and without loss of generality we may assume that a_{1} > 0. Then let h = x_{1}^{a_{1}−1} ⋯ x_{n}^{a_{n}}. The inductive assumption and b) imply φ(f) = φ(x_{1}h) = M_{1}φ(h)=M_{1} h(M_{1}, …, M_{n})·w =M_{1}M_{1}^{a_{1}−1}⋯M_{n}^{a_{n}} ·w = M_{1}^{a_{1}} ⋯ M_{n}^{a_{n}} · w = f(M_{1}^{a_{1}} ⋯ M_{n}^{a_{n}}) · w. Now the proof is complete. ⊓ ⊔

Definition 2.6. The matrices M_{1},…,M_{n} described before are called the multiplication matrices of φ.

Corollary 2.7. Let I be a zero-dimensional proper ideal in P , let O = (t_{1}, …, t_{μ}) be a tuple of polynomials such that \overline{O} = (\overline{t}_{1}, …, \overline{t}_{μ}) is a basis of P/I as a K -vector space, let w = NFV_{O,I}(1) viewed as a column vector, and let M_{1}, …, M_{n} be the multiplication matrices of NFV_{O,I}.

a) For f ∈ P we get NF_{O,I}(f) = O·f(M_{1}, …, M_{n})· w, hence NF_{O,I} is an explicit normal form map with respect to (O, I).

b) For f ∈ P we have NFV_{O,I}(f) = f(M_{1}, …, M_{n}) · w, hence NFV_{O,I} is an explicit normal form vector map with respect to (O, I).

Proof. It suffices to prove b), which follows directly from Proposition 2.5.c applied to the map NFV_{O,I}. We observe that for every given input f there is more than an algorithm which computes NFV_{O,I}(f), actually there is an explicit formula. ⊓ ⊔

Example 2.8. We consider Example 2.4 again, and compute M_{1} and M_{2} , which we conveniently call M_{x} and M_{y}. It turns out that

M_{x} =( \begin{matrix}0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & \frac{1}{2} & 0 & \frac{1}{2} \\ 0 & 1 & −1 & 0 & −1 \\ 0 & 0 & \frac{1}{2} & 0 & \frac{1}{2} \end{matrix} ) M_{y} =( \begin{matrix}0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 1 & \frac{1}{2} & 0 & \frac{1}{2} & 1 \\ 0 & −1 & 0 & 0 & 0 \\ 0 & \frac{1}{2} & 1 & \frac{1}{2} & 0 \end{matrix} )

while w = (1, 0, 0, 0, 0)^{tr} . It is immediate to check that M_{x}M_{y} = M_{y}M_{x}. We want to compute NFV_{O,I}(x^{6}y^{2}). We may use the formula of Corollary 2.7 above and get

NFV_{O,I}(x^{6}y^{2}) = M_{x}^{6}M_{y}^{2} · w = (0, 0, \frac{1}{2} , 0, \frac{1}{2} )^{tr}

Therefore NF_{O,I}(x^{6}y^{2}) = \frac{1}{2} y + \frac{1}{2} y^{2} .

The following theorem states a sort of converse to Proposition 2.5. It simply says that n pairwise commuting matrices determine a unique zero-dimensional ideal.

Theorem 2.9. Let μ ≥ 1, let w ∈ K^{μ} be a non-zero vector, and let M_{1}, …, M_{n} be pairwise commuting matrices in Mat_{μ}(K).

a) There exists a unique map φ : P ⟶ K^{μ} with the following properties: a_{1}) φ(1) = w, a_{2}) φ is K -linear, a_{3}) φ(x_{i}f) = M_{i}φ(f) for all f ∈ P , i = 1, …, n.

b) The kernel of φ is a proper zero-dimensional ideal.

c) Moreover, if φ is surjective and we denote Ker(φ) by I, then c_{1}) For every O = (h_{1}, …, h_{μ}) such that φ(h_{i}) = e_{i} for i = 1, …, μ, we have φ = NFV_{O,I}. c_{2}) The matrices M_{1}, …, M_{n} are the multiplication

matrices of NFV_{O,I}.

Proof. Using property a_{2}), it suffices to show how φ is defined on terms. By a_{1}), it is defined on 1. By induction on the degree we may assume that it is uniquely defined on terms of degree at most d − 1. Let t be a term of degree d. Either t is a term in a single indeterminate, say x_{i}, or at least two indeterminates, say x_{i}, x_{j}, have positive exponents. In the first case there a unique way of writing t = x_{i}t′ with deg(t′) = d − 1. Property a_{3}) implies that φ(t) = M_{i}φ(t′), and we are done. Let us examine the second case. We can write t = x_{i}t′ = x_{j}t′′ with terms t′, t′′ of degree d−1. Then there exists a term τ such that t′ = x_{j}τ and t′′ = x_{i}τ. Therefore

φ(t) = M_{i}φ(t′) = M_{i}M_{j}φ(τ) = M_{j}M_{i}φ(τ) = M_{j}φ(t′′)

so that φ(t) is well-defined and forced upon us by the assumptions. Thus we have proved existence and uniqueness.

We show that Ker(φ) is a zero-dimensional ideal. To see that it is an ideal, we let f ∈ Ker(φ), g ∈ P and prove that gf ∈ Ker(φ). By linearity, we may assume that g is a term, and by induction we may assume that g is an indeterminate, say x_{i}. Then φ(x_{i}f) = M_{i}φ(f) = 0. The ideal Ker(φ) is a proper ideal, since φ(1) = w ≠ 0. It is zero-dimensional, because P/ Ker(φ) is a finite-dimensional K -vector space.

Finally we prove c). We know that φ is surjective and Ker(φ) is an ideal, so that every O with the given property is such that \overline{O} is a basis of P/ Ker(φ) as a K -vector space. This proves that φ = NFV_{O,I}. Then we deduce from Proposition 2.5.b) that there exists an n-tuple of multiplication matrices, i.e. a unique n-tuple of pairwise commuting matrices N_{1}, …, N_{n} in the ring Mat_{μ}(K), such that φ(x_{i}f) = N_{i} · φ(f) for all f ∈ P and all i = 1, …, n. Since our matrices satisfy the same condition, we infer that M_{i} = N_{i} for i = 1, …, n, and the proof is complete. ⊓ ⊔

3. BORDER BASES AND MULTIPLICATI-ON MATRICES

We are going to use some ideas developed in [5] to produce an extension of the notion of a Gröbner basis.

Let us recall a definition from [8].

Definition 3.1. A pair (g, t) is said to be a marked polynomial if g is a non-zero polynomial and t ∈ Supp(g). We also say that g is marked by t. Let G = (g_{1}, …, g_{ν}) be a tuple of non-zero polynomials, T = (t_{1}, …, t_{ν}) a tuple of power products. If (g_{1}, t_{1}), …, (g_{ν}, t_{ν}) are marked polynomials, we say that G is marked by T . The tuple G is said to be marked coherently by T if there exists a term ordering σ with the property that t_{i} = LT_{σ}(g_{i}) for every i = 1, …, ν.

In the case that O = {t_{1}, …, t_{μ}} is a complete set of estimable terms (see Definition 2.3) it is useful to define a related set of power products.

Definition 3.2. Let O = {t_{1}, …, t_{μ}} be a complete set of estimable terms. We define

O^{+} = {t ∈ 𝕋^{n} \ O | ∃ i ∈ {i, …, n}, t′ ∈ O with x_{i}t′ = t}

Proposition 3.3. Let I be a zero-dimensional proper ideal in P , let O = {t_{1}, …, t_{μ}} be a complete set of estimable terms such that \overline{O} = (\overline{t}_{1}, …, \overline{t}_{μ}) is a basis of P/I as a K -vector space, and let O^{+} = {b_{1}, …, b_{ν}}.

a) For each j = 1, …, ν there exists a unique linear combination ∑_{k=1}^{μ} a_{kj}t_{k} with a_{kj} ∈ K for k ∈ {1, …, μ}, j ∈ {1, …, ν}, and g_{j} = b_{j} − ∑_{k=1}^{μ} a_{kj}t_{k} ∈ I.

b) The ideal I is generated by {g_{1}, …, g_{ν}}.

Proof. Remark 2.2 tells us that P = V (O)⊕I, from which we deduce a). Let J be the ideal generated by {g_{1}, …, g_{ν}}. To complete the proof we need to show that J = I. Since J ⊆ I it suffices to show that P = V (O) + J, hence it suffices to show that t ∈ V (O) + J for every term t. We know that 1 ∈ V (O), since O is a complete set of estimable terms, so we make induction on deg(t), and assume that the claim is proved up to degree d−1. Let t be a term of degree d > 0. There exists i such that t = x_{i}t′ for a suitable term t′ of degree d − 1. Then t′ = ∑_{i=1}^{μ} a_{i}t_{i} + g with a_{i} ∈ K for i = 1, …, μ and g ∈ J. Therefore t = ∑_{i=1}^{μ} a_{i}x_{i}t_{i} + x_{i}g. Now, either x_{i}t_{i} ∈ O or x_{i}t_{i} ∈ O^{+} . In the first case there is nothing to prove. If x_{i}t_{i} ∈ O^{+}, then x_{i}t_{i} belongs to V (O) + J by assumption, and the proof is complete. ⊓ ⊔

Definition 3.4. Following Proposition 3.3, we call G the set {g_{1}, …, g_{ν}} and let the elements of G be marked by the corresponding elements of O^{+} . Then the pair (G, O^{+}), is called the border basis of I with respect to O.

Example 3.5. We continue the study of our running Example 2.4. In that case we have O = {1, x, y, x^{2}, y^{2}}. We get O^{+} = {xy, x^{3}, y^{3}, x^{2}y, xy^{2}} and we know already that f_{xy} = xy − x − \frac{1}{2} y + x^{2} − \frac{1}{2} y^{2} , f_{x^{3}} = x^{3} − x, f_{y^{3}} = y^{3} − y. It is easy to check that f_{x^{2}y} = x^{2}y − \frac{1}{2} y − \frac{1}{2} y^{2} and f_{xy^{2}} = xy^{2} − x − \frac{1}{2} y + x^{2} − \frac{1}{2} y^{2} . In conclusion, the set F = {f_{xy}, f_{x^{3}}, f_{y^{3}}, f_{x^{2}y}, f_{xy^{2}}} with f_{xy} marked by xy, f_{x^{3}} by x^{3} , f_{y^{3}} by y^{3} , f_{x^{2}y} by x^{2}y, f_{xy^{2}} by xy^{2}, is the border basis of I with respect to O.

We want to make an important connection between multiplication matrices and the notion of a border basis.

Let O = {t_{1}, …, t_{μ}} be a complete set of estimable terms and let O^{+} = {b_{1}, …, b_{ν}}. Let G = {g_{1}, …, g_{ν}} be polynomials marked by the corresponding elements of O^{+} and such that Supp(g_{k}−b_{k}) ⊆ O for k = 1, …, ν. We construct matrices M_{1}, …, M_{n} ∈ Mat_{μ}(K) in the following way. If x_{k}t_{j} ∈O, then the j -column of M_{k} is (0, …, 0, 1, 0, …, 0)^{tr}, with 1 in the position corresponding to the power product x_{k}t_{j}. If x_{k}t_{j} ∈ O^{+} there exists i ∈ {1, …, ν} such that x_{k}t_{j} = b_{i}, and in this case j -column of M_{k} contains the coefficients of (t_{1}, …, t_{μ}) in the representation of the polynomial g_{i}−b_{i} as a linear combination of the elements in O.

Definition 3.6. The matrices M_{1}, …, M_{n} constructed above are called the matrices associated to (G, O^{+}).

Theorem 3.7. Let O = (t_{1}, …, t_{μ}) be such that O is a complete set of estimable terms and let O^{+} = {b_{1}, …, b_{ν}}. Furthermore let G = {g_{1}, …, g_{ν}} be polynomials marked by the corresponding elements of O^{+} so that Supp(g_{k}−b_{k}) ⊆ O for k = 1, …, ν, and let I be the ideal generated by G. The following conditions are equivalent.

i) The matrices M_{1}, …, M_{n} associated to (G, O^{+}) are pairwise commuting.

ii) The pair (G, O^{+}) is the border basis of I with respect

to O. Moreover, if the two equivalent conditions are satisfied we have

a) The ideal I is zero-dimensional, and dim_{K}(P/I) = μ.

b) The tuple \overline{O} is a basis of P/I as a K -vector space.

c) The matrices M_{1}, …, M_{n} are the multiplication matrices of NFV_{O,I}.

Proof. The set O is a complete set of estimable terms, hence 1 ∈ O and we may assume that t_{1} = 1. Let us prove that i) ⇒ ii). We choose w = e_{1} , and if the matrices M_{1}, …, M_{n} are pairwise commuting, we deduce from Theorem 2.9 that there exists a K -linear map φ : P ⟶ K^{μ} such that φ(1) = e_{1} and φ(x_{i}f) = M_{i}φ(f). We claim that φ(t_{i}) = e_{i} for i = 1, …, μ. The claim is true for i = 1 by construction, and we make induction on the degree. So let t_{i} ≠ 1. It is possible to write t_{i} = x_{k}t_{j} for a suitable k and a term t_{j} ∈ O. Then φ(t_{i}) = M_{k}φ(t_{j}) = M_{k}e_{j} where e_{j} = (0, …, 0, 1, 0, …, 0)^{tr} , with 1 in position j. Therefore φ(t_{i}) is the j column of M_{k}, which is e_{i} by construction, and the claim is proved. Therefore \overline{O} is a basis of P/I. We use Proposition 3.3 to see that (G, O^{+}) is the unique border basis of I with respect to O.

Now we prove that ii) ⇒ i). If the pair (G, O^{+}) is the border basis of I with respect to O, then \overline{O} is a basis of P/I, hence we may define NFV_{O,I} : P ⟶ K^{ν} with the property that NFV_{O,I}(1) = e_{1} . We apply Proposition 2.5 to this map and get a unique n-tuple of pairwise commuting matrices N_{1}, …, N_{n} in the ring Mat_{μ}(K), such that NFV_{O,I}(x_{k}f) = N_{k} · NFV_{O,I}(f) for all f ∈ P and all k = 1, …, n. Therefore NFV_{O,I}(x_{k}t_{j}) = N_{k} · NFV_{O,I}(t_{j}) = N_{k} · e_{j}, which is the j^{th} column of N_{k}, and hence N_{k} = M_{k} for every k = 1, …, n.

The proof of a), b), c) is already included in the arguments used to prove the equivalence of i) and ii). ⊓ ⊔ We know from Corollary 2.7 that the existence of the commuting matrices yields an algorithm, actually a formula, for the computation of NF_{(O,I)}(f). Can we achieve the same results by using the border basis (G, O^{+}) as a set of “rewriting rules”? We recall the fundamental theorem of [8]

Theorem 3.8. A tuple G of marked polynomials is marked coherently if and only if every sequence of reduction steps associated to G terminates.

We deduce from it that in the case of a non coherently marked border basis, there exist a polynomial f and an infinite sequence of reduction steps which starts at f. If we look at the multiplication matrices, we see that they encode the way to express the normal form of the product of a normal form by an indeterminate. This implies that in the case of a non coherently marked border basis F , we can use the polynomials in F as rewrite rules and obtain the desired normal form of f, but we must be careful and use them only for rewriting elements in O^{+} . To understand this remark better, let us see the following example. To learn more on that see [10].

Example 3.9. We go back to Example 2.8 and compute NF_{O,I}(x^{6}y^{2}) again, but this time we use the border basis F computed in Example 3.5. We proceed as follows. We write x^{6}y^{2} = x^{3}y^{2} · x^{3} , we use the marked polynomial f_{x^{3}} to make a reduction step and get x^{4}y^{2} which we write x^{4}y^{2} = xy^{2} · x^{3} . We use f_{x^{3}} again and get x^{2}y^{2} = xy·xy. We use f_{xy} and get xy(x+ \frac{1}{2} y−x^{2}+ \frac{1}{2} y^{2}) = x^{2}y+ \frac{1}{2} xy^{2}−x^{3}y+ \frac{1}{2} xy^{3}. We use f_{x^{3}} and then f_{y^{3}} to get x^{2}y + \frac{1}{2} xy^{2} − xy + \frac{1}{2} xy = − \frac{1}{2} xy +x^{2}y + \frac{1}{2} xy^{2}. Finally we use f_{xy}, f_{x^{2}y}, f_{xy^{2}} and get − \frac{1}{2} (−x^{2} + \frac{1}{2} y^{2} +x+ \frac{1}{2} y)+ \frac{1}{2} y^{2} + \frac{1}{2} y + \frac{1}{2} (x^{2} + \frac{1}{2} y^{2} +x+ \frac{1}{2} y) = \frac{1}{2} y + \frac{1}{2} y^{2} . Therefore NF_{O,I}(x^{6}y^{2}) = \frac{1}{2} y + \frac{1}{2} y^{2}, which agrees with the value computed in Example 2.8.

We could follow different paths, but suppose we try to reduce x^{2}y^{2} in the following way. We reduce xy to x+ \frac{1}{2} y − x^{2} + \frac{1}{2} y^{2} , hence we reduce x^{2}y^{2} to (x + \frac{1}{2} y − x^{2} + \frac{1}{2} y^{2})^{2} . This is equal to x^{4} − x^{2}y^{2} + \frac{1}{4} y^{4} − 2x^{3} − x^{2}y + xy^{2} + \frac{1}{2} y^{3} + x^{2} + xy + \frac{1}{4} y^{2} , and we see the power product x^{2}y^{2}. Now it is easy to proceed with a strategy of rewriting that produces x^{2}y^{2} periodically, and hence does not terminate.

4. AN INVERSE PROBLEM IN DESIGN OF EXPERIMENTS

We start this section by recalling some basic definitions in the theory of DoE.

Definition 4.1. Let E_{1}, E_{2}, …, E_{n} be finite subsets of K. Then the Cartesian product D = E_{1}×E_{2}×⋯×E_{n} ⊂ K^{n} is a finite set of points called a full factorial design. If moreover #(E_{i}) = l_{i} for i = 1, …, n, then we say that E_{1} × E_{2} × ⋯ × E_{n} has levels l_{1}, l_{2}, …, l_{n}. An l^{n} -design is a full factorial design with l_{1} = l_{2} = ⋯ = l_{n} = l.

Let E_{1} = {a_{11}, … a_{1 l_{1}}}, …, E_{n} = {a_{n1}, … a_{n l_{n}}} and let D = E_{1} × ⋯ × E_{n}. Then let f_{k} = ∏_{i=1}^{l_{k}}(x_{k} − a_{ki}) for every k = 1, …, n. Then the defining ideal of D viewed as as an affine subvariety of 𝔸_{n}(K) is I(D) = (f_{1}, …, f_{n}). Moreover, the set

O(D) = {x_{1}^{a_{1}}x_{2}^{a_{2}} ⋯ x_{n}^{a_{n}} | 0 ≤ a_{k} ≤ l_{k} for k = 1, …, n}

is a complete set of estimable terms such that \overline{O(D)} is a basis of P/I(D) as a K -vector space.

Definition 4.2. The n polynomials f_{1}, …, f_{n} are called the canonical polynomials of D. The set O(D) is called the complete set of estimable terms of D.

Definition 4.3. Let D be a full factorial design and let F ⊂ D. It is called a fractional factorial design or a fraction of D. Its defining ideal is called I(F).

Now we are ready to state a main problem in DoE.

Problem 4.4. Let D be a full factorial design, and let O ⊂ O(D) be a complete set of estimable terms. What are the fractions F of D such that \overline{O} is a basis of P/I(F) as a K -vector space?

Before we start to investigate the problem, we need a technical result which is a slight modification of Lemma 3.2. from [3], and whose proof is included here for the sake of completeness.

Lemma 4.5. Let D be a full factorial design and denote by I(D) = (f_{1}, …, f_{n}), where f_{1}, …, f_{n} are its canonical polynomials. Denote by \overline{K} the algebraic closure of K and let I be a proper ideal of \overline{K}[X] such that I(D) ⊂ I. Then a) I is a radical ideal, which defines a Fraction of D.

b) I can be defined by polynomials in K[X].

c) The polynomials of every border basis of I are elements of K[X].

Proof. Let 𝔸n ; \overline{K} be the affine space of dimension n over \overline{K}. Let F ⊂ 𝔸n ; \overline{K} be the set of zeroes of I. From the fact that I(D) ⊂ I it follows that F ⊆ D. By localizing the ring A = \overline{K}[X]/I at the maximal ideals M corresponding to the points of D, we have that either IA_{M} = (1) or IA_{M} = MA_{M}. Therefore I is a radical ideal, hence it is the defining ideal of F.

Finally, condition c) follows from Proposition 3.3. ⊓ ⊔

We observe that O = {t_{1}, …, t_{μ}} is given, which implies that O^{+} = {b_{1}, …, b_{ν}} is also given. We know that O is a complete set of estimable terms, hence 1 ∈ O, and we may assume that t_{1} = 1. Moreover, D is fixed, which implies that its canonical polynomials f_{1}, …, f_{n} are given. A fraction F is a solution of Problem 4.4 if and only if \overline{O} is a basis of P/I(F) and f_{i} ∈ I(F) for i = 1, …, n. Proposition 3.3 shows that, given O, ideals I such that \overline{O} is a basis of P/I are in one to one correspondence to border bases (g_{1}, …, g_{ν}) marked by (b_{1}, …, b_{ν}). This fact suggests the following algorithm Theorem 4.6. Let D be a full factorial design with levels l_{1}, l_{2}, …, l_{n}, let f_{1}, …, f_{n} be the canonical polynomials of D, and let O ⊂ O(D) be a complete set of estimable terms. Consider the following sequence of instructions.

1) Subdivide the set O^{+} into two subsets, O_{1}^{+} , O_{2}^{+} , where O_{1}^{+} = O^{+} ∩ {x_{1}^{l_{1}}, …, x_{n}^{l_{n}}}, O_{2}^{+} = O^{+} \ O_{1}^{+} .

2) Subdivide the set F = {f_{1}, …, f_{n}} into two subsets, F_{1} , F_{2} , where F_{1} = {f_{i} ∈ F | x_{i}^{l_{i}} ∈ O^{+}}, F_{2} = F \F_{1} , and f_{i} is marked by x_{i}^{l_{i}} for every f_{i} ∈ F_{1} .

3) Let η = #(O_{2}^{+}), and for every power product b_{k} ∈ O_{2}^{+} let g_{k} = b_{k} + ∑_{j=1}^{μ} a_{kj}t_{j} be polynomials in the ring K[A][x_{1}, …, x_{n}], where A is a list of μ × η independent new indeterminates a_{kj}. Mark g_{k} by b_{k} for k = 1, …, η, and call G_{2} the set of these marked polynomials.

4) Let G = F_{1} ∪ G_{2} and construct M_{1}, …, M_{n}, the matrices associated to (G, O^{+}).

5) Impose that M_{1}, …, M_{n} are pairwise commuting.

6) Let w = (1, 0 …, 0)^{tr} and impose that the equations f_{k}(M_{1}, …, M_{n}) · w = (0, 0, …, 0)^{tr} hold true for every f_{k} ∈ F_{2} .

7) Construct the ideal I(O) in K[A] generated by the polynomials arising from Steps 5) and 6).

This is an algorithm which returns an ideal I(O) in K[A] with the following properties

a) The ideal I(O) is zero-dimensional and defined over the field K.

b) The zeros of I(O) are in one-to-one correspondence with the solutions of Problem 4.4

Proof. Let N = μ × η. By considering Step 5), we see that every zero of I(O) in 𝔸N ; \overline{K} corresponds to an n-tuple of commuting matrices M_{1}, …, M_{n}. By Theorem 3.7 we deduce that it corresponds to the unique border basis of an ideal I with respect to O. By considering Step 6), we see that I(D) ⊂ I. Now Lemma 4.5.c implies that the polynomials of a border basis of I are in P , and hence we have proved that all the zeros of I(O) are in 𝔸_{K}^{N}, i.e. that I(O) is defined over K. We use Lemma 4.5.a to see that I is radical, hence it is the ideal of a finite subset of points of D. But there is only a finite number of such subsets, which proves that I(D) ⊂ I is zero-dimensional. This finishes the proof of a). But the same argument shows that there is a one-to-one correspondence between the zeros of I(O) and the fractions F of D such that \overline{O} is a basis of P/I(F). This proves b), and the proof is complete. ⊓ ⊔

Remark 4.7. It should be noted that the set of solutions of Problem 4.4 is always non-empty, since it contains the so-called distracted fractions (see [11]).

Remark 4.8. If we are not satisfied with the representation of a fraction F via its border basis, we may perform the extra step of solving the corresponding system of polynomial equations and actually find the points p_{1}, …, p_{μ} ∈ 𝔸_{K}^{n} such that F = {p_{1}, …, p_{μ}}.

5. TWO EXAMPLES

5.1 Example 1

Let D ⊂ ℚ^{2} be the full factorial design whose canonical polynomials are f_{1} = x^{3} − x and f_{2} = y^{2} − 1. Then we have F = {f_{1}, f_{2}} and O(D) = {1, x, y, x^{2}, xy, x^{2}y}. The set O = {1, x, y} ⊂ O(D) is a complete set of estimable terms.

We apply the algorithm described in Theorem 4.6 to this example. We subdivide F in the two subsets F_{1} = {y^{2} − 1} and F_{2} = {x^{3}−x}, and mark y^{2}−1 by y^{2} . We subdivide the set O^{+} = {x^{2}, xy, y^{2}} in the two subsets O_{1}^{+} = {y^{2}} and O_{2}^{+} = {x^{2}, xy}. We introduce new independent indeterminates a_{11}, a_{12}, a_{13}, a_{21}, a_{22}, a_{23} , and construct the polynomials g_{1} = x^{2} + a_{11} + a_{12}x + a_{13}y, g_{2} = xy + a_{21} + a_{22}x + a_{23}y in K[A][x, y] and we mark them by x^{2} and xy respectively. We obtain G = {f_{2}, g_{1}, g_{2}}.

The matrices associated to (G, O^{+}) are

M_{x} = ( \begin{matrix}0 & −a_{11} & −a_{21} \\ 1 & −a_{12} & −a_{22} \\ 0 & −a_{13} & −a_{23} \end{matrix} ) M_{y} = ( \begin{matrix}0 & −a_{21} & 1 \\ 0 & −a_{22} & 0 \\ 1 & −a_{23} & 0 \end{matrix} )

We impose that M_{x} and M_{y} commute by imposing that the matrix MxMy − MyMx is the zero matrix, that is

( \begin{matrix}0 & a_{12}a_{21} − a_{11}a_{22} − a_{21}a_{23} − a_{13} & a_{2,1}a_{22} − a_{23} \\ 0 & a_{22}a_{23} − a_{21} & −a_{22}^{2} + 1 \\ 0 & a_{13}a_{22} − a_{12}a_{23} + a_{23}^{2} + a_{11} & −a_{22}a_{23} + a_{21} \end{matrix} ) (1)

is the zero matrix.

We impose that (M_{x}^{3} − M_{x}) · (1, 0, …, 0)^{tr} = 0 and get the following polynomial equations

\begin{matrix}a_{11}a_{12} + a_{13}a_{21} = 0 \\ a_{12}^{2} + a_{13}a_{22} − a_{11} − 1 = 0 \\ a_{12}a_{13} + a_{13}a_{23} = 0 \end{matrix} (2)

We let I(O) be the ideal in K[A] generated by the entries of the matrix (1) and the polynomials in (2). A small computation carried on with CoCoA shows that I(O) is a zero-dimensional, radical ideal and its multiplicity is 18.

In conclusion, out of the 20 = \binom{6}{3} triples of points in D, there are 18 triples which solve Problem 4.4.

5.2 Example 2

Let D ⊂ ℚ^{2} be the full 3^{2} factorial design whose canonical polynomials are f_{1} = x^{3} − x and f_{2} = y^{3} − y. In this case F = {f_{1}, f_{2}} and O(D) = {1, x, y, x^{2}, xy, y^{2}, x^{2}y, xy^{2}}. Let O = {1, x, y, x^{2}, y^{2}} ⊂ O(D). It is a complete set of estimable terms.

We get O^{+} = {x^{3}, y^{3}, xy, x^{2}y, xy^{2}} and we easily check that F_{1} = F = {f_{1}, f_{2}} and F_{2} = ∅; we mark (f_{1}, f_{2}) by (x^{3}, y^{3}). We have O_{1}^{+} = {x^{3}, y^{3}} and O_{2}^{+} = {xy, x^{2}y, xy^{2}}. We introduce new independent indeterminates

a_{11}, …, a_{15}, a_{21}, …, a_{25}, a_{31}, …, a_{35}

and construct the polynomials

g_{1} = xy + a_{11} + a_{12}x + a_{13}y + a_{14}x^{2} + a_{15}y^{2} g_{2} = x^{2}y + a_{21} + a_{22}x + a_{23}y + a_{24}x^{2} + a_{25}y^{2} g_{3} = xy^{2} + a_{31} + a_{32}x + a_{33}y + a_{34}x^{2} + a_{35}y^{2}

in K[A][x, y]. We mark them by xy, x^{2}y and xy^{2} respectively. We obtain G = F_{1} ∪ G = {f_{1}, f_{2}, g_{1}, g_{2}, g_{3}}.

The matrices associated to (G, O^{+}) are

M_{x} = ( \begin{matrix}0 & 0 & −a_{11} & 0 & −a_{31} \\ 1 & 0 & −a_{12} & 1 & −a_{32} \\ 0 & 0 & −a_{13} & 0 & −a_{33} \\ 0 & 1 & −a_{14} & 0 & −a_{34} \\ 0 & 0 & −a_{15} & 0 & −a_{35} \end{matrix} ) M_{y} = ( \begin{matrix}0 & −a_{11} & 0 & −a_{21} & 0 \\ 0 & −a_{12} & 0 & −a_{22} & 0 \\ 1 & −a_{13} & 0 & −a_{23} & 1 \\ 0 & −a_{14} & 0 & −a_{24} & 0 \\ 0 & −a_{15} & 1 & −a_{25} & 0 \end{matrix} )

We impose that M_{x} and M_{y} commute by imposing that the matrix MxMy − MyMx is the zero matrix, and get

\begin{matrix}a_{11}a_{13} + a_{15}a_{31} + a_{21} \\ a_{11}a_{12} + a_{14}a_{21} + a_{31} \\ a_{11}a_{23} + a_{25}a_{31} + a_{11} \\ a_{11}a_{32} + a_{21}a_{34} + a_{11} \\ a_{12}a_{13} + a_{15}a_{32} − a_{11} − a_{14} + a_{22} \\ a_{12}^{2} + a_{14}a_{22} + a_{32} \\ a_{12}a_{23} + a_{25}a_{32} + a_{12} − a_{21} − a_{24} \\ a_{12}a_{32} + a_{22}a_{34} + a_{12} \\ a_{13}^{2} + a_{15}a_{33} + a_{23} \\ a_{12}a_{13} + a_{14}a_{23} − a_{11} − a_{15} + a_{33} \\ a_{13}a_{23} + a_{25}a_{33} + a_{13} \\ a_{13}a_{32} + a_{23}a_{34} + a_{13} − a_{31} − a_{35} \\ a_{13}a_{14} + a_{15}a_{34} − a_{12} + a_{24} \\ a_{12}a_{14} + a_{14}a_{24} + a_{34} \\ a_{14}a_{23} + a_{25}a_{34} + a_{14} − a_{22} \\ a_{14}a_{32} + a_{24}a_{34} + a_{14} \\ a_{13}a_{15} + a_{15}a_{35} + a_{25} \\ a_{12}a_{15} + a_{14}a_{25} − a_{13} + a_{35} \\ a_{15}a_{23} + a_{25}a_{35} + a_{15} \\ a_{15}a_{32} + a_{25}a_{34} + a_{15} − a_{33} \end{matrix} (3)

There is no Step 6) to be performed since F_{2} = ∅. Moreover I(O) is generated by the polynomials (3). A computation carried on with CoCoA shows that I(O) is zero-dimensional, radical and its multiplicity is 81.

In conclusion, out of the 126 = \binom{9}{5} five-tuples of points in D, there are 81 five-tuples which solve Problem 4.4.

One of the solutions of I(O) is the point p ∈ ℚ^{15} whose coordinates are

\begin{matrix}a_{11} = 0 & a_{12} = −1 & a_{13} = − \frac{1}{2} & a_{14} = 1 & a_{15} = − \frac{1}{2} \\ a_{21} = 0 & a_{22} = 0 & a_{23} = − \frac{1}{2} & a_{24} = 0 & a_{25} = − \frac{1}{2} \\ a_{31} = 0 & a_{32} = −1 & a_{33} = − \frac{1}{2} & a_{34} = 1 & a_{35} = − \frac{1}{2} \end{matrix}

By substituting those values in G ⊂ ℚ(A)[x, y] we have the border basis G_{p} ⊂ ℚ[x, y] whose elements are

x^{3} − x, y^{3} − y, xy − x − \frac{1}{2} y + x^{2} − \frac{1}{2} y^{2}, x^{2}y − \frac{1}{2} y − \frac{1}{2} y^{2}, xy^{2} − x − \frac{1}{2} y + x^{2} − \frac{1}{2} y^{2} marked by x^{3}, y^{3}, xy, x^{2}y, xy^{2} respectively.

The fraction F_{p} of D defined by G_{p} is

{(0, 0), (0, −1), (1, 0), (1, 1), (−1, 1)}

We have already met this fraction in Example 2.4.

5.3 A Final Remark

A natural question is how many of the 81 fractions we have found in Example 5.2 can be obtained via Gröbner basis techniques, as explained in [3]. We have seen in Example 2.4 that at least F_{p} cannot be found with such methods.

Indeed, reasoning as in Example 2.4, it is easy to see that the fractions which correspond to solutions of I(O) and have the property that a_{14}, a_{15} are both different from zero, cannot be found with Gröbner basis techniques. The number of such solutions is 36.

All other fractions can be found with Gröbner basis methods. Let us show how by examining G = (f_{1}, f_{2}, g_{1}, g_{2}, g_{3}). The fact that G is not marked coherently by the tuple (x^{3}, y^{3}, xy, x^{2}y, xy^{2}) is an obstruction to the applicability of Gröbner methods. This obstruction can be removed if the coefficient of either x^{2} or y^{2} in g_{1} is zero. If any of these conditions is met, then G is marked coherently by (x^{3}, y^{3}, xy, x^{2}y, xy^{2}), the hypothesis of Corollary 2.14 of [3] hold and we can thus proceed with the Gröbner methods explained there.

If we do that we find the remaining 45 solutions.

6. REFERENCES

[1] W. Auzinger, H.J. Stetter, An elimination algorithm for the computation of all zeros of a system of multivariate polynomial equations, In: Conference in Numerical Analysis, ISNM vol. 86, 11–30, Birkäuser Verlag.

[2] A. Capani, G. Niesi, L. Robbiano, CoCoA, a system for doing Computations in Commutative Algebra, (1995). Available via anonymous ftp from

       cocoa.dima.unige.it.

[3] M. Caboara, L. Robbiano, Families of ideal in Statistics, Proceedings of the ISSAC-97 Conference (Maui, Hawaii, July 1997) Küchlin ed., (1997), 404-409.

[4] M. Kreuzer, L. Robbiano, Computations in Commutative Algebra 1, Springer (2000).

[5] B. Mourrain, A New Criterion for Normal Form Algorithms, Proc. of the 13th International Symposium, Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, LNCS 1719, (1999), 430–443.

[6] G. Pistone, E. Riccomagno, H.P. Wynn, Algebraic Statistics: Computational Commutative Algebra in Statistics, Monographs on Statistics and Applied Probability 89 Chapman&Hall/CRC (2000).

[7] G. Pistone G., H.P. Wynn, Generalised confounding and Gröbner bases, Biometrika 83-3, (1996), 653–666.

[8] A. Reeves, B. Sturmfels, A Note on Polynomial Reduction, J. Symbolic Comput. 16 (1993), 273–277.

[9] L. Robbiano, Gröbner bases and Statistics, In B.Buchberger, F.Winkler, editors, Gröbner Bases and Applications (Proc. of the Conf. 33 years of Gröbner bases), volume 251 of London Mathematical Society Lecture Note Series, Cambridge University Press (1998), 179–204.

[10] L. Robbiano, Zero Dimensional Ideals or The inestimable value of Estimable Terms, Proceedings of the Academy Colloquium ”Constructive Algebra and Systems Theory”, Amsterdam 1 - 3 November 2000

[11] L. Robbiano, M.P. Rogantin Full Factorial Designs and Distracted Fractions, In B.Buchberger, F.Winkler, editors, Gröbner Bases and Applications (Proc. of the Conf. 33 years of Gröbner bases), volume 251 of London Mathematical Society Lecture Note Series, Cambridge University Press (1998), 473–482.