Linearly exponential checking is enough for the lonely runner conjecture and some of its variants

Malikiosis, Romanos Diogenes  ; Santos, Francisco  ; Schymura, Matthias 

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

Résumé

Tao (2018) showed that in order to prove the Lonely Runner Conjecture (LRC) up to $n+1$ runners it suffices to consider positive integer velocities in the order of $n^{O(n^2)}$. Using the zonotopal reinterpretation of the conjecture due to the first and third authors (2017) we here drastically improve this result, showing that velocities up to $\binom {n+1}{2}^{n-1} \le n^{2n}$ are enough.We prove the same finite-checking result, with the same bound, for the more general shifted Lonely Runner Conjecture (sLRC), except in this case our result depends on the solution of a question, that we dub the Lonely Vector Problem (LVP), about sumsets of n rational vectors in dimension two. We also prove the same finite-checking bound for a further generalization of sLRC that concerns cosimple zonotopes with n generators, a class of lattice zonotopes that we introduce.In the last sections we look at dimensions two and three. In dimension two we prove our generalized version of sLRC (hence we reprove the sLRC for four runners), and in dimension three we show that to prove sLRC for five runners it suffices to look at velocities adding up to $195$.

Détail

DOI : 10.1017/fms.2025.10107

Bibliographie

[1] Alcántara, D., Criado, F. and Santos, F., ‘Covering radii of 3-zonotopes and the shifted lonely runner conjecture’, 2025, . Google Scholar | arXiv

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

[3] Averkov, G. and Wagner, C., ‘Inequalities for the lattice width of lattice-free convex sets in the plane’, Beitr. Algebra Geom. 53(1) (2012), 1–23.10.1007/s13366-011-0028-8 Google Scholar | DOI

[4] Barajas, J. and Serra, O., ‘The lonely runner with seven runners’, Electron. J. Combin. 15(48) (2008), 18 pp. (electronic).10.37236/772 Google Scholar | DOI

[5] Beck, M., Hoşten, S. and Schymura, M., ‘Lonely Runner Polyhedra’, Integers 19 (2019), #A29, 13 pp. Google Scholar

[6] Beck, M. and Robins, S., Computing the Continuous Discretely, 2nd ed., Undergraduate Texts in Mathematics (Springer, New York, 2015), Integer-point enumeration in polyhedra, with illustrations by D. Austin.10.1007/978-1-4939-2969-6 Google Scholar | DOI

[7] Betke, U., Henk, M. and Wills, J. M., ‘Successive-minima-type inequalities’, Discrete Comput. Geom. 9(2) (1993), 165–175.10.1007/BF02189316 Google Scholar | DOI

[8] Betke, U. and Wills, J. M., ‘Untere Schranken für zwei diophantische Approximations-Funktionen’, Monatsh. Math. 76 (1972), 214–217 (German).10.1007/BF01322924 Google Scholar | DOI

[9] Bienia, W., Goddyn, L., Gvozdjak, P., Sebő, A. and Tarsi, M., ‘Flows, view obstructions, and the lonely runner’, J. Combin. Theory Ser. B 72(1) (1998), 1–9.10.1006/jctb.1997.1770 Google Scholar | DOI

[10] Bohman, T., Holzman, R. and Kleitman, D., ‘Six lonely runners’, Electron. J. Combin. 8(2) (2001), #R3, 49 pp. (electronic).10.37236/1602 Google Scholar | DOI

[11] Codenotti, G., Santos, F. and Schymura, M., ‘The covering radius and a discrete surface area for non-hollow simplices’, Discrete Comput. Geom. 67 (2022), 65–111.10.1007/s00454-021-00330-3 Google Scholar | DOI

[12] Cslovjecsek, J., Malikiosis, R. D., Naszódi, M. and Schymura, M., ‘Computing the covering radius of a polytope with an application to lonely runners’, Combinatorica 42(4) (2022), 463–490.10.1007/s00493-020-4633-8 Google Scholar | DOI

[13] Cusick, T. W., ‘View-obstruction problems’, Aequationes Math. 9 (1973), 165–170.10.1007/BF01832623 Google Scholar | DOI

[14] De Loera, J. A., Rambau, J. and Santos, F., Triangulations, Algorithms and Computation in Mathematics, vol. 25 (Springer-Verlag, Berlin, 2010), Structures for algorithms and applications.10.1007/978-3-642-12971-1 Google Scholar | DOI

[15] Fan, H. T. and Sun, A., ‘Amending the lonely runner spectrum conjecture’, 2023, . Google Scholar | arXiv

[16] Giri, V. and Kravitz, N., ‘The structure of Lonely Runner spectra’, March 2025, . Google Scholar | arXiv

[17] Gruber, P. M., Convex and Discrete Geometry, Grundlehren der Mathematischen Wissenschaften, vol. 336 (Springer-Verlag, Berlin, 2007). Google Scholar

[18] Gruber, P. M. and Lekkerkerker, C. G., Geometry of Numbers, 2nd ed., North-Holland Math. Libr., vol. 37 (Elsevier, Amsterdam, 1987).10.1016/S0924-6509(08)70411-2 Google Scholar | DOI

[19] Henze, M. and Malikiosis, R. D., ‘On the covering radius of lattice zonotopes and its relation to view-obstructions and the lonely runner conjecture’, Aequationes Math. 91(2) (2017), 331–352.10.1007/s00010-016-0458-3 Google Scholar | DOI

[20] 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.10.1090/tran/7531 Google Scholar | DOI

[21] Miller, E. and Sturmfels, B., Combinatorial Commutative Algebra, Graduate Texts in Mathematics, vol. 227 (Springer-Verlag, New York, 2005). Google Scholar

[22] Perarnau, G. and Serra, O., ‘The Lonely Runner Conjecture turns 60’, Computer Science Review 58 (2025), 100798.10.1016/j.cosrev.2025.100798 Google Scholar | DOI

[23] Schoenberg, I. J., ‘Extremum problems for the motions of a billiard ball. II. The norm’, Indag. Math. 38(3) (1976), 263–279, Nederl. Akad. Wetensch. Proc. Ser. A .10.1016/1385-7258(76)90053-6 Google Scholar | DOI

[24] Shephard, G. C., ‘Combinatorial properties of associated zonotopes’, Can. J. Math. 26 (1974), 302–321.10.4153/CJM-1974-032-5 Google Scholar | DOI

[25] Tao, T., ‘Some remarks on the lonely runner conjecture’, Contrib. Discrete Math. 13(2) (2018), 1–31. Google Scholar

[26] Wills, J. M., ‘Zur simultanen homogenen diophantischen Approximation. I’, Monatsh. Math. 72 (1968), 254–263 (German).10.1007/BF01362551 Google Scholar | DOI