Detección del crecimiento lento en un número finito de consultas

Question

La siguiente pregunta se formuló en ¿Puede resolver este problema utilizando un número finito de consultas? :

Dejemos que $g:[0,1]\to[0,1]$ sea una función continua monotónicamente creciente. Se puede acceder a $g$ mediante consultas de dos tipos:

• Dado $x\in[0,1]$ , volver $g(x)$ .
• Dado $y\in[0,1]$ , volver $g^{-1}(y)$ .

Dados unos parámetros fijos $s,t\in (0,1)$ ¿se puede encontrar, utilizando un número finito de consultas, un punto $x$ para lo cual

$$ g(x+s) - g(x) < t $$ (si tal $x$ existe)?

En la misma página se respondía a esta pregunta, afirmativamente.

En un comentario, el OP se preguntaba entonces qué pasará sin que se asuma que "tal $x$ existe".

Se demostrará aquí que, con una interpretación formal razonable, la respuesta cambiará a "no".

Answer 1

En primer lugar, interpretemos formalmente la pregunta, como sigue:

Tome cualquier $s$ y $t$ en $(0,1)$ . Dejemos que $CI_{s,t}$ sea el conjunto de todas las funciones continuas estrictamente crecientes $g\colon[0,1]\to[0,1]$ . Dejemos que $G_{s,t}$ sea el conjunto de todas las funciones $g\in CI_{s,t}$ tal que el conjunto $$E_{s,t}(g):=\{x\in[0,1-s]\colon g(x+s)-g(x)<t\}$$ es no vacía. ¿Existen secuencias $(x_j)_{j=1}^\infty$ y $(y_j)_{j=1}^\infty$ en $[0,1]$ tal que para cualquier $g\in CI_{s,t}$ existe una forma natural de $n$ tal que la siguiente implicación se mantiene: Si para alguna función $h\in CI_{s,t}$ y para todos $j\in[n]:=\{1,\dots,n\}$ tenemos $h(x_j)=g(x_j)$ y $h^{-1}(y_j)=g^{-1}(y_j)$ entonces

(i) si $g\in G_{s,t}$ entonces ( $h\in G_{s,t}$ y) para algunos $k\in[n]$ nosotros tenemos $x_k\in E_{s,t}(h)$ ;

(ii) si $g\notin G_{s,t}$ entonces $h\notin G_{s,t}$ .

La respuesta ahora es no, en general.

De hecho, tome cualquier $s,t$ tal que $0<t<s<1$ . Tome cualquier secuencia $(x_j)_{j=1}^\infty$ y $(y_j)_{j=1}^\infty$ en $[0,1]$ . Tome cualquier $n$ .

Considere el conjunto $P_{s,t}$ de todos los pares $(a,b)$ tal que $$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}.$$ El conjunto $P_{s,t}$ es no vacía y abierta; de hecho, $$(a,b)\in P_{s,t}\iff \Big(0<a<1-s\ \&\ \frac{a t}{s}<b<\frac{a t+s-t}{s}\Big).$$

Tome ahora cualquier par $(a,b)\in P_{s,t}$ tal que $a\notin\big\{x_j\colon j\in[n]:=\{1,\dots,n\}\big\}$ y $b\notin\{y_j\colon j\in[n]\}$ ; un par de este tipo $(a,b)$ existe, ya que $P_{s,t}$ es no vacío y abierto.

A continuación, dejemos que $g=g_{a,b}=g_{s,t,a,b}$ sea la función cuya gráfica es la unión de los segmentos de recta que unen sucesivamente los puntos $(0,0),(a,b),(a+s,b+t),(1,1)$ . Entonces $g\in CI_{s,t}\setminus G_{s,t}$ .

Dejemos que $$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\}.$$ Entonces $x_{n,a}^-<a<x_{n,a}$ y $y_{n,b}>b$ . Desde $g$ es estrictamente creciente, hay algún $c$ tal que $$b=g(a)<c<\min[g(x_{n,a}),y_{n,a}].$$ Para tales $c$ y todos $x\in[0,1]$ , dejemos que $h$ sea la función cuya gráfica es la unión de los segmentos de recta que unen sucesivamente los puntos $(0,0),(x_{n,a}^-,g(x_{n,a}^-)),(a,c),(x_{n,a},g(x_{n,a})),(a+s,b+t),(1,1)$ . Entonces $h(x_j)=g(x_j)$ y $h^{-1}(y_j)=g^{-1}(y_j)$ para todos $j\in[n]$ . Sin embargo, $h(a+s)-h(a)=g(a+s)-c<g(a+s)-g(a)=t$ para que $h\in G_{s,t}$ mientras que $g\notin G_{s,t}$ . Por lo tanto, la conclusión (ii) de la implicación en la formalización destacada de la pregunta no se sostiene. $\Box$

---

Los gráficos de $g$ (azul) y $h$ (oro) para $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$ se muestran a continuación.

Answer 2

Aquí se demuestra que, incluso con "consultas adaptativas" (consultas que pueden depender de las respuestas a consultas anteriores, en lugar de estar fijadas de antemano), puede no existir un algoritmo finito.

Elige algunos $s'\in(s,1)$ y definir la siguiente función lineal a trozos:

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

Tenga en cuenta que $g_0(0)=0, g_0(1)=1$ Hay un número incontable de $x$ para lo cual $g_0(x+s)-g_0(x) = t$ pero no $x$ para lo cual $g_0(x+s)-g_0(x) < t$ .

Supongamos que las respuestas a todas las consultas son como si $g\equiv g_0$ . Tras un número finito de consultas, es posible que efectivamente $g = g_0$ en cuyo caso no hay solución. Sin embargo, después de un número finito de consultas, hay un número incontable de puntos $x\in [0,s'-s]$ que no participaron en ninguna consulta. Al aumentar ligeramente el valor de $g_0(x)$ manteniendo la función continua, como en la figura de Respuesta de Iosif obtenemos otra función $g_1$ para lo cual $g_1(x+s)-g_1(x)<t$ .

Answer 3

Aunque la pregunta ha sido respondida, es interesante comprobar qué ocurre si cambiamos ligeramente la condición, de $g(x+s)-g(x)<t$ a $g(x+s)-g(x)\leq t$ . La prueba anterior no funciona. Sin embargo, sigo pensando que es imposible decidir si tal $x$ existe con consultas finitas. Fijación de $s$ y $t$ para cada $z\in[0,1-s]$ , dejemos que $G_z$ sea el conjunto de funciones continuas $g_z$ para lo cual:

$$ g_z(x+s) - g_z(x) > t ~~ x\neq z \\ g_z(x+s) - g_z(x) = t ~~ x = z $$

(debería ser posible construir tales funciones continuas; ahora no tengo la construcción exacta).

Para demostrar la imposibilidad, podemos utilizar un argumento de adversario: demostramos que, para cualquier algoritmo de formulación de consultas adaptativas, un adversario puede responder a las consultas de tal manera que el algoritmo nunca sabrá si existe una solución o no.

El adversario trabaja de la siguiente manera: escoge un $z\in[0,1-s]$ y una arbitraria $g_z\in G_z$ y responde a todas las consultas como si $g \equiv g_z$ siempre que las consultas no impliquen el punto $z$ en sí mismo. En caso de que una consulta implique el punto $z$ el adversario elige un punto cercano $z'$ que no es igual a ningún punto registrado (cualquier punto que haya aparecido en una consulta anterior). Construye una nueva función $g_{z'}\in G_{z'}$ que coincide con $g_z$ en todos los puntos registrados (hay un número finito de tales puntos, por lo que debería ser posible construir tal función continua). El adversario puede seguir cambiando de función para siempre, y el algoritmo nunca sabrá el verdadero $z$ y, por tanto, nunca sabrá si existe una solución.