Tibor Beke
Suppose one has an enumerative combinatorial problem that can be evaluated
over the finite fields with ,
,
, ...
elements, giving rise to
the sequence of counts
,
,
, ...
. When is the associated
generating function
Part of the Weil conjectures (ie the theorem of Grothendieck-Deligne) is
that if one counts the number of common zeroes of a set of polynomials
over bigger and bigger finite fields, then the associated generating
function is rational. We review the cohomological proof and subsequent
extensions: to counting problems that involve first-order quantifiers (due
to Kiefe, Macintyre and others) and field extensions (due to Wan). I
continue with my own work, and mention some open problems.