Overview over the real $ au$-conjecture

Christian Engels June 21, 2018 [TCS]

An Overview over the real $\tau$-conjecture

References:

$\tau$-conjecture

Conjecture: The number of integer roots of a univariate polynomial $f$ computed by a constant free circuit of size s is bounded by $s^{O(1)}$.
Proving the conjecture shows that $P_{\mathbb{C}} \neq NP_{\mathbb{C}}$.
Proving the conjecture shows that $VP\neq VNP$.
Theorem: computing the family $(n!)$ is hard (exponential in $\log n$) iff the $\tau$-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)=\sum_{i=1}^k \prod_{j=1}^m f_{i,j}(x)$ with $f_{i,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 $xe^{i}$).

$S(\alpha,\beta)= { re^{i\phi}\in \mathbb{C}\mid r>0, \beta<\phi<\alpha}$.
Conjecture 1: $f(x)=\sum_{i=1}^k \prod_{j=1}^m f_{i,j}(x)$ with $f_{i,j}$ being $t$-sparse, the number of real roots without multiplicity is poly$(mkt)$.
Conjecture 2: $f(x)=\sum_{i=1}^k \prod_{j=1}^m f_{i,j}(x)$ with $f_{i,j}$ being $t$-sparse, the number of real roots with multiplicity is poly$(mkt)$.
Conjecture 3: For every $0<\alpha -\beta<2\pi$, $f(x)=\sum_{i=1}^k \prod_{j=1}^m f_{i,j}(x)$ with $f_{i,j}$ being $t$-sparse, $\lvert N_{\alpha, \beta}(f) -\frac{\alpha-\beta}{2\pi} n\rvert \leq mkt^{O(1)}$ where $N_{\alpha, \beta}(f)$ is the number of roots of $f$ of the form $re^{i\phi}$ (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 $re^{i\phi}$, $r>0$ a root with multiplicity $m$.
- Look at Sector $S(\phi+\pi/n, \phi - \pi/n)$.
- Assuming $f(0)\neq 0$. The number of roots in $S$ are at most $\lvert N_{\alpha,\beta}(f) - \phi+\pi/n - (\phi - \pi/n)\rvert = \lvert N_{\alpha,\beta} -1\vert \leq (kmt)^c+1$
- Hence the multiplicity is bounded by $s^c+1$ and hence the conjecture follows as there are $2n$ sectors.
- If $f(0)=0$ repeat this argument with $f(0+\varepsilon)$ for a small $\varepsilon$.
1->3:
- Proposition 3.1: Let $f$ be a polynomial with degree $n$ and the real part of $f(0)\neq 0$. Then for every $0<\alpha -\beta <2\pi$, $\lvert N_{\alpha,\beta}(f) -\frac{\alpha -\beta }{2\pi}n\rvert \leq M(f)+1/2$ where $M(f) = \max_{\alpha \in [0,2\pi] M_\alpha(f)}$ and $M_\alpha(f)$ the number of distinct possible roots of of the real polynomial $\mathcal{R}(f(xe^{i\alpha}))$. ($\mathcal{R}$ is the real part.)
- Proposition 3.3: Let $f=\sum_{i=1}^k \prod_{j=1}^m f_{i,j}$ where each $f_{i,j}$ is $t$-sparse. Then $\mathcal{R}(f) = \sum_{i=1}^{k(m+1)} \prod_{j=1}^m g_{i,j}$ where $g_{i,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(xe^{i\alpha})$.
- By Proposition 3.3, $\mathcal{R}(f(xe^{i\alpha}))$ 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 $VP_0$.

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

Proof

Part 1

Def: $SPS_{s,e}$ all $\Sigma\Pi\Sigma$ circuits that have at most $s$ monomials, coefficients of bit size $2^e$ and $f_{i,j}$ have degree $e$.
We assume the following conjecture: $SPS_{s,e}$ has at most $(s+\log e)^c$ many integer roots.
- This is clearly weaker than the real $\tau$ conjecture.
Let $s=n^{O(\sqrt{n} \log n)}, e=2^{O(n)}$.
Assume the following statement: perm $\in VP_0$ then $g_n = \prod_{i=1}^{2^n} x -i$, $2^{p(n)}g_n\in SPS_{s,e}$ (we will show this statement later).
Let $H_m$ be the roots of $x-i$ for all $i\leq m$
Notice that $H_{2^n}$ is a hitting set for $SPS_{s,e}$ for $m\leq 2^{o(n)}$ for large enough $n$.
- Here we use our conjecture! The conjecture says, any such $SPS_{s,e}$ circuit has at most $(s+\log e)^c$ many roots.
- Hence, it has $m=(2^{\sqrt{n} \log^2 n} + O(n))^c < 2^{o(n)}$ many roots by our conjecture.
- Hence an set of $>m$ numbers is a hitting set.
Hence $H_m$ is a hitting set for $2^{p(n)}g_n$.
But $g_n$ vanishes on $H$ and is not equal zero.
Hence, the implication: perm$\in VP_0 \Rightarrow 2^{p(n)} g_n \in SPS_{s,e}$ has to be false.

Part 2

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

Lemma 2: If perm $\in VP_0$ then $CH/poly = P/poly$.
Lemma 1: Valiant's Criterion: If $f(j,n)\in GapP/poly$ then $\sum_{j\in {0,1}^n} f(j,n)x_1^{j_1}\cdots x_n^{j_n} \in VNP_0$.
Theorem 1: If perm $\in VP_0$ then for all $(f_n)\in VNP$, $(2^{p(n)}f_n)\in VP_0$.
Proposition 1: Let $f_n(X,Z)\in VP_0$ then $f_n(x^{2^0},\dots, x^{2^{cn-1}},z^{2^0},\dots,z^{2^{cn-1}})$ has $SPS_{s,e}$.
Notice that for our polynomial $g_n$, the degrees and coefficient bit size are bounded by $2^n, 2^{2^{(c+1)n}}$ respectively and the coefficients are computable in $CH/poly$. Hence, the following works.
See $g_n$ as $g_n=\sum_\alpha a(n,\alpha)x^\alpha$ and expand $a$ into binary, resulting in the polynomial:
$h_n(x_1,\dots,x_{cn},z_1,\dots,z_{cn})$ such that $h_n(x^{2^0}, \dots,x^{2^{cn-1}},2^{2^0},\dots,2^{2^{cn-1}})=g_n$.
Let us denote the bits of $a(n,\alpha)$ by $a_i(n,\alpha)$.
$a_i(n,\alpha)$ is computable by Lemma 2 in $GapP/poly$. Hence $h_n \in VNP_0$
By Theorem 1, $2^{p(n)}h_n\in VP_0$.
By Proposition 1, $g_n\in SPS_{s,e}$.

Comments

With my understanding, even proving that the roots of a $\Sigma\Pi\Sigma$ circuit are far away would be interesting and show the lower bound

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

Finding upper bounds for the number of roots for $$ \sum_{i=1}^k \alpha_i \prod_{j=1}^m f_{i,j}^{\beta_{i,j}} $$ where $f_{i,j}$ are $t$-sparse.

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

Wronskian: $$ 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: Let $f_1,\dots,f_k$ be analytical independent functions then $Z(f_1 + \dots + f_n) \leq k-1 + Z(W_k) + Z(W_{k+1}) + 2\sum_{i=1}^{k-2} Z(W_j)$.
Lemma 10: Derivative of $f^\alpha$ of order $p$.
Lemma 11: Take $M$ a set of $t$ monomials and $f_1,\dots, f_s$ be polynomials with monomials in $M$. Take a monomial $P(f_1,f_1^(1),\dots,f_1^{(s-1)}, f_s, \dots, f_s^{(s-1)})$. The number of monomials in $x$ of $P$ is at most $\binom{d+t-1}{t-1}$.
Lemma 2: Let $f=\sum_{i=1}^t \alpha_i x^{\alpha_i}$ where $\alpha_i$ are pairwise not equal. Then $f$ has at most $t-1$ real roots. [Descarte's weak Rule of Signs].

Theorem 9

Let $W_i = W(f_1,\dots,f_i)$, $W_0=1$.
Lemma 22: Let $R_0=f_1 + \dots + f_k$ and $R_{i+1}= \frac{W^2_{i+1}}{W_i} \frac{\partial}{\partial x} \frac{R_i}{W_{i+1}}$. Then $R_{k-1} = W_k$.
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: $R_i$ has at least $Z(f_1+ \dots + f_k) - i - Z(W_i) - 2\sum_{j=1}^{i-1} Z(W_j)$ many real roots.
We want to get analyse the roots of $\frac{R_i}{W_{i+1}}$.
Let us define, where $m_x(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(W_{i+1}) = Z_i^+ + Z_i^= + Z_i^- + Z_i^{-0}$ (as we only look at roots that for $W_{i+1}$).
Let $F$ be the number of zeros of $R_i$. Then
$Z(\frac{R_i}{W_{i+1}}) \geq F- Z_i^= - Z_i^-$.
We have poles (where the value goes to infinite) at $Z_i^-$, $Z_i^{-0}$.
Rolle's Theorem, says: between every two of our zeroes there is a place where the derivated function is zero.
Hence $Z(\frac{\partial}{\partial x}\frac{R_i}{W_{i+1}}) = F-Z_i^= - Z_i^- -1$ but this is not correct. I also have to subtract $Z_i^-+Z_i^{-0}$ as these could match with non-poles on the other size.
Hence the overall is $F-Z_i^= - Z_i^- - 1 - Z_i^- - Z_i^{-0}$.
Now we can figure out the number of roots of $\frac{W^2_{i+1}}{W_i} \partial \frac{R_i}{W_{i+1}}$.
Number of zeroes is just added, hence $(F-Z_i^= - Z_i^- - 1 - Z_i^- - Z_i^{-0}) + Z_i^- - Z(W_i))$
The reason is that by the following argument, we get at least one zero for every $x$ that is in $Z_i^-$. Is this just an obvious lower bound?
We use the fact that if $0< m_x(R_i) < m_x(W_{i+1})$ then $W_{i+1}^2$ grows faster to zero than $1/W_{i+1}$ and hence there is a root at $W_{i+1}^2 \cdot \partial (\frac{R_i}{W_{i+1}})$.
Hence, we get $Z(f_1+ \dots + f_k) - i - Z(W_i) - 2\sum_{j=1}^{i-1} Z(W_j) -Z_i^= - Z_i^- -1 - Z_i^- -Z_i^{-0} + Z_i^- - Z(W_i)$.
Using the equality for $Z(W_{i+1})=Z_i^+ + Z_i^= + Z_i^- + Z_i^{-0}$ i.e., ($-Z(W_{i+1}) + Z_i^+= -Z_i^- -Z_i^= - Z_i^{-0})$ gives us
$Z(f_1 + \dots + f_k) - (i+1) - 2\sum_{j=1}^i Z(W_j) - Z(W_{i+1}) + Z_i^+$ which gives us the required lower bound.

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

Let $f$ be a bivariate polynomial. Then we can identify $X^iY^j$ 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=\sum_{i=1}^k\prod_{j=1}^m f_{ij}$ with $f_{ij}$ 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+\log kt)^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 $k_1,\dots,k_m$ and $t$ be positive integers. We fix supports $S_{i,j}\subseteq \mathbb{N}$ with $\lvert S_{i,j}\rvert \leq t$ we choose coefficients $u_{i,j,s}$ as independent gaussian random variables with $f_{i,j}= \sum_{s\in S_{i,j}} u_{i,j,s} x^s$ and $f=\sum_{i=1}^m \prod_{j=1}^{k_i} f_{i,j}$. Then the expected number of real zeros of $f$ is bounded by $O(tk_1 + \dots + tk_t)$.