# Method for variable substitution in multiple summation

I asked this question on mathoverflow, someone suggested me to ask here as well. So I post it here. Thanks for helping.

I want to ask: is there any general method for variable substitution in multiple summation?

For example in the following equation a new variable $\lambda=n+m-2\mu$ is introduced to transform the LHS to the RHS $$\sum_{n=0}^\infty \sum_{m=0}^\infty \sum_{\mu=0}^{\left\lfloor \frac{m+n}{2}\right\rfloor}f(n,m,\mu,n+m-2\mu) = \sum_{\lambda=0}^\infty \sum_{\mu=0}^\infty \sum_{n=0}^{2\mu+\lambda}f(n,2\mu+\lambda-n,\mu,\lambda)$$

Another example, in which a new variable $\delta=m+n+2 p-2 k-2 \mu-2 \sigma$ is introduced

$$\sum _{n=0}^{\infty } \sum _{m=0}^{\infty } \sum _{p=0}^M \sum _{k=0}^p \sum _{\sigma =0}^{p-k}\quad \sum _{\mu =0}^{\left\lfloor \frac{m+n}{2}+p-k-\sigma \right\rfloor } f(n,m,\mu ,p,k,\sigma ,m+n+2 p-2 k-2 \mu-2 \sigma )$$ $$= \sum _{\delta =0}^{\infty } \sum _{\mu =0}^{\infty } \sum _{p=0}^M \quad\sum _{\beta =0}^{\min \left(p,\left\lfloor \frac{\delta }{2}+\mu \right\rfloor \right)}\quad \sum _{n=0}^{2 (\mu -\beta )+\delta }\quad \sum _{k=0}^{p-\beta }\;\; f(n,\delta +2 \mu-2 \beta -n,\mu ,p,k,p-\beta -k,\delta )$$

Additional remarks: my goal is using a new summation index, e.g. $\lambda$, to express a particular linear combination of the old indices, which is appointed by me, e.g. $n+m-2\mu$. So this is a linear coordinate transformation. My problem is how to determine all the lower and upper bounds of the new summation indices frame, as well as the summation steps which are possibly not $1$.

I wonder whether there is a systematical and efficient technology, so I may be able to do those transformations automatically by programming.

-
Usually we do those summations switch because us, as mathematicians, believe there is a purpose for that... (i.e. it simplifies equations). If you tell a computer to do those switches I think it would just pull you off infinitely many possibilities, which is not a good thing if you want to see something nice one day. The best way I have found up to now to "naturally" understand those index transforms is by making a drawing... I can't answer you with something appropriate but this is my opinion. For instance $$\sum_{n\ge 0} \sum_{k \ge n} = \sum_{k \ge 0} \sum_{n=0}^k$$ is a triangle. –  Patrick Da Silva Jul 21 '11 at 8:33
(Didn't have enough space in one comment) : Draw the $n$'s on the $x$-axis and the $k$'s on the $y$-axis, thus summing over all integer coordinates (n,k) such that $n \ge 0$, $k \ge 0$ and $k \ge n$ (LHS) but this is equivalent to $k \ge 0$, and then $0 \le n \le k$ (RHS). Hope that helps... and good luck with those... –  Patrick Da Silva Jul 21 '11 at 8:37
@Patrick Da Silva: Yes I draw 2-dim or 3-dim axes too when I do the transformation by hand :D But if I have many levels of sum, this will be inefficient cause it's hard to draw high dimension, and those floor and ceiling functions and steps$\neq 1$ are bothering. I think I need to treat the whole summation region as a high dimension polyhedron and find a systematical routine to deal with it. –  Silvia Jul 21 '11 at 9:08
Your sums are kinda ugly though... –  Patrick Da Silva Jul 21 '11 at 15:08
Yes they are:( I used one of the explicit sum formulas of Chebyshev polynomial (mathworld.wolfram.com/ChebyshevPolynomialoftheFirstKind.html eq.15), which introduces those floor functions. –  Silvia Jul 21 '11 at 20:42

When we have to compute an integral $\int_B f(x){\rm d}(x)$ over some simple body $B\subset{\mathbb R^n}$ there usually are many elementary maps $g: \ A\to B, \ u\mapsto g(u)$ which are essentially bijective and make $B$ the image of an even simpler body $A$, or let become $f$ a simpler expression of the new variable $u$.
On the other hand, an $r$-fold summation runs over some simple subset of ${\mathbb Z}^r$, say an octant or a triangle $\{(i,k)\ |\ 0\leq k\leq i\leq n \}$. Unless you resort to number-theoretical tricks there are almost no elementary maps mapping such a set to another such set. Patrick Da Silva has given an example in his comment: It is a linear map with ones in the main diagonal and one off-diagonal element nonzero.
As an aside: It is a famous unsolved problem to get an exact estimate on the number of lattice points in a disk of radius $R$.
@ Christian Blatter: Thanks very much for your answer. I understand the difficulties of counting lattice points in disk, but if considering the summation region bounded only by integer coefficients planes (like $\sum_k A_k x_k=B$ where $A_k, B\in \mathbb{Z}$), the problem might be much simpler and there might even exist a systematical technique for it. Besides, I'm thinking of using Iverson's bracket to avoid dealing with those tricky boundary conditions. –  Silvia Jul 21 '11 at 20:34