17
$\begingroup$

Given $n$, what is the smallest value $\delta_n$ satisfying the following:

For any group of $n$ runners with constant but distinct speeds, starting from the same point and running clockwise along the unit circle, there exists a moment, at which the length of each of $n$ empty circle segments between two consecutive runners does not exceed $\delta_n$.

More formally, for $n \in \mathbb{N}$, $M=\{m_1,\dots,m_n\} \subset \mathbb{N}$, and $t \in [0,1]$, we sort the fractional parts of the values $tm_i$ in ascending order: $0 \le \{tm_{i_1}\} \le\dots\le \{tm_{i_n}\} \le 1$. Then we consider the longest empty segment between two consecutive 'runners': $$ \text{LongestArc}(M,t) := \max\Big\{ \{tm_{i_2}\}-\{tm_{i_1}\}, \dots, \{tm_{i_n}\}-\{tm_{i_{n-1}}\}, 1+\{tm_{i_1}\}-\{tm_{i_n}\} \Big\}.$$ Finally, we put $$ \delta_n := \mathop{\smash{\mathrm{sup}}}_{|M|=n} \inf_{t \in [0,1]} \text{LongestArc}(M,t).$$

Has the problem of finding these values (or, perhaps, an equivalent one) been studied earlier? I have looked through some papers related to the Lonely Runner Conjecture (including this one) but found nothing.

It is clear that $\delta_2=\frac12$. With a little more effort goes $\delta_3=\frac25$, one of the 'extremal' sets here is $M=\{0,1,3\}$. One may check that $\delta_4 \ge \frac13$ by taking $M=\{0,1,2,4\}$. I suspect this bound to be tight. Maybe someone sees a counterexample or a short argument, why is that so?

For large $n$, I believe I can show that $\delta_n \ge \frac{\log n -O(\log \log n)}{n}$. However, I don't have any (decent) upper bound on $\delta_n$ apart from the fact that $\delta_n=o(1)$ as $n \to \infty$.

Finally, I found that the 'dual' problem concerning the values $$ \epsilon_n := \inf_{|M|=n} \mathop{\smash{\mathrm{sup}}}_{t \in [0,1]} \text{LongestArc}(M,t)$$ has earlier been considered on MathOverflow (not in the literature, though). One may also state two more 'dual' extremal problems related to the shortest arc (instead of the longest one), but I haven't found anything published about them as well.

I would appreciate any related reference!

$\endgroup$
7
  • 1
    $\begingroup$ In case anyone wonders how to get the lower bound $\delta_n \ge \frac{\log n-O(\log \log n)}{n}$. Long story sort, one may take a 'random' $n$-element subset of $[n\log n]$ to do so. $\endgroup$ May 24, 2022 at 14:33
  • $\begingroup$ As for the upper bound $\delta_n=o(1)$, there must be a trivial explanation for this, but I have only a rather technical one. Note that if the fractional parts $\{tm_{i}\}$ are 'almost independently' distributed on the circle, then a 'random' $t$ provides a good upper bound for these runners. Finally, observe that you can always pick such a group of 'independent' runners from a 'sufficiently large' set $M$ $\endgroup$ May 24, 2022 at 14:55
  • $\begingroup$ You seem to assume that their velocities are rational, is it clear that it is sufficient to consider this case? $\endgroup$ May 24, 2022 at 15:05
  • $\begingroup$ The trivial upper bound is $\delta_n=O(n^{-1/2})$ but it is so far from your $\frac{\log n}{n}$ that I'd rather wait for somebody with more knowledge in these matters to comment... $\endgroup$
    – fedja
    May 24, 2022 at 16:08
  • 2
    $\begingroup$ @fedja I think it's worth posting! I tried to prove a bound and didn't even get that far... $\endgroup$
    – Will Sawin
    May 24, 2022 at 20:57

2 Answers 2

7
$\begingroup$

I think the answer to the question as posed is "yes", see Konyagin-Ruzsa-Schlag (2011)

https://gauss.math.yale.edu/~ws442/papers/DILATES.pdf

It looks like nothing beyond the bounds discovered in the comments and Fedja's answer above is known.

$\endgroup$
13
$\begingroup$

OK, since Will thinks it is worth posting, here it goes. This is not an answer, just setting up the triviality level. As usual, the circle will be identified with $\mathbb R/\mathbb Z$.

Let $\psi$ be the piecewise linear $1$ periodic function that is $0$ at $0$, raises to $1$ at $\delta/2$, drops down to $0$ at $\delta$ and then stays $0$ throughout the rest of the period (the well-known "triangle hump", just shifted forward from its usual center). We have the Fourier expansion $$ \psi(x)=\frac{\delta}2+\sum_{k\ne 0}c_ke^{2\pi ikx} $$ with $\sum_{k\ne 0}|c_k|=1-\frac\delta 2<1$.

We want to find $t$ such that for every runner moving at the speed $v_0\in V$ ($V$ is the set of all speeds), we have $$ \Psi_{v_0}(t)=\sum_{v\in V} \psi(vt-v_0t)\ne 0\,. $$ This will mean that there is at least one runner in the interval of length $\delta$ ahead of every runner, so the maximal gap is at most $\delta$.

However $$ \Psi_{v_0}(t)=\frac{\delta n}2+\sum_{k\ne 0}c_ke^{-2\pi i kv_0t}F(kt) \\ \ge \frac{\delta n}2-\sum_{k\ne 0}|c_k||F(kt)|\ge \frac{\delta n}2-\sqrt{\sum_{k\ne 0}|c_k||F(kt)|^2} $$ where $F(t)=\sum_{v\in V}e^{2\pi i vt}$.

Note now that for each $k\ne 0$, the mean value of $|F(kt)|^2$ (in the sense of almost-periodic functions, i.e., $\lim_{T\to\infty}\int_{-T}^T\dots\,dt$) is $n$, so the mean value of the sum under the square root is $<n$. Thus, we are fine if $\frac{\delta n}2-\sqrt n\ge 0$, i.e., if $\delta\ge \frac 2{\sqrt n}$.

Edit: I guess that in the view of mathworker21's comments, I should emphasize a bit where exactly the real difficulty is. To this end I'll recast the proof into another language avoiding the Fourier transform altogether though it is actually the same proof.

Let $\delta>0$. Consider the functions $\varphi_v(x,t)$ that are 1-periodic in $x$ and given by $\chi_{[0,\delta]}(vt-x)-\delta$ on the period and $\Phi(x,t)=\sum_v\varphi_v(x,t)$. If for some $t$ we have a $2\delta$-gap, then $$ \int_0^1 |\Phi(x,t)|^2\,dx\ge \delta(-n\delta)^2=n^2\delta^3\,. $$ Thus, if we have that gap for all $t$, we must have $$ \operatorname{Mean}_t\int_0^1 |\Phi(x,t)|^2\,dx\ge n^2\delta^3 $$ but we have the joint in $x,t$ ortogonality of $\varphi_v$, so the left hand side is just $n\delta(1-\delta)$.

The issue is that when $\delta<n^{-1/2}$, the $n\delta$ bump doesn't rise in the $L^2$ integral sense above standard "pure noise level" $\sqrt{n\delta}$ on $[0,1]\ni x$. Trying to use higher $L^p$ norms is problematic for two reasons. First, the integrals of long products now depend on linear dependences between $v$'s with integer coefficients and second, if all speeds are, say, integers from $1$ to $n$, the initial overcrowding interval of length $\frac \delta n$ will already contributes $n^{p-1}\delta$ to that norm, which is way too much. We really need to get rid of (or, at least, suppress) the positive part of $\Phi$ before averaging and that is not easy with polynomial functions, so one needs some new trick or even some new idea to get something non-trivial (which is more or less the definition of "non-trivial").

$\endgroup$
6
  • $\begingroup$ Nice! I was trying to choose $t$ such that $\sum_{v_1, v_2\in V} f( v_1 t -v_2 t)$ is at least its mean value for a suitable test function $f$, and then optimize that sum subject to the $v_i t$ leaving a gap of size $\delta$. The trick where you fix one of the two variables and control the sum by Cauchy-Schwarz is what I was missing. Though perhaps there is a way to translate this idea back into the language I was using, since the sum at the end $\sum_{k\neq 0} |c_k| |F(kt)|^2$ is of the form I was thinking. $\endgroup$
    – Will Sawin
    May 25, 2022 at 1:28
  • 1
    $\begingroup$ @WillSawin Yeah, but unfortunately this is way too rough and I see no way to upgrade the argument so that it would yield something closer to the expected $1/n$ (times some logarithmic factor). It is interesting that one can maintain one fixed interval of length $1/\sqrt n$ free of runners for the $1/\sqrt n$ portion of the time, so if you follow that route, the trivial union bound won't work. Well, I would be as interested as you to see some nontrivial upper estimates now :-) $\endgroup$
    – fedja
    May 25, 2022 at 1:41
  • $\begingroup$ @WillSawin Sorry, but I'm confused what you guys are talking about. Fedja's solution never used that $v_0 \in V$. Indeed, his solution shows the desired result directly: there's some $t$ so that for all $x \in \mathbb{T}$, there's some $vt \in (x,x+\delta)$. Also, Fedja, at the end you can just integrate $t$ from $0$ to $1$, right? $\endgroup$ May 27, 2022 at 2:45
  • $\begingroup$ @mathworker21 You're right that the assumption $v_0 \in V$ is not necessary, but I don't think that makes what we said strictly wrong. There doesn't seem to be any advantage to taking $v_0 \notin V$. One can of course integrate from $0$ to $1$ if the speeds are all integers, but it's cleaner to avoid the reduction to that case if you can. $\endgroup$
    – Will Sawin
    May 27, 2022 at 10:48
  • $\begingroup$ @mathworker21 I edited to explain better "what we are talking about" :-). Feel free to ask questions if something is unclear and thanks for thinking of this problem: it looks rather fascinating. $\endgroup$
    – fedja
    May 27, 2022 at 13:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.