Linearly-exponential checking is enough for the Lonely Runner Conjecture and some of its variants
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915529434857472 |
|---|---|
| author | Malikiosis, Romanos Diogenes Santos, Francisco Schymura, Matthias |
| author_facet | Malikiosis, Romanos Diogenes Santos, Francisco Schymura, Matthias |
| contents | 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 \emph{shifted} Lonely Runner Conjecture (sLRC), except in this case our result depends on the solution of a question, that we dub the \emph{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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_06903 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Linearly-exponential checking is enough for the Lonely Runner Conjecture and some of its variants Malikiosis, Romanos Diogenes Santos, Francisco Schymura, Matthias Combinatorics Number Theory Primary 11H31, Secondary: 52B55, 11J25, 52C07, 52C17 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 \emph{shifted} Lonely Runner Conjecture (sLRC), except in this case our result depends on the solution of a question, that we dub the \emph{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$. |
| title | Linearly-exponential checking is enough for the Lonely Runner Conjecture and some of its variants |
| topic | Combinatorics Number Theory Primary 11H31, Secondary: 52B55, 11J25, 52C07, 52C17 |
| url | https://arxiv.org/abs/2411.06903 |