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

Get the DVI| PS|PDF file of this abstract.