3
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ How is this related to approximation algorithms? $\endgroup$ – Rodrigo de Azevedo Sep 7 '20 at 20:08
  • $\begingroup$ @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. $\endgroup$ – Iosif Pinelis Sep 7 '20 at 20:47
  • 1
    $\begingroup$ 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. $\endgroup$ – Rodrigo de Azevedo Sep 7 '20 at 20:58
  • $\begingroup$ @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. $\endgroup$ – Iosif Pinelis Sep 8 '20 at 2:22
2
$\begingroup$

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.

enter image description here

$\endgroup$
3
  • $\begingroup$ 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). $\endgroup$ – Erel Segal-Halevi Sep 8 '20 at 18:50
  • 1
    $\begingroup$ @ErelSegal-Halevi : I'd guess that even for general $s,t$ there is no finite solution even in the adaptive query model. $\endgroup$ – Iosif Pinelis Sep 8 '20 at 21:05
  • $\begingroup$ 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 $\endgroup$ – Erel Segal-Halevi Sep 10 '20 at 11:19
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.