Young’s natural idempotents as polynomials

Alain Lascoux

Abstract. — Coding permutations as monomials, one obtains a compact expression of representatives of Young’s natural idempotents for the symmetric group, or of qidempotents in the Hecke algebra.

Introduction. — Young made an extensive use of the iterated factorization

∑_{μ∈𝔖(n+1)} μ = ( ∑_{μ∈𝔖(n)} μ) (1 + σ_{n} + σ_{n}σ_{n−1} + ⋯ + σ_{n} ⋯ σ_{1}) ,

where σ_{k} is the simple transposition (k, k + 1) and 𝔖(n) the symmetric group on n letters. For example, he writes

∑_{μ∈𝔖(4)} μ = (1 + σ_{1})(1 + σ_{2} + σ_{2}σ_{1})(1 + σ_{3} + σ_{3}σ_{2} + σ_{3}σ_{2}σ_{1}) .

Coding permutations μ as monomials x^{[μ]}, in a way we shall explain below, one has a similar factorization

(1.1)  ∑_{μ∈𝔖(4)} x^{[μ]} = (1 + x_{1} + x_{1}^{2} + x_{1}^{3})(1 + x_{2} + x_{2}^{2})(1 + x_{3}) ,

but now, the product, in the ring of polynomials, has no relation whatsoever with the product in the group algebra H of the symmetric group, and must be considered only as a tool to give a compact form of some distinguished elements of H.

We shall only treat the case of Young’s natural idempotents [Yo], [Ru], [J-K], which are the product of two factors of the type ∑ μ and ∑(−1)^{ℓ(μ)}μ, summations on two Young subgroups.

We first need to introduce some combinatorial tools.

Given a variable x and an integer n, denote

(x, n) := 1 + x + x^{2} + ⋯ + x^{n−1} .

We embed symmetric groups 𝔖(n) into each other by adding fixed points n + 1, n + 2 …, and define H to be the inductive limit of H_{n} := ℤ[𝔖(n)].

The code of a permutation μ = (μ_{1}, …, μ_{n}) is the table of inversion : code(μ) = [c_{1}, …, c_{n}], where c_{i} := card(j > i, μ_{j} < μ_{i}). Instead of the code we shall rather take the monomial

(1.2)  x^{[μ]} := x_{1}^{c_{1}}x_{2}^{c_{2}} ⋯ x_{n}^{c_{n}} ,

and induce by linearity a morphism P from H to the ring P of polynomials in an infinite number of variables x_{1}, x_{2}, . . .. Thus every polynomial inside P is the image of one and only one element of H.

It is easy to check that

P ( ∑_{μ∈𝔖(4)} μ) := ∑_{μ∈𝔖(4)} x^{[μ]} = (1 + x_{1} + x_{1}^{2} + x_{1}^{3})(1 + x_{2} + x_{2}^{2})(1 + x_{3}) ,

and more generally,

(1.3)  P ( ∑_{μ∈𝔖(n)} μ) := (x_{1}, n)(x_{2}, n − 1) ⋯ (x_{n}, 1) ,

(1.4)  P ( ∑_{μ∈𝔖(n)} (−1)^{ℓ(μ)}μ) := (−x_{1}, n)(−x_{2}, n − 1) ⋯ (−x_{n}, 1) ,

because a vector c in ℕ^{n} is the code of a permutation in 𝔖(n) iff c_{1} ≤ n − 1, c_{2} ≤ n − 2, …, c_{n} ≤ 0.

We define the (right) twisted action of the symmetric group on the ring of polynomials P by

(1.5)  ∀f, g ∈ H , P (f) ⊙ g := P (fg) .

More explicitly, given any c ∈ ℕ^{n} and σ = (k, k + 1) a simple transposition, the twisted action of σ on P satisfies

(1.6)  \{ \begin{matrix}x^{c} ⊙ σ & = & ⋯ x_{k}^{c_{k+1}+1}x_{k+1}^{c_{k}} ⋯ & if c_{k} ≤ c_{k+1} \\ x^{c} ⊙ σ & = & ⋯ x_{k}^{c_{k+1}}x_{k+1}^{c_{k}−1} ⋯ & if not. \end{matrix} .

Equivalently, denoting f → f^{σ} the usual action of the symmetric group (interchanging x_{k} and x_{k+1}), one has

(1.7)  \{ \begin{matrix}x^{c} ⊙ σ & = & (x^{c})^{σ} x_{k} & if c_{k} ≤ c_{k+1} \\ x^{c} ⊙ σ & = & (x^{c})^{σ}/x_{k+1} & if not \end{matrix} .

The symmetric group. — Given a composition I = (i_{1}, …, i_{r}) ∈ ℕ^{r}, let us denote 𝔖(I) the Young sub-group 𝔖(i_{1}) × 𝔖(i_{2}) × ⋯ × 𝔖(i_{r}) of 𝔖(n) permuting the letters in each successive block of respective lengths i_{1}, …, i_{r}, where n is the weight of I ( := i_{1} + ⋯ + i_{r}).

Write _{I} for the sum of elements of 𝔖(I), and ∇_{I} for its image under the involution μ ⟶ (−1)^{ℓ(μ)}μ.

We say that two compositions are conjugate when the partitions obtained by reordering I and J are conjugate (cf. [Mcd]). For example, each of {331, 313, 133} is conjugate to each of {223, 232, 322}, because the two partitions 331 and 322 are conjugate (i.e. their diagrams are exchanged by symmetry of the two coordinate axes).

The key point in Young’s first construction of idempotents [Yo] is the following property, which was isolated by Von Neumann (cf. [Ru]):

LEMMA 2.1. — Given two conjugate compositions I, J of weight n then the space _{I} H_{n}∇_{J} is one-dimensional.

By left and right multiplication by permutations, one obtains the elements that Young associates to the Young sub-groups determined by the rows and columns of tableaux, and which constitute his natural idempotents (in opposition with the orthogonal idempotents he obtained later [Ru], [J-K]).

We can thus restrict to considering only elements of the type _{I}μ∇_{J}, where I is a decreasing partition, J its conjugate increasing composition, and μ any permutation such that _{I}μ∇_{J} is non-zero.

A tabloid t of shape I is a filling of each box of the diagram of I (of coordinate (i, j)) with a number t(i, j). To it, we associate a polynomial

(2.2)  P ol(t) := ∏_{(i,j)}(x_{t(i,j)} , j)

by taking the product on all the boxes of t.

For example,

P ol ( \begin{matrix}4 \\ 5 & 1 & 3 \\ 2 & 6 & 7 \end{matrix} ) = \begin{matrix}(x_{4}, 3) \\ (x_{5}, 2) & (x_{1}, 2) & (x_{3}, 2) \\ (x_{2}, 1) & (x_{6}, 1) & (x_{7}, 1) \end{matrix}

(read the right side as a product).

The column-tabloid t_{I}^{c} of shape I is the tabloid obtained by numbering the boxes of I columnwise by 1, 2, 3, …, and the row-tabloid t_{I}^{r}, by rowwise numbering. The weight-tabloid w_{I} of shape I is the filling of the diagram of I, putting in each box the number of boxes strictly southwest of it (i.e. the box of coordinate (i, j) is filled with the number (i − 1)(j − 1)).

Take for example I = 3322. Then

t_{I}^{c} = 1 4 2 5 7 9 3 6 8 10 , t_{I}^{r} = 1 2 3 4 5 6 7 8 9 10 , w_{I} = 0 2 0 1 2 3 0 0 0 0 .

Reading rowwise the tabloid t_{I}^{c}, one gets a permutation that we shall denote μ_{I}, and which is such that _{I}μ_{I}∇_{J} is different from 0.

To a partition I, we also need to associate a monomial

x^{<I>} := x_{μ_{1}}^{c_{1}} ⋯ x_{μ_{n}}^{c_{n}} = x^{[μ]} ,

where μ = μ_{I}, and where (c_{1}, …, c_{n}) is the code of μ. Equivalently, the exponent of x^{<I>} is obtained by reading the tabloid w_{I} columnwise, from left to right.

With the preceding partition 3322, μ_{I} = 14 2579 36810 has code 02 0123 0000, and x^{<I>} = x^{000 210 20 30} = (x_{1}^{0}x_{2}^{0}x_{3}^{0})(x_{4}^{2}x_{5}^{1}x_{6}^{0})(x_{7}^{2}x_{8}^{0})(x_{9}^{3}x_{10}^{0}).

LEMMA 2.3. — Given a partition I, then

P ( _{I} · μ_{I}) = P ol(t_{I}^{r})x^{<I>}

Proof. — The permutation μ_{I} is exactly the one which, when acting on the values in the tabloid t_{I}^{c}, transforms t_{I}^{c} into t_{I}^{r}. We have to check that this permutation of values inside the tabloid t_{I}^{c} corresponds exactly to the twisted action of the symmetric group on P ol(t_{I}^{r}).

Factorize μ_{I} into cycles ζ^{1}, … ζ^{n} such that the code of ζ^{k}, k = 1, …, n is equal to [0, …, 0, c_{k}, 0, … 0], where [c_{1}, …, c_{n}] is the code of μ_{I}, and suppose by induction that there exists a monomial x^{♣} such that

P ( _{I}ζ^{1} ⋯ ζ^{k}) = P ol(t_{I}^{c}^{ζ^{1}···ζ^{k}}) x^{♣} .

The letters 1, …, k occupy in the tabloid t_{k} := t_{I}^{c}^{ζ^{1}···ζ^{k}} the same position as in t_{I}^{r}, and the other letters are placed columnwise in the remaining part of the diagram (the exponential notation t^{ζ} still means the image of the tabloid t under the permutation ζ of the letters of t).

The value k + 1 occupies a certain box in t_{I}^{r}, of height h, which in t_{k} is occupied by a value p. One has to move k+1 to its final place by successive transpositions (p, p − 1), (p − 1, p − 2), …, (k + 2, k + 1). Suppose that an intermediate step

P ( _{I}ζ^{1} ⋯ ζ^{k}(p, p − 1) ⋯ (r + 1, r)) = P ol(t_{k}^{(p,p−1)···(r+1,r)})x^{♣}x_{r}^{p−r} .

This last polynomial is equal to

(x_{r−1}, h′)(x_{r}, h) x_{r}^{p−r} Q ,

where the factor Q is independent of x_{r−1}, x_{r}. Since h′ ≤ p − r + 1, the twisted action of the simple transposition (r−1, r) on (x_{r−1}, h′)(x_{r}, h)x_{r}^{p−r} consists in exchanging x_{r} and x_{r−1} and multiplying by x_{r−1}.

Finally,

P ( _{I}ζ^{1} ⋯ ζ^{k}ζ^{k+1}) = P ol(t_{I}^{c}^{ζ^{1}···ζ^{k}ζ^{k+1}}) x^{♣} x_{k}^{p−k} ,

and the required result follows at the last step, when obtaining the final tabloid t_{I}^{r}

For example, taking I = 333, an intermediate step in the computation of P ( _{I} μ_{I}) will produce the polynomial

P ol ( \begin{matrix}1 & 2 & 7 \\ 3 & 5 & 8 \\ 4 & 6 & 9 \end{matrix} ) x_{2}^{2} .

To put 3 into its final position, we have to take the image of the preceding polynomial under the sequence of transpositions (7, 6), (6, 5), (5, 4), (4, 3), i.e. taking only the relevant factors, compute the image of

(x_{3}, 2)(x_{5}, 2)(x_{7}, 3):

⟶^{⊙(7,6)}(x_{3}, 2)(x_{5}, 2) x_{6} (x_{6}, 3)

⟶^{⊙(6,5)}(x_{3}, 2) x_{5}^{2} (x_{5}, 3)(x_{6}, 2)

⟶^{⊙(5,4)}(x_{3}, 2) x_{4}^{3} (x_{4}, 3)(x_{6}, 2)

⟶^{⊙(4,3)}x_{3}^{4} (x_{3}, 3)(x_{4}, 2)(x_{6}, 2)

which is the factor in P ol ( \begin{matrix}1 & 2 & 3 \\ 4 & 6 & 8 \\ 5 & 7 & 9 \end{matrix} ) involving the variables x_{3}, …, x_{7}.

Given two strictly increasing sequences of integers B = (β_{1}, …, β_{r}), Γ = (γ_{1}, …, γ_{r}) of the same length, denote x_{B}^{Γ} := x_{β_{1}}^{γ_{1}} ⋯ x_{β_{r}}^{γ_{r}} and

(2.4)  ∇(B, Γ) := ∑_{ν∈𝔖(r)}(−1)^{ℓ(ν)}(x_{B}^{Γ})^{ν} x_{B}^{[ν]} ,

where x_{B}^{[ν]} = x_{β_{1}}^{c_{1}} ⋯ x_{β_{r}}^{c_{r}}, with [c_{1}, …, c_{r}] = code(ν).

THEOREM (2.5). — Given a (decreasing) partition I, let J be its conjugate increasing composition. Then the image of the idempotent _{I} μ_{I} ∇_{J} as a polynomial is

1 ⊙ _{I} ⊙ μ_{I} ⊙ ∇_{J} = P ( _{I} μ_{I} ∇_{J}) = P ol(t_{I}^{r}) ∏_{i} ∇(B^{i}, Γ^{i}) ,

where B^{1}, B^{2}, … are the successive rows of t_{I}^{r} (reading downwards), and Γ^{1}, Γ^{2}, …, the rows of the weight tabloid w_{I}.

Proof. — The polynomial P ol(t_{I}^{r})x^{<I>} factorizes into factors corresponding to each row of t_{I}^{r}, and ∇_{J} also factorizes into operators acting on the elements of one row only. Thus take any integer h and consider the row of height h in t_{I}^{r}. Up to a shift of indices, let 1, 2, … r be the entries in this row. The h-th row of w_{I} is 0, (h − 1), 2(h − 1), …, (r − 1)(h − 1). The factor of P ol(t_{I}^{r})x^{<I>} corresponding to row h is equal to

f = (x_{1}, h) ⋯ (x_{r}, h)x_{1}^{0}x_{2}^{h−1} ⋯ x_{r}^{(r−1)(h−1)} .

Since each (x_{i}, h) is of degree ≤ h − 1, the image of f under the twisted action of the permutation μ is equal to f^{μ} x^{[μ]}, and thus is equal to

(x_{1}, h) ⋯ (x_{r}, h) (x_{1}^{0}x_{2}^{h−1} ⋯ x_{r}^{(r−1)(h−1)})^{μ} x^{[μ]} .

By product, we get the statement of the theorem For example,

P ( _{3321} μ_{3321} ∇_{234}) = P ol ( \begin{matrix}1 & 2 \\ 3 & 4 & 5 \\ 6 & 7 & 8 & 9 \end{matrix} ) ∇(12, 02) ∇(345, 012) =

= (x_{1}, 3)(x_{2}, 3)(x_{2}^{2} − x_{1}^{3})(x_{3}, 2)(x_{4}, 2)(x_{5}, 2)
(x_{3}^{0}x_{4}^{1}x_{5}^{2} − x_{3}^{0}x_{4}^{3}x_{5}^{1} − x_{3}^{2}x_{4}^{0}x_{5}^{2} + x_{3}^{4}x_{4}^{0}x_{5}^{1} + x_{3}^{2}x_{4}^{3}x_{5}^{0} − x_{3}^{4}x_{4}^{2}x_{5}^{0})
(1 − x_{6} + x_{6}^{2} − x_{6}^{3})(1 − x_{7} + x_{7}^{2})(1 − x_{8})

Hecke algebra. — The preceding construction easily extends to the qdeformation of the algebra of the symmetric group. Recall that the Hecke algebra H_{n}^{q} of the symmetric group 𝔖(n) has linear basis T_{μ}, μ ∈ 𝔖(n), and its multiplicative structure is determined by

T_{μ}T_{σ} = T_{μσ}  if ℓ(μσ) > ℓ(μ)
= (q − 1)T_{μ} + qT_{μσ}  otherwise,

for any permutation μ and any simple transposition σ.

Under the morphism (still denoted P) T_{μ} ⟶ x^{[μ]} := P (T_{μ}), the space of polynomials P in an infinite number of variables x_{1}, x_{2}, … can be identified with the limit of P (H_{m}^{q}), m → ∞ and inherits, from the right multiplication of H_{m}^{q} by H_{n}^{q}, m ≥ n, of a structure of right H_{n}-module. In particular, the submodule 1 H_{n}^{q} has linear basis x^{I}, i_{1} ≤ n − 1, i_{2} ≤ n − 2, …, i_{n} ≤ 0.

More explicitly, given I ∈ ℕ^{n} and σ = (k, k +1) a simple transposition, the action of H_{n}^{q} on P satisfies

(3.2)  \{ \begin{matrix}x^{I}T_{σ} & = & (x^{I})^{σ} x_{k} & if i_{k} ≤ i_{k+1} \\ x^{I}T_{σ} & = & (q − 1)x^{I} + q(x^{I})^{σ}/x_{k+1} & if not. \end{matrix}

We have characterized in [LS1], [LS2] the rational local operators acting on the ring of polynomials and satisfying the braid relations (they also satisfy an Hecke relation (T_{k} − q_{1})(T_{k} − q_{2}) = 0). The above action (3.2) does not belong to this family, because it uses the non rational projections π_{k}^{+} and π_{k}^{−} :

π_{k}^{+}(x^{I}) = \{ \begin{matrix}x^{I} & if i_{k} ≤ i_{k+1} \\ 0 & if not \end{matrix}

π_{k}^{−}(x^{I}) = \{ \begin{matrix}0 & if i_{k} ≤ i_{k+1} \\ x^{I} & if not \end{matrix}

Let _{I}^{q} denote the sum ∑_{μ∈𝔖(I)} T_{μ} and ∇_{I}^{q} be its image under the morphism T_{μ} ⟶ (−1/q)^{ℓ(μ)}T_{μ}.

For example,

_{3}^{q} = T_{123} + T_{213} + T_{132} + T_{231} + T_{312} + T_{321} ,

∇_{3}^{q} = T_{123} − q^{−1}T_{213} − q^{−1}T_{132} + q^{−2}T_{231} + q^{−2}T_{312} − q^{−3}T_{321} .

We have

(3.3)  P ( _{r}^{q}) = P ( _{r}) = (x_{1}, r) ⋯ (x_{r}, 1)

and

(3.4)  P (∇_{r}^{q}) = (−x_{1}/q, r) ⋯ (−x_{r}/q, 1) .

We still have the property that, given two conjugate compositions I, J of weight n, _{I}^{q}H_{n}^{q}∇_{J}^{q} is a 1-dimensional module (cf. [DKLLST], more general intertwining spaces are described by [D-K]);

From this property, one can write q-idempotents and describe the irreducible representations of the Hecke algebra in characteristic 0, for generic q (see [D-J]).

Taking into account that ∇_{J}^{q} differs from ∇_{J} by the appearance of powers of q, we define, for two sets B, Γ of integers

(3.5)  ∇^{q}(B, Γ) := ∑_{μ∈𝔖(r)}(−q)^{−ℓ(μ)}(x_{B}^{Γ})^{μ} x_{B}^{[μ]}

(for q = 1, one recovers 2.4).

The computations that we made in the case of the symmetric group remain valid, because at each step we had to compute the image under a simple transposition (k, k +1) = σ of a polynomial f such that π_{k}^{−}(f) = 0, in which case the action of T_{σ} coincides with the twisted action of σ. Therefore we have :

THEOREM (3.6). — Given a (decreasing) partition I, let J be its conjugate increasing composition. Then the image of the q-idempotent _{I}^{q} μ_{I} ∇_{J}^{q} as a polynomial is

P ( _{I}^{q} μ_{I} ∇_{J}^{q}) = P ol(t_{I}^{r}) ∏_{i} ∇^{q}(B^{i}, Γ^{i}) ,

where B^{1}, B^{2}, … are the successive rows of t_{I}^{r} (reading downwards), and Γ^{1}, Γ^{2}, …, the rows of the weight tabloid w_{I}.

For example, in the case of partition I = (3, 3, 2), the corresponding idempotent for the symmetric group 𝔖(8) can be written as the polynomial

(x_{6}^{2} − x_{6} + 1)(1 + x_{2} + x_{2}^{2})(1 + x_{5})(1 + x_{4})(1 + x_{3})(x_{3}^{4}x_{4}^{2} − x_{3}^{4}x_{5} − x_{3}^{2}x_{4}^{3} + x_{3}^{2}x_{5}^{2} + x_{4}^{3}x_{5} − x_{4}x_{5}^{2})(1 + x_{1} + x_{1}^{2})(x_{1}^{3} − x_{2}^{2})(−1 + x_{7}),

and the corresponding q-idempotent for the Hecke algebra is (up to normalization by a power of q)

(1 + x_{2} + x_{2}^{2})(x_{6}^{2} + q^{2} − qx_{6})(1 + x_{5})(1 + x_{4})(1 + x_{3})(qx_{3}^{4}x_{5} − x_{3}^{4}x_{4}^{2} − q^{2}x_{3}^{2}x_{5}^{2} + qx_{3}^{2}x_{4}^{3} + x_{4}x_{5}^{2}q^{3} − x_{4}^{3}x_{5}q^{2})(1 + x_{1} + x_{1}^{2})(x_{1}^{3} − x_{2}^{2}q)(q − x_{7}) .

Both polynomials code a summation on the 40320 permutations of 𝔖(8) that the sytem ACE [Ve] readily accepted to perform, and factorize, producing the above TEX output that MAPLE transformed by a random ordering of exponents.

References

[D-J] R.Dipper, G.James, Representations of Hecke algebras of general linear groups, Proc. London M.S. 52 (1986) 20–52. [D-K] G.Duchamp, S.Kim, Intertwining spaces associated with q-analogues of the Young symmetrizers in the Hecke algebra , Banach Center Publications 36, Warszawa (1996) 61–70.

[DKLLST] G.Duchamp, D.Krob, A.Lascoux, B.Leclerc, T.Scharf, J-Y.Thibon, Euler-Poincaré characteristic and polynomial representation of Iwahori-Hecke algebra, Pub. RIMS 31 (1995) 179–201. [J-K] G.D.James, A.Kerber, The representation theory of the symmetric group, Addison-Wesley (1981).

[LS1] A.Lascoux & M.P.Schützenberger, Symmetry and Flag manifold, Invariant theory , Springer L.N. 996 (1983) 118–144.

[LS2] A.Lascoux & M.P.Schützenberger, Symmetrisation operators on polynomial rings, Funct. Anal i prigogi 21 (1987) 77-78.

[Mcd] I.G.Macdonald, Symmetric functions and Hall polynomials, Oxford Math. Mono (1979).

[Ru] D.E.Rutherford, Substitutional analysis, Edinburgh, the University Press (1948).

[Yo] A.Young, Collected work, University of Toronto Press (1977).

[Ve] S.Veigneau, ACE, an algebraic combinatorics environment for the computer algebra system MAPLE, Thesis (first chapter), Université de Marne La Vallée (1996).

Alain Lascoux Université de Marne-la-Vallée Institut Gaspard Monge

2 rue de la Butte Verte, 93166 Noisy-le-Grand Cedex

            Alain.Lascoux@univ-mlv.fr
       http://phalanstere.univ-mlv.fr/ al/