# Galois Groups in Enumerative Geometry
and Applications

Frank Sottile  F. Sottile
Department of Mathematics
Texas A&M University
College Station
Texas 77843
USA<EMAIL_ADDRESS>http://www.math.tamu.edu/ sottile and  Thomas Yahl
T. Yahl
Department of Mathematics
Texas A&M University
College Station
Texas 77843
USA<EMAIL_ADDRESS>http://www.math.tamu.edu/ thomasjyahl

###### Abstract.

As Jordan observed in 1870, just as univariate polynomials have Galois groups,
so do problems in enumerative geometry. Despite this pedigree, the study of
Galois groups in enumerative geometry was dormant for a century, with a
systematic study only occuring in the past 15 years. We discuss the current
directions of this study, including open problems and conjectures.

###### Key words and phrases:

Galois group, enumerative geometry, sparse polynomial systems, Schubert
caculus, Fano problem, homotopy continuation

###### 1991 Mathematics Subject Classification:

14M25, 65H20, 65H10

Research of Sottile and Yahl supported by grant 636314 from the Simons
Foundation.

## Introduction

We are all familiar with Galois groups: They play important roles in the
structure of field extensions and control the solvability of equations. Less
known is that they have a long history in enumerative geometry. In fact, the
first comprehensive treatise on Galois theory, Jordan’s “Traité des
Substitutions et des Équations algébriques” [43, Ch. III], also discusses
Galois theory in the context of several classical problems in enumerative
geometry.

While Galois theory developed into a cornerstone of number theory and of
arithmetic geometry, its role in enumerative geometry lay dormant until
Harris’s 1979 paper “Galois groups of enumerative problems” [31]. Harris
revisited Jordan’s treatment of classical problems and gave a proof that, over
${\mathbb{C}}$, the Galois and monodromy groups coincide. He used this to
introduce a geometric method to show that an enumerative Galois group is the
full symmetric group and showed that several enumerative Galois groups are
full-symmetric, including generalizations of the classical problems studied by
Jordan.

We sketch the development of Galois groups in enumerative geometry since 1979.
This includes some new and newly applied methods to study or compute Galois
groups in this context, as well as recent results and open problems. A theme
that Jordan initiated is that intrinsic structure of the solutions to an
enumerative problem constrains its Galois group $G$ giving an “upper bound”
for $G$. The problem of identifying the Galois group $G$ becomes that of
showing it is as “large as possible”. In all cases when $G$ has been
determined, it is as large as possible given the intrinsic structure. Thus we
may view $G$ as encoding the intrinsic structure of the enumerative problem.

Consider the problem of lines on a cubic surface. Cayley [14] and Salmon [70]
showed that a smooth cubic surface ${\mathcal{V}}(f)$ in ${\mathbb{P}}^{3}$
($f$ is a homogeneous cubic in four variables) contains 27 lines. (See Figure
1.)

Figure 1. A cubic with 27 lines. (Image courtesy of Oliver Labs)

This holds over any algebraically closed field. When $f$ has rational
coefficients, the field $\mathbb{K}$ of definition of the lines is a Galois
extension of ${\mathbb{Q}}$, and its Galois group $G$ has a faithful action on
the 27 lines.

As the lines lie on a surface, we expect that some will meet, and Schläfli
[71] showed that for a general cubic, these lines form a remarkable incidence
configuration whose symmetry group is the reflection group $E_{6}$. As Jordan
observed, this implies that $G$ is a subgroup of $E_{6}$, and it is now known
that for most cubic surfaces $G=E_{6}$.

A modern view begins with the incidence variety of this enumerative problem.
The space of homogeneous cubics on ${\mathbb{P}}^{3}$ forms a 19-dimensional
projective space, as a cubic in four variables has $\binom{3+(4-1)}{3}=20$
coefficients. Writing ${\mathbb{G}}(1,{\mathbb{P}}^{3})$ for the (four-
dimensional) Grassmannian of lines in ${\mathbb{P}}^{3}$, we have the
incidence variety.

(1)
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\Gamma}:=\\{(\ell,f)\in{\mathbb{G}}(1,{\mathbb{P}}^{3})\times{\mathbb{P}}^{19}_{\mbox{\tiny
cubics}}\,\mid\,f|_{\ell}\equiv 0\\}$.$\pi$${\mathbb{P}}^{19}_{\mbox{\tiny
cubics}}$

Write ${\Bbbk}$ for our ground field, which we assume for now to be
algebraically closed. Both $\Gamma$ and ${\mathbb{P}}^{19}$ are irreducible;
Let us consider their fields of rational functions, ${\Bbbk}(\Gamma)$ and
${\Bbbk}({\mathbb{P}}^{19})$. As the typical fiber of $\pi$ consists of 27
points and $\pi$ is dominant, $\pi^{*}({\Bbbk}({\mathbb{P}}^{19}))$ is a
subfield of ${\Bbbk}(\Gamma)$, and the extension has degree 27. The Galois
group $G$ of the normal closure of this extension acts on the lines in the
generic cubic surface over ${\mathbb{P}}^{19}$, and we have that $G=E_{6}$.

Suppose that ${\Bbbk}={\mathbb{C}}$. If $B\subset{\mathbb{P}}^{19}$ is the set
of singular cubics (a degree 32 hypersurface) then over
${\mathbb{P}}^{19}{\smallsetminus}B$, $\Gamma$ is a covering space of degree
27. Lifting based loops gives the monodromy action of the fundamental group of
${\mathbb{P}}^{19}{\smallsetminus}B$ on the fiber above the base point.
Permutations of the fiber obtained in this way constitute the monodromy group
of $\pi$. For the same reasons as before, this is a subgroup of $E_{6}$. In
fact, it equals $E_{6}$.

This situation, a dominant map $\pi\colon X\to Z$ of irreducible
equidimensional varieties, is called a branched cover. Branched covers are
common in enumerative geometry and applications of algebraic geometry. For the
problem of 27 lines, that the algebraic Galois group equals the geometric
monodromy group is no accident; While Harris [31] gave a modern proof, the
equality of these two groups may be traced back to Hermite [39]. We sketch a
proof, valid over arbitrary fields, in Section 1.

Harris’s article brought this topic into contemporary algebraic geometry. He
also introduced geometric methods to show that the Galois group of an
enumerative problem is fully symmetric in that it is the full symmetric group
on the solutions. In the 25 years following its publication, the Galois group
was determined in only a handful of enumerative problems. For example, D’Souza
[18] showed that the problem of lines in ${\mathbb{P}}^{3}$ tangent to a
smooth octic surface at four points (everywhere tangent lines) had Galois
group that is fully symmetric. Interestingly, he did not determine the number
of everywhere tangent lines.

This changed in 2006 when Vakil introduced a method [89] to deduce that the
Galois group of a Schubert problem on a Grassmannian (a Schubert Galois group)
contains the alternating group on its solutions. Such a Galois group is at
least alternating. He used that to show that most Schubert problems on small
Grassmannians were at least alternating, and to discover an infinite family of
Schubert problems whose Galois groups were not the full symmetric group. As we
saw in the problem of 27 lines on a cubic surface, such an enumerative problem
with a small Galois group typically possesses some internal structure.
Consequently, we use the adjective enriched to describe such a problem or
Galois group. Enriched Schubert problems were also found on more general flag
manifolds [69]. These discoveries inspired a more systematic study of Schubert
Galois groups, which we discuss in Section 6. Despite significant progress,
the inverse Galois problem for Schubert calculus remains open.

Galois groups of enumerative problems are usually transitive permutation
groups. There is a dichotomy between those transitive permutation groups that
preserve no nontrivial partition, called primitive groups, and the imprimitive
groups that do preserve a nontrivial partition. The Galois group of the 27
lines is primitive, but most known enriched Schubert problems have imprimitive
Galois groups.

Another well-understood class of enumerative problems comes from the
Bernstein-Kushnirenko Theorem [8, 49]. This gives the number of solutions to a
system of polynomial equations that are general given the monomials occurring
in the equations. Esterov [24] determined which of these problems have fully
symmetric Galois group and showed that all others have an imprimitive Galois
group. Here, too, the inverse Galois problem remains open. We discuss this in
Section 4.

The problem of lines on a cubic surface is the first in the class of Fano
problems, which involve counting the number of linear subspaces that lie on a
general complete intersection in projective space. Recently, Hashimoto and
Kadets [32] nearly determined the Galois groups of all Fano problems. Most are
at least alternating, except for the lines on a cubic surface and the
$r$-planes lying on the intersection of two quadrics in ${\mathbb{P}}^{2r+2}$.
We explain this in Section 3, and discuss computations which show that several
small Fano problems are full-symmetric.

Branched covers arise from families of polynomial systems, which are common in
the applications of mathematics. Oftentimes the application or the formulation
as a system of polynomials possesses some intrinsic structure, which is
manifested in the corresponding Galois group being enriched. In Section 7, we
discuss two occurrences of enriched Galois groups in applications and a
computational method that exploits structure in Galois groups for computing
solutions to systems of equations.

We begin in Section 1 with a general discussion of Galois groups in
enumerative geometry, and sketch some methods from numerical algebraic
geometry in Section 2. Later, in Section 5, we present methods, both numerical
and symbolic, to compute and study Galois groups in enumerative geometry.

##  1\. Galois groups of branched covers

We will let ${\Bbbk}$ be a field with algebraic closure $\overline{{\Bbbk}}$.
We adopt standard terminology from algebraic geometry: An affine (projective)
scheme ${\mathcal{V}}(F)$ is defined in ${\mathbb{A}}^{n}$
(${\mathbb{P}}^{n}$) by polynomials (homogeneous forms)
$F=(f_{1},\dotsc,f_{m})$ in $n$ ($n{+}1$) variables with coefficients in
${\Bbbk}$. We will call the collection $F$ a system (of equations) and say the
isolated points of ${\mathcal{V}}(F)$ (over $\overline{{\Bbbk}}$) are the
solutions to $F$. The affine scheme ${\mathcal{V}}(F)$ is a variety when every
irreducible component of ${\mathcal{V}}(F)$ is reduced. We may also use
variety to refer to the underlying variety. We write $X(\overline{{\Bbbk}})$
for the points of a variety $X$ with coordinates in $\overline{{\Bbbk}}$.

Recall that the Galois group of a separable univariate polynomial
$f(x)\in{\Bbbk}[x]$ is the Galois group of the splitting field of $f$, which
is generated over ${\Bbbk}$ by the roots of $f$. Given a system $F$ of
multivariate polynomials over ${\Bbbk}$, its splitting field is the field
generated by over ${\Bbbk}$ by the coordinates of all solutions to $F$, and
its Galois group is the Galois group of this field extension.

A separable map $\pi\colon X\to Z$ of irreducible varieties is a branched
cover when $X$ and $Y$ have the same dimension and $\pi(X)$ is dense in $Z$
($\pi$ is dominant). Branched covers are ubiquitous in enumerative geometry
and in applications of algebraic geometry. When the varieties are complex,
there is a proper subvariety $B\subset Z$ (the branch locus) such that $\pi$
is a covering space over $Z{\smallsetminus}B$. We explain how to associate a
Galois/monodromy group to a branched cover and then give some background on
permutation groups, and the relation between imprimitivity of the Galois group
and decomposability of the branched cover.

###  1.1. Galois and monodromy groups of branched covers

Let $\pi\colon X\to Z$ be a branched cover. As $\pi$ is dominant, the function
field ${\Bbbk}(Z)$ of $Z$ embeds as a subfield of the function field
${\Bbbk}(X)$ of $X$. This realizes ${\Bbbk}(X)$ as a finite extension of
${\Bbbk}(Z)$ of degree $d$, the degree of $\pi$. Let $\mathbb{K}$ be the
normal closure of this extension. The Galois group of the branched cover
$\pi$, denoted $\mbox{\rm Gal}_{\pi}$, is the Galois group of
$\mathbb{K}/{\Bbbk}(Z)$. This is a transitive subgroup of the symmetric group
$S_{d}$ that is well-defined up to conjugation.

There is also a geometric construction of $\mbox{\rm Gal}_{\pi}$. For $1\leq
s\leq d$, let $X_{Z}^{s}$ be the $s$-th fold iterated fiber product of
$\pi\colon X\to Z$,

$X_{Z}^{s}\ :=\ \underbrace{X\times_{Z}X\times_{Z}\dotsb\times_{Z}X}_{s}\,.$

The fiber of $\pi^{s}\colon X_{Z}^{s}\to Z$ over a point $z\in Z$ is the
$s$-fold Cartesian product $(\pi^{-1}(z))^{s}$ of the fiber of $\pi$ over $z$.

The fiber product has many irreducible components when $s>1$, possibly of
different dimensions. Let
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}U}\subset
Z$ be the maximal dense open subset over which $\pi$ is étale—fibers
$\pi^{-1}(z)$ for $z\in U$ are zero-dimensional reduced schemes of degree $d$.
Its complement is the branch locus $B$ of $\pi$. The big diagonal of
$X_{Z}^{s}$ is the closed subscheme consisting of $s$-tuples with a repeated
coordinate. Let
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}X_{Z}^{(s)}}$
be the closure in $X_{Z}^{s}$ of the complement of the big diagonal in
$(\pi^{s})^{-1}(U)$. The fiber of $X_{Z}^{(s)}$ over a point $z\in
U(\overline{{\Bbbk}})$ consists of $s$-tuples of distinct points of the fiber
$\pi^{-1}(z)$.

When $s=d$, the symmetric group $S_{d}$ acts on $X_{Z}^{(d)}$, permuting each
$d$-tuple. It permutes the irreducible components and acts simply transitively
on the fiber above a point $z\in U(\overline{{\Bbbk}})$. Let
$X^{\prime}\subset X_{Z}^{(d)}$ be an irreducible component (they are all
isomorphic when $s=d$).

We compare this to the construction of the splitting field of a univariate
polynomial. Replacing $X$ and $Z$ by appropriate affine open subsets, we may
embed $X$ as a hypersurface in $Z\times{\mathbb{A}}^{1}_{t}$ with $X\to Z$ the
projection. Writing ${\Bbbk}[X]$ and ${\Bbbk}[Z]$ for their coordinate rings,
there is a monic irreducible polynomial
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}f}\in{\Bbbk}[Z][t]$
of degree $d$ such that ${\Bbbk}[X]={\Bbbk}[Z][t]/\langle f\rangle$. Thus
${\Bbbk}(X)={\Bbbk}(Z)[t]/\langle f\rangle={\Bbbk}(Z)(\alpha)$, where $\alpha$
is the image of $t$ in ${\Bbbk}[X]$. If $X^{\prime}$ is an irreducible
component of $X_{Z}^{(d)}$, then
${\Bbbk}(X^{\prime})={\Bbbk}(Z)(\alpha_{1},\dotsc,\alpha_{d})$ where
$\alpha_{i}\in{\Bbbk}[X^{\prime}]$ is given by the composition of inclusion
$X^{\prime}\subset X^{(d)}_{Z}$, the $i$th coordinate projection
$X^{(d)}_{Z}\to X$, and the function $\alpha$. As $i\neq
j\Rightarrow\alpha_{i}\neq\alpha_{j}$ ($X^{\prime}$ does not lie in the big
diagonal), we see that $\alpha_{1},\dotsc,\alpha_{d}$ are the roots of $f$ in
${\Bbbk}(X^{\prime})$. Thus ${\Bbbk}(X^{\prime})$ is the splitting field of
$f$ and Galois over ${\Bbbk}(Z)$.

The monodromy group $\mbox{\rm Mon}_{\pi}$ of the branched cover is the
subgroup of $S_{d}$ that preserves $X^{\prime}$. Elements of $\mbox{\rm
Mon}_{\pi}$ are automorphisms of the extension
${\Bbbk}(X^{\prime})/{\Bbbk}(Z)$ so that $\mbox{\rm Mon}_{\pi}\subset\mbox{\rm
Gal}({\Bbbk}(X^{\prime})/{\Bbbk}(Z))$, the Galois group of
${\Bbbk}(X^{\prime})/{\Bbbk}(Z)$. Since $\mbox{\rm Mon}_{\pi}$ acts simply
transitively on fibers of $X^{\prime}\to Z$ above points in
$U(\overline{{\Bbbk}})$, its order is the degree of the map $X^{\prime}\to Z$,
which is the order of the field extension ${\Bbbk}(X^{\prime})/{\Bbbk}(Z)$.
Hence we arrive at the result $\mbox{\rm Mon}_{\pi}=\mbox{\rm
Gal}({\Bbbk}(X^{\prime})/{\Bbbk}(Z))$.

######  Theorem 1 (Galois equals monodromy).

For a branched cover $\pi\colon X\to Z$ defined over a field ${\Bbbk}$, the
Galois group is equal to the monodromy group,

$\mbox{\rm Gal}_{\pi}\ =\ \mbox{\rm Mon}_{\pi}\,.$

The enumerative problem of 27 lines on a cubic surface has a corresponding
incidence variety (1) which is a branched cover, and its Galois/monodromy
group is a special case of the results of this section. Incidence varieties of
enumerative problems typically are branched covers and therefore have Galois
groups as we will see throughout this survey.

We make an important observation. While the Galois group of a branched cover
$\pi\colon X\to Z$ is defined via a geometric construction, it does depend
upon the field of definition. For example, consider the branched cover
$\pi\colon{\mathbb{A}}^{1}\to{\mathbb{A}}^{1}$ given by $x\mapsto x^{3}$.
Assume that ${\Bbbk}$ does not have characteristic 3, for otherwise $\pi$ is
inseparable. Over the rational numbers, that is
$\pi\colon{\mathbb{A}}^{1}({\mathbb{Q}})\to{\mathbb{A}}^{1}({\mathbb{Q}})$, it
has Galois group $S_{3}$, but over any field containing $\sqrt{-3}$ (e.g. $-3$
is a square in ${\Bbbk}$) its Galois group is
$A_{3}={\mathbb{Z}}/3{\mathbb{Z}}$. This is because the discriminant of the
cubic $x^{3}-t$ defining $\pi$ is $-27t^{2}$, which is a square only in fields
containing $\sqrt{-3}$. When necessary, we write $\mbox{\rm
Gal}_{\pi}({\Bbbk})$ to indicate that the branched cover is defined over
${\Bbbk}$.

If $\pi\colon X\to Z$ is a branched cover defined over ${\Bbbk}$ and
$\mathbb{F}/{\Bbbk}$ is any field extension, $\mbox{\rm
Gal}_{\pi}(\mathbb{F})$ is isomorphic to the subgroup of $\mbox{\rm
Gal}_{\pi}({\Bbbk})$ corresponding to the extension $\mathbb{K}/\mathbb{E}$,
where $\mathbb{K}$ is the normal closure of ${\Bbbk}(X)/{\Bbbk}(Z)$ and
$\mathbb{E}=\mathbb{K}\cap\mathbb{F}(Z)$.

###  1.2. Complex branched covers

Suppose that $\pi\colon X\to Z$ is a branched cover of complex varieties. Then
the étale locus $U\subset Z$ is the open subset that is maximal with respect
to inclusion such that the restriction $\pi\colon\pi^{-1}(U)\to U$ is a
covering space. We will also call $U$ the set of regular values of $\pi$.

The monodromy group $\mbox{\rm Mon}_{\pi}$ as defined in Section 1.1 agrees
with the usual notion of the monodromy group of the covering space

$\pi\ \colon\ \pi^{-1}(U)\ \longrightarrow\ U\,.$

This is the group of permutations of a fiber $\pi^{-1}(z)$ obtained by lifting
loops in $U$ that are based at $z$ to paths in $\pi^{-1}(U)$ that connect
points in the fiber. If $d$ is the degree of $\pi$, lifting based loops in $U$
to paths in a component $X^{\prime}$ of $X_{Z}^{(d)}$ gives this equality. For
more on covering spaces and monodromy groups, see [33, 64].

The complement of any (Zariski) open subset $V$ of $Z$ has real codimension at
least 2. The loops in $U$ that generate the monodromy group can be chosen to
lie in $V$ (by a change of base point if necessary). A consequence is that the
monodromy group $\mbox{\rm Mon}_{\pi}$ is equal to the monodromy group of any
restriction $\pi\colon\pi^{-1}(V)\to V$ to a Zariski open set $V$ such that
this map is a covering space.

###  1.3. Enriched Galois groups

As Harris showed [31], many enumerative problems have Galois groups that are
the full symmetric group $S_{d}$ on their solutions. We call such a Galois
group/enumerative problem fully symmetric. It is a standard part of the
Algebra curriculum that any finite group may arise as the Galois group of a
branched cover. Nevertheless, determining the possible Galois groups of a
given class of enumerative problems (the inverse Galois problem for that
class), as well as the Galois group of any particular enumerative problem is
an interesting problem that is largely open.

Many techniques to study Galois groups in enumerative geometry are able to
show that the Galois group $\mbox{\rm Gal}_{\pi}$ is either $S_{d}$ or
contains its subgroup $A_{d}$ of alternating permutations. We call such an
enumerative problem/Galois group at least alternating. While many enumerative
Galois groups are at least alternating, we know of no natural enumerative
problem whose Galois group is the alternating group (besides those similar to
$x\mapsto x^{3}$).

As we saw in the problem of 27 lines, when a Galois group fails to be fully
symmetric, we expect there is a geometric reason for this failure. That is,
the set of solutions is enriched with extra structure that prevents the Galois
group from being fully symmetric. Consequently, we will call a Galois group or
enumerative problem enriched if its Galois group is not fully symmetric.

Let us recall some aspects of permutation groups. A permutation group of
degree $d$ is a subgroup $G$ of $S_{d}$. Thus $G$ has a natural action on the
set
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}[d]}:=\\{1,\dotsc,d\\}$,
as well as on the subsets of $[d]$. The group is transitive if for any
$i,j\in[d]$, there is an element $g\in G$ with $g(i)=j$. More generally, for
any $1\leq s\leq d$, $G$ is $s$-transitive if for any distinct
$i_{1},\dotsc,i_{s}\in[d]$ and distinct $j_{1},\dotsc,j_{s}\in[d]$, there is
an element $g\in G$ with $g(i_{m})=j_{m}$ for $m=1,\dotsc,s$. That is, $G$ is
$s$-transitive when it acts transitively on the set of distinct $s$-tuples of
elements of $[d]$. This has the following consequence.

######  Proposition 2.

The monodromy group $\mbox{\rm Mon}_{\pi}$ of a branched cover $\pi\colon X\to
Z$ is $s$-transitive if and only if the variety $X_{Z}^{(s)}$ is irreducible.

Let $G$ be a transitive permutation group of degree $d$. A block of $G$ is a
subset $B\subset[d]$ such that for every $g\in G$, either $gB=B$ or $gB\cap
B=\emptyset$. The subsets $\emptyset$, $[d]$, and every singleton are blocks
of every permutation group. If these trivial blocks are the only blocks, then
$G$ is primitive and otherwise it is imprimitive.

The Galois group $E_{6}$ for the problem of 27 lines is primitive, but it is
not 2-transitive. For the latter, observe that some pairs of lines on a cubic
surface meet, while other pairs are disjoint. These incidences provide an
obstruction to 2-transitivity.

When $G$ is imprimitive, we have a factorization $d=ab$ with $1<a,b<d$ and
there is a bijection $[a]\times[b]\leftrightarrow[d]$ such that $G$ preserves
the projection $[a]\times[b]\to[b]$. That is, the fibers
$\\{[a]\times\\{i\\}\mid i\in[b]\\}$ are blocks of $G$ and its action on this
set of blocks gives a homomorphism $G\to S_{b}$ with transitive image. In
particular, $G$ is a subgroup of the group of permutations of
$[d]=[a]\times[b]$ which preserve the fibers of the projection
$[a]\times[b]\to[b]$. This group is the wreath product $S_{a}\wr S_{b}$, which
is the semi-direct product $(S_{a})^{b}\rtimes S_{b}$, where $S_{b}$ acts on
$(S_{a})^{b}$ by permuting factors.

Imprimitivity has a geometric manifestation. A branched cover $\pi\colon X\to
Z$ is decomposable if there is a nonempty Zariski open subset $V\subset Z$ and
a variety $Y$ such that $\pi$ factors over $V$,

(2) $\pi^{-1}(V)\ \xrightarrow{\;\varphi\;}\ Y\ \xrightarrow{\;\psi\;}\ V\,,$

with $\varphi$ and $\psi$ both nontrivial branched covers. The fibers of
$\varphi$ over points of $\psi^{-1}(v)$ are blocks of the action of $\mbox{\rm
Gal}_{\pi}$ on $\pi^{-1}(v)$, which implies that $\mbox{\rm Gal}_{\pi}$ is
imprimitive. Pirola and Schlesinger [66] observed that decomposability of
$\pi$ is equivalent to imprimitivity of $\mbox{\rm Gal}_{\pi}$.

######  Proposition 3.

A branched cover is decomposable if and only if its Galois group is
imprimitive.

Harris’s geometric method to show that a Galois group of an enumerative
problem over ${\mathbb{C}}$ is fully-symmetric involves two steps. First, show
that $X_{Z}^{(2)}$ is irreducible, so that $\mbox{\rm Mon}_{\pi}$ is
2-transitive. Next, identify an instance of the enumerative problem (a point
$z\in Z$) with $d{-}1$ solutions, where exactly one solution has multiplicity
2. This implies that a small loop in $Z$ around $z$ induces a simple
transposition in $\mbox{\rm Mon}_{\pi}$. This implies that $\mbox{\rm
Mon}_{\pi}=S_{d}$, as $S_{d}$ is its only 2-transitive subgroup containing a
simple transposition. Jordan [43] gave a useful generalization of this last
fact about $S_{d}$, which we use in Section 5.

######  Proposition 4.

Suppose that $G\subset S_{d}$ is a permutation group. If $G$ is primitive and
contains a $p$-cycle for some prime number $p<d{-}2$, then $G$ is at least
alternating.

If $G$ contains a $d$-cycle, a $d{-}1$-cycle, and a $p$-cycle for some prime
number $p<d{-}2$ then $G=S_{d}$.

##  2\. Numerical Algebraic Geometry

Methods from numerical analysis underlie algorithms that readily solve systems
of polynomial equations. Numerical algebraic geometry uses this to represent
and study algebraic varieties on a computer. We sketch some of its fundamental
algorithms, which will later be used for studying Galois groups.

###  2.1. Homotopy continuation

When ${\Bbbk}={\mathbb{C}}$, solutions to enumerative problems, fibers of
branched covers, and monodromy are all effectively computed using algorithms
based on numerical homotopy continuation. This begins with a homotopy, which
is a family ${\mathcal{H}}(x;t)$ of systems of polynomials that interpolate
between the systems at $t=0$ and $t=1$ in a particular way: We require that
the variety
${\mathcal{V}}({\mathcal{H}}(x;t))\subset{\mathbb{C}}^{n}_{x}\times{\mathbb{C}}_{t}$
contains a curve $C$ that is the union of the 1-dimensional irreducible
components of ${\mathcal{V}}({\mathcal{H}})$ which project dominantly to
${\mathbb{C}}_{t}$. We further require that $1\in{\mathbb{C}}_{t}$ is a
regular value of the projection $\pi\colon C\to{\mathbb{C}}_{t}$, that $\pi$
is proper near $1$, and that ${\mathcal{V}}({\mathcal{H}}(x;t))$ is smooth at
all points of the fiber
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}W}:=\pi^{-1}(1)$.
The start system is ${\mathcal{H}}(x;1)$ and write $W$ for its set of isolated
solutions, which we assume are known. The target system is
${\mathcal{H}}(x;0)$ and we wish to use ${\mathcal{H}}$ to compute the
isolated solutions to the target system.

Given a homotopy ${\mathcal{H}}(x;t)$, we restrict $C$ to the points above an
arc $\gamma\subset{\mathbb{C}}_{t}$ with endpoints $\\{0,1\\}$ such that
$\gamma$ avoids the critical values of $\pi\colon C\to{\mathbb{C}}_{t}$,
except possibly at $t=0$. In what follows, we will take $\gamma$ to be the
interval $[0,1]$, for simplicity. This restriction is a collection of arcs in
$C$, one for each point of $W$, which start at points of $W$ at $t=1$ and lie
above $(0,1]$. Some arcs may be unbounded near $t=0$, while the rest end in
points of $\pi^{-1}(0)$, and all points of $\pi^{-1}(0)$ are reached.
Beginning with the (known) points of $W$, standard path-tracking algorithms
[1] from numerical analysis may follow these arcs and compute the points of
$\pi^{-1}(0)$. When $\pi\colon C\to{\mathbb{C}}_{t}$ is proper near $t=0$ and
smooth above $t=0$, there are $|W|$ points in $\pi^{-1}(0)$ so that each path
gives a point of $\pi^{-1}(0)$. In this case, the homotopy is optimal. For
more on numerical homotopy continuation, see [58, 79].

The most straightforward optimal homotopy is a parameter homotopy [55, 59], in
which the structure and number of solutions of the start, target, and
intermediate systems are the same. A source for parameter homotopies is a
branched cover $X\to Z$, where $Z$ is a rational variety and $X$ is a
subvariety of ${\mathbb{C}}^{n}\times Z$. Suppose that
$f\colon{\mathbb{C}}_{t}\to Z$ is a rational curve with $f(0)$ and $f(1)$
lying in the open set $U$ of regular values of $X\to Z$. Pulling back $X\to Z$
along $f$ gives a dominant map
$\pi\colon{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}f^{*}(X)}\to{\mathbb{C}}_{t}$
with the same degree $d$ as $X\to Z$. A generating set ${\mathcal{H}}(x;t)$ of
the ideal of $f^{*}(X)\subset{\mathbb{C}}^{n}\times{\mathbb{C}}_{t}$ gives a
homotopy that is optimal as there are $d$ solutions to both the start and
target systems.

For example, suppose that $X\to Z={\mathbb{P}}^{19}$ is the branched cover (1)
from the problem of 27 lines. Given smooth cubics $f_{1}$ and $f_{0}$, the
pencil
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}f(t)}:=tf_{1}+(1-t)f_{0}$
is a map ${\mathbb{C}}_{t}\to{\mathbb{P}}^{19}$ as above. A general line
$\ell$ in ${\mathbb{P}}^{3}$ is the span of points $[x_{1},x_{2},1,0]$ and
$[x_{3},x_{4},0,1]$, for $(x_{1},x_{2},x_{3},x_{4})\in{\mathbb{C}}^{4}$. A
general point on $\ell$ has the form $[ux_{1}+x_{3},xu_{2}+x_{4},u,1]$, for
$u\in{\mathbb{C}}$, and $\ell$ lies on the cubic ${\mathcal{V}}(f(t))$ when
$f(t)(ux_{1}+x_{3},xu_{2}+x_{4},u,1)$ is identically zero. Thus, if we expand
$f(t)(ux_{1}+x_{3},xu_{2}+x_{4},u,1)$ as a polynomial in $u$, the four
coeffcients of the resulting cubic are equations in $x_{1},\dotsc,x_{4},t$ for
the general line $\ell$ to lie on the cubic ${\mathcal{V}}(f(t))$. Let
${\mathcal{H}}(x;t)$ be these four coefficients. When ${\mathcal{V}}(f_{1})$
has 27 lines of the given form, this is a homotopy, and if we knew the
coordinates of those 27 lines, numerical homotopy continuation using
${\mathcal{H}}(x;t)$ could be used to compute the lines on
${\mathcal{V}}(f_{0})$.

###  2.2. Witness sets

Numerical homotopy continuation enables the reliable computation of solutions
to systems of polynomial equations. Numerical algebraic geometry uses this
ability to solve as a basis for algorithms that study and manipulate varieties
on a computer. Its starting point is a witness set, which is a data structure
for varieties in ${\mathbb{C}}^{n}$ [77, 78]. Suppose that
$X\subset{\mathbb{C}}^{n}$ is a union of irreducible components of the same
dimension $m$ of a variety ${\mathcal{V}}(F)$, where $F$ is a system of
polynomials. If $L\subset{\mathbb{C}}^{n}$ is a general linear subspace of
codimension $m$, then
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}W}:=X\cap
L$ is a transverse intersection consisting of $\deg(X)$ points, called a
linear section of $X$. The triple $(W,F,L)$ is a witness set for $X$
(typically, $L$ is represented by $m$ linear forms).

Given a witness set $(W,F,L)$ for $X$ and a general codimension $m$ linear
subspace $L^{\prime}$, we may compute the linear section $W^{\prime}=X\cap
L^{\prime}$ and obtain another witness set $(W^{\prime},F,L^{\prime})$ for $X$
as follows. Let $L(t):=tL+(1-t)L^{\prime}$ be the convex combination of (the
equations for) $L$ and $L^{\prime}$, and form the homotopy
${\mathcal{H}}(x;t):=(F,L(t))$. Path-tracking using ${\mathcal{H}}(x;t)$
starting from the points of $W$ at $t=1$ will compute the points of
$W^{\prime}$ at $t=0$. This instance of the parameter homotopy is called
“moving the witness set”.

Suppose that we have a third codimension $m$ linear subspace
$L^{\prime\prime}$. We may then use $W^{\prime}$ to compute the linear section
$W^{\prime\prime}=X\cap L^{\prime\prime}$, and then use $W^{\prime\prime}$ to
return to $W$. The arcs connect every point $w\in W$ to a point $w^{\prime}\in
W^{\prime}$, then to a point $w^{\prime\prime}\in W^{\prime\prime}$, and
finally to a possibly different point $\sigma(w)\in W$. This defines a
permutation $\sigma$ of $W$. The four points, as they are connected by smooth
arcs, lie in the same irreducible component of $X$. Thus the cycles in the
permutation $\sigma$ refine the partition of $W$ given by the irreducible
components of $X$. Repeating this procedure with possible different linear
subspaces $L^{\prime},L^{\prime\prime}$, and then applying the trace test [53,
76], leads to a numerical irreducible decomposition of $X$; that is, it
computes the partition $W=W_{1}\sqcup W_{2}\sqcup\dotsb\sqcup W_{r}$, where
$X_{1},\dotsc,X_{r}$ are the irreducible components of $X$ and
$W_{i}:=X_{i}\cap L$. This algorithm was developed in [74, 75, 76].

Several freely available software packages have implementations of the basic
algorithms of Numerical Algebraic Geometry. These include Macaulay 2 [30] in
its Numerical Algebraic Geometry package [52], in Bertini [5], and in
HomotopyContinuation.jl [10].

##  3\. Fano Problems

Debarre and Manivel determined the dimension and degree of the variety of
$r$-planes lying on general complete intersections in ${\mathbb{P}}^{n}$. When
this is zero-dimensional it is called a Fano problem. For example, the problem
of 27 lines is a Fano problem. Galois groups of Fano problems were studied
classically by Jordan and Harris and recently by Hashimoto and Kadets, who
nearly determined the Galois group for each Fano problem.

###  3.1. Combinatorics of Fano Problems

Let ${\mathbb{G}}(r,{\mathbb{P}}^{n})$ be the Grassmann variety defined over
the complex numbers of $r$-dimensional linear subspaces of ${\mathbb{P}}^{n}$,
which has dimension $(r{+}1)(n{-}r)$. Given a variety
$X\subseteq{\mathbb{P}}^{n}$, its Fano scheme is the subscheme of
${\mathbb{G}}(r,{\mathbb{P}}^{n})$ of $r$-planes lying on $X$.

Fano schemes may be studied uniformly when $X\subset{\mathbb{P}}^{n}$ is a
complete intersection. For this, let
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}d_{\bullet}}:=(d_{1},\dotsc,d_{s})$
be a weakly increasing list of integers greater than 1. Suppose that
$F=(f_{1},\dotsc,f_{s})$ are homogeneous polynomials on ${\mathbb{P}}^{n}$
with $f_{i}$ of degree $d_{i}$. Let ${\mathcal{V}}_{r}(F)$ be the Fano scheme
of $r$-planes in ${\mathcal{V}}(F)$.

Just as ${\mathcal{V}}(F)$ has expected dimension $n{-}s$, there is an
expected dimension for ${\mathcal{V}}_{r}(F)$. Let $f$ be a form on
${\mathbb{P}}^{n}$ of degree $d$. Its restriction to
$H\in{\mathbb{G}}(r,{\mathbb{P}}^{n})$ is a form of degree $d$ on $H$; as the
dimension of the vector space of such forms is $\binom{d+r}{r}$, we expect
this to be the codimension of ${\mathcal{V}}_{r}(f)$ in
${\mathbb{G}}(r,{\mathbb{P}}^{n})$. Thus the expected dimension of
${\mathcal{V}}_{r}(F)$ is

${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\delta}={\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\delta(r,n,d_{\bullet})}\
:=\ (r{+}1)(n{-}r)\ -\ \sum_{i=1}^{s}\binom{d_{i}+r}{r}\,.$

Write ${\mathbb{C}}^{(r,n,d_{\bullet})}$ for the vector space of homogeneous
polynomials $F=(f_{1},\dotsc,f_{s})$ in $n{+}1$ variables with $f_{i}$ of
degree $d_{i}$. Debarre and Manivel [16] showed that there is a dense open
subset
$U={\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}U_{(r,n,d_{\bullet})}}\subset{\mathbb{C}}^{(r,n,d_{\bullet})}$
with the following property: For $F\in U$, if $\delta\geq 0$ and $n-s\geq 2r$,
then ${\mathcal{V}}_{r}(F)$ is a smooth variety of dimension $\delta$, and if
$\delta<0$ or $n{-}s<2r$, then ${\mathcal{V}}_{r}(F)$ is empty. A Fano problem
is the enumerative problem of determining ${\mathcal{V}}_{r}(F)$ for $F\in
U_{(r,n,d_{\bullet})}$, when $\delta(r,n,d_{\bullet})=0$ and $n{-}s\geq 2r$.

Since the Grassmannian has Picard group generated by $O(1)$ induced by its
Plücker embedding, when $\delta\geq 0$ and $n{-}s\geq 2r$ and $F\in U$, the
Fano variety ${\mathcal{V}}_{r}(F)$ has a well-defined degree. Standard
techniques in intersection theory allow this degree to be computed, using that
${\mathcal{V}}_{r}(F)$ is the vanishing of sections of appropriate vector
bundles on ${\mathbb{G}}(r,{\mathbb{P}}^{n})$. (These are
$\mbox{Sym}_{d_{i}}(T)$, where $T$ is the dual of the tautological
$(r{+}1)$-subbundle on the Grassmannian.)

This leads to a formula for this degree. For that, define the polynomials

${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}Q_{r,d}(x)}\
=\
\prod_{a_{0}+\dotsb+a_{r}=d}(a_{0}x_{0}+\dotsb+a_{r}x_{r})\in{\mathbb{Z}}[x_{0},\dotsc,x_{r}]\
\quad a_{i}\in\mathbb{Z}_{\geq 0}$

as well as $Q_{r,d_{\bullet}}=Q_{r,d_{1}}(x)\dotsb Q_{r,d_{s}}(x)$ and the
Vandermonde polynomial

$\mbox{V}_{r}(x)\ =\ \prod_{0\leq i<j\leq r}(x_{i}-x_{j})\,.$

When $\delta(r,n,d_{\bullet})=0$, $n-s\geq 2r$, and $F\in
U_{(r,n,d_{\bullet})}$, the degree $\deg(r,n,d_{\bullet})$ of
${\mathcal{V}}_{r}(F)$ is the coefficient of $x_{0}^{n}x_{1}^{n-1}\dotsb
x_{r}^{n-r}$ in the product $Q_{r,d_{\bullet}}(x)\mbox{V}_{r}(x)$ [16, Thm.
4.3]. Table 1 gives these degrees for all Fano problems with a small number of
solutions.

Table 1. Small finite Fano problems $r$ | $n$ | $d_{\bullet}$ |  $\\#$ of solutions | Galois Group
---|---|---|---|---
1 | 4 | $(2,2)$ | 16 | $D_{5}$
1 | 3 | $(3)$ | 27 | $E_{6}$
2 | 6 | $(2,2)$ | 64 | $D_{7}$
3 | 8 | $(2,2)$ | 256 | $D_{9}$
1 | 7 | $(2,2,2,2)$ | 512 | $S_{512}$
1 | 6 | $(2,2,3)$ | 720 | $S_{720}$
2 | 8 | $(2,2,2)$ | 1024 | $S_{1024}$
1 | 5 | $(3,3)$ | 1053 | $S_{1053}$

###  3.2. Galois groups of Fano problems

Consider the incidence correspondence,

$\Gamma:=\\{(F,H)\in{\mathbb{C}}^{(r,n,d_{\bullet})}\times{\mathbb{G}}(r,{\mathbb{P}}^{n})\,\mid\,F|_{H}=0\\}$.$\pi$${\mathbb{C}}^{(r,n,d_{\bullet})}$

The fiber over a general complete intersection $F\in U_{(r,n,d_{\bullet})}$ is
the Fano variety ${\mathcal{V}}_{r}(F)$. When we have a Fano problem,
$\delta(r,n,d_{\bullet})=0$ and $n-s\geq 2r$, $\pi$ is a branched cover of
degree $\deg(r,n,d_{\bullet})$. We define the Galois group of the Fano problem
to be
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mbox{\rm
Gal}_{(r,n,d_{\bullet})}=\mbox{\rm Gal}_{\pi}}$.

The study of Galois groups of Fano problems began with Jordan [43] with the
problem of 27 lines on a smooth cubic surface, which has data $(1,3,(3))$. By
observing the incidence structure of the lines on a smooth cubic, Jordan
determined that the Galois group over ${\mathbb{C}}$ is a subgroup of $E_{6}$,
$\mbox{\rm Gal}_{(1,3,(3))}\subseteq E_{6}$.

Harris [31] showed that Jordan’s inclusion is an equality, $\mbox{\rm
Gal}_{(1,3,(3))}=E_{6}$, and then generalized this, showing that $\mbox{\rm
Gal}_{(1,n,(2n-3))}$ is fully symmetric for $n\geq 4$. For this, he used the
interpretation of the Galois group as a monodromy group. Using arguments from
algebraic geometry, when $n\geq 4$ he showed that the monodromy group is
2-transitive and contains a simple transposition.

Hashimoto and Kadets [32] recently revisited this topic, determining these
groups in many cases. There are two special cases of finite Fano problems,
that of lines on a cubic surface and that of linear spaces on the intersection
of two quadrics. Hashimoto and Kadets showed that these problems are enriched
and that

$\mbox{\rm Gal}_{(1,3,(3))}\ =\ E_{6}\qquad\mbox{and}\qquad\mbox{\rm
Gal}_{(r,2r+2,(2,2))}\ =\ W(D_{2r+3})\,.$

The enriched Galois structure is reflected in that these are the only Fano
problems where the $r$-planes on ${\mathcal{V}}(F)$ will intersect. As in the
problem of 27 lines, the generic incidence structure prevents the Galois group
from being fully symmetric. In all other cases, they showed that the Galois
group is at least alternating. In Section 5.2, we describe a method based on
numerical homotopy continuation to compute monodromy permutations, when
${\Bbbk}={\mathbb{C}}$. We used this to show that some small Fano problems
have full symetric Galois groups.

######  Theorem 5.

Each of the Fano problems

$(1,7,(2,2,2,2))\,,\ (1,6,(2,2,3))\,,\ (2,8,(2,2,2,2))\,,\ \mbox{and}\
(1,5,(3,3))\,,$

has full symmetric Galios group.

##  4\. Galois groups of sparse polynomial equations

We work over the complex numbers. With modifications due to separability, much
of this holds over an arbitrary field. However, a key argument in Esterov’s
proof for Theorem 7 uses that the field is uncountable, together with
topological properties of ${\mathbb{C}}$.

The Bernstein-Kuchnirenko Theorem gives an upper bound on the number of
solutions in the algebraic torus $({\mathbb{C}}^{\times})^{n}$ to a system of
polynomials. This bound depends on the monomials which appear in the equations
(their support). When the equations are general given their support, this
bound is attained. The family of all systems with a given support forms a
branched cover and therefore has a Galois group. Esterov identified two
structures in the support which imply that the Galois group is imprimitive,
and showed that if they are not present, then the Galois group is full
symmetric. It remains an open problem to determine the Galois group when it is
imprimitive.

###  4.1. Systems of sparse polynomial equations

A (Laurent) monomial in $n$ variables $x_{1},\dotsc,x_{n}$ with exponent
vector $\alpha=(\alpha_{1},\dotsc,\alpha_{n})\in{\mathbb{Z}}^{n}$ is

${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}x^{\alpha}}\
:=\ x_{1}^{\alpha_{1}}x_{2}^{\alpha_{2}}\dotsb x_{n}^{\alpha_{n}}\,.$

This is a character of the algebraic torus $({\mathbb{C}}^{\times})^{n}$. A
(Laurent) polynomial $f$ over ${\mathbb{C}}$ is a linear combination of
monomials,

$f\ =\ \sum c_{\alpha}x^{\alpha}\qquad c_{\alpha}\in{\mathbb{C}}\,.$

For a nonempty finite set ${\mathcal{A}}\subseteq{\mathbb{Z}}^{n}$, the space
of polynomials supported on ${\mathcal{A}}$ is written
${\mathbb{C}}^{\mathcal{A}}$. This is the set of polynomials $f$ such that
$c_{\alpha}\neq 0$ implies $\alpha\in{\mathcal{A}}$.

Given a collection
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\mathcal{A}}_{\bullet}}=({\mathcal{A}}_{1},{\mathcal{A}}_{2},\dotsc,{\mathcal{A}}_{n})$
of nonempty finite subsets of ${\mathbb{Z}}^{n}$, write

${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\mathbb{C}}^{{\mathcal{A}}_{\bullet}}}\
:=\
{\mathbb{C}}^{{\mathcal{A}}_{1}}\times\dotsb\times{\mathbb{C}}^{{\mathcal{A}}_{n}}$

for the vector space of $n$-tuples $F=(f_{1},\dotsc,f_{n})$ of polynomials,
where $f_{i}$ has support ${\mathcal{A}}_{i}$, for each $i=1,\dotsc,n$. An
element $F\in{\mathbb{C}}^{{\mathcal{A}}_{\bullet}}$ is a square system of
polynomials whose solutions are those $x\in({\mathbb{C}}^{\times})^{n}$ such
that

$f_{1}(x_{1},\dotsc,x_{n})\ =\ f_{2}(x_{1},\dotsc,x_{n})\ =\ \dotsb\ =\
f_{n}(x_{1},\dotsc,x_{n})\ =\ 0\,,$

written $F(x)=0$. We call $F$ a sparse polynomial system with support
${\mathcal{A}}_{\bullet}$.

Given supports
${\mathcal{A}}_{\bullet}=({\mathcal{A}}_{1},\dotsc,{\mathcal{A}}_{n})$, define
the incidence variety

$\Gamma={\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\Gamma_{{\mathcal{A}}_{\bullet}}}\
:=\
\left\\{(F,x)\in{\mathbb{C}}^{{\mathcal{A}}_{\bullet}}\times({\mathbb{C}}^{\times})^{n}\mid
F(x)=0\right\\}\,.$

It is equipped with projections
$\pi\colon\Gamma\to{\mathbb{C}}^{{\mathcal{A}}_{\bullet}}$ and
$p\colon\Gamma\to({\mathbb{C}}^{\times})^{n}$. The fiber $p^{-1}(x)$ for
$x\in({\mathbb{C}}^{\times})^{n}$ is the set of all polynomials
$(f_{1},\dotsc,f_{n})$ with $f_{i}(x)=0$ for each $i$. Observing that
$f_{i}(x)=0$ is a non-zero linear equation on
${\mathbb{C}}^{{\mathcal{A}}_{i}}$, we see that
$p^{-1}(x)\subset{\mathbb{C}}^{{\mathcal{A}}_{\bullet}}$ is the product of $n$
hyperplanes and thus has codimension $n$. Consequently,
$\Gamma\to({\mathbb{C}}^{\times})^{n}$ is a vector bundle, and therefore
irreducible, and it has dimension equal to
$\dim{\mathbb{C}}^{{\mathcal{A}}_{\bullet}}$.

Thus the map $\pi\colon\Gamma\to{\mathbb{C}}^{{\mathcal{A}}_{\bullet}}$ is a
branched cover when $\pi$ is dominant, equivalently, when a generic system
$F\in{\mathbb{C}}^{{\mathcal{A}}_{\bullet}}$ has a positive, finite number of
solutions in $({\mathbb{C}}^{\times})^{n}$. The number of solutions to a
generic system is determined by the polyhedral geometry of its support, which
we review. For convex bodies $K_{1},\dotsc,K_{n}\subset{\mathbb{R}}^{n}$ and
nonnegative real numbers, $t_{1},\dotsc,t_{n}\in{\mathbb{R}}_{\geq 0}$,
Minkowski proved that the volume of the Minkowski sum

$t_{1}K_{1}+\dotsb+t_{n}K_{n}\ :=\ \\{t_{1}x_{1}+\dotsb+t_{n}x_{x}\mid
x_{i}\in K_{i}\\}$

is a homogeneous polynomial of degree $n$ in $t_{1},\dotsc,t_{n}$. Its
coefficient of $t_{1}\dotsb t_{n}$ is the mixed volume of
$K_{1},\dotsc,K_{n}$. For supports
${\mathcal{A}}_{\bullet}=({\mathcal{A}}_{1},\dotsc,{\mathcal{A}}_{n})$, let
$\mbox{\rm MV}({\mathcal{A}}_{\bullet})$ be the mixed volume of their convex
hulls, $\mbox{\rm conv}({\mathcal{A}}_{1}),\dotsc,\mbox{\rm
conv}({\mathcal{A}}_{n})$. This is described in detail in [26]. We state the
Bernstein-Kushnirenko Theorem [8, 48].

######  Theorem 6 (Bernstein-Kushnirenko).

A system $F\in{\mathbb{C}}^{{\mathcal{A}}_{\bullet}}$ has at most $\mbox{\rm
MV}({\mathcal{A}}_{\bullet})$ isolated solutions in
$({\mathbb{C}}^{\times})^{n}$. This bound is sharp and attained for generic
$F\in{\mathbb{C}}^{{\mathcal{A}}_{\bullet}}$.

Thus $\pi\colon
X_{{\mathcal{A}}_{\bullet}}\to{\mathbb{C}}^{{\mathcal{A}}_{\bullet}}$ is a
branched cover of degree $\mbox{\rm MV}({\mathcal{A}}_{\bullet})$ if and only
if $\mbox{\rm MV}({\mathcal{A}}_{\bullet})>0$, which Minkowski determined as
follows. For a nonempty subset
$I\subseteq{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}[n]}:=\\{1,\dotsc,n\\}$,
write
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\mathcal{A}}_{I}}:=({\mathcal{A}}_{i}\mid
i\in I)$ and let ${\mathbb{Z}}{\mathcal{A}}_{I}$ be the affine span of the
supports in ${\mathcal{A}}_{I}$. This is the free abelian group generated by
all differences $\alpha{-}\beta$ for $\alpha,\beta\in{\mathcal{A}}_{i}$ for
some $i\in I$. Then $\mbox{\rm MV}({\mathcal{A}}_{\bullet})=0$ if and only if
there exists a subset $I\subseteq[n]$ such that $|I|>\mbox{\rm
rank}({\mathbb{Z}}{\mathcal{A}}_{I})$. One direction is obvious. When
$|I|>\mbox{\rm rank}({\mathbb{Z}}{\mathcal{A}}_{I})=m$, then there is a change
of variables so that the subsystem of polynomials with indices in $I$ has more
equations than variables. In particular, $\mbox{\rm
MV}({\mathcal{A}}_{\bullet})\neq 0$ implies that
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\mathbb{Z}}{\mathcal{A}}_{\bullet}}:={\mathbb{Z}}{\mathcal{A}}_{[n]}$
has full rank $n$.

###  4.2. Galois groups of sparse polynomial systems

Suppose that ${\mathcal{A}}_{\bullet}$ is a collection of supports with
$\mbox{\rm MV}(A_{\bullet})>0$. Write $\mbox{\rm
Gal}_{{\mathcal{A}}_{\bullet}}$ for the Galois group of the corresponding
branched cover
$\pi\colon\Gamma_{{\mathcal{A}}_{\bullet}}\to{\mathbb{C}}^{{\mathcal{A}}_{\bullet}}$.
Esterov [24] studied these groups, identifying two structures which imply that
$\mbox{\rm Gal}_{{\mathcal{A}}_{\bullet}}$ is imprimitive.

We call ${\mathcal{A}}_{\bullet}$ lacunary if
${\mathbb{Z}}{\mathcal{A}}_{\bullet}\neq{\mathbb{Z}}^{n}$. If $\mbox{\rm
MV}({\mathcal{A}}_{\bullet})>[{\mathbb{Z}}^{n}\colon{\mathbb{Z}}{\mathcal{A}}_{\bullet}]$,
then it is strictly lacunary. Lacunary systems generalize the following
example. Let $n=1$ and suppose that we have a univariate polynomial $f(x)$ of
the form $g(x^{3})$, for $g$ a univariate polynomial with $g(0)\neq 0$.
Observe that ${\mathbb{Z}}{\mathcal{A}}_{\bullet}\subset 3{\mathbb{Z}}$. The
zeroes of $f$ ($\\{x\in{\mathbb{C}}\mid f(x)=0\\}$) are cube roots of the
zeroes of $g$, and the group of cubic roots of unity acts freely on the zeroes
of $f$. These orbits are blocks of the action of the Galois group of $f$. When
$g$ has two or more roots, there is more than one orbit, and the action of the
Galois group is imprimitive.

We call ${\mathcal{A}}_{\bullet}$ triangular if there exists a nonempty proper
subset $I\subsetneq[n]$ such that $\mbox{\rm
rank}({\mathbb{Z}}{\mathcal{A}}_{I})=|I|$. In this case there is a change of
variables so that the equations indexed by $I$ involve only the first $|I|$
variables. We write $\mbox{\rm MV}({\mathcal{A}}_{I})$ for the mixed volume of
the supports of the polynomials indexed by $I$ as polynomials in the first
$|I|$ variables. We say ${\mathcal{A}}_{\bullet}$ is strictly triangular if
$1<\mbox{\rm MV}({\mathcal{A}}_{I})<\mbox{\rm MV}({\mathcal{A}}_{\bullet})$.

Strictly triangular systems generalize the following example. Let $n=2$ and
write our variables as $(y,z)$ and suppose that we have a system $F$ of the
form $f(y)=g(y,z)=0$, where $\deg(f)$, $\deg_{z}(g)$ are both at least 2.
(Here, $\deg_{z}(g)$ is the degree of $g$ as a polynomial in $z$.) Since the
first coordinate of a solution $(y^{*},z^{*})$ of $F$ is a solution of $f$,
the action of the Galois group of $F$ has blocks given by the fibers of the
projection to the first coordinate. When $f$ and $g$ are general given their
supports, there are $\deg(f)$ blocks, each of size $\deg_{z}(g)$, and the
action of the Galois group is imprimitive.

We provide more details in Section 7. This is explained fully in [24], and
algorithmically in [12, Sect. 2.3]. When ${\mathcal{A}}_{\bullet}$ is neither
lacunary nor strictly triangular, Esterov showed that $\mbox{\rm
Gal}_{{\mathcal{A}}_{\bullet}}$ is 2-transitive using that a countable union
of subvarieties is nowhere dense. Then, he showed that a small loop around the
discriminant of these systems generates a simple transposition, which shows
that $\mbox{\rm Gal}_{{\mathcal{A}}_{\bullet}}$ is full symmetric.

######  Theorem 7 (Esterov).

Let ${\mathcal{A}}_{\bullet}$ be a set of supports with $\mbox{\rm
MV}({\mathcal{A}}_{\bullet})>0$. If ${\mathcal{A}}_{\bullet}$ is neither
strictly lacunary nor strictly triangular, then $\mbox{\rm
Gal}_{{\mathcal{A}}_{\bullet}}$ is the full symmetric group. If
${\mathcal{A}}_{\bullet}$ is strictly lacunary or strictly triangular, then
$\mbox{\rm Gal}_{{\mathcal{A}}_{\bullet}}$ is imprimitive. If
${\mathcal{A}}_{\bullet}$ is lacunary but not strictly lacunary, then
$\mbox{\rm Gal}_{{\mathcal{A}}_{\bullet}}$ is the group $\mbox{\rm
Hom}({\mathbb{Z}}^{n}/{\mathbb{Z}}{\mathcal{A}}_{\bullet},{\mathbb{C}}^{\times})$
of roots of unity.

When ${\mathcal{A}}_{\bullet}$ is either strictly lacunary or strictly
triangular, Esterov’s theorem does not determine the group $\mbox{\rm
Gal}_{{\mathcal{A}}_{\bullet}}$ explicitly. As it is imprimitive, the Galois
group $\mbox{\rm Gal}_{{\mathcal{A}}_{\bullet}}$ is a subgroup of a certain
wreath product. It may be a proper subgroup, as the following example shows.

######  Example 8.

Let $n=2$ and suppose that ${\mathcal{A}}$ is consists of the vertices of the
$2\times 2$ square and its center point $(1,1)$, which we show below.

Let ${\mathcal{A}}_{\bullet}:=({\mathcal{A}},{\mathcal{A}})$. Its mixed volume
is $\mbox{\rm MV}({\mathcal{A}}_{\bullet})=8$, which is twice the area of the
square. Thus a general system of polynomials with support
${\mathcal{A}}_{\bullet}$ has eight solutions in
$({\mathbb{C}}^{\times})^{n}$. The lattice
${\mathbb{Z}}{\mathcal{A}}_{\bullet}$ has index 2 in ${\mathbb{Z}}^{2}$, so
solutions come in four pairs of symmetric points, $(x,y)$ and $(-x,-y)$. These
pairs are preserved by the Galois group, showing that it is a subgroup of the
wreath product $S_{2}\wr S_{4}$. It can be shown that $\mbox{\rm
Gal}_{{\mathcal{A}}_{\bullet}}=(S_{2}\wr S_{4})\cap A_{8}$ and is thus a
proper subgroup of this wreath product. $\diamond$

This example is due to Esterov and Lang [25], who gave conditions which imply
that the Galois group is the full wreath product, for certain lacunary
systems. Despite this, there is no known criteria for when that occurs, not
even a conjecture about which groups can occur as Galois groups of sparse
polynomial systems. Also, it is not clear what can be said about Galois groups
of sparse polynomials over other fields than the complex numbers.

##  5\. Computing Galois Groups

Understanding Galois groups of enumerative problems has both benefited from
and inspired the development of and use of computational tools. We discuss an
adaptation of the well-known symbolic method of computing cycle types of
Frobenius elements and then several methods based on numerical homotopy
continuation. For a prime $p\in{\mathbb{Z}}$, write
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\mathbb{F}}_{p}}={\mathbb{Z}}/p{\mathbb{Z}}$
for the field with $p$ elements.

###  5.1. Frobenius elements

Let $f\in{\mathbb{Z}}[x]$ be a monic irreducible univariate polynomial and
$\mathbb{K}$ its splitting field, a finite Galois extension of ${\mathbb{Q}}$.
Let
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\mathcal{O}}}\subset\mathbb{K}$
be those elements that are integral over ${\mathbb{Z}}$. For every prime
$p\in{\mathbb{Z}}$ not dividing the discriminant of $f$, there is a unique
Frobenius element
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\sigma_{p}}\in\mbox{\rm
Gal}(\mathbb{K}/{\mathbb{Q}})$ in the Galois group of $\mathbb{K}$ over
${\mathbb{Q}}$ that restricts to the Frobenius automorphism above $p$: For
every prime $\varpi$ of ${\mathcal{O}}$ with $\varpi\cap{\mathbb{Z}}=\langle
p\rangle$ ($\varpi$ is above $p$), and every $z\in{\mathcal{O}}$, we have
$\sigma_{p}(z)\equiv z^{p}\mod\varpi$. If $f$ is not monic, then we first
invert the primes dividing the leading coefficient of $f$. This is explained
in [50, §§ VII.2].

The cycle type of $\sigma_{p}$ (as a permutation of the roots of $f$) is given
by the degrees of the irreducible factors in ${\mathbb{F}}_{p}[x]$ of
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}f_{p}}:=f\mod
p$, as these factors give primes $\varpi$ above $p$. Indeed, if $g$ is an
irreducible factor of degree $r$, then
${\mathcal{O}}/\varpi\simeq{\mathbb{F}}_{p}[x]/\langle g\rangle$ is a finite
field with $p^{r}$ elements. The cycle type of $\sigma_{p}$ records how $p$
splits in ${\mathcal{O}}$ and is also called the splitting type of
$\sigma_{p}$ or of $f_{p}$. The prime $p$ does not divide the discriminant
exactly when $f_{p}$ is squarefree with the same degree as $f$. This gives a
method to compute cycle types of elements of $\mbox{\rm
Gal}(\mathbb{K}/{\mathbb{Q}})$: For a prime $p$ with $\deg(f_{p})=\deg(f)$,
factor the reduction $f_{p}$, and if no factor is repeated, record the degrees
of the factors.

This is particularly effective due to the Chebotarev Density Theorem [86, 87]:
Let $\mathbb{K}/{\mathbb{Q}}$ be a Galois extension and $\lambda$ a cycle type
of an element in $\mbox{\rm Gal}(\mathbb{K}/{\mathbb{Q}})$. Let $n_{\lambda}$
be the fraction of elements in $\mbox{\rm Gal}(\mathbb{K}/{\mathbb{Q}})$ with
cycle type $\lambda$. Then the density of primes $p\leq N$ such that the
Frobenius element $\sigma_{p}$ has splitting type $\lambda$ tends to
$n_{\lambda}$ as $N\to\infty$. Loosely, for $p$ sufficiently large, Frobenius
elements are distributed uniformly in $\mbox{\rm
Gal}(\mathbb{K}/{\mathbb{Q}})$.

Table 2 illustrates this when $f$ is
$x^{6}-503x^{5}-544x^{4}-69x^{3}-152x^{2}-49x-763$,

Table 2. Frobenius elements for $f$

$\begin{array}[]{||r|r|r|r|r|r|r|r|r|r|r||}\hline\cr
1^{6}&1^{4},2&1^{2},2^{2}&2^{3}&1^{3},3&1,2,3&3^{2}&1^{2},4&2,4&1,5&6\rule{0.0pt}{12.0pt}\\\
\hline\cr\hline\cr 1&15&45&15&40&120&40&90&90&144&120\\\ \hline\cr\hline\cr
3&12&24&9&47&146&32&112&71&121&143\\\
\hline\cr.989&15.02&44.97&14.99&40.07&120.03&39.95&89.87&89.97&144.24&119.9\\\
\hline\cr\hline\cr\end{array}$

which has Galois group $S_{6}$. The headers in the first row are the cycle
types (conjugacy classes) of permutations in $S_{6}$, expressed using the
frequency representation for cycles type in which $(2^{3})$ indicates three
2-cycles. The second row contains the sizes of each conjugacy class. The third
row records how many of the first $720=6!$ primes $p$ not dividing the
discriminant111$18972006774677773002386748159696=2^{4}\cdot 3^{12}\cdot 7\cdot
29\cdot 2633\cdot 88805021\cdot 47006055979$. did $f_{p}$ have the
corresponding splitting type. For the last row, we repeated this calculation
for the first $720\cdot 10^{5}$ primes larger than $10^{8}$. We display the
observed number that had a given splitting type, divided by $10^{5}$ for
comparison.

Determining the splitting type of Frobenius elements gives information about
Galois groups, including information about the distribution of cycle types in
a Galois group. For example, if the Galois group Gal is known to be a subgroup
of a particular permutation group $G$, knowing the cycle types of relatively
few elements often suffices to show that $\mbox{\rm Gal}=G$, as Proposition 4
does for the symmetric group. If we do not have a candidate for Gal, then
computing many Frobenius elements may help to predict the Galois group with a
high degree of confidence, by the Chebotarev density theorem.

Frobenius elements are also a tool for studying Galois groups in enumerative
geometry. Let $\pi\colon X\to Z$ be a branched cover of irreducible varieties
defined over ${\mathbb{Z}}$ with $Z$ smooth and rational. For any regular
value $z\in Z({\mathbb{Q}})$ of $\pi$, let $\mathbb{K}_{z}$ be the field
generated by the coordinates of the points in the fiber $\pi^{-1}(z)$ (in
$X(\overline{{\mathbb{Q}}})$). This is a finite Galois extension of
${\mathbb{Q}}$ whose Galois group is a subgroup of $\mbox{\rm
Gal}_{\pi}({\mathbb{Q}})$. For all except finitely many primes $p$, both $z$
and $\pi^{-1}(z)$ have reductions $z_{p}$ and $\pi^{-1}(z_{p})$ modulo $p$,
and there is a Frobenius element
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\sigma_{p,z}}\in\mbox{\rm
Gal}(\mathbb{K}_{z}/{\mathbb{Q}})$. This is also a consequence of [50, §§
VII.2].

Given a prime $p$ and a cycle type $\lambda$ of an element in the Galois group
$\mbox{\rm Gal}_{\pi}({\mathbb{Q}})$, we may consider the density of points
$z\in Z({\mathbb{F}}_{p})$ that are regular values of $\pi$ such that the
corresponding Frobenius element has conjugacy class $\lambda$. Ekedahl [21]
showed that in the limit as $p\to\infty$, this density tends to $n_{\lambda}$,
the density of the conjugacy class in $\mbox{\rm Gal}_{\pi}({\mathbb{Q}})$.

This theoretical result may be used in an algorithm. Assume that $\pi\colon
X\to Z$ is a branched cover of irreducible varieties defined over
${\mathbb{Z}}$ with $Z$ an open subset of an affine space
${\mathbb{A}}^{m}({\mathbb{Z}})$. All enumerative problems we discuss have
this form, as $Z$ is typically a variety of parameters (coefficients of
polynomials or entries of matrices representing flags). Replacing $X$ by an
open subset, we have that
$X\subset{\mathbb{A}}^{m}({\mathbb{Z}})\times{\mathbb{A}}^{n}({\mathbb{Z}})$
is an affine variety with ideal $I\subset{\mathbb{Z}}[z,x]$. Specializing $I$
at an integer point $z\in Z({\mathbb{Z}})$ gives the ideal $I(z)$ of the fiber
$\pi^{-1}(z)$. The splitting type of the fiber at $p$ may determined by a
primary decomposition of the ideal $I(z)$ modulo $p$.

Consider this for the branched cover $\pi\colon\Gamma\to{\mathbb{P}}^{19}$ of
lines on cubic surfaces (1). For each of 69 primes $p$ between $5$ and
$11579$, we determined the splitting type of the 27 lines for many (70 to 220
million) randomly chosen smooth cubic surfaces in
${\mathbb{P}}^{19}({\mathbb{F}}_{p})$, and compared that to the distribution
of cycle types in the Galois group $E_{6}$. More specifically, let
$n_{\lambda}$ be the density of elements in $E_{6}$ with cycle type $\lambda$.
For a prime $p$, let $E_{p,\lambda}$ be the empirical density, the observed
fraction of surfaces whose lines had splitting type $\lambda$. By Ekedahl’s
Theorem, $\lim_{p\to\infty}E_{p,\lambda}=n_{\lambda}$. (This same limit holds
if we replace smooth cubics in ${\mathbb{P}}^{19}({\mathbb{F}}_{p})$ by
isomorphism classes of smooth cubics over ${\mathbb{F}}_{p}$ [4].) Figure 2
presents

$.2$$.1$$0$$\lambda=(1,2,8^{3})$$2$$4$$6$$8$$\log(p)$

$.5$$.25$$0$$-.25$$\lambda=(2,5^{3},10)$$2$$4$$6$$8$$\log(p)$

$0$$-.25$$-.5$$-.75$$\lambda=(1^{15},2^{5})$$2$$4$$6$$8$$\log(p)$

Figure 2. Relative discrepancy, $\frac{E_{p,\lambda}}{n_{\lambda}}-1$, against
$\log(p)$ at 69 primes $p$, for splitting types
$\lambda\in\\{(1,2,8^{3}),(2,5^{3},10),(1^{15},2^{5})\\}$.

some data from our calculation. The full computation is archived on the web
page222https://www.math.tamu.edu/~sottile/research/stories/27_Frobenius/.

There are algorithms to compute this decomposition implemented in software
such as Macaulay2 [30] or Singular [17]. While these rely on Gröbner bases,
they are unreasonably effective, as they also take advantage of fast Gröbner
basis calculation in positive characteristic, for example the F5 algorithm
[27].

###  5.2. Computing Galois groups numerically

In Section 2.2, we discussed how moving a witness set $W$ to another one,
$W^{\prime}$, to a third, $W^{\prime\prime}$, and then back to $W$ computes a
permutation $\sigma$ of $W$. This is readily adapted to computing a
permutation of a fiber of a branched cover, which is an element of its Galois
group $\mbox{\rm Gal}_{\pi}$. While computing several such monodromy
permutations only gives a subgroup of $\mbox{\rm Gal}_{\pi}$, that may be
sufficient to determine it [54]. We explain a numerical method from [35] that
computes a generating set for the Galois group and another numerical method to
study transitivity.

Given a branched cover $\pi\colon X\to Z$ of degree $d$ over ${\mathbb{C}}$
with $Z$ rational, let $U\subset Z$ be the regular locus so that
$\pi^{-1}(U)\to U$ is a covering space. Suppose that we have computed all
points in a fiber $\pi^{-1}(z)$ for some point $z\in U$. Choosing other points
$z^{\prime},z^{\prime\prime}\in U$, we may construct three parameter
homotopies that move the points of $\pi^{-1}(z)$ to those of
$\pi^{-1}(z^{\prime})$, to $\pi^{-1}(z^{\prime\prime})$, and then back to
$\pi^{-1}(z)$. The tracked paths give a permutation $\sigma$ of the fiber
$\pi^{-1}(z)$.

Writing the points of $\pi^{-1}(z)$ in some order $(w_{1},\dotsc,w_{d})$ gives
a point in the fiber of $X^{(d)}_{Z}$ over $z$. (Recall that $X^{(d)}_{Z}$ was
used in Section 1.1 to give a geometric construction of $\mbox{\rm
Gal}_{\pi}$.) The $d$-tuples of computed paths between the fibers
$\pi^{-1}(z)$, $\pi^{-1}(z^{\prime})$, $\pi^{-1}(z^{\prime\prime})$, and back
to $\pi^{-1}(z)$ give a path in $X^{(d)}_{Z}$ from the point
$(w_{1},\dotsc,w_{d})$ and the point $(\sigma(w_{1}),\dotsc,\sigma(w_{d}))$ in
the same fiber. These paths all lie in the same irreducible component of
$X^{(d)}_{Z}$, showing that $\sigma\in\mbox{\rm Gal}_{\pi}$.

This may be used to compute many permutations in $\mbox{\rm Gal}_{\pi}$,
giving an increasing sequence of subgroups of $\mbox{\rm Gal}_{\pi}$. As with
computing Frobenius elements, this may suffice to determine $\mbox{\rm
Gal}_{\pi}$. For example, if the computed subgroup of $\mbox{\rm Gal}_{\pi}$
is $S_{d}$, then $\mbox{\rm Gal}_{\pi}=S_{d}$ is full-symmetric. This method
was used in [54] to show that several Schubert Galois groups (see Section 6)
were full-symmetric, including one with $d=17589$. In that computation, every
time a new permutation $\pi$ was found, GAP [29] was called to test if the
computed set of permutations generated the symmetric group.

A drawback is that numerical path tracking may be inexact, which can lead to
false conclusions (this is known as path-crossing). A consequence of the
calculation in [54] was the implementation of an algorithm [36] for a
posteriori certification of the computed solutions to a system of polynomials,
based on Smale’s $\alpha$-theory [73]. Certification using Krawczyk’s method
from interval arithmetic [46] has also been implemented [9], providing another
approach. More substantially, algorithms were developed [6, 7] to certify
path-tracking and thereby certifiably compute monodromy.

This approach of computing monodromy may be improved to compute a generating
set of the Galois group [35]. Given a branched cover $\pi\colon X\to Z$ as
above, restricting to an open subset of $Z$ and compactifying, we may assume
that $Z={\mathbb{P}}^{N}$. The branch locus of $\pi\colon
X\to{\mathbb{P}}^{N}$ is a hypersurface $B\subset{\mathbb{P}}^{N}$. Let
$z\in{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}U}:={\mathbb{P}}^{n}\smallsetminus
B$. Lifting loops in $U$ based at $z$ gives a surjective homomorphism from the
fundamental group of $U$ to the monodromy group of the cover $\pi^{-1}(U)\to
U$ [33, 64].

A witness set for $B$ can be used to obtain a generating set for the
fundamental group of $U$. Suppose that $\ell\cap B$ is a linear section of the
hypersurface $B$, so that $\ell\simeq{\mathbb{P}}^{1}$ is a line. Zariski [93]
showed that the inclusion $\ell\cap U\hookrightarrow U$ induces a surjection
from the fundamental group of $\ell\cap U$ to the fundamental group of $U$. As
the fundamental group of $\ell\cap U$ is generated by based loops around each
of the (finitely many) points of $\ell\smallsetminus(B\cap\ell)$, lifts of
these loops generate the Galois group $\mbox{\rm Gal}_{\pi}$ of the branched
cover.

In [35], this method is demonstrated on the branched cover
$\Gamma\to{\mathbb{P}}^{19}$ (1) from the problem of 27 lines. The branch
locus $B$ is the set of singular cubics, which forms a hypersurface on
${\mathbb{P}}^{19}$ of degree 32, so that a general line $\ell$ in
${\mathbb{P}}^{19}$ meets $B$ transversally in 32 points. The computed
permutations for a particular choice of $\ell$ (given in Figure 5 in [35])
generate $E_{6}$. Each permutation is a product of six disjoint 2-cycles in
$S_{27}$. Here is one,

$(1,6)(4,13)(8,25)(10,19)(11,16)(20,27)\ .$

That a loop around a point of $\ell\cap B$ gives a permutation that is the
product of six disjoint 2-cycles is a manifestation of the enriched structure
of this enumerative problem; Above a general point of $B$, there are six
solutions of multiplicity 2. Contrast this with the result of Esterov [24]
from Section 4 where a single loop around $B$ gave a simple transposition.

Similar ideas were used to establish Theorem 5, except that rather than
compute a full witness set for the branch locus, a single point $z\in\ell\cap
B$ in a linear section of the branch locus was computed. Lifting one loop
around $z$ gave a simple transposition, which was sufficient to show that
those Fano problems wre full symmetric.

We mention another method from [35] involving transitivity. Let $\pi\colon
X\to Z$ be a branched cover of degree $d$. By Proposition 2, for any $1\leq
s\leq d$, $s$-transitivity of the Galois group $\mbox{\rm Gal}_{\pi}$ is
equivalent to the irreducibility of the variety $X_{Z}^{(s)}$. Numerical
irreducible decomposition may be used to determine the (ir)reducibility of
$X_{Z}^{(s)}$ and therby determine whether or not $\mbox{\rm Gal}_{\pi}$ is
$s$-transitive. Details and an example involving the problem of 27 lines are
given in [35, Sect. 4].

##  6\. Galois groups in Schubert calculus

In his seminal book, “Kalkul der abzählenden Geometrie” [72] Schubert
presented methods for computing the number of solutions to problems in
enumerative geometry. Justifying these methods was Hilbert’s 15th problem
[40], and they collectively came to be known as “Schubert’s Calculus”. A
central role was played by the Grassmannian and its Schubert cycles/varieties.
Schubert and others studied these objects further, and now Schubert varieties
and the interplay of their geometry, combinatorics, and algebra make them
central objects in combinatorial algebraic geometry [28] and other areas of
mathematics. This study is also called Schubert calculus. We are concerned
with the overlap of these versions of Schubert calculus—problems in
enumerative geometry that involve intersections of Schubert varieties in
Grassmannians and flag manifolds.

These Schubert problems form a rich and well-understood class of examples that
has long served as a laboratory for investigating new phenomena in enumerative
geometry [45]. Thousands to millions of Schubert problems are computable and
therefore may be studied on a computer. Recently, this has also included
reality in enumerative geometry [81], and the resulting experimentation
generated conjectures [37, 69, 80] and examples [38] concerning reality in
Schubert calculus. These in turn helped to inspire proofs of some conjectures
[22, 23, 51, 62, 63, 61, 67].

Vakil’s geometric Littlewood-Richardson rule [88] gave a new tool [89] for
investigating Galois groups of Schubert problems (Schubert Galois groups) on
Grassmannians. He used it to discover an infinite family of Schubert problems
on Grassmannians with enriched Galois groups. The study of reality in flag
manifolds uncovered another infinite family of enriched Schubert problems in
manifolds of partial flags [69, Thm. 2.18]. Subsequent results and
constructions have led to the expectation that a Schubert Galois group should
be an iterated wreath product of symmetric groups, together with an
understanding of the structure of enriched Schubert problems. Despite this, we
are far from a classification, and the study has been limited to Grassmannians
and type $A$ flag manifolds.

After describing Schubert problems in Grassmannians, in Section 6.2 we
construct Schubert problems whose Galois groups are symmetric groups $S_{b}$
acting on flags of subsets of $[b]:=\\{1,\dotsc,b\\}$; This gives many
enriched Schubert problems on flag manifolds in type $A$. We also present a
conjectural solution to the inverse Galois problem for Schubert calculus. In
Section 6.3 we describe a general construction of Schubert problems whose
Galois groups are expected to be wreath products of two Schubert Galois
groups. Our last section discusses results on Schubert Galois groups that are
leading to an emerging picture of a possible classification of Schubert
problems by their Galois groups.

###  6.1. Schubert problems

Consider the classical Schubert problem: “Which lines in ${\mathbb{P}}^{3}$
meet each of four general lines?” Three mutually skew lines $\ell^{1}$,
$\ell^{2}$, and $\ell^{3}$ lie on a unique hyperboloid (Fig. 3).

$\ell^{2}$$\ell^{1}$$\ell^{3}$$\ell^{4}$$h^{1}$$h^{2}$$p$

Figure 3. Problem of four lines

This hyperboloid has two rulings. One contains $\ell^{1}$, $\ell^{2}$, and
$\ell^{3}$, and the second consists of the lines meeting them. A general
fourth line, $\ell^{4}$, meets the hyperboloid in two points, and through each
of these points there is a unique line in the second ruling. These two lines,
$h^{1}$ and $h^{2}$, are the solutions to this instance of the problem of four
lines. Its Galois group is the symmetric group $S_{2}$: Indeed, the solutions
move as $\ell_{4}$ moves and rotating $\ell_{4}$ $180^{\circ}$ about the point
$p$ will interchange the two lines.

More generally, a Schubert problem involves determining the linear subspaces
of a vector space that have specified positions with respect to certain fixed,
but general linear subspaces. For the problem of four lines, if we replace
projective space ${\mathbb{P}}^{3}$ by ${\mathbb{C}}^{4}$, the lines become
2-dimensional linear subspaces. Thus the problem of four lines is to determine
the 2-planes in ${\mathbb{C}}^{4}$ that meet four given 2-planes nontrivially.

We introduce some terminology. First, fix integers $1\leq m<n$. The collection
of all $m$-dimensional subspaces of ${\mathbb{C}}^{n}$ is the Grassmannian
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mbox{\rm
Gr}(m,n)}$ (also written
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mbox{\rm
Gr}(m,{\mathbb{C}}^{n})}$), which is an algebraic manifold of dimension
$m(n{-}m)$. In Section 3, this space was written
${\mathbb{G}}(m{-}1,{\mathbb{P}}^{n-1})$.

The Grassmannian has distinguished Schubert varieties. These depend upon the
choice of a (complete) flag, which is a collection
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}F}\colon
F_{1}\subset F_{2}\subset\dotsb\subset F_{n}={\mathbb{C}}^{n}$ of linear
subspaces with $\dim{F_{i}}=i$. Given a flag $F$, a Schubert variety is the
collection of all $m$-planes having a given position with respect to $F$. A
position is encoded by a partition, which is a weakly decreasing sequence of
nonnegative integers
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\lambda}\colon\lambda_{1}\geq\dotsb\geq\lambda_{m}\geq
0$ with $\lambda_{1}\leq n{-}m$. For a flag $F$ and partition $\lambda$, the
corresponding Schubert variety is

(3)
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\Omega_{\lambda}F}\
:=\ \\{H\in\mbox{\rm Gr}(m,n)\mid\dim H\cap F_{n-m+i-\lambda_{i}}\geq i\
\mbox{ for }i=1,\dotsc,m\\}.$

Setting
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}|\lambda|}:=\lambda_{1}+\dotsb+\lambda_{m}$,
the Schubert variety $\Omega_{\lambda}F$ has codimension $|\lambda|$ in
$\mbox{\rm Gr}(m,n)$.

Only $m$ of the $n$ subspaces $F_{i}$ in $F$ appear in the definition (3) of
the Schubert variety $\Omega_{\lambda}F$. If $i<m$ and
$\lambda_{i}=\lambda_{i+1}$, then the condition on $H$ in (3) from
$\lambda_{i+1}$ implies the condition on $H$ for $\lambda_{i}$. Those $i$ with
$\lambda_{i}>\lambda_{i+1}$ (or $i=m$ with $\lambda_{m}>0$) are essential.
When $(m,n)=(2,4)$ and $\lambda=(1,0)$, the essential condition is when $i=1$.
Indeed, $\Omega_{(1,0)}F=\\{H\in\mbox{\rm Gr}(2,4)\mid\dim H\cap F_{2}\geq
1\\}$. In ${\mathbb{P}}^{3}$, this is the set of lines ${\mathbb{P}}H$ that
meet the fixed line ${\mathbb{P}}F_{2}$.

A Schubert problem is a list
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\lambda^{\bullet}}}=\lambda^{1},\dotsc,\lambda^{s}$
of partitions with $\sum_{j}|\lambda^{j}|=m(n-m)$, the dimension of the
Grassmannian. An instance of ${\lambda^{\bullet}}$ is given by a choice
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{F^{\bullet}}}=(F^{1},\dotsc,F^{s})$
of flags. The solutions to this instance form the set of $m$-planes $H$ that
have position $\lambda^{j}$ with respect to the flag $F^{j}$, for each $j$.
This set is the intersection

(4)
$\Omega_{\lambda^{1}}F^{1}\,\bigcap\,\Omega_{\lambda^{2}}F^{2}\,\bigcap\,\dotsb\,\bigcap\,\Omega_{\lambda^{s}}F^{s}\,.$

Kleiman [44] showed that this intersection is transverse when the flags are
general. When the flags are general, this implies that for each solution
(point $H$ in (4)), the inequalities in (3) for each pair $\lambda^{j},F^{j}$
hold with equality. Also, the number of solutions does not depend upon the
(general) flags. Write $d({\lambda^{\bullet}})$ for this number, which may be
computed using algorithms in Schubert’s calculus.

Let ${\mathbb{F}}{\ell}(n)$ be the space of complete flags in
${\mathbb{C}}^{n}$ and consider the incidence variety:

(5)
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\Gamma_{{\lambda^{\bullet}}}}:=\\{(H,F^{1},\dotsc,F^{s})\in\mbox{\rm
Gr}(m,n)\times{\mathbb{F}}{\ell}(n)^{s}\,\mid\,$$H\in\Omega_{\lambda^{i}}F^{i}\
\mbox{for}\
i=1,\dotsc,s\\}$$\pi_{{\lambda^{\bullet}}}$${\mathbb{F}}{\ell}(n)^{s}$

The total space $\Gamma_{{\lambda^{\bullet}}}$ of this Schubert problem is
irreducible, as it is a fiber bundle over the Grassmannian $\mbox{\rm
Gr}(m,n)$ with irreducible fibers (this is explained in [82, Sect. 2.2]). The
fiber of $\pi_{{\lambda^{\bullet}}}$ over
$(F^{1},\dotsc,F^{s})\in{\mathbb{F}}{\ell}(n)^{s}$ is the intersection (4).
Since this is transverse and consists of $d({\lambda^{\bullet}})$ points for
general flags, $\pi_{{\lambda^{\bullet}}}$ is a branched cover of degree
$d({\lambda^{\bullet}})$. We write $\mbox{\rm Gal}_{{\lambda^{\bullet}}}$ for
its Galois group, which we call a Schubert Galois group.

###  6.2. Some enriched Schubert problems

We present a construction of many enriched Schubert problems on Grassmannians
and flag manifolds. These are based on the following generalization of the
problem of four lines: Let $1<b$ be an integer and consider the 2-planes
$h\subset{\mathbb{C}}^{2b}$ that meet each of four general $b$-planes
$K^{1},\dotsc,K^{4}$ in at least a one-dimensional subspace. Since
$2b-2+1-(b-1)=b$, this Schubert problem is given by four partitions, each
equal to $(b{-}1,0)$.

This has $b$ solutions, which we now describe. As the $K^{i}$ are general, we
have $K^{i}\oplus K^{j}={\mathbb{C}}^{2b}$ for $i\neq j$. Then $K^{3},K^{4}$
are graphs of isomorphisms $f_{3},f_{4}\colon K^{1}\to K^{2}$, and
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\varphi}:=f_{4}^{-1}\circ
f_{3}$ is a linear isomorphism of $K^{1}$. If $\ell=\varphi(\ell)\subset
K^{1}$ is a $\varphi$-stable line (one-dimensional subspace) in $K^{1}$, then
$f_{3}(\ell)=f_{4}(\ell)$ and $H:=\ell\oplus f_{3}(\ell)$ is a solution to
this enumerative problem. Furthermore, all solutions have this form, as $H\cap
K^{i}$ for $i=1,\dotsc,4$ are four lines in the same 2-plane $H$. As the
subspaces $K^{i}$ are general, the linear transformation $\varphi$ is semi-
simple and therefore has $b=\dim(K^{1})$ distinct stable lines (generated by
its eigenvectors). Thus this Schubert problem has $b$ solutions.

Note that the monodromy group for the eigenvectors of semi-simple linear
transformations $\varphi$ is the full symmetric group $S_{b}$ acting on the
set of 1-dimensional $\varphi$-stable linear subspaces of $K^{1}$. Thus the
Galois group of this Schubert problem is the full symmetric group $S_{b}$
acting naturally as permutations on the set
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}[b]}:=\\{1,\dotsc,b\\}$.

######  Example 9.

Vakil [89, § 3.14] used these problems in $\mbox{\rm Gr}(2,2b)$ to construct
an infinite family of Schubert problems with enriched Galois groups. Let
$1\leq a<b$ and consider the Schubert problem in $\mbox{\rm Gr}(2a,2b)$ of
$2a$-planes that meet each of four general $b$-planes $K^{1},\dotsc,K^{4}$ in
at least an $a$-dimensional linear subspace. The previous argument
generalizes: Let $f_{3},f_{4}\colon K^{1}\to K^{2}$ and
$\varphi:=f_{4}^{-1}\circ f_{3}\colon K^{1}\to K^{1}$ be the linear
isomorphisms determined by $K^{1},\dotsc,K^{4}$. Every solution has the form
$L\oplus f_{3}(L)$ for $L=\varphi(L)\subset K^{1}$ a $\varphi$-stable
$a$-dimensional linear subspace. Consequently, $L$ is spanned by $a$ linearly
independent eigenvectors of $\varphi$. Thus this Schubert problem has
$\binom{b}{a}$ solutions.

The symmetric group $S_{b}$ acts naturally on the set $\binom{[b]}{a}$ of
subsets of $[b]$ of cardinality $a$, and this argument shows that this
permutation group (written $S\binom{[b]}{a}$) is the Galois group of this
Schubert problem. This action is not 2-transitive when $1<a<b{-}1$. It
preserves the dimension of the intersection of a pair of solutions, and thus
has at least $\min\\{a,b{-}a\\}$ distinct orbits on pairs of solutions.
$\diamond$

We generalize Vakil’s examples, while also generalizing [69, Thm. 2.18].

######  Example 10.

Suppose that $1\leq a_{1}<\dotsb<a_{r}<b$ are integers and write
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{a_{\bullet}}}$
for the sequence $a_{1}<\dotsb<a_{r}$. Let
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\mathbb{F}}{\ell}(2{a_{\bullet}},2b)}$
be the space of partial flags of the form

$F\ \colon\ F_{2a_{1}}\ \subset\ F_{2a_{2}}\ \subset\ \dotsb\ \subset\
F_{2a_{r}}\ \subset\ {\mathbb{C}}^{2b}\,,$

where $\dim F_{2a_{i}}=2a_{i}$. Fix four general $b$-planes
$K^{1},K^{2},K^{3},K^{4}$ in ${\mathbb{C}}^{2b}$. Consider the Schubert
problem that seeks the partial flags
$F\in{\mathbb{F}}{\ell}(2{a_{\bullet}},2b)$ such that for $i=1,\dotsc,r$,

(6) $\dim F_{2a_{i}}\bigcap K^{j}\ \geq\ a_{i}\qquad\mbox{ for all }\
j=1,\dotsc,4\,.$

As before, $K^{1},\dotsc,K^{4}$ give isomorphisms $f_{3},f_{4}\colon K^{1}\to
K^{2}$ and $\varphi=f_{4}^{-1}\circ f_{3}\colon K^{1}\to K^{1}$. For each
$1\leq i\leq r$, the solutions to (6) are given by $L_{a_{i}}\oplus
f_{3}(L_{a_{i}})$ where $L_{a_{i}}\subset K^{1}$ is a $\varphi$-stable linear
subspace of dimension $a_{i}$.

Consequently, the solutions to (6) for all $i$ are in bijection with
$\varphi$-stable flags

$L_{a_{1}}\ \subset\ L_{a_{2}}\ \subset\ \dotsb\ \subset\ L_{a_{r}}\ \subset\
K^{1}\,,$

where $\dim L_{a_{i}}=a_{i}$. Since $L_{a_{i}}$ is necessarily spanned by
$a_{i}$ independent eigenvectors of $\varphi$, these are in bijection with
flags of subsets of $[b]$:

${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\binom{[b]}{{a_{\bullet}}}}\
:=\ \\{T_{1}\subset T_{2}\subset\dotsb\subset
T_{r}\subset[b]\,\mid\,|T_{i}|=a_{i}\\}\,.$

Thus $\binom{[b]}{{a_{\bullet}}}$ counts solutions to this Schubert problem
and its Galois group is the symmetric group $S_{b}$, with its natural action
on the set $\binom{[b]}{{a_{\bullet}}}$ of flags of subsets. Write
$S\binom{[b]}{{a_{\bullet}}}$ for this permutation group. $\diamond$

This completes the following existence proof concerning Schubert Galois
groups.

######  Theorem 11.

For any positive integers $1\leq a_{1}<\dotsb<a_{r}<b$, there is a Schubert
problem on the flag manifold ${\mathbb{F}}{\ell}(2{a_{\bullet}},2b)$ with
Galois group $S\binom{[b]}{{a_{\bullet}}}$.

These Schubert Galois groups form the basis for a conjectured solution to the
Inverse Galois Problem in Schubert calculus.

######  Conjecture 12.

A Galois group for a Schubert problem on a type A flag manifold is an iterated
wreath product of permutation groups $S\binom{[b]}{{a_{\bullet}}}$, and all
such wreath products occur.

Schubert Galois groups for Grassmannians are iterated wreath products of
permutation groups $S\binom{[b]}{a}$, and all such wreath products occur.

Conjecture 12 describes all known Schubert Galois groups—we discuss that and
more in Section 6.4. Additionally, all Schubert problems we know of with
enriched Galois groups are either among those described in Examples 9 or 10 or
they are fibrations of Schubert problems, a structure we discuss in Section
6.3 which is conjectured to give such wreath products.

###  6.3. Compositions of Schubert problems

By Proposition 3, when a branched cover is decomposable, its Galois group is a
subgroup of the wreath product of the Galois groups of its factors. We explain
how to construct a Schubert problem on a Grassmannian $\mbox{\rm
Gr}(2a{+}m,2b{+}n)$ with decomposable branched cover. This is built from one
of the Schubert problems of Example 9 on $\mbox{\rm Gr}(2a,2b)$ and any
Schubert problem ${\mu^{\bullet}}$ on $\mbox{\rm Gr}(m,n)$ with
$d({\mu^{\bullet}})>1$. Conjecturally, its Galois group is the wreath product
$(\mbox{\rm Gal}_{{\mu^{\bullet}}})^{\binom{b}{a}}\rtimes S\binom{[b]}{a}$.
This conjecture would establish existence in the Inverse Galois Problem for
Schubert problems on Grassmannians.

It is convenient to represent a partition $\mu$ by its (Young) diagram, which
is a left-justified array of boxes with $\mu_{i}$ boxes in row $i$. Thus

$(1)\ \longleftrightarrow\
\raisebox{-2.0pt}{\includegraphics{pictures/1}}\,,\qquad(2,2)\
\longleftrightarrow\
\raisebox{-6.0pt}{\includegraphics{pictures/22}}\,,\quad\mbox{and}\quad\
(3,2,1,1)\ \longleftrightarrow\
\raisebox{-14.0pt}{\includegraphics{pictures/3211}}\ .$

We omit any trailing 0s in a partition $\mu$. Observe that the essential
conditions in $\mu$ correspond to the boxes that form south east corners.
Consequently, a rectangular partition imposes a single incidence condition.

As the number $d({\mu^{\bullet}})$ of solutions to a Schubert problem
${\mu^{\bullet}}$ may be computed in the cohomology ring of the corresponding
Grassmannian [28], we often write a Schubert problem multiplicatively. Thus
$(\raisebox{-0.5pt}{\includegraphics{pictures/1s}},\raisebox{-0.5pt}{\includegraphics{pictures/1s}},\raisebox{-0.5pt}{\includegraphics{pictures/1s}},\raisebox{-0.5pt}{\includegraphics{pictures/1s}})$,
which is the problem of four lines, is also written
$\raisebox{-0.5pt}{\includegraphics{pictures/1s}}\cdot\raisebox{-0.5pt}{\includegraphics{pictures/1s}}\cdot\raisebox{-0.5pt}{\includegraphics{pictures/1s}}\cdot\raisebox{-0.5pt}{\includegraphics{pictures/1s}}$
or as $\raisebox{-0.5pt}{\includegraphics{pictures/1s}}^{4}$. The construction
of a composition of Schubert problems is a bit technical, we will illustrate
it first on the simplest example, when ${\lambda^{\bullet}}={\mu^{\bullet}}$
are both the problem of four lines.

######  Example 13.

Consider the Schubert problem ${\kappa^{\bullet}}$ in $\mbox{\rm Gr}(4,8)$
given by the partitions

(7) ${\kappa^{\bullet}}\ =\
\raisebox{-2.0pt}{\includegraphics{pictures/3}\,}\cdot\
\raisebox{-2.0pt}{\includegraphics{pictures/3}\,}\cdot\
\raisebox{-10.0pt}{\includegraphics{pictures/111}\,}\cdot\
\raisebox{-10.0pt}{\includegraphics{pictures/111}\,}\cdot\
\raisebox{-2.0pt}{\includegraphics{pictures/1}\,}\cdot\
\raisebox{-2.0pt}{\includegraphics{pictures/1}\,}\cdot\
\raisebox{-2.0pt}{\includegraphics{pictures/1}\,}\cdot\
\raisebox{-2.0pt}{\includegraphics{pictures/1}\,}.$

An instance of this Schubert problem is given by two 2-planes
$\ell^{1}_{2},\ell^{2}_{2}$, two 6-planes $L^{3}_{6},L^{4}_{6}$, and four
4-planes $K^{1}_{4},\dotsc,K^{4}_{4}$, and its solutions are

(8) $\\{H\in\mbox{\rm Gr}(4,8)\,\mid\,\begin{array}[]{r}\dim
H\cap\ell^{i}_{2}\geq 1\ \mbox{ for }i=1,2\\\ \dim H\cap L^{j}_{6}\geq 3\
\mbox{ for }j=3,4\end{array}\ \dim H\cap K^{t}_{4}\geq 1\ \mbox{ for
}t=1,\dotsc,4\\}\ .$

Assume that these linear subspaces $\ell^{i}_{2},L^{j}_{6},K^{t}_{4}$ are in
general position, which implies the dimension assertions that follow. Let
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\Lambda}:=\ell^{1}_{2}\oplus\ell^{2}_{2}\simeq{\mathbb{C}}^{4}$
and
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}M}:=L^{3}_{6}\cap
L^{4}_{6}\simeq{\mathbb{C}}^{4}$.

If $H$ is a solution to (8), then $\dim H\cap\Lambda\geq 2$ and $\dim H\cap
M\geq 2$. As $\Lambda\cap M=\\{0\\}$ and $\dim H=4$, these inequalities are
equalities. Set
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}h}:=H\cap\Lambda\in
G(2,\Lambda)$. For $j=3,4$, the intersection $H\cap L^{j}_{6}$ has codimension
1 in $H$ and therefore $\dim h\cap L^{j}_{6}=1$. Setting
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\ell^{j}_{2}}:=\Lambda\cap
L^{j}_{6}$, we see that $h$ is a solution to the instance of the problem of
four lines given by $\ell^{1}_{2},\dotsc,\ell^{4}_{2}$.

Similarly, for each $i=1,\dotsc,4$, $H\cap M$ meets the 2-plane
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}k^{i}_{2}(h)}:=(h\oplus
K^{i}_{4})\cap M$. Thus $H\cap M$ is a solution to the problem of four lines
given by $k^{1}_{2}(h),\dotsc,k^{4}_{2}(h)$. Conversely, given a solution
$h\subset\Lambda$ to the problem of four lines given by
$\ell^{1}_{2},\dotsc,\ell^{4}_{2}$ and a solution $h^{\prime}\subset M$ to the
problem of four lines given by $k^{1}_{2}(h),\dotsc,k^{4}_{2}(h)$, their sum
$h\oplus h^{\prime}$ is a solution to the Schubert problem (8). $\diamond$

Thus the branched cover
$\pi\colon\Gamma_{{\kappa^{\bullet}}}\rightarrow{\mathbb{F}}{\ell}(8)^{8}$ of
this Schubert problem (5) is decomposable. Indeed, let
$U\subset{\mathbb{F}}{\ell}(8)^{8}$ be the subset of flags in the general
position used in Example 13. If we let $X:=\pi^{-1}(U)$ be the restriction of
$\Gamma_{{\kappa^{\bullet}}}$ to this set of general instances, then Example
13 shows that we have a factorization $X\rightarrow Y\rightarrow U$. Here, the
fiber of $Y\to U$ over an instance in $U$ is the instance of
$\raisebox{-0.5pt}{\includegraphics{pictures/1s}}^{4}$ in $\mbox{\rm
Gr}(2,\Lambda)$ given by $\ell_{2}^{1},\dotsc,\ell_{2}^{4}$, and given a
solution $h$ to this instance, the fiber of $X\to Y$ over $h$ is the instance
of $\raisebox{-0.5pt}{\includegraphics{pictures/1s}}^{4}$ in $\mbox{\rm
Gr}(2,M)$ given by $k^{1}_{2}(h),\dotsc,k^{4}_{2}(h)$.

We make a definition inspired by this structure.

######  Definition 14.

A Schubert problem ${\kappa^{\bullet}}$ is fibered over a Schubert problem
${\lambda^{\bullet}}$ with fiber ${\mu^{\bullet}}$ if the branched cover
$\Gamma_{{\kappa^{\bullet}}}\to{\mathbb{F}}{\ell}(n)^{s}$ is decomposable, and
it admits a decomposition

$X\ \longrightarrow\ Y\ \longrightarrow\ U\quad(U\ \subset\
{\mathbb{F}}{\ell}(n)^{s}\ \mbox{ is open and dense})$

such that

  1. (1)

fibers of $Y\to U$ are instances of ${\lambda^{\bullet}}$,

  2. (2)

fibers of $X\to Y$ are instances of ${\mu^{\bullet}}$, and

  3. (3)

general instances of ${\lambda^{\bullet}}$ and ${\mu^{\bullet}}$ occur as
fibers in this way.

We will call ${\kappa^{\bullet}}$ a fibration. This notion is developed in
[57] and [84], where the following is proven, which is a special case of [57,
Lemma 15].

######  Proposition 15.

If a Schubert problem ${\kappa^{\bullet}}$ is fibered over
${\lambda^{\bullet}}$ with fiber ${\mu^{\bullet}}$, then
$d({\kappa^{\bullet}})=d({\lambda^{\bullet}})\cdot d({\mu^{\bullet}})$, and
its Galois group is a subgroup of the wreath product

$\mbox{\rm Gal}_{{\kappa^{\bullet}}}\ \subset\ \left(\mbox{\rm
Gal}_{{\mu^{\bullet}}}\right)^{d({\lambda^{\bullet}})}\rtimes\mbox{\rm
Gal}_{{\lambda^{\bullet}}}\,.$

Consequently, the Schubert Galois group from Example 13 is a subgroup of the
wreath product $(S_{2})^{2}\rtimes S_{2}$. In fact, its Galois group equals
this wreath product [56, Sect. 5.5.2].

The construction of Example 13 was generalized in [84]. Given two Schubert
problems ${\lambda^{\bullet}}$ and ${\mu^{\bullet}}$ on possibly different
Grassmannians, that paper describes how to use them to build a new Schubert
problem ${\lambda^{\bullet}}\circ{\mu^{\bullet}}$ on another Grassmannian,
called their composition. It uses combinatorics to prove that
$d({\lambda^{\bullet}}\circ{\mu^{\bullet}})=d({\lambda^{\bullet}})\cdot
d({\mu^{\bullet}})$, and it is expected—but not proven—that
${\lambda^{\bullet}}\circ{\mu^{\bullet}}$ is fibered over
${\lambda^{\bullet}}$ with fiber ${\mu^{\bullet}}$.

Next, it identifies a family of Schubert problems and shows that for any
Schubert problem ${\lambda^{\bullet}}$ in that family, any composition
${\lambda^{\bullet}}\circ{\mu^{\bullet}}$ is fibered over
${\lambda^{\bullet}}$ with fiber ${\mu^{\bullet}}$. This family includes all
the Schubert problems of Example 9. We explain this construction when
$\lambda$ is a Schubert problem of Example 9, which is a motivation for
Conjecture 12.

Write $\Box_{a,b}$ for the rectangular partition with $a$ rows, each of length
$b{-}a$. For example,

$\Box_{1,2}\ =\
\raisebox{-2.0pt}{\includegraphics{pictures/1}}\,,\quad\Box_{1,6}\ =\
\raisebox{-2.0pt}{\includegraphics{pictures/5}}\,,\quad\Box_{2,4}\ =\
\raisebox{-6.0pt}{\includegraphics{pictures/22}}\,,\quad\mbox{ and
}\quad\Box_{3,7}\ =\ \raisebox{-10.0pt}{\includegraphics{pictures/444}}\ .$

Every Schubert problem in Example 9 has the form $\Box_{a,b}^{\,4}$.

Fix integers $1\leq a<b$ and $1\leq m<n$, and let
${\mu^{\bullet}}=(\mu^{1},\dotsc,\mu^{s})$ be any Schubert problem on
$\mbox{\rm Gr}(m,n)$. Set
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}r}:=n{-}m$.
The composition, $\Box_{a,b}^{\,4}\circ{\mu^{\bullet}}$, of $\Box_{a,b}^{\,4}$
and ${\mu^{\bullet}}$ is the Schubert problem on $\mbox{\rm Gr}(2a+m,2b+n)$
given by the following partitions

$\Box_{a,b+r}\,,\,\Box_{a,b+r}\ ,\ \Box_{a+m,b+m}\,,\,\Box_{a+m,b+m}\ ,\
\mu^{1},\dotsc,\mu^{s}\,.$

Suppose that $a=1$, $b=2$, and
${\mu^{\bullet}}=\raisebox{-0.5pt}{\includegraphics{pictures/1s}}^{4}$. Then
$m=r=2$ and $n=4$, so that these partitions are

$\Box_{1,4}\,,\,\Box_{1,4}\ ,\ \Box_{3,4}\,,\,\Box_{3,4}\ ,\
\raisebox{-0.5pt}{\includegraphics{pictures/1s}},\raisebox{-0.5pt}{\includegraphics{pictures/1s}},\raisebox{-0.5pt}{\includegraphics{pictures/1s}},\raisebox{-0.5pt}{\includegraphics{pictures/1s}}\,,$

which is the Schubert problem ${\kappa^{\bullet}}$ (7) of Example 13.

######  Proposition 16 (Theorem 3.8 of [84]).

The Schubert problem $\Box_{a,b}^{\,4}\circ{\mu^{\bullet}}$ is fibered over
the Schubert problem $\Box_{a,b}^{\,4}$ on $\mbox{\rm Gr}(2a,2b)$ with fiber
the Schubert problem ${\mu^{\bullet}}$ on $\mbox{\rm Gr}(m,n)$. We have

$\mbox{\rm Gal}_{\Box_{a,b}^{\,4}\circ{\mu^{\bullet}}}\ \subset\
\left(\mbox{\rm Gal}_{{\mu^{\bullet}}}\right)^{\binom{b}{a}}\rtimes
S{\textstyle\binom{[b]}{a}}\,.$

We conjecture this inclusion is an equality—that would prove the existence
statement in Conjecture 12, for Grassmannians.

###### Sketch of proof..

We explain how to decompose a general instance of the Schubert problem
$\Box_{a,b}^{\,4}\circ{\mu^{\bullet}}$. This is similar to Example 13. This
involves constructing an instance of $\Box_{a,b}^{\,4}$ as an auxiliary
problem, and for each of its solutions, constructing an instance of
${\mu^{\bullet}}$.

An instance of the Schubert problem $\Box_{a,b}^{\,4}\circ{\mu^{\bullet}}$ is
given by two $b$-planes $K^{1}_{b},K^{2}_{b}$, two codimension $b$-planes
$L^{3}_{b+n},L^{4}_{b+n}$, and flags $F^{1},\dotsc,F^{s}$ in
${\mathbb{C}}^{2b+n}$. The Schubert problem seeks the $(2a{+}m)$-planes $H$
such that for every $i=1,2$, $j=3,4$, and $t=1,\dotsc,s$, we have

$\dim H\cap K^{i}_{b}\ \geq\ a\,,\ \ \dim H\cap L^{j}_{b+n}\ \geq\ a+m\,,\
\mbox{ and }\ H\in\Omega_{\mu^{t}}F^{t}\,.$

Suppose that the linear subspaces $K^{i}_{b},L^{j}_{b+n}$, and the flags
$F^{t}$ are in general position. Let $H$ be a solution to this instance of
$\Box_{a,b}^{\,4}\circ{\mu^{\bullet}}$. If we set
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\Lambda}:=K^{1}_{b}\oplus
K^{2}_{b}\simeq{\mathbb{C}}^{2b}$ and
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}M}:=L^{3}_{b+n}\cap
L^{4}_{b+n}\simeq{\mathbb{C}}^{n}$, then $\dim H\cap\Lambda=2a$ and $H\cap
M=m$. Setting
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}K^{j}_{b}}:=\Lambda\cap
L^{j}_{b+n}$ for $j=3,4$, we have that
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}h}:=H\cap\Lambda$
is a solution to the Schubert problem $\Box_{a,b}^{\,4}$ in $\mbox{\rm
Gr}(2a,\Lambda)$ given by $K^{1}_{b},\dotsc,K^{4}_{b}$. Let $1\leq t\leq s$.
Since the flag $F^{t}$ is in general position,
$\dim(h+F^{t}_{r})=\dim(h)+\dim(F^{t}_{r})=2a+r$. As $M$ has codimension $2b$
and also meets $h+F^{t}_{r}$ properly, $(h+F^{t}_{r})\cap M$ has dimension
$2a{+}r{-}2b$. Thus for $1\leq r\leq n$, $(h+F^{t}_{r+2b-2a})\cap M$ defines a
flag $F^{t}(h)$ in $M$. A further exercise in dimension-counting and the
definition of Schubert variety (3) shows that $H\cap
M\in\Omega_{\mu^{t}}F^{t}(h)$.

Furthermore, for every solution $h$ to the auxiliary problem
$\Box_{a,b}^{\,4}$ in $\mbox{\rm Gr}(2a,\Lambda)$, if we define flags
$F^{i}(h)$ in $M$ as above, then, for every solution $h^{\prime}$ to the
instance of the Schubert problem ${\mu^{\bullet}}$ in $\mbox{\rm Gr}(m,M)$
given by the flags $F^{\bullet}(h)$, the direct sum $h\oplus h^{\prime}$ is a
solution to the original Schubert problem. ∎

###  6.4. An emerging landscape of Schubert Galois groups

The constructions and results described in Sections 6.2 and 6.3 arose from a
sustained investigation of Schubert Galois groups in which computer
experimentation informed theoretical advances. This began with Vakil’s seminal
paper [89]. There, he used his geometric Littlewood-Richardson rule [88] in a
method used to show a Schubert Galois group is at least alternating. He
applied this method to study Schubert Galois groups in small Grassmannians.
Subsequent experimentation and results this inspired is leading to an
understanding what to expect for Schubert Galois groups, and an outline of a
potential classification is emerging from this study.

Without delving into its (considerable) details, we sketch salient features of
Vakil’s geometric Littlewood-Richardson rule [89]. Given a Schubert problem
${\mu^{\bullet}}$ on a Grassmannian $G(m,n)$, it constructs a tree
${\mathcal{T}}_{{\mu^{\bullet}}}$ with $d({\mu^{\bullet}})$ leaves that
encodes a sequence of deformations of intersections of Schubert varieties as
the flags move into special position. Each node
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\bullet}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\bullet}$
of ${\mathcal{T}}_{{\mu^{\bullet}}}$ determines an enumerative problem which
involves intersecting a subset of the Schubert varieties in ${\mu^{\bullet}}$
with a checkerboard variety
$Y_{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\bullet}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\bullet}(E,M)$.
Here $E,M$ are two flags in a special position (determined by
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\bullet}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\bullet}$)
and
$Y_{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\bullet}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\bullet}(E,M)$
is the set of $m$-planes in $G(m,n)$ having a particular position with respect
to $E,M$ (again specified by
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\bullet}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\bullet}$).
Let
$d({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\bullet}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\bullet})$
be the number of solutions to this enumerative problem and $\mbox{\rm
Gal}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\bullet}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\bullet})$
be its Galois group.

The root of the tree ${\mathcal{T}}_{{\mu^{\bullet}}}$ is labeled by
${\mu^{\bullet}}$. For a leaf node
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\bullet}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\bullet}$,
$d({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\bullet}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\bullet})=1$.
Every node
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\bullet}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\bullet}$
of ${\mathcal{T}}_{{\mu^{\bullet}}}$ that is not a leaf has either one child
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\bullet}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\bullet}^{\prime}$
or two children
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\bullet}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\bullet}^{\prime}$
and
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\bullet}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\bullet}^{\prime\prime}$,
and we have
$d({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\bullet}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\bullet})=d({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\bullet}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\bullet}^{\prime})$,
respectively
$d({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\bullet}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\bullet})=d({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\bullet}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\bullet}^{\prime})+d({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\bullet}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\bullet}^{\prime\prime})$,
when there is one child, respectively two children. The children of a node are
in bijection with the irreducible components of the checkerboard variety
$Y_{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\bullet}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\bullet}}(E,M)$
as the flags $E,M$ become more degenerate.

######  Theorem 17 (Thms 3.2 and 3.10 of [89]).

Let
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\bullet}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\bullet}$
be a node in ${\mathcal{T}}_{{\mu^{\bullet}}}$. Suppose that the Galois group
of each child of
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\bullet}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\bullet}$
is at least alternating. Then $\mbox{\rm
Gal}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\bullet}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\bullet})$
is at least alternating if one of the following conditions (1), (2a), or (2b)
hold.

  1. (1)

${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\bullet}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\bullet}$
has a unique child.

  2. (2)

${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\bullet}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\bullet}$
has two children
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\bullet}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\bullet}^{\prime}$
and
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\bullet}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\bullet}^{\prime\prime}$,
and

    1. (a)

$d({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\bullet}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\bullet}^{\prime})\neq
d({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\bullet}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\bullet}^{\prime\prime})$
or both are equal to $1$, or

    2. (b)

$\mbox{\rm
Gal}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\bullet}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\bullet})$
is $2$-transitive, and we do not have
$d({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\bullet}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\bullet}^{\prime})=d({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\bullet}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\bullet}^{\prime\prime})=6$.

When
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\bullet}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\bullet}$
is a leaf,
$d({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\bullet}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\bullet})=1$
so that $\mbox{\rm
Gal}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\bullet}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\bullet})=S_{1}$
is at least alternating. Theorem 17 leads to Vakil’s recursive method that may
conclude $\mbox{\rm Gal}({\mu^{\bullet}})$ is at least alternating. Given a
Schubert problem ${\mu^{\bullet}}$, this method first constructs
${\mathcal{T}}_{{\mu^{\bullet}}}$, which it then investigates. If, for every
non-leaf node
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\bullet}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\bullet}$,
either (1) or (2a) hold at
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\bullet}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\bullet}$,
then it declares that $\mbox{\rm Gal}_{{\mu^{\bullet}}}$ is at least
alternating. Otherwise, the method is inconclusive. It is not a decision
procedure, but it is a useful filter to identify Schubert problems that may
have enriched Galois groups and thus are worthy of further study.

Vakil wrote a Maple script333http://math.stanford.edu/~vakil/programs/galois
that runs his method on all Schubert problems on a given Grassmannian. He ran
this on all small Grassmannians. Every Schubert Galois group on $\mbox{\rm
Gr}(2,n)$ for $n\leq 16$ and on $\mbox{\rm Gr}(3,n)$ for $n\leq 9$ was found
to be at least alternating (for $\mbox{\rm Gr}(3,n)$, Condition (2b) in
Theorem 17 was needed). As $\mbox{\rm Gr}(4,6)\simeq\mbox{\rm Gr}(2,6)$ and
$\mbox{\rm Gr}(4,7)\simeq\mbox{\rm Gr}(3,7)$, the next Grassmannian was
$\mbox{\rm Gr}(4,8)$. His algorithm was inconclusive for 14 (out of 3501)
Schubert problems on $\mbox{\rm Gr}(4,8)$. These 14 include the problem
$\Box_{2,4}^{4}$ from Example 9 and the problem of Example 13. The Galois
groups of these 14 problems are known and none are 2-transitive [56, Sect.
5.5].

A Schubert problem ${\mu^{\bullet}}$ on $\mbox{\rm Gr}(m,n)$ is simple if at
most two of the conditions in ${\mu^{\bullet}}$ are not
$\raisebox{-0.5pt}{\includegraphics{pictures/1s}}=(1,0,\dotsc,0)$. Using the
Pieri homotopy algorithm [41] to compute solutions to simple Schubert problems
and monodromy, Galois groups of many simple Schubert problems (including one
with 17,589 solutions) were shown to have full-symmetric Galois groups [54].

The first general result concerning Schubert Galois groups was given in [11].
Using Vakil’s algorithm and combinatorial reasoning, it was shown that every
Schubert problem on $\mbox{\rm Gr}(2,n)$ for all $n$ has at least alternating
Galois group. With an eye towards Condition (2b) in Theorem 17, another
general result showed that Galois groups of Schubert problems on $\mbox{\rm
Gr}(3,n)$, for every $n$ are 2-transitive [82]. Yet another general result is
that all simple Schubert problems are at least alternating [83]. These results
and computations described below suggest the following dichotomy for Schubert
Galois groups.

######  Conjecture 18.

A Schubert Galois group is either the full symmetric group or it is not
2-transitive.

Robert Williams used the method of computing Frobenius elements to show that
many Schubert problems have full symmetric Galois groups over ${\mathbb{Q}}$
[92]. These include all Schubert problems on a Grassmannian $\mbox{\rm
Gr}(2,n)$ with up to 500 solutions, as well as all simple Schubert problems on
any Grassmannian with up to 500 solutions [83], and all Schubert problems on
$\mbox{\rm Gr}(4,9)$ with at most 300 solutions [57]. The numbers here, 300
and 500, are approximate and they represent the limit of the software
used—Singular [17]—to solve a Schubert problem over a prime field (typically
${\mathbb{F}}_{1009}$) in a few hours.

We close with a sketch of the results from [57], which determined all enriched
problems on $\mbox{\rm Gr}(4,9)$. This began by using Vakil’s method, both his
maple implementation and a perl implementation by C. Brooks, to identify many
Schubert problems on $\mbox{\rm Gr}(4,9)$ that were at least alternating. For
only 233 of the 38,760 Schubert problems was the method inconclusive, and
further study found exactly 149 Schubert problems on $\mbox{\rm Gr}(4,9)$ that
had enriched Galois groups. We remark that this (and earlier computations on
$\mbox{\rm Gr}(4,8)$) only tested Schubert problems that could not be reduced
to a Schubert problem on a smaller Grassmannian.

Each of these 149 enriched Schubert problems was shown to be a fibration as in
Definition 14, where the constituent Schubert problems were on a $\mbox{\rm
Gr}(2,4)$ or a $\mbox{\rm Gr}(2,5)$, and had full symmetric Galois groups,
either $S_{2}$ or $S_{3}$ or $S_{5}$. By Proposition 15, the Schubert Galois
group of each was a subgroup of a wreath product of symmetric groups.
Computing sufficiently many Frobenius elements showed that in each case, the
Galois group was the expected wreath product. This computation is explained
and archived on the web
page444https://www.math.tamu.edu/~sottile/research/stories/GIVIX/. Of these,
120 are compositions of Schubert problems as in Proposition 16, while the
remaining 29 had a different structure.

While these results on Schubert Galois groups have not resulted in a
classification, there is an emerging landscape of what to expect, which we
summarize for Grassmannians $\mbox{\rm Gr}(m,n)$.

  * •

If $\min\\{m,n{-}m\\}=1$, then $\mbox{\rm Gr}(m,n)\simeq{\mathbb{P}}^{n-1}$,
and Schubert calculus becomes linear algebra; all Schubert problems have one
solution. There are no non-trivial Galois groups.

  * •

If $\min\\{m,n{-}m\\}=2$, then $\mbox{\rm Gr}(m,n)\simeq\mbox{\rm Gr}(2,n)$
and all Schubert Galois groups are at least alternating [11] and conjectured
to be fully symmetric.

  * •

If $\min\\{m,n{-}m\\}=3$, then $\mbox{\rm Gr}(m,n)\simeq\mbox{\rm Gr}(3,n)$
and all Schubert Galois groups are 2-transitive [82] and conjectured to be
fully symmetric.

  * •

If $\min\\{m,n{-}m\\}\geq 4$, then $\mbox{\rm Gr}(m,n)$ has enriched Schubert
problems. An enriched Schubert problem is either equivalent to one of Vakil’s
problems from Example 9, or it is a fibration of Schubert problems.

We also remark that we do not know whether or not Schubert Galois groups
depend upon the base field. In particular, are they the same for
${\mathbb{Q}}$ and for ${\mathbb{C}}$, or different?

##  7\. Galois groups in applications

Structures in polynomial systems or in enumerative geometry give information
about the associated Galois groups. In a growing number of applications of
algebraic geometry, information about associated Galois groups may be used to
detect these structures and then exploit them for solving or for understanding
the application. We sketch this in three application realms. Esterov’s partial
determination of Galois groups for sparse polynomial systems leads to a
surprisingly efficient algorithm to recursively decompose and solve sparse
systems. Work in vision reconstruction problems uses Galois groups to detect
decompositions, which are then used in efficient solvers. The classical
problem of Alt, to determine four-bar mechanisms whose coupler curve passes
through nine given points, has a hidden symmetry of order six coming from the
structure of the problem and its formulation as a system of equations.

###  7.1. Solving decomposable sparse polynomial systems

By Proposition 3, when a branched cover $\pi\colon X\to Z$ is decomposable in
that there is a Zariski open subset $V\subset Z$ over which $\pi$ factors,

$None$ $\pi^{-1}(V)\ \xrightarrow{\;\varphi\;}\ Y\ \xrightarrow{\;\psi\;}\
V\,,$

then its Galois group $\mbox{\rm Gal}_{\pi}$ is imprimitive (and vice-versa).
Améndola, Lindberg, and Rodriguez [3] proposed methods to exploit this
structure in numerical algebraic geometry. For example, when the decomposition
(2) is known explicitly, fibers of $\pi\colon X\to Z$ may be recovered from
the partial data consisting of one fiber of $\varphi\colon\pi^{-1}(V)\to Y$
and one fiber of $\psi\colon Y\to V$. They illustrated this on examples where
$V=Z$ and the first map $\varphi\colon X\to Y$ comes from the invariants of a
group acting on the fibers of $\pi$. Interestingly, their methods do not
require knowledge of the full Galois group, only of the decomposition (2).

This approach is particularly fruitful for the sparse polynomial systems of
Section 4, whose notation and definitions we use. Let
${\mathcal{A}}_{\bullet}$ be a collection of supports for a sparse polynomial
system. By Esterov’s Theorem 7, if ${\mathcal{A}}_{\bullet}$ is either
strictly lacunary or strictly triangular, then $\mbox{\rm
Gal}_{{\mathcal{A}}_{\bullet}}$ is imprimitive, and $\mbox{\rm
Gal}_{{\mathcal{A}}_{\bullet}}$ is completely determined (either a group of
units or full symmetric) in all other cases. Not only does this characterize
when the branched cover
$\pi\colon\Gamma_{{\mathcal{A}}_{\bullet}}\to{\mathbb{C}}^{{\mathcal{A}}_{\bullet}}$
is decomposable, but it leads to an algorithmic procedure for an explicit
description of the decomposition. We sketch that; As complete description is
given in [12].

When ${\mathcal{A}}_{\bullet}$ is lacunary,
${\mathbb{Z}}^{n}/{\mathbb{Z}}{\mathcal{A}}_{\bullet}$ is a nontrivial finite
group. Let
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\varphi}\colon({\mathbb{C}}^{\times})^{n}\twoheadrightarrow({\mathbb{C}}^{\times})^{n}$
be the map induced by the inclusion
${\mathbb{Z}}^{n}\xrightarrow{\sim}{\mathbb{Z}}{\mathcal{A}}_{\bullet}\subset{\mathbb{Z}}^{n}$
and the functor $\mbox{\rm Hom}(\\_{\ },{\mathbb{C}}^{\times})$. This has
kernel $\mbox{\rm
Hom}({\mathbb{Z}}^{n}/{\mathbb{Z}}{\mathcal{A}}_{\bullet},{\mathbb{C}}^{\times})$,
a group of units in $({\mathbb{C}}^{\times})^{n}$. If $\mathcal{B}_{\bullet}$
is the preimage of ${\mathcal{A}}_{\bullet}$ under the identification
${\mathbb{Z}}^{n}\xrightarrow{\sim}{\mathbb{Z}}{\mathcal{A}}_{\bullet}$, then
a system $F(x)$ with support ${\mathcal{A}}_{\bullet}$ has the form
$G(\varphi(x))$, where the system $G$ has support $\mathcal{B}_{\bullet}$.
Thus $\mbox{\rm
Hom}({\mathbb{Z}}^{n}/{\mathbb{Z}}{\mathcal{A}}_{\bullet},{\mathbb{C}}^{\times})$
acts on the solutions of any system
$F\in{\mathbb{C}}^{{\mathcal{A}}_{\bullet}}$, and in fact on the branched
cover
$\pi\colon\Gamma_{{\mathcal{A}}_{\bullet}}\to{\mathbb{C}}^{{\mathcal{A}}_{\bullet}}$.
This action is free, and the quotient variety is the branched cover
$\psi\colon\Gamma_{\mathcal{B}_{\bullet}}\to{\mathbb{C}}^{\mathcal{B}_{\bullet}}(={\mathbb{C}}^{{\mathcal{A}}_{\bullet}})$.
We have $\mbox{\rm
MV}({\mathcal{A}}_{\bullet})=|{\mathbb{Z}}^{n}/{\mathbb{Z}}{\mathcal{A}}_{\bullet}|\cdot\mbox{\rm
MV}(\mathcal{B}_{\bullet})$ and when $\mbox{\rm
MV}({\mathcal{A}}_{\bullet})>|{\mathbb{Z}}^{n}/{\mathbb{Z}}{\mathcal{A}}_{\bullet}|$,
the decomposition of
$\pi\colon\Gamma_{{\mathcal{A}}_{\bullet}}\to{\mathbb{C}}^{{\mathcal{A}}_{\bullet}}$
through the intermediate variety $\Gamma_{\mathcal{B}_{\bullet}}$ is
nontrivial.

The first of the maps in this decomposition is induced from the inclusions
$\Gamma_{{\mathcal{A}}_{\bullet}}\subset{\mathbb{C}}^{{\mathcal{A}}_{\bullet}}\times({\mathbb{C}}^{\times})^{n}$
and
$\Gamma_{\mathcal{B}_{\bullet}}\subset{\mathbb{C}}^{\mathcal{B}_{\bullet}}\times({\mathbb{C}}^{\times})^{n}$
by the identification
${\mathbb{C}}^{{\mathcal{A}}_{\bullet}}={\mathbb{C}}^{\mathcal{B}_{\bullet}}$
and the monomial map
$\varphi\colon({\mathbb{C}}^{\times})^{n}\to({\mathbb{C}}^{\times})^{n}$, from
which fibers may be explicitly computed. The map $\varphi$ is computed from
the Smith normal form of a matrix whose columns are generators of
${\mathbb{Z}}{\mathcal{A}}_{\bullet}$. Similarly, the second map is simply the
branched cover associated to the family of sparse systems of support
$\mathcal{B}_{\bullet}$. If $\mathcal{B}_{\bullet}$ is lacunary or triangular,
then this may be further decomposed. If not, then its fibers are readily
computed by numerical software such as PHCpack [90] or HomotopyContinuation.jl
[10], using the polyhedral homotopy [42].

Suppose now that ${\mathcal{A}}_{\bullet}$ is strictly triangular with witness
$\emptyset\neq I\subsetneq[n]$, so that $\mbox{\rm
rank}({\mathbb{Z}}{\mathcal{A}}_{I})=|I|$ and $1<\mbox{\rm
MV}({\mathcal{A}}_{I})<\mbox{\rm MV}({\mathcal{A}}_{\bullet})$. Then there is
a monomial change of coordinates on $({\mathbb{C}}^{\times})^{n}$ and a
reindexing of the supports so that $I=[m]$ and
${\mathcal{A}}_{1},\dotsc,{\mathcal{A}}_{m}\subset{\mathbb{Z}}^{m}$, which is
the first $m$ coordinates of ${\mathbb{Z}}^{n}$. Writing
$({\mathbb{C}}^{\times})^{n}=({\mathbb{C}}^{\times})^{m}\times({\mathbb{C}}^{\times})^{n-m}$
for the corresponding splitting, points $x\in({\mathbb{C}}^{\times})^{n}$ are
ordered pairs $x=(y,z)$ with $y\in({\mathbb{C}}^{\times})^{m}$ and
$z\in({\mathbb{C}}^{\times})^{n-m}$. Then a system $F$ with support
${\mathcal{A}}_{\bullet}$ has the form $F(x)=(G(y),H(y,z))$, where $G$ has
support ${\mathcal{A}}_{I}$ and $H$ has support ${\mathcal{A}}_{I^{c}}$, where
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}I^{c}}:=\\{m{+}1,\dotsc,n\\}$.
Any solution to $F=0$ is a pair $(y^{*},z^{*})$, where $y^{*}$ is a solution
to $G(y)=0$, and $z^{*}$ is a solution to the system $H(y^{*},z)=0$ on
$({\mathbb{C}}^{\times})^{n-m}$. This structure is apparent in the
decomposition

(9) $\Gamma_{{\mathcal{A}}_{\bullet}}\ \longrightarrow\
\Gamma_{{\mathcal{A}}_{I}}\times{\mathbb{C}}^{{\mathcal{A}}_{I^{c}}}\
\longrightarrow\
{\mathbb{C}}^{{\mathcal{A}}_{I}}\times{\mathbb{C}}^{{\mathcal{A}}_{I^{c}}}\ =\
{\mathbb{C}}^{{\mathcal{A}}_{\bullet}}\,,$

where the first map is induced by the projection
$({\mathbb{C}}^{\times})^{n}\to({\mathbb{C}}^{\times})^{m}$ onto the first $m$
coordinates applied to solutions $(y^{*},z^{*})$.

Let $p\colon{\mathbb{Z}}^{n}\to{\mathbb{Z}}^{n-m}$ be the projection to the
last $n{-}m$ coordinates and observe that for any solution $y^{*}$ to
$G(y)=0$, $H(y^{*},z)$ has support $p({\mathcal{A}}_{I^{c}})$. We have the
following product formula (see [85, Lem. 6] or [24, Thm. 1.10]),

$\mbox{\rm MV}({\mathcal{A}}_{\bullet})\ =\ \mbox{\rm
MV}({\mathcal{A}}_{I})\cdot\mbox{\rm MV}(p({\mathcal{A}}_{I^{c}}))\,.$

Since $1<\mbox{\rm MV}({\mathcal{A}}_{I})$ and $1<\mbox{\rm
MV}({\mathcal{A}}_{\bullet})/\mbox{\rm MV}({\mathcal{A}}_{I})=\mbox{\rm
MV}(p({\mathcal{A}}_{I^{c}}))$, the decomposition (9) is nontrivial. When
either ${\mathcal{A}}_{I}$ or $p({\mathcal{A}}_{I^{c}})$ is lacunary or
triangular, these maps may be further decomposed. If one is neither lacunary
or triangular, then its fibers are readily computed by numerical software as
above.

This leads to an algorithm to recursively decompose the branched cover
$\pi\colon\Gamma_{{\mathcal{A}}_{\bullet}}\to{\mathbb{C}}^{{\mathcal{A}}_{\bullet}}$.
In each decomposition, the decomposability of each factor is determined by
examining another sparse family. Given a blackbox solver (e.g.
HomotopyContinuation.jl [10] or PHCpack [90]) to compute fibers of
indecomposable branched covers, combined with the methods of Améndola, et. al
[3], results in an efficient algorithm for solving sparse polynomial systems,
which was developed in [12]. These methods have been implemented in the
Macaulay2 [30] package DecomposableSparseSystems.m2 [13]. In [12] this package
was used in an experiment in which thousands of decomposable systems were
solved, both using the black box solver PHCpack and that package (called
Algorithm 9 in [12]). Figure 4 shows a box plot of the timings.

Figure 4. Box plot of timings comparing PHCpack and Algorithm 9.

###  7.2. Vision Problems

A camera takes a 2-dimensional image of a 3-dimensional scene. The fundamental
problem of image reconstruction is to recover the scene from images taken by
cameras at different unknown locations. For this, some features (e.g. points,
lines, and incidences) are matched between images. This matching is used to
infer the camera positions, which are then used for the full reconstruction.
There are many versions of this nonlinear problem of determining camera
positions—different types of cameras and different configurations of matched
features.

A calibrated perspective camera consists of a focal point
$\mathbf{t}\in{\mathbb{R}}^{3}$ and a direction vector $\mathbf{v}$. The image
is the projection of ${\mathbb{R}}^{3}{\smallsetminus}\\{\mathbf{t}\\}$ from
the point $\mathbf{t}$ onto a plane with normal vector $\mathbf{v}$ lying a
distance 1 from $\mathbf{t}$ in the direction of $\mathbf{v}$. The image of a
point $\mathbf{x}\in{\mathbb{R}}^{3}$ is the intersection of the line between
$\mathbf{t}$ and $\mathbf{x}$ with this plane. The considered features are
some points, lines, and their incidences, which are assumed to be present in
each image.

An image reconstruction problem is specified by the number of cameras (images)
and the matched features. For example, we may have two cameras and five points
in each image. Such a problem is minimal if, for general data, there is a
positive, finite number of solutions (camera positions). The degree of the
minimal problem is this number of (complex) solutions for general data, which
is a measure of the algebraic complexity of solving the minimal problem.
Highly optimized solvers have been developed for some minimal problems [47,
65]. The minimal reconstruction problems were recently classified [20],
finding many new minimal problems. Among these new minimal reconstruction
problems are some which have imprimitive Galois groups, whose corresponding
decomposable structure may be exploited for solving [3].

We present some of the formulation of reconstruction problems. Fix a reference
frame, choosing one camera to be at the origin and to face upwards. Any other
camera is the translation of the first by an element of the special Euclidean
group, $\text{SE}_{\mathbb{R}}(3)$. A element of $\text{SE}_{\mathbb{R}}(3)$
is a pair $[\mathbf{R}\mid\mathbf{t}]$, where $\mathbf{R}\in\text{SO}(3)$ is a
rotation matrix and $\mathbf{t}\in{\mathbb{R}}^{3}$ is a translation vector.
Then $[\mathbf{R}\mid\mathbf{t}]$ represents a camera with focal point
$\mathbf{t}$ and direction vector $\mathbf{R}\mathbf{k}$, where $\mathbf{k}$
is the upward-pointing unit vector. In this way, elements of
$\text{SE}_{\mathbb{R}}(3)$ give coordinates for cameras. The fixed camera has
coordinate $[\mathbf{I}\mid\mathbf{0}]$ where $\mathbf{I}$ is the identity
matrix and $\mathbf{0}$ is the zero vector.

The image plane $\Pi$ of a camera $[\mathbf{R}\mid\mathbf{t}]$ consists of the
points $\mathbf{p}\in{\mathbb{R}}^{3}$ satisfying the equation
$(\mathbf{R}\mathbf{k})\cdot(\mathbf{p}-\mathbf{t})=1$. For
$\mathbf{x}\in{\mathbb{R}}^{3}\smallsetminus\\{\mathbf{t}\\}$, its image in
$\Pi$ is the point

$\mathbf{t}\ +\
\frac{\mathbf{x}-\mathbf{t}}{(\mathbf{R}\mathbf{k})\cdot(\mathbf{x}-\mathbf{t})}\
.$

Translating by $-\mathbf{t}$ and applying $\mathbf{R}^{-1}$ sends the image
plane $\Pi$ to the standard reference plane
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\Pi_{\mathbf{0}}}:=\\{(x,y,1)\mid
x,y\in{\mathbb{R}}\\}$ for the camera $[\mathbf{I}\mid\mathbf{0}]$. We use the
coordinates from $\Pi_{\mathbf{0}}$ to represent images of points for all
camera. Thus a point $\mathbf{y}\in\Pi_{\mathbf{0}}$ is the image of a point
$\mathbf{x}\in{\mathbb{R}}^{3}$ under the camera $[\mathbf{R}\mid\mathbf{t}]$
if

(10) $\mathbf{x}\ =\ \mathbf{R}\alpha\mathbf{y}\ +\ \mathbf{t}\,,$

where $\alpha=(\mathbf{R}\mathbf{k})\cdot(\mathbf{x}-\mathbf{t})$ is the focal
depth of the point $\mathbf{x}$ relative to $[\mathbf{R}\mid\mathbf{t}]$.
Figure 5 is a schematic showing the correspondence between five points
$\mathbf{x}\in{\mathbb{R}}^{3}$ and their images in the planes $\Pi$, for two
cameras.

$C_{1}$
---
$C_{2}$
---
$[\mathbf{R}\mid\mathbf{t}]$
---
Figure 5. Minimal problem of two cameras with five points.

Given matched configurations of points, lines, and incidences in
$\Pi_{\mathbf{0}}$ for each of several, say $n$, cameras, equations based on
(10) formulate the image reconstruction problem as a system of equations on
$(\text{SE}_{\mathbb{R}}(3))^{n-1}$. Complexifying gives a system of
polynomials that depends upon the input configuration. When the problem is
minimal, this gives a branched cover over the parameter space of all input
configurations. The degree of the branched cover is the degree of the minimal
problem. As we have seen before, there is a Galois group for each minimal
problem. When the Galois group is imprimitive, Proposition 3 implies that the
branched cover is decomposable. If a decomposition (2) is known, then that may
be exploited for solving.

One such problem with imprimitive Galois group is that of reconstructing five
points given images from two cameras, which is illustrated in Figure 5. The
branched cover corresponding to this minimal problem has degree 20. The
imprimitivity may be understood by observing that the solutions come in pairs:
Given one solution $([\mathbf{I}\mid\mathbf{0}],[\mathbf{R}\mid\mathbf{t}])$,
a second is given by rotating the camera $[\mathbf{R}\mid\mathbf{t}]$
$180^{\circ}$ around the line between the two cameras. (This also changes the
inferred positions of the unknown points $\mathbf{x}\in{\mathbb{R}}^{3}$.)
This is called a twisted pair in the literature, and we see that the Galois
group preserves the resulting partition of the 20 solutions into ten twisted
pairs, and is hence a subgroup of $S_{2}\wr S_{10}$. In fact, the Galois group
is even smaller, it is $(S_{2}\wr S_{10})\cap A_{20}$ [19], which is the Weyl
group $D_{10}$. This imprimitivity implies the associated branch cover is
decomposable and the system can be solved in stages. A decomposition for this
problem is implicit in [65].

In [19], the minimal problems of degree at most 1000 with imprimitive Galois
group were classified. Those were further studied using numerical algebraic
geometry, which led to an understanding of their structure, and for each an
explicit decomposition was found.

###  7.3. Alt’s Problem

Polynomial systems arise in engineering when designing mechanisms with a
desired range of motion. Robotic arm movements, for instance, may need to be
able to reach several positions to perform specific tasks. These movements can
be modeled by polynomial systems, from which they can be studied with the
methods discussed. One such problem due to Alt [2] is the nine-point synthesis
problem for four-bar linkages.

A four-bar linkage is a planar mechanism built from a quadrilateral (which may
self-intersect) with rotating joints and fixed side lengths. One side of the
quadrilateral is the base which is fixed in place, while the other sides move
as allowed by freely rotating the joints. The side opposite the base is the
coupler bar, and a triangle is erected on the coupler bar. In an actual
mechanism, a tool is placed at the apex of the triangle and the mechanism is
maneuvered to position the tool.

To understand this motion, consider the quadrilateral. Removing the coupler
bar, the two bars that were incident to it may each rotate freely around their
fixed points. The coupler bar imposes a distance constraint on the rotating
bars, and there remains one degree of freedom. (The abstract curve of this
motion has genus one.) In the resulting motion, the apex of the triangle
traces the coupler curve.

Figure 6. A four-bar mechanism and coupler curve.

The space of all mechanisms is nine-dimensional. Indeed, the two fixed points
may be any points in ${\mathbb{R}}^{2}$, giving four dimensions (degrees of
freedom). The lengths of each of the remaining five segments in the mechanism