Detecting slow growth in a finite number of queries

Question

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".

Answer 1

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.

Answer 2

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$.

Answer 3

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.