On the distribution of runners on a circle

Abstract

Consider $n$ runners running on a circular track of unit length with constant speeds such that $k$ of the speeds are distinct. We show that, at some time, there will exist a sector $S$ which contains at least $|S|n+\Omega (\sqrt{k})$ runners. The result can be generalized as follows. Let $f(x,y)$ be a complex bivariate polynomial whose Newton polytope has $k$ vertices. Then there exists $a\in \mathbb{C}\setminus \{0\}$ and a complex sector $S=\{r{e}^{ı\theta }:r>0,\alpha \le \theta \le \beta \}$ such that the univariate polynomial $f(x,a)$ contains at least $\frac{\beta -\alpha }{2\pi }n+\Omega (\sqrt{k})$ non-zero roots in $S$ (where $n$ is the total number of such roots and $0\le (\beta -\alpha )\le 2\pi$). This shows that the Real $\tau$-Conjecture of Koiran implies the conjecture on Newton polytopes of Koiran et al.