Galois groups of Schubert problems via homotopy computation

Leykin, Anton; Sottile, Frank

doi:10.1090/S0025-5718-09-02239-X

Galois groups of Schubert problems via homotopy computation
HTML articles powered by AMS MathViewer

by Anton Leykin and Frank Sottile PDF

Math. Comp. 78 (2009), 1749-1765 Request permission

Abstract:

Numerical homotopy continuation of solutions to polynomial equations is the foundation for numerical algebraic geometry, whose development has been driven by applications of mathematics. We use numerical homotopy continuation to investigate the problem in pure mathematics of determining Galois groups in the Schubert calculus. For example, we show by direct computation that the Galois group of the Schubert problem of 3-planes in $\mathbb {C}^8$ meeting 15 fixed 5-planes non-trivially is the full symmetric group $S_{6006}$.

References

Daniel J. Bates, Jonathan D. Hauenstein, Andrew J. Sommese, and Charles W. Wampler, Bertini: Software for numerical algebraic geometry, Available at http:// www. nd. edu/ ˜sommese/ bertini.
Daniel J. Bates, Andrew J. Peterson, Chrisand Sommese, and Charles W. Wampler, Numerical computation of the genus of an irreducible curve within an algebraic set, 2007.
Sara Billey and Ravi Vakil, Intersections of Schubert varieties and other permutation array schemes, Algorithms in algebraic geometry, IMA Vol. Math. Appl., vol. 146, Springer, New York, 2008, pp. 21–54. MR 2397936, DOI 10.1007/978-0-387-75155-9_{3}
C. I. Byrnes, Pole assignment by output feedback, Three decades of mathematical system theory, Lect. Notes Control Inf. Sci., vol. 135, Springer, Berlin, 1989, pp. 31–78. MR 1025786, DOI 10.1007/BFb0008458
William Fulton, Young tableaux, London Mathematical Society Student Texts, vol. 35, Cambridge University Press, Cambridge, 1997. With applications to representation theory and geometry. MR 1464693
The GAP Group, GAP – Groups, Algorithms, and Programming, Version 4.4.9, 2006.
Ewgenij Gawrilow and Michael Joswig, polymake: a framework for analyzing convex polytopes, Polytopes—combinatorics and computation (Oberwolfach, 1997) DMV Sem., vol. 29, Birkhäuser, Basel, 2000, pp. 43–73. MR 1785292
Joe Harris, Galois groups of enumerative problems, Duke Math. J. 46 (1979), no. 4, 685–724. MR 552521
Birkett Huber, Frank Sottile, and Bernd Sturmfels, Numerical Schubert calculus, J. Symbolic Comput. 26 (1998), no. 6, 767–788. Symbolic numeric algebra for polynomials. MR 1662035, DOI 10.1006/jsco.1998.0239
Birkett Huber and Jan Verschelde, Pieri homotopies for problems in enumerative geometry applied to pole placement in linear systems control, SIAM J. Control Optim. 38 (2000), no. 4, 1265–1287. MR 1760069, DOI 10.1137/S036301299935657X
C. Jordan (ed.), Traité des substitutions, Gauthier-Villars, Paris, 1870.
R. Baker Kearfott and Zhaoyun Xing, An interval step control for continuation methods, SIAM J. Numer. Anal. 31 (1994), no. 3, 892–914. MR 1275119, DOI 10.1137/0731048
Steven L. Kleiman, The transversality of a general translate, Compositio Math. 28 (1974), 287–297. MR 360616
S. L. Kleiman and Dan Laksov, Schubert calculus, Amer. Math. Monthly 79 (1972), 1061–1082. MR 323796, DOI 10.2307/2317421
T. Lee, T.Y. Li, and C. Tsai, Hom4ps-2.0: A software package for solving polynomial systems by the polyhedral homotopy continuation method, Available at http://www.math. msu.edu/˜li/Software.htm, 2007.
A. Leykin and F. Sottile, Galois groups of Schubert problems, 2007, http://www.math.tamu.edu/~sottile/stories/Galois.
Anton Leykin and Jan Verschelde, Interfacing with the numerical homotopy algorithms in PHCpack, Mathematical software—ICMS 2006, Lecture Notes in Comput. Sci., vol. 4151, Springer, Berlin, 2006, pp. 354–360. MR 2387182, DOI 10.1007/11832225_{3}5
Anton Leykin, Jan Verschelde, and Yan Zhuang, Parallel homotopy algorithms to solve polynomial systems, Mathematical software—ICMS 2006, Lecture Notes in Comput. Sci., vol. 4151, Springer, Berlin, 2006, pp. 225–234. MR 2387173, DOI 10.1007/11832225_{2}2
T.-Y. Li, personal communication.
T. Y. Li, Tim Sauer, and J. A. Yorke, The cheater’s homotopy: an efficient procedure for solving systems of polynomial equations, SIAM J. Numer. Anal. 26 (1989), no. 5, 1241–1251. MR 1014884, DOI 10.1137/0726069
Jim Ruffo, Yuval Sivan, Evgenia Soprunova, and Frank Sottile, Experimentation and conjectures in the real Schubert calculus for flag manifolds, Experiment. Math. 15 (2006), no. 2, 199–221. MR 2253007
H. Schubert, Anzahl-Bestimmungen für Lineare Räume, Acta Math. 8 (1886), no. 1, 97–118 (German). Beliebiger dimension. MR 1554694, DOI 10.1007/BF02417085
—, Losüng des Charakteristiken-Problems für lineare Räume. Beliebiger Dimension, Mittheil. Math. Ges. Hamburg (1886), 135–155, (dated 1885).
Michael Shub and Steve Smale, Complexity of Bézout’s theorem. I. Geometric aspects, J. Amer. Math. Soc. 6 (1993), no. 2, 459–501. MR 1175980, DOI 10.1090/S0894-0347-1993-1175980-4
Andrew J. Sommese, Jan Verschelde, and Charles W. Wampler, Introduction to numerical algebraic geometry, Solving polynomial equations, Algorithms Comput. Math., vol. 14, Springer, Berlin, 2005, pp. 301–335. MR 2161992, DOI 10.1007/3-540-27357-3_{8}
Andrew J. Sommese and Charles W. Wampler II, The numerical solution of systems of polynomials, World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2005. Arising in engineering and science. MR 2160078, DOI 10.1142/9789812567727
Frank Sottile, Pieri’s formula via explicit rational equivalence, Canad. J. Math. 49 (1997), no. 6, 1281–1298. MR 1611668, DOI 10.4153/CJM-1997-063-7
Frank Sottile, Some real and unreal enumerative geometry for flag manifolds, Michigan Math. J. 48 (2000), 573–592. Dedicated to William Fulton on the occasion of his 60th birthday. MR 1786506, DOI 10.1307/mmj/1030132734
Frank Sottile, Elementary transversality in the Schubert calculus in any characteristic, Michigan Math. J. 51 (2003), no. 3, 651–666. MR 2021013, DOI 10.1307/mmj/1070919565
Richard P. Stanley, Some combinatorial aspects of the Schubert calculus, Combinatoire et représentation du groupe symétrique (Actes Table Ronde CNRS, Univ. Louis-Pasteur Strasbourg, Strasbourg, 1976) Lecture Notes in Math., Vol. 579, Springer, Berlin, 1977, pp. 217–251. MR 0465880
Ravi Vakil, A geometric Littlewood-Richardson rule, Ann. of Math. (2) 164 (2006), no. 2, 371–421. Appendix A written with A. Knutson. MR 2247964, DOI 10.4007/annals.2006.164.371
Ravi Vakil, Schubert induction, Ann. of Math. (2) 164 (2006), no. 2, 489–512. MR 2247966, DOI 10.4007/annals.2006.164.489
J. Verschelde, Algorithm 795: PHCpack: A general-purpose solver for polynomial systems by homotopy continuation, ACM Trans. Math. Softw. 25 (1999), no. 2, 251–276, Software available at http://www.math.uic.edu/~jan.