# Are sums of sequences decidable?

Suppose that $f,g$ are rational functions with integer coefficients such that $\sum_{n=0}^{\infty}f(n)$ and $\sum_{n=0}^{\infty}g(n)$ both converge. Is it decidable whether $\sum_{n=0}^{\infty}f(n)=\sum_{n=0}^{\infty}g(n)$? If this problem is decidable, then what is the computational complexity of this problem? If this problem is undecidable, then what is the turing degree of this problem? I am also interested in answers concerning generalizations of this problem such as when we take double sums or when we include factorial functions and exponential functions as well. This question does not have much to do with my current research. Instead, I am mainly interested in this question out of curiosity.

-
To decide this, one would need to know whether numbers such as $\zeta(5)/\zeta(3)$ are rational. In fact, via partial fractions, and Euler-Maclaurin formula this problem is reduces to deciding whether linear combinations of incomplete zeta function are zero or not. – Boris Bukh Jun 9 '13 at 22:13
Boris, would you care to explain the reduction? – François G. Dorais Jun 10 '13 at 0:06
This is almost exactly equality testing on the real numbers, which is known to be undecidable. In brief, we usually effectively represent a real number as a function computing a sequence (for instance, a sequence of shrinking intervals that converge to that number). Your series representation is almost exactly equivalent. Given two such representations, equality is undecidable; not sure about the Turing degree. For a reference, maybe the wikipedia page: en.wikipedia.org/wiki/Computable_analysis and "Intro to computable analysis": eccc.hpi-web.de/resources/pdf/ica.pdf. – usul Jun 10 '13 at 4:28
@usul I don't think this is nearly as hard as equality testing on the real numbers, the form of the sum is very special. – David Speyer Jun 10 '13 at 13:19
@D K : Take an arbitrary rational function $g$ such that $g(0)=0$ and $g(x) \to 0$ when $x \to \infty$, and consider its discrete derivative $f(x)=g(x+1)-g(x)$. Then $\sum_{n=0}^{\infty} f(n)=0$. – François Brunault Jun 10 '13 at 15:29

It seems pretty clear that this is an open problem, so I will do the job of (trying to) put this question out of its misery by summarizing a few of the remarks in the comments. This answer is community wiki.

Replacing $f(n)$ by $f(n)-g(n)$, one may as well ask whether the sum is zero or not.

Variations: Suppose one makes the restriction that $f(n)$ is an even function, or alternatively (and almost equivalently) consider summations from $-\infty$ to $\infty$. Then the degree of $f(n)$ must be at most $-2$, and one has (taking $R$ through a sequence of half integers and $C_R$ the corresponding circle centered at zero):

$$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 \cot(\pi \alpha) \mathrm{Res}(f)(\alpha)$$ Literally speaking, this is only correct if $f(z)$ has simple poles, but the general case is no more difficult. It follows that determining whether the sum is equal to zero or not is the same as verifying an identity in $$\overline{\mathbf{Q}}(e^{\pi \beta_1}, \ldots, e^{\pi \beta_n}),$$ for a fixed set of algebraic numbers $\beta_i$. By Schanuel's conjecture, the only such relationships are the "obvious" ones, so in this case one conjecturally has an algorithm.

Periods: Passing now to the general (no longer even) case but specializing in a different direction: for certain special $f(n)$, the sum in question is a period (e.g. $\zeta(n)$ for $n \ge 2$ an integer). Kontsevich and Zagier raise the question whether determining the equality of two periods is decidable or not; the expectation is that it should be, but there are no real ideas in this direction. There certainly are no known general algorithms for proving equalities.

General Remarks: By expanding into partial fractions, one has the general formula: $$\sum f(n) = \sum_{n=0}^{\infty} \sum_{r,s} \frac{(-1)^r \cdot r! \cdot A_{r,s}}{(n + \alpha_s)^{r+1}} = \sum_{r,s} A_{r,s} \cdot \psi^{(r)}(\alpha_i),$$ Where $\psi^{(r)}(z)$ is the Polygamma function, so $\psi^{(0)}(z) = \psi(z)$ is the logarithmic derivative of the Gamma function. Note that this only makes sense when one has convergence, which happens if and only if $\sum A_{0,s} = 0$ (this also means one can replace $\psi(z)$ by $\psi(z) + \gamma$ if you wish). Explicitly, for those who worry about such things, the $r=0$ term can be written (since $\sum A_{0,s} = 0$) as: $$\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)$$

The functions $\psi^{(r)}(z)$ can also be thought of as Hurwitz zeta functions. The most general hope would be that the only relationships between values of polygamma functions at algebraic arguments are those which are occurring for "motivic" reasons. There's not much to motivate this beyond the related explanations (which are already conjectures) in the easier cases discussed above.

-