Explain the proof below in detail and also find alternative terms for „good“ and „superb“, specifically ones that capture the essence of the definition and aren't just some arbitrary measure of „goodness“: 
Proposition 25.3.2. (a) Suppose that p 6≤ q. Then for every g ∈S

n there exists a transposition σ i,j ∈S p

such that σ

i,j · g = g · h for h ∈S q∨.

(b) Suppose that p = q. Then there exists a unique S

p orbit O ∈ S n /S p∨, such

that:

(i) The action of S

p on O is simple (see Sect. 20.5.1).

(ii) For every g ∈S

n such that ̄g ∈ S n /S p∨ does not belong to O, there exists a

transposition σ

i,j ∈S p such that σ i,j · g = g· h for h ∈S p∨.

Let us deduce Theorem 25.2.5 from Proposition 25.3.2.


25.3.4. Let us call an element g ∈S

n “good” if there does not exists of a permuta-

tion σ

i,j ∈S p such that

σ

i,j · g = g· h, h ∈S q∨.

Let X denote the set { 1,...,n}, and we regard q∨ and p as two ways to represent it as a disjoint union of subsets

t

i X ′ i ' X 't

j X ′′ j.

An element g ∈S

n is an automorphism of X.

25.3.5. Let is view the union t

i X ′ i as a set X ′, and the union t

j X ′′ j as a set X ′′,

and let view the element g as an isomorphism of sets Φ: X ′ → X ′′. We will view the decomposition

X ′ = t

i X ′ i

as a partition according to q∨, where the blocks are positioned horizontally. We will view the decomposition

X ′′ = t

j X ′ j

as a partition according to p, where the blocks are positioned vertically. Note that the latter can also be thought as a partition according to p∨, where the blocks are positioned horizontally.

Let us call a map Φ: X ′ → X ′′ “good” if for every row X ′

i ⊂ X ′, its elements

get sent by means of Φ to elements of X ′′ having distinct latitudes.

It is easy to see that “goodness” of g ∈S

n is equivalent to the “goodness” of the

corresponding map Φ.

Furthermore, multiplication of g on the left (resp., right) by an element of S

p

(resp., S

q) corresponds to composing (resp., pre-composing) Φ with an automor-

phism of X ′′ (resp., X ′) that acts along the columns (resp., rows).

25.3.6. Let us call an element Φ: X ′ → X ′′ “superb” if it is ”good”, and the following additional condition holds:

For every index i (numbering the rows in X ′) and every x′ ∈X ′

i, the element Φ(x′)

is such that all elements underneath it in its column in X ′′ are of the form Φ(̃ x′)

for ̃ x′ ∈X ′ ̃i with ̃i < i.

We have: Lemma 25.3.7. For a given “good” map Φ there exists a unique element h′′ ∈S

p

such that the map

Φ

s:= h′′ ◦ Φ

is “superb.”

The proof of the lemma is given below. Let us assume it, and finish the proof of the proposition.

25.3.8. Let us prove point (a) of the proposition. We need to show that if there exists a good map Φ: X ′ → X ′′, then p∨ ≥ q∨, i.e., that for every i, the volume of the first i rows of X ′ is ≤ than the volume of the first i rows of X ′′.

By Lemma 25.3.7, with no restriction of generality, we can assume that Φ is “superb.” However, for a“superb” map, the first i rows of X ′ get sent to the first i rows of X ′′. Hence, our assertion follows from the pigeonhole principle.

25.3.9. Let us prove point (b) of the proposition. In this case X ′ and X ′′ have the same shape, and there exists a distinguished “good” map Φ

0: X ′ → X ′′, namely

the identity map. We need to show that every other “good” Φ can be uniquely written as h′′ ◦ Φ

0 ◦ h′

where h′′ acts along the columns of X ′′ and h′ acts along the rows of X ′. By Lemma 25.3.7, with no restriction of generality, we can assume that Φ is “superb.” In this we need to show that Φ can be uniquely written as

Φ

0 ◦ h′ ,

where h′ acts along the rows of X ′. However, for X ′ and X ′′ having the same shape, a “superb” map sends the ith row of X ′ bijectively to the ith row of X ′′, and the assertion is manifest. 

Proof of Lemma 25.3.7. We define the map Φ

s (and hence the corresponding ele-

ment h′′) inductively on i. Suppose that Φ

s has been defined on the rows X ′

1 t...t

X ′

i− 1. With no restriction of generality, we can assume that Φ and Φ s are equal on

the above rows.

For every element x ∈ X

i consider the transposition σ x ∈ S p along the column

to which Φ(x) belongs, that puts it in the lowest position not occupied by elements

Φ(̃ x′) for ̃x′ ∈X ′ ̃i with ̃i < i.

We define Φ

s on X i by

(Π

x∈X i σ x)

· Φ.

Note that the order of the product in Π

x∈X i σ x does not matter, because the

“goodness” of Φ implies that all of the σ

x ’s act along distinct columns, and hence,

commute.

The resulting element Φ

s satisfies the condition of being superb on the first i

rows bu construction. The uniquness of Φ

s also follows from the construction.