Notes on the model theory of finite and pseudo-finite fields Zoé Chatzidakis, CNRS - Université Paris 7.

These notes contain the material covered during a mini-course given at the University of Helsinki, 22 - 29 April 2009. The reader wishing to see more on pseudo-finite fields can also consult the notes on the course given in Madrid (November 2005), posted on my web page. The main part of this course is based on a paper by James Ax [A], The elementary theory of finite fields. The interested reader can find a very complete account of the theory of finite fields in the book of Fried and Jarden [FJ].

The course was funded by the Finnish network MALJA. I also thank the audience for their enthusiasm and comments.

Table of contents Section 1. Finite fields - properties page 2 Section 2. An aside - a result of Ax 4 Section 3. Axiomatisation of a candidate for the theory of finite fields 7 Section 4. Showing that T_{f}^{∗} ⊢ T_{f} 12 Section 5. More results on pseudo-finite fields 17 Section 6. Measure, definability and other applications 18 Bibliography 27 1. Finite fields - properties

(1.1) Basic properties of finite fields

The characteristic of a unitary commutative ring is the smallest positive integer n such that 1 + 1 + ⋯ + 1 (n times) equals 0. If there is no such integer n, one says that the characteristic is 0. If R is a finite ring, and a fortiori a finite field, then its characteristic is finite. Hence, if F is a finite field, the homomorphism ℤ → F which sends 1 ∈ ℤ to 1 ∈ F must have kernel a prime ideal, i.e., pℤ for some prime p.

Conversely, if p is a prime number, then pℤ is a maximal ideal of ℤ and ℤ/pℤ is a field with p elements. This field is denoted by 𝔽_{p}, and it is the prime field of characteristic p, i.e., it is contained in every field of characteristic p (by the above). In a field of characteristic 0, the subring generated by 1 is (isomorphic to) ℤ, and therefore the field also contains the field of fractions of ℤ, ℚ. We call ℚ the prime field of characteristic 0.

Let F be a finite field of characteristic p > 0. Since 1 ∈ F, it necessarily contains the field 𝔽_{p}, and is therefore a vector space over 𝔽_{p}, whence of cardinality p^{n} for some n ∈ ℕ.

Let F be a field of characteristic p having q = p^{n} elements, let K be an algebraically closed field containing F. Let us consider the multiplicative group F^{×} = F \ {0} of F. It has q − 1 elements and hence every non-zero element of F satisfies the equation X^{q−1} − 1 = 0. [If G is a finite group of size n, then every element g of G satisfies g^{n} = 1]. Thus all elements of F satisfy X^{q} − X = 0. Let f(X) = X^{q} − X, a polynomial over 𝔽_{p}. Then f′(X) = qX^{q−1} − 1 = −1 because “q = 0” since it is a power of the characteristic. Hence all roots of F (X) = 0 are simple roots, and we obtain

X^{q} − X = ∏_{a∈F}(X − a).

Indeed, since every element of 𝔽_{q} satisfies X^{q} − X = 0, we know that each (X − a), a ∈ 𝔽_{q}, divides X^{q} − X, and therefore so does their product ∏_{a∈F} (X − a). Degree considerations and the fact that the coefficient of X^{q} is 1 imply that these two polynomials are equal.

Conversely, let us consider the set S ⊂ K of all solutions of X^{q} − X = 0. As above, its roots are all distinct. S is closed under multiplication, and S \ {0} by multiplicative inverse. Because we are in characteristic p and q is a power of p, we obtain, using the binomial expansion of (a + b)^{n} and the fact that “p = 0”, that (a + b)^{p} = a^{p} + b^{p}, and (a + b)^{q} = a^{q} + b^{q}. This implies that S is closed under addition, and is therefore a subfield of K.

So, we have shown: Theorem. Let F be a finite field. Then for some prime p and q = p^{n}, F has q elements. Its elements are exactly the roots of the equation X^{q} − X = 0.

(1.2) Existence? We actually haven’t shown that for every n there is a field with p^{n} elements. To do that, we accept that 𝔽_{p} exists, and that it embeds into some algebraically closed field K. Then, one shows, by induction on the degree n of a polynomial f(X), that f(X) can be written as the product of an element c ∈ K (c is the coefficient of X^{n}) and of n linear terms (X − a) for some elements a ∈ K. Thus, in K, the polynomial X^{q} − X is the product of q linear factors of this form, and because the derivative of X^{q} − X is identically equal to −1, these roots are simple: i.e., X^{q} − X has q distinct solutions in K. By the above, the set S of these roots is a field with q elements, and which is unique up to isomorphism. We denote this field by 𝔽_{q}.

(1.3) The Frobenius map. We have noticed above that when F is a field of characteristic p, then (a + b)^{p} = a^{p} + b^{p} for a, b ∈ F. The map x ↦ x^{p} is therefore a ring morphism (as it obviously is a multiplicative map). Also, as x^{p} = 0 implies x = 0, it is injective. The map x ↦ x^{p} is called the Frobenius map, and I will denote it by Frob_{p}, or Frob. Similarly, if q = p^{n}, then I’ll denote Frob^{n} also by Frob_{q}.

(1.4) The multiplicative group of a finite field. Let F = 𝔽_{q} be a finite field. We will show that F^{×} is cyclic. It can be written as a finite direct sum of cyclic subgroups, and if it is not cyclic, then its exponent^{1} m is a proper divisor of q − 1. But all roots of X^{q−1} = 1 are simple roots, whence all roots of X^{m} = 1 are simple as well. This implies that q − 1 = m.

(1.5) Perfect fields. A field F of characteristic p > 0 is perfect if every element of F has a p-th root. By convention, every field of characteristic 0 is perfect.

If F = 𝔽_{p^{n}} is finite, then the order of F^{×} is prime to p, which implies that every element is (multiplicatively) divisible by p, i.e., F is perfect. Another way of seeing this is the fact that the map Frob : x ↦ x^{p} is injective: as F is finite, it must be onto.

An example of imperfect field is 𝔽_{p}(t), where t is transcendental over 𝔽_{p}. Then the image by Frob of 𝔽_{p}(t) is 𝔽_{p}(t^{p}).

(1.6) The algebraic closure of 𝔽_{p}.

Let m, n be positive integers, p a prime. Then

𝔽_{p^{m}} ⊆ 𝔽_{p^{n}} ⟺ m divides n,

and in that case we have [𝔽_{p^{n}} : 𝔽_{p^{m}}] = n/m.

Indeed, if 𝔽_{p^{m}} ⊆ 𝔽_{p^{n}} then 𝔽_{p^{n}} is in particular an 𝔽_{p^{m}}-vector space, which implies that for some ℓ, |𝔽_{p^{n}}| = |𝔽_{p^{m}}|^{ℓ}, i.e., p^{n} = p^{mℓ} and n = mℓ. We then have [𝔽_{p^{n}} : 𝔽_{p^{m}}] = ℓ. Conversely, if m divides n, then p^{m} − 1 divides p^{n} − 1, whence all roots of X^{p^{m}−1} = 1 are contained in 𝔽_{p^{n}}, i.e., 𝔽_{p^{m}} ⊆ 𝔽_{p^{n}}.

It follows easily that for any m, n ≥ 1,

𝔽_{p^{m}} ∩ 𝔽_{p^{n}} = 𝔽_{p^{d}} and 𝔽_{p^{m}}𝔽_{p^{n}}

where d is the greatest common divisor of m and n, and e is the least common multiple of m and n. Here, 𝔽_{p^{m}}𝔽_{p^{n}} denotes the field composite of 𝔽_{p^{m}} and 𝔽_{p^{n}}, i.e., the subfield (of the large algebraically closed field K) they generate.

Let α be algebraic over 𝔽_{p}. Then 𝔽_{p}(α) is a finite-dimensional 𝔽_{p}-vector space, and is therefore also finite. This implies that the algebraic closure 𝔽_{p}^{alg} of 𝔽_{p} is ⋃_{n∈ℕ} 𝔽_{p^{n}}. [I assume known the fact that every element of the algebraic closure of a field satisfies a

1 The exponent of a group G is the smallest n > 0 such that every element g ∈ G satisfies g^{n} = 1, and ∞ if such an n doesn’t exist. non-trivial equation with coefficients in the field. One can also show the result directly: if f(X) is a non-constant polynomial with coefficients in ⋃_{n∈ℕ} 𝔽_{p^{n}}, then it in fact belongs to 𝔽_{q}[X] for some q = p^{n}; hence the roots of f(X) generate a finite field.]

(1.7) More on the Frobenius map. The Frobenius map is the identity on 𝔽_{p} (since every element of 𝔽_{p} satisfies X^{p} − X = 0), and defines an automorphism of each 𝔽_{p^{n}}. Hence it defines an element φ of Aut(𝔽_{p}^{alg}/𝔽_{p}). Observe that if d ∈ ℕ, the elements of 𝔽_{p}^{alg} which are fixed by φ^{d} are precisely the elements of 𝔽_{p^{d}}. Furthermore, one checks that the restriction φ|_{𝔽_{p^{d}}} of φ to 𝔽_{p^{d}} has order exactly d: φ^{ℓ} being the identity on 𝔽_{p^{d}} means

exactly that all elements of 𝔽_{p^{d}} satisfy X^{p^{ℓ}} = X, and therefore that d divides ℓ.

As [𝔽_{p^{d}} : 𝔽_{p}] = d, we know that Aut(𝔽_{p^{d}}/𝔽_{p}) has siez at most d. Since φ ∈ Aut(𝔽_{p^{d}}/𝔽_{p}) has order exactly d, this therefore implies that

Aut(𝔽_{p^{d}}/𝔽_{p}) ≃ ℤ/dℤ,

and that φ generates Aut(𝔽_{p^{d}}/𝔽_{p}).

(1.8) Description of Aut(𝔽_{p}^{alg}/𝔽_{p}). While we will not explicitly use it, we can now describe completely Aut(𝔽_{p}^{alg}/𝔽_{p}). As 𝔽_{p}^{alg} is a direct limit of the finite fields 𝔽_{p^{n}}, it follows, by Galois duality, that

Aut(𝔽_{p}^{alg}/𝔽_{p}) = lim_{←} ℤ/nℤ := ℤ̂.

The connecting maps are, for n dividing m, the canonical projection ℤ/mℤ → ℤ/nℤ. That is, the group ℤ̂ is described as the set of sequences (a_{n})_{n} ∈ ∏_{n>1} ℤ/nℤ such that if n divides m, then a_{n} ≡ a_{m}mod n. It is a profinite group, i.e., an inverse limit of finite groups. It is a closed subgroup of ∏_{n>1} ℤ/nℤ, where each ℤ/nℤ is equipped with the discrete topology, and we take the product topology on ∏_{n>1} ℤ/nℤ. The element φ = Frob_{p} is a topological generator of Aut(𝔽_{p}^{alg}/𝔽_{p}): its restriction to any 𝔽_{q} generates Aut(𝔽_{q}/𝔽_{p}).

2. An aside: a result of Ax

(2.1) The fact that 𝔽_{p}^{alg} is a union of finite fields, has a very nice consequence: Let X̄ = (X_{1}, …, X_{n}) and f̄(X̄) be an n-tuple^{2} of polynomials 𝔽_{p}^{alg}[X̄]. Assume that f̄(X̄) defines an injective map f̃: (𝔽_{p}^{alg})^{n} → (𝔽_{p}^{alg})^{n}. Then f̃ is also surjective.

Proof. Indeed, the elements of f̄ have their coefficients in some 𝔽_{q}, and therefore the restriction of f̃ to 𝔽_{q}^{n} is also injective; as 𝔽_{q} is finite, f̃|_{𝔽_{q}^{n}} is surjective. This being true on

all finite fields containing 𝔽_{q}, we obtain the result.

(2.2) Theorem (Ax) Let f̄(X̄) be a n n-tuple of polynomials in ℂ[X̄], X̄ = (X_{1}, …, X_{n}), and assume that the map f̃ it defines ℂ^{n} → ℂ^{n} is injective. Then it is also surjective.

2 In class I forgot to say/insist that f̄ had to be an n-tuple of polynomials for the map f̃ to make sense. Sorry.

There are two proofs of this result, which we present below. They are essentially equivalent, but one of them uses ultraproducts. Proof 1 of Ax’s result (2.2). One uses the fact that the completions of the theory ACF of algebraically closed fields^{3} is obtained by specifying the characteristic. Thus the theory of algebraically closed fields of characteristic 0 is obtained by adding to ACF an infinite set of sentences: for each prime p, an axiom saying that “p ≠ 0”. Any statement true in all (or some) algebraically closed fields of characteristic 0 must therefore be true in all algebraically closed fields of sufficiently large characteristic. Let m_{i}(X̄), i = 1, …, N(d), be an enumeration of the monomials in X̄ = (X_{1}, …, X_{n}) of degree ≤ d, and consider the formulas φ(x̄), ψ(x̄), where x̄ = (x_{i,j})_{1≤i≤n,1≤j≤N(n)}, and ȳ = (y_{1}, …, y_{n}), z̄ = (z_{1}, …, z_{n}):

\begin{matrix}φ(x̄) : & ∀ȳ, z̄ (⋀_{i} ∑_{j} x_{i,j}m_{i}(ȳ) = ∑_{i} x_{i,j}m_{i}(z̄)) → (ȳ = z̄) \\ ψ(x̄) : & ∀z̄∃ȳ ⋀_{i} ∑_{j} x_{i,j}m_{i}(ȳ) = z_{i}. \end{matrix}

Thus φ(x̄) says that the map f̃ defined by the n-tuple f̄(X̄) of polynomials, with f_{i}(X̄) = ∑_{j} x_{i,j}m_{j}(X̄), i = 1, …, n, is injective, while ψ(x̄) says that f̃ is surjective.

All algebraically closed fields of positive characteristic satisfy ∀x̄ φ(x̄) → ψ(x̄), hence also ℂ satisfies this sentence. This proves the theorem.

(2.3) Ultraproducts Definitions. Let I be a set, (A_{i}, i ∈ I), a family of L-structures, and F a subset of P(I) (P(I) is the set of subsets of I).

(1) F is a filter (on I) iff: (i) ∅ ∉ F; (ii) if X, Y ∈ F then X ∩ Y ∈ F; (iii) if X ∈ F and Y ⊇ X then Y ∈ F.

(2) F is an ultrafilter iff it is a maximal filter, i.e., is contained properly in no filter. One shows easily that a filter F is an ultrafilter if and only if, for every X ⊆ I, either X or I \ X is in F.

(3) A filter F is principal iff there is some i ∈ I such that {i} ∈ F. If there is no such i, it is called non-principal.

(4) We define an L-structure on the Cartesian product ∏_{i∈I} A_{i} as follows. We view an element a of ∏_{i∈I} A_{i} as a function from I to the disjoint union of the A_{i}’s, whose value at i is in A_{i}. If f is an n-ary function symbol, R is an n-ary function symbol, and (a_{1}, …, a_{n}) ∈ ∏_{i∈I} A_{i}, then f(a_{1}, …, a_{n})(i) = f(a_{1}(i), …, a_{n}(i)), and ∏_{i∈I} A_{i} ⊧ R(a_{1}, …, a_{n}) iff A_{i} ⊧ R(a_{1}(i), …, a_{n}(i)) for every i ∈ I. Finally, the interpretation of a constant c is the function which to i associates the interpretation of c in A_{i}.

(5) Let F be a filter on I. We define an equivalence relation ≡_{F} on ∏_{i∈I} A_{i} by setting

a ≡_{F} b ⟺ {i ∈ I | a(i) = b(i)} ∈ F.

3 The theory ACF is axiomatised by adding to the theory of fields for every n ≥ 1 the axiom expressing that every polynomial of degree exactly n has a solution: ∀y_{0}, …, y_{n−1} ∃x x^{n}+ ∑_{i=0}^{n−1} y_{i}x^{i} = 0.

The equivalence class of a ∈ ∏_{i∈I} A_{i} will be denoted by [a]_{F}, and the set of equivalence classes by ∏_{i∈I} A_{i}/F. ∏_{i∈I} A_{i}/F has a natural L-structure: the constant c is interpreted by [c]_{F}; f([a_{1}]_{F}, …, [a_{n}]_{F}) = [f(a_{1}, …, a_{n})]_{F}, and R([a_{1}]_{F}, …, [a_{n}]_{F}) holds iff {i ∈ I | A_{i} ⊧ R(a_{1}(i), …, a_{n}(i))} ∈ F. The structure ∏_{i∈I} A_{i}/F is called the reduced product of the structures A_{i} with respect to F. If F is an ultrafilter, then ∏_{i∈I} A_{i}/F is called the ultraproduct of the A_{i} with respect to F. If all A_{i} are equal to the same structure A, then we talk of reduced power and of ultrapower of A.

(6) Observe that the natural map ∏_{i∈I} A_{i} → ∏_{i∈I} A_{i}/F is a homomorphism of Lstructures.

(2.4) Examples. If I is finite, then all ultrafilters on I are principal. Note that if F is principal, say {j} ∈ I, then the ultraproduct ∏_{i∈I} A_{i}/F is naturally isomorphic to A_{j}.

The best known non-principal filter (on an infinite set I) is called the Fréchet filter and is the set of all subsets X of I such that I \ X is finite. It is contained in all non-principal ultrafilters on I (Exercise).

Observe that if A ⊆ I is infinite, then it intersects every cofinite subset of I; hence A and the Fréchet filter generate a (proper) filter, and A belongs to a non-principal ultrafilter.

(2.5) Łos’ Theorem. Let I be infinite, F a filter on I, (A_{i})_{i∈I} a family of L-structures, and A = ∏_{i∈I} A_{i}/F.

(1) Let φ(x) be a positive L-formula, a a tuple in ∏_{i∈I} A_{i}. Then

A ⊧ φ([a]_{F}) ⟺ {i ∈ I | A_{i} ⊧ φ(a(i))} ∈ F.

(2) Assume in addition that F is an ultrafilter, and let φ(x) be any formula, a a tuple in

∏_{i∈I} A_{i}. Then

A ⊧ φ([a]_{F}) ⟺ {i ∈ I | A_{i} ⊧ φ(a(i))} ∈ F.

This result is not difficult to prove, using induction on the complexity of the formulas. Note the restriction in (1) of φ(x) being positive: the result definitely doesn’t hold for formulas involving a negation, as can be shown by the following easy example. Let a, b ∈ ∏_{i} A_{i}. Then [a]_{F} = [b]_{F} ⟺ {i ∈ I | a(i) = b(i)} ∈ F. But if F is not an ultrafilter, choose A ⊂ I such that A and I \ A are not in F; then (assuming |A_{i}| ≥ 2 for all i, choose b such that {i ∈ I | a(i) = b(i)} = A. Clearly [a]_{F} ≠ [b]_{F} but {i ∈ I | a(i) ≠ b(i)} ∉ F.

(2.6) One immediate consequence of Łos’ theorem is that if F is an ultrafilter on I, then the L-structure A embeds elementarily into its ultrapower A^{I}/F, via the map which to an element a associates [â]_{F}, where â is the function taking the value a on I.

(2.7) Theorem (Keisler-Shelah). Two L-structures A and B are elementarily equivalent if and only if they have isomorphic ultrapowers.

(2.8) Second proof of Ax’s result (2.2). Let U be a non-principal ultrafilter on the set of all primes p, and consider K = ∏_{p} 𝔽_{p}^{alg}/U. Then this is an algebraically closed field of characteristic 0, of size 2^{ℵ_{0}}, and therefore is isomorphic to ℂ. By Łos’s theorem, since every 𝔽_{p}^{alg} satisfies the sentence ∀x̄ φ(x̄) → ψ(x̄), so does ℂ.

3. Axiomatisation of a candidate for the theory of finite fields In this section, we will give an axiomatisation of a theory, which we will call T_{f}^{∗}, and

verify that finite fields are models of T_{f}^{∗}. We will also study its infinite models. In the next section, we will show that this theory is the theory T_{f} of all finite fields, i.e., is the set of sentences which are true in all finite fields.

(3.1) The theory T_{f}^{∗} will be obtained by adding to the theory of fields the following axiom schemes:

– Axiom 1 saying that the fields are perfect,

– Axiom 2(ℓ) saying that the field has exactly one algebraic extension of degree ℓ, for every ℓ > 1,

– Axiom 3(m, n, d) a scheme of axioms expressing that the field is pseudo-algebraically closed (abbreviated by PAC), see definition below (3.8) (for every m, n, d ∈ ℕ).

(3.2) Axiom 1. This one is easy: for each prime p, add the axiom

p = 0 → ∀y∃x y = x^{p}.

(3.3) First half of Axiom 2(ℓ). Fix ℓ, we will first define a formula Irr_{ℓ}(ȳ), where ȳ = (y_{0}, …, y_{ℓ−1}), which says that the polynomial P_{ℓ}(ȳ)(X) := X^{ℓ} + y_{ℓ−1}X^{ℓ−1} + y_{ℓ−2}X^{ℓ−2} + ⋯ + y_{0} is irreducible, i.e., is not the product of two polynomials of lower (non-zero) degree. The formula Irr_{ℓ}(ȳ) expresses that ∀z_{0}, …, z_{ℓ−1}, for all 1 ≤ d < ℓ the polynomials X^{ℓ} +y_{ℓ−1}X^{ℓ−1} +y_{ℓ−2}X^{ℓ−2} +⋯+y_{0} and (X^{d} +z_{d−1}X^{d−1} +⋯+z_{0})(X^{ℓ−d} +z_{ℓ−1}X^{ℓ−d−1} + z_{ℓ−2}X^{ℓ−d−2} + ⋯ + z_{d}) are not equal. I.e., Irr_{ℓ}(ȳ) is the disjunction over j = 0, …, ℓ − 1, of the formulas

y_{j} ≠ ∑_{i=0}^{d−1} z_{i}z′_{j−i}

where z′_{m} = z_{ℓ−d+m} if 0 ≤ m < ℓ − d, z′_{m} = 1 if m = ℓ − d, and z′_{m} = 0 otherwise.

So the first half of axiom 2(ℓ) will say ∃ȳ Irr_{ℓ}(ȳ). A field F which satisfies this axiom will therefore have an algebraic extension of degree ℓ.

(3.4) Second half of Axiom 2(ℓ). To finish this axiomatisation, we need to say that this extension is unique. Equivalently, that if P (X) and Q(X) are irreducible polynomials of degree ℓ, then the extension of F generated by a root of P (X) contains a root of Q(X).

In order to do that, we first need to show that we can interpret, uniformly in the ℓ-tuple ȳ (which satisfies Irr_{ℓ} in the field F) the extension generated over F by a root of the polynomial P_{ℓ}(ȳ)(X).

(3.5) Interpretation of a finite algebraic extension of a field inside the field. Let ā = (a_{0}, …, a_{ℓ−1}) be an ℓ-tuple satisfying Irr_{ℓ} in the field F. Let α be a root of P_{ℓ}(ā)(X), and recall that

F (α) ≃_{F} F [X]/(P_{ℓ}(ā)(X)).

In particular F (α) is an F -vector space of dimension ℓ, with basis {1, α, α^{2}, …, α^{ℓ−1}}. This remark allows us to interpret easily, inside F and uniformly in the ℓ-tuple ā, the structure (F (α), +, ×, 0, 1, P_{F}), where +, ×, 0, 1 are the usual addition, multiplication and constants on the field F (α), and P_{F} is a unary predicate for the subfield F. We let S = F^{ℓ} (the direct sum of ℓ copies of F), +^{∗} the usual addition on the vector space S, and 0^{∗} = (0, 0, …, 0), 1^{∗} = (1, 0, …, 0), P_{F}^{∗} the set of elements {(b, 0, …, 0) | b ∈ F }. Clearly these sets, elements and relations are definable in F, with no parameters.

Multiplication by α induces a linear transformation of the vector space F (α), and its matrix is

M_{α} = ( \begin{matrix}0 & 0 & ⋯ & 0 & −a_{0} \\ 1 & 0 & ⋯ & 0 & −a_{1} \\ ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & 0 & ⋯ & 1 & −a_{ℓ−1} \end{matrix} )

since α^{ℓ} = − ∑_{i=0}^{ℓ−1} a_{i}α^{i}. Note that multiplication by α^{i} is also a linear transformation, and its matrix is simply M_{α}^{i}. So, we define ×^{∗} as follows

(x_{1}, …, x_{ℓ}) ×^{∗} (y_{1}, …, y_{ℓ}) = (x_{1}I_{ℓ} + x_{2}M_{α} + ⋯ x_{ℓ}M_{α}^{ℓ−1}) ( y_{1} ; y_{2} ; ⋮ ; y_{ℓ} ) .

Here I_{ℓ} denotes the identity (ℓ × ℓ)-matrix. Observe that the definition of ×^{∗} uses the tuple (a_{0}, …, a_{ℓ−1}), but is totally uniform.

Hence, there is a formula θ^{∗}(x̄, ȳ) of the language of fields, such that if Irr_{ℓ}(ā) and Irr_{ℓ}(b̄) hold for some ℓ-tuples ā and b̄ in F and α is a root of P_{ℓ}(ā)(X), then F ⊧ θ^{∗}(ā, b̄) if and only if F (α) ⊧ ∃z P_{ℓ}(b̄)(z) = 0.

So, axiom 2 (ℓ) is:

∃x̄ Irr_{ℓ}(x̄) ∧ ∀ȳ[Irr_{ℓ}(ȳ) → θ^{∗}(x̄, ȳ)].

(3.6) A comment on this condition. The condition of having at most one extension of each degree is equivalent to the following: whenever L is an algebraic extension of F of degree n, then Aut(L/F) ≃ ℤ/nℤ. In particular, Aut(L/F) is abelian and cyclic. For a proof, see e.g. (3.6) in the Madrid notes. You may also want to read some very basic facts on Galois theory which appear in that section.

(3.7) Algebraic sets, varieties . . .. Let F be a perfect field, Ω a large algebraically closed field containing it, and F^{alg} the algebraic closure of F (inside Ω). Given an n-tuple ā in Ω, we look at

I(ā/F) = {f(X̄) ∈ F [X̄] | f(ā) = 0}.

We then have the following result:

I(ā/F)Ω[X̄]is prime ⟺ F (ā) ∩ F^{alg} = F.

Here X̄ = (X_{1}, …, X_{n}), I(ā/F)Ω[X̄] denotes the ideal generated by I(ā/F) inside Ω[X̄]. If I(ā/F) satisfies one of these equivalent conditions, then we say it is absolutely prime.

This terminology also applies to any prime ideal of F [X̄] which generates a prime ideal in Ω[X̄].

An algebraic subset of Ω^{n} is the set of solutions of some (finite) set of polynomial equations with coefficients in Ω. The algebraic sets are the closed subsets of a topology on Ω^{n}, the Zariski topology. This topology is Noetherian, and therefore every closed set is the union of finitely many irreducible closed subsets^{4}. Thus to an algebraic set S we can associate I(S), the set of polynomials in Ω[X̄] which vanish at all points of S. The set S is a variety iff the ideal I(S) is prime, iff it is closed irreducible. It will be defined over F if I(S) is generated by its intersection with F [X̄]. A point of S is F -rational if all its coordinates are in F, and the set of F -rational points is denoted S(F).

(3.8) Pseudo-algebraically closed fields. A field F is pseudo-algebraically closed (abbreviated by PAC) if every variety V defined over F has an F -rational point.

Before showing that being PAC is an elementary property, we will show an easy property of PAC fields:

(3.9) Lemma. Let F be a perfect PAC field, L a field containing F, and assume that L ∩ F^{alg} = F. Then F is existentially closed in L, denoted F ≺_{1} L, i.e.: every existential formula with parameters in F which is true in L is true in F.

Proof. An existential formula of L(F) is of the form ∃ ȳφ(ȳ), where φ(ȳ) is a boolean combination of polynomial equations with coefficients in F. Hence a disjunct of conjuncts of polynomial equations and inequations (over F), and we may therefore assume it is a conjunction of equations and inequations^{5}. Using the fact that modulo the theory of fields, the formula x ≠ 0, is equivalent to ∃y xy = 1, we may assume that φ(ȳ) is a conjunction of polynomial equations with coefficients in F.

Let ā ∈ L be a solution of φ(ȳ). Since L ∩ F^{alg} = F, we know that the ideal I(ā/F) = {f(X̄) ∈ F [X̄] | f(ā) = 0} is an absolutely prime ideal, see (3.7). I.e., the set V of tuples on which all elements of I(ā/F) vanish is a variety, which is defined over F. Since F is PAC, it follows that there is some tuple b̄ on which all polynomials of I(ā/F) vanish. Hence, b̄ satisfies every polynomial equation over F that ā satisfies, and in particular, will satisfy φ.

(3.10) Comments. The condition L ∩ F^{alg} = F is clearly necessary: if α ∈ L ∩ F^{alg} and α ∉ F, and if p(X) is the minimal polynomial of α over F, then L ⊧ ∃y p(y) = 0, but F ⊧ ∀y p(y) ≠ 0.

It is in general not a sufficient condition. E.g., we will see that one can find a pseudofinite field F such that F ∩ 𝔽_{p}^{alg} = 𝔽_{p}, and clearly 𝔽_{p} ⊀_{1} F.

(3.11) Theorem. There is a theory (in the language of rings) whose models are exactly the PAC fields.

Proof. Fix integers m, n, d. We need to express the following:

4 A closed set U is irreducible if whenever U = U_{1} ∪ U_{2} with U_{1}, U_{2} closed, then U_{1} = U or U_{2} = U

5 Use that each of ∃ȳ φ_{i}(ȳ), i = 1, 2, implies ∃ȳ (φ_{1}∨φ_{2})(ȳ) to get rid of the disjunctions.

Let f_{1}(X̄), …, f_{m}(X̄) be polynomials in X̄ = (X_{1}, …, X_{n}) of degree ≤ d, and assume they generate an absolutely prime ideal. Then they have a common zero.

This follows from results of Hermann, see below (3.14). If d is an integer, then we denote by F [X̄]_{≤d} the set of polynomials of degree ≤ d. They form a finite dimensional F -vector space, and are therefore definable in F. The following maps are also definable: Addition: F [X̄]_{≤d} × F [X̄]_{≤d} → F [X̄]_{≤d}, Multiplication: F [X̄]_{≤d} × F [X̄]_{≤d} → F [X̄]_{≤2d}.

(3.12) Results of Hermann. (For a proof, see [He] or [S].)

(1) There is a constant A = A(n, d) such that for every field F, polynomials f_{1}, …, f_{m}, g ∈ F [X̄]_{≤d}, if g belongs to the ideal of F [X̄] generated by f_{1}, …, f_{m}, then there are h_{1}, …, h_{m} ∈ F [X̄]_{≤A} such that g = ∑_{i=1}^{m} f_{i}h_{i}.

(2) There is a constant B = B(n, d) such that for every field F, for every ideal I of F [X] generated by elements of F [X]_{≤d} and for every g ∈ F [X]_{≤d}, if g^{k} ∈ I for some integer k, then g^{B} ∈ I.

(3) There is a constant C = C(n, d) such that for every field F, ideals I and J generated by elements of F [X]_{≤d}, the ideals I ∩J and J : I = {f ∈ F [X] | fI ⊆ J} are generated by elements of F [X]_{≤C}.

(4) There is a constant D = D(n, d) such that for every field F and ideal I of F [X] generated by elements of F [X]_{≤d}, if I is not prime, then there are g, h ∈ F [X]_{≤D} such that gh ∈ I but g, h ∉ I.

(5) There is a constant E = E(n, d) such that for every field F and ideal I of F [X] generated by elements of F [X]_{≤d}, there are at most E minimal prime ideals containing I, and they are generated by elements of F [X]_{≤E}.

(3.13) Corollary. Let n, d ≥ 1. There is a formula φ(ȳ), ȳ an mN(d)-tuple of variables, such that in every field F, for every mN(d)-tuple ā in F, if f_{1}, …, f_{m} is the m-tuple of elements of F [X̄]_{≤d} encoded by ā, then

F ⊧ φ(ā) ⟺ the ideal of F [X̄] generated by f_{1}, …, f_{m} is prime.

Proof. Let D = D(n, d), A = A(n, D). Then f_{1}, …, f_{m} generate a prime ideal I in F [X̄]

if and only if for all g, h ∈ F [X̄]_{≤D}, either gh ∉ I or one of g, h is in I,

if and only if for all g, h ∈ F [X̄]_{≤D}, either for all h_{1}, …, h_{m} ∈ F [X̄]_{≤A}, gh ≠ ∑_{i=1}^{m} h_{i}f_{i}, or there are h_{1}, …, h_{m} ∈ F [X̄]_{≤A} such that [g = ∑_{i=1}^{m} h_{i}f_{i} or h = ∑_{i=1}^{m} h_{i}f_{i}].

This last statement is clearly an elementary property of the mN(d)-tuple ā of coefficients of f_{1}, …, f_{m}.

(3.14) Corollary. Let n, d ≥ 1. There is a quantifier-free formula ψ(ȳ), ȳ an mN(d)- tuple of variables such that in every field F, for every mN(d)-tuple ā in F, if f_{1}, …, f_{m} is the m-tuple of elements of F [X̄]_{≤d} encoded by ā, then

F ⊧ ψ(ā) ⟺ the ideal of F^{alg}[X] generated by f_{1}, …, f_{m} is prime.

Proof. Take the formula φ(ȳ) given by (3.13). By quantifier-elimination of the theory of algebraically closed fields^{6}, there is a quantifier-free formula ψ(ȳ) such that in every algebraically closed field K, for every mN(d)-tuple ā in K we have

K ⊧ φ(ā) ⟺ K ⊧ ψ(ā).

But if the tuple ā is in the subfield F of K, we have

K ⊧ ψ(ā) ⟺ F ⊧ ψ(ā).

Thus F ⊧ ψ(ā) if and only if the m-tuple (f_{1}, …, f_{m}) of F [X̄]_{≤d} encoded by ā generates a prime ideal in F^{alg}[X̄].

(3.15) The theorem of Lang-Weil ([LW]). For every positive integers n, d, there is positive constant C (= C(n, d)) such that for every finite field 𝔽_{q} and variety V defined by polynomials in 𝔽_{q}[X_{1}, …, X_{n}]_{≤d},

||V (𝔽_{q})| − q^{dim(V)}| ≤ Cq^{dim(V)−1/2}.

[Recall that V (𝔽_{q}) is the set of points of V ∩ 𝔽_{q}^{n}, and dim(V) is the dimension of V, i.e., tr.deg(𝔽_{q}(V)/𝔽_{q}).]

In particular, if q > C^{2}, then any variety V as above will have a rational point in 𝔽_{q}. Indeed, we get

0 < −Cq^{dim(V)−1/2} + q^{dim(V)} ≤ |V (𝔽_{q})|.

The constant C can be effectively computed.

(3.16) Axiom 3(m, n, d). So the third axiom will simply say: whenever f_{1}(X̄), …, f_{m}(X̄) are polynomials in X̄ = (X_{1}, …, X_{n}) of degree ≤ d and which generate an absolutly prime ideal, then there is an n-tuple ā such that ⋀_{i} f_{i}(ā) = 0, unless the field has less than C(n, d) elements.

(3.17) Definition A field F is pseudo-finite iff it satisfies the axioms 1, 2(ℓ) and if it is PAC. In other words, if it is an infinite model of the theory T_{f}^{∗}. Theorem.

(1) Finite fields are models of the axioms 1, 2(ℓ) and 3(m, n, d). In other words they are models of the theory T_{f}^{∗} introduced in (3.1).

(2) Let Q be the set of all prime powers, and let U be a non-principal ultrafilter on Q. Then the field F^{∗} = ∏_{q∈Q} 𝔽_{q}/U is a pseudo-finite field.

Proof. Clearly any infinite model of the scheme of axioms 3(m, n, d) is pseudo-algebraically closed, so it suffices to show the first assertion. The result of Lang-Weil (3.15) gives scheme of axioms 3(m, n, d). We also know that finite fields are perfect, and that they have exactly one algebraic extension of each degree.

6 Modulo the theory ACF, every formula is equivalent to a quantifier-free formula.

4. Showing that T_{f}^{∗} ⊢ T_{f}.

So, we have shown that the theory T_{f}^{∗} is satisfied by every finite field, and therefore is contained in the theory T_{f} of all finite fields. In order to show that T_{f}^{∗} axiomatises the theory of all finite fields, we need to show the converse. I.e., that if a sentence θ is true in all finite fields, then it is true in all models of T_{f}^{∗}. Since such a sentence is obviously true in all finite models of T_{f}^{∗}, it remains to show that it is true in all pseudo-finite fields. In other words, we need to show that the pseudo-finite fields are exactly the infinite models of the theory T_{f}.

To do that, it is enough to show that if F is a pseudo-finite field, then F is elementarily equivalent to an ultraproduct of finite fields. Indeed, this will imply that a formula which is true in all finite fields is also true in this arbitrary infinite model of T_{f}^{∗} (by Łos’ theorem), and therefore that T_{f} = T_{f}^{∗} (or rather, T_{f}^{∗} ⊢ T_{f}).

The strategy to do that, is to describe the completions of the theory T_{f}^{∗}, or rather, of the theory Psf of pseudo-finite fields, obtained by adding to T_{f}^{∗} axioms saying that there are infinitely many elements.

Once we have described the completions of Psf, we will relatively easily obtain the result, as well as some “quantifier-elimination” results.

The main tool in the description of the completions of Psf is the following

(4.1) The embedding Lemma. (Simplified version). Let K, E, K^{∗} be perfect fields, contained in some large algebraically closed field Ω, and such that

(1) K ⊂ E, K^{∗},

(2) K^{alg} ∩ K^{∗} = K^{alg} ∩ E = K,

(3) K^{∗} is pseudo-finite and ℵ_{1}-saturated,^{7}

(4) E is countable, has at most one extension of each degree. Then there is a field embedding φ : E^{alg} → K^{∗}^{alg} such that φ|_{K} = id and φ(E) ⊆ K^{∗}.

Thus in particular, φ(E)^{alg} ∩ K^{∗} = φ(E).

I will not give a proof of this result, as it uses the Galois correspondence in an essential way. You can find a proof in (6.8) of the Madrid notes, or in the book of Fried and Jarden.

(4.2) Theorem. Let K and L be pseudo-finite fields, containing a common subfield k. Assume that

k^{alg} ∩ K = k^{alg} ∩ L = k.

Then K ≡_{k} L (i.e., K and L are elementarily equivalent in the language L(k) obtained by adding to the language of rings constant symbols for the elements of k). Proof. If the result is false, then a formula showing it is false will only involve finitely many parameters from k. Hence, we may assume that k is countable. Passing to elementary extensions of K and L, we may also assume that K and L are ℵ_{1}-saturated: if K ≺ K^{∗}, L ≺ L^{∗} and K^{∗} ≡_{k} L^{∗}, then also K ≡_{k} L.

7 Recall that a model M is ℵ_{1}-saturated if for every countable subset A of M, and set Σ(x) of formulas with parameters in A, if Σ is finitely consistent, then it has a realisation in M. Every model has an elementary extension which is ℵ_{1}-saturated.

We now consider the following family I of partial isomorphisms: f : A → B, where A ⊂ K and B ⊂ L, is in I if and only if it is a field isomorphism, A and B are countable, and A^{alg} ∩ K = A, B^{alg} ∩ L = B.

We will show that the family I has the back-and-forth property, i.e.:

– If f ∈ I and a ∈ K there is g ∈ I extending f and with a in its domain,

– and if b ∈ L, there is g ∈ I extending f and with b in its image.

Suppose we have f and a as above. Let E = A(a)^{alg} ∩ K. We first extend f to an automorphism f̃ of the big algebraically closed field Ω in which we are working, and let E_{0} = f̃(E). We wish to use the Embedding lemma (4.1). We already know that E_{0} ∩B^{alg} = B, since we had E ∩A^{alg} ⊂ K ∩A^{alg} = A. Furthermore, as E^{alg} ∩K = E, and K has at most one algebraic extension of each degree, we know that E has at most one algebraic extension of each degree: indeed, if M is an algebraic extension of E of degree n, then MK is an algebraic extension of K of degree n also. This property is preserved by f̃, and we may therefore apply the Embedding lemma to B, E_{0}, L: there is ψ : E_{0} → L which is the identity on B and such that ψ(E_{0})^{alg} ∩ L = ψ(E_{0}). Then g = ψf̃|_{E} is our desired element of I.

The other direction (back) follows by symmetry.

(4.3) Back and forth? This is just a saturated version of Ehrenfeuch-Fraïssé games. One shows by induction on the number of quantifiers, that if f ∈ I, then f preserves all formulas with n quantifiers, i.e., if φ(x̄) has n quantifiers, and ā is in the domain of f, then K ⊧ φ(ā) if and only if L ⊧ φ(f(ā)).

(4.4) Definition. If K is a field and k_{0} ⊆ K the prime subfield of K (i.e., the field of fractions of the subring of K generated by 1; it equals ℚ or 𝔽_{p}), then the (field of) absolute numbers of K is the field k_{0}^{alg} ∩ K.

(4.5) Corollary. The completions of Psf are obtained by describing the isomorphism type of the field of absolute numbers of a model. Proof. Clear from Theorem (4.2): if F_{1} and F_{2} are pseudo-finite and have isomorphic fields of absolute numbers k, then F_{1} ≡ F_{2}.

(4.6) Corollary. If F_{1} ⊆ F_{2} are pseudo-finite fields then

F_{1} ≺ F_{2} ⟺ F_{1}^{alg} ∩ F_{2} = F_{1}.

Proof. This follows from Theorem (4.2), with k = F_{2}.

(4.7) Corollary (Kiefe). Modulo the theory Psf, any formula φ(x̄) is equivalent to a Boolean combination of formulas of the form ∃t f(x̄, t) = 0, where f(X̄, T) ∈ ℤ[X̄, T]. Proof. By compactness, it suffices to show that if F_{1}, F_{2} are two pseudo-finite fields of the same characteristic, and ā, b̄ are n-tuples in F_{1}, F_{2} respectively, such that for every f(X̄, T) ∈ ℤ[X̄, T],

(1)  F_{1} ⊧ ∃t f(ā, t) = 0 ⟺ F_{2} ⊧ ∃t f(b̄, t) = 0,

then for any formula φ(x̄), we have

F_{1} ⊧ φ(ā) ⟺ F_{2} ⊧ φ(b̄).

By Theorem (4.2), this last condition is equivalent to the existence of an isomorphism between the fields A = k_{0}(ā)^{alg} ∩ F_{1} and B = k_{0}(b̄)^{alg} ∩ F_{2}, where k_{0} is the prime subfield of F_{1} and F_{2}. We will show that (1) implies that such an isomorphism exists. First of all note that there is an isomorphism φ : k_{0}(ā) → k_{0}(b̄) which sends ā to b̄: this is because the tuples ā and b̄ satisfy the same polynomial equations over k_{0}. Extend φ to φ : k_{0}(ā)^{alg} → k_{0}(b̄)^{alg}. We need to show that such a φ can be chosen with φ(A) = B. Equivalently, we need to find σ ∈ Aut(k_{0}(b̄)^{alg})/k_{0}(b̄)) such that σ(φ(A)) = B. We know that for any f(X̄, T) ∈ ℤ[X̄, T], we have

φ(A) ⊧ ∃t f(b̄, t) = 0 ⟺ B ⊧ ∃t f(b̄, t) = 0.

The result will now follow from the following lemma:

(4.8) Lemma. Let B be a field, and B_{1}, B_{2} two perfect subfields of B^{alg}. Assume that for every f(T) ∈ B[T] we have

B_{1} ⊧ ∃t f(t) = 0 ⟺ B_{2} ⊧ ∃tf(t) = 0.

Then there is σ ∈ Aut(B^{alg}/B) such that σ(B_{1}) = B_{2}. Proof. If the characteristic is p > 0 and b ∈ B, then there is a unique element of B^{alg} satisfying X^{p} = b, so we can assume that B is also perfect. As B^{alg} is the the union of finite normal extensions of B, we will show that for any finite normal^{8} extension L of B, we have

B_{1} ∩ L ≃_{B} B_{2} ∩ L.

For each finite normal extension L of B consider

S_{L} = {σ ∈ Aut(B^{alg}/B) | σ(L ∩ B_{1}) = L ∩ B_{2}}.

Claim. S_{L} is not empty.

Let α ∈ L be such that L ∩ B_{1} = B(α), and let f(T) be its minimal polynomial^{9}. Then B_{1} ⊧ f(α) = 0, and so there is some β ∈ B_{2} such that f(β) = 0. Let σ ∈ Aut(L/B) be such that σ(α) = β. Then certainly σ(B_{1}) ⊆ B_{2}, and therefore [B_{1} : B] ≤ [B_{2} : B]. The symmetric argument gives [B_{2} : B] ≤ [B_{1} : B], and this implies that the degrees are equal, and σ(B_{1}) = B_{2}. Lift σ to an element of Aut(B^{alg}/B).

Thus the family S_{L}, L ranging over all finite normal extensions of B, has the finite intersection property: If L and M are finite normal extensions of B, then so is their field

8 A normal extension of a field B is an extension L which is stable under all elements of Aut(B^{alg}/B). Equivalently, if f(T) is an irreducible polynomial of B[T], then either L contains all roots of f(T), or it contains none.

9 That such an element exists is because B is perfect composite^{10} LM ans we have S_{LM} ⊆ S_{L} ∩ S_{M}. By compactness of the profinite group Aut(B^{alg}/B), there is some σ in the intersection of all S_{L}, and this σ satisfies σ(B_{1}) = B_{2}.

(4.9) Another way of stating Corollary (4.5) is to say that modulo Psf, every sentence is equivalent to a Boolean combination of sentences ∃t f(t) = 0, where f(T) ∈ ℤ[T].

What are the constraints on fields of absolute numbers of pseudo-finite fields? Actually, none, beside the fact that they must have at most one extension of each degree. [Recall that they must be relatively algebraically closed in a field having exactly one extension of each degree]. Hence ℚ^{alg} is allowable, as is any subfield of 𝔽_{p}^{alg}.

To finish the proof that T_{f} = T_{f}^{∗}, it therefore suffices to prove the following:

(4.10) Theorem. Let k = 𝔽_{p} or k = ℚ, and let E ⊆ k^{alg} have at most one extension of each degree. Then there is an ultraproduct K^{∗} of finite fields such that the field of absolute numbers of K^{∗} is isomorphic to E. When the characteristic of E is 0, K^{∗} can be chosen to be an ultraproduct of prime fields. Proof. We will start with the easy cases, when the characteristic of E is p > 0. The characteristic 0 case will need Chebotarev’s theorem, see below (4.11) Case 1. E is infinite (and of characteristic p).

Let n_{m} be a sequence of integers such that n_{m} divides n_{m+1}, and E = ⋃_{m} 𝔽_{p^{nm}}. For instance, as 𝔽_{p} = ⋃_{m} 𝔽_{p^{m!}}, we can define n_{m} by 𝔽_{p^{nm}} = E ∩ 𝔽_{p^{m!}}. Let U be any non-principal ultrafilter on ℕ such that {n_{m} | m ∈ ℕ} ∈ U, and let K^{∗} = ∏_{m} 𝔽_{p^{nm}} /U. Then K^{∗} ∩ 𝔽_{p}^{alg} ≃ E.

Indeed, clearly K^{∗} is of characteristic p. Let d ∈ ℕ. If 𝔽_{p}^{d} ⊂ E, then 𝔽_{p^{d}} will be contained in all fields 𝔽_{p^{nm}} with m ≥ d. Hence, by Łos’ theorem, K^{∗} will satisfy the sentence “there is an element of multiplicative order exactly p^{d} − 1”, and therefore will contain (a copy of) 𝔽_{p^{d}}. On the other hand, if 𝔽_{p}^{d} ⊄ E, then 𝔽_{p^{d}} is contained in no 𝔽_{p^{nm}}, therefore K^{∗} will satisfy “there is no element of multiplicative order exactly q^{d} − 1”, and K^{∗} will not contain 𝔽_{q^{d}}. Hence we will have K^{∗} ∩ 𝔽_{p}^{alg} = 𝔽_{q}. Case 2. E is finite.

Let q = |E|, so that E = 𝔽_{q}. Consider any non-trivial ultrafilter U on the set P of prime numbers, and let K^{∗} = ∏_{ℓ∈P} 𝔽_{q}^{ℓ}/U. Then K^{∗} is of characteristic p and contains 𝔽_{q}. But, if d > 1, all but at most one field 𝔽_{q^{ℓ}} satisfy “there is no element of multiplicative order exactly p^{d} − 1”, and therefore K^{∗} ∩ 𝔽_{p}^{alg} = 𝔽_{q}. Case 3. E is of characteristic 0.

Write ℚ^{alg} as the union of an increasing chain L_{n}, n ∈ ℕ, of finite Galois extensions of ℚ. For each n, let E_{n} = L_{n} ∩ F, and let I(n) be the (finite) set of subfields of L_{n} which properly contain E_{n}. We will find a sentence θ_{n} which describes L_{n} ∩ F. Choose a generator α of E_{n} over ℚ, and let f_{n}(T) be its minimal polynomial over ℚ. Similarly, for each M ∈ I(n), choose a generator β_{M} of M over ℚ, let g_{M}(T) be the minimal polynomial of β_{M} over ℚ, and define g_{n}(T) = ∏_{M∈I(n)} g_{M}(T). Consider now the sentence θ_{n} : ∃t f_{n}(t) = 0 ∧ ∀t g_{n}(t) ≠ 0. This is a sentence satisfied by E, and if F is any field of characteristic 0, then F ⊧ θ_{n} ⟺ F ∩ L_{n} ≃ E_{n}.

10 the subfield of B^{alg} generated by L and M.

As the L_{n}’s form an increasing chain, so do the E_{n}’s, and we have θ_{n} → θ_{n−1}. In order to find an ultraproduct of prime fields with field of absolute numbers isomorphic to F, it is therefore enough to show that for each n, the set

S_{n} := {p ∈ P | 𝔽_{p} ⊧ θ_{n}}

is infinite. As S_{n} ⊃ S_{n+1}, there will be a non-principal ultrafilter U containing all S_{n}’s, and if K^{∗} = ∏_{p∈P} 𝔽_{p}/U, then K^{∗} ⊧ θ_{n} for each n, i.e.: K^{∗} ∩ ℚ^{alg} ≃ E.

That S_{n} is infinite follows from Tchebotarev’s theorem. Here is the consequence of Tchebotarev’s theorem that we will use:

(4.11) Let f_{1}(T), …, f_{m}(T), g(T) ∈ ℤ[T], T a single variable. Let L be the Galois extension of ℚ obtained by adjoining all roots of the polynomials f_{i}(T), i = 1, …, m. Assume that there is a subfield E of L such that Aut(L/E) is cyclic and

E ⊧ ⋀_{i=1}^{m} ∃t f_{i}(t) = 0 ∧ ∀t g(t) ≠ 0.

Then the set of prime numbers p such that 𝔽_{p} ⊧ ⋀_{i=1}^{m} ∃t f_{i}(t) = 0 ∧ ∀t g(t) ≠ 0 is infinite.

(4.12) Decidability issues. Observe first that by Theorem (4.10) we have

Psf ⊂ Psf_{0} ⊂ T_{prime} and Psf ⊂ T_{f} ⊂ T_{prime}.

(Here Psf_{0} denotes the theory of pseudo-finite fields of characteristic 0 and T_{prime} the theory of all prime fields. We will first show that the theory Psf is decidable, that is, that there is an algorithm which decides, given a sentence θ, whether it is true in all pseudo-finite fields or not. From this we will be able to derive the decidability of the other theories.

We have an enumeration of a set Γ consisting of axioms for the theory Psf (this assumes that the bounds given in (3.12) on degrees of polynomials can be computed effectively, but they can). Hence, we can produce an enumeration of the set of all proofs made using axioms of Γ, and therefore of the theory Psf (by the completeness theorem, if a sentence is true in all pseudo-finite fields, then it is provable from Γ). Similarly, we have an enumeration of a set Γ_{0} of axioms for the theory Psf_{0} of all pseudo-finite fields of characteristic 0, and of the theory Psf_{0}. Note that Γ_{0} = Γ ∪ {p ≠ 0 | p a prime}.

This tells us that if θ is in Psf, then going through the enumeration of Psf we will find it. However, we need another procedure to decide if θ ∉ Psf. This is what we will do below. Let us fix a sentence θ.

Let ψ_{n}, n ∈ ℕ, be an enumeration of all sentences which are Boolean combinations of sentences of the form ∃t f(t) = 0, where f(T) ∈ ℤ[T]. By (4.9), we know that Γ ⊢ θ ↔ ψ_{n} for some n, i.e., θ ↔ ψ_{n} ∈ Psf, and therefore we can effectively find this ψ_{n}. Note that the proof of θ ↔ ψ_{n} uses only a finite number of axioms expressing the PAC property, and we can therefore find a constant C_{1} (given by Lang-Weil (3.15)) such that in all finite fields 𝔽_{q} with q > C_{1} we have

𝔽_{q} ⊧ θ ↔ ψ_{n}.

It now remains to decide whether ψ_{n} is true in all pseudo-finite fields. I.e., we need to show that if k is a prime field, and E ⊆ k^{alg} has at most one algebraic extension of each degree, then E ⊧ ψ_{n}. Step 1. Decide whether ψ_{n} ∈ Psf_{0} or not.

We know that ψ_{n} is (equivalent to) a disjunction of sentences of the form ⋀_{i} ∃t f_{i}(t) = 0 ∧ ∀t g(t) ≠ 0. Let L be the extension of ℚ generated by all roots of all polynomials appearing in ψ_{n}. Then one can compute effectively Aut(L/ℚ), as well as those subfields E of L such that Aut(L/E) is cyclic. Hence we can decide whether or not ψ_{n} is true in all subfields E of L such that Aut(L/E) is cyclic. If it is not, then ψ_{n} ∉ Psf_{0} and therefore ψ_{n} ∉ Psf, i.e., θ ∉ Psf_{0}, θ ∉ Psf. Step 2. Decide whether ψ_{n} ∈ Psf.

Assume that ψ_{n} ∈ Psf_{0}. Then it is provable from Γ_{0}, and its proof only uses finitely many axioms expressing that the characteristic is ≠ p; therefore there is a constant C_{2} such that ψ_{n} holds in all pseudo-finite fields of characteristic p > C_{2}. It therefore remains to check whether ψ_{n} holds in all pseudo-finite fields of characteristic p ≤ C_{2}. Fix one such p. Then, as in step 1 we let 𝔽_{p^{m}} be the extension of 𝔽_{p} generated by all roots of polynomials appearing in ψ_{n}. It then suffices to check whether 𝔽_{p^{d}} ⊧ ψ_{n} or not for all d dividing m. This is certainly decidable, and finishes the proof that Psf is decidable. Step 3. Decidability of T_{f} and of T_{prime}.

We assume now that all pseudo-finite fields satisfy θ. Hence there is a proof of θ from Γ, and this proof will involve only finitely many axioms saying that varieties have points. Hence, there is a constant C_{3} such that T_{f} ∪ {there are at least C_{3} elements} proves θ. It now remains to check whether θ holds in the finitely many finite fields of size < C_{3}. But this is decidable.

Similarly, assume that all pseudo-finite fields of characteristic 0 satisfy θ. Then the proof of θ from Psf_{0} uses only finitely many axioms saying that varieties have points and that “p ≠ 0”, and there is a constant C_{4} such that T_{f} ∪ {“p ≠ 0”, p < C_{4}} proves θ. It now remains to check whether θ holds in the finitely many prime fields of size < C_{4}. [So we didn’t need C_{1} after all].

5. More results on pseudo-finite fields If M is a structure, and φ(x̄) is a formula in the language of M, we denote by φ(M)

the set of tuples in M satisfying φ.

(5.1) Examples of pseudo-finite fields. If F is an infinite subfield of 𝔽_{p}^{alg}, then F is PAC by the theorem of Lang-Weil (3.15), and is perfect. Hence, any infinite subfield F of 𝔽_{p}^{alg} pseudo-finite as soon as it satisfies axiom 2(ℓ) for all ℓ. (By group theory results, it actually suffices to have it for all primes). Hence, if f is any function from the set of prime numbers to the positive integers, and F is the field composite of all 𝔽_{p^{f(ℓ)}}, ℓ a prime, then F is pseudo-finite.

This gives us many pseudo-finite fields of positive characteristic. In characteristic 0, there are no such explicit examples. However a result of Jarden (see [FJ] for a proof) shows that there are many such fields. The profinite group Aut(ℚ^{alg}/ℚ) is compact, and has a unique Haar probability measure. In the sense of this measure, for almost all σ ∈ Aut(ℚ^{alg}/ℚ), the subfield of ℚ^{alg} fixed by σ is pseudo-finite. Other examples are of course non-principal ultraproducts of prime fields.

(5.2) Quantifier-elimination results for pseudo-finite fields. An easy consequence of Kiefe’s result (4.7) is: Theorem. Let L′ be the language obtained by adding to the language of rings an (n + 1)- ary predicate R_{n} for every n > 1, and add to the theory Psf the axioms

R_{n}(x_{0}, …, x_{n}) ⟺ ∃y ∑_{i=0}^{n} x_{i}y^{i} = 0,

to obtain a theory Psf′. Then Psf′ eliminates quantifiers. Proof. Let F_{1} and F_{2} be pseudo-finite fields, containing a common L′-substructure A. Then A is a subring. We need to show that F_{1} ≡_{A} F_{2}. By Lemma (4.8) (or its proof), there is an isomorphism f : A^{alg} ∩ F_{1} → A^{alg} ∩ F_{2} which is the identity on A. Now apply Theorem (4.2).

(5.3) A language in which Psf is model complete. We form the language L_{c} by adjoining to the language L of rings new constant symbols c_{i,n}, where 2 ≤ n ∈ ℕ and 0 ≤ i ≤ n − 1. The theory Psf_{c} is obtained by adding to the theory Psf for each n an axiom stating that the polynomial X^{n} + ∑_{i=0}^{n−1} c_{i,n}X^{i} is irreducible.

Note that every pseudo-finite field expands to a model of Psf_{c}: if F is pseudo-finite, for each n choose the c_{i,n} to be the coefficients of some (monic) irreducible polynomial of degree n.

Recall that a theory T is model complete if whenever M ⊆ N are models of T, then M ≺ N. If T is model complete, then every formula is equivalent modulo T to an existential formula (and to a universal formula). Theorem. The theory Psf_{c} is model complete. Proof. Let F_{1} ⊆ F_{2} be models of Psf_{c}. If L is an algebraic extension of F_{1} of degree n, then L is generated over F_{1} by a solution of the equation X^{n} + ∑_{i=0}^{n−1} c_{i,n}X^{i}. Since F_{i} ⊧ Psf_{c}, this polynomial stays irreducible over F_{2}, i.e., F_{2} ∩ L = F_{1}. By (4.6), we obtain F_{1} ≺ F_{2}.

(5.4) Other quantifier-elimination results. Fried and Sacerdote introduce a more geometric language, in which one has quantifier elimination. They are using “Galois formulas”, and the process is called “elimination through Galois stratification”. The elimination procedure is primitive recursive. For details see [FHJ1] or [FJ]. One should note that this is the language that Denef and Loeser found more convenient to set up motivic integration in [DL].

(5.5) Results of Kiefe on Zeta and Poincaré series. Recall that if R is a ring, then R[[t]], the ring of formal power series over R, is the set of formal sums ∑_{i=0}^{∞} a_{i}t^{i}. Addition and multiplication are defined by

∑ a_{i}t^{i} + ∑ b_{j}t^{j} = ∑(a_{i} + b_{i})t^{i},  ∑_{i} a_{i}t^{i} ∑ b_{j}t^{j} = ∑_{n}( ∑_{i+j=n} a_{i}b_{j})t^{n}.

[Note that there are only finitely many non-negative integers such that i + j = n, so that ∑_{i+j=n} a_{i}b_{j} is a finite sum and is well defined].

Let φ(x̄) be an L-formula, with parameters in 𝔽_{q}, some q = p^{n}, p a prime. For each s ≥ 1, we define

N_{s}(φ) = |φ(𝔽_{q^{s}})|.

We then define two formal series over ℚ, the Poincaré series P and the Zeta series Z by

P (φ, t) = ∑_{s=1}^{∞} N_{s}(φ)t^{s}, Z(φ, t) = exp(∑_{s=1}^{∞} \frac{N_{s}(φ)}{s}t^{s}).

Theorem (Kiefe). P (φ, t) is rational in t (i.e., is of the form p(t)/q(t), with p(t), q(t) ∈ ℚ[t], and q(0) ≠ 0), and Z(φ, t) = exp(f(t))(g(t)/h(t))^{1/ℓ} for some integer ℓ and polynomials f(t), g(t), h(t) ∈ ℚ[t].

Note that we have the functional equation

P (φ, t) = t\frac{d}{dt}(log(Z(φ, t))), Z(θ, 0) = 1.

Hence the first assertion will follow from the first. When φ is a quantifier-free formula, this is a result of Dwork. For a proof, see the book of Fried and Jarden [FJ], for instance. The proof given there uses Galois formulas.

6. Measure, definability, and other applications

(6.1) Counting points. We saw in Theorem (4.10) that every pseudo-finite field is elementarily equivalent to an ultraproduct of finite fields. This implies in fact that every pseudo-finite field elementarily embeds into an ultraproduct of finite fields (an ultrapower of ultraproducts is an ultraproduct). Now, every finite field can be equipped with a measure (the counting measure), and one would think that the ultraproduct of these measures might define something interesting on F. It turns out that this is the case, and we will see below how it works. The main tool is the following Theorem ([CDM]). Let φ(x̄, ȳ) be a formula, x̄ an n-tuple of variables (ȳ an m-tuple of variables). Then there is a finite set D ⊂ {0, 1, …, n} × ℚ^{>0} ∪ {(0, 0)} of pairs (d, μ), and a constant C > 0, formulas φ_{d,μ}(ȳ) for (d, μ) ∈ D such that:

(1) If 𝔽_{q} is a finite field and ā an m-tuple in 𝔽_{q}, then there is some (d, μ) ∈ D such that

||φ(𝔽_{q}, ā)| − μq^{d}| < Cq^{d−1/2}.  (∗)

[Here φ(𝔽_{q}, ā) denotes the set {b̄ ∈ 𝔽_{q}^{n} | 𝔽_{q} ⊧ φ(b̄, ā)}.]

(2) The formula φ_{d,μ}(ȳ) defines in each 𝔽_{q} the set of tuples ā such that (∗) holds. I am not going to give a proof of this result, although I will later sketch a strategy for

the proof. With some work one can show that the constant C can be found effectively, see [FHJ2], and also [FS], [FHJ1]. First a few remarks.

(6.2) Remarks.

(1) Observe that the pair (0, 0) has been put in D to take care of the case when φ(𝔽_{q}, ā) is empty.

(2) If φ(x̄, ā) defines a variety V, then this is simply the Theorem of Lang-Weil, with d = dim(V) and μ = 1.

(3) Thus, if φ(x̄, ā) defines an algebraic set W, all of whose irreducible components are defined over 𝔽_{q}, then d will be the maximal dimension of the irreducible components of W, and μ the number of these components of maximal dimension. Note that therefore, if φ(x̄, ȳ) is quantifier-free, then the associated set of pairs will be contained in {0, …, n} × ℕ^{>0} ∪ {(0, 0)}.

(4) If q is sufficiently large, the formulas φ_{d,μ}(ȳ) will define a partition of the parameter set 𝔽_{q}^{m}.

(5) If n = 1, then there are positive numbers A ∈ ℕ and r ∈ ℚ such that for every 𝔽_{q} and

tuple ā in 𝔽_{q},

either |φ(𝔽_{q}, ā)| < A or |φ(𝔽_{q}, ā)| ≥ rq.

Indeed, let D be the set of pairs (d, μ) associated to φ(x, ȳ); define A_{0} = sup{μ | (0, μ) ∈ D}, r_{0} = inf{μ | (1, μ) ∈ D}. Let r = r_{0}/2 and A = sup{A_{0} + C, 4C^{2}/r_{0}^{2}}. Using (∗), this gives the assertion.

(6) Observe that if q is sufficiently large, (0, μ) ∈ D and 𝔽_{q} ⊧ φ_{0,μ}(ā), then, because q^{−1/2} becomes very small, and in particular < 1/2, the number μ must give the exact size of the set φ(𝔽_{q}, ā) defined by φ(x̄, ā).

(6.3) Some simple applications of this result.

(1) There is no formula of the language of rings which defines in each field 𝔽_{q}^{2} the subfield 𝔽_{q}.

(2) We know that the multiplicative group of 𝔽_{q} is cyclic, of order q − 1. There is no formula which defines in all fields 𝔽_{q} the set of generators of the multiplicative group 𝔽_{q}^{×}.

(3) Let G, H be groups definable in the pseudo-finite field F, and assume that f : G → H is definable, ker(f) is finite, and dim(G) = dim(H) = d. Then

μ(G)[H : f(G)] = μ(H)| ker(f)|.

Proof. (1) If φ(x) is a formula, there are A > 0 and r ∈ ℚ^{>0} such that for every finite field 𝔽_{q}, the size of the set defined by φ is either ≤ A or greater than rq. hence, we cannot have a formula which defines in all 𝔽_{q^{2}} a set of size q = \sqrt{q^{2}}.

(2) The function ϕ (called the Euler function) giving the number of generating elements of a cyclic group can be computed. Note that if m, n are relatively prime integers then ϕ(nm) = ϕ(n)ϕ(m) (since ℤ/mnℤ ≃ ℤ/nℤ × ℤ/mℤ). Also, ϕ(p^{n}) = (p − 1)p^{n−1}, since any lifting of a generator of ℤ/pℤ to ℤ/p^{n}/ℤ is a generator of ℤ/p^{n}ℤ.

First observe that if p^{n} > 2, then ϕ(p^{n}) ≥ \sqrt{n}. Hence, for every A ∈ ℕ, the set of integers n such that ϕ(n) < A is finite.

We will now show that for every ε > 0, there is some prime power q such that ϕ(q − 1) < ε(q − 1). Observe that

ϕ(n)/n = ∏_{ℓ a prime divisor of n}(1 − \frac{1}{ℓ}).

Fix some prime p, and let ℓ_{1}, …, ℓ_{m} be distinct prime numbers, M = ∏_{i=1}^{m}(ℓ_{i} − 1). Then for every i, we have p^{M} ≡ 1 mod(ℓ_{i}) and therefore ϕ(p^{M} − 1) ≤ (p^{M} − 1) ∏_{i=1}^{m}(1 − 1/ℓ_{i}). Hence we can find arbitrarily small values of \frac{ϕ(p^{M} −1)}{p^{M} −1}, which shows our assertion.

The existence of a formula defining the set of generators in all 𝔽_{q} would then, as in (1), contradict (6.2)(5).

(3) Let F^{∗} = ∏_{i∈I} 𝔽_{q_{i}}/U be an elementary extension of F, let a be a tuple of elements of F needed to define f, G and H (and their group law, and (a(i))_{i} a sequence such that [a(i)_{i}]_{U} = a.

Let φ_{1}(x̄, ā) be the formula defining G, ψ_{1}(x̄, ȳ, z̄, ā) the one defining its group law, φ_{2}(x̄, ā) the formula defining H, ψ_{2}(x̄, ȳ, z̄, ā) the one defining its group law, and θ(x̄, ȳ, ā) the formula defining the graph of f. The following property is then a first order property of the parameter ā:

ψ_{i}(x̄, ȳ, z̄, ā) is the graph of a group operation on the set defined by φ_{i}(x̄, ā) (i = 1, 2), and θ(x̄, ȳ, ā) is the graph of a group morphism between the set defined by φ_{1}(x̄, ā) and the set defined by φ_{2}(x̄, ā), whose kernel is of size m.

Hence, by Łos’ theorem, for a set J ∈ U, we have, for all j ∈ J, that the following statement holds in 𝔽_{q_{j}}: ψ_{1}(x̄, ȳ, z̄, ā(j)) is the graph of a group operation on the set G_{j} defined by φ_{1}(x̄, ā(j)), ψ_{2}(x̄, ȳ, z̄, ā(j)) is the graph of a group operation on the set H_{j} defined by φ_{2}(x̄, ā(j)), and θ(x̄, ȳ, ā(j)) is the graph of a group morphism f_{j} : G_{j} → H_{j}, whose kernel is of size m.

But G_{j} and H_{j} are finite!! Hence we have |G_{j}|[H_{j} : f_{j}(G_{j})] = |H_{j}|| ker(f_{j})|. For q_{j} sufficiently large, dividing by q_{j}^{d}, we get μ(G_{j})[H_{j} : f_{j}(G_{j})] = μ(H_{j})| ker(f)|.

There is a first-order formula which expresses that fact, is satisfied in all 𝔽_{q_{j}} for j ∈ J, and therefore is satisfied by ā in F^{∗}, whence also in F. This gives the result.

(6.4) Very rough sketch of the proof of Theorem (6.1). The result is proved by induction on the complexity of formulas.

Let us first assume that φ(x̄, ȳ) is positive quantifier-free, that is, it is a disjunction of conjunction of equations (over ℤ).

Let 𝔽_{q} be a finite field, and ā a tuple in 𝔽_{q}. Consider the set S defined by φ(x̄, ā). Then S = W (𝔽_{q}), where W is the algebraic set given by the equations of φ(x̄, ā). However, we do not know that the Theorem of Lang-Weil can tell us the estimate of how many points there are: we will be able to apply this theorem only if all irreducible components of W are defined over 𝔽_{q}. In order to be able to use Lang-Weil, we must therefore find an algebraic set W′ such that W′(𝔽_{q}) = W (𝔽_{q}) and all irreducible components of W′ are defined over 𝔽_{q}. This is done in the following fashion:

Write W = W_{1} ∪⋯∪W_{m} where each W_{i} is irreducible over 𝔽_{q}. If W_{i} is a variety, then we know by Lang-Weil (3.15) that |W (𝔽_{q})| ∼ q^{dim(W_{i})} and we do nothing. If W_{i} is not a variety, then W_{i} has several irreducible components, and any point in W_{i}(𝔽_{q}) will belong to the intersection W′_{i} of all these components, and we replace W_{i} by W′_{i}. We repeat the procedure and find eventually an algebraic set W′, all of whose irreducible components are defined over 𝔽_{q} and such that W′(𝔽_{q}) = W (𝔽_{q}). This procedure is effective, and using the results on bounds in polynomial rings, and we can write W′ = W′_{1} ∪⋯∪W′_{ℓ}, where the W′_{i} are varieties defined over 𝔽_{q}. If d is the maximum of the dimensions of the W′_{i}, and μ is the number of components of W′ of dimension d, the result of Lang-Weil will then give us that |W (𝔽_{q})| ∼ μq^{d}. One also knows that having dimension d is an elementary property of the coefficients of a set of polynomials defining a variety. Thus, there is a formula φā(ȳ) satisfied by ā in 𝔽_{q} and which expresses how we obtained W′ from W, and that W′ has exactly μ components of maximal dimension d. For each pair (𝔽_{q}, ā) we can find such a formula. By compactness, there are a finite number of those, say φ_{1}(ȳ), …, φ_{k}(ȳ) such that in any finite field 𝔽, we have 𝔽 ⊧ ∀ȳ (∃x̄φ(x̄, ȳ)) ↔ (⋁_{j} φ_{j}(ȳ)). To each formula φ_{j}(ȳ) is associated a pair (d, μ), and we put them together to obtain the desired φ_{d,μ}.

The case of a quantifier-free formula φ(x̄, ȳ) follows, observing that modulo the theory of fields, an inequation z ≠ 0 is equivalent to ∃y yz = 1. Thus, every quantifier-free definable set is in bijection, via a projection, with an algebraic set. We then use the first case.

Let us now assume that φ(x̄, ȳ) is arbitrary. Then, Theorem (5.3) tells us, using compactness, that there are positive quantifier-free L_{c}-formulas ψ_{1}(x̄, ȳ, z̄), …, ψ_{m}(x̄, ȳ, z̄) such that

Psf ⊢ ∀x̄, ȳ (φ(x̄, ȳ) ↔ ∃z̄⋁_{j} ψ_{j}(x̄, ȳ, z̄)),

and furthermore such that for some integer N, in any field F one has

F ⊧ ∀x̄, ȳ (∃z̄ ψ_{j}(x̄, ȳ, z̄) → ∃^{≤N} z̄ ψ_{j}(x̄, ȳ, z̄)).

The same equivalence holds in sufficiently large finite fields, say of size ≥ C′ for some C′ (only depending on φ(x̄, ȳ)). Given some sufficiently large finite field 𝔽 and tuple ā in 𝔽, we know by the previous steps how to estimate the size of the sets defined by the formulas ψ_{i}(x̄, ā, z̄). The problem is that the set defined by ⋁_{j} ψ_{j}(x̄, ā, z̄) is not in bijection with the set defined by φ(x̄, ā): given some x̄ in that set, there may be several z̄ such that ψ_{j}(x̄, ā, z̄) holds. One uses a trick to transform the algebraic sets defined by the ψ_{j}, in such a way that we are able to count how many z̄ are sitting above an x̄. Then we use some counting arguments and induction to conclude. The constant C of the Theorem will be sufficiently large so that, in field of size smaller than C′ (and in which we do not necessarily have the equivalence), the inequality still holds. E.g., one can choose C ≥ C′^{n}, where n = |x|.^{11}

(6.5) Definition of the measure on pseudo-finite fields. Let φ(x̄, ȳ) be a formula (x̄ an n-tuple of variables), and D, φ_{d,μ}(ȳ) the set and formulas given by Theorem (6.1). It follows from Remark (6.2)(6) that if F is a pseudo-finite field and ā a tuple in F, then there will be a unique pair (d, μ) ∈ D such that F ⊧ φ_{d,μ}(ā). We then define dim(φ(x̄, ā)) = d and μ(φ(x̄, ā)) = μ. If S is the set defined by φ(x̄, ā), then we also write dim(S) and μ(S) respectively. Proposition. Let F be a pseudo-finite field, S, T two definable sets.

(1) If V is a variety defined over F, then dim(V (F)) = dim(V) and μ(V (F)) = 1.

(2) Assume that T ∩ S = ∅. Then

μ(S ∪ T) = \{ \begin{matrix}μ(S) + μ(T) & if dim(S) = dim(T), \\ μ(S) & if dim(S) > dim(T), \\ μ(T) & if dim(S) < dim(T). \end{matrix}

11 The argument I gave in class was not completely correct I think; it needs to be refined. An alternate proof can be given using Galois stratification, see [FHJ1].

(3) Assume that f : S → T is a definable function, which is onto. If for all ȳ ∈ T, dim(f^{−1}(ȳ)) = d, then dim(S) = dim(T)+d. If moreover for every ȳ ∈ T, μ(f^{−1}(ȳ)) = m, then μ(S) = mμ(T).

(4) Let us define a function m_{S} on definable subsets of S as follows. Assume that T ⊆ S is definable, and let (d, μ) = (dim(S), μ(S)), (e, ν) = (dim(T), μ(T)). Then

m_{S}(T) = \{ \begin{matrix}0 & if e < d, \\ ν/μ & if d = e. \end{matrix}

Then m_{S} is a finitely additive measure on the set of definable subsets of S.

(5) Let S̄ be the Zariski closure of S (in F^{alg}. I.e., the smallest Zariski closed set containing S. It is defined over F). Then dim(S) = dim(S̄). [That is, we are saying that the algebraic dimension of the algebraic set S̄ coincides with the model-theoretic dimension of the set S]

Proof. (1) is clear.

Recall that F embeds elementarily in some ultraproduct ∏_{q∈Q} 𝔽_{q}/U of finite fields. Assume that S is defined by φ(x̄, ā), write ā = [ā_{q}]_{U}, and S_{q} for the subset of 𝔽_{q}^{n} defined by φ(x̄, ā_{q}). Note that for some set A ∈ U, we will then have 𝔽_{q} ⊧ φ_{d,μ}(ā_{q}) for all q ∈ A, and therefore |S_{q}| ∼ μq^{d}. A moment’s thought shows that this gives items (2) - (4).

(5) By (5.3), there is an algebraic set W (F) ⊂ F^{n+ℓ} such that S = π(W (F)) and the restriction of the projection π to W is finite-to-one. Without loss of generality, W (F) is Zariski dense in W, and by (3) we obtain that dim(W) = dim(S). Working now in F^{alg}, we have that π is also finite-to-one on a Zariski-dense open subset of W, and therefore dim(W) = dim(V) (algebraic dimensions). Since V ⊇ S̄, we get that dim(V) = dim(S̄).

(6.6) Existence of certain bounds. Let φ(x̄, ȳ) be a formula.

(1) (Not the Strict Order Property)There is a number M such that in any finite or pseudofinite field F, the length of a chain of definable subsets of F^{n} defined by formulas φ(x̄, ā) for some tuples ā in F, is bounded by M.

(2) (Finite Shelah rank) There is a number M such that in any finite field or pseudo-finite field F, if S is a definable set and (ā_{i})_{i∈I} is a set of tuples such that each φ(x̄, ā_{i}) defines a subset of S of the same dimension d as S, and for i ≠ j, dim(φ(x̄, ā_{i})∧φ(x̄, ā_{j})) < d, then |I| ≤ M.

Proof. These two facts follow from general properties of measures. It suffices to show them for all pseudo-finite fields, since then they will be true in all sufficiently large finite fields, whence, taking into account the finitely many small finite fields, we will get the bound M.

(1) Assume that this is not the case, i.e., that there are such chains of arbitrarily large length. Then, going to a sufficiently saturated pseudo-finite field F, we can find a sequence (ā_{i})_{i∈ℕ} of tuples in F such that if i < j then the set S_{j} defined by φ(x̄, ā_{j}) is strictly contained in the set S_{i} defined by φ(x̄, ā_{i}). Let D be the finite set of pairs associated to φ. Because D is finite, we may, going to a subsequence, assume that for every i ∈ ℕ, dim(S_{i}) = d and μ(S_{i}) = μ. The proof is by induction on d.

If d = 0, then we know that μ is the size of the set S_{i}, and therefore |I| = 1. Assume d > 0 and that the result holds for all definable sets of smaller dimension. For i > 0 let T_{i} = S_{0} \ S_{i}. Then the sets T_{i}, i ∈ ℕ, form a strictly increasing chain of subsets of S_{0}, and we have dim(T_{i}) < d (since (dim(S_{i}), μ(S_{i})) = (dim(S_{0}), μ(S_{0}))). This contradicts the induction hypothesis and proves the result.

(2) Let D be the set of pairs associated to the formula φ(x̄, ȳ), and let ν be the inf of all μ such that (d, μ) ∈ D. If φ(x̄, ā_{i}), i ∈ I, define subsets S_{i} of S such that dim(S_{i}) = d and dim(S_{i} ∩ S_{j}) < d, then we get m_{S}(S_{i}) ≥ ν/μ(S) and m_{S}(S_{i} ∩ S_{j}) = 0. This gives |I| ≤ μ(S)/ν.

(6.7) The independence property. Recall that a formula φ(x̄, ȳ) has the independence property (in the model M) iff for every n, there are tuples ā_{i}, 1 ≤ i ≤ n, and b̄_{s}, s ∈ P({1, …, n}), in M such that

M ⊧ φ(ā_{i}, b̄_{s}) ⟺ i ∈ s

for every i and s. A complete theory has the independence property if there is a formula which has the independence property. Theorem (Duret [D]) The theory of any pseudo-algebraically closed field which is not separably closed, has the independence property.

We will give here a simple case of his proof, for a pseudo-finite field of characteristic ≠ 2. (In characteristic 2, the example can be modified). Let F be a pseudo-finite field and consider the formula φ(x, y) which says that x + y is a square and x ≠ y. Let a_{1}, …, a_{n} be distinct elements of F, s a subset of {1, …, n}, we want to find an element b such that b + a_{i} is a square if and only if i ∈ s. Renumbering the a_{i}’s, we may assume that i ∈ s ⟺ i ≤ r.

Because F is pseudo-finite, it contains an element c which is not a square. Then, as F has a unique extension of degree 2, we have F^{×} = F^{×}^{2} ∪ cF^{×}^{2}, and therefore

F ⊧ ∀x [(∀y y^{2} ≠ x) ↔ (∃y y^{2} = cx)].

Let t be transcendental over F, and consider the extension

L = F (t, \sqrt{t + a_{1}}, …, \sqrt{t + a_{r}}, \sqrt{c(t + a_{r+1})}, …, \sqrt{c(t + a_{n})}).

Then L ∩ F^{alg} = F (This needs a proof which I will not give). Hence, by Lemma (3.9), in F there is an element d such that d + a_{1}, …, d + a_{r}, c(d + a_{r+1}), …, c(d + a_{n}) are squares. I.e., d + a_{i} is a square if and only if i ≤ r.

(6.8) Graphs interpretable in pseudo-finite fields. The above proof shows that the random graph is interpretable in any pseudo-finite field (of characteristic ≠ 2), by the formula expressing that x + y is a square and x ≠ y.

Observe that if −1 is a square in F, then the formula ψ(x, y) saying that x − y is a square and is non-zero would work as well. If −1 is not a square in F, then the formula ψ(x, y) defines the random tournament. (a tournament is a binary relation not intersecting the diagonal and such that given two distinct elements, one exactly of (a, b), (b, a) is in the relation. The random tournament is a tournament in which given any two disjoint finite sets A and B there is an element c such that ⋀_{a∈A} R(c, a) ∧ ⋀_{b∈B} R(b, c).

Hrushovski proves in [H1] that one cannot interpret the random triangle-free graph in any countable pseudo-finite field. Beyarslan proves in [B] that one can interpret in any pseudo-finite field the random n-hypergraph. Recall that if n ≥ 2, an n-hypergraph is a sn n-ary relation R satisfying:

– R(x_{1}, …, x_{n}) → ⋀_{i≠j} x_{i} ≠ x_{j},

– R(x_{1}, …, x_{n}) → ⋀_{σ∈Sym({1,...,n})} R(x_{σ(1)}, …, x_{σ(n)}).

The random n-hypergraph is the existentially closed countable n-hypergraph. I.e., it is countable, and satisfies, for all m, ℓ,

if a_{1}, …, a_{m}, b_{1}, …, b_{ℓ} are distinct (n − 1)-element subsets, then there is an element x such that ⋀_{i} R(x, a_{i}) ∧ ⋀_{j} ¬ R(x, b_{j}).

(6.9) Another interesting result, in the vein of (6.3). Say that I ⊂ 𝔽_{p} is an interval (p a prime) if there is some interval J in ℤ such that I is the image of J under the natural reduction modulo p : ℤ → ℤ/pℤ = 𝔽_{p}.

Proposition (Kowalski [K]). If φ(x) is a formula of the language of rings which defines in all prime field 𝔽_{p} an interval, then there is a number N such that for every prime p, one of |φ(𝔽_{p})|, |¬φ(𝔽_{p})| has size ≤ N.

Note that an argument using measures is not sufficient, since the interval [0, \frac{p−1}{2}] has size approximately \frac{p}{2}.

(6.10) N-dimensional asymptotic classes. Let N be a positive integer. A class C of finite structures is an N-dimensional asymptotic class if to each formula φ(x̄, ȳ), x̄ an n-tuple, ȳ an m-tuple, one can associate a finite set D of pairs (d, μ) ∈ {0, …, Nn} × ℝ^{>0} ∪ {(0, 0)}, as well as formulas φ_{d,μ} for (d, μ) ∈ D, and a constant C > 0 such that (1) For any M ∈ C and m-tuple ā ∈ M, one has, for some (d, μ) ∈ D,

||φ(M, ā)| − μ|M|^{d/N} | = o(|M|^{d/N}).  (∗)

[Here φ(M, ā) denotes the set {b̄ ∈ M^{n} | M ⊧ φ(b̄, ā)}.]

(2) The formula φ_{d,μ}(ȳ) defines in each M ∈ C the set of tuples ā such that (∗) holds. Here the notation o(|M|^{d/N}) means: for every ε ∈ ℝ^{>0}, there is Q ∈ ℕ such that if M ∈ C has size > Q and if ā satisfies φ_{d,μ} in M, then ||φ(M, ā)| − μ|M|^{d/N} | < ε|M|^{d/N}.

The universe M is then thought to be N-dimensional. Because of the definability condition, it turns out that one only need to verify the properties for formulas with x a singleton. For more details one can consult the survey paper by Elwes and Macpherson [EM].

(6.11) Measurable structures. A structure M is measurable if there is a function h = (Dim, μ) (dimension and measure) from the set Def(M) of definable subsets of cartesian powers of M, taking values in ℕ × ℝ^{>0} ∪ {(0, 0)}, and satisfying the following conditions:

(1) For every formula φ(x̄, ȳ) there is a finite set D = D_{φ} such that for any ā in M h(φ(M, ā)) ∈ D.

(2) If S is finite (or empty), then h(S) = (0, |S|),

(3) For every formula φ, and (d, μ) ∈ D_{φ}, the set {ā | h(φ(M, ā)) = (d, μ)} is definable in M (without parameters).

(4) (Additivity) Let S, T be disjoint definable subsets of M^{n}. Then Dim(S ∪ T) = sup{Dim(S), Dim(T)}, and

μ(S ∪ T) = \{ \begin{matrix}μ(S) + μ(T) & if Dim(S) = Dim(T), \\ μ(S) & if Dim(S) > Dim(T), \\ μ(T) & if Dim(S) < Dim(T). \end{matrix}

(5) (Fubini) Assume that f : S → T is a definable function, which is onto. If for all ȳ ∈ T, Dim(f^{−1}(ȳ)) = d, then Dim(S) = Dim(T) + d. If moreover for every ȳ ∈ T, μ(f^{−1}(ȳ)) = m, then μ(S) = mμ(T).

(6.12) Comments. The motivating example are pseudo-finite fields. Because of the definability condition and the Fubini condition, one can restrict one’s attention to definable subsets of M. Also, as with pseudo-finite fields, it follows that the theory of a measurable structure is supersimple.

If C is an N-dimensional asymptotic class of finite structures, then any structure in the elementary class generated by C will be measurable, and we also see that the definitions and measures will be uniform through the structures in this elementary class.

The converse is however not true: there exists measurable structures which are not elementarily equivalent to ultraproducts of finite structures. Below we will give such an example.

(6.13) Definitions.

(1) Recall that a first order theory T is strongly minimal if in any model M of T, any definable (with parameters) subset of M is finite or cofinite.

(2) In a strongly minimal theory one can define a rank, called the Morley rank as well as a multiplicity, the Morley degree, of definable sets. I will not give precise definitions, let me say that the rank satisfies the obvious axioms of a dimension (see properties (4) and (5) of Dim in (6.11)), and that the Morley degree of a definable set S is the maximal number n such that S can be definably partitioned into sets of the same rank as S. Furthermore, the Morley rank of the universe is 1, and of a finite set is 0. A strongly minimal theory T has the DMP (definable multiplicity property) if for any model M, formula φ(x̄, ȳ) and integer n > 0, the set of tuples ā in M such that φ(M, ā) has Morley degree n, is definable.

Important examples of strongly minimal theories with the DMP are the completions of the theory ACF of algebraically closed fields. Moreover, if T_{1} and T_{2} are strongly minimal with the DMP, then so is the Hrushovski fusion T_{3} constructed from T_{1} and T_{2}.

(6.14) Theorem (Ryten-Tomasic [RT]) Let T be a strongly minimal theory with the DMP and which eliminates imaginaries. Consider the theory T_{σ} of models of T with an automorphism σ (so, structures in the language L to which one has added a unary function symbol σ), let N be an existentially closed model of T_{σ}, and let F be the L-structure {a ∈ N | σ(a) = a}. Then F is measurable of dimension 1.

(6.15) Example of a measurable structure not arising from an asymptotic class of finite structures. So, let T_{1} be the theory of algebraically closed fields of characteristic 2 (in a language L_{1}), and T_{2} the theory of algebraically closed fields of characteristic 3 (in the language L_{2}). Let T_{3} be the Hrushovski fusion of T_{1} and T_{2}, and let F be as above. Then the reduct of F to L_{1} is a pseudo-finite field of characteristic 2, the reduct of F to L_{2} is a pseudo-finite field of characteristic 3, and F cannot be elementarily equivalent to an ultraproduct of finite L_{1} ∪ L_{2}-structures: a power of 2 can never equal a power of 3 unless they both equal 1. But, by the result of Ryten-Tomasic, the L_{1} ∪ L_{2}-structure F is measurable of dimension 1.

(6.16) Examples of finite dimensional asymptotic classes. By Theorem (6.1), the collection of all finite fields forms a 1-dimensional asymptotic class, as does any subclass. Also, for a fixed n > 1, the class of all GL_{n}(𝔽_{q}) is an (n^{2} −1)-dimensional asymptotic class. The definability assumption comes from the fact that there is a uniform interpretation of the field 𝔽_{q} in these groups ([P]). Here is another example.

Fix a prime p, and relatively prime integers m, n with m ≥ 1 and n > 1. Let C_{(m,n,p)} be the class of all fields 𝔽_{p^{kn+m}} with a distinguished automorphism Frob^{k}, for k ∈ ℕ^{>0}. One can show that there is no formula of the field language which defines in each field 𝔽_{p^{kn+m}} the graph of Frob^{k}. These structures appear in a significant way in the study of certain finite simple groups: for instance C_{(1,2,2)} is uniform parameter biinterpretable with the classes of Suzuki groups ^{2}B_{2}(2^{2k+1}) and the Ree groups ^{2}F_{4}(2^{2k+1}), and C_{(1,2,3)} with the class of Reee groups ^{2}G_{2}(3^{2k+1}).

Bibliography

[A] J. Ax, The elementary theory of finite fields, Annals of Math. 88 (1968), 239 – 271.

[B] O. Beyarslan, Interpreting Random Hypergraphs in Pseudofinite Fields, to appear in J. of Inst. Math. Jussieu.

[CK] C.C. Chang, H.J. Keisler, Model theory, North-Holland, Amsterdam 1977.

[CDM] Z. Chatzidakis, L. van den Dries, A. Macintyre, Definable sets over finite fields,

J. reine u. ang. Math. 427 (1992), 107 – 135.

[DL] J. Denef, F. Loeser, Definable sets, motives and p-adic integrals, J. Amer. Math. Soc. 14 (2001), no. 2, 429–469.

[DS] L. van den Dries, K. Schmidt, Bounds in the theory of polynomials rings over fields. A non-standard approach. Invent. Math. 76 (1984), 77 – 91.

[Du] J. -L. Duret, Les corps faiblement algébriquement clos non séparablement clos ont la propriété d’indépendance, in: Model theory of Algebra and Arithmetic, Pacholski et al. ed., Springer Lecture Notes 834 (1980), 135 –157.

[EM] R. Elwes, H.D. Macpherson, A survey of asymptotic classes and measurable structures, in Model theory and applications to algebra and analysis (Eds. Z. Chatzidakis, H.D. Macpherson, A. Pillay, A.J. Wilkie), Cambridge University Press, 2008, 125 – 159.

[FHJ1] M. Fried, D. Haran, M. Jarden, Galois stratification over Frobenius fields, Adv. in Math. 51 (1984), 1 – 35.

[FHJ2] M. Fried, D. Haran, M. Jarden, Effective counting of the points of definable sets over finite fields, Israel J. Math. 85 (1994), 103 – 133.

[FJ] M. Fried, M. Jarden, Field Arithmetic, Ergebnisse 11, Springer Berlin-Heidelberg 1986.

[FS] M. Fried, G. Sacerdote, Solving diophantine problems over all residue class fields of a number field and all finite fields, Annals of Math. 104 (1976), 203 – 233.

[H] I. Halupczok, A measure for perfect PAC fields with pro-cyclic Galois group. Journal of Algebra 310 (2007), 371-395.

[He] G. Hermann, Die Frage der endlich vielen Schritte in der Theorie der Polynomideale, Math. Ann. 95 (1926), no. 1, 736 – 788.

[H1] E. Hrushovski, Pseudo-finite fields and related structures, in: Model Theory and Applications, Bélair et al. ed., Quaderni di Matematica Vol. 11, Aracne, Rome 2005, 151 – 212.

[H2] E. Hrushovski, The first-order theory of the Frobenius, preprint, available at

ArXiv: http://front.math.ucdavis.edu/math.LO/0406514.

[HP1] E. Hrushovski, A. Pillay, Groups definable in local fields and pseudo-finite fields, Israel J. of Math. 85 (1994), 203 – 262.

[HP2] E. Hrushovski, A. Pillay, Definable subgroups of algebraic groups over finite fields,

J. reine angew. Math. 462 (1995), 69 – 91.

[K] E. Kowalski, Exponential sums over definable subsets of finite fields, Israel J. Math. 160 (2007), 219–251.

[L1] S. Lang, Introduction to algebraic geometry, Addison-Wesley Pub. Co., Menlo Park 1973.

[L2] S. Lang, Algebra, Addison-Wesley Pub. Co., Menlo Park 1984.

[LW] S. Lang, A. Weil, Number of points of varieties in finite fields, Am. J. of Math. 76 (1954), 819 –827.

[M] A. Macintyre, Nonstandard Frobenius, in preparation.

[MS] H.D. Macpherson, C. Steinhorn, One-dimensional asymptotic classes of finite structures, Trans. Amer. Math. Soc. 360(2008), 411–448.

[P] F. Point, Ultraproducts and Chevalley groups, Arch. Math. Logic 38 (1999), 355–372.

[R] M. Ryten, Results around asymptotic and measurable groups, PhD thesis, University of Leeds, 2008.

[RT] M. Ryten, I. Tomašić, ACFA and measurability, Selecta Mathematica New series,

11 (2005), 523-537.

[S] A. Seidenberg, Constructions in algebra, Trans. Amer. Math. Soc. 197 (1974), 273 – 313.