Probabilistic Saturations and Alt’s Problem

Abstract

Alt’s problem, formulated in 1923, is to count the number of four-bar linkages whose coupler curve interpolates nine general points in the plane. This problem can be phrased as counting the number of solutions to a system of polynomial equations which was first solved numerically using homotopy continuation by Wampler, Morgan, and Sommese in 1992. Since there is still not a proof that all solutions were obtained, we consider upper bounds for Alt’s problem by counting the number of solutions outside of the base locus to a system arising as the general linear combination of polynomials. In particular, we derive effective symbolic and numeric methods for studying such systems using probabilistic saturations that can be employed using both finite fields and floating-point computations. We give bounds on the size of finite field required to achieve a desired level of certainty. These methods can also be applied to many other problems where similar systems arise such as computing the volumes of Newton-Okounkov bodies and computing intersection theoretic invariants including Euler characteristics, Chern classes, and Segre classes.

Keywords:

• Computational algebraic geometry
• modular Grobner basis
• homotopy continuation
• four-bar linkage

Acknowledgments

The authors would like to thank the Fall 2018 semester program on Nonlinear Algebra at the Institute for Computational and Experimental Research in Mathematics (ICERM) where this project was started.

Declaration of Interest

No potential conflict of interest was reported by the author(s).

Additional information

Funding

JDH was supported in part by NSF CCF 1812746.