Skip to main content
5 of 7
added 121 characters in body
Iosif Pinelis
  • 127.7k
  • 8
  • 107
  • 229

The question is stated informally, using the terms "queries" and "access".

Here is how I formally interpret it:

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

Iosif Pinelis
  • 127.7k
  • 8
  • 107
  • 229