Can program be used to simplify algebraic expressions?

Question

We know 1+2+...+n is equal to n(n+1)/2.

But can we get the same result programatically if we don't know it in advance?

About why I have such a question.

Think of a more complex situation:

X1+X2+...+Xk=n, where Xi is integer and >= 0.

What's the Expectation of X1^2+...Xk^2?

The result is not obvious just by a glance, and we'll want to feed it to a program to reduce the algebra once we've worked out the (verbose)mathematical representation of Expectation of X1^2+...Xk^2

Rileyrilievo

Your edit made it rather unclear ... – Uzia

@Uzia ,it's about developing a program that can discover the explicit formula. – Rileyrilievo

I'd suppose that there's no way a program could find closed-form expressions for arbitrary sums. First off, not all sums have closed-form expressions involving only elementary functions. Second, the ability to algorithmically reduce any arbitrary expression sounds dangerously close to being able to algorithmically determine whether a Turing machine halts on an input... I'll think about whether this is true and, if so, whether I can prove it. – Peterec

@Patrick: determining whether an arbitrary arithmetic expression depending on one variable is zero is equivalent to the halting problem. – Weakminded

@Patrick: for integration, there is an algorithm (Risch algorithm) which terminates with the closed form antiderivative (in term of elementary functions) iff it exists. Unfortunately, it needs to decide whether two expressions are equal, which is undecidable. The counterpart in infinite series is Karr's algorithm. – Weakminded

Looks undecidable per Richardson's theorem. en.wikipedia.org/wiki/Richardson%27s_theorem – Touching

Answer 1

Perhaps you're thinking of a Computer algebra system (CAS)? WolframAlpha is a free online one that uses Mathematica (a very powerful CAS system) on it's backend. Here you can see it compute/simplify your expression: WolframAlpha.

Your example is just the sum of squares which has a pretty simple explicit formula: n(n+1)(2n+1)/6. More generally, you can use Faulhaber's formula to calculate Sum of n^p.

Rioux

n(n+1)(2n+1)/6 is for 1^2+2^2+...n^2,my example is a lot more complex than that. – Rileyrilievo

Well you won't be able to get an explicit formula unless you define the sequence X_k. In general, it is sometimes impossible to get a simple closed form expression for such sums. Only simple sums like this can be easily simplified. – Rioux

Can you talk about the algorithm of WolframAlpha, is it just a series of hard code math formulas? – Rileyrilievo

Expectation of X1^2+...Xk^2 has an explicit formula but it's all about math and I won't expand it here as here is about programing. – Rileyrilievo

Mathematica is developed for years. The algorithms it support are numerous and would (and probably do) fill books. You should either use a ready made solution or constraint your problem. – Irritate

No, it actually does symbolic math in the background. CAS is a very advanced topic in computer science and can require years of research to build something non-trivial. To put it into perspective, it took Mathematica 22 years to get to where it is now. I don't think it's something that could be adequately discussed on SO. – Rioux

@Rioux I think it can be discussed here ... #6406506 – Wheelsman

Answer 2

Okay, first some suggestions about the math part of the question and then some about the software development.

There's an e-book "A=B" by Marko Petkov·sek, Herbert S. Wilf and Doron Zeilberger which deals with solving (or showing there is no solution of) summation problems even more difficult than just polynomials. A review of the book by Ian Wanless is worth a quick reading. The e-book is freely downloadable, but bound copies can be purchased, e.g. from Amazon.

A 2004 Trans. of AMS paper Closed Form Summation of C-finite Sequences by Greene and Wilf is also available online.

In general you will need some basic CAS software to implement these algorithms, and it sounds like the goal is to develop such software yourself. I would recommend studying some of the open source CAS (computer algebra software) packages like Maxima or Axiom to get a feel for the scope of what is involved. Of course it's likely that a narrowly targeted application can do with only a fraction of what these fairly mature and high-end packages implement, but I don't feel that I can point you down a more directed path given the current phrasing of the question.

If "Expectation" of expressions is included in the scope of your project, there are a number of complications piled on top of mere algebraically manipulation. One certainly needs to be able to specify probability density functions to support expected values, and presumably some integration software (though potentially limiting the choice of parameterized distributions could lead to a simplified problem of looking up moments of those distributions). I do think this is a particularly nice application to jump into, as seemingly simple expressions (sums, max/min) of random variables can lead to nightmarish consideration of cases, well-suited to the patience of a computer.

Sadiras

OP seems to deal with integer-valued random variables, for which the integrals turn into potentially infinite series. Those are definitely trickier than integrals, but should they be finite, the material you point to could work ("linear combination of hypergeometric series" is actually very broad). – Weakminded

@Alexandre C.: It's a good point that the OP mentioned once restricting to integers. I'm chewing on your comment to Patrick87 that "an arbitrary arithmetic expression depending on one variable" can represent an undecidable problem. AFAIK the diophantine version of this would require more than one variable, but perhaps I've missed recent developments. – Sadiras

I forgot to mention that the variable is real and that you need some usual functions as well. This was written with the Risch theorem in mind (which solves the antiderivative problem provided you can prove such expressions are zero) – Weakminded

Answer 3

EDIT, due to your recent clarification of the post.

You won't get away with a hand made solution, unless you have a whole team of PhDs and several years to spend. The best advice I can give you is to buy a Mathematica (or other) license and interface it with your program.

If you are a Lisp programmer, using Maxima is another potential (free this one) solution.

If you want background on the state of art in summation algorithms, this paper is a good start.

---

X1+X2+...+Xk=n, where Xi is integer and >= 0.

What's the Expectation of X1^2+...Xk^2?

This kind of problems occupy a lot of people to figure out how to do it on paper.

Let us take k = 2. Then X_1 + X_2 = n gives X_2 = n - X_1.

So the expectation to be computed is E = X_1^2 + (n - X_1)^2 = 2 X_1^2 -2n X_1 + n^2.

This reads

E = sum(p_k * (2 * k^2 - 2 * n * k + n^2), k = 0..infinity)

where p_k = Prob(X_1 = k). This kind of sums, depending on p_k, is generally very difficult to compute. I'd say that the problem is even more difficult than computing integrals in closed form (for which no software fully implement the available -- but undecidable -- Risch algorithm).

To convince yourself, take eg. p_k = 1 / (log(k) * k^4).

Finding a formula (or a formula generator) for it is at the very least a very difficult research problem.

Weakminded

K is not infinity,but a fixed constant.+1, as this is the only answer that tackle on some details, others are all talking about the history/story of symbolic algebra which I'm not asking about. – Rileyrilievo

@Je Rog: Then finite summation algorithms can be explained in this book. Nonetheless, you're better not implement this yourself (unless you happen to have a lot of free time) – Weakminded

I don't want to implement it myself, but do want to understand the principle how it's implemented, not just stories/history. – Rileyrilievo