3
$\begingroup$

The question is: I give the computer a sum, such as $\sum_{n=1}^\infty\frac{1}{n^3}$, the computer is expected to return an elegant closed-form solution, because the answer may be irrational. Has this problem been solved using a computer? Or, has it been proved to be undecidable? Or is it open?

$\endgroup$
4
  • 1
    $\begingroup$ What kind of sums are you expecting as input? Just powers of $n$? Any rational functions? $\endgroup$
    – Curtis F
    Jul 31 '19 at 6:34
  • $\begingroup$ @CurtisF Anything is what I have in mind, because I know little about series and their properties and so it might be stupid to ask. Anyway, be as general as possible, while the individual terms do follow a pattern. What’s known about this problem? $\endgroup$
    – Zirui Wang
    Jul 31 '19 at 6:38
  • 6
    $\begingroup$ Your question seems to be, essentially, "Do computer algebra systems exist?" Yes, they do. $\endgroup$ Jul 31 '19 at 11:20
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ Aug 1 '19 at 7:02
2
$\begingroup$

It's complicated. Some very broad classes have been solved completely, but that's still one way of saying that it's only been done for special cases. The book A=B by Wilf, Zeilberger and Petrovšek would probably interest you: it describes algorithms for some of these broad classes.

$\endgroup$
2
  • $\begingroup$ One quick question: Does their algorithm work for sums whose values are irrational? For example, $$\sum_{k=1}^\infty\frac{(-1)^{k+1}}{2k-1}=\frac{\pi}{4}.$$ I wonder how the computer can figure out whether a value equals, say, $\pi$ or $\sqrt2$, which have infinite precision. This is the most puzzling part of my question. In what I know, the method to deal with real numbers is by reasoning or deduction and not by calculation. That's why we infrequently see real numbers in CS. But infinite sums involve real numbers and seem to contradict our current wisdom. Could that be why it's undecidable? $\endgroup$
    – Zirui Wang
    Jul 31 '19 at 9:57
  • 2
    $\begingroup$ Roughly speaking, the algorithms described will find solutions which are "similar" (in a precise sense) to the terms of the sum. They won't pull powers of $\pi$ out of thin air. I suspect that computer algebra systems which can evaluate the example sum in the question work by transforming it to a sum which they have in a database of known sums. $\endgroup$ Jul 31 '19 at 10:08
1
$\begingroup$

In the general case, this is undecidable, and it turns out the answer has nothing to do with being rational or irrational.

Consider a Turing Machine with state set $Q$ with a single halting state $H$. Let's define $isHalting(H) = 1$ and $isHalting(q) = 0 $ for $q \neq H$. Define $state(n,w)$ to be the state of the Turing Machine starting on input $w$ after $n$ steps.

Then consider the infinite sum $\sum_{n=1}^\infty isHalting(state(n,w))$. If this sum is $0$, then the Turing Machine does not halt. If it's $\infty$ then the machine halts.

Now, if you're skeptical about the $state$ and $isHalting$ functions, that's fair, but it turns out that you can encode these steps, or any logical formula, in arithmetic using something called Gödel numbering.

So even without using any irrational numbers, it's undecidable to determine not only the result of an infinite sum, but just whether that sum is 0 or not.

Of course, like @PeterTaylor says, there are plenty of specific cases where you can compute it, and this is one thing thefield of computer algebra is trying to determine. But this is normal for undecidable problems: there are also plenty of specific times that we can figure out whether a given Turing Machine halts, or whether a program has a given property, etc.

$\endgroup$
0
0
$\begingroup$

There is a closed form solution if and only if the exponent is an even integer.

$\endgroup$
2
  • $\begingroup$ My question is about the most general case. One over n cube is just an example. Has the general problem been solved? But you indeed taught me something I didn’t know, thanks. $\endgroup$
    – Zirui Wang
    Jul 31 '19 at 6:30
  • $\begingroup$ @scaaahu The "if and only if" claim applies only to infinite sums of the form $\sum_{n=1}^\infty 1/n^c$ for positive integers $c$. The question isn't restricted to such sums. $\endgroup$ Jul 31 '19 at 12:32
-3
$\begingroup$

Given a general infinite series, the most a computer can do is calculate the partial sums (the sum of the first thousand terms or the first million terms, for example). And even then it can only calculate the approximate values of those partial sums, to some finite degree of precision.

Showing that an infinite series converges to some closed-form expression (such as

$\displaystyle \lim_{k \rightarrow \infty} \sum_{n=1}^k \frac{1}{n^2}= \frac{\pi^2}{6}$

for example) can only proved by mathematical reasoning. We do not know how to create a computer algorithm that will originate that reasoning (although a proof-checking algorithm could possibly validate the proof once it was found).

At best, a program can compare the partial sums of the series to values of combinations and functions of mathematical constants such as $\pi$, $e$ or $\sqrt{2}$ and suggest a closed-form solution if it finds a close match. This field of research is called experimental mathematics.

$\endgroup$
6
  • $\begingroup$ This is consistent with my understanding. (Thus +1). But, why do I remember there is indeed a theorem pointed out by gnasher729. Please see his answer Do you recall anything like that? Thanks for your attention. $\endgroup$
    – Nobody
    Jul 31 '19 at 11:19
  • $\begingroup$ @scaaahu The result mentioned by gnasher729 "There is a closed form solution if and only if the exponent is an even integer" refers specifically to the known closed-form values for the Riemann zeta function. The original question was asking about infinite series in general and was only using $\zeta(2)$ as an example. $\endgroup$
    – gandalf61
    Jul 31 '19 at 11:29
  • 1
    $\begingroup$ "At best, a program can compare the partial sums of the series to values of combinations and functions of mathematical constants such as $\pi$, $e$ or $\sqrt{2}$ and suggest a closed-form solution if it finds a close match." I don't think this follows from the previous sentence. Yes, any algorithm that the computer will employ will be based on some clever mathematical insight, which as of now computers are unable to provide. That, however, does not mean that these algorithms cannot be stored and effectively matched automatically to solve many actual inputs in practice, as CAS in fact do. $\endgroup$
    – Discrete lizard
    Jul 31 '19 at 11:32
  • $\begingroup$ A computer does not know approximate values of real numbers any more “natively” than it knows symbolic expressions. It is not necessarily easier to program a computer to report an approximate value of $\sum\limits_n \dfrac{1}{n^2}$ than to report the exact value. $\endgroup$ Jul 31 '19 at 16:38
  • $\begingroup$ @Giles A computer can only report that $\sum\limits_n \dfrac{1}{n^2} = \frac{\pi^2}{6}$ if it is already given that statement or some logically equivalent statement. And it cannot print an exact value for $\frac{\pi^2}{6}$ because it is irrational. How would you write a program to report the exact value of $\sum\limits_n \dfrac{1}{n^3}$ ? This limit definitely exists but we don't know how to express it in a closed form. On the other hand, writing a program to calculate partial sums to any required degree of precision is trivial. $\endgroup$
    – gandalf61
    Aug 1 '19 at 11:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.