Polynomial-time approximate-root conjecture for circuit-system Gale duals

Let nNn\in\mathbb{N}), let γi,jQ\gamma_{i,j}\in\mathbb{Q} and biZb_i\in\mathbb{Z} for all i,ji,j, and consider the univariate rational function

g(u):=i=1n+1(γi,1u+γi,0)bi1.g(u):=\prod_{i=1}^{n+1}\left(\gamma_{i,1}u+\gamma_{i,0}\right)^{b_i}-1.

For coprime integers u,vu,v, define the logarithmic height of u/vu/v by h(u/v):=max{u,v}h(u/v):=\max\{|u|,|v|\}, with h(0):=0h(0):=0. Set B:=maxibiB:=\max_i|b_i| and logH:=maxi,jh(γi,j)\log H:=\max_{i,j}h(\gamma_{i,j}). An approximate root is understood in the sense of Smale.

Polynomial-time approximate-root conjecture. Following this notation, one can find approximate roots for all the real roots of gg in time polynomial in logn(BH)\log^n(BH).

This conjecture concerns the real-solving complexity of circuit systems, which generalize univariate trinomial equations. It is motivated by reductions of circuit-system solving to real roots of Gale-dual rational functions; its status is not resolved in the supplied text.

Sources & referencesView supporting material

Primary source

Emma Boniface, Weixun Deng and J. Maurice Rojas, “Trinomials and Deterministic Complexity Limits for Real Solving”, arXiv:2202.06115 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.