# Finding an approximate double-zero using binary search

Let $$f$$ be a continuous real function on $$[-1,1]$$. The function is accessible via queries: for any $$x$$, the value of $$f(x)$$ can be computed in constant time. If $$f(-1)<0$$ and $$f(1)>0$$, then by the intermediate value theorem, $$f$$ has a zero --- an $$x \in [-1,1]$$ for which $$f(x)=0$$. Suppose we want to find a zero approximately, that is: given $$\delta>0$$, find an interval of length at most $$\delta$$, that contains a zero. This can be done using binary search: start with the entire interval $$[-1,1]$$; let $$c$$ be the middle of the interval; if $$f(c)=0$$ we are done; if $$f(c)>0$$ then recursively search between the leftmost end of the current interval and $$c$$; if $$f(c)<0$$ then recursively search between $$c$$ and the rightmost end. After $$O(\log(1/\delta))$$ steps, the interval length is at most $$\delta$$. So the run-time is polynomial in the length of the binary representation of $$\delta$$.

Now, suppose we have two continuous functions, $$f$$ and $$g$$, both defined on $$[-1,1]\times[-1,1]$$. Suppose $$f(-1,y)<0$$ for all $$y$$ and $$f(1,y)>0$$ for all $$y$$, and $$g(x,-1)<0$$ for all $$x$$ and $$g(x,1)>0$$ for all $$x$$. By the Poincare-Miranda theorem, there exists a double-zero, that is, a point $$(x,y)\in[-1,1]\times[-1,1]$$ such that $$f(x,y)=g(x,y)=0$$. We want to find a double-zero approximately, that is: given $$\delta>0$$, find a square of side-length at most $$\delta$$, that contains a double-zero. Is it possible to do in time $$O(poly(\log(1/\delta))$$?

I tried to apply binary search, but it did not work. If I could know, for example, that for some $$c\in[-1,1]$$, $$f(c,y)<0$$ for all $$y$$, then I could recursively search the rectangle $$[c,1]\times[-1,1]$$. But there is no reason to think that such a $$c$$ exists.

Can this problems be solved using $$O(poly(\log(1/\delta))$$ queries?

This paper studies a similar problem: finding an approximate fixed-point of a two-dimensional function from the unit square to itself, which is accessible via value queries. The authors prove that computing a fixed point with $$p$$ decimal digits requires $$\Omega(2^p)$$ queries. Equivalently, computing a square of side-length at most $$\delta$$ that contains a fixed point requires $$\Omega(1/\delta)$$ queries.

I claim that the same is true for finding a double-zero with general functions. The proof is by reduction from the fixed-point problem. Let $$h$$ be a continuous function for which we want to find a fixed point, and suppose it is a function on the square $$[-1,1]^2$$. Define two functions $$f$$ and $$g$$ as follows:

$$f(x,y) := x - h(x,y)_1 \\ g(x,y) := y-h(x,y)_2$$

Note that $$f(-1,y) \leq (-1) - (-1) = 0 ~~~~ f(1,y) \geq 1 - 1 = 0 \\ g(x,-1) \leq (-1) - (-1) = 0 ~~~~ g(x,1) \geq 1 - 1 = 0,$$ so the pair $$(f,g)$$ has a double-zero. Moreover, $$(x,y)$$ is a double-zero of $$(f,g)$$ if and only if it is a fixed point of $$h$$. Therefore, finding an approximate double-zero requires $$\Omega(1/\delta)$$ queries.

For the case of monotone functions, I asked a separate question in cstheory.SE.

• @YvesDaoust ??? An $\Omega(1/\delta)$ bound implies that an $O(\mathrm{poly}(\log(1/\delta)))$ bound does not hold, directly answering the question in the negative. Commented Apr 4, 2023 at 10:54