First-order objects in algebraic geometry

This week I had a delightful lunch conversation with Sameera Vemulapalli about the following question: given the equations $f_i \in \mathbb{Z}[x_1, \dots, x_n]$ defining a variety in $\mathbb{C}^n$ , does the variety defined by the same equations in $\mathbb{F}_q$ have the same dimension and degree, provided that $q$ is large enough and not a power of one of finitely many “bad” primes?

My experience has been that if you walk up to someone who is experienced in algebraic geometry and ask them this question, they say “sure, that should be true” or “oh yeah, that’s known”, but nobody can come up with a proof or reference. In this article I want to put down the reason I came up with.

Lefschetz principle and Gröbner bases

The motivation behind this particular phrasing of the question is the first-order Lefschetz principle in algebraic geometry. This is a result that I know from model theory and which states that a system of polynomial equations and inequations (always with coefficients in $\mathbb{Z}$ ) has a solution in an algebraically closed field of a fixed characteristic if and only if it has a solution in the algebraic closure of the respective prime field. Moreover, if there exists a solution in characteristic zero, then a solution exists in finite fields $\mathbb{F}_q$ for all sufficiently large $q$ which are not a power of one of finitely many “bad” primes. Both of these assertions follow easily (and in the best traditions of mathematical logic) from the theory of Gröbner bases.

I was first exposed to computer algebra by Alessio d’Alì, Thomas Kahle and Bernd Sturmfels in our work on The Geometry of Gaussoids. Back then I was very puzzled by the fact that we did our computations in QQ[a12, a13, ...] and wrote in the paper about $\mathbb{C}[a_{12}, a_{13}, \dots]$ . Why were computations with polynomials over a non-algebraically closed field enough to show that a $\mathbb{Z}$ -defined polynomial system has no solution? Well, whether a system of polynomial equations and inequations

$\begin{gathered} f_i = 0, \, \text{for $i=1, \dots, s$}, \\ g_j \mathrel{\char`≠} 0, \, \text{for $j=1, \dots, t$}, \end{gathered}$

with $f_i, g_j \in \mathbb{Z}[x_1, \dots, x_n]$ has a solution in $\mathbb{C}^n$ depends (by Hilbert’s Nullstellensatz) entirely on whether a Gröbner basis of the ideal $\langle\, f_i, 1 - y\prod_j g_j\,\rangle \subseteq \mathbb{C}[x_1, \dots, x_n, y]$ is trivial. The polynomials defining this ideal have coefficients in $\mathbb{Z}$ and by Buchberger’s algorithm, a Gröbner basis can be computed without ever stepping outside of the field of fractions of $\mathbb{Z}$ , i.e., $\mathbb{Q}$ .

Side remark: Perhaps a more geometric reason for this which I learned from Computational synthetic geometry, Proposition 4.7 — and more delightful lunch conversations with Andreas Kretschmer — can be seen using the Zariski solution set of the polynomial system. To get there, first form the ideal $I$ generated by the equations $f_i$ and the multiplicative monoid $U$ generated by the inequations $g_j$ , both in $R = \mathbb{Q}[x_1, \dots, x_n]$ . The Zariski solution set is the spectrum of the ring $S$ which arises from localizing the coordinate ring $R / I$ at $U$ . $\mathrm{Spec}(S)$ contains all prime ideals in $R$ above $I$ which do not intersect $U$ . These primes are precisely the points in algebraic extensions of $\mathbb{Q}$ which solve the polynomial system — and this is all encoded in the polynomial ring $R = \mathbb{Q}[x_1, \dots, x_n]$ . I recommend checking out the proof.

Back to the Lefschetz principle. The point of this reasoning is that first-order properties such as emptiness of a ( $\mathbb{Z}$ -defined) constructible set over an algebraically closed field can be decided by a finite symbolic computation over the prime field: first compute a Gröbner basis for the radical of the equations in the system and then check whether the product of all inequations in the system reduces to zero modulo the Gröbner basis. (Or some variant of this computation, such as the one given earlier using an auxiliary variable $y$ .)

Gröbner bases, here, provide a normal form for proofs of first-order facts about varieties. The Gröbner basis proof or refutation of the solvability of the system over $\mathbb{C}$ consists of finitely many steps of elementary arithmetic operations over $\mathbb{Q}$ . (Essentially many, many, many instances of the division algorithm.) By reducing all numerators and denominators modulo a chosen prime $p$ , one either recovers a proof of the same fact over positive characteristic (hence in $\overline{\mathbb{F}_p}$ and hence in a finite extension of $\mathbb{F}_p$ ) or the proof becomes invalid because at some point in these arithmetic operations we divide by $0 \bmod p$ . Since there are only finitely many steps, there are only finitely many primes over which the reasoning breaks down.

Hilbert series, dimension and degree

These ideas can be brought to bear on other properties of varieties and this raises the question which properties are “first-order” enough to be stable under passing from $\mathbb{C}$ to sufficiently large finite fields of sufficiently large characteristics. I will just call these fields appropriate from now on, relative to a fixed set of polynomial equations. The key will be, as before, the existence of symbolic algorithms for computing these properties.

Recall that the Hilbert series of an ideal $I$ is determined by its initial ideal and hence directly by the combinatorics of a Gröbner basis. The discussion of Buchberger’s algorithm above implies that a Gröbner basis computation in $\mathbb{Q}[x_1, \dots, x_n]$ remains a valid computation of a Gröbner basis (by Buchberger’s criterion, the stopping condition is also just arithmetic) for appropriate finite fields. The Gröbner basis will look the same up to the reduction of all coefficients modulo $p$ ; and for all but finitely many $p$ the leading monomials are the same. The $k$ -th coefficient of the Hilbert series counts the number of monomials of degree $k$ which are not divisible by a leading monomial in the Gröbner basis — which does not involve the ground field at all anymore. Hence, the computation of the Hilbert series over appropriate finite fields will turn out the same as over $\mathbb{Q}$ .

In particular, the dimension and degree, which are encoded in the Hilbert series, of the variety over appropriate finite fields are fully determined by the complex variety. This includes the special case of the number of points in a zero-dimensional complex variety. And the equality goes both ways: the opposite direction justifies a common heuristic in computer algebra to try difficult computations over finite fields first (to avoid explosion of numerators and denominators in $\mathbb{Q}$ ) and still hopefully get useful information. I have recently been trying to solve a surprisingly unruly system of polynomial equations given to me by Laszlo Csirmaz for which exactly the explosion of coefficients in the Gröbner basis appears to be the major problem. Per suggestion and (much appreciated!) help from Anna-Laura Sattelberger, I could finally get a Gröbner basis of this ideal over $\mathbb{F}_7$ in Singular and it confirms some very exciting observations from the numerical irreducible decomposition in Bertini — one step closer to a solution. Until the problem is completely solved, I am satisfied to understand the finite field method and to have seen its success in practice.

Addendum (06 July 2022): Frédéric Chyzak kindly pointed out to me at the ISSAC conference dinner that (depending on the implementation) it will not make a huge difference if the prime in the finite field heuristic is 7 or, say, 9973, because both fit into a machine word, so for the CPU all coefficients would be the same size and arithmetic on them equally cheap. The larger prime should give better information for the same cost. My one Singular computation supports that remark. Thanks!