Positivity of Nearly Linearly Recurrent Sequences

Título: Positividad de Secuencias Casi Linealmente Recurrentes

1. El Problema: La Positividad de Secuencias Casi Linealmente Recurrentes (NLRS)

El artículo aborda el Problema de Positividad para un tipo generalizado de secuencias llamadas Secuencias Casi Linealmente Recurrentes (NLRS, por sus siglas en inglés).

• Definición: Una NLRS de orden $d$ es una secuencia de números racionales $(u_n)_{n=0}^{\infty}$ que satisface un sistema de desigualdades:
  $$\varepsilon_0 \le u_{n+d} - a_{d-1}u_{n+d-1} - \dots - a_0 u_n \le \varepsilon_1$$
  donde $a_i$ y $\varepsilon_0, \varepsilon_1$ son constantes racionales ($a_0 \neq 0$).
• Generalización:
  • Si $\varepsilon_0 = \varepsilon_1 = 0$, se recupera una Secuencia Linealmente Recurrente (LRS) clásica.
  • Si $\varepsilon_0 = \varepsilon_1$, es una LRS inhomogénea.
  • En el caso general, representan LRS sujetas a perturbaciones acotadas en cada paso.
• Contexto: Este problema es un caso especial del problema de no alcanzabilidad en sistemas lineales invariantes en el tiempo (LTI) y en bucles de restricciones lineales.
• Objetivo: Dado un sistema de recurrencia y condiciones iniciales, determinar si todas las secuencias que satisfacen la recurrencia permanecen no negativas ($u_n \ge 0$) para todo $n \in \mathbb{N}$.
• Desafío: El problema de positividad para LRS clásicas (orden arbitrario) es un problema abierto hace 50 años. Para NLRS, la no determinismo introducido por las perturbaciones ($\varepsilon_0, \varepsilon_1$) hace que el análisis algorítmico sea aún más complejo.

2. Metodología y Enfoque Técnico

Los autores desarrollan un procedimiento de decisión para el caso de orden dos ($d=2$). La metodología se divide en tres fases principales:

A. Formulación Matricial y Reducción a un Problema de Control

• Se reformula la recurrencia como un sistema LTI discreto: $x_{n+1} = A x_n + r_n e_1$, donde $r_n \in [\varepsilon_0, \varepsilon_1]$ actúa como un control no determinista.
• El problema de positividad se reduce a verificar si la solución del sistema permanece en un semiespacio ($e_d^\top x \ge 0$) para todas las posibles secuencias de controles.
• Utilizando el principio "bang-bang" (en control óptimo, el mínimo se alcanza en los extremos del intervalo de control), se demuestra que para verificar la positividad de todas las secuencias, basta con analizar la secuencia que minimiza la suma de los términos. Esto convierte el problema en el análisis de una secuencia específica $u^{(min)}_n$.

B. Análisis de Casos Espectrales
Para el caso de orden 2, la matriz $A$ tiene dos autovalores complejos conjugados $\lambda, \bar{\lambda}$. El procedimiento clasifica el comportamiento según el radio espectral $|\lambda|$:

1. Radio espectral > 1: La secuencia tiende a $-\infty$ (no positiva).
2. Radio espectral = 1: La suma de los términos absolutos diverge, llevando a la negatividad.
3. Radio espectral < 1: La secuencia converge a un límite. El problema se reduce a determinar si este límite es cero o no, y si es positivo.

C. El Núcleo Teórico: Resultados de Transcendencia
El caso crítico es cuando $|\lambda| < 1$. El límite de la secuencia minimizada depende de una serie infinita de la forma:
$$\alpha = \sum_{n=0}^{\infty} |a\lambda^n + \bar{a}\bar{\lambda}^n|$$
Los autores demuestran que $\alpha$ es un número trascendente (no es raíz de ningún polinomio con coeficientes enteros) bajo ciertas condiciones (que $\lambda^n$ no sea real para $n>0$).

• Implicación: Si $\alpha$ es trascendente, no puede ser cero. Por lo tanto, el límite de la secuencia es estrictamente no nulo. Esto permite determinar el signo del límite mediante cálculos numéricos de precisión finita.

D. Herramientas Matemáticas Avanzadas
La prueba de trascendencia es la contribución técnica más profunda y combina:

1. Aproximación Diofántica: Uso de expansiones en fracciones continuas del argumento de $\lambda$ para construir recurrencias lineales de orden creciente que aproximan la secuencia de valores absolutos.
2. Teorema del Subespacio (Subspace Theorem): Una generalización multidimensional del Teorema de Roth (Schlickewei), utilizado para encontrar relaciones lineales entre potencias de $\lambda$.
3. Teorema de Baker: Se utiliza para establecer cotas inferiores en formas lineales de logaritmos, lo que permite demostrar que la serie no puede converger a cero si se asume que es algebraica, generando una contradicción.

3. Contribuciones Clave

1. Procedimiento de Decisión para Orden 2: El primer algoritmo que decide la positividad para secuencias casi linealmente recurrentes de orden dos, incluso con constantes algebraicas reales.
2. Nuevo Resultado de Transcendencia: Demostración de que la serie infinita $\sum |a\lambda^n + \bar{a}\bar{\lambda}^n|$ es trascendente cuando $|\lambda| < 1$ y $\lambda$ no es real. Este resultado es de interés independiente en teoría de números.
3. Conexión Interdisciplinaria: Establece un puente sólido entre la teoría de sistemas de control (LTI), la teoría de autómatas y la teoría de números (transcendencia y aproximación diofántica).

4. Resultados Principales

• Teorema 1: El Problema de Positividad para NLRS de orden 2 es decidible.
• Teorema 2 (Transcendencia): Bajo las condiciones de orden 2 y radio espectral < 1, la suma de los valores absolutos de la secuencia es un número trascendente.
• Algoritmo: El procedimiento termina verificando si el límite de la secuencia minimizada es positivo (calculado numéricamente) y comprobando un número finito de términos iniciales.

5. Significado e Impacto

• Avance en Problemas Abiertos: Mientras que el problema de positividad para LRS generales sigue abierto, este trabajo resuelve una generalización natural (con perturbaciones) para un caso de dimensión baja, demostrando que la no determinismo no impide la decidibilidad en este contexto específico.
• Aplicaciones en Verificación de Programas: Las NLRS modelan bucles con restricciones lineales y abstracciones de tamaño de datos. La decidibilidad de la positividad es crucial para la verificación de terminación de programas y el análisis de bucles no deterministas.
• Limitaciones y Futuro:
  • El enfoque actual depende fuertemente del principio "bang-bang", lo que lo hace aplicable a la variante "universal" (todas las secuencias son positivas).
  • La variante "existencial" (¿existe alguna secuencia positiva?) es más difícil porque el principio "bang-bang" no aplica directamente, requiriendo técnicas diferentes.
  • Extender el resultado a orden 3 o superiores presenta desafíos significativos, especialmente en la construcción de las aproximaciones diofánticas y la aplicación del Teorema del Subespacio.

En resumen, el artículo presenta una solución elegante y profunda para un problema de decisión complejo en sistemas dinámicos, utilizando herramientas avanzadas de teoría de números para superar las barreras algorítmicas impuestas por la no determinismo.