# Can you solve this problem using a finite number of queries?

Let $$g:[0,1]\to[0,1]$$ be a continuous monotonically-increasing function. You can access $$g$$ using queries of two kinds:

• Given $$x\in[0,1]$$, return $$g(x)$$.
• Given $$y\in[0,1]$$, return $$g^{-1}(y)$$.

Given fixed parameters $$s,t\in (0,1)$$, can you find, using finitely many queries, a point $$x$$ for which

$$g(x+s) - g(x) < t$$

(if such $$x$$ exists)?

Example: if $$g$$ is the function below, $$s=0.3$$ and $$t>0.1$$, then $$x=0.4$$ is a solution as $$g(x+s)-g(x)=0.1$$. If $$t\leq 0.1$$ then there is no solution.

• I guess that you would not like to add continuity as an assumption? Sep 7, 2020 at 9:10
• @JochenWengenroth good question. I added a continuity assumption, but not sure it matters. Sep 7, 2020 at 9:28
• if it is continuous, then such $x$ form an open set, how can it be a single point? Sep 7, 2020 at 9:35
• For continuous $g$ I believe that a quite simple ''bisection algorithm'' does the job. Sep 7, 2020 at 9:37
• I think that $s,t \in (0,1]$? Does $s = 0$ or $t = 0$ make any sense? Sep 7, 2020 at 10:08

The question is stated informally, using the terms "queries" and "access".

Here is how I formally interpret it:

Take any $$s$$ and $$t$$ in $$(0,1)$$. Let $$G_{s,t}$$ be the set of all continuous strictly increasing functions $$g\colon[0,1]\to[0,1]$$ such that the set $$E:=E_{s,t}(g):=\{x\in[0,1-s]\colon g(x+s)-g(x) is nonempty. Do there exist sequences $$(x_j)_{j=1}^\infty$$ and $$(y_j)_{j=1}^\infty$$ in $$[0,1]$$ such that for any $$g\in G_{s,t}$$ there is a natural $$n$$ such that the following implication holds: If a function $$h\colon[0,1]\to[0,1]$$ is continuous and strictly increasing and for all $$j\in[n]:=\{1,\dots,n\}$$ we have $$h(x_j)=g(x_j)$$ and $$h^{-1}(y_j)=g^{-1}(y_j)$$, then ($$h\in G_{s,t}$$ and) for some $$k\in[n]$$ we have $$x_k\in E_{s,t}(h)$$?

Then the answer is yes.

Indeed, informally, let the $$j$$th query give us the values $$g(q_j)$$ and $$g(q_j+s)$$, where $$(q_j)_{j=1}^\infty$$ is an enumeration of the set of all rational numbers in the interval $$[0,1-s]$$. Take any $$g\in G_{s,t}$$, so that $$E_{s,t}(g)\ne\emptyset$$. Since $$g$$ is continuous, the set $$E_{s,t}(g)\subseteq[0,1-s]$$ is open in $$[0,1-s]$$, and hence $$q_n\in E_{s,t}(g)$$ for some natural $$n$$. So, we will find the point $$q_n\in E_{s,t}(g)$$ on our $$n$$th query.

Formally, let $$(y_j)_{j=1}^\infty$$ be any sequence in $$[0,1]$$ (it will be of no use to us). For each natural $$j$$, let $$x_{2j-1}:=q_j$$ and $$x_{2j}:=q_j+s$$.

Take any $$g\in G_{s,t}$$. Then, as noted above, $$q_n\in E_{s,t}(g)$$ for some natural $$n$$. Now, if a function $$h\colon[0,1]\to[0,1]$$ is continuous and strictly increasing and for all $$j\in[2n]$$ we have $$h(x_j)=g(x_j)$$ and $$h^{-1}(y_j)=g^{-1}(y_j)$$, then for $$k=2n-1(\in[2n])$$ we have $$x_k=x_{2n-1}=q_n\in[0,1-s]$$ and $$h(x_k+s)-h(x_k)=h(x_{2n})-h(x_{2n-1})=g(x_{2n})-g(x_{2n-1})=g(q_n+s)-g(q_n) (because $$q_n\in E_{s,t}(g)$$), so that $$x_k\in E_{s,t}(h)$$ (and $$h\in G_{s,t}$$). Thus, the implication in question holds.

The monotonicity condition on $$g$$ or the knowledge of values of $$g^{-1}$$ was not actually needed in this proof.

• Thanks! But this solution assumes that such a point $x$ exists. What if we do not make this assumption, and need to also decide whether or not it exists? Sep 7, 2020 at 15:17
• @ErelSegal-Halevi : You did say "if such x exists". The bulk of the work here was to formalize the problem. Anyway, I think that without the existence assumption and with a reasonable formal interpretation, the answer will change to "no". However, I'd suggest that you post, separately, a quite formally presented question without the existence assumption, avoiding such terms as "query", "access", etc. or perhaps using them only for an accompanying informal version of the question. Sep 7, 2020 at 15:29
• @ErelSegal-Halevi : A negative answer to the question without the existence assumption is now posted at mathoverflow.net/questions/371123/… Sep 7, 2020 at 18:52
• Wonderful, thanks so much Sep 8, 2020 at 18:41

Iosif Pinelis proved that, when a solution is guaranteed to exist, it can be found using finitely many queries.

When a solution is not guaranteed to exist, then it may be impossible to decide whether or not it exists with finitely many queries. I could prove it for the special case $$t = s$$. Suppose that, after some $$n$$ queries, for every $$j\in [n]$$, the answer for query $$x_j$$ is $$g(x_j)=x_j$$ and the answer for query $$y_j$$ is $$g^{-1}(y_j)=y_j$$. Then, it is possible that $$g(x)\equiv x$$, in which case no solution exists. However, it is also possible that $$g(x)$$ is slightly different than $$x$$ in some open interval that does not contain any $$x_j$$ or $$y_j$$. In this case a solution exists.

When $$t and a solution is not guaranteed to exist, Iosif Pinelis proved that the problem may not be decided using a finite number of non-adaptive queries (queries that must be determined in advance, and may not depend on answers to previous queries). The idea is that, for every finite number $$n$$ of queries, there is a piecewise-linear function $$g$$ for which no solution exists, and a slight modification of it - that does not change the answer to any of the $$n$$ queries - yields a function $$h$$ for which a solution exists.

A remaining open case is that of adaptive queries, in which each query may depend on answers to previous queries. When $$t, I do not know if it is possible to decide with finitely-many queries.