Gröbner Bases and Statistics

Lorenzo Robbiano ^{1}

Abstract

This survey describes how to use methods of Algebraic Geometry and Commutative Algebra to study some problems arising in Design of Experiments, a branch of Statistics.

Contents

1 - Introduction

2 - From Design of Experiments to Commutative Algebra 3 - Computing Confounding Polynomials: the BM-Algorithm 4 - Identifying the Models 5 - Some Problems

Problem 1: Given a Fraction, what are the Models identifiable by it? Problem 2: Given a Model, what are the Fractions which identify it? Problem 3: Which Fractions identify the highest (lowest) number of

Models?

6 - Concluding Remarks

1 Introduction

Whenever two branches of Science meet it is a great time for research. Sometimes such events are unexpected, sometimes they are more natural. In this survey I will try to set up a foundation for a fruitful interaction between Design of Experiments (DoE) on one side and Commutative Algebra, Algebraic Geometry and Computer Algebra on the other. DoE is a branch of Statistics, and in its history algebraic methods are not rare, so this kind of interaction falls into the category of natural events. Furthermore, it is now clear how strong was, and still is, the influence of Computer Algebra methods in Commutative Algebra and Algebraic Geometry: for instance Gröbner basis theory, which originated with the fundamental work by Buchberger (see Buchberger (1965), Buchberger (1970) and Buchberger (1985)), is nowadays recognized to be a basic tool applicable in several sectors of Science. From now on we can say that this influence extends into the realm of DoE.

Let us have a look at the main concepts in DoE by discussing an example. Suppose that a firm wants to introduce a new product, say a portable telephone, into the market. They need to obtain useful a priori information from the potential customers. Let’s say that the strategy of the firm is to test the reaction to five features of the telephone: colour, shape, weight, material and price. Let us associate the variables C with colour, S with shape, W with weight, M with material, P with price and suppose that for each variable, three values are chosen, which can be coded as {0, 1, 2}. The interpretation is, for instance, that C = 0 means red, C = 1 means green, C = 2 means black; W = 0 means weight in between 200 and 250 grams, and so on. Therefore the particular characteristics of a portable telephone are codified by a point whose coordinates are five integers chosen from {0, 1, 2}. So the point (0, 0, 0, 0, 0) could correspond to a red, rounded, light, plastic, low priced telephone, while the point (0, 1, 1, 0, 2) could correspond to a red, slanted, medium weight, plastic, high priced telephone, and so on. A selected set of potential customers should be asked to rate the various possibilities, i.e. the various points, on a scale from 0 to 10, say.

1Partially supported by the Consiglio Nazionale delle Ricerche (CNR).

Similar examples can be drawn from several fields of application, ranging from industrial design to chemistry, marketing, and finance. The method is always to draw information from experiments, and the goal can be to gain information from the market, to detect failures in a complex system, to find the correct blend of substances in a chemical product and so on (see for instance Box et al. (1978)). The nice feature of these examples is that all of them can be modeled in the same way, that is to say with a finite set of experimental treatments or points, which are described by their coordinates. The set of all these points is called a Design. A complete set where all combinations of values are allowed, such as the 3^{5} points in our example, is a product set called in Statistics a Full (or Full Factorial) Design (see Definition 2.17).

Let us go back to our example. We call D the set of the 3^{5} = 243 points, and suppose for a moment that we can ask the customers to rate all of them. Having done that, to each point we associate for instance the mean value of the answers, and we get a function y : D → ℚ (the choice of the mean value as an example is motivated by the fact that we are going to treat models without replications). We observe that every function from a finite set of points to a field is a polynomial function (see Corollary 2.14), hence y = f(C, S, W, M, P) with f a polynomial in ℚ[C, S, W, M, P]. Such a polynomial function is called a polynomial model for our design. It encodes all the relevant information, and from it the firm can deduce fundamental knowledge for the final decision on the characteristics of the portable telephone.

However, in this case (as well as in other fundamental situations) there is an obstacle: no potential customer would be willing to rate 243 cases. The problem is to determine a suitable subset F of D, called a Fraction, from which we can equally well reconstruct a good model. For instance it would be nice to be able to identify the model, simply from rating a small subset of D.

Before we go on let’s introduce some commutative algebra. The polynomial X(X −1)(X −2) = X^{3} −3X^{2} +2X vanishes on the set {0, 1, 2}. This fact can be interpreted as saying that the polynomial functions X^{3}, X^{2}, X are linearly dependent over {0, 1, 2}. In fact the function X^{3} takes the same values as 3X^{2} − 2X, which, in statistical jargon, is expressed by saying that X^{3} and 3X^{2} − 2X are confounded by {0, 1, 2}.

Also in the multivariate case a full design has canonical confounding polynomials (or equations) (see Definition 2.19) and a canonical basis of powerproducts (see Definition 2.20), O(D). In our example (henceforth we use X_{1}, X_{2}, X_{3}, X_{4}, X_{5} instead of C, S, W, M, P) the canonical confounding polynomials are f_{i} := X_{i}(X_{i} − 1)(X_{i} − 2), i := 1, …, 5. All together they generate I(D), the defining ideal of D (see Lemma 2.2). The canonical basis O(D) is the set of 243 power-products {X_{1}^{a_{1}}X_{2}^{a_{2}} ⋯ X_{5}^{a_{5}} | a_{i} = 0, 1, 2; i := 1, …, 5}.

Given a full design D, a fraction F of it is simply a subset, but from the algebraic point of view, its description is no longer canonical. Of course the ideal I(F), which defines the given fraction, contains I(D), the defining ideal of D, simply because every polynomial which vanishes on D automatically vanishes on F. So, there are more confounding polynomials, which have to be joined to the canonical polynomials of D (see Definition 4.2), and the key point is to be able to draw information about a given fraction from its confounding polynomials. With the purpose of better popularizing the subject, we describe in Section 3 the best known algorithm for computing the defining ideal of any given finite set of points, the Buchberger-Möller Algorithm. Then we show in Section 4 that for every fraction there exists a unique canonical confounding polynomial (see Theorem-Definition 4.5), though it is often hard to extract further relevant information from it. The first attempt to solve the problem of identifying a model from a fraction can be done easily by linear algebra methods (see Theorems 4.12 and 4.14). But we want much more. For instance, if we go back to our guiding example, we may envisage the following potential situations. The first case is that the firm wants to use a particular fraction F of D. The reason could be that they have already run previous experiments for similar purposes. In this case the question is: given a fraction, what are the models identifiable by it? This is our Problem 1 of Section 5. The second, and most important case is that the firm already knows the support of the model, i.e. the set of the power-products actually occurring in the polynomial which describes the model. It is clear that such support is contained in O(D), so, to identify the model, it suffices to identify the coefficients. For instance the coefficient of X_{1} quantifies the importance that the customers give to the colour of the telephone. The coefficient of X_{1}X_{2} quantifies the importance given to the interaction between colour and shape and so on. Indeed in Statistics the indeterminates are called main effects and the other power-products, which involve more than one indeterminate, interactions. Suppose that via some previously acquired knowledge, the firm knows that only the constant and the main effects are relevant; then the model has the shape y = a_{0} + a_{1}X_{1} + a_{2}X_{2} + a_{3}X_{3} + a_{4}X_{4} + a_{5}X_{5}. One has to identify only six coefficients. A first basic remark (see Theorem 2.6 and Corollary 2.12) shows that it suffices to consider fractions with six points, but then the question is: what are the fractions of D, which identify the six coefficients? This is our Problem 2 of Section 5, one of the most important in DoE.

At this point Gröbner bases are most welcome. It was in Pistone and Wynn (1996) that for the first time a bridge was built between the two theories, and Problem 1 was introduced and partially solved. More solutions to these problems, in particular to Problem 2, were given in Caboara and Robbiano (1997) and Robbiano and Rogantin (1998), where Gröbner bases play a fundamental rôle.

Section 5 is entirely devoted to the discussion of these problems, including our Problem 3, which is a variant and was first tackled in Caboara et al. (1997). We explain how Gröbner bases can be used to clarify many aspects, and also what their limits are. Needless to say, there are many questions left open; this survey reports on some of them and includes some new results, for instance Theorem 5.16. But the main emphasis here is to clarify the importance of using algebraic methods in DoE.

I hope that this survey may be used by both statisticians and algebraists as a guide to the exploration of this beautiful field.

Here let me mention that many detailed examples are included, and it is my pleasure to say that all the computations were performed with our system CoCoA (see Capani et al. (1995) and Capani et al. (1997)); in particular a package written in CoCoAL (the high level programming language of CoCoA) by Caboara, called statfamilies, was intensively used to produce Example 5.5 and others. For interested researchers, the package, as well as the system CoCoA, are available at the URL http://cocoa.dima.unige.it.

Special thanks are due to G. Pistone, E. Riccomagno, M.P. Rogantin and H.P. Wynn, who introduced me to this beautiful subject. Finally, warm thanks are due to J. Abbott and M.P. Rogantin, who read the first draft and supplied valuable help and advice.

2 From Design of Experiments to Commutative Algebra

We start by recalling some basic facts from commutative algebra and algebraic geometry. Throughout the section we use R for k[X_{1}, …, X_{n}]. The first thing to mention is that every polynomial in R can be interpreted as a function from k^{n} to k. Indeed, to every element P ∈ k^{n} one associates f(P) ∈ k.

Definition 2.1 Let X ⊂ k^{n}. Then we call

I(X) := {f ∈ R | f(P) = 0 ∀P ∈ X }

Lemma 2.2 The following facts hold 1) I(X) is an ideal, which is called the defining ideal of X.

2) I(X) is radical.

Proof. The first assertion is straightforward, while the second follows from the remark that f^{m}(P) = 0 implies f(P) = 0. ⊓ ⊔

Example 2.1

An ideal of this type is obtained when X := {P }, and P ∈ k^{n} is a rational point, i.e. a point with coordinates in k. If P := (a_{1}, a_{2}, …, a_{n}), then I(P) := I({P }) = (X_{1} − a_{1}, X_{2} − a_{2}, …, X_{n} − a_{n}). And clearly R/I(P) ≅ k.

The situation relevant to DoE is when a finite set of distinct points P_{1}, P_{2}, …, P_{s} ∈ k^{n} is given and X := {P_{1}, P_{2}, …, P_{s}}.

Lemma 2.3 Let P_{1}, P_{2}, …, P_{s} ∈ k^{n} and X := {P_{1}, P_{2}, …, P_{s}}. Then

I(X) = I(P_{1}) ∩ I(P_{2}) ∩ … ∩ I(P_{s})

Proof. It follows immediately from the definitions. ⊓ ⊔

Although this fact suggests a way of computing such ideals, there is a much better method based on the Buchberger-Möller Algorithm, which will be sketched in Section 3. In the rest of this section we take a closer look at rational points.

Definition 2.4 Let A be a ring, and I, J ideals in A. Then I and J are said to be comaximal if I + J = A.

Lemma 2.5 (Chinese Remainder Theorem) Let A be a ring, I_{1}, I_{2}, …, I_{s} ideals in A and consider the canonical homomorphism Φ : A/(∩_{j}I_{j}) → ⊕_{j}(A/I_{j}). Then

1) Φ is injective

2) If the ideals I_{j} are pairwise comaximal, Φ is an isomorphism.

Proof. Let J := ∩_{j}I_{j}. Then Φ is defined by Φ(a mod J) := (a mod I_{1}, …, a mod I_{s}), hence it is clearly injective.

Let us prove 2). First we observe that if we call J_{i} := ∩_{r≠i}I_{r}, then for every i the two ideals I_{i} and J_{i} are comaximal. This follows from the fact that if a maximal ideal contains J_{i}, then it must contain at least one of the I_{r}. Therefore, for every i := 1, …, s there exists α_{i} ∈ I_{i}, β_{i} ∈ J_{i}, such that α_{i} + β_{i} = 1. Now let m := (m_{1} mod I_{1}, …, m_{s} mod I_{s}) ∈ ⊕_{j}(A/I_{j}). Then it is easy to see that m = Φ(∑ m_{i}β_{i}). ⊓ ⊔

Theorem 2.6 Let P_{1}, P_{2}, …, P_{s} be distinct points in k^{n} and X := {P_{1}, P_{2}, …, P_{s}}. Then

R/I(X) ≅ k^{s}

Proof. We have already said that R/I(P) ≅ k for every rational point P. The conclusion follows from Lemma 2.3 and Lemma 2.5, since the I(P_{i}), being maximal ideals, are pairwise comaximal. ⊓ ⊔

We recall the following facts (see for instance Cox et al. (1992) from the theory of Gröbner bases.

Definition 2.7 Let f ∈ R. Then we denote by Supp(f), and we call it the support of f, the set of power-products with non-zero coefficient, when f is written as a linear combination of power-products.

Example 2.2

Let f(X, Y, Z) := X^{2} − 4XY + \frac{1}{2}Z − 3. Then Supp(f) = \{X^{2}, XY, Z, 1\}

Definition 2.8 Let {X_{1}, …, X_{n}}^{∗} be the set of power-products in the indeterminates X_{1}, …, X_{n}. Then a term-order σ on {X_{1}, …, X_{n}}^{∗} is a total order (denoted by <_{σ}) such that

a) T, T′, S ∈ {X_{1}, …, X_{n}}^{∗}, T <_{σ} T′ imply T · S <_{σ} T′ · S

b) 1 <_{σ} T for every T ∈ {X_{1}, …, X_{n}}^{∗}

Example 2.3

Examples of term-orders are Lex, DegLex, DegRevLex. A classification of term-orders is described in Robbiano (1985) and Robbiano (1986).

Definition 2.9 Let σ be a term-order and I an ideal of R. Then we denote by Lt_{σ}(I) the ideal generated by the set {Lt_{σ}(f) | f ∈ I, f ≠ 0}, where Lt_{σ}(f) is the σ-leading term of f. We denote by O_{σ}(I) the set of power-products, which are not multiples of any of the σ-leading terms of the elements of I.

Definition 2.10 Let O ⊆ {X_{1}, …, X_{n}}^{∗}. We say that O is a standard set of power-products if T ∈ O and T′ divides T implies T′ ∈ O, i.e. all divisors of an element of O are also in O.

Proposition-Definition 2.11 With the above assumptions we have 1) O_{σ}(I) is a basis of R/I as a k-vectorspace.

2) It is a standard set of power-products. We call it the standard set of power-products associated to σ and I.

Corollary 2.12 Let P_{1}, P_{2}, …, P_{s} be distinct points in k^{n} and denote by X := {P_{1}, P_{2}, …, P_{s}}. Let σ be a term-order and O_{σ}(I(X)) the standard set of power-products associated to σ and I(X). Then #(O_{σ}(I(X))) = s and O_{σ}(I(X)) is a basis of R/I(X) as a k-vectorspace.

Example 2.4

Let n := 3 and call the indeterminates X, Y, Z. Then let P_{1} := (\frac{1}{3}, 5, \frac{1}{2}), P_{2} := (1, 2, \frac{1}{5}), P_{3} := (2, 2, 3), P_{4} := (2, 2, 2) and X := {P_{1}, P_{2}, P_{3}, P_{4}}. If σ := DegRevLex then the reduced σ-Gröbner Basis of I(X) is \{X^{2} − 3X − \frac{10}{27}Y + \frac{74}{27}, XY − 2X − \frac{1}{3}Y + \frac{2}{3}, Y^{2} − 7Y + 10, XZ − \frac{1}{5}X + \frac{1}{6}Y − 2Z + \frac{1}{15} Y Z − \frac{1}{2}Y − 2Z + 1, Z^{2} + \frac{126}{25}X + \frac{31}{20}Y − 5Z − \frac{359}{50}\} from which we may easily deduce that O_{σ}(I(X)) = {1, X, Y, Z}. In contrast, if σ := Lex, the reduced σ-Gröbner Basis of I(X) is \{X + \frac{155}{189}Z^{3} − \frac{1537}{378}Z^{2} + \frac{1795}{378}Z − \frac{113}{63}, Y − \frac{8}{3}Z^{3} + \frac{208}{15}Z^{2} − \frac{56}{3}Z + \frac{6}{5}, Z^{4} − \frac{57}{10}Z^{3} + \frac{48}{5}Z^{2} − \frac{47}{10}Z + \frac{3}{5}\}

and O_{σ}(I(X)) = {1, Z, Z^{2}, Z^{3}}. In both cases #(O_{σ}(I(X))) = 4.

The elements β_{i} used in Lemma 2.5 behave as a canonical basis. When we deal with finite sets of points, this kind of element plays an important rôle, so we are led to the following

Definition 2.13 Let P_{1}, P_{2}, …, P_{s} be distinct points in k^{n} and denote by X := {P_{1}, P_{2}, …, P_{s}}. A polynomial s_{P_{i}} ∈ R is said to be a separator of P_{i} from X if s_{P_{i}}(P_{i}) = 1 and s_{P_{i}}(P_{j}) = 0 for every j ≠ i.

Corollary 2.14 Let P_{1}, P_{2}, …, P_{s} be distinct points in k^{n}, and b_{1}, …, b_{s} ∈ k. Then there exists a polynomial f ∈ R such that f(P_{i}) = b_{i} for i := 1, …, s. In particular there exist separators.

Proof. It is another way of reading Theorem 2.6. ⊓ ⊔

Definition 2.15 A polynomial f ∈ R such that f(P_{i}) = b_{i} for i := 1, …, s as above is called an interpolator or an interpolating polynomial of the values b_{1}, …, b_{s} at the points P_{1}, P_{2}, …, P_{s}.

Corollary 2.16 Let P_{1}, P_{2}, …, P_{s} be distinct points in k^{n} and denote by X := {P_{1}, P_{2}, …, P_{s}}. Then let T ⊆ X, Y := X \T , and for every P ∈ T let s_{P} be a separator of P from X. Finally let s_{T} := ∑_{P ∈T} s_{P}; then I(Y) = (I(X), s_{T}).

Proof. Clearly I(Y) ⊇ (I(X), s_{T}). It is also clear that 1 − s_{T} vanishes on T . Consequently, if f ∈ I(Y), then f · (1 − s_{T}) vanishes on X, hence f − f · s_{T} ∈ I(X), and the conclusion follows. ⊓ ⊔

Now we are ready to take the first important step in the direction of DoE.

Definition 2.17 Let E_{1}, E_{2}, …, E_{n} be finite subsets of k. Then the cartesian product E_{1} × E_{2} × ⋯ × E_{n} ⊂ k^{n} is a finite set of points called a full (or full factorial) design. If #(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 design with l_{1} = l_{2} = ⋯ = l_{n} = l. For instance it is common to speak of 2^{5}, 3^{4} full designs and so on.

Theorem 2.18 Let E_{1} := {a_{11}, … a_{1l_{1}}}, …, E_{n} := {a_{n1}, … a_{nl_{n}}} be finite subsets of k. Let f_{1} := ∏_{i=1}^{l_{1}}(X_{1} − a_{1i}), …, f_{n} := ∏_{i=1}^{l_{n}}(X_{n} − a_{ni}). If we denote by D the full design E_{1} × ⋯ × E_{n} then

1) I(D) = (f_{1}, …, f_{n}).

2) {f_{1}, …, f_{n}} is the reduced σ-Gröbner basis of I(D) for every term-order σ.

Proof. The proof of 1) is an easy exercise. To prove 2) we observe that the f_{i} are univariate polynomials, hence they are uniquely ordered independently of σ and their leading terms are pairwise coprime. ⊓ ⊔

Definition 2.19 The polynomials f_{1}, …, f_{n} defined in Theorem 2.18 are called canonical polynomials (or equations) of D.

Definition 2.20 With the same notation as in Theorem 2.18, we denote by O(D) the set of power-products {X_{1}^{a_{1}}X_{2}^{a_{2}} ⋯ X_{n}^{a_{n}} | 0 ≤ a_{j} < l_{j}, j = 1, …, n}. From the same theorem we deduce that it is the standard set of power-products associated to I(D) with respect to every term-order. Hence we call it the standard set of power-products of D.

Example 2.5

The most frequently used full design D with levels (l_{1}, l_{2}, …, l_{n}) ∈ ℕ^{n} is the set of points {0, 1, …, l_{1} − 1} × … × {0, 1, …, l_{n} − 1} ⊂ ℕ^{n}. For such a full design the canonical polynomials are f_{j} := X_{j} (X_{j} − 1) ⋯ (X_{j} − l_{j} + 1) for

j := 1, …, n.

Example 2.6

Let D be a 2^{3} full design. Then O(D) = {1, X, Y, Z, XY, XZ, Y Z, XY Z}, no matter which values of the coordinates of its points are given.

Lemma 2.21 Let X ⊂ k^{n} be a finite set of points. Then there exists a unique minimal full design D_{X} containing X.

Proof. For i := 1, …, n let E_{i} := {a_{i1}, … a_{il_{i}}} be the set of the i^{th} coordinates of the points in X. Then clearly D_{X} := E_{1} ×⋯×E_{n} is the solution. ⊓ ⊔

Theorem 2.22 Let s be a positive integer, P_{1}, P_{2}, …, P_{s} be distinct points in k^{n} and X := {P_{1}, P_{2}, …, P_{s}}. Then it is possible to generate I(X) with n + 1 polynomials.

Proof. Let D_{X} be the minimal design containing X. Then I(D_{X}) is generated by n polynomials by Theorem 2.18 and contained in I(X). Now it suffices to apply Corollary 2.16 to the pair (D_{X} , X). ⊓ ⊔

In the next section we discuss an efficient way of computing I(X).

3 Computing Confounding Polynomials: the Buchberger-Möller Algorithm

Before we sketch the Buchberger-Möller Algorithm (BM-Algorithm), we explain the idea informally. We recall (see Definition 2.9) that given a termorder σ and an ideal I, the symbol Lt_{σ}(I) denotes the ideal generated by the σ-leading terms of the non-zero elements of I. Let us consider a finite set of points X := {P_{1}, …, P_{s}} ⊂ k^{n}, let us fix a term-order σ and let {X_{1}, …, X_{n}}^{∗} be the monoid of all power-products in X_{1}, …, X_{n}. Then {X_{1}, …, X_{n}}^{∗} = O_{σ}(I(X)) ∪ Lt_{σ}(I(X)) and the union is disjoint. On the other hand the set O_{σ}(I(X)) is finite (it has cardinality s) by Theorem 2.6 and the generators of Lt_{σ}(I(X)) delineate the border of O_{σ}(I(X)), in the sense that if T is a generator of Lt_{σ}(I(X)) and T = X_{i}S, then S ∈ O_{σ}(I(X)). Therefore the region to be explored in order to find O_{σ}(I(X)) and the generators of Lt_{σ}(I(X)) is a finite region and the idea is to explore it moving one step at a time from the σ-smallest power-product, which is 1. The exploration will eventually find the reduced σ-Gröbner basis of I(X), the set O_{σ}(I(X)) and a set of separators from X for the points P_{1}, …, P_{s}.

Let us describe the BM-Algorithm in pseudocode.

BM-Algorithm

INPUT: X := {P_{1}, …, P_{s}} ⊂ k^{n}; σ a term-order. OUTPUT: GB:= the reduced σ-Gröbner basis of I(X); O := O_{σ}(I(X));

S := a list of separators of the P_{i} from X.

GB := ∅; O := ∅; S := ∅; r := 0; L := [1] WHILE L ≠ 0 DO

“Main Loop” END RETURN GB, O, S END

And now we describe the Main Loop.

T := Min_{σ}(L); L := L\{T } f := T − ∑_{i=1}^{s} T (P_{π(i)}) · s_{i} IF f vanishes on X THEN

GB := GB ∪ {f} - updating GB L := L\{Multiples of T }

ELSE O := O ∪ {T } - updating O r := r + 1 π(r) := Min{i | f(P_{i}) ≠ 0} s_{r} := f(P_{π(r)})^{−1} · f S := S ∪ {s_{r}} - updating S FOR i := 1, …, r − 1 DO

s_{i} := s_{i} − s_{i}(P_{π(r)}) · s_{r} - making S into a list of “partial” separators END L := L ∪ {X_{i}T | i := 1, …, n}\Lt_{σ}(GB) - updating L

Theorem 3.1 Given X := {P_{1}, …, P_{s}} ⊂ k^{n}, σ a term-order, the Buchberger-Möller algorithm terminates and computes the reduced σ-Gröbner basis of I(X), O := O_{σ}(I(X)) and a list of separators of the P_{i} from X. The complexity of the algorithm is quadratic in the number of indeterminates and cubic in the number of points.

Sketch of the Proof. The key remark is that the evaluation function separates the polynomials which are in I(X) from the polynomials which are not in I(X). And the algorithm keeps processing the power-products from the smallest in the list L, so that it actually separates polynomials whose leading term is a generator of Lt_{σ}(I(X)), from polynomials whose support is in O_{σ}(I(X)). If the power-product under investigation is not a generator of the leading term ideal, then it produces a separator of a point from X and in this case the list L can be enlarged. But only s power-products are of this type by Theorem 2.6, so that after a finite number of steps only elements in the reduced Gröbner basis can be obtained and the list eventually empties. By easy considerations on the linear algebra operations used it is not hard to check the correctness of the algorithm.

As for the complexity, see Mora and Robbiano (1993), Marinari et al. (1991) ⊓ ⊔

Corollary 3.2 Using the Buchberger-Möller Algorithm it is possible to compute interpolating polynomials.

Proof. Once we have separators s_{P_{1}}, …, s_{P_{s}} and we are given s values b_{1}, …, b_{s}, then an interpolating polynomial is ∑_{i=1}^{s} b_{i} · s_{P_{i}} . ⊓ ⊔

Example 3.1

We use the same points as in Example 2.4 and we check that s_{P_{1}} = \frac{1}{3}Y − \frac{2}{3} is a separator of P_{1} from \{P_{2}, P_{3}, P_{4}\}, s_{P_{2}} = −X − \frac{5}{9}Y + \frac{28}{9} is a separator of P_{2} from \{P_{1}, P_{3}, P_{4}\}, s_{P_{3}} = −\frac{9}{5}X − \frac{1}{2}Y +Z + \frac{13}{5} is a separator of P_{3} from \{P_{1}, P_{2}, P_{4}\}, s_{P_{4}} = \frac{14}{5}X + \frac{13}{18}Y − Z − \frac{182}{45} is a separator of P_{4} from {P_{1}, P_{2}, P_{3}}. If we want to interpolate the values {2, 3, 0, −7} at the points P_{1}, P_{2}, P_{3}, P_{4}, we find a solution by taking 2s_{P_{1}} + 3s_{P_{2}} − 7s_{P_{4}} = 2(\frac{1}{3}Y − \frac{2}{3}) + 3(−X − \frac{5}{9}Y + \frac{28}{9}) − 7(\frac{14}{5}X + \frac{13}{18}Y − Z − \frac{182}{45}) = −\frac{113}{5}X − \frac{109}{18}Y + 7Z + \frac{1634}{45}

Many improvements can be made in an actual implementation of the BMalgorithm and many generalizations can be performed, in particular to the case of finite sets of possibly non-reduced (fat) points. On this subject it is worth mentioning the paper by Bigatti and Kreuzer (1998), which is now in preparation.

In the next section we start to explore the connection between designs and models.

4 Identifying the Models

In Section 2 we have seen that every function on a finite set of points can be represented by a polynomial function (see Corollary 2.14) and we have seen how to compute such a polynomial (see Corollary 3.2). These facts are relevant to DoE, since its main goal is to construct good models from a subset of a full design.

Now it is time to give the following fundamental definitions:

Definition 4.1 Given a full design D, a fractional factorial design is a proper subset F of D. It is also called a fraction of D. Its defining ideal I(F) contains the ideal I(D).

Definition 4.2 Any set of polynomials that, added to the canonical polynomials of a full design D, generates the ideal of a fraction F, is called a set of confounding polynomials of F in D.

Definition 4.3 Let D be a full design and F a fraction of it. Then we call characteristic polynomial of F ⊂ D a polynomial f such that f(P) = 0 for every P ∈ F and f(P) = 1 for every P ∈ D\F.

We have seen in Theorem 2.18 that I(D) is generated by the canonical polynomials {f_{1}, …, f_{n}}, which is a universal Gröbner basis, and as a consequence of Corollary 2.16 and Theorem 2.22 we have the following:

Proposition 4.4 Let D be a full design, F a fraction of it, and {f_{1}, …, f_{n}} the canonical polynomials of I(D). Let f be a characteristic polynomial of F. Then I(F) = (f_{1}, …, f_{n}, f).

Theorem-Definition 4.5 Let D be a full design, f_{1}, …, f_{n} the canonical polynomials (as described in Theorem 2.18), and F a fraction of it. Then there exists a unique characteristic polynomial f of F in D such that deg_{X_{i}}(f) < deg(f_{i}) for every i := 1, …, n. It will be called the canonical confounding polynomial of F in D.

Proof. Let f, g be two characteristic polynomials of F in D. Then, by definition, f − g vanishes on D, hence it belongs to the ideal I(D) = (f_{1}, …, f_{n}). The set {f_{1}, …, f_{n}} is a universal Gröbner basis, hence the theory tells us that f and g have the same normal form with respect to it and such a normal form is the remainder of the division of f (or of g) with respect to {f_{1}, …, f_{n}}. The conclusion follows immediately. ⊓ ⊔

Remark 4.6 In DoE it is more common to use the indicator polynomial of F ⊂ D, which is a polynomial such that f(P) = 1 for every P ∈ F and f(P) = 0 for every P ∈ D\F. Of course the indicator polynomial and the characteristic polynomial sum to 1 on D, so that it is clear how to switch from one to the other.

Example 4.1

Let D be a 2^{3} full design as described in Example 2.5. Its canonical polynomials are

f_{1} := X(X − 1), f_{2} := Y (Y − 1), f_{3} := Z(Z − 1)

Let F := {(0, 0, 0), (1, 0, 0), (1, 1, 0), (1, 0, 1), (0, 1, 1)} be a fraction of D. Let P := (0, 1, 0), Q := (0, 0, 1), R := (1, 1, 1). Then D = F ∪ {P, Q, R}. Using the BM-algorithm we find the separators s_{P} = Y − Y Z − XY + XY Z, s_{Q} = Z − Y Z − XZ + XY Z, s_{R} = XY Z respectively of the points P, Q, R from D. Therefore the polynomial s_{P} + s_{Q} + s_{R} = Y + Z − XY − XZ − 2Y Z + 3XY Z is the canonical confounding polynomial of F in D.

It is important to observe that all the information of F ⊂ D is completely contained in its canonical confounding polynomial. In DoE this point of view has not been fully explored yet. On the other hand, the beauty of encoding the information into the single canonical confounding polynomial is somehow overshadowed by the fact that directly from it one cannot easily extract further useful information. There is a recent exception to the previous sentence, namely this approach has been used in Fontana et al. (1997), but only in a special case. We, however, shall change direction.

Definition 4.7 Let F be a fraction of a full design D. Let σ be a termorder and G_{σ} the corresponding reduced Gröbner basis of I(F). The set of those polynomials in G_{σ}, which are not among the canonical polynomials of D is called the σ-canonical set of confounding polynomials of F in D.

Moreover we use the notation O_{σ}(F) instead of O_{σ}(I(F)).

Proposition 4.8 Let F be a fraction of a full design D. Let σ be a degreecompatible term-order. Then the BM-algorithm computes O_{σ}(F) with elements of minimal degree.

Proof. In fact the order which the power-products enter the computation is −σ (i.e. σ-smallest first). ⊓ ⊔

Example 4.2

Let D be a 2^{3} full design and let F be the following fraction of it:

{(1, 0, 0), (1, 1, 0), (1, 0, 1), (0, 1, 1)}.

If σ := DegRevLex, then the σ-canonical set of confounding polynomials of F in D is {XY − X − Y + 1, XZ − X − Z + 1, Y Z + X − 1}. And O_{σ}(F) = {1, X, Y, Z}. Alternatively, if σ := Lex, then the σ-canonical set of confounding polynomials of F in D is {X + Y Z − 1}. And O_{σ}(F) = {1, Y, Z, Y Z}.

Example 4.3

Let D be a 2^{3} full design and let F be the following fraction of it (as in Example 4.1): {(0, 0, 0), (1, 0, 0), (1, 1, 0), (1, 0, 1), (0, 1, 1)}. If either σ := DegRevLex or σ := Lex, then the σ-canonical set of confounding polynomials of F in D is {XY + Y Z − Y, XZ + Y Z − Z}. In both cases O_{σ}(F) = {1, X, Y, Z, Y Z}.

Now we are ready to enter the “true” game. We have seen that over the fractions of a full design all the functions are polynomial. But what kind of polynomials are to be considered? Let us see what happens with the data of Example 4.2. For instance we know that the polynomial X + Y Z − 1 vanishes on F := {(1, 0, 0), (1, 1, 0), (1, 0, 1), (0, 1, 1)}. This implies that the two polynomial functions X and 1 − Y Z take the same values on F, i.e. they are confounded by F. On the other hand the 4 points are not planar, hence no linear combination of 1, X, Y, Z except the trivial one vanishes on F. In other words, the polynomial functions 1, X, Y, Z on F are linearly independent. Now suppose that we are looking for a linear combination of these four polynomial functions, which interpolates some given values at the four points, for instance 2, 5, −3, −6. We have learned that the interpolation problem can be solved via separators (see Corollary 3.2), but there is another way to proceed. Namely we take a generic linear combination a+bX +cY +dZ of these four functions, where a, b, c, d are independent parameters. Then we evaluate it at the four points, and impose the given values. We get a+b = 2, a+b+c = 5, a+b+d = −3, a+c+d = −6, which is a non-singular linear system. The unique solution is a = −4, b = 6, c = 3, d = −5. In this case, by evaluating the polynomial a + bX + cY + dZ at the four points of F, we could identify it, i.e. we could identify its coefficients.

Example 4.4

Let us go back to Example 4.1 . O(D) = {1, X, Y, Z, XY, XZ, Y Z, XY Z}, therefore to compute the canonical confounding polynomial of F in D we can also proceed as follows. We consider the generic linear combination a_{1} + a_{2}X + a_{3}Y + a_{4}Z + a_{5}XY + a_{6}XZ + a_{7}Y Z + a_{8}XY Z and we impose that its evaluation at the points of F is 0, and at the points of D\F is 1. We get the following linear system a_{1} = 0, a_{1} + a_{2} = 0, a_{1} + a_{2} + a_{3} + a_{5} = 0, a_{1} + a_{2} + a_{4} + a_{6} = 0, a_{1} + a_{3} + a_{4} + a_{7} = 0, a_{1} + a_{3} − 1 = 0, a_{1} + a_{4} − 1 = 0, a_{1} + a_{2} + a_{3} + a_{4} + a_{5} + a_{6} + a_{7} + a_{8} − 1 = 0, from which we deduce a_{1} = 0, a_{2} = 0, a_{3} = 1, a_{4} = 1, a_{5} = −1, a_{6} = −1, a_{7} = −2, a_{8} = 3, hence we find f := Y +Z −XY −XZ −2Y Z +3XY Z, in agreement with Example 4.1.

Once again in this example, by evaluating a_{1} +a_{2}X +a_{3}Y +a_{4}Z +a_{5}XY + a_{6}XZ + a_{7}Y Z + a_{8}XY Z at the eight points of D, we could identify it, i.e. we could identify its coefficients. The considerations made before and these examples lead to the following:

Definition 4.9 A polynomial model is a polynomial function, i.e. y = f(X_{1}, …, X_{n}), where f(X_{1}, …, X_{n}) ∈ k[X_{1}, …, X_{n}]. If k ⊂ K is a field extension and f(X_{1}, …, X_{n}) ∈ K[X_{1}, …, X_{n}] is such that its coefficients are algebraically independent over k, then y = f(X_{1}, …, X_{n}) is called a linear family of polynomial models or simply a linear polynomial model. The information of a linear polynomial model is encoded in the support of the polynomial, so we can call linear polynomial model the vector space generated by a set of power-products and call support of the model such a set.

Example 4.5

Let k := ℚ, K := ℚ(a, b, c), where a, b, c are transcendental over ℚ. Then y = aX^{2} − bXY Z + c is a linear polynomial model. Its support is {X^{2}, XY Z, 1}

Definition 4.10 Let y = f(X_{1}, …, X_{n}) be a linear polynomial model and consider a set X := {P_{1}, P_{2}, …, P_{s}} of distinct points of k^{n}. We say that y is identifiable by X if, by evaluating it at the given points, we can uniquely determine its coefficients.

In practice it is common to use polynomial models, whose support is a standard set of power-products. The reason is quite clear: if for a given problem it is relevant to evaluate a power-product, it seems to be even more relevant to evaluate its divisors.

Definition 4.11 A complete (linear) polynomial model is a (linear) polynomial model, whose support is a standard set of power-products.

Now we can rephrase some results with the new terminology, in particular we can interpret Theorem 2.6 and Corollary 2.12.

Theorem 4.12 Let P_{1}, P_{2}, …, P_{s} be distinct points in k^{n} and denote by X := {P_{1}, P_{2}, …, P_{s}}. Then let y = f(X_{1}, …, X_{n}) be a linear polynomial model, with support S := {T_{1}, …, T_{r}} and let 𝕏(S, X) be the (s × r)-matrix whose element in position (i, j) is T_{j}(P_{i}), the evaluation of T_{j} at P_{i}. Then the following conditions are equivalent

1) y is identifiable by X

2) rk(𝕏(S, X)) = r

3) S is a set of linearly independent functions on X.

Proof. We know from Theorem 2.6 that the dimension of the vector-space of polynomial functions over X is s, therefore the equivalence is simply a statement in elementary linear algebra. ⊓ ⊔ Remark 4.13 In DoE matrices such as 𝕏(S, X) above are called matrices of the model.

Theorem 4.14 Let P_{1}, P_{2}, …, P_{s} be distinct points in k^{n} and denote by X := {P_{1}, P_{2}, …, P_{s}}. Let σ be a term-order and O_{σ}(I(X)) the standard set of power-products associated to σ and I(X). Then every polynomial model, whose support is contained in O_{σ}(I(X)), is identifiable by X.

Proof. It follows immediately from Theorem 4.12 and Corollary 2.12. ⊓ ⊔

In the following section some important problems in DoE are discussed.

5 Some Problems

At this point many natural and fundamental questions arise. Let D be a full design with levels (l_{1}, l_{2}, …, l_{n}). We know that its cardinality is #(D) = l_{1}×l_{2}×⋯×l_{n}, which is also #(O(D)) (see Definition 2.20 and Corollary 2.12).

problem 1: Let F := {P_{1}, P_{2}, …, P_{s}} ⊂ D. What are the complete linear polynomial models which can be identified by F?

problem 2: Let y = f(X_{1}, …, X_{n}) be a complete linear polynomial model, whose support is contained in O(D)). What are the minimal fractions, which identify y?

problem 3: Let s < #(D). What are the fractions of D of cardinality s, which identify the highest (lowest) number of complete linear polynomial models?

5.1 Problem 1

It is important to understand the relation between Problem 1 and the algebraic methods, from several points of view. As we mentioned in the introduction, this connection was the first one discovered between DoE and Gröbner bases (see Pistone and Wynn (1996)). A first step is to observe that Problem 1 can be rephrased in the following way:

Problem 1′: Let F := {P_{1}, P_{2}, …, P_{s}} ⊂ D. What are the possible standard sets of power-products, which are bases of R/I(F) as a k-vectorspace?

Actually the exact rephrasing of Problem 1 would be the following: let F := {P_{1}, P_{2}, …, P_{s}} ⊂ D; what are the standard sets of power-products, which are k-linearly independent as sets of elements of R/I(F)? But, of course, if we are able to find the maximal ones, we get the non-maximal ones for free.

A first step can easily be made by linear algebra methods. Namely, suppose we have F := {P_{1}, P_{2}, …, P_{s}} ⊂ D and a standard set of power-products O ⊂ O(D) (or even any set of power-products). If we want to check whether or not it is a basis of R/I(F) as a k-vectorspace, it suffices to construct the matrix 𝕏(O, F) (see Theorem 4.12). The answer is:

Corollary 5.1 The following conditions are equivalent 1) O is a basis of R/I(F)

2) 𝕏(O, F) is invertible

Proof. It follows immediately from Theorem 4.12. ⊓ ⊔

However, Problem 1′ looks for a complete answer, in the sense that we want to find all the standard sets of power-products, which are bases of R/I(F) as a k-vectorspace. A good approach seems to be the theory of Gröbner bases; indeed one can use Corollary 2.12 and produce many solutions to the problem. But now the question is: how many? It is well-known that, given an ideal I, for every term-order σ there is a unique standard set of power-products O_{σ}(I). The term-orders are infinite in number, but the standard sets of power-products associated to I are finite (see Robbiano (1985), Robbiano (1986), Mora and Robbiano (1993)) and each one is a basis of R/I as a k-vectorspace. Are they all? Let us have a look at the following important example:

Example 5.1

Let D be a 3^{2} full design. Since X^{3}, Y^{3} are the leading terms of the canonical polynomials, no matter which values of the coordinates are chosen, it turns out that

O(D) = {1, X, Y, X^{2}, XY, Y^{2}, X^{2}Y, XY^{2}, X^{2}Y^{2}}

Let us consider the fraction F := {(0, 0), (0, −1), (1, 0), (1, 1), (−1, 1)} of D and let O := {1, X, Y, X^{2}, Y^{2}}, which is a standard set of power-products. We construct

𝕏(O, F) = ( \begin{matrix}1 & 0 & 0 & 0 & 0 \\ 1 & 0 & −1 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 1 & 1 \\ 1 & −1 & 1 & 1 & 1 \end{matrix} )

whose determinant is −4, hence we use Corollary 5.1 and conclude that O is a basis of R/I(F). The polynomial f := X^{2} + XY − X − \frac{1}{2}Y^{2} − \frac{1}{2}Y is in the defining ideal of F (this fact can be easily seen by checking that f vanishes at the 5 points of F). Let σ be a term-order. From the definition of term-order it follows that X^{2} >_{σ} X and Y^{2} >_{σ} Y. Now 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}. The conclusion is that O := {1, X, Y, X^{2}, Y^{2}} cannot be O_{σ}(F), whatever σ we choose.

The above example shows that the theory of Gröbner bases provides a good approach to the problem, but it does not always yield the full solution. More work has to be done.

5.2 Problem 2

Now we are going to discuss the more important and more complicated Problem 2, which can be reformulated as:

Problem 2′: Let O ⊂ O(D) be a standard set of power-products. What are the fractions F of D, such that O is a basis of R/I(F) as a k-vectorspace?

Definition 5.2 Let O ⊂ O(D) be a standard set of power-products.

If σ is a term-order, then we denote by Sol(O, σ) the set of those fractions F, such that O_{σ}(F) = O, hence O_{σ}(F) is a basis of R/I(F) as a k-vectorspace.

We denote by Sol(O, ∃σ) the set of those fractions F, such that there exists a term-order σ with O_{σ}(F) = O, hence O_{σ}(F) is a basis of R/I(F) as a kvectorspace.

We denote by Sol(O) the set of those fractions F, such that O is a basis of R/I(F) as a k-vectorspace, hence Sol(O) is the set of all the solutions to Problem 2′.

Example 5.1 shows explicitly that Sol(O, ∃σ) ⊂ Sol(O) may happen. This fact induces several other questions. For instance, we would like to be able to find easy classes of solutions. It would also be nice to have good classes of examples where Gröbner bases suffice to solve the problem completely. This investigation was carried out in Robbiano and Rogantin (1998) and in Caboara and Robbiano (1997). Here we report on some ideas explained there.

Definition 5.3 Given n indeterminates X_{1}, …, X_{n}, let D be a full design and O ⊂ O(D) a standard set of power-products. Then there exists a unique minimal set, Min(O), of power-products which generates {X_{1}, …, X_{n}}^{∗}\O, which means that every element in {X_{1}, …, X_{n}}^{∗}\O is a multiple of an element of Min(O). The set of power-products in Min(O), which are not among the leading terms of the canonical polynomials of D, is called CutOut(O).

The meaning is that O is the set of power-products not divisible by any element of the set CutOut(O)∪{Lt(f_{1}), …, Lt(f_{n})}. Let us illustrate it with an example.

Example 5.2

Let D be a 3^{2} full design. We know that the leading terms of the two generators of I(D) are X^{3}, Y^{3}. Moreover, we know (see Example 5.1) that O(D) = {1, X, Y, X^{2}, XY, Y^{2}, X^{2}Y, XY^{2}, X^{2}Y^{2}}. If O_{1} := {1, X, Y, X^{2}, XY, Y^{2}} then CutOut(O_{1}) = {X^{2}Y, XY^{2}}. If O_{2} := {1, X, Y, X^{2}, XY, X^{2}Y } then CutOut(O_{2}) = {Y^{2}}.

Let D be a full design and O ⊆ O(D) a standard set of power-products. Let us denote by f_{1}, …, f_{n} the canonical polynomials of D and let CutOut(O) := {T_{1}, …, T_{h}}. Suppose we are able to find h more polynomials {g_{1}, …, g_{h}} and a term-order σ such that:

1) Lt_{σ}(g_{i}) = T_{i}, for i := 1, …, h;

2) {f_{1}, …, f_{n}, g_{1}, …, g_{h}} is a σ-Gröbner basis. Then we denote by I the ideal generated by {f_{1}, …, f_{n}, g_{1}, …, g_{h}} and we see that I(D) ⊂ I, hence I = I(F), where F is a fraction of D. Moreover O_{σ}(I) = O_{σ}(F) = O, hence O is a basis of R/I(F) by Corollary 2.12, and the fraction F, whose cardinality is #(O) by Theorem 2.6, is a solution to Problem 2’.

Example 5.3

We continue with the same data as in Example 5.2. Suppose that the values of the coordinates are {0, 1, 2} for both X and Y. Then f_{1} = X(X − 1)(X − 2), f_{2} = Y (Y − 1)(Y − 2). If we take g_{1} := X(X − 1)Y, g_{2} := XY (Y − 1), then one checks that {f_{1}, f_{2}, g_{1}, g_{2}} is a σ-Gröbner basis for every σ. Therefore I := (f_{1}, f_{2}, g_{1}, g_{2}) defines a fraction F, which is easily seen to be {(0, 0), (0, 1), (0, 2), (1, 0), (2, 0), (1, 1)}, and O_{1} = {1, X, Y, X^{2}, XY, Y^{2}} is a basis of R/I(F). By the equivalence of Problem 2 and Problem 2’, we conclude that any polynomial model whose support is contained in O_{1} can be identified by F.

The example can be explained by the following facts.

Definition 5.4 Let k be an infinite field, T := X_{1}^{a_{1}}X_{2}^{a_{2}} ⋯ X_{n}^{a_{n}} and let α_{1}, …, α_{n} be n sequences of elements of the base field k, where α_{r} = (α_{r,i})_{i∈ℕ} for r := 1, …, n and α_{r,i} ≠ α_{r,j} if i ≠ j. Then we call the polynomial

D(T) := ∏_{i=1}^{a_{1}}(X_{1} − α_{1,i}) ⋯ ∏_{i=1}^{a_{n}}(X_{n} − α_{n,i})

the distraction of T with respect to α_{1}, …, α_{n}.

Proposition 5.5 Let T_{1}, …, T_{h} be power-products such that T_{i} does not divide T_{j} for every i ≠ j, let α_{1}, …, α_{n} be n sequences of elements of k and let I := (D(T_{1}), …, D(T_{h})) be the ideal generated by the corresponding distractions with respect to α_{1}, …, α_{n}. Then {D(T_{1}), …, D(T_{h})} is the reduced Gröbner basis of I with respect to every term-order.

Proof. See Carrà and Robbiano (1990), Theorem 1.4 and Corollary 2.6. ⊓ ⊔

It is clear that, in order to get a distraction of T, it suffices to have vectors of sufficiently many elements of k. So we can speak of distractions associated to vectors, not to sequences, and sometimes we can drop the assumption that k is infinite.

Theorem 5.6 Let D be a full design with levels (l_{1}, l_{2}, …, l_{n}) and whose values of the coordinates are 0, 1, …, l_{i} − 1, for i := 1, …, n. Let I(D) := (f_{1}, …, f_{n}) be its defining ideal, where f_{j} := X_{j} (X_{j} − 1) ⋯ (X_{j} − l_{j} + 1) are the canonical polynomials, for i = 1, …, n; let O(D) be its corresponding standard set of power-products and O a standard set of powerproducts contained in O(D). Assume that {T_{1}, …, T_{h}} = CutOut(O). Let α_{1}, α_{2}, …, α_{n} be permutations of (0, 1, …, l_{1} − 1), …, (0, 1, …, l_{n} − 1) respectively and D(T_{1}), … D(T_{h}) the distractions of T_{1}, …, T_{h} with respect to α_{1}, α_{2}, …, α_{n}.

Then, for every term-order σ, we have: {f_{1}, …, f_{n}, D(T_{1}), … D(T_{h})} is a σ-Gröbner basis and {D(T_{1}), …, D(T_{h})} is the σ-canonical set of confounding polynomials of a fraction F, such that O_{σ}(F) = O.

Proof. See Robbiano and Rogantin (1998), Theorem 3.4. ⊓ ⊔

Remark 5.7 It is easy to see that the choice of coordinates can be generalized to any set. It suffices then to change the permutations α_{1}, α_{2}, …, α_{n} accordingly.

Definition 5.8 Given a full design D, a term-order σ, and a standard set of power-products O ⊂ O(D), let F be a fraction of D, whose σ-canonical set of confounding polynomials is given by distractions as indicated in Theorem 5.6. Then F is called a distracted fraction.

Definition 5.9 Given a full design D and a standard set of power-products O ⊂ O(D), we denote by Distr(O) the set of the distracted fractions, whose associated standard set of power-products is O for some term-order σ. Then we denote by Sol(O, ∀σ) the set of those fractions F such that O_{σ}(F) = O for every term-order σ.

Corollary 5.10 Given the hypotheses of Theorem 5.6, Distr(O) ⊆ Sol(O, ∀σ)

Proof. It follows from Proposition 5.5. ⊓ ⊔

Remark 5.11 In Robbiano and Rogantin (1998) some more theory is developed. For instance an explicit formula for #(Distr(O)) is proved and a better insight is given to the difference between Distr(O) and Sol(O, ∀σ). The following example is drawn from that paper.

Example 5.4

Let D be a 2^{3} full design, O := {1, x, y, z}.

Let F := {(0, 0, 0), (0, 0, 1), (1, 0, 0), (1, 1, 0)}. Then I(F) = (x^{2} − x, y^{2} − y, z^{2}−z, xy−x, xz, yz) and {xy−x, xz, yz} is the DegRevLex-canonical set of confounding polynomials of F. Therefore O = O_{DegRevLex}(F) and we deduce from Robbiano and Rogantin (1998), Theorem 3.13 that {xy−x, xz, yz} is the τ-canonical set of confounding polynomials of F for every term-order τ, and thus that F ∈ Sol(O, ∀σ). On the other hand, F ∉ Distr(O). Suppose the contrary; then it follows from See Carrà and Robbiano (1990) that every pair of polynomials in {x^{2} − x, y^{2} − y, z^{2} − z, xy − x, xz, yz} should be a Gröbner basis. But clearly {xy − x, xz} is not. With respect to the 2^{3} full design and the standard set of power-products O := {1, x, y, z}, we conclude that Distr(O) ⊂ Sol(O, ∀σ). A suitable computation done with statfamilies shows that #(Distr(O)) = 8 and #(Sol(O, ∀σ)) = 32.

We have already seen that Gröbner basis theory in general cannot solve Problem 2′ completely. But there are nice situations where it does.

We recall the following:

Theorem 5.12 Given a full design D, a term-order σ and a standard set of power-products O ⊂ O(D), there is an algorithm which computes Sol(O, σ).

Proof. See Caboara and Robbiano (1997), Theorem 3.3 and subsequent remarks. ⊓ ⊔

Definition 5.13 Let O ⊂ {X_{1}, …, X_{n}}^{∗} denote a standard set of powerproducts, σ a term-order and T a power-product. We put σ(O, T) := {T′ ∈ O | T′ <_{σ} T }.

Theorem 5.14 Given a full design D and a standard set of power-products O ⊂ O(D), we let CutOut(O) := {T_{1}, …, T_{h}} and assume that there exists a term-order σ such that σ(O, T_{i}) = O for every i := 1, …, h. Then

1) Sol(O) = Sol(O, σ).

2) There is an algorithm which computes them, hence it computes all the solutions to Problem 2′.

22 Robbiano

Proof. See Caboara and Robbiano (1997), Corollary 2.14. ⊓ ⊔

Actually the proof follows from the construction of a family of ideals, which are the defining ideals of the fractions which solve the problem. The process is deeply connected with the theory of Gröbner bases as well as the theory of algebraic schemes. The details are described in Caboara and Robbiano (1997). Here we show the full computation and the solution of an instance of Problem 2′.

Example 5.5

Let D be the 3^{2} full design given by the polynomials f_{1} := X(X − 1)(X − 2), f_{2} := Y (Y − 1)(Y − 2); then O(D) = {1, X, Y, X^{2}, XY, Y^{2}, X^{2}Y, XY^{2}, X^{2}Y^{2}}. If O := {1, X, Y, Y^{2}}, then we get CutOut(O) = {X^{2}, XY }. If σ is any degree-compatible term-order with X >_{σ} Y, then we match the assumptions of Theorem 5.14, since σ(O, X^{2}) = σ(O, XY) = O. To solve Problem 2′ completely in this specific example, it suffices to find all the σ-canonical sets of confounding polynomials, whose leading terms are X^{2}, XY. All the corresponding fractions F are such that Lt_{σ}(I(F)) is minimally generated by {X^{2}, XY, Y^{3}}.

Let g_{1} := X^{2} + a_{1}Y^{2} + a_{2}X + a_{3}Y + a_{4}, g_{2} := XY + a_{5}Y^{2} + a_{6}X + a_{7}Y + a_{8} The theory says that we have to impose that {f_{1}, f_{2}, g_{1}, g_{2}} is a σ-Gröbner basis. This yields the following algebraic system:

a_{7}^{2}a_{8} − a_{6}a_{7} + a_{5} = 0, a_{7}^{3} + 3a_{7}^{2} + 2a_{7} = 0, a_{5}a_{7}^{2} + 3a_{5}a_{7} + 2a_{5} = 0, a_{7}^{2}a_{8} − a_{6}a_{7} + a_{5} = 0, a_{4}a_{5}a_{7} − a_{1}a_{3} − a_{2}a_{5} − 3a_{1} = 0, a_{5}a_{7}a_{8} + a_{3}a_{5} − a_{5}a_{6} − a_{1}a_{7} = 0, a_{4}a_{7}a_{8} − a_{3}a_{4} − a_{4}a_{6} − a_{2}a_{8} − 3a_{4}a_{8} − 3a_{4} = 0, a_{4}a_{7}^{2} − a_{3}^{2} − a_{2}a_{7} + a_{1} − 3a_{3} − 2 = 0, a_{4}a_{6}a_{7} − a_{2}a_{3} − a_{4}a_{5} − a_{2}a_{6} + 2a_{4}a_{8} − 3a_{2} = 0, a_{6}a_{7}^{2} − a_{5}a_{7} + 3a_{6}a_{7} + 2a_{7}a_{8} − 3a_{5} = 0, a_{7}a_{8}^{2} − a_{4}a_{7} + a_{3}a_{8} − 2a_{6}a_{8} − 3a_{8}^{2} − a_{2} − 3a_{4} = 0, a_{6}a_{7}a_{8} + a_{3}a_{6} − a_{6}^{2} − a_{2}a_{7} − a_{5}a_{8} + 2a_{8}^{2} − a_{1} + 2a_{4} = 0

Solving the system yields 81 solutions, which correspond to 81 among all the \binom{9}{4} = 126 fractions of cardinality 4. These 81 fractions are all the fractions F of D such that {1, X, Y, Y^{2}} is a basis of R/I(F). In this case Problem 2′ is solved completely.

5.3 Problem 3

We conclude the survey by saying a few words about Problem 3. As before, it is easy to see that the problem can be rephrased as Problem 3′: Let s < #(D). What are the fractions F of D of cardinality s, with the highest (lowest) number of standard sets of power-products, which are a basis of R/I(F) as a k-vectorspace?

Again Example 5.1 shows that the theory of Gröbner bases cannot give the full solution. An interesting approach is taken in Caboara et al. (1997), where the theory of Gröbner Fans (see Mora and Robbiano (1989)) is used. Here we show that it is possible to characterize those fractions with a unique standard set of power-products as a basis of R/I(F). First, we recall from Robbiano and Rogantin (1998) the following

Theorem 5.15 Given a design D and a standard set of power-products O ⊂ O(D), let F be a fraction. Let σ be a term-order and G_{σ} := {g_{1}, …, g_{h}} the σ-canonical set of confounding polynomials of F. If we write g_{i} := T_{i}−r_{i}, with T_{i} := Lt_{σ}(g_{i}) for i := 1, …, h, then the following conditions are equivalent

1) T divides T_{i} for every T in the support of r_{i} and every i := 1, …, h 2) G_{σ} is the τ-canonical set of confounding polynomials of F for every

term-order τ 3) F ∈ Sol(O, ∀σ).

Proof. See Robbiano and Rogantin (1998), Theorem 3.13. ⊓ ⊔

So we may conclude by proving the following

Theorem 5.16 Given a design D and a standard set of power-products O ⊂ O(D), let F be a fraction. Then the following conditions are equivalent

1) O is the unique standard set of power-products which is a basis of R/I(F) as a k-vectorspace

2) F ∈ Sol(O, ∀σ).

Proof. The fact that 1) implies 2) is obvious. Let us prove that 2) implies 1). If F ∈ Sol(O, ∀σ), then we deduce from Theorem 5.15 that there exists a set of polynomials G := {g_{1}, …, g_{h}} which is the σ-canonical set of confounding polynomials, for every σ. Moreover the shape of these polynomials is g_{i} := T_{i} − r_{i}, with T_{i} = Lt(g_{i}) for every σ and T divides T_{i} for every T ∈ Supp(r_{i}). Let Supp(r_{i}) := {T_{i1}, …, T_{im_{i}}}; then T_{i}, T_{i1}, …, T_{im_{i}} are linearly dependent modulo I(F). Now let O′ be another standard set of power-products which is a basis of R/I(F) as a k-vectorspace. The key remark is that T_{i} cannot be in O′, otherwise also all the T_{ij} would be in O′, simply because T_{ij} divides T_{i}. This fact implies that O′ ⊆ O, hence they are equal simply because they have the same cardinality. ⊓ ⊔

Remark 5.17 This theorem shows that not only the Distracted Fractions but also those fractions as in Example 5.4 identify a unique maximal complete linear polynomial model. In other words their fan has only one leaf, if we use the terminology of Caboara et al.

6 Concluding Remarks

We conclude the survey by summarizing some of the most important facts treated above. Putting together Corollary 5.10, Example 5.1, the subsequent discussion, Theorem 5.12, Theorem 5.14 and Theorem 5.16, we conclude by saying that

Distr(O) ⊆ Sol(O, ∀σ) ⊆ Sol(O, ∃σ) ⊆ Sol(O)

All the inclusions can be strict and the set Sol(O, ∀σ) is precisely the set of those fractions which identify a unique maximal complete linear polynomial model. Moreover, given a term-order σ, there is an algorithm which computes all the elements in Sol(O, σ), and we have established in Theorem 5.14 a set of sufficient conditions for Sol(O, σ) to be equal to Sol(O).

The problem of computing Sol(O) in general, is still unsolved.

References

Adams, W. W., Loustaunau, P. (1994): An Introduction to Gröbner Bases. Graduate Studies in Mathematics: Amer. Math. Soc., Providence, R.I.

Bigatti, A.M., Kreuzer, M. (1998): On the Computation of Ideals of Points. In Preparation.

Box, G. E. P., Hunter, W. G., Hunter, J. S. (1978): Statistics for Experimenters. John Wiley & Sons, New York.

Buchberger, B. (1965): On Finding a Vector Space Basis of the Residue Class Ring Modulo a Zero Dimensional Polynomial Ideal (German). PhD Thesis, Univ. of Innsbruck, Austria.

Buchberger, B. (1970): An Algorithmical Criterion for the Solvability of Algebraic Systems of Equations (German). Aequationes mathematicae 4/3, 374–383.

Buchberger, B. (1985): An Algorithmic Method in Polynomial Ideal Theory. Chapter 6 in Progress, directions, and open problems in multidimensional systems theory. N. K. Bose, Ed., D. Reidel Publishing Company, 184–232.

Buchberger, B., Möller, M. (1982): The Construction of Multivariate Polynomials with Preassigned Zeroes. Proceedings EUROCAM 82, LNCS 144, 24–31.

Caboara, M., Pistone, G., Riccomagno, E. Wynn, H.P. (1997): The Fan of an Experimental Design. Preprint.

Caboara, M., Robbiano, L. (1997): Families of Ideals in Statistics. Proceedings of the 1997 ISSAC (Maui, Hawaii, July 97) Küchlin Ed., New York, 404– Capani, A., Niesi, G., Robbiano, L. (1995): CoCoA, a system for doing Com-

putations in Commutative Algebra. Available via anonymous ftp from cocoa.dima.unige.it.

Capani, A., Niesi, G., Robbiano, L. (1997): Some Features of CoCoA 3. Moldova Journal of Computer Science 4/3, 296–314.

Carrà, G., Robbiano, L. (1990): On SuperG-Bases. J. Pure Appl. Algebra 68, 279–292.

Cox, D., Little, J., O’Shea, D. (1992): Ideals, Varieties, and Algorithms. Springer-Verlag, New York.

Dey, A. (1985): Orthogonal Fractional Factorial Designs. John Wiley and Sons, New York.

Diaconis, P., Sturmfels, B. (1993): Algebraic Algorithms for Sampling from Conditional Distributions. To appear in Annals of Statistics

Eisenbud, D. (1995): Commutative Algebra with a View toward Algebraic Geometry. Springer Graduate Texts in Mathematics 150.

Fisher, R.A. (1935): The Design of Experiments. Oliver and Boyd, Edinburgh (1935) (1st ed.).

Fontana, M., Pistone, G., Rogantin, M.P. (1997): Classification of Two-Level Factorial Fractions. Preprint.

Geramita, A.V., Seberry, J. (1979): Orthogonal Designs: Quadratic Forms and Hadamard Matrices . Marcel Dekker, New York, N.Y.

Heiberger, R.M. (1989): Computation for the Analysis of Designed Experiments. John Wiley and Sons, New York.

Holliday, T., Riccomagno, E., Wynn, H. P., Pistone, G. (1997): The Application of Computational Algebraic Geometry to the Analysis of Designed Experiments. A Case Study. To appear in Computational Statistics.

Kreuzer, M, Robbiano, L. (1998): Computations in Commutative Algebra. In Preparation.

Marinari, M.G., Möller, M., Mora, F. (1991): Gröbner Bases of Ideals Defined by Functionals with an Application to Ideals of projective Points. AAECC 4, 103–145.

Mora, F., Robbiano, L. (1989): The Gröbner Fan of an Ideal. In L. Robbiano, ed., Computational Aspects of Commutative Algebra. Academic Press, London, 183–208.

Mora, F., Robbiano, L. (1993): Points in affine and projective spaces. In D. Eisenbud and L. Robbiano eds., Computational Algebraic Geometry and Commutative Algebra, Cortona-91, Symposia Mathematica Vol XXXIV . Cambridge University Press, 106–150.

Pistone G., Wynn, H.P. (1996). Generalised Confounding and Gröbner Bases. Biometrika 83-3, 653–666.

Raktoe, B.L., Hedayat, A., Federer, W.T. (1981): Factorial Designs. John Wiley and Sons, New York.

Robbiano, L. (1985): Term Orderings in the Polynomial Ring. Lecture Notes in Computer Science 203.

Robbiano, L. (1986): On the Theory of Graded Structures. J. Symbolic Comput. 2 139–170.

Robbiano, L., Rogantin, M.P. (1998): Full Factorial Designs and Distracted Fractions. This volume.

Street A.P., Street, D.J. (1987): Combinatorics of Experimental Design. Oxford Clarendon.

Yates, F. (1937): Design and Analysis of Factorial Experiments, London: Imperial Bureau of Soil Sciences.

L. Robbiano

Dipartimento di Matematica, Università di Genova (Italy)

                                  E-mail: robbiano@dima.unige.it