Overview over the real au au-conjecture

Christian Engels June 21, 2018 [TCS]

An Overview over the real τ\tau-conjecture

References:

τ\tau-conjecture

Introduction

Conjecture

Let f(x)=i=1kj=1mfi,j(x)f(x)=\sum_{i=1}^k \prod_{j=1}^m f_{i,j}(x) with fi,jf_{i,j} being tt-sparse. then the number of real roots is bounded by some polynomial in mktmkt (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 xeixe^{i}).

Koiran - Shallow circuits with High-Powered Inputs

Theorem

If the conjecture is true then the permanent is not in VP0VP_0.

In the following VP0VP_0 and VNP0VNP_0 are the known classes, except that we only allow constants from 1,0,+1{-1,0,+1} to be used.

Proof

Part 1

Part 2

Ingredients for Part 2. In the following, s=nO(nlogn)s=n^{O(\sqrt n \log n)} and e=2O(n)e=2^{O(n)}.

Comments

Koiran, Portier, Tavenas - A Wronskian approach to the real τ\tau-conjecture

Finding upper bounds for the number of roots for i=1kαij=1mfi,jβi,j \sum_{i=1}^k \alpha_i \prod_{j=1}^m f_{i,j}^{\beta_{i,j}} where fi,jf_{i,j} are tt-sparse.

Theorem 12: Such an ff has at most O(tmk22)O(t^{\frac{mk^2}{2}}) roots.

Wronskian: W(f1,,fk)=det(f1fk  k1xk1f1k1xk1fk) W(f_1,\dots, f_k) = \det \begin{pmatrix} f_1& \dots& f_k\ \vdots& \ddots& \vdots\ \frac{\partial^{k-1}}{\partial x^{k-1}} f_1&\dots&\frac{\partial^{k-1}}{\partial x^{k-1}} f_k \end{pmatrix}

Proof

Ingredients

Theorem 9

Koiran, Portier, Tavenas, Thomasse - A τ\tau-conjecture for Newton Polygons

Briquel, Buergisser - The real tau conjecture is true on average