Dada una serie formal de potencias $f \in k[[X]]$ , donde $k$ es un campo conmutativo, ¿hay alguna buena manera de saber si $f\in k(X)$ ?
Edición: Para aclarar, "buena forma de decirlo" significa "algoritmo computable para decirlo".
Edición 2: He metido la pata en esta pregunta, así que me abstengo de aceptar una respuesta. Aceptaré una respuesta después de que se haya emitido un número suficiente de votos para la mejor respuesta.
¡Fracciones continuas!
Para motivar esta respuesta, primero hay que recordar el algoritmo de la fracción continua para comprobar si un número real es racional. En concreto, dado un número real $r$ , restar su suelo $\lfloor r \rfloor$ , toma el recíproco, y repite. El número $r$ es racional si y sólo si en algún momento al restar el suelo se obtiene $0$ .
Por supuesto, un número real de precisión infinita no es algo que una máquina de Turing pueda examinar completamente en tiempo finito. En la práctica, la entrada sería sólo una aproximación a un número real, digamos que se especifica dando los primeros 100 dígitos después del punto decimal. Ya no hay suficiente información para determinar si el número es racional, pero sigue teniendo sentido preguntar si hasta la precisión dada es un número racional de poca altura es decir, con numerador y denominador pequeños en relación con la cantidad de precisión dada. Si el número es racional de pequeña altura, uno se dará cuenta de ello al calcular numéricamente su fracción continua, porque al restar el suelo durante uno de los primeros pasos (antes de que los errores se agraven hasta el punto de dominar los resultados) se obtendrá un número que es extremadamente pequeño en relación con la precisión; al sustituir este resto por $0$ en la fracción continua construida hasta ahora da el número racional de altura pequeña.
¿Cuál es el análogo de la serie de potencias? En lugar del campo de los números reales, trabaja con el campo de las series formales de Laurent $k((x))$ cuyos elementos son series con a lo sumo un número finito de términos con potencias negativas de $x$ : piensa en $x$ como si fuera pequeño. Para $f = \sum a_n x^n \in k((x))$ , defina $\lfloor f \rfloor = \sum_{n \le 0} a_n x^n$ Esta es una suma con sólo un número finito de términos no nulos. Empezando por $f$ , computa $f - \lfloor f \rfloor$ , toma el recíproco, y repite. La serie $f$ es una función racional (en $k(x)$ ) si y sólo si en algún momento al restar el suelo se obtiene $0$ .
Se aplican las mismas advertencias que antes. En la práctica, el modelo es que se tiene aritmética exacta para los elementos de $k$ (los coeficientes), pero una serie se especificará sólo parcialmente: tal vez se den sólo los 100 primeros términos de $f$ digamos. La única pregunta que puede esperar responder es si $f$ es, hasta la precisión dada, igual a una función racional de baja altura (es decir, con numerador y denominador de bajo grado). La respuesta se hará evidente cuando se aplique el algoritmo de la fracción continua: compruebe si al restar el piso durante uno de los primeros pasos se obtiene una serie que comienza con una potencia positiva alta de $x$ .
Bonificación: Así como las fracciones continuas periódicas en el caso clásico corresponden a números reales irracionales cuadráticos, las fracciones continuas periódicas en el caso de las series de Laurent corresponden a series que pertenecen a una extensión cuadrática de $k(x)$ es decir, al campo de funciones de una curva hiperelíptica sobre $k$ . En 1826, Abel explotó esta idea como ingrediente de un método para determinar qué integrales hiperelípticas podían calcularse en términos elementales.
Dada una función $f(z)= \sum _{k=1}^{\infty} a _kz^{-k}$ es el símbolo de la Operador de Hankel $$H=\left(a _{i+j-1}\right) _{i,j}$$ El teorema de Kronecker dice que $f$ es racional si $H$ es de rango finito $n$ .
Desde el punto de vista de la teoría de sistemas, la posibilidad de recuperar una función racional $P(z)/Q(z)$ , donde es $Q(z)$ mónico, por su expansión de MacLaurin en el infinito ha sido ampliamente estudiado como el problema de realización parcial de la teoría de sistemas. Está íntimamente relacionado con temas como el algoritmo de Berlekamp-Massey en el contexto de la teoría de la codificación y el filtrado de Kalman.
En la teoría de la aproximación Aproximación de Pade se ocupa de la aproximación a una función racional, pero como algoritmo es bastante inconveniente.
Por otro lado, un enfoque como el adoptado aquí parece más eficiente. Sólo hay que comprobar la desaparición de los determinantes de Toeplitz $D(m,n;u)$ en una sola coordenada $(m,n)$ aunque esto debe hacerse para todos $u$ en una zona cercana al origen.
También quería mencionar que la investigación de las funciones racionales no se limita a las propiedades analíticas, son cerradas bajo $+$ y $\otimes$ (producto Hadamard) pero no bajo cocientes Hadamard arbitrarios.Lo siguiente ha sido demostrado por van der Poorten. Referencia
("Conjetura de Pisot") Sea $\sum s _n z^n$ y $\sum t _n z^n$ sean dos series de potencias racionales con coefficientes en un campo característico 0 $K$ . Si cada $t_n$ es differente de 0 y existe un anillo generado finitamente sobre $\mathbb{Z}$ , $A$ tal que $s _n /t _n \in A$ para todos $n$ entonces la serie de potencias $\sum (s _n /t _n) z^n$ es racional.
Y parece que hay más estructura aritmética/algebraica, si está familiarizado con los resultados clásicos sobre las estructuras del álgebra de Hopf podría estar interesado en este documento: "The algebraic structure of linearly recursive sequences under Hadamard product" R.G. Larson, E.J. Taft.
Que una serie de potencias corresponda o no a una función racional es independiente de cualquier segmento inicial finito de sus coeficientes; en consecuencia, (como algunas series de potencias están y otras no están dadas por funciones racionales), hay que conocer infinitos coeficientes de la serie de potencias para saber si está dada por una función racional o no. En la mayoría de las descripciones naturales de lo que significa presentar una serie de este tipo (por ejemplo, como una caja negra a la que se puede consultar el coeficiente en un índice concreto, o incluso como el código de una máquina/programa de Turing en un lenguaje estándar que produce la secuencia de coeficientes), se deduce que es imposible calcular la respuesta (un cálculo que sólo requiere un número finito de pasos).
Edito: "un cálculo que sólo requiere un número finito de pasos" es suficiente para demostrar la imposibilidad en el caso de la caja negra (se necesitarían infinitas consultas para establecer los valores de infinitos coeficientes). Se me olvidó añadir el razonamiento que cubre el caso del código de la máquina de Turing: si se tuviera un algoritmo de este tipo, entonces se podría utilizar para resolver el Problema de la Parada, así: dejemos que $I_i$ sea una corriente de coeficientes computable que define una serie no racional, y sea $Q(p)_i$ sea 0 si p se detiene en i pasos, y $I_i$ de lo contrario. El código de una máquina de Turing que computa $Q(p)$ puede construirse fácilmente (de forma computable) a partir de la propia p, y se garantiza que esta máquina produce un flujo de infinitos coeficientes, cuyo resultado define una serie racional si y sólo si p se detiene finalmente. En consecuencia, la indecidibilidad del problema de parada da el resultado de imposibilidad deseado.
Como se ha señalado la cuestión es si los coeficientes satisfacen una recursión lineal. ¿Pero cómo se sabe eso? Hay un teorema de Kronecker (es el Lemma III en la página 5 del capítulo 1 de Raphael Salem, Números algebraicos y análisis de Fourier publicado por Wadsworth en 1983, originalmente publicado por D C Heath, 1963) que dice $\sum c_n z^n$ es una función racional si y sólo si el determinante de $\Delta_m$ es cero para todos los $m$ suficientemente grande, donde $\Delta_m$ es un $(m + 1)\times(m + 1)$ matriz en la que el $j$ -la fila es $c_{j-1}, c_j, ..., c_{m+j-1}$ para $j = 1, ..., m + 1$ . Así que puedes calcular los determinantes de varios $m$ y si empiezas a obtener ceros puedes imaginar que es hora de empezar a buscar esa recurrencia lineal.
Más o menos por definición este es el caso precisamente cuando los coeficientes de $f$ satisface una recurrencia lineal homogénea con coeficientes en $k$ . Equivalentemente, los coeficientes de $f$ son una combinación lineal de términos de la forma $n^r \lambda^n, \lambda \in \bar{k}, r \in \mathbb{Z}_{\ge 0}$ . Pero no me queda claro qué es lo que sabe y lo que no sabe sobre este problema y cómo $f$ se da.
Editar: Esto me parece imposible por el teorema de Rice. Voy a citar el artículo de Wikipedia:
Supongamos que tenemos un conjunto de lenguajes S. Entonces el problema de decidir si el lenguaje de una máquina de Turing dada está en S es indecidible, siempre que exista una máquina de Turing que reconozca un lenguaje en S y una máquina de Turing que reconozca un lenguaje que no esté en S. Efectivamente, esto significa que no hay ninguna máquina que pueda decidir siempre correctamente si el lenguaje de una máquina de Turing dada tiene una propiedad particular no trivial. Los casos especiales incluyen la indecidibilidad de si una máquina de Turing acepta una cadena particular, si una máquina de Turing reconoce un lenguaje particular reconocible, y si el lenguaje reconocido por una máquina de Turing podría ser reconocido por una máquina más simple no trivial, como un autómata finito.
Este problema en particular está muy cerca de determinar si una máquina de Turing reconoce un lenguaje regular.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
