A BIJECTION BETWEEN PROCTOR’S AND SUNDARAM’S ODD ORTHOGONAL TABLEAUX

MARKUS FULMEK AND CHRISTIAN KRATTENTHALER^{†} INSTITUT FÜR MATHEMATIK UNIVERSITÄT WIEN STRUDLHOFGASSE 4 A-1090 VIENNA, AUSTRIA

Abstract. An explicit bijection between Proctor’s odd orthogonal tableaux and Sundaram’s odd orthogonal tableaux is given.

1. Introduction Over the last twenty years many enumerative combinatorialists have been inter-

ested in identities which count the number of tableaux or plane partitions of a given type. Sometimes two families of tableaux or plane partitions have the same counts. But it seems to be very rare to find bijections between two such families. In this paper we use the Garsia–Milne technique to generate a bijection in such a situation.

This situation is the following. Proctor [10, 11] and Sundaram [14] defined different tableaux that both enumerate the odd orthogonal characters. To be more precise, the generating function with respect to a certain weight for either Proctor’s tableaux of shape λ or Sundaram’s tableaux of shape λ equals the irreducible character of SO (2n + 1) indexed by λ. Since the generating functions are equal, there must exist a weight-preserving bijection between the two sets of tableaux. The purpose of this paper is to construct an explicit such bijection.

Our bijection bases on the fact that both types of tableaux “generate” Jacobi– Trudi-type identities for their generating functions, as shown in [2]. In fact, the bijection combines mappings from [2] with the involution principle of Garsia and Milne [3].

We remark that lately there has been considerable interest in combinatorial descriptions of classical group characters. Such descriptions evolved mainly from either algebraic combinatorics or algebraic geometry, culminating in Proctor’s [11] and Littelmann’s [8] papers, respectively, which can also serve as reference papers. However, the relations between the various combinatorial descriptions that have been developed are in most cases unclear, except for the general linear characters where all descriptions are more or less the same. In this paper we relate two combinatorial descriptions for orthogonal characters which come from the algebraic combinatorics side. Recently, Sheats [12] related the symplectic tableaux of King and El-Sharkaway [6] and the symplectic tableaux of DeConcini [1], the first coming from the algebraic combinatorics side, the second coming from the algebraic geometry side. But there is still much more work to be done to understand the relations, in particular between the descriptions that come from different sides.

† Supported in part by EC’s Human Capital and Mobility Program, grant CHRX-CT93-0400, the second author was also supported by the Austrian Science Foundation FWF, grant P10191-PHY

Our paper is organized as follows. In section 2 we define the odd orthogonal tableaux of Proctor and Sundaram and their weights. Since we use the involution principle we briefly review it in section 3. Then, in section 4 we give a rough outline of our bijection. The details of the underlying involutions are provided in section 5. An elaborate example is the subject of section 6. As indicated at the beginning, the ideas behind the involutions in section 5 stem from lattice path proofs for Jacobi–Trudi-type identities for the irreducible characters of SO (2n + 1) given in [2]. This background is explained in section 7. It may be helpful to read this section immediately after having digested what Proctor tableaux and Sundaram tableaux are and how the Garsia–Milne involution principle works, since it gives an idea of the “program” for our bijection, not requiring that the reader is familiar with [2]. Finally, in section 8 we comment on bijections between some more odd orthogonal tableaux, due to Proctor [11] and King and Welsh [7].

2. Proctor’s and Sundaram’s odd orthogonal tableaux For readers convenience, we recall some basic concepts. An r-tuple λ = (λ_{1}, …, λ_{r})

with λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{r} > 0 is called a partition of length r. We denote the length of the partition λ by ℓ(λ). The Ferrers board of λ is an array of cells with ℓ(λ) leftjustified rows and λ_{i} cells in row i. The conjugate of λ is the partition (λ′_{1}, …, λ′_{λ_{1}}) where λ′_{j} is the length of the j-th column in the Ferrers board of λ.

We shall consider fillings of the cells of a Ferrers board with positive integers. Given a filling T we write T_{i,j} for the entry in cell (i, j). Also, we write T_{.,j} for the entries in the j-th column of T. The notation T_{.,j} has to be understood in a suggestive sense, for instance, {T_{.,j} ≤ p} means the multiset of all entries in the j-th column of T that are at most p. 2.1. Sundaram tableaux. Now let λ be a partition with ℓ (λ) ≤ n+1. A (2n+1)- Sundaram tableau of shape λ is a filling T of the cells of the Ferrers board of λ with elements from {1, 2, …, 2n, ∞} such that

(1) entries along rows are weakly increasing, each row is allowed to contain only at most one entry ∞,

(2) entries along columns are weakly increasing, and strictly increasing with respect to the finite entries,

(3) all entries in row i are at least 2i − 1. Obviously it suffices to require (3) to hold for the first element in each row only, since rows are weakly increasing. So (3) is equivalent with

T_{i,1} ≥ 2i − 1 for 1 ≤ i ≤ ℓ (λ) . (2.1)

Figure 1 shows an example of a 9-Sundaram tableau of shape (5, 4, 3, 1, 1).

Example of a 9-Sundaram tableau

1 4 4 6 7 4 5 5 6 5 7 ∞ ∞ ∞

Figure 1

2.2. Proctor tableaux. Let λ be a partition. A (2n+1)-Proctor tableau of shape λ is a filling of the cells of the Ferrers board of λ with elements from {1, 2, …, 2n, 2n+ 1} such that

(1) entries along rows are weakly increasing,

(2) entries along columns are strictly increasing,

(3) the (2c)-th orthogonal condition is satisfied for all c (see below), and the (2n + 1)-st orthogonal condition is satisfied,

(4) the (2c)-th protection condition is satisfied for all c (see below).

A filling T satisfies the p-th orthogonal condition if the number of entries less or equal than p in the first two columns of T is less or equal to p. Stated more formally, this is

|{T_{.,1} ≤ p}| + |{T_{.,2} ≤ p}| ≤ p, (2.2)

where |S| denotes the cardinality of a multiset S, as usual.

A filling T satisfies the (2c)-th protection condition if whenever i + j = 2c and T_{i,1} = 2c − 1 and T_{j,2} = T_{j,3} = ⋯ = T_{j,h−1} = 2c − 1 and T_{j,h} = 2c, then we have T_{j−1,h} = 2c − 1. Stated in a more formal manner, this is

i + j = 2c and T_{i,1} = 2c − 1
and T_{j,2} = ⋯ = T_{j,h−1} = 2c − 1 (for h ≥ 2)
and T_{j,h} = 2c
(2.3)  implies T_{j−1,h} = 2c − 1.

The filling in Figure 2 satisfies the 6-th protection condition if and only if 5 is inserted instead of ∗ (choose i = 4 and j = 2). In fact, if ∗ = 5 then it is a 9-Proctor tableau of shape (5, 4, 3, 1).

Example of a 9-Proctor tableau, provided ∗ = 5

1 4 4 ∗ 6 2 5 5 6 3 7 8 5

Figure 2

Note that by the (2n+1)-st orthogonal condition for every (2n+1)-Proctor tableau of shape λ we must have λ′_{1} + λ′_{2} ≤ 2n + 1. 2.3. Odd orthogonal characters. For both types of (2n + 1)-orthogonal tableaux just introduced we define weights in the following way (the definition is the same for both types):

w (T) := ∏_{i=1}^{n} x_{i}^{#(2i−1∈T)−#(2i∈T)}. (2.4)

With this definition of weights, the irreducible character of the orthogonal group SO (2n + 1) indexed by λ is given as

so_{2n+1} (λ, x) = ∑_{T} w (T) , (2.5)

where the sum is over all (2n+1)-Proctor tableaux T of shape λ, or equivalently over all (2n + 1)-Sundaram tableaux T of shape λ. Hence there exists a weight-preserving bijection between odd orthogonal Proctor tableaux and odd orthogonal Sundaram tableaux of the same shape. The purpose of this work is to construct such a bijection explicitly.

3. The involution principle of Garsia and Milne Since we are going to rely on the involution principle of Garsia and Milne [3] (see

also [13, sec. 4.6]), we recall it first, for convenience.

Suppose we are given two finite sets 𝕊 and ℙ with signed weight functions w_{𝕊}, w_{ℙ}, respectively. Denote the subsets of positively/negatively signed elements of 𝕊 and ℙ by 𝕊^{+}/𝕊^{−} and ℙ^{+}/ℙ^{−}, respectively. Let there be sets G_{𝕊} and G_{ℙ} of “good” elements contained in the respective positive sets, i.e. G_{𝕊} ⊆ 𝕊^{+} and G_{ℙ} ⊆ ℙ^{+}. Denote the complementary sets of “bad” elements by B_{𝕊} := 𝕊 \ G_{𝕊} and B_{ℙ} := ℙ \ G_{ℙ}. Suppose there is a weight- and sign-preserving bijection 𝔞 between 𝕊 and ℙ, 𝔞 : 𝕊 ↦ ℙ. Furthermore, suppose that there are weight-preserving but sign-reversing involutions 𝔦_{𝕊} and 𝔦_{ℙ} on the respective sets of bad elements, 𝔦_{𝕊} : B_{𝕊} ↦ B_{𝕊} and 𝔦_{ℙ} : B_{ℙ} ↦ B_{ℙ}. (One can think of these involutions as “cancelling” all the bad elements.) Then there must be a weight-preserving bijection between the sets G_{𝕊} and G_{ℙ} of respective good elements. And an explicit such bijection, g say, can be constructed in the following algorithmic way. Start with some element x ∈ G_{𝕊}. Then g(x) is given by (𝔞 ∘ 𝔦_{𝕊} ∘ 𝔞^{−1} ∘ 𝔦_{ℙ})^{n} ∘ 𝔞 (x), for some n ≥ 0 (depending on x). To be precise, n is the minimal nonnegative integer such that (𝔞 ∘ 𝔦_{𝕊} ∘ 𝔞^{−1} ∘ 𝔦_{ℙ})^{n} ∘ 𝔞 (x) is in G_{ℙ}. (In fact, n is unique, since 𝔦_{ℙ} is not defined for an element of G_{ℙ}.) For a proof see [3] or [13, sec. 4.6].

Illustration of involution principle

[figure: +; B_{𝕊}^{+}; +; −; B_{𝕊}^{−}; −; + G_{𝕊} +; 𝔦_{𝕊}; 𝔦_{𝕊}; +; B_{ℙ}^{+}; +; −; B_{ℙ}^{−}; −; + G_{ℙ} +; 𝔦_{ℙ}; 𝔦_{ℙ}; 𝔞]

Figure 3

4. Outline of the bijection The reason that our bijection is not straight-forward but employs the involution

principle, is that (2n + 1)-Proctor tableaux and (2n + 1)-Sundaram tableaux are rather “far away from one another”. The first obvious difference is the set of entries. This is, of course, very easy to remove. Just replace 2n + 1 by ∞ in every (2n + 1)- Proctor tableau. Since neither entries 2n + 1 nor entries ∞ do contribute to the tableau’s weight, this certainly is a weight-preserving conversion. From now on we shall consider these converted tableaux and, by abuse of terminology, call them also (2n + 1)-Proctor tableaux.

In the following, let λ be a fixed partition with λ′_{1} + λ′_{2} ≤ 2n + 1 and ℓ(λ) ≤ n + 1. (Recall that λ′_{1} + λ′_{2} ≤ 2n + 1 is needed to have well-defined (2n + 1)-Proctor tableaux, and ℓ(λ) ≤ n+1 is needed to have well-defined (2n+1)-Sundaram tableaux.) Basically, in view of section 3, the only thing we have to do is to specify the sets 𝕊, ℙ, their weights w_{𝕊}, w_{ℙ}, the sets G_{𝕊}, G_{ℙ} of good elements, the bijection 𝔞, and the involutions 𝔦_{𝕊}, 𝔦_{ℙ} on the sets of bad elements.

Of course, the sets G_{𝕊} and G_{ℙ} of good elements are the set of (2n + 1)-Sundaram tableaux of shape λ and the set of (2n + 1)-Proctor tableaux of shape λ, respectively. Next we have to embed G_{𝕊} and G_{ℙ} into the bigger sets 𝕊 and ℙ. To describe these sets we have to set up some more terminology.

Consider our partition λ and think of the Ferrers board of λ in the following way: The lower edge forms a sequence of λ_{1} “steps”. Columns may be viewed as “heaps of cells” stacked on top of each “step”. The number of cells in the heap stacked on the i-th step is precisely λ′_{i} (by definition the length of column i). Now define a generalized Ferrers board of λ to consist of λ_{1} columns of arbitrary non-negative length, stacked on the “steps” of the Ferrers board of λ. Figure 4 gives an example of this concept, where λ = (4, 3, 2). Figure 4.a shows the Ferrers board of (4, 3, 2), while Figure 4.b shows a generalized Ferrers board of (4, 3, 2) with column-lengths 1, 5, 1, 0. By the rows of such a generalized Ferrers board of λ we mean the rows (in the usual sense) that contain at least one cell of the board (but may contain “holes”, too). The bottom-most row gets number λ′_{1}, the other rows are numbered “from bottom to top”, as indicated in Figure 4.

a. Ferrers board of (4, 3, 2) b. A generalized Ferrers board of (4, 3, 2)

−10123  1 2 3 4

Figure 4

Let σ ∈ 𝔖_{λ_{1}} (𝔖_{λ_{1}} denotes the symmetric group of order λ_{1}) be an arbitrary permutation and ε ∈ {−1, +1}^{λ_{1}} be an arbitrary vector of +1’s and −1’s. The generalized Ferrers board with parameters (λ, σ, ε) is the generalized Ferrers board F of λ where the length of the j-th column of F, denoted by cl_{j}(F), is given by

cl_{j}(F) = λ′_{j} − j + σ (j) · ε_{σ(j)}. (4.1)

An example with λ = (4, 3, 2), σ = 1423, and ε = (−1, 1, 1, 1) is displayed in Figure 4.b. Note that for σ = id and ε = (1, 1 …, 1) the generalized Ferrers board with parameters (λ, σ, ε) is precisely the (ordinary) Ferrers board of λ.

Our next definition concerns fillings of the cells of generalized Ferrers boards. A (2n + 1)-tabloid T with parameters (λ, σ, ε) (we shall frequently write T (λ, σ, ε) for short) is a filling of the cells of the generalized Ferrers board with parameters (λ, σ, ε) with elements from {1, 2 …, 2n, ∞} such that columns are weakly increasing, and strictly increasing with respect to the finite entries. So, entry ∞ may occur more than once in any column, occupying the bottom entries. When we display a tabloid we indicate the corresponding permutation σ by writing σ(j) beneath the j-th column, and the corresponding sign vector ε by writing the sign of ε_{σ(j)} beneath the j-th column. For example, the second tabloid in the second row of Figure 9 is a tabloid with parameters ((3, 3, 2, 2, 1, 1), 132, (−1, +1, +1)).

The signed weight of a tabloid T (λ, σ, ε) is defined by

w (T (λ, σ, ε)) := sgn (σ) · sgn (ε) · ∏_{i=1}^{n} x_{i}^{#(2i−1∈T)−#(2i∈T)}, (4.2)

where sgn (ε) := ∏_{k=1}^{λ_{1}} ε_{k}.

Now we are in the position to say what the sets 𝕊 and ℙ are. We define the set 𝕊, and also the set ℙ, to be the set of all (2n + 1)-tabloids T (λ, σ, ε), where σ varies over 𝔖_{λ_{1}} and ε varies over {−1, +1}^{λ_{1}} arbitrarily. For notational reasons we consider 𝕊 and ℙ as two different sets. Observe that the set G_{𝕊} of all (2n + 1)-Sundaram tableaux of shape λ, viewed as tabloids with parameters σ = id and ε = (1, 1, …, 1), is indeed contained in 𝕊, as well as the set G_{ℙ} of (2n + 1)-Proctor tableaux of shape λ, viewed as tabloids with parameters σ = id and ε = (1, 1, …, 1), is contained in ℙ. Of course, the weights w_{𝕊} and w_{ℙ} are given by w in (4.2).

Since 𝕊 and ℙ are the same set, we do not have to say much about the bijection 𝔞. It is simply the identity mapping. Note that this reduces the bijection g given by the involution principle to x ↦ (𝔦_{𝕊} ∘ 𝔦_{ℙ})^{n}(x), for some n depending on x. In plain words, 𝔦_{ℙ} and 𝔦_{𝕊} are applied alternatively to x, as long as possible.

Finally we have to specify the involutions 𝔦_{𝕊} and 𝔦_{ℙ} on the sets B_{𝕊} = 𝕊 \ G_{𝕊} and B_{ℙ} = ℙ \ G_{ℙ} of bad elements, respectively. This is done in full detail in the next section. Actually, we partition B_{𝕊} into two disjoint subsets B_{𝕊}^{1} and B_{𝕊}^{2} and construct involutions 𝔦_{𝕊}^{1} and 𝔦_{𝕊}^{2} for each of these. The involution 𝔦_{𝕊} then is simply the union of these two “subinvolutions”. Similarly, we partition B_{ℙ} into three disjoint subsets B_{ℙ}^{1}, B_{ℙ}^{2}, B_{ℙ}^{3} and construct involutions 𝔦_{ℙ}^{1}, 𝔦_{ℙ}^{2}, 𝔦_{ℙ}^{3} for each of these. The involution 𝔦_{ℙ} then is the union of these three “subinvolutions”.

5. The involutions We start with the involution 𝔦_{𝕊} : B_{𝕊} ↦ B_{𝕊}, since it is much easier to describe.

5.1. The involution 𝔦_{𝕊}. As promised in the previous section, we partition B_{𝕊} into two disjoint subsets B_{𝕊}^{1} and B_{𝕊}^{2}, and construct involutions 𝔦_{𝕊}^{1} and 𝔦_{𝕊}^{2} on each of these. To define B_{𝕊}^{1} and B_{𝕊}^{2} we introduce two types of violations. Then, given some tabloid in B_{𝕊}, we look at all the violations in the tabloid (there will be at least one), and pick up the “minimal” one (in a certain sense). If this violation is of the first type then the tabloid belongs to B_{𝕊}^{1}, otherwise it belongs to B_{𝕊}^{2}.

The first type of violation stems from (2.1). We define a Sundaram violation in row i of a (2n + 1)-tabloid T to be

(5.1) T_{i,1} < 2i − 1 or cell (i, 1) does not belong to T .

To motivate the second type of violation, recall that for Sundaram tabloids we required that columns are weakly increasing, and strictly increasing with respect to the finite entries (so that entry ∞ is allowed to occur more than once in any column). However, we did not say anything about the rows. So, tabloids might very well have nonincreasing rows or more than one entry ∞ in some row, both of which is forbidden for Sundaram tableaux. This leads us to define a violation of row monotonicity in row i and column j of a (2n + 1)-tabloid T to be the following:

(1) cell (i, j) belongs to T, j < λ_{1} and i ≤ λ′_{j+1},
(2) either T_{i,j} > T_{i,j+1},
or  T_{i,j} = T_{i,j+1} = ∞,
or  cell (i, j + 1) does not belong to T.

Now, given a (2n + 1)-tabloid T in B_{𝕊}, choose the maximal row, row I say, containing either a Sundaram or a row monotonicity violation, and choose the minimal column, column J say, which contains a violation in row I. (Of course, Sundaram violations always occur in column 1.) If in this row and column we have a Sundaram violation, then T belongs to B_{𝕊}^{1}, otherwise T belongs to B_{𝕊}^{2}.

There is one thing to check: We must show that all tabloids in B_{𝕊} do in fact contain either a Sundaram or a row monotonicity violation. Note that the tabloids in G_{𝕊} = 𝕊 \ B_{𝕊} (basically the Sundaram tableaux) all have λ = id and ε = (1, 1, …, 1) and no monotonicity violations and no Sundaram violations. Therefore it suffices to show that there are no tabloids in 𝕊 with λ ≠ id or ε ≠ (1, 1, …, 1) that do not exhibit any of the above violations.

Suppose there is a tabloid T (λ, σ, ε) with no monotonicity violation. In particular, there is no entry T_{i,j}, with j < λ_{1} and i ≤ λ′_{j+1}, for which cell (i, j + 1) does not belong to T. This implies that the upper edge of the generalized Ferrers board of λ (forming the shape of T) consists only of ascending steps. In terms of ε and σ this means the following: Let ε_{i_{1}} = ⋯ = ε_{i_{k}} = −1, ε_{j_{1}} = ⋯ = ε_{j_{l}} = 1, i_{1} < i_{2} < … i_{k}, j_{1} < j_{2} ⋯ < j_{l}, k + l = λ_{1}. Then because of (4.1) we must have

σ (1) = i_{k}, σ (2) = i_{k−1}, …, σ (k) = i_{1},
(5.2)  σ (k + 1) = j_{1}, σ (k + 2) = j_{2}, …, σ (λ_{1}) = j_{l}.

Hence, if some ε_{j} = −1, then also ε_{σ(1)} = −1. But then cell (1, 1) does not belong to T, which is a Sundaram violation. On the other hand, if all ε_{j} = 1, then we must have σ = id by (5.2).

Finally we define the involutions 𝔦_{𝕊}^{1} on B_{𝕊}^{1} and 𝔦_{𝕊}^{2} on B_{𝕊}^{2}. We start with the definition of 𝔦_{𝕊}^{1}. This mapping relies on an operation which we call inversion up to 2c of a column j of a tabloid T, where c is some positive integer ≤ n. (Also 𝔦_{ℙ}^{3} will rely on this operation.) This is defined as follows. If for some p, 1 ≤ p ≤ c, both entries 2p − 1 and 2p occur in column j then remove both of them. If neither 2p − 1 nor 2p is in column j then insert both of them. Apart from that, let the remaining entries remain unchanged (these are the ones where either 2p − 1 or 2p are in column j, but not both). Of course, put all the obtained entries, old and new, into increasing order to form the new column j. Figure 5 shows an example of an inversion up to 2c with c = 4. Observe that inversion up to 2c is a weight-preserving operation, since a pair of entries 2k − 1, 2k contributes x_{k}x_{k}^{−1} = 1 to the weight of the tableau, hence it can be removed or inserted without change of the weight. Observe further that it is an involution. Another application to the same column j restores the original situation.

Example of the “inversion up to 2c”

1 2 6 9  ⟶  3 4 6 7 8 9

Figure 5

For later use, we have to compute the effect of inversion up to 2c on the length of a column. Denote the tabloid that is obtained from tabloid T by inversion up to 2c of column j by \overline{T}. Also denote the lengths of the j-th column of T and \overline{T} by cl_{j}(T) and cl_{j}(\overline{T}), respectively. Then it is obvious that

|\{T_{.,j} ≤ 2c\}| + |\{\overline{T}_{.,j} ≤ 2c\}| = 2c. (5.3)

Hence the difference of column lengths is

cl_{j}(\overline{T}) − cl_{j}(T) = 2c − 2 · |\{T_{.,j} ≤ 2c\}|. (5.4)

Now we construct the involution 𝔦_{𝕊}^{1} on B_{𝕊}^{1}. Let T (λ, σ, ε) be a tabloid in B_{𝕊}^{1}, with the Sundaram violation in row I that was selected before. Invert column 1 up to 2I − 2, leave σ unchanged, and replace ε_{σ(1)} by −ε_{σ(1)}. Let \overline{T} be the new tabloid. For examples, see operations 2, 6, 10, 14 and 18 in Figure 9.

We have to check that 𝔦_{𝕊}^{1} is well-defined, and a weight-preserving and sign-reversing involution. For being well-defined, we have to check that \overline{T} lies in B_{𝕊}^{1}, i.e, that it lies in 𝕊 and contains a Sundaram violation that is minimal with respect to our selection scheme. To show that \overline{T} lies in 𝕊, we have to show that column j has the correct length with respect to (4.1), for all j. Since only the first column was changed it suffices to check the length of the first column of \overline{T}. The length of the first column of T is λ′_{1} − 1 + σ (1) · ε_{σ(1)}, hence

|{T_{.,1} ≤ 2I − 2}| = I − 1 + σ (1) ε_{σ(1)}.

According to (5.4), we therefore have

cl_{1}(\overline{T}) = cl_{1}(T) − 2σ (1) ε_{σ(1)} = λ′_{1} − 1 + σ (1) (−ε_{σ(1)}),

which is exactly what we need. That 𝔦_{𝕊}^{1} reverses sign is obvious since it changes sgn (ε) and does not change sgn (σ). It is weight-preserving since inversion up to 2c has these properties. Moreover, it is clear that \overline{T} again satisfies \overline{T}_{I,1} < 2I − 1 or that cell (I, 1) does not belong to \overline{T}. And, I is maximal with respect to this property. Therefore, if 𝔦_{𝕊}^{1} is applied to \overline{T} then we recover T, since it means applying inversion up to 2I − 2 to the first column again, and this restores the original object, as we already observed. Hence, 𝔦_{𝕊}^{1} is an involution.

Now we define 𝔦_{𝕊}^{2}. Let T (λ, σ, ε) be a (2n + 1)-tabloid in B_{𝕊}^{2} with the violation of row monotonicity in row I and column J that were selected above. Again, think of a tabloid T as heaps of cells (making up the columns) side by side. Now, interchange the heap “above and including T_{I−1,J}” and the heap “above and including T_{I,J+1}”, replace σ by σ′ := σ ∘ (J, J + 1), and leave ε unchanged. This yields some new object 𝔦_{𝕊}^{2} (T) = T′ (λ, σ′, ε). This operation is shown with some examples in Figure 6, only displaying the involved columns. See operations 4, 8 and 16 in Figure 9 for more elaborate examples. Note that the effect on the numbers beneath the displayed tabloid that encode the permutation σ is that those beneath the J-th and the (J+1)-st column are simply interchanged, the same being true for the the +’s and −’s encoding ε.

Example of the operation defined for violations of row monotonicity

2 3 5 4 9 9^{+} ^{+}^{2} ^{1} ↔ ^{345 2 9 9^{+} ^{+}^{1} ^{2}}  ^{36 7 7 ∞ ∞^{+} ^{−}^{3} ^{2}} ↔ ^{367 ∞ ∞ 7^{−} ^{+}^{2} ^{3}}  ^{3678^{−} ^{+}^{1} ^{3}} ↔ ^{36 8 7^{+} ^{−}^{3} ^{1}}

Figure 6

We have to check that our new object T′(λ, σ′, ε) is again a (2n + 1)-tabloid in B_{𝕊}^{2}, and that 𝔦_{𝕊}^{2} is a weight-preserving and sign-reversing involution. First, T′ has the correct column length with respect to (4.1) and is therefore an element of 𝕊. For, by construction we have

cl_{J}(T′) = (λ′_{J} − I + 1) + (cl_{J+1}(T) − (λ′_{J+1} − I))
= λ′_{J} − J + σ (J + 1) · ε_{σ(J+1)}
= λ′_{J} − J + σ′ (J) · ε_{σ′(J)},

and an analogous computation yields that column J + 1 has the correct length, too. Second, T′ again shows a violation of row monotonicity in the same row I and same column J (just look at the pictures of Figure 6). Besides, since the entry in cell (I, J) and entries to the left or in lower rows were not changed, this violation is again the “minimal” with respect to our selection scheme. Therefore T′(λ, σ′, ε) is an element of B_{𝕊}^{2}.

The observation that T′(λ, σ′, ε) shows a violation of row monotonicity at the same place as T (λ, σ, ε), implies that if 𝔦_{𝕊}^{2} is applied to T′(λ, σ, ε) then one recovers T (λ, σ, ε). Therefore 𝔦_{𝕊}^{2} is an involution on B_{𝕊}^{2}. That 𝔦_{𝕊}^{2} is weight-preserving is obvious. It reverses sign since ε is not changed and σ and σ′ are related by a transposition and hence have different sign. 5.2. The involution 𝔦_{ℙ}. Proctor tableaux are somewhat more complicated than Sundaram tableaux, and so is the corresponding involution 𝔦_{ℙ} on B_{ℙ}. As promised, we shall partition the set B_{ℙ} into three disjoint subsets B_{ℙ}^{1}, B_{ℙ}^{2}, and B_{ℙ}^{3} and construct involutions 𝔦_{ℙ}^{1}, 𝔦_{ℙ}^{2}, and 𝔦_{ℙ}^{3} for each of these, respectively. The involution 𝔦_{ℙ} then is the union of these three subinvolutions.

First, we define the set B_{ℙ}^{1}. B_{ℙ}^{1} consists of all (2n + 1)-tabloids with more than 2σ (j) − 1 entries ∞ in column j or with ε_{σ(j)} = −1 for some j. (In terms of the preceding subsection these properties are considered as certain violations of “Proctortableau-ness”.) In symbols,

B_{ℙ}^{1} := {T (λ, σ, ε) ∈ B_{ℙ} : (∃j : |{T_{.,j} = ∞}| > 2σ (j) − 1) or (∃j : ε_{σ(j)} = −1)}. (5.5)

We define operation 𝔦_{ℙ}^{1} : B_{ℙ}^{1} → B_{ℙ}^{1} as follows: Given some T ∈ B_{ℙ}^{1}, search for J minimal with |{T_{.,J} = ∞}| > 2σ (J) − 1 or ε_{σ(J)} = −1. If ε_{σ(J)} = −1, then insert 2σ (J) entries ∞ at the bottom of column J, else remove 2σ (J) entries ∞ from column J. In both cases, leave σ unchanged, and replace ε_{σ(J)} by −ε_{σ(J)}. For elaborate examples, see operations 1, 7, 9, 15 and 17 in Figure 9.

We have to check that this operation is a weight-preserving and sign-reversing involution on B_{ℙ}^{1}. 𝔦_{ℙ}^{1} is clearly an involution, and it is easy to see that the combined effect of insertion/removal of entries in column J together with the change of ε_{σ(J)} yields a new column of the correct length (with respect to (4.1)), which either contains more than 2σ (J) − 1 entries ∞ or has ε_{σ(J)} = −1. So for every T ∈ B_{ℙ}^{1} we have 𝔦_{ℙ}^{1} (T) ∈ B_{ℙ}^{1}. 𝔦_{ℙ}^{1} clearly is weight-preserving since entries ∞ do not contribute to the weight at all. It is sign-reversing since sgn (ε) is changed and σ is left unchanged.

Next we define set B_{ℙ}^{2}. B_{ℙ}^{2} consists of all (2n + 1)-tabloids not in B_{ℙ}^{1} where the number of entries ∞ is greater than 1 and less than 2σ (J) − 2 in some column J. (In terms of the preceding subsection, this property is another violation of “Proctortableau-ness”.) In symbols,

B_{ℙ}^{2} := {T (λ, σ, ε) ∈ B_{ℙ} \ B_{ℙ}^{1} : (∃J : |{T_{.,J} = ∞}| ∈ [2, 2σ (J) − 3])}. (5.6)

(Observe, that ε actually equals (1, 1, …, 1) for all elements of B_{ℙ}^{2}.)

For this set we define mapping 𝔦_{ℙ}^{2} as follows: Given some T ∈ B_{ℙ}^{2}, search for column J with σ (J) minimal, where |{T_{.,J} = ∞}| ∈ [2, 2σ (J) − 3]. Write l for |{T_{.,J} = ∞}|. Suppose, l lies in the set

S_{k} := {2k, 2k + 1} ∪ {2σ (J) − 2k − 2, 2σ (J) − 2k − 1}

for some k, 1 ≤ k ≤ ⌈\frac{σ(J)}{2}⌉ − 1. (It is obvious that the sets S_{k}, 1 ≤ k ≤ ⌈\frac{σ(J)}{2}⌉ − 1, form a partition of the set {2, 3, …, 2σ (J) − 3}, hence k is uniquely determined.) We can deduce immediately that

σ (J) − 2k ≥ σ (J) − 2 ⌈\frac{σ (J)}{2}⌉ + 2 ≥ 1.

Therefore, there must exist an index S with σ (S) = σ (J) − 2k. Now remove 2k entries ∞ from column J, insert them in column S, replace σ by σ′ := σ ∘ (J, S), and leave ε unchanged. This yields the new object T′(λ, σ′, ε). For elaborate examples see operations 3 and 5 in Figure 9.

We have to check that this operation is a weight-preserving and sign-reversing involution on B_{ℙ}^{2}. It is easy to check that 𝔦_{ℙ}^{2}(T) = T′(λ, σ′, ε) has the correct column lengths with respect to (4.1) by using the fact that ε_{i} = 1 for all i. The number |{T_{.,S} = ∞}| of entries ∞ in column S (before application of mapping 𝔦_{ℙ}^{2}) lies in [0, 1] ∪ [2σ (S) − 2, 2σ (S) − 1], since otherwise J were not the column with σ (J) minimal (or T would not belong to B_{ℙ}^{2} at all). Since σ (S) = σ (J) − 2k, we have

|{T′_{.,S} = ∞}| ∈ [2k, 2k + 1] ∪ [2σ (S) + 2k − 2, 2σ (S) + 2k − 1]
= [2k, 2k + 1] ∪ [2σ (J) − 2k − 2, 2σ (J) − 2k − 1]
= [2k, 2k + 1] ∪ [2σ′ (S) − 2k − 2, 2σ′ (S) − 2k − 1] ,

and

|{T′_{.,J} = ∞}| ∈ [0, 1] ∪ [2σ (J) − 4k − 2, 2σ (J) − 4k − 1]
= [0, 1] ∪ [2σ′ (J) − 2, 2σ′ (J) − 1] .

All the columns other than columns J and S were not changed at all. Therefore T′ is again an element of B_{ℙ}^{2}. Besides, in the set of all columns of T′ having the defining property of (5.6), column S is obviously the one with σ′(S) minimal. So, by applying 𝔦_{ℙ}^{2} to T′(λ, σ′, ε) we would recover T (λ, σ, ε). Hence, 𝔦_{ℙ}^{2} is an involution. 𝔦_{ℙ}^{2} is clearly weight-preserving, since moving around entries ∞ has no influence on the weight. It is sign-reversing, since the the sign of σ and σ′ is different and ε was left unchanged.

The “remaining” tabloids B_{ℙ}\ (B_{ℙ}^{1} ∪ B_{ℙ}^{2}) constitute our set B_{ℙ}^{3}. They are (2n + 1)- tabloids T (λ, σ, ε) with ε = (1, 1, …, 1) (since otherwise T were in B_{ℙ}^{1}) and |{T_{.,j} =

∞}| ∈ [0, 1] ∪ [2σ (j) − 2, 2σ (j) − 1] (since otherwise T were in B_{ℙ}^{1} or in B_{ℙ}^{2}) that are no (2n + 1)-Proctor tableaux. Instead of directly working with these tabloids, it is more convenient to map them by a weight- and sign-preserving bijection, P say, to another set, \overline{B_{ℙ}^{3}} say. \overline{B_{ℙ}^{3}} consists of fillings of slightly different generalized Ferrers boards of λ. If σ is a permutation in 𝔖_{λ_{1}} and ε is a sign-vector in {1} × {1, −1}^{λ_{1}−1} (note the difference to the previous definition of vector ε) then for \overline{B_{ℙ}^{3}} we consider generalized Ferrers boards F of λ where the length of the j-th column of F is given by

cl_{j}(F) = λ′_{j} − j + (σ (j) − 1) ε_{σ(j)} + 1. (5.7)

(Note the difference to (4.1)). By definition, \overline{B_{ℙ}^{3}} consists of all fillings T of a generalized Ferrers board F with parameters (λ, σ, ε), but with column-lengths according to (5.7), with elements from {1, 2, …, 2n, ∞}, that are strictly increasing along columns and that are no Proctor tableaux. (Note that column-strictness implies that in particular there is at most one entry ∞ in any column.) To differentiate from our previous tabloids, we call objects in \overline{B_{ℙ}^{3}} new (2n + 1)-tabloids. The definition of signed weight for a tabloid in \overline{B_{ℙ}^{3}} is quite similar to (4.2),

w (T (λ, σ, ε)) := sgn (σ) ∏_{i=1}^{n} x_{i}^{#(2i−1∈T)−#(2i∈T)}. (5.8)

Note, however, that in contrast to (4.2) vector ε does not contribute to the sign here.

The bijection P between B_{ℙ}^{3} and \overline{B_{ℙ}^{3}} is defined as follows. Consider some tabloid T (λ, σ, ε) ∈ B_{ℙ}^{3}. As mentioned above, we have ε = (1, 1, …, 1) for all tabloids in B_{ℙ}^{3}. Now, for every column j with σ (j) > 1 and |{T_{.,j} = ∞}| ≥ 2σ (j) − 2, remove 2σ (j)−2 entries ∞ and set ε_{σ(j)} = −1. For an example, see operation 11 in Figure 9. This is indeed a bijection. The inverse mapping is easily described. Given a tabloid T (λ, σ, ε) ∈ \overline{B_{ℙ}^{3}}, insert 2σ (j) − 2 entries ∞ in every column j with ε_{σ(j)} = −1.

Recalling the definitions of signed weights (4.2) and (5.8) as well as the fact that entries ∞ do not contribute to the weight, it is easy to see that P is a weight- and sign-preserving bijection between B_{ℙ}^{3} and \overline{B_{ℙ}^{3}}.

So the remaining task is to give a weight-preserving and sign-reversing involution on \overline{B_{ℙ}^{3}}, which is actually the most intricate part.

Similar to the definition of 𝔦_{𝕊}, we first define a list of violations for new tabloids. Then, among all violations we pick up the “minimal” (in some sense), and finally we apply a certain operation which depends on the type of violation that we are considering.

To motivate our definitions of violations, observe that \overline{B_{ℙ}^{3}} consists precisely of those new (2n + 1)-tabloids (T, σ, ε) where either σ ≠ id or ε ≠ (1, 1, …, 1) or there is some violation of row monotonicity or some violation of the orthogonal or protection conditions.

We define a violation of row monotonicity at p of a new (2n + 1)-tabloid T to be:

(1) cell (i, j) belongs to T, j < λ_{1}, i ≤ λ′_{j+1}, and T_{i,j} = p,
(2) either T_{i,j} > T_{i,j+1},
or  cell (i, j + 1) does not belong to T.

(Note that here we do not consider two entries ∞ in the same row as a violation since this is not forbidden for Proctor tableaux.)

The other types of violations (and their namings) stem from [2] and come from the underlying lattice path interpretations given there. This is commented in section 7.

We say that a new (2n+1)-tabloid T (λ, σ, ε) contains an even reflected intersection at 2c, for some c with 1 ≤ c ≤ n, if

|{T_{.,1} ≤ 2c}| + |{T_{.,2} ≤ 2c}| = 2c + (σ (1) − 1) ε_{σ(1)} + (σ (2) − 1) ε_{σ(2)}. (5.9)

For an example consider the second tabloid in the third row of Figure 9. It contains an even reflected intersection at 6.

We say that a new (2n + 1)-tabloid T (λ, σ, ε) contains an odd reflected crossing at 2c − 1, for some c with 1 ≤ c ≤ n, if the first two columns of T contain neither 2c − 1 nor 2c and

|{T_{.,1} ≤ 2c − 2}| + |{T_{.,2} ≤ 2c − 2}| = 2c + (σ (1) − 1) ε_{σ(1)} + (σ (2) − 1) ε_{σ(2)} − 1.

The right-most tabloid in Figure 8 contains an odd reflected crossing at 6.

And, we say that a new tabloid T (λ, σ, ε) contains an odd reflected violation at 2c − 1, for some c with 1 ≤ c ≤ n, if the following specialization of (2.3) holds (the additions are underlined in the text; note that they imply that there is no even reflected intersection at 2c or 2c − 2):

i + j = 2c and T_{i,1} = 2c − 1 \underline{and T_{i+1,1} > 2c}
and T_{j,2} = ⋯ = T_{j,h−1} = 2c − 1 (for h ≥ 2)
\underline{and T_{j+1,2} = ⋯ = T_{j+1,h−1} > 2c (for h ≥ 2)}
and T_{j,h} = 2c \underline{and T_{j−1,h} < 2c − 1}.

The left-most tabloid in Figure 8 contains an odd reflected violation at 6 (choose i = 4, j = 2, h = 3).

The important fact is that every element of \overline{B_{ℙ}^{3}} contains either a row monotonicity violation, or an even reflected intersection, or an odd reflected crossing, or an odd reflected violation. For, suppose that there is T (λ, σ, ε) in \overline{B_{ℙ}^{3}} containing none of these violations. Then we claim that there holds

|{T_{.,1} ≤ 2c}| + |{T_{.,2} ≤ 2c}| < 2c + (σ (1) − 1) ε_{σ(1)} + (σ (2) − 1) ε_{σ(2)}, (5.10)

for c = 0, 1, …, n. (Note that this inequality generalizes the orthogonal condition (2.2) for p = 2c, to which it reduces for σ = id and ε = (1, 1, …, 1).) In fact, these inequalities follow from the observation that

|{T_{.,1} ≤ ∞}|+|{T_{.,2} ≤ ∞}| = cl_{1}(T) + cl_{2}(T)

= λ′_{1} − 1 + (σ(1) − 1)ε_{σ(1)} + 1 + λ′_{2} − 2 + (σ(2) − 1)ε_{σ(2)} + 1 (by (5.7)) < 2n + 1 + (σ(1) − 1)ε_{σ(1)} + (σ(2) − 1)ε_{σ(2)} (since λ′_{1} + λ′_{2} ≤ 2n + 1),

and a downward induction on c which uses that T contains neither an even intersection nor an odd reflected crossing. Since T does not contain any row monotonicity violation by assumption, the arguments leading to (5.2) also apply here. Therefore, if there is some ε_{j} = −1 then we must have ε_{σ(1)} = −1 by (5.2). The generalized orthogonal condition (5.10) with c = 0 then enforces ε_{σ(2)} = 1. Therefore σ(2) = 1 by (5.2), and so (5.10) does not hold for c = 0, which is a contradiction. Hence we must have ε = (1, 1, …, 1) which in turn implies σ = id, again by (5.2). Summarizing, T is a new (2n + 1)-tabloid with parameters σ = id and ε = (1, 1, …, 1) (which by (5.7) means that it is a filling of the Ferrers board of λ), that satisfies the (2c)-th orthogonal condition (since it satisfies (5.10)) and the (2c)-th protection condition (since it does not contain any odd reflected violation), for all c. In short, T is a (2n + 1)-Proctor tableau, which is a contradiction since Proctor tableaux are excluded from \overline{B_{ℙ}^{3}}.

Finally we turn to the definition of 𝔦_{ℙ}^{3} on \overline{B_{ℙ}^{3}}. Let T (λ, σ, ε) be in \overline{B_{ℙ}^{3}}. Among all the row monotonicity violations, even reflected intersections, odd reflected crossings, odd reflected violations, pick out these which are at p with p maximal, and among all these pick the ones in the minimal column. If we encounter a row monotonicity violation among the latter, then 𝔦_{ℙ}^{3} acts in the same way as 𝔦_{𝕊}^{2} did. In the same way as it was done for 𝔦_{𝕊}^{2} and the column-lengths (4.1), it is checked that this operation takes care of the (new) column lengths (5.7). Besides, the image under this operation will again contain a row monotonicity violation, at the same p and in the same column. Hence, by this operation we obtain an element of \overline{B_{ℙ}^{3}}, and by applying 𝔦_{ℙ}^{3} again we would recover our original tabloid.

Example for the operation in case of an even reflected intersection

1 3 3 4 4 5 6 ⟶  ^{12 1 5 6} ⟶  ^{1 1 2 5 6}

Figure 7

If we do not encounter a row monotonicity violation but an even intersection at 2c, or one of the other two violations at 2c − 1, then the basic idea for the definition of 𝔦_{ℙ}^{3} is as follows: Apply inversion up to 2c to both columns 1 and 2 and interchange the two “inverted heaps”, replace σ by \overline{σ} := σ ∘ (1, 2), and replace ε_{σ(1)} and ε_{σ(2)} by their negatives, except that ε_{1} is not changed. (ε_{1} has to be 1 by definition of \overline{B_{ℙ}^{3}}.) This operation is weight-preserving since inversion up to 2c is, and it is sign-reversing since σ and \overline{σ} differ in sign and the weight (5.8) does not depend on vector ε.

Figure 7 gives an example for this operation with 2c = 4.

In the case of an even reflected intersection we apply this idea without further modification, thus obtaining \overline{T} (λ, \overline{σ}, \overline{ε}). For an elaborate example, see operation 12 in Figure 9.

We have to check that \overline{T} (λ, \overline{σ}, \overline{ε}) is in \overline{B_{ℙ}^{3}} and that application of 𝔦_{ℙ}^{3} to \overline{T} (λ, \overline{σ}, \overline{ε}) would give back T (λ, σ, ε). First, \overline{T} has the correct column lengths with respect to (5.7) since for {i, j} = {1, 2} we have

cl_{i}(\overline{T}) = λ′_{i} − i + (σ (i) − 1) ε_{σ(i)} + 1 − |\{T_{.,i} ≤ 2c\}| + 2c − |\{T_{.,j} ≤ 2c\}|
= λ′_{i} − i + (σ (i) − 1) ε_{σ(i)} + 1 − ((σ (i) − 1) ε_{σ(i)} + (σ (j) − 1) ε_{σ(j)})
= λ′_{i} − i + (σ (j) − 1) (−ε_{σ(j)}) + 1
= λ′_{i} − i + (\overline{σ} (i) − 1) \overline{ε}_{\overline{σ}(i)} + 1.

Note that the exceptional case of ε_{1} (which must always equal 1) does not matter in this (and the following) computation, since ε_{1} is always multiplied by (1 − 1) = 0. Moreover,

|\{\overline{T}_{.,1} ≤ 2c\}| + |\{\overline{T}_{.,2} ≤ 2c\}| = 4c − (2c + (σ (1) − 1) ε_{σ(1)} + (σ (2) − 1) ε_{σ(2)})
= 2c + (\overline{σ} (1) − 1) \overline{ε}_{\overline{σ}(1)} + (\overline{σ} (2) − 1) \overline{ε}_{\overline{σ}(2)},

which says that in \overline{T} we encounter an even reflected intersection again, for the same value 2c. Hence, \overline{T} (λ, \overline{σ}, \overline{ε}) is in \overline{B_{ℙ}^{3}}. Besides, this operation did not introduce a row monotonicity violation at 2c in the first column. For, suppose that l is minimal such that T_{l,1} > 2c. Then we must have T_{l,2} ≥ T_{l,1} > 2c because T does not contain a row monotonicity violation at some integer > 2c. Now, if we assume that T_{l−1,2} ≤ 2c, then by using (5.7) we obtain for the number of entries ≤ 2c in the first two columns of T

|{T_{.,1} ≤ 2c}| + |{T_{.,2} ≤ 2c}| = l − 1 + (σ(1) − 1)ε_{σ(1)} + l − 2 + (σ(2) − 1)ε_{σ(2)},

which contradicts (5.9) in parity. Hence we have T_{l−1,2} > 2c. So our operation cannot introduce a row monotonicity violation at 2c in the first column of \overline{T}. Therefore, by applying 𝔦_{ℙ}^{3} to \overline{T} (λ, \overline{σ}, \overline{ε}) we recover T (λ, σ, ε).

In case of odd reflected violations and odd reflected crossings, the basic idea of the operation as explained above is modified in the following way. Suppose we encounter an odd reflected violation at 2c. First, set T_{i,1} = 2c and, to compensate for the according change in weight (with respect to (5.8)), set T_{j,h} = 2c−1. This amounts to an interchange of entries 2c and 2c−1 in T which by assumption does not violate the strict monotonicity in columns. Moreover, this interchange clearly preserves weight. Next, insert 2c − 1 in column 1 and 2c in column 2 (in the appropriate rows). This is possible by assumption without violating column-strictness. Again, this insertion does not change weight. Now apply the operation from above. Figure 8 gives an example for this operation with 2c = 6, i = 4, j = 2, h = 3.

Conversion of odd reflected violation into odd reflected crossing

2 3 4 3 5 6 4 7 7 5^{+} ^{+} ^{+}^{1} ^{2} ^{3}  →  ^{2 3 4 3 5 5 4 7 7 6}  →  ^{2 3 3 5 4 4 6 5 5 7 7 6}  →  ^{4 1 2 5 2 7 7 3^{−} ^{+} ^{+}^{2} ^{1} ^{3}}

Figure 8

Again, we have to check that this operation gives us an element of \overline{B_{ℙ}^{3}}. To see this, we compute the resulting column lengths. For {i, j} = {1, 2} we have

cl_{i}(\overline{T}) = λ′_{i} − i + (σ (i) − 1) ε_{σ(i)} + 1 − |\{T_{.,i} ≤ 2c\}| + 2c − (|\{T_{.,j} ≤ 2c\}| + 1)

= λ′_{i} − i + (σ (i) − 1) ε_{σ(i)} + 1 − ((σ (i) − 1) ε_{σ(i)} + (σ (j) − 1) ε_{σ(j)} − 1) − 1

= λ′_{i} − i + (σ (j) − 1) (−ε_{σ(j)}) + 1.
= λ′_{i} − i + (\overline{σ} (i) − 1) \overline{ε}_{\overline{σ}(i)} + 1.

Observe that neither column 1 nor column 2 of the resulting tableau \overline{T} contains 2c−1 or 2c. Hence |\{\overline{T}_{.,1} ≤ 2c\}| + |\{\overline{T}_{.,2} ≤ 2c\}| = |\{\overline{T}_{.,1} ≤ 2c − 2\}| + |\{\overline{T}_{.,2} ≤ 2c − 2\}| and so

|\{\overline{T}_{.,1} ≤ 2c − 2\}|+|\{\overline{T}_{.,2} ≤ 2c − 2\}|
= 2c − |{T_{.,1} ≤ 2c}| − 1 + 2c − |{T_{.,2} ≤ 2c}| − 1
= 2c − (σ (1) − 1) ε_{σ(1)} − (σ (2) − 1) ε_{σ(2)} − 1
= 2c + (\overline{σ} (1) − 1) \overline{ε}_{\overline{σ}(1)} + (\overline{σ} (2) − 1) \overline{ε}_{\overline{σ}(2)} − 1.

So this operation converted an odd reflected violation at 2c into an odd reflected crossing at 2c. Hence, \overline{T} (λ, \overline{σ}, \overline{ε}) is indeed in \overline{B_{ℙ}^{3}}. Also, this operation did not introduce a row monotonicity violation at 2c − 1 in the first column (there is no entry 2c − 1 in the first column of \overline{T}), and, of course, no even intersection at 2c − 1 (which simply does not exist). Therefore this odd reflected crossing in \overline{T} is the “minimal” violation according to our selection scheme. Since 𝔦_{ℙ}^{3} should become an involution, the definition of 𝔦_{ℙ}^{3} for odd reflected crossings has to be the inverse of the above described conversion of an odd reflected violation into an odd reflected crossing. A close look shows that this operation can indeed be reversed. This completes the definition of the involution 𝔦_{ℙ}^{3} and hence of 𝔦_{ℙ}.

6. The example After these sometimes tricky constructions time has come to have a look at a

concrete example, worked out in detail. In Figure 9 we start with a 13-Sundaram tableau of shape λ = (3, 3, 2, 2, 1, 1) (λ′ = (6, 4, 2)), and apply the algorithmic bijection until we finally reach the corresponding 13-Proctor tableau. The algorithm consists of alternatively applying 𝔦_{ℙ} and 𝔦_{𝕊}, as long as possible. Each step is labelled by the corresponding subinvolution. All the time, we keep track of permutation σ and vector ε by writing σ (j) as well as the sign of ε_{σ(j)} below column j. Moreover, the violation that is responsible for the respective involution is graphically marked with thick lines.

7. The background In this section we explain the background behind our bijection. As indicated

in the introduction, the basic source for the operations of the previous section is the paper [2]. In [2, sec. 8] it was shown how to prove combinatorially that the generating function ∑ w(T) for all (2n + 1)-Sundaram tableaux T of shape λ equals the determinant

|∑_{k≥0} e_{λ′_{i}−i+j−k} (x) − ∑_{k≥0} e_{λ′_{i}−i−j−k} (x)|_{λ_{1}×λ_{1}}, (7.1)

where x = (x_{1}, x_{1}^{−1}, x_{2}, x_{2}^{−1}, …, x_{n}, x_{n}^{−1}) and e_{m}(z_{1}, z_{2}, …, z_{s}) denotes the m-th elementary symmetric function in z_{1}, z_{2}, …, z_{s} (cf. [9, p. 12]). Also in [2] it was shown how to prove combinatorially that the generating function ∑ w(T) for all (2n + 1)- Proctor tableaux T of shape λ equals the determinant

|e_{λ′_{i}−i+1} (x, 1) ⋮ e_{λ′_{i}−i+j} (x, 1) + e_{λ′_{i}−i−j+2} (x, 1)|_{λ_{1}×λ_{1}}, (7.2)

where e_{m}(x, 1) = e_{m}(x_{1}, x_{1}^{−1}, …, x_{n}, x_{n}^{−1}, 1) = e_{m}(x) + e_{m−1}(x). The notation of the determinant means that the first expression gives the entries of the first column and the second the entries for the remaining columns, j ≥ 2. Actually, by (2.5) both determinants equal the odd orthogonal character so_{2n+1} (λ, x). That they are the same can also be shown directly by first subtracting the sums in (7.1), thereby

Example for the algorithmic bijection

[figure: ^{1 4 ∞ 6 7 ∞ 9 10 11 11 ∞ ∞^{+} ^{+} ^{+}^{1} ^{2} ^{3}}; ^{\overrightarrow{𝔦_{ℙ}^{1}}^{(1)}}; 4; ∞; 7; ∞; 1; 10; 6; 11; 9; 11; −; +; +; 1; 2; 3; 7>; ^{\overrightarrow{𝔦_{𝕊}^{1}}^{(2)}}; ^{1 4 ∞ 3 7 ∞ 4 10 6 11 9 11^{+} ^{+} ^{+}^{1} ^{2} ^{3}}; k=1,; σ(S)=3−2k; =1.; ^{\overrightarrow{𝔦_{ℙ}^{2}}^{(3)}}; 1; 3; 4; 4; 6; 7; 9; 10; 11; 11; ∞; ∞; +; +; +; 3; 2; 1; !; ^{\overrightarrow{𝔦_{𝕊}^{2}}^{(4)}}; ^{1346 7 4 9 10 11 11 ∞ ∞^{+} ^{+} ^{+}^{3} ^{1} ^{2}}; k=1,; σ(S)=3−2k; =1.; ^{\overrightarrow{𝔦_{ℙ}^{2}}^{(5)}}; 7; 1; 10; 3; 11; 4; 4; ∞; 6; ∞; 9; 11; +; +; +; 1; 3; 2; 7>; ^{\overrightarrow{𝔦_{𝕊}^{1}}^{(6)}}; ^{7 10 11 4 1 ∞ 6 ∞ 9 11^{−} ^{+} ^{+}^{1} ^{3} ^{2}}; ^{\overrightarrow{𝔦_{ℙ}^{1}}^{(7)}}; ^{7 1 10 6 11 4 9 ∞ 11 ∞ ∞ ∞^{+} ^{+} ^{+}^{1} ^{3} ^{2}}; ^{\overrightarrow{𝔦_{𝕊}^{2}}^{(8)}}; ^{1 4 7 6 11 10 9 ∞ 11 ∞ ∞ ∞^{+} ^{+} ^{+}^{1} ^{2} ^{3}}; ^{\overrightarrow{𝔦_{ℙ}^{1}}^{(9)}}; 4; 7; 11; 10; 1; ∞; 6; ∞; 9; 11; −; +; +; 1; 2; 3; 7>; ^{\overrightarrow{𝔦_{𝕊}^{1}}^{(10)}}; ^{1 4 7 3 11 10 4 ∞ 6 ∞ 9 11^{+} ^{+} ^{+}^{1} ^{2} ^{3}}; ^{\overrightarrow{P}^{(11)}}; ^{1 7 3 10 4 4 6 11 9 11^{+} ^{−} ^{+}^{1} ^{2} ^{3}}; even; reflected; intersection; at 6; ^{\overrightarrow{𝔦_{ℙ}^{3}}^{(12)}}; ^{12 7 4 1 10 5 6 6 11 9 11^{+} ^{+} ^{+}^{2} ^{1} ^{3}}; ^{\overrightarrow{P^{−1}}^{(13)}}; 1; 2; 7; 4; 1; 10; 5; 6; 6; 11; 9; 11; +; +; +; 2; 1; 3; 7>; ^{\overrightarrow{𝔦_{𝕊}^{1}}^{(14)}}; ^{7 1 10 6 4 11 9 11^{−} ^{+} ^{+}^{2} ^{1} ^{3}}; ^{\overrightarrow{𝔦_{ℙ}^{1}}^{(15)}}; 49 7 11 1 10 ∞ 6 ∞ 11 ∞ ∞^{+} ^{+} ^{+}_{2} _{1} _{3}; ^{\overrightarrow{𝔦_{𝕊}^{2}}^{(16)}}; 1 4 7 6 9 10 11 11 ∞ ∞ ∞ ∞^{+} ^{+} ^{+}_{1} _{2} _{3}; ^{\overrightarrow{𝔦_{ℙ}^{1}}^{(17)}}; 4; 7; 9; 10; 1; 11; 6; ∞; 11; ∞; −; +; +; 1; 2; 3; 7>; ^{\overrightarrow{𝔦_{𝕊}^{1}}^{(18)}}; 1 4 7 3 9 10 4 11 6 ∞ 11 ∞^{+} ^{+} ^{+}_{1} _{2} _{3}]

Figure 9

writing (7.1) as

|∑_{k=1}^{2j} e_{λ′_{i}−i−j+k}(x)|_{λ_{1}×λ_{1}} = |∑_{k=1}^{j} e_{λ′_{i}−i−j+2k}(x, 1)|_{λ_{1}×λ_{1}},

and then subtracting column 1 from columns 2 through λ_{1}, column 2 from columns 3 through λ_{1}, etc. This results precisely in (7.2).

Now, here is the idea for our bijection between (2n + 1)-Sundaram tableaux and (2n + 1)-Proctor tableaux of the same shape λ: Expand the determinant (7.1) and interpret the resulting sum of (signed) monomials as a generating function for certain objects, O_{𝕊} say. The (2n + 1)-Sundaram tableaux of shape λ will appear in O_{𝕊} since (7.1) equals their generating function. Subsequently, find a weight-preserving and sign-reversing involution that cancels all the remaining objects in O_{𝕊}. Likewise, expand the determinant (7.2) and interpret the resulting sum of (signed) monomials as a generating function for certain objects. In fact, as we saw by the reduction of (7.1) to (7.2), the determinant (7.2), when expanded, is a generating function for a subset of O_{𝕊}. The (2n + 1)-Proctor tableaux of shape λ will appear in this subset since (7.2) equals their generating function. Subsequently, find a weight-preserving and sign-reversing involution that cancels all the remaining objects in this subset. And also, find a weight-preserving and sign-reversing involution that cancels all the objects in O_{𝕊} that are not in this subset. (I.e., translate the algebraic steps that lead from (7.1) to (7.2) into combinatorics.) Provided these involutions are found, the involution principle (see section 3) applies and gives us an explicit bijection between (2n + 1)-Sundaram tableaux and (2n + 1)-Proctor tableaux of the same shape λ.

The proof for (7.1) in [2] consisted exactly of expanding the determinant, interpreting the resulting sum as a generating function for certain families of lattice paths, and finally cancelling those families of lattice paths that did not correspond to Sundaram tableaux by a weight-preserving and sign-reversing involution. The set 𝕊 (= ℙ) defined in section 4 (paragraph after (4.2)) is the tabloid translation of the families of lattice paths. (Each column of a tabloid corresponds to a lattice path. The entries of the columns correspond to the labels of the horizontal steps in the lattice path.) The involution in [2] consisted of two different operations, one being the usual Gessel– Viennot mapping [4, 5], corresponding to our 𝔦_{𝕊}^{2} (see section 5.1), and one being a modified reflection of paths, corresponding to our 𝔦_{𝕊}^{1} (see section 5.1).

Likewise, the proof for (7.2) in [2] consisted exactly of expanding the determinant, interpreting the resulting sum as a generating function for certain families of lattice paths, and finally cancelling those families of lattice paths that did not correspond to Proctor tableaux by a weight-preserving and sign-reversing involution. The families of lattice paths correspond to the union \overline{B_{ℙ}^{3}}∪\{(2n+1)-Proctor tableaux of shape λ\}. The involution in [2] consisted of two different operations, too. One was the usual Gessel–Viennot mapping, corresponding to our 𝔦_{ℙ}^{3} (see section 5.2) in the case of a row monotonicity violation. The other one was called “modified reflection-Gessel– Viennot mapping” and mapped even intersections to even intersections and odd reflected violations to odd reflected crossings. This operation corresponds to our 𝔦_{ℙ}^{3} (see section 5.2) in the case of the other violations. (Actually, in [2] we even had to modify this mapping because we did not want it to introduce points of intersections. Fortunately, this is not necessary here.) Finally, the subtraction of the sums in the entries in (7.1) and the subsequent column operations that transformed (7.1) into (7.2) are combinatorially modelled by 𝔦_{ℙ}^{1} and 𝔦_{ℙ}^{2} (see section 5.2), respectively.

8. Concluding remarks In [11, sec. 6] Proctor defined 4 different types of odd orthogonal tableaux, one

type being due to King and Welsh [7]. Let us call them odd orthogonal tableaux of the first, second, third, and fourth kind (as was done in [2]). The first kind is the one considered in the previous sections. King and Welsh [7, App. A, p. 276f] gave a bijection between the tableaux of first and second kind, and an analogous argument provides a bijection between the tableaux of third and fourth kind (see [2, sec. 7, next-to-last paragraph]). We remark that it is not difficult to construct an explicit bijection between the tableaux of first and third kind using the involution principle again, by embedding both types of tableaux in a set of tabloids with new column lengths (5.7) and using the involution 𝔦_{ℙ}^{3} and a variation of it. Thus all five types of odd orthogonal tableaux (including Sundaram tableaux) are related by an explicit bijection.

References

1. C. DeConcini, Symplectic standard tableaux, Adv. in Math. 34 (1979), 1–27.

2. M. Fulmek and C. Krattenthaler, Lattice path proofs for determinantal formulas for symplectic and orthogonal characters, J. Combin. Theory Ser. A (to appear).

3. A. M. Garsia and S. C. Milne, Method for constructing bijections for classical partition identities, Proc. Nat. Acad. Sci. U.S.A. 78 (1981), 2026–2028.

4. I. M. Gessel and X. Viennot, Binomial determinants, paths, and hook length formulae, Adv. in Math. 58 (1985), 300—321.

5. I.M. Gessel and X. Viennot, Determinants, paths, and plane partitions, preprint, 1988.

6. R. C. King and N. G. I. El-Sharkaway, Standard Young tableaux and weight multiplicities of the classical Lie groups, J. Physics A 16 (1983), 3153–3178.

7. R. C. King and T. A. Welsh, Construction of orthogonal group modules using tableaux, Linear and Multilinear Algebra 33 (1993), 251–283.

8. P. Littelmann, A Littlewood–Richardson rule for symmetrizable Kac–Moody algebras, Invent. Math. 116 (1994), 329–346.

9. I.G. Macdonald, Symmetric Functions and Hall Polynomials, Oxford University Press, New York/London, 1979.

10. R. A. Proctor, A Schensted algorithm which models tensor representations of the orthogonal group, Can. J. Math. 42 (1990), 28–49.

11. , Young tableaux, Gelfand patterns and branching rules for classical Lie groups, J. Algebra 164 (1994), 299–360.

12. J. T. Sheats, A symplectic jeu de taquin bijection between the tableaux of King and of DeConcini, to appear.

13. D. Stanton and D. White, Constructive combinatorics, Undergraduate Texts in Math., Springer– Verlag, New York, Berlin Heidelberg, Tokyo, 1986.

14. S. Sundaram, Orthogonal tableaux and an insertion algorithm for SO(2n+1), J. Combin. Theory Ser. A 53 (1990), 239–256.