# 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? – Jochen Wengenroth Sep 7 '20 at 9:10
• @JochenWengenroth good question. I added a continuity assumption, but not sure it matters. – Erel Segal-Halevi Sep 7 '20 at 9:28
• if it is continuous, then such $x$ form an open set, how can it be a single point? – Fedor Petrov Sep 7 '20 at 9:35
• For continuous $g$ I believe that a quite simple ''bisection algorithm'' does the job. – Jochen Wengenroth Sep 7 '20 at 9:37
• I think that $s,t \in (0,1]$? Does $s = 0$ or $t = 0$ make any sense? – Dieter Kadelka Sep 7 '20 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)$$?

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? – Erel Segal-Halevi Sep 7 '20 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. – Iosif Pinelis Sep 7 '20 at 15:29
• @ErelSegal-Halevi : A negative answer to the question without the existence assumption is now posted at mathoverflow.net/questions/371123/… – Iosif Pinelis Sep 7 '20 at 18:52
• Wonderful, thanks so much – Erel Segal-Halevi Sep 8 '20 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.