INTERSECTIONS OF SCHUBERT VARIETIES AND OTHER PERMUTATION ARRAY SCHEMES

SARA BILLEY^{∗} AND RAVI VAKIL^{†}

Abstract. Using a blend of combinatorics and geometry, we give an algorithm for algebraically finding all flags in any zero-dimensional intersection of Schubert varieties with respect to three transverse flags, and more generally, any number of flags. The number of flags in a triple intersection is also a structure constant for the cohomology ring of the flag manifold. Our algorithm is based on solving a limited number of determinantal equations for each intersection (far fewer than the naive approach in the case of triple intersections). These equations may be used to compute Galois and monodromy groups of intersections of Schubert varieties. We are able to limit the number of equations by using the permutation arrays of Eriksson and Linusson, and their permutation array varieties, introduced as generalizations of Schubert varieties. We show that there exists a unique permutation array corresponding to each realizable Schubert problem and give a simple recurrence to compute the corresponding rank table, giving in particular a simple criterion for a Littlewood-Richardson coefficient to be 0. We describe pathologies of Eriksson and Linusson’s permutation array varieties (failure of existence, irreducibility, equidimensionality, and reducedness of equations), and define the more natural permutation array schemes. In particular, we give several counterexamples to the Realizability Conjecture based on classical projective geometry. Finally, we give examples where Galois/monodromy groups experimentally appear to be smaller than expected.

Key words. Schubert varieties, permutation arrays, Littlewood-Richardson coefficients

AMS(MOS) subject classifications. Primary 14M17; Secondary 14M15

1. Introduction. A typical Schubert problem asks how many lines in three-space meet four generally chosen lines. The answer, two, may be obtained by computation in the cohomology ring of the Grassmannian variety of two-dimensional planes in four-space. Such questions were considered by H. Schubert in the nineteenth century. During the past century, the study of the Grassmannian has been generalized to the flag manifold where one can ask analogous questions.

The flag manifold Fl_{n}(K) parameterizes the complete flags

F_{•} = {{0} = F_{0} ⊂ F_{1} ⊂ ⋯ ⊂ F_{n} = K^{n}}

where F_{i} is a vector space of dimension i. (Unless otherwise noted, we will work over an arbitrary base field K. The reader, and Schubert, is welcome to assume K = ℂ throughout. For a general field, we should use the Chow ring rather than the cohomology ring, but they agree for K = ℂ. For simplicity, we will use the term “cohomology” throughout.)

∗ Department of Mathematics, University of Washington, Seattle, WA, billey@math.washington.edu, supported by NSF grant DMS-9983797

† Department of Mathematics, Stanford University, Stanford, CA, vakil@math.stanford.edu, supported by NSF grant DMS-0238532

A modern Schubert problem asks how many flags have relative position u, v, w with respect to three generally chosen fixed flags X_{•}, Y_{•} and Z_{•}. One concrete solution to this problem, due to Lascoux and Schützenberger [Lascoux and Schützenberger, 1982], is to compute a product of Schubert polynomials and expand in the Schubert polynomial basis. The coefficient indexed by u, v, w is the solution. This corresponds to a computation in the cohomology ring of the flag variety. (Caution: this solution is known to work only in characteristic 0, due to the potential failure of the Kleiman-Bertini theorem in positive characteristic, cf. [Vakil, 2006b, Sect. 2].) The quest for a combinatorial rule for expanding these products is a long-standing open problem, and corresponds to the multiplication rule for Schubert polynomials.

The main goal of this paper is to describe a method for directly identifying all flags in X_{u}(F_{•})∩X_{v}(G_{•})∩X_{w}(H_{•}) when ℓ(u)+ℓ(v)+ℓ(w) = ( \begin{matrix}n \\ 2 \end{matrix} ), thereby computing c_{u,v,w} explicitly. This method extends to Schubert problems with more than three flags, and more generally to parameter spaces of flags in given relative position. The only geometrically reasonable meaning of “given relative position” is the specification of a “rank table” of intersection dimensions, tracking how the pieces of the various flags meet. Achievable or realizable rank tables yield unique “permutation arrays”, and indeed this problem motivated their definition by Eriksson and Linusson. These permutation arrays are closely related to the checker boards used in [Vakil, 2006a, Vakil, 2006b]. The resulting permutation array varieties are natural generalizations of Schubert varieties to an arbitrary number of flags. The advantages of our method are further described in Remark 5.1.

The benefit of permutation arrays is that the elements identify the minimal jumps in dimension, and therefore naturally correspond to critical vectors in the geometry. We use the data from the permutation array to identify and solve a collection of determinantal equations for the permutation array varieties, allowing us to solve Schubert problems explicitly and effectively, for example allowing us to compute Galois/monodromy groups. Maple code for solving Schubert problems using permutation arrays is available at

http://www.math.washington.edu/∼billey/papers/maple.code/ We show that permutation array varieties may be badly behaved. For

example, their equations are not always reduced or irreducible, so we argue that the “correct” generalization of Schubert varieties are permutation array schemes. We describe pathologies of these varieties/schemes, and show that they are not irreducible nor even equidimensional in general, making a generalization of the Bruhat order problematic. We also give counterexamples to Eriksson and Linusson’s Realizability Conjecture 4.1.

We emphasize that the pathologies described here are not an artifact of permutation arrays; permutation arrays are equivalent to tables of intersection dimensions. Permutation arrays are much more manageable as data sets than the full table of intersection dimensions.

On one hand our results are bad news for permutation arrays: the hope that they would predict which rank tables (tables of all intersection dimensions) are possible does not hold true, and this deep question remains open. This difficulty of this problem is very similar to the problem of determining which matroids are realizable. On the other hand, by highlighting key linear-algebraic data, they provide more geometric information about a Schubert problem which can be used for computation. In many of the examples we have tried, the new approach is more effective than any earlier naive approach, sometimes requiring no calculations at all beyond construction of the permutation array. It is an interesting open problem to determine which method is most effective for large Schubert problems. Furthermore, permutation arrays are a “complete flag analog” of Vakil’s checkerboards [Vakil, 2006a]. So, one could ask if there exists a rule for multiplying Schubert classes based on these arrays.

Varieties based on rank tables have appeared in several other places in the literature as well, including [Eisenbud and Saltman, 1987] [Fulton, 1991, Magyar, 2005, Magyar and van der Kallen, 1999].

The outline of the paper is as follows. In Section 2, we review Schubert varieties and the flag manifold. In Section 3, we review the construction of permutation arrays and the Eriksson-Linusson algorithm for generating all such arrays. In Section 4, we describe permutation varieties and their pathologies, and explain why their correct definition is as schemes. In Section 5, we describe how to use permutation arrays to solve Schubert problems and give equations for certain intersections of Schubert varieties. In Section 6, we give two examples of an algorithm for computing triple intersections of Schubert varieties and thereby computing the cup product in the cohomology ring of the flag manifold. The equations we give also allow us to compute Galois and monodromy groups for intersections of Schubert varieties; we describe this application in Section 7. To our knowledge, this is the first use of the Hilbert irreducibility theorem to compute monodromy groups. Our computations lead to examples where the Galois/monodromy group is “smaller than expected”.

2. The flag manifold and Schubert varieties. In this section we briefly review the notation and basic concepts for flag manifolds and Schubert varieties. We refer the reader to one of the following books for further background information: [Fulton, 1997, Macdonald, 1991, Manivel, 1998, Gonciulea and V. Lakshmibai, 2001, Kumar, 2002].

As described earlier, the flag manifold Fl_{n} = Fl_{n}(K) parametrizes the complete flags

F_{•} = {{0} = F_{0} ⊂ F_{1} ⊂ ⋯ ⊂ F_{n} = K^{n}}

where F_{i} is a vector space of dimension i over the field K. Fl_{n} is a smooth projective variety of dimension ( \begin{matrix}n \\ 2 \end{matrix} ). A complete flag is determined by an ordered basis (f_{1}, …, f_{n}) for K^{n} by taking F_{i} = span(f_{1}, …, f_{i}).

Two flags [F_{•}], [G_{•}] ∈ Fl_{n} are in relative position w ∈ S_{n} when
dim(F_{i} ∩ G_{j}) = rank w[i, j] for all 1 ≤ i, j ≤ n

where w[i, j] is the principal submatrix of the permutation matrix for w with lower right hand corner in position (i, j). We use the notation

pos(F_{•}, G_{•}) = w.

Warning: in order to use the typical meaning for a principal submatrix we are using a nonstandard labeling of a permutation matrix. The permutation matrix we associate to w has a 1 in the w(i)th row of column n − i + 1 for 1 ≤ i ≤ n. For example, the matrix associated to w = (5, 3, 1, 2, 4) is

[ \begin{matrix}0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1. \end{matrix} ]

If pos(F_{•}, G_{•}) = (5, 3, 1, 2, 4) then dim(F_{2} ∩G_{3}) = 2 and dim(F_{3} ∩G_{2}) = 1. Define a Schubert cell with respect to a fixed flag F_{•} in Fl_{n} to be

X_{w}^{o}(F_{•}) = {G_{•} | F_{•} and G_{•} have relative position w}
= {G_{•} | dim(F_{i} ∩ G_{j}) = rk w[i, j]}.

Using our labeling of a permutation matrix, the codimension of X_{w}^{o} is equal to the length of w (the number of inversions in w), denoted ℓ(w). In fact, X_{w}^{o} is isomorphic to the affine space K^{( \begin{matrix}n \\ 2 \end{matrix} )−ℓ(w)}. We say the flags F_{•} and G_{•} are in transverse position if G_{•} ∈ X_{id}(F_{•}). A randomly chosen flag will be transverse to any fixed flag F_{•} with probability 1 (using any reasonable measure, assuming the field is infinite).

The Schubert variety X_{w}(F_{•}) is the closure of X_{w}^{o}(F_{•}) in Fl_{n}. Schubert varieties may also be written in terms of rank conditions:

X_{w}(F_{•}) = {G_{•} | dim(F_{i} ∩ G_{j}) ≥ rk w[i, j]}.  (2.1)

If the flags F_{•} and G_{•} are determined by ordered bases for K^{n} then these inequalities can be rephrased as determinantal equations on the coefficients in the bases [Fulton, 1997, 10.5, Ex. 10, 11]. Of course this allows one in theory to solve all Schubert problems, but the number and complexity of the equations conditions grows quickly to make this prohibitive for large n or d. See Section 5.2 for more details.

We remark that the rank equations in (2.1) are typically written in terms of an increasing rank function in the literature as we have done. However, when one wants to write down polynomial equations which vanish on this set, one must use a decreasing rank function. A rank function strictly less than k on a matrix means that every k×k determinantal minor vanishes, while a rank function strictly greater than k means that SOME j×j minor for j ≥ k does NOT vanish. The first description defines a closed subvariety, but the second condition does not. Luckily the rank functions that we are interested in are the coranks of the matrices with the ordered basis reversed so when we need to explicitly present polynomial equations that define a Schubert variety, we will use decreasing rank functions.

The cohomology ring H^{∗}(Fl_{n}) of Fl_{n} is isomorphic to

ℤ[x_{1}, …, x_{n}]/⟨e_{1}, e_{2}, …, e_{n}⟩

where e_{i} is the ith elementary symmetric function on x_{1}, …, x_{n}. For details see [Fulton, 1997, 10.2, B.3]. The cycles [X_{u}] corresponding to Schubert varieties form a ℤ-basis for the ring. The class [X_{u}] := [X_{u}(F_{•})] is independent of the choice of base flag. The product is defined by

[X_{u}] · [X_{v}] = [X_{u}(F_{•}) ∩ X_{v}(G_{•})]

where F_{•} and G_{•} are in transverse position. Speaking informally, X_{u}(F_{•})∩ X_{v}(G_{•}) is a union of irreducible components which are GL_{n}-translates of Schubert varieties. Therefore, in the cohomology ring, the expansion of a product of Schubert cycles

[X_{u}] · [X_{v}] = ∑_{ℓ(w)=ℓ(u)+ℓ(v)} c_{u,v}^{w}[X_{w}]  (2.2)

has nonnegative integer coefficients in the basis of Schubert cycles.

A simpler geometric interpretation of the coefficients c_{u,v}^{w} may be given in terms of triple intersections [Fulton, 1997, 10.2]. There exists a perfect pairing on H^{∗}(Fl_{n}) such that

[X_{w}] · [X_{y}] = \begin{cases}[X_{w_{o}}] & y = w_{o}w \\ 0 & y ≠ w_{o}w, ℓ(y) = ( \begin{matrix}n \\ 2 \end{matrix} ) − ℓ(w). \end{cases}  (2.3)

Here w_{o} = (n, n − 1, …, 1) is the longest permutation in S_{n}, of length ( \begin{matrix}n \\ 2 \end{matrix} ) = dim(Fl_{n}), and [X_{w_{o}}] is the class of a point. Combining equations (2.2) and (2.3) we have

[X_{u}] · [X_{v}] · [X_{w_{o}w}] = c_{u,v}^{w}[X_{w_{o}}].

In characteristic 0, c_{u,v}^{w} counts the number of points [E_{•}] ∈ Fl_{n} in the variety

X_{u}(F_{•}) ∩ X_{v}(G_{•}) ∩ X_{w_{o}w}(H_{•})  (2.4)

when ℓ(u) + ℓ(v) + ℓ(w_{o}w) = ( \begin{matrix}n \\ 2 \end{matrix} ) and F_{•}, G_{•}, H_{•} are three generally chosen flags. Note, it is not sufficient to assume the three flags are pairwise transverse in order to get the expected number of points in the intersection. There can be additional dependencies among the subspaces of the form F_{i} ∩ G_{j} ∩ H_{k}.

The main goal of this article is to describe a method to find all flags in a general d-fold intersection of Schubert varieties when the intersection is zero-dimensional. Enumerating the flags found explicitly in a triple intersection would give the numbers c_{u,v}^{w}. We will use the permutation arrays defined in the next section to identify a different set of equations defining the intersections of Schubert varieties which are easier to solve.

3. Permutation arrays. In [Eriksson and Linusson, 2000a] and [Eriksson and Linusson, 2000b], Eriksson and Linusson develop a d dimensional analog of a permutation matrix. One way to generalize permutation matrices is to consider all d-dimensional arrays of 0’s and 1’s with a single 1 in each hyperplane with a single fixed coordinate. They claim that a better way is to consider a permutation matrix to be a two-dimensional array of 0’s and 1’s such that the rank of any principal minor is equal to the number of occupied rows in that submatrix or equivalently equal to the number of occupied columns in that submatrix. The locations of the 1’s in a permutation matrix will be the elements in the corresponding permutation array. We will summarize their work here and refer the reader to their well-written paper for further details.

Let P be any collection of points in [n]^{d} := {1, 2, …, n}^{d}. We will think of these points as the locations of dots in an [n]^{d}-dot array. Define a partial order on [n]^{d} by

x = (x_{1}, …, x_{d}) ⪯ y = (y_{1}, …, y_{d}),

read “x is dominated by y”, if x_{i} ≤ y_{i} for all 1 ≤ i ≤ d. This poset is a lattice with meet and join operation defined by

x ∨ y = z  if z_{i} = max(x_{i}, y_{i}) for all i
x ∧ y = z  if z_{i} = min(x_{i}, y_{i}) for all i.

These operations extend to any set of points R by taking ⋁ R = z where z_{i} is the the maximum value in coordinate i over the whole set, and similarly for ⋀ R.

Let P [y] = {x ∈ P | x ⪯ y} be the principal subarray of P containing all points of P which are dominated by y. Define

rk_{j}P = #{1 ≤ k ≤ n | there exists x ∈ P with x_{j} = k}.

P is rankable of rank r if rk_{j}P = r for all 1 ≤ j ≤ d. P is totally rankable if every principal subarray of P is rankable.

For example, with n = 4, d = 3 the following example is a totally rankable dot array:

{(3, 4, 1), (4, 2, 2), (1, 4, 3), (3, 3, 3), (2, 3, 4), (3, 2, 4), (4, 1, 4)}.

We picture this as four 2-dimensional slices, where the first one is “slice 1” and the last is “slice 4”:

•  •  \begin{aligned}& • \\ • \end{aligned}  \begin{aligned}& & • \\ & • \\ • \end{aligned}

Thus (3, 4, 1) corresponds to the dot in the first slice on the left.

The array {(3, 4, 1), (4, 2, 2), (1, 4, 3)} is not rankable since it has only two distinct values appearing in the second index and three in the first and third.

Many pairs P, P′ of totally rankable dot arrays are rank equivalent, i.e. rk_{j}P [x] = rk_{j}P′[x], for all x and j. However, among all rank equivalent dot arrays there is a unique one with a minimal number of dots [Eriksson and Linusson, 2000a, Prop. 4.1]. In order to characterize the minimal totally rankable dot arrays, we give the following two definitions. We say a position x is redundant in P if there exists a collection of points R ⊂ P such that x = ⋁ R, #R > 1, and every y ∈ R has at least one y_{i} = x_{i}. We say a position x is covered by dots in P if x is redundant for some R ⊂ P, x ∉ R, and for each 1 ≤ j ≤ d there exists some y ∈ R such that y_{j} < x_{j}. We show in Lemma 3.1 that it suffices to check only subsets R of size at most d when determining if a position is redundant or covered.

Theorem 3.1. [Eriksson and Linusson, 2000b, Theorem 3.2] Let P be a dot array. The following are equivalent:

1. P is totally rankable.

2. Every two dimensional projection of every principal subarray is totally rankable.

3. Every redundant position is covered by dots in P.

4. If there exist dots in P in positions y and z and integers i, j such that y_{i} < z_{i} and y_{j} = z_{j}, then there exists a dot in some position x ⪯ (y ∨ z) such that x_{i} = z_{i} and x_{j} < z_{j}.

Define a permutation array in [n]^{d} to be a totally rankable dot array of rank n with no redundant dots (or equivalently, no covered dots). The permutation arrays are the unique representatives of each rank equivalence class of totally rankable dot arrays with no redundant dots. These arrays are Eriksson and Linusson’s analogs of permutation matrices.

The definition of permutation arrays was motivated because they include the possible relative configurations of flags:

Theorem 3.2. [Eriksson and Linusson, 2000b, Thm. 3.1] Given flags E_{•}^{1}, E_{•}^{2}, …, E_{•}^{d}, there exists an [n]^{d}-permutation array P describing the rank table of all intersection dimensions as follows. For each x ∈ [n]^{d},

rk(P [x]) = dim (E_{x_{1}}^{1} ∩ E_{x_{2}}^{2} ∩ ⋯ ∩ E_{x_{d}}^{d}) .  (3.1)

A special case is the permutation array corresponding to n generally chosen flags, which we denote the transverse permutation array

T_{n,d} = {(x_{1}, …, x_{d}) ∈ [n]^{d} | ∑ x_{i} = (d − 1)n + 1} .  (3.2)

This corresponds to

rk(T_{n,d}[x]) = max (0, n − ∑_{i=1}^{d}(n − x_{i})) .

Eriksson and Linusson give an algorithm for producing all permutation arrays in [n]^{d} recursively from the permutation arrays in [n]^{d−1} [Eriksson and Linusson, 2000b, Sect. 2.3]. We review their algorithm, which we call the EL-algorithm below, as this is key to our algorithm for intersecting Schubert varieties.

Let A be any antichain of dots in P under the dominance order. Let C(A) be the set of positions covered by dots in A. Define the downsizing operator D(A, P) with respect to A on P to be the result of the following process.

1. Set Q_{1} = P \ A.

2. Set Q_{2} = Q_{1} ∪ C(A).

3. Set D(A, P) = Q_{2} \ R(Q_{2}) where R(Q) is the set of redundant positions of Q.

The downsizing of a totally rankable array P is successful if the resulting array is again totally rankable and has rank rk(P) − 1.

Theorem 3.3. (The EL-Algorithm) For each pair n, d of positive integers, the set of all permutation arrays in [n]^{d} can be obtained by the following algorithm:

1. For each permutation array P_{n} in [n]^{d−1}.

2. If P_{n}, …, P_{i} have been defined, and i > 1, then choose an antichain A_{i} of dots in P_{i} such that the downsizing D(A_{i}, P_{i}) is successful. Set P_{i−1} = D(A_{i}, P_{i}).

3. Set A_{1} = P_{1}.

4. Set P = {(x_{1}, …, x_{d−1}, i) | (x_{1}, …, x_{d−1}) ∈ A_{i}}. Add P to the

list of permutation arrays in [n]^{d} constructed thus far. Furthermore, each permutation array P is constructed from a unique P_{n} in [n]^{d−1} and a unique sequence of anti-chains.

For example, starting with the 2-dimensional array

{(1, 4), (2, 3), (3, 1), (4, 2)}

corresponding to the permutation w = (1, 2, 4, 3), we run through the algorithm as follows. (In the figure, dots correspond to elements in P and circled dots correspond to elements in A.)

\begin{matrix}P_{4} = \{(1, 4), (2, 3), (3, 1), (4, 2)\} & A_{4} = \{(1, 4), (2, 3)\} \\ P_{3} = \{(2, 4), (3, 1), (4, 2)\} & A_{3} = \{(3, 1)\} \\ P_{2} = \{(2, 4), (4, 2)\} & A_{2} = \{(2, 4), (4, 2)\} \\ P_{1} = \{(4, 4)\} & A_{1} = \{(4, 4)\} \end{matrix}

\begin{aligned}& • \\ • \end{aligned}  \begin{aligned}• \\ & • \end{aligned}

This produces the 3-dimensional array

P = {(4, 4, 1), (2, 4, 2), (4, 2, 2), (3, 1, 3), (1, 4, 4), (2, 3, 4)}.

We prefer to display 3-dimensional dot-arrays as 2-dimensional number arrays as in [Eriksson and Linusson, 2000b, Vakil, 2006a] where a square (i, j) contains the number k if (i, j, k) ∈ P. The previous example is represented by

4 4 2 3 2 1 .

Note that there is at most one number in any square if the number-array represents a permutation array: by Theorem 3.1 Part 4, if two dots y, z in a totally rankable array P existed such that y_{1} = z_{1}, y_{2} = z_{2}, y_{3} < z_{3}, then there exists a third dot x ⪯ (y ∨ z) = z in P with x_{3} = z_{3} and x_{i} < y_{i} for i = 1 or 2, but this implies that z is redundant for the set R = {x, y}, hence P is not a permutation array.

Corollary 3.1. In Theorem 3.3, each P_{i} is an [n]^{d−1}-permutation array of rank i. Furthermore, if P determines the rank table for flags E_{•}^{1}, …, E_{•}^{d}, then P_{i} determines the rank table for E_{•}^{1}, …, E_{•}^{d−1} intersecting the vector space E_{i}^{d}, i.e.

rk (P_{i}[x]) = dim (E_{x_{1}}^{1} ∩ E_{x_{2}}^{2} ∩ ⋯ ∩ E_{x_{d−1}}^{d−1} ∩ E_{i}^{d}) .

Proof. P_{i} is the permutation array obtained from the projection

{(x_{1}, …, x_{d}) | (x_{1}, …, x_{d}, x_{d+1}) ∈ P and x_{d+1} ≤ i}

by removing all repeated or covered elements.

To represent a 4-dimensional permutation array, we often draw the n 3-dimensional permutation arrays P_{1}, …, P_{n} from the EL-algorithm. For example,

4  4 4 3  4 4 3 4 3 2  1 4 3 2

represents the 4-dimensional permutation array with entries

\begin{matrix}(4, 2, 4, 1), (2, 4, 4, 2), (4, 4, 3, 2), (3, 3, 4, 3), (3, 4, 3, 3), (4, 3, 3, 3), \\ (4, 4, 2, 3), (1, 4, 1, 4), (2, 1, 4, 4), (3, 3, 3, 4), (4, 2, 2, 4). \end{matrix}

We finish this section with a substantial improvement on the speed to the Eriksson-Linusson algorithm. In Step 2 of Theorem 3.3, one must find all positions covered by a subset of points in the antichain A_{i}. This appears to require on the order of 2^{|A_{i}|} computations. However, here we show that subsets of size at most d are sufficient.

Lemma 3.1. A position x ∈ [n]^{d} is covered (or equivalently, redundant) in a permutation array P if and only if there exists a subset S with |S| ≤ d which covers x.

Proof. Assume x is covered by a set Y = {y^{1}, y^{2}, …, y^{k}} for k > d. That is,

• For each position 1 ≤ j ≤ d, there exists a y^{i} such that y_{j}^{i} < x_{j}

and there exists a y^{l} such that y_{j}^{l} = x_{j}.

• For each y^{i} ∈ Y, there exists a j such that y_{j}^{i} < x_{j} and there exists

an l such that y_{l}^{i} = x_{l}.

Consider a complete bipartite graph with left vertices labeled by Y and right vertices labeled by {x_{1}, …, x_{d}}. Color the edge from y^{i} to x_{j} red if y_{j}^{i} = x_{j}, and blue if y_{j}^{i} < x_{j}. Since x = ⋁ Y, y_{j}^{i} > x_{j} is not possible. This is a complete bipartite graph such that each vertex meets at least one red and one blue edge, and conversely any such complete bipartite graph with left vertices chosen from P and right vertices {x_{1}, …, x_{d}} corresponds to a covering of x.

We can easily bound the minimum size of a covering set for x to be at most d+1 as follows. Choose one red and one blue edge adjacent to x_{1}. Let S be the left end-points of these two edges. Vertex x_{2} is connected to both elements of S in the complete bipartite graph. If the edges connecting x_{2} to S are different colors, proceed to x_{3}. If the edges agree in color, choose one additional edge of a different color adjacent to x_{2}. Add its left endpoint to S. Continuing in this way for x_{3}, …, x_{d}, we have |S| ≤ d + 1 and that x is covered by S.

Given a covering set S of size d + 1, we now find a subset of size d which covers x. Say x_{i_{1}}, x_{i_{2}}, …, x_{i_{k}} are all the right vertices which are adjacent to a unique edge of either color. Let T be the left endpoints of all of these edges; these are necessary in any covering subset. Choose one vertex in Y \ T, say ỹ. Each remaining x_{j} has at least two edges of each color, so we can choose one of each color which is not adjacent to ỹ. The induced subgraph on (S \ {ỹ}, {x_{1}, …, x_{d}}) is again a complete bipartite graph where every vertex is adjacent to at least one red and one blue edge, hence S \ {ỹ} covers x.

4. Permutation array varieties/schemes and their pathologies. In analogy with Schubert cells, for any [n]^{d}-permutation array P, Eriksson and Linusson define the permutation array variety X_{P}^{o} to be the subset of Fl_{n}^{d} = {(E_{•}^{1}, …, E_{•}^{d})} in “relative position P ” [Eriksson and Linusson, 2000b, §1.2.2]. We will soon see why X_{P}^{o} is a locally closed subvariety of Fl_{n}^{d}; this will reinforce the idea that the correct notion is of a permutation array scheme. The closure of X_{P}^{o} will be defined by the rank equations

rk(P [x]) ≥ dim (E_{x_{1}}^{1} ∩ E_{x_{2}}^{2} ∩ ⋯ ∩ E_{x_{d}}^{d}) .  (4.1)

These rank equations can then be interpreted as determinantal equations as we explain below. These varieties/schemes will give a convenient way to manage the equations of intersections of Schubert varieties.

Based on many examples, Eriksson and Linusson [Eriksson and Linusson, 2000b, Conj. 3.2] conjectured the following statement.

Realizability Conjecture 4.1. Every permutation array can be realized by flags. Equivalently, every X_{P}^{o} is nonempty.

This question is motivated by more than curiosity. A fundamental question is: what are the possible relative configurations of d flags? In other words: what rank (intersection dimension) tables are possible? For d = 2, the answer leads to the theory of Schubert varieties. By Theorem 3.2, each achievable rank table yields a permutation array, and the permutation arrays may be enumerated by Theorem 3.3. The Realizability Conjecture then says that we have fully answered this fundamental question. Failure of realizability would imply that we still have a poor understanding of how flags can meet.

The Realizability Conjecture is true for d = 1, 2, 3. For d = 1, the only permutation array variety is the flag variety. For d = 2, the permutation array varieties are the “generalized” Schubert cells (where the reference flag may vary). The case d = 3 follows from [Shapiro et al., 1997] (as described in [Eriksson and Linusson, 2000b, §3.2]), see also [Vakil, 2006a, §4.8]. The case n ≤ 2 is fairly clear, involving only one-dimensional subspaces of a two-dimensional vector space (or projectively, points on ℙ^{1}), cf. [Eriksson and Linusson, 2000b, Lemma 4.3]. Nonetheless, the conjecture is false, and we give examples below which show the bounds d ≤ 3 and n ≤ 2 are maximal for such a realizability statement. We found it interesting that the combinatorics of permutation arrays prevent some naive attempts at counterexamples from working; somehow, permutation arrays see some subtle linear algebraic information, but not all.

Fiber permutation array varieties. If P is an [n]^{d+1} permutation array, then there is a natural morphism X_{P}^{o} → Fl_{n}^{d} corresponding to “forgetting the last flag”. We call the fiber over a point (E_{•}^{1}, …, E_{•}^{d}) a fiber permutation array variety, and denote it X_{P}^{o} (E_{•}^{1}, …, E_{•}^{d}). If the flags E_{•}^{1}, …, E_{•}^{d} are chosen generally, we call the fiber permutation array variety a generic fiber permutation array variety. Note that a generic fiber permutation array variety is empty unless the projection of the permutation array to the “bottom hyperplane of P ” is the transverse permutation array T_{n,d}, as this projection describes the relative positions of the first d flags.

The Schubert cells X_{w}^{o}(E_{•}^{1}) are fiber permutation array varieties, with d = 2. Also, any intersection of Schubert cells

X_{w_{1}}(E_{•}^{1}) ∩ X_{w_{2}}(E_{•}^{2}) ∩ ⋯ ∩ X_{w_{d}}(E_{•}^{d})

is a disjoint union of fiber permutation array varieties, and if the E_{•}^{i} are generally chosen, the intersection is a disjoint union of generic fiber permutation array varieties.

Permutation array varieties were introduced partially for this reason, to study intersections of Schubert varieties, and indeed that is the point of this paper. It was hoped that they would in general be tractable and well-behaved (cf. the Realizability Conjecture 4.1), but sadly this is not the case. The remainder of this section is devoted to their pathologies, and is independent of the rest of the paper.

Permutation array schemes. We first observe that the more natural algebro-geometric definition is of permutation array schemes: the set of d-tuples of flags in configuration P comes with a natural scheme structure, and it would be naive to expect that the resulting schemes are reduced. In other words, the “correct” definition of X_{P}^{o} will contain infinitesimal information not present in the varieties. More precisely, the X_{P}^{o} defined above may be defined scheme-theoretically by the equations (3.1), and these equations will not in general be all the equations cutting out the set X_{P}^{o} (see the “Further Pathologies” discussion below). Those readers preferring to avoid the notion of schemes may ignore this definition. Other readers should re-define X_{P}^{o} to be the scheme cut out by equations (3.1), which is a locally closed subscheme of Fl_{n}^{d}. More explicitly, (3.1) specifies certain rank conditions, which can be written in terms of equations as follows. Requiring that the rank of a matrix is r corresponds to requiring that all of the (r + 1) × (r + 1) minors vanish, and that some r × r minor does not vanish.

We now give a series of counterexamples to the Realizability Conjecture 4.1.

Counterexample 1. Eriksson and Linusson defined their permutation array varieties over ℂ, so we begin with a counterexample to realizability over K = ℂ, and it may be read simply as an admonition to always consider a more general base field (or indeed to work over the integers). The Fano plane is the projective plane over the field 𝔽_{2}, consisting of 7 lines ℓ_{1}, …, ℓ_{7} and 7 points p_{1}, …, p_{7}. We may name them so that p_{i} lies on ℓ_{i}, as in Figure 1. Thus we have a configuration of 7 flags over 𝔽_{2}. (This is a projective picture, so this configuration is in affine dimension n = 3, and the points p_{i} should be interpreted as one-dimensional subspaces, and the lines ℓ_{j} as two-dimensional subspaces, of K^{3}.) The proof of Theorem 3.2 is independent of the base field, so the rank table of intersection dimensions of the flags yields a permutation array. However, a classical and straightforward argument in projective coordinates shows that the configuration of Figure 1 may not be achieved over the complex numbers (or indeed over any field of characteristic not 2). In particular, this permutation array variety is not realizable over ℂ. In order to patch this counterexample, one might now restate the Realizability Conjecture 4.1 by saying that there always exists a field such that X_{P}^{o} is nonempty. However, the problems have only just begun.

Fig. 1. The Fano plane, and a bijection of points and lines (indicated by arrows from points to the corresponding line).

Counterexample 2. We next sketch an elementary counterexample for n = 3 and d = 9, over an arbitrary field, with the disadvantage that it requires a computer check. Recall Pappus’ Theorem in classical geometry: if A, B, and C are collinear, and D, E, and F are collinear, and X = AE ∩ BD, Y = AF ∩ CD, and Z = BF ∩ CE, then X, Y, and Z are collinear [Coxeter and Greitzer, 1967, §3.5]. The result holds over any field. A picture is shown in Figure 2. (Ignore the dashed arc and the stars for now.)

We construct an unrealizable permutation array as follows. We imagine that line Y Z does not meet X. (In the figure, the starred line Y Z “hops over” the point marked X.) We construct a counterexample with nine flags by letting the flags correspond to the nine lines of our “deformed Pappus configuration”, choosing points on the lines arbitrarily. We then construct the rank table of this configuration, and verify that this corresponds to

Fig. 2. Pappus’ Theorem, and a counterexample to Realizability in dimension d = 3 with n = 9

a valid permutation array. (This last step was done by computer.) This permutation array is not realizable, by Pappus’ theorem.

Counterexample 3. Our next example shows that realizability already fails for n = 4, d = 4. The projective intuition is as follows. Suppose ℓ_{1}, ℓ_{2}, ℓ_{3}, ℓ_{4} are four lines in projective space, no three meeting in a point, such that we require ℓ_{i} and ℓ_{j} to meet, except (possibly) ℓ_{3} and ℓ_{4}. This forces all 4 lines to be coplanar, so ℓ_{3} and ℓ_{4} must meet. Hence we construct an unrealizable configuration as follows: we “imagine” (as in Figure 3) that ℓ_{3} and ℓ_{4} don’t meet. Again, we must turn the projective picture in ℙ^{3} into linear algebra in 4-space, so the projective points in the figure correspond to one-dimensional subspaces, the projective lines in the figure correspond to two-dimensional subspaces of their respective flags, etc. Again, the tail of each arrow corresponds with the point which lies on the line the arrow follows. We construct the corresponding dot array:

4  4 4 3  4 4 3 4 3 2  1 4 3 2

Here the rows represent the flag F_{•}^{1}, columns represent the flag F_{•}^{2}, numbers represent the flag F_{•}^{3}, and the boards represent the flag F_{•}^{4}. This is readily checked to be a permutation array. The easiest way is to compare it to the dot array for the “legitimate” configuration, where F_{2}^{3} and F_{2}^{4} do meet, and using the fact that this second array is a permutation array by Theorem 3.2. The only difference between the permutation array above and the “legitimate” one is that the circled 3 should be a 2.

Fig. 3. A counterexample to realizability with n = d = 4

Remark. Eriksson and Linusson have verified the Realizability Conjecture 4.1 for n = 3 and d = 4 [Eriksson and Linusson, 2000b, §3.1]. Hence the only four open cases left are n = 3 and 5 ≤ d ≤ 8. These cases seem simple, as they involve (projectively) between 5 and 8 lines in the plane. Can these remaining cases be settled?

Further pathologies from Mnëv’s universality theorem: failure of irreducible and equidimensionality. Mnëv’s universality theorem shows that permutation array schemes will be “arbitrarily” badly behaved in general, even for n = 3. Informally, Mnëv’s theorem states that given any singularity type of finite type over the integers there is a configuration of projective lines in the plane such that the corresponding permutation array scheme has that singularity type. By a singularity type of finite type over the integers, we mean up to smooth parameters, any singularity cut out by polynomials with integer co-efficients in a finite number of variables. See [Mnëv, 1985, Mnëv, 1988] for the original sources, and [Vakil, 2006c, §3] for a precise statement and for an exposition of the version we need. (Mnëv’s theorem is usually stated in a different language of course.)

In particular, (i) permutation array schemes need not be irreducible, answering a question raised in [Eriksson and Linusson, 2000b, §1.2.3]. They can have arbitrarily many components, indeed of arbitrarily many different dimensions. (ii) Permutation array schemes need not be reduced, i.e. they have genuine scheme-theoretic (or infinitesimal) structure not present in the variety. In other words, the definition of permutation array schemes is indeed different from that of permutation array varieties, and the equations (3.1) do not cut out the permutation array varieties scheme-theoretically. (iii) Permutation array schemes need not be equidimensional. Hence the hope that permutation array varieties/schemes might be well-behaved is misplaced. In particular, the notion of Bruhat order is problematic as already noted in [Eriksson and Linusson, 2000b]. We suspect, for example, that there exist two permutation array schemes X and Y such that Y is reducible, and some but not all components of Y lie in the closure of X.

Although Mnëv’s theorem is constructive, we have not attempted to explicitly produce a reducible or non-reduced permutation array scheme.

5. Intersecting Schubert varieties. In this section, we consider a Schubert problem in Fl_{n} of the form

X = X_{w^{1}}(E_{•}^{1}) ∩ X_{w^{2}}(E_{•}^{2}) ∩ ⋯ ∩ X_{w^{d}}(E_{•}^{d})

with E_{•}^{1}, …, E_{•}^{d} chosen generally and ∑_{i} ℓ(w^{i}) = ( \begin{matrix}n \\ 2 \end{matrix} ). We show there is a unique permutation array P for this problem if X is nonempty, and we identify it. In Theorem 5.2 we show how to use P to write down equations for X. These equations can also be used to determine if E_{•}^{1}, …, E_{•}^{d} are sufficiently general for computing intersection numbers. The number of solutions will always be either infinite or no greater than the expected number. The expected number is achieved on a dense open subset of Fl_{n}^{d}. It may be useful for the reader to refer to the examples in Section 6 while reading this section.

Theorem 5.1. If X is 0-dimensional and nonempty, there exists a unique permutation array P ⊂ [n]^{d+1} such that

dim (E_{x_{1}}^{1} ∩ E_{x_{2}}^{2} ∩ ⋯ ∩ E_{x_{d}}^{d} ∩ F_{x_{d+1}}) = rkP [x]

for all F_{•} ∈ X and all x ∈ [n]^{d+1}. Hence, X is equal to the fiber permutation array variety X_{P}^{o} (E_{•}^{1}, …, E_{•}^{d}).

It is natural to ask which permutation array this is, and this will be necessary for later computations. We describe the permutation array (in the guise of its rank table) in Subsection 5.1.

The generalization to the case where X has positive dimension is left to the interested reader; the permutation array then describes the generic behavior on every component of X. The argument below carries through essentially without change.

Proof. Consider the variety

X′ := X_{w^{1}}(F_{•}) ×_{Fl_{n}} X_{w^{2}}(F_{•}) ×_{Fl_{n}} ⋯ ×_{Fl_{n}} X_{w^{d}}(F_{•}).  (5.1)

Here F_{•} is the flag parametrized by the base Fl_{n}. The “incidence variety” X′ is a product of Schubert variety bundles over the flag variety, and hence clearly irreducible; its dimension is

dim X′ = (d + 1)\binom{n}{2} − ∑_{i} ℓ(w^{i}) = d\binom{n}{2}.

Let E_{•}^{i} be the flag parametrized by the ith factor of (5.1). To each point of X′ there is a permutation array describing how the d + 1 flags E_{•}^{1}, …, E_{•}^{d}, F_{•} meet, i.e. with rank table

dim (E_{x_{1}}^{1} ∩ E_{x_{2}}^{2} ∩ ⋯ ∩ E_{x_{d}}^{d} ∩ F_{x_{d+1}}) .

As each entry in the rank table is uppersemicontinuous, there is a dense open subset U ⊂ X′ on which the rank table (and hence the permutation array) is constant. Let ∂X′ = X′ − U. By the hypothesis ∑_{i} ℓ(w^{i}) = \binom{n}{2}, the morphism X′ → Fl_{n}^{d} (remembering the flags E_{•}^{1},…, E_{•}^{d}) is generically finite, and as dim ∂X′ < dim X′ = dim Fl_{n}^{d}, the preimage of a general point of Fl_{n}^{d} (i.e. X) misses dim ∂X′.

We next describe how to compute the rank table described in Theorem 5.1.

5.1. Permutation array algorithm. We describe the rank table of the general element of the product of bundles (5.1). We will compute

dim (E_{x_{1}}^{1} ∩ ⋯ ∩ E_{x_{p}}^{p} ∩ F_{x_{d+1}})

inductively on p, where the base case p = 0 is trivial. We assume that the answer is known for p−1, and describe the case p. Let V = E_{x_{1}}^{1} ∩⋯∩E_{x_{p−1}}^{p−1}. This meets flag F_{•} in a known way (by the inductive hypothesis, say the it lies in the Schubert cell X_{λ}(F_{•}) in the Grassmannian G(dim V, n)), and E_{•}^{p} meets F_{•} in a known way, corresponding to permutation w^{p}. As we are considering a general element of the product of bundles, the question boils down to the following: given a general element [V] ∈ X_{λ}(F_{•}) ⊂ G(dim V, n), and a general element [E_{•}^{p}] ∈ X_{w^{p}}(F_{•}) ⊂ Fl_{n}, how do V, E_{•}^{p}, and F_{•} meet, i.e. what is

dim(V ∩ E_{x_{p}}^{p} ∩ F_{x_{d+1}})

as x_{p} and x_{d+1} vary through {1, …, n}? In other words, we have the data of one n × n table, containing the entries dim(E_{x_{p}}^{p} ∩ F_{x_{d+1}}) (the data of w^{p}; here x_{p} and x_{d+1} vary through {1, …, n}), and we wish to fill in the entries of another n × n table, with entries dim(V ∩ E_{x_{p}}^{p} ∩ F_{x_{d+1}}), where one edge (where x_{p} = n) is known (the data of V).

We now address this linear algebra problem. We fix E_{•}^{p} and F_{•}, and let V vary in X_{λ}^{o}(F_{•}). Choose a basis e_{1}, …, e_{n} of our n-dimensional space, so that F_{i} = ⟨e_{1}, …, e_{i}⟩, and E_{i}^{p} is the span of the appropriate i basis elements in terms of the permutation array for the permutation w^{p}, i.e. E_{j}^{p} is the span of the e_{i}’s where i ∈ {w_{1}, …, w_{i}} and w = w_{0}(w^{p})^{−1}. We can assume that F_{•} is actually in the Schubert cell X_{w^{p}}^{o}(E_{•}^{p}), not just the Schubert variety X_{w^{p}}(E_{•}^{p}): by repeating this discussion with any component of the boundary, we see that such a boundary locus is of strictly smaller dimension. (Again, the interested reader will readily generalize this discussion to the case where X has positive dimension; the generalization of Theorem 5.1 gives a permutation array for the behavior at the general point of each component of X.)

The Schubert cell X_{λ} corresponds to a subset λ = {λ_{1}, …, λ_{dim V} } ⊂ {1, …, n}, and a general element [V] of X_{λ}(F_{•}) is spanned by the vectors

v_{1} =?e_{1} + ⋯ +?e_{λ_{1}}  (5.2)
v_{2} =?e_{1} + ⋯ + ˆ?e_{λ_{1}} + ⋯ +?e_{λ_{2}},  (5.3)
⋮  (5.4)
v_{dim V} =?e_{1} + ⋯ + ˆ?e_{λ_{1}} + ⋯ + { \atop ?e_{λ_{dim V −1}}} + ⋯ +?e_{λ_{dim V}}  (5.5)

where the non-zero coefficients (the question marks) are chosen generally. Let V_{i} be the set of indices j such that e_{j} has non-zero coefficient in v_{i}.

We wish to compute dim(V ∩ E_{j}^{p} ∩ F_{k}) for each j = x_{p} and k = x_{d+1}. This is now a rank calculation: V ∩ F_{k} is the span of those basis elements of V (in (5.2)–(5.5)) involving no basis elements above e_{k}. We seek the dimension of the intersection of this with E_{j}^{p}, which is the span of known standard basis elements indexed by I_{j}. Therefore,

dim(V ∩ E_{j}^{p} ∩ F_{k}) = dim(span{v_{i} : λ_{i} ≤ k} ∩ span{e_{w_{1}}, …, e_{w_{j}}}) (5.6)

where w = w_{0}(w^{p})^{−1} as above. This dimension is the corank of the matrix whose rows are determined by the given basis of V ∩ F_{x_{d+1}} and the basis of E_{x_{p}}^{p}. This can be computed “by eye” as follows. We then look for k columns, and more than k of the first dim V rows each of whose question marks all appear in the chosen k columns. Whenever we find such a configuration, we erase all but the first k of those rows — the remaining rows are dependent on the first k. The number of rows of the matrix remaining after this operation is the rank of the matrix, and the number of erased rows is the corank.

Thus we have described how to compute the rank table of the general element of the product of bundles (5.1).

One interesting problem in Schubert calculus is to determine efficiently if a structure constant for H^{∗}(G/B, ℤ) is zero, or equivalently if X is empty. In the case of the Grassmannian manifold, non-empty Schubert problems are related to triples of eigenvalues satisfying Horn’s recurrence and Knutson-Tao honeycombs [Knutson and Tao, 2001]. For the flag manifold, both Knutson [Knutson, 2001] and Purbhoo [Purbhoo, 2006] gave a sufficient criteria for vanishing in terms of decent cycling and “root games” respectively. Below we give a criteria for vanishing that is very easy to compute, in fact more efficient than Knutson or Purbhoo’s result, however, less comprehensive. As evidence that our criteria is more efficient, we give a pseudo random example in S_{15} which was computed in a few seconds on by a computer. This technique has been extended recently in [Ardila and Billey, 2006] by considering a matroid on the 1-dimensional spans E_{x_{1}}^{1} ∩ ⋯ ∩ E_{x_{d}}^{d}.

Corollary 5.1. Let P be the permutation array whose rank table coincides with the table constructed by the algorithm in Section 5.1 for a given collection of permutations w^{1}, …, w^{d} such that ∑_{i} ℓ(w^{i}) = ( \begin{matrix}n \\ 2 \end{matrix} ). Let P_{n} be the projection of P onto the first d coordinates following the notation of Theorem 3.3. If P_{n} ≠ T_{n,d}, then X is the empty set.

When d = 4, this corollary can often be used to detect when the coefficients c_{u,v}^{w} are zero in Equation 2.2. This criterion catches 7 of the 8 zero coefficients in 3 dimensions, 373 of the 425 in 4 dimensions, and 28920 of the 33265 in dimension 5. The dimension 3 case missed by this criterion is presumably typical of what the criterion fails to see: there are no 2-planes in 3-space containing three general 1-dimensional subspaces. However, given a 2-plane V, three general flags with 1-subspaces contained in V are indeed transverse.

The corollary and algorithm are efficient to apply. For example, consider the following three permutations (anagrams) of the name “Richard P. Stanley” in S_{15}.^{1} To interpret these phases as permutations, only the letters count — not spaces or punctuation — the permutation is not casesensitive, and repeated letters are listed in their original order in the name which is also the identity element.

• u = A Children’s Party

• v = Hip Trendy Rascal

• w = Raid Ranch Let Spy. Using a computer, we can easily compute P_{n} corresponding to X = X_{u} ∩ X_{v} ∩ X_{w}:

P15 = [ \begin{matrix}& & & & & & & & & & & & & & 11 \\ & & & & & & & & & & & & & 14 \\ & & & & & & & & & & & & 14 & 11 & 3 \\ & & & & & & & & & & & 15 \\ & & & & & & & & & & 15 & 14 & 11 & 5 \\ & & & & & & & & & 15 & 14 & 11 & 6 \\ & & & & & & & & 15 & 8 \\ & & & & & & & 15 & 14 & & 13 \\ & & & & & & 15 & 14 & 8 & 4 \\ & & & & & 15 & 14 & 13 & & & 12 \\ & & & & 15 & 14 & 13 & 8 & 3 & & & & & & 2 \\ & & & 15 & 14 & 13 & 12 & & & & 11 & 9 \\ & & 15 & 8 & & & & 2 & & & & & & & 1 \\ & 15 & 13 & & & 11 & & & & & 10 \\ 15 & 13 & 8 & 7 \end{matrix} ]

Clearly, P_{15} ≠ T_{15,3} so X is empty and c_{u,v}^{w_{0}w} = 0.

The array T_{n,d} is an antichain under the dominance order on [n]^{d} so each element x ∈ T_{n,d} corresponds with a principle subarray T_{n,d}[x] = {x} consisting of a single element. Therefore, each x ∈ T_{n,d} corresponds with a 1-dimensional vector space E_{x_{1}}^{1} ∩ E_{x_{2}}^{2} ∩ ⋯ ∩ E_{x_{d−1}}^{d−1} ∩ E_{i}^{d}. Define

V (E_{•}^{1}, …, E_{•}^{d}) = {v_{x} | x ∈ T_{n,d}}

1The name Richard P. Stanley has an unusually high number of interesting anagrams. Stanley has a long list of such anagrams on his office door. They are also available on his homepage by clicking on his name.

to be a collection of non-zero vectors chosen such that v_{x} ∈ E_{x_{1}}^{1} ∩E_{x_{2}}^{2} ∩⋯∩ E_{x_{d}}^{d}. These lines will provide a “skeleton” for the given Schubert problem.

Theorem 5.2. Let X = X_{w^{1}}(E_{•}^{1}) ∩ X_{w^{2}}(E_{•}^{2}) ∩ ⋯ ∩ X_{w^{d}}(E_{•}^{d}) be a 0-dimensional intersection, with E_{•}^{1}, …, E_{•}^{d} general. Let P ⊂ [n]^{d+1} be the unique permutation array associated to this intersection. Then polynomial equations defining X can be determined simply by knowing P and V (E_{•}^{1}, …, E_{•}^{d}).

To prove the theorem, we give an algorithm for constructing the promised equations in terms of the data in P and V (E_{•}^{1}, …, E_{•}^{d}). Then we explain how to construct all the flags in X from the solutions to the equations.

Proof. Let P_{1}, …, P_{n} be the sequence of permutation arrays in [n]^{d} used to obtain P in the EL-Algorithm in Theorem 3.3. If F_{•} ∈ X, then by Corollary 3.1 P_{i} is the unique permutation array encoding dim(E_{x_{1}}^{1} ∩ E_{x_{2}}^{2} ∩ ⋯ ∩ E_{x_{d}}^{d} ∩ F_{i}). Furthermore, for each x ∈ P_{i}, 1 ≤ i ≤ n, choose a representative vector in the corresponding intersection, say v_{x}^{i} ∈ E_{x_{1}}^{1} ∩ E_{x_{2}}^{2} ∩ ⋯ ∩ E_{x_{d}}^{d} ∩ F_{i}. Define

V_{i} = {v_{y}^{i} | y ∈ P_{i}}
V_{i}[x] = {v_{y}^{i} | y ∈ P_{i}[x]}.

More specifically, choose the vectors v_{x}^{i} so that v_{x}^{i} ∉ Span(V_{i}[x] \ {v_{x}^{i}}) since the rank function must increase at position x. Therefore, we have

v.rk(V_{i}[x]) = rk(P_{i}[x])  (5.7)

for all x ∈ [n]^{d} and all 1 ≤ i ≤ n where v.rk(S) is the dimension of the vector space spanned by the vectors in S. These rank conditions define X.

Let V_{n} = V (E_{•}^{1}, …, E_{•}^{d}) be the finite collection of vectors in the case i = n. Given V_{i+1}, P_{i+1} and P_{i}, we compute

V_{i} = {v_{x}^{i} | x ∈ P_{i}}

recursively as follows. If x ∈ P_{i} ∩ P_{i+1} then set

v_{x}^{i} = v_{x}^{i+1}.

If x ∈ P_{i} \ P_{i+1} and y, …, z is a basis set for P_{i+1}[x], i.e. v_{y}^{i+1}, …, v_{z}^{i+1} are independent and span the vector space generated by all v_{w}^{i+1} with w ∈ P_{i+1}[x], then set

v_{x}^{i} = c_{y}^{i}v_{y}^{i} + ⋯ + c_{z}^{i}v_{z}^{i}  (5.8)

where c_{y}^{i}, …, c_{z}^{i} are indeterminate. Now the same rank equations as in (5.7) must hold. In fact, it is sufficient in a 0-dimensional variety X to require only

v.rk{v_{y}^{i} | y ∈ P_{i}[x]} ≤ rk(P_{i}[x])  (5.9)

for all x ∈ [n]^{d} and all 1 ≤ i ≤ n. Let minors_{k}(M) be the set of all k × k determinantal minors of a matrix M. Let M(V_{i}[x]) be the matrix whose rows are given by the vectors in V_{i}[x]. Then, the rank conditions (5.9) can be rephrased as

minors_{rk(P_{i}[x])+1}(M(V_{i}[x])) = 0  (5.10)

for all 1 ≤ i < n and x ∈ [n]^{d} such that ∑ x_{i} > (d − 1)n.

For each set of solutions S to the equations in (5.10), we obtain a collection of vector sets by substituting solutions for the indeterminates in the formulas (5.8) for the vectors. Note, these “solutions” may be written in terms of other variables so at an intermediate point in the computation, there could potentially be an infinite number of solutions. We further eliminate variables whenever a vector depends only on one variable c_{y}^{i} by setting it equal to any nonzero value which does not force another c_{z}^{j} = 0. If ever a solution implies c_{z}^{j} = 0, then the choice of E_{•}^{1}, …, E_{•}^{d} was not general. Let V_{1}^{S}, … V_{n}^{S} be the final collection of vector sets depending on the solutions S. Since X is 0-dimensional, if V_{1}^{S}, … V_{n}^{S} depends on any indeterminate then E_{•}^{1}, …, E_{•}^{d} was not general. Let F_{i}^{S} be the span of the vectors in V_{i}^{S}. Then the flag F_{•}^{S} = (F_{1}^{S}, …, F_{n}^{S}) satisfies all the rank conditions defining X = X_{P}^{o} (E_{•}^{1}, …, E_{•}^{d}). Hence, F_{•}^{S} ∈ X.

Corollary 5.2. The equations appearing in (5.10) provide a test for determining if E_{•}^{1}, …, E_{•}^{d} is sufficiently general for the given Schubert problem. Namely, the number of flags satisfying the equations (5.10) is the generic intersection number if each indeterminate c_{z}^{i} takes a nonzero value, and the solution space determined by the equations is 0-dimensional.

Remark 5.1. Theorem 5.2 has two clear advantages over a naive approach to intersecting Schubert varieties. First, we have reduced the computational complexity for finding all solutions to certain Schubert problems. See Section 5.2 for a detailed analysis. Second, we see the permutation arrays as a complete flag analog of the checkerboards in the geometric Littlewood-Richardson rule of [Vakil, 2006a]. More specifically, checker boards are two nested [n]^{2} permutation arrays. A permutation array P can be thought of as n nested permutation arrays P_{1}, P_{2}, …, P_{n} using the notation in Theorem 3.3. Then the analog of the initial board in the checker’s game would be the unique [n]^{2} permutation array corresponding to two permutations u and v, the final boards in the tree would encode the permutations w such that c_{uv}^{w} ≠ 0 in (2.2). The “legal moves” from level i to level i + 1 can be determined by degenerations in specific cases solving the equations in Theorem 5.2, but we don’t know a general rule at this time. A two-step version of such a rule is given in [Coskun], see also [Coskun and Vakil].

5.2. Algorithmic Complexity. It is well known that solving Schubert problems are “hard”. To our knowledge, no complete analysis of the algorithmic complexity is known. We will attempt to show that the approach outlined in Theorem 5.2 typically reduces the number of variables introduced into the system, while unfortunately increasing the number of rank conditions. Therefore, the entire process is still exponential as both n and d grow large.

For a fixed n and d, the following naive approach would imply that a typical Schubert problem would require one to consider d · n^{2} rank conditions in n^{2} variables. First, consider an arbitrary flag F_{•} ∈ Fl_{n}. In terms of a fixed basis, {e_{1}, …, e_{n}}, one could give an ordered basis for F_{•} with n^{2} variable coefficients. Then for each permutation w^{i} for 1 ≤ i ≤ d, the condition that F_{•} ∈ X_{w^{i}}(E^{i}) is equivalent to n^{2} rank conditions by definition (2.1). Each rank condition, can be checked via determinantal equations on matrices with entries among the n^{2} variables.

One could easily improve the naive computations in two ways:

1. Assume F_{•} ∈ X_{w^{1}}(E^{1}). Then one would need at most ( \begin{matrix}n \\ 2 \end{matrix} ) variables and only (d − 1)n^{2} additional rank conditions.

2. Second, some of the rank conditions in (2.1) are redundant. One only needs to check the conditions for pairs in Fulton’s essential set [Fulton, 1991]. Eriksson and Linusson [Eriksson and Linusson, 1995] have shown that the average size of the essential set is \frac{1}{36}n^{2}. However, this does not significantly reduce the number of rank equations on average or in the worst case. In our approach, the number of rank conditions grows like n^{d}, i.e.

polynomial in n for a fixed d but exponential in d. We have succeeded in solving many Schubert problems for n = 6 and d = 3 using this approach. There are Schubert problems for n = 8 and d = 3 for which our code in Maple cannot solve the associated system of equations. Computing the unique permutation array associated to a collection of permutations is relatively quick. In the next section we give an example with n = 15 and d = 3 which was calculated in just a few seconds. Examples with n = 25 and d = 3 take just over 1 minute.

The main advantage of our approach is that variables are only introduced as necessary. In order to minimize the number of variables, we recommend solving the equations in a particular order. First, it is useful to solve all equations pertaining to V_{i+1} before computing the initial form of the vectors in V_{i}. Second, we have found that proceeding through all x ∈ [n]^{d} such that ∑ x_{i} > (d − 1)n in lexicographic order works well, with the additional caveat that if P_{i}[x] = {x} then the matrix M with rows given by the vectors indexed by {x} ∪ (P_{i} ∩ P_{i+1}) must have rank at most i. Solve all of the determinantal equations implying the rank condition v.rk(V_{i}[x]) = rk(P_{i}[x]) simultaneously and substitute each solution back into the collection of vectors before considering the next rank condition. The second point is helpful because we solve all rank i equations before considering the rank i + 1 equations.

The following table gives the number of free variables necessary for solving all Schubert problems with n = 3, 4, 5 and d = 3. Row n and column i gives the number of Schubert problems for that n requiring i free variables.

0  1  2  3  4 5
n = 3  8  1  0  0  0 0
n = 4 176 23 11 1  0 0
n = 5 10639 910 585 457 135 0

For n = 6, all examples computed so far (over 10,000) require at most 5 free variables.

It is well known in that solving more equations with fewer variables is not necessarily an improvement. More experiments are required to characterize the “best” method of computing Schubert problems. We are limited in experimenting with this solution technique to what a symbolic programming language like Maple can do in a reasonable period of time. The examples in the next section will illustrate how this technique is useful in keeping both the number of variables and the complexity of the rank equations to a minimum.

6. The key example: triple intersections. We now implement the algorithm of the previous section in an important special case. Our goal is to describe a method for directly identifying all flags in X = X_{u}(E_{•}^{1}) ∩

X_{v}(E_{•}^{2}) ∩ X_{w}(E_{•}^{3}) when ℓ(u) + ℓ(v) + ℓ(w) = ( \begin{matrix}n \\ 2 \end{matrix} ) and E_{•}^{1}, E_{•}^{2}, and E_{•}^{3}

are in general position. This gives a method for computing the structure constants in the cohomology ring of the flag variety from equations (2.2) and (2.4) .

There are two parts to this algorithm. First, we use Algorithm 5.1 to find the unique permutation array P ⊂ [n]^{4} with position vector (u, v, w) such that P_{n} = T_{n,3}. Second, given P we use the equations in (5.10) to find all flags in X.

As a demonstration, we explicitly compute the flags in X in two cases. For convenience, we work over ℂ, but of course the algorithm is independent of the field. In the first there is just one solution which is relatively easy to see “by eye”. In the second case, there are two solutions, and the equations are more complicated. The algorithm has been implemented in Maple and works well on examples where n ≤ 8.

Example 1. Let u = (1, 3, 2, 4), v = (3, 2, 1, 4), w = (1, 3, 4, 2). The sum of their lengths is 1 + 3 + 2 = 6 = ( \begin{matrix}n \\ 2 \end{matrix} ). The unique permutation array P ∈ [4]^{4} determined by Algorithm 5.1 consists of the following dots:

(4421) (4142) (2442) (4233) (3243)
(3433) (4414) (4324) (3424) (3334)
(2434) (2344) (1444)

The EL-algorithm produces the following list of permutation arrays P_{1}, P_{2}, P_{3}, P_{4} in [4]^{3} corresponding to P:

\begin{aligned}& 2 & 4 4 2 & 4 4 3 4 3 2 & 4 4 3 4 3 2 4 3 2 1 \\ P_{1} & & P_{2} & P_{3} & P_{4} \end{aligned}

Notice that P_{4} is the transverse permutation array T_{4,3}. Notice also how to read u, v, and w from P_{1}, …, P_{4}: P_{i} has one less row than P_{i+1}; listing these excised rows from right to left yields u. Similarly, listing the excised columns from right to left yields v, and listing the excised numbers from right to left yields w (see the example immediately above).

We want to specify three transverse fixed flags E_{•}^{1}, E_{•}^{2}, E_{•}^{3}. It will be notationally convenient to represent a vector v = (v_{1}, …, v_{n}) by the polynomial v_{1} + v_{2}x + ⋯ + v_{n}x^{n−1}. We choose three flags, or equivalently three “transverse” ordered bases, as follows:

\begin{aligned}E_{•}^{1} & = & ⟨1, x, x^{2}, x^{3}⟩ \\ E_{•}^{2} & = & ⟨x^{3}, x^{2}, x, 1⟩ \\ E_{•}^{3} & = & ⟨(x + 1)^{3}, (x + 1)^{2}, (x + 1), 1⟩ \end{aligned}

We will show that the only flag in X_{u}(E_{•}^{1}) ∩ X_{v}(E_{•}^{2}) ∩ X_{w}(E_{•}^{3}) is

F_{•} = ⟨2 + 3x − x^{3}, x^{3}, x^{2}, 1⟩.  (6.1)

For each element (i, j, k) in P_{4}, we choose a vector in the corresponding 1-dimensional intersection E_{i}^{1} ∩ E_{j}^{2} ∩ E_{k}^{3} ∩ F_{4} and put it in position (i, j) in the matrix below:

V (E_{•}^{1}, E_{•}^{2}, E_{•}^{3}) = V_{4} = [ \begin{matrix}0 & 0 & 0 & 1 \\ 0 & 0 & x & x + 1 \\ 0 & x^{2} & x(x + 1) & (x + 1)^{2} \\ x^{3} & x^{2}(x + 1) & x(x + 1)^{2} & (x + 1)^{3} \end{matrix} ] .

In P_{3}, every element in the 4th column is covered by a subset in the antichain removed from P_{4}. This column adds only one degree of freedom so we establish V_{3} by adding only one variable in position (2, 4) and solving all other rank two equations in terms of this one:

V_{3} = [ \begin{matrix}0 & 0 & 0 & 0 \\ 0 & 0 & 0 & (1 + x) + cx \\ 0 & x^{2} & 0 & 1 + x + (1 + c)x(1 + x) \\ x^{3} & x^{2}(x + 1) & 0 & (x + 1)^{2} + cx(x + 1)^{2} \end{matrix} ] .

According to equation (5.8) the entry in position (4, 2) can have two indeterminates: b(1 + x) + cx, where b, c ≠ 0. As any two linearly dependent ordered pairs (b, c) yield the same configuration of subspaces, we may normalize b to 1.

Once V_{3} is determined, we find the vectors in V_{2}. In P_{2}, every element is contained in P_{3}, so V_{2} is a subset of V_{3}:

V_{2} = [ \begin{matrix}0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 + (2 + c)x \\ 0 & 0 & 0 & 0 \\ x^{3} & 0 & 0 & (x + 1)^{2} + cx(x + 1)^{2} \end{matrix} ] .

The rank of P_{2} is 2, so all 3 × 3 minors of the following matrix must be zero:

( \begin{matrix}0 & 0 & 0 & 1 \\ 1 & 2 + c & 0 & 0 \\ 1 & 2 + c & 1 + 2c & c \end{matrix} ) .

In particular, 1 + 2c = 0, so the only solution is c = −\frac{1}{2}. Substituting for c, we have

V_{2}^{S} = [ \begin{matrix}0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 + \frac{3}{2}x \\ 0 & 0 & 0 & 0 \\ x^{3} & 0 & 0 & (x + 1)^{2} − \frac{1}{2}x(x + 1)^{2} \end{matrix} ] .

Finally P_{1} is contained in P_{2}, so V_{1}^{S} contains just the vector

v_{(4,4,2)}^{1} = v_{(4,4,2)}^{2} = (x + 1)^{2} − \frac{1}{2}x(x + 1)^{2} = \frac{1}{2}(2 + 3x − x^{3}).

Therefore, there is just one solution, namely the flag spanned by the collections of vectors V_{1}^{S}, V_{2}^{S}, V_{3}^{S}, V_{4}^{S} which is equivalent to the flag in (6.1).

If we choose an arbitrary general collection of three flags, we can always change bases so that we have the following situation:

\begin{aligned}E_{•}^{1} & = & ⟨1, x, x^{2}, x^{3}⟩ \\ E_{•}^{2} & = & ⟨x^{3}, x^{2}, x, 1⟩ \\ E_{•}^{3} & = & ⟨a_{1} + a_{2}x + a_{3}x^{2} + x^{3}, b_{1} + b_{2}x + x^{2}, c_{1} + x, 1⟩. \end{aligned}

Using these coordinates, the same procedure as above will produce the unique solution

F_{•} = ⟨(a_{1} − a_{3}b_{1}) + (a_{2} − b_{2}a_{3})x − x^{3}, x^{3}, x^{2}, 1⟩.

Example 2. This example is of a Schubert problem with multiple solutions. Let u = (1, 3, 2, 5, 4, 6), v = (3, 5, 1, 2, 4, 6), w = (3, 1, 6, 5, 4, 2). If P is the unique permutation array in [6]^{4} determined by Algorithm 5.1 for u, v, w then the EL-algorithm produces the following list of permutation arrays P_{1}, …, P_{6} in [6]^{3} corresponding to P:

2  4 4 2  4 5 5 4 2

26 SARA BILLEY AND RAVI VAKIL

6 6 4 6 5 6 5 4 2  6 6 5 6 5 4 6 5 4 2 6 5 4 2 1  6 6 5 6 5 4 6 5 4 3 6 5 4 3 2 6 5 4 3 2 1

We take the following triple of fixed flags:

\begin{aligned}E_{•}^{1} & = & ⟨1, x, …, x^{5}⟩ \\ E_{•}^{2} & = & ⟨x^{5}, …, x, 1⟩ \\ E_{•}^{3} & = & ⟨(1 + x)^{5}, (1 + x)^{4}, …, 1⟩ \end{aligned}

The third flag is clearly not chosen generally but leads to two solutions to this Schubert problem which is the generic number of solutions. We prefer to work with explicit but simple numbers here to demonstrate the computation without making the formulas too complicated.

The vector table associated to P_{6} is easily determined by Pascal’s formula:

[ \begin{matrix}[] & [] & [] & [] & [] & [1, 0, 0, 0, 0, 0] \\ [] & [] & [] & [] & [0, 1, 0, 0, 0, 0] & [1, 1, 0, 0, 0, 0] \\ [] & [] & [] & [0, 0, 1, 0, 0, 0] & [0, 1, 1, 0, 0, 0] & [1, 2, 1, 0, 0, 0] \\ [] & [] & [0, 0, 0, 1, 0, 0] & [0, 0, 1, 1, 0, 0] & [0, 1, 2, 1, 0, 0] & [1, 3, 3, 1, 0, 0] \\ [] & [0, 0, 0, 0, 1, 0] & [0, 0, 0, 1, 1, 0] & [0, 0, 1, 2, 1, 0] & [0, 1, 3, 3, 1, 0] & [1, 4, 6, 4, 1, 0] \\ [0, 0, 0, 0, 0, 1] & [0, 0, 0, 0, 1, 1] & [0, 0, 0, 1, 2, 1] & [0, 0, 1, 3, 3, 1] & [0, 1, 4, 6, 4, 1] & [1, 5, 10, \\ & & & & & 10, 5, 1] \end{matrix} ]

The vector table associated to P_{5} has one degree of freedom. The vector in position (3, 5) is freely chosen to be x + c x^{2}. Then for all other points in P_{5} \ P_{6} we can solve a rank 2 equation which determines the corresponding vector in terms of c. Therefore, V_{5} becomes

[ \begin{matrix}[] & [] & [] & [] & [] & [] \\ [] & [] & [] & [] & [] & [1, \frac{10(c−1)}{3c} , 0, 0, 0, 0] \\ [] & [] & [] & [] & [0, 1, c, 0, 0, 0] & [1, \frac{−13+10 c}{3(c−1)} , \frac{−10+7 c}{3(c−1)} \\ & & & & & 0, 0, 0] \\ [] & [] & [] & [0, 0, 1, & [0, 1, \frac{−4+7 c}{2+c} , & [1, 6 \frac{−5+3 c}{−8+5 c} , \frac{3(−12+7 c)}{−8+5 c} , \\ & & & \frac{−6}{c−4} , 0, 0] & \frac{6(c−1)}{2+c} , 0, 0] & \frac{2(−7+4 c)}{−8+5 c} , 0, 0] \\ [] & x4 & [] & [0, 0, 1, \frac{−6}{c−4} , & [0, 1, \frac{3(−4+3 c)}{2(c−1)} , & [1, 4, 6, 4, 1, 0] \\ & & & \frac{−2−c}{c−4} , 0] & \frac{3(−3+2 c)}{c−1} , \frac{−8+5 c}{2(c−1)} , 0] \\ x5 & x4 + x5 & [] & [0, 0, 1, \frac{−6}{c−4} , & [0, 1, 4, 6, 4, 1] & [1, 5, 10, 10, 5, 1] \\ & & & \frac{−3c}{c−4} , \frac{2(1−c)}{c−4} ] \end{matrix} ]

Every vector in V_{4} appears in V_{5}, but now some of them are subject to new rank conditions:

[ \begin{matrix}[] & [] & [] & [] & [] & [] \\ [] & [] & [] & [] & [] & [1, \frac{10(c−1)}{3c} , 0, 0, 0, 0] \\ [] & [] & [] & [] & [] & [] \\ [] & [] & [] & [0, 0, 1, \frac{−6}{c−4} , 0, 0] & [] & [1, \frac{6(−5+3 c)}{−8+5 c} , \frac{3(−12+7 c)}{−8+5 c} , \\ & & & & & \frac{2(−7+4 c)}{−8+5 c} , 0, 0] \\ [] & x4 & [] & [0, 0, 1, \frac{−6}{c−4} , − \frac{2+c}{c−4} , 0] & [] & [] \\ x5 & x4 + x5 & [] & [0, 0, 1, \frac{−6}{c−4} , \frac{−3c}{c−4} , \frac{−2c+2}{c−4} ] & [] & [1, 4 + d, 6 + 4d, 4 + 6d, 1 + 4d, d] \end{matrix} ] .

In particular, the top 3 vectors should span a two-dimensional subspace. This happens if the following matrix has rank 2:

[ \begin{matrix}1 & \frac{10(c−1)}{3c} & 0 & 0 & 0 & 0 \\ 1 & \frac{6(−5+3 c)}{−8+5 c} & \frac{3(−12+7 c)}{−8+5 c} & \frac{2(−7+4 c)}{−8+5 c} & 0 & 0 \\ 0 & 0 & 1 & \frac{−6}{c−4} & 0 & 0 \end{matrix} ]

or equivalently if the following nontrivial minors of the matrix are zero

[\frac{4(10 c + c^{2} − 20)}{3c (−8 + 5 c)}, \frac{−8(10 c + c^{2} − 20)}{(−8 + 5 c) (c − 4) c}, \frac{−8(10 c + c^{2} − 20)}{(−8 + 5 c) (c − 4)},

\frac{−8 (c − 1) (10 c + c^{2} − 20)}{3 (−8 + 5 c) (c − 4) c}].

All rank 3 minors will be zero if c^{2} + 10 c − 20 = 0, or c = −5 ± 3 \sqrt{5}. Plugging each solution for c into the vectors gives the two solutions V_{4}^{S_{1}} and V_{4}^{S_{2}}. For example, using c = −5 + 3 \sqrt{5} and solving a single rank 2 equation involving d gives:

[ \begin{matrix}[] & [] & [] & [] & [] & [] \\ [] & [] & [] & [] & [] & [1, 10 \frac{2+\sqrt{5}}{5+3 \sqrt{5}} , 0, 0, 0, 0] \\ [] & [] & [] & [] & [] & [] \\ [] & [] & [] & [0, 0, 1, \frac{2}{(3+\sqrt{5})} , 0, 0] & [] & [1, 2 \frac{20+9 \sqrt{5}}{11+5 \sqrt{5}} , \frac{47+21 \sqrt{5}}{11+5 \sqrt{5}} , \\ & & & & & 2 \frac{9+4 \sqrt{5}}{11+5 \sqrt{5}} , 0, 0] \\ [] & x4 & [] & [0, 0, 1, \frac{2}{(3+\sqrt{5})} , − \frac{1+\sqrt{5}}{3+\sqrt{5}} , 0] & [] & [] \\ x5 & x4 + x5 & [] & [0, 0, 1, \frac{2}{(3+\sqrt{5})} , − \frac{5+3 \sqrt{5}}{3+\sqrt{5}} , \frac{−2(2+\sqrt{5})}{3+\sqrt{5}} ] & [] & [1, \frac{5+\sqrt{5}}{2} , 2 \sqrt{5}, −5 + 3 \sqrt{5}, \\ & & & & & −5 + 2 \sqrt{5}, \frac{−3+\sqrt{5}}{2} ] \end{matrix} ]

The remaining vectors in V_{1}^{S_{1}}, V_{2}^{S_{1}}, V_{3}^{S_{1}} will be a subset of V_{4}^{S_{1}} so no further equations need to be solved, and similarly for V_{4}^{S_{2}}.

7. Monodromy and Galois groups. The monodromy group of a problem in enumerative geometry captures information reflecting three aspects of algebraic geometry: geometry, algebra, and arithmetic. Informally, it is the symmetry group of the set of solutions. Three more precise interpretations are given below. Historically, these groups were studied since the nineteenth century [Jordan, 1870, Dickson et al., 1916, Weber, 1941]; modern interest probably dates from a letter from Serre to Kleiman in the seventies (see the historical discussion in the survey article [Kleiman, 1987, p. 325]). Their modern foundations were laid by Harris [Harris, 1979]; among other things, he showed that the monodromy group of a problem is equivalent to the Galois group of the equations defining it.

These groups are difficult to compute in general, and indeed they are known for relatively few enumerative problems. In this section, we use the computation of explicit algebraic solutions to Schubert problems (along with a criterion from [Vakil, 2006b]) to give a method to compute many such groups explicitly (when they are “full”, or as large as possible), and to give an experimental method to compute groups in other cases.

It is most interesting to exhibit cases where the Galois/monodromy group is unexpectedly small. Indeed, Harris writes of his calculations:

the results represent an affirmation of one understanding of the geometry underlying each of these problems, in the following sense: in every case dealt with here, the actual structure on the set of solutions of the enumerative problem as determined by the Galois group of the problems, is readily described in terms of standard algebrao-geometric constructions. In particular, in every case in which current theory had failed to discern any intrinsic structure on the set of solutions — it is proved here — there is in fact none. [Harris, 1979, p. 687-8]

We exhibit an example of a Schubert problem whose Galois/monodromy group experimentally appears to be smaller than expected — it is the dihedral group D_{4} ⊂ S_{4}. This is the first example in which current theory fails to discern intrinsic structure. Examples of “small” Galois groups were given in [Vakil, 2006b, Sect. 5]; but there an explanation had already been given by Derksen. Here, however, we have a mystery: We do not understand geometrically why the group is D_{4}. (However, see the end of this section for a conjectural answer.)

We now describe the three interpretations of the Galois/monodromy group for a Schubert problem. The definition for a general problem in enumerative geometry is the obvious generalization; see [Harris, 1979] for a precise definition, and for the equivalence of (A) and (B). See [Vakil, 2006b, Sect. 2.9] for more discussion.

(A) Geometry. Begin with m general flags; suppose there are N solutions to the Schubert problem (i.e. there are N flags meeting our m given flags in the specified manner). Move the m flags around in such a way that no two of the solutions ever come together, returning the m flags to their starting positions, and follow the N solutions. The N solutions are returned to their initial positions as a set, but the individual N solutions may be permuted. What are the possible permutations? (See the applet

http://lamar.colostate.edu/~jachter/mono.html for an illustration of

this concept.)

(B) Algebra. The m flags are parameterized by Fl_{n}^{m}. Define the “solution space” to be the subvariety of Fl_{n} ×Fl_{n}^{m} mapping to Fl_{n}^{m}, corresponding to those flags satisfying the given Schubert conditions. There is one irreducible component X of the solution space mapping dominantly to Fl_{n}^{m}; the morphism has generic degree N. The Galois/monodromy group is the Galois group of the Galois closure of the corresponding extension of function fields. The irreducibility of X implies that the Galois group G is a transitive subgroup of S_{N}.

(C) Arithmetic. If the m flags are defined over ℚ, then the smallest field of definition of a solution must have Galois group that is a subgroup of the Galois/monodromy group G. Moreover, for a randomly chosen set of m flags, the field of definition will have Galois group precisely G with positive probability (depending on the particular problem). The equivalence of this version with the previous two follows from (B) by the Hilbert irreducibility theorem, as Fl_{n}^{m} is rational ([Lang, 1983, Sect. 9.2], see also [Serre, 1989, Sect. 1.5] and [Cohen, 1981]). We are grateful to M. Nakamaye for discussions on this topic.

Given any enumerative problem with N solutions, we see that the Galois/ monodromy group is a subgroup of S_{N}; it is well-defined up to conjugacy in S_{N}. As the solution set should be expected to be as symmetric as possible, one should expect it to be as large as possible; it should be S_{N} unless the set of solutions has some additional geometric structure.

For example, in [Harris, 1979], Harris computed several Galois/ monodromy groups, and in each case they were the full symmetric group, unless there was a previously known geometric reason why the group was smaller. The incidence relations of the 27 lines on a smooth cubic surface prevent the corresponding group from being two-transitive. There exist two of the 27 lines that intersect, and there exist another two that do not. These incidence relations can be used to show that the Galois/monodromy group must be contained in the reflection group W (E_{6}) ⊂ S_{27}, e.g. [Manin, 1974, Sects. 25, 26] or [Hartshorne, 1977, Prob. V.4.11]; Harris shows that equality holds [Harris, 1979, III.3].

Other examples can be computed based on permutation arrays.

Corollary 7.1. The explicit equations defining a Schubert problem in Theorem 5.2 can be used to determine the Galois/monodromy group for the problem as well.

As a toy example, we see that the monodromy group for Example 2 is S_{2}, as there are two solutions to the Schubert problem, and the only transitive subgroup of S_{2} is S_{2} itself. Algebraically, this corresponds to the fact that the roots of the irreducible quadratic c^{2} + 10c − 20 in example 2 generate a Galois extension of ℚ with Galois group S_{2}.

Unfortunately, the calculations of monodromy groups for flag varieties becomes computationally infeasible as n → 10 where the number of solutions becomes larger. Therefore, we have considered related problems of computing Schubert problems for the Grassmannian manifolds G(k, n). Here, G(k, n) is the set of k-dimensional planes in ℂ^{n}. Schubert varieties are defined analogously by rank conditions with respect to a fixed flag. These varieties are indexed by partitions λ = (λ_{1}, …, λ_{k}) where λ_{1} ≥ ⋯ ≥ λ_{k} ≥ 0. The permutation arrays work equally well for keeping track of the rank conditions for intersecting Schubert varieties in the Grassmannian if we replace the condition that a permutation array must have rank n by requiring rank k.

In the case of the Grassmannian, combinatorial criteria were given for the Galois/monodromy group of a Schubert problem to be A_{N} or S_{N} in [Vakil, 2006b]. Intersections on the Grassmannian manifold may be interpreted as a special case of intersections on the flag manifold, so our computational techniques apply. We sketch the criteria here, and refer the reader to [Vakil, 2006b] for explicit descriptions and demonstrations.

Criterion 7.1. Schubert Induction. Given a Schubert problem in the Grassmannian manifold, a choice of geometric degenerations yields a directed rooted tree. The edges are directed away from the root. Each vertex has out-degree between 0 and 2. The portion of the tree connected to an outward-edge of a vertex is called a branch of that vertex. Let N be the number of leaves in the tree.

(i) Suppose each vertex with out-degree two satisfies either (a) there are a different number of leaves on the two branches, or (b) there is one leaf on each branch. Then the Galois/monodromy group of the Schubert problem is A_{N} or S_{N}.

(ii) Suppose each vertex with out-degree two has a branch with one leaf. Then the Galois/monodromy group of the Schubert problem is S_{N}.

(iii) Suppose that each vertex with out-degree two satisfies (a) or (b) above, or (c) there are m ≠ 6 leaves on each branch, and it is known that the corresponding Galois/monodromy group is two-transitive. Then the Galois/monodromy group is A_{N} or S_{N}.

Part (i) is [Vakil, 2006b, Thm. 5.2], (ii) follows from the proof of [Vakil, 2006b, Thm. 5.2], and (iii) is [Vakil, 2006b, Thm. 5.10]. Criterion (i) seems to apply “almost always”. Criterion (ii) applies rarely. Criterion (iii) requires additional information and is useful only in ad hoc circumstances.

The method discussed in this paper of explicitly (algebraically) solving Schubert problems gives two new means of computing Galois groups. The first, in combination with the Schubert induction rule, is a straightforward means of proving that a Galois group is the full symmetric group. The second gives strong experimental evidence (but no proof!) that a Galois group is smaller than expected.

Criterion 7.2. Criterion for Galois/monodromy group to be full. If m flags defined over ℚ are exhibited such that the solutions are described in terms of the roots of an irreducible degree N polynomial p(x), and this polynomial has a discriminant that is not a square, then by the arithmetic interpretation (C) above, the Galois/monodromy group is not contained in A_{N}.

Hence in combination with the Schubert induction criterion (i), this gives a criterion for a Galois/monodromy group to be the full symmetric group S_{N}.

(In principle one could omit the Schubert induction criterion: if one could exhibit a single Schubert problem defined over ℚ whose Galois group was S_{N}, then the Galois/monodromy group would have to be S_{N} as well. However, showing that a given degree N polynomial has Galois group S_{N} is difficult; our discriminant criterion is immediate to apply.)

The smallest Schubert problem where Criterion 7.1(i) applies but Criterion 7.1(ii) does not is the intersection of six copies of the Schubert variety indexed by the partition (1) in G(2, 5) (and the dual problem in G(3, 5)). Geometrically, it asks how many lines in ℙ^{4} meet six planes. When the planes are chosen generally, there are five solutions (i.e. five lines). By satisfying the first criterion we know the Galois/monodromy group is “at least alternating” i.e. either A_{N} or S_{N}, but we don’t know that the group is S_{N}. We randomly chose six planes defined over ℚ. Maple found the five solutions, which were in terms of the solutions of the quintic 101z^{5} − 554z^{4} + 887z^{3} − 536z^{2} + 194z − 32. This quintic has nonsquare discriminant, so we conclude that the Galois/monodromy group is S_{5}. As other examples, the Schubert problem (2)^{2}(1)^{4} in G(2, 6) has full Galois/monodromy group S_{6}, the Schubert problem (2)(1)^{6} in G(2, 6) has full Galois/monodromy group S_{9}, and the Schubert problem (2, 2)(1)^{5} in G(3, 6) has full Galois/monodromy group S_{6}. We applied this to many Schubert problems and found no examples satisfying Criterion 7.1(i) or (iii) that did not have full Galois group S_{N}.

As an example of the limits of this method, solving the Schubert problem (1)^{8} in G(2, 6) is not computationally feasible (it has 14 solutions), so this is the smallest Schubert problem whose Galois/monodromy group is unknown (although Criterion 7.1(i) applies, so the group is A_{14} or S_{14}).

Criterion 7.3. Probabilistic evidence for smaller Galois or monodromy groups. If for a fixed Schubert problem, a large number of “random” choices of flags in ℚ^{n} always yield Galois groups contained in a proper subgroup G ⊂ S_{N}, and the group G is achieved for some choice of Schubert conditions, this gives strong evidence that the Galois/monodromy group is G.

This is of course not a proof — we could be very unlucky in our “random” choices of conditions — but it leaves little doubt.

As an example, consider the Schubert problem (2, 1, 1)(3, 1)(2, 2)^{2} in G(4, 8). There are four solutions to this Schubert problem. When random (rational) choices of the four conditions are taken, Maple always (experimentally!) yields a solution in terms of \sqrt{a + b\sqrt{c}} where a, b, and c are rational. The Galois group of any such algebraic number is contained in D_{4}: it is contained in S_{4} as \sqrt{a + b\sqrt{c}} has at most 4 Galois conjugates, and the Galois closure may be obtained by a tower of quadratic extensions over ℚ. Thus the Galois group is a 2-subgroup of S_{4} and hence contained in a 2-Sylow subgroup D_{4}.

We found a specific choice of Schubert conditions for which the Galois group of the Galois closure K of ℚ(\sqrt{a + b\sqrt{c}}) over ℚ was D_{4}. (The numbers a, b, and c are large and hence not included here; the Galois group computation is routine.) Thus we have rigorously shown that the Galois group is at least D_{4}, hence D_{4} or S_{4}. We have strong experimental evidence that the group is D_{4}.

Challenge: Prove that the Galois group of this Schubert problem is D_{4}.

We conjecture that the geometry behind this example is as follows. Given four general conditions, the four solutions may be labeled V_{1}, …, V_{4} so that either (i) dim(V_{i} ∩V_{j}) = 0 if i ≡ j (mod 2) and dim(V_{i} ∩V_{j}) = 2 otherwise, or (ii) dim(V_{i} ∩ V_{j}) = 2 if i ≡ j (mod 2) and dim(V_{i} ∩ V_{j}) = 0 otherwise. If (i) or (ii) holds then necessarily G ≠ S_{4}, implying G ≅ D_{4}.

This example (along with the examples of [Vakil, 2006b, Sect. 5.12]) naturally leads to the following question. Suppose V_{1}, …, V_{N} are the solutions to a Schubert problem (with generally chosen conditions). Construct a rank table

{dim (⋂_{i∈I} V_{i})}_{I⊂{1,...,n}} .

In each known example, the Galois/monodromy group is precisely the group of permutations of {1, …, n} preserving the rank table.

Question: Is this always true? Remark. Schubert problems for the Grassmannian varieties were among the first examples where the Galois/monodromy groups may be smaller than expected. The first example is due to H. Derksen; the “hidden geometry” behind the smaller Galois group is clearer from the point of view of quiver theory. Derksen’s example, and other infinite families of examples, are given in [Vakil, 2006b, Sect. 5.13–5.15].

8. Acknowledgments. We want to thank Federico Ardila for pointing out a subtle error in an earlier draft of the paper. We would also like to thank Eric Babson, Mike Nakamaye, and Frank Sottile for helpful discussions. Along the way, we have done a lot of experimentation on computers using both free and for-profit software including Allegro Common Lisp and Maple.

REFERENCES

[Ardila and Billey, 2006] F. Ardila and S. Billey, Flag arrangements and triangula-

tions of products of simplices, to appear in Advances in Math.

[Cohen, 1981] S. D. Cohen, The distribution of Galois groups and Hilbert’s irreducibil-

ity theorem, Proc. London Math. Soc. (3) 43 (1981), no. 2, 227–250.

[Coskun] I. Coskun, A Littlewood-Richarson rule for the two-step flag varieties, preprint, 2004.

[Coskun and Vakil] I.Coskun and R.Vakil, Geometric positivity in the cohomology of homogeneous spaces and generalized Schubert calculus, arXiv:math.AG/0610538.

[Coxeter and Greitzer, 1967] H. S. M. Coxeter and S. L. Greitzer, Geometry Revis-

ited, Math. Ass. of Amer., New Haven, 1967.

[Dickson et al., 1916] L. Dickson, H. F. Blichfeldt, and G. A. Miller, Theory and

applications of finite groups, John Wiley, New York, 1916.

[Eisenbud and Saltman, 1987] David Eisenbud and David Saltman, Rank varieties of matrices, Commutative algebra (Berkeley, CA, 1987), 173–212, Math. Sci. Res. Inst. Publ. 15, Springer, New York, 1989.

[Eriksson and Linusson, 1995] K. Eriksson and S. Linusson, The size of Fulton’s essential set, Sém. Lothar. Combin., 34 (1995), pp. Art. B34l, approx. 19 pp. (electronic).

[Eriksson and Linusson, 2000a] K. Eriksson and S. Linusson, A combinatorial theory of higher-dimensional permutation array, Adv. in Appl. Math. 25 (2000), no. 2, 194–211.

[Eriksson and Linusson, 2000b] K. Eriksson and S. Linusson, A decomposition of Fl(n)^{d} indexed by permutation arrays., Adv. in Appl. Math. 25 (2000), no. 2, 212–227.

[Fulton, 1991] W. Fulton, Flags, Schubert polynomials, degeneracy loci, and determi-

nantal formulas, Duke Math. J., 65 (1991), pp. 381–420.

[Fulton, 1997] W. Fulton, Young tableaux, with Applications to Representation Theory and Geometry, London Math. Soc. Student Texts 35, Cambridge U. P., Cambridge, 1997.

[Gonciulea and V. Lakshmibai, 2001] N. Gonciulea and V. Lakshmibai, Flag vari-

eties, Hermann-Actualities Mathématiques, 2001.

[Harris, 1979] J. Harris, Galois groups of enumerative problems, Duke Math. J. 46

(1979), no. 4, 685–724.

[Hartshorne, 1977] R. Hartshorne, Algebraic Geometry, GTM 52, Springer-Verlag,

New York-Heidelberg, 1977.

[Jordan, 1870] C. Jordan, Traité des Substitutions, Gauthier-Villars, Paris, 1870. [Kleiman, 1987] S. Kleiman, Intersection theory and enumerative geometry: a decade

in review, in Algebraic geometry, Bowdoin, 1985, Proc. Sympos. Pure Math., 46, Part 2, 321–370, Amer. Math. Soc., Providence, RI, 1987.

[Knutson, 2001] A. Knutson,Descent-cycling in Schubert calculus, Experiment. Math.,

10,(2001), no. 3, 345–353.

[Knutson and Tao, 2001] A.Knutson and T.Tao, Honeycombs and sums of Hermitian

matrices, Notices Amer. Math. Soc., 48 (2001), 175–186.

[Kumar, 2002] S. Kumar, Kac-Moody Groups, Their Flag Varieties and Representation

Theory, Progress in Math. 204, Birkhäuser, Boston, 2002.

[Lang, 1983] S. Lang, Fundamentals of Diophantine Geometry, Springer-Verlag, New

York, 1983.

[Lascoux and Schützenberger, 1982] Lascoux, A. and M.-P. Schützenberger, Polynômes de Schubert, C. R. Acad. Sci. Paris Sér. I Math. 294 (1982), no.

13, 447–450.

[Macdonald, 1991] I. G. Macdonald, Notes on Schubert Polynomials, Publ. du LACIM

vol. 6, Université du Québec à Montréal, Montreal, 1991.

[Magyar, 2005] Peter Magyar, Bruhat order for two flags and a Line, Journal of Al-

gebraic Combinatorics, 21, (2005).

[Magyar and van der Kallen, 1999] Peter Magyar and Wilberd van der Kallen, The Space of triangles, vanishing theorems, and combinatorics, Journal of Algebra, 222, (1999), 17-50.

[Manin, 1974] Yu. Manin, Cubic forms: Algebra, Geometry, Arithmetic, North-

Holland, Amsterdam, 1974.

[Manivel, 1998] L. Manivel, Symmetric Functions, Schubert Polynomials and Degeneracy Loci, J. Swallow trans. SMF/AMS Texts and Monographs, vol. 6, AMS, Providence RI, 2001.

[Mnëv, 1985] N. Mnëv, Varieties of combinatorial types of projective configurations and

convex polyhedra, Dolk. Akad. Nauk SSSR, 283 (6) (1985), 1312–1314.

[Mnëv, 1988] N. Mnëv, The universality theorems on the classification problem of configuration varieties and convex polytopes varieties, in Topology and geometry — Rohlin seminar, Lect. Notes in Math. 1346, Springer-Verlag, Berlin, 1988, 527–543.

[Purbhoo, 2006] K. Purbhoo, Vanishing and nonvanishing criteria in Schubert calculus,

International Math. Res. Not., Art. ID 24590 (2006), pp.1–38.

[Serre, 1989] J.-P. Serre, Lectures on the Mordell-Weil theorem, M. Waldschmidt

trans. F. Viehweg, Braunschweig, 1989.

[Shapiro et al., 1997] B. Shapiro, M. Shapiro, and A. Vainshtein, On combinatorics and topology of pairwise intersections of Schubert cells in SL_{n}/B, in The Arnol’d-Gelfand Mathematical Seminars, 397–437, Birkhäuser, Boston, 1997.

[Vakil, 2006a] R. Vakil, A geometric Littlewood-Richardson rule, with an appendix

joint with A. Knutson, Ann. of Math. (2) 164 (2006), no. 2, 371–421.

[Vakil, 2006b] R. Vakil, Schubert induction, Ann. of Math. (2) 164 (2006), no. 2, 489–

512.

[Vakil, 2006c] R. Vakil, Murphy’s Law in algebraic geometry: Badly-behaved deforma-

tion spaces, Invent. Math. 164 (2006), no. 3, 569–590.

[Weber, 1941] H. Weber, Lehrbuch der Algebra, Chelsea Publ. Co., New York, 1941.