An integer parallelotope with small surface area. (English) Zbl 07740623
A convex polytope \(P\) in the Euclidean \(n\)-space \(\mathbb{R}^n\) is called an integer parallelotope is the family \(\{ x + P: x \in \mathbb{Z}^n \}\) is a tiling. Since the volume of every integer parallelotope is \(1\), the isoperimetric inequality implies that its surface area is at least approximately \(\sqrt{n}\). In this paper the authors prove that this estimate is asymptotically tight. More specifically, for every \(n \in \mathbb{N}\), they construct an integer parallelotope \(P_n\) whose surface area is of order \(n^{1/2+o(1)}\).
Reviewer: Zsolt Lángi (Budapest)
MSC:
| 52B12 | Special polytopes (linear programming, centrally symmetric, etc.) |
| 52A20 | Convex sets in \(n\) dimensions (including convex hypersurfaces) |
References:
| [1] | Alexandrov, A. D., Convex Polyhedra, Springer Monographs in Mathematics (2005), Springer-Verlag: Springer-Verlag Berlin, Translated from the 1950 Russian edition by N. S. Dairbekov, S. S. Kutateladze and A. B. Sossinsky, With comments and bibliography by V. A. Zalgaller and appendices by L. A. Shor and Yu. A. Volkov · Zbl 1067.52011 |
| [2] | Alon, Noga; Feige, Uriel, On the power of two, three and four probes, (Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (2009), SIAM: SIAM Philadelphia, PA), 346-354 · Zbl 1422.68040 |
| [3] | Alon, Noga; Klartag, Bo’az, Economical toric spines via Cheeger’s inequality, J. Topol. Anal., 1, 101-111 (2009) · Zbl 1185.05085 |
| [4] | Aste, Tomaso; Weaire, Denis, The Pursuit of Perfect Packing (2008), Taylor & Francis: Taylor & Francis New York · Zbl 1159.52019 |
| [5] | Bezdek, Károly, Sphere packings revisited, Eur. J. Comb., 27, 864-883 (2006) · Zbl 1091.52010 |
| [6] | Braverman, Mark; Minzer, Dor, Optimal tiling of the Euclidean space using permutation-symmetric bodies, (36th Computational Complexity Conference, LIPIcs. 36th Computational Complexity Conference, LIPIcs, Leibniz Int. Proc. Inform., vol. 200 (2021), Schloss Dagstuhl. Leibniz-Zent. Inform: Schloss Dagstuhl. Leibniz-Zent. Inform Wadern), Article 5 pp. · Zbl 07711587 |
| [7] | Choe, Jaigyoung, On the existence and regularity of fundamental domains with least boundary area, J. Differ. Geom., 29, 623-663 (1989) · Zbl 0643.53041 |
| [8] | Delaunay, B., Sur la partition régulière de l’espace à 4 dimensions. I, II, Bull. Acad. Sci. URSS, 2, 79-110 (1929), (French) · JFM 56.1120.02 |
| [9] | Dellamonica, D.; Haxell, P.; Łuczak, T.; Mubayi, D.; Nagle, B.; Person, Y.; Rödl, V.; Schacht, M.; Verstraëte, J., On even-degree subgraphs of linear hypergraphs, Comb. Probab. Comput., 21, 113-127 (2012) · Zbl 1241.05052 |
| [10] | Dolbilin, N. P., Properties of faces of parallelohedra, (Geometriya, Topologiya i Matematicheskaya Fizika. II. Geometriya, Topologiya i Matematicheskaya Fizika. II, Tr. Mat. Inst. Steklova, vol. 266 (2009)), 112-126 · Zbl 1185.52020 |
| [11] | Dolbilin, N. P., Parallelohedra: a retrospective and new results, Trans. Mosc. Math. Soc., 207-220 (2012) · Zbl 1271.52013 |
| [12] | Engel, Peter, Geometric Crystallography, Handbook of Convex Geometry, vol. A, B, 989-1041 (1993), North-Holland: North-Holland Amsterdam · Zbl 0804.51032 |
| [13] | Fedorov, E. S., Načala učeniya o figurah (1953), Izdat. Akad. Nauk SSSR: Izdat. Akad. Nauk SSSR Moscow |
| [14] | Feige, Uriel, Small linear dependencies for binary vectors of low weight, (Building Bridges. Building Bridges, Bolyai Soc. Math. Stud., vol. 19 (2008), Springer: Springer Berlin), 283-307 · Zbl 1157.05317 |
| [15] | Feige, Uriel; Han Kim, Jeong; Ofek, Eran, Witnesses for non-satisfiability of dense random 3CNF formulas, (47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings (2006), IEEE Computer Society), 497-508 |
| [16] | Feige, Uriel; Kindler, Guy; O’Donnell, Ryan, Understanding parallel repetition requires understanding foams, (22nd Annual IEEE Conference on Computational Complexity. 22nd Annual IEEE Conference on Computational Complexity, CCC 2007, 13-16 June 2007, San Diego, California, USA (2007), IEEE Computer Society), 179-192 |
| [17] | Fejes Tóth, László, Über das kürzeste Kurvennetz, das eine Kugeloberfläche in flächengleiche konvexe Teile zerlegt, Math. Naturwiss. Anz. Ungar. Akad. Wiss., 62, 349-354 (1943) · Zbl 0061.38310 |
| [18] | Gallager, R. G., Low-density parity-check codes, IRE Trans. Inf. Theory, 8, 21-28 (1962) · Zbl 0107.11802 |
| [19] | Giannopoulos, Apostolos; Koldobsky, Alexander; Valettas, Petros, Inequalities for the surface area of projections of convex bodies, Can. J. Math., 70, 804-823 (2018) · Zbl 1400.52003 |
| [20] | Golub, Gene H.; Van Loan, Charles F., Matrix Computations, Johns Hopkins Studies in the Mathematical Sciences (2013), Johns Hopkins University Press: Johns Hopkins University Press Baltimore, MD · Zbl 1268.65037 |
| [21] | Guruswami, Venkatesan; Kothari, Pravesh K.; Manohar, Peter, Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random, (STOC ’22—Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (2022), ACM: ACM New York), 678-689 · Zbl 07774370 |
| [22] | Hales, T. C., The honeycomb conjecture, Discrete Comput. Geom., 25, 1-22 (2001) · Zbl 1007.52008 |
| [23] | Hsieh, Jun-Ting; Kothari, Pravesh K.; Mohanty, Sidhanth, A simple and sharper proof of the hypergraph Moore bound (2022), Preprint, available at |
| [24] | Kelvin, Lord, On homogeneous division of space, Proc. R. Soc. Lond., 55, 1-16 (1894), (English) · JFM 25.0880.02 |
| [25] | Kindler, Guy; O’Donnell, Ryan; Rao, Anup; Wigderson, Avi, Spherical cubes and rounding in high dimensions, (49th Annual IEEE Symposium on Foundations of Computer Science. 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA (2008), IEEE Computer Society), 189-198 |
| [26] | Kindler, Guy; Rao, Anup; O’Donnell, Ryan; Wigderson, Avi, Spherical cubes: optimal foams from computational hardness amplification, Commun. ACM, 55, 90-97 (2012) |
| [27] | Klain, Daniel A.; Rota, Gian-Carlo, Introduction to Geometric Probability, Lezioni Lincee. [Lincei Lectures] (1997), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0896.60004 |
| [28] | Lángi, Zsolt, An isoperimetric problem for three-dimensional parallelohedra, Pac. J. Math., 316, 169-181 (2022) · Zbl 1490.52014 |
| [29] | Lefmann, Hanno; Pudlák, Pavel; Savický, Petr, On sparse parity check matrices, Des. Codes Cryptogr., 12, 107-130 (1997) · Zbl 0902.94018 |
| [30] | Minkowski, H., Allgemeine Lehrsätze über die convexen Polyeder, Nachr. Ges. Wiss. Gött., Math.-Phys. Kl., 1897, 198-219 (1897), (German) · JFM 28.0427.01 |
| [31] | Naor, Assaf, Extension, separation and isomorphic reverse isoperimetry (2021), Preprint, available at · Zbl 1486.46026 |
| [32] | Naor, Assaf; Verstraëte, Jacques, Parity check matrices and product representations of squares, Combinatorica, 28, 163-185 (2008) · Zbl 1164.05005 |
| [33] | Odlyzko, A. M., Asymptotic Enumeration Methods, Handbook of Combinatorics, vols. 1, 2, 1063-1229 (1995), Elsevier Sci. B. V.: Elsevier Sci. B. V. Amsterdam · Zbl 0845.05005 |
| [34] | Raz, Ran, A counterexample to strong parallel repetition, SIAM J. Comput., 40, 771-777 (2011) · Zbl 1234.68141 |
| [35] | Rogers, C. A., A note on coverings and packings, J. Lond. Math. Soc., 25, 327-331 (1950) · Zbl 0038.02902 |
| [36] | Shtogrin, M. I., Regular Dirichlet-Voronoĭ Partitions for the Second Triclinic Group, Trudy Mat. Inst. Steklov., vol. 1, 23 (1973), Izdat. “Nauka”: Izdat. “Nauka” Moscow |
| [37] | Venkov, B. A., On a class of Euclidean polyhedra, Vestn. Leningr. Univ., Ser. Mat. Fiz. Him., 9, 11-31 (1954) |
| [38] | Vershynin, Roman, An introduction with applications in data science, (High-Dimensional Probability. High-Dimensional Probability, Cambridge Series in Statistical and Probabilistic Mathematics, vol. 47 (2018), Cambridge University Press: Cambridge University Press Cambridge), With a foreword by Sara van de Geer · Zbl 1430.60005 |
| [39] | Weaire, D.; Phelan, R., A counter-example to Kelvin’s conjecture on minimal surfaces, Philos. Mag. Lett., 69, 107-110 (1994) · Zbl 0900.52003 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
