Certification for polynomial systems via square subsystems (Q820969)

Given a set of polynomials \(f = (f_1,\dots,f_N)\) with \(f_i \in \mathbb C[z_1,\dots,z_n]\), an approximate solution to the system \(f_1(z) = 0, \dots, f_N(z) = 0\) is an estimate \(\hat \zeta\) of some point \(\zeta\) in the common vanishing locus of the \(f_i\) (i.e. \(\zeta\) is a solution of the system \(f\)). By ``approximate solution'' the authors mean that the approximation error \(\| \zeta - \hat \zeta \|\) can be refined efficiently as a function of the input size and the desired precision. To verify that an approximation is suitable, numerical certification seeks to develop criteria and algorithms. In this paper the authors produce algorithms to address the following problems: \begin{itemize} \item[(1)] How to certify that a point \(\zeta \in \mathbb C^n\) is an approximate solution of \(f\)? \item[(2)] If it is known that \(f\) has \(e\) solutions, how can we certify that a set \(Z \subset \mathbb C^n\) of \(e\) points consists of approximate solutions to \(f\)? \end{itemize} The authors consider numerical certification of approximate solutions to a system of polynomial equations with more equations than unknowns by first certifying solutions to a suitable square subsystem. They give several approaches, using different additional information. Among these are liaison, Newton-Okounkov bodies, or intersection theory. They may be used to certify individual solutions, reject non-solutions, or certify that we have found all solutions.