pdf icon
Volume 9 (2013) Article 10 pp. 403-411
On the Real $\tau$-Conjecture and the Distribution of Complex Roots
Received: December 4, 2012
Revised: April 11, 2013
Published: May 21, 2013
Download article from ToC site:
[PDF (178K)] [PS (547K)] [Source ZIP]
Keywords: arithmetic circuits, lower bounds, roots
ACM Classification: F.1.m
AMS Classification: 03D15, 68Q17

Abstract: [Plain Text Version]

$ \newcommand{\eee}{\mathrm{e}} $

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$ \[\Big|N_{\alpha,\beta}(f)- \frac{(\alpha-\beta)}{2\pi} n \Big|\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\eee^{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.