SCHUBERT INDUCTION

RAVI VAKIL

Abstract. We describe a Schubert induction theorem, a tool for analyzing intersections on a Grassmannian over an arbitrary base ring. The key ingredient in the proof is the Geometric Littlewood-Richardson rule of [V2].

As applications, we show that all Schubert problems for all Grassmannians are enumerative over the real numbers, and sufficiently large finite fields. We prove a generic smoothness theorem as a substitute for the Kleiman-Bertini theorem in positive characteristic. We compute the monodromy groups of many Schubert problems, and give some surprising examples where the monodromy group is much smaller than the full symmetric group.

Contents

1. Questions and answers 1 2. The main theorem, and its proof 6 3. Galois/monodromy groups of Schubert problems 11 References 21

The main theorem of this paper (Theorem 2.5) is an inductive method (“Schubert induction”) of proving results about intersections of Schubert varieties in the Grassmannian. In Section 1 we describe the questions we wish to address. The main theorem is stated and proved in Section 2, and applications are given there and in Section 3.

1. Questions and answers

Fix a Grassmannian G(k, n) = 𝔾(k − 1, n − 1) over a base field (or ring) K. Given a partition α, the condition of requiring a k-plane V to satisfy dim V ∩ F_{n−α_{i}+i} ≥ i with respect to a flag F_{·} is called a Schubert condition. The variety of k-planes satisfying a Schubert condition with respect to a flag F_{·} is the Schubert variety Ω_{α}(F_{·}). Let Ω_{α} ∈ A^{∗}(G(k, n)) denote the corresponding Schubert class. Let Ω Ω Ω_{α}(F_{·}) ⊂ G(k, n) × F l(n) be the “universal Schubert variety”.

Date: Saturday, April 12, 2003. Revised version: Thursday, February 17, 2005. 1991 Mathematics Subject Classification. Primary 14M15, 14N15; Secondary 14N10, 14C17, 14P99, 14Q10,

14G15, 14G27.

Partially supported by NSF Grant DMS–0228011, an AMS Centennial Fellowship, and an Alfred P. Sloan Research Fellowship.

A Schubert problem is the following: Given m Schubert conditions Ω_{α_{i}}(F_{·}^{i}) with respect to fixed general flags F_{·}^{i} (1 ≤ i ≤ m) whose total codimension is dim G(k, n), what is the cardinality of their intersection? In other words, how many k-planes satisfy various linear algebraic conditions with respect to m general flags? This is the natural generalization of the classical problem: how many lines in ℙ^{3} meet four fixed general lines? The points of intersection are called the solutions of the Schubert problem. We say that the number of solutions is the answer to the Schubert problem. An immediate if imprecise follow-up is: What can one say about the solutions?

For example, if K = ℂ, the answer to the Schubert problems for m = 3 are precisely the Littlewood-Richardson coefficients c_{αβ}^{γ}.

Let π_{i} : G(k, n) × F l(n)^{m} → G(k, n) × F l(n) (1 ≤ i ≤ m) denote the projection, where the projection to F l(n) is from the ith F l(n) of the domain. We will make repeated use of the following diagram.

(1)  \xymatrix{π_{1}^{∗}Ω Ω Ω_{α_{1}}(F_{·}^{1}) ∩ π_{2}^{∗}Ω Ω Ω_{α_{2}}(F_{·}^{2}) ∩ ⋯ ∩ π_{m}^{∗}Ω Ω Ω_{α_{m}}(F_{·}^{m}) \ar[d]^{S} \ar[r] \ar@{^{(}->}[r] & G(k, n) × F l(n)^{m} \\ F l(n)^{m}}

Then a Schubert problem asks: what is the cardinality of S^{−1}(F_{·}^{1}, …, F_{·}^{m}) for general (F_{·}^{1}, …, F_{·}^{m}) ∈ F l(n)^{m}?

Suppose the base field is K, and α_{1}, …, α_{m} are given such that dim (Ω_{α_{1}} ∪ ⋯ ∪ Ω_{α_{m}}) =

0. The corresponding Schubert problem is said to be enumerative over K if there are m flags F_{·}^{1}, …, F_{·}^{m} defined over K such that S^{−1}(F_{·}^{1}, …, F_{·}^{m}) consists of deg (Ω_{α_{1}} ∪ ⋯ ∪ Ω_{α_{m}}) (distinct) K-points.

1.1. The answer to this problem over ℂ is the prototype of the program in enumerative geometry. By the Kleiman-Bertini theorem [Kl1], the Schubert conditions intersect transversely, i.e. at a finite number of reduced points. Hence the problem is reduced to one about the intersection theory of the Grassmannian. The intersection ring (the Schubert calculus) is known, using other interpretations of the Littlewood-Richardson coefficients in combinatorics or representation theory.

Yet many natural questions remain:

1.2. Reality questions. The classical “reality question” for Schubert problems [F1, p. 55], [F2, Ch. 13], [FP, Sect. 9.8] is:

Question 1. Are all Schubert problems enumerative over ℝ?

See [S1, S6] for this problem’s history. For G(1, n) and G(n − 1, n) the question can be answered positively using linear algebra. Sottile proved the result for G(2, n) (and G(n − 2, n)) for all n, [S2], and for all problems involving only Pieri classes [S5]; see [S3] for further discussion. The case G(2, n), in the guise of lines in projective space, as well as the analogous problem for conics in projective space, also follows from [V1].

This question can be fully answered with Schubert induction.

1.3. Proposition. — All Schubert problems for all Grassmannians are enumerative over ℝ. Moreover, for a fixed m, there is a set of m flags that works for all choices of α_{1}, …, α_{m}.

Our argument actually shows that the conclusion of Proposition 1.3 holds for any field satisfying the implicit function theorem, such as ℚ_{p}.

As noted in [V2, Sect. 3.8(f)], Eisenbud’s suggestion that the deformations of the Geometric Littlewood-Richardson rule are a degeneration of that arising from the osculating flag to a rational normal curve, along with this proposition, would imply that the Shapiro-Shapiro conjecture is true asymptotically. (See [EG] for the proof in the case k = 2.)

1.4. Enumerative geometry in positive characteristic. Enumerative geometry in positive characteristic is almost a stillborn field, because of the failure of the Kleiman-Bertini theorem. (Examples of the limits of our understanding are plane conics and cubics in characteristic 2 [Vn, Ber].) In particular, the Kleiman-Bertini Theorem fails in positive characteristic for all G(k, n) that are not projective spaces (i.e. 1 < k < n−1) — Kleiman’s counterexample [Kl1, ex. 9] for G(2, 4) easily generalizes. Although D. Laksov and R. Speiser have developed a sophisticated characteristic-free theory of transversality [L, Sp, LSp1, LSp2], it does not apply in this case [S7, Sect. 5].

Question 2. Are Schubert problems enumerative over an algebraically closed field of positive characteristic?

We answer this question by giving a good enough answer to a logically prior one:

Question 3. Is there any patch to the failure of the Kleiman-Bertini theorem on Grassmannians?

A related natural question is:

Question 4. Are Schubert problems enumerative over finite fields?

We now answer all three questions. The appropriate replacement of Kleiman-Bertini is the following. We say a morphism f : X → Y is generically smooth if there is a dense open set V of Y and a dense open set U of f^{−1}(V) such that f is smooth on U. If X and Y are varieties and f is dominant, this is equivalent to the condition that the function field of X is separably generated over the function field of Y.

1.5. Generic smoothness theorem. — The morphism S is generically smooth. More generally, if Q ⊂ G(k, n) is a subvariety such that (Q × F l(n)) ∩ Ω Ω Ω_{α}(F_{·}) → F l(n) is generically smooth for all α, then

\xymatrix{(Q × F l(n)^{m}) ∩ π_{1}^{∗}Ω Ω Ω_{α_{1}}(F_{·}^{1}) ∩ π_{2}^{∗}Ω Ω Ω_{α_{2}}(F_{·}^{2}) ∩ ⋯ ∩ π_{m}^{∗}Ω Ω Ω_{α_{m}}(F_{·}^{m}) \ar[r] & F l(n)^{m}}

is as well.

This begs the following question: is the only obstruction to the Kleiman-Bertini theorem for G(k, n) the one suggested by Kleiman, i.e. whether the variety in question intersects a general translate of all Schubert varieties transversely? More precisely, is it true that for all Q_{1} and Q_{2} such that Q_{i} ∩ Ω Ω Ω_{α}(F_{·}) → F l(n) is generically smooth for all α, and i = 1, 2, it follows that

\xymatrix{Q_{1} ∩ σ(Q_{2}) \ar[r] & P GL(n)}

is also generically smooth, where σ ∈ P GL(n)?

Theorem 1.5 answers Question 3, and leads to answers to Questions 2 and 4:

1.6. Corollary. —

(a) All Schubert problems are enumerative for algebraically closed fields.

(b) For any prime p, there is a positive density of points P defined over finite fields of characteristic p where S^{−1}(P) consists of deg (Ω_{α_{1}} ∪ ⋯ ∪ Ω_{α_{m}}) distinct points. Moreover, for a fixed m, there is a positive density of points that works for all choices of α_{1} …, α_{m}.

Part (a) follows as usual (see Sect. 1.1). If dim (Ω_{α_{1}} ∪ ⋯ ∪ Ω_{α_{m}}) = 0, then Theorem 1.5 implies that S is generically separable (i.e. the extension of function fields is separable). Then (b) follows by applying the Chebotarev density theorem for function fields to

\xymatrix{∐_{α_{1},...,α_{m}} π_{1}^{∗}Ω Ω Ω_{α_{1}}(F_{·}^{1}) ∩ π_{2}^{∗}Ω Ω Ω_{α_{2}}(F_{·}^{2}) ∩ ⋯ ∩ π_{m}^{∗}Ω Ω Ω_{α_{m}}(F_{·}^{m}) \ar[r] & F l(n)^{m}}

(see for example [E, Lemma 1.2], although all that is needed is the curve case, e.g. [FJ, Sect. 5.4]).

Sottile has proved transversality for intersection of codimension 1 Schubert varieties [S7], and P. Belkale has recently proved transversality in general, using his proof of Horn’s conjecture [Bel, Thm. 0.9].

1.7. Effective numerical solutions (over ℂ) to all Schubert problems for all Grassmannians. Even over the complex numbers, questions remain.

Question 5. Is there an effective numerical method for solving Schubert problems (i.e. calculating the solutions to any desired accuracy)?

The case of intersections of “Pieri classes” was dealt with in [HSS]. For motivation in control theory, see for example [HV]. In theory, one could numerically solve Schubert problems using the Plücker embedding; however, this is unworkable in practice.

Schubert induction leads to an algorithm for effectively numerically finding all solutions to all Schubert problems over ℂ. The method will be described in [SVV], and the reasoning is sketched in Section 2.10.

1.8. Galois or monodromy groups of Schubert problems. The Galois or monodromy group of an enumerative problem measures three (related) things:

(a) (geometric) As the conditions are varied, how do the solutions permute?

(b) (arithmetic) What is the field of definition of the solutions, given the field of definition of the flags?

(c) (algebraic) What is the Galois group of the field extension of the “variety of solutions” over the “variety of conditions” (see (1))?

(See [H] for a complete discussion.) Historically, these groups were studied since the nineteenth century [J, D, W]; modern interest probably dates from a letter from Serre to Kleiman in the seventies (see the historical discussion in the survey article [Kl2, p. 325]). Their modern foundations were laid by Harris in [H]; the connection between (a) and

(c) is made there. The connection to (b) is via the Hilbert irreducibility theorem, as the target of S is rational ([La, Sect. 9.2], see also [Se, Sect. 1.5] and [C]). We are grateful to M. Nakamaye for discussions on this topic.

Question 6. What is the Galois group of a Schubert problem?

We partially answer this question. There is an explicit combinatorial criterion that implies that a Schubert problem has Galois group “at least alternating” (i.e. if there are d solutions, the group is A_{d} or S_{d}). This criterion holds over an arbitrary base ring. To prove it, we will discuss useful methods for analyzing Galois groups via degenerations. The criterion is quite strong, and seems to apply to all but a tiny proportion of Schubert problems. For example:

1.9. Theorem. — The Galois group of any Schubert problem on the Grassmannians G(2, n) (n ≤ 16) and G(3, n) (n ≤ 9) is either alternating or symmetric.

A short Maple program applying the criterion to a general Schubert problem is available upon request from the author.

One might expect that the Galois group of a Schubert problem is always the full symmetric group. However, this not the case. To our knowledge, the first examples are due to H. Derksen. In Section 3.12 we describe the smallest example (involving 4 flags in G(4, 8)), and determine that the Galois action is that of S_{4} on order 2 subsets of {1, 2, 3, 4}. In Section 3.14 we give a family of examples with \binom{N}{K} solutions, with Galois group S_{N}, and action corresponding to the S_{N}-action on order K subsets of {1, …, N}.

We also describe three-flag examples (i.e. corresponding to Littlewood-Richardson coefficients) with similar behavior (Sect. 3.15). Littlewood-Richardson coefficients interpret structure coefficients of the ring of symmetric functions as the cardinality of some set. These three-flag examples show that the set has further structure, i.e. the objects are not indistinguishable. (More correctly, pairs of objects are not indistinguishable; this corresponds to failure of two-transitivity of the monodromy group in S_{N}.)

This family of examples was independently found by Derksen. From his quiver-theoretic point of view, the smallest member of this family (in G(6, 12)) corresponds to the extended Dynkin diagram of E_{6}, and the smallest member of the other family (in G(4, 8)) corresponds to the extended Dynkin diagram of D_{4}.

See [BiV] for more suspected examples when the Galois group is smaller than expected, but where the geometric reason is not understood.

1.10. Flag varieties. The conjecture of [V3] (Conjecture 4.9 of the first arXiv version of [V2]) would imply that the results of this paper except for those on Galois/monodromy groups apply to all Schubert problems on flag manifolds. In particular, as the conjecture is verified in cohomology for n ≤ 5, the results all hold in this range. For example:

1.11. Proposition. — All Schubert problems for F l(n) are enumerative over any algebraically closed field or any field with an implicit function theorem (e.g. ℝ) for n ≤ 5. For a fixed m, there is a set of m flags that works for all choices of α_{1}, …, α_{m}.

(The generalizations of the other statements in this paper are equally straightforward.)

We note that in the case of triple intersections where the answer is 1, Knutson has shown that the solution to the problem can be obtained by using spans and intersections of the linear spaces in the three flags [K]; see also Purbhoo’s result [P].

2. The main theorem, and its proof

2.1. The key observation. Let f : Y → X be a proper morphism of irreducible varieties that we wish to show has some property P. We wish to show a property P holds for f by an inductive method. We will apply this to the morphism f = S.

We will require that P satisfy the conditions (A)–(D) below. As an example of P, the reader should think of “f is generically finite, and there is a Zariski-dense subset U of real points of Y for which f^{−1}(p) consists of deg f real points for all p ∈ U.”

(A) We require that the condition of having P depends only on dense open subsets of the target, i.e. if U ⊂ X is a dense open subset, then f : Y → X has P if and only if f|_{f^{−1}(U)} has P.

(B) Suppose D is a Cartier divisor of X such that D ×_{X} Y is reduced. We require that if D ×_{X} Y → D has property P, then f has property P.

This motivates the following inductive approach. Suppose

X_{0} = X ↩ X_{1} ↩ X_{2} ↩ ⋯ ↩ X_{s}

is a sequence of inclusions, where X_{i+1} is a Cartier divisor of X_{i}. Suppose Y_{i,j} (1 ≤ i ≤ s, 1 ≤ j ≤ J_{i}) is a subvariety of Y such that f maps Y_{i,j} to X_{i}, and Y_{i,j} → X_{i} is proper, and for each 0 ≤ i < s, 1 ≤ j ≤ J_{i},

Y_{i,j} ×_{X_{i}} X_{i+1} = ∪_{j′∈I_{i,j}}Y_{i+1,j′}

for some I_{i,j} ⊂ J_{i+1}, where each Y_{i+1,j′} appears with multiplicity one.

If (C) Y_{i+1,j′} → X_{i+1} has P for all j′ ∈ I_{i,j} implies ∪_{j′∈I_{i,j}}Y_{i+1,j′} → X_{i+1} has P, and (D) Y_{s,j} → X_{s} has P for all j ∈ J_{s} (the base case for the induction),

then we may conclude that f : Y → X has P. (Note that Y ×_{X} X_{s} → X_{s} may be badly behaved; hence the need for the inductive approach. Intersections with Cartier divisors are often better-behaved than arbitrary intersections.)

The main result of this paper is that this process may be applied to the morphism S. The key ingredient is the Geometric Littlewood-Richardson rule.

For some applications, we will need to refine the statement slightly. For example, to obtain lower bounds on monodromy groups, we will need the fact that I_{i,j} never has more than two elements.

2.2. Sketch of the Geometric Littlewood-Richardson rule [V2]. The key ingredient in the proof of the Schubert induction theorem 2.5 is the Geometric Littlewood-Richardson rule, which is a procedure for computing the intersection of Schubert cycles by giving an explicit specialization of the flags defining two representative of the class, via codimension one degenerations. We sketch the rule now.

The variety F l(n) × F l(n) is stratified by the locally closed subvarieties with fixed numerical data. For each (a_{ij})_{i,j≤n}, the corresponding subvariety is {(F_{·}, F′_{·}) : dim F_{i} ∩ F′_{j} = a_{ij}}. We denote such numerical data by the configuration • (normally interpreted as a permutation), and the corresponding locally closed subvariety by X_{•}.

The variety G(k, n) × F l(n) × F l(n) is the disjoint union of “two-flag Schubert varieties”, locally closed subvarieties with specified numerical data. For each (a_{ij}, b_{ij})_{i,j≤n}, the corresponding subvariety is {(F_{·}, F′_{·}, V) : dim F_{i} ∩ F′_{j} = a_{ij}, dim F_{i} ∩ F′_{j} ∩ V = b_{ij}, }. We denote the data of the (b_{ij}) by ∘, so the locally closed subvarieties are indexed by the configuration ∘•. Denote the corresponding two-flag Schubert variety by X_{∘•}. (Warning: the closure of a two-flag Schubert variety need not be a union of two-flag Schubert varieties [V2, Caution 2.20(a)], so this is not a stratification in general.)

There is a specialization order •_{init}, …, •_{final} in the Bruhat order, corresponding to partial factorizations of the longest word [V2, Sect. 2.3]. If • ≠ •_{final} is in the specialization order, then let •_{next} be the next term in the order. We have X_{•_{next}} ⊂ \overline{X}_{•}, dim X_{•_{next}} = dim X_{•} − 1, X_{•_{init}} is dense in F l(n) × F l(n), and X_{•_{final}} is the diagonal in F l(n) × F l(n).

There is a subset of configurations ∘•, called mid-sort, where • is in the specialization order [V2, Defn. 2.8].

2.3. Geometric Littlewood-Richardson Rule, inexplicit form (cf. [V2, Sect. 2]). —

(i) For any two partitions α_{1}, α_{2}, π_{1}^{∗}Ω Ω Ω_{α_{1}}(F_{·}^{1}) ∩ π_{2}^{∗}Ω Ω Ω_{α_{2}}(F_{·}^{2}) = \overline{X}_{∘•_{init}} for some mid-sort ∘•_{init}, or π_{1}^{∗}Ω Ω Ω_{α_{1}}(F_{·}^{1}) ∩ π_{2}^{∗}Ω Ω Ω_{α_{2}}(F_{·}^{2}) = ∅.

(ii) For any mid-sort ∘•_{final}, \overline{X}_{∘•_{final}} = π_{1}^{∗}Ω Ω Ω_{α}(F_{·}) ∩ Δ (= π_{2}^{∗}Ω Ω Ω_{α}(F_{·}) ∩ Δ) for some α, where Δ is the pullback to G(k, n) × F l(n) × F l(n) of the diagonal X_{•_{final}} of F l(n) × F l(n).

(iii) For any mid-sort ∘• with • ≠ •_{final}, consider the diagram [V2, equ. (1)]

(2)  \xymatrix{\overline{X}_{∘•} \ar@{^{(}->}[r]^{open} \ar[d] & \overline{X}_{∘•} \ar[d] & D_{X} \ar@{^{(}->}[l]_{closed} \ar[d] \\ X_{•} \ar@{^{(}->}[r]^{open} & X_{•} ∪ X_{•_{next}} & X_{•_{next}}. \ar@{^{(}->}[l]_{closed}}

The closures of X_{∘•} are taken in G(k, n) × X_{•} and G(k, n) × (X_{•} ∪ X_{•_{next}}) respectively, and the Cartier divisor D_{X} is defined by fibered product. There are one or two mid-sort configurations (depending on ∘•), denoted by ∘_{swap}•_{next} and/or ∘_{stay}•_{next}, such that D_{X} = \overline{X}_{∘_{swap}•_{next}}, \overline{X}_{∘_{stay}•_{next}}, or \overline{X}_{∘_{stay}•_{next}} ∪ \overline{X}_{∘_{swap}•_{next}} (with multiplicity 1).

There is a more precise version of this rule describing the mid-sort ∘•, and ∘_{swap}•_{next} and ∘_{stay}•_{next} (see [V2, Sect. 2]). For almost all applications here this version will suffice, but the precise definition of mid-sort, ∘_{swap}•_{next}, and ∘_{stay}•_{next} will be implicitly required for the Galois/monodromy results of Section 3.

2.4. Statement of Main theorem. Fix an irreducible subvariety Q ⊂ G(k, n), and define S = S(α_{1}, …, α_{m−1}) ⊂ G(k, n) × F l(n)^{m−1} by

(3)  S := (Q × F l(n)^{m−1}) ∩ π_{1}^{∗}Ω Ω Ω_{α_{1}}(F_{·}^{1}) ∩ ⋯ ∩ π_{m−1}^{∗}Ω Ω Ω_{α_{m−1}}(F_{·}^{m−1}).

Then S is irreducible, and the projection to B := F l(n)^{m−1} has relative dimension dim Q− ∑ |α_{i}|. (This follows easily by constructing S as a fibration over Q.)

Let P be a property of morphisms satisfying (A). For such S → B, and any mid-sort ∘•, let ρ_{1} and ρ_{2} be the two projections from B × (F l(n) × F l(n)) onto its factors. Using (2), construct

(4)  [figure: ρ_{1}^{∗}S ∩ ρ_{2}^{∗}\overline{X}_{∘•}; open; e; ρ_{1}^{∗}S ∩ ρ_{2}^{∗}\overline{X}_{∘•}; f; ρ_{1}^{∗}S ∩ ρ_{2}^{∗}D_{X}; closed; g; ρ^{∗}_{1}S∩ρ^{∗}_{2}\overline{X}∘_{swap} •_{next} and/or ρ^{∗}_{1}S∩ρ^{∗}_{2}\overline{X}∘_{stay}•_{next}; birat’l; h; B × X_{•}; open; B × (X_{•} ∪ X_{•_{next}}); B × X_{•_{next}}.; closed]

As in (2), \overline{X}_{∘•} is the closure of X_{∘•} in the appropriate space; ρ_{2}^{∗}\overline{X}_{∘•} is the pullback of \overline{X}_{∘•} from X_{•} or X_{•} ∪ X_{•_{next}}, and similarly for the other terms of the top row. The upper right should be interpreted as

ρ_{1}^{∗}S ∩ ρ_{2}^{∗}\overline{X}_{∘_{swap} •_{next}}, ρ_{1}^{∗}S ∩ ρ_{2}^{∗}\overline{X}_{∘_{stay}•_{next}}, or ρ_{1}^{∗}S ∩ ρ_{2}^{∗}\overline{X}_{∘_{swap} •_{next}} ∐ ρ_{1}^{∗}S ∩ ρ_{2}^{∗}\overline{X}_{∘_{stay}•_{next}},

as in the Geometric Littlewood-Richardson rule 2.3.

2.5. Schubert induction theorem. — Let P be a property of morphisms that depends only on dense open sets of the target (condition (A)). Suppose for any diagram (4) and for any mid-sort checker configuration ∘• that g has P implies f has P (condition (B)) and that h has P implies g has P (condition (C)). If the projection

(5)  \xymatrix{(Q × F l(n)) ∩ Ω Ω Ω_{α}(F_{·}) \ar[r] & F l(n)}

has P for all partitions α (the “base case” of the Schubert induction), then the projection

\xymatrix{(Q × F l(n)^{m}) ∩ π_{1}^{∗}Ω Ω Ω_{α_{1}}(F_{·}^{1}) ∩ ⋯ ∩ π_{m}^{∗}Ω Ω Ω_{α_{m}}(F_{·}^{m}) \ar[r] & F l(n)^{m}}

has P for all m, α_{1}, …, α_{m}.

In particular (taking Q = G(k, n)) if the projection

(6)  \xymatrix{Ω Ω Ω_{α}(F_{·}) \ar[r] & F l(n)}

has P for all α (condition (D)), then the projection

\xymatrix{S : π_{1}^{∗}Ω Ω Ω_{α_{1}}(F_{·}^{1}) ∩ ⋯ ∩ π_{m}^{∗}Ω Ω Ω_{α_{m}}(F_{·}^{m}) \ar[r] & F l(n)^{m}}

has P. Proof. To begin with, note that (A) implies that if f has P then e has P as well.

We show that

(7) (Q × F l(n)^{m−1} × X_{•}) ∩ π_{1}^{∗}Ω Ω Ω_{α_{1}}(F_{·}^{1}) ∩ ⋯ ∩ π_{m−1}^{∗}Ω Ω Ω_{α_{m−1}}(F_{·}^{m−1}) ∩ ρ^{∗}\overline{X}_{∘•} → F l(n)^{m−1} × X_{•}

(where ρ is the projection to X_{•}) has P for all m and mid-sort ∘•, by induction on (m, •), where (m_{1}, •_{1}) precedes (m_{2}, •_{2}) if m_{1} < m_{2}, or m_{1} = m_{2} and •_{1} < •_{2} in the specialization order.

Base case m = 1, • = •_{final}. By the Geometric Littlewood-Richardson rule 2.3 (ii),

[figure: (Q × X_{•_{final}}) ∩ ρ^{∗}\overline{X}_{∘•_{final}}; ≅; X_{•_{final}}; (i.e., (7)); (Q × X_{•_{final}}) ∩ π_{1}^{∗}Ω Ω Ω_{α}(F_{·}) ∩ Δ; ≅; X_{•_{final}}; ≅; (Q × F l(n)) ∩ Ω Ω Ω_{α}(F_{·}); F l(n)]

has P by (5).

Inductive step, case • ≠ •_{final}. By the inductive hypothesis, (Q×F l(n)^{m−1}×X_{•_{next}})∩π_{1}^{∗}Ω Ω Ω_{α_{1}}(F_{·}^{1})∩⋯∩π_{m−1}^{∗}Ω Ω Ω_{α_{m−1}}(F_{·}^{m−1})∩ρ^{∗}\overline{X}_{∘_{stay}•_{next}} → F l(n)^{m−1}×X_{•_{next}} and/or (Q×F l(n)^{m−1}×X_{•_{next}})∩π_{1}^{∗}Ω Ω Ω_{α_{1}}(F_{·}^{1})∩⋯∩π_{m−1}^{∗}Ω Ω Ω_{α_{m−1}}(F_{·}^{m−1})∩ρ^{∗}\overline{X}_{∘_{swap} •_{next}} → F l(n)^{m−1}×X_{•_{next}} have P. Then an application of (B) and (C) shows that (7)has P as well.

Inductive step, case • = •_{final}, m > 1. Suppose \overline{X}_{∘•_{final}} = π_{1}^{∗}Ω Ω Ω_{α}(F_{·}) ∩ Δ and π_{1}^{∗}Ω Ω Ω_{α_{m−1}}(F_{·}) ∩ π_{2}^{∗}Ω Ω Ω_{α}(F′_{·}) = \overline{X}_{∘′•_{init}} (using the Geometric Littlewood-Richardson rule 2.3 (ii) and (i) respectively). Then

[figure: (Q×F l(n)^{m−1}×X_{•})∩π_{1}^{∗}Ω Ω Ω_{α_{1}}(F_{·}^{1})∩···∩π_{m−1}^{∗}Ω Ω Ω_{α_{m−1}}(F_{·}^{m−1})∩ρ^{∗}\overline{X}_{∘•}; ≅; F l(n)^{m−1}×X_{•}; ≅; (Q×F l(n)^{m−1}×X_{•})∩π_{1}^{∗}Ω Ω Ω_{α_{1}}(F_{·}^{1})∩···∩π_{m−1}^{∗}Ω Ω Ω_{α_{m−1}}(F_{·}^{m−1})∩π_{m}^{∗}Ω Ω Ω_{α}(F_{·}^{m}); ≅; F l(n)^{m}; (Q×F l(n)^{m−1}×X_{•})∩π_{1}^{∗}Ω Ω Ω_{α_{1}}(F_{·}^{1})∩···∩π_{m−2}^{∗}Ω Ω Ω_{α_{m−2}}(F_{·}^{m−2})∩ρ^{∗}\overline{X}_{∘′•_{init}}; F l(n)^{m}]

which has P as (by (A))

(Q × F l(n)^{m−1} × X_{•}) ∩ π_{1}^{∗}Ω Ω Ω_{α_{1}}(F_{·}^{1}) ∩ ⋯ ∩ π_{m−2}^{∗}Ω Ω Ω_{α_{m−2}}(F_{·}^{m−2}) ∩ ρ^{∗}\overline{X}_{∘′•_{init}} → F l(n)^{m−2} × X_{•_{init}}

has P by the inductive hypothesis. □

For some applications, we will need a slight variation.

2.6. Schubert induction theorem, bis. — Suppose P satisfies conditions (A–C). If

\xymatrix{∐_{α: dim Q−|α|=0}(Q × F l(n)) ∩ Ω Ω Ω_{α}(F_{·}) \ar[r] & F l(n)}

has P then

\xymatrix{∐_{α_{1},...,α_{m}: dim Q−∑ |α_{i}|=0}(Q × F l(n)^{m}) ∩ π_{1}^{∗}Ω Ω Ω_{α_{1}}(F_{·}^{1}) ∩ ⋯ ∩ π_{m}^{∗}Ω Ω Ω_{α_{m}}(F_{·}^{m}) \ar[r] & F l(n)^{m}}

has P for all m.

The proof is identical to that of Theorem 2.5; we simply restrict attention to morphisms (7)of relative dimension zero. There is only one base case (D), (6), which is rather trivial (checking that the identity F l(n) → F l(n) has P).

2.7. Applications. We now verify the conditions (A–C) for several P to prove the results claimed in Section 1.

2.8. Positive characteristic: Proof of Proposition 1.5. Let P be the property that the morphism f is generically smooth. Then P clearly satisfies (A–C) (note that the relative dimensions of (f, g, h) are the same, and that X_{∘_{stay}•_{next}} and X_{∘_{swap} •_{next}} are disjoint), and the Schubert induction hypothesis (D); apply Theorem 2.5. □

2.9. Reality: Proof of Proposition 1.3. Let P be the property that there is a Zariski-dense subset U of real points of Y for which S^{−1}(p) consists of deg S real points for all p ∈ U. Clearly P satisfies (A–C). Apply Theorem 2.6. □

As mentioned earlier, the same argument applies to any field satisfying the implicit function theorem, such as ℚ_{p}.

2.10. Numerical solutions. Informally, this application corresponds to applying Theorem 2.6 to the property of generically finite morphisms f : X ↪ G(k, n) × Y → Y “for each point of Y whose preimage is a finite number of points, there is an effective (in practice) algorithm for numerically finding these points”. Condition (C) corresponds to the fact that if |f^{−1}(y)| = deg f and the points of f^{−1}(y) can be numerically calculated, then by the implicit function theorem, the points of f^{−1}(y′) can be numerically calculated for all y′ such that dim f^{−1}(y′) = 0. This idea will be developed in [SVV].

3. Galois/monodromy groups of Schubert problems

3.1. We recall the “checker tournament” algorithm [V2, Sect. 2.18] for solving Schubert problems. We begin with m partitions, and we make a series of moves. Each move consists of one of the following.

(i) Take two partitions, and begin a checkergame if possible, else end the tournament.

(ii) Translate a completed checkergame back to a partition.

(iii) Make a move in an ongoing checkergame.

These parallel (i)–(iii) of Theorem 2.3. When one partition and no checkergames are left, the tournament is complete. At step (iii), the checker tournament may bifurcate (if both a “stay” and a “swap” are possible), and both branches must be completed.

This answer to the Schubert problem can be interpreted as a creating a directed tree, where the vertices correspond to partially completed checker tournament. Each vertex has in-degree 1 (one immediate ancestor) except for the root (corresponding to the original Schubert problem), and out-degree (number of immediate descendants) between 0 and 2. The graph is constructed starting with the root, and for each vertex that is not a completed checkergame, a choice may be made (depending on (iii)) which may lead to a bifurcation. Vertices corresponding to a single partition and no checkergames are called leaves. (There may be other vertices with out-degree 0, arising from (i); these are not leaves.) The answer is the number of leaves of the tree.

The answer is of course independent of the choices made; in the description of [V2, Sect. 2.18], and in the proof of Theorems 2.5 and 2.6, each checkergame was chosen to be completed before the next was begun.

3.2. Theorem. — Suppose we are given a Schubert problem such that there is a directed tree as above, where each vertex with out-degree two satisfies either

(a) there are a different number of leaves on the 2 branches, or

(b) there is one leaf on each branch.

Then the Galois group of the Schubert problem is at least alternating.

3.3. Specialization of monodromy. To prove the theorem, we will examine how Galois groups behave under specialization.

We say a generically finite morphism f : X → Y is generically separable if the corresponding extension of function fields is separable. Define the Galois group Gal_{f} of a generically finite and separable (i.e. generically étale) morphism to be the Galois group of the Galois closure of the corresponding extension of function fields.

3.4. Remark: The complex case. To motivate later statements over an arbitrary ground ring, we first consider the complex case. Suppose

\xymatrix{W \ar[d] & Y \ar@{^{(}->}[l]_{closed} \ar[d] \\ X & Z \ar@{^{(}->}[l]_{closed}}

is a fiber diagram of complex schemes, where the vertical morphisms are proper generically finite degree d; W, X, and Z are irreducible varieties; Z is Cartier in X; X is regular in codimension 1 along Z; and Y is reduced. Then Gal_{W→X} can be interpreted as an element of S_{d} by fixing a point of X with d preimages, and considering loops in the smooth locus of X based at that point, and their induced permutations of the preimages.

(a) If Y is irreducible, then by interpreting Gal_{Y→Z} by choosing a general base point of Z and elements of the fundamental group of the smooth part of Z generating the Galois group, we have constructed an inclusion Gal_{Y→Z} ↪ Gal_{W→X}. In particular, if the first group is at least alternating, then so is the second.

(b) If Y has two components Y_{1} and Y_{2}, which each map generically finitely onto Z with degrees d_{1} and d_{2} respectively (so d_{1} + d_{2} = d), then the same construction produces a subgroup H of Gal_{Y_{1}→Z} × Gal_{Y_{2}→Z} which surjects onto Gal_{Y_{i}→Z} (for i = 1, 2), and an injection of H into Gal_{W→X} (via the induced inclusion S_{d_{1}} × S_{d_{2}} ↪ S_{d}).

Then a purely group-theoretical argument (Prop. 3.7) relying on Goursat’s lemma will show that if Gal_{Y_{i}→Z} is at least alternating (i = 1, 2), W is connected (so Gal_{W→X} is transitive), and d_{1} ≠ d_{2} or d_{1} = d_{2} = 1, then Gal_{W→X} is at least alternating as well.

3.5. The general case. With this complex intuition in hand, we prove Remarks 3.4(a) and (b) over an arbitrary ring. Suppose k_{1} ⊂ k_{2} is a separable degree d field extension. Choose an ordering x_{1}, …, x_{d} of the \overline{k}_{1}-valued points (over Spec k_{1}) of Spec k_{2}. If g : X → Y is a generically finite separable (i.e. generically étale) morphism, define the “Galois scheme” GalSch_{g} by

\overbrace{X ×_{Y} ⋯ ×_{Y} X}^{deg g} \Δ

where Δ is the “big diagonal”. Recall that the Galois group of k_{1} ⊂ k_{2} can be interpreted as a subgroup of S_{d} as follows: σ is in the Galois group if and only if (x_{σ(1)}, …, x_{σ(d)}) is in the same component of GalSch_{Spec k_{2}→Spec k_{1}} as (x_{1}, …, x_{d}).

To understand how this behaves in families, let R be a discrete valuation ring with function field K and residue field k. Suppose the following is a fiber diagram

\xymatrix{X_{K} \ar[d] \ar@{^{(}->}[r]^{open} & X_{R} \ar[d] & X_{k} \ar[d] \ar@{^{(}->}[l]_{closed} \\ Spec K \ar@{^{(}->}[r]^{open} & Spec R & Spec k \ar@{^{(}->}[l]_{closed}}

where X_{K} is irreducible, X_{k} is reduced, and the vertical morphisms are finite and separable (and hence étale, using X_{k} reduced).

After choice of algebraic closures, there is a bijection from the \overline{K}-valued points of X_{K} with the \overline{k}-valued points of X_{k}.

By observing that each component of GalSch_{X_{k}→Spec k} lies in a unique irreducible component of GalSch_{X_{R}→Spec R} (as GalSch_{X_{R}→Spec R} → Spec R is étale along X_{k}), we see that Remarks 3.4 (a) and (b) hold in general (by applying these comments to O_{X,Z}).

3.6. Proof of Theorem 3.2. Each vertex v corresponds to a diagram

\xymatrix{X \ar@{^{(}->}[r] \ar[d]_{f_{v}} & B × G(k, n) \\ B}

where X is irreducible, and B is a product of flag varieties (one for each partition) and strata X_{∘•} (one for each checkergame in process). The morphism f_{v} is generically finite and separable, and its degree is the answer to the corresponding enumerative problem.

We label each vertex v with the number of leaves on that branch (i.e. with deg f_{v}), and with the Galois group Gal_{v} of that problem. We prove that Gal_{v} = A_{deg f_{v}} or S_{deg f_{v}} for all v by induction on v. (This is a slight generalization of Schubert induction.)

If v is a leaf, the result is trivial.

Suppose next that v is a vertex with one descendant w, and Gal_{w} is at least alternating. If the move from v to w is of type (i) or (ii), then the morphism f_{v} is the same as f_{w}, so the result holds. If the move from vertex v is of type (iii) (so exactly one of {stay, swap} is possible), then G_{v} is at least alternating by Remark 3.4(a).

Next, suppose v has two immediate descendants, so we are in case (iii) and both “stay” and “swap” are possible. If one branch has no leaves, then G_{v} is at least alternating by Remark 3.4(a), so assume otherwise. As X is irreducible, Gal_{v} is transitive. By Remark 3.4(b) and the group theoretic calculation of Proposition 3.7, Gal_{v} is at least alternating, and the inductive step is complete.

Thus by induction the root vertex has at least alternating Galois group, completing the proof of the Theorem 3.2. □

3.7. Proposition. — Suppose G is a transitive subgroup of S_{m+n} such that G ∩ (S_{m} × S_{n}) contains a subgroup H such that the projection of H to S_{m} (resp. S_{n}) is either A_{m} (m ≥ 4) or S_{m} (resp. A_{n} for n ≥ 4, or S_{n}).

(a) If m ≠ n, then G = A_{m+n} (m + n ≥ 4) or S_{m+n}.

(b) If m = n = 1 then G = S_{2}.

Note that if m = n, then

{e, (1, n + 1)(2, n + 2) ⋯ (n, 2n)} ⋊ (S_{{1,...,n}} × S_{{n+1,...,2n}})

is a subgroup of S_{2n} whose intersection with S_{{1,...,n}} × S_{{n+1,...,2n}} surjects onto each of its factors.

Proof. Part (b) is trivial, so we prove (a). Assume without loss of generality that n > m.

Recall Goursat’s lemma: if H ⊂ G_{1} × G_{2}, such that H surjects onto both factors, then there are normal subgroups N_{i} ⊲ G_{i} (i = 1, 2) and an isomorphism ϕ : G_{1}/N_{1} →^{∼} G_{2}/N_{2} such that (g_{1}, g_{2}) ∈ H if and only if ϕ(g_{1}N_{1}) = g_{2}N_{2}.

We first show that if G is a transitive subgroup of S_{m+n} (n > m ≥ 3) containing A_{m}×A_{n}, then G contains any 3-cycle and hence A_{m+n}. Color the numbers 1 through m red and m + 1 through m + n green. Any monochromatic 3-cycle lies in A_{m} × A_{n} and hence G. Suppose τ is any element of G sending a green number to a red position. (i) If there are two numbers of each color in the positions of one color (say, red) then the conjugate of a 3-cycle in A_{m} by τ will be a 3-cycle α of 1 red and 2 green objects, and the conjugate of a different 3-cycle in A_{m} by τ will be a 3-cycle α of 1 green and 2 red objects. Similarly, (ii) if there is at least one number of each color in the positions of both colors, we can find a conjugate α of a 3-cycle in A_{m} or A_{n} by τ that is a 3-cycle α of 1 red and 2 green objects, and the conjugate of a 3-cycle in A_{n} or A_{m} by τ that is a 3-cycle α of 1 green and 2 red objects. By conjugating α and β further by elements of A_{m} × A_{n}, we can obtain any nonmonochromatic 3-cycle. Now τ falls into case (i) and/or (ii), or n = m + 1 and τ sends all red objects to green positions, and all but one green object to red positions. Suppose p is the green position containing the green object in τ, and σ is a 3-cycle in A_{n} moving p. Then τ^{−1}στ is a permutation where exactly one red object is sent to a green position, and vice versa, and we are in case (ii). Thus in all cases G contains A_{m+n}, as desired.

We now deal with the case m, n ≥ 3. By Goursat’s lemma, G must contain A_{m} × A_{n}. (For example, if the projections of H to S_{m} and S_{n} are surjective, then H arises from isomorphic quotients S_{n}/N_{m} ≅ S_{n}/N_{n}. Then (N_{m}, N_{n}) = (S_{m}, S_{n}) or (N_{m}, N_{n}) = (A_{m}, A_{n}); in both cases A_{m} ⊂ N_{m} and A_{n} ⊂ N_{n}.) Then apply the previous paragraph.

For the remaining cases, it is straightforward to see (using Goursat) that (i) if the image of H is A_{n} (resp. S_{n}) and m = 1, then A_{m+n} ⊂ G (resp. G = S_{m+n}), and (ii) if H surjects onto A_{n} (n ≥ 4) or S_{n} and m = 2, then A_{m+n} ⊂ G. □

3.8. Remark. We note for use in Section 3.12 that if n = 1 and the projection to S_{m} is surjective, then the same argument shows that G = S_{m+n}.

3.9. Applying Theorem 3.2. Theorem 3.2 is quite strong, and can be checked with a naive computer program. For example, it implies that all Schubert problems for G(2, n) for n ≤ 16 are at least alternating. It also implies that all but a tiny handful of Schubert problems for Grassmannians of dimension less than 20 are at least alternating; we will describe these exceptions.

For k > 1, the criterion will fail for the Schubert problem (1)^{k^{2}} on G(k, 2k): the first degeneration (i.e. the first vertex with out-degree 2) will correspond to

(1)^{k^{2}} = (2)(1)^{k^{2}} + (1, 1)(1)^{k^{2}}

and the two branches will have the same number of leaves by symmetry. More generally, if 1 ≤ m < k and (m, k) ≠ (1, 2), the criterion will fail for the Schubert problem

(\overbrace{m, …, m}^{m})(1)^{k^{2}−m^{2}}

on G(k, 2k) for the same reason.

9  ×  5

Figure 1. The two counterexamples of G(3, 6)

×  4 ×

Figure 2. An induced (non-primitive) counterexample in G(3, 7)

On G(3, 6), the only counterexamples are of this sort, when m = 1 and 2, shown in Figure 1. By “embedding” these problems in larger problems, these trivially induce counterexamples in larger Grassmannians; for example, Figure 2 is a counterexample in G(3, 7) that is really an avatar of the second example in G(3, 6). We call counterexamples in G(k, n) not arising in this way, i.e. involving only subpartitions not meeting the right column and bottom row of the rectangle, primitive counterexamples.

Then G(3, 7) has only three counterexamples, shown in Figure 3, and the counterexamples in G(4, 7) are given by the transposes of these. The Grassmannian G(3, 8) has six counterexamples, shown in Figure 4, and G(3, 9) has 13 counterexamples, shown in Figure 5.

All of these exceptions can be excluded with the following, slightly stronger criterion.

6 ×  4 ×  ×  5 ×

Figure 3. The primitive counterexamples in G(3, 7)

4 ×  ×  ×  × 3  2  ×  × 5 × 7  4 ×  ×  6 ×

Figure 4. The primitive counterexamples in G(3, 8)

×  × 3  2  ×  × 5 ×  × 4  ×  ×  × 3 5 ×  ×  ×  × 3 2 ×  ×  ×  × 2 4 6  × 8  × ×  4 ×  3 ×  7  9

Figure 5. The primitive counterexamples in G(3, 9)

3.10. Theorem. — Suppose we are given a Schubert problem such that there is a directed tree as above, where each vertex with two immediate descendants satisfies (a) or (b) of Theorem 3.2, or

(c) there are m ≠ 6 leaves on each branch, and it is known that the corresponding Galois group is two-transitive.

Then the Galois group of the Schubert problem is at least alternating.

In particular, to show that the Galois group is (n−2)-transitive, it often suffices to show that it is two-transitive.

As with Theorem 3.2, the proof reduces to the following variation of Proposition 3.7.

3.11. Proposition. — Suppose G is a two-transitive subgroup of S_{2m} (m ≠ 6) such that G ∩ (S_{m} × S_{m}) contains a subgroup H such that the projection of H to both factors S_{m} is either A_{m} (m ≥ 4) or S_{m}. Then G = A_{2m} or S_{2m}.

The proof is similar to that of Proposition 3.7, and is omitted.

If m = n = 6, D. Allcock has pointed out that the Mathieu group M_{12} can be expressed as a subgroup of S_{12} such that

M_{12} ∩ (S_{6} × S_{6}) = {(g, σ(g)) : g ∈ S_{6}}

where σ is an outer automorphism of S_{6}. Thus Proposition 3.11 cannot be extended to m = 6.

We say two vertices v, w in a directed tree (as in Sect. 3.1) are equivalent if they are connected by a chain of edges v_{1} → v_{2} → ⋯ → v_{s} ((v_{1}, v_{s}) = (v, w) or (w, v)) and deg f_{v} = deg f_{w} (and hence = deg f_{v_{i}} for all i). In each of the cases G(3, n) (6 ≤ n ≤ 9) given above, it is possible to find such a tree satisfying Theorem 3.10 (a)–(c), where the vertices of type

(c) are equivalent to vertices corresponding to Schubert problems (i.e. corresponding to a set of partitions, with no checkergames-in-progress), and to show by ad hoc means that these Schubert problems are two-transitive. (The details are omitted; this method should not be expected to be workable in general.) Hence all Schubert problems for these Grassmannians have Galois group at least alternating.

The Grassmannian G(4, 8) has only 31 Schubert problems where the criterion of Theorem 3.2 does not apply (not shown here). Each of these cases may be reduced to checking that a certain Schubert problem is two-transitive. As we shall see in the next Section, in one of these cases two-transitivity does not hold!

3.12. Galois groups of Schubert problems needn’t be the full symmetric group, or alternating.

3.13. Derksen’s example in G(4, 8). One of the 31 examples in G(4, 8) described above has a Galois group that is not equal to S_{n} or A_{n} (and hence is not two-transitive by our earlier discussion): the Schubert problem of Figure 6. This example (and the existence of Schubert problems with a “small” Galois group) is due to H. Derksen. By Theorem 1.9, this is the smallest example of a Schubert problem with a Galois group smaller than alternating.

The problem has six solutions. We show now that the Galois group is S_{4}. Fix four general flags in K^{8}, and consider the Schubert problem in G(2, 8) (corresponding to these flags) shown in Figure 7. This problem has four solutions, corresponding to four transverse 2-planes V_{1}, V_{2}, V_{3}, V_{4}. It is straightforward to check that V_{i} + V_{j} (i < j) is a solution to the original problem of Figure 6, in G(4, 8). Hence the Galois group of the original Figure 6. This Schubert problem (in G(4, 8)) has 6 solutions; the Galois group is S_{4}

problem is not two-transitive: two solutions W_{1} and W_{2} may have intersection of dimension 0 or 2, and both possibilities occur. The Galois group is a subgroup of S_{4} (acting on the six elements as described above), and is canonically the Galois group of the problem of Figure 7.

4

Figure 7. An auxiliary Schubert problem in G(2, 8)

Applying Theorem 3.2 (indeed Theorem 1.9), the Galois group of Figure 7 is at least A_{4}. By examining the directed tree of Theorem 3.2 more closely, we see that the Galois group is actually S_{4}: the first branching has one branch with three leaves and one branch with one leaf (see Remark 3.8).

3.14. A family of examples generalizing Derksen’s. Derksen’s example can be generalized to produce other examples of smaller-than-expected Galois groups, where the Galois action is that of S_{N} acting on the order K subsets of {1, 2, …, N}, as follows. The Schubert problem of Figure 8 in G(2K, 2N) has \binom{N}{K} solutions. Given four general flags in G(2, 2N), the auxiliary problem of Figure 9 has N solutions, corresponding to N transverse 2-planes V_{1}, …, V_{N} in G(2, 2N). By repeated applications of Remark 3.8, the Galois group of the auxiliary Schubert problem is S_{N}. The subspace V_{i_{1}} + ⋯ + V_{i_{K}} (1 ≤ i_{1} < ⋯ < i_{K} ≤ N) is a solution to the original problem of Figure 8. Hence the original problem exhibits the desired behavior.

N − K  4 K  ^{…}

Figure 8. A Schubert problem in G(2K, 2N) with \binom{N}{K} solutions and Galois group S_{N}

The only statements in the previous paragraph that are nontrivial to verify are (i) the enumeration of solutions to the Schubert problem, and (ii) the fact that the Galois group

\begin{aligned}& 4 \\ ⋯ \\ N − 1 \end{aligned}

Figure 9. An auxiliary problem

of the auxiliary problem is S_{N}. Both are easiest to see in terms of puzzles. (See [KTW] for a definition of puzzles, and [V2, App. A] for the bijection between checkers and puzzles.)

Part (i) is the number of ways of filling in the puzzle of Figure 10 (where the blocks of 1’s are all of size K, and the blocks of 0’s are all of size N −K), which reduces to Figure 11. After trying the puzzle, the reader will quickly see that the number of solutions is \binom{N}{K}. The solutions correspond to the choice of labels on segment A — there will be N − K 0’s and K 1’s, and each order appears in precisely one completed puzzle.

0

1 1 0 0

1 1

0

0

1 1 0 0

1 1 0

1

0 0 1

1

0 0 1

0 0 1

1 0

0 1

1

with pieces of the form ways can you fill in the puzzle In how many

?

0

1 0

1 0 1 0

1

1

0

Figure 10. The puzzle corresponding to Figure 8

To construct the directed tree for part (ii), note that the order of the first checkergame corresponds to filling in the top half of the puzzle of Figure 10 (and hence Figure 11) row by row; the directed graph corresponds to the tree of choices made while completing the puzzle in this order. Applying this in the case K = 1, the puzzles of the previous paragraph show that the tree is of the desired form.

It is interesting (but inessential) to note more generally that the tree for \binom{N}{K} (call it of type (N, K)) can be interpreted in terms of Pascal’s triangle as follows. The two branches at the first branch point have \binom{N−1}{K−1} and \binom{N−1}{K} leaves, and the two corresponding directed trees are of type (N − 1, K − 1) and (N − 1, K) respectively. Thus Theorem 3.2 fails to

0 0 1

1 0 1 0 1

0

1 1

0

1

0 0 1

1 1 0

1 0 1 0

A 0

Figure 11. The puzzle corresponding to Figure 8, partially completed

apply because of vertices of type (2N′′, N′′), corresponding to the central terms in Pascal’s triangle.

3.15. A similar family of three-flag examples. We now exhibit a family of three-flag examples with behavior similar to that of the previous section. The Schubert problem of Figure 12 in G(3K, 3N) has \binom{N}{K} solutions and Galois group S_{N}, where the action is that of S_{N} on order K subsets of {1, …, N}.

K  N − K  N − K K  3

Figure 12. A Schubert problem in G(3K, 3N) with \binom{N}{K} solutions and Galois group S_{N}

As with the previous family, to prove this, first count solutions using checkers or puzzles. The puzzle is shown in Figure 13, which again reduces to Figure 11 (without the equatorial cut). Next, fix three general flags. Consider the analogous problem with K = 1. There are N solutions, corresponding to N transverse 3-spaces V_{1}, …, V_{N}. The Galois group is S_{N} by Remark 3.8, as the tree is identical to that of the previous section. The sum of any K of these 3-spaces is a solution to the original Schubert problem (with respect to the same three flags). Thus the Galois group of the original problem is S_{N} as desired.

3.16. Acknowledgments. I am grateful to F. Sottile for advice and discussions. His philosophy is clearly present in this paper. In particular, the phrase “Schubert induction” appeared first in [S6, Sect. 1], although with a slightly different meaning. I thank A. Buch and A. Knutson for introducing me to this subject. I also thank B. Sturmfels for suggesting that [V2] might have numerical applications (see Sect. 1 Question 5), D. Allcock for discussions on the symmetric group, B. Poonen for advice on the Chebotarev density theorem,

0

1 1 0

0

1 1 0 0

1

1 0

1  1  0

0 0

1 0  1  0 1  1  0

0 0

1

1 0

1 1

0

0 0 1

1

Figure 13. The puzzle corresponding to Figure 12

and W. Fulton for improving the exposition of the main result. I am grateful to H. Derksen for pointing out (using the theory of quivers) that the Galois/monodromy group of Schubert problems is sometimes not the full symmetric group, and for producing explicit examples. I thank H. Kley and D. Davis for careful reading of an earlier version. Finally, I am grateful to I. Coskun for very detailed suggestions.

References

[Bel] P. Belkale, Geometric proofs of Horn and saturation conjectures, preprint 2002, math.AG/0208107v2.

[Ber] A. Berg, Enumerative geometry for plane cubic curves in characteristic 2, Compositio Math. 111 (1998), no. 2, 123–147.

[BiV] S. Billey and R. Vakil, Intersections of Schubert varieties in Gl_{n}/B and other permutation array schemes, preprint 2005.

[C] S. D. Cohen, The distribution of Galois groups and Hilbert’s irreducibility theorem, Proc. London Math. Soc. (3) 43 (1981), no. 2, 227–250.

[D] L. Dickson, H. F. Blichfeldt, and G. A. Miller, Theory and applications of finite groups, John Wiley, New York, 1916.

[E] T. Ekedahl, An effective version of Hilbert’s irreducibility theorem, Séminaire de Théorie des Nombres, Paris 1988–1989, 241–249, Progr. Math., 91, Birkhäuser Boston, Boston, MA, 1990.

[EG] A. Eremenko and A. Gabrielov, Rational functions with real critical points and the B. and M. Shapiro conjecture in real enumerative geometry, Annals of Math. 155 (2002), no. 1, 105–129.

[FJ] M. Fried and M. Jarden, Field Arithmetic, Springer-Verlag, Berlin, 1986.

[F1] W. Fulton, Introduction to intersection theory in algebraic geometry, Regional Conf. Series in Math. 54, Amer. Math. Soc., Providence, 1984.

[F2] W. Fulton, Intersection Theory, Springer-Verlag, New York, 1980.

[FP] W. Fulton and P. Pragacz, Schubert varieties and degeneracy loci, Lecture Notes in Math. 1689 Springer-Verlag, Berlin, 1998.

[H] J. Harris, Galois groups of enumerative problems, Duke Math. J. 46 (1979), no. 4, 685–724.

[HSS] B. Huber, F. Sottile, and B. Sturmfels, Numerical Schubert calculus, J. Symbolic Comput. 26 (1998), no. 6, 767–788.

[HV] B. Huber and J. Verschelde, Pieri homotopies for problems in enumerative geometry applied to pole placement in linear systems control, SIAM J. Control Optim. 38 (2000), 1265–1287.

[J] C. Jordan, Traité des Substitutions, Gauthier-Villars, Paris, 1870.

[Kl1] S. Kleiman, The transversality of a general translate, Compositio Math. 28 (1974), 287–297.

[Kl2] S. Kleiman, Intersection theory and enumerative geometry: a decade in review, Algebraic geometry, Bowdoin, 1985, Proc. Sympos. Pure Math., 46, Part 2, 321–370, Amer. Math. Soc., Providence, RI, 1987.

[K] A. Knutson, personal communication.

[KTW] A. Knutson, T. Tao, and C. Woodward, The honeycomb model of GL(n) tensor products II: Puzzles determine facets of the Littlewood-Richardson cone, J. Amer. Math. Soc. 17 (2004), no. 1, 19–48.

[L] D. Laksov, Deformations of determinental schemes, Compositio Math. 30 (1975), 287–297.

[LSp1] D. Laksov and R. Speiser, Transversality criteria in any characteristic, Enumerative geometry (Sitges, 1987), Lectures Notes in Math. 1436, Springer-Verlag, 1990, pp. 139–150.

[LSp2] D. Laksov and R. Speiser, Transversality criteria in any characteristic, Pacific J. Math. 156 (1992), 307– 328.

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

[P] K. Purbhoo, preprint.

[Se] J. P. Serre, Lectures on the Mordell-Weil theorem, M. Waldschmidt trans. F. Viehweg, Braunschweig, 1989.

[S1] F. Sottile, Enumerative geometry for real varieties, Algebraic Geometry, Santa Cruz, 1995, J. Kollár et al. ed., Proc. Sympos. Pure Math. vol. 56, Part 2, Amer. Math. Soc., 1997.

[S2] F. Sottile, Enumerative geometry for the real Grassmannian of lines in projective space, Duke Math. J., 87 (1997), 59–85.

[S3] F. Sottile, Real enumerative geometry and effective algebraic equivalence, J. Pure and App. Alg. 117 and 118 (1997), 601–615.

[S4] F. Sottile, Pieri’s formula via explicit rational equivalence, Can. J. Math., 46 (1997), 1281–1298.

[S5] F. Sottile, The special Schubert calculus is real, ERA of the Amer. Math. Soc. 5 (1999), 35–39.

[S6] F. Sottile, Some real and unreal enumerative geometry for flag manifolds, Michigan Math. J. (Fulton volume) 48 (2000), 573–592.

[S7] F. Sottile, Elementary transversality in the Schubert calculus in any characteristic, Michigan Math. J. 56 (2003), 651–666.

[SVV] F. Sottile, R. Vakil, and J. Verschelde, Effective solutions to all Schubert problems, work in progress.

[Sp] R. Speiser, Transversality theorems for families of maps, Algebraic Geometry (Sundance 1986), A. Holme and R. Speiser eds., Lectures Notes in Math. 1311, Springer-Verlag, 1988, pp. 235–252.

[Vn] I. Vainsencher, Conics in characteristic 2, Compositio Math. 36 (1978), no. 1, 101–112.

[V1] R. Vakil, The enumerative geometry of rational and elliptic curves in projective space, J. Reine Angew. Math. (Crelle) 529 (2000), 101–153.

[V2] R. Vakil, A geometric Littlewood-Richardson rule, Annals of Math., to appear.

[V3] R. Vakil, A conjectural geometric Littlewood-Richardson rule for the equivariant K-theory of the flag variety, in preparation.

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

Dept. of Mathematics, Stanford University, Stanford CA 94305–2125

  E-mail address: vakil@math.stanford.edu