Zeta functions of equivalence relations over finite fields (Q620933)

The motivating problem for the present article is the following. Fix a finite field \(\mathbb{F}_q\). Suppose that \(S \subseteq \mathbb{A}^n_{\mathbb{F}_q}\) and \(R \subseteq S \times S\) are constructible sets (i.e., given by polynomial equalities and inequalities with coefficients in \(\mathbb{F}_q\)) and that for all \(k \geq 1\), \(R(\mathbb{F}_{q^k})\) defines an equivalence relation \(\sim_R\) on \(S(\mathbb{F}_{q^k})\) (given by \(a \sim_R b \iff (a,b) \in R(\mathbb{F}_{q^k})\)). Let \(N_k\) be the number of \(\sim_R\)-equivalence classes on \(S(\mathbb{F}_{q^k})\) and consider the generating function \[ z(S/R; t) := \sum_{k = 1}^\infty N_k t^{k-1} . \] Theorem~1 of the present article states that this generating function is a rational function in \(t\). More precisely, it is of the form \[ z(S/R; t) = p(t) + \sum_{i = 1}^N c_i \frac{d}{dt}\log Z(\mathcal{W}_i, t), \] where \(p\) is a polynomial, \(c_i\) are rationals, and \(Z(\mathcal{W}_i, t)\) is the Weil zeta function of a variety \(\mathcal{W}_i\). For model theorists, deducing Theorem~1 from known result is very simple, and indeed the complete proof is given in the introduction of the article. However, the main interest of the article is that everything is explained to non-model-theorists, in the language of algebraic geometry. The central object of study is the category \(\text{Constr}_k\) of constructible sets over a field \(k\), where morphisms are maps with constructible graph. In model theoretic terms, this is the category of ``\(k\)-definable sets in algebraically closed fields''. More precisely, a priori definable sets are more general; the fact that every definable set is constructible follows from ``quantifier elimination'', which can be formulated algebraically as follows: if \(f: \mathcal{X} \to \mathcal{Y}\) is a morphism of varieties and \(C \subseteq \mathcal{X}\) is a constructible set, then \(f(C)\) is constructible, too. An important ingredient to the proof of Theorem~1 is that ``algebraically closed fields have elimination of imaginaries''. The author presents two equivalent algebraic formulations of this (Theorems~2 and 3) and gives a new proof. Theorem~2 says that for any \(S\) and \(R\) as above, there exists an ``effective quotient'' \(Q\) in \(\text{Constr}_k\): a coequalizer of \(R \rightrightarrows S\) such that \(R \to S \times_Q S\) is an isomorphism. Theorem~3 says that for any constructible family of constructible sets, there is a (constructible) moduli space. (If, in Theorems~2 and 3, one replaces ``constructible'' by ``definable'', then the equivalence becomes a standard exercise in model theory. In the version with constructible sets, one needs quantifier elimination for the implication ``Theorem~2 \(\Rightarrow\) Theorem~3''.) In the second part of the introduction, the author proposes some generalizations and variants of Theorem~1 which one should consider, in particular concerning groupoids defined over a finite field.