Combinatorics, Special Functions and Computer Algebra
A workshop at the occasion of Peter Paule's 60th birthday

Combinatorics on polynomial equations: do they describe nice varieties?
Joachim von zur Gathen

Abstract: We consider natural combinatorial questions about systems of multivariate polynomials over a finite field and the variety V that they define over an algebraic closure. Fixing the number of variables, the number of polynomials and the sequence of degrees, there are finitely many such systems. We ask: for how many systems is V nice? Is that usually the case?
"Nice" can refer to various properties: The system is regular, the variety is a set-theoretic (or ideal-theoretic) complete intersection, it is (absolutely) irreducible, or nonsingular.
All properties usually hold. More precisely, for each of them we present a nonzero ``genericity’’ polynomial in the coefficients of the system so that the property holds when this polynomial does not vanish. The polynomials come with explicit bounds on their degrees. Over finite fields, they yield estimates on the probability for the properties to hold. These probabilities tend rapidly to 1 with growing field size.
A further important property is non-degeneracy: the variety is not contained in a hyperplane. Somewhat surprisingly, this behaves differently. Fixing the degree of V, most systems (with at least two polynomials) describe varieties that are hypersurfaces in some proper linear subspace, thus as degenerate as possible.
Joint work with Guillermo Matera.