Supongamos que $f,g$ son funciones racionales con coeficientes enteros tales que $\sum_{n=0}^{\infty}f(n)$ e $\sum_{n=0}^{\infty}g(n)$ ambos convergen. Es decidable si $\sum_{n=0}^{\infty}f(n)=\sum_{n=0}^{\infty}g(n)$? Si este problema es decidable, entonces, ¿qué es la complejidad computacional de este problema? Si este problema es indecidible, entonces ¿cuál es el grado de turing de este problema? Yo también estoy interesado en las respuestas relativas a las generalizaciones de este problema, como cuando vamos a tomar el doble de las sumas o cuando se incluyen las factorial de las funciones exponencial y funciones. Esta pregunta no tiene mucho que ver con mi investigación actual. En su lugar, principalmente estoy interesado en esta cuestión de curiosidad.
Respuesta
¿Demasiados anuncios?
Parece bastante claro que este es un problema abierto, así que voy a hacer el trabajo de (intentar) hacer esta pregunta de su miseria con un resumen de algunos de los comentarios en los comentarios. Esta respuesta es la wiki de la comunidad.
La sustitución de $f(n)$ por $f(n)-g(n)$, uno se puede preguntar si la suma es cero o no.
Variaciones: Supongamos que uno hace la restricción de que el $f(n)$ es una incluso de la función, o, alternativamente, (y casi de forma equivalente) considerar la posibilidad de sumatorias de $-\infty$ a $\infty$. A continuación, el grado de $f(n)$ debe ser en la mayoría de las $-2$, y que una de ellas (teniendo en $R$ a través de una secuencia de la mitad de los números enteros y $C_R$ el correspondiente círculo centrado en cero):
$$0 = \lim_{R \rightarrow \infty} \frac{1}{2 \pi i} \oint_{C_R} \frac{\pi \cos \pi z}{\sin \pi z} f(z) dz = \sum_{-\infty}^{\infty} f(n) + \sum_{f(\alpha) = \infty} \pi \cuna(\pi \alpha) \mathrm{Res}(f)(\alpha)$$ Literalmente hablando, esto sólo es correcto si $f(z)$ sencilla polos, pero el caso general no es más difícil. De ello se deduce que la determinación de si la suma es igual a cero o no es la misma como la verificación de una identidad en $$\overline{\mathbf{Q}}(e^{\pi \beta_1}, \ldots, e^{\pi \beta_n}),$$ para un conjunto fijo de números algebraicos $\beta_i$. Por Schanuel la conjetura, la única de esas relaciones son el "obvio", por lo que en este caso uno conjecturally dispone de un algoritmo.
Períodos: Pasando ahora a la general (no) caso pero que se especializa en una dirección diferente: para ciertos especial $f(n)$, la suma en cuestión es un periodo (por ejemplo, $\zeta(n)$ para $n \ge 2$ un entero). Kontsevich y Zagier plantear la cuestión de si la determinación de la igualdad de los dos períodos es decidable o no; la expectativa es que debería ser, pero no hay ideas en esta dirección. Existen, sin duda, no se conocen algoritmos generales para la comprobación de la igualdad.
Observaciones generales: Mediante la expansión en fracciones parciales, se tiene la fórmula general: $$\sum f(n) = \sum_{n=0}^{\infty} \sum_{r,s} \frac{(-1)^r \cdot r! \cdot A_{r,s}}{(n + \alpha_s)^{i+1}} = \sum_{r,s} A_{r,s} \cdot \psi^{(r)}(\alpha_i),$$ Donde $\psi^{(r)}(z)$ es el Polygamma función, por lo $\psi^{(0)}(z) = \psi(z)$ es la derivada logarítmica de la función Gamma. Tenga en cuenta que esto sólo tiene sentido cuando uno tiene la convergencia, lo que ocurre si y sólo si $\sum A_{0,s} = 0$ (esto también significa que nadie puede reemplazar a $\psi(z)$ por $\psi(z) + \gamma$ si quieres). Explícitamente, para aquellos que se preocupan esas cosas, la $r=0$ plazo puede ser escrito (ya $\sum A_{0,s} = 0$) como: $$\sum_{n=0}^{\infty} \sum_{s} \frac{A_{0,s}}{(n + \alpha_s)} = \sum_{n=0}^{\infty} \sum_{s} \frac{A_{0,s}}{(n + \alpha_s)} - \frac{A_{0,s}}{n+1} = \sum_{s} A_{0,s} (\psi(\alpha_s) - \psi(1)) = \sum_s A_{0,s} \psi(\alpha_s)$$
Las funciones de $\psi^{(r)}(z)$ también puede ser pensado como una zeta de Hurwitz funciones. La mayoría de los generales de la esperanza sería que las únicas relaciones entre los valores de polygamma de las funciones algebraicas argumentos son los que se están produciendo para "motivic" razones. No hay mucho para motivar a este más allá de los relacionados con explicaciones (que ya son conjeturas) en el más fácil de los casos discutidos anteriormente.
