Formalization Blueprint for “An Introduction to Algebraic Combinatorics” by Darij Grinberg

A.2 Details: Infinite products (part 2) – Finite product composition rule

This chapter contains the detailed proof of the finite product composition rule for formal power series (Lemma A.43), which states that substitution (composition) distributes over finite products. This lemma is used in the proof of Proposition 1.399 (the infinite product composition rule), whose detailed proof is also given here.

Lemma A.43

Let \(I\) be a finite set. If \(\left( f_{i}\right) _{i\in I}\in K\left[ \left[ x\right] \right] ^{I}\) is a family of FPSs, and if \(g\in K\left[ \left[ x\right] \right] \) is an FPS satisfying \(\left[ x^{0}\right] g=0\), then \(\left( \prod _{i\in I}f_{i}\right) \circ g=\prod _{i\in I}\left( f_{i}\circ g\right) \).

theorem PowerSeries.comp_prod_finite {K : Type u_1} [CommRing K] {ι : Type u_2} [DecidableEq ι] (s : Finset ι) (f : ιPowerSeries K) (g : PowerSeries K) (hg : constantCoeff g = 0) :
subst g (∏ is, f i) = is, subst g (f i)
Proof

This follows by a straightforward induction on \(\left\vert I\right\vert \).

Base case (\(\left\vert I\right\vert =0\)): The empty product is \(\underline{1}\) (the constant FPS with value \(1\)), and we have \(\underline{1}\circ g=\underline{1}\) for any \(g\in K\left[ \left[ x\right] \right] \). Hence both sides equal \(\underline{1}\).

Induction step: Assume the result holds for all sets of size \(\left\vert I\right\vert - 1\). Pick some \(a\in I\) and write \(\prod _{i\in I}f_{i}=f_{a}\cdot \prod _{i\in I\setminus \left\{ a\right\} }f_{i}\). By Proposition 1.181 (b) (the substitution rule for products: \(\left( u\cdot v\right) \circ g=\left( u\circ g\right) \cdot \left( v\circ g\right) \)), we have

\[ \left( f_{a}\cdot \prod _{i\in I\setminus \left\{ a\right\} }f_{i}\right) \circ g=\left( f_{a}\circ g\right) \cdot \left( \prod _{i\in I\setminus \left\{ a\right\} }f_{i}\right) \circ g. \]

By the induction hypothesis (applied to the set \(I\setminus \left\{ a\right\} \), which has size \(\left\vert I\right\vert -1\)),

\[ \left( \prod _{i\in I\setminus \left\{ a\right\} }f_{i}\right) \circ g=\prod _{i\in I\setminus \left\{ a\right\} }\left( f_{i}\circ g\right) . \]

Combining, we obtain

\[ \left( \prod _{i\in I}f_{i}\right) \circ g=\left( f_{a}\circ g\right) \cdot \prod _{i\in I\setminus \left\{ a\right\} }\left( f_{i}\circ g\right) =\prod _{i\in I}\left( f_{i}\circ g\right) . \]

A.2.1 Detailed proof of Proposition 1.399

Detailed proof of Proposition 1.399.

Let \(\left( f_{i}\right) _{i\in I}\in K\left[ \left[ x\right] \right] ^{I}\) be a multipliable family of FPSs. Let \(g\in K\left[ \left[ x\right] \right] \) be an FPS satisfying \(\left[ x^{0}\right] g=0\).

We shall first show the following auxiliary claim:

Claim 1: Let \(M\) be an \(x^{n}\)-approximator for \(\left( f_{i}\right) _{i\in I}\). Then, the set \(M\) determines the \(x^{n}\)-coefficient in the product of \(\left( f_{i}\circ g\right) _{i\in I}\).

[Proof of Claim 1: The set \(M\) is an \(x^{n}\)-approximator for \(\left( f_{i}\right) _{i\in I}\). In other words, \(M\) is a finite subset of \(I\) that determines the first \(n+1\) coefficients in the product of \(\left( f_{i}\right) _{i\in I}\) (by the definition of “\(x^{n}\)-approximator”).

Let \(J\) be a finite subset of \(I\) satisfying \(M\subseteq J\subseteq I\). Then, Lemma A.43 (applied to \(J\) instead of \(I\)) yields

\begin{equation} \left( \prod _{i\in J}f_{i}\right) \circ g=\prod _{i\in J}\left( f_{i}\circ g\right) . \label{pf.prop.fps.subs.rule-infprod.3}\end{equation}
1

Also, Lemma A.43 (applied to \(M\) instead of \(I\)) yields

\begin{equation} \left( \prod _{i\in M}f_{i}\right) \circ g=\prod _{i\in M}\left( f_{i}\circ g\right) . \label{pf.prop.fps.subs.rule-infprod.4}\end{equation}
2

However, Proposition 1.364 (a) (applied to \(\mathbf{a}_{i}=f_{i}\)) yields

\[ \prod _{i\in J}f_{i}\overset {x^{n}}{\equiv }\prod _{i\in M}f_{i}. \]

We also have \(g\overset {x^{n}}{\equiv }g\) (since the relation \(\overset {x^{n}}{\equiv }\) is an equivalence relation). Hence, Proposition 1.338 (applied to \(a=\prod _{i\in J}f_{i}\) and \(b=\prod _{i\in M}f_{i}\) and \(c=g\) and \(d=g\)) yields

\[ \left( \prod _{i\in J}f_{i}\right) \circ g\overset {x^{n}}{\equiv }\left( \prod _{i\in M}f_{i}\right) \circ g. \]

In view of (1) and (2), this rewrites as

\[ \prod _{i\in J}\left( f_{i}\circ g\right) \overset {x^{n}}{\equiv }\prod _{i\in M}\left( f_{i}\circ g\right) . \]

In other words,

\[ \text{each }m\in \left\{ 0,1,\ldots ,n\right\} \text{ satisfies }\left[ x^{m}\right] \left( \prod _{i\in J}\left( f_{i}\circ g\right) \right) =\left[ x^{m}\right] \left( \prod _{i\in M}\left( f_{i}\circ g\right) \right) \]

(by the definition of the relation \(\overset {x^{n}}{\equiv }\)). Applying this to \(m=n\), we obtain

\[ \left[ x^{n}\right] \left( \prod _{i\in J}\left( f_{i}\circ g\right) \right) =\left[ x^{n}\right] \left( \prod _{i\in M}\left( f_{i}\circ g\right) \right) . \]

Forget that we fixed \(J\). We thus have shown that every finite subset \(J\) of \(I\) satisfying \(M\subseteq J\subseteq I\) satisfies

\[ \left[ x^{n}\right] \left( \prod _{i\in J}\left( f_{i}\circ g\right) \right) =\left[ x^{n}\right] \left( \prod _{i\in M}\left( f_{i}\circ g\right) \right) . \]

In other words, the set \(M\) determines the \(x^{n}\)-coefficient in the product of \(\left( f_{i}\circ g\right) _{i\in I}\) (by the definition of what it means to “determine the \(x^{n}\)-coefficient in the product of \(\left( f_{i}\circ g\right) _{i\in I}\)”). This proves Claim 1.]

Now, let \(n\in \mathbb {N}\). Lemma 1.363 (applied to \(\mathbf{a}_{i}=f_{i}\)) shows that there exists an \(x^{n}\)-approximator for \(\left( f_{i}\right) _{i\in I}\). Consider this \(x^{n}\)-approximator for \(\left( f_{i}\right) _{i\in I}\), and denote it by \(M\). Thus, \(M\) is an \(x^{n}\)-approximator for \(\left( f_{i}\right) _{i\in I}\); in other words, \(M\) is a finite subset of \(I\) that determines the first \(n+1\) coefficients in the product of \(\left( f_{i}\right) _{i\in I}\) (by the definition of “\(x^{n}\)-approximator”). Claim 1 shows that the set \(M\) determines the \(x^{n}\)-coefficient in the product of \(\left( f_{i}\circ g\right) _{i\in I}\). Hence, there is a finite subset of \(I\) that determines the \(x^{n}\)-coefficient in the product of \(\left( f_{i}\circ g\right) _{i\in I}\) (namely, \(M\)). In other words, the \(x^{n}\)-coefficient in the product of \(\left( f_{i}\circ g\right) _{i\in I}\) is finitely determined.

Forget that we fixed \(n\). We thus have shown that for each \(n\in \mathbb {N}\), the \(x^{n}\)-coefficient in the product of \(\left( f_{i}\circ g\right) _{i\in I}\) is finitely determined. In other words, each coefficient in the product of \(\left( f_{i}\circ g\right) _{i\in I}\) is finitely determined. In other words, the family \(\left( f_{i}\circ g\right) _{i\in I}\) is multipliable (by the definition of “multipliable”).

It remains to prove that \(\left( \prod _{i\in I}f_{i}\right) \circ g=\prod _{i\in I}\left( f_{i}\circ g\right) \).

In order to do so, we again fix \(n\in \mathbb {N}\). Lemma 1.363 (applied to \(\mathbf{a}_{i}=f_{i}\)) shows that there exists an \(x^{n}\)-approximator for \(\left( f_{i}\right) _{i\in I}\). Consider this \(x^{n}\)-approximator for \(\left( f_{i}\right) _{i\in I}\), and denote it by \(M\). Thus, \(M\) is an \(x^{n}\)-approximator for \(\left( f_{i}\right) _{i\in I}\); in other words, \(M\) is a finite subset of \(I\) that determines the first \(n+1\) coefficients in the product of \(\left( f_{i}\right) _{i\in I}\) (by the definition of “\(x^{n}\)-approximator”). Moreover, Proposition 1.364 (b) (applied to \(\mathbf{a}_{i}=f_{i}\)) yields

\begin{equation} \prod _{i\in I}f_{i}\overset {x^{n}}{\equiv }\prod _{i\in M}f_{i}. \label{pf.prop.fps.subs.rule-infprod.1}\end{equation}
3

We also have \(g\overset {x^{n}}{\equiv }g\) (since the relation \(\overset {x^{n}}{\equiv }\) is an equivalence relation). Hence, Proposition 1.338 (applied to \(a=\prod _{i\in I}f_{i}\) and \(b=\prod _{i\in M}f_{i}\) and \(c=g\) and \(d=g\)) yields

\begin{equation} \left( \prod _{i\in I}f_{i}\right) \circ g\overset {x^{n}}{\equiv }\left( \prod _{i\in M}f_{i}\right) \circ g. \label{pf.prop.fps.subs.rule-infprod.2}\end{equation}
4

However, Lemma A.43 (applied to \(M\) instead of \(I\)) yields

\[ \left( \prod _{i\in M}f_{i}\right) \circ g=\prod _{i\in M}\left( f_{i}\circ g\right) . \]

In view of this, we can rewrite (4) as

\[ \left( \prod _{i\in I}f_{i}\right) \circ g\overset {x^{n}}{\equiv }\prod _{i\in M}\left( f_{i}\circ g\right) . \]

In other words,

\[ \text{each }m\in \left\{ 0,1,\ldots ,n\right\} \text{ satisfies }\left[ x^{m}\right] \left( \left( \prod _{i\in I}f_{i}\right) \circ g\right) =\left[ x^{m}\right] \left( \prod _{i\in M}\left( f_{i}\circ g\right) \right) \]

(by the definition of the relation \(\overset {x^{n}}{\equiv }\)). Applying this to \(m=n\), we obtain

\begin{equation} \left[ x^{n}\right] \left( \left( \prod _{i\in I}f_{i}\right) \circ g\right) =\left[ x^{n}\right] \left( \prod _{i\in M}\left( f_{i}\circ g\right) \right) . \label{pf.prop.fps.subs.rule-infprod.6}\end{equation}
5

However, Claim 1 shows that the set \(M\) determines the \(x^{n}\)-coefficient in the product of \(\left( f_{i}\circ g\right) _{i\in I}\). Hence, the definition of the infinite product \(\prod _{i\in I}\left( f_{i}\circ g\right) \) (specifically, Definition 1.343 (b)) yields

\[ \left[ x^{n}\right] \left( \prod _{i\in I}\left( f_{i}\circ g\right) \right) =\left[ x^{n}\right] \left( \prod _{i\in M}\left( f_{i}\circ g\right) \right) . \]

Comparing this with (5), we obtain

\[ \left[ x^{n}\right] \left( \left( \prod _{i\in I}f_{i}\right) \circ g\right) =\left[ x^{n}\right] \left( \prod _{i\in I}\left( f_{i}\circ g\right) \right) . \]

Forget that we fixed \(n\). We thus have shown that each \(n\in \mathbb {N}\) satisfies

\[ \left[ x^{n}\right] \left( \left( \prod _{i\in I}f_{i}\right) \circ g\right) =\left[ x^{n}\right] \left( \prod _{i\in I}\left( f_{i}\circ g\right) \right) . \]

In other words, the FPSs \(\left( \prod _{i\in I}f_{i}\right) \circ g\) and \(\prod _{i\in I}\left( f_{i}\circ g\right) \) agree in all their coefficients. Hence, \(\left( \prod _{i\in I}f_{i}\right) \circ g=\prod _{i\in I}\left( f_{i}\circ g\right) \). This completes our proof of Proposition 1.399.