Topics in hyperplane arrangements, polytopes and box-splines.

*(English)*Zbl 1217.14001
Universitext. New York, NY: Springer (ISBN 978-0-387-78962-0/pbk; 978-0-387-78963-7/ebook). xx, 384 p. (2011).

Some diverse subjects are treated here. The mention of box splines will attract the attention of numerical analysts, and hyperplane arrangements belong, in this context, to algebraic geometry; but polytopes are central in the book as in the title.

The basic problem is to compute the partition functions \({\mathcal T}_X(x)\), where \(X=(a_1,\dots,a_m)\) is a finite spanning subset of \(V={\mathbb R}^s\), and for \(b\in \Lambda=\sum{\mathbb Z} a_i\), we define \[ {\mathcal T}_X(b):=\#\{(n_1,\dots,n_m)\in {\mathbb N}^m\mid \sum n_ia_i=b\}. \] This is the number of integral points in the polytope \[ \Pi_X(b)=\{y\in{\mathbb R}_{\geq 0}^m\mid Ay=b\}, \] where \(A\) is the matrix whose columns are the \(a_i\). Every convex polytope arises in this way, so the problem is as general as counting integer points in polytopes. We assume here that the convex hull \(\text{Conv}(X)\) of \(X\) does not contain \(0\); otherwise, one should replace \(\Pi_X(b)\) by \(\Pi^1_X(b)\) and \({\mathcal T}_X(b)\) by \(Q_X(b)\), requiring \(n_i\leq 1\) and \(y_i\leq 1\), so as to still deal with bounded polytopes.

The zonotope or box \(B(X)\) is the Minkowski sum of the segments \([0,a_i]\). It is the set of points \(x\in V\) for which \(\Pi^1_X(x)\neq\emptyset\). If \(0\not\in \text{Conv}(X)\), one may instead work with the cone \(C(X)\) generated by \(X\). The box spline \(B(x)\) and the multivariate spline \(T_X(x)\) are given by \[ \int_V f(x)B_X(x)\,dx=\int_0^1\cdots\int_0^1 f\Big(\sum_{i=1}^m t_ia_i\Big)\,dt_1\cdots dt_m, \] and (for \(0\not\in \text{Conv}(X)\)) \[ \int_V f(x)T_X(x)\,dx=\int_0^\infty\cdots\int_0^\infty f\Big(\sum_{i=1}^m t_ia_i\Big)\,dt_1\cdots dt_m, \] where \(f\) runs through a suitable set of test functions. These have support on \(B(X)\) and \(C(X)\) respectively. The functions \(T_X(x)\), \(B_X(x)\) and \({\mathcal T}_X(x)\) can all be expressed as finite sums of local pieces. These local pieces are polynomials for the splines. For the partition functions they are quasipolynomials, i.e., they are polynomials on each coset of some sublattice \(\Lambda_0\subset \Lambda\). Together with their derivatives (respectively translates) they span a finite-dimensional space \(D(X)\) of polynomials, respectively a finite-dimensional space \(DM(X)\) of quasipolynomials.

These spaces were studied by W. Dahmen and C. A. Micchelli [Trans. Am. Math. Soc. 308, No. 2, 509–532 (1988; Zbl 0655.10013)], who showed that they are given by a system of differential equations (in the spline cases) or difference equations (in the partition function case). The differential and difference operators are each indexed by the cocircuits in \(X\) viewed as matroids, and the spaces \(D(X)\) and \(DM(X)\) are closely linked.

This book revisits the paper of Dahmen and Micchelli and reproves some of their results (in a slightly sharper form) by different methods. Moreover (and presumably this is the aspect that first attracted the authors to the subject), they relate the theory to the theory of hyperplane arrangements, viewing \(X\) as a list of linear functions on \(U=V^\vee\). This is what gives the book its interdisciplinary character. The methods of the book are rather algebraic, very different in flavour from the majority of work on splines from a numerical analysis point of view, but similar to the work on partition functions of Szenes, Brion and Vergne.

The book falls into five sections: a helpful summary is given in the introduction, and the remainder of this review is a prĂ©cis of that summary. The first part of the book collects basic material on convex sets and polytopes, on Laplace and Fourier transforms and on modules over the Weyl algebra \(W(U)\) of differential operators with complex polynomial coefficients on \(U\). There is also a discussion of linear difference equations and their relation to systems of PDEs, and a digression about Tutte polynomials, which are computed for root systems.

The second part is about the differentiable, i.e. spline, case. The authors analyze the coordinate ring of the complement of a hyperplane arrangement via modules over \(W(U)\) and use their analysis to prove the result of Dahmen and Micchelli on the dimension of \(D(X)\): they introduce the notion of graded dimension of \(D(X)\) which is related to Tutte polynomials.

The third part is about the discrete, i.e. partition function, case. Now, the elements of \(X\) lie in a lattice \(\Lambda\), which was not needed earlier, and the methods of the second part can be made to go further as a result. The hyperplane arrangements are replaced by toric arrangements (given by some characters of a torus being \(1\)). These are also studied via module theory and the partition functions are computed via residues, following Szenes and Vergne. A result of M. Brion and M. Vergne [J. Am. Math. Soc. 10, No. 4, 797–833 (1997; Zbl 0926.52016)], proved here by a different method, provides a link back to multivariate splines. This leads to a description of some classical computations, including Dedekind sums.

Two more specialised sections conclude the book. The fourth gives an account of the application of splines to approximation theory, in a language acceptable to algebraists. The fifth addresses the Jeffrey-Kirwan residue formula, which appeared as a purely combinatorial device earlier, in its perhaps native geometric context, and, specifically, in relation to wonderful models of subspace arrangements, following earlier work of the authors.

The book is written at a relatively elementary level: the authors do not presuppose a detailed knowledge of approximation theory nor (except, to some extent, in the final section) of algebraic geometry. Even so, and despite the clear and careful writing, it is not always easy to read, simply because of the amount of detail that is necessary. A motivated reader will find it well worth the effort.

The basic problem is to compute the partition functions \({\mathcal T}_X(x)\), where \(X=(a_1,\dots,a_m)\) is a finite spanning subset of \(V={\mathbb R}^s\), and for \(b\in \Lambda=\sum{\mathbb Z} a_i\), we define \[ {\mathcal T}_X(b):=\#\{(n_1,\dots,n_m)\in {\mathbb N}^m\mid \sum n_ia_i=b\}. \] This is the number of integral points in the polytope \[ \Pi_X(b)=\{y\in{\mathbb R}_{\geq 0}^m\mid Ay=b\}, \] where \(A\) is the matrix whose columns are the \(a_i\). Every convex polytope arises in this way, so the problem is as general as counting integer points in polytopes. We assume here that the convex hull \(\text{Conv}(X)\) of \(X\) does not contain \(0\); otherwise, one should replace \(\Pi_X(b)\) by \(\Pi^1_X(b)\) and \({\mathcal T}_X(b)\) by \(Q_X(b)\), requiring \(n_i\leq 1\) and \(y_i\leq 1\), so as to still deal with bounded polytopes.

The zonotope or box \(B(X)\) is the Minkowski sum of the segments \([0,a_i]\). It is the set of points \(x\in V\) for which \(\Pi^1_X(x)\neq\emptyset\). If \(0\not\in \text{Conv}(X)\), one may instead work with the cone \(C(X)\) generated by \(X\). The box spline \(B(x)\) and the multivariate spline \(T_X(x)\) are given by \[ \int_V f(x)B_X(x)\,dx=\int_0^1\cdots\int_0^1 f\Big(\sum_{i=1}^m t_ia_i\Big)\,dt_1\cdots dt_m, \] and (for \(0\not\in \text{Conv}(X)\)) \[ \int_V f(x)T_X(x)\,dx=\int_0^\infty\cdots\int_0^\infty f\Big(\sum_{i=1}^m t_ia_i\Big)\,dt_1\cdots dt_m, \] where \(f\) runs through a suitable set of test functions. These have support on \(B(X)\) and \(C(X)\) respectively. The functions \(T_X(x)\), \(B_X(x)\) and \({\mathcal T}_X(x)\) can all be expressed as finite sums of local pieces. These local pieces are polynomials for the splines. For the partition functions they are quasipolynomials, i.e., they are polynomials on each coset of some sublattice \(\Lambda_0\subset \Lambda\). Together with their derivatives (respectively translates) they span a finite-dimensional space \(D(X)\) of polynomials, respectively a finite-dimensional space \(DM(X)\) of quasipolynomials.

These spaces were studied by W. Dahmen and C. A. Micchelli [Trans. Am. Math. Soc. 308, No. 2, 509–532 (1988; Zbl 0655.10013)], who showed that they are given by a system of differential equations (in the spline cases) or difference equations (in the partition function case). The differential and difference operators are each indexed by the cocircuits in \(X\) viewed as matroids, and the spaces \(D(X)\) and \(DM(X)\) are closely linked.

This book revisits the paper of Dahmen and Micchelli and reproves some of their results (in a slightly sharper form) by different methods. Moreover (and presumably this is the aspect that first attracted the authors to the subject), they relate the theory to the theory of hyperplane arrangements, viewing \(X\) as a list of linear functions on \(U=V^\vee\). This is what gives the book its interdisciplinary character. The methods of the book are rather algebraic, very different in flavour from the majority of work on splines from a numerical analysis point of view, but similar to the work on partition functions of Szenes, Brion and Vergne.

The book falls into five sections: a helpful summary is given in the introduction, and the remainder of this review is a prĂ©cis of that summary. The first part of the book collects basic material on convex sets and polytopes, on Laplace and Fourier transforms and on modules over the Weyl algebra \(W(U)\) of differential operators with complex polynomial coefficients on \(U\). There is also a discussion of linear difference equations and their relation to systems of PDEs, and a digression about Tutte polynomials, which are computed for root systems.

The second part is about the differentiable, i.e. spline, case. The authors analyze the coordinate ring of the complement of a hyperplane arrangement via modules over \(W(U)\) and use their analysis to prove the result of Dahmen and Micchelli on the dimension of \(D(X)\): they introduce the notion of graded dimension of \(D(X)\) which is related to Tutte polynomials.

The third part is about the discrete, i.e. partition function, case. Now, the elements of \(X\) lie in a lattice \(\Lambda\), which was not needed earlier, and the methods of the second part can be made to go further as a result. The hyperplane arrangements are replaced by toric arrangements (given by some characters of a torus being \(1\)). These are also studied via module theory and the partition functions are computed via residues, following Szenes and Vergne. A result of M. Brion and M. Vergne [J. Am. Math. Soc. 10, No. 4, 797–833 (1997; Zbl 0926.52016)], proved here by a different method, provides a link back to multivariate splines. This leads to a description of some classical computations, including Dedekind sums.

Two more specialised sections conclude the book. The fourth gives an account of the application of splines to approximation theory, in a language acceptable to algebraists. The fifth addresses the Jeffrey-Kirwan residue formula, which appeared as a purely combinatorial device earlier, in its perhaps native geometric context, and, specifically, in relation to wonderful models of subspace arrangements, following earlier work of the authors.

The book is written at a relatively elementary level: the authors do not presuppose a detailed knowledge of approximation theory nor (except, to some extent, in the final section) of algebraic geometry. Even so, and despite the clear and careful writing, it is not always easy to read, simply because of the amount of detail that is necessary. A motivated reader will find it well worth the effort.

Reviewer: G. K. Sankaran (Bath)

##### MSC:

14-02 | Research exposition (monographs, survey articles) pertaining to algebraic geometry |

05B35 | Combinatorial aspects of matroids and geometric lattices |

05E40 | Combinatorial aspects of commutative algebra |

11P21 | Lattice points in specified regions |

14A05 | Relevant commutative algebra |

14M25 | Toric varieties, Newton polyhedra, Okounkov bodies |

14N20 | Configurations and arrangements of linear subspaces |

41A15 | Spline approximation |

52B20 | Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) |

52B40 | Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) |

65D07 | Numerical computation using splines |