# Infinite distributive law

This is related to an previous post of mine and is from a result in my book. I have the following equality: $$p(x)=\sum_{k_i\ge 0}\left(\frac{x^{\sum_{i=1}^\infty ik_i}}{\prod_{i=1}^\infty k_i!(i!)^{k_i}}\right)$$ where the summation runs over all sequences $k_1,k_2\cdots$ of non-negative integers containing finitely many non-zero entries. The next sentence in the book is

Consequently $p(x)=\prod_{i=1}^\infty \left(\sum_{k_i=0}^\infty \frac{x^{ik_i}}{k_i!(i!)^{k_i}}\right)$.

Its not clear to me how this sentence follows from the previous expression for $p(x)$.

My attempt: If $(a_1,a_2\cdots),(b_1,b_2,\cdots)$ are natural sequences with finitely many non zero terms then the first expression for $p(x)$ contains terms like $+\cdots\left(\frac{x^{a_1}}{a_1!1!^{a_1}}.\frac{x^{2a_2}}{a_2!2!^{a_2}}.\frac{x^{3a_3}}{a_3!3!^{a_3}}\cdots\right)\cdots+\left(\frac{x^{b_1}}{b_1!1!^{b_1}}.\frac{x^{2b_2}}{b_2!2!^{b_2}}.\frac{x^{3b_3}}{b_3!3!^{b_3}}\cdots\right)+\cdots$. If I attempt to distribute this sum as a product, terms like $\frac{x^{a_1}}{a_1!1!^{a_1}}\frac{x^{2b_2}}{b_2!2!^{b_2}}$ etc appear which do not seem to be there in the initial $p(x)$.

I have a feeling that this is not as difficult as I am taking it to be. If someone can just clarify my doubt I will be extremely obliged.

(By the way $p(x)$ is the exponential generating function for the Bell numbers.)

• If you use \left( and \right) the size is automatically fitted, which is better than just specifying \Big. Apr 11, 2013 at 13:57
• @AsafKaragila: Okay. Thanks. Apr 11, 2013 at 16:10

Your expression for $p(x)$ is $$\sum_{k_i\ge 0}\left(\frac{x^{\sum_{i=1}^\infty ik_i}}{\prod_{i=1}^\infty k_i!(i!)^{k_i}}\right)=\sum_{k_i\ge 0}\left(\prod_{i=1}^\infty\frac{x^{i k_i}}{k_i!(i!)^{k_i}}\right).$$ Now, when you expand $\displaystyle \prod_{i=1}^\infty \left(\sum_{k_i=0}^\infty \frac{x^{ik_i}}{k_i!(i!)^{k_i}}\right)$ what you do is, for each $i$, pick a $k_i$, then form the product of all the corresponding $\displaystyle \frac{x^{ik_i}}{k_i!(i!)^{k_i}}$, resulting in $\displaystyle \prod_{i=1}^\infty\frac{x^{i k_i}}{k_i!(i!)^{k_i}}$, and then add all these expressions, but that is precisely what the displayed sum is. (Of course, one picks $k_i=0$ for almost all $i$ in order for the expressions to be meaningful.)

As the comments with Brian indicate, the confusion is perhaps over the way the author is using notation. It is perhaps better to write the first expression as follows: Let ${\mathbb N}^{\mathbb N}_*$ be the set of all functions $f:\mathbb N^+\to\mathbb N$ (all sequences) such that $f(n)=0$ for all but finitely many $n$. The first sum is then $$\sum_{f\in\mathbb N^{\mathbb N}_*}\left(\frac{x^{\sum_{i=1}^\infty i f(i)}}{\prod_{i=1}^\infty (f(i))!(i!)^{f(i)}}\right).$$ On the other hand, the product is just $$\prod_{i=1}^\infty \left(\sum_{j=0}^\infty \frac{x^{i j}}{j!(i!)^{j}}\right).$$ When you expand, you pick for each $i$ a $j$ (which, naturally, depends on $i$, so we can call it $f(i)$), with the understanding that you pick $j=0$ almost all the time. Etc.

The way the book writes the expressions, essentially the same notation is used to mean two completely different things: First, $k_i\ge0$ means you are looking at an infinite sequences $(k_1,k_2,\dots)$ with almost all $k_i$ being $0$ (this is just an $f\in{\mathbb N}^{\mathbb N}_*$). The second time, in $\sum_{k_i=0}^\infty$, the author now just means $\sum_{n=0}^\infty$, but is using $k_i$ as the index, rather than $n$.

At the bottom of it, what the author is using is a generalized distributive law, a more general case of which would be that in a sufficiently complete Boolean algebra, $$\bigwedge_{a\in X}\bigvee\{u_{a,i}\mid i\in I_a\}=\bigvee_{f\in\prod_{a\in X}I_a}\bigwedge\{u_{a,f(a)}\mid a\in X\}$$ for $X$ a non-empty set, $I_a$ a non-empty index set (for each $a\in X$) and arbitrary elements $u_{a,i}$ of the Boolean algebra (for $a\in X, i\in I_a$), though I doubt that this more general presentation would actually clarify things. This family of generalized distributive laws, by the way, is just a reformulation of the axiom of choice.

One final remark is that it is not capriciousness that makes us look only at functions in $\mathbb N^{\mathbb N}_*$ rather than all functions $f:\mathbb N^+\to\mathbb N$: We are actually looking at all functions, but only the ones in ${\mathbb N}^{\mathbb N}_*$ "matter". There are two ways of interpreting the expansions we have. One is purely formal, and then the convention that almost all $k_i$ must be $0$ is essentially a matter of definitions, but this convention is adopted because of the second way: Namely, we can consider the expansions as defining analytic functions (for an appropriate interval where they converge, typically $|x|<1$).

Note that given a sequence $k_1,k_2,\dots$, we have that $\displaystyle \lim_{n\to\infty}\prod_{i=1}^n \frac{x^{i k_i}}{k_i!(i!)^{k_i}}=0$ if $k_i\ne 0$ infinitely often (more precisely, we say that the product diverges to $0$), essentially because $\displaystyle\frac{x^i}{i!}\to0$ as $i\to\infty$. But then the only sequences $f:i\mapsto k_i$ that contribute to the sum are the ones in ${\mathbb N}^{\mathbb N}_*$ anyway.

• Perhaps I’m missing something perfectly straightforward, but I don’t see any way to justify that interpretation of the expression $$\prod_{i=1}^\infty \left(\sum_{k_i=0}^\infty \frac{x^{ik_i}}{k_i!(i!)^{k_i}}\right)\;.$$ Apr 11, 2013 at 22:13
• @BrianM.Scott It may certainly be that I am confused, but all I am saying is that to expand $(a_1+a_2+\dots)(b_1+b_2+\dots)\dots$ you pick an $a_i$, a $b_j$, a $c_k$, and so on, and multiply them together, and then add over all such indices $(i,j,k,\dots)$ Can you tell me what the issue is? I'll do my best to clarify. Apr 11, 2013 at 22:27
• But what is the inner summation? For a fixed $i$, just what things are being summed? For a fixed value of $k_i$ there are infinitely many sequences $k$ having that value of $k_i$, even with the limitation to finitely many non-zero terms. Apr 11, 2013 at 22:29
• $\displaystyle \sum_{k_i=0}^\infty \frac{x^{ik_i}}{k_i!(i!)^{k_i}}=\sum_{n=0}^\infty \frac{x^{in}}{n!(i!)^n}$. Apr 11, 2013 at 22:31
• All we are doing is the standard $\displaystyle \bigwedge_{n\in\omega}\bigvee_{m\in\omega}a_{n,m}=\bigvee_{f\in{}^\omega\omega} \bigwedge_{n\in\omega}a_{n,f(n)}$. Apr 11, 2013 at 22:34

As a clarification to the answer above, I'd like to point out that the distributive law for infinite products $$\prod_{i\in \mathbb N} \sum_{k\in \mathbb N} \alpha_{i,k} = \sum_{(k_i)_{i\in \mathbb N} \in \mathbb N^\mathbb N} \prod_{i\in \mathbb N} \alpha_{i,k_i}$$ does actually require some justification and hypotheses. It is not a consequence of the distributive law for Boolean algebras. Essentially, this is because addition and multiplication are not the same as minima and maxima.

A simple example to see why extra hypotheses are needed: If $(\beta_k)_{k\in\mathbb N}$ is a sequence of positive numbers with $\sum_k \beta_k = 1$ and $$\alpha_{i,k} = \beta_k,$$ then the left hand side of the distributive law is equal to 1, while the right hand side is equal to 0.

The question of course then becomes what are the right hypotheses, and how do you justify the distributive law under those hypotheses. I don't know of anywhere that this is written up nicely, but if you assume that there exists a sequence $(k_i)_{i\in \mathbb N}\in \mathbb N^\mathbb N$ such that the series

$$\sum_{i\in\mathbb N} \sum_{k\in\mathbb N} \begin{cases} |\alpha_{i,k}| & k \neq k_i\\ |\alpha_{i,k} - 1| & k = k_i \end{cases}$$

converges, then you can prove the distributive law by approximating by finite subsets. In your example, the sequence $k_i = 0$ satisfies this condition.

Here's a brief idea of how to prove the distributive law by approximating by finite subsets. Suppose that $\alpha_i$ is an absolutely summable sequence, and we want to show that $$\prod_{i\in\mathbb N} (1 + \alpha_i) = \sum_{F\subset\mathbb N}\prod_{i\in F}\alpha_i,$$ where the sum is taken over finite subsets of $\mathbb N$. We can demonstrate this as follows: $$\prod_{i\in\mathbb N} (1 + \alpha_i) = \lim_{N\to\infty} \prod_{i = 1}^N (1 + \alpha_i) = \lim_{N\to\infty} \sum_{F\subset\{1,\ldots,N\}} \prod_{i\in F}\alpha_i = \sum_{F\subset\mathbb N}\prod_{i\in F}\alpha_i.$$ The last equality requires some justification. If the terms $\alpha_i$ are nonnegative, then it is immediate. More generally, if the sequence $\alpha_i$ is absolutely summable, then $$\sum_{F\subset\mathbb N} \left|\prod_{i\in F}\alpha_i\right| = \sum_{F\subset\mathbb N}\prod_{i\in F}|\alpha_i| = \prod_{i\in\mathbb N} (1 + |\alpha_i|) < \infty,$$ i.e. the sequence $\left(\prod_{i\in F}\alpha_i\right)_{F\subset\mathbb N}$ is absolutely summable, justifying the last step.