description/proof of that for index set, sum by \(n\)-th power of index set is sum by quotient set of \(n\)-th power index set of sum by quotient set of \(n\)-symmetric group
Topics
About: set
The table of contents of this article
Starting Context
- The reader knows a definition of product set.
- The reader knows a definition of quotient set.
- The reader knows a definition of \(n\)-symmetric group.
- The reader knows a definition of representatives set of quotient set.
Target Context
- The reader will have a description and a proof of the proposition that for any index set, the sum by the \(n\)-th power of the index set is the sum by the canonical quotient set of the \(n\)-th power index set of the sum by the canonical quotient set of the \(n\)-symmetric group for each element of the quotient set of the \(n\)-th power index set.
Orientation
There is a list of definitions discussed so far in this site.
There is a list of propositions discussed so far in this site.
Main Body
1: Structured Description
Here is the rules of Structured Description.
Entities:
\(J\): \(\in \{\text{ the index sets }\}\)
\(n\): \(\in \mathbb{N} \setminus \{0\}\)
\(J^n\): \(= \text{ the product set }\)
\(S_n\): \(= \text{ the } n \text{ -symmetric group }\)
\(\sim\): \(\in \{\text{ the equivalence relations on } J^n\}\), such that \(\forall j = (j_1, ..., j_n), j' = (j'_1, ..., j'_n) \in J^n (j \sim j' \iff \exists \sigma \in S_n ((j_{\sigma_1}, ..., j_{\sigma_n}) = (j'_1, ..., j'_n)))\)
\(J^n / \sim\): \(= \text{ the quotient set }\)
\(\overline{J^n / \sim - f}\): \(= \text{ the representatives set of } J^n / \sim\), where \(f: J^n / \sim \to J^n\), the representatives map, is chosen arbitrarily
\(\{\sim_{j} \vert j \in \overline{J^n / \sim - f}\}\): \(\sim_{j} \in \{\text{ the equivalent relations of } S_n\}\), such that \(\forall \sigma, \sigma' \in S_n (\sigma \sim_{j} \sigma' \iff (j_{\sigma_1}, ..., j_{\sigma_n}) = (j_{\sigma'_1}, ..., j_{\sigma'_n}))\)
\(\{S_n / \sim_{j} \vert j \in \overline{J^n / \sim - f}\}\}\): \(S_n / \sim_{j} \in \{\text{ the quotient sets }\}\)
//
Statements:
\(\sum_{j \in J^n} = \sum_{j \in \overline{J^n / \sim - f}} \sum_{\sigma \in S_n / \sim_{j}} = \sum_{[j] \in J^n / \sim} \sum_{\sigma \in S_n / \sim_{f ([j])}}\)
//
2: Note
What is being done is really just a common sense: \(J^n\) is divided into the subsets each of which is the permutations of a combination ('combination' means any element of \(J^n / \sim\)).
For example, when \(j = \{1, 2\}\) and \(n = 3\), \(J^n = \{(1, 1, 1), (1, 1, 2), (1, 2, 1), (1, 2, 2), (2, 1, 1), (2, 1, 2), (2, 2, 1), (2, 2, 2)\}\), \(J^n / \sim = \{\{(1, 1, 1)\}, \{(1, 1, 2), (1, 2, 1), (2, 1, 1)\}, \{(1, 2, 2), (2, 1, 2), (2, 2, 1)\}, \{(2, 2, 2)\}\}\), \(\overline{J^n / \sim - f} = \{(1, 1, 1), (1, 1, 2), (1, 2, 2), (2, 2, 2)\}\) as a choice, and \(\sum_{j \in J^n}\) is accomplished by taking each element of \(\overline{J^n / \sim - f}\), summing by all the distinct permutations of the element, and summing up the sums.
The point of this proposition is offering an exact notation of the intuitively natural procedure.
\(\sim_{j}\) depends on the choice of \(f\) (the choice of the representative for each class).
For example, when \(j = \{1, 2\}\) and \(n = 3\), if \((1, 1, 2)\) is a representative, \((1, 2, 3) \mapsto (1, 2, 3) \in S_n\) and \((1, 2, 3) \mapsto (2, 1, 3) \in S_n\) will be equivalent, but if \((1, 2, 1)\) is a representative, \((1, 2, 3) \mapsto (1, 2, 3) \in S_n\) and \((1, 2, 3) \mapsto (2, 1, 3) \in S_n\) will not be equivalent (instead, \((1, 2, 3) \mapsto (1, 2, 3) \in S_n\) and \((1, 2, 3) \mapsto (3, 2, 1) \in S_n\) will be equivalent).
Nevertheless, \(\sum_{\sigma \in S_n / \sim_{j}}\) covers the same set of permutations for the class \([j]\).
When \(J\) is linearly-ordered, a natural choice for the representative of \([(j_1, ..., j_n)]\) is \(j_1 \le ... \le j_n\) (or \(j_n \le ... \le j_1\)).
The motivation for this proposition is that often, the summand of \(\sum_{j \in J^n}\) depends (totally or partially) on the combination \([j]\), and then, thinking \(\sum_{j \in J^n}\) as \(\sum_{j \in \overline{J^n / \sim - f}} \sum_{\sigma \in S_n / \sim_{j}}\) can become handy: for example, when the summand depends totally on \([j]\), \(\sum_{j \in \overline{J^n / \sim - f}} \sum_{\sigma \in S_n / \sim_{j}} = \sum_{j \in \overline{J^n / \sim - f}} \vert S_n / \sim_{j} \vert\) where \(\vert S_n / \sim_{j} \vert\) denotes the cardinality of \(S_n / \sim_{j}\).
3: Proof
Whole Strategy: Step 1: see that \(\sim\) is indeed an equivalence relation; Step 2: see that \(\sim_{j}\) is indeed an equivalence relation; Step 3: see that \(\sum_{j \in J^n} = \sum_{j \in \overline{J^n / \sim - f}} \sum_{\sigma \in S_n / \sim_{j}} = \sum_{[j] \in J^n / \sim} \sum_{\sigma \in S_n / \sim_{f ([j])}}\).
Step 1:
Let us see that \(\sim\) is indeed an equivalence relation.
For each \(j = (j_1, ..., j_n) \in J^n\), \(j \sim j\), because there is \(\sigma = id \in S_n\) such that \((j_{\sigma_1}, ..., j_{\sigma_n}) = (j_1, ..., j_n)\).
For each \(j = (j_1, ..., j_n), j' = (j'_1, ..., j'_n) \in J^n\) such that \(j \sim j'\), \(j' \sim j\), because while there is a \(\sigma \in S_n\) such that \((j_{\sigma_1}, ..., j_{\sigma_n}) = (j'_1, ..., j'_n)\), there is \(\sigma^{-1} \in S_n\) such that \((j'_{{\sigma^{-1}}_1}, ..., j'_{{\sigma^{-1}}_n}) = (j_1, ..., j_n)\), which is true because while there is a \(\sigma_l = \sigma (l) = 1\), \(l = \sigma^{-1} (1)\), and \(j_1 = j_{\sigma_l} = j'_l = j'_{\sigma^{-1} (1)}\).
For each \(j = (j_1, ..., j_n), j' = (j'_1, ..., j'_n), j'' = (j''_1, ..., j''_n) \in J^n\) such that \(j \sim j'\) and \(j' \sim j''\), \(j \sim j''\), because while there are a \(\sigma \in S_n\) such that \((j_{\sigma_1}, ..., j_{\sigma_n}) = (j'_1, ..., j'_n)\) and a \(\sigma' \in S_n\) such that \((j'_{\sigma'_1}, ..., j'_{\sigma'_n}) = (j''_1, ..., j''_n)\), there is \(\sigma \circ \sigma' \in S_n\) such that \((j_{(\sigma \circ \sigma')_1}, ..., j_{(\sigma \circ \sigma')_n}) = (j''_1, ..., j''_n)\), which is true because while \(j''_1 = j'_{\sigma'_1}\), \(\sigma'_1 = l\) for an \(l\) and \(j'_{\sigma'_1} = j'_l = j_{\sigma_l} = j_{\sigma (l)} = j_{\sigma (\sigma'_1)} = j_{\sigma (\sigma' (1))} = j_{\sigma \circ \sigma' (1)} = j_{\sigma \circ \sigma'_1}\), so, \(j''_1 = j_{\sigma \circ \sigma'_1}\).
Step 2:
Let us see that \(\sim_{j}\) is indeed an equivalence relation.
For each \(\sigma \in S_n\), \(\sigma \sim_{j} \sigma\), because \((j_{\sigma_1}, ..., j_{\sigma_n}) = (j_{\sigma_1}, ..., j_{\sigma_n})\).
For each \(\sigma, \sigma' \in S_n\) such that \(\sigma \sim_{j} \sigma'\), \(\sigma' \sim_{j} \sigma\), because while \((j_{\sigma_1}, ..., j_{\sigma_n}) = (j_{\sigma'_1}, ..., j_{\sigma'_n})\), \((j_{\sigma'_1}, ..., j_{\sigma'_n}) = (j_{\sigma_1}, ..., j_{\sigma_n})\).
For each \(\sigma, \sigma', \sigma'' \in S_n\) such that \(\sigma \sim_{j} \sigma'\) and \(\sigma' \sim_{j} \sigma''\), \(\sigma \sim_{j} \sigma''\), because while \((j_{\sigma_1}, ..., j_{\sigma_n}) = (j_{\sigma'_1}, ..., j_{\sigma'_n})\) and \((j_{\sigma'_1}, ..., j_{\sigma'_n}) = (j_{\sigma''_1}, ..., j_{\sigma''_n})\), \((j_{\sigma_1}, ..., j_{\sigma_n}) = (j_{\sigma'_1}, ..., j_{\sigma'_n}) = (j_{\sigma''_1}, ..., j_{\sigma''_n})\).
Step 3:
Let us see that \(\sum_{j \in J^n} = \sum_{j \in \overline{J^n / \sim - f}} \sum_{\sigma \in S_n / \sim_{j}}\).
There is no duplication in \(\sum_{j \in J^n}\), obviously.
There is no duplication in \(\sum_{j \in \overline{J^n / \sim - f}} \sum_{\sigma \in S_n / \sim_{j}}\), because while there is no duplication in \(\sum_{j \in \overline{J^n / \sim - f}}\), there is no duplication in the corresponding \(\{[j]\}\), and for each \([j]\), there is no duplication in \(\sum_{\sigma \in S_n / \sim_{j}}\) because \(\sigma \in S_n / \sim_{j}\) is determined exactly for that effect, and there is no duplication between \([j]\) and \([j']\) because \([j]\) and \([j']\) represent some different combinations and permutating any combination does not change the combination.
Each element of \(\sum_{j \in J^n}\) exists in \(\sum_{j \in \overline{J^n / \sim - f}} \sum_{\sigma \in S_n / \sim_{j}}\), because the element is of a combination whose representative is in \(\sum_{j \in \overline{J^n / \sim - f}}\), and the element is a permutation of the combination, which is in the corresponding \(\sum_{\sigma \in S_n / \sim_{j}}\).
Each element of \(\sum_{j \in \overline{J^n / \sim - f}} \sum_{\sigma \in S_n / \sim_{j}}\) obviously exists in \(\sum_{j \in J^n}\).
So, \(\sum_{j \in J^n} = \sum_{j \in \overline{J^n / \sim - f}} \sum_{\sigma \in S_n / \sim_{j}}\).
\(\sum_{j \in \overline{J^n / \sim - f}} \sum_{\sigma \in S_n / \sim_{j}} = \sum_{[j] \in J^n / \sim} \sum_{\sigma \in S_n / \sim_{f ([j])}}\) is just an obvious reformulation: the latter is taking the class, \([j]\), instead of its representative, \(j\), but anyway, \(\sum_{\sigma \in S_n / \sim_{j}} = \sum_{\sigma \in S_n / \sim_{f ([j])}}\) because \(j = f ([j])\).
