Conjecture: The number of integer roots of a univariate polynomial f computed by a constant free circuit of size s is bounded by sO(1).
Proving the conjecture shows that PC=NPC.
Proving the conjecture shows that VP=VNP.
Theorem: computing the family (n!) is hard (exponential in logn) iff the τ-conjecture is true. (Buergisser)
Number of real roots of Chebyshev polynomials is exponential in the circuit size (and other examples).
Introduction
Conjecture
Let f(x)=∑i=1k∏j=1mfi,j(x) with fi,j being t-sparse. then the number of real roots is bounded by some polynomial in mkt (all polynomials are univariate).
A note on multiplicities
Hrubes basically shows that it does not matter if we count multiplicities or not as both imply each other (via some construction with replacing x ith xei).
S(α,β)=reiϕ∈C∣r>0,β<ϕ<α.
Conjecture 1: f(x)=∑i=1k∏j=1mfi,j(x) with fi,j being t-sparse, the number of real roots without multiplicity is poly(mkt).
Conjecture 2: f(x)=∑i=1k∏j=1mfi,j(x) with fi,j being t-sparse, the number of real roots with multiplicity is poly(mkt).
Conjecture 3: For every 0<α−β<2π, f(x)=∑i=1k∏j=1mfi,j(x) with fi,j being t-sparse, ∣Nα,β(f)−2πα−βn∣≤mktO(1) where Nα,β(f) is the number of roots of f of the form reiϕ (the angles of the roots are distributed uniformly, expect an error linearly depending on the terms of f).
2->1: Obvious.
3->2:
Look at reiϕ, r>0 a root with multiplicity m.
Look at Sector S(ϕ+π/n,ϕ−π/n).
Assuming f(0)=0. The number of roots in S are at most ∣Nα,β(f)−ϕ+π/n−(ϕ−π/n)∣=∣Nα,β−1∣≤(kmt)c+1
Hence the multiplicity is bounded by sc+1 and hence the conjecture follows as there are 2n sectors.
If f(0)=0 repeat this argument with f(0+ε) for a small ε.
1->3:
Proposition 3.1: Let f be a polynomial with degree n and the real part of f(0)=0. Then for every 0<α−β<2π, ∣Nα,β(f)−2πα−βn∣≤M(f)+1/2 where M(f)=maxα∈[0,2π]Mα(f) and Mα(f) the number of distinct possible roots of of the real polynomial R(f(xeiα)). (R is the real part.)
Proposition 3.3: Let f=∑i=1k∏j=1mfi,j where each fi,j is t-sparse. Then R(f)=∑i=1k(m+1)∏j=1mgi,j where gi,j are t-sparse (This is shown by a standard interpolation argument).
By Proposition 3.1 we can look at the real roots of f(xeiα).
By Proposition 3.3, R(f(xeiα)) has the form of Conjecture 1, giving us (k(m+1)(m+1))O(1) many roots.
This shows Conjecture 3.
Koiran - Shallow circuits with High-Powered Inputs
Theorem
If the conjecture is true then the permanent is not in VP0.
In the following VP0 and VNP0 are the known classes, except that we only allow constants from −1,0,+1 to be used.
Proof
Part 1
Def: SPSs,e all ΣΠΣ circuits that have at most s monomials, coefficients of bit size 2e and fi,j have degree e.
We assume the following conjecture: SPSs,e has at most (s+loge)c many integer roots.
This is clearly weaker than the real τ conjecture.
Let s=nO(nlogn),e=2O(n).
Assume the following statement: perm ∈VP0 then gn=∏i=12nx−i, 2p(n)gn∈SPSs,e (we will show this statement later).
Let Hm be the roots of x−i for all i≤m
Notice that H2n is a hitting set for SPSs,e for m≤2o(n) for large enough n.
Here we use our conjecture! The conjecture says, any such SPSs,e circuit has at most (s+loge)c many roots.
Hence, it has m=(2nlog2n+O(n))c<2o(n) many roots by our conjecture.
Hence an set of >m numbers is a hitting set.
Hence Hm is a hitting set for 2p(n)gn.
But gn vanishes on H and is not equal zero.
Hence, the implication: perm∈VP0⇒2p(n)gn∈SPSs,e has to be false.
Part 2
Ingredients for Part 2. In the following, s=nO(nlogn) and e=2O(n).
Lemma 2: If perm ∈VP0 then CH/poly=P/poly.
Lemma 1: Valiant's Criterion: If f(j,n)∈GapP/poly then ∑j∈0,1nf(j,n)x1j1⋯xnjn∈VNP0.
Theorem 1: If perm ∈VP0 then for all (fn)∈VNP, (2p(n)fn)∈VP0.
Proposition 1: Let fn(X,Z)∈VP0 then fn(x20,…,x2cn−1,z20,…,z2cn−1) has SPSs,e.
Notice that for our polynomial gn, the degrees and coefficient bit size are bounded by 2n,22(c+1)n respectively and the coefficients are computable in CH/poly. Hence, the following works.
See gn as gn=∑αa(n,α)xα and expand a into binary, resulting in the polynomial:
hn(x1,…,xcn,z1,…,zcn) such that hn(x20,…,x2cn−1,220,…,22cn−1)=gn.
Let us denote the bits of a(n,α) by ai(n,α).
ai(n,α) is computable by Lemma 2 in GapP/poly. Hence hn∈VNP0
By Theorem 1, 2p(n)hn∈VP0.
By Proposition 1, gn∈SPSs,e.
Comments
With my understanding, even proving that the roots of a ΣΠΣ circuit are far away would be interesting and show the lower bound
Koiran, Portier, Tavenas - A Wronskian approach to the real τ-conjecture
Finding upper bounds for the number of roots for
i=1∑kαij=1∏mfi,jβi,j
where fi,j are t-sparse.
Theorem 12: Such an f has at most O(t2mk2) roots.
Theorem 9: Let f1,…,fk be analytical independent functions then Z(f1+⋯+fn)≤k−1+Z(Wk)+Z(Wk+1)+2∑i=1k−2Z(Wj).
Lemma 10: Derivative of fα of order p.
Lemma 11: Take M a set of t monomials and f1,…,fs be polynomials with monomials in M. Take a monomial P(f1,f1(1),…,f1(s−1),fs,…,fs(s−1)). The number of monomials in x of P is at most (t−1d+t−1).
Lemma 2: Let f=∑i=1tαixαi where αi are pairwise not equal. Then f has at most t−1 real roots. [Descarte's weak Rule of Signs].
Theorem 9
Let Wi=W(f1,…,fi), W0=1.
Lemma 22: Let R0=f1+⋯+fk and Ri+1=WiWi+12∂x∂Wi+1Ri. Then Rk−1=Wk.
Rolle's Theorem: Let f(a)=f(b) and continuous and differentiable, then there exists c such that f′(c)=0.
Induction on i with hypothesis: Ri has at least Z(f1+⋯+fk)−i−Z(Wi)−2∑j=1i−1Z(Wj) many real roots.
We want to get analyse the roots of Wi+1Ri.
Let us define, where mx(F) is the multiplicity of the root in F:
Z_i^+ = #{ x \mid m_x(R_i) > m_x(W_{i+1}) >0 }.
Z_i^= = #{ x \mid m_x(R_i) = m_x(W_{i+1}) >0 }.
Z_i^- = #{ x \mid 0< m_x(R_i) < m_x(W_{i+1}) }.
Z_i^{-0} = #{ x \mid 0= m_x(R_i) < m_x(W_{i+1}) }.
This list is exhaustive and hence Z(Wi+1)=Zi++Zi=+Zi−+Zi−0 (as we only look at roots that for Wi+1).
Let F be the number of zeros of Ri. Then
Z(Wi+1Ri)≥F−Zi=−Zi−.
We have poles (where the value goes to infinite) at Zi−, Zi−0.
Rolle's Theorem, says: between every two of our zeroes there is a place where the derivated function is zero.
Hence Z(∂x∂Wi+1Ri)=F−Zi=−Zi−−1 but this is not correct. I also have to subtract Zi−+Zi−0 as these could match with non-poles on the other size.
Hence the overall is F−Zi=−Zi−−1−Zi−−Zi−0.
Now we can figure out the number of roots of WiWi+12∂Wi+1Ri.
Number of zeroes is just added, hence (F−Zi=−Zi−−1−Zi−−Zi−0)+Zi−−Z(Wi))
The reason is that by the following argument, we get at least one zero for every x that is in Zi−. Is this just an obvious lower bound?
We use the fact that if 0<mx(Ri)<mx(Wi+1) then Wi+12 grows faster to zero than 1/Wi+1 and hence there is a root at Wi+12⋅∂(Wi+1Ri).
Hence, we get Z(f1+⋯+fk)−i−Z(Wi)−2∑j=1i−1Z(Wj)−Zi=−Zi−−1−Zi−−Zi−0+Zi−−Z(Wi).
Using the equality for Z(Wi+1)=Zi++Zi=+Zi−+Zi−0 i.e., (−Z(Wi+1)+Zi+=−Zi−−Zi=−Zi−0) gives us
Z(f1+⋯+fk)−(i+1)−2∑j=1iZ(Wj)−Z(Wi+1)+Zi+ which gives us the required lower bound.
Koiran, Portier, Tavenas, Thomasse - A τ-conjecture for Newton Polygons
Let f be a bivariate polynomial. Then we can identify XiYj with a point (i,j). Call this Mon(f). Now Newt(f) is the convex hull of all Mon(f).
Conjecture: Any bivariate polynomial f=∑i=1k∏j=1mfij with fij having at most t monomials. Then the newton polynomial of f has at most (kmt)O(1) edges.
Assume that for some constant c<2 the upper bound on the number of edges of the newton polynomial of the form of f is bounded by 2(m+logkt)c when the product kmt is sufficiently large. Then the permanent is not computable by polynomial size circuits.
Briquel, Buergisser - The real tau conjecture is true on average
Let k1,…,km and t be positive integers. We fix supports Si,j⊆N with ∣Si,j∣≤t we choose coefficients ui,j,s as independent gaussian random variables with fi,j=∑s∈Si,jui,j,sxs and f=∑i=1m∏j=1kifi,j. Then the expected number of real zeros of f is bounded by O(tk1+⋯+tkt).