Orthogonal arrays. Theory and applications.

*(English)*Zbl 0935.05001
Springer Series in Statistics. New York, NY: Springer. xxii, 416 p. (1999).

This is the first book dedicated to the theory and applications of Orthogonal Arrays (OA) and it is destined to become a classic, equally valuable for discrete mathematicians and for statisticians (but D. Raghavarao’s [Constructions and combinatorial problems in design of experiments (1971; Zbl 0222.62036)] is an interesting precursor). The body of the book opens with a rather thorough treatment of some of the basic aspects of the theory of OA. The Rao bounds are proved and there is an in depth discussion of some improvements in special situations. The vector space method of construction is introduced (this goes by the name of Bush construction) and the basic (trivial) duality between linear codes and linear OA is exploited to obtain basic constructions for OA (the original Bush constructions correspond to the duals of extended Reed-Solomon codes and to hyperovals in projective planes of characteristic 2, the Rao-Hamming construction yields the simplex codes). The Addelman-Kempthorne family, although not linear, is described in this context. This is followed by an introduction to error-correcting codes and the linear-programming method (without proofs), which yields bounds for codes and OA. Chapter 5 presents some more important families of (mostly linear) error-correcting codes and their OA counterparts (cyclic codes, Reed-Solomon codes, quadratic residue codes, the Golay codes, Reed-Muller codes, the Nordstrom-Robinson code and some more isolated examples), but the reader is warned in the introduction to the chapter (justly so) that the treatment is not self-contained. The following chapters are among the highlights of the book: the method of difference schemes (equivalently: OA with a regular group action on the alphabet) is given a thorough treatment, the relations with such popular and important structures as Hadamard matrices and Latin squares are explored. Chapter 9 discusses mixed OA, a natural generalization of the concept of an OA. The Preface justly describes Chapter 10 as a smorgasbord of unrelated topics and thus seems to introduce this term to English literature (the correct spelling would be smörgåsbord). The long Chapter 11 introduces to some of the aspects of the design of experiments. The book closes with a list of valuable tables and an appendix on Galois fields.

Where there is light there is also shadow. My most important criticism concerns the very concept of the book. A more accurate subtitle would have been Theory and some applications in the design of experiments. In fact the applications covered in the text are almost exclusively from this area. Other vast areas of application are hardly mentioned. To give just one important example, strongly universal hash families form a natural generalization of OA of strength 2. These structures are widely used in theoretical computer science. Another statistical approach to OA interprets the runs as elements of a sample space (with uniform distribution) and the factors as random variables. In this setting OA of strength \(t\) are characterized as families of random variables each \(t\) of which are statistically independent. This approach leads to applications in derandomization, among others. There are many more such applications, in cryptography (block cyphers, authentication, etc.) and theory of algorithms.

The short sections on resilient functions and on tms-nets cannot compensate for this defect. Moreover the section on tms-nets (a generalization of OA used for quasi-Monte Carlo methods of numerical integration) is rather inadequate and even inaccurate (it is stated that the term net is unrelated to geometrical nets, but in fact geometrical nets are special cases of tms-nets and this was the reason behind Niederreiter’s terminology).

In the theoretical arena the book has a tendency to retreat to the case of strength 2 too easily. For example, an important family with parameters \(\text{OA}(p^{n+m},p^n,p^m,2)\) for \(n\geq m\) is constructed via difference schemes. There is a natural direct construction using the affine group, which can easily be generalized to arbitrary strength. Another weak point of the book is that the level of generality is not always judiciously chosen. The use of algebraic and geometric tools would greatly benefit the clarity of exposition. For example, Galois geometries are not used. When projective planes are finally introduced (Section 8.4) this is done in a sloppy way. The main axiom is missing. Consider the constructions of mixed OA. The simple geometric notion of points, lines, etc. in general position suffices to explain all the examples with number of runs a prime-power as given in Chapter 9. An even more dramatic example are compound orthogonal arrays. Judging from Chapter 11 these are important structures. Unfortunately the constructions given in Section 10.7 do not look very systematic. However, they can all be explained in a uniform way using the simple notion of a short exact sequence of linear codes (a code, a projection of the code to a subset of coordinates and the kernel of the projection).

This work will become a standard as a textbook and an indispensible reference for researchers in design theory, coding theory and statistics. While it is not perfect (see the criticism brought forward above) it does represent a landmark. The many tables and research problems will keep researchers busy for a long time to come.

Where there is light there is also shadow. My most important criticism concerns the very concept of the book. A more accurate subtitle would have been Theory and some applications in the design of experiments. In fact the applications covered in the text are almost exclusively from this area. Other vast areas of application are hardly mentioned. To give just one important example, strongly universal hash families form a natural generalization of OA of strength 2. These structures are widely used in theoretical computer science. Another statistical approach to OA interprets the runs as elements of a sample space (with uniform distribution) and the factors as random variables. In this setting OA of strength \(t\) are characterized as families of random variables each \(t\) of which are statistically independent. This approach leads to applications in derandomization, among others. There are many more such applications, in cryptography (block cyphers, authentication, etc.) and theory of algorithms.

The short sections on resilient functions and on tms-nets cannot compensate for this defect. Moreover the section on tms-nets (a generalization of OA used for quasi-Monte Carlo methods of numerical integration) is rather inadequate and even inaccurate (it is stated that the term net is unrelated to geometrical nets, but in fact geometrical nets are special cases of tms-nets and this was the reason behind Niederreiter’s terminology).

In the theoretical arena the book has a tendency to retreat to the case of strength 2 too easily. For example, an important family with parameters \(\text{OA}(p^{n+m},p^n,p^m,2)\) for \(n\geq m\) is constructed via difference schemes. There is a natural direct construction using the affine group, which can easily be generalized to arbitrary strength. Another weak point of the book is that the level of generality is not always judiciously chosen. The use of algebraic and geometric tools would greatly benefit the clarity of exposition. For example, Galois geometries are not used. When projective planes are finally introduced (Section 8.4) this is done in a sloppy way. The main axiom is missing. Consider the constructions of mixed OA. The simple geometric notion of points, lines, etc. in general position suffices to explain all the examples with number of runs a prime-power as given in Chapter 9. An even more dramatic example are compound orthogonal arrays. Judging from Chapter 11 these are important structures. Unfortunately the constructions given in Section 10.7 do not look very systematic. However, they can all be explained in a uniform way using the simple notion of a short exact sequence of linear codes (a code, a projection of the code to a subset of coordinates and the kernel of the projection).

This work will become a standard as a textbook and an indispensible reference for researchers in design theory, coding theory and statistics. While it is not perfect (see the criticism brought forward above) it does represent a landmark. The many tables and research problems will keep researchers busy for a long time to come.

Reviewer: J.Bierbrauer (Houghton)

##### MSC:

05-02 | Research exposition (monographs, survey articles) pertaining to combinatorics |

05B15 | Orthogonal arrays, Latin squares, Room squares |

94B05 | Linear codes, general |

62K99 | Design of statistical experiments |