| Part I The Essentials of Discrete Volume Computations |
|
|
1 The Coin-Exchange Problem of Frobenius |
|
|
3 | |
|
1.1 Why Use Generating Functions? |
|
|
3 | |
|
|
|
5 | |
|
1.3 Partial Fractions and a Surprising Formula |
|
|
7 | |
|
|
|
11 | |
|
|
|
13 | |
|
|
|
15 | |
|
|
|
17 | |
|
|
|
23 | |
|
2 A Gallery of Discrete Volumes |
|
|
25 | |
|
2.1 The Language of Polytopes |
|
|
25 | |
|
|
|
26 | |
|
|
|
29 | |
|
2.4 The Bernoulli Polynomials as Lattice-Point Enumerators of Pyramids |
|
|
31 | |
|
2.5 The Lattice-Point Enumerators of the Cross-Polytopes |
|
|
36 | |
|
|
|
38 | |
|
2.7 Polygons with Rational Vertices |
|
|
41 | |
|
2.8 Euler's Generating Function for General Rational Polytopes |
|
|
45 | |
|
|
|
48 | |
|
|
|
50 | |
|
|
|
54 | |
|
3 Counting Lattice Points in Polytopes: The Ehrhart Theory |
|
|
57 | |
|
3.1 Triangulations and Pointed Cones |
|
|
57 | |
|
3.2 Integer-Point Transforms for Rational Cones |
|
|
60 | |
|
3.3 Expanding and Counting Using Ehrhart's Original Approach |
|
|
64 | |
|
3.4 The Ehrhart Series of an Integral Polytope |
|
|
67 | |
|
3.5 From the Discrete to the Continuous Volume of a Polytope |
|
|
71 | |
|
|
|
73 | |
|
3.7 Rational Polytopes and Ehrhart Quasipolynomials |
|
|
75 | |
|
3.8 Reflections on the Coin-Exchange Problem and the Gallery of Chapter 2 |
|
|
76 | |
|
|
|
76 | |
|
|
|
77 | |
|
|
|
82 | |
|
|
|
83 | |
|
4.1 Generating Functions for Somewhat Irrational Cones |
|
|
84 | |
|
4.2 Stanley's Reciprocity Theorem for Rational Cones |
|
|
86 | |
|
4.3 Ehrhart—Macdonald Reciprocity for Rational Polytopes |
|
|
87 | |
|
4.4 The Ehrhart Series of Reflexive Polytopes |
|
|
88 | |
|
4.5 More "Reflections" on Chapters 1 and 2 |
|
|
90 | |
|
|
|
90 | |
|
|
|
91 | |
|
|
|
93 | |
|
5 Face Numbers and the Dehn—Sommerville Relations in Ehrhartian Terms |
|
|
95 | |
|
|
|
95 | |
|
5.2 Dehn—Sommerville Extended |
|
|
97 | |
|
5.3 Applications to the Coefficients of an Ehrhart Polynomial |
|
|
98 | |
|
|
|
100 | |
|
|
|
102 | |
|
|
|
103 | |
|
|
|
104 | |
|
|
|
105 | |
|
|
|
106 | |
|
6.2 Semimagic Squares: Points in the Birkhoff—von Neumann Polytope |
|
|
108 | |
|
6.3 Magic Generating Functions and Constant-Term Identities |
|
|
111 | |
|
6.4 The Enumeration of Magic Squares |
|
|
116 | |
|
|
|
117 | |
|
|
|
119 | |
|
|
|
120 | |
| Part II Beyond the Basics |
|
|
7 Finite Fourier Analysis |
|
|
123 | |
|
|
|
123 | |
|
7.2 Finite Fourier Series for Periodic Functions on Z |
|
|
125 | |
|
7.3 The Finite Fourier Transform and Its Properties |
|
|
129 | |
|
7.4 The Parseval Identity |
|
|
131 | |
|
7.5 The Convolution of Finite Fourier Series |
|
|
133 | |
|
|
|
135 | |
|
|
|
135 | |
|
|
|
139 | |
|
8.1 Fourier—Dedekind Sums and the Coin-Exchange Problem Revisited |
|
|
139 | |
|
8.2 The Dedekind Sum and Its Reciprocity and Computational Complexity |
|
|
143 | |
|
8.3 Rademacher Reciprocity for the Fourier—Dedekind Sum |
|
|
144 | |
|
8.4 The Mordell—Pommersheim Tetrahedron |
|
|
147 | |
|
|
|
150 | |
|
|
|
151 | |
|
|
|
153 | |
|
9 The Decomposition of a Polytope into Its Cones |
|
|
155 | |
|
9.1 The Identity "Σmelement of zzm = 0" ...or "Much Ado About Nothing" |
|
|
155 | |
|
9.2 Tangent Cones and Their Rational Generating Functions |
|
|
159 | |
|
|
|
160 | |
|
9.4 Brion Implies Ehrhart |
|
|
162 | |
|
|
|
163 | |
|
|
|
164 | |
|
10 Euler–Maclaurin Summation in Rd |
|
|
167 | |
|
10.1 Todd Operators and Bernoulli Numbers |
|
|
167 | |
|
10.2 A Continuous Version of Brion's Theorem |
|
|
170 | |
|
10.3 Polytopes Have Their Moments |
|
|
172 | |
|
10.4 From the Continuous to the Discrete Volume of a Polytope |
|
|
174 | |
|
|
|
176 | |
|
|
|
177 | |
|
|
|
178 | |
|
|
|
179 | |
|
11.1 A New Discrete Volume Using Solid Angles |
|
|
179 | |
|
11.2 Solid-Angle Generating Functions and a Brion-Type Theorem |
|
|
182 | |
|
11.3 Solid-Angle Reciprocity and the Brianchon—Gram Relations |
|
|
184 | |
|
11.4 The Generating Function of Macdonald's Solid-Angle Polynomials |
|
|
188 | |
|
|
|
189 | |
|
|
|
189 | |
|
|
|
190 | |
|
12 A Discrete Version of Green's Theorem Using Elliptic Functions |
|
|
191 | |
|
|
|
191 | |
|
12.2 The Weierstraß and ζ Functions |
|
|
193 | |
|
12.3 A Contour-Integral Extension of Pick's Theorem |
|
|
195 | |
|
|
|
196 | |
|
|
|
196 | |
|
|
|
197 | |
| Appendix: Triangulations of Polytopes |
|
199 | |
| Hints for black club Exercises |
|
203 | |
| References |
|
211 | |
| List of Symbols |
|
221 | |
| Index |
|
223 | |