Título: Discrepancia continua de secuencias de de Bruijn
Directores: Nicolás Álvarez y Verónica Becher
Jurados: Esteban Feuerstein y Martín Mereb

Aula virtual: meet.google.com/xri-tgsx-spy

Resumen:
Una secuencia de de Bruijn de orden n sobre el alfabeto {0,1} es una secuencia circular de longitud 2^n en la que cada bloque de longitud n aparece exactamente una vez. Hay exactamente 2^{2^{n-1}}/2^n de ellas. Una de las propiedades de interés de estas secuencias es cuánto se alejan de tener los bloques de ceros y unos equidistribuidos.

En esta tesis definimos una medida sobre las secuencias de de Bruijn, que llamamos discrepancia continua: cuanto menor es su valor, mejor equidistribuidos están, dentro de la secuencia, los ceros y los unos, los bloques de dos símbolos, los bloques de tres símbolos, y así sucesivamente. Damos un método eficiente, basado en backtracking exhaustivo con poda, para calcular la discrepancia continua de todas las secuencias de de Bruijn de orden hasta 7, y a partir de los resultados conjeturamos cómo crece esta discrepancia en función del orden n.

La motivación de esta medida es una pregunta abierta planteada por Nikolay Korobov en 1955: cuál es la mínima discrepancia, en el sentido clásico de la teoría de la distribución uniforme, que puede alcanzar una secuencia de la forma (2^n x módulo 1), n = 1, 2, 3, …, para un número real x.