4
$\begingroup$

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.

enter image description here

$\endgroup$
6
  • $\begingroup$ I guess that you would not like to add continuity as an assumption? $\endgroup$ – Jochen Wengenroth Sep 7 '20 at 9:10
  • $\begingroup$ @JochenWengenroth good question. I added a continuity assumption, but not sure it matters. $\endgroup$ – Erel Segal-Halevi Sep 7 '20 at 9:28
  • 6
    $\begingroup$ if it is continuous, then such $x$ form an open set, how can it be a single point? $\endgroup$ – Fedor Petrov Sep 7 '20 at 9:35
  • 2
    $\begingroup$ For continuous $g$ I believe that a quite simple ''bisection algorithm'' does the job. $\endgroup$ – Jochen Wengenroth Sep 7 '20 at 9:37
  • 2
    $\begingroup$ I think that $s,t \in (0,1]$? Does $s = 0$ or $t = 0$ make any sense? $\endgroup$ – Dieter Kadelka Sep 7 '20 at 10:08
4
$\begingroup$

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)<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 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)$?

Then the answer is yes.

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)<t$ (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.

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

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<s$ 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<s$, I do not know if it is possible to decide with finitely-many queries.

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