Introduction
Double posets and E E E E E E [19 ] ; their goal was to construct a combinatorial Hopf algebra which harbors a noticeable amount of structure, including an analogue of the Littlewood-Richardson rule and a lift of the internal product operation of the Malvenuto-Reutenauer Hopf algebra of permutations. In this note, we shall employ these same notions to restate in a simpler form, and reprove in a more elementary fashion, a formula for the antipode in the Hopf algebra QSym of quasisymmetric functions due to (the same) Malvenuto and Reutenauer [18 Theorem 3.1] . We then further generalize this formula to a setting in which a group acts on the double poset (a generalization inspired by Katharina Jochemko’s [15 ] .
In the present version of the paper, some (classical and/or straightforward) proofs are missing or sketched. A more detailed version exists, in which at least a few of these proofs are elaborated on more1
A short summary of this paper has been submitted to the FPSAC conference [12 ] .
Acknowledgments
Katharina Jochemko’s work [15 ] provoked this research. I learnt a lot about QSym from Victor Reiner. The SageMath computer algebra system [23 ] was used for some computations that suggested one of the proofs.
Note on the published version of this paper
The document you are reading is the preprint of a paper (of the same title) that was published in the Electronic Journal of Combinatorics in 2017 (Volume 24, Issue 2, doi:10.37236/6660). The published version differs from this preprint insubstantially2
Quasisymmetric functions
Let us first briefly introduce the notations that will be used in the following.
We set N = { 0 , 1 , 2 , … } \mathbb{N} = \{0,1,2,\ldots\} N = { 0 , 1 , 2 , … } composition means a finite sequence of positive integers. We let Comp be the set of all compositions. For n ∈ N n \in\mathbb{N} n ∈ N composition of n n n n n n ( α 1 , α 2 , … , α k ) (\alpha_1,\alpha_2,\ldots,\alpha_k) ( α 1 , α 2 , … , α k ) α 1 + α 2 + ⋯ + α k = n \alpha_1+\alpha_2+\cdots+\alpha_k=n α 1 + α 2 + ⋯ + α k = n
Let k \mathbf{k} k k \mathbf{k} k k \mathbf{k} k k [ [ x 1 , x 2 , x 3 , … ] ] \mathbf{k}[[x_1,x_2,x_3,\ldots]] k [[ x 1 , x 2 , x 3 , … ]] x 1 , x 2 , x 3 , … x_1,x_2,x_3,\ldots x 1 , x 2 , x 3 , … k \mathbf{k} k monomial shall always mean a monomial (without coefficients) in the variables x 1 , x 2 , x 3 , … x_1,x_2,x_3,\ldots x 1 , x 2 , x 3 , … 3
We consider the k \mathbf{k} k k [ [ x 1 , x 2 , x 3 , … ] ] \mathbf{k}[\![x_1,x_2,x_3,\ldots]\!] k [ [ x 1 , x 2 , x 3 , … ] ] x 1 , x 2 , x 3 , … x_1,x_2,x_3,\ldots x 1 , x 2 , x 3 , … k \mathbf{k} k x 1 a 1 x 2 a 2 x 3 a 3 ⋯ ∈ Mon x_1^{a_1}x_2^{a_2}x_3^{a_3}\cdots\in\operatorname{Mon} x 1 a 1 x 2 a 2 x 3 a 3 ⋯ ∈ Mon x 1 a 1 ⋅ x 2 a 2 ⋅ x 3 a 3 ⋯ x_1^{a_1}\cdot x_2^{a_2}\cdot x_3^{a_3}\cdots x 1 a 1 ⋅ x 2 a 2 ⋅ x 3 a 3 ⋯ k [ [ x 1 , x 2 , x 3 , … ] ] \mathbf{k}[\![x_1,x_2,x_3,\ldots]\!] k [ [ x 1 , x 2 , x 3 , … ] ] k \mathbf{k} k Mon \operatorname{Mon} Mon k [ [ x 1 , x 2 , x 3 , … ] ] \mathbf{k}[\![x_1,x_2,x_3,\ldots]\!] k [ [ x 1 , x 2 , x 3 , … ] ] k \mathbf{k} k k [ [ x 1 , x 2 , x 3 , … ] ] \mathbf{k}[\![x_1,x_2,x_3,\ldots]\!] k [ [ x 1 , x 2 , x 3 , … ] ]
We furthermore endow the ring k [ [ x 1 , x 2 , x 3 , … ] ] \mathbf{k}[\![x_1,x_2,x_3,\ldots]\!] k [ [ x 1 , x 2 , x 3 , … ] ] [13 Proof of Corollary 2.6.11] ):
We endow the ring k \mathbf{k} k k \mathbf{k} k k [ [ x 1 , x 2 , x 3 , … ] ] \mathbf{k}[\![x_1,x_2,x_3,\ldots]\!] k [ [ x 1 , x 2 , x 3 , … ] ] k [ [ x 1 , x 2 , x 3 , … ] ] \mathbf{k}[\![x_1,x_2,x_3,\ldots]\!] k [ [ x 1 , x 2 , x 3 , … ] ] Mon \operatorname{Mon} Mon k \mathbf{k} k
∏ m ∈ Mon k ⟶ k [ [ x 1 , x 2 , x 3 , … ] ] , ( λ m ) m ∈ Mon ⟼ ∑ m ∈ Mon λ m m . \prod_{m\in\operatorname{Mon}}\mathbf{k}\longrightarrow\mathbf{k}[\![x_1,x_2,x_3,\ldots]\!],\qquad(\lambda_m)_{m\in\operatorname{Mon}}\longmapsto\sum_{m\in\operatorname{Mon}}\lambda_m m. m ∈ Mon ∏ k ⟶ k [ [ x 1 , x 2 , x 3 , … ] ] , ( λ m ) m ∈ Mon ⟼ m ∈ Mon ∑ λ m m . We use this isomorphism to transport the product topology on ∏ m ∈ Mon k \prod_{m\in\operatorname{Mon}}\mathbf{k} ∏ m ∈ Mon k k [ [ x 1 , x 2 , x 3 , … ] ] \mathbf{k}[\![x_1,x_2,x_3,\ldots]\!] k [ [ x 1 , x 2 , x 3 , … ] ]
The resulting topology on k [ [ x 1 , x 2 , x 3 , … ] ] \mathbf{k}[\![x_1,x_2,x_3,\ldots]\!] k [ [ x 1 , x 2 , x 3 , … ] ] k [ [ x 1 , x 2 , x 3 , … ] ] \mathbf{k}[\![x_1,x_2,x_3,\ldots]\!] k [ [ x 1 , x 2 , x 3 , … ] ] k \mathbf{k} k k [ [ x 1 , x 2 , x 3 , … ] ] \mathbf{k}[\![x_1,x_2,x_3,\ldots]\!] k [ [ x 1 , x 2 , x 3 , … ] ] ( a n ) n ∈ N (a_n)_{n\in\mathbb{N}} ( a n ) n ∈ N a a a m m m n ∈ N n\in\mathbb{N} n ∈ N
(the coefficient of m in a n ) = (the coefficient of m in a ) . \text{(the coefficient of $m$ in $a_n$)}=\text{(the coefficient of $m$ in $a$)}. (the coefficient of m in a n ) = (the coefficient of m in a ) . Note that this topological k \mathbf{k} k k [ [ x 1 , x 2 , x 3 , … ] ] \mathbf{k}[\![x_1,x_2,x_3,\ldots]\!] k [ [ x 1 , x 2 , x 3 , … ] ] k [ x 1 , x 2 , x 3 , … ] \mathbf{k}[x_1,x_2,x_3,\ldots] k [ x 1 , x 2 , x 3 , … ] x i x_i x i 1 1 1
Inside the k \mathbf{k} k k [ [ x 1 , x 2 , x 3 , … ] ] \mathbf{k}[\![x_1,x_2,x_3,\ldots]\!] k [ [ x 1 , x 2 , x 3 , … ] ] k [ [ x 1 , x 2 , x 3 , … ] ] b d d \mathbf{k}[\![x_1,x_2,x_3,\ldots]\!]_{\mathrm{bdd}} k [ [ x 1 , x 2 , x 3 , … ] ] bdd bounded-degree formal power series; these are the power series f f f d ∈ N d\in\mathbb{N} d ∈ N > d >d > d f f f 4 k \mathbf{k} k k [ [ x 1 , x 2 , x 3 , … ] ] b d d \mathbf{k}[\![x_1,x_2,x_3,\ldots]\!]_{\mathrm{bdd}} k [ [ x 1 , x 2 , x 3 , … ] ] bdd k \mathbf{k} k k [ [ x 1 , x 2 , x 3 , … ] ] \mathbf{k}[\![x_1,x_2,x_3,\ldots]\!] k [ [ x 1 , x 2 , x 3 , … ] ]
Two monomials m m m n n n pack-equivalent 5 x i 1 a 1 x i 2 a 2 ⋯ x i ℓ a ℓ x_{i_1}^{a_1}x_{i_2}^{a_2}\cdots x_{i_\ell}^{a_\ell} x i 1 a 1 x i 2 a 2 ⋯ x i ℓ a ℓ x j 1 a 1 x j 2 a 2 ⋯ x j ℓ a ℓ x_{j_1}^{a_1}x_{j_2}^{a_2}\cdots x_{j_\ell}^{a_\ell} x j 1 a 1 x j 2 a 2 ⋯ x j ℓ a ℓ ( i 1 < i 2 < ⋯ < i ℓ ) (i_1<i_2<\cdots<i_\ell) ( i 1 < i 2 < ⋯ < i ℓ ) ( j 1 < j 2 < ⋯ < j ℓ ) (j_1<j_2<\cdots<j_\ell) ( j 1 < j 2 < ⋯ < j ℓ ) ( a 1 , a 2 , … , a ℓ ) (a_1,a_2,\ldots,a_\ell) ( a 1 , a 2 , … , a ℓ ) 6 f ∈ k [ [ x 1 , x 2 , x 3 , … ] ] f\in\mathbb{k}[[x_1,x_2,x_3,\ldots]] f ∈ k [[ x 1 , x 2 , x 3 , … ]] quasisymmetric if it satisfies the following condition: If m m m n n n m m m f f f n n n f f f
It is easy to see that the quasisymmetric power series form a k \mathbb{k} k k [ [ x 1 , x 2 , x 3 , … ] ] \mathbb{k}[[x_1,x_2,x_3,\ldots]] k [[ x 1 , x 2 , x 3 , … ]] k \mathbb{k} k k [ [ x 1 , x 2 , x 3 , … ] ] \mathbb{k}[[x_1,x_2,x_3,\ldots]] k [[ x 1 , x 2 , x 3 , … ]] k \mathbb{k} k k [ [ x 1 , x 2 , x 3 , … ] ] b d d \mathbb{k}[[x_1,x_2,x_3,\ldots]]_{\mathrm{bdd}} k [[ x 1 , x 2 , x 3 , … ] ] bdd k \mathbb{k} k quasisymmetric functions over k \mathbb{k} k
The symmetric functions (in the usual sense of this word in combinatorics – so, really, symmetric bounded-degree power series in k [ [ x 1 , x 2 , x 3 , … ] ] \mathbb{k}[[x_1,x_2,x_3,\ldots]] k [[ x 1 , x 2 , x 3 , … ]] k \mathbb{k} k [25 §§7.19, 7.23] and [13 §§5-6] and other sources.7
As a k \mathbb{k} k ( M α ) α ∈ Comp (M_\alpha)_{\alpha\in\operatorname{Comp}} ( M α ) α ∈ Comp M α M_\alpha M α α \alpha α α \alpha α ( α 1 , α 2 , … , α ℓ ) (\alpha_1,\alpha_2,\ldots,\alpha_\ell) ( α 1 , α 2 , … , α ℓ )
M α = ∑ i 1 < i 2 < ⋯ < i ℓ x i 1 α 1 x i 2 α 2 ⋯ x i ℓ α ℓ = ∑ m is a monomial pack-equivalent to x 1 α 1 x 2 α 2 ⋯ x ℓ α ℓ m M_\alpha=\sum_{i_1<i_2<\cdots<i_\ell}x_{i_1}^{\alpha_1}x_{i_2}^{\alpha_2}\cdots x_{i_\ell}^{\alpha_\ell}
=\sum_{\substack{m\text{ is a monomial pack-equivalent}\\\text{to }x_1^{\alpha_1}x_2^{\alpha_2}\cdots x_\ell^{\alpha_\ell}}}m M α = i 1 < i 2 < ⋯ < i ℓ ∑ x i 1 α 1 x i 2 α 2 ⋯ x i ℓ α ℓ = m is a monomial pack-equivalent to x 1 α 1 x 2 α 2 ⋯ x ℓ α ℓ ∑ m (where the i k i_k i k ( M α ) α ∈ Comp (M_\alpha)_{\alpha\in\operatorname{Comp}} ( M α ) α ∈ Comp monomial basis of QSym, and is the simplest to define among many. (We shall briefly encounter another basis in Example 3.6.)
The k \mathbb{k} k k \mathbb{k} k k \mathbb{k} k [21 ] , [13 §1] , [20 §1-§2] , [Abe77], [28 ] , [4 ] or [7 Chapter 7] ) and for a deeper study of the Hopf algebra QSym (see [16 ] , [14 Chapter 6] or [13 §5] ); in this note we shall need but the very basics of this structure, and so it is only them that we introduce.
In the following, all tensor products are over k \mathbb{k} k ⊗ \otimes ⊗ ⊗ k \otimes_{\mathbb{k}} ⊗ k
Now, we define two k \mathbb{k} k Δ \Delta Δ ε \varepsilon ε 8
Δ ( M ( α 1 , α 2 , … , α ℓ ) ) = ∑ k = 0 ℓ M ( α 1 , α 2 , … , α k ) ⊗ M ( α k + 1 , α k + 2 , … , α ℓ ) (1) \Delta\left(M_{(\alpha_1,\alpha_2,\ldots,\alpha_\ell)}\right)=\sum_{k=0}^{\ell}M_{(\alpha_1,\alpha_2,\ldots,\alpha_k)}\otimes M_{(\alpha_{k+1},\alpha_{k+2},\ldots,\alpha_\ell)} \tag*{(1)} Δ ( M ( α 1 , α 2 , … , α ℓ ) ) = k = 0 ∑ ℓ M ( α 1 , α 2 , … , α k ) ⊗ M ( α k + 1 , α k + 2 , … , α ℓ ) (1) for every ( α 1 , α 2 , … , α ℓ ) ∈ C o m p (\alpha_1,\alpha_2,\ldots,\alpha_\ell)\in\mathrm{Comp} ( α 1 , α 2 , … , α ℓ ) ∈ Comp
ε ( M ( α 1 , α 2 , … , α ℓ ) ) = δ ℓ , 0 \varepsilon\left(M_{(\alpha_1,\alpha_2,\ldots,\alpha_\ell)}\right)=\delta_{\ell,0} ε ( M ( α 1 , α 2 , … , α ℓ ) ) = δ ℓ , 0 for every ( α 1 , α 2 , … , α ℓ ) ∈ C o m p (\alpha_1,\alpha_2,\ldots,\alpha_\ell)\in\mathrm{Comp} ( α 1 , α 2 , … , α ℓ ) ∈ Comp
(Here, δ u , v \delta_{u,v} δ u , v { 1 , if u = v ; 0 , if u ≠ v \begin{cases}1,&\text{if }u=v;\\0,&\text{if }u\ne v\end{cases} { 1 , 0 , if u = v ; if u = v u u u v v v
The map ε \varepsilon ε ε \varepsilon ε f ∈ Q S y m f\in\mathrm{QSym} f ∈ QSym f ( 0 , 0 , 0 , … ) f(0,0,0,\ldots) f ( 0 , 0 , 0 , … ) x 1 , x 2 , x 3 , … x_1,x_2,x_3,\ldots x 1 , x 2 , x 3 , … f f f Δ \Delta Δ 9
It is well-known that these maps Δ \Delta Δ ε \varepsilon ε
Q S y m → Δ Q S y m ⊗ Q S y m ↓ Δ ↓ Δ ⊗ i d Q S y m ⊗ Q S y m → i d ⊗ Δ Q S y m ⊗ Q S y m ⊗ Q S y m Q S y m → Δ Q S y m ⊗ Q S y m ↘ ≅ ↓ ε ⊗ i d k ⊗ Q S y m Q S y m → Δ Q S y m ⊗ Q S y m ↘ ≅ ↓ i d ⊗ ε Q S y m ⊗ k \begin{array}{c c c}
\mathrm{QSym} & \xrightarrow{\Delta} & \mathrm{QSym}\otimes\mathrm{QSym}\\
\downarrow{\Delta} & & \downarrow{\Delta\otimes\mathrm{id}}\\
\mathrm{QSym}\otimes\mathrm{QSym} & \xrightarrow{\mathrm{id}\otimes\Delta} & \mathrm{QSym}\otimes\mathrm{QSym}\otimes\mathrm{QSym}
\end{array}
\qquad
\begin{array}{c c c}
\mathrm{QSym} & \xrightarrow{\Delta} & \mathrm{QSym}\otimes\mathrm{QSym}\\
\searrow_{\cong} & & \downarrow{\varepsilon\otimes\mathrm{id}}\\
& k\otimes\mathrm{QSym} &
\end{array}
\qquad
\begin{array}{c c c}
\mathrm{QSym} & \xrightarrow{\Delta} & \mathrm{QSym}\otimes\mathrm{QSym}\\
\searrow_{\cong} & & \downarrow{\mathrm{id}\otimes\varepsilon}\\
& \mathrm{QSym}\otimes k &
\end{array} QSym ↓ Δ QSym ⊗ QSym Δ id ⊗ Δ QSym ⊗ QSym ↓ Δ ⊗ id QSym ⊗ QSym ⊗ QSym QSym ↘ ≅ Δ k ⊗ QSym QSym ⊗ QSym ↓ ε ⊗ id QSym ↘ ≅ Δ QSym ⊗ k QSym ⊗ QSym ↓ id ⊗ ε (where the ≅ \cong ≅ ( Q S y m , Δ , ε ) (\mathrm{QSym},\Delta,\varepsilon) ( QSym , Δ , ε ) k k k Δ \Delta Δ ε \varepsilon ε k k k k k k Q S y m \mathrm{QSym} QSym k k k m : Q S y m ⊗ Q S y m → Q S y m m:\mathrm{QSym}\otimes\mathrm{QSym}\to\mathrm{QSym} m : QSym ⊗ QSym → QSym k k k a ⊗ b a\otimes b a ⊗ b a b ab ab u : k → Q S y m u:k\to\mathrm{QSym} u : k → QSym k k k 1 ∈ k 1\in k 1 ∈ k 1 ∈ Q S y m 1\in\mathrm{QSym} 1 ∈ QSym k k k S : Q S y m → Q S y m S:\mathrm{QSym}\to\mathrm{QSym} S : QSym → QSym
Q S y m ⊗ Q S y m → S ⊗ i d Q S y m ⊗ Q S y m Δ ↗ ↘ m Q S y m → ε k → u Q S y m Δ ↘ ↗ m Q S y m ⊗ Q S y m → i d ⊗ S Q S y m ⊗ Q S y m (2) \begin{array}{c c c}
& \mathrm{QSym}\otimes\mathrm{QSym} & \xrightarrow{S\otimes\mathrm{id}} \mathrm{QSym}\otimes\mathrm{QSym}\\
{}^{\Delta}\nearrow& & \searrow^{m}\\
\mathrm{QSym} & \xrightarrow{\varepsilon} k \xrightarrow{u} \mathrm{QSym}\\
{}_{\Delta}\searrow& & \nearrow_{m}\\
& \mathrm{QSym}\otimes\mathrm{QSym} & \xrightarrow{\mathrm{id}\otimes S} \mathrm{QSym}\otimes\mathrm{QSym} \tag*{(2)}
\end{array} Δ ↗ QSym Δ ↘ QSym ⊗ QSym ε k u QSym QSym ⊗ QSym S ⊗ id QSym ⊗ QSym ↘ m ↗ m id ⊗ S QSym ⊗ QSym (2) commutative. This map S S S antipode of QSym. It is known to be an involution and an algebra automorphism of QSym, and its action on the various quasisymmetric functions defined combinatorially is the main topic of this note. The existence of the antipode S S S Hopf algebra .
Double posets
Next, we shall introduce the notion of a double poset, following Malvenuto and Reutenauer [19 ] .
Definition 3.1. (a) We shall encode posets as pairs ( E , < ) (E, <) ( E , < ) E E E < < < E E E < < < a < b a < b a < b a a a b b b < < < a a a b b b < < < ( a , b ) (a,b) ( a , b ) < < <
(b) If < < < E E E a a a b b b E E E a a a b b b < < < a < b a < b a < b a = b a = b a = b b < a b < a b < a < < < E E E total order if and only if every two elements of E E E < < <
(c) If < < < E E E a a a b b b E E E a a a < < < b b b a < b a < b a < b c ∈ E c \in E c ∈ E a < c < b a < c < b a < c < b < < < Z \mathbb{Z} Z i ∈ Z i \in\mathbb{Z} i ∈ Z < < < i + 1 i + 1 i + 1
(d) A double poset is defined as a triple ( E , < 1 , < 2 ) (E, <_1, <_2) ( E , < 1 , < 2 ) E E E < 1 <_1 < 1 < 2 <_2 < 2 E E E
(e) A double poset ( E , < 1 , < 2 ) (E, <_1, <_2) ( E , < 1 , < 2 ) special if the relation < 2 <_2 < 2
(f) A double poset ( E , < 1 , < 2 ) (E, <_1, <_2) ( E , < 1 , < 2 ) semispecial if every two < 1 <_1 < 1 E E E < 2 <_2 < 2
(g) A double poset ( E , < 1 , < 2 ) (E, <_1, <_2) ( E , < 1 , < 2 ) tertispecial if it satisfies the following condition: If a a a b b b E E E a a a < 1 <_1 < 1 b b b a a a b b b < 2 <_2 < 2
(h) If < < < E E E opposite relation of < < < > > > E E E e ∈ E e \in E e ∈ E f ∈ E f \in E f ∈ E e > f e > f e > f f < e f < e f < e < < < > > > < < <
Clearly, every special double poset is semispecial, and every semispecial double poset is tertispecial.10
Definition 3.2. If E = ( E , < 1 , < 2 ) E=(E,<_{1},<_{2}) E = ( E , < 1 , < 2 ) E E E ϕ : E → { 1 , 2 , 3 , … } \phi:E\to\{1,2,3,\ldots\} ϕ : E → { 1 , 2 , 3 , … }
every e ∈ E e\in E e ∈ E f ∈ E f\in E f ∈ E e < 1 f e<_{1}f e < 1 f ϕ ( e ) ≤ ϕ ( f ) \phi(e)\leq\phi(f) ϕ ( e ) ≤ ϕ ( f )
every e ∈ E e\in E e ∈ E f ∈ E f\in E f ∈ E e < 1 f e<_{1}f e < 1 f f < 2 e f<_{2}e f < 2 e ϕ ( e ) < ϕ ( f ) \phi(e)<\phi(f) ϕ ( e ) < ϕ ( f )
Example 3.3. The notion of an E E E P P P ( P , ω ) (P,\omega) ( P , ω ) 11
If < 2 <_{2} < 2 < 1 <_{1} < 1 E E E ( E , < 1 ) (E,<_{1}) ( E , < 1 ) { 1 , 2 , 3 , … } \{1,2,3,\ldots\} { 1 , 2 , 3 , … }
If < 2 <_{2} < 2 < 1 <_{1} < 1 E E E ( E , < 1 ) (E,<_{1}) ( E , < 1 ) { 1 , 2 , 3 , … } \{1,2,3,\ldots\} { 1 , 2 , 3 , … }
For a more interesting example, let μ = ( μ 1 , μ 2 , μ 3 , … ) \mu=(\mu_{1},\mu_{2},\mu_{3},\ldots) μ = ( μ 1 , μ 2 , μ 3 , … ) λ = ( λ 1 , λ 2 , λ 3 , … ) \lambda=(\lambda_{1},\lambda_{2},\lambda_{3},\ldots) λ = ( λ 1 , λ 2 , λ 3 , … ) μ ⊆ λ \mu\subseteq\lambda μ ⊆ λ [13 §2] for the notations we are using here.) The skew Young diagram Y ( λ / μ ) Y(\lambda/\mu) Y ( λ / μ ) ( i , j ) ∈ { 1 , 2 , 3 , … } 2 (i,j)\in\{1,2,3,\ldots\}^{2} ( i , j ) ∈ { 1 , 2 , 3 , … } 2 μ i < j ≤ λ i \mu_{i}<j\leq\lambda_{i} μ i < j ≤ λ i Y ( λ / μ ) Y(\lambda/\mu) Y ( λ / μ ) < 1 <_{1} < 1 < 2 <_{2} < 2
( i , j ) < 1 ( i ′ , j ′ ) ⟺ ( i ≤ i ′ and j ≤ j ′ and ( i , j ) ≠ ( i ′ , j ′ ) ) (i,j)<_{1}(i',j')\Longleftrightarrow(i\leq i'\ \text{and}\ j\leq j'\ \text{and}\ (i,j)\ne(i',j')) ( i , j ) < 1 ( i ′ , j ′ ) ⟺ ( i ≤ i ′ and j ≤ j ′ and ( i , j ) = ( i ′ , j ′ )) and
( i , j ) < 2 ( i ′ , j ′ ) ⟺ ( i ≥ i ′ and j ≤ j ′ and ( i , j ) ≠ ( i ′ , j ′ ) ) . (i,j)<_{2}(i',j')\Longleftrightarrow(i\geq i'\ \text{and}\ j\leq j'\ \text{and}\ (i,j)\ne(i',j')). ( i , j ) < 2 ( i ′ , j ′ ) ⟺ ( i ≥ i ′ and j ≤ j ′ and ( i , j ) = ( i ′ , j ′ )) . The resulting double poset Y ( λ / μ ) = ( Y ( λ / μ ) , < 1 , < 2 ) \mathbf{Y}(\lambda/\mu)=(Y(\lambda/\mu),<_{1},<_{2}) Y ( λ / μ ) = ( Y ( λ / μ ) , < 1 , < 2 ) Y ( λ / μ ) \mathbf{Y}(\lambda/\mu) Y ( λ / μ ) λ / μ \lambda/\mu λ / μ [13 §2] for the meaning of these words.)
This double poset Y ( λ / μ ) \mathbf{Y}(\lambda/\mu) Y ( λ / μ ) a a a b b b Y ( λ / μ ) Y(\lambda/\mu) Y ( λ / μ ) a a a < 1 <_{1} < 1 b b b a a a b b b b b b
either a < 2 b a <_{2} b a < 2 b b < 2 a b <_{2} a b < 2 a < h <_{h} < h Y ( λ / μ ) \mathcal{Y}(\lambda/\mu) Y ( λ / μ )
( i , j ) < h ( i ′ , j ′ ) ⟺ ( i > i ′ or ( i = i ′ and j < j ′ ) ) . (i,j) <_{h} (i',j') \Longleftrightarrow(i > i' \text{ or } (i=i' \text{ and } j<j')). ( i , j ) < h ( i ′ , j ′ ) ⟺ ( i > i ′ or ( i = i ′ and j < j ′ )) . Then, Y h ( λ / μ ) = ( Y ( λ / μ ) , < 1 , < h ) \mathcal{Y}_{h}(\lambda/\mu)=(\mathcal{Y}(\lambda/\mu),<_{1},<_{h}) Y h ( λ / μ ) = ( Y ( λ / μ ) , < 1 , < h ) Y h ( λ / μ ) \mathcal{Y}_{h}(\lambda/\mu) Y h ( λ / μ ) λ / μ \lambda/\mu λ / μ
We now assign a certain formal power series to every double poset:
Definition 3.4. If E = ( E , < 1 , < 2 ) E=(E,<_{1},<_{2}) E = ( E , < 1 , < 2 ) w : E → { 1 , 2 , 3 , … } w:E\to\{1,2,3,\ldots\} w : E → { 1 , 2 , 3 , … } Γ ( E , w ) ∈ k [ [ x 1 , x 2 , x 3 , … ] ] \Gamma(E,w)\in\mathbb{k}[[x_{1},x_{2},x_{3},\ldots]] Γ ( E , w ) ∈ k [[ x 1 , x 2 , x 3 , … ]]
Γ ( E , w ) = ∑ π is an E -partition x π , w , where x π , w = ∏ e ∈ E x π ( e ) w ( e ) . \Gamma(E,w)=\sum_{\pi\text{ is an }E\text{-partition}}x_{\pi,w},\qquad\text{where }x_{\pi,w}=\prod_{e\in E}x_{\pi(e)}^{w(e)}. Γ ( E , w ) = π is an E -partition ∑ x π , w , where x π , w = e ∈ E ∏ x π ( e ) w ( e ) . The following fact is easy to see (but will be reproven below):
Proposition 3.5. Let E = ( E , < 1 , < 2 ) E=(E,<_{1},<_{2}) E = ( E , < 1 , < 2 ) w : E → { 1 , 2 , 3 , … } w:E\to\{1,2,3,\ldots\} w : E → { 1 , 2 , 3 , … } Γ ( E , w ) ∈ QSym \Gamma(E,w)\in\operatorname{QSym} Γ ( E , w ) ∈ QSym
Example 3.6. The power series Γ ( E , w ) \Gamma(E,w) Γ ( E , w )
(a) If E = ( E , < 1 , < 2 ) E=(E,<_{1},<_{2}) E = ( E , < 1 , < 2 ) w : E → { 1 , 2 , 3 , … } w:E\to\{1,2,3,\ldots\} w : E → { 1 , 2 , 3 , … } Γ ( E , w ) = ∑ π is an E -partition x π \Gamma(E,w)=\sum_{\pi\text{ is an }E\text{-partition}}x_{\pi} Γ ( E , w ) = ∑ π is an E -partition x π x π = ∏ e ∈ E x π ( e ) x_{\pi}=\prod_{e\in E}x_{\pi(e)} x π = ∏ e ∈ E x π ( e ) Γ ( E , w ) \Gamma(E,w) Γ ( E , w ) Γ ( E ) \Gamma(E) Γ ( E ) Γ ( E ) \Gamma(E) Γ ( E ) [19 §2.2] . All results proven below for Γ ( E , w ) \Gamma(E,w) Γ ( E , w ) Γ ( E ) \Gamma(E) Γ ( E )
(b) If E = { 1 , 2 , … , ℓ } E=\{1,2,\ldots,\ell\} E = { 1 , 2 , … , ℓ } ℓ ∈ N \ell\in\mathbb{N} ℓ ∈ N < 1 <_{1} < 1 Z \mathbb{Z} Z < 2 <_{2} < 2 < 1 <_{1} < 1 E = ( E , < 1 , < 2 ) E=(E,<_{1},<_{2}) E = ( E , < 1 , < 2 ) Γ ( E , w ) = M α \Gamma(E,w)=M_{\alpha} Γ ( E , w ) = M α α \alpha α ( w ( 1 ) , w ( 2 ) , … , w ( ℓ ) ) (w(1),w(2),\ldots,w(\ell)) ( w ( 1 ) , w ( 2 ) , … , w ( ℓ ))
Note that every M α M_{\alpha} M α ℓ \ell ℓ w w w ( M α ) α ∈ Comp (M_{\alpha})_{\alpha\in\operatorname{Comp}} ( M α ) α ∈ Comp Γ ( E , w ) \Gamma(E,w) Γ ( E , w ) Γ ( E , w ) \Gamma(E,w) Γ ( E , w ) E E E w w w k \mathbb{k} k QSym \operatorname{QSym} QSym
(c) Let α = ( α 1 , α 2 , … , α ℓ ) \alpha= (\alpha_1,\alpha_2,\ldots,\alpha_{\ell}) α = ( α 1 , α 2 , … , α ℓ ) n n n D ( α ) D(\alpha) D ( α ) { α 1 , α 1 + α 2 , α 1 + α 2 + α 3 , … , α 1 + α 2 + ⋯ + α ℓ − 1 } \{\alpha_1,\alpha_1+\alpha_2,\alpha_1+\alpha_2+\alpha_3,\ldots,\alpha_1+\alpha_2+\cdots+\alpha_{\ell-1}\} { α 1 , α 1 + α 2 , α 1 + α 2 + α 3 , … , α 1 + α 2 + ⋯ + α ℓ − 1 } E E E { 1 , 2 , … , n } \{1,2,\ldots,n\} { 1 , 2 , … , n } < 1 <_{1} < 1 E E E Z \mathbb{Z} Z < 2 <_{2} < 2 E E E
i + 1 < 2 i for every i ∈ D ( α ) i+1 <_{2} i \qquad\text{for every } i \in D(\alpha) i + 1 < 2 i for every i ∈ D ( α ) and
i < 2 i + 1 for every i ∈ { 1 , 2 , … , n − 1 } ∖ D ( α ) . i <_{2} i+1 \qquad\text{for every } i \in\{1,2,\ldots,n-1\}\setminus D(\alpha). i < 2 i + 1 for every i ∈ { 1 , 2 , … , n − 1 } ∖ D ( α ) . (There are several choices for such an order; in particular, we can find one which is a total order.) Then,
Γ ( ( E , < 1 , < 2 ) ) = ∑ i 1 ≤ i 2 ≤ ⋯ ≤ i n ; i j < i j + 1 whenever j ∈ D ( α ) x i 1 x i 2 ⋯ x i n = ∑ β is a composition of n ; D ( β ) ⊇ D ( α ) M β . \begin{aligned}
\Gamma((E,<_{1},<_{2})) = \sum_{\substack{i_1\leq i_2\leq\cdots\leq i_n;\\ i_j<i_{j+1}\text{ whenever }j\in D(\alpha)}} x_{i_1}x_{i_2}\cdots x_{i_n} \\
&= \sum_{\substack{\beta\text{ is a composition of }n;\\ D(\beta)\supseteq D(\alpha)}} M_{\beta}.
\end{aligned} Γ (( E , < 1 , < 2 )) = i 1 ≤ i 2 ≤ ⋯ ≤ i n ; i j < i j + 1 whenever j ∈ D ( α ) ∑ x i 1 x i 2 ⋯ x i n = β is a composition of n ; D ( β ) ⊇ D ( α ) ∑ M β . This power series is known as the α \alpha α fundamental quasisymmetric function , usually called F α F_{\alpha} F α [8 ] , [17 §2] , [3 §2.4] and [10 §2] ) or L α L_{\alpha} L α [25 §7.19] or [13 Definition 5.2.4] ).
(d) Let E E E Y ( λ / μ ) \mathbf{Y}(\lambda/\mu) Y ( λ / μ ) Y h ( λ / μ ) \mathbf{Y}_{h}(\lambda/\mu) Y h ( λ / μ ) Example 3.3 for two partitions μ \mu μ λ \lambda λ Γ ( E ) \Gamma(E) Γ ( E ) s λ / μ s_{\lambda/\mu} s λ / μ
(e) Similarly, dual immaculate functions as defined in [3 §3.7] can be realized as Γ ( E ) \Gamma(E) Γ ( E ) E E E [10 Proposition 4.4] ), which helped the author to prove one of their properties [10 ] . (The E E E immaculate tableaux .)
(f) When the relation < 2 <_{2} < 2 E = ( E , < 1 , < 2 ) E=(E,<_{1},<_{2}) E = ( E , < 1 , < 2 ) E E E E E E ( P , ω ) (P,\omega) ( P , ω ) P = ( E , < 1 ) P=(E,<_{1}) P = ( E , < 1 ) ω \omega ω E → { 1 , 2 , … , ∣ E ∣ } E\to\{1,2,\ldots,|E|\} E → { 1 , 2 , … , ∣ E ∣ } ω − 1 ( 1 ) < 2 ω − 1 ( 2 ) < 2 ⋯ < 2 ω − 1 ( ∣ E ∣ ) \omega^{-1}(1)<_{2}\omega^{-1}(2)<_{2}\cdots<_{2}\omega^{-1}(|E|) ω − 1 ( 1 ) < 2 ω − 1 ( 2 ) < 2 ⋯ < 2 ω − 1 ( ∣ E ∣ ) [25 §7.19] , and the power series Γ ( E ) \Gamma(E) Γ ( E ) K P , ω K_{P,\omega} K P , ω [25 §7.19] . This can also be rephrased using the notations of [13 §5.2] : When the relation < 2 <_{2} < 2 E = ( E , < 1 , < 2 ) E=(E,<_{1},<_{2}) E = ( E , < 1 , < 2 ) E E E 1 , 2 , … , n 1,2,\ldots,n 1 , 2 , … , n n = ∣ E ∣ n=|E| n = ∣ E ∣ 1 < 2 2 < 2 ⋯ < 2 n 1<_{2}2<_{2}\cdots<_{2}n 1 < 2 2 < 2 ⋯ < 2 n E E E P P P [13 Definition 5.2.1] , where P P P ( E , < 1 ) (E,<_{1}) ( E , < 1 ) Γ ( E ) \Gamma(E) Γ ( E ) F P ( x ) F_P(x) F P ( x ) [13 Definition 5.2.1] . Conversely, if P P P F P ( x ) F_P(x) F P ( x ) [13 Definition 5.2.1] is our Γ ( ( P , < P , < Z ) ) \Gamma((P,<_{P},<_{\mathbb{Z}})) Γ (( P , < P , < Z ))
The antipode theorem
We now come to the main results of this note. We first state a theorem and a corollary which are not new, but will be reproven in a more self-contained way which allows them to take their (well-deserved) place as fundamental results rather than afterthoughts in the theory of QSym.
Definition 4.1. We let S S S
Theorem 4.2. Let ( E , < 1 , < 2 ) (E,<_{1},<_{2}) ( E , < 1 , < 2 ) w : E → { 1 , 2 , 3 , … } w:E\to\{1,2,3,\ldots\} w : E → { 1 , 2 , 3 , … } S ( Γ ( ( E , < 1 , < 2 ) , w ) ) = ( − 1 ) ∣ E ∣ Γ ( ( E , > 1 , < 2 ) , w ) S\left(\Gamma((E,<_{1},<_{2}),w)\right)=(-1)^{|E|}\Gamma((E,>_{1},<_{2}),w) S ( Γ (( E , < 1 , < 2 ) , w ) ) = ( − 1 ) ∣ E ∣ Γ (( E , > 1 , < 2 ) , w ) > 1 >_{1} > 1 < 1 <_{1} < 1
Corollary 4.3. Let ( E , < 1 , < 2 ) (E,<_{1},<_{2}) ( E , < 1 , < 2 ) S ( Γ ( ( E , < 1 , < 2 ) ) ) = ( − 1 ) ∣ E ∣ Γ ( ( E , > 1 , < 2 ) ) S\left(\Gamma((E,<_{1},<_{2}))\right)=(-1)^{|E|}\Gamma((E,>_{1},<_{2})) S ( Γ (( E , < 1 , < 2 )) ) = ( − 1 ) ∣ E ∣ Γ (( E , > 1 , < 2 )) > 1 >_{1} > 1 < 1 <_{1} < 1
We shall give examples for consequences of these facts shortly (Example 4.8 ), but let us first explain where they have already appeared. Corollary 4.3 is equivalent to [13 Corollary 5.2.20] 12 [18 Lemma 3.2] ). Theorem 4.2 is equivalent to Malvenuto’s and Reutenauer’s [18 Theorem 3.1] 13
Let me sketch how to derive [18 Theorem 3.1] from our Theorem 4.2. Indeed, contract all undirected edges in G G G G ′ G' G ′ E E E < 1 <_{1} < 1 < 2 <_{2} < 2 E E E
( a < 1 b ) ⟺ ( a ≠ b , and there exists a path from a to b in G ) (a<_{1}b)\Longleftrightarrow(a\ne b,\text{ and there exists a path from }a\text{ to }b\text{ in }G) ( a < 1 b ) ⟺ ( a = b , and there exists a path from a to b in G ) and
( a < 2 b ) ⟺ ( a ≠ b , and there exists a path from a to b in G ′ ) . (a<_{2}b)\Longleftrightarrow(a\ne b,\text{ and there exists a path from }a\text{ to }b\text{ in }G'). ( a < 2 b ) ⟺ ( a = b , and there exists a path from a to b in G ′ ) . The map w w w e ∈ E e\in E e ∈ E G G G e e e ( E , < 1 , < 2 ) (E,<_{1},<_{2}) ( E , < 1 , < 2 ) a a a < 1 <_{1} < 1 b b b G G G a a a b b b x i x_i x i X X X [18 Section 3] ) are in 1-to-1 correspondence with ( E , < 1 , < 2 ) (E,<_{1},<_{2}) ( E , < 1 , < 2 ) X = { 1 , 2 , 3 , … } X=\{1,2,3,\ldots\} X = { 1 , 2 , 3 , … } 14
To these known results, we add another, which seems to be unknown so far (probably because it is far harder to state in the terminologies of ( P , ω ) (P,\omega) ( P , ω )
Definition 4.4. Let G G G E E E G G G
(a) Let < < < E E E G G G preserves the relation < < < g ∈ G g \in G g ∈ G a ∈ E a \in E a ∈ E b ∈ E b \in E b ∈ E a < b a < b a < b g a < g b ga < gb g a < g b
(b) Let w : E → { 1 , 2 , 3 , … } w:E\to\{1,2,3,\ldots\} w : E → { 1 , 2 , 3 , … } G G G preserves w w w if every g ∈ G g \in G g ∈ G e ∈ E e \in E e ∈ E w ( g e ) = w ( e ) w(ge)=w(e) w ( g e ) = w ( e )
(c) Let g ∈ G g \in G g ∈ G E E E g g g E E E g g g E E E E E E e ∈ E e \in E e ∈ E g e ge g e E E E
(d) If X X X X E X^E X E E → X E \to X E → X G G G π ∈ X E \pi\in X^E π ∈ X E g ∈ G g \in G g ∈ G g π ∈ X E g\pi\in X^E g π ∈ X E e ∈ E e \in E e ∈ E π ( g − 1 e ) \pi(g^{-1}e) π ( g − 1 e )
(e) Let F F F G G G E E E π ∈ F \pi\in F π ∈ F E E E g ∈ G g \in G g ∈ G g π = π g\pi=\pi g π = π E E E G G G O O O F F F E E E O O O E E E
Before we come to the promised result, let us state two simple facts:
Lemma 4.5. Let G G G F F F E E E G G G E E E O O O G G G F F F O O O E E E O O O E E E
Proposition 4.6. Let E = ( E , < 1 , < 2 ) E=(E,<_{1},<_{2}) E = ( E , < 1 , < 2 ) Par E \operatorname{Par} E Par E E E E G G G E E E G G G < 1 <_{1} < 1 < 2 <_{2} < 2
(a) Then, Par E \operatorname{Par} E Par E G G G G G G { 1 , 2 , 3 , … } E \{1,2,3,\ldots\}^{E} { 1 , 2 , 3 , … } E
G and G ′ G' G ′ [18 Theorem 3.1] follows from Theorem 4.2 above. With some harder work, one can conversely derive our Theorem 4.2 from [18 Theorem 3.1] . (b) Let w : E → { 1 , 2 , 3 , … } w:E\to\{1,2,3,\ldots\} w : E → { 1 , 2 , 3 , … } G G G w w w O O O G G G Par E \operatorname{Par} E Par E x π , w x_{\pi,w} x π , w π ∈ O \pi\in O π ∈ O
Theorem 4.7. Let E = ( E , < 1 , < 2 ) E=(E,<_{1},<_{2}) E = ( E , < 1 , < 2 ) Par E \operatorname{Par} E Par E E E E w : E → { 1 , 2 , 3 , … } w:E\to\{1,2,3,\ldots\} w : E → { 1 , 2 , 3 , … } G G G E E E G G G < 1 <_{1} < 1 < 2 <_{2} < 2 w w w G G G Par E \operatorname{Par} E Par E E E E Par E \operatorname{Par} E Par E G G G G G G { 1 , 2 , 3 , … } E \{1,2,3,\ldots\}^{E} { 1 , 2 , 3 , … } E Proposition 4.6 (a)). For any G G G O O O Par E \operatorname{Par} E Par E x O , w x_{O,w} x O , w
x O , w = x π , w for some element π of O . x_{O,w}=x_{\pi,w}\qquad\text{for some element }\pi\text{ of }O. x O , w = x π , w for some element π of O . (This is well-defined, since Proposition 4.6 (b) shows that x π , w x_{\pi,w} x π , w
Let
Γ ( E , w , G ) = ∑ O is a G -orbit on Par E x O , w \Gamma(E,w,G)=\sum_{\substack{O\text{ is a }G\text{-orbit on }\operatorname{Par} E}}x_{O,w} Γ ( E , w , G ) = O is a G -orbit on Par E ∑ x O , w and
Γ + ( E , w , G ) = ∑ O is an E -coeven G -orbit on Par E x O , w . \Gamma^{+}(E,w,G)=\sum_{\substack{O\text{ is an }E\text{-coeven }G\text{-orbit on }\operatorname{Par} E}}x_{O,w}. Γ + ( E , w , G ) = O is an E -coeven G -orbit on Par E ∑ x O , w . Then, Γ ( E , w , G ) \Gamma(E,w,G) Γ ( E , w , G ) Γ + ( E , w , G ) \Gamma^{+}(E,w,G) Γ + ( E , w , G ) QSym \operatorname{QSym} QSym
S ( Γ ( E , w , G ) ) = ( − 1 ) ∣ E ∣ Γ + ( ( E , > 1 , < 2 ) , w , G ) . S\bigl(\Gamma(E,w,G)\bigr)=(-1)^{|E|}\Gamma^{+}\bigl((E,>_{1},<_{2}),w,G\bigr). S ( Γ ( E , w , G ) ) = ( − 1 ) ∣ E ∣ Γ + ( ( E , > 1 , < 2 ) , w , G ) . Here, > 1 >_{1} > 1 < 1 <_{1} < 1
This theorem, which combines Theorem 4.2 with the ideas of Pólya enumeration, is inspired by Jochemko’s reciprocity result for order polynomials [15 Theorem 2.8] , which can be obtained from it by specializations (see § 10 for the details of how Jochemko’s result follows from ours).
We shall now briefly review a number of particular cases of Theorem 4.2 .
Example 4.8. (a) Corollary 4.3 follows from Theorem 4.2 by letting w w w
(b) Let α = ( α 1 , α 2 , … , α ℓ ) \alpha=(\alpha_{1},\alpha_{2},\ldots,\alpha_{\ell}) α = ( α 1 , α 2 , … , α ℓ ) n n n E = ( E , < 1 , < 2 ) E=(E,<_{1},<_{2}) E = ( E , < 1 , < 2 ) Example 3.6 (b). Let w : { 1 , 2 , … , ℓ } → { 1 , 2 , 3 , … } w:\{1,2,\ldots,\ell\}\to\{1,2,3,\ldots\} w : { 1 , 2 , … , ℓ } → { 1 , 2 , 3 , … } i i i α i \alpha_{i} α i Example 3.6 (b) shows, we have Γ ( E , w ) = M α \Gamma(E,w)=M_{\alpha} Γ ( E , w ) = M α Theorem 4.2 to
these E E E w w w
S ( M α ) = ( − 1 ) ℓ Γ ( ( E , > 1 , < 2 ) , w ) = ( − 1 ) ℓ ∑ i 1 ≥ i 2 ≥ ⋯ ≥ i ℓ x i 1 α 1 x i 2 α 2 ⋯ x i ℓ α ℓ = ( − 1 ) ℓ ∑ i 1 ≤ i 2 ≤ ⋯ ≤ i ℓ x i 1 α ℓ x i 2 α ℓ − 1 ⋯ x i ℓ α 1 = ( − 1 ) ℓ ∑ γ is a composition of n ; D ( γ ) ⊆ D ( ( α ℓ , α ℓ − 1 , … , α 1 ) ) M γ . \begin{aligned}
S(M_\alpha)=(-1)^\ell\Gamma((E,>_1,< _2),w)=(-1)^\ell\sum_{i_1\ge i_2\ge\cdots\ge i_\ell}x_{i_1}^{\alpha_1}x_{i_2}^{\alpha_2}\cdots x_{i_\ell}^{\alpha_\ell} \\
&=(-1)^\ell\sum_{i_1\le i_2\le\cdots\le i_\ell}x_{i_1}^{\alpha_\ell}x_{i_2}^{\alpha_{\ell-1}}\cdots x_{i_\ell}^{\alpha_1}=(-1)^\ell\sum_{\substack{\gamma\text{ is a composition of }n;\\D(\gamma)\subseteq D((\alpha_\ell,\alpha_{\ell-1},\ldots,\alpha_1))}}M_\gamma.
\end{aligned} S ( M α ) = ( − 1 ) ℓ Γ (( E , > 1 , < 2 ) , w ) = ( − 1 ) ℓ i 1 ≥ i 2 ≥ ⋯ ≥ i ℓ ∑ x i 1 α 1 x i 2 α 2 ⋯ x i ℓ α ℓ = ( − 1 ) ℓ i 1 ≤ i 2 ≤ ⋯ ≤ i ℓ ∑ x i 1 α ℓ x i 2 α ℓ − 1 ⋯ x i ℓ α 1 = ( − 1 ) ℓ γ is a composition of n ; D ( γ ) ⊆ D (( α ℓ , α ℓ − 1 , … , α 1 )) ∑ M γ . This is the formula for S ( M α ) S(M_\alpha) S ( M α ) [5 Proposition 3.4] , in [16 (4.26)] , in [13 Theorem 5.1.11] , and in [2 Theorem 4.1] (originally due to Ehrenborg and to Malvenuto and Reutenauer).
(c) Applying Corollary 4.3 to the double poset of Example 3.6 (c) (where the relation < 2 <_2 < 2 [16 (4.27)] , [13 (5.2.7)] , [2 Theorem 5.1] ).
(d) Let us use the notations of Example 3.3. For any partition λ \lambda λ λ t \lambda^t λ t λ \lambda λ μ \mu μ λ \lambda λ μ ⊆ λ \mu\subseteq\lambda μ ⊆ λ > 1 >_1 > 1 > 2 >_2 > 2 < 1 <_1 < 1 < 2 <_2 < 2 τ : Y ( λ / μ ) → Y ( λ t / μ t ) \tau:Y(\lambda/\mu)\to Y(\lambda^t/\mu^t) τ : Y ( λ / μ ) → Y ( λ t / μ t ) ( i , j ) ∈ Y ( λ / μ ) (i,j)\in Y(\lambda/\mu) ( i , j ) ∈ Y ( λ / μ ) ( j , i ) (j,i) ( j , i ) ( Y ( λ / μ ) , > 1 , < 2 ) (Y(\lambda/\mu),>_1,< _2) ( Y ( λ / μ ) , > 1 , < 2 ) ( Y ( λ t / μ t ) , > 1 , > 2 ) (Y(\lambda^t/\mu^t),>_1,>_2) ( Y ( λ t / μ t ) , > 1 , > 2 ) ϕ \phi ϕ ϕ \phi ϕ ϕ − 1 \phi^{-1} ϕ − 1
Γ ( ( Y ( λ / μ ) , > 1 , < 2 ) ) = Γ ( ( Y ( λ t / μ t ) , > 1 , > 2 ) ) . (3) \Gamma((Y(\lambda/\mu),>_1,< _2))=\Gamma((Y(\lambda^t/\mu^t),>_1,>_2)). \tag*{(3)} Γ (( Y ( λ / μ ) , > 1 , < 2 )) = Γ (( Y ( λ t / μ t ) , > 1 , > 2 )) . (3) But applying Corollary 4.3 to the tertispecial double poset Y ( λ / μ ) Y(\lambda/\mu) Y ( λ / μ )
S ( Γ ( Y ( λ / μ ) ) ) = ( − 1 ) ∣ λ / μ ∣ Γ ( ( Y ( λ / μ ) , > 1 , < 2 ) ) = ( − 1 ) ∣ λ / μ ∣ Γ ( ( Y ( λ t / μ t ) , > 1 , > 2 ) ) (4) S(\Gamma(Y(\lambda/\mu)))=(-1)^{|\lambda/\mu|}\Gamma((Y(\lambda/\mu),>_1,< _2))
=(-1)^{|\lambda/\mu|}\Gamma((Y(\lambda^t/\mu^t),>_1,>_2)) \tag*{(4)} S ( Γ ( Y ( λ / μ ))) = ( − 1 ) ∣ λ / μ ∣ Γ (( Y ( λ / μ ) , > 1 , < 2 )) = ( − 1 ) ∣ λ / μ ∣ Γ (( Y ( λ t / μ t ) , > 1 , > 2 )) (4) (by (3) ). But from Example 3.6 (d), we know that Γ ( Y ( λ / μ ) ) = s λ / μ \Gamma(Y(\lambda/\mu))=s_{\lambda/\mu} Γ ( Y ( λ / μ )) = s λ / μ [13 Remark 2.2.5] shows that Γ ( ( Y ( λ / μ ) , > 1 , > 2 ) ) = s λ / μ \Gamma((Y(\lambda/\mu),>_1,>_2))=s_{\lambda/\mu} Γ (( Y ( λ / μ ) , > 1 , > 2 )) = s λ / μ λ t \lambda^t λ t μ t \mu^t μ t λ \lambda λ μ \mu μ Γ ( ( Y ( λ t / μ t ) , > 1 , > 2 ) ) = s λ t / μ t \Gamma((Y(\lambda^t/\mu^t),>_1,>_2))=s_{\lambda^t/\mu^t} Γ (( Y ( λ t / μ t ) , > 1 , > 2 )) = s λ t / μ t (4) rewrites as
S ( s λ / μ ) = ( − 1 ) ∣ λ / μ ∣ s λ t / μ t (5) S(s_{\lambda/\mu})=(-1)^{|\lambda/\mu|}s_{\lambda^t/\mu^t} \tag*{(5)} S ( s λ / μ ) = ( − 1 ) ∣ λ / μ ∣ s λ t / μ t (5) (since Γ ( Y ( λ / μ ) ) = s λ / μ \Gamma(Y(\lambda/\mu))=s_{\lambda/\mu} Γ ( Y ( λ / μ )) = s λ / μ Γ ( ( Y ( λ t / μ t ) , > 1 , > 2 ) ) = s λ t / μ t \Gamma((Y(\lambda^t/\mu^t),>_1,>_2))=s_{\lambda^t/\mu^t} Γ (( Y ( λ t / μ t ) , > 1 , > 2 )) = s λ t / μ t S S S
It is also possible (but more difficult) to derive (5) by using the double poset Y h ( λ / μ ) Y_{\mathrm{h}}(\lambda/\mu) Y h ( λ / μ ) Y ( λ / μ ) Y(\lambda/\mu) Y ( λ / μ ) [13 proof of Corollary 5.2.22] .)
(e) A result of Benedetti and Sagan [2 Theorem 8.2] on the antipodes of immaculate functions can be obtained from Corollary 4.3 using dualization.
Remark 4.9. Corollary 4.3 has a sort of converse. Namely, let us assume that k = Z \mathbf{k} = \mathbb{Z} k = Z ( E , < 1 , < 2 ) (E, <_1, <_2) ( E , < 1 , < 2 ) S ( Γ ( ( E , < 1 , < 2 ) ) ) = ( − 1 ) ∣ E ∣ Γ ( ( E , > 1 , < 2 ) ) S\left(\Gamma((E, <_1, <_2))\right) = (-1)^{\lvert E\rvert}\Gamma((E, >_1, <_2)) S ( Γ (( E , < 1 , < 2 )) ) = ( − 1 ) ∣ E ∣ Γ (( E , > 1 , < 2 )) ( E , < 1 , < 2 ) (E, <_1, <_2) ( E , < 1 , < 2 )
More precisely, the following holds: Define the length ℓ ( α ) \ell(\alpha) ℓ ( α ) α \alpha α α \alpha α size ∣ α ∣ \lvert\alpha\rvert ∣ α ∣ α \alpha α α \alpha α η : QSym → QSym \eta:\operatorname{QSym} \to\operatorname{QSym} η : QSym → QSym k \mathbf{k} k
η ( M α ) = { M α , if ℓ ( α ) ≥ ∣ α ∣ − 1 ; 0 , if ℓ ( α ) < ∣ α ∣ − 1 \eta(M_\alpha) =
\begin{cases}
M_\alpha, & \text{if } \ell(\alpha) \geq\lvert\alpha\rvert- 1; \\
0, & \text{if } \ell(\alpha) < \lvert\alpha\rvert- 1
\end{cases} η ( M α ) = { M α , 0 , if ℓ ( α ) ≥ ∣ α ∣ − 1 ; if ℓ ( α ) < ∣ α ∣ − 1 for every α ∈ Comp \alpha\in\operatorname{Comp} α ∈ Comp
Thus, η \eta η m m m m m m < deg m − 1 < \deg m - 1 < deg m − 1 k [ [ x 1 , x 2 , x 3 , … ] ] \mathbf{k}[[x_1,x_2,x_3,\ldots]] k [[ x 1 , x 2 , x 3 , … ]] a a a b b b a ≤ b a \leq b a ≤ b a a a ≤ \leq ≤ b b b ( E , < 1 , < 2 ) (E, <_1, <_2) ( E , < 1 , < 2 )
η ( ( − 1 ) ∣ E ∣ S ( Γ ( ( E , < 1 , < 2 ) ) ) ) ≤ η ( Γ ( ( E , > 1 , < 2 ) ) ) , (6) \eta\left((-1)^{\lvert E\rvert}S\left(\Gamma((E, <_1, <_2))\right)\right) \leq\eta\left(\Gamma((E, >_1, <_2))\right), \tag*{(6)} η ( ( − 1 ) ∣ E ∣ S ( Γ (( E , < 1 , < 2 )) ) ) ≤ η ( Γ (( E , > 1 , < 2 )) ) , (6) and equality holds if and only if the double poset ( E , < 1 , < 2 ) (E, <_1, <_2) ( E , < 1 , < 2 ) η \eta η
The proof of (6) is somewhat technical, but not too hard. A rough outline is given in the detailed version of this paper.
Lemmas: packed E-partitions and comultiplications
We shall now prepare for the proofs of our results. To this end, we introduce the notion of a packed map .
Definition 5.1. (a) An initial interval will mean a set of the form { 1 , 2 , … , ℓ } \{1,2,\ldots,\ell\} { 1 , 2 , … , ℓ } ℓ ∈ N \ell\in\mathbb{N} ℓ ∈ N
(b) If E E E π : E → { 1 , 2 , 3 , … } \pi:E\to\{1,2,3,\ldots\} π : E → { 1 , 2 , 3 , … } π \pi π packed if π ( E ) \pi(E) π ( E ) { 1 , 2 , … , ∣ π ( E ) ∣ } \{1,2,\ldots,|\pi(E)|\} { 1 , 2 , … , ∣ π ( E ) ∣ }
Proposition 5.2. Let E E E π : E → { 1 , 2 , 3 , … } \pi:E\to\{1,2,3,\ldots\} π : E → { 1 , 2 , 3 , … } ℓ = ∣ π ( E ) ∣ \ell=|\pi(E)| ℓ = ∣ π ( E ) ∣
(a) We have π ( E ) = { 1 , 2 , … , ℓ } \pi(E)=\{1,2,\ldots,\ell\} π ( E ) = { 1 , 2 , … , ℓ }
(b) Let w : E → { 1 , 2 , 3 , … } w:E\to\{1,2,3,\ldots\} w : E → { 1 , 2 , 3 , … } i ∈ { 1 , 2 , … , ℓ } i\in\{1,2,\ldots,\ell\} i ∈ { 1 , 2 , … , ℓ } α i \alpha_i α i
α i = ∑ e ∈ π − 1 ( i ) w ( e ) . \alpha_i=\sum_{e\in\pi^{-1}(i)}w(e). α i = e ∈ π − 1 ( i ) ∑ w ( e ) . Then, ( α 1 , α 2 , … , α ℓ ) (\alpha_1,\alpha_2,\ldots,\alpha_\ell) ( α 1 , α 2 , … , α ℓ )
Proof of Proposition 5.2. This follows from the assumption that π \pi π
Definition 5.3. Let E E E π : E → { 1 , 2 , 3 , … } \pi:E\to\{1,2,3,\ldots\} π : E → { 1 , 2 , 3 , … } w : E → { 1 , 2 , 3 , … } w:E\to\{1,2,3,\ldots\} w : E → { 1 , 2 , 3 , … } ( α 1 , α 2 , … , α ℓ ) (\alpha_1,\alpha_2,\ldots,\alpha_\ell) ( α 1 , α 2 , … , α ℓ ) ev w π \operatorname{ev}_{w}\pi ev w π
Proposition 5.4. Let E = ( E , < 1 , < 2 ) E=(E,<_{1},<_{2}) E = ( E , < 1 , < 2 ) w : E → { 1 , 2 , 3 , … } w:E\to\{1,2,3,\ldots\} w : E → { 1 , 2 , 3 , … }
Γ ( E , w ) = ∑ φ is a packed E -partition M ev w φ . (7) \Gamma(E,w)=\sum_{\varphi\text{ is a packed }E\text{-partition}}M_{\operatorname{ev}_{w}\varphi}. \tag*{(7)} Γ ( E , w ) = φ is a packed E -partition ∑ M ev w φ . (7) Proof of Proposition 5.4. For every finite subset T T T { 1 , 2 , 3 , … } \{1,2,3,\ldots\} { 1 , 2 , 3 , … } { 1 , 2 , … , ∣ T ∣ } → T \{1,2,\ldots,|T|\}\to T { 1 , 2 , … , ∣ T ∣ } → T r T r_T r T π : E → { 1 , 2 , 3 , … } \pi:E\to\{1,2,3,\ldots\} π : E → { 1 , 2 , 3 , … } packing of π \pi π r π ( E ) − 1 ∘ π : E → { 1 , 2 , 3 , … } r_{\pi(E)}^{-1}\circ\pi:E\to\{1,2,3,\ldots\} r π ( E ) − 1 ∘ π : E → { 1 , 2 , 3 , … } { 1 , 2 , … , ∣ π ( E ) ∣ } \{1,2,\ldots,|\pi(E)|\} { 1 , 2 , … , ∣ π ( E ) ∣ } pack π \operatorname{pack}\pi pack π pack π \operatorname{pack}\pi pack π E E E π \pi π E E E 15 pack π \operatorname{pack}\pi pack π E E E E E E π \pi π
We shall show that for every packed E E E φ \varphi φ
∑ π is an E -partition ; pack π = φ x π , w = M ev w φ . (8) \sum_{\substack{\pi\text{ is an }E\text{-partition};\\ \operatorname{pack}\pi=\varphi}}x_{\pi,w}=M_{\operatorname{ev}_{w}\varphi}. \tag*{(8)} π is an E -partition ; pack π = φ ∑ x π , w = M ev w φ . (8) ( ( pack π ) ( e ) ≤ ( pack π ) ( f ) ) ⟺ ( π ( e ) ≤ π ( f ) ) ((\operatorname{pack}\pi)(e)\leq(\operatorname{pack}\pi)(f))\Longleftrightarrow(\pi(e)\leq\pi(f)) (( pack π ) ( e ) ≤ ( pack π ) ( f )) ⟺ ( π ( e ) ≤ π ( f )) and
( ( pack π ) ( e ) < ( pack π ) ( f ) ) ⟺ ( π ( e ) < π ( f ) ) ((\operatorname{pack}\pi)(e)<(\operatorname{pack}\pi)(f))\Longleftrightarrow(\pi(e)<\pi(f)) (( pack π ) ( e ) < ( pack π ) ( f )) ⟺ ( π ( e ) < π ( f )) hold. Hence, pack π \operatorname{pack}\pi pack π E E E π \pi π E E E
Once this is proven, it will follow that
Γ ( E , w ) = ∑ π is an E-partition x π , w = ∑ φ is a packed E-partition ∑ π is an E-partition ; pack π = φ x π , w ⏟ = M ev w φ (by (8)) = ∑ φ is a packed E-partition M ev w φ \begin{aligned}
\Gamma(E,w)
&=\sum_{\pi\text{ is an E-partition}}x_{\pi,w}\\
&=\sum_{\varphi\text{ is a packed E-partition}}
\underbrace{\sum_{\substack{\pi\text{ is an E-partition};\\\operatorname{pack}\pi=\varphi}}x_{\pi,w}}_{=M_{\operatorname{ev}_w\varphi}\ \text{(by (8))}}\\
&=\sum_{\varphi\text{ is a packed E-partition}}M_{\operatorname{ev}_w\varphi}
\end{aligned} Γ ( E , w ) = π is an E-partition ∑ x π , w = φ is a packed E-partition ∑ = M ev w φ (by (8)) π is an E-partition ; pack π = φ ∑ x π , w = φ is a packed E-partition ∑ M ev w φ (since pack π \operatorname{pack}\pi pack π π \pi π
and Proposition 5.4 will be proven.
So it remains to prove (8). Let φ \varphi φ ℓ = ∣ φ ( E ) ∣ \ell=|\varphi(E)| ℓ = ∣ φ ( E ) ∣ φ ( E ) = { 1 , 2 , … , ℓ } \varphi(E)=\{1,2,\ldots,\ell\} φ ( E ) = { 1 , 2 , … , ℓ } φ \varphi φ α i = ∑ e ∈ φ − 1 ( i ) w ( e ) \alpha_i=\sum_{e\in\varphi^{-1}(i)}w(e) α i = ∑ e ∈ φ − 1 ( i ) w ( e ) i ∈ { 1 , 2 , … , ℓ } i\in\{1,2,\ldots,\ell\} i ∈ { 1 , 2 , … , ℓ } ev w φ = ( α 1 , α 2 , … , α ℓ ) \operatorname{ev}_w\varphi=(\alpha_1,\alpha_2,\ldots,\alpha_\ell) ev w φ = ( α 1 , α 2 , … , α ℓ ) ev w φ \operatorname{ev}_w\varphi ev w φ M ev w φ M_{\operatorname{ev}_w\varphi} M ev w φ
M ev w φ = ∑ i 1 < i 2 < ⋯ < i ℓ x i 1 α 1 x i 2 α 2 ⋯ x i ℓ α ℓ = ∑ i 1 < i 2 < ⋯ < i ℓ ∏ k = 1 ℓ x i k α k = ∑ i 1 < i 2 < ⋯ < i ℓ ∏ k = 1 ℓ x i k ∑ e ∈ φ − 1 ( k ) w ( e ) = ∑ i 1 < i 2 < ⋯ < i ℓ ∏ k = 1 ℓ ∏ e ∈ E ; φ ( e ) = k x i k w ( e ) = ∑ i 1 < i 2 < ⋯ < i ℓ ∏ k = 1 ℓ ∏ e ∈ E ; φ ( e ) = k x i φ ( e ) w ( e ) = ∑ i 1 < i 2 < ⋯ < i ℓ ∏ e ∈ E x i φ ( e ) w ( e ) = ∑ T ⊆ { 1 , 2 , 3 , … } ; ∣ T ∣ = ℓ ∏ e ∈ E x r T ( φ ( e ) ) w ( e ) . \begin{aligned}
M_{\operatorname{ev}_w\varphi}
&=\sum_{i_1<i_2<\cdots<i_\ell}x_{i_1}^{\alpha_1}x_{i_2}^{\alpha_2}\cdots x_{i_\ell}^{\alpha_\ell}
=\sum_{i_1<i_2<\cdots<i_\ell}\prod_{k=1}^{\ell}x_{i_k}^{\alpha_k}\\
&=\sum_{i_1<i_2<\cdots<i_\ell}\prod_{k=1}^{\ell}
x_{i_k}^{\sum_{e\in\varphi^{-1}(k)}w(e)}
=\sum_{i_1<i_2<\cdots<i_\ell}\prod_{k=1}^{\ell}\prod_{\substack{e\in E;\\\varphi(e)=k}}x_{i_k}^{w(e)}\\
&=\sum_{i_1<i_2<\cdots<i_\ell}\prod_{k=1}^{\ell}\prod_{\substack{e\in E;\\\varphi(e)=k}}x_{i_{\varphi(e)}}^{w(e)}
=\sum_{i_1<i_2<\cdots<i_\ell}\prod_{e\in E}x_{i_{\varphi(e)}}^{w(e)}\\
&=\sum_{\substack{T\subseteq\{1,2,3,\ldots\};\\|T|=\ell}}\prod_{e\in E}x_{r_T(\varphi(e))}^{w(e)}.
\end{aligned} M ev w φ = i 1 < i 2 < ⋯ < i ℓ ∑ x i 1 α 1 x i 2 α 2 ⋯ x i ℓ α ℓ = i 1 < i 2 < ⋯ < i ℓ ∑ k = 1 ∏ ℓ x i k α k = i 1 < i 2 < ⋯ < i ℓ ∑ k = 1 ∏ ℓ x i k ∑ e ∈ φ − 1 ( k ) w ( e ) = i 1 < i 2 < ⋯ < i ℓ ∑ k = 1 ∏ ℓ e ∈ E ; φ ( e ) = k ∏ x i k w ( e ) = i 1 < i 2 < ⋯ < i ℓ ∑ k = 1 ∏ ℓ e ∈ E ; φ ( e ) = k ∏ x i φ ( e ) w ( e ) = i 1 < i 2 < ⋯ < i ℓ ∑ e ∈ E ∏ x i φ ( e ) w ( e ) = T ⊆ { 1 , 2 , 3 , … } ; ∣ T ∣ = ℓ ∑ e ∈ E ∏ x r T ( φ ( e )) w ( e ) . Hence,
M Ev w φ = ∑ T ⊆ { 1 , 2 , 3 , … } ∣ T ∣ = ℓ ∏ e ∈ E x r T ( φ ( e ) ) w ( e ) = ∑ T ⊆ { 1 , 2 , 3 , … } ∣ T ∣ = ℓ x r T ∘ φ , w . (9) M_{\operatorname{Ev}_{w}}\varphi
=
\sum_{\substack{T\subseteq\{1,2,3,\ldots\}\\ |T|=\ell}}
\prod_{e\in E}x_{r_T(\varphi(e))}^{w(e)}
=
\sum_{\substack{T\subseteq\{1,2,3,\ldots\}\\ |T|=\ell}}x_{r_T\circ\varphi,w}. \tag*{(9)} M Ev w φ = T ⊆ { 1 , 2 , 3 , … } ∣ T ∣ = ℓ ∑ e ∈ E ∏ x r T ( φ ( e )) w ( e ) = T ⊆ { 1 , 2 , 3 , … } ∣ T ∣ = ℓ ∑ x r T ∘ φ , w . (9) On the other hand, recall that φ \varphi φ E E E π \pi π pack π = φ \operatorname{pack}\pi=\varphi pack π = φ E E E pack π \operatorname{pack}\pi pack π E E E π \pi π E E E E E E π \pi π pack π = φ \operatorname{pack}\pi=\varphi pack π = φ π : E → { 1 , 2 , 3 , … } \pi:E\to\{1,2,3,\ldots\} π : E → { 1 , 2 , 3 , … } pack π = φ \operatorname{pack}\pi=\varphi pack π = φ
∑ π is an E -partition pack π = φ x π , w = ∑ π : E → { 1 , 2 , 3 , … } pack π = φ x π , w = ∑ T ⊆ { 1 , 2 , 3 , … } ∣ T ∣ = ℓ ∑ π : E → { 1 , 2 , 3 , … } pack π = φ ; π ( E ) = T x π , w \begin{aligned}
\sum_{\substack{\pi\text{ is an }E\text{-partition}\\ \operatorname{pack}\pi=\varphi}}x_{\pi,w}
=
\sum_{\substack{\pi:E\to\{1,2,3,\ldots\}\\ \operatorname{pack}\pi=\varphi}}x_{\pi,w} \\
&=
\sum_{\substack{T\subseteq\{1,2,3,\ldots\}\\ |T|=\ell}}
\ \sum_{\substack{\pi:E\to\{1,2,3,\ldots\}\\ \operatorname{pack}\pi=\varphi;\ \pi(E)=T}}x_{\pi,w}
\end{aligned} π is an E -partition pack π = φ ∑ x π , w = π : E → { 1 , 2 , 3 , … } pack π = φ ∑ x π , w = T ⊆ { 1 , 2 , 3 , … } ∣ T ∣ = ℓ ∑ π : E → { 1 , 2 , 3 , … } pack π = φ ; π ( E ) = T ∑ x π , w (because if π : E → { 1 , 2 , 3 , … } \pi:E\to\{1,2,3,\ldots\} π : E → { 1 , 2 , 3 , … } pack π = φ \operatorname{pack}\pi=\varphi pack π = φ ∣ π ( E ) ∣ = ℓ |\pi(E)|=\ell ∣ π ( E ) ∣ = ℓ ℓ \ell ℓ T T T { 1 , 2 , 3 , … } \{1,2,3,\ldots\} { 1 , 2 , 3 , … } π : E → { 1 , 2 , 3 , … } \pi:E\to\{1,2,3,\ldots\} π : E → { 1 , 2 , 3 , … } pack π = φ \operatorname{pack}\pi=\varphi pack π = φ π ( E ) = T \pi(E)=T π ( E ) = T π = r T ∘ φ \pi=r_T\circ\varphi π = r T ∘ φ
Claim 1: The map r T ∘ φ r_T\circ\varphi r T ∘ φ π : E → { 1 , 2 , 3 , … } \pi:E\to\{1,2,3,\ldots\} π : E → { 1 , 2 , 3 , … } pack π = φ \operatorname{pack}\pi=\varphi pack π = φ π ( E ) = T \pi(E)=T π ( E ) = T
Claim 2: If π : E → { 1 , 2 , 3 , … } \pi:E\to\{1,2,3,\ldots\} π : E → { 1 , 2 , 3 , … } pack π = φ \operatorname{pack}\pi=\varphi pack π = φ π ( E ) = T \pi(E)=T π ( E ) = T π = r T ∘ φ \pi=r_T\circ\varphi π = r T ∘ φ
Proof of Claim 1. We have ∣ T ∣ = ℓ |T|=\ell ∣ T ∣ = ℓ T T T ℓ \ell ℓ ℓ = ∣ T ∣ \ell=|T| ℓ = ∣ T ∣
( r T ∘ φ ) ( E ) = r T ( φ ( E ) ) = r T ( { 1 , 2 , … , ℓ } ) = r T ( { 1 , 2 , … , ∣ T ∣ } ) = T (r_T\circ\varphi)(E)
=
r_T\left(\varphi(E)\right)
=
r_T\left(\{1,2,\ldots,\ell\}\right)
=
r_T\left(\{1,2,\ldots,|T|\}\right)
=
T ( r T ∘ φ ) ( E ) = r T ( φ ( E ) ) = r T ( { 1 , 2 , … , ℓ } ) = r T ( { 1 , 2 , … , ∣ T ∣ } ) = T (by the definition of r T r_T r T pack ( r T ∘ φ ) \operatorname{pack}(r_T\circ\varphi) pack ( r T ∘ φ )
pack ( r T ∘ φ ) = r ( r T ∘ φ ) ( E ) − 1 ∘ ( r T ∘ φ ) = r T − 1 ∘ ( r T ∘ φ ) \operatorname{pack}(r_T\circ\varphi)
=
r_{(r_T\circ\varphi)(E)}^{-1}\circ(r_T\circ\varphi)
=
r_T^{-1}\circ(r_T\circ\varphi) pack ( r T ∘ φ ) = r ( r T ∘ φ ) ( E ) − 1 ∘ ( r T ∘ φ ) = r T − 1 ∘ ( r T ∘ φ ) (since ( r T ∘ φ ) ( E ) = T (r_T\circ\varphi)(E)=T ( r T ∘ φ ) ( E ) = T
Therefore, for every ℓ \ell ℓ T T T { 1 , 2 , 3 , … } \{1,2,3,\ldots\} { 1 , 2 , 3 , … }
∑ π : E → { 1 , 2 , 3 , … } pack π = φ ; π ( E ) = T x π , w = x r T ∘ φ , w . \sum_{\substack{\pi:E\to\{1,2,3,\ldots\}\\ \operatorname{pack}\pi=\varphi;\ \pi(E)=T}}x_{\pi,w}=x_{r_T\circ\varphi,w}. π : E → { 1 , 2 , 3 , … } pack π = φ ; π ( E ) = T ∑ x π , w = x r T ∘ φ , w . Hence,
∑ π is an E -partition ; pack π = φ x π , w = ∑ T ⊆ { 1 , 2 , 3 , … } ∣ T ∣ = ℓ ∑ π : E → { 1 , 2 , 3 , … } pack π = φ ; π ( E ) = T x π , w = ∑ T ⊆ { 1 , 2 , 3 , … } ∣ T ∣ = ℓ x r T ∘ φ , w = M E v w φ \sum_{\substack{\pi\text{ is an }E\text{-partition};\ \operatorname{pack}\pi=\varphi}}x_{\pi,w}
=
\sum_{\substack{T\subseteq\{1,2,3,\ldots\}\\ |T|=\ell}}
\sum_{\substack{\pi:E\to\{1,2,3,\ldots\}\\ \operatorname{pack}\pi=\varphi;\ \pi(E)=T}}x_{\pi,w}
=
\sum_{\substack{T\subseteq\{1,2,3,\ldots\}\\ |T|=\ell}}x_{r_T\circ\varphi,w}
=M_{E v w}\varphi π is an E -partition ; pack π = φ ∑ x π , w = T ⊆ { 1 , 2 , 3 , … } ∣ T ∣ = ℓ ∑ π : E → { 1 , 2 , 3 , … } pack π = φ ; π ( E ) = T ∑ x π , w = T ⊆ { 1 , 2 , 3 , … } ∣ T ∣ = ℓ ∑ x r T ∘ φ , w = M E v w φ (by (9)). Thus, (8) is proven, and with it Proposition 5.4.
Proof of Proposition 3.5. Proposition 3.5 follows immediately from Proposition 5.4 (since M α ∈ QSym M_\alpha\in\operatorname{QSym} M α ∈ QSym α \alpha α
We shall now describe the coproduct of Γ ( E , w ) \Gamma(E,w) Γ ( E , w ) [19 Theorem 2.2] .
Definition 5.5. Let E = ( E , < 1 , < 2 ) E=(E,<_{1},<_{2}) E = ( E , < 1 , < 2 )
(a) Then, Adm E \operatorname{Adm}E Adm E ( P , Q ) (P,Q) ( P , Q ) P P P Q Q Q E E E P ∩ Q = ∅ P\cap Q=\varnothing P ∩ Q = ∅ P ∪ Q = E P\cup Q=E P ∪ Q = E p ∈ P p\in P p ∈ P q ∈ Q q\in Q q ∈ Q q < 1 p q<_{1}p q < 1 p ( P , Q ) (P,Q) ( P , Q ) admissible partitions of E E E [19 ] , they are the decompositions of ( E , < 1 ) (E,<_{1}) ( E , < 1 )
(b) For any subset T T T E E E E ∣ T E\mid_T E ∣ T ( T , < 1 , < 2 ) (T,<_{1},<_{2}) ( T , < 1 , < 2 ) < 1 <_{1} < 1 < 2 <_{2} < 2 < 1 <_{1} < 1 < 2 <_{2} < 2 T T T
Proposition 5.6. Let E = ( E , < 1 , < 2 ) E=(E,<_{1},<_{2}) E = ( E , < 1 , < 2 ) w : E → { 1 , 2 , 3 , … } w:E\to\{1,2,3,\ldots\} w : E → { 1 , 2 , 3 , … }
Δ ( Γ ( E , w ) ) = ∑ ( P , Q ) ∈ Adm E Γ ( E ∣ P , w ∣ P ) ⊗ Γ ( E ∣ Q , w ∣ Q ) (10) \Delta\left(\Gamma(E,w)\right)=\sum_{(P,Q)\in\operatorname{Adm}E}\Gamma\left(E\mid_P,w\mid_P\right)\otimes\Gamma\left(E\mid_Q,w\mid_Q\right) \tag*{(10)} Δ ( Γ ( E , w ) ) = ( P , Q ) ∈ Adm E ∑ Γ ( E ∣ P , w ∣ P ) ⊗ Γ ( E ∣ Q , w ∣ Q ) (10) Thus, the map r T ∘ φ : E → { 1 , 2 , 3 , … } r_T\circ\varphi:E\to\{1,2,3,\ldots\} r T ∘ φ : E → { 1 , 2 , 3 , … } pack ( r T ∘ φ ) = φ \operatorname{pack}(r_T\circ\varphi)=\varphi pack ( r T ∘ φ ) = φ ( r T ∘ φ ) ( E ) = T (r_T\circ\varphi)(E)=T ( r T ∘ φ ) ( E ) = T r T ∘ φ r_T\circ\varphi r T ∘ φ π : E → { 1 , 2 , 3 , … } \pi:E\to\{1,2,3,\ldots\} π : E → { 1 , 2 , 3 , … } pack π = φ \operatorname{pack}\pi=\varphi pack π = φ π ( E ) = T \pi(E)=T π ( E ) = T
Proof of Claim 2. Let π : E → { 1 , 2 , 3 , … } \pi:E\to\{1,2,3,\ldots\} π : E → { 1 , 2 , 3 , … } pack π = φ \operatorname{pack}\pi=\varphi pack π = φ π ( E ) = T \pi(E)=T π ( E ) = T pack π \operatorname{pack}\pi pack π pack π = r π ( E ) − 1 ∘ π = r T − 1 ∘ π \operatorname{pack}\pi=r_{\pi(E)}^{-1}\circ\pi=r_T^{-1}\circ\pi pack π = r π ( E ) − 1 ∘ π = r T − 1 ∘ π π ( E ) = T \pi(E)=T π ( E ) = T r T − 1 ∘ π = pack π = φ r_T^{-1}\circ\pi=\operatorname{pack}\pi=\varphi r T − 1 ∘ π = pack π = φ π = r T ∘ φ \pi=r_T\circ\varphi π = r T ∘ φ
Now, both Claims 1 and 2 are proven; hence, our proof is complete.
A particular case of Proposition 5.6 (namely, the case when w ( e ) = 1 w(e)=1 w ( e ) = 1 e ∈ E e\in E e ∈ E [16 Théorème 4.16] .
The proof of Proposition 5.6 relies on a simple bijection that an experienced combinatorialist will have no trouble finding (and proving even less); let us just give a brief outline of the argument.19
Proof of Proposition 5.6. Whenever α = ( α 1 , α 2 , … , α ℓ ) \alpha=(\alpha_1,\alpha_2,\ldots,\alpha_\ell) α = ( α 1 , α 2 , … , α ℓ ) k ∈ { 0 , 1 , … , ℓ } k\in\{0,1,\ldots,\ell\} k ∈ { 0 , 1 , … , ℓ } α [ : k ] \alpha[:k] α [ : k ] ( α 1 , α 2 , … , α k ) (\alpha_1,\alpha_2,\ldots,\alpha_k) ( α 1 , α 2 , … , α k ) α [ k : ] \alpha[k:] α [ k : ] ( α k + 1 , α k + 2 , … , α ℓ ) (\alpha_{k+1},\alpha_{k+2},\ldots,\alpha_\ell) ( α k + 1 , α k + 2 , … , α ℓ )
Δ ( M α ) = ∑ k = 0 ℓ M α [ : k ] ⊗ M α [ k : ] (11) \Delta(M_\alpha)=\sum_{k=0}^{\ell}M_{\alpha[:k]}\otimes M_{\alpha[k:]} \tag*{(11)} Δ ( M α ) = k = 0 ∑ ℓ M α [ : k ] ⊗ M α [ k : ] (11) for every ℓ ∈ N \ell\in\mathbb{N} ℓ ∈ N α \alpha α ℓ \ell ℓ
Now, applying Δ \Delta Δ
Δ ( Γ ( E , w ) ) = ∑ φ is a packed E -partition Δ ( M ev w φ ) = ∑ φ is a packed E -partition ∑ k = 0 ∣ φ ( E ) ∣ M ( ev w φ ) [ : k ] ⊗ M ( ev w φ ) [ k : ] (by (11)) = ∑ φ is a packed E -partition ∑ k = 0 ∣ φ ( E ) ∣ M ( ev w φ ) [ : k ] ⊗ M ( ev w φ ) [ k : ] . (12) \begin{aligned}
\Delta(\Gamma(E,w))=\sum_{\substack{\varphi\text{ is a packed}\\E\text{-partition}}}\Delta(M_{\operatorname{ev}_{w}\varphi}) \\
&=\sum_{\substack{\varphi\text{ is a packed}\\E\text{-partition}}}\sum_{k=0}^{|\varphi(E)|}M_{(\operatorname{ev}_{w}\varphi)[:k]}\otimes M_{(\operatorname{ev}_{w}\varphi)[k:]}
\qquad\text{(by (11))} \\
&=\sum_{\substack{\varphi\text{ is a packed}\\E\text{-partition}}}\sum_{k=0}^{|\varphi(E)|}M_{(\operatorname{ev}_{w}\varphi)[:k]}\otimes M_{(\operatorname{ev}_{w}\varphi)[k:]}. \tag*{(12)}
\end{aligned} Δ ( Γ ( E , w )) = φ is a packed E -partition ∑ Δ ( M ev w φ ) = φ is a packed E -partition ∑ k = 0 ∑ ∣ φ ( E ) ∣ M ( ev w φ ) [ : k ] ⊗ M ( ev w φ ) [ k : ] (by (11)) = φ is a packed E -partition ∑ k = 0 ∑ ∣ φ ( E ) ∣ M ( ev w φ ) [ : k ] ⊗ M ( ev w φ ) [ k : ] . (12) On the other hand, rewriting each of the tensorands on the right hand side of (10) using (7), we obtain
∑ ( P , Q ) ∈ Adm E Γ ( E ∣ P , w ∣ P ) ⊗ Γ ( E ∣ Q , w ∣ Q ) = ∑ ( P , Q ) ∈ Adm E ( ∑ φ is a packed E ∣ P -partition M ev w ∣ P φ ) ⊗ ( ∑ φ is a packed E ∣ Q -partition M ev w ∣ Q φ ) = ∑ ( P , Q ) ∈ Adm E ( ∑ σ is a packed E ∣ P -partition M ev w ∣ P σ ) ⊗ ( ∑ τ is a packed E ∣ Q -partition M ev w ∣ Q τ ) = ∑ ( P , Q ) ∈ Adm E ∑ σ is a packed E ∣ P -partition τ is a packed E ∣ Q -partition M ev w ∣ P σ ⊗ M ev w ∣ Q τ . \begin{aligned}
\sum_{(P,Q)\in\operatorname{Adm}E}\Gamma(E|_P,w|_P)\otimes\Gamma(E|_Q,w|_Q) \\
&=\sum_{(P,Q)\in\operatorname{Adm}E}
\left(\sum_{\substack{\varphi\text{ is a packed}\\E|_P\text{-partition}}}M_{\operatorname{ev}_{w|_P}\varphi}\right)
\otimes
\left(\sum_{\substack{\varphi\text{ is a packed}\\E|_Q\text{-partition}}}M_{\operatorname{ev}_{w|_Q}\varphi}\right) \\
&=\sum_{(P,Q)\in\operatorname{Adm}E}
\left(\sum_{\substack{\sigma\text{ is a packed}\\E|_P\text{-partition}}}M_{\operatorname{ev}_{w|_P}\sigma}\right)
\otimes
\left(\sum_{\substack{\tau\text{ is a packed}\\E|_Q\text{-partition}}}M_{\operatorname{ev}_{w|_Q}\tau}\right) \\
&=\sum_{(P,Q)\in\operatorname{Adm}E}
\sum_{\substack{\sigma\text{ is a packed }E|_P\text{-partition}\\\tau\text{ is a packed }E|_Q\text{-partition}}}
M_{\operatorname{ev}_{w|_P}\sigma}\otimes M_{\operatorname{ev}_{w|_Q}\tau}.
\end{aligned} ( P , Q ) ∈ Adm E ∑ Γ ( E ∣ P , w ∣ P ) ⊗ Γ ( E ∣ Q , w ∣ Q ) = ( P , Q ) ∈ Adm E ∑ φ is a packed E ∣ P -partition ∑ M ev w ∣ P φ ⊗ φ is a packed E ∣ Q -partition ∑ M ev w ∣ Q φ = ( P , Q ) ∈ Adm E ∑ σ is a packed E ∣ P -partition ∑ M ev w ∣ P σ ⊗ τ is a packed E ∣ Q -partition ∑ M ev w ∣ Q τ = ( P , Q ) ∈ Adm E ∑ σ is a packed E ∣ P -partition τ is a packed E ∣ Q -partition ∑ M ev w ∣ P σ ⊗ M ev w ∣ Q τ . We need to prove that the right hand sides of this equality and of (12) are equal (because then, it will follow that so are the left hand sides, and thus Proposition 5.6 will be proven). For this, it is clearly enough to exhibit a bijection between
the pairs ( φ , k ) (\varphi,k) ( φ , k ) φ \varphi φ k ∈ { 0 , 1 , … , ∣ φ ( E ) ∣ } k \in\{0,1,\ldots,|\varphi(E)|\} k ∈ { 0 , 1 , … , ∣ φ ( E ) ∣ }
and
the triples ( ( P , Q ) , σ , τ ) ((P,Q),\sigma,\tau) (( P , Q ) , σ , τ ) ( P , Q ) ∈ Adm E (P,Q) \in\operatorname{Adm} E ( P , Q ) ∈ Adm E E ∣ P E\mid_P E ∣ P σ \sigma σ E ∣ Q E\mid_Q E ∣ Q τ \tau τ
which bijection has the property that whenever it maps ( φ , k ) (\varphi,k) ( φ , k ) ( ( P , Q ) , σ , τ ) ((P,Q),\sigma,\tau) (( P , Q ) , σ , τ ) ( ev w φ ) [ : k ] = ev w ∣ P σ (\operatorname{ev}_w\varphi)[:k]=\operatorname{ev}_{w\mid_P}\sigma ( ev w φ ) [ : k ] = ev w ∣ P σ ( ev w φ ) [ k : ] = ev w ∣ Q τ (\operatorname{ev}_w\varphi)[k:]=\operatorname{ev}_{w\mid_Q}\tau ( ev w φ ) [ k : ] = ev w ∣ Q τ ( φ , k ) (\varphi,k) ( φ , k ) P = φ − 1 ( { 1 , 2 , … , k } ) P=\varphi^{-1}(\{1,2,\ldots,k\}) P = φ − 1 ({ 1 , 2 , … , k }) Q = φ − 1 ( { k + 1 , k + 2 , … , ∣ φ ( E ) ∣ } ) Q=\varphi^{-1}(\{k+1,k+2,\ldots,|\varphi(E)|\}) Q = φ − 1 ({ k + 1 , k + 2 , … , ∣ φ ( E ) ∣ }) σ = φ ∣ P \sigma=\varphi\mid_P σ = φ ∣ P τ = pack ( φ ∣ Q ) \tau=\operatorname{pack}(\varphi\mid_Q) τ = pack ( φ ∣ Q ) 20 ( ( P , Q ) , σ , τ ) ((P,Q),\sigma,\tau) (( P , Q ) , σ , τ ) k = ∣ σ ( P ) ∣ k=|\sigma(P)| k = ∣ σ ( P ) ∣ φ \varphi φ E → { 1 , 2 , 3 , … } E\to\{1,2,3,\ldots\} E → { 1 , 2 , 3 , … } e ∈ E e\in E e ∈ E { σ ( e ) , if e ∈ P ; τ ( e ) + k , if e ∈ Q . \begin{cases}\sigma(e),&\text{if }e\in P;\\ \tau(e)+k,&\text{if }e\in Q.\end{cases} { σ ( e ) , τ ( e ) + k , if e ∈ P ; if e ∈ Q . 21
Claim 1: Every e ∈ E e\in E e ∈ E f ∈ E f\in E f ∈ E e < 1 f e<_{1}f e < 1 f φ ( e ) ≤ φ ( f ) \varphi(e)\le\varphi(f) φ ( e ) ≤ φ ( f )
Claim 2: Every e ∈ E e\in E e ∈ E f ∈ E f\in E f ∈ E e < 1 f e<_{1}f e < 1 f f < 2 e f<_{2}e f < 2 e φ ( e ) < φ ( f ) \varphi(e)<\varphi(f) φ ( e ) < φ ( f )
We shall only prove Claim 1 (as the proof of Claim 2 is similar). So let e ∈ E e\in E e ∈ E f ∈ E f\in E f ∈ E e < 1 f e<_{1}f e < 1 f φ ( e ) ≤ φ ( f ) \varphi(e)\le\varphi(f) φ ( e ) ≤ φ ( f )
Case 1: We have e ∈ P e\in P e ∈ P f ∈ P f\in P f ∈ P
Case 2: We have e ∈ P e\in P e ∈ P f ∈ Q f\in Q f ∈ Q
Case 3: We have e ∈ Q e\in Q e ∈ Q f ∈ P f\in P f ∈ P
Case 4: We have e ∈ Q e\in Q e ∈ Q f ∈ Q f\in Q f ∈ Q
In Case 1, our claim φ ( e ) ≤ φ ( f ) \varphi(e)\le\varphi(f) φ ( e ) ≤ φ ( f ) σ \sigma σ E ∣ P E\mid_P E ∣ P φ ( e ) = σ ( e ) \varphi(e)=\sigma(e) φ ( e ) = σ ( e ) φ ( f ) = σ ( f ) \varphi(f)=\sigma(f) φ ( f ) = σ ( f ) τ \tau τ E ∣ Q E\mid_Q E ∣ Q φ ( e ) = τ ( e ) + k \varphi(e)=\tau(e)+k φ ( e ) = τ ( e ) + k φ ( f ) = τ ( f ) + k \varphi(f)=\tau(f)+k φ ( f ) = τ ( f ) + k e ∈ P e\in P e ∈ P φ \varphi φ φ ( e ) = σ ( e ) ≤ k \varphi(e)=\sigma(e)\le k φ ( e ) = σ ( e ) ≤ k f ∈ Q f\in Q f ∈ Q φ \varphi φ φ ( f ) = τ ( f ) + k > k \varphi(f)=\tau(f)+k>k φ ( f ) = τ ( f ) + k > k φ ( e ) ≤ k < φ ( f ) \varphi(e)\le k<\varphi(f) φ ( e ) ≤ k < φ ( f ) e ∈ Q e\in Q e ∈ Q f ∈ P f\in P f ∈ P e < 1 f e<_{1}f e < 1 f ( P , Q ) ∈ Adm E (P,Q)\in\operatorname{Adm} E ( P , Q ) ∈ Adm E
defined to be u u u E E E E F EF E F v v v F F F E F EF E F E F EF E F [19 §2.1] . Combined with Proposition 3.5, this fact gives a combinatorial proof for the fact that QSym is a k k k Δ M α \Delta M_{\alpha} Δ M α Δ L α \Delta L_{\alpha} Δ L α Δ s λ / μ \Delta s_{\lambda/\mu} Δ s λ / μ Δ M α \Delta M_{\alpha} Δ M α
Proof of Theorem 4.2
Before we come to the proof of Theorem 4.2, let us state five lemmas:
Lemma 6.1. Let E = ( E , < 1 , < 2 ) E=(E,<_{1},<_{2}) E = ( E , < 1 , < 2 ) P P P Q Q Q E E E P ∩ Q = ∅ P\cap Q=\varnothing P ∩ Q = ∅ P ∪ Q = E P\cup Q=E P ∪ Q = E p ∈ P p\in P p ∈ P q ∈ Q q\in Q q ∈ Q q q q < 1 <_{1} < 1 p p p ( P , Q ) ∈ Adm E (P,Q)\in\operatorname{Adm} E ( P , Q ) ∈ Adm E
Proof of Lemma 6.1. For any a ∈ E a\in E a ∈ E b ∈ E b\in E b ∈ E [ a , b ] [a,b] [ a , b ] { e ∈ E ∣ a < 1 e < 1 b } \{e\in E\mid a<_{1}e<_{1}b\} { e ∈ E ∣ a < 1 e < 1 b } E E E a a a b b b c c c E E E a < 1 c < 1 b a<_{1}c<_{1}b a < 1 c < 1 b [ a , c ] [a,c] [ a , c ] [ c , b ] [c,b] [ c , b ] [ a , b ] [a,b] [ a , b ]
both numbers ∣ [ a , c ] ∣ and ∣ [ c , b ] ∣ are smaller than ∣ [ a , b ] ∣ . (13) \text{both numbers } |[a,c]| \text{ and } |[c,b]| \text{ are smaller than } |[a,b]|. \tag*{(13)} both numbers ∣ [ a , c ] ∣ and ∣ [ c , b ] ∣ are smaller than ∣ [ a , b ] ∣. (13) A pair ( p , q ) ∈ P × Q (p,q)\in P\times Q ( p , q ) ∈ P × Q malposition if it satisfies q < 1 p q<_{1}p q < 1 p ( u , v ) (u,v) ( u , v ) ∣ [ v , u ] ∣ |[v,u]| ∣ [ v , u ] ∣ ( u , v ) ∈ P × Q (u,v)\in P\times Q ( u , v ) ∈ P × Q v < 1 u v<_{1}u v < 1 u ( u , v ) ∈ P × Q (u,v)\in P\times Q ( u , v ) ∈ P × Q u ∈ P u\in P u ∈ P v ∈ Q v\in Q v ∈ Q v v v < 1 <_{1} < 1 u u u p ∈ P p\in P p ∈ P q ∈ Q q\in Q q ∈ Q q q q < 1 <_{1} < 1 p p p w ∈ E w\in E w ∈ E v < 1 w < 1 u v<_{1}w<_{1}u v < 1 w < 1 u v < 1 u v<_{1}u v < 1 u w w w a = v a=v a = v c = w c=w c = w b = u b=u b = u ∣ [ v , w ] ∣ |[v,w]| ∣ [ v , w ] ∣ ∣ [ w , u ] ∣ |[w,u]| ∣ [ w , u ] ∣ ∣ [ v , u ] ∣ |[v,u]| ∣ [ v , u ] ∣ ( w , v ) (w,v) ( w , v ) ( u , w ) (u,w) ( u , w ) ( u , v ) (u,v) ( u , v ) ∣ [ v , u ] ∣ |[v,u]| ∣ [ v , u ] ∣ w ∈ E = P ∪ Q w\in E=P\cup Q w ∈ E = P ∪ Q w ∈ P w\in P w ∈ P w ∈ Q w\in Q w ∈ Q w ∈ P w\in P w ∈ P ( w , v ) (w,v) ( w , v ) w ∈ Q w\in Q w ∈ Q ( u , w ) (u,w) ( u , w ) ( w , v ) (w,v) ( w , v ) ( u , w ) (u,w) ( u , w ) ( p , q ) ∈ P × Q (p,q)\in P\times Q ( p , q ) ∈ P × Q q < 1 p q<_{1}p q < 1 p p ∈ P p\in P p ∈ P q ∈ Q q\in Q q ∈ Q q < 1 p q<_{1}p q < 1 p ( P , Q ) ∈ Adm E (P,Q)\in\operatorname{Adm} E ( P , Q ) ∈ Adm E
Lemma 6.2. Let E = ( E , < 1 , < 2 ) E=(E,<_{1},<_{2}) E = ( E , < 1 , < 2 ) ( P , Q ) ∈ Adm E (P,Q)\in\operatorname{Adm} E ( P , Q ) ∈ Adm E E ∣ P E|_{P} E ∣ P
Proof of Lemma 6.2. Recall that we are using the symbol < 1 <_{1} < 1 E E E P P P a a a < 1 <_{1} < 1 b b b a a a b b b P P P < 1 <_{1} < 1 E E E P P P
Thus, for the duration of this proof, we shall revert to a less ambiguous notation. Namely, the notation < 1 <_{1} < 1 E E E E E E < 1 <_{1} < 1 P P P < 1 , P <_{1,P} < 1 , P < 1 <_{1} < 1 < 2 <_{2} < 2 P P P < 2 , P <_{2,P} < 2 , P < 2 <_{2} < 2 E ∣ P E|_{P} E ∣ P E ∣ P = ( P , < 1 , P , < 2 , P ) E|_{P}=(P,<_{1,P},<_{2,P}) E ∣ P = ( P , < 1 , P , < 2 , P )
We need to show that the double poset E ∣ P = ( P , < 1 , P , < 2 , P ) E|_{P}=(P,<_{1,P},<_{2,P}) E ∣ P = ( P , < 1 , P , < 2 , P ) a a a b b b P P P a a a < 1 , P <_{1,P} < 1 , P b b b a a a b b b < 2 , P <_{2,P} < 2 , P
Let a a a b b b P P P a a a < 1 , P <_{1,P} < 1 , P b b b a < 1 , P b a<_{1,P}b a < 1 , P b
there exists no c ∈ P satisfying a < 1 , P c < 1 , P b . (14) \text{there exists no }c\in P\text{ satisfying }a<_{1,P}c<_{1,P}b. \tag*{(14)} there exists no c ∈ P satisfying a < 1 , P c < 1 , P b . (14) We have a < 1 , P b a<_{1,P}b a < 1 , P b a < 1 b a<_{1}b a < 1 b < 1 , P <_{1,P} < 1 , P < 1 <_{1} < 1 P P P
Now, if c ∈ E c\in E c ∈ E a < 1 c < 1 b a<_{1}c<_{1}b a < 1 c < 1 b c c c P P P 22 a < 1 , P c < 1 , P b a<_{1,P}c<_{1,P}b a < 1 , P c < 1 , P b 23 c ∈ E c\in E c ∈ E a < 1 c < 1 b a<_{1}c<_{1}b a < 1 c < 1 b a < 1 b a<_{1}b a < 1 b a a a < 1 <_{1} < 1 b b b E E E a a a b b b < 2 <_{2} < 2 a < 2 b a<_{2}b a < 2 b a = b a=b a = b b < 2 a b<_{2}a b < 2 a a a a b b b P P P < 2 <_{2} < 2 < 2 , P <_{2,P} < 2 , P a < 2 , P b a<_{2,P}b a < 2 , P b a = b a=b a = b b < 2 , P a b<_{2,P}a b < 2 , P a a a a b b b < 2 , P <_{2,P} < 2 , P
Now, forget that we fixed a a a b b b a a a b b b P P P a a a < 1 , P <_{1,P} < 1 , P b b b a a a b b b < 2 , P <_{2,P} < 2 , P
(We could similarly show that E ∣ Q E|_{Q} E ∣ Q
no p ∈ P and q ∈ Q satisfy q < 1 p . (15) \text{no }p\in P\text{ and }q\in Q\text{ satisfy }q<_{1}p. \tag*{(15)} no p ∈ P and q ∈ Q satisfy q < 1 p . (15) From c ∈ E c\in E c ∈ E c ∉ P c\notin P c ∈ / P c ∈ E ∖ P ⊆ Q c\in E\setminus P\subseteq Q c ∈ E ∖ P ⊆ Q P ∪ Q = E P\cup Q=E P ∪ Q = E p = b p=b p = b q = c q=c q = c c < 1 b c<_{1}b c < 1 b c < 1 b c<_{1}b c < 1 b
Lemma 6.3. Let E = ( E , < 1 , < 2 ) E=(E,<_{1},<_{2}) E = ( E , < 1 , < 2 ) w : E → { 1 , 2 , 3 , … } w:E\to\{1,2,3,\ldots\} w : E → { 1 , 2 , 3 , … }
(a) If E = ∅ E=\varnothing E = ∅ Γ ( E , w ) = 1 \Gamma(E,w)=1 Γ ( E , w ) = 1
(b) If E ≠ ∅ E\ne\varnothing E = ∅ ε ( Γ ( E , w ) ) = 0 \varepsilon(\Gamma(E,w))=0 ε ( Γ ( E , w )) = 0
Proof of Lemma 6.3. (a) Part (a) is obvious (since there is only one E E E π \pi π E = ∅ E=\varnothing E = ∅ E E E π \pi π x π , w = 1 x_{\pi,w}=1 x π , w = 1
(b) Observe that Γ ( E , w ) \Gamma(E,w) Γ ( E , w )
∑ e ∈ E w ( e ) \sum_{e\in E}w(e) e ∈ E ∑ w ( e ) When E ≠ ∅ E\ne\varnothing E = ∅ > 0 >0 > 0 Γ ( E , w ) \Gamma(E,w) Γ ( E , w ) ε \varepsilon ε ε \varepsilon ε > 0 >0 > 0
Lemma 6.4. Let ( E , < 1 , < 2 ) (E,<_{1},<_{2}) ( E , < 1 , < 2 ) > 1 >_{1} > 1 < 1 <_{1} < 1 P P P Q Q Q E E E P ∪ Q = E P\cup Q=E P ∪ Q = E π : E → { 1 , 2 , 3 , … } \pi:E\to\{1,2,3,\ldots\} π : E → { 1 , 2 , 3 , … } π ∣ P \pi|_{P} π ∣ P ( P , > 1 , < 2 ) (P,>_{1},<_{2}) ( P , > 1 , < 2 ) f ∈ P f\in P f ∈ P
no p ∈ P and q ∈ Q satisfy q < 1 p . (16) \text{no }p\in P\text{ and }q\in Q\text{ satisfy }q<_{1}p. \tag*{(16)} no p ∈ P and q ∈ Q satisfy q < 1 p . (16) Also, assume that
π ( f ) ≤ π ( h ) for every h ∈ E . (17) \pi(f)\le\pi(h)\qquad\text{for every }h\in E. \tag*{(17)} π ( f ) ≤ π ( h ) for every h ∈ E . (17) Furthermore, assume that
π ( f ) < π ( h ) for every h ∈ E satisfying h < 2 f . (18) \pi(f)<\pi(h)\qquad\text{for every }h\in E\text{ satisfying }h<_{2}f. \tag*{(18)} π ( f ) < π ( h ) for every h ∈ E satisfying h < 2 f . (18) (a) If p ∈ P ∖ { f } p\in P\setminus\{f\} p ∈ P ∖ { f } q ∈ Q ∪ { f } q\in Q\cup\{f\} q ∈ Q ∪ { f } q < 1 p q<_{1}p q < 1 p q < 2 p q<_{2}p q < 2 p p < 2 q p<_{2}q p < 2 q
(b) If π ∣ Q \pi|_{Q} π ∣ Q ( Q , < 1 , < 2 ) (Q,<_{1},<_{2}) ( Q , < 1 , < 2 ) π ∣ Q ∪ { f } \pi|_{Q\cup\{f\}} π ∣ Q ∪ { f } ( Q ∪ { f } , < 1 , < 2 ) (Q\cup\{f\},<_{1},<_{2}) ( Q ∪ { f } , < 1 , < 2 )
Proof of Lemma 6.4. From P ∪ Q = E P\cup Q=E P ∪ Q = E E ∖ P = ( P ∪ Q ) ∖ P ⊆ Q E\setminus P=(P\cup Q)\setminus P\subseteq Q E ∖ P = ( P ∪ Q ) ∖ P ⊆ Q
(a) Let p ∈ P ∖ { f } p\in P\setminus\{f\} p ∈ P ∖ { f } q ∈ Q ∪ { f } q\in Q\cup\{f\} q ∈ Q ∪ { f } q < 1 p q<_{1}p q < 1 p q < 2 p q<_{2}p q < 2 p p < 2 q p<_{2}q p < 2 q
Indeed, assume the contrary. Thus, we have either q < 2 p q<_{2}p q < 2 p p < 2 q p<_{2}q p < 2 q q < 1 p q<_{1}p q < 1 p p ∈ P ∖ { f } ⊆ P p\in P\setminus\{f\}\subseteq P p ∈ P ∖ { f } ⊆ P q ∈ Q q\in Q q ∈ Q q ∈ Q q\in Q q ∈ Q q = f q=f q = f q ∈ Q ∪ { f } q\in Q\cup\{f\} q ∈ Q ∪ { f } q ∈ Q ) . H e n c e , q\in Q). Hence, q ∈ Q ) . H e n ce , p > 1 f p>_{1}f p > 1 f π ( p ) ≤ π ( f ) \pi(p)\le\pi(f) π ( p ) ≤ π ( f ) π ∣ P \pi|_{P} π ∣ P ( P , > 1 , < 2 ) (P,>_{1},<_{2}) ( P , > 1 , < 2 ) f f f p p p P P P
Now, recall that we have either q < 2 p q<_{2}p q < 2 p p < 2 q p<_{2}q p < 2 q q = f q=f q = f f < 2 p f<_{2}p f < 2 p p < 2 f p<_{2}f p < 2 f p < 2 f p<_{2}f p < 2 f p < 2 f p <_{2} f p < 2 f (18) (applied to h = p h=p h = p π ( f ) < π ( p ) \pi(f)<\pi(p) π ( f ) < π ( p ) π ( p ) ≤ π ( f ) \pi(p)\leq\pi(f) π ( p ) ≤ π ( f ) f < 2 p f<_{2}p f < 2 p
But π ∣ P \pi|_{P} π ∣ P ( P , > 1 , < 2 ) (P,>_{1},<_{2}) ( P , > 1 , < 2 ) π ( p ) < π ( f ) \pi(p)<\pi(f) π ( p ) < π ( f ) p > 1 f p>_{1}f p > 1 f f < 2 p f<_{2}p f < 2 p p p p f f f P P P (17) (applied to h = p h=p h = p π ( f ) ≤ π ( p ) \pi(f)\leq\pi(p) π ( f ) ≤ π ( p ) π ( p ) < π ( f ) ≤ π ( p ) \pi(p)<\pi(f)\leq\pi(p) π ( p ) < π ( f ) ≤ π ( p )
(b) Assume that π ∣ Q \pi|_{Q} π ∣ Q ( Q , < 1 , < 2 ) (Q,<_{1},<_{2}) ( Q , < 1 , < 2 ) π ∣ Q ∪ { f } \pi|_{Q\cup\{f\}} π ∣ Q ∪ { f } ( Q ∪ { f } , < 1 , < 2 ) (Q\cup\{f\},<_{1},<_{2}) ( Q ∪ { f } , < 1 , < 2 )
Claim 1: Every a ∈ Q ∪ { f } a\in Q\cup\{f\} a ∈ Q ∪ { f } b ∈ Q ∪ { f } b\in Q\cup\{f\} b ∈ Q ∪ { f } a < 1 b a<_{1}b a < 1 b π ( a ) ≤ π ( b ) \pi(a)\leq\pi(b) π ( a ) ≤ π ( b )
Claim 2: Every a ∈ Q ∪ { f } a\in Q\cup\{f\} a ∈ Q ∪ { f } b ∈ Q ∪ { f } b\in Q\cup\{f\} b ∈ Q ∪ { f } a < 1 b a<_{1}b a < 1 b b < 2 a b<_{2}a b < 2 a π ( a ) < π ( b ) \pi(a)<\pi(b) π ( a ) < π ( b )
Proof of Claim 1: Let a ∈ Q ∪ { f } a\in Q\cup\{f\} a ∈ Q ∪ { f } b ∈ Q ∪ { f } b\in Q\cup\{f\} b ∈ Q ∪ { f } a < 1 b a<_{1}b a < 1 b π ( a ) ≤ π ( b ) \pi(a)\leq\pi(b) π ( a ) ≤ π ( b ) a = f a=f a = f (17) (applied to h = b h=b h = b a ≠ f a\neq f a = f a ∈ Q a\in Q a ∈ Q a ∈ Q ∪ { f } a\in Q\cup\{f\} a ∈ Q ∪ { f } b ∈ P b\in P b ∈ P a < 1 b a<_{1}b a < 1 b (16) (applied to p = b p=b p = b q = a q=a q = a b ∈ P b\in P b ∈ P b ∈ E ∖ P ⊆ Q b\in E\setminus P\subseteq Q b ∈ E ∖ P ⊆ Q π ( a ) ≤ π ( b ) \pi(a)\leq\pi(b) π ( a ) ≤ π ( b ) π ∣ Q \pi|_{Q} π ∣ Q ( Q , < 1 , < 2 ) (Q,<_{1},<_{2}) ( Q , < 1 , < 2 ) a ∈ Q a\in Q a ∈ Q b ∈ Q b\in Q b ∈ Q a < 1 b a<_{1}b a < 1 b
Proof of Claim 2: Let a ∈ Q ∪ { f } a\in Q\cup\{f\} a ∈ Q ∪ { f } b ∈ Q ∪ { f } b\in Q\cup\{f\} b ∈ Q ∪ { f } a < 1 b a<_{1}b a < 1 b b < 2 a b<_{2}a b < 2 a π ( a ) < π ( b ) \pi(a)<\pi(b) π ( a ) < π ( b ) a = f a=f a = f (18) (applied to h = b h=b h = b a = f a=f a = f b < 2 a = f b<_{2}a=f b < 2 a = f a ≠ f a\neq f a = f a ∈ Q a\in Q a ∈ Q a ∈ Q ∪ { f } a\in Q\cup\{f\} a ∈ Q ∪ { f } b ∈ P b\in P b ∈ P a < 1 b a<_{1}b a < 1 b (16) (applied to p = b p=b p = b q = a q=a q = a b ∈ P b\in P b ∈ P b ∈ E ∖ P ⊆ Q b\in E\setminus P\subseteq Q b ∈ E ∖ P ⊆ Q π ( a ) < π ( b ) \pi(a)<\pi(b) π ( a ) < π ( b ) π ∣ Q \pi|_{Q} π ∣ Q ( Q , < 1 , < 2 ) (Q,<_{1},<_{2}) ( Q , < 1 , < 2 ) a ∈ Q a\in Q a ∈ Q b ∈ Q b\in Q b ∈ Q a < 1 b a<_{1}b a < 1 b b < 2 a b<_{2}a b < 2 a
Now, both Claim 1 and Claim 2 are proven. As already said, this completes the proof of Lemma 6.4 (b).
Lemma 6.5. Let E = ( E , < 1 , < 2 ) E=(E,<_{1},<_{2}) E = ( E , < 1 , < 2 ) ∣ E ∣ > 0 |E|>0 ∣ E ∣ > 0 π : E → { 1 , 2 , 3 , … } \pi:E\to\{1,2,3,\ldots\} π : E → { 1 , 2 , 3 , … } > 1 >_{1} > 1 < 1 <_{1} < 1
∑ ( P , Q ) ∈ Adm E ; π ∣ P is a ( P , > 1 , < 2 ) -partition ; π ∣ Q is a ( Q , < 1 , < 2 ) -partition ( − 1 ) ∣ P ∣ = 0. (19) \sum_{\substack{(P,Q)\in\operatorname{Adm} E;\\
\pi|_{P}\text{ is a }(P,>_{1},<_{2})\text{-partition};\\
\pi|_{Q}\text{ is a }(Q,<_{1},<_{2})\text{-partition}}}
(-1)^{|P|}=0. \tag*{(19)} ( P , Q ) ∈ Adm E ; π ∣ P is a ( P , > 1 , < 2 ) -partition ; π ∣ Q is a ( Q , < 1 , < 2 ) -partition ∑ ( − 1 ) ∣ P ∣ = 0. (19) Proof of Lemma 6.5. Our goal is to prove (19) . To do so, we denote by Z Z Z ( P , Q ) ∈ Adm E (P,Q)\in\operatorname{Adm} E ( P , Q ) ∈ Adm E π ∣ P \pi|_{P} π ∣ P ( P , > 1 , < 2 ) (P,>_{1},<_{2}) ( P , > 1 , < 2 ) π ∣ Q \pi|_{Q} π ∣ Q ( Q , < 1 , < 2 ) (Q,<_{1},<_{2}) ( Q , < 1 , < 2 ) T : Z → Z T:Z\to Z T : Z → Z Z Z Z Property P: Let ( P , Q ) ∈ Z (P,Q) \in Z ( P , Q ) ∈ Z T ( ( P , Q ) ) T((P,Q)) T (( P , Q )) ( P ′ , Q ′ ) (P',Q') ( P ′ , Q ′ ) ( − 1 ) ∣ P ′ ∣ = − ( − 1 ) ∣ P ∣ (-1)^{|P'|} = -(-1)^{|P|} ( − 1 ) ∣ P ′ ∣ = − ( − 1 ) ∣ P ∣
Once such an involution T T T 24 T T T
The definition of the map T : Z → Z T: Z \to Z T : Z → Z F F F E E E e ∈ E e \in E e ∈ E π ( e ) \pi(e) π ( e ) F F F 25 ( E , < 2 ) (E,<_{2}) ( E , < 2 ) 26 f f f f f f g ∈ F g \in F g ∈ F g < 2 f g <_{2} f g < 2 f f f f T T T ( P , Q ) ∈ Z (P,Q) \in Z ( P , Q ) ∈ Z
{ ( P ∪ { f } , Q ∖ { f } ) , if f ∉ P ; ( P ∖ { f } , Q ∪ { f } ) , if f ∈ P . \begin{cases}
(P \cup\{f\}, Q \setminus\{f\}), & \text{if } f \notin P; \\
(P \setminus\{f\}, Q \cup\{f\}), & \text{if } f \in P.
\end{cases} { ( P ∪ { f } , Q ∖ { f }) , ( P ∖ { f } , Q ∪ { f }) , if f ∈ / P ; if f ∈ P . In order to prove that the map T T T Z Z Z
\begin{cases}
(P \cup\{f\}, Q \setminus\{f\}), & \text{if } f \notin P; \\
(P \setminus\{f\}, Q \cup\{f\}), & \text{if } f \in P
\end{cases}
\in Z \tag*{(20)}\end{cases}
for every ( P , Q ) ∈ Z (P,Q) \in Z ( P , Q ) ∈ Z
Proof of (20): Fix ( P , Q ) ∈ Z (P,Q) \in Z ( P , Q ) ∈ Z ( P , Q ) (P,Q) ( P , Q ) Adm E \operatorname{Adm} E Adm E π ∣ P \pi|_P π ∣ P ( P , > 1 , < 2 ) (P,>_{1},<_{2}) ( P , > 1 , < 2 ) π ∣ Q \pi|_Q π ∣ Q ( Q , < 1 , < 2 ) (Q,<_{1},<_{2}) ( Q , < 1 , < 2 ) Z Z Z
From ( P , Q ) ∈ Adm E (P,Q) \in\operatorname{Adm} E ( P , Q ) ∈ Adm E P ∩ Q = ∅ P \cap Q = \varnothing P ∩ Q = ∅ P ∪ Q = E P \cup Q = E P ∪ Q = E
no p ∈ P and q ∈ Q satisfy q < 1 p . (21) \text{no } p \in P \text{ and } q \in Q \text{ satisfy } q <_{1} p. \tag*{(21)} no p ∈ P and q ∈ Q satisfy q < 1 p . (21) We know that f f f F F F E E E e ∈ E e \in E e ∈ E π ( e ) \pi(e) π ( e )
π ( f ) ≤ π ( h ) for every h ∈ E . (22) \pi(f) \leq\pi(h) \qquad\text{for every } h \in E. \tag*{(22)} π ( f ) ≤ π ( h ) for every h ∈ E . (22) Moreover,
π ( f ) < π ( h ) for every h ∈ E satisfying h < 2 f (23) \pi(f) < \pi(h) \qquad\text{for every } h \in E \text{ satisfying } h <_{2} f \tag*{(23)} π ( f ) < π ( h ) for every h ∈ E satisfying h < 2 f (23) We need to prove (20) . We are in one of the following two cases:
Case 1: We have f ∈ P f \in P f ∈ P
Case 2: We have f ∉ P f \notin P f ∈ / P
Let us first consider Case 1. In this case, we have f ∈ P f \in P f ∈ P
Recall that P ∩ Q = ∅ P \cap Q = \varnothing P ∩ Q = ∅ P ∪ Q = E P \cup Q = E P ∪ Q = E ( P ∖ { f } ) ∩ ( Q ∪ { f } ) = ∅ (P \setminus\{f\}) \cap(Q \cup\{f\}) = \varnothing ( P ∖ { f }) ∩ ( Q ∪ { f }) = ∅ ( P ∖ { f } ) ∪ ( Q ∪ { f } ) = E (P \setminus\{f\}) \cup(Q \cup\{f\}) = E ( P ∖ { f }) ∪ ( Q ∪ { f }) = E
Furthermore, there exist no p ∈ P ∖ { f } p \in P \setminus\{f\} p ∈ P ∖ { f } q ∈ Q ∪ { f } q \in Q \cup\{f\} q ∈ Q ∪ { f } q q q < 1 <_{1} < 1 p p p 27 P ∖ { f } P \setminus\{f\} P ∖ { f } Q ∪ { f } Q \cup\{f\} Q ∪ { f } P P P Q Q Q ( P ∖ { f } , Q ∪ { f } ) ∈ Adm E (P \setminus\{f\}, Q \cup\{f\}) \in\operatorname{Adm} E ( P ∖ { f } , Q ∪ { f }) ∈ Adm E
Furthermore, π ∣ P \pi\mathbin{|}_{P} π ∣ P ( P , > 1 , < 2 ) (P, >_{1}, <_{2}) ( P , > 1 , < 2 ) π ∣ P ∖ { f } \pi\mathbin{|}_{P \setminus\{f\}} π ∣ P ∖ { f } ( P ∖ { f } , > 1 , < 2 ) (P \setminus\{f\}, >_{1}, <_{2}) ( P ∖ { f } , > 1 , < 2 ) P ∖ { f } ⊆ P P \setminus\{f\} \subseteq P P ∖ { f } ⊆ P
Furthermore, π ∣ Q ∪ { f } \pi\mathbin{|}_{Q \cup\{f\}} π ∣ Q ∪ { f } ( Q ∪ { f } , < 1 , < 2 ) (Q \cup\{f\}, <_{1}, <_{2}) ( Q ∪ { f } , < 1 , < 2 ) 28
Altogether, we now know that ( P ∖ { f } , Q ∪ { f } ) ∈ Adm E (P \setminus\{f\}, Q \cup\{f\}) \in\operatorname{Adm} E ( P ∖ { f } , Q ∪ { f }) ∈ Adm E π ∣ P ∖ { f } \pi\mathbin{|}_{P \setminus\{f\}} π ∣ P ∖ { f } ( P ∖ { f } , > 1 , < 2 ) (P \setminus\{f\}, >_{1}, <_{2}) ( P ∖ { f } , > 1 , < 2 ) π ∣ Q ∪ { f } \pi\mathbin{|}_{Q \cup\{f\}} π ∣ Q ∪ { f } ( Q ∪ { f } , < 1 , < 2 ) (Q \cup\{f\}, <_{1}, <_{2}) ( Q ∪ { f } , < 1 , < 2 ) ( P ∖ { f } , Q ∪ { f } ) ∈ Z (P \setminus\{f\}, Q \cup\{f\}) \in Z ( P ∖ { f } , Q ∪ { f }) ∈ Z Z Z Z
{ ( P ∪ { f } , Q ∖ { f } ) , if f ∉ P ; ( P ∖ { f } , Q ∪ { f } ) , if f ∈ P = ( P ∖ { f } , Q ∪ { f } ) (since f ∈ P ) \begin{cases}
(P \cup\{f\}, Q \setminus\{f\}), & \text{if } f \notin P;\\
(P \setminus\{f\}, Q \cup\{f\}), & \text{if } f \in P
\end{cases}
= (P \setminus\{f\}, Q \cup\{f\}) \quad\text{(since } f \in P\text{)} { ( P ∪ { f } , Q ∖ { f }) , ( P ∖ { f } , Q ∪ { f }) , if f ∈ / P ; if f ∈ P = ( P ∖ { f } , Q ∪ { f }) (since f ∈ P ) Hence, (20) is proven in Case 1.
Let us next consider Case 2. In this case, we have f ∉ P f \notin P f ∈ / P f ∈ E ∖ P = Q f \in E \setminus P = Q f ∈ E ∖ P = Q P ∩ Q = ∅ P \cap Q = \varnothing P ∩ Q = ∅ P ∪ Q = E P \cup Q = E P ∪ Q = E
Recall that P ∩ Q = ∅ P \cap Q = \varnothing P ∩ Q = ∅ P ∪ Q = E P \cup Q = E P ∪ Q = E ( P ∪ { f } ) ∩ ( Q ∖ { f } ) = ∅ (P \cup\{f\}) \cap(Q \setminus\{f\}) = \varnothing ( P ∪ { f }) ∩ ( Q ∖ { f }) = ∅ ( P ∪ { f } ) ∪ ( Q ∖ { f } ) = E (P \cup\{f\}) \cup(Q \setminus\{f\}) = E ( P ∪ { f }) ∪ ( Q ∖ { f }) = E
We have f ∈ Q f \in Q f ∈ Q Q ∪ P = P ∪ Q = E Q \cup P = P \cup Q = E Q ∪ P = P ∪ Q = E > 1 >_{1} > 1 < 1 <_{1} < 1 < 1 <_{1} < 1 ( E , > 1 , < 2 ) (E, >_{1}, <_{2}) ( E , > 1 , < 2 ) < 1 <_{1} < 1 > 1 >_1 > 1 > 1 >_1 > 1 < 1 <_1 < 1 π ∣ Q \pi\mathbin{|}_Q π ∣ Q ( Q , < 1 , < 2 ) (Q,<_{1},<_{2}) ( Q , < 1 , < 2 )
no p ∈ Q and q ∈ P satisfy q > 1 p (24) \text{no }p\in Q\text{ and }q\in P\text{ satisfy }q>_{1}p \tag*{(24)} no p ∈ Q and q ∈ P satisfy q > 1 p (24) 30 ( E , > 1 , < 2 ) (E,>_{1},<_{2}) ( E , > 1 , < 2 ) < 1 <_{1} < 1 Q Q Q P P P ( E , < 1 , < 2 ) (E,<_{1},<_{2}) ( E , < 1 , < 2 ) > 1 >_{1} > 1 P P P Q Q Q
There exist no p ∈ P ∪ { f } p\in P\cup\{f\} p ∈ P ∪ { f } q ∈ Q ∖ { f } q\in Q\setminus\{f\} q ∈ Q ∖ { f } q q q < 1 <_{1} < 1 p p p 31 P ∪ { f } P\cup\{f\} P ∪ { f } Q ∖ { f } Q\setminus\{f\} Q ∖ { f } P P P Q Q Q ( P ∪ { f } , Q ∖ { f } ) ∈ Adm E (P\cup\{f\},Q\setminus\{f\})\in\operatorname{Adm}E ( P ∪ { f } , Q ∖ { f }) ∈ Adm E
Furthermore, π ∣ Q \pi\mathbin{|}_Q π ∣ Q ( Q , < 1 , < 2 ) (Q,<_{1},<_{2}) ( Q , < 1 , < 2 ) π ∣ Q ∖ { f } \pi\mathbin{|}_{Q\setminus\{f\}} π ∣ Q ∖ { f } ( Q ∖ { f } , < 1 , < 2 ) (Q\setminus\{f\},<_{1},<_{2}) ( Q ∖ { f } , < 1 , < 2 ) Q ∖ { f } ⊆ Q Q\setminus\{f\}\subseteq Q Q ∖ { f } ⊆ Q
Furthermore, π ∣ P ∪ { f } \pi\mathbin{|}_{P\cup\{f\}} π ∣ P ∪ { f } ( P ∪ { f } , > 1 , < 2 ) (P\cup\{f\},>_{1},<_{2}) ( P ∪ { f } , > 1 , < 2 ) 32
Altogether, we now know that ( P ∪ { f } , Q ∖ { f } ) ∈ Adm E (P\cup\{f\},Q\setminus\{f\})\in\operatorname{Adm}E ( P ∪ { f } , Q ∖ { f }) ∈ Adm E π ∣ P ∪ { f } \pi\mathbin{|}_{P\cup\{f\}} π ∣ P ∪ { f } ( P ∪ { f } , > 1 , < 2 ) (P\cup\{f\},>_{1},<_{2}) ( P ∪ { f } , > 1 , < 2 ) π ∣ Q ∖ { f } \pi\mathbin{|}_{Q\setminus\{f\}} π ∣ Q ∖ { f } ( Q ∖ { f } , < 1 , < 2 ) (Q\setminus\{f\},<_{1},<_{2}) ( Q ∖ { f } , < 1 , < 2 ) ( P ∪ { f } , Q ∖ { f } ) ∈ Z (P\cup\{f\},Q\setminus\{f\})\in Z ( P ∪ { f } , Q ∖ { f }) ∈ Z Z Z Z
{ ( P ∪ { f } , Q ∖ { f } ) , if f ∉ P ; ( P ∖ { f } , Q ∪ { f } ) , if f ∈ P = ( P ∪ { f } , Q ∖ { f } ) (since f ∉ P ) ∈ Z . \begin{cases}
(P\cup\{f\},Q\setminus\{f\}), & \text{if }f\notin P;\\
(P\setminus\{f\},Q\cup\{f\}), & \text{if }f\in P
\end{cases}
=(P\cup\{f\},Q\setminus\{f\})\quad\text{(since }f\notin P\text{)}
\in Z. { ( P ∪ { f } , Q ∖ { f }) , ( P ∖ { f } , Q ∪ { f }) , if f ∈ / P ; if f ∈ P = ( P ∪ { f } , Q ∖ { f }) (since f ∈ / P ) ∈ Z . Hence, (20) is proven in Case 2.
We have now proven (20) in both Cases 1 and 2. Thus, (20) always holds. In other words, the map T T T
What the map T T T ( P , Q ) ∈ Z (P,Q)\in Z ( P , Q ) ∈ Z f f f P P P Q Q Q T T T ( P , Q ) ∈ Z (P,Q)\in Z ( P , Q ) ∈ Z T ( ( P , Q ) ) T((P,Q)) T (( P , Q )) ( P ′ , Q ′ ) (P',Q') ( P ′ , Q ′ )
( − 1 ) ∣ P ′ ∣ = − ( − 1 ) ∣ P ∣ (-1)^{|P'|}=-(-1)^{|P|} ( − 1 ) ∣ P ′ ∣ = − ( − 1 ) ∣ P ∣ (because P ′ = { P ∪ { f } , if f ∉ P ; P ∖ { f } , if f ∈ P P'=\begin{cases}P\cup\{f\},&\text{if }f\notin P;\\P\setminus\{f\},&\text{if }f\in P\end{cases} P ′ = { P ∪ { f } , P ∖ { f } , if f ∈ / P ; if f ∈ P ∣ P ′ ∣ = ∣ P ∣ ± 1 |P'|=|P|\pm1 ∣ P ′ ∣ = ∣ P ∣ ± 1
Now, forget that we fixed a a a b b b a ∈ Q a\in Q a ∈ Q b ∈ P b\in P b ∈ P b > 1 a b>_{1}a b > 1 a a ∈ Q a\in Q a ∈ Q b ∈ P b\in P b ∈ P b > 1 a b>_{1}a b > 1 a a a a b b b p p p q q q p ∈ Q p\in Q p ∈ Q q ∈ P q\in P q ∈ P q > 1 p q>_{1}p q > 1 p
We know that q q q < 1 <_{1} < 1 p p p q < 1 p q<_{1}p q < 1 p p > 1 q p>_{1}q p > 1 q ( E , > 1 , < 2 ) (E,>_{1},<_{2}) ( E , > 1 , < 2 ) < 1 <_{1} < 1 Q Q Q P P P q q q p p p ( E , < 1 , < 2 ) (E,<_{1},<_{2}) ( E , < 1 , < 2 ) > 1 >_{1} > 1 P P P Q Q Q p p p q q q p < 2 q p<_{2}q p < 2 q q < 2 p q<_{2}p q < 2 p q q q < 1 <_{1} < 1 p p p q q q p p p < 2 <_{2} < 2 E E E q < 2 p q<_{2}p q < 2 p q = p q=p q = p p < 2 q p<_{2}q p < 2 q q = p q=p q = p p < 2 q p<_{2}q p < 2 q q < 2 p q<_{2}p q < 2 p q < 1 p q<_{1}p q < 1 p T T T (19) . Hence, Lemma 6.5 is proven.
Proof of Theorem 4.2 . We shall prove Theorem 4.2 by strong induction over ∣ E ∣ |E| ∣ E ∣ E = ( E , < 1 , < 2 ) \mathbf{E}=(E,<_{1},<_{2}) E = ( E , < 1 , < 2 ) w : E → { 1 , 2 , 3 , … } w:E\to\{1,2,3,\ldots\} w : E → { 1 , 2 , 3 , … } Theorem 4.2 is proven for all tertispecial double posets of smaller size33
S ( Γ ( ( E , < 1 , < 2 ) , w ) ) = ( − 1 ) ∣ E ∣ Γ ( ( E , > 1 , < 2 ) , w ) . S\left(\Gamma\left((E,<_{1},<_{2}),w\right)\right)=(-1)^{|E|}\Gamma\left((E,>_{1},<_{2}),w\right). S ( Γ ( ( E , < 1 , < 2 ) , w ) ) = ( − 1 ) ∣ E ∣ Γ ( ( E , > 1 , < 2 ) , w ) . Here, as usual, > 1 >_{1} > 1 < 1 <_{1} < 1
If E = ∅ E=\varnothing E = ∅ 34 E ≠ ∅ E\ne\varnothing E = ∅ ∣ E ∣ > 0 |E|>0 ∣ E ∣ > 0 Lemma 6.3 (b) shows that ε ( Γ ( E , w ) ) = 0 \varepsilon(\Gamma(E,w))=0 ε ( Γ ( E , w )) = 0
u ( ε ( Γ ( E , w ) ) ⏟ = 0 ) = u ( 0 ) = 0. u\left(\underbrace{\varepsilon(\Gamma(E,w))}_{=0}\right)=u(0)=0. u = 0 ε ( Γ ( E , w )) = u ( 0 ) = 0. The upper commutative pentagon of (2) shows that u ∘ ε = m ∘ ( S ⊗ id ) ∘ Δ u\circ\varepsilon=m\circ(S\otimes\operatorname{id})\circ\Delta u ∘ ε = m ∘ ( S ⊗ id ) ∘ Δ Γ ( E , w ) \Gamma(E,w) Γ ( E , w ) ( u ∘ ε ) ( Γ ( E , w ) ) = ( m ∘ ( S ⊗ id ) ∘ Δ ) ( Γ ( E , w ) ) (u\circ\varepsilon)(\Gamma(E,w))=(m\circ(S\otimes\operatorname{id})\circ\Delta)(\Gamma(E,w)) ( u ∘ ε ) ( Γ ( E , w )) = ( m ∘ ( S ⊗ id ) ∘ Δ ) ( Γ ( E , w )) ( u ∘ ε ) ( Γ ( E , w ) ) = 0 (u\circ\varepsilon)(\Gamma(E,w))=0 ( u ∘ ε ) ( Γ ( E , w )) = 0
0 = ( m ∘ ( S ⊗ id ) ∘ Δ ) ( Γ ( E , w ) ) = m ( ( S ⊗ id ) ( Δ ( Γ ( E , w ) ) ) ) = m ( ( S ⊗ id ) ( ∑ ( P , Q ) ∈ Adm E Γ ( E ∣ P , w ∣ P ) ⊗ Γ ( E ∣ Q , w ∣ Q ) ) ) (by (10)) = m ( ∑ ( P , Q ) ∈ Adm E S ( Γ ( E ∣ P , w ∣ P ) ) ⊗ Γ ( E ∣ Q , w ∣ Q ) ) = ∑ ( P , Q ) ∈ Adm E S ( Γ ( E ∣ P , w ∣ P ) ) Γ ( E ∣ Q , w ∣ Q ) = S ( Γ ( E ∣ E , w ∣ E ) ) Γ ( E ∣ ∅ , w ∣ ∅ ) + ∑ ( P , Q ) ∈ Adm E ; ∣ P ∣ < ∣ E ∣ S ( Γ ( E ∣ P , w ∣ P ) ) Γ ( E ∣ Q , w ∣ Q ) . (25) \begin{aligned}
0=(m\circ(S\otimes\operatorname{id})\circ\Delta)(\Gamma(E,w))=m\left((S\otimes\operatorname{id})(\Delta(\Gamma(E,w)))\right) \\
&=m\left((S\otimes\operatorname{id})\left(\sum_{(P,Q)\in\operatorname{Adm}E}\Gamma(E|_{P},w|_{P})\otimes\Gamma(E|_{Q},w|_{Q})\right)\right)\qquad\text{(by (10))} \\
&=m\left(\sum_{(P,Q)\in\operatorname{Adm}E}S(\Gamma(E|_{P},w|_{P}))\otimes\Gamma(E|_{Q},w|_{Q})\right) \\
&=\sum_{(P,Q)\in\operatorname{Adm}E}S(\Gamma(E|_{P},w|_{P}))\Gamma(E|_{Q},w|_{Q}) \\
&=S(\Gamma(E|_{E},w|_{E}))\Gamma(E|_{\varnothing},w|_{\varnothing})+
\sum_{\substack{(P,Q)\in\operatorname{Adm}E;\\|P|<|E|}}
S(\Gamma(E|_{P},w|_{P}))\Gamma(E|_{Q},w|_{Q}). \tag*{(25)}
\end{aligned} 0 = ( m ∘ ( S ⊗ id ) ∘ Δ ) ( Γ ( E , w )) = m ( ( S ⊗ id ) ( Δ ( Γ ( E , w ))) ) = m ( S ⊗ id ) ( P , Q ) ∈ Adm E ∑ Γ ( E ∣ P , w ∣ P ) ⊗ Γ ( E ∣ Q , w ∣ Q ) (by (10)) = m ( P , Q ) ∈ Adm E ∑ S ( Γ ( E ∣ P , w ∣ P )) ⊗ Γ ( E ∣ Q , w ∣ Q ) = ( P , Q ) ∈ Adm E ∑ S ( Γ ( E ∣ P , w ∣ P )) Γ ( E ∣ Q , w ∣ Q ) = S ( Γ ( E ∣ E , w ∣ E )) Γ ( E ∣ ∅ , w ∣ ∅ ) + ( P , Q ) ∈ Adm E ; ∣ P ∣ < ∣ E ∣ ∑ S ( Γ ( E ∣ P , w ∣ P )) Γ ( E ∣ Q , w ∣ Q ) . (25) (since the only pair ( P , Q ) ∈ Adm E (P,Q)\in\operatorname{Adm}E ( P , Q ) ∈ Adm E ∣ P ∣ ≥ ∣ E ∣ |P|\ge|E| ∣ P ∣ ≥ ∣ E ∣ ( E , ∅ ) (E,\varnothing) ( E , ∅ ) ( P , Q ) ∈ Adm E (P,Q)\in\operatorname{Adm}E ( P , Q ) ∈ Adm E ∣ P ∣ < ∣ E ∣ |P|<|E| ∣ P ∣ < ∣ E ∣
But whenever ( P , Q ) ∈ Adm E (P,Q)\in\operatorname{Adm}E ( P , Q ) ∈ Adm E ∣ P ∣ < ∣ E ∣ |P|<|E| ∣ P ∣ < ∣ E ∣ E ∣ P = ( P , < 1 , < 2 ) E|_{P}=(P,<_{1},<_{2}) E ∣ P = ( P , < 1 , < 2 ) Lemma 6.2 ), and therefore we have S ( Γ ( E ∣ P , w ∣ P ) ) = S ( Γ ( ( P , < 1 , < 2 ) , w ∣ P ) ) = ( − 1 ) ∣ P ∣ Γ ( ( P , > 1 , < 2 ) , w ∣ P ) S(\Gamma(E|_{P},w|_{P}))=S(\Gamma((P,<_{1},<_{2}),w|_{P}))=(-1)^{|P|}\Gamma((P,>_{1},<_{2}),w|_{P}) S ( Γ ( E ∣ P , w ∣ P )) = S ( Γ (( P , < 1 , < 2 ) , w ∣ P )) = ( − 1 ) ∣ P ∣ Γ (( P , > 1 , < 2 ) , w ∣ P )
0 = S ( Γ ( E ∣ E , w ∣ E ⏟ = E ) ) Γ ( E ∣ ∅ , w ∣ ∅ ) ⏟ = Γ ( ( ∅ , < 1 , < 2 ) , w ∣ ∅ ) = 1 (by Lemma 6.3 (a)) + ∑ ( P , Q ) ∈ Adm E ; ∣ P ∣ < ∣ E ∣ S ( Γ ( E ∣ P , w ∣ P ) ) = ( − 1 ) ∣ P ∣ Γ ( ( P , > 1 , < 2 ) , w ∣ P ) ⏟ Γ ( E ∣ Q , w ∣ Q ) = S ( Γ ( E , w ) ) + ∑ ( P , Q ) ∈ Adm E ; ∣ P ∣ < ∣ E ∣ ( − 1 ) ∣ P ∣ Γ ( ( P , > 1 , < 2 ) , w ∣ P ) Γ ( E ∣ Q , w ∣ Q ) . \begin{aligned}
0={}&S\left(\Gamma\left(\underbrace{\mathrm{E}|_{E},w|_{E}}_{=\mathrm{E}} \right)\right)\underbrace{\Gamma\left(\mathrm{E}|_{\varnothing},w|_{\varnothing}\right)}_{=\Gamma((\varnothing,<_{1},<_{2}),w|_{\varnothing})=1\\ \text{(by Lemma 6.3 (a))}}\\
&+\sum_{\substack{(P,Q)\in\operatorname{Adm}\mathrm{E};\\ |P|<|\mathrm{E}|}} \frac{S\left(\Gamma(\mathrm{E}|_{P},w|_{P})\right)}{\underbrace{=(-1)^{|P|}\Gamma((P,>_{1},<_{2}),w|_{P})}} \Gamma(\mathrm{E}|_{Q},w|_{Q})\\
={}&S(\Gamma(\mathrm{E},w))+\sum_{\substack{(P,Q)\in\operatorname{Adm}\mathrm{E};\\ |P|<|\mathrm{E}|}}(-1)^{|P|}\Gamma((P,>_{1},<_{2}),w|_{P})\Gamma(\mathrm{E}|_{Q},w|_{Q}).
\end{aligned} 0 = = S Γ = E E ∣ E , w ∣ E = Γ (( ∅ , < 1 , < 2 ) , w ∣ ∅ ) = 1 (by Lemma 6.3 (a)) Γ ( E ∣ ∅ , w ∣ ∅ ) + ( P , Q ) ∈ Adm E ; ∣ P ∣ < ∣ E ∣ ∑ = ( − 1 ) ∣ P ∣ Γ (( P , > 1 , < 2 ) , w ∣ P ) S ( Γ ( E ∣ P , w ∣ P ) ) Γ ( E ∣ Q , w ∣ Q ) S ( Γ ( E , w )) + ( P , Q ) ∈ Adm E ; ∣ P ∣ < ∣ E ∣ ∑ ( − 1 ) ∣ P ∣ Γ (( P , > 1 , < 2 ) , w ∣ P ) Γ ( E ∣ Q , w ∣ Q ) . Thus,
S ( Γ ( E , w ) ) = − ∑ ( P , Q ) ∈ Adm E ; ∣ P ∣ < ∣ E ∣ ( − 1 ) ∣ P ∣ Γ ( ( P , > 1 , < 2 ) , w ∣ P ) Γ ( E ∣ Q , w ∣ Q ) . (26) S(\Gamma(\mathrm{E},w))=-\sum_{\substack{(P,Q)\in\operatorname{Adm}\mathrm{E};\\ |P|<|\mathrm{E}|}}(-1)^{|P|}\Gamma((P,>_{1},<_{2}),w|_{P})\Gamma(\mathrm{E}|_{Q},w|_{Q}). \tag*{(26)} S ( Γ ( E , w )) = − ( P , Q ) ∈ Adm E ; ∣ P ∣ < ∣ E ∣ ∑ ( − 1 ) ∣ P ∣ Γ (( P , > 1 , < 2 ) , w ∣ P ) Γ ( E ∣ Q , w ∣ Q ) . (26) For every subset P P P E E E
Γ ( ( P , > 1 , < 2 ) , w ∣ P ) = ∑ π is a ( P , > 1 , < 2 ) -partition x π , w ∣ P (by the definition of Γ ( ( P , > 1 , < 2 ) , w ∣ P ) ) = ∑ σ is a ( P , > 1 , < 2 ) -partition x σ , w ∣ P . (27) \begin{aligned}
\Gamma((P,>_{1},<_{2}),w|_{P})
&=\sum_{\pi\ \text{is a }(P,>_{1},<_{2})\text{-partition}}\mathbf{x}_{\pi,w|_{P}}\\
&\hspace{1cm}\text{(by the definition of }\Gamma((P,>_{1},<_{2}),w|_{P})\text{)}\\
&=\sum_{\sigma\ \text{is a }(P,>_{1},<_{2})\text{-partition}}\mathbf{x}_{\sigma,w|_{P}}. \tag*{(27)}
\end{aligned} Γ (( P , > 1 , < 2 ) , w ∣ P ) = π is a ( P , > 1 , < 2 ) -partition ∑ x π , w ∣ P (by the definition of Γ (( P , > 1 , < 2 ) , w ∣ P ) ) = σ is a ( P , > 1 , < 2 ) -partition ∑ x σ , w ∣ P . (27) (here, we have renamed the summation index π \pi π σ \sigma σ
For every subset Q Q Q E E E
Γ ( E ∣ Q ⏟ = ( Q , < 1 , < 2 ) , w ∣ Q ) = Γ ( ( Q , < 1 , < 2 ) , w ∣ Q ) = ∑ π is a ( Q , < 1 , < 2 ) -partition x π , w ∣ Q (by the definition of Γ ( ( Q , < 1 , < 2 ) , w ∣ Q ) ) = ∑ τ is a ( Q , < 1 , < 2 ) -partition x τ , w ∣ Q . (28) \begin{aligned}
\Gamma\left(\underbrace{\mathrm{E}|_{Q}}_{=(Q,<_{1},<_{2})},w|_{Q}\right)
&=\Gamma((Q,<_{1},<_{2}),w|_{Q})\\
&=\sum_{\pi\ \text{is a }(Q,<_{1},<_{2})\text{-partition}}\mathbf{x}_{\pi,w|_{Q}}\\
&\hspace{1cm}\text{(by the definition of }\Gamma((Q,<_{1},<_{2}),w|_{Q})\text{)}\\
&=\sum_{\tau\ \text{is a }(Q,<_{1},<_{2})\text{-partition}}\mathbf{x}_{\tau,w|_{Q}}. \tag*{(28)}
\end{aligned} Γ = ( Q , < 1 , < 2 ) E ∣ Q , w ∣ Q = Γ (( Q , < 1 , < 2 ) , w ∣ Q ) = π is a ( Q , < 1 , < 2 ) -partition ∑ x π , w ∣ Q (by the definition of Γ (( Q , < 1 , < 2 ) , w ∣ Q ) ) = τ is a ( Q , < 1 , < 2 ) -partition ∑ x τ , w ∣ Q . (28) (here, we have renamed the summation index π \pi π τ \tau τ
Now,
\begin{aligned}
\sum_{(P,Q)\in\operatorname{Adm} E}(-1)^{|P|}
\underbrace{\Gamma\left((P,>_1,<_{2}),w|_P\right)}_{ \sum_{\sigma\text{ is a }(P,>_1,<_{2})\text{-partition}}x_{\sigma,w|_P}\text{ (by {xref}`(27)`)}}
\underbrace{\Gamma\left(E|_Q,w|_Q\right)}_{ \sum_{\tau\text{ is a }(Q,<_{1},<_{2})\text{-partition}}x_{\tau,w|_Q}\text{ (by {xref}`(28)`)}
&=
\sum_{(P,Q)\in\operatorname{Adm} E}(-1)^{|P|}
\left(\sum_{\sigma\text{ is a }(P,>_1,<_{2})\text{-partition}}x_{\sigma,w|_P}\right)
\left(\sum_{\tau\text{ is a }(Q,<_{1},<_{2})\text{-partition}}x_{\tau,w|_Q}\right)\\
&=
\sum_{(P,Q)\in\operatorname{Adm} E}(-1)^{|P|}
\sum_{\substack{\sigma\text{ is a }(P,>_1,<_{2})\text{-partition}\\
\tau\text{ is a }(Q,<_{1},<_{2})\text{-partition}}}
x_{\sigma,w|_P}x_{\tau,w|_Q}\\
&=
\sum_{(P,Q)\in\operatorname{Adm} E}(-1)^{|P|}
\sum_{\substack{\sigma:P\to\{1,2,3,\ldots\};\\
\tau:Q\to\{1,2,3,\ldots\};\\
\sigma\text{ is a }(P,>_1,<_{2})\text{-partition};\\
\tau\text{ is a }(Q,<_{1},<_{2})\text{-partition}}}
x_{\sigma,w|_P}x_{\tau,w|_Q}\\
&=
\sum_{(P,Q)\in\operatorname{Adm} E}(-1)^{|P|}
\sum_{\substack{\pi:E\to\{1,2,3,\ldots\};\\
\pi|_P\text{ is a }(P,>_1,<_{2})\text{-partition};\\
\pi|_Q\text{ is a }(Q,<_{1},<_{2})\text{-partition}}}
\underbrace{x_{\pi|_P,w|_P}x_{\pi|_Q,w|_Q}}_{=x_{\pi,w}}\\
&\quad\left(
\begin{gathered}
\text{here, we have substituted }(\pi|_P,\pi|_Q)\text{ for }(\sigma,\tau)\text{ in the inner sum,}\\
\text{since every pair }(\sigma,\tau)\text{ consisting of a map }\sigma:P\to\{1,2,3,\ldots\}\\
\text{and a map }\tau:Q\to\{1,2,3,\ldots\}\\
\text{can be written as }(\pi|_P,\pi|_Q)\text{ for a unique }\pi:E\to\{1,2,3,\ldots\}\\
\text{(namely, for the }\pi:E\to\{1,2,3,\ldots\}\text{ that is defined to send every}\\
e\in P\text{ to }\sigma(e)\text{ and to send every }e\in Q\text{ to }\tau(e)\text{)}
\end{gathered}
\right)\\
&=
\sum_{(P,Q)\in\operatorname{Adm} E}(-1)^{|P|}
\sum_{\substack{\pi:E\to\{1,2,3,\ldots\};\\
\pi|_P\text{ is a }(P,>_1,<_{2})\text{-partition};\\
\pi|_Q\text{ is a }(Q,<_{1},<_{2})\text{-partition}}}
x_{\pi,w}\\
&=
\sum_{\pi:E\to\{1,2,3,\ldots\}}
\underbrace{\sum_{\substack{(P,Q)\in\operatorname{Adm} E;\\
\pi|_P\text{ is a }(P,>_1,<_{2})\text{-partition};\\
\pi|_Q\text{ is a }(Q,<_{1},<_{2})\text{-partition}}}
(-1)^{|P|}}_{ =0\text{ (by {xref}`(19)`)}
x_{\pi,w}
=
\sum_{\pi:E\to\{1,2,3,\ldots\}}0x_{\pi,w}
=
0.}}
Thus,
0 = ∑ ( P , Q ) ∈ Adm E ( − 1 ) ∣ P ∣ Γ ( ( P , > 1 , < 2 ) , w ∣ P ) Γ ( E ∣ Q , w ∣ Q ) = ( − 1 ) ∣ E ∣ Γ ( ( E , > 1 , < 2 ) , w ∣ E ) Γ ( E ∣ ∅ , w ∣ ∅ ) + ∑ ( P , Q ) ∈ Adm E ; ∣ P ∣ < ∣ E ∣ ( − 1 ) ∣ P ∣ Γ ( ( P , > 1 , < 2 ) , w ∣ P ) Γ ( E ∣ Q , w ∣ Q ) \begin{aligned}
0={}&\sum_{(P,Q)\in\operatorname{Adm} E}(-1)^{|P|}\Gamma\bigl((P,>_1,<_{2}),w|_P\bigr)\Gamma\bigl(E|_Q,w|_Q\bigr)\\
={}&(-1)^{|E|}\Gamma\bigl((E,>_1,<_{2}),w|_E\bigr)\Gamma\bigl(E|_{\varnothing},w|_{\varnothing}\bigr)\\
&+\sum_{\substack{(P,Q)\in\operatorname{Adm} E;\\|P|<|E|}}(-1)^{|P|}\Gamma\bigl((P,>_1,<_{2}),w|_P\bigr)\Gamma\bigl(E|_Q,w|_Q\bigr)
\end{aligned} 0 = = ( P , Q ) ∈ Adm E ∑ ( − 1 ) ∣ P ∣ Γ ( ( P , > 1 , < 2 ) , w ∣ P ) Γ ( E ∣ Q , w ∣ Q ) ( − 1 ) ∣ E ∣ Γ ( ( E , > 1 , < 2 ) , w ∣ E ) Γ ( E ∣ ∅ , w ∣ ∅ ) + ( P , Q ) ∈ Adm E ; ∣ P ∣ < ∣ E ∣ ∑ ( − 1 ) ∣ P ∣ Γ ( ( P , > 1 , < 2 ) , w ∣ P ) Γ ( E ∣ Q , w ∣ Q ) because the only pair ( P , Q ) ∈ Adm E (P,Q)\in\operatorname{Adm} E ( P , Q ) ∈ Adm E ∣ P ∣ ≥ ∣ E ∣ |P|\geq|E| ∣ P ∣ ≥ ∣ E ∣ ( P , Q ) = ( E , ∅ ) (P,Q)=(E,\varnothing) ( P , Q ) = ( E , ∅ ) ( P , Q ) ∈ Adm E (P,Q)\in\operatorname{Adm} E ( P , Q ) ∈ Adm E ∣ P ∣ < ∣ E ∣ |P|<|E| ∣ P ∣ < ∣ E ∣
= ( − 1 ) ∣ E ∣ Γ ( ( E , > 1 , < 2 ) , w ) + ∑ ( P , Q ) ∈ Adm E ; ∣ P ∣ < ∣ E ∣ ( − 1 ) ∣ P ∣ Γ ( ( P , > 1 , < 2 ) , w ∣ P ) Γ ( E ∣ Q , w ∣ Q ) , \begin{aligned}
={}&(-1)^{|E|}\Gamma\bigl((E,>_1,<_{2}),w\bigr)\\
&+\sum_{\substack{(P,Q)\in\operatorname{Adm} E;\\|P|<|E|}}(-1)^{|P|}\Gamma\bigl((P,>_1,<_{2}),w|_P\bigr)\Gamma\bigl(E|_Q,w|_Q\bigr),
\end{aligned} = ( − 1 ) ∣ E ∣ Γ ( ( E , > 1 , < 2 ) , w ) + ( P , Q ) ∈ Adm E ; ∣ P ∣ < ∣ E ∣ ∑ ( − 1 ) ∣ P ∣ Γ ( ( P , > 1 , < 2 ) , w ∣ P ) Γ ( E ∣ Q , w ∣ Q ) , so that
( − 1 ) ∣ E ∣ Γ ( ( E , > 1 , < 2 ) , w ) = − ∑ ( P , Q ) ∈ Adm E ; ∣ P ∣ < ∣ E ∣ ( − 1 ) ∣ P ∣ Γ ( ( P , > 1 , < 2 ) , w ∣ P ) Γ ( E ∣ Q , w ∣ Q ) = S ( Γ ( ( E ⏟ = ( E , < 1 , < 2 ) , w ) ) ) (by (26)) = S ( Γ ( ( E , < 1 , < 2 ) , w ) ) , \begin{aligned}
(-1)^{|E|}\Gamma\bigl((E,>_1,<_{2}),w\bigr)
=
-\sum_{\substack{(P,Q)\in\operatorname{Adm} E;\\|P|<|E|}}(-1)^{|P|}\Gamma\bigl((P,>_1,<_{2}),w|_P\bigr)\Gamma\bigl(E|_Q,w|_Q\bigr) \\
&=S\left(\Gamma\left(\left(\underbrace{E}_{=(E,<_{1},<_{2})},w\right)\right)\right)\qquad\text{(by (26))} \\
&=S\bigl(\Gamma((E,<_{1},<_{2}),w)\bigr),
\end{aligned} ( − 1 ) ∣ E ∣ Γ ( ( E , > 1 , < 2 ) , w ) = − ( P , Q ) ∈ Adm E ; ∣ P ∣ < ∣ E ∣ ∑ ( − 1 ) ∣ P ∣ Γ ( ( P , > 1 , < 2 ) , w ∣ P ) Γ ( E ∣ Q , w ∣ Q ) = S Γ = ( E , < 1 , < 2 ) E , w (by (26)) = S ( Γ (( E , < 1 , < 2 ) , w ) ) , and thus S ( Γ ( ( E , < 1 , < 2 ) , w ) ) = ( − 1 ) ∣ E ∣ Γ ( ( E , > 1 , < 2 ) , w ) S\bigl(\Gamma((E,<_{1},<_{2}),w)\bigr)=(-1)^{|E|}\Gamma((E,>_{1},<_{2}),w) S ( Γ (( E , < 1 , < 2 ) , w ) ) = ( − 1 ) ∣ E ∣ Γ (( E , > 1 , < 2 ) , w )
Proof of Theorem 4.7
Before we begin proving Theorem 4.7, we state a criterion for E-partitions that is less wasteful (in the sense that it requires fewer verifications) than the definition:
Lemma 7.1. Let E = ( E , < 1 , < 2 ) E=(E,<_{1},<_{2}) E = ( E , < 1 , < 2 ) ϕ : E → { 1 , 2 , 3 , … } \phi:E\to\{1,2,3,\ldots\} ϕ : E → { 1 , 2 , 3 , … }
Condition 1: If e ∈ E e\in E e ∈ E f ∈ E f\in E f ∈ E e e e < 1 <_{1} < 1 f f f e < 2 f e<_{2}f e < 2 f ϕ ( e ) ≤ ϕ ( f ) \phi(e)\leq\phi(f) ϕ ( e ) ≤ ϕ ( f )
Condition 2: If e ∈ E e\in E e ∈ E f ∈ E f\in E f ∈ E e e e < 1 <_{1} < 1 f f f f < 2 e f<_{2}e f < 2 e ϕ ( e ) < ϕ ( f ) \phi(e)<\phi(f) ϕ ( e ) < ϕ ( f )
Then, ϕ \phi ϕ
Proof of Lemma 7.1. For any a ∈ E a \in E a ∈ E b ∈ E b \in E b ∈ E [ a , b ] [a,b] [ a , b ] E E E
We need to show that ϕ \phi ϕ
Claim 1: Every e ∈ E e \in E e ∈ E f ∈ E f \in E f ∈ E e < 1 f e <_1 f e < 1 f ϕ ( e ) ≤ ϕ ( f ) \phi(e) \leq\phi(f) ϕ ( e ) ≤ ϕ ( f )
Claim 2: Every e ∈ E e \in E e ∈ E f ∈ E f \in E f ∈ E e < 1 f e <_1 f e < 1 f f < 2 e f <_2 e f < 2 e ϕ ( e ) < ϕ ( f ) \phi(e) < \phi(f) ϕ ( e ) < ϕ ( f )
Proof of Claim 1: Assume the contrary. Thus, there exists a pair ( e , f ) ∈ E × E (e,f) \in E \times E ( e , f ) ∈ E × E e < 1 f e <_1 f e < 1 f ϕ ( e ) ≤ ϕ ( f ) \phi(e) \leq\phi(f) ϕ ( e ) ≤ ϕ ( f ) malrelation . Fix a malrelation ( u , v ) (u,v) ( u , v ) ∣ [ u , v ] ∣ |[u,v]| ∣ [ u , v ] ∣ ( u , v ) (u,v) ( u , v ) u ∈ E u \in E u ∈ E v ∈ E v \in E v ∈ E u < 1 v u <_1 v u < 1 v ϕ ( u ) ≤ ϕ ( v ) \phi(u) \leq\phi(v) ϕ ( u ) ≤ ϕ ( v )
If u u u < 1 <_1 < 1 v v v ϕ ( u ) ≤ ϕ ( v ) \phi(u) \leq\phi(v) ϕ ( u ) ≤ ϕ ( v ) 35 ϕ ( u ) ≤ ϕ ( v ) \phi(u) \leq\phi(v) ϕ ( u ) ≤ ϕ ( v ) u u u < 1 <_1 < 1 v v v w ∈ E w \in E w ∈ E u < 1 w < 1 v u <_1 w <_1 v u < 1 w < 1 v u < 1 v u <_1 v u < 1 v w w w a = u a=u a = u c = w c=w c = w b = v b=v b = v ∣ [ u , w ] ∣ |[u,w]| ∣ [ u , w ] ∣ ∣ [ w , v ] ∣ |[w,v]| ∣ [ w , v ] ∣ ∣ [ u , v ] ∣ |[u,v]| ∣ [ u , v ] ∣ ( u , w ) (u,w) ( u , w ) ( w , v ) (w,v) ( w , v ) ( u , v ) (u,v) ( u , v ) ∣ [ u , v ] ∣ |[u,v]| ∣ [ u , v ] ∣ ϕ ( u ) ≤ ϕ ( w ) \phi(u) \leq\phi(w) ϕ ( u ) ≤ ϕ ( w ) u < 1 w u <_1 w u < 1 w ( u , w ) (u,w) ( u , w ) ϕ ( w ) ≤ ϕ ( v ) \phi(w) \leq\phi(v) ϕ ( w ) ≤ ϕ ( v ) w < 1 v w <_1 v w < 1 v ( w , v ) (w,v) ( w , v ) ϕ ( u ) ≤ ϕ ( w ) ≤ ϕ ( v ) \phi(u) \leq\phi(w) \leq\phi(v) ϕ ( u ) ≤ ϕ ( w ) ≤ ϕ ( v ) ϕ ( u ) ≤ ϕ ( v ) \phi(u) \leq\phi(v) ϕ ( u ) ≤ ϕ ( v )
Instead of Claim 2, we shall prove the following stronger claim:
Claim 3: Every e ∈ E e \in E e ∈ E f ∈ E f \in E f ∈ E e < 1 f e <_1 f e < 1 f e < 2 f e <_2 f e < 2 f ϕ ( e ) < ϕ ( f ) \phi(e) < \phi(f) ϕ ( e ) < ϕ ( f )
Proof of Claim 3: Assume the contrary. Thus, there exists a pair ( e , f ) ∈ E × E (e,f) \in E \times E ( e , f ) ∈ E × E e < 1 f e <_1 f e < 1 f e < 2 f e <_2 f e < 2 f ϕ ( e ) < ϕ ( f ) \phi(e) < \phi(f) ϕ ( e ) < ϕ ( f ) malrelation . Fix a malrelation ( u , v ) (u,v) ( u , v ) ∣ [ u , v ] ∣ |[u,v]| ∣ [ u , v ] ∣ ( u , v ) (u,v) ( u , v ) u ∈ E u \in E u ∈ E v ∈ E v \in E v ∈ E u < 1 v u <_1 v u < 1 v u < 2 v u <_2 v u < 2 v ϕ ( u ) < ϕ ( v ) \phi(u) < \phi(v) ϕ ( u ) < ϕ ( v ) u u u < 1 <_{1} < 1 v v v ϕ ( u ) < ϕ ( v ) \phi(u)<\phi(v) ϕ ( u ) < ϕ ( v ) 36 ϕ ( u ) < ϕ ( v ) \phi(u)<\phi(v) ϕ ( u ) < ϕ ( v ) u u u < 1 <_{1} < 1 v v v w ∈ E w\in E w ∈ E u < 1 w < 1 v u<_{1}w<_{1}v u < 1 w < 1 v u < 1 v u<_{1}v u < 1 v w w w (13) to a = u a=u a = u c = w c=w c = w b = v b=v b = v ∣ [ u , w ] ∣ \lvert[u,w]\rvert ∣[ u , w ]∣ ∣ [ w , v ] ∣ \lvert[w,v]\rvert ∣[ w , v ]∣ ∣ [ u , v ] ∣ \lvert[u,v]\rvert ∣[ u , v ]∣ ( u , w ) (u,w) ( u , w ) ( w , v ) (w,v) ( w , v ) ( u , v ) (u,v) ( u , v ) ∣ [ u , v ] ∣ \lvert[u,v]\rvert ∣[ u , v ]∣
But ϕ ( v ) ≤ ϕ ( u ) \phi(v)\leq\phi(u) ϕ ( v ) ≤ ϕ ( u ) ϕ ( u ) < ϕ ( v ) \phi(u)<\phi(v) ϕ ( u ) < ϕ ( v ) u < 1 w u<_{1}w u < 1 w ϕ ( u ) ≤ ϕ ( w ) \phi(u)\leq\phi(w) ϕ ( u ) ≤ ϕ ( w ) e = u e=u e = u f = w f=w f = w w < 1 v w<_{1}v w < 1 v ϕ ( w ) ≤ ϕ ( v ) \phi(w)\leq\phi(v) ϕ ( w ) ≤ ϕ ( v ) e = w e=w e = w f = v f=v f = v ϕ ( v ) ≤ ϕ ( u ) ≤ ϕ ( w ) ≤ ϕ ( v ) \phi(v)\leq\phi(u)\leq\phi(w)\leq\phi(v) ϕ ( v ) ≤ ϕ ( u ) ≤ ϕ ( w ) ≤ ϕ ( v ) ϕ ( v ) = ϕ ( u ) = ϕ ( w ) = ϕ ( v ) \phi(v)=\phi(u)=\phi(w)=\phi(v) ϕ ( v ) = ϕ ( u ) = ϕ ( w ) = ϕ ( v )
Now, using ϕ ( w ) = ϕ ( v ) \phi(w)=\phi(v) ϕ ( w ) = ϕ ( v ) w < 2 v w<_{2}v w < 2 v 37 u u u w w w w w w v v v u < 2 w u<_{2}w u < 2 w u < 2 w < 2 v u<_{2}w<_{2}v u < 2 w < 2 v u < 2 v u<_{2}v u < 2 v
Proof of Claim 2. The condition “f < 2 e f<_{2}e f < 2 e e < 2 f e<_{2}f e < 2 f
Claims 1 and 2 are now both proven, and so Lemma 7.1 follows.
Proof of Lemma 4.5 . Consider the following three logical statements:
Statement 1: The G G G O O O E E E
Statement 2: All elements of O O O E E E
Statement 3: At least one element of O O O E E E
Statements 1 and 2 are equivalent (according to the definition of when a G G G E E E Lemma 4.5 says). Thus, it suffices to show that Statements 2 and 3 are equivalent (because we already know that Statements 1 and 2 are equivalent). Since Statement 2 obviously implies Statement 3 (in fact, the G G G O O O
There exists at least one E E E ϕ ∈ O \phi\in O ϕ ∈ O ϕ \phi ϕ π ∈ O \pi\in O π ∈ O π \pi π E E E ϕ \phi ϕ E E E
every g ∈ G satisfying g ϕ = ϕ is E -even . (29) \text{every }g \in G\text{ satisfying }g\phi=\phi\text{ is }E\text{-even}. \tag*{(29)} every g ∈ G satisfying g ϕ = ϕ is E -even . (29) Now, let g ∈ G g \in G g ∈ G g π = π g\pi=\pi g π = π ϕ \phi ϕ G G G O O O O = G ϕ O=G\phi O = Gϕ π ∈ O = G ϕ \pi\in O=G\phi π ∈ O = Gϕ h ∈ G h \in G h ∈ G π = h ϕ \pi=h\phi π = h ϕ h h h g π = π g\pi=\pi g π = π π = h ϕ \pi=h\phi π = h ϕ g h ϕ = h ϕ gh\phi=h\phi g h ϕ = h ϕ h − 1 g h ϕ = ϕ h^{-1}gh\phi=\phi h − 1 g h ϕ = ϕ h − 1 g h h^{-1}gh h − 1 g h g g g h − 1 g h h^{-1}gh h − 1 g h E E E
the action of h − 1 g h on E is an even permutation of E . (30) \text{the action of }h^{-1}gh\text{ on }E\text{ is an even permutation of }E. \tag*{(30)} the action of h − 1 g h on E is an even permutation of E . (30) Now, let ε \varepsilon ε G G G Aut E \operatorname{Aut} E Aut E 38 G G G E E E ε ( h − 1 g h ) \varepsilon(h^{-1}gh) ε ( h − 1 g h ) h − 1 g h h^{-1}gh h − 1 g h E E E E E E
But since ε \varepsilon ε ε ( h − 1 g h ) = ε ( h ) − 1 ε ( g ) ε ( h ) \varepsilon(h^{-1}gh)=\varepsilon(h)^{-1}\varepsilon(g)\varepsilon(h) ε ( h − 1 g h ) = ε ( h ) − 1 ε ( g ) ε ( h ) ε ( h − 1 g h ) \varepsilon(h^{-1}gh) ε ( h − 1 g h ) ε ( g ) \varepsilon(g) ε ( g ) E E E ε ( h − 1 g h ) \varepsilon(h^{-1}gh) ε ( h − 1 g h ) ε ( g ) \varepsilon(g) ε ( g ) g g g E E E E E E g g g E E E
Now, let us forget that we fixed g g g g ∈ G g \in G g ∈ G g π = π g\pi=\pi g π = π E E E π \pi π E E E
Let us now forget that we fixed π \pi π π ∈ O \pi\in O π ∈ O E E E
We leave the fairly straightforward proof of Proposition 4.6 to the reader. Next, we will show three simple properties of posets on which groups act. First, we introduce a notation:
Definition 7.2. Let G G G g ∈ G g \in G g ∈ G E E E G G G ⟨ g ⟩ \langle g\rangle ⟨ g ⟩ G G G G G G g g g E E E ⟨ g ⟩ \langle g\rangle ⟨ g ⟩ E E E g g g E E E E E E g g g
We can also describe these g g g e ∈ E e \in E e ∈ E g g g e e e g g g e e e ⟨ g ⟩ e = { g k e ∣ k ∈ Z } \langle g\rangle e=\{g^k e\mid k\in\mathbb{Z}\} ⟨ g ⟩ e = { g k e ∣ k ∈ Z } g g g E E E g g g E E E E E E g g g E E E E E E
Proposition 7.3. Let E E E < 1 <_1 < 1 E E E G G G E E E G G G < 1 <_1 < 1
Let g ∈ G g \in G g ∈ G E g E^g E g g g g E E E < 1 g <^g_1 < 1 g E g E^g E g
( u < 1 g v ) ⟺ ( there exist a ∈ u and b ∈ v with a < 1 b ) . (u <^g_1 v) \Longleftrightarrow(\text{there exist } a \in u \text{ and } b \in v \text{ with } a <_1 b). ( u < 1 g v ) ⟺ ( there exist a ∈ u and b ∈ v with a < 1 b ) . Then, < 1 g <^g_1 < 1 g
Proposition 7.3 is precisely [15 Lemma 2.4] , but let us outline the proof for the sake of completeness:
Proof of Proposition 7.3. Let us first show that the relation < 1 g <^g_1 < 1 g u ∈ E g u \in E^g u ∈ E g u < 1 g u u <^g_1 u u < 1 g u u u u
We have u ∈ E g u \in E^g u ∈ E g u u u g g g E E E
Since u < 1 g u u <^g_1 u u < 1 g u a ∈ u a \in u a ∈ u b ∈ u b \in u b ∈ u a < 1 b a <_1 b a < 1 b < 1 g <^g_1 < 1 g a a a b b b k ∈ Z k \in\mathbb{Z} k ∈ Z b = g k a b = g^k a b = g k a a a a b b b g g g u u u k k k
Each element of G G G G G G g g g G G G n n n g n = 1 G g^n = 1_G g n = 1 G n n n p ∈ Z p \in\mathbb{Z} p ∈ Z g n p = ( g n ) p = 1 G g^{np} = (g^n)^p = 1_G g n p = ( g n ) p = 1 G g n = 1 G g^n = 1_G g n = 1 G p = k p = k p = k g n k = 1 G g^{nk} = 1_G g nk = 1 G
Now, a < 1 b = g k a a <_1 b = g^k a a < 1 b = g k a G G G < 1 <_1 < 1 h a < 1 h g k a ha <_1 hg^k a ha < 1 h g k a h ∈ G h \in G h ∈ G g ℓ k a < 1 g ℓ k g k a g^{\ell k}a <_1 g^{\ell k}g^k a g ℓ k a < 1 g ℓ k g k a ℓ ∈ N \ell\in\mathbb{N} ℓ ∈ N g ℓ k a < 1 g ℓ k g k a = g ( ℓ + 1 ) k a g^{\ell k}a <_1 g^{\ell k}g^k a = g^{(\ell+1)k}a g ℓ k a < 1 g ℓ k g k a = g ( ℓ + 1 ) k a ℓ ∈ N \ell\in\mathbb{N} ℓ ∈ N g 0 k a < 1 g 1 k a < 1 g 2 k a < 1 ⋯ < 1 g n k a g^{0k}a <_1 g^{1k}a <_1 g^{2k}a <_1 \cdots<_1 g^{nk}a g 0 k a < 1 g 1 k a < 1 g 2 k a < 1 ⋯ < 1 g nk a g 0 k a < 1 g n k a ⏟ = 1 G a = a g^{0k}a <_1 \underbrace{g^{nk}a}_{=1_Ga=a} g 0 k a < 1 = 1 G a = a g nk a g 0 k ⏟ = g 0 = 1 G a = 1 G a = a \underbrace{g^{0k}}_{=g^0=1_G}a = 1_Ga = a = g 0 = 1 G g 0 k a = 1 G a = a < 1 g <^g_1 < 1 g
Let us next show that the relation < 1 g <^g_1 < 1 g u u u v v v w w w E g E^g E g u < 1 g v u <^g_1 v u < 1 g v v < 1 g w v <^g_1 w v < 1 g w u < 1 g w u <^g_1 w u < 1 g w
There exist a ∈ u a \in u a ∈ u b ∈ v b \in v b ∈ v a < 1 b a <_1 b a < 1 b u < 1 g v u <^g_1 v u < 1 g v a a a
There exist a ′ ∈ v a' \in v a ′ ∈ v b ′ ∈ w b' \in w b ′ ∈ w a ′ < 1 b ′ a' <_1 b' a ′ < 1 b ′ v < 1 g w v <^g_1 w v < 1 g w a ′ a' a ′ b ′ b' b ′
The set v v v g g g v ∈ E g v \in E^g v ∈ E g b b b a ′ a' a ′ g g g v v v k ∈ Z k \in\mathbb{Z} k ∈ Z a ′ = g k b a' = g^k b a ′ = g k b k k k a < 1 b a <_1 b a < 1 b g k a < 1 g k b g^k a <_1 g^k b g k a < 1 g k b G G G < 1 <_1 < 1 g k a < 1 g k b = a ′ < 1 b ′ g^k a <_1 g^k b = a' <_1 b' g k a < 1 g k b = a ′ < 1 b ′ g k a ∈ u g^k a \in u g k a ∈ u a ∈ u a \in u a ∈ u u u u g g g b ′ ∈ w b' \in w b ′ ∈ w u < 1 g w u <^g_1 w u < 1 g w < 1 g <^g_1 < 1 g < 1 g <^g_1 < 1 g
Now, we know that the relation < 1 g <^g_1 < 1 g < 1 g <^g_1 < 1 g
Remark 7.4. Proposition 7.3 can be generalized: Let E E E < 1 <_{1} < 1 E E E G G G E E E G G G < 1 <_{1} < 1 H H H G G G E H E^{H} E H H H H E E E < 1 H <^{H}_{1} < 1 H E H E^{H} E H
( u < 1 H v ) ⟺ ( there exist a ∈ u and b ∈ v with a < 1 b ) . \left(u <^{H}_{1} v\right) \Longleftrightarrow\left(\text{there exist }a \in u\text{ and }b \in v\text{ with }a <_{1} b\right). ( u < 1 H v ) ⟺ ( there exist a ∈ u and b ∈ v with a < 1 b ) . Then, < 1 H <^{H}_{1} < 1 H Proposition 7.3 ) implicitly appears in [27 p. 30] .
Proposition 7.5. Let E = ( E , < 1 , < 2 ) E=(E,<_{1},<_{2}) E = ( E , < 1 , < 2 ) G G G E E E G G G < 1 <_{1} < 1 < 2 <_{2} < 2 g ∈ G g \in G g ∈ G E g E^{g} E g g g g E E E < 1 g <^{g}_{1} < 1 g E g E^{g} E g
( u < 1 g v ) ⟺ ( there exist a ∈ u and b ∈ v with a < 1 b ) . \left(u <^{g}_{1} v\right) \Longleftrightarrow\left(\text{there exist }a \in u\text{ and }b \in v\text{ with }a <_{1} b\right). ( u < 1 g v ) ⟺ ( there exist a ∈ u and b ∈ v with a < 1 b ) . Define a binary relation < 2 g <^{g}_{2} < 2 g E g E^{g} E g
( u < 2 g v ) ⟺ ( there exist a ∈ u and b ∈ v with a < 2 b ) . \left(u <^{g}_{2} v\right) \Longleftrightarrow\left(\text{there exist }a \in u\text{ and }b \in v\text{ with }a <_{2} b\right). ( u < 2 g v ) ⟺ ( there exist a ∈ u and b ∈ v with a < 2 b ) . Let E g E^{g} E g ( E g , < 1 g , < 2 g ) (E^{g},<^{g}_{1},<^{g}_{2}) ( E g , < 1 g , < 2 g ) E g E^{g} E g
Proof of Proposition 7.5. Proposition 7.3 shows that < 1 g <^{g}_{1} < 1 g < 2 g <^{g}_{2} < 2 g E g = ( E g , < 1 g , < 2 g ) E^{g}=(E^{g},<^{g}_{1},<^{g}_{2}) E g = ( E g , < 1 g , < 2 g ) E g E^{g} E g
Let u u u v v v E g E^{g} E g u u u < 1 g <^{g}_{1} < 1 g v v v u u u v v v < 2 g <^{g}_{2} < 2 g
We have u < 1 g v u <^{g}_{1} v u < 1 g v u u u < 1 g <^{g}_{1} < 1 g v v v a ∈ u a \in u a ∈ u b ∈ v b \in v b ∈ v a < 1 b a <_{1} b a < 1 b < 1 g <^{g}_{1} < 1 g a a a b b b
If there was a c ∈ E c \in E c ∈ E a < 1 c < 1 b a <_{1} c <_{1} b a < 1 c < 1 b u < 1 g w < 1 g v u <^{g}_{1} w <^{g}_{1} v u < 1 g w < 1 g v w w w g g g c c c u u u < 1 g <^{g}_{1} < 1 g v v v c c c a a a < 1 <_{1} < 1 b b b a < 1 b a <_{1} b a < 1 b a a a b b b < 2 <_{2} < 2 E E E u u u v v v < 2 g <^{g}_{2} < 2 g
Now, let us forget that we fixed u u u v v v u u u v v v E g E^{g} E g u u u < 1 g <^{g}_{1} < 1 g v v v u u u v v v < 2 g <^{g}_{2} < 2 g E g = ( E g , < 1 g , < 2 g ) E^{g}=(E^{g},<^{g}_{1},<^{g}_{2}) E g = ( E g , < 1 g , < 2 g )
Proposition 7.6. Let E = ( E , < 1 , < 2 ) E=(E,<_{1},<_{2}) E = ( E , < 1 , < 2 ) G G G E E E G G G < 1 <_{1} < 1 < 2 <_{2} < 2
Let g ∈ G g\in G g ∈ G E g E^{g} E g < 1 g <_{1}^{g} < 1 g < 2 g <_{2}^{g} < 2 g E g E^{g} E g E g E^{g} E g
There is a bijection Φ \Phi Φ
the maps π : E → { 1 , 2 , 3 , … } \pi:E\to\{1,2,3,\ldots\} π : E → { 1 , 2 , 3 , … } g π = π g\pi=\pi g π = π
and
the maps π ‾ : E g → { 1 , 2 , 3 , … } \overline{\pi}:E^{g}\to\{1,2,3,\ldots\} π : E g → { 1 , 2 , 3 , … }
Namely, this bijection Φ \Phi Φ π : E → { 1 , 2 , 3 , … } \pi:E\to\{1,2,3,\ldots\} π : E → { 1 , 2 , 3 , … } g π = π g\pi=\pi g π = π π ‾ : E g → { 1 , 2 , 3 , … } \overline{\pi}:E^{g}\to\{1,2,3,\ldots\} π : E g → { 1 , 2 , 3 , … }
π ‾ ( u ) = π ( a ) for every u ∈ E g and a ∈ u . \overline{\pi}(u)=\pi(a)\qquad\text{for every }u\in E^{g}\text{ and }a\in u. π ( u ) = π ( a ) for every u ∈ E g and a ∈ u . (The well-definedness of this map π ‾ \overline{\pi} π g π = π g\pi=\pi g π = π a 1 a_{1} a 1 a 2 a_{2} a 2 g g g u u u π ( a 1 ) = π ( a 2 ) . \pi(a_{1})=\pi(a_{2}). π ( a 1 ) = π ( a 2 ) .
Consider this bijection Φ \Phi Φ π : E → { 1 , 2 , 3 , … } \pi:E\to\{1,2,3,\ldots\} π : E → { 1 , 2 , 3 , … } g π = π g\pi=\pi g π = π
(a) If π \pi π E E E Φ ( π ) \Phi(\pi) Φ ( π ) E g E^{g} E g
(b) If Φ ( π ) \Phi(\pi) Φ ( π ) E g E^{g} E g π \pi π E E E
(c) Let w : E → { 1 , 2 , 3 , … } w:E\to\{1,2,3,\ldots\} w : E → { 1 , 2 , 3 , … } w g : E g → { 1 , 2 , 3 , … } w^{g}:E^{g}\to\{1,2,3,\ldots\} w g : E g → { 1 , 2 , 3 , … }
w g ( u ) = ∑ a ∈ u w ( a ) for every u ∈ E g . w^{g}(u)=\sum_{a\in u}w(a)\qquad\text{for every }u\in E^{g}. w g ( u ) = a ∈ u ∑ w ( a ) for every u ∈ E g . Then, x Φ ( π ) , w g = x π , w x_{\Phi(\pi),w^{g}}=x_{\pi,w} x Φ ( π ) , w g = x π , w
Proof of Proposition 7.6 (sketched). The definition of Φ \Phi Φ
( Φ ( π ) ) ( u ) = π ( a ) for every u ∈ E g and a ∈ u . (31) (\Phi(\pi))(u)=\pi(a)\qquad\text{for every }u\in E^{g}\text{ and }a\in u. \tag*{(31)} ( Φ ( π )) ( u ) = π ( a ) for every u ∈ E g and a ∈ u . (31) (a) Assume that π \pi π E E E Φ ( π ) \Phi(\pi) Φ ( π ) E g E^{g} E g Lemma 7.1 (applied to E g E^{g} E g ( E g , < 1 g , < 2 g ) (E^{g},<_{1}^{g},<_{2}^{g}) ( E g , < 1 g , < 2 g ) Φ ( π ) \Phi(\pi) Φ ( π ) E E E ( E , < 1 , < 2 ) (E,<_{1},<_{2}) ( E , < 1 , < 2 ) ϕ \phi ϕ
Condition 1: If e ∈ E g e\in E^{g} e ∈ E g f ∈ E g f\in E^{g} f ∈ E g e e e < 1 g <_{1}^{g} < 1 g f f f e < 2 g f e<_{2}^{g}f e < 2 g f ( Φ ( π ) ) ( e ) ≤ ( Φ ( π ) ) ( f ) (\Phi(\pi))(e)\leq(\Phi(\pi))(f) ( Φ ( π )) ( e ) ≤ ( Φ ( π )) ( f )
Condition 2: If e ∈ E g e\in E^{g} e ∈ E g f ∈ E g f\in E^{g} f ∈ E g e e e < 1 g <_{1}^{g} < 1 g f f f f < 2 g e f<_{2}^{g}e f < 2 g e ( Φ ( π ) ) ( e ) < ( Φ ( π ) ) ( f ) (\Phi(\pi))(e)<(\Phi(\pi))(f) ( Φ ( π )) ( e ) < ( Φ ( π )) ( f ) Proof of Condition 1: Let e ∈ E g e \in E^{g} e ∈ E g f ∈ E g f \in E^{g} f ∈ E g e e e < 1 g <_{1}^{g} < 1 g f f f e < 2 g f e <_{2}^{g} f e < 2 g f
We have e < 1 g f e <_{1}^{g} f e < 1 g f e e e < 1 g <_{1}^{g} < 1 g f f f a ∈ e a \in e a ∈ e b ∈ f b \in f b ∈ f a < 1 b a <_{1} b a < 1 b a a a b b b π \pi π E E E π ( a ) ≤ π ( b ) \pi(a) \leq\pi(b) π ( a ) ≤ π ( b ) a < 1 b a <_{1} b a < 1 b Φ ( π ) \Phi(\pi) Φ ( π ) ( Φ ( π ) ) ( e ) = π ( a ) (\Phi(\pi))(e) = \pi(a) ( Φ ( π )) ( e ) = π ( a ) a ∈ e a \in e a ∈ e ( Φ ( π ) ) ( f ) = π ( b ) (\Phi(\pi))(f) = \pi(b) ( Φ ( π )) ( f ) = π ( b ) b ∈ f b \in f b ∈ f ( Φ ( π ) ) ( e ) = π ( a ) ≤ π ( b ) = ( Φ ( π ) ) ( f ) (\Phi(\pi))(e) = \pi(a) \leq\pi(b) = (\Phi(\pi))(f) ( Φ ( π )) ( e ) = π ( a ) ≤ π ( b ) = ( Φ ( π )) ( f )
Proof of Condition 2: Let e ∈ E g e \in E^{g} e ∈ E g f ∈ E g f \in E^{g} f ∈ E g e e e < 1 g <_{1}^{g} < 1 g f f f f < 2 g e f <_{2}^{g} e f < 2 g e
We have e < 1 g f e <_{1}^{g} f e < 1 g f e e e < 1 g <_{1}^{g} < 1 g f f f a ∈ e a \in e a ∈ e b ∈ f b \in f b ∈ f a < 1 b a <_{1} b a < 1 b a a a b b b
If there was a c ∈ E c \in E c ∈ E a < 1 c < 1 b a <_{1} c <_{1} b a < 1 c < 1 b g g g w w w c c c e < 1 g w < 1 g f e <_{1}^{g} w <_{1}^{g} f e < 1 g w < 1 g f e e e < 1 g <_{1}^{g} < 1 g f f f c c c a a a < 1 <_{1} < 1 b b b a < 1 b a <_{1} b a < 1 b a a a b b b < 2 <_{2} < 2 E E E a < 2 b a <_{2} b a < 2 b a = b a = b a = b b < 2 a b <_{2} a b < 2 a a < 2 b a <_{2} b a < 2 b a < 2 b a <_{2} b a < 2 b e < 2 g f e <_{2}^{g} f e < 2 g f a ∈ e a \in e a ∈ e b ∈ f b \in f b ∈ f f < 2 g e f <_{2}^{g} e f < 2 g e < 2 g <_{2}^{g} < 2 g a = b a = b a = b a < 1 b a <_{1} b a < 1 b b < 2 a b <_{2} a b < 2 a π \pi π E E E π ( a ) < π ( b ) \pi(a) < \pi(b) π ( a ) < π ( b ) a < 1 b a <_{1} b a < 1 b b < 2 a b <_{2} a b < 2 a Φ ( π ) \Phi(\pi) Φ ( π ) ( Φ ( π ) ) ( e ) = π ( a ) (\Phi(\pi))(e) = \pi(a) ( Φ ( π )) ( e ) = π ( a ) a ∈ e a \in e a ∈ e ( Φ ( π ) ) ( f ) = π ( b ) (\Phi(\pi))(f) = \pi(b) ( Φ ( π )) ( f ) = π ( b ) b ∈ f b \in f b ∈ f ( Φ ( π ) ) ( e ) = π ( a ) < π ( b ) = ( Φ ( π ) ) ( f ) (\Phi(\pi))(e) = \pi(a) < \pi(b) = (\Phi(\pi))(f) ( Φ ( π )) ( e ) = π ( a ) < π ( b ) = ( Φ ( π )) ( f )
Thus, Condition 1 and Condition 2 are proven. Hence, Proposition 7.6 (a) is proven.
(b) Assume that Φ ( π ) \Phi(\pi) Φ ( π ) E g E^{g} E g π \pi π E E E Lemma 7.1 (applied to ϕ = π \phi= \pi ϕ = π
Condition 1: If e ∈ E e \in E e ∈ E f ∈ E f \in E f ∈ E e e e < 1 <_{1} < 1 f f f e < 2 f e <_{2} f e < 2 f π ( e ) ≤ π ( f ) \pi(e) \leq\pi(f) π ( e ) ≤ π ( f )
Condition 2: If e ∈ E e \in E e ∈ E f ∈ E f \in E f ∈ E e e e < 1 <_{1} < 1 f f f f < 2 e f <_{2} e f < 2 e π ( e ) < π ( f ) \pi(e) < \pi(f) π ( e ) < π ( f )
Proof of Condition 1: Let e ∈ E e \in E e ∈ E f ∈ E f \in E f ∈ E e e e < 1 <_{1} < 1 f f f e < 2 f e <_{2} f e < 2 f
We have e < 1 f e <_{1} f e < 1 f e e e < 1 <_{1} < 1 f f f u u u v v v g g g e e e f f f u u u v v v E g E^{g} E g e ∈ u e \in u e ∈ u f ∈ v f \in v f ∈ v u < 1 g v u <_{1}^{g} v u < 1 g v e < 1 f e <_{1} f e < 1 f ( Φ ( π ) ) ( u ) ≤ ( Φ ( π ) ) ( v ) (\Phi(\pi))(u) \leq(\Phi(\pi))(v) ( Φ ( π )) ( u ) ≤ ( Φ ( π )) ( v ) Φ ( π ) \Phi(\pi) Φ ( π ) E g E^{g} E g Φ ( π ) \Phi(\pi) Φ ( π ) ( Φ ( π ) ) ( u ) = π ( e ) (\Phi(\pi))(u) = \pi(e) ( Φ ( π )) ( u ) = π ( e ) e ∈ u e \in u e ∈ u ( Φ ( π ) ) ( v ) = π ( f ) (\Phi(\pi))(v) = \pi(f) ( Φ ( π )) ( v ) = π ( f ) f ∈ v f \in v f ∈ v π ( e ) = ( Φ ( π ) ) ( u ) ≤ ( Φ ( π ) ) ( v ) = π ( f ) \pi(e) = (\Phi(\pi))(u) \leq(\Phi(\pi))(v) = \pi(f) π ( e ) = ( Φ ( π )) ( u ) ≤ ( Φ ( π )) ( v ) = π ( f )
Proof of Condition 2: Let e ∈ E e \in E e ∈ E f ∈ E f \in E f ∈ E e e e < 1 <_{1} < 1 f f f f < 2 e f <_{2} e f < 2 e
We have e < 1 f e <_{1} f e < 1 f e e e < 1 <_{1} < 1 f f f u u u v v v g g g e e e f f f u u u v v v E g E^{g} E g e ∈ u e \in u e ∈ u f ∈ v f \in v f ∈ v u < 1 g v u <_{1}^{g} v u < 1 g v e < 1 f e <_{1} f e < 1 f v < 2 u v <_{2} u v < 2 u f < 2 e f <_{2} e f < 2 e ( Φ ( π ) ) ( u ) < ( Φ ( π ) ) ( v ) (\Phi(\pi))(u) < (\Phi(\pi))(v) ( Φ ( π )) ( u ) < ( Φ ( π )) ( v ) Φ ( π ) \Phi(\pi) Φ ( π ) E g E^{g} E g Φ ( π ) \Phi(\pi) Φ ( π ) ( Φ ( π ) ) ( u ) = π ( e ) (\Phi(\pi))(u) = \pi(e) ( Φ ( π )) ( u ) = π ( e ) e ∈ u e \in u e ∈ u ( Φ ( π ) ) ( v ) = π ( f ) (\Phi(\pi))(v) = \pi(f) ( Φ ( π )) ( v ) = π ( f ) f ∈ v f \in v f ∈ v π ( e ) = ( Φ ( π ) ) ( u ) < ( Φ ( π ) ) ( v ) = π ( f ) \pi(e) = (\Phi(\pi))(u) < (\Phi(\pi))(v) = \pi(f) π ( e ) = ( Φ ( π )) ( u ) < ( Φ ( π )) ( v ) = π ( f )
Thus, Condition 1 and Condition 2 are proven. Hence, Proposition 7.6 (b) is proven.
(c) The definition of x Φ ( π ) , w g x_{\Phi(\pi),w^{g}} x Φ ( π ) , w g
x Φ ( π ) , w g = ∏ e ∈ E g x ( Φ ( π ) ) ( e ) w g ( e ) = ∏ u ∈ E g x ( Φ ( π ) ) ( u ) w g ( u ) = ∏ u ∈ E g ∏ a ∈ u x ( Φ ( π ) ) ( u ) w ( a ) = ∏ u ∈ E g ∏ a ∈ u x π ( a ) w ( a ) = ∏ a ∈ E x π ( a ) w ( a ) = ∏ e ∈ E x π ( e ) w ( e ) = x π , w . \begin{aligned}
x_{\Phi(\pi),w^{g}} &= \prod_{e\in E^{g}} x_{(\Phi(\pi))(e)}^{w^{g}(e)}
= \prod_{u\in E^{g}} x_{(\Phi(\pi))(u)}^{w^{g}(u)}
= \prod_{u\in E^{g}}\prod_{a\in u} x_{(\Phi(\pi))(u)}^{w(a)} \\
&= \prod_{u\in E^{g}}\prod_{a\in u} x_{\pi(a)}^{w(a)}
= \prod_{a\in E}x_{\pi(a)}^{w(a)}
= \prod_{e\in E}x_{\pi(e)}^{w(e)}
= x_{\pi,w}.
\end{aligned} x Φ ( π ) , w g = e ∈ E g ∏ x ( Φ ( π )) ( e ) w g ( e ) = u ∈ E g ∏ x ( Φ ( π )) ( u ) w g ( u ) = u ∈ E g ∏ a ∈ u ∏ x ( Φ ( π )) ( u ) w ( a ) = u ∈ E g ∏ a ∈ u ∏ x π ( a ) w ( a ) = a ∈ E ∏ x π ( a ) w ( a ) = e ∈ E ∏ x π ( e ) w ( e ) = x π , w . (by the definition of x π , w x_{\pi,w} x π , w
Our next lemma is a standard argument in Pólya enumeration theory (compare it with the proof of Burnside’s lemma):
Lemma 7.7. Let G G G F F F G G G O O O G G G F F F π ∈ O \pi\in O π ∈ O
(a) We have
1 ∣ O ∣ = 1 ∣ G ∣ ∑ g ∈ G ; g π = π 1. (32) \frac{1}{|O|}=\frac{1}{|G|}\sum_{\substack{g\in G;\\g\pi=\pi}}1. \tag*{(32)} ∣ O ∣ 1 = ∣ G ∣ 1 g ∈ G ; g π = π ∑ 1. (32) (b) Let E E E G G G g ∈ G g \in G g ∈ G sign E g \operatorname{sign}_{E}g sign E g E E E e ∈ E e \in E e ∈ E g e ge g e g ∈ G g \in G g ∈ G E E E sign E g = 1 \operatorname{sign}_{E}g=1 sign E g = 1
\begin{cases}
\frac{1}{|O|}, & \text{if } O \text{ is } E\text{-coeven};\\
0, & \text{if } O \text{ is not } E\text{-coeven}
\end{cases}
=
\frac{1}{|G|}\sum_{\substack{g\in G;\\g\pi=\pi}}\operatorname{sign}_{E}g. \tag*{(33)}\end{cases}
Proof of Lemma 7.7. Let Stab G π \operatorname{Stab}_{G}\pi Stab G π π \pi π { g ∈ G ∣ g π = π } \{g \in G \mid g\pi= \pi\} { g ∈ G ∣ g π = π } G G G stabilizer subgroup or the isotropy group of π \pi π G G G π \pi π O O O O O O G G G F F F π ∈ O \pi\in O π ∈ O O = G π O=G\pi O = G π ∣ O ∣ = ∣ G π ∣ = ∣ G ∣ / ∣ Stab G π ∣ |O|=|G\pi|=|G|/|\operatorname{Stab}_{G}\pi| ∣ O ∣ = ∣ G π ∣ = ∣ G ∣/∣ Stab G π ∣
1 ∣ O ∣ = 1 ∣ G ∣ / ∣ Stab G π ∣ = ∣ Stab G π ∣ ∣ G ∣ . (34) \frac{1}{|O|}
=
\frac{1}{|G|/|\operatorname{Stab}_{G}\pi|}
=
\frac{|\operatorname{Stab}_{G}\pi|}{|G|}. \tag*{(34)} ∣ O ∣ 1 = ∣ G ∣/∣ Stab G π ∣ 1 = ∣ G ∣ ∣ Stab G π ∣ . (34) (a) We have
∑ g ∈ G ; g π = π 1 = ∣ { g ∈ G ∣ g π = π } ∣ = ∣ Stab G π ∣ . \sum_{\substack{g\in G;\\g\pi=\pi}} 1 = \left|\{g\in G\mid g\pi=\pi\}\right| = |\operatorname{Stab}_{G}\pi|. g ∈ G ; g π = π ∑ 1 = ∣ { g ∈ G ∣ g π = π } ∣ = ∣ Stab G π ∣. Hence,
1 ∣ G ∣ ∑ g ∈ G ; g π = π 1 = 1 ∣ G ∣ ∣ Stab G π ∣ = ∣ Stab G π ∣ ∣ G ∣ = 1 ∣ O ∣ . \frac{1}{|G|}\sum_{\substack{g\in G;\\g\pi=\pi}}1
=\frac{1}{|G|}|\operatorname{Stab}_{G}\pi|
=\frac{|\operatorname{Stab}_{G}\pi|}{|G|}
=\frac{1}{|O|}. ∣ G ∣ 1 g ∈ G ; g π = π ∑ 1 = ∣ G ∣ 1 ∣ Stab G π ∣ = ∣ G ∣ ∣ Stab G π ∣ = ∣ O ∣ 1 . (by (34) ). This proves Lemma 7.7 (a).
(b) We need to prove (33) . Assume first that O O O E E E O O O E E E O O O E E E π \pi π E E E π ∈ O \pi\in O π ∈ O g ∈ G g\in G g ∈ G g π = π g\pi=\pi g π = π E E E g ∈ G g\in G g ∈ G g π = π g\pi=\pi g π = π sign E g = 1 \operatorname{sign}_{E}g=1 sign E g = 1 g g g E E E sign E g = 1 \operatorname{sign}_{E}g=1 sign E g = 1
1 ∣ G ∣ ∑ g ∈ G ; g π = π sign E g = 1 ∣ G ∣ ∑ g ∈ G ; g π = π 1 = 1 ∣ O ∣ \frac{1}{|G|}\sum_{\substack{g\in G;\\g\pi=\pi}}\operatorname{sign}_{E}g
=\frac{1}{|G|}\sum_{\substack{g\in G;\\g\pi=\pi}}1
=\frac{1}{|O|} ∣ G ∣ 1 g ∈ G ; g π = π ∑ sign E g = ∣ G ∣ 1 g ∈ G ; g π = π ∑ 1 = ∣ O ∣ 1 (by (32) )
= { 1 ∣ O ∣ , if O is E -coeven ; 0 , if O is not E -coeven =\begin{cases}
\frac{1}{|O|}, & \text{if $O$ is $E$-coeven};\\
0, & \text{if $O$ is not $E$-coeven}
\end{cases} = { ∣ O ∣ 1 , 0 , if O is E -coeven ; if O is not E -coeven (since O O O E E E
Thus, we have proven (33) under the assumption that O O O E E E O O O E E E O O O E E E π \pi π E E E π ∈ O \pi\in O π ∈ O g ∈ G g\in G g ∈ G g π = π g\pi=\pi g π = π E E E g ∈ Stab G π g\in\operatorname{Stab}_{G}\pi g ∈ Stab G π E E E g ∈ G g\in G g ∈ G g π = π g\pi=\pi g π = π g ∈ Stab G π g\in\operatorname{Stab}_{G}\pi g ∈ Stab G π g ∈ Stab G π g\in\operatorname{Stab}_{G}\pi g ∈ Stab G π sign E g = 1 \operatorname{sign}_{E}g=1 sign E g = 1 g g g E E E sign E g = 1 \operatorname{sign}_{E}g=1 sign E g = 1
Now, the map
Stab G π ⟶ { 1 , − 1 } , g ⟼ sign E g \operatorname{Stab}_{G}\pi\longrightarrow\{1,-1\},\qquad g\longmapsto\operatorname{sign}_{E}g Stab G π ⟶ { 1 , − 1 } , g ⟼ sign E g is a group homomorphism (since the action of G G G E E E G → Aut E G\to\operatorname{Aut}E G → Aut E g ∈ Stab G π g\in\operatorname{Stab}_{G}\pi g ∈ Stab G π sign E g = 1 \operatorname{sign}_{E}g=1 sign E g = 1 Stab G π \operatorname{Stab}_{G}\pi Stab G π 1 1 1 − 1 -1 − 1
∑ g ∈ Stab G π sign E g \sum_{g\in\operatorname{Stab}_{G}\pi}\operatorname{sign}_{E}g g ∈ Stab G π ∑ sign E g cancel each other out (one half of them are 1, and the others are − 1 -1 − 1 ∑ g ∈ Stab G π sign E g = 0 \sum_{g\in\operatorname{Stab}_{G}\pi}\operatorname{sign}_{E}g=0 ∑ g ∈ Stab G π sign E g = 0
1 ∣ G ∣ ∑ g ∈ G ; g π = π sign E g ⏟ = ∑ g ∈ Stab G π = 1 ∣ G ∣ ∑ g ∈ Stab G π sign E g ⏟ = 0 = 0 = { 1 ∣ O ∣ , if O is E -coeven ; 0 , if O is not E -coeven \frac{1}{|G|}\underbrace{\sum_{\substack{g\in G;\\g\pi=\pi}}\operatorname{sign}_{E}g}_{=\sum_{g\in\operatorname{Stab}_{G}\pi}}=\frac{1}{|G|}\underbrace{\sum_{g\in\operatorname{Stab}_{G}\pi}\operatorname{sign}_{E}g}_{=0}=0=\begin{cases}\frac{1}{|O|},&\text{if $O$ is $E$-coeven};\\0,&\text{if $O$ is not $E$-coeven}\end{cases} ∣ G ∣ 1 = ∑ g ∈ Stab G π g ∈ G ; g π = π ∑ sign E g = ∣ G ∣ 1 = 0 g ∈ Stab G π ∑ sign E g = 0 = { ∣ O ∣ 1 , 0 , if O is E -coeven ; if O is not E -coeven (since O O O E E E (33) . Lemma 7.7 (b) is thus proven. □
Proof of Theorem 4.7 (sketched). Let g ∈ G g\in G g ∈ G E g E^{g} E g < 1 g <_{1}^{g} < 1 g < 2 g <_{2}^{g} < 2 g E g E^{g} E g E g E^{g} E g ( E g , < 1 g , < 2 g ) (E^{g},<_{1}^{g},<_{2}^{g}) ( E g , < 1 g , < 2 g ) E g = ( E g , < 1 g , < 2 g ) E^{g}=(E^{g},<_{1}^{g},<_{2}^{g}) E g = ( E g , < 1 g , < 2 g )
Now, forget that we fixed g g g E g = ( E g , < 1 g , < 2 g ) E^{g}=(E^{g},<_{1}^{g},<_{2}^{g}) E g = ( E g , < 1 g , < 2 g ) g ∈ G g\in G g ∈ G
Moreover, for every g ∈ G g\in G g ∈ G > 1 g >_{1}^{g} > 1 g < 1 g <_{1}^{g} < 1 g g ∈ G g\in G g ∈ G w g : E g → { 1 , 2 , 3 , … } w^{g}:E^{g}\to\{1,2,3,\ldots\} w g : E g → { 1 , 2 , 3 , … } w g ( u ) = ∑ a ∈ u w ( a ) w^{g}(u)=\sum_{a\in u}w(a) w g ( u ) = ∑ a ∈ u w ( a ) G G G w w w w ( a ) w(a) w ( a ) a ∈ u a\in u a ∈ u u u u ∑ a ∈ u w ( a ) \sum_{a\in u}w(a) ∑ a ∈ u w ( a ) ∣ u ∣ ⋅ w ( b ) |u|\cdot w(b) ∣ u ∣ ⋅ w ( b ) b ∈ u b\in u b ∈ u g ∈ G g\in G g ∈ G
S ( Γ ( ( E g , < 1 g , < 2 g ) , w g ) ) = ( − 1 ) ∣ E g ∣ Γ ( ( E g , > 1 g , < 2 g ) , w g ) . (35) S\left(\Gamma\left((E^{g},<_{1}^{g},<_{2}^{g}),w^{g}\right)\right)=(-1)^{|E^{g}|}\Gamma\left((E^{g},>_{1}^{g},<_{2}^{g}),w^{g}\right). \tag*{(35)} S ( Γ ( ( E g , < 1 g , < 2 g ) , w g ) ) = ( − 1 ) ∣ E g ∣ Γ ( ( E g , > 1 g , < 2 g ) , w g ) . (35) (Indeed, this follows from Theorem 4.2 (applied to ( E g , < 1 g , < 2 g ) (E^{g},<_{1}^{g},<_{2}^{g}) ( E g , < 1 g , < 2 g ) w g w^{g} w g ( E , < 1 , < 2 ) (E,<_{1},<_{2}) ( E , < 1 , < 2 ) w w w ( E g , < 1 g , < 2 g ) (E^{g},<_{1}^{g},<_{2}^{g}) ( E g , < 1 g , < 2 g )
For every g ∈ G g\in G g ∈ G
∑ π is an E -partition ; g π = π x π , w = Γ ( E g , w g ) (36) \sum_{\substack{\pi\text{ is an }E\text{-partition};\\g\pi=\pi}}x_{\pi,w}=\Gamma(E^{g},w^{g}) \tag*{(36)} π is an E -partition ; g π = π ∑ x π , w = Γ ( E g , w g ) (36) Γ ( E g , w g ) = ∑ π is an E g -partition x π , w g = ∑ π is an E ‾ g -partition x π ‾ , w g (37) \Gamma(E^{g},w^{g})=\sum_{\pi\text{ is an }E^{g}\text{-partition}}x_{\pi,w^{g}}=\sum_{\pi\text{ is an }\overline{E}^{g}\text{-partition}}x_{\overline{\pi},w^{g}} \tag*{(37)} Γ ( E g , w g ) = π is an E g -partition ∑ x π , w g = π is an E g -partition ∑ x π , w g (37) (here, we have renamed the summation index π \pi π π ‾ \overline{\pi} π
In Proposition 7.6, we have introduced a bijection Φ \Phi Φ
the maps π : E → { 1 , 2 , 3 , … } \pi:E\to\{1,2,3,\ldots\} π : E → { 1 , 2 , 3 , … } g π = π g\pi=\pi g π = π
and
the maps π ‾ : E g → { 1 , 2 , 3 , … } \overline{\pi}:E^{g}\to\{1,2,3,\ldots\} π : E g → { 1 , 2 , 3 , … }
It is clearly sufficient to prove Theorem 4.7 for k = Z k = \mathbb{Z} k = Z k k k S S S Z \mathbb{Z} Z k k k k = Q k = \mathbb{Q} k = Q Z [ [ x 1 , x 2 , x 3 , … ] ] \mathbb{Z}[[x_1,x_2,x_3,\ldots]] Z [[ x 1 , x 2 , x 3 , … ]] Q [ [ x 1 , x 2 , x 3 , … ] ] \mathbb{Q}[[x_1,x_2,x_3,\ldots]] Q [[ x 1 , x 2 , x 3 , … ]] QSym Z = QSym Q ∩ Z [ [ x 1 , x 2 , x 3 , … ] ] \operatorname{QSym}_{\mathbb{Z}}=\operatorname{QSym}_{\mathbb{Q}}\cap\mathbb{Z}[[x_1,x_2,x_3,\ldots]] QSym Z = QSym Q ∩ Z [[ x 1 , x 2 , x 3 , … ]] 40 k = Q k = \mathbb{Q} k = Q
Every G G G O O O Par E \operatorname{Par} E Par E
1 ∣ O ∣ ∑ π ∈ O x π , w = 1 ∣ O ∣ ∑ π ∈ O x O , w = 1 ∣ O ∣ ∣ O ∣ x O , w = x O , w . (38) \frac{1}{|O|}\sum_{\pi\in O}x_{\pi,w}
=\frac{1}{|O|}\sum_{\pi\in O}x_{O,w}
=\frac{1}{|O|}|O|x_{O,w}=x_{O,w}. \tag*{(38)} ∣ O ∣ 1 π ∈ O ∑ x π , w = ∣ O ∣ 1 π ∈ O ∑ x O , w = ∣ O ∣ 1 ∣ O ∣ x O , w = x O , w . (38) Parts (a) and (b) of Proposition 7.6 show that this bijection Φ \Phi Φ
the E E E π : E → { 1 , 2 , 3 , … } \pi:E\to\{1,2,3,\ldots\} π : E → { 1 , 2 , 3 , … } g π = π g\pi=\pi g π = π
and
the E g E^g E g π ‾ : E g → { 1 , 2 , 3 , … } \overline{\pi}:E^g\to\{1,2,3,\ldots\} π : E g → { 1 , 2 , 3 , … }
Hence, we can substitute Φ ( π ) \Phi(\pi) Φ ( π ) π ‾ \overline{\pi} π ∑ π ‾ is an E g -partition x π ‾ , w g \sum_{\overline{\pi}\text{ is an }E^g\text{-partition}}x_{\overline{\pi},w^g} ∑ π is an E g -partition x π , w g
∑ π ‾ is an E g -partition x π ‾ , w g = ∑ π is an E -partition; g π = π x Φ ( π ) , w g = ∑ π is an E -partition; g π = π x π , w , \sum_{\overline{\pi}\text{ is an }E^g\text{-partition}}x_{\overline{\pi},w^g}
=
\sum_{\substack{\pi\text{ is an }E\text{-partition;}\\g\pi=\pi}}x_{\Phi(\pi),w^g}
=
\sum_{\substack{\pi\text{ is an }E\text{-partition;}\\g\pi=\pi}}x_{\pi,w}, π is an E g -partition ∑ x π , w g = π is an E -partition; g π = π ∑ x Φ ( π ) , w g = π is an E -partition; g π = π ∑ x π , w , (by Proposition 7.6 (c)) whence
∑ π is an E -partition; g π = π x π , w = ∑ π ‾ is an E g -partition x π ‾ , w g = Γ ( E g , w g ) (39) \sum_{\substack{\pi\text{ is an }E\text{-partition;}\\g\pi=\pi}}x_{\pi,w}
=
\sum_{\overline{\pi}\text{ is an }E^g\text{-partition}}x_{\overline{\pi},w^g}
=
\Gamma(E^g,w^g) \tag*{(39)} π is an E -partition; g π = π ∑ x π , w = π is an E g -partition ∑ x π , w g = Γ ( E g , w g ) (39) (by (37)). This proves (36).
Now,
Γ ( E , w , G ) = ∑ O is a G -orbit on Par E x O , w = ∑ O is a G -orbit on Par E 1 ∣ O ∣ ∑ π ∈ O x π , w = ∑ O is a G -orbit on Par E ∑ π ∈ O 1 ∣ O ∣ x π , w 1 ∣ O ∣ = 1 ∣ G ∣ ∑ g ∈ G ; g π = π 1 (by (32), applied to F = Par E ) = ∑ O is a G -orbit on Par E ∑ π ∈ O ( 1 ∣ G ∣ ∑ g ∈ G ; g π = π 1 ) x π , w = ∑ π is an E -partition ( 1 ∣ G ∣ ∑ g ∈ G ; g π = π 1 ) x π , w = 1 ∣ G ∣ ∑ π is an E -partition ∑ g ∈ G ; g π = π x π , w = 1 ∣ G ∣ ∑ g ∈ G ∑ π is an E -partition ; g π = π x π , w = 1 ∣ G ∣ ∑ g ∈ G Γ ( E g , w g ) (by (36)) = 1 ∣ G ∣ ∑ g ∈ G Γ ( ( E g , ⟨ 1 g , ⟨ 2 g ) , w g ) . (40) \begin{aligned}
\Gamma(E,w,G)
&= \sum_{\substack{O\text{ is a }G\text{-orbit on }\operatorname{Par} E}} x_{O,w}
= \sum_{\substack{O\text{ is a }G\text{-orbit on }\operatorname{Par} E}} \frac{1}{\lvert O\rvert}\sum_{\pi\in O}x_{\pi,w}\\
&= \sum_{\substack{O\text{ is a }G\text{-orbit on }\operatorname{Par} E}}\sum_{\pi\in O}\frac{1}{\lvert O\rvert}x_{\pi,w}
\qquad\frac{1}{\lvert O\rvert}=\frac{1}{\lvert G\rvert}\sum_{\substack{g\in G;\\g\pi=\pi}}1
\quad\text{(by (32), applied to }F=\operatorname{Par} E\text{)}\\
&= \sum_{\substack{O\text{ is a }G\text{-orbit on }\operatorname{Par} E}}\sum_{\pi\in O}
\left(\frac{1}{\lvert G\rvert}\sum_{\substack{g\in G;\\g\pi=\pi}}1\right)x_{\pi,w}\\
&= \sum_{\pi\text{ is an }E\text{-partition}}
\left(\frac{1}{\lvert G\rvert}\sum_{\substack{g\in G;\\g\pi=\pi}}1\right)x_{\pi,w}
= \frac{1}{\lvert G\rvert}\sum_{\pi\text{ is an }E\text{-partition}}\sum_{\substack{g\in G;\\g\pi=\pi}}x_{\pi,w}\\
&= \frac{1}{\lvert G\rvert}\sum_{g\in G}\sum_{\substack{\pi\text{ is an }E\text{-partition};\\g\pi=\pi}}x_{\pi,w}
= \frac{1}{\lvert G\rvert}\sum_{g\in G}\Gamma(E^{g},w^{g})
\qquad\text{(by (36))}\\
&= \frac{1}{\lvert G\rvert}\sum_{g\in G}\Gamma\left(\left(E^{g},\langle{}^{g}_{1},\langle{}^{g}_{2}\right),w^{g}\right). \tag*{(40)}
\end{aligned} Γ ( E , w , G ) = O is a G -orbit on Par E ∑ x O , w = O is a G -orbit on Par E ∑ ∣ O ∣ 1 π ∈ O ∑ x π , w = O is a G -orbit on Par E ∑ π ∈ O ∑ ∣ O ∣ 1 x π , w ∣ O ∣ 1 = ∣ G ∣ 1 g ∈ G ; g π = π ∑ 1 (by (32), applied to F = Par E ) = O is a G -orbit on Par E ∑ π ∈ O ∑ ∣ G ∣ 1 g ∈ G ; g π = π ∑ 1 x π , w = π is an E -partition ∑ ∣ G ∣ 1 g ∈ G ; g π = π ∑ 1 x π , w = ∣ G ∣ 1 π is an E -partition ∑ g ∈ G ; g π = π ∑ x π , w = ∣ G ∣ 1 g ∈ G ∑ π is an E -partition ; g π = π ∑ x π , w = ∣ G ∣ 1 g ∈ G ∑ Γ ( E g , w g ) (by (36)) = ∣ G ∣ 1 g ∈ G ∑ Γ ( ( E g , ⟨ 1 g , ⟨ 2 g ) , w g ) . (40) Hence, Γ ( E , w , G ) ∈ QSym \Gamma(E,w,G)\in\operatorname{QSym} Γ ( E , w , G ) ∈ QSym
Applying the map S S S (40) , we obtain
S ( Γ ( E , w , G ) ) = 1 ∣ G ∣ ∑ g ∈ G S ( Γ ( ( E g , ⟨ 1 g , ⟨ 2 g ⟩ ) , w g ) ) = 1 ∣ G ∣ ∑ g ∈ G ( − 1 ) ∣ E g ∣ Γ ( ( E g , ⟨ 1 g , ⟨ 2 g ⟩ ) , w g ) . (41) \begin{aligned}
S\bigl(\Gamma(E,w,G)\bigr)
&=\frac{1}{\lvert G\rvert}\sum_{g\in G}S\bigl(\Gamma((E^{g},\langle{}_{1}^{g},\langle{}_{2}^{g}\rangle),w^{g})\bigr)\\
&=\frac{1}{\lvert G\rvert}\sum_{g\in G}(-1)^{\lvert E^{g}\rvert}\Gamma\bigl((E^{g},\langle{}_{1}^{g},\langle{}_{2}^{g}\rangle),w^{g}\bigr). \tag*{(41)}
\end{aligned} S ( Γ ( E , w , G ) ) = ∣ G ∣ 1 g ∈ G ∑ S ( Γ (( E g , ⟨ 1 g , ⟨ 2 g ⟩) , w g ) ) = ∣ G ∣ 1 g ∈ G ∑ ( − 1 ) ∣ E g ∣ Γ ( ( E g , ⟨ 1 g , ⟨ 2 g ⟩) , w g ) . (41) On the other hand, for every g ∈ G g\in G g ∈ G sign E g \operatorname{sign}_{E}g sign E g E E E e ∈ E e\in E e ∈ E g e ge g e g ∈ G g\in G g ∈ G E E E sign E g = 1 \operatorname{sign}_{E}g=1 sign E g = 1 G G G O O O Par E \operatorname{Par} E Par E π ∈ O \pi\in O π ∈ O
\begin{cases}
\dfrac{1}{\lvert O\rvert}, & \text{if }O\text{ is }E\text{-coeven};\\
0, & \text{if }O\text{ is not }E\text{-coeven}
\end{cases}
=
\frac{1}{\lvert G\rvert}\sum_{\substack{g\in G;\\g\pi=\pi}}\operatorname{sign}_{E}g \tag*{(42)}\end{cases}
((33) , applied to $F=\operatorname{Par} E). Furthermore,
sign E g = ( − 1 ) ∣ E ∣ − ∣ E g ∣ (43) \operatorname{sign}_{E}g=(-1)^{\lvert E\rvert-\lvert E^{g}\rvert} \tag*{(43)} sign E g = ( − 1 ) ∣ E ∣ − ∣ E g ∣ (43) for every g ∈ G g\in G g ∈ G 41
The permutation ζ \zeta ζ E E E e ∈ E e\in E e ∈ E g e ge g e ζ \zeta ζ g g g E E E ζ \zeta ζ g g g E E E ζ \zeta ζ g g g E E E E g E^{g} E g E g E^{g} E g ζ \zeta ζ
But if σ \sigma σ X X X σ \sigma σ ( − 1 ) ∣ X ∣ − ∣ X σ ∣ (-1)^{\lvert X\rvert-\lvert X^{\sigma}\rvert} ( − 1 ) ∣ X ∣ − ∣ X σ ∣ X σ X^{\sigma} X σ σ \sigma σ X = E X=E X = E σ = ζ \sigma=\zeta σ = ζ X σ = E g X^{\sigma}=E^{g} X σ = E g ζ \zeta ζ ( − 1 ) ∣ E ∣ − ∣ E g ∣ (-1)^{\lvert E\rvert-\lvert E^{g}\rvert} ( − 1 ) ∣ E ∣ − ∣ E g ∣ E g E^{g} E g ζ \zeta ζ sign E g = ( − 1 ) ∣ E ∣ − ∣ E g ∣ \operatorname{sign}_{E}g=(-1)^{\lvert E\rvert-\lvert E^{g}\rvert} sign E g = ( − 1 ) ∣ E ∣ − ∣ E g ∣ sign E g \operatorname{sign}_{E}g sign E g ζ \zeta ζ
Now,
Γ + ( E , w , G ) = ∑ O is an E -coeven G -orbit on Par E x O , w = 1 ∣ O ∣ ∑ π ∈ O x π , w = 1 ∣ O ∣ ∑ π ∈ O x π , w (by (38)) = ∑ O is a G -orbit on Par E { 1 ∣ O ∣ , if O is E -coeven ; 0 , if O is not E -coeven ∑ π ∈ O x π , w ( here, we have extended the sum to all G -orbits on Par E (not just the E -coeven ones); but all new addends are 0 and therefore do not influence the value of the sum ) = ∑ O is a G -orbit on Par E ∑ π ∈ O { 1 ∣ O ∣ , if O is E -coeven ; 0 , if O is not E -coeven x π , w = 1 ∣ G ∣ ∑ g ∈ G ; g π = π sign E g (by (41)) = ∑ O is a G -orbit on Par E ∑ π ∈ O ( 1 ∣ G ∣ ∑ g ∈ G ; g π = π sign E g ) x π , w = ∑ π is an E -partition ( 1 ∣ G ∣ ∑ g ∈ G ; g π = π sign E g ) x π , w = 1 ∣ G ∣ ∑ g ∈ G ∑ π is an E -partition ; g π = π ( sign E g ) x π , w = 1 ∣ G ∣ ∑ g ∈ G ( − 1 ) ∣ E ∣ − ∣ E g ∣ Γ ( ( E g , ⟨ g 1 g , g 2 g ⟩ ) , w g ) = 1 ∣ G ∣ ∑ g ∈ G ( − 1 ) ∣ E ∣ − ∣ E g ∣ Γ ( ( E g , ⟨ g 1 g , g 2 g ⟩ ) , w g ) . (44) \begin{aligned}
\Gamma^+(\mathrm{E},w,G)
&=\sum_{\substack{O\text{ is an }E\text{-coeven }G\text{-orbit on }\operatorname{Par}\mathrm{E}}} x_{O,w}
=\frac{1}{|O|}\sum_{\pi\in O}x_{\pi,w}\\
&=\frac{1}{|O|}\sum_{\pi\in O}x_{\pi,w}\qquad\text{(by (38))}\\
&=\sum_{\substack{O\text{ is a }G\text{-orbit on }\operatorname{Par}\mathrm{E}}}
\begin{cases}
\frac{1}{|O|},&\text{if }O\text{ is }E\text{-coeven};\\
0,&\text{if }O\text{ is not }E\text{-coeven}
\end{cases}
\sum_{\pi\in O}x_{\pi,w}\\
&\qquad\left(\text{here, we have extended the sum to all }G\text{-orbits on }\operatorname{Par}\mathrm{E}\right.\\
&\qquad\left.\text{(not just the }E\text{-coeven ones); but all new addends are }0\right.\\
&\qquad\left.\text{and therefore do not influence the value of the sum}\right)\\
&=\sum_{\substack{O\text{ is a }G\text{-orbit on }\operatorname{Par}\mathrm{E}}}
\sum_{\pi\in O}
\begin{cases}
\frac{1}{|O|},&\text{if }O\text{ is }E\text{-coeven};\\
0,&\text{if }O\text{ is not }E\text{-coeven}
\end{cases}
x_{\pi,w}\\
&=\frac{1}{|G|}\sum_{g\in G;\,g\pi=\pi}\operatorname{sign}_{E}g
\qquad\text{(by (41))}\\
&=\sum_{\substack{O\text{ is a }G\text{-orbit on }\operatorname{Par}\mathrm{E}}}
\sum_{\pi\in O}
\left(\frac{1}{|G|}\sum_{\substack{g\in G;\\g\pi=\pi}}\operatorname{sign}_{E}g\right)x_{\pi,w}\\
&=\sum_{\substack{\pi\text{ is an }E\text{-partition}}}
\left(\frac{1}{|G|}\sum_{\substack{g\in G;\\g\pi=\pi}}\operatorname{sign}_{E}g\right)x_{\pi,w}\\
&=\frac{1}{|G|}\sum_{g\in G}\sum_{\substack{\pi\text{ is an }E\text{-partition};\\g\pi=\pi}}
(\operatorname{sign}_{E}g)x_{\pi,w}\\
&=\frac{1}{|G|}\sum_{g\in G}(-1)^{|E|-|E^{g}|}
\Gamma\left(\left(E^{g},\langle g^{g}_{1},g^{g}_{2}\rangle\right),w^{g}\right)\\
&=\frac{1}{|G|}\sum_{g\in G}(-1)^{|E|-|E^{g}|}
\Gamma\left(\left(E^{g},\langle g^{g}_{1},g^{g}_{2}\rangle\right),w^{g}\right). \tag*{(44)}
\end{aligned} Γ + ( E , w , G ) = O is an E -coeven G -orbit on Par E ∑ x O , w = ∣ O ∣ 1 π ∈ O ∑ x π , w = ∣ O ∣ 1 π ∈ O ∑ x π , w (by (38)) = O is a G -orbit on Par E ∑ { ∣ O ∣ 1 , 0 , if O is E -coeven ; if O is not E -coeven π ∈ O ∑ x π , w ( here, we have extended the sum to all G -orbits on Par E (not just the E -coeven ones); but all new addends are 0 and therefore do not influence the value of the sum ) = O is a G -orbit on Par E ∑ π ∈ O ∑ { ∣ O ∣ 1 , 0 , if O is E -coeven ; if O is not E -coeven x π , w = ∣ G ∣ 1 g ∈ G ; g π = π ∑ sign E g (by (41)) = O is a G -orbit on Par E ∑ π ∈ O ∑ ∣ G ∣ 1 g ∈ G ; g π = π ∑ sign E g x π , w = π is an E -partition ∑ ∣ G ∣ 1 g ∈ G ; g π = π ∑ sign E g x π , w = ∣ G ∣ 1 g ∈ G ∑ π is an E -partition ; g π = π ∑ ( sign E g ) x π , w = ∣ G ∣ 1 g ∈ G ∑ ( − 1 ) ∣ E ∣ − ∣ E g ∣ Γ ( ( E g , ⟨ g 1 g , g 2 g ⟩ ) , w g ) = ∣ G ∣ 1 g ∈ G ∑ ( − 1 ) ∣ E ∣ − ∣ E g ∣ Γ ( ( E g , ⟨ g 1 g , g 2 g ⟩ ) , w g ) . (44) Hence, Γ + ( E , w , G ) ∈ Q S y m \Gamma^+(\mathrm{E},w,G)\in\mathrm{QSym} Γ + ( E , w , G ) ∈ QSym
The group G G G > 1 >_{1} > 1 < 1 <_{1} < 1 ( E , > 1 , < 2 ) (E, >_{1}, <_{2}) ( E , > 1 , < 2 ) 42 (44) to ( E , > 1 , < 2 ) (E, >_{1}, <_{2}) ( E , > 1 , < 2 ) > 1 >_{1} > 1 > 1 g >_{1}^{g} > 1 g E E E < 1 <_{1} < 1 < 1 g <_{1}^{g} < 1 g
Γ + ( ( E , > 1 , < 2 ) , w , G ) = 1 ∣ G ∣ ∑ g ∈ G ( − 1 ) ∣ E ∣ − ∣ E g ∣ Γ ( ( E g , > 1 g , < 2 g ) , w g ) . \Gamma^{+}\left((E, >_{1}, <_{2}), w, G\right)=\frac{1}{|G|}\sum_{g\in G}(-1)^{|E|-|E^{g}|}\Gamma\left((E^{g}, >_{1}^{g}, <_{2}^{g}), w^{g}\right). Γ + ( ( E , > 1 , < 2 ) , w , G ) = ∣ G ∣ 1 g ∈ G ∑ ( − 1 ) ∣ E ∣ − ∣ E g ∣ Γ ( ( E g , > 1 g , < 2 g ) , w g ) . Multiplying both sides of this equality by ( − 1 ) ∣ E ∣ (-1)^{|E|} ( − 1 ) ∣ E ∣
( − 1 ) ∣ E ∣ Γ + ( ( E , > 1 , < 2 ) , w , G ) = ( − 1 ) ∣ E ∣ 1 ∣ G ∣ ∑ g ∈ G ( − 1 ) ∣ E ∣ − ∣ E g ∣ Γ ( ( E g , > 1 g , < 2 g ) , w g ) = 1 ∣ G ∣ ∑ g ∈ G ( − 1 ) ∣ E ∣ ( − 1 ) ∣ E ∣ − ∣ E g ∣ Γ ( ( E g , > 1 g , < 2 g ) , w g ) = 1 ∣ G ∣ ∑ g ∈ G ( − 1 ) ∣ E g ∣ Γ ( ( E g , > 1 g , < 2 g ) , w g ) = S ( Γ ( E , w , G ) ) (by xref‘(40)‘). \begin{aligned}
(-1)^{|E|}\Gamma^{+}\left((E, >_{1}, <_{2}), w, G\right)
&=(-1)^{|E|}\frac{1}{|G|}\sum_{g\in G}(-1)^{|E|-|E^{g}|}\Gamma\left((E^{g}, >_{1}^{g}, <_{2}^{g}), w^{g}\right)\\
&=\frac{1}{|G|}\sum_{g\in G}(-1)^{|E|}(-1)^{|E|-|E^{g}|}\Gamma\left((E^{g}, >_{1}^{g}, <_{2}^{g}), w^{g}\right)\\
&=\frac{1}{|G|}\sum_{g\in G}(-1)^{|E^{g}|}\Gamma\left((E^{g}, >_{1}^{g}, <_{2}^{g}), w^{g}\right)\\
&=S\left(\Gamma(E,w,G)\right)\qquad\text{(by {xref}`(40)`).}
\end{aligned} ( − 1 ) ∣ E ∣ Γ + ( ( E , > 1 , < 2 ) , w , G ) = ( − 1 ) ∣ E ∣ ∣ G ∣ 1 g ∈ G ∑ ( − 1 ) ∣ E ∣ − ∣ E g ∣ Γ ( ( E g , > 1 g , < 2 g ) , w g ) = ∣ G ∣ 1 g ∈ G ∑ ( − 1 ) ∣ E ∣ ( − 1 ) ∣ E ∣ − ∣ E g ∣ Γ ( ( E g , > 1 g , < 2 g ) , w g ) = ∣ G ∣ 1 g ∈ G ∑ ( − 1 ) ∣ E g ∣ Γ ( ( E g , > 1 g , < 2 g ) , w g ) = S ( Γ ( E , w , G ) ) (by xref ‘(40)‘). This completes the proof of Theorem 4.7. □
Application: Jochemko's theorem
We shall now demonstrate an application of Theorem 4.7: namely, we will use it to provide an alternative proof of [15 Theorem 2.13] . The way we derive [15 Theorem 2.13] from Theorem 4.7 is classical, and in fact was what originally motivated the discovery of Theorem 4.7 (although, of course, it cannot be conversely derived from [15 Theorem 2.13] , so it is an actual generalization).
An intermediate step between [15 Theorem 2.13] and Theorem 4.7 will be the following fact:
Corollary 8.1. Let E = ( E , < 1 , < 2 ) E=(E,<_{1},<_{2}) E = ( E , < 1 , < 2 ) w : E → { 1 , 2 , 3 , … } w:E\to\{1,2,3,\ldots\} w : E → { 1 , 2 , 3 , … } G G G E E E G G G < 1 <_{1} < 1 < 2 <_{2} < 2 w w w q ∈ N q\in\mathbb{N} q ∈ N Par q E \operatorname{Par}_{q}E Par q E E E E { 1 , 2 , … , q } \{1,2,\ldots,q\} { 1 , 2 , … , q } G G G Par q E \operatorname{Par}_{q}E Par q E Par q E \operatorname{Par}_{q}E Par q E G G G G G G { 1 , 2 , … , q } E \{1,2,\ldots,q\}^{E} { 1 , 2 , … , q } E
(a) There exists a unique polynomial Ω E , G ∈ Q [ X ] \Omega_{E,G}\in\mathbb{Q}[X] Ω E , G ∈ Q [ X ] q ∈ N q\in\mathbb{N} q ∈ N
Ω E , G ( q ) = (the number of all G -orbits on Par q E ) . (45) \Omega_{E,G}(q)=\text{(the number of all $G$-orbits on $\operatorname{Par}_{q}E$)}. \tag*{(45)} Ω E , G ( q ) = (the number of all G -orbits on Par q E ) . (45) (b) This polynomial satisfies
Ω E , G ( − q ) = ( − 1 ) ∣ E ∣ ( the number of all E -coeven G -orbits on Par q ( E , > 1 , < 2 ) ) = ( − 1 ) ∣ E ∣ ( the number of all E -coeven G -orbits on Par q ( E , < 1 , > 2 ) ) (46) \begin{aligned}
\Omega_{E,G}(-q) = (-1)^{|E|}\left(\text{the number of all }E\text{-coeven }G\text{-orbits on }\operatorname{Par}_{q}(E,>_{1},<_{2})\right) \\
&= (-1)^{|E|}\left(\text{the number of all }E\text{-coeven }G\text{-orbits on }\operatorname{Par}_{q}(E,<_{1},>_{2})\right) \tag*{(46)}
\end{aligned} Ω E , G ( − q ) = ( − 1 ) ∣ E ∣ ( the number of all E -coeven G -orbits on Par q ( E , > 1 , < 2 ) ) = ( − 1 ) ∣ E ∣ ( the number of all E -coeven G -orbits on Par q ( E , < 1 , > 2 ) ) (46) for all q ∈ N q \in\mathbb{N} q ∈ N
Proof of Corollary 8.1 (sketched). Set k = Q \mathbf{k} = \mathbb{Q} k = Q f ∈ QSym f \in\operatorname{QSym} f ∈ QSym q ∈ N q \in\mathbb{N} q ∈ N ps 1 ( f ) ( q ) ∈ Q \operatorname{ps}^{1}(f)(q) \in\mathbb{Q} ps 1 ( f ) ( q ) ∈ Q
ps 1 ( f ) ( q ) = f ( 1 , 1 , … , 1 ⏟ q times , 0 , 0 , 0 , … ) . \operatorname{ps}^{1}(f)(q)=f\left(\underbrace{1,1,\ldots,1}_{q\ \text{times}},0,0,0,\ldots\right). ps 1 ( f ) ( q ) = f q times 1 , 1 , … , 1 , 0 , 0 , 0 , … . (that is, ps 1 ( f ) ( q ) \operatorname{ps}^{1}(f)(q) ps 1 ( f ) ( q ) x 1 , x 2 , … , x q x_{1},x_{2},\ldots,x_{q} x 1 , x 2 , … , x q x q + 1 , x q + 2 , x q + 3 , … x_{q+1},x_{q+2},x_{q+3},\ldots x q + 1 , x q + 2 , x q + 3 , … f f f
(a) Consider the elements Γ ( E , w , G ) \Gamma(E,w,G) Γ ( E , w , G ) Γ + ( E , w , G ) \Gamma^{+}(E,w,G) Γ + ( E , w , G ) QSym \operatorname{QSym} QSym Par q E \operatorname{Par}_{q}E Par q E G G G Par E \operatorname{Par}E Par E
Now, [13 Proposition 7.1.7 (i)] shows that, for any given f ∈ QSym f \in\operatorname{QSym} f ∈ QSym Q [ X ] \mathbb{Q}[X] Q [ X ] q ∈ N q \in\mathbb{N} q ∈ N ps 1 ( f ) ( q ) \operatorname{ps}^{1}(f)(q) ps 1 ( f ) ( q ) f = Γ ( E , w , G ) f=\Gamma(E,w,G) f = Γ ( E , w , G ) Q [ X ] \mathbb{Q}[X] Q [ X ] q ∈ N q \in\mathbb{N} q ∈ N ps 1 ( Γ ( E , w , G ) ) ( q ) \operatorname{ps}^{1}(\Gamma(E,w,G))(q) ps 1 ( Γ ( E , w , G )) ( q ) q ∈ N q \in\mathbb{N} q ∈ N
ps 1 ( Γ ( E , w , G ) ) ( q ) = Γ ( E , w , G ) ⏟ O is a G -orbit on Par E ( 1 , 1 , … , 1 ⏟ q times , 0 , 0 , 0 , … ) = ∑ O is a G -orbit on Par E x O , w ( 1 , 1 , … , 1 ⏟ q times , 0 , 0 , 0 , … ) = ∑ O is a G -orbit on Par E { 1 , if O ⊆ Par q E ; 0 , if O ⊈ Par q E = ∑ O is a G -orbit on Par q E { 1 , if O ⊆ Par q E ; 0 , if O ⊈ Par q E = ∑ O is a G -orbit on Par q E 1 = ( the number of all G -orbits on Par q E ) , (47) \begin{aligned}
\operatorname{ps}^{1}(\Gamma(E,w,G))(q)
&=\underbrace{\Gamma(E,w,G)}_{ O\text{ is a }G\text{-orbit on }\operatorname{Par}E}
\left(\underbrace{1,1,\ldots,1}_{q\ \text{times}},0,0,0,\ldots\right)\\
&=\sum_{O\text{ is a }G\text{-orbit on }\operatorname{Par}E}x_{O,w}
\left(\underbrace{1,1,\ldots,1}_{q\ \text{times}},0,0,0,\ldots\right)\\
&=\sum_{O\text{ is a }G\text{-orbit on }\operatorname{Par}E}
\begin{cases}
1, & \text{if }O\subseteq\operatorname{Par}_{q}E;\\
0, & \text{if }O\not\subseteq\operatorname{Par}_{q}E
\end{cases}\\
&=\sum_{O\text{ is a }G\text{-orbit on }\operatorname{Par}_{q}E}
\begin{cases}
1, & \text{if }O\subseteq\operatorname{Par}_{q}E;\\
0, & \text{if }O\not\subseteq\operatorname{Par}_{q}E
\end{cases}\\
&=\sum_{O\text{ is a }G\text{-orbit on }\operatorname{Par}_{q}E}1
=\left(\text{the number of all }G\text{-orbits on }\operatorname{Par}_{q}E\right), \tag*{(47)}
\end{aligned} ps 1 ( Γ ( E , w , G )) ( q ) = O is a G -orbit on Par E Γ ( E , w , G ) q times 1 , 1 , … , 1 , 0 , 0 , 0 , … = O is a G -orbit on Par E ∑ x O , w q times 1 , 1 , … , 1 , 0 , 0 , 0 , … = O is a G -orbit on Par E ∑ { 1 , 0 , if O ⊆ Par q E ; if O ⊆ Par q E = O is a G -orbit on Par q E ∑ { 1 , 0 , if O ⊆ Par q E ; if O ⊆ Par q E = O is a G -orbit on Par q E ∑ 1 = ( the number of all G -orbits on Par q E ) , (47) this rewrites as follows: There exists a unique polynomial in Q [ X ] \mathbb{Q}[X] Q [ X ] q ∈ N q \in\mathbb{N} q ∈ N G G G Par q E \operatorname{Par}_q E Par q E
(b) [13 Proposition 7.1.7 (i)] shows that, for any given f ∈ QSym f \in\operatorname{QSym} f ∈ QSym Q [ X ] \mathbb{Q}[X] Q [ X ] q ∈ N q \in\mathbb{N} q ∈ N ps 1 ( f ) ( q ) \operatorname{ps}^{1}(f)(q) ps 1 ( f ) ( q ) ps 1 ( f ) \operatorname{ps}^{1}(f) ps 1 ( f ) [13 Proposition 7.1.7] . From our above proof of Corollary 8.1 (a), we see that
Ω E , G = ps 1 ( Γ ( E , w , G ) ) . \Omega_{E,G}=\operatorname{ps}^{1}\left(\Gamma(E,w,G)\right). Ω E , G = ps 1 ( Γ ( E , w , G ) ) . But [13 Proposition 7.1.7 (iii)] shows that, for any f ∈ QSym f \in\operatorname{QSym} f ∈ QSym m ∈ N m \in\mathbb{N} m ∈ N ps 1 ( S ( f ) ) ( m ) = ps 1 ( f ) ( − m ) \operatorname{ps}^{1}(S(f))(m)=\operatorname{ps}^{1}(f)(-m) ps 1 ( S ( f )) ( m ) = ps 1 ( f ) ( − m ) f = Γ ( E , w , G ) f=\Gamma(E,w,G) f = Γ ( E , w , G )
ps 1 ( S ( Γ ( E , w , G ) ) ) ( m ) = ps 1 ( Γ ( E , w , G ) ) ( − m ) = Ω E , G ( − m ) . \operatorname{ps}^{1}\left(S\left(\Gamma(E,w,G)\right)\right)(m)=\operatorname{ps}^{1}\left(\Gamma(E,w,G)\right)(-m)=\Omega_{E,G}(-m). ps 1 ( S ( Γ ( E , w , G ) ) ) ( m ) = ps 1 ( Γ ( E , w , G ) ) ( − m ) = Ω E , G ( − m ) . for any m ∈ N m \in\mathbb{N} m ∈ N m ∈ N m \in\mathbb{N} m ∈ N
Ω E , G ( − m ) = ps 1 ( S ( Γ ( E , w , G ) ) = ( − 1 ) ∣ E ∣ Γ + ( ( E , ≻ 1 , ≺ 2 ) , w , G ) (by Theorem 4.7) ) ( m ) = ps 1 ( ( − 1 ) ∣ E ∣ Γ + ( ( E , ≻ 1 , ≺ 2 ) , w , G ) ) ( m ) = ( − 1 ) ∣ E ∣ ps 1 ( Γ + ( ( E , ≻ 1 , ≺ 2 ) , w , G ) ) ( m ) . \begin{aligned}
\Omega_{E,G}(-m)=\operatorname{ps}^{1}\left(\underset{=(-1)^{|E|}\Gamma^{+}((E,\succ_{1},\prec_{2}),w,G)\text{ (by Theorem 4.7)}}{S\left(\Gamma(E,w,G)\right)}\right)(m) \\
&=\operatorname{ps}^{1}\left((-1)^{|E|}\Gamma^{+}((E,\succ_{1},\prec_{2}),w,G)\right)(m) \\
&=(-1)^{|E|}\operatorname{ps}^{1}\left(\Gamma^{+}((E,\succ_{1},\prec_{2}),w,G)\right)(m).
\end{aligned} Ω E , G ( − m ) = ps 1 ( = ( − 1 ) ∣ E ∣ Γ + (( E , ≻ 1 , ≺ 2 ) , w , G ) (by Theorem 4.7) S ( Γ ( E , w , G ) ) ) ( m ) = ps 1 ( ( − 1 ) ∣ E ∣ Γ + (( E , ≻ 1 , ≺ 2 ) , w , G ) ) ( m ) = ( − 1 ) ∣ E ∣ ps 1 ( Γ + (( E , ≻ 1 , ≺ 2 ) , w , G ) ) ( m ) . Renaming m m m q q q q ∈ N q \in\mathbb{N} q ∈ N
Ω E , G ( − q ) = ( − 1 ) ∣ E ∣ ps 1 ( Γ + ( ( E , ≻ 1 , ≺ 2 ) , w , G ) ) ( q ) . (48) \Omega_{E,G}(-q)=(-1)^{|E|}\operatorname{ps}^{1}\left(\Gamma^{+}((E,\succ_{1},\prec_{2}),w,G)\right)(q). \tag*{(48)} Ω E , G ( − q ) = ( − 1 ) ∣ E ∣ ps 1 ( Γ + (( E , ≻ 1 , ≺ 2 ) , w , G ) ) ( q ) . (48) But just as we proved (47) , we can show that every q ∈ N q \in\mathbb{N} q ∈ N
ps 1 ( Γ + ( E , w , G ) ) ( q ) = ( the number of all E -coeven G -orbits on Par q E ) . \operatorname{ps}^{1}\left(\Gamma^{+}(E,w,G)\right)(q)=(\text{the number of all }E\text{-coeven }G\text{-orbits on }\operatorname{Par}_{q}E). ps 1 ( Γ + ( E , w , G ) ) ( q ) = ( the number of all E -coeven G -orbits on Par q E ) . Applying this to ( E , ≻ 1 , ≺ 2 ) (E,\succ_{1},\prec_{2}) ( E , ≻ 1 , ≺ 2 ) E E E
ps 1 ( Γ + ( ( E , ≻ 1 , ≺ 2 ) , w , G ) ) ( q ) = ( the number of all E -coeven G -orbits on Par q ( E , ≻ 1 , ≺ 2 ) ) . \operatorname{ps}^{1}\left(\Gamma^{+}((E,\succ_{1},\prec_{2}),w,G)\right)(q)
=(\text{the number of all }E\text{-coeven }G\text{-orbits on }\operatorname{Par}_{q}(E,\succ_{1},\prec_{2})). ps 1 ( Γ + (( E , ≻ 1 , ≺ 2 ) , w , G ) ) ( q ) = ( the number of all E -coeven G -orbits on Par q ( E , ≻ 1 , ≺ 2 )) . Now, (47) becomes
Ω E , G ( − q ) = ( − 1 ) ∣ E ∣ ps 1 ( Γ + ( ( E , ≻ 1 , ≺ 2 ) , w , G ) ) ( q ) = ( the number of all E -coeven G -orbits on Par q ( E , ≻ 1 , ≺ 2 ) ) = ( − 1 ) ∣ E ∣ ( the number of all E -coeven G -orbits on Par q ( E , ≻ 1 , ≺ 2 ) ) . \begin{aligned}
\Omega_{E,G}(-q)=(-1)^{|E|}\underset{=(\text{the number of all }E\text{-coeven }G\text{-orbits on }\operatorname{Par}_{q}(E,\succ_{1},\prec_{2}))}{\operatorname{ps}^{1}\left(\Gamma^{+}((E,\succ_{1},\prec_{2}),w,G)\right)(q)} \\
&=(-1)^{|E|}(\text{the number of all }E\text{-coeven }G\text{-orbits on }\operatorname{Par}_{q}(E,\succ_{1},\prec_{2})).
\end{aligned} Ω E , G ( − q ) = ( − 1 ) ∣ E ∣ = ( the number of all E -coeven G -orbits on Par q ( E , ≻ 1 , ≺ 2 )) ps 1 ( Γ + (( E , ≻ 1 , ≺ 2 ) , w , G ) ) ( q ) = ( − 1 ) ∣ E ∣ ( the number of all E -coeven G -orbits on Par q ( E , ≻ 1 , ≺ 2 )) . In order to prove Corollary 8.1 (b), it thus remains to show that
(the number of all E -coeven G -orbits on Par q ( E , > 1 , < 2 ) ) = (the number of all E -coeven G -orbits on Par q ( E , < 1 , > 2 ) ) (49) \begin{aligned}
&\text{(the number of all $E$-coeven $G$-orbits on $\operatorname{Par}_q(E, >_1, <_2)$)}\\
&=\text{(the number of all $E$-coeven $G$-orbits on $\operatorname{Par}_q(E, <_1, >_2)$)} \tag*{(49)}
\end{aligned} (the number of all E -coeven G -orbits on Par q ( E , > 1 , < 2 ) ) = (the number of all E -coeven G -orbits on Par q ( E , < 1 , > 2 ) ) (49) for every q ∈ N q \in\mathbb{N} q ∈ N
Proof of (49) : Let q ∈ N q \in\mathbb{N} q ∈ N w 0 : { 1 , 2 , … , q } → { 1 , 2 , … , q } w_0:\{1,2,\ldots,q\}\to\{1,2,\ldots,q\} w 0 : { 1 , 2 , … , q } → { 1 , 2 , … , q } i ∈ { 1 , 2 , … , q } i \in\{1,2,\ldots,q\} i ∈ { 1 , 2 , … , q } q + 1 − i q+1-i q + 1 − i
Par q ( E , > 1 , < 2 ) ⟶ Par q ( E , < 1 , > 2 ) , π ↦ w 0 ∘ π \operatorname{Par}_q(E, >_1, <_2) \longrightarrow\operatorname{Par}_q(E, <_1, >_2), \qquad\pi\mapsto w_0 \circ\pi Par q ( E , > 1 , < 2 ) ⟶ Par q ( E , < 1 , > 2 ) , π ↦ w 0 ∘ π is an isomorphism of G G G Par q ( E , > 1 , < 2 ) ≅ Par q ( E , < 1 , > 2 ) \operatorname{Par}_q(E, >_1, <_2) \cong\operatorname{Par}_q(E, <_1, >_2) Par q ( E , > 1 , < 2 ) ≅ Par q ( E , < 1 , > 2 ) G G G
Now, the second formula of [15 Theorem 2.13] follows from our (45), applied to E = ( P , ≺ , < ω ) E=(P,\prec,<_{\omega}) E = ( P , ≺ , < ω ) < ω <_{\omega} < ω P P P ( p < ω q ) ⟺ ( ω ( p ) < ω ( q ) ) (p<_{\omega}q)\Longleftrightarrow(\omega(p)<\omega(q)) ( p < ω q ) ⟺ ( ω ( p ) < ω ( q )) [15 Theorem 2.13] can also be derived from our above arguments. We leave the details to the reader.
A final question
With the results proven above (specifically, Theorems 4.2 and 4.7 ), we have obtained formulas for a large class of quasisymmetric generating functions for maps from a double poset to { 1 , 2 , 3 , … } \{1,2,3,\ldots\} { 1 , 2 , 3 , … }
Question 9.1. In [11 ] , I have studied generalizations of Whitney’s famous non-broken-circuit theorem for graphs and matroids. One of the cornerstones of that study is the bijection Φ \Phi Φ [11 proofs of Lemma 2.8, Lemma 5.29 and Lemma 8.25] , which is uncannily reminiscent of the involution T T T Theorem 4.2 . (Actually, this bijection Φ \Phi Φ Φ \Phi Φ T T T
