Undergraduate Texts in Mathematics - maths.ed.ac.uk

1 Undergraduate Texts in MathematicsEditorsS. RibetAbbott: Understanding : Mathematics : A Concise History and Philosophy. Readings in : The Heritage of Thales. Readings in : Introduction to Analytic Number Theory. Second : Basic : Groups and : Linear Algebra Done Right. Second : Limits: A New Approach to Real : Complex Analysis. Second : Linear Algebra Through Geometry. Second : Computing the Continuous DiscretelyBerberian: A First Course in Real : Conics and Cubics: A Concrete Introduction to Algebraic maud: An Introduction to Probabilistic : Factorization and Primality : Second Year Calculus. Readings in : Mathematical Introduction to Linear Programming and Game : Mathematical Analysis: An : Introduction to Cryptography.

2 Second Rooij: Topological Spaces: From Distance to : The Geometry of Spacetime: An Introduction to Special and General Brunt: The Lebesgue Stieltjes Integral: A Practical : A Course in Modern Geometries. Second : A Field Guide to AlgebraChilds: A Concrete Introduction to Higher Algebra. Second : Elementary Probability Theory: With Stochastic Processes and an Introduction to Mathematical Finance. Fourth Shea: Ideals, Varieties, and Algorithms. Second : Basic Concepts of Algebraic : Difference Equations. From Rabbits to ChaosCurtis: Linear Algebra: An Introductory Approach. Fourth : Reading, Writing, and Proving: A Closer Look at : The Joy of Sets: Fundamentals of Contemporary Set Theory. Second : General : Why Math?Ebbinghaus/Flum/Thomas: Mathematical Logic.

3 Second : Measure, Topology, and Fractal : An Introduction to Difference Equations. Third s/Sur nyi: Topics in the Theory of : Practical Analysis on One : An Accompaniment to Higher : Inside : The Fundamental Theory of : Intermediate Real : Calculus Two: Linear and Nonlinear Functions. Second : Functions of Several Variables. Second : Combinatorial Optimization for : Optimization Techniques: An : Methods of Mathematical : An Introduction to Wavelets Through Linear : Complex : A Course in Calculus and Real AnalysisGordon: Discrete : Analysis by Its History. Readings in : Finite-Dimensional Vector Spaces. Second : Naive Set mmerlin/Hoffmann: Numerical Mathematics . Readings in : Combinatorics and Graph : Geometry: Euclid and : Introduction to Calculus and Classical : Mathematical Refl ections: In a Room with Many : Mathematical Vistas: From a Room with Many : Elementary Stability and Bifurcation Theory.

4 Second Texts in Mathematics (continued after index)Matthias Beck Sinai RobinsComputing the Continuous DiscretelyInteger-Point Enumeration in PolyhedraMatthias BeckMathematics DepartmentSan Francisco State UniversitySan Francisco, CA RobinsDepartment of MathematicsTemple UniversityPhiladelphia, PA BoardS. AxlerMathematics DepartmentSan Francisco State UniversitySan Francisco, CA RibetDepartment of MathematicsUniversity of California, BerkeleyBerkeley, CA 978-0-387-29139-0 eISBN-13: 978-0-387-46112-0 Library of Congress Control Number: 2006931787 Mathematics Subject Classifi cations (2000): 05 Axx 11 Dxx 11 Pxx 11 Hxx 52 Bxx 52 Cxx 68 Rxx 2007 Springer Science+Business Media, LLCAll rights reserved. This work may not be translated or copied in whole or in part without the written permission of the publisher (Springer Science+Business Media, LLC, 233 Spring Street, New York, NY 10013, USA), except for brief excerpts in connection with reviews or scholarly analysis.

5 Use in connection with any form of information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed is use in this publication of trade names, trademarks, service marks, and similar terms, even if they are not identifi ed as such, is not to be taken as an expression of opinion as to whether or not they are subject to proprietary on acid-free 8 7 6 5 4 3 TendaiTo my mom, Michal Robinswith all our world is continuous, but the mind is MumfordWe seek to bridge some critical gaps between various fields of Mathematics bystudying the interplay between the continuous volume and the discrete vol-ume of polytopes. Examples of polytopes in three dimensions include crystals,boxes, tetrahedra, and any convex object whose faces are all flat.

6 It is amusingto see how many problems in combinatorics, number theory, and many othermathematical areas can be recast in the language of polytopes that exist insome Euclidean space. Conversely, the versatile structure of polytopes givesus number-theoretic and combinatorial information that flows naturally fromtheir and discrete volumeof a bodyPcan be described intuitively as the numberof grid points that lie insideP, given a fixed grid in Euclidean space. Thecontinuous volumeofPhas the usual intuitive meaning of volume that weattach to everyday objects we see in the real PrefaceIndeed, the difference between the two realizations of volume can bethought of in physical terms as follows. On the one hand, the quantum-level grid imposed by the molecular structure of reality gives us a discretenotion of space and hence discrete volume.

7 On the other hand, the New-tonian notion of continuous space gives us the continuous volume. We seethings continuously at the Newtonian level, but in practice we often computethings discretely at the quantum level. Mathematically, the grid weimposein space corresponding to the grid formed by the atoms that make up anobject helps us compute the usual continuous volume in very surprising andcharming ways, as we shall order to see the continuous/discrete interplay come to life amongthethree fields of combinatorics, number theory, and geometry, we begin ourfo-cus with the simple-to-statecoin-exchange problemof Frobenius. The beautyof this concrete problem is that it is easy to grasp, it provides a useful com-putational tool, and yet it has most of the ingredients of the deeper theoriesthat are developed the first chapter, we give detailed formulas that arise naturally fromthe Frobenius coin-exchange problem in order to demonstrate the intercon-nections between the three fields mentioned above.

8 The coin-exchange problemprovides a scaffold for identifying the connections between thesefields. In theensuing chapters we shed this scaffolding and focus on the interconnectionsthemselves:(1) Enumeration of integer points in polyhedra combinatorics,(2) Dedekind sums and finite Fourier series number theory,(3) Polygons and polytopes place a strong emphasis on computational techniques, and on com-puting volumes by counting integer points using various old and new , the formulas we get should not only be pretty (which they are!) butshould also allow us to efficiently compute volumes by using some nicefunc-tions. In the very rare instances of mathematical exposition when we have aformulation that is both easy to write and quickly computable, we havefound a mathematical nugget.

9 We have endeavored to fill this book withsuchmathematical of the material in this book is developed by the reader in the morethan 200 exercises. Most chapters contain warm-up exercises that do notde-pend on the material in the chapter and can be assigned before the chapteris read. Some exercises are central, in the sense that current or later materialdepends on them. Those exercises are marked with , and we give detailedhints for them at the end of the book. Most chapters also contain lists of openresearch turns out that even a fifth grader can write an interesting paper oninteger-point enumeration [145], while the subject lends itself todeep inves-tigations that attract the current efforts of leading researchers. Thus, it is anarea of Mathematics that attracts our innocent childhood questions as wellPrefaceIXas our refined insight and deeper curiosity.

10 The level of study is highly ap-propriate for a junior/senior Undergraduate course in Mathematics . In fact,this book is ideally suited to be used for acapstone course. Because the threetopics outlined above lend themselves to more sophisticated exploration, ourbook has also been used effectively for an introductory graduate help the reader fully appreciate the scope of the connections betweenthe continuous volume and the discrete volume, we begin the discourse in twodimensions, where we can easily draw pictures and quickly experiment. Wegently introduce the functions we need in higher dimensions (Dedekind sums)by looking at the coin-exchange problem geometrically as the discrete volumeof a generalized triangle, called a initial techniques are quite simple, essentially nothing more than ex-panding rational functions into partial fractions.