mejorar los límites conocidos para las expansiones de Pierce; premio en efectivo

Question

He aquí un problema que pensé de nuevo en 1978 o así, y sólo un poco progreso se ha hecho en ella desde entonces. Aún pienso en ti de vez en cuando, pero probablemente a que muchas personas no han pensado en ello. Como me estoy haciendo mayor, ahora me ofrecen un premio en efectivo para cualquier persona que puede hacer que los nuevos avances.

El problema se refiere a la cantidad de pasos en una forma extremadamente simple algoritmo. Deje $a, b$ ser enteros positivos con $a > b$. Set $b_0 = b$, y para $i \geq 1$ definir $b_i = a \bmod b_{i-1}$. Ya que en general $x \bmod y < y$, esto significa $b_0 > b_1 > \cdots$, por lo que eventualmente $b_n = 0$. Definir $P(a,b) = n$ en este caso. Así, por ejemplo, $P(35,22) = 7$, desde $b_0 = 22$, $b_1 = 35 \bmod 22 = 13$, $b_2 = 9$, $b_3 = 8$, $b_4 = 3$, $b_5 = 2$, $b_6 = 1$, $b_7 = 0$. Esto se ve de manera superficial, como el algoritmo de Euclides para el mcd, pero se comporta de manera muy diferente.

Pregunta: ¿cómo de grande es $P(a,b)$ como una función de la $a$? El límite superior $P(a,b) = O(a^{1/3})$ es conocida y el límite inferior $P(a,b) > c \log a$ para infinidad de $a$ es también conocido. (Véase, por ejemplo, http://archive.numdam.org/ARCHIVE/JTNB/JTNB_1991__3_1/JTNB_1991__3_1_43_0/JTNB_1991__3_1_43_0.pdf - mi primer y único papel con Erdos, y https://cs.uwaterloo.ca/research/tr/1996/21/cs-96-21.pdf .)

Ofrezco Estados Unidos \$200 for any significant improvement to either the upper or lower bounds. If I had to guess, I'd say probably $P(a,b) = O((\log a)^2)$.

Una de las razones por qué esto es interesante porque $P(a,b)$ es esencialmente la longitud de la "Pierce expansión" de $b/a$, que es una alternancia de expansión de la serie de la forma ${1 \over {x_1}} - {1 \over {x_1 x_2}} + {1 \over {x_1 x_2 x_3}} - \cdots$.

Answer 1

Muy buena pregunta! Esta es una (larga) comentario, no una respuesta

He encontrado una heurística de lo que sugiere el límite inferior es fuerte, y me pregunto si usted tiene alguna razón para dudar de ella. El modelo es que, dada $n$ y $a_k$, $a_{k+1}$ es uniformemente de $\{0,\ldots,a_k-1\}$. Alternativamente, $a_{k+1}=\lfloor Ua_k\rfloor$ donde $U$ es una variable aleatoria uniforme. Así que usted está pidiendo a empezar desde algún lugar en el rango de 1 a $a$, ¿cuántas $U$'s hacer tiene que multiplicar antes de llegar a 0 (parte entera). Usted puede comprobar rápidamente que la probabilidad de no obtener 0 después de multiplicar $100\log a$ condiciones es $O(a^{-K})$ para algunos razonablemente grande de energía.

Así que incluso teniendo en cuenta los diferentes valores de $b$, la probabilidad de que cualquiera de ellos conducen a una cadena de longitud 100$\log a$ es $O(a^{1-K})$. Dado que este es summable, por Borel-Cantelli, no es $a_0$ tal que para todos los $a\ge a_0$, no hay una cadena de longitud $100\log a$.