Acknowledgments. I have used GPT-5.4 via Christian Stump’s convenient https://sciencebench.ai/ front-end. I thank Christian for his work on this.
n n n The notion of an n n n [13 ] (based on an idea of Wiles [14 proof of Lemma 2.2.3] ).
We first introduce some notations. Rings are always understood to be associative and unital (but not necessarily commutative); ring morphisms preserve the unity (unless we speak of “nonunital ring morphisms”). For any nonnegative integer n n n [ n ] [n] [ n ] { 1 , 2 , … , n } \{1,2,\ldots,n\} { 1 , 2 , … , n } S n S_n S n n n n [ n ] [n] [ n ] σ \sigma σ [ n ] [n] [ n ] ( − 1 ) σ (-1)^\sigma ( − 1 ) σ σ \sigma σ σ ∈ S n \sigma\in S_n σ ∈ S n ( − 1 ) σ = ( − 1 ) ℓ ( σ ) (-1)^\sigma= (-1)^{\ell(\sigma)} ( − 1 ) σ = ( − 1 ) ℓ ( σ ) ℓ ( σ ) \ell(\sigma) ℓ ( σ ) σ . ) \sigma.) σ . )
The cycles of a permutation σ \sigma σ
[ 7 ] → [ 7 ] , i ↦ 8 − i \begin{aligned}
[7] &\to[7],\\
i &\mapsto8-i
\end{aligned} [ 7 ] i → [ 7 ] , ↦ 8 − i of [7] has the four cycles ( 1 , 7 ) (1,7) ( 1 , 7 ) ( 2 , 6 ) (2,6) ( 2 , 6 ) ( 3 , 5 ) (3,5) ( 3 , 5 ) ( 4 ) (4) ( 4 ) ( 2 , 6 ) (2,6) ( 2 , 6 ) ( 6 , 2 ) (6,2) ( 6 , 2 )
In [2 ] , Buchstaber and Rees defined the notion of an n n n [3 ] , [4 ] and [8 ] (among other works), although mostly only for commutative Q \mathbb{Q} Q n n n A A A B B B
Definition 0.1. Let A A A B B B f : A → B f:A \to B f : A → B Z \mathbb{Z} Z
(a) We say that f f f central if we have
f ( a a ′ ) = f ( a ′ a ) for all a , a ′ ∈ A . f(aa')=f(a'a) \qquad\text{for all } a,a'\in A. f ( a a ′ ) = f ( a ′ a ) for all a , a ′ ∈ A . (b) If f f f n n n Z \mathbb{Z} Z f n : A n → B f_n:A^n\to B f n : A n → B
f n ( a 1 , a 2 , … , a n ) = ∑ σ ∈ S n ( − 1 ) σ ∏ c = ( i 1 , i 2 , … , i k ) is a cycle of σ f ( a i 1 a i 2 ⋯ a i k ) . (1) \begin{aligned}
f_n(a_1,a_2,\ldots,a_n)
&=\sum_{\sigma\in S_n}(-1)^\sigma
\prod_{\substack{c=(i_1,i_2,\ldots,i_k)\\\text{is a cycle of }\sigma}}
f(a_{i_1}a_{i_2}\cdots a_{i_k}). \tag*{(1)}
\end{aligned} f n ( a 1 , a 2 , … , a n ) = σ ∈ S n ∑ ( − 1 ) σ c = ( i 1 , i 2 , … , i k ) is a cycle of σ ∏ f ( a i 1 a i 2 ⋯ a i k ) . (1) (we will see in a moment why this is well-defined). For example, for n = 3 n=3 n = 3
f 3 ( a 1 , a 2 , a 3 ) = f ( a 1 ) f ( a 2 ) f ( a 3 ) − f ( a 1 ) f ( a 2 a 3 ) − f ( a 2 ) f ( a 1 a 3 ) − f ( a 3 ) f ( a 1 a 2 ) + f ( a 1 a 2 a 3 ) + f ( a 1 a 3 a 2 ) . \begin{aligned}
f_3(a_1,a_2,a_3)={}&f(a_1)f(a_2)f(a_3)-f(a_1)f(a_2a_3)-f(a_2)f(a_1a_3)\\
&-f(a_3)f(a_1a_2)+f(a_1a_2a_3)+f(a_1a_3a_2).
\end{aligned} f 3 ( a 1 , a 2 , a 3 ) = f ( a 1 ) f ( a 2 ) f ( a 3 ) − f ( a 1 ) f ( a 2 a 3 ) − f ( a 2 ) f ( a 1 a 3 ) − f ( a 3 ) f ( a 1 a 2 ) + f ( a 1 a 2 a 3 ) + f ( a 1 a 3 a 2 ) . (here, the first addend corresponds to the permutation σ = i d ∈ S 3 \sigma=\mathrm{id}\in S_3 σ = id ∈ S 3 ( 1 ) (1) ( 1 ) ( 2 ) (2) ( 2 ) ( 3 ) (3) ( 3 ) t 2 , 3 ∈ S 3 t_{2,3}\in S_3 t 2 , 3 ∈ S 3 ( 1 ) (1) ( 1 ) ( 2 , 3 ) (2,3) ( 2 , 3 ) t 1 , 3 t_{1,3} t 1 , 3 t 1 , 2 t_{1,2} t 1 , 2 S 3 S_3 S 3
Note that the right hand side of (1) is well-defined, since the centrality of f f f f ( a i 1 a i 2 ⋯ a i k ) f(a_{i_1}a_{i_2}\cdots a_{i_k}) f ( a i 1 a i 2 ⋯ a i k ) c c c ( i 1 , i 2 , … , i k ) (i_1,i_2,\ldots,i_k) ( i 1 , i 2 , … , i k ) ( i p , i p + 1 , … , i k , i 1 , i 2 , … , i p − 1 ) (i_p,i_{p+1},\ldots,i_k,i_1,i_2,\ldots,i_{p-1}) ( i p , i p + 1 , … , i k , i 1 , i 2 , … , i p − 1 ) f f f
f ( a i 1 a i 2 ⋯ a i k ) = f ( a i p a i p + 1 ⋯ a i k a i 1 a i 2 ⋯ a i p − 1 ) . f(a_{i_1}a_{i_2}\cdots a_{i_k})=f(a_{i_p}a_{i_{p+1}}\cdots a_{i_k}a_{i_1}a_{i_2}\cdots a_{i_{p-1}}). f ( a i 1 a i 2 ⋯ a i k ) = f ( a i p a i p + 1 ⋯ a i k a i 1 a i 2 ⋯ a i p − 1 ) . The map f n f_n f n n-Frobenius map of f f f a , b , c ∈ A a,b,c \in A a , b , c ∈ A
f 0 ( ) = 1 ; f 1 ( a ) = f ( a ) ; f 2 ( a , b ) = f ( a ) f ( b ) − f ( a b ) ; f 3 ( a , b , c ) = f ( a ) f ( b ) f ( c ) − f ( a ) f ( b c ) − f ( b ) f ( a c ) − f ( c ) f ( a b ) + f ( a b c ) + f ( a c b ) . \begin{aligned}
f_0() &= 1;\\
f_1(a) &= f(a);\\
f_2(a,b) &= f(a)f(b)-f(ab);\\
f_3(a,b,c) &= f(a)f(b)f(c)-f(a)f(bc)\\
&\quad-f(b)f(ac)-f(c)f(ab)+f(abc)+f(acb).
\end{aligned} f 0 ( ) f 1 ( a ) f 2 ( a , b ) f 3 ( a , b , c ) = 1 ; = f ( a ) ; = f ( a ) f ( b ) − f ( ab ) ; = f ( a ) f ( b ) f ( c ) − f ( a ) f ( b c ) − f ( b ) f ( a c ) − f ( c ) f ( ab ) + f ( ab c ) + f ( a c b ) . As we will soon see (Proposition 0.6), the map f n f_n f n
f n ( a 1 , a 2 , … , a n ) = f ( a n ) f n − 1 ( a 1 , a 2 , … , a n − 1 ) − ∑ i = 1 n − 1 f n − 1 ( a 1 , a 2 , … , a i − 1 , a i a n , a i + 1 , a i + 2 , … , a n − 1 ) . (2) \begin{aligned}
f_n(a_1,a_2,\ldots,a_n)
&=f(a_n)f_{n-1}(a_1,a_2,\ldots,a_{n-1})\\
&\quad-\sum_{i=1}^{n-1}f_{n-1}(a_1,a_2,\ldots,a_{i-1},a_i a_n,a_{i+1},a_{i+2},\ldots,a_{n-1}). \tag*{(2)}
\end{aligned} f n ( a 1 , a 2 , … , a n ) = f ( a n ) f n − 1 ( a 1 , a 2 , … , a n − 1 ) − i = 1 ∑ n − 1 f n − 1 ( a 1 , a 2 , … , a i − 1 , a i a n , a i + 1 , a i + 2 , … , a n − 1 ) . (2) (c) Let n n n f f f n n n Frobenius n-homomorphism ) if f f f f n + 1 = 0 f_{n+1}=0 f n + 1 = 0
Example 0.2. The only 0-homomorphism is the zero map. The 1-homomorphisms are just the nonunital ring homomorphisms. The 2-homomorphisms are the central maps f : A → B f:A\to B f : A → B
f ( a ) f ( b ) f ( c ) − f ( a ) f ( b c ) − f ( b ) f ( a c ) − f ( c ) f ( a b ) + f ( a b c ) + f ( a c b ) = 0 f(a)f(b)f(c)-f(a)f(bc)-f(b)f(ac)-f(c)f(ab)+f(abc)+f(acb)=0 f ( a ) f ( b ) f ( c ) − f ( a ) f ( b c ) − f ( b ) f ( a c ) − f ( c ) f ( ab ) + f ( ab c ) + f ( a c b ) = 0 for all a , b , c ∈ A a,b,c\in A a , b , c ∈ A
An example of an n n n Tr : B n × n → B \operatorname{Tr}:B^{n\times n}\to B Tr : B n × n → B B n × n B^{n\times n} B n × n n × n n\times n n × n Tr n + 1 = 0 \operatorname{Tr}_{n+1}=0 Tr n + 1 = 0 B n × n B^{n\times n} B n × n fundamental trace identity for n × n n\times n n × n [9 Corollary] , [Dotsen11, Theorem 1], [10 §VII.7.3.2] or [11 Theorem 4.3 (b)] .
This general concept of an n n n [10 §VII.7.3] , [Bellai10, Definition 2.2], [12 ] , [5 ] , generalizing the pseudorepresentations introduced by Taylor [13 ] (which, in turn, were based on an idea of Wiles [14 proof of Lemma 2.2.3] ). Again, much of the literature requires that A A A Q \mathbb{Q} Q n ! n! n ! n n n Z \mathbb{Z} Z f : A → B f:A\to B f : A → B A A A B B B n n n B B B
f ~ : B ⊗ Z A → B , b ⊗ a ↦ b f ( a ) \widetilde{f}:B\otimes_{\mathbb{Z}}A\to B,\qquad b\otimes a\mapsto bf(a) f : B ⊗ Z A → B , b ⊗ a ↦ b f ( a ) is a pseudocharacter of degree n n n B B B f : A → B f:A\to B f : A → B B B B A A A B B B n n n n n n n n n n n n n n n
In this note, I will prove certain basic (but nontrivial) properties of n n n [8 Theorem 3.2] , without assuming A A A n ! n! n ! [8 ] becomes unusable in this generality, so one is forced to do combinatorics.
The first main result of this note is a generalization of the first part of [8 Theorem 3.2] (also part of [12 Lemme 2.8] ):1
Theorem 0.3. Let A A A B B B B B B n , m ∈ N n,m\in\mathbb{N} n , m ∈ N f : A → B f:A\to B f : A → B n n n g : A → B g:A\to B g : A → B m m m f + g f+g f + g ( n + m ) (n+m) ( n + m )
In short: the sum of an n n n m m m ( n + m ) (n+m) ( n + m )
The second main result generalizes the second part of [8 Theorem 3.2] :
Theorem 0.4. Let A A A B B B C C C B B B C C C n , m ∈ N n,m\in\mathbb{N} n , m ∈ N f : B → C f:B\to C f : B → C n n n g : A → B g:A\to B g : A → B m m m f ∘ g f\circ g f ∘ g n m nm nm
In short: the composition of an n n n m m m n m nm nm
The proofs will use some auxiliary results that may well be useful on their own. In particular, Theorem 0.11 is a formula for the n n n
Recursion and explicit formula
First, I will pay a debt from Definition 0.1 (b), by proving the equivalence of the two definitions of n n n
Proposition 0.6. Let A A A B B B f : A → B f:A\to B f : A → B Z \mathbb{Z} Z
The recursive definition (2) of f n f_n f n f 0 ( ) : = 1 f_0():=1 f 0 ( ) := 1
Proof sketch. We use (1) as the definition of f n f_n f n f n f_n f n
Let n ≥ 1 n\ge1 n ≥ 1 a 1 , a 2 , … , a n ∈ A a_1,a_2,\ldots,a_n\in A a 1 , a 2 , … , a n ∈ A
f n ( a 1 , a 2 , … , a n ) = ∑ σ ∈ S n ( − 1 ) σ ∏ c = ( i 1 , i 2 , … , i k ) is a cycle of σ f ( a i 1 a i 2 ⋯ a i k ) = ∑ i = 1 n ∑ σ ∈ S n ; σ ( i ) = n ( − 1 ) σ ∏ c = ( i 1 , i 2 , … , i k ) is a cycle of σ f ( a i 1 a i 2 ⋯ a i k ) . (3) \begin{aligned}
f_n(a_1,a_2,\ldots,a_n)
&=\sum_{\sigma\in S_n}(-1)^\sigma\prod_{\substack{c=(i_1,i_2,\ldots,i_k)\\\text{is a cycle of }\sigma}}f(a_{i_1}a_{i_2}\cdots a_{i_k})\\
&=\sum_{i=1}^{n}\ \sum_{\substack{\sigma\in S_n;\\\sigma(i)=n}}(-1)^\sigma\prod_{\substack{c=(i_1,i_2,\ldots,i_k)\\\text{is a cycle of }\sigma}}f(a_{i_1}a_{i_2}\cdots a_{i_k}). \tag*{(3)}
\end{aligned} f n ( a 1 , a 2 , … , a n ) = σ ∈ S n ∑ ( − 1 ) σ c = ( i 1 , i 2 , … , i k ) is a cycle of σ ∏ f ( a i 1 a i 2 ⋯ a i k ) = i = 1 ∑ n σ ∈ S n ; σ ( i ) = n ∑ ( − 1 ) σ c = ( i 1 , i 2 , … , i k ) is a cycle of σ ∏ f ( a i 1 a i 2 ⋯ a i k ) . (3) (since each σ ∈ S n \sigma\in S_n σ ∈ S n σ ( i ) = n \sigma(i)=n σ ( i ) = n i ∈ { 1 , 2 , … , n } i\in\{1,2,\ldots,n\} i ∈ { 1 , 2 , … , n }
We start with the addend for i = n i=n i = n
Each permutation τ ∈ S n − 1 \tau\in S_{n-1} τ ∈ S n − 1 τ ^ ∈ S n \widehat{\tau}\in S_n τ ∈ S n τ ^ ( n ) : = n \widehat{\tau}(n):=n τ ( n ) := n τ ^ ( i ) : = τ ( i ) \widehat{\tau}(i):=\tau(i) τ ( i ) := τ ( i ) i < n i<n i < n τ ↦ τ ^ \tau\mapsto\widehat{\tau} τ ↦ τ S n − 1 S_{n-1} S n − 1 { σ ∈ S n ∣ σ ( n ) = n } \{\sigma\in S_n \mid\sigma(n)=n\} { σ ∈ S n ∣ σ ( n ) = n }
∑ σ ∈ S n ; σ ( n ) = n ( − 1 ) σ ∏ c = ( i 1 , i 2 , … , i k ) is a cycle of σ f ( a i 1 a i 2 ⋯ a i k ) = ∑ τ ∈ S n − 1 ( − 1 ) τ ^ ∏ c = ( i 1 , i 2 , … , i k ) is a cycle of τ ^ f ( a i 1 a i 2 ⋯ a i k ) = ∑ τ ∈ S n − 1 ( − 1 ) τ f ( a n ) ∏ c = ( i 1 , i 2 , … , i k ) is a cycle of τ f ( a i 1 a i 2 ⋯ a i k ) = f ( a n ) ∑ τ ∈ S n − 1 ( − 1 ) τ ∏ c = ( i 1 , i 2 , … , i k ) is a cycle of τ f ( a i 1 a i 2 ⋯ a i k ) = f ( a n ) f n − 1 ( a 1 , a 2 , … , a n − 1 ) . (4) \begin{aligned}
\sum_{\substack{\sigma\in S_n;\\ \sigma(n)=n}}(-1)^\sigma
\prod_{\substack{c=(i_1,i_2,\ldots,i_k)\\\text{is a cycle of }\sigma}}
f(a_{i_1}a_{i_2}\cdots a_{i_k})
&=\sum_{\tau\in S_{n-1}}(-1)^{\widehat{\tau}}
\prod_{\substack{c=(i_1,i_2,\ldots,i_k)\\\text{is a cycle of }\widehat{\tau}}}
f(a_{i_1}a_{i_2}\cdots a_{i_k})\\
&=\sum_{\tau\in S_{n-1}}(-1)^\tau f(a_n)
\prod_{\substack{c=(i_1,i_2,\ldots,i_k)\\\text{is a cycle of }\tau}}
f(a_{i_1}a_{i_2}\cdots a_{i_k})\\
&=f(a_n)\sum_{\tau\in S_{n-1}}(-1)^\tau
\prod_{\substack{c=(i_1,i_2,\ldots,i_k)\\\text{is a cycle of }\tau}}
f(a_{i_1}a_{i_2}\cdots a_{i_k})\\
&=f(a_n)f_{n-1}(a_1,a_2,\ldots,a_{n-1}). \tag*{(4)}
\end{aligned} σ ∈ S n ; σ ( n ) = n ∑ ( − 1 ) σ c = ( i 1 , i 2 , … , i k ) is a cycle of σ ∏ f ( a i 1 a i 2 ⋯ a i k ) = τ ∈ S n − 1 ∑ ( − 1 ) τ c = ( i 1 , i 2 , … , i k ) is a cycle of τ ∏ f ( a i 1 a i 2 ⋯ a i k ) = τ ∈ S n − 1 ∑ ( − 1 ) τ f ( a n ) c = ( i 1 , i 2 , … , i k ) is a cycle of τ ∏ f ( a i 1 a i 2 ⋯ a i k ) = f ( a n ) τ ∈ S n − 1 ∑ ( − 1 ) τ c = ( i 1 , i 2 , … , i k ) is a cycle of τ ∏ f ( a i 1 a i 2 ⋯ a i k ) = f ( a n ) f n − 1 ( a 1 , a 2 , … , a n − 1 ) . (4) Now, let i ∈ { 1 , 2 , … , n − 1 } i\in\{1,2,\ldots,n-1\} i ∈ { 1 , 2 , … , n − 1 } n − 1 n-1 n − 1 a 1 ′ , a 2 ′ , … , a n − 1 ′ a'_1,a'_2,\ldots,a'_{n-1} a 1 ′ , a 2 ′ , … , a n − 1 ′ A A A
( a 1 ′ , a 2 ′ , … , a n − 1 ′ ) : = ( a 1 , a 2 , … , a i − 1 , a i a n , a i + 1 , a i + 2 , … , a n − 1 ) . (5) (a'_1,a'_2,\ldots,a'_{n-1})
:=(a_1,a_2,\ldots,a_{i-1},a_i a_n,a_{i+1},a_{i+2},\ldots,a_{n-1}). \tag*{(5)} ( a 1 ′ , a 2 ′ , … , a n − 1 ′ ) := ( a 1 , a 2 , … , a i − 1 , a i a n , a i + 1 , a i + 2 , … , a n − 1 ) . (5) That is, we set a i ′ : = a i a n a'_i:=a_i a_n a i ′ := a i a n
a r ′ : = a r for all r ≠ i . (6) a'_r:=a_r\qquad\text{for all }r\ne i. \tag*{(6)} a r ′ := a r for all r = i . (6) Let t i , n ∈ S n t_{i,n}\in S_n t i , n ∈ S n i i i n n n τ ∈ S n − 1 \tau\in S_{n-1} τ ∈ S n − 1 τ ^ ∈ S n \widehat{\tau}\in S_n τ ∈ S n n n n n n n τ ^ ∘ t i , n ∈ S n \widehat{\tau}\circ t_{i,n}\in S_n τ ∘ t i , n ∈ S n i → t i , n n → τ ^ n i\xrightarrow{t_{i,n}}n\xrightarrow{\widehat{\tau}}n i t i , n n τ n τ ^ ∘ t i , n \widehat{\tau}\circ t_{i,n} τ ∘ t i , n τ \tau τ
d = ( j 1 , j 2 , … , j ℓ ) d=(j_1,j_2,\ldots,j_\ell) d = ( j 1 , j 2 , … , j ℓ ) be the cycle of τ \tau τ i i i i = j ℓ i=j_\ell i = j ℓ τ \tau τ i i i 1 1 1 ℓ = 1 \ell=1 ℓ = 1 τ ^ ∘ t i , n \widehat{\tau}\circ t_{i,n} τ ∘ t i , n τ \tau τ d d d
d ′ : = ( j 1 , j 2 , … , j ℓ , n ) . d':=(j_1,j_2,\ldots,j_\ell,n). d ′ := ( j 1 , j 2 , … , j ℓ , n ) . (To see this, just observe that τ ^ ∘ t i , n \hat{\tau} \circ t_{i,n} τ ^ ∘ t i , n j ℓ j_{\ell} j ℓ n n n j ℓ = i → t i , n n → τ ^ n j_{\ell}=i \xrightarrow{t_{i,n}} n \xrightarrow{\hat{\tau}} n j ℓ = i t i , n n τ ^ n n → t i , n i = j ℓ → τ ^ j 1 n \xrightarrow{t_{i,n}} i=j_{\ell} \xrightarrow{\hat{\tau}} j_{1} n t i , n i = j ℓ τ ^ j 1 τ ^ ∘ t i , n \hat{\tau} \circ t_{i,n} τ ^ ∘ t i , n τ \tau τ t i , n t_{i,n} t i , n i i i n n n τ ^ ∘ t i , n \hat{\tau} \circ t_{i,n} τ ^ ∘ t i , n d ′ = ( j 1 , j 2 , … , j ℓ , n ) d'=(j_{1},j_{2},\ldots,j_{\ell},n) d ′ = ( j 1 , j 2 , … , j ℓ , n ) τ \tau τ d d d
∏ c = ( i 1 , i 2 , … , i k ) is a cycle of τ ^ ∘ t i , n f ( a i 1 a i 2 ⋯ a i k ) = f ( a j 1 a j 2 ⋯ a j ℓ a n ) ⋅ ∏ c = ( i 1 , i 2 , … , i k ) is a cycle of τ distinct from d f ( a i 1 a i 2 ⋯ a i k ) . (7) \prod_{\substack{c=(i_{1},i_{2},\ldots,i_{k})\\\text{is a cycle of }\hat{\tau}\circ t_{i,n}}} f(a_{i_{1}}a_{i_{2}}\cdots a_{i_{k}})
=
f(a_{j_{1}}a_{j_{2}}\cdots a_{j_{\ell}}a_{n})\cdot
\prod_{\substack{c=(i_{1},i_{2},\ldots,i_{k})\\\text{is a cycle of }\tau\\\text{distinct from }d}} f(a_{i_{1}}a_{i_{2}}\cdots a_{i_{k}}). \tag*{(7)} c = ( i 1 , i 2 , … , i k ) is a cycle of τ ^ ∘ t i , n ∏ f ( a i 1 a i 2 ⋯ a i k ) = f ( a j 1 a j 2 ⋯ a j ℓ a n ) ⋅ c = ( i 1 , i 2 , … , i k ) is a cycle of τ distinct from d ∏ f ( a i 1 a i 2 ⋯ a i k ) . (7) However, for each cycle c = ( i 1 , i 2 , … , i k ) c=(i_{1},i_{2},\ldots,i_{k}) c = ( i 1 , i 2 , … , i k ) τ \tau τ d d d
a i 1 a i 2 ⋯ a i k = a i 1 ′ a i 2 ′ ⋯ a i k ′ . (8) a_{i_{1}}a_{i_{2}}\cdots a_{i_{k}}=a'_{i_{1}}a'_{i_{2}}\cdots a'_{i_{k}}. \tag*{(8)} a i 1 a i 2 ⋯ a i k = a i 1 ′ a i 2 ′ ⋯ a i k ′ . (8) (because c ≠ d c\ne d c = d c c c i i i i 1 , i 2 , … , i k i_{1},i_{2},\ldots,i_{k} i 1 , i 2 , … , i k c c c i i i a i 1 ′ = a i 1 a'_{i_{1}}=a_{i_{1}} a i 1 ′ = a i 1 a i 2 ′ = a i 2 a'_{i_{2}}=a_{i_{2}} a i 2 ′ = a i 2 a i 1 ′ a i 2 ′ ⋯ a i k ′ = a i 1 a i 2 ⋯ a i k a'_{i_{1}}a'_{i_{2}}\cdots a'_{i_{k}}=a_{i_{1}}a_{i_{2}}\cdots a_{i_{k}} a i 1 ′ a i 2 ′ ⋯ a i k ′ = a i 1 a i 2 ⋯ a i k d = ( j 1 , j 2 , … , j ℓ ) d=(j_{1},j_{2},\ldots,j_{\ell}) d = ( j 1 , j 2 , … , j ℓ ) τ \tau τ i i i j ℓ = i j_{\ell}=i j ℓ = i j 1 , j 2 , … , j ℓ − 1 j_{1},j_{2},\ldots,j_{\ell-1} j 1 , j 2 , … , j ℓ − 1 d d d i i i a j 1 ′ = a j 1 a'_{j_{1}}=a_{j_{1}} a j 1 ′ = a j 1 a j 2 ′ = a j 2 a'_{j_{2}}=a_{j_{2}} a j 2 ′ = a j 2 a j ℓ ′ = a i ′ = a i a n = a j ℓ a n a'_{j_{\ell}}=a'_{i}=a_{i}a_{n}=a_{j_{\ell}}a_{n} a j ℓ ′ = a i ′ = a i a n = a j ℓ a n i = j ℓ i=j_{\ell} i = j ℓ
a j 1 ′ a j 2 ′ ⋯ a j ℓ − 1 ′ a j ℓ ′ = a j 1 a j 2 ⋯ a j ℓ − 1 a j ℓ a n = a j 1 a j 2 ⋯ a j ℓ a n . a'_{j_{1}}a'_{j_{2}}\cdots a'_{j_{\ell-1}}a'_{j_{\ell}}
=a_{j_{1}}a_{j_{2}}\cdots a_{j_{\ell-1}}a_{j_{\ell}}a_{n}
=a_{j_{1}}a_{j_{2}}\cdots a_{j_{\ell}}a_{n}. a j 1 ′ a j 2 ′ ⋯ a j ℓ − 1 ′ a j ℓ ′ = a j 1 a j 2 ⋯ a j ℓ − 1 a j ℓ a n = a j 1 a j 2 ⋯ a j ℓ a n . In other words,
a j 1 a j 2 ⋯ a j ℓ a n = a j 1 ′ a j 2 ′ ⋯ a j ℓ − 1 ′ a j ℓ ′ = a j 1 ′ a j 2 ′ ⋯ a j ℓ ′ . (9) a_{j_{1}}a_{j_{2}}\cdots a_{j_{\ell}}a_{n}
=a'_{j_{1}}a'_{j_{2}}\cdots a'_{j_{\ell-1}}a'_{j_{\ell}}
=a'_{j_{1}}a'_{j_{2}}\cdots a'_{j_{\ell}}. \tag*{(9)} a j 1 a j 2 ⋯ a j ℓ a n = a j 1 ′ a j 2 ′ ⋯ a j ℓ − 1 ′ a j ℓ ′ = a j 1 ′ a j 2 ′ ⋯ a j ℓ ′ . (9) Using (9) and (8), we can rewrite (7) as
∏ c = ( i 1 , i 2 , … , i k ) is a cycle of τ ^ ∘ t i , n f ( a i 1 a i 2 ⋯ a i k ) = f ( a j 1 ′ a j 2 ′ ⋯ a j ℓ ′ ) ⋅ ∏ c = ( i 1 , i 2 , … , i k ) is a cycle of τ distinct from d f ( a i 1 ′ a i 2 ′ ⋯ a i k ′ ) = ∏ c = ( i 1 , i 2 , … , i k ) is a cycle of τ f ( a i 1 ′ a i 2 ′ ⋯ a i k ′ ) . (10) \prod_{\substack{c=(i_{1},i_{2},\ldots,i_{k})\\\text{is a cycle of }\hat{\tau}\circ t_{i,n}}} f(a_{i_{1}}a_{i_{2}}\cdots a_{i_{k}})
=
f(a'_{j_{1}}a'_{j_{2}}\cdots a'_{j_{\ell}})\cdot
\prod_{\substack{c=(i_{1},i_{2},\ldots,i_{k})\\\text{is a cycle of }\tau\\\text{distinct from }d}} f(a'_{i_{1}}a'_{i_{2}}\cdots a'_{i_{k}})
=
\prod_{\substack{c=(i_{1},i_{2},\ldots,i_{k})\\\text{is a cycle of }\tau}} f(a'_{i_{1}}a'_{i_{2}}\cdots a'_{i_{k}}). \tag*{(10)} c = ( i 1 , i 2 , … , i k ) is a cycle of τ ^ ∘ t i , n ∏ f ( a i 1 a i 2 ⋯ a i k ) = f ( a j 1 ′ a j 2 ′ ⋯ a j ℓ ′ ) ⋅ c = ( i 1 , i 2 , … , i k ) is a cycle of τ distinct from d ∏ f ( a i 1 ′ a i 2 ′ ⋯ a i k ′ ) = c = ( i 1 , i 2 , … , i k ) is a cycle of τ ∏ f ( a i 1 ′ a i 2 ′ ⋯ a i k ′ ) . (10) Finally,
( − 1 ) τ ^ ∘ t i , n = ( − 1 ) τ ^ ⏟ = ( − 1 ) τ (since τ ^ has the same inversions as τ ) ( − 1 ) t i , n ⏟ = − 1 (since transpositions have sign − 1 ) = − ( − 1 ) τ . (11) (-1)^{\hat{\tau}\circ t_{i,n}}
=
\underbrace{(-1)^{\hat{\tau}}}_{=(-1)^\tau\ \text{(since }\hat{\tau}\text{ has the same inversions as }\tau\text{)}}
\underbrace{(-1)^{t_{i,n}}}_{=-1\ \text{(since transpositions have sign }-1\text{)}}
= -(-1)^\tau. \tag*{(11)} ( − 1 ) τ ^ ∘ t i , n = = ( − 1 ) τ (since τ ^ has the same inversions as τ ) ( − 1 ) τ ^ = − 1 (since transpositions have sign − 1 ) ( − 1 ) t i , n = − ( − 1 ) τ . (11) Forget that we fixed τ \tau τ τ ∈ S n − 1 \tau\in S_{n-1} τ ∈ S n − 1 τ ^ ∘ t i , n ∈ S n \hat{\tau}\circ t_{i,n} \in S_n τ ^ ∘ t i , n ∈ S n i i i n n n τ ↦ τ ^ ∘ t i , n \tau\mapsto\hat{\tau}\circ t_{i,n} τ ↦ τ ^ ∘ t i , n S n − 1 S_{n-1} S n − 1 { σ ∈ S n ∣ σ ( i ) = n } \{\sigma\in S_n \mid\sigma(i)=n\} { σ ∈ S n ∣ σ ( i ) = n } σ ∈ S n \sigma\in S_n σ ∈ S n i i i n n n σ ∘ t i , n − 1 \sigma\circ t_{i,n}^{-1} σ ∘ t i , n − 1 n n n n n n τ ^ \hat{\tau} τ ^ τ ∈ S n − 1 \tau\in S_{n-1} τ ∈ S n − 1
∑ σ ∈ S n σ ( i ) = n ( − 1 ) σ ∏ c = ( i 1 , i 2 , … , i k ) is a cycle of σ f ( a i 1 a i 2 ⋯ a i k ) = ∑ τ ∈ S n − 1 ( − 1 ) τ ^ ∘ t i , n ∏ c = ( i 1 , i 2 , … , i k ) is a cycle of τ ^ ∘ t i , n f ( a i 1 a i 2 ⋯ a i k ) = − ∑ τ ∈ S n − 1 ( − 1 ) τ ∏ c = ( i 1 , i 2 , … , i k ) is a cycle of τ f ( a i 1 ′ a i 2 ′ ⋯ a i k ′ ) = − f n − 1 ( a 1 ′ , a 2 ′ , … , a n − 1 ′ ) = − f n − 1 ( a 1 , a 2 , … , a i − 1 , a i a n , a i + 1 , a i + 2 , … , a n − 1 ) (12) \begin{aligned}
\sum_{\substack{\sigma\in S_n\\ \sigma(i)=n}}(-1)^\sigma
\prod_{\substack{c=(i_1,i_2,\ldots,i_k)\\ \text{is a cycle of }\sigma}}
f(a_{i_1}a_{i_2}\cdots a_{i_k})
&=
\sum_{\tau\in S_{n-1}}(-1)^{\hat{\tau}\circ t_{i,n}}
\prod_{\substack{c=(i_1,i_2,\ldots,i_k)\\ \text{is a cycle of }\hat{\tau}\circ t_{i,n}}}
f(a_{i_1}a_{i_2}\cdots a_{i_k})\\
&=
-\sum_{\tau\in S_{n-1}}(-1)^\tau
\prod_{\substack{c=(i_1,i_2,\ldots,i_k)\\ \text{is a cycle of }\tau}}
f(a'_{i_1}a'_{i_2}\cdots a'_{i_k})\\
&=-f_{n-1}(a'_1,a'_2,\ldots,a'_{n-1})\\
&=-f_{n-1}(a_1,a_2,\ldots,a_{i-1},a_i a_n,a_{i+1},a_{i+2},\ldots,a_{n-1}) \tag*{(12)}
\end{aligned} σ ∈ S n σ ( i ) = n ∑ ( − 1 ) σ c = ( i 1 , i 2 , … , i k ) is a cycle of σ ∏ f ( a i 1 a i 2 ⋯ a i k ) = τ ∈ S n − 1 ∑ ( − 1 ) τ ^ ∘ t i , n c = ( i 1 , i 2 , … , i k ) is a cycle of τ ^ ∘ t i , n ∏ f ( a i 1 a i 2 ⋯ a i k ) = − τ ∈ S n − 1 ∑ ( − 1 ) τ c = ( i 1 , i 2 , … , i k ) is a cycle of τ ∏ f ( a i 1 ′ a i 2 ′ ⋯ a i k ′ ) = − f n − 1 ( a 1 ′ , a 2 ′ , … , a n − 1 ′ ) = − f n − 1 ( a 1 , a 2 , … , a i − 1 , a i a n , a i + 1 , a i + 2 , … , a n − 1 ) (12) (by (5)).
Forget that we fixed i i i i ∈ { 1 , 2 , … , n − 1 } i \in\{1,2,\ldots,n-1\} i ∈ { 1 , 2 , … , n − 1 } i = n i=n i = n
f n ( a 1 , a 2 , … , a n ) = ∑ σ ∈ S n ; σ ( n ) = n ( − 1 ) σ ∏ c = ( i 1 , i 2 , … , i k ) is a cycle of σ f ( a i 1 a i 2 ⋯ a i k ) ⏟ = f ( a n ) f n − 1 ( a 1 , a 2 , … , a n − 1 ) (by (4)) + ∑ i = 1 n − 1 ∑ σ ∈ S n ; σ ( i ) = n ( − 1 ) σ ∏ c = ( i 1 , i 2 , … , i k ) is a cycle of σ f ( a i 1 a i 2 ⋯ a i k ) ⏟ = − f n − 1 ( a 1 , a 2 , … , a i − 1 , a i a n , a i + 1 , a i + 2 , … , a n − 1 ) (by (12)) = f ( a n ) f n − 1 ( a 1 , a 2 , … , a n − 1 ) − ∑ i = 1 n − 1 f n − 1 ( a 1 , a 2 , … , a i − 1 , a i a n , a i + 1 , a i + 2 , … , a n − 1 ) . \begin{aligned}
f_n(a_1,a_2,\ldots,a_n)
={}&\sum_{\substack{\sigma\in S_n;\\ \sigma(n)=n}}(-1)^\sigma
\underbrace{\prod_{\substack{c=(i_1,i_2,\ldots,i_k)\\ \text{is a cycle of }\sigma}}
f(a_{i_1}a_{i_2}\cdots a_{i_k})}_{=f(a_n)f_{n-1}(a_1,a_2,\ldots,a_{n-1})\ \text{(by (4))}}\\
&+\sum_{i=1}^{n-1}\sum_{\substack{\sigma\in S_n;\\ \sigma(i)=n}}(-1)^\sigma
\underbrace{\prod_{\substack{c=(i_1,i_2,\ldots,i_k)\\ \text{is a cycle of }\sigma}}
f(a_{i_1}a_{i_2}\cdots a_{i_k})}_{=-f_{n-1}(a_1,a_2,\ldots,a_{i-1},a_i a_n,a_{i+1},a_{i+2},\ldots,a_{n-1})\ \text{(by (12))}}\\
={}&f(a_n)f_{n-1}(a_1,a_2,\ldots,a_{n-1})\\
&-\sum_{i=1}^{n-1}f_{n-1}(a_1,a_2,\ldots,a_{i-1},a_i a_n,a_{i+1},a_{i+2},\ldots,a_{n-1}).
\end{aligned} f n ( a 1 , a 2 , … , a n ) = = σ ∈ S n ; σ ( n ) = n ∑ ( − 1 ) σ = f ( a n ) f n − 1 ( a 1 , a 2 , … , a n − 1 ) (by (4)) c = ( i 1 , i 2 , … , i k ) is a cycle of σ ∏ f ( a i 1 a i 2 ⋯ a i k ) + i = 1 ∑ n − 1 σ ∈ S n ; σ ( i ) = n ∑ ( − 1 ) σ = − f n − 1 ( a 1 , a 2 , … , a i − 1 , a i a n , a i + 1 , a i + 2 , … , a n − 1 ) (by (12)) c = ( i 1 , i 2 , … , i k ) is a cycle of σ ∏ f ( a i 1 a i 2 ⋯ a i k ) f ( a n ) f n − 1 ( a 1 , a 2 , … , a n − 1 ) − i = 1 ∑ n − 1 f n − 1 ( a 1 , a 2 , … , a i − 1 , a i a n , a i + 1 , a i + 2 , … , a n − 1 ) . This proves (2). Thus, Proposition 0.6 is proved.
Symmetry of n n n
Next, we note something simple:
Proposition 0.7. Let A A A B B B f : A → B f:A\to B f : A → B Z \mathbb{Z} Z n ∈ N n\in\mathbb{N} n ∈ N f n : A n → B f_n:A^n\to B f n : A n → B n n n τ ∈ S n \tau\in S_n τ ∈ S n a 1 , a 2 , … , a n ∈ A a_1,a_2,\ldots,a_n\in A a 1 , a 2 , … , a n ∈ A
f n ( a τ ( 1 ) , a τ ( 2 ) , … , a τ ( n ) ) = f n ( a 1 , a 2 , … , a n ) . f_n\left(a_{\tau(1)},a_{\tau(2)},\ldots,a_{\tau(n)}\right)=f_n(a_1,a_2,\ldots,a_n). f n ( a τ ( 1 ) , a τ ( 2 ) , … , a τ ( n ) ) = f n ( a 1 , a 2 , … , a n ) . Proof. Let τ ∈ S n \tau\in S_n τ ∈ S n a 1 , a 2 , … , a n ∈ A a_1,a_2,\ldots,a_n\in A a 1 , a 2 , … , a n ∈ A
f n ( a 1 , a 2 , … , a n ) = ∑ σ ∈ S n ( − 1 ) σ ∏ c = ( i 1 , i 2 , … , i k ) is a cycle of σ f ( a i 1 a i 2 ⋯ a i k ) = ∑ σ ∈ S n ( − 1 ) σ ∏ c = ( j 1 , j 2 , … , j k ) is a cycle of σ f ( a j 1 a j 2 ⋯ a j k ) . (13) \begin{aligned}
f_n(a_1,a_2,\ldots,a_n)
&=\sum_{\sigma\in S_n}(-1)^\sigma
\prod_{\substack{c=(i_1,i_2,\ldots,i_k)\\ \text{is a cycle of }\sigma}}
f(a_{i_1}a_{i_2}\cdots a_{i_k})\\
&=\sum_{\sigma\in S_n}(-1)^\sigma
\prod_{\substack{c=(j_1,j_2,\ldots,j_k)\\ \text{is a cycle of }\sigma}}
f(a_{j_1}a_{j_2}\cdots a_{j_k}). \tag*{(13)}
\end{aligned} f n ( a 1 , a 2 , … , a n ) = σ ∈ S n ∑ ( − 1 ) σ c = ( i 1 , i 2 , … , i k ) is a cycle of σ ∏ f ( a i 1 a i 2 ⋯ a i k ) = σ ∈ S n ∑ ( − 1 ) σ c = ( j 1 , j 2 , … , j k ) is a cycle of σ ∏ f ( a j 1 a j 2 ⋯ a j k ) . (13) and
f n ( a τ ( 1 ) , a τ ( 2 ) , … , a τ ( n ) ) = ∑ σ ∈ S n ( − 1 ) σ ∏ c = ( i 1 , i 2 , … , i k ) is a cycle of σ f ( a τ ( i 1 ) a τ ( i 2 ) ⋯ a τ ( i k ) ) . (14) f_n\left(a_{\tau(1)},a_{\tau(2)},\ldots,a_{\tau(n)}\right)
=\sum_{\sigma\in S_n}(-1)^\sigma
\prod_{\substack{c=(i_1,i_2,\ldots,i_k)\\ \text{is a cycle of }\sigma}}
f\left(a_{\tau(i_1)}a_{\tau(i_2)}\cdots a_{\tau(i_k)}\right). \tag*{(14)} f n ( a τ ( 1 ) , a τ ( 2 ) , … , a τ ( n ) ) = σ ∈ S n ∑ ( − 1 ) σ c = ( i 1 , i 2 , … , i k ) is a cycle of σ ∏ f ( a τ ( i 1 ) a τ ( i 2 ) ⋯ a τ ( i k ) ) . (14) However, recall that conjugate permutations have the same cycle type. More concretely: If σ ∈ S n \sigma\in S_n σ ∈ S n τ ∘ σ ∘ τ − 1 \tau\circ\sigma\circ\tau^{-1} τ ∘ σ ∘ τ − 1 σ \sigma σ ( i 1 , i 2 , … , i k ) (i_1,i_2,\ldots,i_k) ( i 1 , i 2 , … , i k ) σ \sigma σ ( τ ( i 1 ) , τ ( i 2 ) , … , τ ( i k ) ) (\tau(i_1),\tau(i_2),\ldots,\tau(i_k)) ( τ ( i 1 ) , τ ( i 2 ) , … , τ ( i k )) τ ∘ σ ∘ τ − 1 \tau\circ\sigma\circ\tau^{-1} τ ∘ σ ∘ τ − 1 σ \sigma σ τ ∘ σ ∘ τ − 1 \tau\circ\sigma\circ\tau^{-1} τ ∘ σ ∘ τ − 1 σ ∈ S n \sigma\in S_n σ ∈ S n
∏ c = ( i 1 , i 2 , … , i k ) is a cycle of σ f ( a τ ( i 1 ) a τ ( i 2 ) ⋯ a τ ( i k ) ) = ∏ c = ( j 1 , j 2 , … , j k ) is a cycle of τ ∘ σ ∘ τ − 1 f ( a j 1 a j 2 ⋯ a j k ) . \prod_{\substack{c=(i_1,i_2,\ldots,i_k)\\\text{is a cycle of }\sigma}} f\left(a_{\tau(i_1)}a_{\tau(i_2)}\cdots a_{\tau(i_k)}\right)
=
\prod_{\substack{c=(j_1,j_2,\ldots,j_k)\\\text{is a cycle of }\tau\circ\sigma\circ\tau^{-1}}} f\left(a_{j_1}a_{j_2}\cdots a_{j_k}\right). c = ( i 1 , i 2 , … , i k ) is a cycle of σ ∏ f ( a τ ( i 1 ) a τ ( i 2 ) ⋯ a τ ( i k ) ) = c = ( j 1 , j 2 , … , j k ) is a cycle of τ ∘ σ ∘ τ − 1 ∏ f ( a j 1 a j 2 ⋯ a j k ) . Substituting this into (14) , we obtain
f n ( a τ ( 1 ) , a τ ( 2 ) , … , a τ ( n ) ) = ∑ σ ∈ S n ( − 1 ) σ ∏ c = ( j 1 , j 2 , … , j k ) is a cycle of τ ∘ σ ∘ τ − 1 f ( a j 1 a j 2 ⋯ a j k ) = ∑ σ ∈ S n ( − 1 ) τ ∘ σ ∘ τ − 1 ∏ c = ( j 1 , j 2 , … , j k ) is a cycle of τ ∘ σ ∘ τ − 1 f ( a j 1 a j 2 ⋯ a j k ) = ∑ σ ∈ S n ( − 1 ) σ ∏ c = ( j 1 , j 2 , … , j k ) is a cycle of σ f ( a j 1 a j 2 ⋯ a j k ) . \begin{aligned}
f_n\left(a_{\tau(1)},a_{\tau(2)},\ldots,a_{\tau(n)}\right)
&=\sum_{\sigma\in S_n}(-1)^\sigma
\prod_{\substack{c=(j_1,j_2,\ldots,j_k)\\\text{is a cycle of }\tau\circ\sigma\circ\tau^{-1}}}f\left(a_{j_1}a_{j_2}\cdots a_{j_k}\right)\\
&=\sum_{\sigma\in S_n}(-1)^{\tau\circ\sigma\circ\tau^{-1}}
\prod_{\substack{c=(j_1,j_2,\ldots,j_k)\\\text{is a cycle of }\tau\circ\sigma\circ\tau^{-1}}}f\left(a_{j_1}a_{j_2}\cdots a_{j_k}\right)\\
&=\sum_{\sigma\in S_n}(-1)^\sigma
\prod_{\substack{c=(j_1,j_2,\ldots,j_k)\\\text{is a cycle of }\sigma}}f\left(a_{j_1}a_{j_2}\cdots a_{j_k}\right).
\end{aligned} f n ( a τ ( 1 ) , a τ ( 2 ) , … , a τ ( n ) ) = σ ∈ S n ∑ ( − 1 ) σ c = ( j 1 , j 2 , … , j k ) is a cycle of τ ∘ σ ∘ τ − 1 ∏ f ( a j 1 a j 2 ⋯ a j k ) = σ ∈ S n ∑ ( − 1 ) τ ∘ σ ∘ τ − 1 c = ( j 1 , j 2 , … , j k ) is a cycle of τ ∘ σ ∘ τ − 1 ∏ f ( a j 1 a j 2 ⋯ a j k ) = σ ∈ S n ∑ ( − 1 ) σ c = ( j 1 , j 2 , … , j k ) is a cycle of σ ∏ f ( a j 1 a j 2 ⋯ a j k ) . (here, we have substituted σ \sigma σ τ ∘ σ ∘ τ − 1 \tau\circ\sigma\circ\tau^{-1} τ ∘ σ ∘ τ − 1 τ \tau τ S n S_n S n (13) , we obtain f n ( a τ ( 1 ) , a τ ( 2 ) , … , a τ ( n ) ) = f n ( a 1 , a 2 , … , a n ) f_n\left(a_{\tau(1)},a_{\tau(2)},\ldots,a_{\tau(n)}\right)=f_n(a_1,a_2,\ldots,a_n) f n ( a τ ( 1 ) , a τ ( 2 ) , … , a τ ( n ) ) = f n ( a 1 , a 2 , … , a n )
The proof of Proposition 0.7 can be somewhat generalized, essentially replacing the permutation τ \tau τ
Proposition 0.8. Let A A A B B B f : A → B f:A\to B f : A → B Z \mathbb{Z} Z
Let U = { u 1 , u 2 , … , u n } U=\{u_1,u_2,\ldots,u_n\} U = { u 1 , u 2 , … , u n } u 1 , u 2 , … , u n u_1,u_2,\ldots,u_n u 1 , u 2 , … , u n S U S_U S U U U U a u a_u a u A A A u ∈ U u\in U u ∈ U
f n ( a u 1 , a u 2 , … , a u n ) = ∑ α ∈ S U ( − 1 ) α ∏ c = ( i 1 , i 2 , … , i k ) is a cycle of α f ( a i 1 a i 2 ⋯ a i k ) . f_n(a_{u_1},a_{u_2},\ldots,a_{u_n})
=
\sum_{\alpha\in S_U}(-1)^\alpha
\prod_{\substack{c=(i_1,i_2,\ldots,i_k)\\\text{is a cycle of }\alpha}}
f(a_{i_1}a_{i_2}\cdots a_{i_k}). f n ( a u 1 , a u 2 , … , a u n ) = α ∈ S U ∑ ( − 1 ) α c = ( i 1 , i 2 , … , i k ) is a cycle of α ∏ f ( a i 1 a i 2 ⋯ a i k ) . Proof. Let τ : [ n ] → U \tau: [n] \to U τ : [ n ] → U i ∈ [ n ] i \in[n] i ∈ [ n ] u i u_i u i τ \tau τ U = { u 1 , u 2 , … , u n } U = \{u_1, u_2, \ldots, u_n\} U = { u 1 , u 2 , … , u n } u 1 , u 2 , … , u n u_1, u_2, \ldots, u_n u 1 , u 2 , … , u n σ ∈ S n \sigma\in S_n σ ∈ S n τ ∘ σ ∘ τ − 1 \tau\circ\sigma\circ\tau^{-1} τ ∘ σ ∘ τ − 1 U U U
S n ⟶ S U , σ ⟼ τ ∘ σ ∘ τ − 1 , (15) \begin{aligned}
S_n &\longrightarrow S_U,\\
\sigma&\longmapsto\tau\circ\sigma\circ\tau^{-1}, \tag*{(15)}
\end{aligned} S n σ ⟶ S U , ⟼ τ ∘ σ ∘ τ − 1 , (15) which is easily seen to be a group isomorphism. Intuitively speaking, τ ∘ σ ∘ τ − 1 \tau\circ\sigma\circ\tau^{-1} τ ∘ σ ∘ τ − 1 σ \sigma σ [ n ] [n] [ n ] i ∈ [ n ] i \in[n] i ∈ [ n ] σ \sigma σ σ \sigma σ τ ( i ) \tau(i) τ ( i ) τ ∘ σ ∘ τ − 1 \tau\circ\sigma\circ\tau^{-1} τ ∘ σ ∘ τ − 1 σ ∈ S n \sigma\in S_n σ ∈ S n σ \sigma σ ( i 1 , i 2 , … , i k ) (i_1,i_2,\ldots,i_k) ( i 1 , i 2 , … , i k ) σ \sigma σ ( τ ( i 1 ) , τ ( i 2 ) , … , τ ( i k ) ) (\tau(i_1),\tau(i_2),\ldots,\tau(i_k)) ( τ ( i 1 ) , τ ( i 2 ) , … , τ ( i k )) τ ∘ σ ∘ τ − 1 \tau\circ\sigma\circ\tau^{-1} τ ∘ σ ∘ τ − 1 σ \sigma σ τ ∘ σ ∘ τ − 1 \tau\circ\sigma\circ\tau^{-1} τ ∘ σ ∘ τ − 1 σ ∈ S n \sigma\in S_n σ ∈ S n
∏ c = ( i 1 , i 2 , … , i k ) is a cycle of σ f ( a τ ( i 1 ) a τ ( i 2 ) ⋯ a τ ( i k ) ) = ∏ c = ( j 1 , j 2 , … , j k ) is a cycle of τ ∘ σ ∘ τ − 1 f ( a j 1 a j 2 ⋯ a j k ) . (16) \prod_{\substack{c=(i_1,i_2,\ldots,i_k)\\\text{is a cycle of }\sigma}} f\left(a_{\tau(i_1)}a_{\tau(i_2)}\cdots a_{\tau(i_k)}\right)
=
\prod_{\substack{c=(j_1,j_2,\ldots,j_k)\\\text{is a cycle of }\tau\circ\sigma\circ\tau^{-1}}} f\left(a_{j_1}a_{j_2}\cdots a_{j_k}\right). \tag*{(16)} c = ( i 1 , i 2 , … , i k ) is a cycle of σ ∏ f ( a τ ( i 1 ) a τ ( i 2 ) ⋯ a τ ( i k ) ) = c = ( j 1 , j 2 , … , j k ) is a cycle of τ ∘ σ ∘ τ − 1 ∏ f ( a j 1 a j 2 ⋯ a j k ) . (16) Moreover, if σ ∈ S n \sigma\in S_n σ ∈ S n
( − 1 ) σ = ( − 1 ) τ ∘ σ ∘ τ − 1 . (17) (-1)^\sigma= (-1)^{\tau\circ\sigma\circ\tau^{-1}}. \tag*{(17)} ( − 1 ) σ = ( − 1 ) τ ∘ σ ∘ τ − 1 . (17) (This is easiest to see by factoring σ \sigma σ [7 Exercise 5.12] .)
But each i ∈ [ n ] i \in[n] i ∈ [ n ] a u i = a τ ( i ) a_{u_i}=a_{\tau(i)} a u i = a τ ( i ) τ \tau τ τ ( i ) = u i \tau(i)=u_i τ ( i ) = u i a τ ( i ) = a u i a_{\tau(i)}=a_{u_i} a τ ( i ) = a u i
f n ( a u 1 , a u 2 , … , a u n ) = f n ( a τ ( 1 ) , a τ ( 2 ) , … , a τ ( n ) ) = ∑ σ ∈ S n ( − 1 ) σ ∏ c = ( i 1 , i 2 , … , i k ) is a cycle of σ f ( a τ ( i 1 ) a τ ( i 2 ) ⋯ a τ ( i k ) ) = ∑ σ ∈ S n ( − 1 ) τ ∘ σ ∘ τ − 1 ∏ c = ( j 1 , j 2 , … , j k ) is a cycle of τ ∘ σ ∘ τ − 1 f ( a j 1 a j 2 ⋯ a j k ) \begin{aligned}
f_n(a_{u_1},a_{u_2},\ldots,a_{u_n})
&=f_n\left(a_{\tau(1)},a_{\tau(2)},\ldots,a_{\tau(n)}\right)\\
&=\sum_{\sigma\in S_n}(-1)^{\sigma}\prod_{\substack{c=(i_1,i_2,\ldots,i_k)\\\text{is a cycle of }\sigma}}f\left(a_{\tau(i_1)}a_{\tau(i_2)}\cdots a_{\tau(i_k)}\right)\\
&=\sum_{\sigma\in S_n}(-1)^{\tau\circ\sigma\circ\tau^{-1}}\prod_{\substack{c=(j_1,j_2,\ldots,j_k)\\\text{is a cycle of }\tau\circ\sigma\circ\tau^{-1}}}f(a_{j_1}a_{j_2}\cdots a_{j_k})
\end{aligned} f n ( a u 1 , a u 2 , … , a u n ) = f n ( a τ ( 1 ) , a τ ( 2 ) , … , a τ ( n ) ) = σ ∈ S n ∑ ( − 1 ) σ c = ( i 1 , i 2 , … , i k ) is a cycle of σ ∏ f ( a τ ( i 1 ) a τ ( i 2 ) ⋯ a τ ( i k ) ) = σ ∈ S n ∑ ( − 1 ) τ ∘ σ ∘ τ − 1 c = ( j 1 , j 2 , … , j k ) is a cycle of τ ∘ σ ∘ τ − 1 ∏ f ( a j 1 a j 2 ⋯ a j k ) (by (1), applied to a τ ( i ) a_{\tau(i)} a τ ( i ) a i a_i a i
∑ σ ∈ S n ( − 1 ) τ ∘ σ ∘ τ − 1 ∏ c = ( j 1 , j 2 , … , j k ) is a cycle of τ ∘ σ ∘ τ − 1 f ( a j 1 a j 2 ⋯ a j k ) = ∑ α ∈ S U ( − 1 ) α ∏ c = ( j 1 , j 2 , … , j k ) is a cycle of α f ( a j 1 a j 2 ⋯ a j k ) \sum_{\sigma\in S_n}(-1)^{\tau\circ\sigma\circ\tau^{-1}}\prod_{\substack{c=(j_1,j_2,\ldots,j_k)\\\text{is a cycle of }\tau\circ\sigma\circ\tau^{-1}}}f(a_{j_1}a_{j_2}\cdots a_{j_k})
=\sum_{\alpha\in S_U}(-1)^\alpha\prod_{\substack{c=(j_1,j_2,\ldots,j_k)\\\text{is a cycle of }\alpha}}f(a_{j_1}a_{j_2}\cdots a_{j_k}) σ ∈ S n ∑ ( − 1 ) τ ∘ σ ∘ τ − 1 c = ( j 1 , j 2 , … , j k ) is a cycle of τ ∘ σ ∘ τ − 1 ∏ f ( a j 1 a j 2 ⋯ a j k ) = α ∈ S U ∑ ( − 1 ) α c = ( j 1 , j 2 , … , j k ) is a cycle of α ∏ f ( a j 1 a j 2 ⋯ a j k ) (here, we have substituted α \alpha α τ ∘ σ ∘ τ − 1 \tau\circ\sigma\circ\tau^{-1} τ ∘ σ ∘ τ − 1 ( j 1 , j 2 , … , j k ) (j_1,j_2,\ldots,j_k) ( j 1 , j 2 , … , j k ) ( i 1 , i 2 , … , i k ) (i_1,i_2,\ldots,i_k) ( i 1 , i 2 , … , i k )
f n ( a u 1 , a u 2 , … , a u n ) = ∑ α ∈ S U ( − 1 ) α ∏ c = ( i 1 , i 2 , … , i k ) is a cycle of α f ( a i 1 a i 2 ⋯ a i k ) . f_n(a_{u_1},a_{u_2},\ldots,a_{u_n})=\sum_{\alpha\in S_U}(-1)^\alpha\prod_{\substack{c=(i_1,i_2,\ldots,i_k)\\\text{is a cycle of }\alpha}}f(a_{i_1}a_{i_2}\cdots a_{i_k}). f n ( a u 1 , a u 2 , … , a u n ) = α ∈ S U ∑ ( − 1 ) α c = ( i 1 , i 2 , … , i k ) is a cycle of α ∏ f ( a i 1 a i 2 ⋯ a i k ) . Thus, Proposition 0.8 is proved.
The sum of two n n n
The proof of Theorem 0.3 will require two lemmas:
Lemma 0.9. Let A A A B B B f : A → B f:A\to B f : A → B Z \mathbb{Z} Z m ∈ N m\in\mathbb{N} m ∈ N f m = 0 f_m=0 f m = 0 f n = 0 f_n=0 f n = 0 n ≥ m n\ge m n ≥ m
Proof sketch. If some positive integer n n n f n − 1 = 0 f_{n-1}=0 f n − 1 = 0 f n = 0 f_n=0 f n = 0 n n n
Lemma 0.10. Let A A A B B B B B B f : A → B f:A\to B f : A → B g : A → B g:A\to B g : A → B Z \mathbb{Z} Z a 1 , a 2 , … , a p ∈ A a_1,a_2,\ldots,a_p\in A a 1 , a 2 , … , a p ∈ A
For any subset I = { i 1 , i 2 , … , i k } I=\{i_1,i_2,\ldots,i_k\} I = { i 1 , i 2 , … , i k } [ p ] [p] [ p ] i 1 , i 2 , … , i k i_1,i_2,\ldots,i_k i 1 , i 2 , … , i k h : A → B h:A\to B h : A → B
h I ( a ) : = h k ( a i 1 , a i 2 , … , a i k ) ∈ B . h_I(a):=h_k(a_{i_1},a_{i_2},\ldots,a_{i_k})\in B. h I ( a ) := h k ( a i 1 , a i 2 , … , a i k ) ∈ B . (This is well-defined, i.e., does not depend on the order in which we label the elements of I I I i 1 , i 2 , … , i k i_1,i_2,\ldots,i_k i 1 , i 2 , … , i k Proposition 0.7 shows that the map h k h_k h k
(f+g)_p(a_1,a_2,\ldots,a_p)=\sum_{U\mathbin{\mathaccent\cdot\cup}V=[p]}f_U(a)\cdot g_V(a).
Here, the notation “U\mathbin{\mathaccent\cdot\cup}V=[p] ” means that U U U V V V [ p ] [p] [ p ] U U U [ p ] [p] [ p ] V V V [ p ] [p] [ p ]
Proof of Lemma 0.10 (sketched). From (1) (applied to f + g f+g f + g p p p f f f n n n
( f + g ) p ( a 1 , a 2 , … , a p ) = ∑ σ ∈ S p ( − 1 ) σ ∏ c = ( i 1 , i 2 , … , i k ) is a cycle of σ ( f + g ) ( a i 1 a i 2 ⋯ a i k ) = ∑ σ ∈ S p ( − 1 ) σ ∏ c = ( i 1 , i 2 , … , i k ) is a cycle of σ ( f ( a i 1 a i 2 ⋯ a i k ) + g ( a i 1 a i 2 ⋯ a i k ) ) . (18) \begin{aligned}
(f+g)_p(a_1,a_2,\ldots,a_p)
&=\sum_{\sigma\in S_p}(-1)^\sigma\prod_{\substack{c=(i_1,i_2,\ldots,i_k)\\\text{is a cycle of }\sigma}}(f+g)(a_{i_1}a_{i_2}\cdots a_{i_k})\\
&=\sum_{\sigma\in S_p}(-1)^\sigma\prod_{\substack{c=(i_1,i_2,\ldots,i_k)\\\text{is a cycle of }\sigma}}\left(f(a_{i_1}a_{i_2}\cdots a_{i_k})+g(a_{i_1}a_{i_2}\cdots a_{i_k})\right). \tag*{(18)}
\end{aligned} ( f + g ) p ( a 1 , a 2 , … , a p ) = σ ∈ S p ∑ ( − 1 ) σ c = ( i 1 , i 2 , … , i k ) is a cycle of σ ∏ ( f + g ) ( a i 1 a i 2 ⋯ a i k ) = σ ∈ S p ∑ ( − 1 ) σ c = ( i 1 , i 2 , … , i k ) is a cycle of σ ∏ ( f ( a i 1 a i 2 ⋯ a i k ) + g ( a i 1 a i 2 ⋯ a i k ) ) . (18) Now, fix a permutation σ ∈ S p \sigma\in S_p σ ∈ S p
∏ c = ( i 1 , i 2 , … , i k ) is a cycle of σ ( f ( a i 1 a i 2 ⋯ a i k ) + g ( a i 1 a i 2 ⋯ a i k ) ) , (19) \prod_{\substack{c=(i_1,i_2,\ldots,i_k)\\\text{is a cycle of }\sigma}}\left(f(a_{i_1}a_{i_2}\cdots a_{i_k})+g(a_{i_1}a_{i_2}\cdots a_{i_k})\right), \tag*{(19)} c = ( i 1 , i 2 , … , i k ) is a cycle of σ ∏ ( f ( a i 1 a i 2 ⋯ a i k ) + g ( a i 1 a i 2 ⋯ a i k ) ) , (19) then we obtain a sum over all ways to choose, for each cycle c = ( i 1 , i 2 , … , i k ) c=(i_1,i_2,\ldots,i_k) c = ( i 1 , i 2 , … , i k ) σ \sigma σ f ( a i 1 a i 2 ⋯ a i k ) + g ( a i 1 a i 2 ⋯ a i k ) f(a_{i_1}a_{i_2}\cdots a_{i_k})+g(a_{i_1}a_{i_2}\cdots a_{i_k}) f ( a i 1 a i 2 ⋯ a i k ) + g ( a i 1 a i 2 ⋯ a i k ) σ \sigma σ f ( a i 1 a i 2 ⋯ a i k ) f(a_{i_1}a_{i_2}\cdots a_{i_k}) f ( a i 1 a i 2 ⋯ a i k ) g ( a i 1 a i 2 ⋯ a i k ) g(a_{i_1}a_{i_2}\cdots a_{i_k}) g ( a i 1 a i 2 ⋯ a i k )
∏ c = ( i 1 , i 2 , … , i k ) is a cycle of σ ( f ( a i 1 a i 2 ⋯ a i k ) + g ( a i 1 a i 2 ⋯ a i k ) ) = ∑ coloring of all cycles of σ in red and blue ∏ c = ( i 1 , i 2 , … , i k ) is a cycle of σ { f ( a i 1 a i 2 ⋯ a i k ) , if c is red ; g ( a i 1 a i 2 ⋯ a i k ) , if c is blue . \prod_{\substack{c=(i_1,i_2,\ldots,i_k)\\\text{is a cycle of }\sigma}}\left(f(a_{i_1}a_{i_2}\cdots a_{i_k})+g(a_{i_1}a_{i_2}\cdots a_{i_k})\right)
=
\sum_{\substack{\text{coloring of all cycles of }\sigma\\\text{in red and blue}}}
\prod_{\substack{c=(i_1,i_2,\ldots,i_k)\\\text{is a cycle of }\sigma}}
\begin{cases}
f(a_{i_1}a_{i_2}\cdots a_{i_k}), & \text{if }c\text{ is red};\\
g(a_{i_1}a_{i_2}\cdots a_{i_k}), & \text{if }c\text{ is blue}.
\end{cases} c = ( i 1 , i 2 , … , i k ) is a cycle of σ ∏ ( f ( a i 1 a i 2 ⋯ a i k ) + g ( a i 1 a i 2 ⋯ a i k ) ) = coloring of all cycles of σ in red and blue ∑ c = ( i 1 , i 2 , … , i k ) is a cycle of σ ∏ { f ( a i 1 a i 2 ⋯ a i k ) , g ( a i 1 a i 2 ⋯ a i k ) , if c is red ; if c is blue . Equivalently, instead of coloring cycles, we can just as well color the elements of these cycles red and blue (viz., all elements of all red cycles are colored red, while all elements of all blue cycles are colored blue). These colorings are not arbitrary, but must have the property that each cycle is either completely red (i.e., all its elements are red) or completely blue (i.e., all its elements are blue); in other words, they must have the property that σ \sigma σ (19) can be rewritten as follows:
∏ c = ( i 1 , i 2 , … , i k ) is a cycle of σ ( f ( a i 1 a i 2 ⋯ a i k ) + g ( a i 1 a i 2 ⋯ a i k ) ) = ∑ coloring of all elements of [ p ] in red and blue; σ sends red elements to red elements and blue elements to blue elements ∏ c = ( i 1 , i 2 , … , i k ) is a cycle of σ { f ( a i 1 a i 2 ⋯ a i k ) , if c is red ; g ( a i 1 a i 2 ⋯ a i k ) , if c is blue \begin{aligned}
\prod_{\substack{c=(i_1,i_2,\ldots,i_k)\\\text{is a cycle of }\sigma}} \left(f\left(a_{i_1}a_{i_2}\cdots a_{i_k}\right)+g\left(a_{i_1}a_{i_2}\cdots a_{i_k}\right)\right)
&=\sum_{\substack{\text{coloring of all elements of }[p]\text{ in red and blue;}\\\sigma\text{ sends red elements to red elements}\\\text{and blue elements to blue elements}}}
\prod_{\substack{c=(i_1,i_2,\ldots,i_k)\\\text{is a cycle of }\sigma}}
\begin{cases}
f\left(a_{i_1}a_{i_2}\cdots a_{i_k}\right), & \text{if }c\text{ is red};\\
g\left(a_{i_1}a_{i_2}\cdots a_{i_k}\right), & \text{if }c\text{ is blue}
\end{cases}
\end{aligned} c = ( i 1 , i 2 , … , i k ) is a cycle of σ ∏ ( f ( a i 1 a i 2 ⋯ a i k ) + g ( a i 1 a i 2 ⋯ a i k ) ) = coloring of all elements of [ p ] in red and blue; σ sends red elements to red elements and blue elements to blue elements ∑ c = ( i 1 , i 2 , … , i k ) is a cycle of σ ∏ { f ( a i 1 a i 2 ⋯ a i k ) , g ( a i 1 a i 2 ⋯ a i k ) , if c is red ; if c is blue (where “c c c c c c
Of course, a coloring of all elements of [ p ] [p] [ p ] [ p ] [p] [ p ] U U U V V V U U U V V V U U U V V V U ⊔ V = [ p ] U\sqcup V=[p] U ⊔ V = [ p ] σ \sigma σ σ ( U ) ⊆ U \sigma(U)\subseteq U σ ( U ) ⊆ U σ \sigma σ σ ( V ) ⊆ V \sigma(V)\subseteq V σ ( V ) ⊆ V (19) can be rewritten as follows:
∏ c = ( i 1 , i 2 , … , i k ) is a cycle of σ ( f ( a i 1 a i 2 ⋯ a i k ) + g ( a i 1 a i 2 ⋯ a i k ) ) = ∑ U ⊔ V = [ p ] ; σ ( U ) ⊆ U ; σ ( V ) ⊆ V ∏ c = ( i 1 , i 2 , … , i k ) is a cycle of σ { f ( a i 1 a i 2 ⋯ a i k ) , if c ⊆ U ; g ( a i 1 a i 2 ⋯ a i k ) , if c ⊆ V (20) \begin{aligned}
\prod_{\substack{c=(i_1,i_2,\ldots,i_k)\\\text{is a cycle of }\sigma}} \left(f\left(a_{i_1}a_{i_2}\cdots a_{i_k}\right)+g\left(a_{i_1}a_{i_2}\cdots a_{i_k}\right)\right)
&=\sum_{\substack{U\sqcup V=[p];\\\sigma(U)\subseteq U;\\\sigma(V)\subseteq V}}
\prod_{\substack{c=(i_1,i_2,\ldots,i_k)\\\text{is a cycle of }\sigma}}
\begin{cases}
f\left(a_{i_1}a_{i_2}\cdots a_{i_k}\right), & \text{if }c\subseteq U;\\
g\left(a_{i_1}a_{i_2}\cdots a_{i_k}\right), & \text{if }c\subseteq V
\end{cases} \tag*{(20)}
\end{aligned} c = ( i 1 , i 2 , … , i k ) is a cycle of σ ∏ ( f ( a i 1 a i 2 ⋯ a i k ) + g ( a i 1 a i 2 ⋯ a i k ) ) = U ⊔ V = [ p ] ; σ ( U ) ⊆ U ; σ ( V ) ⊆ V ∑ c = ( i 1 , i 2 , … , i k ) is a cycle of σ ∏ { f ( a i 1 a i 2 ⋯ a i k ) , g ( a i 1 a i 2 ⋯ a i k ) , if c ⊆ U ; if c ⊆ V (20) (where “c ⊆ U c\subseteq U c ⊆ U c c c U U U c ⊆ V c\subseteq V c ⊆ V
Forget that we fixed σ \sigma σ (20) for each σ ∈ S p \sigma\in S_p σ ∈ S p (18) becomes
\begin{aligned}
(f+g)_p(a_1,a_2,\ldots,a_p)
&=\sum_{\sigma\in S_p}(-1)^\sigma
\prod_{\substack{c=(i_1,i_2,\ldots,i_k)\\\text{is a cycle of }\sigma}}
\left(f(a_{i_1}a_{i_2}\cdots a_{i_k})+g(a_{i_1}a_{i_2}\cdots a_{i_k})\right)\\
&=\sum_{\sigma\in S_p}(-1)^\sigma
\sum_{\substack{U\mathbin{\mathaccent\cdot\cup}V=[p];\\\sigma(U)\subseteq U;\\\sigma(V)\subseteq V}}
\prod_{\substack{c=(i_1,i_2,\ldots,i_k)\\\text{is a cycle of }\sigma}}
\begin{cases}
f(a_{i_1}a_{i_2}\cdots a_{i_k}),&\text{if }c\subseteq U;\\
g(a_{i_1}a_{i_2}\cdots a_{i_k}),&\text{if }c\subseteq V
\end{cases}
\end{aligned}
(by (20))
\sum_{U\mathbin{\mathaccent\cdot\cup}V=[p]}
\sum_{\substack{\sigma\in S_p;\\\sigma(U)\subseteq U;\\\sigma(V)\subseteq V}}
(-1)^\sigma
\prod_{\substack{c=(i_1,i_2,\ldots,i_k)\\\text{is a cycle of }\sigma}}
\begin{cases}
f(a_{i_1}a_{i_2}\cdots a_{i_k}),&\text{if }c\subseteq U;\\
g(a_{i_1}a_{i_2}\cdots a_{i_k}),&\text{if }c\subseteq V
\end{cases} \tag*{(21)}
(here, we have interchanged the two summation signs).
Now, fix a decomposition U\mathbin{\mathaccent\cdot\cup}V=[p] of the set [ p ] [p] [ p ] U U U V V V σ ∈ S p \sigma\in S_p σ ∈ S p σ ( U ) ⊆ U \sigma(U)\subseteq U σ ( U ) ⊆ U σ ( V ) ⊆ V \sigma(V)\subseteq V σ ( V ) ⊆ V ( α , β ) (\alpha,\beta) ( α , β ) α : = σ ∣ U \alpha:=\sigma|_U α := σ ∣ U U U U β : = σ ∣ V \beta:=\sigma|_V β := σ ∣ V V V V
from { permutations σ ∈ S p satisfying σ ( U ) ⊆ U and σ ( V ) ⊆ V } to S U × S V \text{from }\{\text{permutations }\sigma\in S_p\text{ satisfying }\sigma(U)\subseteq U\text{ and }\sigma(V)\subseteq V\}
\text{ to }S_U\times S_V from { permutations σ ∈ S p satisfying σ ( U ) ⊆ U and σ ( V ) ⊆ V } to S U × S V (where S X S_X S X X X X σ \sigma σ ( α , β ) : = ( σ ∣ U , σ ∣ V ) (\alpha,\beta):=(\sigma|_U,\sigma|_V) ( α , β ) := ( σ ∣ U , σ ∣ V ) σ \sigma σ α \alpha α β \beta β σ \sigma σ
( − 1 ) σ = ( − 1 ) α ( − 1 ) β (-1)^\sigma=(-1)^\alpha(-1)^\beta ( − 1 ) σ = ( − 1 ) α ( − 1 ) β (this follows, e.g., by writing α \alpha α β \beta β
∑ σ ∈ S p ; σ ( U ) ⊆ U ; σ ( V ) ⊆ V ( − 1 ) σ ∏ c = ( i 1 , i 2 , … , i k ) is a cycle of σ { f ( a i 1 a i 2 ⋯ a i k ) , if c ⊆ U ; g ( a i 1 a i 2 ⋯ a i k ) , if c ⊆ V = ∑ ( α , β ) ∈ S U × S V ( − 1 ) α ( − 1 ) β ∏ c = ( i 1 , i 2 , … , i k ) is a cycle of α or of β { f ( a i 1 a i 2 ⋯ a i k ) , if c ⊆ U ; g ( a i 1 a i 2 ⋯ a i k ) , if c ⊆ V = ∑ ( α , β ) ∈ S U × S V ( − 1 ) α ( − 1 ) β ( ∏ c = ( i 1 , i 2 , … , i k ) is a cycle of α f ( a i 1 a i 2 ⋯ a i k ) ) ( ∏ c = ( i 1 , i 2 , … , i k ) is a cycle of β g ( a i 1 a i 2 ⋯ a i k ) ) = ( ∑ α ∈ S U ( − 1 ) α ∏ c = ( i 1 , i 2 , … , i k ) is a cycle of α f ( a i 1 a i 2 ⋯ a i k ) ) ( ∑ β ∈ S V ( − 1 ) β ∏ c = ( i 1 , i 2 , … , i k ) is a cycle of β g ( a i 1 a i 2 ⋯ a i k ) ) . (22) \begin{aligned}
\sum_{\substack{\sigma\in S_p;\\ \sigma(U)\subseteq U;\\ \sigma(V)\subseteq V}}(-1)^\sigma
\prod_{\substack{c=(i_1,i_2,\ldots,i_k)\\ \text{is a cycle of }\sigma}}
\begin{cases}
f(a_{i_1}a_{i_2}\cdots a_{i_k}), & \text{if }c\subseteq U;\\
g(a_{i_1}a_{i_2}\cdots a_{i_k}), & \text{if }c\subseteq V
\end{cases} \\
&=\sum_{(\alpha,\beta)\in S_U\times S_V}(-1)^\alpha(-1)^\beta
\prod_{\substack{c=(i_1,i_2,\ldots,i_k)\\ \text{is a cycle of }\alpha\text{ or of }\beta}}
\begin{cases}
f(a_{i_1}a_{i_2}\cdots a_{i_k}), & \text{if }c\subseteq U;\\
g(a_{i_1}a_{i_2}\cdots a_{i_k}), & \text{if }c\subseteq V
\end{cases} \\
&=\sum_{(\alpha,\beta)\in S_U\times S_V}(-1)^\alpha(-1)^\beta
\left(
\prod_{\substack{c=(i_1,i_2,\ldots,i_k)\\ \text{is a cycle of }\alpha}}
f(a_{i_1}a_{i_2}\cdots a_{i_k})
\right)
\left(
\prod_{\substack{c=(i_1,i_2,\ldots,i_k)\\ \text{is a cycle of }\beta}}
g(a_{i_1}a_{i_2}\cdots a_{i_k})
\right) \\
&=\left(
\sum_{\alpha\in S_U}(-1)^\alpha
\prod_{\substack{c=(i_1,i_2,\ldots,i_k)\\ \text{is a cycle of }\alpha}}
f(a_{i_1}a_{i_2}\cdots a_{i_k})
\right)
\left(
\sum_{\beta\in S_V}(-1)^\beta
\prod_{\substack{c=(i_1,i_2,\ldots,i_k)\\ \text{is a cycle of }\beta}}
g(a_{i_1}a_{i_2}\cdots a_{i_k})
\right). \tag*{(22)}
\end{aligned} σ ∈ S p ; σ ( U ) ⊆ U ; σ ( V ) ⊆ V ∑ ( − 1 ) σ c = ( i 1 , i 2 , … , i k ) is a cycle of σ ∏ { f ( a i 1 a i 2 ⋯ a i k ) , g ( a i 1 a i 2 ⋯ a i k ) , if c ⊆ U ; if c ⊆ V = ( α , β ) ∈ S U × S V ∑ ( − 1 ) α ( − 1 ) β c = ( i 1 , i 2 , … , i k ) is a cycle of α or of β ∏ { f ( a i 1 a i 2 ⋯ a i k ) , g ( a i 1 a i 2 ⋯ a i k ) , if c ⊆ U ; if c ⊆ V = ( α , β ) ∈ S U × S V ∑ ( − 1 ) α ( − 1 ) β c = ( i 1 , i 2 , … , i k ) is a cycle of α ∏ f ( a i 1 a i 2 ⋯ a i k ) c = ( i 1 , i 2 , … , i k ) is a cycle of β ∏ g ( a i 1 a i 2 ⋯ a i k ) = α ∈ S U ∑ ( − 1 ) α c = ( i 1 , i 2 , … , i k ) is a cycle of α ∏ f ( a i 1 a i 2 ⋯ a i k ) β ∈ S V ∑ ( − 1 ) β c = ( i 1 , i 2 , … , i k ) is a cycle of β ∏ g ( a i 1 a i 2 ⋯ a i k ) . (22) However, if we write the set U U U U = { u 1 , u 2 , … , u r } U=\{u_1,u_2,\ldots,u_r\} U = { u 1 , u 2 , … , u r } u 1 , u 2 , … , u r u_1,u_2,\ldots,u_r u 1 , u 2 , … , u r
f U ( a ) = f r ( a u 1 , a u 2 , … , a u r ) f_U(a)=f_r(a_{u_1},a_{u_2},\ldots,a_{u_r}) f U ( a ) = f r ( a u 1 , a u 2 , … , a u r ) (by the definition of f U f_U f U
= ∑ α ∈ S U ( − 1 ) α ∏ c = ( i 1 , i 2 , … , i k ) is a cycle of α f ( a i 1 a i 2 ⋯ a i k ) . (23) =\sum_{\alpha\in S_U}(-1)^\alpha
\prod_{\substack{c=(i_1,i_2,\ldots,i_k)\\ \text{is a cycle of }\alpha}}
f(a_{i_1}a_{i_2}\cdots a_{i_k}). \tag*{(23)} = α ∈ S U ∑ ( − 1 ) α c = ( i 1 , i 2 , … , i k ) is a cycle of α ∏ f ( a i 1 a i 2 ⋯ a i k ) . (23) (by Proposition 0.8, applied to r r r n n n
∑ α ∈ S U ( − 1 ) α ∏ c = ( i 1 , i 2 , … , i k ) is a cycle of α f ( a i 1 a i 2 ⋯ a i k ) = f U ( a ) . \sum_{\alpha\in S_U}(-1)^\alpha
\prod_{\substack{c=(i_1,i_2,\ldots,i_k)\\ \text{is a cycle of }\alpha}}
f(a_{i_1}a_{i_2}\cdots a_{i_k})=f_U(a). α ∈ S U ∑ ( − 1 ) α c = ( i 1 , i 2 , … , i k ) is a cycle of α ∏ f ( a i 1 a i 2 ⋯ a i k ) = f U ( a ) . Similarly,
∑ β ∈ S V ( − 1 ) β ∏ c = ( i 1 , i 2 , … , i k ) is a cycle of β g ( a i 1 a i 2 ⋯ a i k ) = g V ( a ) . \sum_{\beta\in S_V}(-1)^\beta
\prod_{\substack{c=(i_1,i_2,\ldots,i_k)\\ \text{is a cycle of }\beta}}
g(a_{i_1}a_{i_2}\cdots a_{i_k})=g_V(a). β ∈ S V ∑ ( − 1 ) β c = ( i 1 , i 2 , … , i k ) is a cycle of β ∏ g ( a i 1 a i 2 ⋯ a i k ) = g V ( a ) . Substituting these two equalities into (22), we obtain
∑ σ ∈ S p ; σ ( U ) ⊆ U ; σ ( V ) ⊆ V ( − 1 ) σ ∏ c = ( i 1 , i 2 , … , i k ) is a cycle of σ { f ( a i 1 a i 2 ⋯ a i k ) , if c ⊆ U ; g ( a i 1 a i 2 ⋯ a i k ) , if c ⊆ V = f U ( a ) ⋅ g V ( a ) . (24) \sum_{\substack{\sigma\in S_p;\\ \sigma(U)\subseteq U;\\ \sigma(V)\subseteq V}}(-1)^\sigma\prod_{\substack{c=(i_1,i_2,\ldots,i_k)\\\text{is a cycle of }\sigma}}\begin{cases} f(a_{i_1}a_{i_2}\cdots a_{i_k}), & \text{if }c\subseteq U;\\ g(a_{i_1}a_{i_2}\cdots a_{i_k}), & \text{if }c\subseteq V \end{cases}
= f_U(a)\cdot g_V(a). \tag*{(24)} σ ∈ S p ; σ ( U ) ⊆ U ; σ ( V ) ⊆ V ∑ ( − 1 ) σ c = ( i 1 , i 2 , … , i k ) is a cycle of σ ∏ { f ( a i 1 a i 2 ⋯ a i k ) , g ( a i 1 a i 2 ⋯ a i k ) , if c ⊆ U ; if c ⊆ V = f U ( a ) ⋅ g V ( a ) . (24) Now forget that we fixed the decomposition U ⊔ V = [ p ] U\sqcup V=[p] U ⊔ V = [ p ]
( f + g ) p ( a 1 , a 2 , … , a p ) = ∑ U ⊔ V = [ p ] f U ( a ) ⋅ g V ( a ) . (f+g)_p(a_1,a_2,\ldots,a_p)=\sum_{U\sqcup V=[p]}f_U(a)\cdot g_V(a). ( f + g ) p ( a 1 , a 2 , … , a p ) = U ⊔ V = [ p ] ∑ f U ( a ) ⋅ g V ( a ) . This proves Lemma 0.10.
Proof of Theorem 0.3 (sketched). The map f f f n n n g g g f + g f+g f + g ( f + g ) n + m + 1 = 0 (f+g)_{n+m+1}=0 ( f + g ) n + m + 1 = 0
Let p : = n + m + 1 p:=n+m+1 p := n + m + 1 a 1 , a 2 , … , a p ∈ A a_1,a_2,\ldots,a_p\in A a 1 , a 2 , … , a p ∈ A
( f + g ) p ( a 1 , a 2 , … , a p ) = ∑ U ⊔ V = [ p ] f U ( a ) ⋅ g V ( a ) , (25) (f+g)_p(a_1,a_2,\ldots,a_p)=\sum_{U\sqcup V=[p]}f_U(a)\cdot g_V(a), \tag*{(25)} ( f + g ) p ( a 1 , a 2 , … , a p ) = U ⊔ V = [ p ] ∑ f U ( a ) ⋅ g V ( a ) , (25) where the notations are as defined in Lemma 0.10.
Now, fix any decomposition U ⊔ V = [ p ] U\sqcup V=[p] U ⊔ V = [ p ] [ p ] [p] [ p ] U U U V V V
f U ( a ) ⋅ g V ( a ) = 0. (26) f_U(a)\cdot g_V(a)=0. \tag*{(26)} f U ( a ) ⋅ g V ( a ) = 0. (26) [Proof: From U ⊔ V = [ p ] U\sqcup V=[p] U ⊔ V = [ p ]
∣ U ∣ + ∣ V ∣ = ∣ U ⊔ V ∣ = ∣ [ p ] ∣ = p = n + m + 1 > n + m . |U|+|V|=|U\sqcup V|=|[p]|=p=n+m+1>n+m. ∣ U ∣ + ∣ V ∣ = ∣ U ⊔ V ∣ = ∣ [ p ] ∣ = p = n + m + 1 > n + m . Hence, we must have ∣ U ∣ > n |U|>n ∣ U ∣ > n ∣ V ∣ > m |V|>m ∣ V ∣ > m ∣ U ∣ ≤ n |U|\le n ∣ U ∣ ≤ n ∣ V ∣ ≤ m |V|\le m ∣ V ∣ ≤ m ∣ U ∣ + ∣ V ∣ ≤ n + m |U|+|V|\le n+m ∣ U ∣ + ∣ V ∣ ≤ n + m ∣ U ∣ + ∣ V ∣ > n + m |U|+|V|>n+m ∣ U ∣ + ∣ V ∣ > n + m ∣ U ∣ > n |U|>n ∣ U ∣ > n ∣ V ∣ > m |V|>m ∣ V ∣ > m ∣ U ∣ ≥ n + 1 |U|\ge n+1 ∣ U ∣ ≥ n + 1 f n + 1 = 0 f_{n+1}=0 f n + 1 = 0 f f f n n n ∣ U ∣ |U| ∣ U ∣ n + 1 n+1 n + 1 n n n m m m f ∣ U ∣ = 0 f_{|U|}=0 f ∣ U ∣ = 0 ∣ U ∣ ≥ n + 1 |U|\ge n+1 ∣ U ∣ ≥ n + 1 U U U U = { u 1 , u 2 , … , u r } U=\{u_1,u_2,\ldots,u_r\} U = { u 1 , u 2 , … , u r } u 1 , u 2 , … , u r u_1,u_2,\ldots,u_r u 1 , u 2 , … , u r r = ∣ U ∣ r=|U| r = ∣ U ∣ f r = f ∣ U ∣ = 0 f_r=f_{|U|}=0 f r = f ∣ U ∣ = 0 f U f_U f U
f U ( a ) = f r ⏟ = 0 ( a u 1 , a u 2 , … , a u r ) = 0. f_U(a)=\underbrace{f_r}_{=0}(a_{u_1},a_{u_2},\ldots,a_{u_r})=0. f U ( a ) = = 0 f r ( a u 1 , a u 2 , … , a u r ) = 0. Hence, f U ( a ) ⋅ g V ( a ) = 0 ⋅ g V ( a ) = 0 f_U(a)\cdot g_V(a)=0\cdot g_V(a)=0 f U ( a ) ⋅ g V ( a ) = 0 ⋅ g V ( a ) = 0 (26) .]
Forget that we fixed the decomposition U ⊔ V = [ p ] U\sqcup V=[p] U ⊔ V = [ p ] (26) holds for each such decomposition. In other words, all addends on the right hand side of (25) are 0 0 0 0 0 0 (25) as
( f + g ) p ( a 1 , a 2 , … , a p ) = 0. (f+g)_p(a_1,a_2,\ldots,a_p)=0. ( f + g ) p ( a 1 , a 2 , … , a p ) = 0. Since a 1 , a 2 , … , a p a_1,a_2,\ldots,a_p a 1 , a 2 , … , a p ( f + g ) p = 0 (f+g)_p=0 ( f + g ) p = 0 ( f + g ) n + m + 1 = 0 (f+g)_{n+m+1}=0 ( f + g ) n + m + 1 = 0 p = n + m + 1 p=n+m+1 p = n + m + 1 Theorem 0.3 .
The composition formula
Next, we introduce some notations. A set partition (henceforth just partition ) of a finite set J J J { J 1 , J 2 , … , J k } \{J_1,J_2,\ldots,J_k\} { J 1 , J 2 , … , J k } J J J J 1 ∪ J 2 ∪ ⋯ ∪ J k = J J_1\cup J_2\cup\cdots\cup J_k=J J 1 ∪ J 2 ∪ ⋯ ∪ J k = J J 1 , J 2 , … , J k J_1,J_2,\ldots,J_k J 1 , J 2 , … , J k blocks of the partition. For instance, the five partitions of [ 3 ] [3] [ 3 ] 2
{ { 1 , 2 , 3 } } (with 1 block) \{\{1,2,3\}\}\quad\text{(with 1 block)} {{ 1 , 2 , 3 }} (with 1 block) and
{ { 1 , 2 } , { 3 } } and { { 1 , 3 } , { 2 } } and { { 2 , 3 } , { 1 } } (with 2 blocks each) \{\{1,2\},\{3\}\}\quad\text{and}\quad\{\{1,3\},\{2\}\}\quad\text{and}\quad\{\{2,3\},\{1\}\}
\quad\text{(with 2 blocks each)} {{ 1 , 2 } , { 3 }} and {{ 1 , 3 } , { 2 }} and {{ 2 , 3 } , { 1 }} (with 2 blocks each) and
{ { 1 } , { 2 } , { 3 } } (with 3 blocks) . \{\{1\},\{2\},\{3\}\}\quad\text{(with 3 blocks)}. {{ 1 } , { 2 } , { 3 }} (with 3 blocks) . Note that { { 1 , 3 } , { 2 } } \{\{1,3\},\{2\}\} {{ 1 , 3 } , { 2 }} { { 2 } , { 3 , 1 } } \{\{2\},\{3,1\}\} {{ 2 } , { 3 , 1 }} Π J \Pi_J Π J J J J ∅ \varnothing ∅ 0 0 0 Π ∅ = { ∅ } \Pi_{\varnothing}=\{\varnothing\} Π ∅ = { ∅ }
Let us agree to always write partitions with their blocks distinct: e.g., when we say “{ P 1 , P 2 , … , P k } ∈ Π J \{P_1,P_2,\ldots,P_k\}\in\Pi_J { P 1 , P 2 , … , P k } ∈ Π J P 1 , P 2 , … , P k P_1,P_2,\ldots,P_k P 1 , P 2 , … , P k
The following formula (discovered by GPT-5.4) will be crucial to our proof of Theorem 0.4 :
Theorem 0.11. Let A A A B B B C C C B B B C C C g : A → B g:A\to B g : A → B f : B → C f:B\to C f : B → C Z \mathbb{Z} Z h : = f ∘ g : A → C h:=f\circ g:A\to C h := f ∘ g : A → C a 1 , a 2 , … , a n ∈ A a_1,a_2,\ldots,a_n\in A a 1 , a 2 , … , a n ∈ A P = { p 1 , p 2 , … , p r } P=\{p_1,p_2,\ldots,p_r\} P = { p 1 , p 2 , … , p r } [ n ] [n] [ n ] p 1 , p 2 , … , p r p_1,p_2,\ldots,p_r p 1 , p 2 , … , p r
b P : = g r ( a p 1 , a p 2 , … , a p r ) . (27) b_P:=g_r(a_{p_1},a_{p_2},\ldots,a_{p_r}). \tag*{(27)} b P := g r ( a p 1 , a p 2 , … , a p r ) . (27) (This is well-defined, i.e., does not depend on the order in which we label the elements of P P P p 1 , p 2 , … , p r , b e c a u s e x r e f ‘ P r o p o s i t i o n 0.7 ‘ s h o w s t h a t t h e m a p p_1,p_2,\ldots,p_r, because {xref}`Proposition 0.7` shows that the map p 1 , p 2 , … , p r , b ec a u se x r e f ‘ P r o p os i t i o n 0.7‘ s h o w s t ha tt h e ma p
h n ( a 1 , a 2 , … , a n ) = ∑ π = { P 1 , P 2 , … , P k } ∈ Π [ n ] f k ( b P 1 , b P 2 , … , b P k ) . h_n(a_1,a_2,\ldots,a_n)=\sum_{\pi=\{P_1,P_2,\ldots,P_k\}\in\Pi_{[n]}}f_k(b_{P_1},b_{P_2},\ldots,b_{P_k}). h n ( a 1 , a 2 , … , a n ) = π = { P 1 , P 2 , … , P k } ∈ Π [ n ] ∑ f k ( b P 1 , b P 2 , … , b P k ) . (The expression f k ( b P 1 , b P 2 , … , b P k ) f_k\left(b_{P_1},b_{P_2},\ldots,b_{P_k}\right) f k ( b P 1 , b P 2 , … , b P k ) π \pi π P 1 , P 2 , … , P k P_1,P_2,\ldots,P_k P 1 , P 2 , … , P k f k f_k f k
Example 0.12. Let us set n = 3 n=3 n = 3
h 3 ( a 1 , a 2 , a 3 ) = ∑ π = { P 1 , P 2 , … , P k } ∈ Π [ 3 ] f k ( b P 1 , b P 2 , … , b P k ) = f 1 ( b { 1 , 2 , 3 } ) + f 2 ( b { 1 , 2 } , b { 3 } ) + f 2 ( b { 1 , 3 } , b { 2 } ) + f 2 ( b { 2 , 3 } , b { 1 } ) + f 3 ( b { 1 } , b { 2 } , b { 3 } ) = f 1 ( g 3 ( a 1 , a 2 , a 3 ) ) + f 2 ( g 2 ( a 1 , a 2 ) , g 1 ( a 3 ) ) + f 2 ( g 2 ( a 1 , a 3 ) , g 1 ( a 2 ) ) + f 2 ( g 2 ( a 2 , a 3 ) , g 1 ( a 1 ) ) + f 3 ( g 1 ( a 1 ) , g 1 ( a 2 ) , g 1 ( a 3 ) ) . \begin{aligned}
h_3(a_1,a_2,a_3)
&=\sum_{\pi=\{P_1,P_2,\ldots,P_k\}\in\Pi_{[3]}}f_k\left(b_{P_1},b_{P_2},\ldots,b_{P_k}\right)\\
&=f_1\left(b_{\{1,2,3\}}\right)+f_2\left(b_{\{1,2\}},b_{\{3\}}\right)+f_2\left(b_{\{1,3\}},b_{\{2\}}\right)\\
&\quad+f_2\left(b_{\{2,3\}},b_{\{1\}}\right)+f_3\left(b_{\{1\}},b_{\{2\}},b_{\{3\}}\right)\\
&=f_1\left(g_3(a_1,a_2,a_3)\right)+f_2\left(g_2(a_1,a_2),g_1(a_3)\right)+f_2\left(g_2(a_1,a_3),g_1(a_2)\right)\\
&\quad+f_2\left(g_2(a_2,a_3),g_1(a_1)\right)+f_3\left(g_1(a_1),g_1(a_2),g_1(a_3)\right).
\end{aligned} h 3 ( a 1 , a 2 , a 3 ) = π = { P 1 , P 2 , … , P k } ∈ Π [ 3 ] ∑ f k ( b P 1 , b P 2 , … , b P k ) = f 1 ( b { 1 , 2 , 3 } ) + f 2 ( b { 1 , 2 } , b { 3 } ) + f 2 ( b { 1 , 3 } , b { 2 } ) + f 2 ( b { 2 , 3 } , b { 1 } ) + f 3 ( b { 1 } , b { 2 } , b { 3 } ) = f 1 ( g 3 ( a 1 , a 2 , a 3 ) ) + f 2 ( g 2 ( a 1 , a 2 ) , g 1 ( a 3 ) ) + f 2 ( g 2 ( a 1 , a 3 ) , g 1 ( a 2 ) ) + f 2 ( g 2 ( a 2 , a 3 ) , g 1 ( a 1 ) ) + f 3 ( g 1 ( a 1 ) , g 1 ( a 2 ) , g 1 ( a 3 ) ) . Proof of Theorem 0.11. I would welcome an inclusion/exclusion argument using cycles of permutations, but GPT-5.4 suggests an induction proof instead, and that shall do.
We induct on n n n
Base case: For n = 0 n=0 n = 0 h 0 ( ) = f 0 ( ) h_0()=f_0() h 0 ( ) = f 0 ( ) Π [ 0 ] = Π ∅ = { ∅ } \Pi_{[0]}=\Pi_{\varnothing}=\{\varnothing\} Π [ 0 ] = Π ∅ = { ∅ }
Strictly speaking, this is enough to complete the base case, but let us also check the n = 1 n=1 n = 1
For n = 1 n=1 n = 1 h 1 ( a 1 ) = f 1 ( b { 1 } ) h_1(a_1)=f_1\left(b_{\{1\}}\right) h 1 ( a 1 ) = f 1 ( b { 1 } ) f 1 = f f_1=f f 1 = f h 1 = h h_1=h h 1 = h b { 1 } = g 1 ( a 1 ) = g ( a 1 ) b_{\{1\}}=g_1(a_1)=g(a_1) b { 1 } = g 1 ( a 1 ) = g ( a 1 ) h ( a 1 ) = f ( g ( a 1 ) ) h(a_1)=f\left(g(a_1)\right) h ( a 1 ) = f ( g ( a 1 ) ) h = f ∘ g h=f\circ g h = f ∘ g
Induction step: Let n ≥ 2 n\ge2 n ≥ 2 n − 1 n-1 n − 1 n n n n n n
The induction hypothesis yields
h n − 1 ( a 1 , a 2 , … , a n − 1 ) = ∑ π = { P 1 , P 2 , … , P k } ∈ Π [ n − 1 ] f k ( b P 1 , b P 2 , … , b P k ) . (28) h_{n-1}(a_1,a_2,\ldots,a_{n-1})=
\sum_{\pi=\{P_1,P_2,\ldots,P_k\}\in\Pi_{[n-1]}}f_k\left(b_{P_1},b_{P_2},\ldots,b_{P_k}\right). \tag*{(28)} h n − 1 ( a 1 , a 2 , … , a n − 1 ) = π = { P 1 , P 2 , … , P k } ∈ Π [ n − 1 ] ∑ f k ( b P 1 , b P 2 , … , b P k ) . (28) Moreover, for each i ∈ [ n − 1 ] i\in[n-1] i ∈ [ n − 1 ] n − 1 n-1 n − 1 a 1 ( i ) , a 2 ( i ) , … , a n − 1 ( i ) a_1^{(i)},a_2^{(i)},\ldots,a_{n-1}^{(i)} a 1 ( i ) , a 2 ( i ) , … , a n − 1 ( i ) A A A
( a 1 ( i ) , a 2 ( i ) , … , a n − 1 ( i ) ) : = ( a 1 , a 2 , … , a i − 1 , a i a n , a i + 1 , a i + 2 , … , a n − 1 ) (29) \left(a_1^{(i)},a_2^{(i)},\ldots,a_{n-1}^{(i)}\right):=\left(a_1,a_2,\ldots,a_{i-1},a_i a_n,a_{i+1},a_{i+2},\ldots,a_{n-1}\right) \tag*{(29)} ( a 1 ( i ) , a 2 ( i ) , … , a n − 1 ( i ) ) := ( a 1 , a 2 , … , a i − 1 , a i a n , a i + 1 , a i + 2 , … , a n − 1 ) (29) (these are what we called a 1 ′ , a 2 ′ , … , a n − 1 ′ a'_1,a'_2,\ldots,a'_{n-1} a 1 ′ , a 2 ′ , … , a n − 1 ′ n − 1 n-1 n − 1
h n − 1 ( a 1 ( i ) , a 2 ( i ) , … , a n − 1 ( i ) ) = ∑ π = { P 1 , P 2 , … , P k } ∈ Π [ n − 1 ] f k ( b P 1 ( i ) , b P 2 ( i ) , … , b P k ( i ) ) , (30) h_{n-1}\left(a_1^{(i)},a_2^{(i)},\ldots,a_{n-1}^{(i)}\right)
=\sum_{\pi=\{P_1,P_2,\ldots,P_k\}\in\Pi_{[n-1]}}f_k\left(b_{P_1}^{(i)},b_{P_2}^{(i)},\ldots,b_{P_k}^{(i)}\right), \tag*{(30)} h n − 1 ( a 1 ( i ) , a 2 ( i ) , … , a n − 1 ( i ) ) = π = { P 1 , P 2 , … , P k } ∈ Π [ n − 1 ] ∑ f k ( b P 1 ( i ) , b P 2 ( i ) , … , b P k ( i ) ) , (30) where for any subset P = { p 1 , p 2 , … , p r } P=\{p_1,p_2,\ldots,p_r\} P = { p 1 , p 2 , … , p r } [ n − 1 ] [n-1] [ n − 1 ] p 1 , p 2 , … , p r p_1,p_2,\ldots,p_r p 1 , p 2 , … , p r
b P ( i ) : = g r ( a p 1 ( i ) , a p 2 ( i ) , … , a p r ( i ) ) . (31) b_P^{(i)}:=g_r\left(a_{p_1}^{(i)},a_{p_2}^{(i)},\ldots,a_{p_r}^{(i)}\right). \tag*{(31)} b P ( i ) := g r ( a p 1 ( i ) , a p 2 ( i ) , … , a p r ( i ) ) . (31) Note that if P P P [ n − 1 ] [n-1] [ n − 1 ] i ∈ [ n − 1 ] i\in[n-1] i ∈ [ n − 1 ] i ∉ P i\notin P i ∈ / P
b P = b P ( i ) . (32) b_P=b_P^{(i)}. \tag*{(32)} b P = b P ( i ) . (32) (Indeed, let P P P [ n − 1 ] [n-1] [ n − 1 ] i ∈ [ n − 1 ] i\in[n-1] i ∈ [ n − 1 ] i ∉ P i\notin P i ∈ / P P P P P = { p 1 , p 2 , … , p r } P=\{p_1,p_2,\ldots,p_r\} P = { p 1 , p 2 , … , p r } p 1 , p 2 , … , p r p_1,p_2,\ldots,p_r p 1 , p 2 , … , p r k ∈ [ r ] k\in[r] k ∈ [ r ] p k ≠ i p_k\ne i p k = i i ∉ P = { p 1 , p 2 , … , p r } i\notin P=\{p_1,p_2,\ldots,p_r\} i ∈ / P = { p 1 , p 2 , … , p r } a p k ( i ) = a p k a_{p_k}^{(i)}=a_{p_k} a p k ( i ) = a p k (29) shows that a j ( i ) = a j a_j^{(i)}=a_j a j ( i ) = a j j ≠ i j\ne i j = i (31) equals the right hand side of (27) . Therefore, the same holds for the left hand sides as well. In other words, we have b P ( i ) = b P b_P^{(i)}=b_P b P ( i ) = b P (32) .)
Note also that (27) yields b { n } = g 1 ( a n ) = g ( a n ) b_{\{n\}}=g_1(a_n)=g(a_n) b { n } = g 1 ( a n ) = g ( a n )
Next, we observe that each subset P P P [ n − 1 ] [n-1] [ n − 1 ]
b P ∪ { n } = b P b { n } − ∑ i ∈ P b P ( i ) . (33) b_{P\cup\{n\}}=b_Pb_{\{n\}}-\sum_{i\in P}b_P^{(i)}. \tag*{(33)} b P ∪ { n } = b P b { n } − i ∈ P ∑ b P ( i ) . (33) (Indeed, let P P P [ n − 1 ] [n-1] [ n − 1 ] P P P P = { p 1 , p 2 , … , p r } P=\{p_1,p_2,\ldots,p_r\} P = { p 1 , p 2 , … , p r } p 1 , p 2 , … , p r p_1,p_2,\ldots,p_r p 1 , p 2 , … , p r P ∪ { n } = { p 1 , p 2 , … , p r , n } P\cup\{n\}=\{p_1,p_2,\ldots,p_r,n\} P ∪ { n } = { p 1 , p 2 , … , p r , n } p 1 , p 2 , … , p r , n p_1,p_2,\ldots,p_r,n p 1 , p 2 , … , p r , n P ⊆ [ n − 1 ] P\subseteq[n-1] P ⊆ [ n − 1 ]
b P ∪ { n } = g r + 1 ( a p 1 , a p 2 , … , a p r , a n ) b_{P\cup\{n\}}=g_{r+1}\left(a_{p_1},a_{p_2},\ldots,a_{p_r},a_n\right) b P ∪ { n } = g r + 1 ( a p 1 , a p 2 , … , a p r , a n ) (by (27) ).
But each i ∈ [ r ] i\in[r] i ∈ [ r ]
b P ( p i ) = g r ( a p 1 ( p i ) , a p 2 ( p i ) , … , a p r ( p i ) ) ⏟ ( a p 1 , a p 2 , … , a p i − 1 , a p i a n , a p i + 1 , a p i + 2 , … , a p r ) b_P^{(p_i)}=g_r\underbrace{\left(a_{p_1}^{(p_i)},a_{p_2}^{(p_i)},\ldots,a_{p_r}^{(p_i)}\right)}_{\left(a_{p_1},a_{p_2},\ldots,a_{p_{i-1}},a_{p_i}a_n,a_{p_{i+1}},a_{p_{i+2}},\ldots,a_{p_r}\right)} b P ( p i ) = g r ( a p 1 , a p 2 , … , a p i − 1 , a p i a n , a p i + 1 , a p i + 2 , … , a p r ) ( a p 1 ( p i ) , a p 2 ( p i ) , … , a p r ( p i ) ) (by (31) )
= ( a p 1 , a p 2 , … , a p i − 1 , a p i a n , a p i + 1 , a p i + 2 , … , a p r ) =\left(a_{p_1},a_{p_2},\ldots,a_{p_{i-1}},a_{p_i}a_n,a_{p_{i+1}},a_{p_{i+2}},\ldots,a_{p_r}\right) = ( a p 1 , a p 2 , … , a p i − 1 , a p i a n , a p i + 1 , a p i + 2 , … , a p r ) (indeed, all k ≠ i k\ne i k = i p k ≠ p i p_k\ne p_i p k = p i p 1 , p 2 , … , p r p_1,p_2,\ldots,p_r p 1 , p 2 , … , p r a p k ( p i ) = a p k a_{p_k}^{(p_i)}=a_{p_k} a p k ( p i ) = a p k (29) ), whereas a p i ( p i ) = a p i a n a_{p_i}^{(p_i)}=a_{p_i}a_n a p i ( p i ) = a p i a n (29) ))
= g r ( a p 1 , a p 2 , … , a p i − 1 , a p i a n , a p i + 1 , a p i + 2 , … , a p r ) . (34) =g_r\left(a_{p_1},a_{p_2},\ldots,a_{p_{i-1}},a_{p_i}a_n,a_{p_{i+1}},a_{p_{i+2}},\ldots,a_{p_r}\right). \tag*{(34)} = g r ( a p 1 , a p 2 , … , a p i − 1 , a p i a n , a p i + 1 , a p i + 2 , … , a p r ) . (34) Now, the recursion (2) (applied to g g g r + 1 r+1 r + 1 ( a p 1 , a p 2 , … , a p r , a n ) \left(a_{p_1},a_{p_2},\ldots,a_{p_r},a_n\right) ( a p 1 , a p 2 , … , a p r , a n ) f f f n n n ( a 1 , a 2 , … , a n ) ) (a_1,a_2,\ldots,a_n)) ( a 1 , a 2 , … , a n ))
g r + 1 ( a p 1 , a p 2 , … , a p r , a n ) = g ( a n ) g r ( a p 1 , a p 2 , … , a p r ) − ∑ i = 1 r g r ( a p 1 , a p 2 , … , a p i − 1 , a p i a n , a p i + 1 , a p i + 2 , … , a p r ) = b { n } b P − ∑ i = 1 r b P ( p i ) = b { n } b P − ∑ j ∈ P b P ( j ) . g_{r+1}(a_{p_1},a_{p_2},\ldots,a_{p_r},a_n)
= g(a_n)g_r(a_{p_1},a_{p_2},\ldots,a_{p_r})
-\sum_{i=1}^{r}g_r(a_{p_1},a_{p_2},\ldots,a_{p_{i-1}},a_{p_i}a_n,a_{p_{i+1}},a_{p_{i+2}},\ldots,a_{p_r})
= b_{\{n\}}b_P-\sum_{i=1}^{r}b_P^{(p_i)}
= b_{\{n\}}b_P-\sum_{j\in P}b_P^{(j)}. g r + 1 ( a p 1 , a p 2 , … , a p r , a n ) = g ( a n ) g r ( a p 1 , a p 2 , … , a p r ) − i = 1 ∑ r g r ( a p 1 , a p 2 , … , a p i − 1 , a p i a n , a p i + 1 , a p i + 2 , … , a p r ) = b { n } b P − i = 1 ∑ r b P ( p i ) = b { n } b P − j ∈ P ∑ b P ( j ) . (here, we have substituted j j j p i p_i p i P = { p 1 , p 2 , … , p r } P=\{p_1,p_2,\ldots,p_r\} P = { p 1 , p 2 , … , p r } p 1 , p 2 , … , p r p_1,p_2,\ldots,p_r p 1 , p 2 , … , p r
b P ∪ { n } = b { n } b P − ∑ j ∈ P b P ( j ) = b P b { n } − ∑ i ∈ P b P ( i ) . b_{P\cup\{n\}}=b_{\{n\}}b_P-\sum_{j\in P}b_P^{(j)}=b_Pb_{\{n\}}-\sum_{i\in P}b_P^{(i)}. b P ∪ { n } = b { n } b P − j ∈ P ∑ b P ( j ) = b P b { n } − i ∈ P ∑ b P ( i ) . This proves (33).
Let del : Π [ n ] → Π [ n − 1 ] \operatorname{del}:\Pi_{[n]}\to\Pi_{[n-1]} del : Π [ n ] → Π [ n − 1 ] π \pi π [ n ] [n] [ n ] [ n − 1 ] [n-1] [ n − 1 ] n n n π \pi π n = 4 n=4 n = 4
del ( { { 1 , 4 } , { 2 , 3 } } ) = { { 1 } , { 2 , 3 } } \operatorname{del}(\{\{1,4\},\{2,3\}\})=\{\{1\},\{2,3\}\} del ({{ 1 , 4 } , { 2 , 3 }}) = {{ 1 } , { 2 , 3 }} and
del ( { { 1 } , { 2 , 3 } , { 4 } } ) = { { 1 } , { 2 , 3 } } . \operatorname{del}(\{\{1\},\{2,3\},\{4\}\})=\{\{1\},\{2,3\}\}. del ({{ 1 } , { 2 , 3 } , { 4 }}) = {{ 1 } , { 2 , 3 }} . Thus, we can split the sum on the right hand side of Theorem 0.11 as follows:
∑ π = { P 1 , P 2 , … , P k } ∈ Π [ n ] f k ( b P 1 , b P 2 , … , b P k ) = ∑ ω = { Q 1 , Q 2 , … , Q ℓ } ∈ Π [ n − 1 ] ∑ π = { P 1 , P 2 , … , P k } ∈ Π [ n ] del ( π ) = ω f k ( b P 1 , b P 2 , … , b P k ) . (35) \sum_{\pi=\{P_1,P_2,\ldots,P_k\}\in\Pi_{[n]}}f_k(b_{P_1},b_{P_2},\ldots,b_{P_k})
=
\sum_{\omega=\{Q_1,Q_2,\ldots,Q_\ell\}\in\Pi_{[n-1]}}
\sum_{\substack{\pi=\{P_1,P_2,\ldots,P_k\}\in\Pi_{[n]}\\\operatorname{del}(\pi)=\omega}}
f_k(b_{P_1},b_{P_2},\ldots,b_{P_k}). \tag*{(35)} π = { P 1 , P 2 , … , P k } ∈ Π [ n ] ∑ f k ( b P 1 , b P 2 , … , b P k ) = ω = { Q 1 , Q 2 , … , Q ℓ } ∈ Π [ n − 1 ] ∑ π = { P 1 , P 2 , … , P k } ∈ Π [ n ] del ( π ) = ω ∑ f k ( b P 1 , b P 2 , … , b P k ) . (35) Now, fix a partition ω = { Q 1 , Q 2 , … , Q ℓ } ∈ Π [ n − 1 ] \omega=\{Q_1,Q_2,\ldots,Q_\ell\}\in\Pi_{[n-1]} ω = { Q 1 , Q 2 , … , Q ℓ } ∈ Π [ n − 1 ] π ∈ Π [ n ] \pi\in\Pi_{[n]} π ∈ Π [ n ] del ( π ) = ω \operatorname{del}(\pi)=\omega del ( π ) = ω [ n ] [n] [ n ] ω \omega ω n n n ω \omega ω { n } \{n\} { n } n n n Q 1 , Q 2 , … , Q ℓ Q_1,Q_2,\ldots,Q_\ell Q 1 , Q 2 , … , Q ℓ ℓ + 1 \ell+1 ℓ + 1 π ∈ Π [ n ] \pi\in\Pi_{[n]} π ∈ Π [ n ] del ( π ) = ω \operatorname{del}(\pi)=\omega del ( π ) = ω
{ Q 1 , Q 2 , … , Q ℓ , { n } } \{Q_1,Q_2,\ldots,Q_\ell,\{n\}\} { Q 1 , Q 2 , … , Q ℓ , { n }} and the ℓ \ell ℓ
{ Q 1 , Q 2 , … , Q j ∪ { n } , … , Q ℓ } for j ∈ [ ℓ ] \{Q_1,Q_2,\ldots,Q_j\cup\{n\},\ldots,Q_\ell\}\qquad\text{for }j\in[\ell] { Q 1 , Q 2 , … , Q j ∪ { n } , … , Q ℓ } for j ∈ [ ℓ ] (the notation “Q 1 , Q 2 , … , Q j ∪ { n } , … , Q ℓ Q_1,Q_2,\ldots,Q_j\cup\{n\},\ldots,Q_\ell Q 1 , Q 2 , … , Q j ∪ { n } , … , Q ℓ Q 1 , Q 2 , … , Q ℓ Q_1,Q_2,\ldots,Q_\ell Q 1 , Q 2 , … , Q ℓ j j j Q j ∪ { n } Q_j\cup\{n\} Q j ∪ { n }
∑ π = { P 1 , P 2 , … , P k } ∈ Π [ n ] del ( π ) = ω f k ( b P 1 , b P 2 , … , b P k ) = f ℓ + 1 ( b Q 1 , b Q 2 , … , b Q ℓ , b { n } ) + ∑ j = 1 ℓ f ℓ ( b Q 1 , b Q 2 , … , b Q j ∪ { n } , … , b Q ℓ ) (36) \begin{aligned}
\sum_{\substack{\pi=\{P_1,P_2,\ldots,P_k\}\in\Pi_{[n]}\\ \operatorname{del}(\pi)=\omega}}
f_k\left(b_{P_1},b_{P_2},\ldots,b_{P_k}\right)
&=f_{\ell+1}\left(b_{Q_1},b_{Q_2},\ldots,b_{Q_\ell},b_{\{n\}}\right)\\
&\quad+\sum_{j=1}^{\ell}f_\ell\left(b_{Q_1},b_{Q_2},\ldots,b_{Q_j\cup\{n\}},\ldots,b_{Q_\ell}\right) \tag*{(36)}
\end{aligned} π = { P 1 , P 2 , … , P k } ∈ Π [ n ] del ( π ) = ω ∑ f k ( b P 1 , b P 2 , … , b P k ) = f ℓ + 1 ( b Q 1 , b Q 2 , … , b Q ℓ , b { n } ) + j = 1 ∑ ℓ f ℓ ( b Q 1 , b Q 2 , … , b Q j ∪ { n } , … , b Q ℓ ) (36) (where “b Q 1 , b Q 2 , … , b Q j ∪ { n } , … , b Q ℓ b_{Q_1},b_{Q_2},\ldots,b_{Q_j\cup\{n\}},\ldots,b_{Q_\ell} b Q 1 , b Q 2 , … , b Q j ∪ { n } , … , b Q ℓ b Q 1 , b Q 2 , … , b Q ℓ b_{Q_1},b_{Q_2},\ldots,b_{Q_\ell} b Q 1 , b Q 2 , … , b Q ℓ j j j b Q j ∪ { n } b_{Q_j\cup\{n\}} b Q j ∪ { n }
Now, let j ∈ [ ℓ ] j\in[\ell] j ∈ [ ℓ ] Q j ⊆ [ n − 1 ] Q_j\subseteq[n-1] Q j ⊆ [ n − 1 ] Q j Q_j Q j ω ∈ Π [ n − 1 ] \omega\in\Pi_{[n-1]} ω ∈ Π [ n − 1 ]
b Q j ∪ { n } = b Q j b { n } − ∑ i ∈ Q j b Q j ( i ) b_{Q_j\cup\{n\}}=b_{Q_j}b_{\{n\}}-\sum_{i\in Q_j}b_{Q_j}^{(i)} b Q j ∪ { n } = b Q j b { n } − i ∈ Q j ∑ b Q j ( i ) (by (33) , applied to P = Q j P=Q_j P = Q j
f ℓ ( b Q 1 , b Q 2 , … , b Q j ∪ { n } , … , b Q ℓ ) = f ℓ ( b Q 1 , b Q 2 , … , b Q j b { n } − ∑ i ∈ Q j b Q j ( i ) , … , b Q ℓ ) = f ℓ ( b Q 1 , b Q 2 , … , b Q j b { n } , … , b Q ℓ ) − ∑ i ∈ Q j f ℓ ( b Q 1 , b Q 2 , … , b Q j ( i ) , … , b Q ℓ ) (37) \begin{aligned}
f_\ell\left(b_{Q_1},b_{Q_2},\ldots,b_{Q_j\cup\{n\}},\ldots,b_{Q_\ell}\right)
&=f_\ell\left(b_{Q_1},b_{Q_2},\ldots,b_{Q_j}b_{\{n\}}-\sum_{i\in Q_j}b_{Q_j}^{(i)},\ldots,b_{Q_\ell}\right)\\
&=f_\ell\left(b_{Q_1},b_{Q_2},\ldots,b_{Q_j}b_{\{n\}},\ldots,b_{Q_\ell}\right)\\
&\quad-\sum_{i\in Q_j}f_\ell\left(b_{Q_1},b_{Q_2},\ldots,b_{Q_j}^{(i)},\ldots,b_{Q_\ell}\right) \tag*{(37)}
\end{aligned} f ℓ ( b Q 1 , b Q 2 , … , b Q j ∪ { n } , … , b Q ℓ ) = f ℓ b Q 1 , b Q 2 , … , b Q j b { n } − i ∈ Q j ∑ b Q j ( i ) , … , b Q ℓ = f ℓ ( b Q 1 , b Q 2 , … , b Q j b { n } , … , b Q ℓ ) − i ∈ Q j ∑ f ℓ ( b Q 1 , b Q 2 , … , b Q j ( i ) , … , b Q ℓ ) (37) (since the map f ℓ f_\ell f ℓ Z \mathbb{Z} Z j j j k ∈ [ ℓ ] ∖ { j } k\in[\ell]\setminus\{j\} k ∈ [ ℓ ] ∖ { j } i ∈ Q j i\in Q_j i ∈ Q j Q k ∩ Q j = ∅ Q_k\cap Q_j=\varnothing Q k ∩ Q j = ∅ ω \omega ω i ∉ Q k i\notin Q_k i ∈ / Q k i ∈ Q j i\in Q_j i ∈ Q j b Q k = b Q k ( i ) b_{Q_k}=b_{Q_k}^{(i)} b Q k = b Q k ( i ) (32) , applied to P = Q k P=Q_k P = Q k (37) , we can replace each b Q k b_{Q_k} b Q k b Q k ( i ) b_{Q_k}^{(i)} b Q k ( i ) (37) rewrites as
f ℓ ( b Q 1 , b Q 2 , … , b Q j ∪ { n } , … , b Q ℓ ) = f ℓ ( b Q 1 , b Q 2 , … , b Q j b { n } , … , b Q ℓ ) − ∑ i ∈ Q j f ℓ ( b Q 1 ( i ) , b Q 2 ( i ) , … , b Q j ( i ) , … , b Q ℓ ( i ) ) = f ℓ ( b Q 1 , b Q 2 , … , b Q j ∪ { n } , … , b Q ℓ ) − ∑ i ∈ Q j f ℓ ( b Q 1 ( i ) , b Q 2 ( i ) , … , b Q ℓ ( i ) ) . (38) \begin{aligned}
f_{\ell}\left(b_{Q_1},b_{Q_2},\ldots,b_{Q_j\cup\{n\}},\ldots,b_{Q_\ell}\right)
&=f_{\ell}\left(b_{Q_1},b_{Q_2},\ldots,b_{Q_j}b_{\{n\}},\ldots,b_{Q_\ell}\right)\\
&\quad-\sum_{i\in Q_j}f_{\ell}\left(b_{Q_1}^{(i)},b_{Q_2}^{(i)},\ldots,b_{Q_j}^{(i)},\ldots,b_{Q_\ell}^{(i)}\right)\\
&=f_{\ell}\left(b_{Q_1},b_{Q_2},\ldots,b_{Q_j\cup\{n\}},\ldots,b_{Q_\ell}\right)\\
&\quad-\sum_{i\in Q_j}f_{\ell}\left(b_{Q_1}^{(i)},b_{Q_2}^{(i)},\ldots,b_{Q_\ell}^{(i)}\right). \tag*{(38)}
\end{aligned} f ℓ ( b Q 1 , b Q 2 , … , b Q j ∪ { n } , … , b Q ℓ ) = f ℓ ( b Q 1 , b Q 2 , … , b Q j b { n } , … , b Q ℓ ) − i ∈ Q j ∑ f ℓ ( b Q 1 ( i ) , b Q 2 ( i ) , … , b Q j ( i ) , … , b Q ℓ ( i ) ) = f ℓ ( b Q 1 , b Q 2 , … , b Q j ∪ { n } , … , b Q ℓ ) − i ∈ Q j ∑ f ℓ ( b Q 1 ( i ) , b Q 2 ( i ) , … , b Q ℓ ( i ) ) . (38) Forget that we fixed j j j j ∈ [ ℓ ] j\in[\ell] j ∈ [ ℓ ]
∑ j = 1 ℓ f ℓ ( b Q 1 , b Q 2 , … , b Q j ∪ { n } , … , b Q ℓ ) = ∑ j = 1 ℓ ( f ℓ ( b Q 1 , b Q 2 , … , b Q j b { n } , … , b Q ℓ ) − ∑ i ∈ Q j f ℓ ( b Q 1 ( i ) , b Q 2 ( i ) , … , b Q ℓ ( i ) ) ) = ∑ j = 1 ℓ f ℓ ( b Q 1 , b Q 2 , … , b Q j ∪ { n } , … , b Q ℓ ) − ∑ j = 1 ℓ ∑ i ∈ Q j f ℓ ( b Q 1 ( i ) , b Q 2 ( i ) , … , b Q ℓ ( i ) ) . (39) \begin{aligned}
\sum_{j=1}^{\ell}f_{\ell}\left(b_{Q_1},b_{Q_2},\ldots,b_{Q_j\cup\{n\}},\ldots,b_{Q_\ell}\right)
&=\sum_{j=1}^{\ell}\left(f_{\ell}\left(b_{Q_1},b_{Q_2},\ldots,b_{Q_j}b_{\{n\}},\ldots,b_{Q_\ell}\right)\right.\\
&\quad\left.-\sum_{i\in Q_j}f_{\ell}\left(b_{Q_1}^{(i)},b_{Q_2}^{(i)},\ldots,b_{Q_\ell}^{(i)}\right)\right)\\
&=\sum_{j=1}^{\ell}f_{\ell}\left(b_{Q_1},b_{Q_2},\ldots,b_{Q_j\cup\{n\}},\ldots,b_{Q_\ell}\right)\\
&\quad-\sum_{j=1}^{\ell}\sum_{i\in Q_j}f_{\ell}\left(b_{Q_1}^{(i)},b_{Q_2}^{(i)},\ldots,b_{Q_\ell}^{(i)}\right). \tag*{(39)}
\end{aligned} j = 1 ∑ ℓ f ℓ ( b Q 1 , b Q 2 , … , b Q j ∪ { n } , … , b Q ℓ ) = j = 1 ∑ ℓ ( f ℓ ( b Q 1 , b Q 2 , … , b Q j b { n } , … , b Q ℓ ) − i ∈ Q j ∑ f ℓ ( b Q 1 ( i ) , b Q 2 ( i ) , … , b Q ℓ ( i ) ) = j = 1 ∑ ℓ f ℓ ( b Q 1 , b Q 2 , … , b Q j ∪ { n } , … , b Q ℓ ) − j = 1 ∑ ℓ i ∈ Q j ∑ f ℓ ( b Q 1 ( i ) , b Q 2 ( i ) , … , b Q ℓ ( i ) ) . (39) In this equality, we can replace the two summation signs ∑ j = 1 ℓ ∑ i ∈ Q j \sum_{j=1}^{\ell}\sum_{i\in Q_j} ∑ j = 1 ℓ ∑ i ∈ Q j ∑ i = 1 n − 1 \sum_{i=1}^{n-1} ∑ i = 1 n − 1 Q 1 , Q 2 , … , Q ℓ Q_1,Q_2,\ldots,Q_\ell Q 1 , Q 2 , … , Q ℓ [ n − 1 ] [n-1] [ n − 1 ] i ∈ [ n − 1 ] i\in[n-1] i ∈ [ n − 1 ]
∑ j = 1 ℓ f ℓ ( b Q 1 , b Q 2 , … , b Q j ∪ { n } , … , b Q ℓ ) = ∑ j = 1 ℓ f ℓ ( b Q 1 , b Q 2 , … , b Q j b { n } , … , b Q ℓ ) − ∑ i = 1 n − 1 f ℓ ( b Q 1 ( i ) , b Q 2 ( i ) , … , b Q ℓ ( i ) ) . (40) \begin{aligned}
\sum_{j=1}^{\ell}f_{\ell}\left(b_{Q_1},b_{Q_2},\ldots,b_{Q_j\cup\{n\}},\ldots,b_{Q_\ell}\right)
&=\sum_{j=1}^{\ell}f_{\ell}\left(b_{Q_1},b_{Q_2},\ldots,b_{Q_j}b_{\{n\}},\ldots,b_{Q_\ell}\right)\\
&\quad-\sum_{i=1}^{n-1}f_{\ell}\left(b_{Q_1}^{(i)},b_{Q_2}^{(i)},\ldots,b_{Q_\ell}^{(i)}\right). \tag*{(40)}
\end{aligned} j = 1 ∑ ℓ f ℓ ( b Q 1 , b Q 2 , … , b Q j ∪ { n } , … , b Q ℓ ) = j = 1 ∑ ℓ f ℓ ( b Q 1 , b Q 2 , … , b Q j b { n } , … , b Q ℓ ) − i = 1 ∑ n − 1 f ℓ ( b Q 1 ( i ) , b Q 2 ( i ) , … , b Q ℓ ( i ) ) . (40) Substituting this into (37), we find
∑ π = { P 1 , P 2 , … , P k } ∈ Π [ n ] del ( π ) = ω f k ( b P 1 , b P 2 , … , b P k ) = f ℓ + 1 ( b Q 1 , b Q 2 , … , b Q ℓ , b { n } ) + ∑ j = 1 ℓ f ℓ ( b Q 1 , b Q 2 , … , b Q j b { n } , … , b Q ℓ ) − ∑ i = 1 n − 1 f ℓ ( b Q 1 ( i ) , b Q 2 ( i ) , … , b Q ℓ ( i ) ) . (41) \sum_{\substack{\pi=\{P_1,P_2,\ldots,P_k\}\in\Pi_{[n]}\\ \operatorname{del}(\pi)=\omega}} f_k\left(b_{P_1},b_{P_2},\ldots,b_{P_k}\right)
= f_{\ell+1}\left(b_{Q_1},b_{Q_2},\ldots,b_{Q_\ell},b_{\{n\}}\right)
+ \sum_{j=1}^{\ell} f_\ell\left(b_{Q_1},b_{Q_2},\ldots,b_{Q_j}b_{\{n\}},\ldots,b_{Q_\ell}\right)
- \sum_{i=1}^{n-1} f_\ell\left(b_{Q_1}^{(i)},b_{Q_2}^{(i)},\ldots,b_{Q_\ell}^{(i)}\right). \tag*{(41)} π = { P 1 , P 2 , … , P k } ∈ Π [ n ] del ( π ) = ω ∑ f k ( b P 1 , b P 2 , … , b P k ) = f ℓ + 1 ( b Q 1 , b Q 2 , … , b Q ℓ , b { n } ) + j = 1 ∑ ℓ f ℓ ( b Q 1 , b Q 2 , … , b Q j b { n } , … , b Q ℓ ) − i = 1 ∑ n − 1 f ℓ ( b Q 1 ( i ) , b Q 2 ( i ) , … , b Q ℓ ( i ) ) . (41) However, the recursion (2) (applied to ℓ + 1 \ell+1 ℓ + 1 ( b Q 1 , b Q 2 , … , b Q ℓ , b { n } ) \left(b_{Q_1},b_{Q_2},\ldots,b_{Q_\ell},b_{\{n\}}\right) ( b Q 1 , b Q 2 , … , b Q ℓ , b { n } ) n n n ( a 1 , a 2 , … , a n ) \left(a_1,a_2,\ldots,a_n\right) ( a 1 , a 2 , … , a n )
f ℓ + 1 ( b Q 1 , b Q 2 , … , b Q ℓ , b { n } ) = f ( b { n } ) f ℓ ( b Q 1 , b Q 2 , … , b Q ℓ ) − ∑ i = 1 ℓ f ℓ ( b Q 1 , b Q 2 , … , b Q i b { n } , … , b Q ℓ ) = f ( b { n } ) f ℓ ( b Q 1 , b Q 2 , … , b Q ℓ ) − ∑ j = 1 ℓ f ℓ ( b Q 1 , b Q 2 , … , b Q j b { n } , … , b Q ℓ ) . \begin{aligned}
f_{\ell+1}\left(b_{Q_1},b_{Q_2},\ldots,b_{Q_\ell},b_{\{n\}}\right)
= f\left(b_{\{n\}}\right)f_\ell\left(b_{Q_1},b_{Q_2},\ldots,b_{Q_\ell}\right)
- \sum_{i=1}^{\ell} f_\ell\left(b_{Q_1},b_{Q_2},\ldots,b_{Q_i}b_{\{n\}},\ldots,b_{Q_\ell}\right) \\
&= f\left(b_{\{n\}}\right)f_\ell\left(b_{Q_1},b_{Q_2},\ldots,b_{Q_\ell}\right)
- \sum_{j=1}^{\ell} f_\ell\left(b_{Q_1},b_{Q_2},\ldots,b_{Q_j}b_{\{n\}},\ldots,b_{Q_\ell}\right).
\end{aligned} f ℓ + 1 ( b Q 1 , b Q 2 , … , b Q ℓ , b { n } ) = f ( b { n } ) f ℓ ( b Q 1 , b Q 2 , … , b Q ℓ ) − i = 1 ∑ ℓ f ℓ ( b Q 1 , b Q 2 , … , b Q i b { n } , … , b Q ℓ ) = f ( b { n } ) f ℓ ( b Q 1 , b Q 2 , … , b Q ℓ ) − j = 1 ∑ ℓ f ℓ ( b Q 1 , b Q 2 , … , b Q j b { n } , … , b Q ℓ ) . In other words,
f ℓ + 1 ( b Q 1 , b Q 2 , … , b Q ℓ , b { n } ) + ∑ j = 1 ℓ f ℓ ( b Q 1 , b Q 2 , … , b Q j b { n } , … , b Q ℓ ) = f ( b { n } ) f ℓ ( b Q 1 , b Q 2 , … , b Q ℓ ) . f_{\ell+1}\left(b_{Q_1},b_{Q_2},\ldots,b_{Q_\ell},b_{\{n\}}\right)
+ \sum_{j=1}^{\ell} f_\ell\left(b_{Q_1},b_{Q_2},\ldots,b_{Q_j}b_{\{n\}},\ldots,b_{Q_\ell}\right)
= f\left(b_{\{n\}}\right)f_\ell\left(b_{Q_1},b_{Q_2},\ldots,b_{Q_\ell}\right). f ℓ + 1 ( b Q 1 , b Q 2 , … , b Q ℓ , b { n } ) + j = 1 ∑ ℓ f ℓ ( b Q 1 , b Q 2 , … , b Q j b { n } , … , b Q ℓ ) = f ( b { n } ) f ℓ ( b Q 1 , b Q 2 , … , b Q ℓ ) . Substituting this into (42), we obtain
∑ π = { P 1 , P 2 , … , P k } ∈ Π [ n ] del ( π ) = ω f k ( b P 1 , b P 2 , … , b P k ) = f ( b { n } ) f ℓ ( b Q 1 , b Q 2 , … , b Q ℓ ) − ∑ i = 1 n − 1 f ℓ ( b Q 1 ( i ) , b Q 2 ( i ) , … , b Q ℓ ( i ) ) . (42) \sum_{\substack{\pi=\{P_1,P_2,\ldots,P_k\}\in\Pi_{[n]}\\ \operatorname{del}(\pi)=\omega}} f_k\left(b_{P_1},b_{P_2},\ldots,b_{P_k}\right)
= f\left(b_{\{n\}}\right)f_\ell\left(b_{Q_1},b_{Q_2},\ldots,b_{Q_\ell}\right)
- \sum_{i=1}^{n-1} f_\ell\left(b_{Q_1}^{(i)},b_{Q_2}^{(i)},\ldots,b_{Q_\ell}^{(i)}\right). \tag*{(42)} π = { P 1 , P 2 , … , P k } ∈ Π [ n ] del ( π ) = ω ∑ f k ( b P 1 , b P 2 , … , b P k ) = f ( b { n } ) f ℓ ( b Q 1 , b Q 2 , … , b Q ℓ ) − i = 1 ∑ n − 1 f ℓ ( b Q 1 ( i ) , b Q 2 ( i ) , … , b Q ℓ ( i ) ) . (42) Forget that we fixed ω \omega ω ω = { Q 1 , Q 2 , … , Q ℓ } ∈ Π [ n − 1 ] \omega=\{Q_1,Q_2,\ldots,Q_\ell\}\in\Pi_{[n-1]} ω = { Q 1 , Q 2 , … , Q ℓ } ∈ Π [ n − 1 ]
∑ π = { P 1 , P 2 , … , P k } ∈ Π [ n ] f k ( b P 1 , b P 2 , … , b P k ) = ∑ ω = { Q 1 , Q 2 , … , Q ℓ } ∈ Π [ n − 1 ] π = { P 1 , P 2 , … , P k } ∈ Π [ n ] del ( π ) = ω f k ( b P 1 , b P 2 , … , b P k ) = ∑ ω = { Q 1 , Q 2 , … , Q ℓ } ∈ Π [ n − 1 ] ( f ( b { n } ) f ℓ ( b Q 1 , b Q 2 , … , b Q ℓ ) − ∑ i = 1 n − 1 f ℓ ( b Q 1 ( i ) , b Q 2 ( i ) , … , b Q ℓ ( i ) ) ) (by (43)) = f ( b { n } ⏟ = g ( a n ) ) ∑ ω = { Q 1 , Q 2 , … , Q ℓ } ∈ Π [ n − 1 ] f ℓ ( b Q 1 , b Q 2 , … , b Q ℓ ) ⏟ = ∑ π = { P 1 , P 2 , … , P k } ∈ Π [ n − 1 ] f k ( b P 1 , b P 2 , … , b P k ) = h n − 1 ( a 1 , a 2 , … , a n − 1 ) (by (28)) − ∑ i = 1 n − 1 ∑ ω = { Q 1 , Q 2 , … , Q ℓ } ∈ Π [ n − 1 ] f ℓ ( b Q 1 ( i ) , b Q 2 ( i ) , … , b Q ℓ ( i ) ) ⏟ = ∑ π = { P 1 , P 2 , … , P k } ∈ Π [ n − 1 ] f k ( b P 1 ( i ) , b P 2 ( i ) , … , b P k ( i ) ) = h n − 1 ( a 1 ( i ) , a 2 ( i ) , … , a n − 1 ( i ) ) (by (30)) = f ( g ( a n ) ) h n − 1 ( a 1 , a 2 , … , a n − 1 ) − ∑ i = 1 n − 1 h n − 1 ( a 1 ( i ) , a 2 ( i ) , … , a n − 1 ( i ) ⏟ = ( a 1 , a 2 , … , a i − 1 , a i a n , a i + 1 , a i + 2 , … , a n − 1 ) (by (29)) ) = h ( a n ) h n − 1 ( a 1 , a 2 , … , a n − 1 ) − ∑ i = 1 n − 1 h n − 1 ( a 1 , a 2 , … , a i − 1 , a i a n , a i + 1 , a i + 2 , … , a n − 1 ) . \begin{aligned}
\sum_{\pi=\{P_1,P_2,\ldots,P_k\}\in\Pi_{[n]}} f_k\left(b_{P_1},b_{P_2},\ldots,b_{P_k}\right)
&=\sum_{\substack{\omega=\{Q_1,Q_2,\ldots,Q_\ell\}\in\Pi_{[n-1]}\\ \pi=\{P_1,P_2,\ldots,P_k\}\in\Pi_{[n]}\\ \operatorname{del}(\pi)=\omega}} f_k\left(b_{P_1},b_{P_2},\ldots,b_{P_k}\right)\\
&=\sum_{\omega=\{Q_1,Q_2,\ldots,Q_\ell\}\in\Pi_{[n-1]}}\left(f\left(b_{\{n\}}\right)f_\ell\left(b_{Q_1},b_{Q_2},\ldots,b_{Q_\ell}\right)-\sum_{i=1}^{n-1}f_\ell\left(b_{Q_1}^{(i)},b_{Q_2}^{(i)},\ldots,b_{Q_\ell}^{(i)}\right)\right)\qquad\text{(by (43))}\\
&=f\left(\underbrace{b_{\{n\}}}_{=g(a_n)}\right)\underbrace{\sum_{\omega=\{Q_1,Q_2,\ldots,Q_\ell\}\in\Pi_{[n-1]}}f_\ell\left(b_{Q_1},b_{Q_2},\ldots,b_{Q_\ell}\right)}_{=\sum_{\pi=\{P_1,P_2,\ldots,P_k\}\in\Pi_{[n-1]}}f_k\left(b_{P_1},b_{P_2},\ldots,b_{P_k}\right)=h_{n-1}(a_1,a_2,\ldots,a_{n-1})\ \text{(by (28))}}\\
&\quad-\sum_{i=1}^{n-1}\underbrace{\sum_{\omega=\{Q_1,Q_2,\ldots,Q_\ell\}\in\Pi_{[n-1]}}f_\ell\left(b_{Q_1}^{(i)},b_{Q_2}^{(i)},\ldots,b_{Q_\ell}^{(i)}\right)}_{=\sum_{\pi=\{P_1,P_2,\ldots,P_k\}\in\Pi_{[n-1]}}f_k\left(b_{P_1}^{(i)},b_{P_2}^{(i)},\ldots,b_{P_k}^{(i)}\right)=h_{n-1}\left(a_1^{(i)},a_2^{(i)},\ldots,a_{n-1}^{(i)}\right)\ \text{(by (30))}}\\
&=f\left(g(a_n)\right)h_{n-1}(a_1,a_2,\ldots,a_{n-1})-\sum_{i=1}^{n-1}h_{n-1}\left(\underbrace{a_1^{(i)},a_2^{(i)},\ldots,a_{n-1}^{(i)}}_{=(a_1,a_2,\ldots,a_{i-1},a_i a_n,a_{i+1},a_{i+2},\ldots,a_{n-1})\ \text{(by (29))}}\right)\\
&=h(a_n)h_{n-1}(a_1,a_2,\ldots,a_{n-1})-\sum_{i=1}^{n-1}h_{n-1}(a_1,a_2,\ldots,a_{i-1},a_i a_n,a_{i+1},a_{i+2},\ldots,a_{n-1}).
\end{aligned} π = { P 1 , P 2 , … , P k } ∈ Π [ n ] ∑ f k ( b P 1 , b P 2 , … , b P k ) = ω = { Q 1 , Q 2 , … , Q ℓ } ∈ Π [ n − 1 ] π = { P 1 , P 2 , … , P k } ∈ Π [ n ] del ( π ) = ω ∑ f k ( b P 1 , b P 2 , … , b P k ) = ω = { Q 1 , Q 2 , … , Q ℓ } ∈ Π [ n − 1 ] ∑ ( f ( b { n } ) f ℓ ( b Q 1 , b Q 2 , … , b Q ℓ ) − i = 1 ∑ n − 1 f ℓ ( b Q 1 ( i ) , b Q 2 ( i ) , … , b Q ℓ ( i ) ) ) (by (43)) = f = g ( a n ) b { n } = ∑ π = { P 1 , P 2 , … , P k } ∈ Π [ n − 1 ] f k ( b P 1 , b P 2 , … , b P k ) = h n − 1 ( a 1 , a 2 , … , a n − 1 ) (by (28)) ω = { Q 1 , Q 2 , … , Q ℓ } ∈ Π [ n − 1 ] ∑ f ℓ ( b Q 1 , b Q 2 , … , b Q ℓ ) − i = 1 ∑ n − 1 = ∑ π = { P 1 , P 2 , … , P k } ∈ Π [ n − 1 ] f k ( b P 1 ( i ) , b P 2 ( i ) , … , b P k ( i ) ) = h n − 1 ( a 1 ( i ) , a 2 ( i ) , … , a n − 1 ( i ) ) (by (30)) ω = { Q 1 , Q 2 , … , Q ℓ } ∈ Π [ n − 1 ] ∑ f ℓ ( b Q 1 ( i ) , b Q 2 ( i ) , … , b Q ℓ ( i ) ) = f ( g ( a n ) ) h n − 1 ( a 1 , a 2 , … , a n − 1 ) − i = 1 ∑ n − 1 h n − 1 = ( a 1 , a 2 , … , a i − 1 , a i a n , a i + 1 , a i + 2 , … , a n − 1 ) (by (29)) a 1 ( i ) , a 2 ( i ) , … , a n − 1 ( i ) = h ( a n ) h n − 1 ( a 1 , a 2 , … , a n − 1 ) − i = 1 ∑ n − 1 h n − 1 ( a 1 , a 2 , … , a i − 1 , a i a n , a i + 1 , a i + 2 , … , a n − 1 ) . On the other hand, the recursion (2) yields
h n ( a 1 , a 2 , … , a n ) = h ( a n ) h n − 1 ( a 1 , a 2 , … , a n − 1 ) − ∑ i = 1 n − 1 h n − 1 ( a 1 , a 2 , … , a i − 1 , a i a n , a i + 1 , a i + 2 , … , a n − 1 ) . \begin{aligned}
h_n(a_1,a_2,\ldots,a_n)
&=h(a_n)h_{n-1}(a_1,a_2,\ldots,a_{n-1})\\
&\quad-\sum_{i=1}^{n-1}h_{n-1}(a_1,a_2,\ldots,a_{i-1},a_i a_n,a_{i+1},a_{i+2},\ldots,a_{n-1}).
\end{aligned} h n ( a 1 , a 2 , … , a n ) = h ( a n ) h n − 1 ( a 1 , a 2 , … , a n − 1 ) − i = 1 ∑ n − 1 h n − 1 ( a 1 , a 2 , … , a i − 1 , a i a n , a i + 1 , a i + 2 , … , a n − 1 ) . Comparing these two equalities, we find
h n ( a 1 , a 2 , … , a n ) = ∑ π = { P 1 , P 2 , … , P k } ∈ Π [ n ] f k ( b P 1 , b P 2 , … , b P k ) . h_n(a_1,a_2,\ldots,a_n)=\sum_{\pi=\{P_1,P_2,\ldots,P_k\}\in\Pi_{[n]}}f_k(b_{P_1},b_{P_2},\ldots,b_{P_k}). h n ( a 1 , a 2 , … , a n ) = π = { P 1 , P 2 , … , P k } ∈ Π [ n ] ∑ f k ( b P 1 , b P 2 , … , b P k ) . This is precisely Theorem 0.11 for our n n n Theorem 0.11 .
The composition of n n n
Proof of Theorem 0.4 . Let h : = f ∘ g : A → C h:=f\circ g:A\to C h := f ∘ g : A → C h h h n m nm nm h h h h n m + 1 = 0 h_{nm+1}=0 h nm + 1 = 0
Since g g g h h h a , a ′ ∈ A a,a'\in A a , a ′ ∈ A
h ( a a ′ ) = f ( g ( a a ′ ) ) (since h = f ∘ g ) = f ( g ( a ′ a ) ) (since g is central, so g ( a a ′ ) = g ( a ′ a ) ) = h ( a ′ a ) (since h = f ∘ g ), \begin{aligned}
h(aa')&=f\left(g(aa')\right) &&\text{(since }h=f\circ g\text{)}\\
&=f\left(g(a'a)\right) &&\text{(since }g\text{ is central, so }g(aa')=g(a'a)\text{)}\\
&=h(a'a) &&\text{(since }h=f\circ g\text{),}
\end{aligned} h ( a a ′ ) = f ( g ( a a ′ ) ) = f ( g ( a ′ a ) ) = h ( a ′ a ) (since h = f ∘ g ) (since g is central, so g ( a a ′ ) = g ( a ′ a ) ) (since h = f ∘ g ), which shows that h h h h n m + 1 = 0 h_{nm+1}=0 h nm + 1 = 0
Set N : = n m + 1 N:=nm+1 N := nm + 1 a 1 , a 2 , … , a N ∈ A a_1,a_2,\ldots,a_N\in A a 1 , a 2 , … , a N ∈ A h N ( a 1 , a 2 , … , a N ) = 0 h_N(a_1,a_2,\ldots,a_N)=0 h N ( a 1 , a 2 , … , a N ) = 0
For any subset P = { p 1 , p 2 , … , p r } P=\{p_1,p_2,\ldots,p_r\} P = { p 1 , p 2 , … , p r } [ N ] [N] [ N ] p 1 , p 2 , … , p r p_1,p_2,\ldots,p_r p 1 , p 2 , … , p r
b P : = g r ( a p 1 , a p 2 , … , a p r ) . b_P:=g_r(a_{p_1},a_{p_2},\ldots,a_{p_r}). b P := g r ( a p 1 , a p 2 , … , a p r ) . (This is well-defined for the same reason as in Theorem 0.11 .) Then, Theorem 0.11 (applied to N N N n n n
h N ( a 1 , a 2 , … , a N ) = ∑ π = { P 1 , P 2 , … , P k } ∈ Π [ N ] f k ( b P 1 , b P 2 , … , b P k ) . (43) h_N(a_1,a_2,\ldots,a_N)=\sum_{\pi=\{P_1,P_2,\ldots,P_k\}\in\Pi_{[N]}}f_k(b_{P_1},b_{P_2},\ldots,b_{P_k}). \tag*{(43)} h N ( a 1 , a 2 , … , a N ) = π = { P 1 , P 2 , … , P k } ∈ Π [ N ] ∑ f k ( b P 1 , b P 2 , … , b P k ) . (43) (where f k ( b P 1 , b P 2 , … , b P k ) f_k(b_{P_1},b_{P_2},\ldots,b_{P_k}) f k ( b P 1 , b P 2 , … , b P k ) Theorem 0.11 ).
However, we claim that any partition π = { P 1 , P 2 , … , P k } ∈ Π [ N ] \pi=\{P_1,P_2,\ldots,P_k\}\in\Pi_{[N]} π = { P 1 , P 2 , … , P k } ∈ Π [ N ]
f k ( b P 1 , b P 2 , … , b P k ) = 0. (44) f_k(b_{P_1},b_{P_2},\ldots,b_{P_k})=0. \tag*{(44)} f k ( b P 1 , b P 2 , … , b P k ) = 0. (44) [Proof: Let π = { P 1 , P 2 , … , P k } ∈ Π [ N ] \pi= \{P_1, P_2, \ldots, P_k\} \in\Pi_{[N]} π = { P 1 , P 2 , … , P k } ∈ Π [ N ] f f f n n n f n + 1 = 0 f_{n+1} = 0 f n + 1 = 0 k ≥ n + 1 k \ge n+1 k ≥ n + 1 f k = 0 f_k = 0 f k = 0 Lemma 0.9 , applied to B B B C C C n + 1 n+1 n + 1 k k k A A A B B B m m m n n n (44) certainly holds in this case. Hence, for the rest of this proof of (44) , we WLOG assume that k < n + 1 k < n+1 k < n + 1 k ≤ n k \le n k ≤ n n ≥ k n \ge k n ≥ k { P 1 , P 2 , … , P k } \{P_1, P_2, \ldots, P_k\} { P 1 , P 2 , … , P k } [ N ] [N] [ N ]
∣ P 1 ∣ + ∣ P 2 ∣ + ⋯ + ∣ P k ∣ = ∣ [ N ] ∣ = N = n m + 1 > n ⏟ ≥ k m ≥ k m . |P_1| + |P_2| + \cdots+ |P_k| = |[N]| = N = nm + 1 > \underbrace{n}_{\ge k}m \ge km. ∣ P 1 ∣ + ∣ P 2 ∣ + ⋯ + ∣ P k ∣ = ∣ [ N ] ∣ = N = nm + 1 > ≥ k n m ≥ k m . Hence, at least one of the k k k ∣ P 1 ∣ , ∣ P 2 ∣ , … , ∣ P k ∣ |P_1|, |P_2|, \ldots, |P_k| ∣ P 1 ∣ , ∣ P 2 ∣ , … , ∣ P k ∣ m m m ∣ P 1 ∣ ≤ m |P_1| \le m ∣ P 1 ∣ ≤ m ∣ P 2 ∣ ≤ m |P_2| \le m ∣ P 2 ∣ ≤ m … \ldots … ∣ P k ∣ ≤ m |P_k| \le m ∣ P k ∣ ≤ m k k k ∣ P 1 ∣ + ∣ P 2 ∣ + ⋯ + ∣ P k ∣ ≤ m + m + ⋯ + m ⏟ k t i m e s = k m |P_1| + |P_2| + \cdots+ |P_k| \le\underbrace{m + m + \cdots+ m}_{k\ \mathrm{times}} = km ∣ P 1 ∣ + ∣ P 2 ∣ + ⋯ + ∣ P k ∣ ≤ k times m + m + ⋯ + m = k m ∣ P 1 ∣ + ∣ P 2 ∣ + ⋯ + ∣ P k ∣ > k m |P_1| + |P_2| + \cdots+ |P_k| > km ∣ P 1 ∣ + ∣ P 2 ∣ + ⋯ + ∣ P k ∣ > k m j ∈ [ k ] j \in[k] j ∈ [ k ] ∣ P j ∣ > m |P_j| > m ∣ P j ∣ > m j j j g g g m m m g m + 1 = 0 g_{m+1} = 0 g m + 1 = 0 P j P_j P j P j = { p 1 , p 2 , … , p r } P_j = \{p_1, p_2, \ldots, p_r\} P j = { p 1 , p 2 , … , p r } p 1 , p 2 , … , p r p_1, p_2, \ldots, p_r p 1 , p 2 , … , p r r = ∣ P j ∣ > m r = |P_j| > m r = ∣ P j ∣ > m r ≥ m + 1 r \ge m+1 r ≥ m + 1 g m + 1 = 0 g_{m+1} = 0 g m + 1 = 0 g r = 0 g_r = 0 g r = 0 Lemma 0.9 , applied to g g g m + 1 m+1 m + 1 r r r f f f m m m n n n b P j b_{P_j} b P j b P j = g r ( a p 1 , a p 2 , … , a p r ) = 0 b_{P_j} = g_r(a_{p_1}, a_{p_2}, \ldots, a_{p_r}) = 0 b P j = g r ( a p 1 , a p 2 , … , a p r ) = 0 g r = 0 g_r = 0 g r = 0 f k ( b P 1 , b P 2 , … , b P k ) = 0 f_k(b_{P_1}, b_{P_2}, \ldots, b_{P_k}) = 0 f k ( b P 1 , b P 2 , … , b P k ) = 0 f k f_k f k Z \mathbb{Z} Z k k k 0 0 0
Now, substituting (44) into (43) , we find
h N ( a 1 , a 2 , … , a N ) = ∑ π = { P 1 , P 2 , … , P k } ∈ Π [ N ] 0 = 0. h_N(a_1,a_2,\ldots,a_N) = \sum_{\pi=\{P_1,P_2,\ldots,P_k\}\in\Pi_{[N]}} 0 = 0. h N ( a 1 , a 2 , … , a N ) = π = { P 1 , P 2 , … , P k } ∈ Π [ N ] ∑ 0 = 0. Since we have proved this for all a 1 , a 2 , … , a N ∈ A a_1, a_2, \ldots, a_N \in A a 1 , a 2 , … , a N ∈ A h N = 0 h_N = 0 h N = 0 h n m + 1 = 0 h_{nm+1} = 0 h nm + 1 = 0 N = n m + 1 N = nm + 1 N = nm + 1
