Sesión Lógica y Computabilidad (II)

Diciembre 13, 11:00 ~ 11:20

Una construcción de números absolutamente normales con fracción continua normal

Becher, Verónica

{ Un número real se dice normal en base $b$ ($b \in \mathbb N_{\geq 2}$) si su expansión en base $b$ presenta cualquier bloque finito de dígitos $x_1...x_k$ con frecuencia $1/b^k$ (para cualquier $k \in \mathbb N$). Es decir, todos los bloques de tama\~no $k$ aparecen con la misma frecuencia. Un número se dice absolutamente normal si es normal para toda base entera $b$. Casi todos los números son absolutamente normales, es decir, el conjunto de números que no lo son tiene medida de Lebesgue cero. La expansión en fracción continua de un número real $x$ % \in (0,1)$, es una secuencia de números naturales $[a_1,a_2,...]$ tal que \[ x= %a_0 + \lfloor x \rfloor + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{\ddots \, + \cfrac{1}{a_n + \cfrac{1}{\ddots} } }}} \] El desarrollo en fracción continua también posee una noción de normalidad. Se dice normal si la frecuencia de aparición de cualquier bloque $x_1...x_k$ coincide con la medida de Gauss del intervalo $I_{x_1,...,x_k}$, integrado por los números cuya fracción continua comienza con $x_1...x_k$. La medida de Gauss se caracteriza por la siguiente propiedad de invariancia por shift: la medida del intervalo $I_{x_1,...,x_k}$ coincide con la medida del conjunto de números cuya fracción continua presenta el bloque $x_1...x_k$ en otra posición dada. Siguiendo la estrategia adoptada por Becher, Heiber y Slaman en 2013 para construir números absolutamente normales mediante un algoritmo de tiempo polinomial, proponemos aquí un algoritmo también polinomial para construir números que, además de ser absolutamente normales, poseen fracción continua normal. El método consiste en elegir intervalos encajados de manera que cada intervalo asegure determinado nivel de regularidad (baja {\it discrepancia}) en la expansión en cierta base o en fracción continua. La principal dificultad es la necesidad de controlar los tamaños de los intervalos de la forma $I_{x_1,...,x_k}$, ya que para cualquier $k$ fijo, existen intervalos de esta forma de tamaño arbitrariamente pequeño. Para esto utilizamos un caso particular (Morita 1994; Vallée 1997) de una versión muy general del teorema central del límite. También usamos un resultado sobre grandes desvíos (Kifer, Peres y Weiss 2001) para obtener cotas para la medida de los conjuntos con {\it discrepancia} alta. El problema de construir un número que satisfaga ambas formas de normalidad apareció explícitamente en la literatura en 2006. Recientemente, en 2017, Scheerer publicó un algoritmo para tal fin cuya complejidad es doblemente exponencial. El presente trabajo ha sido aceptado para su publicación en International Mathematics Research Notices y está disponible en {\tt \small https:\/arxiv.org/abs/1704.03622}.

Autores: Becher, Verónica / Yuhjtman, Sergio .