Abstract
The k-tiling problem for a convex polytope P is the problem of covering \( \mathbb {R}^d\) with translates of P using a discrete multiset \(\varLambda \) of translation vectors such that every point in \( \mathbb {R}^d\) is covered exactly k times, except possibly for the boundary of P and its translates. A classical result in the study of tiling problems is a theorem of McMullen [Mathematika 27(1):113–121, 1980] that a convex polytope P that 1-tiles \( \mathbb {R}^d\) with a discrete multiset \(\varLambda \) can, in fact, 1-tile \( \mathbb {R}^d\) with a lattice \(\mathcal {L}\). A generalization of McMullen’s theorem for k-tiling was conjectured by Gravin et al. [Combinatorica 32(6):629–649, 2012], which states that if P k-tiles \( \mathbb {R}^d\) with a discrete multiset \(\varLambda \), then P m-tiles \( \mathbb {R}^d\) with a lattice \(\mathcal {L}\) for some m. In this paper, we consider the case when P k-tiles \( \mathbb {R}^d\) with a discrete multiset \(\varLambda \) such that every element of \(\varLambda \) is contained in a quasi-periodic set \(\mathcal {Q}\) (i.e., a finite union of translated lattices). This is motivated by the result of Gravin et al. [Discrete Comput Geom 50(4):1033–1050, 2013] and Kolountzakis [Discrete Comput Geom 23(4):537–553, 2000], showing that for \(d \in \{2,3\}\), if a polytope P k-tiles \( \mathbb {R}^d\) with a discrete multiset \(\varLambda \), then P m-tiles \( \mathbb {R}^d\) with a quasi-periodic set \(\mathcal {Q}\) for some m. Here we show for all values of d that if a polytope P k-tiles \( \mathbb {R}^d\) with a discrete multiset \(\varLambda \) that is contained in a quasi-periodic set \(\mathcal {Q}\) that satisfies a mild hypothesis, then P m-tiles \( \mathbb {R}^d\) with a lattice \(\mathcal {L}\) for some m. This strengthens the results of Gravin, Kolountzakis, Robins, and Shiryaev, and is a step in the direction of proving the conjecture of Gravin et al. [Combinatorica 32(6):629–649, 2012].
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Alexandrov, A.D.: Convex polyhedra. Springer Monographs in Mathematics. Springer, Berlin (2005). 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
Bartle, R.G., Sherbert, D.R.: Introduction to Real Analysis, 2nd edn. Wiley, New York (1992)
Barvinok, A.: A Course in Convexity, Graduate Studies in Mathematics, vol. 54. American Mathematical Society, Providence, RI (2002). doi:10.1090/gsm/054
Beck, M., Robins, S.: Computing the Continuous Discretely. Undergraduate Texts in Mathematics. Springer, New York (2007)
Bolle, U.: On multiple tiles in \(E^2\). In: Böröczky, K., Fejes Tóth, G. (eds.) Intuitive geometry (Szeged, 1991), Colloq. Math. Soc. János Bolyai, vol. 63, pp. 39–43. North-Holland, Amsterdam (1994)
Gravin, N., Robins, S., Shiryaev, D.: Translational tilings by a polytope, with multiplicity. Combinatorica 32(6), 629–649 (2012). doi:10.1007/s00493-012-2860-3
Gravin, N., Kolountzakis, M.N., Robins, S., Shiryaev, D.: Structure results for multiple tilings in 3D. Discrete Comput. Geom. 50(4), 1033–1050 (2013). doi:10.1007/s00454-013-9548-3
Gruber, P.M.: Convex and discrete geometry, Grundlehren der Mathematischen Wissenschaften, vol. 336. Springer, Berlin (2007)
Kolountzakis, M.N.: On the structure of multiple translational tilings by polygonal regions. Discrete Comput. Geom. 23(4), 537–553 (2000). doi:10.1007/s004540010014
Kolountzakis, M.N., Matolcsi, M.: Tilings by translation. La Gaceta de la Real Sociedad Espanola 13, 725–746 (2010)
Kuipers, L., Niederreiter, H.: Uniform Distribution of Sequences, Pure and Applied Mathematics. Wiley-Interscience, New York (1974)
McMullen, P.: Convex bodies which tile space by translation. Mathematika 27(1), 113–121 (1980). doi:10.1112/S0025579300010007
Minkowski, H.: Allgemeine Lehrsätze über die convexen Polyeder. Nachrichten von der Gesellschaft der Wissenschaften zu Göttingen, Mathematisch-Physikalische Klasse 1897, 198–220 (1897)
Shiryaev, D.: Personal communication, Nanyang Technological University, Singapore (2014)
Stanley, R.P.: A zonotope associated with graphical degree sequences. DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 4, 555–570 (1991)
Venkov, B.A.: On a class of Euclidean polyhedra. Vestnik Leningrad. Univ. Ser. Mat. Fiz. Him. 9(2), 11–31 (1954)
Acknowledgments
The author would like to thank Sinai Robins for his advice and helpful discussions during the preparation of this paper and for introducing the author to this topic. The author would like to thank the anonymous reviewers for their valuable comments and suggestions to improve the quality of the paper. Lastly, the author would like to thank Henk Hollmann and Thomas Gavin for proofreading this paper.
Author information
Authors and Affiliations
Corresponding author
Additional information
Editor in Charge: János Pach
Rights and permissions
About this article
Cite this article
Chan, S.H. Quasi-periodic Tiling with Multiplicity: A Lattice Enumeration Approach. Discrete Comput Geom 54, 647–662 (2015). https://doi.org/10.1007/s00454-015-9713-y
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-015-9713-y