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

About 4 years old · traced to

Let n∈Nn\in\mathbb{N}), let γi,j∈Q\gamma_{i,j}\in\mathbb{Q} and bi∈Zb_i\in\mathbb{Z} for all i,ji,j, and consider the univariate rational function

g(u):=∏i=1n+1(γi,1u+γi,0)bi−1.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:=max⁡i∣bi∣B:=\max_i|b_i| and log⁡H:=max⁡i,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 log⁡n(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.

References

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.