# Product of Summations is Summation Over Cartesian Product of Products

 It has been suggested that this page or section be merged into Product of Summations. (Discuss)

## Theorem

This is a generalization of the distributive law:

$\displaystyle \prod_{a \mathop \in A} \sum_{b \mathop \in B_a} t_{a, b} = \sum_{c \mathop \in \prod_{a \mathop \in A} B_a} \prod_{a \mathop \in A} t_{a, c_a}$

where the product of sets $\prod_{a \mathop \in A} B_a$ is taken to be a cartesian product.

## Definition of Terms

In its simplest form $A$ is a range of positive natural numbers in $\closedint 1 n$.

$B$ is vector of sets, indexed by the elements of $A$.

$A$ also indexes elements of the cartesian product which are n-tuples.

The sets $B_a$ are finite sets, usually of integers.

These form the indexes of summation.

However in its usage in Product Form of Sum on Completely Multiplicative Function, $A$ may not be consecutive integers.

In that usage, $A$ are primes.

An extra level of abstraction is required, to map from the elements of a set to consecutive positive natural numbers that index the n-tuples formed from the Cartesian products.

To be continued.

## Example

Let:

 $\ds A$ $=$ $\ds \set {1, 2}$ $\ds B_1$ $=$ $\ds \set {1, 2}$ $\ds B_2$ $=$ $\ds \set {1, 2}$

Then:

 $\ds \prod_{a \mathop \in A} \sum_{b \mathop \in B_a} t_{a, b}$ $=$ $\ds \paren {t_{1, 1} + t_{1, 2} } \paren {t_{2, 1} + t_{2, 2} }$ $\ds$ $=$ $\ds \sum_{c \mathop \in \prod_{a \mathop \in A} B_a} \prod_{a \mathop \in A} t_{a, c_a}$ $\ds$ $=$ $\ds \sum_{c \mathop \in \set {\tuple {m, n}: m \mathop \in B_1 \land n \mathop \in B_2} } t_{1, c_1} t_{2, c_2}$ $\ds$ $=$ $\ds \sum_{c \mathop \in \set {\tuple {1, 1}, \tuple {1, 2}, \tuple {2, 1}, \tuple {2, 2} } } t_{1, c_1} t_{2, c_2}$ $\ds$ $=$ $\ds t_{1, 1} t_{2, 1} + t_{1, 1} t_{2, 2} + t_{1, 2} t_{2, 1} + t_{1, 2} t_{2, 2}$

## Usage

Used in the derivation of the Euler Product expression for the Riemann Zeta function.

## Proof

For simplicity, let $A = \closedint 1 n$.

This reduces the complexity without loss of generality, as if we wanted to use an arbitrary set we could store the actual elements in an $n$-tuple and index them.

So we can think of $\closedint 1 n$ as representing the actual elements.

Use induction on $n$:

For $n = 1$:

$\displaystyle \sum_{b \mathop \in B_1} t_{1, b} = \sum_{c \mathop \in B_1} t_{1, c}$

which is true, proving the case.

Assume the formula is true for $n$, and prove it for $n + 1$.

$\displaystyle \paren {\prod_{a \mathop \in \closedint 1 n} \sum_{b \mathop \in B_a} t_{a, b} } \paren {\sum_{b \mathop \in B_{n + 1} } t_{n+1, b} } = \paren {\sum_{c \mathop \in \prod_{a \in \closedint 1 n} B_a} \prod_{a \mathop \in \closedint 1 n} t_{a, c_a} } \paren {\sum_{b \mathop \in B_{n + 1} } t_{n + 1, b} }$

We need this result which we will prove below,

$\displaystyle \paren {\sum_{c \mathop \in \prod_{a \in \closedint 1 n} B_a} \prod_{a \mathop \in \closedint 1 n} t_{a, c_a} } \sum_{b \mathop \in X_{n + 1} } t_{n + 1, b} = \sum_{c \mathop \in \paren {\prod_{a \mathop \in \closedint 1 n} B_a} \times X_{n + 1} } \prod_{a \mathop \in \closedint 1 {n + 1} } t_{a, c_a}$

which gives:

 $\ds \paren {\prod_{a \mathop \in \closedint 1 n} \sum_{b \mathop \in B_a} t_{a, b} } \paren {\sum_{b \mathop \in B_{n + 1} } t_{n + 1, b} }$ $=$ $\ds \sum_{c \mathop \in \paren {\prod_{a \mathop \in \closedint 1 n} B_a} \times B_{n + 1} } \prod_{a \mathop \in \closedint 1 {n + 1} } t_{a, c_a}$ $\ds$ $=$ $\ds \sum_{c \mathop \in \prod_{a \in \closedint 1 {n + 1} } B_a} \prod_{a \mathop \in \closedint 1 {n + 1} } t_{a, c_a}$

This completes the induction case on $n$ while assuming:

$\displaystyle \paren {\sum_{c \mathop \in \prod_{a \in \closedint 1 n} B_a} \prod_{a \mathop \in \closedint 1 n} t_{a, c_a} } \sum_{b \mathop \in X_{n + 1} } t_{n + 1, b} = \sum_{c \mathop \in \paren {\prod_{a \mathop \in \closedint 1 n} B_a} \times X_{n + 1} } \prod_{a \mathop \in \closedint 1 {n + 1} } t_{a, c_a}$

To prove this, use induction on the size $X_{n + 1}$.

If $X_{n + 1}$ has a single element:

$\displaystyle \paren {\sum_{c \mathop \in \prod_{a \in \closedint 1 n} B_a} \prod_{a \mathop \in \closedint 1 n} t_{a, c_a} } t_{n + 1, k} = \sum_{c \mathop \in \paren {\prod_{a \mathop \in \closedint 1 n} B_a} \times \set k} \prod_{a \mathop \in \closedint 1 {n + 1} } t_{a, c_a}$

which is true, proving the case for size $1$.

Now assume it is true for $X_{n + 1}$ and $Y_{n + 1}$ we will prove it for $Z_{n + 1}$.

This corresponds to the induction step if the size of $Y_{n + 1}$ is $1$.

So all we are doing is proving a more general case.

We do this because $X_{n + 1}$ and $Y_{n + 1}$ are then symmetrical, and so the proof is easier to understand.

$Z_{n + 1} = X_{n + 1} \cup Y_{n + 1}$

Then:

$\displaystyle \sum_{b \mathop \in Z_{n + 1} } t_{n + 1, b} = \paren {\sum_{b \mathop \in X_{n + 1} } t_{n + 1, b} + \sum_{b \mathop \in Y_{n + 1} } t_{n + 1, b} }$

Thus:

 $\ds$  $\ds \paren {\sum_{c \mathop \in \prod_{a \mathop \in \closedint 1 n} B_a} \prod_{a \mathop \in \closedint 1 n} t_{a, c_a} } \sum_{b \mathop \in Z_{n + 1} } t_{n + 1, b}$ from left hand side of assumption $\ds$ $=$ $\ds \paren {\sum_{c \in \prod_{a \mathop \in \closedint 1 n} B_a} \prod_{a \mathop \in \closedint 1 n} t_{a, c_a} } \paren {\sum_{b \mathop \in X_{n + 1} } t_{n + 1, b} + \sum_{b \mathop \in Y_{n + 1} } t_{n + 1,b} }$ substituting for $Z_{n + 1}$ $\ds$ $=$ $\ds \paren {\sum_{c \in \prod_{a \mathop \in \closedint 1 n} B_a} \prod_{a \mathop \in \closedint 1 n} t_{a, c_a} } \sum_{b \mathop \in X_{n + 1} } t_{n + 1, b} + \paren {\sum_{c \mathop \in \prod_{a \mathop \in \closedint 1 n} B_a} \prod_{a \mathop \in \closedint 1 n} t_{a, c_a} } \sum_{b \in Y_{n + 1} } t_{n + 1, b}$ $\ds$ $=$ $\ds \sum_{c \mathop \in \paren {\prod_{a \mathop \in \closedint 1 n} B_a} \times X_{n + 1} } \prod_{a \mathop \in \closedint 1 {n + 1} } t_{a, c_a} + \sum_{c \mathop \in \paren {\prod_{a \mathop \in \closedint 1 n} B_a} \times Y_{n + 1} } \prod_{a \mathop \in \closedint 1 {n + 1} } t_{a, c_a}$ using the assumption for $X$ and $Y$ $\ds$ $=$ $\ds \sum_{c \mathop \in \paren {\paren {\prod_{a \mathop \in \closedint 1 n} B_a} \times X_{n + 1} \mathop \cup \paren {\prod_{a \mathop \in \closedint 1 n} B_a} \times Y_{n + 1} } } \prod_{a \mathop \in \closedint 1 {n + 1} } t_{a, c_a}$ merging the two summations into one

The cartesian product is:

 $\ds$  $\ds \paren {\prod_{a \mathop \in \closedint 1 n} B_a} \times X_{n + 1} \cup \paren {\prod_{a \mathop \in \closedint 1 n} B_a} \times Y_{n + 1}$ $\ds$ $=$ $\ds \paren {\prod_{a \mathop \in \closedint 1 n} B_a} \times \paren {X_{n + 1} \cup Y_{n + 1} }$ using $R \times P \cup R \times Q = R \times \paren {P \cup Q}$ $\ds$ $=$ $\ds \paren {\prod_{a \mathop \in \closedint 1 n} B_a} \times Z_{n + 1}$ using $X_{n + 1} \cup Y_{n + 1} = Z_{n + 1}$

Substituting back in:

$\displaystyle \sum_{c \mathop \in \paren {\paren {\prod_{a \mathop \in \closedint 1 n} B_a} \times X_{n + 1} \mathop \cup \paren {\prod_{a \mathop \in \closedint 1 n} B_a} \times Y_{n + 1} } } \prod_{a \mathop \in \closedint 1 {n + 1} } t_{a,c_a} = \sum_{c \mathop \in \paren {\prod_{a \mathop \in \closedint 1 n} B_a} \times Z_{n+1} } \prod_{a \mathop \in \closedint 1 {n + 1} } t_{a, c_a}$

which is the right hand side of the assumption.

$\blacksquare$