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$ Commented Sep 7, 2020 at 9:10
  • $\begingroup$ @JochenWengenroth good question. I added a continuity assumption, but not sure it matters. $\endgroup$ Commented Sep 7, 2020 at 9:28
  • 6
    $\begingroup$ if it is continuous, then such $x$ form an open set, how can it be a single point? $\endgroup$ Commented Sep 7, 2020 at 9:35
  • 2
    $\begingroup$ For continuous $g$ I believe that a quite simple ''bisection algorithm'' does the job. $\endgroup$ Commented Sep 7, 2020 at 9:37
  • 2
    $\begingroup$ I think that $s,t \in (0,1]$? Does $s = 0$ or $t = 0$ make any sense? $\endgroup$ Commented Sep 7, 2020 at 10:08

2 Answers 2

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$ Commented Sep 7, 2020 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$ Commented Sep 7, 2020 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$ Commented Sep 7, 2020 at 18:52
  • $\begingroup$ Wonderful, thanks so much $\endgroup$ Commented Sep 8, 2020 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .