Detecting slow growth in a finite number of queries The following question was asked at 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)?

On the same page, this question was answered, affirmatively.
In a comment, the OP then asked what will happen without the assumption that "such $x$ exists".
It will be shown here that, with a reasonable formal interpretation, the answer will change to "no".
 A: First of all, let us formally interpret the question, as follows:

Take any $s$ and $t$ in $(0,1)$. Let $CI_{s,t}$ be the set of all continuous strictly increasing functions $g\colon[0,1]\to[0,1]$. Let $G_{s,t}$ be the set of all functions $g\in CI_{s,t}$
such that the set
$$E_{s,t}(g):=\{x\in[0,1-s]\colon g(x+s)-g(x)<t\}$$
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 CI_{s,t}$ there is a natural $n$ such that the following implication holds: If for some function $h\in CI_{s,t}$ 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
(i) if $g\in G_{s,t}$ then ($h\in G_{s,t}$ and) for some $k\in[n]$ we
have $x_k\in E_{s,t}(h)$;
(ii) if $g\notin G_{s,t}$ then $h\notin G_{s,t}$.

The answer is now no, in general.
Indeed, take any $s,t$ such that $0<t<s<1$. Take any sequences $(x_j)_{j=1}^\infty$ and $(y_j)_{j=1}^\infty$ in $[0,1]$. Take any natural $n$.
Consider the set $P_{s,t}$ of all pairs $(a,b)$ such that
$$0<a<a+s<1\ \&\ 0<b<b+t<1\ \&\ \min\Big(\frac{b}{a},\frac{1-b-t}{1-a-s}\Big)>\frac{t}{s}.$$
The set $P_{s,t}$ is nonempty and open; in fact,
$$(a,b)\in P_{s,t}\iff \Big(0<a<1-s\ \&\ \frac{a t}{s}<b<\frac{a t+s-t}{s}\Big).$$
Take now any pair $(a,b)\in P_{s,t}$ such that $a\notin\big\{x_j\colon j\in[n]:=\{1,\dots,n\}\big\}$ and $b\notin\{y_j\colon j\in[n]\}$; such a pair $(a,b)$ exists, since $P_{s,t}$ is nonempty and open.
Next, let $g=g_{a,b}=g_{s,t,a,b}$ be the function whose graph is the union of the straight line segments successively connecting the points $(0,0),(a,b),(a+s,b+t),(1,1)$. Then $g\in CI_{s,t}\setminus G_{s,t}$.
Let
$$x_{n,a}:=\min\{x_j\colon j\in[n],x_j>a\},\quad x_{n,a}^-:=\max\{x_j\colon j\in[n],x_j<a\},\quad y_{n,b}:=\min\{y_j\colon j\in[n],y_j>b\}.$$
Then $x_{n,a}^-<a<x_{n,a}$ and $y_{n,b}>b$. Since $g$ is strictly increasing, there is some $c$ such that
$$b=g(a)<c<\min[g(x_{n,a}),y_{n,a}].$$
For such $c$ and all $x\in[0,1]$, let
$h$ be the function whose graph is the union of the straight line segments successively connecting the points $(0,0),(x_{n,a}^-,g(x_{n,a}^-)),(a,c),(x_{n,a},g(x_{n,a})),(a+s,b+t),(1,1)$. Then $h(x_j)=g(x_j)$ and $h^{-1}(y_j)=g^{-1}(y_j)$ for all $j\in[n]$. However, $h(a+s)-h(a)=g(a+s)-c<g(a+s)-g(a)=t$, so that $h\in G_{s,t}$, whereas $g\notin G_{s,t}$. Thus, conclusion (ii) of the implication in the highlighted formalization of the question fails to hold. $\Box$

The graphs of $g$ (blue) and $h$ (gold) for $s=4/10,t=2/10,a=3/10,b=5/10,x_{n,a}^-=2/10,x_{n,a}=4/10,y_{n,a}>55/100$ are shown below.

A: Here is a proof that, even with "adaptive queries" (queries that may depend on answers to previous queries, rather than be set in advance), a finite algorithm may not exist.
Pick some $s'\in(s,1)$, and define the following piecewise-linear function:
$$
g_0(x) := 
\begin{cases}
(t/s)\cdot x & x \leq s'
\\
(s' t / s) + \frac{1-(s' t / s)}{1-s'} \cdot (x-s') & x\geq s'
\end{cases}
$$
Note that $g_0(0)=0, g_0(1)=1$, there are uncountably many $x$ for which $g_0(x+s)-g_0(x) = t$, but no $x$ for which $g_0(x+s)-g_0(x) < t$.
Suppose that the answers to all queries are as if $g\equiv g_0$. After finitely many queries, it is possible that indeed $g = g_0$, in which case there is no solution. However, after finitely many queries, there are uncountably many points $x\in [0,s'-s]$ that did not participate in any query. By slightly increasing the value of $g_0(x)$ while keeping the function continuous, as in the figure in Iosif's answer, we get another function $g_1$, for which $g_1(x+s)-g_1(x)<t$.
A: While the question has been answered, it is interesting to check what happens if we slightly change the condition, from $g(x+s)-g(x)<t$ to $g(x+s)-g(x)\leq t$. The above proof does not work.
However, I still think that it is impossible to decide if such $x$ exists with finitely-many queries. Fixing $s$ and $t$, for every $z\in[0,1-s]$, let $G_z$ be the set of continuous functions $g_z$ for which:
$$
g_z(x+s) - g_z(x) > t ~~~~ x\neq z
\\
g_z(x+s) - g_z(x) = t ~~~~ x = z
$$
(it should be possible to construct such continuous functions; I do not have the exact construction now).
To prove impossibility, we can use an adversary argument: we show that, for any algorithm for asking adaptive queries, an adversary can answer the queries in such a way that the algorithm will never know if a solution exists or not.
The adversary works as follows: he picks an arbitrary $z\in[0,1-s]$, and an arbitrary $g_z\in G_z$, and answers all queries as if $g \equiv g_z$, as long as the queries do not involve the point $z$ itself. In case a query does involve the point $z$, the adversary picks a nearby point $z'$, that is not equal to any recorded point (any point that appeared in a previous query). He constructs a new function $g_{z'}\in G_{z'}$, that coincides with $g_z$ in all recorded points (there are finitely many such points, so it should be possible to construct such a continuous function). The adversary can keep switching functions forever, and the algorithm will never know the actual $z$, and thus will never know if a solution exists.
