Introduction

The problem of inverting a birational maps arises in several contexts in algorithmic algebraic geometry, and an efficient solution is useful in many situations.

For instance, consider the parameterization problem, which is useful for numerous applications in CAD/CAM (see section 3). A closer look to the existing parameterization algorithms reveals that a parameterization is often obtained via inversion of some birational map.

In this paper, we present a new efficient algorithm for the inversion of birational maps, based on the method of Gröbner bases (Buchberger 1965, Buchberger 1979, Buchberger 1983, Beckers and Weispfenning 1993).

For a special case, the inversion problem has also been investigated in (Essen 1990, Audoly et al. 1991) (see also (Ollivier 1989) for related work), in the context of the Jacobian conjecture (Keller 1939). The general problem was solved in (Sweedler 1993) (see also Shannon and Sweedler 1988). However, Sweedler's method depends on computing the components of the inverse map one by one, i.e. it requires the computation of a Gröbner basis with lexicographical termorder. It is known (see Faugère et al. 1993) that such a Gröbner basis is much harder to compute than Gröbner bases with respect to other term orders (e.g. the reverse lexicographical termorder).

Gröbner bases were introduced in 1965 by the first editor (Buchberger) in his Ph.D. thesis. It took some years before the concept became known to the research communities in Mathematics and Theoretical Computer Science, but about ten years later many other research groups around the world started working on or using this concept. The theory of Gröbner bases has become an important subarea in computer algebra, it is included in all the major program systems of symbolic computation, and it is being fruitfully applied in a variety of seemingly unrelated research areas.

We at RISC-Linz wanted to celebrate the fact that Gröbner bases have been around now for a third of a century, and in doing so provide a snapshot of the state of the art. For this reason we organized a Special Year on Gröbner Bases, culminating in an intensive course for young researchers (January 1998) and in the conference “33 Years of Gröbner Bases”, held at RISC-Linz in February 2–4, 1998. The conference included both tutorials on various aspects of Gröbner bases and their application, and the presentation of original research papers on new developments in the theory of Gröbner bases.

The present book is the outcome of these activities. It contains a short introduction to the theory of Gröbner bases, tutorial papers on the interaction between Gröbner bases and various other mathematical theories, and the original research papers presented at the conference.

Introduction

In this note, we give a sketch of several interactions between coding theory (or rather algebraic coding theory) and Gröbner bases theory. Precisely, coding theory is the theory of error-correcting codes, which are used widely in digital communication and storage systems to transmit or to store digital information error-free or as correct as possible. Although error-correcting codes are probabilistic by nature in the sense that they are used to battle against random noise in transmission or storage channels, practical codes are constructed in deterministic fashions with algebraic methods, without which error control cannot be achieved with low complexity and cost. As a result, almost all of them are algebraic. Therefore we discuss nothing but the algebraic error-correcting codes.

Introduction

Design of Experiments (DoE) is a branch of Statistics, which has a long tradition in the use of algebraic methods (see for example Box et al. 1978 and Collombier 1996). In general all these methods were developed in the case of binary experiments, with coding levels either {0,1} or {-1,1} and some generalizations to the non-binary case were also developed (see Collombier 1996).

More recently some connections were discovered between classical problems in Statistics and the methods of Computer Algebra. For instance in their recent work Pistone and Wynn (1996) address the problem of identifying polynomial models in general designs. In particular they point out the connection between DoE and Gröbner bases.

Introduction

This article is a brief survey of recent work on Gröbner bases (Buchberger 1965) of toric ideals and their role in integer programming. Toric varieties and ideals are crucial players in the interaction between combinatorics, discrete geometry, commutative algebra and algebraic geometry. For a detailed treatment of this topic see (Sturmfels 1995). Our survey focuses on the application of toric ideals to integer programming, a specific branch of discrete optimization, and for the sake of brevity we leave details to the references that are included.

We study a family of integer programs associated with a fixed matrix A and the corresponding toric ideal IA. In Section 2, we show that reduced Gröbner bases of IA are test sets for these integer programs. In Section 3, we define the universal Gröbner basis of IA and we identify it as a subset of the Graver basis of A. Section 4 deals with the effect of varying the cost function while keeping the matrix A fixed; there we give a self contained construction of the state polytope and Gröbner fan of IA. Moreover, we show that the edge directions of the state polytope are precisely the elements in the universal Gröbner basis of IA. We conclude in Section 5 with a discussion of practical issues that arise while computing Gröbner bases of toric ideals. In particular we discuss algorithms for finding generating sets for IA.

This is the first book devoted to broad study of the combinatorics of words, that is to say, of sequences of symbols called letters. This subject is in fact very ancient and has cropped up repeatedly in a wide variety of contexts. Even in the most elegant parts of abstract pure mathematics, the proof of a beautiful theorem surprisingly often reduces to some very down to earth combinatorial lemma concerning linear arrays of symbols. In applied mathematics, that is in the subjects to which mathematics can be applied, such problems are even more to be expected. This is true especially in those areas of contemporary applied mathematics that deal with the discrete and non-commutative aspects of the world about us, notably the theory of automata, information theory, and formal linguistics.

The systematic study of words seems to have been initiated by Axel Thue in three papers [Norske Vid. Selsk. Skr. I Mat. Nat. Kl. Christiania, 1906, 1–22; 1912, 1–67; 1914, 1–34.]. Even more than for his theorems, we owe him a great debt for delineating this subject. Both before and after his time, a multitude of fragmentary results have accumulated in the most diverse contexts, and a substantial but not very widely known lore was beginning to crystallize to the point where a systematic treatment of the subject was badly needed and long over due.

This need is splendidly fulfilled by the present volume.

Introduction

The investigation of words includes a series of combinatorial studies with rather surprising conclusions that can be summarized roughly by the following statement: Each sufficiently long word over a finite alphabet behaves locally in a regular fashion. That is to say, an arbitrary word, subject only to the constraint that it be sufficiently long, possesses some regularity. This claim becomes meaningful only if one specifies the kind of regularities that are intended, of course. The discovery and the analysis of these unavoidable regularities constitute a major topic in the combinatorics of words. A typical example is furnished by van der Waerden's theorem.

It should not be concluded that any sufficiently long word is globally regular. On the contrary, the existence of unavoidable regularities leads to the dual question of avoidable regularities: properties not automatically shared by all sufficiently long words. For such a property there exist infinitely many words (finiteness of the alphabet is supposed) that do not satisfy it. The present chapter is devoted mainly to the study of one such property.

A square is a word of the form uu, with u a nonempty word. A word contains a square if one of its factors is a square; otherwise, the word is called square-free. For instance, abcacbacbc contains the square acbacb, and abcacbabcb is square-free. The answer to the question of whether every sufficiently long word contains a square is no, provided the alphabet has at least three letters.

The new printing of Combinatorics on words does not bring many changes. Except for the correction of some misprints and errors, the text has not been modified. I would like to thank those readers who have sent corrections and, in particular, Aldo De Luca, Pavel Goralcik and Bruno Petazzoni.

More than ten years have passed since the first publication of this book. A lot of water has flowed under the bridges of Lotharingia since then.

There is bad news, first. Roger Lyndon, the author of the Foreword of the first edition passed away a few years ago, leaving the memory of a great mathematician and a marvellous man, as did Marcel-Paul Schützenberger this year. He was the spirit behind the scene, and most of the ideas contained in the book were inspired by him. Also, the collective group of authors almost entirely consists of his former students. It is a small tribute to dedicate this book to him.

There is also good news. A new volume on the subject of combinatorics on words is in preparation. It will contain chapters, written by new authors, on topics that had not been included in this volume, making a complementary work, but one which can be read independently. It will cover in particular some aspects of symbolic dynamics, the theory of Young tableaux through the approach of the plactic monoid, combinatorial aspects of free algebras, number systems, and word functions.

Introduction

This chapter contains the main definitions used in the rest of the book. It also presents some basic results about words that are of constant use in the sequel. In the first section are defined words, free monoids, and some terms about words, such as length and factors.

Section 1.2 is devoted to submonoids and to morphism of free monoids, one of the basic tools for words. Many of the proofs of properties of words involve a substitution from the alphabet into words over another alphabet, which is just the definition of a morphism of free monoids. A nontrivial result called the defect theorem is proved. The theorem asserts that if a relation exists among words in a set, those words can be written on a smaller alphabet. This is a weak counterpart for free monoids of the Nielsen–Schreier theorem for subgroups of a free group.

In Section 1.3 the definition of conjugate words is given, together with some equivalent characterizations. Also defined are primitive words, or words that are not a repetition of another word. A very useful result, due to Fine and Wilf, is proved that concerns the possibility of multiple repetitions. The last section introduces the notation of formal series that deal with linear combinations of words, which will be used in Chapters 5–7 and 11.

A list of problems, some of them difficult, is collected at the end.

Introduction

This chapter is devoted to the study of a special type of unavoidable regularities. We consider a mapping φ:A+ → E from A+ to a set E, and we search in a word w for factors of the type w1w2 … wn with φ(w1) = φ(w2)= … = φ(wn). The mapping is called repetitive when such a factor appears in each sufficiently long word. This is related both to square-free words (Chapter 2), by considering the identity mapping, and to van der Waerden's theorem (Chapter 3), as will be shown later on.

It will first be shown that any mapping from A+ to a finite set is repetitive (Theorem 4.1.1).

After a direct proof of this fact, it will be shown how the result can also be deduced from Ramsey's theorem (which is stated without proof).

Investigated also is the special case where φ is a morphism from A+ to a semigroup S. First it is proved that a morphism to the semigroup of positive integers is repetitive when the alphabet is finite (Theorem 4.2.1). Then it is proved that a morphism to a finite semigroup is uniformly repetitive, in the sense that the words w1, w2,…, wn/i> in the foregoing definition can be chosen of equal length (Theorem 4.2.2). This is, as will be shown, a generalization of van der Waerden's theorem. Finally, the chapter mentions a number of extensions and other results.

Introduction

Let us consider two words x, y of the free monoid A*, satisfying the equality:

By Proposition 1.3.2 of Chapter 1, there exist a word u ∈ A* and two integers n, p ≥ 0 such that

In this chapter, we will view x and y as the letters of an alphabet Ξ. We will say that xy = yx is an equation in the unknowns Ξ = {x, y} and that the morphism α: Ξ* → A* defined by α(x) = un and α(y) = up is a solution of the equation. Observe that all solutions of this particular equation are of this type.

The basic notions on equations are presented in Section 9.1. In Section 9.2, we consider a few equations whose families of solutions admit a finite description, as in the preceding example. Indeed, the family of solutions of Eq. (9.0.1) is entirely described by the unique expression (9.0.2), where u runs over all words and n, p over all positive integers. This idea is formalized in Section 9.3, which introduces the notion of parametrizable equations and where it is recalled that all equations in three unknowns are parametrizable.

Not all equations are parametrizable, however. We are thus led in Section 9.4 to define the rank of an equation, which is the maximum number of the letters occurring in the expression of particular solutions called principal.

Introduction

Let us recall the definition: a word f in A* is a finite sequence of elements of A, called letters. We shall call a subword of a word f any sequence contained in the sequence f. The word aba for instance is a subword of the word bacbcab as well as of the word aabbaa. It can be observed immediately that two sub-sequences of f, distinct as subsequences, may define the same subword: thus aba is a subword of bacbcab in only one way but may be obtained as a subword of aabbaa in eight different ways.

A word f being given it is easy to compute the set of its subwords and their multiplicity; this computation is obtained by a simple induction formula. The main problem of interest in this chapter, sometimes implicitly but more often explicitly, is the one of the inverse correspondence. Under what conditions is a given set of words S the set of subwords, or a subset of certain kind of the set of subwords, of a word f? Once these conditions are met, what are the words f that are thus determined? In which cases are they uniquely determined? Some of these conditions on that set S are rather obvious. For instance if g is a subword of f, then any subword of g is a subword of f.