Computing the Continuous Discretely

by Beck, Matthias; Robins, Sinai

• ISBN13: 9780387291390
• ISBN10: 0387291393
• Format: Hardcover
• Copyright: 2006-12-01
• Publisher: Springer Verlag

Summary

This much-anticipated textbook illuminates the field of discrete mathematics with examples, theory, and applications of the discrete volume of a polytope. The authors have weaved a unifying thread through basic yet deep ideas in discrete geometry, combinatorics, and number theory. Because there is no other book that puts together all of these ideas in one place, this text is truly a service to the mathematical community. We encounter here a friendly invitation to the field of "counting integer points in polytopes", also known as Ehrhart theory, and its various connections to elementary finite Fourier analysis, generating functions, the Frobenius coin-exchange problem, solid angles, magic squares, Dedekind sums, computational geometry, and more. With 250 exercises and open problems, the reader will feel like an active participant, and the authors' engaging style will encourage such participation. For teachers, this text is ideally suited as a capstone course for undergraduate students or as a compelling text in discrete mathematical topics for beginning graduate students. For scientists, this text can be utilized as a quick tooling device, especially for those who want a self-contained, easy-to-read introduction to these topics.

Table of Contents

Part I The Essentials of Discrete Volume Computations
1 The Coin-Exchange Problem of Frobenius	3
1.1 Why Use Generating Functions?	3
1.2 Two Coins	5
1.3 Partial Fractions and a Surprising Formula	7
1.4 Sylvester's Result	11
1.5 Three and More Coins	13
Notes	15
Exercises	17
Open Problems	23
2 A Gallery of Discrete Volumes	25
2.1 The Language of Polytopes	25
2.2 The Unit Cube	26
2.3 The Standard Simplex	29
2.4 The Bernoulli Polynomials as Lattice-Point Enumerators of Pyramids	31
2.5 The Lattice-Point Enumerators of the Cross-Polytopes	36
2.6 Pick's Theorem	38
2.7 Polygons with Rational Vertices	41
2.8 Euler's Generating Function for General Rational Polytopes	45
Notes	48
Exercises	50
Open Problems	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
3.6 Interpolation	73
3.7 Rational Polytopes and Ehrhart Quasipolynomials	75
3.8 Reflections on the Coin-Exchange Problem and the Gallery of Chapter 2	76
Notes	76
Exercises	77
Open Problems	82
4 Reciprocity	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
Notes	90
Exercises	91
Open Problems	93
5 Face Numbers and the Dehn—Sommerville Relations in Ehrhartian Terms	95
5.1 Face It!	95
5.2 Dehn—Sommerville Extended	97
5.3 Applications to the Coefficients of an Ehrhart Polynomial	98
5.4 Relative Volume	100
Notes	102
Exercises	103
Open Problems	104
6 Magic Squares	105
6.1 It's a Kind of Magic	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
Notes	117
Exercises	119
Open Problems	120
Part II Beyond the Basics
7 Finite Fourier Analysis	123
7.1 A Motivating Example	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
Notes	135
Exercises	135
8 Dedekind Sums	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
Notes	150
Exercises	151
Open Problems	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
9.3 Brion's Theorem	160
9.4 Brion Implies Ehrhart	162
Notes	163
Exercises	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
Notes	176
Exercises	177
Open Problems	178
11 Solid Angles	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
Notes	189
Exercises	189
Open Problems	190
12 A Discrete Version of Green's Theorem Using Elliptic Functions	191
12.1 The Residue Theorem	191
12.2 The Weierstraß and ζ Functions	193
12.3 A Contour-Integral Extension of Pick's Theorem	195
Notes	196
Exercises	196
Open Problems	197
Appendix: Triangulations of Polytopes	199
Hints for black club Exercises	203
References	211
List of Symbols	221
Index	223