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

• How is this related to approximation algorithms? Sep 7, 2020 at 20:08
• @RodrigodeAzevedo : Here I used the tags used for the linked question. I think the approximation algorithm here is given by the choice of the query points, to approximate the functions $g$ and $g^{-1}$ by their restrictions to the corresponding sets of the query points, in order to detect slow growth. Sep 7, 2020 at 20:47
• I don't want to be too annoying and split hairs that no one cares about, but both questions have a computer science "feel" combined with real analysis. However, an algorithm that approximates something is not an approximation algorithm as used by computer scientists — the tag description has a CS bent. The semidefinite programming approach to MAX-CUT is an approximation algorithm, however. Sep 7, 2020 at 20:58
• @RodrigodeAzevedo : I have had very little experience in computer science. However, it appears that the author of the linked question (whose tags I borrowed here) is a computer scientist. So, it appears to me that for some computer scientists the approximation-algorithms tag seems appropriate. Sep 8, 2020 at 2:22

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) 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. 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\frac{t}{s}.$$ The set $$P_{s,t}$$ is nonempty and open; in fact, $$(a,b)\in P_{s,t}\iff \Big(0

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_jb\}.$$ Then $$x_{n,a}^- and $$y_{n,b}>b$$. Since $$g$$ is strictly increasing, there is some $$c$$ such that $$b=g(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, 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. • Very interesting! In the language of queries, it seems that your formalization corresponds to "non-adaptive queries". This means that the algorithm has to decide in advance what queries to ask, i.e., the sequences $x_n$ and $y_n$ are pre-determined. There is a different model called "adaptive queries", in which the algorithm may decide what queries to ask based on the replies to previous queries, i.e., $x_j$ and $y_j$ may depend on $g(x_1),\ldots,g(x_{j-1})$ and $g(y_1),\ldots,g(y_{j-1})$. When $s=t$, there is no finite solution even in the adaptive query model (see the original question). Sep 8, 2020 at 18:50
• @ErelSegal-Halevi : I'd guess that even for general $s,t$ there is no finite solution even in the adaptive query model. Sep 8, 2020 at 21:05
• I agree, and added a proof. Sorry for using the language of queries - this is the language I am used to. It comes from papers such as this: combinatorics.org/ojs/index.php/eljc/article/view/735 Sep 10, 2020 at 11:19

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

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