Computing the Continuous Discretely: Integer-point Enumeration in Polyhedra

Front Cover
Springer Science & Business Media, 2007 - Computers - 226 pages
0 Reviews
The world is continuous, but the mind is discrete. David Mumford We seek to bridge some critical gaps between various ?elds of mathematics by studying the interplay between the continuous volume and the discrete v- ume of polytopes. Examples of polytopes in three dimensions include crystals, boxes, tetrahedra, and any convex object whose faces are all ?at. It is amusing to see how many problems in combinatorics, number theory, and many other mathematical areas can be recast in the language of polytopes that exist in some Euclidean space. Conversely, the versatile structure of polytopes gives us number-theoretic and combinatorial information that ?ows naturally from their geometry. Fig. 0. 1. Continuous and discrete volume. The discrete volume of a body P can be described intuitively as the number of grid points that lie inside P, given a ?xed grid in Euclidean space. The continuous volume of P has the usual intuitive meaning of volume that we attach to everyday objects we see in the real world. VIII Preface Indeed, the di?erence between the two realizations of volume can be thought of in physical terms as follows. On the one hand, the quant- level grid imposed by the molecular structure of reality gives us a discrete notion of space and hence discrete volume. On the other hand, the N- tonian notion of continuous space gives us the continuous volume.
  

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

The CoinExchange Problem of Frobenius
3
12 Two Coins
5
13 Partial Fractions and a Surprising Formula
7
14 Sylvesters Result
11
15 Three and More Coins
13
Notes
15
Exercises
17
Open Problems
23
Exercises
119
Open Problems
120
Finite Fourier Analysis
123
72 Finite Fourier Series for Periodic Functions on Z
125
73 The Finite Fourier Transform and Its Properties
129
74 The Parseval Identity
131
75 The Convolution of Finite Fourier Series
133
Notes
135

A Gallery of Discrete Volumes
25
22 The Unit Cube
26
23 The Standard Simplex
29
24 The Bernoulli Polynomials as LatticePoint Enumerators of Pyramids
31
25 The LatticePoint Enumerators of the CrossPolytopes
36
26 Picks Theorem
38
27 Polygons with Rational Vertices
41
28 Eulers Generating Function for General Rational Polytopes
45
Notes
48
Exercises
50
Open Problems
54
Counting Lattice Points in Polytopes The Ehrhart Theory
57
32 IntegerPoint Transforms for Rational Cones
60
33 Expanding and Counting Using Ehrharts Original Approach
64
34 The Ehrhart Series of an Integral Polytope
67
35 From the Discrete to the Continuous Volume of a Polytope
71
36 Interpolation
73
37 Rational Polytopes and Ehrhart Quasipolynomials
75
38 Reflections on the CoinExchange Problem and the Gallery of Chapter 2
76
Exercises
77
Open Problems
82
Reciprocity
83
41 Generating Functions for Somewhat Irrational Cones
84
42 Stanleys Reciprocity Theorem for Rational Cones
86
43 EhrhartMacdonald Reciprocity for Rational Polytopes
87
44 The Ehrhart Series of Reflexive Polytopes
88
45 More Reflections on the CoinExchange Problem and the Gallery of Chapter 2
90
Exercises
91
Open Problems
93
Face Numbers and the DehnSommerville Relations in Ehrhartian Terms
94
52 DehnSommerville Extended
97
53 Applications to the Coefficients of an Ehrhart Polynomial
98
54 Relative Volume
100
Notes
102
Exercises
103
Magic Squares
105
61 Its a Kind of Magic
106
Integer Points in the Birkhoffvon Neumann Polytope
108
63 Magic Generating Functions and ConstantTerm Identities
111
64 The Enumeration of Magic Squares
116
Notes
117
Dedekind Sums the Building Blocks of Latticepoint Enumeration
138
82 The Dedekind Sum and Its Reciprocity and Computational Complexity
143
83 Rademacher Reciprocity for the FourierDedekind Sum
144
84 The MordellPommersheim Tetrahedron
147
Notes
150
Exercises
151
Open Problems
153
The Decomposition of a Polytope into Its Cones
155
92 Tangent Cones and Their Rational Generating Functions
159
93 Brions Theorem
160
94 Brion Implies Ehrhart
162
Notes
163
Exercises
164
EulerMaclaurin Summation Rd
166
102 A Continuous Version of Brions Theorem
170
103 Polytopes Have Their Moments
172
104 From the Continuous to the Discrete Volume of a Polytope
174
Notes
176
Exercises
177
Open Problems
178
Solid Angles
179
112 SolidAngle Generating Functions and a BrionType Theorem
182
113 SolidAngle Reciprocity and the BrianchonGram Relations
184
114 The Generating Function of Macdonalds SolidAngle Polynomials
188
Notes
189
Open Problems
190
A Discrete Version of Greens Theorem Using Elliptic Functions
191
122 The Weierstraß and ζ Functions
193
123 A ContourIntegral Extension of Picks Theorem
195
Notes
196
Open Problems
197
Vertex and Hyperplane Descriptions of Polytopes
199
A1 Every hcone is a vcone
200
A2 Every vcone is an hcone
202
Triangulations of Polytopes
204
Hints for Exercises
209
References
217
List of Symbols
227
Index
229
Copyright

Common terms and phrases

References to this book

Bibliographic information