# Product of Summations is Summation Over Cartesian Product of Products

## 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.

## Cartesian Products

To be continued.

## Example

Let:

\(\displaystyle A\) | \(=\) | \(\displaystyle \set {1, 2}\) | |||||||||||

\(\displaystyle B_1\) | \(=\) | \(\displaystyle \set {1, 2}\) | |||||||||||

\(\displaystyle B_2\) | \(=\) | \(\displaystyle \set {1, 2}\) |

Then:

\(\displaystyle \prod_{a \mathop \in A} \sum_{b \mathop \in B_a} t_{a, b}\) | \(=\) | \(\displaystyle \paren {t_{1, 1} + t_{1, 2} } \paren {t_{2, 1} + t_{2, 2} }\) | |||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \sum_{c \mathop \in \prod_{a \mathop \in A} B_a} \prod_{a \mathop \in A} t_{a, c_a}\) | |||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \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}\) | |||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \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}\) | |||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle 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:

\(\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} }\) | \(=\) | \(\displaystyle \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}\) | |||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \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:

\(\displaystyle \) | \(\) | \(\displaystyle \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 | ||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \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}$ | ||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \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}\) | |||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \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$ | ||||||||||

\(\displaystyle \) | \(=\) | \(\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}\) | merging the two summations into one |

The cartesian product is:

\(\displaystyle \) | \(\) | \(\displaystyle \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}\) | |||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \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}$ | ||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \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$