Cuando una serie de energía formal es una función racional en disfraz

Question

¿Dada una serie de energía formal $f \in k[[X]]$, donde $k$ es un campo conmutativo, existe alguna buena manera de saber si o no $f\in k(X)$?

Edit: Para aclarar, "buena manera de decir" significa "algoritmo computable para contar".

Edit 2: realmente atornillar esta cuestión, por lo que yo estoy recusing de aceptar una respuesta. Voy a aceptar una respuesta después de un número suficiente de votos ha sido emitido para la mejor respuesta.

Answer 1

Fracciones continuas!

Para motivar esta respuesta, en primer lugar recordar la continuación de la fracción algoritmo para comprobar si un número real es racional. Es decir, dado un número real $r$, reste su suelo,$\lfloor r \rfloor$, tomar el recíproco, y repetir. El número de $r$ es racional si y sólo si en algún punto de restar el piso da $0$.

Por supuesto, una precisión infinita número real no es algo que una máquina de Turing puede examinar plenamente en tiempo finito. En la práctica, la entrada sería sólo una aproximación a un número real, decir especificado por dar el 100 primeros dígitos después del punto decimal. No hay suficiente información dada para determinar si el número es racional, pero aún así tiene sentido preguntar si hasta a la precisión es un número racional de pequeña altura, es decir, con el numerador y el denominador pequeño en relación a la cantidad de precisión dada. Si el número es racional de pequeña altura, uno se dará cuenta de esto cuando computación en la continuación de su fracción numérica, debido a que restar el suelo durante uno de los primeros pasos (antes de los errores compuesto hasta el punto de que dominan los resultados) se le da un número que es muy pequeño en relación a la precisión; la sustitución de este resto, por $0$ en la continuidad de la fracción construida hasta el momento da la pequeña altura de número racional.

¿Cuál es la potencia de la serie analógica? En lugar del campo de los números reales, el trabajo con el campo formal de la serie de Laurent $k((x))$, cuyos elementos son de serie con a lo más un número finito de términos con potencias negativas de $x$: creo que de $x$ por ser pequeña. Para $f = \sum a_n x^n \in k((x))$, definir $\lfloor f \rfloor = \sum_{n \le 0} a_n x^n$; esto es una suma con sólo un número finito distinto de cero términos. Comenzando con $f$, calcula el $f - \lfloor f \rfloor$, tomar el recíproco, y repetir. La serie $f$ es una función racional (en $k(x)$) si y sólo si en algún punto de restar el piso da $0$.

Los mismos advertencias como antes de aplicar. En la práctica, el modelo es que uno tiene exacta de la aritmética de los elementos de $k$ (coeficientes), pero una serie serán especificados sólo parcialmente: tal vez uno se da sólo los 100 primeros términos de $f$, dicen. La única pregunta que usted pueda esperar respuesta es si $f$ es, hasta el da de precisión, igual a una función racional de baja altura (es decir, con el numerador y el denominador de bajo grado). La respuesta se hará evidente cuando la continuación de la fracción se aplica el algoritmo: comprobar si la resta de la planta durante uno de los primeros pasos que da una serie que se inicia con un alto poder positivo de las $x$.

Bonus: como periódico fracciones continuas en el caso clásico corresponden a cuadrática irracionales números reales, periódico fracciones continuas en el caso de la serie de Laurent corresponden a la serie de pertenecer a una ecuación cuadrática de la extensión de $k(x)$, es decir, a la función de campo de un hyperelliptic curva de más de $k$. Abel en 1826 explotado esta idea como un ingrediente en un método para determinar que hyperelliptic integrales puede ser calculada en la escuela primaria!

Answer 2

Si la potencia de la serie corresponde a una función racional o no es independiente de cualquier finito segmento inicial de sus coeficientes; en consecuencia, (como algunos de potencia de la serie son y otros que no están dadas por funciones racionales), uno tiene que saber infinitamente muchos de los coeficientes de la alimentación de la serie con el fin de saber si se está dada por una función racional o no. En la mayoría de los naturales de cuentas de lo que significa para presentar este tipo de series (por ejemplo, como una caja negra que uno puede preguntar por el coeficiente de un índice en particular, o incluso como el código para una máquina de Turing/programa en un lenguaje estándar que produce la secuencia de coeficientes), se sigue que es imposible calcular la respuesta (un cálculo de tomar sólo un número finito de pasos).

Edit: "un cálculo de tomar sólo un número finito de pasos" es suficiente para mostrar la imposibilidad en la caja negra de caso (se necesitaría una infinidad de consultas para establecer los valores de una infinidad de coeficientes). Se me olvidó añadir el razonamiento que cubre la máquina de Turing código caso: si uno tiene un algoritmo, entonces uno podría utilizar para resolver el cese Problema, así: vamos a $I_i$ ser una computable secuencia de coeficientes de la definición de un no-racional de la serie, y deje $Q(p)_i$ 0 si p no parar dentro de i pasos, y $I_i$ lo contrario. El código para una máquina de Turing computing $Q(p)$ puede ser fácilmente (computably) construido a partir de p a sí mismo, y esta máquina está garantizada a la salida de un flujo de infinidad de coeficientes, el resultado de la definición de un racional de la serie si y sólo si p finalmente se detiene. En consecuencia, la undecidability de la detención problema nos da la deseada imposibilidad resultado.

Answer 3

Dada una función de $f(z)= \sum _{k=1}^{\infty} a _kz^{-k}$, es el símbolo de la Hankel operador $$H=\left(a _{i+j-1}\right) _{i,j}$$ Del teorema de Kronecker le dice que $f$ es racional iff $H$ es de rango finito $n$.

A partir de un sistema de la teoría del punto de vista, la posibilidad de recuperación de una función racional $P(z)/Q(z)$ , donde es $Q(z)$ monic, por su MacLaurin de expansión al infinito ha sido ampliamente estudiado como la realización parcial del problema de la teoría de los sistemas. Está íntimamente relacionado a temas tales como el de Berlekamp–Massey algoritmo en el contexto de la teoría de la codificación y filtrado de Kalman.

En la aproximación de la teoría de aproximación de Pade ofertas con aproximación a una función racional, sino como un algoritmo es bastante incómodo.

Por otra parte, un enfoque como el que se toma aquí parece más eficiente. Usted sólo tiene que comprobar la desaparición de las Toeplitz determinantes $D(m,n;u)$ en sólo una coordenada $(m,n)$, aunque esto debe ser hecho por todos los $u$ en una vecindad del origen.

También quería mencionar que la investigación de las funciones racionales no se limita a la analítica de las propiedades, que son cerradas bajo $+$ $\otimes$ (Hadamard producto), pero no con arreglo arbitrario de Hadamard cocientes.El siguiente ha sido probado por van der Poorten. Referencia

("Pisot de la Conjetura") Vamos a $\sum s _n z^n$ $\sum t _n z^n$ dos racional de energía de la serie con coeficientes en un 0-campo de característica de $K$. Si cada $t_n$ es diferente de 0 y no existe un finitely generado anillo sobre $\mathbb{Z}$, $A$ tal que $s _n /t _n \in A$ todos los $n$, entonces el poder de la serie de $\sum (s _n /t _n) z^n$ es racional.

Y parece que hay más de aritmética/estructura algebraica, si familiarizado con los clásicos de los resultados de álgebra de Hopf estructuras usted podría estar interesado en este trabajo: "La estructura algebraica de forma lineal recursiva secuencias en Hadamard producto" R. G. Larson, E. J. Taft.

Answer 4

Como se señaló, la pregunta es si los coeficientes de satisfacer una recursividad lineal. Pero ¿cómo puedes saber eso? Hay un teorema de Kronecker (Lema III en la página 5 del Capítulo 1 de Raphael Salem Algebraicas de los Números y el Análisis de Fourier, publicado por Wadsworth en 1983, publicado originalmente por D a D y C Salud, 1963) que dice que la suma de los infinitos términos de 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 m + 1 matriz en la que la j-ésima fila es c_{j-1}, c_j, ..., c_{m+j-1} para j = 1, ..., m + 1. Así que usted puede calcular los determinantes de diversos m y si usted comienza a recibir los ceros se puede comprender es el momento de empezar a buscar la recurrencia lineal.

Answer 5

Más o menos, por definición, este es el caso, precisamente, cuando los coeficientes de $f$ satisface la recurrencia lineal homogénea con coeficientes en $k$. De forma equivalente, 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 lo que debe hacer y no saben acerca de este problema y cómo $f$ es dado.

Edit: Esto me parece imposible por el Arroz del teorema. Voy a citar el artículo de la Wikipedia:

Supongamos que tenemos un conjunto de idiomas, S. Entonces el problema de decidir si el lenguaje de una máquina de Turing es en S es indecidible, a condición de que no existe una máquina de Turing que reconoce un lenguaje en S y una máquina de Turing que reconoce un idioma que no está en S. de hecho, esto significa que no hay ninguna máquina que pueda siempre correctamente decidir si el lenguaje de una máquina de Turing tiene una determinada propiedad no trivial. Casos especiales incluyen la undecidability de si una máquina de Turing que acepta una cadena de caracteres en particular, si una máquina de Turing se reconoce un determinado lenguaje reconocible, y si el lenguaje reconocido por una máquina de Turing puede ser reconocido por un trivial más simple de la máquina, tales como un autómata finito.

Este problema en particular es en realidad muy de cerca para determinar si una máquina de Turing se reconoce un lenguaje regular.