Real τ-Conjecture

There exists an absolute constant $C>0$ such that, for every nonzero polynomial $f\in\mathbb{R}[x]$ , the number of distinct real roots of $f$ satisfies $\#\{x\in\mathbb{R}:f(x)=0\}\le C\,S(f)$ , where $S(f)$ is the minimum, over all representations $f=\sum_{i=1}^{s}c_i f_i^2$ with $c_i\in\mathbb{R}$ and $f_i\in\mathbb{R}[x]$ , of $\sum_{i=1}^{s}|\operatorname{supp}(f_i)|$ , and $\operatorname{supp}(f_i)$ is the set of monomials having nonzero coefficient in $f_i$ .

References

Primary source

Theory of Computing Systems

Additional references

Real τ-Conjecture for Sum-of-squares: A Unified Approach to Lower Bound and Derandomization — Theory of Computing Systems — Pranjal Dutta

algebraic-complexity-theory derandomization theoretical-computer-science

Posted 4 days ago · edited 4 days ago

Progress summary

Refreshed 4 days ago

Claimed progress

A new paper claims a unified approach to the conjecture’s lower-bound and derandomization aspects, but the conjecture has not been resolved.

Koiran’s 2011 real $\tau$ -Conjecture asserts a polynomial bound on the number of real roots of certain sparse sum-product expressions. It would imply a superpolynomial arithmetic-circuit lower bound for the permanent.

Known results

For a restricted sum-product class, a 2014 paper obtained a real-root bound of order $t^{O(k^2m)}$ and a deterministic polynomial-time identity test, improving earlier dependence on $k$ .

2026 unified-approach paper

Pranjal Dutta’s paper, “Real $\tau$ -Conjecture for Sum-of-squares: A Unified Approach to Lower Bound and Derandomization,” reports a framework connecting the conjecture’s two applications. The available record supplies no abstract or independent assessment, so this is claimed progress rather than a verified resolution.

Current status (as of October 2026): The conjecture remains open; restricted cases and related refinements are known, while Dutta’s broader advance is unverified.

Sources

No solutions have been posted yet.