Empty simplices of large width

Doolittle, Joseph ; Katthän, Lukas  ; Nill, Benjamin  ; Santos, Francisco 

Forum of Mathematics, Sigma, Tome 13 (2025) no. 1, p. e21

Résumé

An empty simplex is a lattice simplex in which vertices are the only lattice points. We show two constructions leading to the first known empty simplices of width larger than their dimension: ◦ We introduce cyclotomic simplices and exhaustively compute all the cyclotomic simplices of dimension $10$ and volume up to $2^{31}$. Among them, we find five empty ones of width $11$ and none of larger width.◦ Using circulant matrices of a very specific form, we construct empty simplices of arbitrary dimension d and width growing asymptotically as $d/\operatorname {\mathrm {arcsinh}}(1) \sim 1.1346\,d$.

Détail

DOI : 10.1017/fms.2024.131

Bibliographie

[1] Averkov, G., Codenotti, G., Macchia, A. and Santos, F., ‘A local maximizer for lattice width of 3-dimensional hollow bodies’, Discrete Applied Math. 298 (2021), 129–142. DOI: 10.1016/j.dam.2021.04.009 Google Scholar | DOI

[2] Barile, M., Bernardi, D., Borisov, A. and Kantor, J.-M., ‘On empty lattice simplices in dimension 4’, Proc. Amer. Math. Soc. 139(12) (2011), 4247–4253. Google Scholar | DOI

[3] Banaszczyk, W., ‘Inequalities for convex bodies and polar reciprocal lattices in n II: Application of K-convexity’, Discrete Comput. Geom. 16 (1996), 305–311. Google Scholar | DOI

[4] Banaszczyk, W., Litvak, A. E., Pajor, A. and Szarek, S. J., ‘The flatness theorem for nonsymmetric convex bodies via the local theory of Banach spaces’, Math. Oper. Res. 24(3) (1999), 728–750. Google Scholar | DOI

[5] Codenotti, G. and Santos, F., ‘Hollow polytopes of large width’, Proc. Amer. Math. Soc. 148(2) (2020), 835–850. DOI: 10.1090/proc/14721 Google Scholar | DOI

[6] Cox, D.A., Little, J. B. and Schenck, H. K., Toric Varieties (American Mathematical Society, Providence, RI, 2011). Google Scholar | DOI

[7] Flajolet, P. and Sedgewick, R., Analytic Combinatorics (Cambridge University Press, Cambridge, 2009). Google Scholar | DOI

[8] Graham, R. L., Knuth, D. E. and Patashnik, O., Mathematics, Concrete. A Foundation for Computer Science, second edn. (Addison-Wesley Publishing Co., Reading, MA, 1994). Google Scholar

[9] Haase, C. and Ziegler, G. M., ‘On the maximal width of empty lattice simplices’, Eur. J. Comb. 21 (2000), 111–119. Google Scholar | DOI

[10] Herr, K., Rehn, T. and Schürmann, A., ‘On lattice-free orbit polytopes’, Discrete Comput. Geom. 53 (2015), 144–172. Google Scholar | DOI

[11] Hoggatt, V. E. and Bicknell, M., ‘Roots of Fibonacci polynomials’, Fibonacci Q. 11(3) (1973), 271–274. https://www.fq.math.ca/Scanned/11-3/hoggatt1.pdf Google Scholar | DOI

[12] Hoggatt, V. E. and Long, C. T., ‘Divisibility properties of generalized Fibonacci polynomials’, Fibonacci Q. 12(2) (1974), 113–120. https://www.fq.math.ca/Scanned/12-2/hoggatt2.pdf Google Scholar | DOI

[13] Hurkens, C. A. J., ‘Blowing up convex sets in the plane’. Linear Alg. Appl. 134 (1990), 121–128. Google Scholar | DOI

[14] Iglesias-Valiño, Ó. and Santos, F., ‘Classification of empty lattice 4-simplices of width larger than two’, Trans. Amer. Math. Soc. 371(9) (2019), 6605–6625. DOI: 10.1090/tran/7531 Google Scholar | DOI

[15] Iglesias-Valiño, Ó. and Santos, F., ‘The complete classification of empty lattice 4-simplices’, Rev. Mat. Iberoam. 37(6) (2021), 2399–2432. DOI: 10.4171/rmi/1268 Google Scholar | DOI

[16] Kannan, R. and Lovász, L., ‘Covering minima and lattice-point-free convex bodies’, Ann. Math. (2) 128(3) (1988), 577–602. Google Scholar | DOI

[17] Kantor, J.-M., ‘On the width of lattice-free simplices’, Compos. Math. 118 (1999), 235–241. Google Scholar | DOI

[18] Khinchine, A., ‘A quantitative formulation of Kronecker’s theory of approximation’, Izv. Acad. Nauk SSSR, Ser. Mat. 12 (1948), 113–122 (in Russian). Google Scholar

[19] Ladisch, F. and Schürmann, A., ‘Equivalence of lattice orbit polytopes’, SIAM J. Appl. Algebra Geom. 2 (2018), 259–280. Google Scholar | DOI

[20] Matsuki, K., Introduction to the Mori Program (Springer, New York, 2002). Google Scholar | DOI

[21] Mayrhofer, L., Schade, J. and Weltge, S., ‘Lattice-free simplices with lattice width 2d − o(d)’, in Integer Programming and Combinatorial Optimization. IPCO 2022 (K. Aardal, L. Sanità, eds.) (Lecture Notesin Computer Science) vol. 13265 (Springer, Cham, 2022), 375–386. DOI: 10.1007/978-3-031-06901-7 28 Google Scholar | DOI

[22] Rehn, T., ‘Exploring core points for fun and profit: a study of lattice-free orbit polytopes’, PhD thesis, Universität Rostock, 2013. http://rosdok.uni-rostock.de/file/rosdok disshab 0000001151/rosdok derivate0000005285/Dissertation Rehn 2014.pdf Google Scholar

[23] Rudelson, M., ‘Distances between nonsymmetric convex bodies and the MM∗-estimate’, Positivity 4(2) (2000), 161–178. Google Scholar | DOI

[24] Sebő, A., ‘An introduction to empty lattice simplices’, in Integer Programming and Combinatorial Optimization (Graz, 1999) (Lecture Notes in Comput. Sci.) vol. 1610 (Springer, Berlin, 1999), 400–414. Google Scholar | DOI

[25] White, G. K., ‘Lattice tetrahedra’, Canad. J. Math. 16 (1964), 389–396. Google Scholar | DOI