On the Distribution of Runners on a Circle

Resources

• [https://arxiv.org/abs/1906.02511](Pavel Hrubes - On the distribution of Runners on a circle)
• We slightly modify the notation to make it clearer in our eyes.

Main Theorem

• $n$ runners on a circle of unit length having exactly $k$ distinct speeds.
• Then there exists a sector $S$ such that $S$ contains at least $\lvert S\rvert n + c\sqrt{k}$ runners where $c>0$ is some fixed constant.
• Real tau conjecture implies the conjecture on newton polynomials.

Main Definitions

• We will identify the interval $[0,1)$ with a circle.
• Let $S_{\alpha,\gamma} = \lbrace x \in [0,1] \mid x-a \mod 1 \leq \gamma \rbrace$, i.e, the sector that starts at $\alpha$ and continues for $\gamma$.
• $\chi_S(x) = \begin{cases} 1& x\mod 1 \in S\ 0& \text{otherwise}.\end{cases}$
• $#\chi_S=\sum_{i=1}^n \chi_S(x_i)$.

Discrepancy

• Discrepancy $D(r_1,\dots,r_n)= \sup_{0\leq a\leq b\leq 1} \frac{1}{n} \lvert (\lvert i\mid r_i\in [a,b]\rvert) -n(b-a)\rvert$.
• Bias = $nD(r_1,\dots,r_n)$.
• Notice that all these things will be applied $\mod 1$ in our case.
• What is discrepancy?
  • It measures roughly how equi distributed across the circle.
  • I.e., equidistributed tends to 0 while a heap tends to 1.
• Theorem 1 in discrepancy statement:
  • Let $s_1,\dots,s_n\in [0,1)$ and $v_1,\dots, v_n\in \mathbb{R}$ with $k$ distinct $v_i$s. Then there exists a $t$ such that $B(s_1+tv_1,\dots, s_n + tv_n) \geq \sqrt{k/12}$.
• How the theorems are identical is clear, as the $a,b$ in the discrepancy gives us our sector.

Main Proof

Lemma 4

• $\int_{t=0}^1 \int_{\alpha=0}^1 \chi_{S_{\alpha,\gamma}}(s_1 + t v_1) d\alpha dt = \gamma$
• $\int_{t=0}^1 \int_{\alpha=0}^1 \chi_{S_{\alpha,\gamma}}(s_1 + t v_1)\chi_{S_{\alpha,\gamma}}(s_ + t v_2) d\alpha dt = \gamma^2$
• Proof:
  • $\int_{\alpha=0}^1 \chi_{S_{\alpha,\gamma}}(s_1 + t v_1) d\alpha = \int_{t=0}^1 \chi_{S_{\alpha,\gamma}}(s_1 + t v_1)dt = \gamma$
    • Because $\chi$ is a step function that is one for $\gamma$ steps. Hence, if we "rotate" our sector or "rotate" our point, we will land for a $\gamma$ interval in it.
    • As $\chi_{S_{\alpha,\gamma}}(x+z) = \chi_{S_{\alpha-z,\gamma}}$ we can rewrite the statement
    • $\int_{\alpha=0}^1 \chi_{S_{\alpha-tv_1,\gamma}}(s_1)\chi_{S_{\alpha-tv_2,\gamma}}(s_2 + t v_2) d\alpha$
    • By shifting the range we get $\int_{\alpha=-tv_1}^{tv_1} \chi_{S_{\alpha,\gamma}}(s_1)\chi_{S_{\alpha+(v_1-v_2)t,\gamma}}(s_2) d\alpha$
    • As $\chi_{S_{\alpha,\gamma}}$ is 1 periodic in the first argument, we can shift the borders without shifting the indices, giving us:
    • $\int_{t=1}^1 \int_{\alpha=0}^{1} \chi_{S_{\alpha,\gamma}}(s_1)\chi_{S_{\alpha+(v_1-v_2)t,\gamma}}(s_2) d\alpha dt$
    • Now we can change the order of integration and notice that the first part is independent of $t$:
    • $\int_{t=1}^1 \chi_{S_{\alpha,\gamma}}(s_1) \int_{\alpha=0}^{1} \chi_{S_{\alpha+(v_1-v_2)t,\gamma}}(s_2) d\alpha dt$
    • Now by a similar border shifting as above, we get that this is equal to:
    • $\int_{t=1}^1 \chi_{S_{\alpha,\gamma}}(s_1) \gamma d\alpha dt = \gamma^2$

Lemma 6

• Let there be $m$ different runners and $#\chi_{S_{\alpha,\gamma}}(\bar s+t\bar v)$ then $\int_{\gamma=0}^1 \left(#\chi_{S_{\alpha,\gamma}} -ym\right)^2\geq \frac{1}{12}$.
• Proof:
  • As $#\chi_{S_{\alpha,\gamma}}$ is integer valued, $\lvert #\chi_{S_{\alpha,\gamma}} - \gamma m\rvert \geq d(\gamma m)$ where $d(x) \in [0,1/2]$, the distance to the nearest integer.
  • By the definition $d(\gamma n)$ is $1/m$ periodic and symmetric around $\frac{1}{2m}$.
  • Hence $\int_{\gamma=0}^1 d(\gamma m)^2 = 2n \int_{\gamma=0}^{1/2 m} d(\gamma m)^2$ (where the left hand side is a lower bound of the equation we want to estimate).
  • As if $\gamma \in [0,\frac{1}{2m}]$ then $d(\gamma m)=\gamma m$.
  • $\int_{\gamma=0}^{\frac{1}{2m}} d(\gamma m)^2 = m^2 \int_{\gamma =0}^{\frac{1}{2m}} \gamma^2 = \frac{m^2}{3 (2m)^3} = \frac{1}{24m}$.

Theorem 1 Proof

• Let $v_1,\dots,v_k$ be the distinct speeds of the overall speeds $v_1,\dots,v_n$.
• Let $A_i$ be the runners with speed $v_i$, $i\in [k]$.
• We can look at $#j\chi{S_{\alpha,\gamma}}(\bar s + t \bar v)$ where we only sum over the bucket $A_j$, $j\in [k]$, i.e., $\sum_{i \in A_i} \chi_{S_{\alpha,\gamma}}(s_i + t v_i)$. And $#\chi_{S_{\alpha,\gamma}}(\bar s + t\bar v)$ is the total sum.
• We will estimate $\int_{\alpha=0}^1\int_{\gamma=0}^1 \int_{t=0}^1 \left(#\chi_{S_{\alpha,\gamma}}(\bar s + t\bar v)\right)$.
• For ease of notation let $g_j(\alpha,\gamma,t)=#j\chi{S_{\alpha,\gamma}}(\bar s + t\bar v) - \gamma \lvert A_j\rvert$.
• Lemma 6 gives us that $\int_{\alpha=0}^1\int_{\gamma=0}^1 \int_{t=0}^1 g_j(\alpha,\gamma,t) \geq 1/12$.
• By Lemma 4, $\int_{\alpha=0}^1\int_{\gamma=0}^1 \int_{t=0}^1 g_j(\alpha,\gamma,t)g_{j'}(\alpha,\gamma,t)=0$ if $j\neq j'$.
  • By Lemma 4, we have $\int_{\alpha=0}^1 \int_{t=0}^1 #j\chi{S_{\alpha,\gamma}}(\bar s + t \bar v) = \gamma \lvert A_j\rvert$ (notice that we have $\lvert A_j\rvert$ many parts which by linearity of integrals just multiply out)
  • Hence, again by Lemma 4: $\int_{\alpha=0}^1 \int_{t=0}^\infty g_j(\alpha,\gamma,t)g_{j'}(\alpha,\gamma,t)$ can be written as
  • $\int_{\alpha=0}^1\int_{t=0}^1 #j\chi{S_{\alpha,\gamma}} #{j'}\chi{S_{\alpha,\gamma}} -\int_{\alpha=0}^1\int_{t=0}^1\gamma \lvert A_j\rvert #{j'}\chi{S_{\alpha,\gamma}} - \int_{\alpha=0}^1\int_{t=0}^1 \gamma \lvert A_{j'}\rvert #j\chi{S_{\alpha,\gamma}} + \int_{\alpha=0}^1\int_{t=0}^1 \gamma^2\lvert A_j\rvert \lvert A_{j'}\rvert$.
  • This is equal to $\int_{\alpha=0}^1\int_{t=0}^1 #j\chi{S_{\alpha,\gamma}} #{j'}\chi{S_{\alpha,\gamma}} - \gamma^2\lvert A_j\rvert \lvert A_{j'}\rvert$. (using linearity and that we know $\int_{\alpha=0}^1 \int_{t=0}^1 #j\chi{S_{\alpha,\gamma}}(\bar s + t \bar v) = \gamma \lvert A_j\rvert$).
  • We can also see $\int_{\alpha=0}^1\int_{t=0}^1 #j\chi{S_{\alpha,\gamma}} #{j'}\chi{S_{\alpha,\gamma}}=\sum_{i\in A_j, i'\in A_{j'}} \int_{\alpha=0}^1 \int_{t=0}^1 \chi_{S_{\alpha,\gamma}}(s_i + t v_i) \chi_{S_{\alhpa,\gamma}}(s_{i'} + t v_{i'})$.
  • By the second part of the lemma, this is equal to $\gamma^2 \lvert A_i\rvert \lvert A_{i'}\rvert$.
  • Hence, the equation is zero.
• $\int_{\alpha=0}^1\int_{t=0}^1 \left(#\chi_{S_{\alpha,\gamma}} - \gamma n\right)^2$
• By substitution this is equal to $\int_{\alpha=0}^1\int_{t=0}^1 \left(\sum_{j=1}^k g_j\right)^2$
• By linearity of integral $=\sum_{j=1}^k \int_{\alpha=0}^1\int_{t=0}^1 g_j^2 + \sum_{j\neq j'} \int_{\alpha=0}^1\int_{t=0}^1 g_j g_{j'}$.
• By the above argument this is $\geq k/12$.
• This implies that there exists $\alpha,t,\gamma$ such that $\lvert\int_{\alpha=0}^1\int_{t=0}^1 #\chi_{S_{\alpha,\gamma}} - \gamma n\rvert \geq \sqrt{\frac{k}{12}}$.
• This is a standard argument. Assume all would be smaller than as k does not depend on $\alpha,\gamma$ or $t$ the integral would just be $\geq k/12$.

Theorem 1 is tight

Theorem 7

• Let $v_i=i$. For every $s_1,\dots,s_n$ and every $t,\gamma$ the following holds: For every sector of aperture $\gamma$, $B(s_1+tv_1,\dots,s_n + tv_n) \leq O(\sqrt{n\log n})$.

Tau conjecture relation proof

Setup

• Real $\tau$ conjecture: a real univariate polynomial $\sum_{i=1}^p \prod_{j=1}^q f_{i,j}$ where $f_{i,j}$ has support smaller than $r$ has at most $(pqr)^c$ distinct real roots.
• Newt(f(x,y)): Let $f(x,y)=\sum_{i,j} \alpha_{i,j} x^i y^j$ and let supp(f)=${ (i,j) \mid \alpha_{i,j}\neq 0}$. Then the Newton polytope is the convex hull of supp(f).
• Newton conjecture: Let $f(x,y)$ be a real polynomial than Newt(f(x,y)) has at most $(pqr)^c$ vertices.

Theorem (3)

• Let $f(x,y)$ be a bivariate complex polynomial such that Newt(f(x,y)) has $k$ vertices. Then there exists a real polynomial with $\Omega(k)$ roots.

Lemma 14

Statement

• Let $g(x,y) = y^m \sum_{j=n_1}^{n_2} c_j x^j y^{qj}$.
• Let $h(x,y)$ be a real polynomial such that $Newt(h)$ lies strictly above the line $l$.
• Then: There $0<d<d'$ such that for every $r$ sufficiently small, $g(x,r)+h(x,r)$ contains a root in the interval $(dr^{-q}, d'r^{-q})$

Proof

FILL

Lemma 15

Statement

• Let $V(r_1,\dots,r_k)=\lvert { i\in [k] \mid r_i r_{i+1}<0}\rvert$ the number of sign variations in a sequence.
• Then: $V(\cos(\alpha_1 + \phi n_1),\dots, \cos(a_k + \phi n_k)) \geq (k-1)/8$.

Proof of the Theorem

• Let $Newt(f(x,y))$ be such that it has $k$ edges.
• Let it have $s\geq (k-2)/2$ lower edges WHY?
• Let $e_1,\dots,e_s$ with gradients $q_1,\dots,q_s$ be these edges (with the edge $e_i$ connecting $(a_i,b_i)$ and $(a_{i+1},b_{i+1})$).
• Let $re^{\iota \alpha_i}$ be the coefficient of $x^{a_i b_i}$.
• We can write the real part of $f_{e_i}(x,re^{\iota \phi})$ as $\cos(\alpha_i + b_i \phi)r_ir^{b_i}x^{a_i} + \cos(\alpha_{i+1} + b_{i+1}\phi)r_{i+1}r^{b_i}x^{a_{i+1}} + R(u_i)$ where $u_i$ is such that $Newt(u_i)$ is strictly contained between $(a_i,b_i)$ and $(a_{i+1},b_{i+1})$.
• Let $T(\phi)$ be the sequence $\cos(\alpha_1 + \phi b_1),\dots,\cos(\alpha_{s+1} + \phi b_{s+1})$.
• By the previous lemma, there exist a $\phi$ such that $V(T(\phi))$ has at least $(k-1)/8$ many sign changes.
• By Lemma 14, we can conclude that $R(f(x,re^{\iota \phi}))$ has a root in the interval $(d_ir^{-q_i}, d'_ir^{-q_i})$ for every $r$ sufficiently small. FIGURE THIS OUT EXACTLY
• As $r$ shrinks, the intervals become disjoint and hence, we have at least $(s-1)/8$ distinct roots.