Hostname: page-component-78c5997874-94fs2 Total loading time: 0 Render date: 2024-11-06T12:01:53.524Z Has data issue: false hasContentIssue false

UNIFORM FAMILIES OF POLYNOMIAL EQUATIONS OVER A FINITE FIELD AND STRUCTURES ADMITTING AN EULER CHARACTERISTIC OF DEFINABLE SETS

Published online by Cambridge University Press:  20 October 2000

JAN KRAJÍČEK
Affiliation:
Mathematical Institute, University of Oxford, 24–29 St.Giles', Oxford OX1 3LB Present address: Mathematical Institute, Academy of Sciences, Žitná 25, Prague 115 67, The Czech Republic, [email protected]
Get access

Abstract

Over a fixed finite field ${\bf F}_p$, families ofpolynomial equations$f_i(x_1, \dots, x_{n_N}) = 0$ for $i = 1, \dots, k_N$,that are uniformly determined by a parameter $N$, areconsidered. The notion of a uniform family is defined interms of first-order logic.A notion of an abstract Euler characteristic is used togive sense to a statement that the system has a solutionfor infinite $N$, and a statement linking the solvabilityof a linear system for infinite $N$ with its solvabilityfor finite $N$ is proved.This characterisation is used to formulate a criterionyielding degree lower bounds for various ideal membership proof systems (for example,Nullstellensatz and the polynomial calculus).Further, several results about Euler structures(structures with an abstract Euler characteristic) are proved, and the case of fields, in particular,is investigated more closely. 1991 Mathematics Subject Classification: primary 03F20, 12L12, 15A06;secondary 03C99, 12E12, 68Q15, 13L05.

Type
Research Article
Copyright
© 1999 London Mathematical Society

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)