HANDBOOK OF CONVEX GEOMETRY Volume Β edited by RM. GRUBER, Technische Universität Wien, Austria J.M. WILLS, Universität Siegen, Germany 1993 NORTH-HOLLAND AMSTERDAM · LONDON · NEW YORK · TOKYO ELSEVIER SCIENCE PUBLISHERS B.V. Sara Burgerhartstraat 25 P.O. Box 211, 1000 AE Amsterdam, The Netherlands Library of Congress Cataloging-in-Publication Data Handbook of convex geometry / edited by P.M. Gruber, J.Μ. Wills, p. cm. Includes bibliographical references and index. ISBN 0-444-89598-1 (set of vols A and B). - ISBN 0-444-89596-5 (vol A: alk. paper). - ISBN 0-444-89597-3 (vol B: alk. paper) 1. Convex geometry. I. Gruber, Peter M., 1941- II. Wills, Jörg Μ., 1937- QA639.5.H36 1993 516\08-dc20 93-6696 CIP ISBN: 0 444 89596 5 (Vol A) ISBN: 0 444 89597 3 (Vol B) ISBN: 0 444 89598 1 (Set of Vols A and B) © 1993 Elsevier Science Publishers B.V. All rights reserved No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording or otherwise, without the written permission of the PubUsher, Elsevier Science Publishers B.V, Copyright & Permissions Department, PO. Box 521, 1000 AM Amsterdam, The Netherlands. Special regulations for readers in the U.S.A.: This publication has been registered with the Copyright Clearance Center Inc. (CCC), Salem, Massachusetts. Information can be obtained from the CCC about conditions under which photocopies of parts of this publication may be made in the U.S.A. All other copyright questions, including photocopying outside the U.S.A., should be referred to the Publisher, unless otherwise specified. No responsibility is assumed by the Publisher for any injury and/or damage to persons or property as a matter of products liability, negligence or otherwise, or from any use or operation of any methods, products, instructions or ideas contained in the material herein. This book is printed on acid-free paper. Printed in The Netheriands Preface One aim of this Handbook is to survey convex geometry, its many ramifications and its relations with other areas of mathematics. We believe that it will be a useful tool for the expert. A second aim is to give a high level introduction to most branches of convexity and its applications, showing the major ideas, methods and results. We hope that because of this feature the Handbook will act as an appetizer for future researchers in convex geometry. For them the many explicitly or implicitly stated problems should turn out to be a valuable source of inspiration. Third, the Handbook should be useful for mathematicians working in other areas as well as for econometrists, computer scientists, crystallographers, phycisists and engineers who are looking for geometric tools for their own work. In particular, mathematicians specializing in optimization, functional analysis, number theory, probability theory, the calculus of variations and all branches of geometry should profit from the Handbook. The famous treatise "Theorie der konvexen Körper" by Bonnesen and Fenchel presented in 164 pages an almost complete picture of convexity as it appeared around 1930. While a similarly comprehensive report today seems to be out of reach, the Handbook deals with most of the more important topics of convexity and its applications. By comparing the Handbook with the survey of Bonnesen and Fenchel and with more recent collections of surveys of particular aspects of geo­ metric convexity such as the AMS volume edited by Klee (1963), the Copenhagen Colloquium volume edited by Fenchel (1967), the two green Birkhäuser volumes edited by Tölke and Wills (1979) and Gruber and Wills (1983), respectively, and the New York Academy volume edited by Goodman, Lutwak, Malkevitch and Pollack (1985), the reader may see where progress was made in recent years. During the planning stage of the Handbook, which started in 1986, we got gene­ rous help from many prominent convex geometers, in particular Peter McMuUen, Rolf Schneider and Geoffrey Shephard. The discussion of the list of contents and of prospective authors turned out to be difficult. Both of us are obliged to the authors who agreed to contribute to the Handbook. In the cooperation with them we got much encouragement and the professional contacts furthered our good personal relations with many of them. The manuscripts which we finally received turned out to be much more diverse than we had anticipated. They clearly exhibit the most different characters and scientific styles of the authors and this should make the volume even more attractive. There are several researchers in geometric convexity whom we invited to con­ tribute to the Handbook but who for personal, professional or other reasons - regretfully - were not able to participate. The reader will also note that one area or another is missing in the list of contents. Examples are elementary geometry of normed planes, axiomatic convexity, and Choquet theory, but this should not diminish the usefulness of the Handbook. vi Preface Some fields such as computational and algorithmic aspects or lattice point re­ sults are dealt with in several chapters. The subjects covered are organized in five parts which in some sense reflect the fact that convexity is situated between analysis, geometry and discrete mathematics. This organization clearly has some disadvantages but we think that it will be helpful for the reader who wants to orient himself. In the editing of the Handbook we received much help, in particular from Dr. M. Henk, Dr. J. Müller, Professor S. Hildebrandt, Professor L. Payne and Professor F. Schnitzer. We are most grateful to Ms. S. Clarius and Ms. E. Rosta who typed about 1000 letters to the authors, to colleagues whom we asked for advice and to the Publishers. We most gratefully acknowledge the friendly coop­ erations and expert support of Dr. A. Sevenster and Mr. W. Maas from Elsevier Science Publishers. Finally we should like to express our sincere hope that the readers will appreciate the great effort of so many prominent authors and will find the Handbook useful for their scientific work. Peter M. Gruber Jörg Μ. Wills List of Contributors Bayer, M.M., University of Kansas, Lawrence, KS (Ch. 2.3). Bokowski, J., TH Darmstadt (Ch. 2.5). Brechtken-Manderscheid, U., Universität Würzburg (Ch. 4.3). Brehm, U., Technische Universität Dresden (Ch. 2.4). Burkard, R.E., Technische Universität Graz (Ch. 2.8). Connelly, R., Cornell University Ithaca, NY (Ch. 1.7). Eckhoff, J., Universität Dortmund (Ch. 2.1). Edelsbrunner, H., University of Illinois, Urbana, IL (Ch. 2.9). Engel, P., Universität Bern (Ch. 3.7). Ewald, G., Universität Bochum (Ch. 2.6). Fejes Toth, G., Hungarian Academy of Sciences, Budapest (Ch. 3.3). Florian, Α., Universität Salzburg (Ch. 1.6). Goodey, P., University of Oklahoma, Norman, OK (Ch. 4.9). Gritzmann, P, Universität Trier (Chs. 2.7, 3.2 and 3.4). Groemer, H., University of Arizona, Tucson, AZ (Chs. 1.4 and 4.8). Gruber, PM., Technische Universität Wien (Chs. Ο, 1.9, 1.10, 3.1 and 4.10). Heil, Ε., ΤΗ Darmstadt (Chs, 1.11 and 4.3). Klee, v.. University of Washington, Seattle, WA (Ch. 2.7). Kuperberg, W., Auburn University, Auburn, AL (Ch. 3.3). Lee, C.W., University of Kentucky, Lexington, KY (Ch. 2.3). Leichtweiß, Κ., Universität Stuttgart (Ch. 4.1). Lindenstrauss, J., The Hebrew University, Jerusalem (Ch. 4.5). Lutwak, E., Polytechnic University Brooklyn, NY (Ch. 1.5). Mani-Levitska, P., Universität Bern (Ch. 1.1). Martini, H., Technische Universität Chemnitz (Ch. 1.11). McMuUen, P, University College, London (Ch. 3.6). Milman, V.D., Tel-Aviv University (Ch. 4.5). Papini, PL., Universita degli Studi, Bologna (Ch. 4.6). Ptak, v., Czechoslovak Academy of Sciences, Prague (Ch. 4.7). Roberts, A.W., Macalester College, St. Paul, MN (Ch. 4.2). Sangwine-Yager, J.R., Saint Mary's College of California, Moraga, CA (Ch. 1.2). Schmitt, Ρ, Universität Wien (Ch. 2.2). Schneider, R., Universität Freiburg (Chs. 1.8 and 5.1). Schulte, E., Northeastern University, Boston, ΜΑ (Ch. 3.5). Talenti, G., Universita di Firenze (Chs. 1.3 and 4.4). Weil, W., TH Karlsruhe (Chs. 4.9 and 5.2). Wieacker, J.A., Universität Freiburg (Chs. 5.1 and 5.2). Wills, J.M., Universität Siegen (Chs. 2.4, 3.2 and 3.4). XI CHAPTER 3.1 Geometry of Numbers Peter M. GRUBER Abteilung für Analysis, Technische Universität Wien, Wiedner Hauptstraße 8-10, A-1040 Wien, Austria Contents 1. Introduction '741 2. Lattices and the space of lattices 741 3. The fundamental theorems 744 4. The Minkowski-Hlawka theorem 748 5. Successive minima 750 6. Reduction theory 751 6.1. Korkin-Zolotarev reduction 752 6.2. LLL or Lovasz reduction 753 7. Selected special problems and results 754 7.1. Lattice constants 754 7.2. Minima of the Epstein zeta-function 755 7.3. Moment problem 755 7.4. Parallelohedra 756 7.5. Conjecture on the product of non-homogeneous linear forms 756 7.6. Mordell's converse problem for the linear form theorem 757 References 757 HANDBOOK OF CONVEX GEOMETRY Edited by P.M. Gruber and J.M. Wills © 1993 Elsevier Science Publishers B.V All rights reserved 739 Geometry of numbers 741 1. Introduction Cum grano salis one may say that classical geometry of numbers forms a bridge between convexity, Diophantine approximation and the theory of quadratic forms. Today it is an independent problem-oriented field of mathematics having relations with such diverse areas as coding theory, modular functions, numerical integration and complexity of algorithms. During the last two decades it has again obtained its original geometric flavour. First traces of the geometry of numbers can be found in the work of Kepler, Lagrange, Gauss, Hermite, Korkin and Zolotarev (lattice packing of balls), of Dirichlet and Fedorov (lattice tiling) and of Klein (geometric theory of contin­ ued fractions). The systematic general study was initiated by Minkowski (who also coined the name of this field) in the last years of the nineteenth century. His achievements were complemented in the first decade of the twentieth cen­ tury by the work of Voronoi on the geometric theory of positive quadratic forms. Important contributors in this century were, amongst others, Blichfeldt, Siegel, Furtwängler, Delone, Venkov, Davenport, Mahler, Mordell, Hajos, their students and the schools in Vienna, Manchester-London-Cambridge, Moscow-Leningrad- Samarkand, Chandigarh, Columbus. The last two decades are characterized by the emergence of new fertile areas and the introduction of powerful tools from other parts of mathematics. Examples of such newer developments are lattice polytopes, the zeta-function, effective dense packings of balls, algorithmic problems. In the following we omit almost completely results dealing with lattice packing and covering, particularly with Euclidean balls and lattice polytopes. Very little is said about star bodies and indefinite quadratic forms. Lattice tilings are rarely mentioned, nor applications to Diophantine approximation. For more detailed information and references the reader is referred to the books and surveys of Minkowski (1896, 1907), Keller (1954), Rogers (1964), Cas­ sels (1972), Fejes Toth (1972), Gruber (1979), Loväsz (1986), Kannan (1987a), Conway and Sloane (1987), Gruber and Lekkerkerker (1987), Loväsz (1988), Grötschel, Loväsz and Schrijver (1988), Erdos, Gruber and Hammer (1989), Pohst and Zassenhaus (1989), and to the collected or selected works of Minkowski (1911), Voronoi (1952), Davenport (1977), and Hlawka (1990). See also the sections on packing, covering, tiling, lattice points and crystallography in this volume. 2. Lattices and the space of lattices A lattice L (of full rank d) in d-dimensional EucHdean space E"^ is the set of all integer linear combinations of d linearly independent vectors fei,...,fc^ G E^. (We do not distinguish between points and vectors.) is often identified with the d χ d-matrix Β having columns οι,...,ο^. {&ι,...,ο^} or Β is called a basis of L. Clearly L = BZ^ where is the lattice of all points with integer coordinates. Given a basis Β of L all others bases of L are of the form BU where 742 P.M. Gruber υ is an arbitrary integral unimodular d χ d matrix, i.e., it has integer entries and determinant ibl. The determinant d{V) of L is the absolute value of the determinant of a basis 5 = { 6 1 ,. . . of L or, geometrically expressed, the volume of the fundamental parallelepiped {«161 -1- · · · + a^b^-.O ^ a/ < 1} of L. An inequality of Hadamard says that d{V) ^\bi\--\bd\ where equality holds pre­ cisely if the basis vectors fei,..., ft^ of L are pairwise orthogonal. (| · | stands for the ordinary Euclidean norm.) Schnorr (1985) has called the quotient · · · \bd\/d(V) (^ 1) the orthogonality defect of the basis {61,...,ft^}. Bases with small orthog­ onality defect are of importance for the calculation of "short" basis vectors. The search for bases with small orthogonality defect has recently become of importance for reduction theory, see section 6. A subset of is discrete if it has only finitely many points in any bounded set. The following simple result is well known. Theorem 1· A subset L of is a lattice precisely when it is a discrete subgroup of E^ containing d linearly independent vectors. If a subset Μ of a lattice L is also a lattice it is called a sublattice of L. In this case one may choose bases of L and Μ which are related to each other in particularly simple ways. In the following result (i) and (ii) are due to Hermite and Minkowski, (iii) follows from the theory of elementary divisors. Theorem 2. Let Μ be a sublattice of a lattice L. Then (i) For any basis {61,..., b^} of L there is a basis {ci,..., Q} ofM such that C2 = W21Ö1 (1) Cd = Ud\b\-^"- + Uddbd where Uxx,...,Udd ^ Z. (ii) For any basis {ci,..., Q} 0/ Μ there is a basis {61,..., 6^} ofL such that (1) holds. (iii) There are bases {61,..., ο/ L and {ci,... Q} ofM such that (1) holds and Uij = 0 for i φ j. Given a basis of M, the problem arises to actually determine a basis {ci,... ,Q} of Μ as in (i). Frumkin (1976), and Kannan and Bachem (1979) first described polynomial time algorithms for this purpose. More precisely, there is a polynomial ρ(·, ·) such that given Μ one can determine {ci,..., Q} in at most p{d, s) arithmetic operations where d is the dimension and s the largest binary size of the coordinates of the vectors of the given basis of Μ with respect to {&i,..., ft^}. (The binary size of a rational number is the sum of the lengths of the binary representations of its numerator and its denominator.) Geometry of numbers 743 Let L be a lattice and let «ι,... ,β^_ι G be linearly independent. Then a resuh of Davenport (1955) says that for each sufficiently large λ > 0 there is a basis ... of L such that \bi - λα/|, / = 1,... ,d - 1, is "small" relative to λ. For refinements see Lekkerkerker (1961) and Wang (1975). An important concept is that of the polar or dual lattice V of a lattice L = BZ^: V = {m:l'meZ for all leL} = {B-^fZ^^ where the dot · indicates the ordinary inner product in E"^. Clearly d{V)d{V) = 1. The natural topology on the space ££ of all lattices in E"^ can be introduced in different ways, for example by the following definition: a sequence L/ e iE,i = 1,2,..., is convergent if there are a lattice L e ^ and bases {bii,...,bid} and {bi,.,.,bd} of Li and L, respectively, such that bn fei,...,bid t>d as i oo. Let ie (1) denote the subspace {L e ί£: d{l) = 1} of ^. The following selection or compactness theorem of Mahler (1946) guarantees the existence of lattices having certain extremal properties. For example, given a (proper, compact) convex body Κ it yields the existence of a lattice L G <Sß such that the translates + / G L form a packing of Κ (i.e., any two distinct translates have disjoint interiors) with packing lattice L for which the density V{K)ld(}-) is maximal. {V stands for volume.) One may think of the density as the proportion of space covered by the bodies + /: / G L. Theorem 3. Let L/ G / = 1,2,... , fee Λ sequence of lattices such that the determi­ nants d(L/) are bounded above and which are all admissible for a fixed neighborhood of the origin o. Then Li, L2,... contains a convergent subsequence, (A lattice is admissible for a set Μ or Μ-admissible if it contains no interior point of it, except, possibly, o) Outline of Proof {Following Groemer 1971)· For each L/ consider its Dirichlet- Voronoi cell D{Li,o) = {x: \x\ ^\x-l\ for all / G L}. These cells are ο-symmetric convex polytopes and the assumptions on the L/'s imply that they all contain a fixed ball with center ο and are contained in another fixed ball with center o. Thus the Blaschke selection theorem (see chapter 1.9) assures the existence of a subsequence D(L/^, o) which converges to a convex body D, say. It turns out that D is the Dirichlet-Voronoi cell of a lattice L and L/^ L. • Since iE and its closed subspace ^(1) are both locally compact there are many Borel measures on these spaces. It is of interest to specify such measures which are of geometric significance. Following Siegel (1945) we describe a "natural" construction of such a measure on <^(1). Let M{\) be the (locally compact) mul­ tiplicative group of all real d χ d-matrices of determinant ±1 where each matrix 744 P.M. Gruber Μ e Μ{\) is considered as a point of E"^^ (take lexicographic ordering). There is a Borel subset Sft of il(l) which contains precisely one element of each left coset of the subgroup %(1) of all integral unimodular matrices. It can be shown that 0 < = ]/((J{Aa: 0 < λ < 1}) < +00 where V denotes ordinary Lebesgue mea­ sure in E^'. Now, for any Borel set S8 C 91 let μ(2δ) = V(U{AS8: 0 ^ λ ^ ^)/vd' This defines a Borel measure on 91; actually μ is the restriction to 91 of the suitably normalized Haar measure on M{\). By letting correspond to each lattice L G if(l) its system of bases we obtain a one-to-one correspondence between the lattices L G ^{l) and the left cosets of and thus between and 91. Thus we may consider μ a Borel measure on iß(l). There are several proposals for classifications of the lattices in X, Some of these are connected with reduction or with particular tilings related to a lattice L, for example the tiling Z)(L,o) + /: / G L; see section 7. Another classification (into so- called Bravais types) stems from crystallography and is connected with the groups of rigid motions mapping lattices onto themselves; see, e.g., Erdos, Gruber and Hammer (1989). 3. The fundamental theorems A basic problem in geometry of numbers is to investigate whether a given set in E"^ contains a point (possibly o) of a fixed lattice. In arithmetic terms this amounts to the problem whether an inequality or a system of inequalities in d variables has a (non-trivial) integer solution. In the following we will present several simple but far reaching results, each having a wide range of mainly number-theoretic applications. We begin by stating Minkowski's first or (first) fundamental theorem of 1891. Theorem 4. Let Κ be an o-symmetric convex body and L a lattice in E^. IfV{K) ^ 2^d(L) then Κ contains at least one pair of points ±l^oofL. Outline of Proof {Via a density argument for lattice packings). It is sufficient to show the following: Let Κ contain no point / G l\{o}. Then V{K) < 2^i/(L). (1) The convexity and the symmetry of Κ yield that any two distinct bodies of the form ^AT + /: / G L are disjoint. Hence they form a packing with packing lattice L and the property that any two translates oi \K are disjoint. Since the density of such a packing is < 1, i.e., V{\K)/d{l) < 1, we obtain V{K) < 2'^d(L). This proves (1), concluding the proof of Theorem 4. • For any K, except for so-called parallelohedra (see section 7), one may replace the constant 2^ by a smaller number (depending on K) with the conclusion still