Annals of Combinatorics 2(1998) 365-385
Counting Points on Varieties over Finite Fields Related to a Conjecture of Kontsevich
John R. Stembridge
Department of Mathematics, University of Michigan, Ann Arbor, Michigan 48109--1109, USA
Received December 6, 1998
AMS Subject Classification: 05A15, 05-04, 14Q15, 68Q40
Abstract. We describe a characteristic-free algorithm for ''reducing'' an algebraic variety defined by the vanishing of a set of integer polynomials. In very special cases, the algorithm can be used to decide whether the number of points on a variety, as the ground field varies over finite fields, is a polynomial function of the size of the field. The algorithm is then used to investigate a conjecture of Kontsevich regarding the number of points on a variety associated with the set of spanning trees of any graph. We also prove several theorems describing properties of a (hypothetical) minimal counterexample to the conjecture, and produce counterexamples to some related conjectures.
Keywords: spanning trees, matroids, computational algebra