Bulletin of the American Mathematical Society

Author(s): Chuanming Zong
Journal: Bull. Amer. Math. Soc. 42 (2005), 181-211.
MSC (2000): Primary 05A15, 05B20, 05B25, 05B45, 11H31, 11J13, 15A33, 20K01, 28A25, 52B05, 52C20, 52C22
Posted: January 26, 2005
Retrieve article in: PDF DVI PostScript

Abstract: Unit cubes, from any point of view, are among the simplest and the most important objects in

-dimensional Euclidean space. In fact, as one will see from this survey, they are not simple at all. On the one hand, the known results about them have been achieved by employing complicated machineries from Number Theory, Group Theory, Probability Theory, Matrix Theory, Hyperbolic Geometry, Combinatorics, etc.; on the other hand, the answers for many basic problems about them are still missing. In addition, the geometry of unit cubes does serve as a meeting point for several applied subjects such as Design Theory, Coding Theory, etc. The purpose of this article is to figure out what is known about the unit cubes and what do we want to know about them.

1.: F. Affentranger and R. Schneider, Random projections of regular simplices, Discrete Comput. Geom. 7 (1992), 219-226. MR 1149653 (92k:52008)
2.: S.S. Agaian, Hadamard Matrices and Their Applications, Springer-Verlag, Berlin, 1985. MR 0818740 (87k:05038)
3.: O. Aichholzer, Extremal properties of polytopes of dimension 5, Polytopes-Combinatorics and Computation, DMV Sem. 29 (2000), 111-130. MR 1785295 (2002k:52013)
4.: M. Aigner and G.M. Ziegler, Proofs from the Book (third edition), Springer-Verlag, Berlin, 2004. MR 2014872 (2004h:00002)
5.: K. Ball, Cube slicing in , Proc. Amer. Math. Soc. 97 (1986), 465-473. MR 0840631 (87g:60018)
6.: K. Ball, Logarithmically concave functions and sections of convex sets in , Studia Math. 88 (1988), 69-84. MR 0932007 (89e:52002)
7.: K. Ball, Volumes of sections of cubes and related problems, Lecture Notes in Math. 1376 (1989), 251-260. MR 1008726 (90i:52019)
8.: K. Ball, An elementary introduction to modern convex geometry, Flavors of Geometry (edited by S. Levy), Cambridge University Press, Cambridge, 1997. MR 1491097 (99f:52002)
9.: I. Bárány and L. Lovász, Borsuk's theorem and the number of facets of centrally symmetric polytopes, Acta Math. Sci. Hungar. 40 (1982), 323-329. MR 0686332 (84g:52007)
10.: I. Bárány and A. Pór, On 0-1 polytopes with many facets, Adv. Math. 161 (2001), 209-228. MR 1851645 (2003e:52013)
11.: G. Barba, Intorno al teorema di Hadamard sui determinanti a valore massimo, Giorn. Mat. Battaglia 71 (1933), 70-86.
12.: A. Below, U. Brehm, J.A. De Loera and J. Richter-Gebert, Minimal simplicial dissections and triangulations of convex 3-polytopes, Discrete Comput. Geom. 24 (2000), 35-48. MR 1765232 (2001g:52021)
13.: L.J. Billera, R. Cushman and J.A. Sanders, The Stanley decomposition of the harmonic oscillator, Nederl. Akad. Wetensch. Indag. Math. 50 (1988), 375-393. MR 0976522 (89m:13013)
14.: L.J. Billera and A. Sarangarajan, All 0-1 polytopes are traveling salesman polytopes, Combinatorica 16 (1996), 175-188. MR 1401891 (97j:52016)
15.: C. Borell, Convex set functions in d-space, Period. Math. Hungar. 6 (1975), 111-136. MR 0404559 (53:8359)
16.: K. Böröczky Jr. and M. Henk, Random projections of regular polytopes, Arch. Math. (Basel) 73 (1999), 465-473. MR 1725183 (2001b:52004)
17.: H.J. Brascamp and E.H. Lieb, Best constants in Young's inequality, its converse, and its generalization to more than three functions, Adv. in Math. 20 (1976), 151-173. MR 0412366 (54:492)
18.: J. Brenner and L. Cummings, The Hadamard maximum determinant problem, Amer. Math. Monthly 79 (1972), 626-629. MR 0301030 (46:190)
19.: M.N. Broadie and R.W. Cottle, A note on triangulating the -cube, Discrete Math. 52 (1984), 39-49. MR 0765283 (86c:52011)
20.: G.D. Chakerian and P. Filliman, The measures of the projections of a cube, Studia Sci. Math. Hungar. 21 (1986), 103-110. MR 0898848 (88f:52007)
21.: G.F. Clements and B. Lindström, A sequence of $(\pm 1)$ -determinants with large values, Proc. Amer. Math. Soc. 16 (1965), 548-550. MR 0178001 (31:2259)
22.: K. Corrádi and S. Szabó, A combinatorial approach for Keller's conjecture, Period. Math. Hungar. 21 (1990), 95-100. MR 1070948 (91j:52025)
23.: R.W. Cottle, Minimal triangulations of the 4-cube, Discrete Math. 40 (1982), 25-29. MR 0676709 (84d:05065a)
24.: L. Dalla, D.G. Larman, P. Mani-Levitska and C. Zong, The blocking numbers of convex bodies, Discrete Comput. Geom. 24 (2000), 267-277. MR 1758049 (2001d:52011)
25.: L. Danzer and B. Grünbaum, Über zwei Probleme bezüglich konvexer Körper von P. Erdös und von V.L. Klee, Math. Z. 79 (1962), 95-99. MR 0138040 (25:1488)
26.: P. Delsarte, Bounds for unrestricted codes, by linear programming, Philips Research Reports 27 (1972), 272-289. MR 0314545 (47:3096)
27.: P. Delsarte, An algebraic approach to the association schemes of coding theory, Philips Research Reports, Suppl. 10 (1973), 1-97. MR 0384310 (52:5187)
28.: A. Dvoretzky, Some results on convex bodies and Banach spaces, Proc. Internat. Symp. Linear Spaces (1961), 123-160. MR 0139079 (25:2518)
29.: A. Dvoretzky, Some near-sphericity results, Proc. Symp. Pure Math. 7 (1963), 203-210. MR 0158308 (28:1533)
30.: M.E. Dyer, Z. Füredi and C. McDiarmid, Volumes spanned by random points in the hypercube, Random Structures Algorithms 3 (1992), 91-106. MR 1139489 (92j:52010)
31.: H. Ehlich, Determinantenabschätzungen für binäre Matrizen, Math. Z. 83 (1964), 123-132. MR 0160792 (28:4003)
32.: H. Ehlich, Determinantenabschätzungen für binäre Matrizen mit $n\equiv 3$ mod , Math. Z. 84 (1964), 438-447. MR 0168573 (29:5833)
33.: L. Fejes Tóth, Regular Figures, Pergamon Press, London, 1964. MR 0165423 (29:2705)
34.: T. Fleiner, V. Kaibel and G. Rote, Upper bounds on the maximal number of facets of polytopes, European J. Combin. 21 (2000), 121-130. MR 1737332 (2001d:52019)
35.: P. Furtwängler, Über Gitter konstanter Dichte, Monatsh. Math. Phys. 43 (1936), 281-288.
36.: E.N. Gilbert, A comparison of signaling alphabets, Bell System Tech. J. 31 (1952), 504-522.
37.: N.A. Grigorév, Regular simplices inscribed in a cube and Hadamard matrices, Proc. Steklov Inst. Math. 152 (1982), 97-98. MR 0603815 (82d:10043)
38.: P. Gritzmann, V. Klee and D.G. Larman, Largest -simplices in -polytopes, Discrete Comput. Geom. 13 (1995), 477-515. MR 1318791 (96b:52019)
39.: P.M. Gruber, Zur Charakterisierung konvexer Körper. Über einen Satz von Rogers und Shephard. II. Math. Ann. 184 (1970), 79-105. MR 0256266 (41:922)
40.: W. Gruner, Einlagerung des regulären -Simplex in den -dimensionalen Würfel, Comment. Math. Helvetici 12 (1939/40), 149-152. MR 0001205 (1:195c)
41.: U. Haagerup and H.J. Munkholm, Simplices of maximal volume in hyperbolic -space, Acta Math. 147 (1981), 1-12. MR 0631085 (82j:53116)
42.: J. Hadamard, Résolution d'une question relativ aux déterminants, Bull. Sci. Math. 28 (1893), 240-246.
43.: H. Hadwiger, Ungelöste Probleme Nr. 20, Elem. Math. 12 (1957), 121.
44.: H. Hadwiger, Gitterperiodische Punktmengen und Isoperimetrie, Monatsh. Math. 76 (1972), 410-418. MR 0324550 (48:2902)
45.: M. Haiman, A simple and relatively efficient triangulation of the -cube, Discrete $\&$ Comput. Geom. 6 (1991), 287-289. MR 1098809 (92e:52011)
46.: G. Hajós, Über einfache und mehrfache Bedeckung des -dimensionalen Raumes mit einem Würfelgitter, Math. Z. 47 (1942), 427-467. MR 0006425 (3:302b)
47.: G. Hajós, Sur la factorisation des groupes abelians, Casopis. Pést. Mat. Fys. 74 (1950), 157-162. MR 0045727 (13:623a)
48.: P. Hall, Jr., Combinatorial Theory, Blaisdell, Waltham, Mass., 1966.
49.: D. Hensley, Slicing the cube in and probability, Proc. Amer. Math. Soc. 73 (1979), 95-100. MR 0512066 (80b:60025)
50.: D. Hensley, Slicing convex bodies-Bounds for slice area in terms of the body's covariance, Proc. Amer. Math. Soc. 79 (1980), 619-625. MR 0572315 (81j:52008)
51.: M. Hudelson, V. Klee and D.G. Larman, Largest -simplices in -cubes: Some relatives of the Hadamard maximum determinant problem, Linear Algebra Appl. 241-243 (1996), 519-598. MR 1400454 (98c:15025)
52.: R.B. Hughes and M.R. Anderson, A triangulation of the -cube with simplices, Discrete Math. 117 (1993), 253-256. MR 1226146 (94b:05059)
53.: R.B. Hughes, Minimum-cardinality triangulations of the -cube for and , Discrete Math. 118 (1993), 75-118. MR 1230056 (94h:52025)
54.: R.B. Hughes, Lower bounds on cube simplexity, Discrete Math. 133 (1994), 123-138. MR 1298968 (95i:90033)
55.: R.B. Hughes and M.R. Anderson, Simplexity of the cube, Discrete Math. 158 (1996), 99-150. MR 1411113 (97g:90083)
56.: D.B. Jaffe, Optimal binary linear codes of length $\le 30$ , Discrete Math. 223 (2000), 135-155. MR 1782044 (2001i:94073)
57.: H. Jansen, Lückenlose Ausfüllung des mit gitterförmig angeordneten -dimensionalen Quadern, Dissertation, Kiel, 1909.
58.: F. John, Extremum problems with inequalities as subsidiary conditions, Courant Anniv. Vol. (1948), 187-204. MR 0030135 (10:719b)
59.: J. Kahn, J. Komlós and E. Szemerédi, On the probability that a random $\pm 1$ -matrix is singular, J. Amer. Math. Soc. 8 (1995), 223-240. MR 1260107 (95c:15047)
60.: M. Kanter, Unimodality and dominance for symmetric random vectors, Trans. Amer. Math. Soc. 229 (1977), 65-85. MR 0445580 (56:3917)
61.: O.H. Keller, Über die lückenlose Einfüllung des Raumes mit Würfeln, J. reine angew. Math. 163 (1930), 231-248.
62.: O.H. Keller, Ein Satz über die lückenlose Erfüllung des - und -dimensional Raumes mit Würfeln, J. reine angew. Math. 177 (1937), 61-64.
63.: M.N. Kolountzakis, Lattice tilings by cubes: whole, notched and extended, Electron. J. Combin. 5 (1998), 1-11. MR 1605065 (98k:52054)
64.: U.H. Kortenkamp, J. Richter-Gebert, A. Sarangarajan and G.M. Ziegler, Extremal properties of -polytopes, Discrete Comput. Geom. 17 (1997), 439-448. MR 1455692 (98d:52016)
65.: G. Kowalewski, Einführung in der Determinantentheorie einschliesslich der Fredholmschen Determinanten, Walter de Gruyter & Co., Berlin, 1954. MR 0064003 (16:210b)
66.: J.C. Lagarias and P.W. Shor, Keller's cube-tiling conjecture is false in high dimensions, Bull. Amer. Math. Soc. 27 (1992), 279-283. MR 1155280 (93e:52040)
67.: J.C. Lagarias and P.W. Shor, Cube-tilings of and nonlinear codes, Discrete Comput. Geom. 11 (1994), 359-391. MR 1273224 (95e:52044)
68.: D.G. Larman and P. Mani, Almost ellipsoidal sections and projections of convex bodies, Proc. Cambridge Philos. Soc. 77 (1975), 529-546. MR 0377697 (51:13866)
69.: C. Lee, Triangulating the -cube, Discrete Geometry and Convexity (J.E. Goodman, E. Lutwak, J. Malkevitch and R. Pollack, eds.), New York Academy of Sciences, New York (1985), 205-211. MR 0809208 (87d:52011)
70.: C. Lee, Subdivisions and triangulations of polytopes, Handbook of Discrete and Computational Geometry, CRC Press, Boca Raton (1997), 271-290. MR 1730170
71.: K. Leichtweiß, Über die affine Exzentrizität konvexer Körper, Arch. Math. 10 (1959), 187-199. MR 0107843 (21:6565)
72.: Y. Lonke, On random sections of the cube, Discrete Comput. Geom. 23 (2000), 157-169. MR 1739603 (2001e:60022)
73.: J. Mackey, A cube tiling of dimension eight with no facesharing, Discrete & Comput. Geom. 28 (2002), 275-279. MR 1920144 (2003g:52041)
74.: P.S. Mara, Triangulations for the cube, J. Combin. Theory , 20 (1976), 170-177. MR 0406838 (53:10624)
75.: R.J. McEliece, E.R. Rodemich, H. Rumsey Jr., and L. R. Welch, New upper bounds on the rate of a code via the Delsarte-Macwilliams inequalities, IEEE Trans. Inform. Theory 23 (1977), 157-166. MR 0439403 (55:12296)
76.: P. McMullen, Volumes of projections of unit cubes, Bull. London Math. Soc. 16 (1984), 278-280. MR 0738519 (85j:52019)
77.: A.I. Medyanik, A regular simplex inscribed in a cube, half-circulant Hadamard matrices, and Gaussian sums, Mat. Fiz. Anal. Geom. 8 (2001), 58-81. MR 1846358 (2002h:05029)
78.: H. Minkowski, Geometrie der Zahlen, Teubner, Leipzig, 1896.
79.: H. Minkowski, Diophantische Approximationen, Teubner, Leipzig, 1907.
80.: M.G. Neubauer and A.J. Radcliffe, The maximum determinant of $\pm 1$ matrices, Linear Algebra Appl. 257 (1997), 289-306. MR 1441716 (98a:15014)
81.: M.G. Neubauer, W. Watkins and J. Zeitlin, Maximal -simplices in the real -dimensional unit cube, J. Combin. Theory 80 (1997), 1-12. MR 1472104 (98j:52018)
82.: D. Orden and F. Santos, Asymptotically efficient triangulations of the -cube, Discrete Comput. Geom. 30 (2003), 509-528. MR 2013970 (2004i:68231)
83.: M.I. Ostrovskii, Minimal-volume shadows of cubes, J. Funct. Anal. 176 (2000), 317-330. MR 1784418 (2002a:46004)
84.: R.E.A.C, Paley, On orthogonal matrices, J. Math. Phys. 12 (1933), 311-320.
85.: O. Perron, Über lückenlose Ausfüllung des -dimensionalen Raumes durch kongruente Würfel I; II, Math. Z. (1940), 1-26; 161-180. MR 0003041 (2:153e); MR 0002185 (2:11d)
86.: O. Perron, Modulartige lückenlose Ausfüllung des mit kongruenten Würfeln I; II, Math. Ann. 117 (1940), 415-447; 117 (1941), 609-658. MR 0003042 (2:153f); MR 0006068 (3:253a)
87.: V.S. Pless, W.C. Huffman and R.A. Brualdi (eds.), Handbook of Coding Theory, Elsevier, 1998. MR 1667936 (2000h:94001)
88.: A. Prékopa, On logarithmically concave measures and functions, Acta Sci. Math. (Szeged) 34 (1973), 335-343. MR 0404557 (53:8357)
89.: L. Rédei, Die neue Theorie der endlichen abelschen Gruppen und Verallgemeinerung des Hauptsatzes von Hajós, Acta Math. Acad. Sci. Hungar. 16 (1965), 327-373. MR 0186729 (32:4187)
90.: R.M. Robinson, Multiple tiling of -dimensional space by unit cubes, Math. Z. 166 (1979), 225-264. MR 0526466 (80g:05027)
91.: J.F. Sallee, A triangulation of the -cube, Discrete Math. 40 (1982), 81-86. MR 0676714 (84d:05065b)
92.: J.F. Sallee, A note on minimal triangulations of an -cube, Discrete Applied Math. 4 (1982), 211-215. MR 0675850 (84g:52019)
93.: J.F. Sallee, Middle-cut triangulations of the n-cube, SIAM J. Algbraic Discrete Methods 5 (1984), 407-419. MR 0752044 (86c:05054)
94.: K.W. Schmidt, Lower bounds for maximal -determinants, SIAM J. Appl. Math. 19 (1970), 440-441. MR 0265382 (42:292)
95.: T. Schmidt, Über die Zerlegung des -dimensionalen Raumes in gitterförmig angeordnete Würfeln, Schr. Math. Semin. U. Institut angew. Math. Univ. Berlin 1 (1933), 186-212.
96.: G.C. Shephard, Combinatorial properties of associated zonotopes, Canad. J. Math. 26 (1974), 302-321. MR 0362054 (50:14496)
97.: N.J.A. Sloane, Error-correcting codes and invariant theory: new applications of a nineteenth-century technique, Amer. Math. Monthly 84 (1977), 82-107. MR 0424398 (54:12361)
98.: W.D. Smith, A lower bound for the simplexity of the -cube via hyperbolic volumes, European J. Combin. 21 (2000), 131-137. MR 1737333 (2001c:52004)
99.: S.K. Stein, A symmetric star body that tiles but not as a lattice, Proc. Amer. Math. Soc. 36 (1972), 543-548. MR 0319058 (47:7604)
100.: S.K. Stein, Algebraic tiling, Amer. Math. Monthly 81 (1974), 445-462. MR 0340063 (49:4819)
101.: S.K. Stein and S. Szabó, Algebra and Tiling, Mathematical Association of America, 1994. MR 1311249 (95k:52035)
102.: S. Szabó, On mosaics consisting of multidimensional crosses, Acta Math. Acad. Sci. Hungar. 38 (1981), 191-203. MR 0634580 (83a:51021)
103.: S. Szabó, Multiple tilings by cubes with no shared faces, Aequationes Math. 25 (1982), 83-89. MR 0716380 (85c:52024)
104.: S. Szabó, A reduction of Keller's conjecture, Period. Math. Hungar. 17 (1986), 265-277. MR 0866636 (88j:52032)
105.: S. Szabó, Cube tilings as contributions of algebra to geometry, Beiträge Algebra Geom. 34 (1993), 63-75. MR 1239279 (94f:52039)
106.: W.P. Thurston, The Geometry and Topology of -manifolds, Lecture Notes from Princeton University, 1977.
107.: J.D. Vaaler, A geometric inequality with applications to linear forms, Pacific J. Math. 83 (1979), 543-553. MR 0557952 (81d:52007)
108.: J.H. van Lint, Introduction to Coding Theory, Springer-Verlag, New York, 1982. MR 0658134 (84e:94001)
109.: R.R. Varshamov, Estimate of the number of signals in error correcting codes, Dokl. Akad. Nauk SSSR 117 (1957), 739-741.
110.: J. Williamson, Determinants whose elements are 0 and 1, Amer. Math. Monthly 53 (1946), 427-434. MR 0017261 (8:128g)
111.: M. Wojtas, On Hadamard's inequality for the determinants of order non-divisible by 4, Colloq. Math. 12 (1964), 73-83. MR 0168574 (29:5834)
112.: M. Yamada, Some new series of Hadamard matrices, J. Austral. Math. Soc. 46 (1989), 371-383. MR 0987555 (90e:05022)
113.: C.H. Yang, Some designs for maximal -determinant of order $n\equiv 2$ (mod 4), Math. Comp. 20 (1966), 147-148; 22 (1968), 174-180; 23 (1969), 201-205. MR 0188093 (32:5534)
114.: C.H. Yang, A construction for maximal -matrix of order , Bull. Amer. Math. Soc. 72 (1966), 293. MR 0188239 (32:5678)
115.: G.M. Ziegler, Lectures on -Polytopes, Polytopes-Combinatorics and Computation, DMV Sem. 29 (2000), 1-41. MR 1785291 (2001e:52017)
116.: C. Zong, Strange Phenomena in Convex and Discrete Geometry, Springer-Verlag, New York, 1996. MR 1416567 (97m:52001)
117.: C. Zong, The Cube - A Window to Convex and Discrete Geometry, Cambridge University Press, in press.

Chuanming Zong
Affiliation: School of Mathematical Sciences, Peking University, Beijing 100871, People's Republic of China
Email: cmzong@math.pku.edu.cn

DOI: 10.1090/S0273-0979-05-01050-5
PII: S 0273-0979(05)01050-5
Received by editor(s): June 9, 2004
Posted: January 26, 2005
Additional Notes: This work was supported by the National Science Foundation of China, 973 Project and a special grant from Peking University.
Copyright of article: Copyright 2005, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-9485(e) ISSN 0273-0979(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues: 1891 - Present Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS