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.