Issue 3128 in sympy: Sum and Product manipulations

[sy...@googlecode.com]

Status: Accepted
Owner: ----
Labels: Type-Enhancement Priority-Medium Concrete

New issue 3128 by asme...@gmail.com: Sum and Product manipulations
http://code.google.com/p/sympy/issues/detail?id=3128

In a similar vein to issue 2297, we should have functions to make it easy
to combine and generally manipulate summations and products. Examples
would be

- Addition of two sums with the same limits
- Addition of two sums with different limits (like Sum(i, (i, 0, k)) +
Sum(i, (i, k, m)))
- Change of index
- Product of Sums
- Reorder multiple sums or products
- Reverse order of limits
- The inverse of any of the above rules

[sy...@googlecode.com]

Comment #2 on issue 3128 by thilina....@gmail.com: Sum and Product
manipulations
http://code.google.com/p/sympy/issues/detail?id=3128

I would like to work on this. Could someone tell me what needs to be done
precisely?
Does this require me to implement supporting functions for summation so
that internal calculations can be made simple or implement separate methods
to get the above work done?

--
You received this message because this project is configured to send all
issue notifications to this address.
You may adjust your notification preferences at:
https://code.google.com/hosting/settings

[sy...@googlecode.com]

Comment #3 on issue 3128 by asme...@gmail.com: Sum and Product
manipulations
http://code.google.com/p/sympy/issues/detail?id=3128

I'm not sure what the API should look like, but it should be user-level.

[sy...@googlecode.com]

Comment #4 on issue 3128 by thilina....@gmail.com: Sum and Product
manipulations
http://code.google.com/p/sympy/issues/detail?id=3128

@asmeurer: I am currently working on this. Could you explain me further what
"Change of index" and "Reorder multiple sums or products" mean?

[sy...@googlecode.com]

Comment #5 on issue 3128 by asme...@gmail.com: Sum and Product
manipulations
http://code.google.com/p/sympy/issues/detail?id=3128

Change of index means making a substitution on the index variable, like n
-> n + 1. Reordering means changing something like Sum(expr, (i, 1, n), (j,
1, m)) to Sum(expr, (j, 1, m), (i, 1, n)), which is more complicated if n
is replaced with something that depends on j.

[sy...@googlecode.com]

Comment #6 on issue 3128 by thilina....@gmail.com: Sum and Product
manipulations
http://code.google.com/p/sympy/issues/detail?id=3128

Thanks for the reply. Is it valid to assume that change of index is
always a shift by a constant? We don't normally do changes like n -> 2*n
since then the new `n` will not be an Integer?

[sy...@googlecode.com]

Comment #7 on issue 3128 by asme...@gmail.com: Sum and Product
manipulations
http://code.google.com/p/sympy/issues/detail?id=3128

It is if n appears as 2*n everywhere. But if it simplifies the code, you
can start a simple version with that assumption, and we can work off it. It
probably should be modeled after Integral.transform.

[sy...@googlecode.com]

Comment #8 on issue 3128 by thilina....@gmail.com: Sum and Product
manipulations
http://code.google.com/p/sympy/issues/detail?id=3128

Thanks for the reply Aaron.

[sy...@googlecode.com]

Comment #9 on issue 3128 by thilina....@gmail.com: Sum and Product
manipulations
http://code.google.com/p/sympy/issues/detail?id=3128

I am still having a few problems regarding this. Let's consider, Sum(2*n,
(n, 1, 9)). then changing index n -> 2*n gives Sum(4*n, (n, 0.5, 4.5))
where new n should be incremented by 0.5. But in Sum variables are
incremented by 1. So the above Sums evaluate to different values. It would
be a big help if you can clarify this a little more.

[sy...@googlecode.com]

Comment #10 on issue 3128 by asme...@gmail.com: Sum and Product
manipulations
http://code.google.com/p/sympy/issues/detail?id=3128

Oh forget what I said. I think you are right. It should be a shift.

[sy...@googlecode.com]

Comment #11 on issue 3128 by thilina....@gmail.com: Sum and Product
manipulations
http://code.google.com/p/sympy/issues/detail?id=3128

Thanks Aaron.

[sy...@googlecode.com]

Comment #12 on issue 3128 by thilina....@gmail.com: Sum and Product
manipulations
http://code.google.com/p/sympy/issues/detail?id=3128

I would like to implement the reordering of the Sum/Products too ( I have
committed on this issue in pull request
https://github.com/sympy/sympy/pull/2081). Currently I think of a function
reorder() with an interface like below.

reorder(Sum(x*y, (x, a, b), (y, c, d)), x, y) will return
Sum(x*y, (y, c, d), (x, a, b)).

Generally this function will interchange the limits of the two additional
arguments
passed (here x and y).

As asmeurer has mentioned above, this will be tricky when limit variables
are related. But for the interface, is this a good way of doing this?

[sy...@googlecode.com]

Comment #13 on issue 3128 by thilina....@gmail.com: Sum and Product

manipulations
http://code.google.com/p/sympy/issues/detail?id=3128

I would like to implement the reordering of the Sum/Products too ( I have
committed on this issue in pull request
https://github.com/sympy/sympy/pull/2081). Currently I think of a function
reorder() with an interface like below.

>>> reorder(Sum(x*y, (x, a, b), (y, c, d)), x, y)

Sum(x*y, (y, c, d), (x, a, b)).

Generally this function will interchange the limits of the two additional
arguments
passed (here x and y).

As asmeurer has mentioned above, this will be tricky when limit variables

are related. But for the interface, is this a good method for reordering?

[sy...@googlecode.com]

Comment #14 on issue 3128 by asme...@gmail.com: Sum and Product
manipulations
http://code.google.com/p/sympy/issues/detail?id=3128

This is tricky, because you can have the same variable in multiple limits.
Check and see if other systems do this.

[sy...@googlecode.com]

Comment #15 on issue 3128 by asme...@gmail.com: Sum and Product
manipulations
http://code.google.com/p/sympy/issues/detail?id=3128

As for interdependent limits, you can just raise NotImplementedError for
now.

[sy...@googlecode.com]

Comment #16 on issue 3128 by thilina....@gmail.com: Sum and Product
manipulations
http://code.google.com/p/sympy/issues/detail?id=3128

When the same variable is used in more than one limit, generally reordering
will
change the summation. For example Sum(x, (x, 1, 3), (x, 1, 9)) evaluates to
54 while
Sum(x, (x, 1, 9), (x, 1, 3)) evaluates to 135. So, should we skip the
reordering of
Sum/Products where the same variable is repeated in limits or return the
same
Sum/Product without any changes if repetition is present?

I searched in mathematica and few other CASs and it seems like they do not
provide
reordering of variables in Sum. Actually they give a computed result for
Sum as
opposed to SymPy doing it on user request. So reordering of a variable
doesn't really
apply to them.

If we skip changing orders when repetition is present, I think there will
be no harm
in using the interface I proposed. Comments will be appreciated.

[sy...@googlecode.com]

Comment #17 on issue 3128 by thilina....@gmail.com: Sum and Product
manipulations
http://code.google.com/p/sympy/issues/detail?id=3128

What does reverse order of limits mean?
Is it converting Sum(x, (x, 1, 10) --> Sum(x, (x, 10, 1))?
If so, would an interface like reverse_order(Sum, index1, index2, ...) be
good?
Which reorders the limits of variables related to index1, index2, ... and
so on.

By the way, when equating Sums and Products, shall we apply the
simplifications
proposed by this issue on them? Currently,

Sum(x, (x, 1, 3)) + Sum(x, (x, 4, 6)) == Sum(x, (x, 1, 6)) returns False.

But it should return True. We can simplify LHS and RHS of == before
returning the
value.

[sy...@googlecode.com]

Comment #18 on issue 3128 by asme...@gmail.com: Sum and Product
manipulations
http://code.google.com/p/sympy/issues/detail?id=3128

I am sure that mathematica can represent unevaluated summations. Anyway,
reordering the limits where we have to change them to get the same answer
is something that we might implement some day, so for now, it should just
raise NotImplementedError.

== applies to structural equality, not mathematical equality. So Sum(x, (x,
1, 3)) + Sum(x, (x, 4, 6)) == Sum(x, (x, 1, 6)) should indeed be False
because one is an Add and the other is a Sum.

Regarding limit order, look at https://github.com/sympy/sympy/pull/1696. We
need to be using the Karr convention (this will be harder, because I don't
think we currently do). The same applies to combining sums of Sums.

[sy...@googlecode.com]

Comment #19 on issue 3128 by trel...@psu.edu: Sum and Product manipulations
http://code.google.com/p/sympy/issues/detail?id=3128

I was doing a little work with masters equations and generating functions
the other day, and needed some related functionality to simplify my
expressions that seems very closely related to this thread. I
re-implemented Sum._eval_subs() and added two functions, Sum._eval_factor()
and Sum._eval_expand(). But I'm not sure if/how these last 2 should be
connected to the standard factor() and expand() routines.

@thilina: does your work include these?

[sy...@googlecode.com]

Comment #20 on issue 3128 by thilina....@gmail.com: Sum and Product
manipulations
http://code.google.com/p/sympy/issues/detail?id=3128

@trel: Sorry for taking too long to reply. What does Sum._eval_subs() do?
I tried the function with the SymPy version installed in my machine and it
does not
change anything, returns the same Sum.

As for my work, I am just doing the simplifications which Aaron has
mentioned when
opening this issue. I have hooked all the other simplifications to
simplify() except
for change of index and reorder of limits. Those two are evaluated
separately using
two functions reorder() and change_index(). Here is the pull request:
https://github.com/sympy/sympy/pull/2081. More details can be found there.

Hope I answered your question. If you need further clarifications do let me
know.

[sy...@googlecode.com]

Comment #21 on issue 3128 by asme...@gmail.com: Sum and Product
manipulations
http://code.google.com/p/sympy/issues/detail?id=3128

_eval_subs is the internal representation of subs.

[sy...@googlecode.com]

Comment #22 on issue 3128 by trel...@psu.edu: Sum and Product manipulations
http://code.google.com/p/sympy/issues/detail?id=3128

I've posted my edits to subs, expand, and factor for Sum.
See https://github.com/sympy/sympy/pull/2198

It seems summation notation in it's classical form is not up
to the demands we place on it these days. I know I'm late to
the conversation, but I think the choice of the Karr
convention is a bad idea (#1696).

1) Given that there isn't an excepted convention, I think
the default should be the thing that's easiest to
understand. Pre-calc students in high-school, who do not yet
understand integration, will be really confused by sum(
f(x), (x,3,0)) != f(3) + f(2) + f(1) + f(0).

2) We don't always want Sum(f(x),(x,a,b)) +
Sum(f(x),(x,b,c)) == Sum(f(x),(x,a,c)). It depends on
context.

3) Notation should make everything explicit, avoid
ambiguity, and should not rely on implicit assumptions that
are not easily discovered by a naive reader. Examples of bad
notation are einstein summation notation (not uniquely
parsable) and stochastic differential equation notation
(depends on the specific definition of stochastic
integration used). Summation notation is not a perfect
parallel with integration -- there is no infinitessimal (dx)
term that explicitly communicates some type of orientation
is the summation.

I'd like to just be able to specify a summation in the form
Sum(f(i) for i in W(n)) where W is an rather general
collection of sets of integers parameterized by n, and not
have to worry about the algebra system trying to tell me
what the signs of f(i) should be.

A systematic survey of users would and popular opinion
on what " Sum(x,x=3..1) " means would go a long way to
justifying the choice, 1 way or the other.

[sy...@googlecode.com]

Comment #23 on issue 3128 by asme...@gmail.com: Sum and Product
manipulations
http://code.google.com/p/sympy/issues/detail?id=3128

1. I think summations with reversed limits is a bit of a corner case anyway
for such an audience.

2. Why not?

3. Not using the Karr convention is what leads to ambiguity, because there
is no way to be consistent otherwise, especially with symbolic limits.

I agree that we should have an object that represents summing positive
values over a set (or any values over an ordered set--be sure to make this
distinction; it matters!). It probably should be a separate object, SumSet
or something.

[sy...@googlecode.com]

Comment #24 on issue 3128 by trel...@psu.edu: Sum and Product manipulations
http://code.google.com/p/sympy/issues/detail?id=3128

Agree, reversed limits is definitely a corner case for students. I think
it's a corner case for almost everybody. I think that's a good reason not
to break with intuition.

2. Let S(k) be the set of integers between a(k) and b(k), including the
end points. Let M be the multiset composed of the join of the sets S(k),
for k = 0 .. n. How big is M? This is a very reasonable general math
question. In conventional notation, the answer should be Sum(
Sum(1,(i,a(k),b(k))), (k,0,n) ). However, the Karr convention imposes a
directionality on the sum, such that sometimes this will give the wrong
answer now. An explicit case is when a(k)=k-2, b(k)=2-k, n=4.

>>> [ Sum((Sum(1,(i,-2+k,2-k))),(k,0,j)).doit() for j in [0,1,2,3,4]]
[5, 8, 9, 8, 5]

The answer should be [5, 8, 9, 12, 17]. Note that the problem is not
``easily fixed'' either, by say, inserting an absolute value. In that case,

>>> [ Sum(abs(Sum(1,(i,-2+k,2-k))),(k,0,j)).doit() for j in range(5)]
[5, 8, 9, 10, 13]

which is still wrong. Of course, for this particular example, we can do
the math out by hand, but that would be missing the point. And there is
another version of this problem for which the Karr convention will give the
correct solution.

The Karr convention appeats to me to be a very nice self-consistent
resolution to a potential ambiguity for some problems where oriented sums
are needed. But it is not the unique solution, nor is it the ``intuitive
solution'' (IMO, data needed).

[sy...@googlecode.com]

Comment #25 on issue 3128 by asme...@gmail.com: Sum and Product
manipulations
http://code.google.com/p/sympy/issues/detail?id=3128

As I said, I agree that we need a way to represent summing over a set. The
issue is that representing this is more computationally difficult, and may
require different (less powerful) algorithms. Karr uses his convention
specifically because it makes his algorithm possible. Raoul (hopefully) can
explain this better.

[sy...@googlecode.com]

Comment #26 on issue 3128 by someb...@bluewin.ch: Sum and Product
manipulations
http://code.google.com/p/sympy/issues/detail?id=3128

No, the correct answer is:

In [103]: [ Sum(Sum(1,(i,-2+k,2-k)),(k,0,j)).doit() for j in range(5)]
Out[103]: [5, 8, 9, 8, 5]

If we look at the individual summands:

In [106]: [ [ Sum(1,(i,-2+k,2-k)) for k in range(j+1) ] for j in range(5) ]
Out[106]:
[[Sum(1, (i, -2, 2))],
[Sum(1, (i, -2, 2)), Sum(1, (i, -1, 1))],
[Sum(1, (i, -2, 2)), Sum(1, (i, -1, 1)), Sum(1, (i, 0, 0))],
[Sum(1, (i, -2, 2)),
Sum(1, (i, -1, 1)),
Sum(1, (i, 0, 0)),
Sum(1, (i, 1, -1))],
[Sum(1, (i, -2, 2)),
Sum(1, (i, -1, 1)),
Sum(1, (i, 0, 0)),
Sum(1, (i, 1, -1)),
Sum(1, (i, 2, -2))]]

In [107]: [ [ Sum(1,(i,-2+k,2-k)).doit() for k in range(j+1) ] for j in
range(5) ]
Out[107]: [[5], [5, 3], [5, 3, 1], [5, 3, 1, -1], [5, 3, 1, -1, -3]]


If we look at some specific sum we have for example:

In [121]: S = Sum(1, (i, -1, 1))

In [122]: S.doit()
Out[122]: 3

In [123]: S = Sum(1, (i, 1, -1))

In [124]: S.doit()
Out[124]: -1

These contribution do not cancel out nor do the sum up as if there were
some "abs".

Interchanging limits works as follows:

In [127]: S = Sum(i, (i, a, b))

In [128]: Sr = reverse_order(S, i)

In [129]: Sr
Out[129]: Sum(-i, (i, b + 1, a - 1))

In [130]: S.doit()
Out[130]: -a**2/2 + a/2 + b**2/2 + b/2

In [131]: Sr.doit()
Out[131]: -a**2/2 + a/2 + b**2/2 + b/2

Simply exchanging a and b without shifting misses boundary terms and does
NOT conserve the value of the sum.

[sy...@googlecode.com]

Comment #27 on issue 3128 by someb...@bluewin.ch: Sum and Product
manipulations
http://code.google.com/p/sympy/issues/detail?id=3128

Oh, btw this is how it works in most recent sympy master.
In older versions there were lots of bugs wrt to Sum and Product.

[sy...@googlecode.com]

Comment #28 on issue 3128 by someb...@bluewin.ch: Sum and Product
manipulations
http://code.google.com/p/sympy/issues/detail?id=3128

> However, the Karr convention imposes a directionality on the sum

In the very same way as for integrals:

\int_a^b f(x) dx is NOT equal to \int_b^a f(x) dx

In the summation case we have to shift limits due to the
discrete nature of "dx".

> such that sometimes this will give the wrong answer now.

No, it does not.

The main reason for this definition is that the following holds:

\sum_{m <= i < n} f(i) = \sum_{m <= i < k} + \sum_{k <= i < n}

*independent* on the relative ordering of m, n and k.

This is what we have for integrals too.


Well, you could also make the *definition* that:

\int_a^b f(x) dx == \int_b^a f(x) dx

but that would not feel natural although it might be useful sometimes.
In the same way, defining that:

\sum_{i=a}^b f(i) == \sum_{i=b}^a f(i)

is "wrong".

[sy...@googlecode.com]

Comment #29 on issue 3128 by someb...@bluewin.ch: Sum and Product
manipulations
http://code.google.com/p/sympy/issues/detail?id=3128

> An explicit case is when a(k)=k-2, b(k)=2-k, n=4.

a(k) := k - 2
b(k) := 2 - k
n \in [0, 1, 2, 3, 4]

Lets make a table:

>>> [(k-2, 2-k) for k in range(5)]
[(-2, 2), (-1, 1), (0, 0), (1, -1), (2, -2)]

Next, compute all the elments for each subset Sk(n):

>>> [ Sum(1, (i, k-2, 2-k)).doit() for k in range(5)]

[5, 3, 1, -1, -3]

And compute the cummulative set M(n):

>>> [ Sum(1, (i, k-2, 2-k), (k, 0, n)).doit() for n in range(5)]

[5, 8, 9, 8, 5]

In the following figure, the "*" denote elements being part of S(n)
and the "." are elements not part of S(n).

-2 -1 0 1 2
N: -- o -- o -- o -- o -- o --
n = 0 -- * -- * -- * -- * -- * --
n = 1 -- . -- * -- * -- * -- . --
n = 2 -- . -- . -- * -- . -- . --
n = 3 -- . -- x -- x -- x -- . --
n = 4 -- x -- x -- x -- x -- x --

The elements "x" would be selected if we assume the set notation:

[a(k), b(k)] == {a(k), a(k+1), ..., b(k-1), b(k)} <=> a(k) < b(k)
[a(k), b(k)] == {a(k)} <=> a(k) = b(k)
[b(k), a(k)] == [a(k), b(k)] otherwise

and we have the "full set" independent of the relative order of a(k) and
b(k).

In that case the partial sums Sk(n) would read:

[5, 3, 1, 3, 5]

and the cummulative sums M(n):

[5, 8, 9, 12, 17]

To get this, we have to assume that Sum(f(i), (i, a, b)) == Sum(f(i), (i,
b, a)).
This is not what Karr defines and hence his results are not really "wrong".



In case we take another set notation, namely:

[a(k), b(k)] == {a(k), a(k+1), ..., b(k-1), b(k)} <=> a(k) < b(k)
[a(k), b(k)] == {a(k)} <=> a(k) = b(k)
[a(k), b(k)] == {} <=> a(k) > b(k)

then all is perfectly fine. Again we start with the table:

-2 -1 0 1 2
N: -- o -- o -- o -- o -- o --
n = 0 -- * -- * -- * -- * -- * --
n = 1 -- . -- * -- * -- * -- . --
n = 2 -- . -- . -- * -- . -- . --
n = 3 -- . -- x -- x -- x -- . --
n = 4 -- x -- x -- x -- x -- x --

the first 3 rows are all ok, we can count the number of element of Sk(n)
(number of * on each line) by this sum:

>>> Sk = Sum(1, (i, k-2, 2-k)).doit()
>>> Sk
-2*k + 5

>>> Sk.subs(k,0)
5
>>> Sk.subs(k,1)
3
>>> Sk.subs(k,2)
1

However, for the next two rows we arrive at these intermediate sums.
We could either trust sympy and compute their values:

>>> Sum(1, (i, 1, -1)).doit()
-1
>>> Sum(1, (i, 2, -2)).doit()
-3

It is obvious that this (even in absolute value) does NOT count the
number of "x" on the fourth and fifth row.

If we do not trust sympy then according to Karrs definition we can
to swap limits and obtain:

>>> S3 = Sum(1, (i, 1, -1))
>>> reverse_order(S3, i)
Sum(-1, (i, 0, 0))
>>> _.doit()
-1

>>> S4 = Sum(1, (i, 2, -2))
>>> reverse_order(S4, i)
Sum(-1, (i, -1, 1))
>>> _.doit()
-3

By this swap we implicitely modify the table:

-2 -1 0 1 2
N: -- o -- o -- o -- o -- o --
n = 0 -- * -- * -- * -- * -- * --
n = 1 -- . -- * -- * -- * -- . --
n = 2 -- . -- . -- * -- . -- . --
n = 3 -- . -- . -- + -- . -- . --
n = 4 -- . -- + -- + -- + -- . --

and now count correctly the number of "+" signs. This explains why the
original sequence Sk as well as M is correct.



If we extend the table by one row we find:

-2 -1 0 1 2
N: -- o -- o -- o -- o -- o --
n = 0 -- * -- * -- * -- * -- * --
n = 1 -- . -- * -- * -- * -- . --
n = 2 -- . -- . -- * -- . -- . --
n = 3 -- . -- . -- + -- . -- . --
n = 4 -- . -- + -- + -- + -- . --
n = 5 -- + -- + -- + -- + -- + --

And finally that M(n) is [5, 8, 9, 8, 5, 0] for n = [0, 1, 2, 3, 4, 5].

Compare this also to the continuous case:

>>> Sk = integrate(1, (x, k-2, 2-k))
>>> Sk
-2*k + 4
>>> M = integrate(Sk, (k, 0, 4))
>>> M
0

Clearly, the two "triangles" cancel out.

>>> Sk = Sum(1, (x, k-2, 2-k))
>>> M = Sum(Sk, (k, 0, 5)).doit()
>>> M
0



It all depends on what we onderstand by subsets of integers specified by
their
"boundary" elements only.

[sy...@googlecode.com]

Comment #30 on issue 3128 by someb...@bluewin.ch: Sum and Product
manipulations
http://code.google.com/p/sympy/issues/detail?id=3128

Ok, and now back to the original topic. From the inital list:

- [x] Addition of two sums / products with the same limits
- [x] Addition of two sums with different limits (like Sum(i, (i, 0, k)) +
Sum(i, (i, k, m)))
- [x] Change of index
- [ ] Product of Sums
- [x] Reorder multiple sums or products
- [x] Reverse order of limits
- [ ] The inverse of any of the above rules

Point 1 works:

In [117]: S1 = Sum(i, (i, a, b))
In [118]: S2 = Sum(i**2, (i, a, b))
In [119]: S1+S2
Out[119]: Sum(i, (i, a, b)) + Sum(i**2, (i, a, b))
In [120]: simplify(_)
Out[120]: Sum(i**2 + i, (i, a, b))

In [133]: P1 = Product(i, (i, a, b))
In [137]: P2 = Product(i**3+i, (i, a, b))
In [138]: P1*P2
Out[138]: Product(i, (i, a, b))*Product(i**3 + i, (i, a, b))
In [139]: simplify(_)
Out[139]: Product(i**4 + i**2, (i, a, b))


Point 2 works in special cases, could maybe be improved:

In [127]: Sum(i, (i, 0, k)) + Sum(i, (i, k+1, m))
Out[127]: Sum(i, (i, 0, k)) + Sum(i, (i, k + 1, m))
In [128]: simplify(_)
Out[128]: Sum(i, (i, 0, m))

In [125]: Sum(i, (i, 0, k)) + Sum(i, (i, k, m))
Out[125]: Sum(i, (i, 0, k)) + Sum(i, (i, k, m))
In [126]: simplify(_)
Out[126]: Sum(i, (i, 0, k)) + Sum(i, (i, k, m))

In [131]: Sum(i, (i, 0, k)) + Sum(i, (i, k+12, m))
Out[131]: Sum(i, (i, 0, k)) + Sum(i, (i, k + 12, m))
In [132]: simplify(_)
Out[132]: Sum(i, (i, 0, k)) + Sum(i, (i, k + 12, m))

In [140]: P1 = Product(i, (i, a, b))
In [143]: P2 = Product(i, (i, b+1, c))
In [144]: P1*P2
Out[144]: Product(i, (i, a, b))*Product(i, (i, b + 1, c))
In [145]: simplify(_)
Out[145]: Product(i, (i, a, c))


There are clearly bugs with point 4:

In [156]: S1
Out[156]: Sum(i, (i, a, b))
In [157]: S2
Out[157]: Sum(i**2, (i, a, b))
In [158]: S1*S2
Out[158]: Sum(i, (i, a, b))*Sum(i**2, (i, a, b))
In [159]: simplify(_)
Out[159]: Sum(i**2, (i, a, b))
In [160]: _ - S2
Out[160]: 0

[sy...@googlecode.com]

Comment #31 on issue 3128 by thilina....@gmail.com: Sum and Product
manipulations
http://code.google.com/p/sympy/issues/detail?id=3128

I'll take a look at fixing point 4. How can point 2 be improved?

[sy...@googlecode.com]

Comment #32 on issue 3128 by trel...@psu.edu: Sum and Product manipulations
http://code.google.com/p/sympy/issues/detail?id=3128

Right. The notation of defining sums with just the limits of the sum is
ambiguous (hence, bad notation). Reasonable people may disagree about
the "right" interpretation, and the "best choice" can depend on context.
If I had a multiset compose of the join of sets of integers between -2+k
and 2-k, for k=0..4, __I__ would expect

>>> Sum((Sum(1,(i,-2+k,2-k))),(k,0,4)).doit()

to return the size of the multiset == # of x's in

0 | x x x x x
1 | x x x
2 | x
3 | x x x
4 | x x x x x
---+----------------------
|-3 -2 -1 0 1 2 3

But the best design choice should be whatever makes the users most
comfortable and productive.

[sy...@googlecode.com]

Comment #33 on issue 3128 by thilina....@gmail.com: Sum and Product
manipulations
http://code.google.com/p/sympy/issues/detail?id=3128

Bug in point 4 fixed.

[sy...@googlecode.com]

Comment #34 on issue 3128 by someb...@bluewin.ch: Sum and Product
manipulations
http://code.google.com/p/sympy/issues/detail?id=3128

If you want to compute the number of all the "x" in your graph, then
we can easily make sure that the left boundary of that double triangle
is always smaller or equal to the right one by using "Abs":

>>> a = k - 2
>>> b = 2 - k

>>> Sk = Sum(1, (x, -Abs(a), Abs(b))).doit()
>>> Sk
Abs(-k + 2) + Abs(k - 2) + 1

>>> M = Sum(Sk, (k, 0, 4)).doit()
>>> M
17

which is correct.


This is similar on how to use integration to compute the area below a curve.

>>> integrate(sin(x), (x, 0, 2*pi))
0

which is of course "wrong" or rather not what we asked for because the area
carries a sign. The error is not in the math or implementation but simply
comes from an unsuitable problem statement.

Indeed, if we pose the correct question, we get the "right" answer:

>>> Abs(integrate(sin(x), (x, 0, pi))) + Abs(integrate(sin(x), (x, pi,
>>> 2*pi)))
4

Note that I split the integral at x=pi because Sympy does a bad job on
integrate(Abs(sin(x)), (x, 0, 2*pi)).

[sy...@googlecode.com]

Comment #35 on issue 3128 by someb...@bluewin.ch: Sum and Product
manipulations
http://code.google.com/p/sympy/issues/detail?id=3128

Improving on point two is probably not so easy.

For example if we had two Sums S1, S2, with overlaping summation ranges,
there are situations where one could rewrite the expression S1 + S2 as
S3 + S4 where S3 goes over the common part of the range and S4 is the
remainder.

For example:

>>> E0 = Sum(i, (i, 0, k)) + Sum(i, (i, k, m))
>>> E0.doit()
k + m**2/2 + m/2

>>> E1 = Sum(i, (i, 0, k)) + Sum(i, (i, k+1, m)) + k
>>> E1.doit()
k + m**2/2 + m/2

>>> E2 = simplify(E1)
>>> E2
k + Sum(i, (i, 0, m))

>>> E2.doit()
k + m**2/2 + m/2

Simplify could be extended to be able to get from E0 to E2. This is
especially
important in case the remainder S4 (here S4=k) contains only a single or a
few
element(s).

>>> E0 = Sum(i, (i, 0, k)) + Sum(i, (i, 0, k+2))
>>> E0.doit()
k**2 + 3*k + 3

>>> simplify(E0)
Sum(i, (i, 0, k)) + Sum(i, (i, 0, k + 2))

>>> E1 = Sum(i, (i, 0, k)) + Sum(i, (i, 0, k)) + (k+1) + (k+2)
>>> E1.doit()
k**2 + 3*k + 3

>>> E2 = simplify(E1)
>>> E2
2*k + Sum(2*i, (i, 0, k)) + 3

>>> E2.doit()
k**2 + 3*k + 3

This is another example where we would wish that simplify(E0) yields E2
without human interaction.

One would need a clever heuristic to determined when to do such
transformations.
In the first example, the intersection of both ranges was small while in
the second
the symmetric difference was. Probably one usually wants to do such
transformations
when "one of both is small compared to the other".

[sy...@googlecode.com]

Comment #36 on issue 3128 by someb...@bluewin.ch: Sum and Product
manipulations
http://code.google.com/p/sympy/issues/detail?id=3128

Maybe you want to try it?

In that case, consider also what happens if there are more than two Sums in
the original expression. How to find a (near) optimum on which sums to
combine and how?

Here is another example where I'd like not to have to manually enter E1:

In [293]: E0.doit()
Out[293]: -3**a/2 + 3**(b + 4)/2 + u*(-a**3/3 + a**2/2 - a/6 + b**3/3 +
b**2/2 + b/6)

In [294]: simplify(_)
Out[294]: -3**a/2 + 81*3**b/2 + u*(-2*a**3 + 3*a**2 - a + 2*b**3 + 3*b**2 +
b)/6

In [295]: simplify(E0)
Out[295]: Sum(3**i, (i, a, b + 3)) + Sum(i**2*u, (i, a, b))

In [296]: E1 = Sum(i**2*u, (i, a, b)) + Sum(3**i, (i, a, b)) + Sum(3**i,
(i, b+1, b+3))

In [297]: E1.doit()
Out[297]: -3**a/2 + 3*3**(b + 1)/2 + 3**(b + 2) + 3**(b + 3) + u*(-a**3/3 +
a**2/2 - a/6 + b**3/3 + b**2/2 + b/6)

In [298]: simplify(_)
Out[298]: -3**a/2 + 81*3**b/2 + u*(-2*a**3 + 3*a**2 - a + 2*b**3 + 3*b**2 +
b)/6

In [299]: simplify(E1)
Out[299]: Sum(3**i, (i, b + 1, b + 3)) + Sum(3**i + i**2*u, (i, a, b))

In [300]: _.doit()
Out[300]: -3**a/2 + 3*3**(b + 1)/2 + 3**(b + 2) + 3**(b + 3) + u*(-a**3/3 +
a**2/2 - a/6 + b**3/3 + b**2/2 + b/6)

In [301]: simplify(_)
Out[301]: -3**a/2 + 81*3**b/2 + u*(-2*a**3 + 3*a**2 - a + 2*b**3 + 3*b**2 +
b)/6

I hope this gives you some ideas. Btw, all that applies also to Products of
course.