Theory of Computing
-------------------
Title : On the Real $\tau$-Conjecture and the Distribution of Complex Roots
Authors : Pavel Hrubes
Volume : 9
Number : 10
Pages : 403-411
URL : http://www.theoryofcomputing.org/articles/v009a010
Abstract
--------
Koiran's real $\tau$-conjecture asserts that if a non-zero real
polynomial can be written as $f=\sum_{i=1}^{p}\prod_{j=1}^{q}f_{ij}$,
where each $f_{ij}$ contains at most $k$ monomials, then the number of
distinct real roots of $f$ is polynomially bounded in $pqk$. We show
that the conjecture implies quite a strong property of the complex
roots of $f$: their arguments are uniformly distributed except for an
error which is polynomially bounded in $pqk$. That is, if the
conjecture is true, $f$ has degree $n$ and $f(0)\not=0$, then for
every $0<\alpha-\beta< 2\pi$
|N_{\alpha,\beta}(f)- \frac{(\alpha-\beta)}{2\pi} n| \leq (pqk)^c
where $c$ is an absolute constant and $N_{\alpha,\beta}(f)$ is the
number of roots of $f$ of the form $r e^{i\phi }$, with $r>0$ and
$\beta<\phi <\alpha$, counted with multiplicities. In particular, if
the real $\tau$-conjecture is true, it is also true when multiplicities
of non-zero real roots are included.
A preliminary version of this paper appeared in ECCC, 2012/121.