Authors Pavel Hrube{\v{s}},
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 9 (10), 2013, pp. 403–411
www.theoryofcomputing.org
On the Real τ-Conjecture and
the Distribution of Complex Roots∗
Pavel Hrubeš
Received December 4, 2012; Revised April 11, 2013; Published May 21, 2013
Abstract: Koiran’s real τ-conjecture asserts that if a non-zero real polynomial can be
p q
written as f = ∑i=1 ∏ j=1 fi j , where each fi j 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) 6= 0, then for every 0 < α − β < 2π
(α − β )
Nα,β ( f ) − n ≤ (pqk)c ,
2π
where c is an absolute constant and Nα,β ( f ) is the number of roots of f of the form reiφ ,
with r > 0 and β < φ < α, counted with multiplicities. In particular, if the real τ-conjecture
is true, it is also true when multiplicities of non-zero real roots are included.
ACM Classification: F.1.m
AMS Classification: 03D15, 68Q17
Key words and phrases: arithmetic circuits, lower bounds, roots
1 Introduction
The Shub-Smale τ-conjecture [11, 12] is a conjecture in arithmetic circuit complexity, asserting that a
polynomial which is computable by a small arithmetic circuit has a small number of integer roots. If
true, it gives a lower bound on the circuit complexity of the permanent polynomial [1]. One drawback
∗ A preliminary version of this paper appeared in ECCC 2012/121.
© 2013 Pavel Hrubeš
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2013.v009a010
PAVEL H RUBE Š
of the conjecture is that, by referring to integer roots, it leads one to the area of number theory which is
notorious for its hard problems. It would be desirable to have a hypothesis relating circuit complexity and
the number of real, or even complex, roots. Such a conjecture was put forward by Koiran [6], who calls it
the “real τ-conjecture.” Since τ-conjecture is false when we merely replace “integer root” by “real root”,
the real τ-conjecture counts the number of real roots of a polynomial computed by a restricted circuit. As
shown by Koiran, it nevertheless gives lower bounds for general circuits.1
The real τ-conjecture can be stated without reference to circuits or computation. Let us call a real
(or later complex) polynomial ∑ni=0 ai xi k-sparse if at most k of the coefficients a0 , . . . , an are non-zero.
Let f be a polynomial of the form
p q
f = ∑ ∏ fi j , where each fi j is k-sparse . (1.1)
i=1 j=1
Conjecture 1.1 (The real τ-conjecture). Let f be a non-zero polynomial as in (1.1) with every fi j ∈ R[x].
Then the number of distinct real roots of f is at most (pqk)c , where c is an absolute constant.
Apart from the absence of a counterexample, the conjecture’s motivation is the following corollary of
Descartes’ rule of signs:
Theorem 1.2 (Weak rule of signs). A non-zero k-sparse polynomial has at most k − 1 positive real roots.
In particular, Conjecture 1.1 is true if p = 1 and, in general, f has at most O(pkq ) real roots. A
remarkable aspect of the weak rule of signs is that the number of real roots can be bounded by the
number of terms of a polynomial, rather than the degree. This suggests that in the real setting, sparsity
of a polynomial has a role similar to the notion of degree in the complex setting. Indeed, this analogy
was developed by Khovanskii in his theory of fewnomials [5]. Most notably, he gives a real version of
Bezout’s theorem where the number of solutions of a system of polynomial equations is bounded by
a function of the number of terms in the equations (and the number of equations). It is an intriguing
question whether the quantitative bounds Khovanskii obtains are asymptotically tight and hence how
far can the analogy between degree and the number of terms be pushed. In this perspective, the real
τ-conjecture is an interesting question from a purely mathematical point of view.
It is the author’s conviction that if the real τ-conjecture is true, it is true by virtue of some deeper
phenomenon pertaining to the structure of complex roots. This is because complex roots give a complete
description of a polynomial (up to a multiplicative factor), and complex analysis provides a more powerful
perspective of the world of the reals. Certainly, the real τ-conjecture as stated above has a rather arbitrary
feeling about it. As an extension of the weak rule of signs, it could apparently state much more. The
rule holds also when multiplicities of non-zero real roots are included. Moreover, it implies that the
multiplicity of every non-zero complex root is at most k − 1, and the rule is also valid when we consider
polynomials with complex coefficients. In a less direct manner, it can be shown (see [8, 4]) that the rule
applies also to the number of complex roots lying close to the real axis.
An interesting generalisation of the weak rule of signs, which subsumes the above observations, is
the following. Let α, β be real numbers such that 0 < α − β < 2π, and let f be a complex polynomial.
Denote Nα,β ( f ) the number of complex roots lying in the sector defined by the angles α, β : i. e., let
1 That is, constant-free circuits of unbounded depth.
T HEORY OF C OMPUTING, Volume 9 (10), 2013, pp. 403–411 404
O N THE R EAL τ -C ONJECTURE AND THE D ISTRIBUTION OF C OMPLEX ROOTS
S(α, β ) := {reıφ ∈ C : r > 0 and β < φ < α}
Nα,β ( f ) := the number of roots of f in S(α, β ) counted with multiplicities.
Hayman [3] (see also Proposition 11.2.4 in [9]) proves the following theorem:
Theorem 1.3 (Hayman). Let f be a complex k-sparse polynomial of degree n with f (0) 6= 0. Then for
every 0 < α − β < 2π
α −β
Nα,β ( f ) − n ≤ k −1.
2π
The term (α − β )n/(2π) denotes the number of roots in the sector S(α, β ), assuming the arguments
of the roots are distributed uniformly. So the theorem says that the angles of roots of f are distributed
uniformly except for an error which depends linearly on the number of terms of f . The motivating
example is of course f = xn − 1, where the roots are perfectly spread on the unit circle. Theorem 1.3 gives,
for example, that every sector with α − β > 2π(k − 1)/n contains a root of f . Also, one obtains the weak
rule of signs by letting α → 0+ , β → 0− . One can compare Hayman’s theorem with the Erdös-Turán
theorem [2] which estimates the distribution of roots in terms of the sizes of coefficients of f , rather than
their number.
In this note, we apparently strengthen Conjecture 1.1 so that, instead of counting the number of real
roots, we measure the discrepancy from uniformity á la Theorem 1.3. This is done only to show that the
two versions of the conjecture are actually equivalent. That is, if the real τ-conjecture is true then the
arguments of the complex roots of a polynomial f are uniformly distributed with an error polynomial in
pqk. In particular, if the conjecture is true, it is also true when the multiplicities of the non-zero roots are
included.
Of course, the real τ-conjecture may turn out to be false. This note can also be used to extend the
sphere of possible counterexamples. In order to disprove Conjecture 1.1, it is now enough to construct
a polynomial f which can be succinctly written as (1.1) but whose roots lie in the negative half-plane;
or to construct such an f which has a complex root with multiplicity superpolynomial in pqk—perhaps
already (x + 1)n is a good candidate.
2 Modifications of the conjecture
An apparent detail is whether Conjecture 1.1 should refer to the number of distinct roots, or to the
number of non-zero roots including their multiplicities. Arguments can be made in both directions. The
original Shub-Smale conjecture is inevitably about the number of distinct integer roots, and this suggests
to also exclude multiplicities in Conjecture 1.1. Several applications of Khovanskii’s theory require
counting distinct roots—let us mention Risler’s theorem [10], which relates the number of real roots of a
polynomial and the number of addition gates needed to compute it. Koiran himself seems to believe that
it is important to exclude multiplicities: in [7], Koiran et al. consider polynomials of the form
p q
n
f = ∑ ∏ fi ji j .
i=1 j=1
T HEORY OF C OMPUTING, Volume 9 (10), 2013, pp. 403–411 405
PAVEL H RUBE Š
They give an upper-bound on the number of real roots of f which is independent on the exponents ni j .
They call it a “step towards the real τ-conjecture,” which clearly assumes that multiplicities are ignored.
On the other hand, we note in Observation 3.4 that if the polynomial (x + 1)n can be written as (1.1)
with small pqk then Conjecture 1.1 is false. This suggests that multiplicities of non-zero roots cannot be
neglected and that counting roots with multiplicities is indeed the correct way of counting:
Conjecture 2.1. Let f be a non-zero polynomial as in (1.1) with every fi j ∈ R[x]. Then the number of
non-zero real roots of f , counted with multiplicities, is at most (pqk)c , where c is an absolute constant.
Another detail is whether it is important for the polynomial f in Conjecture 1.1 to be real. This will
be addressed in Corollary 2.5 where it is shown that we can allow the fi j ’s to have complex coefficients.
Finally, inspired by the generalisation of the weak rule of signs given in Theorem 1.3, let us consider the
following:
Conjecture 2.2. Let f be a polynomial as in (1.1) with every fi j ∈ C[x]. Assume that f has degree n and
f (0) 6= 0. Then for every 0 < α − β < 2π,
(α − β )
Nα,β ( f ) − n ≤ (pqk)c ,
2π
where c is an absolute constant.
The assumption f (0) 6= 0 is necessary in order to avoid zero roots. If f (0) = 0 and zero is a root of
multiplicity m, Conjecture 2.2 implies
(α − β )
Nα,β ( f ) − (n − m) ≤ O((pqk)c )
2π
This is shown by considering the polynomial f + ε for a small enough ε. The n − m non-zero roots of
f change only slightly, whereas the zero root of f splits into m distinct roots of f + ε which are almost
uniformly distributed around a circle of radius O(ε 1/m ).
Each Conjecture 1.1, 2.1 and 2.2 seems to be strictly stronger than the previous one. However, we
show that this is in fact not the case:
Theorem 2.3. Conjectures 1.1, 2.1 and 2.2 are equivalent.
This allows one to formulate the following consequences of the real τ-conjecture. Each of them can
be potentially used to construct a counterexample.
Corollary 2.4. Assume Conjecture 1.1. Let f be a complex polynomial as in (1.1) with s := pqk. Then
1. the multiplicity of every non-zero root of f is polynomial in s;
2. if the real part of every root of f is negative (such an f is called Hurwitz polynomial) then
s = Ω(nc ), for a constant c > 0.
Corollary 2.5. If Conjecture 1.1 is true then both Conjecture 1.1 and 2.1 are true even when we allow
the fi j ’s in (1.1) to be complex (while still counting real roots).
T HEORY OF C OMPUTING, Volume 9 (10), 2013, pp. 403–411 406
O N THE R EAL τ -C ONJECTURE AND THE D ISTRIBUTION OF C OMPLEX ROOTS
Proof of Corollary 2.4 and 2.5. Let f be as in (1.1) with fi j ∈ C[x]. Let s := pqk and n be the degree of
f . By Theorem 2.3, we can replace Conjecture 1.1 by Conjecture 2.2, and we will assume the latter.
If reıφ , r > 0, is a root of f with multiplicity m, consider the sector S = S(φ +π/n, φ −π/n). Assuming
f (0) 6= 0, Conjecture 2.2 implies that the number of roots in S is at most sc + 1 and so m ≤ sc + 1 (we
count all roots with their multiplicities). If f (0) = 0, take the polynomial f + ε for a small ε. The roots
vary continuously with ε and S is an open set, hence f + ε has at least as many roots in S as f does. f + ε
p0 q
is of the form ∑i=1 ∏ j=1 fi j where p0 = p + 1 and the fi j ’s are k-sparse. Conjecture 2.2 gives that the
number of roots of f + ε in S is at most (p0 qk)c + 1 ≤ (2s)c + 1 and so m ≤ (2s)c + 1.
If f is a Hurwitz polynomial then N3π/2,π/2 ( f ) = n and Conjecture 2.2 gives that n/2 ≤ sc .
For Corollary 2.5, it is enough to show that the number of non-zero real roots of f is bounded by
a polynomial in s. Consider the two sectors S(α, −α) and S(π + α, π − α) with α = π/n. If f (0) 6= 0,
Conjecture 2.2 gives that the number of roots in each sector is at most sc + 1. If f (0) = 0, take the
polynomial f + ε as above.
3 Proof of Theorem 2.3
The proof has two simple parts. The first, Proposition 3.1, is a general statement about angular distribution
of roots. The second, Proposition 3.3, is a property of depth-three arithmetic circuits which allows to
efficiently compute the real part of a complex polynomial f , provided f itself can be so computed.
For a complex polynomial f = ∑ni=0 ai xi , let
n n
ℜ( f ) = ∑ ℜ(ai )xi , ℑ( f ) = ∑ ℑ(ai )xi ,
i=0 i=0
where ℜ(a), ℑ(a) are the real and the imaginary part of the complex number a, respectively. If ℜ(a0 ) 6= 0
and α ∈ R, let Mα ( f ) be the number of distinct positive roots of the real polynomial fα (x) := ℜ( f (xeıα )).
Furthermore, let
M( f ) := max Mα ( f ) .
α∈[0,2π)
Proposition 3.1. Let f be a complex polynomial of degree n with ℜ( f (0)) 6= 0. Then for every 0 <
α − β < 2π
(α − β )
Nα,β ( f ) − n ≤ M( f ) + 1/2 .
2π
Proof. This follows from Theorem 11.2.1 in [9] where the quantity Nα,β ( f ) is determined exactly. The
regularity assumption of the Theorem can always be guaranteed by considering S(α 0 , β 0 ) with α 0 , β 0
ε-close to α, β .
The proof of Theorem 11.2.1 in [9] relies chiefly on the argument principle, which relates the number
of roots of f inside a domain with the behavior of f on its boundary. For the sake of a reader who is either
curious, or does not want to look for [9], let us give a sketch of an elementary proof of Proposition 3.1.
Consider the family of polynomials f + ıt, where t ≥ 0 is a real parameter. The main point is that the
n complex roots of f + ıt depend continuously on t. If t is sufficiently large, f + ıt has n distinct roots
T HEORY OF C OMPUTING, Volume 9 (10), 2013, pp. 403–411 407
PAVEL H RUBE Š
which are almost completely uniformly distributed around the circle with radius O(t 1/n ). Hence the
sector S(α, β ) contains (α − β )n/2π + c roots, with |c| < 1. As t decreases, the only way how the
number of roots in S(α, β ) can change, is that the roots pass through the boundary of the sector. Hence
one must estimate the number of roots of the form x = reıφ , with r > 0 and φ ∈ {α, β }, which are
roots of f + ıt for some t ≥ 0. If reıφ is a root of f (x) + ıt then r is a root of ℜ( f (xeıφ ) + ıt). However,
ℜ( f (xeıφ ) + ıt) = ℜ( f (xeıφ )) does not depend on t and has Mφ ( f ) positive roots. In addition, considering
the imaginary part gives ℑ( f (reıφ )) + t = 0 and t is uniquely determined by r. So we have reached
(α − β )
Nα,β ( f ) − n ≤ Mα ( f ) + Mβ ( f ) + 1 ≤ 2M( f ) + 1 .
2π
There are few details to correct. First, since Mα ( f ) counts distinct roots, one should better assume that
neither fα nor fβ have multiple real roots—but this can always be achieved by changing α, β by a small
ε. Second, we have missed the bound of Proposition 3.1 by a factor of two—which can be improved by
considering the direction in which the roots pass through the boundary of the sector.
For the purpose of the following lemma, we extend the definition of ℜ( f ) to the case when f is a
multivariate complex polynomial, in the obvious way.
Lemma 3.2.
n n+1 n
ℜ ∏(xi + ıyi ) = ∑ b j ∏(xi + a j yi ) ,
i=1 j=1 i=1
where the a j , b j are some real constants.
Proof. This is a standard interpolation argument. Introduce a new variable z and consider the polynomial
f (z) = ∏ni=1 (xi + zyi )), which is now a real polynomial in 2n + 1 variables. Then
f (z) = f0 + f1 z + · · · + fn zn ,
where the polynomials fi do not depend on z. Choosing n + 1 distinct real numbers a1 , . . . , an+1 , we
obtain
f (ai ) = f0 + f1 ai + · · · + fn ani , i ∈ {1, . . . , n + 1} ,
which can be written as
( f (a1 ), . . . , f (an+1 ))t = V (a1 , . . . , an+1 ) · ( f0 , . . . , fn )t ,
where V (a1 , . . . , an+1 ) is (n + 1) × (n + 1) Vandermonde matrix. The matrix is invertible and hence the
polynomials f0 , . . . , fn are real linear combinations of the polynomials f (a1 ) . . . f (an+1 ). Finally,
n
(−1) j f2 j
ℜ ∏(xi + ıyi ) = ∑
i=1 2 j∈{0,...,n}
and so ℜ(∏ni=1 (xi + ıyi )) = b1 f (a1 ) + · · · + bn+1 f (an+1 ) for some b1 , . . . , bn+1 ∈ R.
T HEORY OF C OMPUTING, Volume 9 (10), 2013, pp. 403–411 408
O N THE R EAL τ -C ONJECTURE AND THE D ISTRIBUTION OF C OMPLEX ROOTS
p q
Proposition 3.3. Let f = ∑i=1 ∏ j=1 fi j where each fi j is a complex k-sparse polynomial. Then
p(q+1) q
ℜ( f ) = ∑ ∏ gi j ,
i=1 j=1
where each gi j is a real k-sparse polynomial.
Proof. Write
p q
ℜ( f ) = ∑ ℜ (ℜ(
∏ ij f ) + ı · ℑ( f ij ))
i=1 j=1
and apply the previous lemma to ℜ ∏qj=1 (ℜ( fi j ) + ı · ℑ( fi j )) for each i ∈ {1, . . . , p}. Note that if fi j is
complex k-sparse then a · ℜ( fi j ) + b · ℑ( fi j ) is real k-sparse for any a, b ∈ R.
Let us note that Proposition 3.3 by itself implies:
p q
Observation 3.4. Assume that f (x) = (x + 1)n can be written as ∑i=1 ∏ j=1 fi j where fi j are complex
k-sparse polynomials. If Conjecture 1.1 is true then pqk = Ω(nc ) for some c > 0.
In order to see this, consider the complex polynomial
f (ıx) + f (−ıx) = (ıx + 1)n + (−ıx + 1)n .
Its degree is either n, if n is even, or n − 1, if it is odd. The roots are of the form
1−ω
ı ,
1+ω
where ω is an n-th root of −1 with ω 6= −1. There are again either n or n − 1 such roots, depending on
the parity of n, and they are all distinct. Furthermore, since |ω| = 1,
1−ω (1 − ω)(1 + ω) 1 − |ω|2 + ω − ω ω −ω 2ℑ(ω)
ı =ı 2
= ı 2
=ı 2
=
1+ω |1 + ω| |1 + ω| |1 + ω| |1 + ω|2
is real. The roots of f (ıx) + f (−ıx) must also be the roots of the non-zero real polynomial ℜ( f (ıx) +
0
f (−ıx)). Conjecture 1.1 in conjunction with Proposition 3.3 then implies that n = O((pqk)c ) for some
constant c0 > 0.
Proof of Theorem 2.3. Clearly, Conjecture 2.1 implies Conjecture 1.1. That Conjecture 2.2 implies
Conjecture 2.1 was explained in the proof of Corollary 2.5.
It remains to prove Conjecture 2.2 assuming Conjecture 1.1. Let f be a complex polynomial as in
Conjecture 2.2. We have f (0) 6= 0 and we can also assume that ℜ( f (0)) 6= 0 – otherwise multiply f by ı.
By Proposition 3.1, we have
(α − β )
Nα,β ( f ) − n ≤ M( f ) + 1/2 ,
2π
T HEORY OF C OMPUTING, Volume 9 (10), 2013, pp. 403–411 409
PAVEL H RUBE Š
where M( f ) is the maximum number of distinct positive roots of ℜ( f (xeiφ )), for φ ∈ [0, 2π). Proposi-
tion 3.3 gives that for a fixed φ
p0 q
iφ
ℜ( f (xe )) = ∑ ∏ gi j ,
i=1 j=1
where all of gi j are real k-sparse and p0 = p(q + 1). Conjecture 1.1 then implies that the number of
positive roots of ℜ( f (xeiφ )) is polynomial in p0 qk = O((pqk)2 ) and so Conjecture 2.2 follows by taking
c large enough.
4 A comment about the proof
The proof of Theorem 2.3 relies mainly on the fact that if a complex polynomial f can be succinctly
represented as (1.1) then so can ℜ( f ), and the theorem will go through for any computational model with
this property. For example, consider the following strengthening of the real τ-conjecture:
Conjecture 4.1. Let A(x1 , . . . , xn ) be an arithmetic formula of size s over R. Let f ∈ R[x] be the
polynomial computed by A(xk1 , . . . , xkn ) where k1 , . . . , kn are some natural numbers. If f is non-zero then
the number of distinct real roots of f is at most sc , for some constant c.
The author is not aware of a counterexample to this statement. As in Theorem 2.3, one can show:
Theorem 4.2. Let f be as above but with A allowed to use complex numbers. Assume that f (0) 6= 0 and
f has degree n. If Conjecture 4.1 is true then for every 0 < α − β < 2π,
(α − β )
Nα,β ( f ) − n ≤ sc ,
2π
with an absolute constant c.
References
[1] P ETER B ÜRGISSER: On defining integers and proving arithmetic circuit lower bounds. Comput.
Complexity, 18(1):81–103, 2009. Preliminary version in STACS’07. [doi:10.1007/s00037-009-
0260-x] 403
[2] PAUL E RD ŐS AND P ÁL T URÁN: On the distribution of roots of polynomials. Ann. of Math.,
51(1):105–119, 1950. JSTOR. 405
[3] WALTER K. H AYMAN: Angular value distribution of power series with gaps. Proc. London
Mathematical Society, s3-24(4):590–624, 1972. [doi:10.1112/plms/s3-24.4.590] 405
[4] AUBREY J. K EMPNER: On the complex roots of algebraic equations. Bull. Amer. Math. Soc.,
41(12):809–843, 1935. [doi:10.1090/S0002-9904-1935-06201-9] 404
T HEORY OF C OMPUTING, Volume 9 (10), 2013, pp. 403–411 410
O N THE R EAL τ -C ONJECTURE AND THE D ISTRIBUTION OF C OMPLEX ROOTS
[5] A SKOLD G. K HOVANSKII: Fewnomials. Volume 88 of Translations of Mathematical Monographs.
Amer. Math. Soc., 1991. 404
[6] PASCAL KOIRAN: Shallow circuits with high-powered inputs. In Proc. 2nd Symp. Innovations in
Computer Science (ICS’11), pp. 309–320. Tsinghua University Press, 2011. ICS’11. 404
[7] PASCAL KOIRAN , NATACHA P ORTIER , AND S ÉBASTIEN TAVENAS: A Wronskian approach to the
real τ-conjecture. Preprint, 2012. [arXiv:1205.1015] 405
[8] N IKOLA O BRESCHKOFF: Über die Wurzeln algebraischer Gleichungen. Jahresbericht der
Deutschen Mathematiker-Vereinigung, 33:52–64, 1925. DigiZeitschriften. 404
[9] Q AZI I. R AHMAN AND G ERHARD S CHMEISSER: Analytic Theory of Polynomials. Oxford Univ.
Press, 2002. 405, 407
[10] J EAN -JACQUES R ISLER: Additive complexity and zeros of real polynomials. SIAM J. Comput.,
14(1):178–183, 1985. [doi:10.1137/0214014] 405
[11] M ICHAEL S HUB AND S TEVE S MALE: On the intractability of Hilbert’s Nullstellensatz and an alge-
braic version of “NP 6= P?”. Duke Mathematical Journal, 81(1):47–54, 1995. [doi:10.1215/S0012-
7094-95-08105-8] 403
[12] S TEVE S MALE: Mathematical problems for the next century. The Mathematical Intelligencer,
20(2):7–15, 1998. [doi:10.1007/BF03025291] 403
AUTHOR
Pavel Hrubeš
postdoctoral fellow
University of Washington, Seattle, WA
pahrubes gmail com
ABOUT THE AUTHOR
PAVEL H RUBEŠ graduated from Charles University in Prague in 2008, and he has been
touring the world ever since. His supervisor was Pavel Pudlák. He is interested in
computational complexity and logic.
T HEORY OF C OMPUTING, Volume 9 (10), 2013, pp. 403–411 411