# 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 \in B_a} t_{a,b} = \sum_{c \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

- $\displaystyle A = \set {1, 2} \land B_1 = \set {1, 2} \land B_2 = \set {1, 2}$
- $\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 = \sum_{c \mathop \in \prod_{a \mathop \in A} B_a} \prod_{a \mathop \in A} t_{a, c_a}$
- $\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 = \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 = 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 Rieman 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 (\prod_{a \in \closedint 1 n} \sum_{b \in B_a} t_{a,b})(\sum_{b \in B_{n+1} } t_{n+1,b}) = (\sum_{c \in \prod_{a \in \closedint 1 n} B_a} \prod_{a \in \closedint 1 n}t_{a,c_a}) (\sum_{b \in B_{n+1}} t_{n+1,b}) $

We need this result which we will prove below,

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

which gives,

- $\displaystyle (\prod_{a \in \closedint 1 n} \sum_{b \in B_a} t_{a,b})(\sum_{b \in B_{n+1}} t_{n+1,b}) = \sum_{c \in (\prod_{a \in \closedint 1 n} B_a) \times B_{n+1}} \prod_{a \in \closedint 1 {n + 1} }t_{a,c_a}$
- $\displaystyle = \sum_{c \in \prod_{a \in \closedint 1 {n + 1} } B_a} \prod_{a \in \closedint 1 {n + 1} }t_{a,c_a}$

This completes the induction case on $n$, but assuming,

- $\displaystyle (\sum_{c \in \prod_{a \in \closedint 1 n} B_a} \prod_{a \in \closedint 1 n}t_{a,c_a}) \sum_{b \in X_{n+1}} t_{n+1,b} = \sum_{c \in (\prod_{a \in \closedint 1 n} B_a) \times X_{n+1}} \prod_{a \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 (\sum_{c \in \prod_{a \in \closedint 1 n} B_a} \prod_{a \in \closedint 1 n}t_{a,c_a}) t_{n+1,k} = \sum_{c \in (\prod_{a \in \closedint 1 n} B_a) \times \{k\}} \prod_{a \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.

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

Then:

- $\displaystyle \sum_{b \in Z_{n+1}} t_{n+1,b} = (\sum_{b \in X_{n+1}} t_{n+1,b} + \sum_{b \in Y_{n+1}} t_{n+1,b}) $

Starting with the left hand side of the assumption,

- $\displaystyle (\sum_{c \in \prod_{a \in \closedint 1 n} B_a} \prod_{a \in \closedint 1 n}t_{a,c_a}) \sum_{b \in Z_{n+1}} t_{n+1,b} $

Substituting for $Z_{n+1}$:

- $\displaystyle = (\sum_{c \in \prod_{a \in \closedint 1 n} B_a} \prod_{a \in \closedint 1 n}t_{a,c_a}) (\sum_{b \in X_{n+1}} t_{n+1,b} + \sum_{b \in Y_{n+1}} t_{n+1,b}) $
- $\displaystyle = (\sum_{c \in \prod_{a \in \closedint 1 n} B_a} \prod_{a \in \closedint 1 n}t_{a,c_a}) \sum_{b \in X_{n+1}} t_{n+1,b} + (\sum_{c \in \prod_{a \in \closedint 1 n} B_a} \prod_{a \in \closedint 1 n} t_{a,c_a}) \sum_{b \in Y_{n+1}} t_{n+1,b}$

Use the assumption for X and Y:

- $\displaystyle = \sum_{c \in (\prod_{a \in \closedint 1 n} B_a) \times X_{n+1}} \prod_{a \in \closedint 1 {n + 1} }t_{a,c_a} + \sum_{c \in (\prod_{a \in \closedint 1 n} B_a) \times Y_{n+1}} \prod_{a \in \closedint 1 {n + 1} }t_{a,c_a}$

Merge the two summations into one:

- $\displaystyle = \sum_{c \in ((\prod_{a \in \closedint 1 n} B_a) \times X_{n+1} \cup (\prod_{a \in \closedint 1 n} B_a)\times Y_{n+1})} \prod_{a \in \closedint 1 {n + 1} }t_{a,c_a}$

The cartesian product is:

- $\displaystyle (\prod_{a \in \closedint 1 n} B_a)\times X_{n+1} \cup (\prod_{a \in \closedint 1 n} B_a)\times Y_{n+1}$

Use $ R\times P \cup R\times Q = R \times (P \cup Q)$ to give:

- $\displaystyle = (\prod_{a \in \closedint 1 n} B_a)\times (X_{n+1} \cup Y_{n+1})$

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

- $\displaystyle = (\prod_{a \in \closedint 1 n} B_a)\times Z_{n+1}$

Substituting back in:

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

which is the right hand side of the assumption.

$\blacksquare$