Feasibility of Complex Equations and Primes in Arithmetic Progressions

One of the most basic notions in polynomial system solving is feasibility: does your system of equations have any roots? We will explore the algorithmic complexity of this problem, focussing on sparse polynomial systems over the complex numbers. In particular, we will see algorithms completely different from homotopy, resultants, and Grobner bases; and how the Generalized Riemann Hypothesis enters our setting. We will also show how earlier methods (of Grigoriev, Karpinski, Odlyzko, and Koiran), depending on unproven number-theoretic hypotheses, can be made unconditional in certain cases.

Aside from complexity-theoretic interests, our algorithms appear practical, and we illustrate this through some examples. No background in algebraic geometry or complexity theory is assumed.