Real $\tau$-Conjecture for Sparse Polynomial Sums and Products

Real $\tau$-Conjecture for Sparse Polynomial Sums and Products

Definitions and mathematical statement

A univariate polynomial is $t$-sparse if at most $t$ of its monomial coefficients are nonzero. Consider any nonzero $f\in{\mathbb{R}}[x]$ admitting a representation \[ f(x)=\sum_{i=1}^{m}\prod_{j=1}^{k}f_{ij}(x), \qquad \#\operatorname{supp}(f_{ij})\le t. \] The real $\tau$-conjecture in this form seeks universal constants $A>0$, $c\ge1$ for which the number of distinct real roots is at most $A(mkt)^c$, for all positive integers $m,k,t$. Exponents are nonnegative integers, while coefficients are arbitrary reals. The bound is independent of the degrees, coefficient magnitudes, and root multiplicities. The nonzero condition excludes the zero polynomial, which vanishes at every real number.

Formulation and concept references: [S1].

Short English statement

Is the number of distinct real zeros of any nonzero sum of products of sparse polynomials bounded by a universal polynomial in its representation parameters?

Research attempt

Status: UNRESOLVED. A degree-independent bound is proved below, but its dependence on the number of factors is exponential. Polynomial bounds are obtained for one summand, one factor, monomial factors, and several structured families. The missing step is to control cancellations between several long products without expanding them. No worst-case conclusion is inferred from the average-case theorem.

Source audit and the representation being measured.

The revised paper [S1], consulted on 27 September 2026, gives an expected-root bound of order $mk^2t$ when the coefficients in the specified sparse-factor representation are independent standard Gaussians. Its version history records a correction to the first version. The deterministic catalogue question allows arbitrary real coefficients, including highly correlated and exceptional choices. Its parameters count summands, factors and monomials, not degree or the bit length of the exponents. The calculations below address that exact representation. They do not claim an improvement to the published average-case theorem.

Zero factors can be discarded together with their summands. Constant factors can be absorbed into another factor, and products can be padded with factors equal to one. A representation can also have enormous cancellations or even represent zero; the last possibility is explicitly excluded in the target. A proof must bound the roots of the resulting nonzero polynomial, not the number of syntactic terms before cancellation alone.

1. An elementary sparse-root lemma.

A nonzero polynomial with $s$ nonzero monomials has at most $s-1$ distinct positive roots. Here is a proof needing only Rolle's theorem. Write \[ P(x)=\sum_{i=1}^s c_i x^{a_i},\qquad 0\le a_1<\cdots<a_s,\quad c_i\ne0. \] Divide by $x^{a_1}$ on $(0,\infty)$. The derivative of the resulting function is a nonzero polynomial with $s-1$ terms, unless $s=1$, which is the immediate base case. By induction it has at most $s-2$ positive roots. If the original quotient has $r$ distinct positive roots, Rolle gives at least $r-1$ distinct derivative roots. Consequently $r\le s-1$. The argument also works for real exponents on the positive half-line.

Apply the same argument to $P(-x)$ to obtain at most $s-1$ negative roots. Zero contributes at most one distinct root. Therefore \[ Z_{\mathbb R}(P)\le 2(s-1)+1=2s-1. \] If the constant coefficient is nonzero, zero is absent and the upper bound improves to $2s-2$. These counts concern distinct zeros. For example $x^D$ has arbitrarily large multiplicity at zero but only one distinct zero, consistently with $s=1$.

2. What full expansion proves and what it loses.

Each product of $k$ polynomials with at most $t$ terms expands into at most $t^k$ terms. Equal exponents can merge, and coefficients can cancel, so the number of nonzero monomials of $f$ is at most $mt^k$. The lemma proves the unconditional estimate \[ Z_{\mathbb R}(f)\le 2mt^k-1. \] This already removes all dependence on the exponents and coefficient sizes. However, $t^k$ is not bounded by a universal polynomial in $mkt$. Taking $t=2$ and increasing $k$ makes this defect explicit. For each fixed $k$ the displayed estimate is polynomial, but the degree of that polynomial depends on $k$, whereas the conjecture requires one exponent for all $k$.

Counting formal products as though their coefficients had independent random signs would be unjustified. A single coefficient of a factor contributes to many expanded coefficients, and terms with the same exponent interact. The expansion estimate is safe precisely because it uses only a support-size upper bound and makes no independence assertion.

3. Three complete parameter subcases.

If $m=1$, a root of the product is a root of one of its nonzero factors. Applying the half-line bound separately and taking a union gives \[ Z_{\mathbb R}\left(\prod_{j=1}^k f_{1j}\right) \le 2k(t-1)+1. \] The possible zero root is counted once, irrespective of how many factors vanish there. This is substantially better than expansion and proves a linear bound in $kt$ for this subcase.

If $k=1$, the sum has at most $mt$ monomials, hence at most $2mt-1$ real roots. If $t=1$, each surviving product is a monomial, and the entire polynomial has at most $m$ terms, giving $2m-1$ roots independently of $k$. In the latter case nonzero constant products cause no exception. The standing assumption $f\ne0$ is necessary when the monomials cancel.

These arguments cannot be combined by simply distributing a root over summands: $P(x)+Q(x)=0$ can hold even when neither $P(x)$ nor $Q(x)$ vanishes. For example $x^D-1$ has a positive root although each of its two monomial summands is nonzero there.

4. A common-exponent family with an explicit bound.

Suppose all factors have the form $a_{ij}+b_{ij}x^d$ for a common integer $d\ge1$. Then \[ f(x)=P(x^d),\qquad P(y)=\sum_{i=1}^m\prod_{j=1}^k(a_{ij}+b_{ij}y), \qquad \deg P\le k. \] The substitution map is injective on polynomials, so $f\ne0$ implies $P\ne0$. For odd $d$, every real root of $P$ has exactly one real preimage. For even $d$, a positive root has two, zero has one, and a negative root has none. Thus $Z_{\mathbb R}(f)\le2k$, independent of both $m$ and $d$. Multiplication by a monomial $x^a$ adds at most the root zero, giving $2k+1$ for that enlarged family.

More generally, suppose $f=P(h(x))$, where $\deg P\le k$ and $h$ is a nonconstant polynomial with at most $u$ terms. For a real root $r$ of $P$, the nonzero polynomial $h(x)-r$ has at most $u+1$ terms and hence at most $2u+1$ distinct real roots. The fibers over different $r$ are disjoint. Therefore \[ Z_{\mathbb R}(P\circ h)\le k(2u+1). \] This proves a polynomial bound for a genuine common-inner-polynomial restriction. General sparse factors need not share such a representation, so identifying it cannot be assumed as a preprocessing step.

5. A two-product monotonicity calculation.

There is also a useful cancellation-sensitive positive-half-line example. Let \[ P(x)=\prod_{j=1}^k(x+a_j),\qquad Q(x)=\prod_{j=1}^k(x+b_j),\qquad 0<a_j\le b_j, \] with at least one strict inequality. For $x>0$ all factors are positive, and \[ \frac{d}{dx}\log\frac{P(x)}{Q(x)} =\sum_{j=1}^k\left(\frac1{x+a_j}-\frac1{x+b_j}\right)>0. \] Consequently $P-cQ$ has at most one positive root for every $c>0$; for $c\le0$ it has none. If all $a_j=b_j$, the difference is $(1-c)P$, with the zero-polynomial case $c=1$ excluded. This argument controls cancellation by an ordered logarithmic derivative, rather than by the expanded degree.

With arbitrary sparse factors, the summands of $P'/P-Q'/Q$ can change signs and have poles. Splitting at the factor roots is possible, but a uniform bound for its zeros is still needed on each surviving interval. Multiplying by all denominators returns a sum of products and can reproduce the original combinatorial expansion problem. The special ordering above is exactly the hypothesis preventing that loss.

6. Why a small general arithmetic circuit is a different target.

Define $T_1(x)=x$ and recursively $T_{2r}(x)=2T_r(x)^2-1$. The identity $T_d(\cos\theta)=\cos(d\theta)$ follows for powers of two from the double-angle formula. Hence $T_{2^s}$ has $2^s$ distinct roots in $(-1,1)$ while this repeated-squaring circuit uses only order $s$ arithmetic operations.

Thus a polynomial real-root bound in the size of an unrestricted arithmetic circuit would be false. The example does not refute the stated real $\tau$-conjecture: it has not supplied a sum-of-products-of-sparse-polynomials representation with $mkt$ polynomial in $s$. Treating an already computed dense intermediate polynomial as one sparse factor would change the model. The representation restriction is therefore essential, not a cosmetic way to describe a circuit.

7. Average bounds and finite checks.

If a nonnegative random root count $Z$ has expectation at most $Cmk^2t$, Markov's inequality gives $\Pr(Z>L)\le Cmk^2t/L$. It does not imply that $Z$ is bounded by that threshold for every coefficient choice. Even when a simple-root configuration persists in an open coefficient neighborhood, the Gaussian measure of that neighborhood can be arbitrarily small as the coefficients and exponents vary. No uniform lower bound for that measure has been established here.

The offline calculations check exact expansions of common-exponent examples, sparse support counts, the Chebyshev recurrence, and an explicit two-product difference with exactly one positive root. They use integer polynomial arithmetic; they do not approximate the roots of arbitrary high-degree inputs or test the Gaussian theorem. A general proof still needs a cancellation bound polynomial simultaneously in $m,k,t$, or a different invariant that survives sums of long products. None of the proved subcases supplies that invariant, so the worst-case conjecture remains unresolved here.

Sources

• S1 The real tau-conjecture is true on average. https://arxiv.org/pdf/1806.00417. Formulation source.