What is known about unit cubes

Zong, Chuanming

doi:10.1090/S0273-0979-05-01050-5

What is known about unit cubes
HTML articles powered by AMS MathViewer

by Chuanming Zong PDF

Bull. Amer. Math. Soc. 42 (2005), 181-211 Request permission

Abstract:

Unit cubes, from any point of view, are among the simplest and the most important objects in $n$-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.

References

Fernando Affentranger and Rolf Schneider, Random projections of regular simplices, Discrete Comput. Geom. 7 (1992), no. 3, 219–226. MR 1149653, DOI 10.1007/BF02187839
S. S. Agaian, Hadamard matrices and their applications, Lecture Notes in Mathematics, vol. 1168, Springer-Verlag, Berlin, 1985. MR 818740, DOI 10.1007/BFb0101073
Oswin Aichholzer, Extremal properties of $0/1$-polytopes of dimension 5, Polytopes—combinatorics and computation (Oberwolfach, 1997) DMV Sem., vol. 29, Birkhäuser, Basel, 2000, pp. 111–130. MR 1785295
Martin Aigner and Günter M. Ziegler, Proofs from The Book, 3rd ed., Springer-Verlag, Berlin, 2004. Including illustrations by Karl H. Hofmann. MR 2014872, DOI 10.1007/978-3-662-05412-3
Keith Ball, Cube slicing in $\textbf {R}^n$, Proc. Amer. Math. Soc. 97 (1986), no. 3, 465–473. MR 840631, DOI 10.1090/S0002-9939-1986-0840631-0
Keith Ball, Logarithmically concave functions and sections of convex sets in $\textbf {R}^n$, Studia Math. 88 (1988), no. 1, 69–84. MR 932007, DOI 10.4064/sm-88-1-69-84
Keith Ball, Volumes of sections of cubes and related problems, Geometric aspects of functional analysis (1987–88), Lecture Notes in Math., vol. 1376, Springer, Berlin, 1989, pp. 251–260. MR 1008726, DOI 10.1007/BFb0090058
Keith Ball, An elementary introduction to modern convex geometry, Flavors of geometry, Math. Sci. Res. Inst. Publ., vol. 31, Cambridge Univ. Press, Cambridge, 1997, pp. 1–58. MR 1491097, DOI 10.2977/prims/1195164788
I. Bárány and L. Lovász, Borsuk’s theorem and the number of facets of centrally symmetric polytopes, Acta Math. Acad. Sci. Hungar. 40 (1982), no. 3-4, 323–329. MR 686332, DOI 10.1007/BF01903592
Imre Bárány and Attila Pór, On $0$-$1$ polytopes with many facets, Adv. Math. 161 (2001), no. 2, 209–228. MR 1851645, DOI 10.1006/aima.2001.1991

Giorn. Mat. Battaglia

71

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), no. 1, 35–48. MR 1765232, DOI 10.1007/s004540010058
L. J. Billera, R. Cushman, and J. A. Sanders, The Stanley decomposition of the harmonic oscillator, Nederl. Akad. Wetensch. Indag. Math. 50 (1988), no. 4, 375–393. MR 976522
Louis J. Billera and A. Sarangarajan, All $0$-$1$ polytopes are traveling salesman polytopes, Combinatorica 16 (1996), no. 2, 175–188. MR 1401891, DOI 10.1007/BF01844844
C. Borell, Convex set functions in $d$-space, Period. Math. Hungar. 6 (1975), no. 2, 111–136. MR 404559, DOI 10.1007/BF02018814
Károly Böröczky Jr. and Martin Henk, Random projections of regular polytopes, Arch. Math. (Basel) 73 (1999), no. 6, 465–473. MR 1725183, DOI 10.1007/s000130050424
Herm Jan Brascamp and Elliott H. Lieb, Best constants in Young’s inequality, its converse, and its generalization to more than three functions, Advances in Math. 20 (1976), no. 2, 151–173. MR 412366, DOI 10.1016/0001-8708(76)90184-5
Joel Brenner and Larry Cummings, The Hadamard maximum determinant problem, Amer. Math. Monthly 79 (1972), 626–630. MR 301030, DOI 10.2307/2317092
Mark N. Broadie and Richard W. Cottle, A note on triangulating the $5$-cube, Discrete Math. 52 (1984), no. 1, 39–49. MR 765283, DOI 10.1016/0012-365X(84)90102-X
G. D. Chakerian and P. Filliman, The measures of the projections of a cube, Studia Sci. Math. Hungar. 21 (1986), no. 1-2, 103–110. MR 898848
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 178001, DOI 10.1090/S0002-9939-1965-0178001-X
K. Corrádi and S. Szabó, A combinatorial approach for Keller’s conjecture, Period. Math. Hungar. 21 (1990), no. 2, 95–100. MR 1070948, DOI 10.1007/BF01946848
Richard W. Cottle, Minimal triangulation of the $4$-cube, Discrete Math. 40 (1982), no. 1, 25–29. MR 676709, DOI 10.1016/0012-365X(82)90185-6
L. Dalla, D. G. Larman, P. Mani-Levitska, and C. Zong, The blocking numbers of convex bodies, Discrete Comput. Geom. 24 (2000), no. 2-3, 267–277. The Branko Grünbaum birthday issue. MR 1758049, DOI 10.1007/s004540010032
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 (German). MR 138040, DOI 10.1007/BF01193107
P. Delsarte, Bounds for unrestricted codes, by linear programming, Philips Res. Rep. 27 (1972), 272–289. MR 314545
P. Delsarte, An algebraic approach to the association schemes of coding theory, Philips Res. Rep. Suppl. 10 (1973), vi+97. MR 384310
Aryeh Dvoretzky, Some results on convex bodies and Banach spaces, Proc. Internat. Sympos. Linear Spaces (Jerusalem, 1960) Jerusalem Academic Press, Jerusalem; Pergamon, Oxford, 1961, pp. 123–160. MR 0139079
Aryeh Dvoretzky, Some near-sphericity results, Proc. Sympos. Pure Math., Vol. VII, Amer. Math. Soc., Providence, R.I., 1963, pp. 203–210. MR 0158308
M. E. Dyer, Z. Füredi, and C. McDiarmid, Volumes spanned by random points in the hypercube, Random Structures Algorithms 3 (1992), no. 1, 91–106. MR 1139489, DOI 10.1002/rsa.3240030107
Hartmut Ehlich, Determinantenabschätzungen für binäre Matrizen, Math. Z. 83 (1964), 123–132 (German). MR 160792, DOI 10.1007/BF01111249
Hartmut Ehlich, Determinantenabschätzung für binäre Matrizen mit $n\equiv 3\,\textrm {mod\,}4$, Math. Z. 84 (1964), 438–447 (German). MR 168573, DOI 10.1007/BF01109911
L. Fejes Tóth, Regular figures, A Pergamon Press Book, The Macmillan Company, New York, 1964. MR 0165423
Tamás Fleiner, Volker Kaibel, and Günter Rote, Upper bounds on the maximal number of facets of 0/1-polytopes, European J. Combin. 21 (2000), no. 1, 121–130. Combinatorics of polytopes. MR 1737332, DOI 10.1006/eujc.1999.0326

Monatsh. Math. Phys.

43

Bell System Tech. J.

31

N. A. Grigor′ev, Regular simplexes inscribed into a cube and Hadamard matrices, Trudy Mat. Inst. Steklov. 152 (1980), 87–88, 237 (Russian). Geometry of positive quadratic forms. MR 603815
P. Gritzmann, V. Klee, and D. Larman, Largest $j$-simplices in $n$-polytopes, Discrete Comput. Geom. 13 (1995), no. 3-4, 477–515. MR 1318791, DOI 10.1007/BF02574058
Peter Gruber, Zur Charakterisierung konvexer Körper. Über einen Satz von Rogers und Shephard. II, Math. Ann. 184 (1970), 79–105 (German). MR 256266, DOI 10.1007/BF01350311
W. Gruner, Einlagerung des regulären $n$-Simplex in den $n$-dimensionalen Würfel, Comment. Math. Helv. 12 (1939/40), 149–152 (German). MR 1205, DOI 10.1007/BF01620643
Uffe Haagerup and Hans J. Munkholm, Simplices of maximal volume in hyperbolic $n$-space, Acta Math. 147 (1981), no. 1-2, 1–11. MR 631085, DOI 10.1007/BF02392865

Bull. Sci. Math.

28

Elem. Math.

12

H. Hadwiger, Gitterperiodische Punktmengen und Isoperimetrie, Monatsh. Math. 76 (1972), 410–418 (German). MR 324550, DOI 10.1007/BF01297304
Mark Haiman, A simple and relatively efficient triangulation of the $n$-cube, Discrete Comput. Geom. 6 (1991), no. 4, 287–289. MR 1098809, DOI 10.1007/BF02574690
Georg Hajós, Über einfache und mehrfache Bedeckung des $n$-dimensionalen Raumes mit einem Würfelgitter, Math. Z. 47 (1941), 427–467 (German). MR 6425, DOI 10.1007/BF01180974
G. Hajós, Sur la factorisation des groupes abéliens, Časopis Pěst. Mat. Fys. 74 (1949), 157–162 (1950) (French, with Czech summary). MR 0045727

Combinatorial Theory

Douglas Hensley, Slicing the cube in $\textbf {R}^{n}$ and probability (bounds for the measure of a central cube slice in $\textbf {R}^{n}$ by probability methods), Proc. Amer. Math. Soc. 73 (1979), no. 1, 95–100. MR 512066, DOI 10.1090/S0002-9939-1979-0512066-8
Douglas Hensley, Slicing convex bodies—bounds for slice area in terms of the body’s covariance, Proc. Amer. Math. Soc. 79 (1980), no. 4, 619–625. MR 572315, DOI 10.1090/S0002-9939-1980-0572315-5
Matthew Hudelson, Victor Klee, and David Larman, Largest $j$-simplices in $d$-cubes: some relatives of the Hadamard maximum determinant problem, Proceedings of the Fourth Conference of the International Linear Algebra Society (Rotterdam, 1994), 1996, pp. 519–598. MR 1400454, DOI 10.1016/0024-3795(95)00541-2
Robert B. Hughes and Michael R. Anderson, A triangulation of the $6$-cube with $308$ simplices, Discrete Math. 117 (1993), no. 1-3, 253–256. MR 1226146, DOI 10.1016/0012-365X(93)90339-U
Robert B. Hughes, Minimum-cardinality triangulations of the $d$-cube for $d=5$ and $d=6$, Discrete Math. 118 (1993), no. 1-3, 75–118. MR 1230056, DOI 10.1016/0012-365X(93)90055-X
Robert B. Hughes, Lower bounds on cube simplexity, Discrete Math. 133 (1994), no. 1-3, 123–138. MR 1298968, DOI 10.1016/0012-365X(94)90020-5
Robert B. Hughes and Michael R. Anderson, Simplexity of the cube, Discrete Math. 158 (1996), no. 1-3, 99–150. MR 1411113, DOI 10.1016/0012-365X(95)00075-8
David B. Jaffe, Optimal binary linear codes of length $\leq 30$, Discrete Math. 223 (2000), no. 1-3, 135–155. MR 1782044, DOI 10.1016/S0012-365X(99)00135-1

Dissertation

Fritz John, Extremum problems with inequalities as subsidiary conditions, Studies and Essays Presented to R. Courant on his 60th Birthday, January 8, 1948, Interscience Publishers, Inc., New York, N. Y., 1948, pp. 187–204. MR 0030135
Jeff Kahn, János Komlós, and Endre Szemerédi, On the probability that a random $\pm 1$-matrix is singular, J. Amer. Math. Soc. 8 (1995), no. 1, 223–240. MR 1260107, DOI 10.1090/S0894-0347-1995-1260107-2
Marek Kanter, Unimodality and dominance for symmetric random vectors, Trans. Amer. Math. Soc. 229 (1977), 65–85. MR 445580, DOI 10.1090/S0002-9947-1977-0445580-7

J. reine angew. Math.

163

J. reine angew. Math.

177

Mihail Kolountzakis, Lattice tilings by cubes: whole, notched and extended, Electron. J. Combin. 5 (1998), Research Paper 14, 11. MR 1605065
U. H. Kortenkamp, J. Richter-Gebert, A. Sarangarajan, and G. M. Ziegler, Extremal properties of $0/1$-polytopes, Discrete Comput. Geom. 17 (1997), no. 4, 439–448. Dedicated to Jörg M. Wills. MR 1455692, DOI 10.1007/PL00009303
Gerhard Kowalewski, Einführung in die Determinantentheorie einschliesslich der Fredholmschen Determinanten, Walter de Gruyter & Co., Berlin, 1954 (German). 4te Aufl. MR 0064003
Jeffrey C. Lagarias and Peter W. Shor, Keller’s cube-tiling conjecture is false in high dimensions, Bull. Amer. Math. Soc. (N.S.) 27 (1992), no. 2, 279–283. MR 1155280, DOI 10.1090/S0273-0979-1992-00318-X
J. C. Lagarias and P. W. Shor, Cube-tilings of $\textbf {R}^n$ and nonlinear codes, Discrete Comput. Geom. 11 (1994), no. 4, 359–391. MR 1273224, DOI 10.1007/BF02574014
D. G. Larman and P. Mani, Almost ellipsoidal sections and projections of convex bodies, Math. Proc. Cambridge Philos. Soc. 77 (1975), 529–546. MR 377697, DOI 10.1017/S0305004100051355
Carl W. Lee, Triangulating the $d$-cube, Discrete geometry and convexity (New York, 1982) Ann. New York Acad. Sci., vol. 440, New York Acad. Sci., New York, 1985, pp. 205–211. MR 809208, DOI 10.1111/j.1749-6632.1985.tb14555.x
Carl W. Lee, Subdivisions and triangulations of polytopes, Handbook of discrete and computational geometry, CRC Press Ser. Discrete Math. Appl., CRC, Boca Raton, FL, 1997, pp. 271–290. MR 1730170
Kurt Leichtweiss, Über die affine Exzentrizität konvexer Körper, Arch. Math. 10 (1959), 187–199 (German). MR 107843, DOI 10.1007/BF01240785
Y. Lonke, On random sections of the cube, Discrete Comput. Geom. 23 (2000), no. 2, 157–169. MR 1739603, DOI 10.1007/PL00009493
John Mackey, A cube tiling of dimension eight with no facesharing, Discrete Comput. Geom. 28 (2002), no. 2, 275–279. MR 1920144, DOI 10.1007/s00454-002-2801-9
Patrick Scott Mara, Triangulations for the cube, J. Combinatorial Theory Ser. A 20 (1976), no. 2, 170–177. MR 406838, DOI 10.1016/0097-3165(76)90014-5
Robert J. McEliece, Eugene R. Rodemich, Howard Rumsey Jr., and Lloyd R. Welch, New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalities, IEEE Trans. Inform. Theory IT-23 (1977), no. 2, 157–166. MR 439403, DOI 10.1109/tit.1977.1055688
Peter McMullen, Volumes of projections of unit cubes, Bull. London Math. Soc. 16 (1984), no. 3, 278–280. MR 738519, DOI 10.1112/blms/16.3.278
A. I. Medyanik, A regular simplex inscribed in a cube, half-circulant Hadamard matrices, and Gaussian sums, Mat. Fiz. Anal. Geom. 8 (2001), no. 1, 58–81 (Russian, with English, Russian and Ukrainian summaries). MR 1846358

Geometrie der Zahlen

Diophantische Approximationen

M. G. Neubauer and A. J. Radcliffe, The maximum determinant of $\pm 1$ matrices, Linear Algebra Appl. 257 (1997), 289–306. MR 1441716, DOI 10.1016/S0024-3795(96)00147-4
Michael G. Neubauer, William Watkins, and Joel Zeitlin, Maximal $j$-simplices in the real $d$-dimensional unit cube, J. Combin. Theory Ser. A 80 (1997), no. 1, 1–12. MR 1472104, DOI 10.1006/jcta.1997.2789
David Orden and Francisco Santos, Asymptotically efficient triangulations of the $d$-cube, Discrete Comput. Geom. 30 (2003), no. 4, 509–528. MR 2013970, DOI 10.1007/s00454-003-2845-5
M. I. Ostrovskii, Minimal-volume shadows of cubes, J. Funct. Anal. 176 (2000), no. 2, 317–330. MR 1784418, DOI 10.1006/jfan.2000.3641

J. Math. Phys.

12

Oskar Perron, Über lückenlose Ausfüllung des $n$-dimensionalen Raumes durch kongruente Würfel, Math. Z. 46 (1940), 1–26 (German). MR 3041, DOI 10.1007/BF01181421
Oskar Perron, Modulartige lückenlose Ausfüllung des $R_n$ mit kongruenten Würfeln. I, Math. Ann. 117 (1940), 415–447 (German). MR 3042, DOI 10.1007/BF01450026
V. S. Pless, W. C. Huffman, and R. A. Brualdi (eds.), Handbook of coding theory. Vol. I, II, North-Holland, Amsterdam, 1998. MR 1667936
András Prékopa, On logarithmic concave measures and functions, Acta Sci. Math. (Szeged) 34 (1973), 335–343. MR 404557
L. Rédei, Die neue Theorie der endlichen abelschen Gruppen und Verallgemeinerung des Hauptsatzes von Hajós, Acta Math. Acad. Sci. Hungar. 16 (1965), 329–373 (German, with Russian summary). MR 186729, DOI 10.1007/BF01904843
Raphael M. Robinson, Multiple tilings of $n$-dimensional space by unit cubes, Math. Z. 166 (1979), no. 3, 225–264. MR 526466, DOI 10.1007/BF01214145
Richard W. Cottle, Minimal triangulation of the $4$-cube, Discrete Math. 40 (1982), no. 1, 25–29. MR 676709, DOI 10.1016/0012-365X(82)90185-6
John F. Sallee, A note on minimal triangulations of an $n$-cube, Discrete Appl. Math. 4 (1982), no. 3, 211–215. MR 675850, DOI 10.1016/0166-218X(82)90041-5
John F. Sallee, The middle-cut triangulations of the $n$-cube, SIAM J. Algebraic Discrete Methods 5 (1984), no. 3, 407–419. MR 752044, DOI 10.1137/0605039
K. W. Schmidt, Lower bounds for maximal $(0,\,1)$-determinants, SIAM J. Appl. Math. 19 (1970), 440–442. MR 265382, DOI 10.1137/0119042

Schr. Math. Semin. U. Institut angew. Math. Univ. Berlin

1

G. C. Shephard, Combinatorial properties of associated zonotopes, Canadian J. Math. 26 (1974), 302–321. MR 362054, DOI 10.4153/CJM-1974-032-5
N. J. A. Sloane, Error-correcting codes and invariant theory: new applications of a nineteenth-century technique, Amer. Math. Monthly 84 (1977), no. 2, 82–107. MR 424398, DOI 10.2307/2319929
Warren D. Smith, A lower bound for the simplexity of the $n$-cube via hyperbolic volumes, European J. Combin. 21 (2000), no. 1, 131–137. Combinatorics of polytopes. MR 1737333, DOI 10.1006/eujc.1999.0327
Sherman K. Stein, A symmetric star body that tiles but not as a lattice, Proc. Amer. Math. Soc. 36 (1972), 543–548. MR 319058, DOI 10.1090/S0002-9939-1972-0319058-6
S. K. Stein, Algebraic tiling, Amer. Math. Monthly 81 (1974), 445–462. MR 340063, DOI 10.2307/2318582
Sherman K. Stein and Sándor Szabó, Algebra and tiling, Carus Mathematical Monographs, vol. 25, Mathematical Association of America, Washington, DC, 1994. Homomorphisms in the service of geometry. MR 1311249
S. Szabó, On mosaics consisting of multidimensional crosses, Acta Math. Acad. Sci. Hungar. 38 (1981), no. 1-4, 191–203. MR 634580, DOI 10.1007/BF01917533
Sándor Szabó, Multiple tilings by cubes with no shared faces, Aequationes Math. 25 (1982), no. 1, 83–89. MR 716380, DOI 10.1007/BF02189600
S. Szabó, A reduction of Keller’s conjecture, Period. Math. Hungar. 17 (1986), no. 4, 265–277. MR 866636, DOI 10.1007/BF01848388
Sándor Szabó, Cube tilings as contributions of algebra to geometry, Beiträge Algebra Geom. 34 (1993), no. 1, 63–75. MR 1239279

The Geometry and Topology of $3$-manifolds

Jeffrey D. Vaaler, A geometric inequality with applications to linear forms, Pacific J. Math. 83 (1979), no. 2, 543–553. MR 557952
Jacobus Hendricus van Lint, Introduction to coding theory, Problemy Matematicheskogo Analiza [Problems in Mathematical Analysis], vol. 8, Springer-Verlag, New York-Berlin, 1982. MR 658134

Dokl. Akad. Nauk SSSR

117

John Williamson, Determinants whose elements are 0 and 1, Amer. Math. Monthly 53 (1946), 427–434. MR 17261, DOI 10.2307/2306240
M. Wojtas, On Hadamard’s inequality for the determinants of order non-divisible by $4$, Colloq. Math. 12 (1964), 73–83. MR 168574, DOI 10.4064/cm-12-1-73-83
Mieko Yamada, Some new series of Hadamard matrices, J. Austral. Math. Soc. Ser. A 46 (1989), no. 3, 371–383. MR 987555
C. H. Yang, Some designs for maximal $(+1,\,-1)$-determinant of order $n\equiv 2\,(\textrm {mod}\,4)$, Math. Comp. 20 (1966), 147–148. MR 188093, DOI 10.1090/S0025-5718-1966-0188093-9
C. H. Yang, A construction for maximal $(+1,\,-1)$-matrix of order $54$, Bull. Amer. Math. Soc. 72 (1966), 293. MR 188239, DOI 10.1090/S0002-9904-1966-11497-0
Günter M. Ziegler, Lectures on $0/1$-polytopes, Polytopes—combinatorics and computation (Oberwolfach, 1997) DMV Sem., vol. 29, Birkhäuser, Basel, 2000, pp. 1–41. MR 1785291
Chuanming Zong, Strange phenomena in convex and discrete geometry, Universitext, Springer-Verlag, New York, 1996. MR 1416567, DOI 10.1007/978-1-4613-8481-6

The Cube – A Window to Convex and Discrete Geometry