ONE-DIMENSIONAL ASYMPTOTIC CLASSES OF FINITE STRUCTURES

DUGALD MACPHERSON AND CHARLES STEINHORN

Abstract. A collection C of finite L-structures is a 1-dimensional asymptotic class if for every m ∈ ℕ and every formula φ(x, ȳ), where ȳ = (y_{1}, …, y_{m}), (i) There is a positive constant C and a finite set E ⊂ ℝ^{>0} such that for every M ∈ C and ā ∈ M^{m}, either |φ(M, ā)| ≤ C, or for some μ ∈ E,

||φ(M, ā)| − μ|M|| ≤ C|M|^{\frac{1}{2}} .

(ii) For every μ ∈ E, there is an L-formula φ_{μ}(ȳ), such that φ_{μ}(M^{m}) is

precisely the set of ā ∈ M^{m} with

||φ(M, ā)| − μ|M|| ≤ C|M|^{\frac{1}{2}} .

One-dimensional asymptotic classes are introduced and studied here. These classes come equipped with a notion of dimension that is intended to provide for the study of classes of finite structures a concept that is central in the development of model theory for infinite structures. Connections with the model theory of infinite structures are also drawn.

1. Introduction

Dimension theory, so-called, has become a pervasive theme in contemporary model theory. Roughly speaking, this term covers several different contexts in which a notion of dimension is assigned to definable sets. This program has been carried out with great success in the development of model theory for infinite structures; see some of the articles in the collection [18], for example. This paper attempts to take a first step to develop a dimension theory for classes of finite structures.

As has often been the case in model theory for infinite structures, this work is directly inspired by model-theoretic investigations of algebraic structures. More specifically, our approach has its origins in the following beautiful theorem of Chatzidakis, van den Dries, and Macintyre:

Theorem 1.1 ([6]). Let φ(x_{1}, …, x_{n}; y_{1}, …, y_{m}) be a formula in the language of rings. Then there is a positive constant C and finitely many pairs (d_{i}, μ_{i}), i ≤ K with d_{i} ∈ {0, 1, …, n} and μ_{i} a positive rational number such that for each finite field 𝔽_{q}, where q is a prime power, and each ā ∈ 𝔽_{q}^{m}, if the set

φ(𝔽_{q}^{n}, ā) := {b̄ ∈ 𝔽_{q}^{n} : 𝔽_{q} ⊧ φ(b̄, ā)}

is nonempty, then

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

Date: January 5, 2007.

Partially supported by NSF grants DMS-9704869 and DMS-0070743, EPSRC grant GR/R37388/01, and the London Mathematical Society.

for some i ≤ K. Moreover, for each pair (d_{i}, μ_{i}), there is a formula ψ_{i}(y_{1}, …, y_{m}) in the language of rings such that ψ_{i}(𝔽_{q}^{m}) consists of those ā ∈ 𝔽_{q}^{m} for which the corresponding inequality holds.

Each pair (d, μ) in the definition thus represents in finite combinatorial form the dimension d and measure μ of those definable sets in finite fields to which the pair corresponds.

In some of the most basic classical model-theoretic contexts in which a notion of dimension plays a central role, the strongly minimal and o-minimal theories for example, the definition places a condition only on definable sets in one variable. Then it is proved that the definition has dimension-theoretic consequences for definable sets in several variables. Following this pattern, we now define the classes of finite structures that we study in this paper.

Definition 1.2. Let L be a first order language, and C be a collection of finite L-structures. Then C is a 1-dimensional asymptotic class if the following hold for every m ∈ ℕ and every formula φ(x, ȳ), where ȳ = (y_{1}, …, y_{m}).

(i) There is a positive constant C and a finite set E ⊂ ℝ^{>0} such that for every M ∈ C and ā ∈ M^{m}, either |φ(M, ā)| ≤ C if φ(M, ā) is non-empty or for some μ ∈ E,

||φ(M, ā)| − μ|M|| ≤ C|M|^{\frac{1}{2}} .

(ii) For every μ ∈ E, there is an L-formula φ_{μ}(ȳ), such that, for all M ∈ C, φ_{μ}(M^{m}) is precisely the set of ā ∈ M^{m} with

||φ(M, ā)| − μ|M|| ≤ C|M|^{\frac{1}{2}} .

There are several variations on this definition. For example, R. Elwes, a Ph.D. student of the first author, has developed the notion of an N-dimensional asymptotic class, for N ≥ 1. It is also possible to relax (or strengthen) the error term, for example requiring that

||φ(M, ā)| − μ|M|| = o(|M|).

We choose the above error term by analogy with [6], which provides our main examples.

We also note that the analogue of condition (ii) does not appear in the definition of a strongly minimal or o-minimal structure. In these settings, an analogous condition follows from the definition. The uniformity that such a condition provides is ensured in these contexts because in each case the definition involves a first-order theory. This is not the case for the classes of structures covered by our definition. The additional clause in the definition thus is necessary; see Example 2.3.

We now offer a brief outline of the paper. Section 2 establishes some basic facts about 1-dimensional asymptotic classes. The most important of these, Theorem 2.1, shows that the definition of a 1-dimensional asymptotic class does indeed have consequences for definable sets in more than one variable. This result might be viewed as a finite combinatorial cell decomposition theorem. Section 3 develops a range of examples. Besides the motivating example of finite fields, this section includes several 1-dimensional asymptotic classes of graphs, classical geometries, and groups, including the class of all finite cyclic groups. The next section, Section 4 elaborates the connections between 1-dimensional asymptotic classes C and the infinite structures that arise as the ultraproducts of members of C. Here we draw explicit links with stable and simple structures of classical infinite model theory. Section 5 builds on the observation in [6] that the dimension and measure on definable subsets of finite fields naturally induces a dimension and measure on the definable subsets of a pseudofinite field. In this section, measurable structures, infinite structures whose definable sets come equipped with a dimension and measure satisfying natural axioms satisfied by pseudofinite fields, are introduced and studied. The paper concludes with an appendix containing a theorem of Scanlon unpublished elsewhere. The argument in this proof is used in the proof of Theorem 5.18 (i).

Since the first draft of this paper was written, there have been substantial further developments. Most of these will be surveyed in [14]. For example, Elwes has developed a notion of N-dimensional asymptotic class, and among other results has shown that any smoothly approximable structure has a sequence of ‘envelopes’ which forms an asymptotic class. Ryten has exhibited 1-dimensional asymptotic classes consisting of finite fields with extra structure (namely a power of the Frobenius of suitable order) and has thereby shown that for any d, any family of finite simple groups of Lie rank d is an asymptotic class. The notion of measurable theory has also been further developed.

The notation throughout is standard; any unexplained terminology or notation is defined where it arises.

Acknowledgements. We are extremely grateful to Thomas Scanlon for allowing us to include Theorem 6.1 and its proof. This ensures that our slight adaptation of his proof, in Theorem 5.18, does not refer in an essential way to unpublished work. We also thank Zoé Chatzidakis for a helpful conversation.

2. Some Basic Properties of One-dimensional Asymptotic Classes

We first prove that Definition 1.2 is analogous to strong minimality and ominimality in the following sense: though it is a condition on definable sets in one variable, so often is easily verifiable, it gives information on definable sets in several variables.

Theorem 2.1. Suppose C is a 1-dimensional asymptotic class of finite L-structures. Then the following holds, for every m, n ∈ ℕ and every formula φ(x̄, ȳ), where x̄ = (x_{1}, …, x_{n}) and ȳ = (y_{1}, …, y_{m}).

i. There is a positive constant C and a finite set D of pairs (d, μ) with d ∈ {0, …, n} and μ ∈ ℝ^{>0}, such that for every M ∈ C and ā ∈ M^{m}, if φ(M^{n}, ā) is non-empty then for some (d, μ) ∈ D we have:

||φ(M^{n}, ā)| − μ|M|^{d}| ≤ C|M|^{d− \frac{1}{2}} .

ii. For every (d, μ) ∈ D, there is an L-formula φ_{d,μ}(ȳ), such that, for all M ∈ C, φ_{d,μ}(M^{m}) is precisely the set of ā ∈ M^{m} with

||φ(M^{n}, ā)| − μ|M|^{d}| ≤ C|M|^{d− \frac{1}{2}} .

Proof. We use induction on n. Assume thus that the result holds for formulas φ(x̄, ȳ) with ℓ(x̄) < n. Now consider a formula φ(z, x̄, ȳ), where ℓ(x̄) = n and ℓ(ȳ) = m. By the n = 1 case, there is a positive integer c, a constant C, μ_{1}, …, μ_{t} ∈ ℝ^{>0}, and formulas χ_{i}(x̄, ȳ), for i = 0, …, c + t, such that for M ∈ C and (b̄, ā) ∈ M^{n+m}, either |φ(M, b̄, ā)| = i for some i ≤ c—and χ_{i}(b̄, ā) holds—or for some i = 1, …, t we have

||φ(M, b̄, ā)| − μ_{i}|M|| ≤ C|M|^{\frac{1}{2}}

(and χ_{c+i}(b̄, ā) holds).

By induction, for each i = 0, …, c + t there are positive integers c_{i}, r_{i}, positive constants C_{i} ∈ ℝ, and sets of pairs (d_{i1}, ν_{i1}), …, (d_{ir_{i}}, ν_{ir_{i}}), with each ν_{ij} ∈ ℝ^{>0} and each d_{ij} ∈ ℕ^{>0}, and formulas ρ_{i0}(ȳ), …, ρ_{i,c_{i}+r_{i}}(ȳ), so that the following hold. If M ∈ C and ā ∈ M^{m}, either |χ_{i}(M^{n}, ā)| = j for some j ≤ c_{i}, and ρ_{ij}(ā) holds, or for some j = 1, …, r_{i},

||χ_{i}(M^{n}, ā)| − ν_{ij}|M|^{d_{ij}} | ≤ C_{i}|M|^{d_{ij}− \frac{1}{2}}

and ρ_{ic_{i}+j}(ā) holds.

We shall consider only structures M ∈ C which are sufficiently large so that for all (b̄, ā) ∈ M^{n+m} there is exactly one i ∈ {0, …, c + t} for which χ_{i}(b̄, ā) holds , and so that for each such i and each ā ∈ M^{m}, ρ_{ij}(ā) holds for exactly one j ∈ {0, …, c_{i} + r_{i}}. Let X be the set of all functions f : {0, …, c + t} → ℕ, such that f(i) ∈ {0, …, c_{i} + r_{i}} for each i ∈ dom(f). Then for all large enough M ∈ C and for each ā ∈ M^{m}, there is a unique fā ∈ X such that ρ_{i,fā(i)}(ā) holds for each i = 0, …, c + t. We set Ptp(ā) := fā in this case. Observe that tp(ā) (in M) determines Ptp(ā).

For each ā ∈ M^{m}, put

S_{i}(ā) := {(z, x̄) ∈ M^{n+1} : φ(z, x̄, ā) ∧ χ_{i}(x̄, ā)}.

Note that φ(M^{n+1}, ā) is the disjoint union of S_{0}, …, S_{c+t}. Suppose now that ā ∈ M^{m} and f = Ptp(ā). Then the following hold:

a. If i ≤ c and f(i) ≤ c_{i}, then |S_{i}(ā)| = if(i).

b. If i ≤ c and f(i) = c_{i} + j > c_{i}, then

|S_{i}(ā)| − iν_{ij}|M|^{d_{ij}} | ≤ iC_{i}|M|^{d_{ij}− \frac{1}{2}} .

c. If i = c + i′ > c and f(i) = j ≤ c_{i}, then

||S_{i}(ā)| − jμ_{i′}|M|| ≤ jC|M|^{\frac{1}{2}} .

d. If i = c + i′ > c and f(i) = c_{i} + j > c_{i}, then

(ν_{ij}|M|^{d_{ij}} − C_{i}|M|^{d_{ij}− \frac{1}{2}} )(μ_{i′}|M| − C|M|^{\frac{1}{2}} ) ≤ |S_{i}(ā)|
≤ (ν_{ij}|M|^{d_{ij}} + C_{i}|M|^{d_{ij}− \frac{1}{2}} )(μ_{i′}|M| + C|M|^{\frac{1}{2}} ).

Hence, in case (d),

||S_{i}(ā)| − μ_{i′}ν_{ij}|M|^{d_{ij}+1}| ≤ ν_{ij}|M|^{d_{ij}}C|M|^{\frac{1}{2}} + C_{i}|M|^{d_{ij}− \frac{1}{2}} μ_{i′}|M| + CC_{i}|M|^{d_{ij}},

which is less than C′|M|^{(d_{ij}+1)− \frac{1}{2}} if C′ is chosen large enough.

Notice that the possibilities depend only on the pair (i, f(i)). For each function f ∈ X and i = 0, …, c + t, define g: {0, …, c + t} → ℕ × ℝ by

g(i) := (g_{1}(i), g_{2}(i)) = \{ \begin{matrix}(0, if(i)) & if (a) holds \\ (d_{ij}, iν_{ij}) & if (b) holds \\ (1, jμ_{i′}) & if (c) holds \\ (d_{ij} + 1, μ_{i′}ν_{ij}) & if (d) holds. \end{matrix}

For each f ∈ X, let d := max{g_{1}(i) : 0 ≤ i ≤ c + t} and A := {i : 0 ≤ i ≤ t ∧ g_{1}(i) = d}. Then put μ := Σ_{i∈A}g_{2}(i). It is now easily checked for all ā ∈ M^{m} such that Ptp(ā) = f that ||φ(M^{n+1}, ā)| − μ|M|^{d}| ≤ C′′|M|^{d− \frac{1}{2}} for some constant C′′. Assertion (i) of the lemma follows.

It remains to check that clause (ii) holds for φ. Since the formulas ρ_{ij}(ā) determine Ptp(ā), and the latter determines the function g for the parameters ā, assertion (ii) is immediate. □

Remark 2.2. The above proof shows that if the elements μ of the set D in Definition 1.2 are rational, then the corresponding μ in Proposition 2.1 also are rational (as for finite fields).

We give an example to show that if C is a 1-dimensional asymptotic class of L-structures and L^{−} ⊂ L, then the set of reducts C^{−} := {M ↾_{L^{−}}: M ∈ C} may not be a 1-dimensional asymptotic class. Clause (i) of Definition 1.2 is preserved under reducts; the problem is with the definability clause (ii). Thus the definability condition (ii) in Definition 1.2 does not follow from (i), unlike the analogous situation in the case of strong minimality and o-minimality.

Example 2.3. Let L be a language with a binary predicate E and two unary predicates P and Q, and let L^{−} just have E. Let C be the collection of all Lstructures consisting of a set of size 3n, where n ∈ ℕ^{>0}, with E interpreted by an equivalence relation with two classes, one class of size 2n, the other of size n. The realizations of P are the elements of the class of size 2n, and Q is interpreted by the class of size n. There is a uniform quantifier elimination for the class C, and it follows that C is a 1-dimensional asymptotic class. However, if C^{−} is the collection of reducts of members of C to L^{−}, then C^{−} is not a 1-dimensional asymptotic class. The reason is that it is not possible, uniformly in members M of C^{−}, to define {x : |E(x, M)| = |M|/3}.

This example suggests we should not assume that C is the collection of finite models of some theory. To illustrate, suppose that L is a language with a single binary relation E, and C consists of all finite L-structures of even size in which E is interpreted by an equivalence relation with just two classes, both of the same size. If Σ is any set of L-sentences true of all members of C, then the set of all finite models of Σ is not a 1-dimensional asymptotic class. However, C is a 1-dimensional asymptotic class.

The next lemma is immediate.

Lemma 2.4. Let C be a 1-dimensional asymptotic class whose language is L, let D be a set of constant symbols not in L, and let L^{+} := L∪D. Then C^{+}, the collection of all expansions of C to L^{+}, is a 1-dimensional asymptotic class.

The following two facts are helpful in developing examples, and will be applied in Section 3.

Lemma 2.5. Let C be a class of finite L-structures, and suppose that every infinite ultraproduct of members of C is strongly minimal. Then C is a 1-dimensional asymptotic class.

Proof. Let φ(x, ȳ) be a formula, and let M ∈ C. By strong minimality, there is a positive integer N_{φ} such that for all ā ∈ M^{m}, either |φ(M, ā)| ≤ N_{φ}, or |¬φ(M, ā)| ≤ N_{φ}. Clause (i) in Definition 1.2 follows, with μ = 1. Clause (ii) is a straightforward consequence of strong minimality as well. □

We often use the final lemma in this section without explicit reference to verify that a class of finite structures is an asymptotic class.

Lemma 2.6. Let C be a collection of finite structures, and suppose that there is a unique complete theory T such that all infinite ultraproducts of members of C satisfy T. Let M ⊧ T be countably infinite. Suppose that for every formula ψ(x, ȳ) there are formulas φ_{1}(x, ȳ), …, φ_{t}(x, ȳ), each isolating a complete type relative to T, for which (i) and (ii) of Definition 1.2 hold for C and such that T ⊧ ψ(x, ȳ) ↔ ⋁_{i=1}^{t} φ_{i}(x, ȳ). Then C is a 1-dimensional asymptotic class.

Proof. Let ψ(x, ȳ) be an arbitrary formula in m+1 variables, and φ_{1}(x, ȳ), …, φ_{t}(x, ȳ) be as in the hypothesis of the lemma. Then, for sufficiently large P ∈ C, and all ā ∈ P^{m}, |ψ(M, ā)| = Σ_{i=1}^{t}|φ_{i}(M, ā)|. The conclusion follows. □

3. Examples

In this section we give a variety of examples, to show that 1-dimensional asymptotic classes arise in a broad range of contexts. Examples arise from supersimple pseudofinite structures. Indeed, it will be shown in Lemma 4.1 that any infinite ultraproduct of a 1-dimensional asymptotic class is supersimple, so does not have the strict order property. In particular, we draw attention to the following non-example.

Example 3.1. The class of all finite totally ordered sets is not a 1-dimensional asymptotic class. For the formula x < y can pick out an arbitrary proper initial segment of a structure, as a varies.

Example 3.2. By the main theorem of [6], the class of finite fields (in the language of rings) is a 1-dimensional asymptotic class.

Example 3.3. (i) Let d be a positive integer, and C_{d} be a class of arbitrarily large finite vertex transitive graphs of valency d. Then C_{d} is a 1-dimensional asymptotic class.

To see this, we apply Lemma 2.5. Let (M_{i} : i ∈ ω) be a collection of nonisomorphic members of C, and let U be a non-principal ultrafilter on ω. We show that M := Π_{i∈ω}M_{i}/U is strongly minimal. Let L be a 2-sorted language, with a sort P, with a binary relation R, for graphs, and a sort Q, with language (.,^{−1}, 1)) for groups, together with a function P ×Q → P for an action of a group on a graph (so we write automorphisms on the right). The structure Π_{i∈ω}(M_{i}, Aut(M_{i}))/U consists of a graph, with domain the sort P, together with a vertex transitive group of automorphisms. The graph is isomorphic to M, and so in particular, M is a vertex transitive infinite graph of finite valency d. It is well known that such graphs are strongly minimal—see, for example, [2] Lemma 2.2.11 for a more general result.

(ii) Let d be a positive integer, and let C be an infinite class of finite graphs of valency d containing just finitely many graphs of any given girth (the girth of a graph is the shortest length of a cycle). If M is an infinite ultraproduct of members of C, them M has no cycles, so is a forest, i.e., a union of trees. Since M also has valency d, it is vertex transitive. Hence, again by Lemma 2.5, C is a 1-dimensional asymptotic class.

Example 3.4. For each prime power q ≡ 1 ( mod 4), let P_{q} be the Paley graph on the finite field 𝔽_{q} of q elements, that is, the graph whose vertex set is 𝔽_{q}, with a joined to b if a − b is a square. This relation is symmetric. We claim that C_{q} := {P_{q} : q ≡ 1 ( mod 4)} is a 1-dimensional asymptotic class.

The main ingredient is the following result of Bollobás and Thomason ([3], see also Theorem 10 in Ch. XIII.2 of [4]): let U and W be disjoint sets of vertices of the Paley graph P_{q} with |U ∪ W | = m, and let v(U, W) be the number of vertices not in U ∪ W joined to each vertex of U and no vertex of W; then

|v(U, W) − 2^{−m}q| ≤ \frac{1}{2}(m − 2 + 2^{−m+1})q^{\frac{1}{2}} + m/2.

Suppose now that P is an infinite ultraproduct of Paley graphs. Let σ_{m} be the sentence saying that if U and W are disjoint sets of vertices with |U ∪ W | = m, then there is a vertex joined to every member of U and to no member of W. Then σ_{m} holds in sufficiently large finite Paley graphs, by the inequality above, and so holds in P. In particular, P is elementarily equivalent to the random graph, so its theory has quantifier-elimination. Thus, every formula ψ(x, ȳ) has a quantifier-free equivalent in sufficiently large finite graphs. Hence, it suffices to check clauses (i) and (ii) of Definition 1.2 for quantifier-free formulas φ(x, ȳ).

Let ȳ = (y_{1}, …, y_{m}). We may suppose that φ(x, ȳ) is a disjunction of t formulas of the form

⋀_{i∈A} x ∼ y_{i} ∧ ⋀_{i∈B} x ≁ y_{i},

where the disjunction ranges over t partitions {1, …, m} = A ∪ B, and ∼ denotes graph adjacency. The formula φ also could involve atomic formulas x = y_{i} or x ≠ y_{i}, but we may ignore these; for example, inequalities affect the solution sets of φ(x, ȳ) by a uniformly bounded number depending only on φ(x, ȳ) and independent of ȳ. In particular, for q ≡ 1( mod 4) and ā ∈ P_{q}^{m},

||φ(P_{q}, ā)| − tq/2^{m}| ≤ \frac{t}{2}(m − 2 + 2^{−m+1})q^{\frac{1}{2}} + tm/2.

Conditions (i) and (ii) of Definition 1.2 follow easily.

Example 3.5. For each prime power q ≡ 3 ( mod 4), let P_{q} be the Paley tournament, with vertex set 𝔽_{q} and with u → v if and only if u − v is a square in 𝔽_{q}. Let C := {P_{q} : q ≡ 3 ( mod 4)}. The asymptotic result for Paley tournaments corresponding to the one above for Paley graphs is due to Graham and Spencer [17]. It yields as above that C is a 1-dimensional asymptotic class, and that any infinite ultraproduct of members of C is elementarily equivalent to the countable universal homogeneous tournament.

We now consider asymptotic classes of 3-hypergraphs. Recall that a two-graph is a 3-hypergraph (H, E) (where E, the edge set, is a collection of 3-element subsets of H) such that every 4-element subset of H contains an even number of members of E. If (H, ∼) is a graph, then there is a two-graph (H, E) whose edges are the 3-subsets of H which contain an odd number of graph-edges. In fact, every two-graph (H, E) arises in this way from a graph (H, ∼), and two graphs (H, ∼_{1}) and (H, ∼_{2}) give the same two-graph if and only if they are ‘switch-equivalent’, i.e., there is a partition H = U ∪ V of the vertex set such that ∼_{2} is obtained from ∼_{1} by interchanging edges and non-edges for pairs {a, b} which meet both U and V. For more on two-graphs, see Chapter 11 of [16]. There is a countable universal homogeneous two-graph. It can be constructed by amalgamation of finite two-graphs, and is the two-graph of the random graph.

Example 3.6. For each prime power q ≡ 1 ( mod 4), let H_{q} be the 3-hypergraph with vertex set 𝔽_{q}, with {a, b, c} an edge if and only if (a − b)(b − c)(a − c) is a square of 𝔽_{q}. Then H_{q} is the two-graph of P_{q}, and hence if C consists of the set of all such H_{q}, every infinite ultraproduct of C is elementarily equivalent to the countable universal homogeneous two-graph.

It follows easily from the result of Bollobás and Thomason cited above that C is a 1-dimensional asymptotic class. To see this, let H_{q} ∈ C and U ⊂ H_{q} with |U| = m. Suppose that a ∈ H_{q} \ U, and let X be the collection of 2-element subsets {u, v} of U such that {u, v, a} is an edge of H_{q}. Let

U(X) := {z ∈ H_{q} \U : (∀x, y ∈ U, x ≠ y){x, y, z} is an edge in H_{q} ↔ {x, y} ∈ X)}.

For each z ∈ H_{q} \ U, let N(z) be the set of neighbors of z in U in the underlying Paley graph P_{q}. It can be checked for all z ∈ H_{q} \ U that

z ∈ U(X) ↔ (N(z) = N(a) ∨ N(z) = U \ N(a)).

It follows that

||U(X)| − 2^{−(m−1)}q| ≤ (m − 2 + 2^{−m+1})q^{\frac{1}{2}} + m.

Hence, by quantifier elimination for the countable universal homogeneous twograph, we see that C is a 1-dimensional asymptotic class.

Remark 3.7. (1) There is a notion of ‘two-tournament’ analogous to that of ‘twograph’. A two-tournament on a set X is a ternary relation R on X obtained from a tournament (X, →) by putting Rx_{1}x_{2}x_{3} if x_{1}, x_{2}, x_{3} are distinct, and an odd number of the relations x_{1} → x_{2}, x_{2} → x_{3}, x_{1} → x_{3} hold. For each prime power q ≡ 3 ( mod 4), let T_{q} be the two-tournament on 𝔽_{q} obtained from the Paley tournament in this way. Then the collection of all such T_{q} forms a 1-dimensional asymptotic class.

(2) It also is possible to find asymptotic classes of two-graphs or two-tournaments living on the projective line PG_{1}(𝔽_{q}), where q is congruent to 1 or 3 modulo 4, respectively. These admit the 2-transitive group PSL_{2}(q) of automorphisms with two orbits on ordered triples of distinct elements. Their ultraproducts are elementarily equivalent to the universal homogeneous two-graph and two-tournament, respectively.

The next result concerns the ‘smoothly approximable structures’ described in detail in [9]. First, recall from Definition 2.1.1 of [9] that a finite substructure N of a structure M is k-homogeneous if all ∅-definable relations on M induce ∅-definable relations on N, and for every pair of k-tuples ā, b̄ of N, ā and b̄ have the same type in N if and only if they have the same type in M. A structure M is smoothly approximable if its theory is ℵ_{0}-categorical, and every finite subset of M is contained in a finite substructure N of M which is |N|-homogeneous in M. Since the choice of language is not an issue, it is convenient to assume that M has quantifier elimination, in which case this holds also for the finite homogeneous substructures. By [8, Corollary 7.4], every ℵ_{0}-categorical ω-stable structure is smoothly approximable.

In [9], a class of Lie geometries is defined. A structure is Lie coordinatizable if it is bi-interpretable with a structure which is Lie coordinatized, that is, built from Lie geometries in a carefully prescribed treelike way, where the tree has finite height. A countable Lie coordinatizable structure is a direct limit of a sequence of ‘envelopes’, essentially, a sequence of finite |N|-homogeneous substructures N of M. It also is elementarily equivalent to any infinite ultraproduct of the envelopes. It is shown in [9] that Lie coordinatizability and smooth approximation coincide for countably infinite structures. For the geometries in the theorem below the finite envelopes are just the natural finite approximating structures. In these examples, unlike the example of all finite fields, the field is fixed, but a vector space dimension is unbounded.

Theorem 3.8. Let M be a smoothly approximable linear, affine, or projective geometry, and C the collection of finite envelopes of M. Then C is a 1-dimensional asymptotic class.

Before proceeding to the proof, we note that Elwes [13] has shown that for every smoothly approximable structure M (equivalently, Lie-coordinatizable structure), there is a subcollection E of the set of finite envelopes of M which for some k forms a k-dimensional asymptotic class and witnesses that M is smoothly approximated. Here k is determined by M – again, see [9]. The definition of a k-dimensional asymptotic class is given in [13], and uses slightly weaker error terms than those of Definition 1.2.

Proof of Theorem 3.8. Observe first that if the conclusion holds for some M over a language L, then by 2.4 it holds for any expansion of M by constants.

We further assert that if it holds for M, with class of envelopes C, then it holds for every smoothly approximable reduct M′ of M to a language L′ ⊂ L, whose corresponding class C′ consists of reducts N′ of members N of C. Indeed, clause (i) of Definition 1.2 is immediate. To see that (ii) holds for C′, let φ(x, ȳ) be an L′-formula with ȳ = (y_{1}, …, y_{m}), and let μ_{1}, …, μ_{r} be the measures of the 1-dimensional sets defined by φ(x, ȳ) in members of C′. There are finitely many inequivalent formulas in m variables in M′, say ρ_{1}, …, ρ_{t}. If N′ ∈ C′ then {ȳ ∈ (N′)^{m} : φ(N′, ȳ) has measure μ_{i}} is 0-definable in N′, and thus is defined by some ρ_{j}(ȳ). The danger is that μ_{i} may correspond to a different formula ρ_{k} in a different member of C′. As C is a 1-dimensional asymptotic class, there is an L-formula ψ_{i}(ȳ) which, in all sufficiently large N ∈ C, defines {ȳ ∈ N^{m} : φ(N, ȳ) has measure μ_{i}}. If for some j we have that ∀ȳ[ψ_{i}(ȳ) ↔ ρ_{j}(ȳ)] holds in some sufficiently large N ∈ C, then it holds in all sufficiently large N ∈ C. It follows that ρ_{j} defines {ȳ : φ(N′, ȳ) has measure μ_{i}} in all sufficiently large N′ ∈ C′, as required.

A similar argument shows that if C is a 1-dimensional asymptotic class of envelopes of M, and φ(x) is a formula which defines a smoothly approximable substructure, then the set of restrictions of members of C to the set of realizations of φ(x) is a 1-dimensional asymptotic class (as we assumed M has quantifier elimination, this set has the full structure induced from M). The same holds if here x is a tuple of variables, provided the set defined by φ has dimension 1. Likewise, if E is a 0-definable equivalence relation with all classes of the same (finite) size, then the class of envelopes of M/E is a 1-dimensional asymptotic class.

Putting together these collected facts, we only need to prove the theorem for the weak linear geometries described in Definition 2.1.4 of [9]. As a consequence of the result above on reducts we may further suppose any Galois group involved is trivial, and hence, in the notation of Definition 2.1.4 of [9], that K = L and its elements are named by constants. This avoids, for example, having to handle separately structures with automorphism group GL(ℵ_{0}, q) or ΓL(ℵ_{0}, q).

All six cases in the definition are now relatively straightforward. For example, consider a vector space with a nondegenerate symplectic form, Case 4 with σ trivial and the bilinear form β (here denoted ⟨−, −⟩) symplectic. In this case, a complete non-algebraic type p(x, ā) over a tuple of parameters ā = (a_{1}, …, a_{m}) is determined by the values for 1 ≤ i ≤ m of ⟨x, a_{i}⟩ in the field K, so has dimension 1 and measure 1/q^{d} where d is the vector space dimension of the span of ā. An arbitrary non-algebraic formula φ(x, ȳ) is a finite disjoint union of such non-algebraic types— possibly after addition or removal of finitely many points—and so its measure is the corresponding finite sum, so depends just on the dimension of the span of ȳ.

Case 6, the quadratic geometries, is slightly more complicated. There is an alternative description of this class of geometries, which appears, for example, in the proof of Case (ii) of Lemma 4.1 in [24], and makes the argument here more direct. Let V be a vector space over a field 𝔽_{q} of characteristic 2 equipped with a quadratic form Q of type O^{−} and corresponding bilinear form ⟨−, −⟩. Let d, d′, e_{1}, …, e_{n}, f_{1}, …, f_{n} be a basis for V as in that proof. Let G be the stabilizer of ⟨d⟩ in P O^{−}(2n + 2, q) and let U be an orbit of G on non-singular 2-spaces containing d. Then the permutation structure induced by G on U is a geometry that falls under Case 6, and all such geometries arise in this way. It follows from the first three paragraphs above that these geometries also form a 1-dimensional asymptotic class. □

Apart from examples arising from Lemma 2.5 and the class of finite cyclic groups given below in Theorem 3.14, the examples we present of 1-dimensional asymptotic classes are all derived from finite fields. It is possible to produce 1-dimensional asymptotic classes which are not uniformly interpretable in finite fields but have unstable ultraproducts. To illustrate, let f be a slowly growing, strictly increasing function. Then let C be the set of all graphs on 𝔽_{q}, where q ≡ 1 ( mod 4), obtained from the Paley graph on 𝔽_{q} by interchanging edges and non-edges on at most f(q) pairs from 𝔽_{q}. Also, the first author’s PhD student Mark Ryten has shown that there are N-dimensional asymptotic classes whose members are certain finite difference fields, and these classes are not uniformly interpretable in finite fields either.

The next two results show that smoothly approximable Lie geometries are interpretable in pseudofinite fields.

Lemma 3.9. Let q be a prime power. Then:

(i) For each fixed q, the 2-sorted structure consisting of a vector space V over 𝔽_{q} of dimension n and a nondegenerate symmetric bilinear form ⟨−, −⟩: V × V → 𝔽_{q} is parameter-definable in the finite field 𝔽_{q^{n}} uniformly in n. (ii) The analogue of (i) also holds if we assume instead that ⟨−, −⟩ is a nonde-

generate alternating bilinear form.

Proof. (i) Put F := 𝔽_{q^{n}}. Then F is an n-dimensional vector space over 𝔽_{q}. Consider the trace function Tr : F → 𝔽_{q}. This is an 𝔽_{q}-linear map, and by Hilbert’s Theorem 90 (see for example Theorem 6.3 of [27], Ch. VIII), ker(Tr) = {y−y^{q} : y ∈ F }. Note that this definition is uniform in n provided that q is fixed. Furthermore, |F : ker(Tr)| = q, and so is constant as n varies. It follows that Tr is definable uniformly as n varies, as it suffices to specify the value of Tr on each of the q cosets of ker(Tr) in F. We now define ⟨x, y⟩ on F by ⟨x, y⟩ = Tr(xy). Then ⟨−, −⟩ is a symmetric bilinear form on F.

(ii) In the alternating case, we treat 𝔽_{q^{2n}} as a vector space over 𝔽_{q} with a definable nondegenerate alternating form, all interpretable in the field 𝔽_{q^{n}}. To this end, we first observe that the field 𝔽_{q^{2n}} is interpretable in the field 𝔽_{q^{n}} uniformly in n, as we have fixed q. Since 𝔽_{q^{2n}} is a 2-dimensional vector space over 𝔽_{q^{n}}, there is a definable nondegenerate alternating bilinear form ⟨−, −⟩_{a} over 𝔽_{q^{n}}. Now define ⟨−, −⟩ : 𝔽_{q^{2n}} × 𝔽_{q^{2n}} → 𝔽_{q} by putting ⟨u, v⟩ = Tr(⟨u, v⟩_{a}), where Tr is the trace function 𝔽_{q^{n}} → 𝔽_{q}. It is easily checked that ⟨−, −⟩ is an alternating bilinear form. To see that it is nondegenerate, let u ∈ 𝔽_{q^{2n}} with u ≠ 0. We now choose b ∈ 𝔽_{q^{n}} so that the polynomial x − x^{q} − b has no root in 𝔽_{q^{n}}—this clearly is possible—then choose v ∈ 𝔽_{q^{2n}} with ⟨u, v⟩_{a} = b. Then ⟨u, v⟩ = Tr(⟨u, v⟩_{a}) = Tr(b) ≠ 0 by the choice of b and Hilbert’s Theorem 90. □

Corollary 3.10. Every linear, affine, or projective smoothly approximable Lie geometry is interpretable in a pseudofinite field.

Proof. As in the proof of Theorem 3.8, we work through examples (1)-(6) in Definition 2.1.4 of [9]. Observe that the projective and affine geometries are interpretable in these. Cases (1) and (2) are easy. The orthogonal space (5) is done in Lemma 3.9(i) above, and the symplectic case of (4) is dealt with in (ii). The quadratic geometry (6) is handled as in Theorem 3.8—it is interpretable in an orthogonal space.

To handle the self-dual geometry (3), consider the proof of Lemma 3.9(ii), with the triple (𝔽_{q}, 𝔽_{q^{n}}, 𝔽_{q^{2n}}). Let w ∈ 𝔽_{q^{2n}} \ 𝔽_{q^{n}}, and let V := 𝔽_{q^{n}} and W := {aw : a ∈ 𝔽_{q^{n}}}. It is easily checked that 𝔽_{q^{2n}}, regarded as a vector space over 𝔽_{q}, is a direct sum of V and W. The restriction to V × W of the bilinear map ⟨−, −⟩ defined above now puts a self-dual geometry on V × W.

Lastly, we must show that a vector space with a hermitian form—the remaining case of (4)—is interpretable in a pseudofinite field. This can be done just as in Lemma 3.9(ii): we simply replace the alternating form ⟨−, −⟩_{a} on F_{q^{2n}} over 𝔽_{q^{n}} by a hermitian form ⟨−, −⟩_{h}. □

The final examples in this section deal with groups. Proposition 3.11 provides examples of 1-dimensional asymptotic classes of groups that Theorem 3.12 demonstrates are in fact typical. The last result of this section, Theorem 3.14, establishes that the class of all finite cyclic groups forms a 1-dimensional asymptotic class.

A group G is extraspecial if for some p we have

G′ = Z(G) = Φ(G) ≅ ℤ_{p},

where Φ(G) denotes the Frattini subgroup of G. See [11, Section 20], for example, for further information about extraspecial groups. Countably infinite extraspecial groups were shown by Felgner in [15] to be ℵ_{0}-categorical.

Proposition 3.11. Let p be an odd prime and let C_{p} be the class of finite extraspecial groups of exponent p. Then C_{p} is a 1-dimensional asymptotic class.

We emphasis that in this proposition the prime p is fixed.

Proof. We first observe that an extraspecial group of exponent p and order p^{2n+1} is uniformly—in n, but not in p—interpretable in a vector space V of dimension 2n over 𝔽_{p}, endowed with a symplectic form ⟨−, −⟩. Indeed, let G = V × 𝔽_{p}, endowed with the binary operation ∗ given by

(u, λ) ∗ (v, μ) = (u + v, λ + μ + \frac{1}{2}⟨u, v⟩)

for (u, λ), (v, μ) ∈ V × 𝔽_{p}. Then—see [11, 20.6])—(G, ∗) is extraspecial of order p^{2n+1} and exponent p, and is the unique such group up to isomorphism.

It is easily verified that the extraspecial group of exponent p and order ℵ_{0} is smoothly approximable by finite extraspecial groups; for example, apply the description of the automorphism groups of finite extraspecial groups in [11, 20.8]. Since the 2-sorted structure (V, 𝔽_{p}) of the preceding paragraph is essentially a Lie geometry, the collection of such structures forms an asymptotic class. The lemma now follows easily, as in the first two paragraphs of the proof of Theorem 3.8. □

The next result shows that the class of extraspecial p-groups for a fixed prime p is in some sense a typical 1-dimensional asymptotic class of groups. The theorem says that any 1-dimensional asymptotic class of groups consists of groups which are ‘bounded-by-abelian-by-bounded.’ Below, and elsewhere in the paper, H′ denotes the derived subgroup of H, and ‘uniformly definable’ means that there is a single defining formula across members of C.

Theorem 3.12. Let C be a 1-dimensional asymptotic class of groups. Then there is a positive integer d such that if G ∈ C, then G has a uniformly ∅-definable that |G : H| ≤ d, H′ ≤ Z(H) and |H′| ≤ d.

Proof. Since the conjugacy relation on a group is definable, there is a constant c such that for all G ∈ C, each conjugacy class of G has size at most c or has positive measure. We call a conjugacy class small if it has size at most c. More generally, given a formula φ(x, ȳ), a group G ∈ C, and ā ∈ G^{m}, we may refer to φ(G, ā) as small or of positive measure, with the obvious meaning. In particular, every definable subgroup H of G is either small or of small index: if H has positive measure, then its cosets are disjoint and of the same positive measure, whence their number is bounded.

Observe that if g, h ∈ G each have at most c conjugates, then gh has at most c^{2} conjugates. It follows that there is a positive integer e such that if |G| > e, the union of the small conjugacy classes is a normal subgroup N(G) of G, and is definable, uniformly in the class C. Also, there is t ∈ ω and e′ > e such that if |G| > e′ then either N(G) contains at most t elements, or N(G) has positive measure, and just one of these alternatives holds. We now define

C_{1} := {G ∈ C : |G| > e′ ∧ N(G) has positive measure}

and

C_{2} := {G ∈ C : |G| > e′ ∧ |N(G)| ≤ t}.

Then {G ∈ C : |G| > e′} is the disjoint union of C_{1} and C_{2}. We now establish

Claim. The class C_{2} is finite.

Proof of Claim. We assume not for a contradiction. For each G ∈ C_{2} and M with N(G) ≤ M ≤ G, write \overline{M} := M/N(G). There is a positive integer d such that if G ∈ C_{2} then Ḡ has at most d conjugacy classes, all except the trivial one having preimage in G of positive measure. In particular, \overline{G} has a bounded number of non-trivial normal subgroups, all uniformly interpretable, as each is a union of at most d conjugacy classes, and each with preimage in G of positive measure. The group \overline{G} cannot have two distinct non-trivial minimal normal subgroups. Indeed, as two such subgroups intersect in the identity, each would be of unbounded order and index and thus the groups G ∈ C_{2} would have a definable subgroup of positive measure and unbounded index, which is impossible. Hence, such a group \overline{G} has a unique smallest non-trivial normal subgroup \overline{M}, with preimage M, and |\overline{G} : \overline{M}| is bounded. As \overline{M} has boundedly many conjugacy classes, it is easy to see that \overline{M} must be non-abelian.

The group \overline{M} is characteristically simple, and hence is a direct product \overline{M} = S_{1}× … × S_{r} of isomorphic non-abelian simple groups. Since \overline{G}/\overline{M} acts transitively on \{S_{1}, …, S_{r}\}, we see that r is bounded. As \overline{M} has a bounded number of conjugacy classes, it follows that S_{i} is (uniformly) definable for each i = 1, …, r. As each S_{i} has positive measure we see that t = 1, that is, \overline{M} is a non-abelian simple group.

Let |\overline{M}| = p_{1}^{a_{1}} … p_{k}^{a_{k}}, where p_{1}, …, p_{k} are distinct primes, and a_{1}, …, a_{k} > 0. As G ranges over C_{2}, we see that the groups \overline{M} have a bounded number of conjugacy classes, and so we can bound k. It follows that some Sylow subgroup \overline{S} of \overline{M} is large. Since \overline{S} has non-trivial center, we may choose g ∈ Z(\overline{S}) \ \{1\}. The group C_{g} := C\overline{M}(g) is large as well, and thus has bounded index in \overline{M} as we range over G ∈ C_{2}. Since \overline{M} is simple, we see that such a group C_{g} must equal \overline{M}; otherwise the kernel of the action of \overline{M} on the left cosets of C_{g} by left multiplication would be a proper and, as [\overline{M} : C_{g}] is bounded, non-trivial normal subgroup of \overline{M}. However, if C_{g} = \overline{M} then g ∈ Z(\overline{M}). It then follows by simplicity that \overline{M} is abelian, a contradiction, and the Claim is proved.

By the Claim, we may assume C = C_{1}. Then N = N(G) has positive measure for each large enough G ∈ C. As its cosets have the same positive measure, there is some r ∈ ℕ such that |G : N| ≤ r. By a result of Wiegold [36] (see also 5.14 of I.D. Macdonald [28]), there is some u ∈ ℕ depending only on the maximal size of a conjugacy class of N such that |N′| ≤ u. In particular, N′ is uniformly definable as G ranges through C. Now put K := C_{N}(N′). Then K is uniformly definable, and there is fixed v ∈ ℕ such that |G : K| ≤ v, again as N consists of the small conjugacy classes in G. We have K ∩ N′ ≤ Z(K) ≤ K. If Z(K) has positive measure, then we may put H := Z(K). If not, then there is some w ∈ ℕ for which |Z(K)| ≤ w for all G ∈ C. Then K/(K ∩ N′) ≅ KN′/N′ ≤ N/N′ is abelian, and hence K/Z(K) is abelian. We then put H := K and d := max{v, w}, and the proof is complete. □

Remark 3.13. The above proof did not require the full strength of Definition 1.2; dimension but not measure was used. The result would hold of any class C of finite groups such that any infinite ultraproduct of members of C is supersimple of S_{1}-rank 1 (see Lemma 4.1 below).

Theorem 3.14. Let C be the class of all finite cyclic groups. Then C is a 1dimensional asymptotic class.

Proof. Below, we regard the cyclic group ℤ_{n} as having domain {0, …, n − 1}, with addition modulo n. We thus sometimes treat an element as a member of both ℤ_{n} and ℤ).

By Szmielew’s definability theorem ([33]; see also Theorem A.2.2 on p. 663 of [19]), every formula φ(x, ȳ) in the language of groups is equivalent, uniformly in all abelian groups, to a Boolean combination of formulas of the form p^{m}|t(x, ȳ) or t(x, ȳ) = 0, where p is a prime, t(x, ȳ) is a term, and division is with respect to the group, that is, p^{m}|t(x, ȳ) means

(∃z) \underbrace{z + … + z}_{p^{m} terms} = t(x, ȳ).

Thus, we may suppose that φ(x, ȳ) is a disjunction of conjunctions of expressions of the above form and their negations. By increasing the number of conjunctions, we may assume further that they are pairwise inconsistent. It follows that we may now suppose that φ(x, ȳ) is just a conjunction of such conditions and their negations.

As a further simplification, by an inclusion-exclusion argument, we may suppose that all the conditions are positive; that is, φ(x, ȳ) is a conjunction of conditions of the above form. A term t(x, ȳ) has the form ℓx + Σ_{i=1}^{r}ℓ_{i}y_{i}, where ℓx is an abbreviation for the sum of ℓ copies of x, but we may easily reduce to the case when it has form ℓx + y.

Suppose one of the conjuncts has the form ℓx + y = 0. This holds in the cyclic group ℤ_{n} if and only if (ℓ, n)|y in ℤ, and if it has solutions, it has exactly (ℓ, n) of them in ℤ_{n}. It follows that if the formula φ(x, ȳ) involves such a conjunct, then in all ℤ_{n} it has a bounded number of solutions, namely at most ℓ. Trivially we can define the set of ȳ where φ(x, ȳ) has a given (bounded) number of solutions in all ℤ_{n}. Thus, we may suppose that φ(x, ȳ) has the form

⋀_{i=1}^{r} p_{i}^{n_{i}} | ℓ_{i}x + y_{i}.

For each i = 1, …, r, let e_{i} := p_{i}^{m_{i}} = (p_{i}^{n_{i}}, n) . Now

ℤ_{n} ⊧ p_{i}^{n_{i}} | ℓ_{i}x + y_{i} ⇔ (∃z) p_{i}^{n_{i}}z ≡ ℓ_{i}x + y_{i} ( mod n) in ℤ
⇔  e_{i}| ℓ_{i}x + y_{i} in ℤ.

Thus, the number of solutions in ℤ_{n} of φ(x, ȳ) is the number of solutions in the set {0, …, n − 1} of the simultaneous integer congruences

ℓ_{i}x + y_{i} ≡ 0 ( mod e_{i}) for i = 1, …, r.

Let d_{i} := (ℓ_{i}, e_{i}). Also, for all i, j ≤ r let

Δ_{ij} := \frac{ℓ_{i}y_{j} − ℓ_{j}y_{i}}{d_{i}d_{j}} .

By a classical fact about simultaneous linear congruences—see Theorem 5.4.3 of Shapiro [32] for example), the system of congruences above has a simultaneous solution if and only if

d_{i}| y_{i} for i = 1, …, r

and

Δ_{ij} ≡ 0 ( mod (\frac{e_{i}}{d_{i}} , \frac{e_{j}}{d_{j}} ))

for all i, j ∈ {1, …, r}. Furthermore, if these conditions hold, then the solution is unique modulo L := lcm\{\frac{e_{1}}{d_{1}} , …, \frac{e_{r}}{d_{r}} \}. Thus, either the system of equations has no solution, or it has exactly n/L many solutions. Since d_{i} ≤ e_{i} ≤ p_{i}^{n_{i}}, the value of L is bounded in terms of the original formula φ. This shows that clause (i) of Definition 1.2 holds for C.

To prove that (ii) of Definition 1.2 holds, we show that there is a formula χ_{L}(ȳ) such that for each n and ȳ ∈ ℤ_{n}^{r},

ℤ_{n} ⊧ χ_{L}(ȳ)
⇔ φ(x, ȳ) (which is ⋀_{i=1}^{r} p_{i}^{n_{i}} |ℓ_{i}x + y_{i}) has exactly n/L solutions in ℤ_{n}.

Note, for i = 1, …, r, that f_{i} := (ℓ_{i}, p_{i}^{n_{i}}) depends only on the formula φ. As d_{i} = (ℓ_{i}, p_{i}^{n_{i}}, n), we see that d_{i} = (f_{i}, n). To state that φ(x, ȳ) has exactly n/L solutions in ℤ_{n}, it suffices to see the following.

a. For each divisor d_{i} of f_{i}, there is a sentence σ_{i,d_{i}}, such that σ_{i,d_{i}} holds in

ℤ_{n} precisely if d_{i} = (f_{i}, n). b. Given that d_{i} = (f_{i}, n), for each i, there is a formula ψ_{i}(y_{i}) which expresses

that d_{i}|y_{i} in ℤ. c. Assuming that d_{i} = (f_{i}, n) and d_{i}|y_{i}, we can express the conditions involving the Δ_{ij}, for each i, j, d_{i}, d_{j}, e_{i}, e_{j}; that is, there is a formula with parameters y_{i}, y_{j} that, uniformly in ℤ_{n}, expresses that

d_{i}d_{j} (\frac{e_{i}}{d_{i}} , \frac{e_{j}}{d_{j}} )| ℓ_{i}y_{j} − ℓ_{j}y_{i}.

For (a), it suffices to note that for any integer r there is a sentence τ_{r} that holds in ℤ_{n} just if r|n in ℤ. Indeed, let τ_{r} be the sentence

(∃x) rx = 0 ∧ ⋀_{0<s<r} sx ≠ 0.

If r|n, with rk = n then ℤ_{n} ⊧ τ_{r} with k as a witness for x; conversely, if ℤ_{n} ⊧ (rx = 0 ∧ ⋀_{0<s<r} sx ≠ 0), then there is t ∈ ℤ with rx = tn. The minimality of r ensures that (r, t) = 1, and hence, as r|tn, that r|n.

For (b), first observe that d_{i}|n in ℤ. We assert that

d_{i}|y_{i} in ℤ if and only if ℤ_{n} ⊧ (∃x) d_{i}x = y_{i}.

The left-to-right direction is immediate. For the converse, suppose ℤ_{n} ⊧ (∃x) d_{i}x = y_{i}. Then in ℤ ⊧ (∃k) (∃x) d_{i}x − y_{i} = kn. As d_{i}|n in ℤ there is an m ∈ ℤ with n = d_{i}m. Hence, in ℤ we have d_{i}(x − km) = y_{i} and thus d_{i}|y_{i}.

For (c), first observe that d_{i}d_{j}|ℓ_{i}y_{j} − ℓ_{j}y_{i}, so the condition can be rewritten as

(\frac{e_{i}}{d_{i}} , \frac{e_{j}}{d_{j}} )| \frac{ℓ_{i}y_{j} − ℓ_{j}y_{i}}{d_{i}d_{j}} .

Since e_{i}|n, the method for (b) gives that this is expressible. □

4. Ultraproducts of asymptotic classes

In the next two sections, we shall assume familiarity with S_{1}-rank and D-rank, as defined for example in Section 6 of [25]. It is shown there that if X ⊂ M^{k} is a definable subset of a supersimple structure M, and any of the D-rank, SU-rank or S_{1}-rank of X is finite, then they are all finite and equal. If moreover T is a complete theory relative to which all formulas have finite D-rank, then T is supersimple.

Lemma 4.1. Let C be a 1-dimensional asymptotic class, and let M be an infinite ultraproduct of members of C. Then Th(M) is supersimple of S_{1}-rank 1.

Proof. Suppose that M = Π_{i∈ω}M_{i}/U is an infinite ultraproduct of structures M_{i} ∈ C, and the formula x = x has S_{1}-rank greater than 1. Then there is a formula φ(x, ȳ), a natural number N, and a sequence (ā_{j} : j ∈ ω) of elements of M^{m} such that the sets φ(M, ā_{j}) are infinite, and |φ(M, ā_{j}) ∧ φ(M, ā_{j′})| ≤ N for all distinct j, j′ ∈ ω. As C is a 1-dimensional asymptotic class there is a μ ∈ ℝ with 0 < μ ≤ 1, a constant c, and for every r ∈ ω a set U_{r} ∈ U such that for each k ∈ U_{r} there are ā_{j} ∈ M_{k}^{m} for j = 1, … r in the finite structure M_{k}, where |M_{k}| = m_{k}, satisfying

||φ(M_{k}, ā_{j})| − μm_{k}| ≤ cmk^{\frac{1}{2}}

for each j, and for distinct j, j′ ∈ {1, …, r},

|φ(M_{k}, ā_{j}) ∧ φ(M_{k}, ā′_{j})| ≤ N.

It follows that

| ⋃_{j=1}^{r} φ(M_{k}, ā_{j})| ≥ r(μm_{k} − cmk^{\frac{1}{2}} ) − \binom{r}{2}N.

For sufficiently large r the expression on the right is greater than m_{k}, a contradiction.

Thus, in M the formula x = x has S_{1}-rank 1. It follows easily that this formula has D-rank 1. Hence, by Lemma 2.4 of [10], if x̄ = (x_{1}, …, x_{n}) then x̄ = x̄ has D-rank n. It follows that all formulas have finite D-rank, so M is supersimple. □

Proposition 4.2. Let C be a 1-dimensional asymptotic class. Then the following are equivalent.

(i) Some ultraproduct of members of C is unstable. (ii) There is m ∈ ω and a formula φ(x, ȳ) (with ℓ(ȳ) = m) such that for each k ∈ ℕ, there are M ∈ C and ā_{1}, …, ā_{k} ∈ M^{m} with

a. |φ(M, ā_{i})| ≥ k for each i = 1, …, k

and

b. |φ(M, ā_{i})△φ(M, ā_{j})| ≥ k for all distinct i, j ∈ {1, …, m}.

Proof. (i) ⇒ (ii). Assume (i) holds. By Lemma 4.1, no ultraproduct of members of C has the strict order property, so some ultraproduct has the independence property. Hence, there is a formula φ(x, ȳ) such that for all n ∈ ω the following holds: there is M ∈ C and {a_{i} : 1 ≤ i ≤ n} such that for every S ⊂ {1, …, n} there is b̄_{S} ∈ M^{m} such that for all i ∈ {1, …, n}, we have φ(a_{i}, b̄_{S}) ⇔ i ∈ S. Condition (ii) now follows easily.

(ii) ⇒ (i). Assume that (ii) holds for some m and φ(x, ȳ). We shall show that φ(x, ȳ) is an unstable formula in some ultraproduct of members of C. For this, it suffices to show that for all t there is an M_{t} ∈ C, and b_{1}, …, b_{t} ∈ M and ā_{1}, …, ā_{t} ∈ M^{m} such that φ(b_{i}, ā_{j}) ⇔ i ≥ j for all i, j ∈ {1 …, t}.

By condition (ii) and Ramsey’s Theorem, there is a constant c and positive rationals μ, ν such that for arbitrarily large r, there is M ∈ C, and a set A := {ā_{1}, …, ā_{r}} ∈ M^{m}, such that

1. for each i ∈ \{1, …, r\}, we have ||φ(M, ā_{i})| − μ|M|| ≤ c|M|^{\frac{1}{2}} ,

2. for i, j ∈ {1, …, r} with i < j, we have ||φ(M, ā_{i}) \ φ(M, ā_{j})| − ν|M|| ≤

c|M|^{\frac{1}{2}} .

Furthermore, we may arrange that (ā_{i} : 1 ≤ i ≤ r) is indiscernible with respect to any given finite set of formulas; in particular, for a fixed K, with respect to formulas defining the asymptotics of sets

{x : φ(x, ā_{i_{1}}) ∧ … ∧ φ(x, ā_{i_{k}}) ∧ ¬φ(x, ā_{i_{k+1}}) ∧ … ∧ ¬φ(x, ā_{i_{K}})},

where i_{1} < … < i_{K}.

Fix a particular K, and choose M and a very large set {ā_{1}, …, ā_{r}} ⊂ M^{m} with respect to K, with the above properties, including the indiscernibility.

We claim that for each 1 ≤ p ≤ q ≤ K, there is a positive real number ρ = ρ(p, q) such that

||\{x : ⋀_{1≤i≤p} φ(x, ā_{i}) ∧ ⋀_{p+1≤j≤q} ¬φ(x, ā_{j})\}| − ρ|M|| ≤ c|M|^{\frac{1}{2}} .

Observe that this assertion is true for the pairs (1, 1) and (1, 2). Now suppose it is true for the pair (p, q) but not for (p, q + 1), where 1 < q < K. Put ℓ := q − 1. Let A_{1}, …, A_{s} ⊂ {ā_{i} : p + 1 ≤ i ≤ r} be disjoint ℓ-sets for s = ⌊(r − p)/ℓ⌋. There is a positive rational ν such that with S(A_{i}) := {x : φ(x, ā_{1}) ∧ … ∧ φ(x, ā_{p}) ∧ ⋀_{ȳ∈A_{i}} ¬φ(x, ȳ)}, we have

||S(A_{i})| − ν|M|| ≤ c|M|^{\frac{1}{2}} .

By the assumption that the claim is not true for (p, q + 1) and the fact that C is a 1-dimensional asymptotic class, there is a constant c′ such that |S(A_{i})∩S(A_{j})| ≤ c′ for all i ≠ j. This is clearly impossible for large enough r: consider | ⋃(S(A_{i}) : p + 1 ≤ i ≤ r)|. Hence the assertion holds for (1, q + 1).

A similar argument shows that if the result holds for (p, q) for p < q ≤ K then it holds for (p + 1, q). Together, these assertions prove that φ is unstable in some infinite ultraproduct. □

Lemma 4.3. There is a 1-dimensional asymptotic class C such that every infinite ultraproduct is superstable of U-rank 1, but no infinite ultraproduct is ω-stable.

Proof. Let L be a language with a binary relation E_{n} for each n. For each k ∈ ω let M_{k} be the L-structure with domain of size 2^{k}, such that for each n ≤ k the relation E_{n} is interpreted as an equivalence relation on M_{k} with 2^{n}-classes, each of size 2^{k−n}, with E_{n+1} refining E_{n}. For n ≥ k, E_{n} is the equivalence relation with singleton clases. It is easily checked that any C is a 1-dimensional asymptotic class. If M is an infinite ultraproduct of members of C then M consists of a descending sequence indexed by ω of equivalence relations, each of index 2 in the previous one, so has U-rank 1 but is not ω-stable. □

We show next that in a 1-dimensional asymptotic class, algebraic closure satisfies a version of the exchange property. It is immediate that the exchange property holds in any infinite ultraproduct of such a class, since the ultraproduct is supersimple of rank 1. This could also be deduced from the proposition below.

Suppose that C is a 1-dimensional asymptotic class, M ∈ C and φ(x, ȳ) is a formula with associated data C, E, and formulas φ_{μ}(ȳ), for μ ∈ E, as in Definition 1.2. We further suppose that C is chosen sufficiently large that these data hold for any formula obtained from φ(x, ȳ) by permuting the variables—that is, if the first argument, the variable x is replaced by some variable y_{i}—and that E is chosen as small as possible, so it only includes measures that actually occur for φ.

We now say that a ∈ M is in the φ-closure of D ⊂ M, written a ∈ cl_{φ}(D), if there is some d̄∈ D such that M ⊧ φ(a, d̄) and φ_{μ}(d̄) does not hold for any μ ∈ E. Observe that this second condition guarantees that |φ(M, d̄)| ≤ C. For a set of formulas Σ, we say that a ∈ cl_{Σ}(D) if a ∈ cl_{φ}(D) for some φ(x, ȳ) ∈ Σ.

For a formula φ(x, y_{1}, …, y_{m}) with data as above, let Γ(φ) be the set of all formulas ψ(y_{i}, x, y_{1}, …, y_{i−1}, y_{i+1}, …, y_{m}) which express, for some i = 1, …, m and t ≤ C, that φ(x, ȳ) ∧ |φ(M, ȳ)| = t . Also, let Δ(φ) be the set of formulas consisting of:

i. all formulas ψ(x, y_{1}, …, y_{i−1}, y_{i+1}, …, y_{m}) of the form

∃y_{i} (φ(x, ȳ) ∧ |φ(M, ȳ)| = t) ,

where 1 ≤ i ≤ m and t ≤ C; ii. all formulas ψ(x, y_{1}, …, y_{i−1}, y_{i+1}, …, y_{m}) expressing

(∃^{>t′}y_{i}) (φ(x, ȳ) ∧ |φ(M, ȳ)| = t) ,

where 1 ≤ i ≤ m, t ≤ C and t′ is chosen sufficiently large that ∃^{>t′} and ∃^{∞} agree for the formula in any infinite ultraproduct of members of C.

The subject of the next proposition is a version of the exchange property for 1dimensional asymptotic classes. The slight imprecision in the statement—the term ‘large enough’—could be avoided by introducing additional notation that we wish to avoid. Also, for a formula φ(x̄, ȳ), a 1-dimensional asymptotic class C, a structure M ∈ C and ā ∈ M^{m}, we sometimes say that φ(M^{n}, ā) is small meaning that it has size at most C, where C is the associated constant of Theorem 2.1.

Proposition 4.4. Suppose that C is a 1-dimensional asymptotic class, M ∈ C, and D ⊂ M. Suppose also a, b ∈ M, and that a ∈ cl_{φ}(Db) \ cl_{Δ(φ)}(D). Then, assuming that M is large enough relative to D and φ, we have b ∈ cl_{Γ(φ)}(Da).

Proof. We may suppose that d̄ is a sequence from D, and that φ(a, d̄, b) holds and |φ(M, d̄, b)| = t, with t ≤ C. Let

S := {(x, y) : φ(x, d̄, y) ∧ |φ(M, d̄, y)| = t}.

If {y : |φ(M, d̄, y)| = t} is small, then S is small and hence a ∈ cl_{Δ(φ)}(D), via a formula of type (i), a contradiction. Thus, there is some μ ∈ ℝ for which S has size approximately μ|M|. Suppose first that the fiber S_{a} ⊂ M of S is large. It follows that the number of x such that S_{x} is large must be small. In particular, a ∈ cl_{ψ}(D) for some formula ψ ∈ Δ(φ) of type (ii) above, again a contradiction. Thus the fiber S_{a} is small, from which it follows that b ∈ cl_{Γ(φ)}(Da), as required. □

It is immediate that the quantifier ‘there exist infinitely many’ is eliminable in any ultraproduct of a 1-dimensional asymptotic class. It follows from this and the result above that algebraic closure defines a pregeometry in any such ultraproduct. We show next that if the pregeometry is trivial—that is, acl(A) = ∪{acl(a) : a ∈ A}—this can be recognized by asymptotic information on the finite structures.

Proposition 4.5. Let C be a 1-dimensional asymptotic class. Then the following are equivalent:

i. for every formula φ(x, ȳ) there is a formula ψ(x, z̄) and some K ∈ ω such that if M ∈ C with |M| > K and A ⊂ M, then cl_{φ}(A) ⊂ ⋃_{a∈A} cl_{ψ}({a}); ii. in any infinite ultraproduct M of members of C, if A ⊂ M then acl(A) =

⋃_{a∈A}(acl({a}); iii. for every φ there is a natural number K_{φ} such that for all M ∈ C with

|M| > K_{φ}, if A ⊂ M then | cl_{φ}(A)| ≤ K_{φ}|A|.

Proof. (i) ⇒ (iii). This is immediate.

(iii) ⇒ (ii). Suppose that (ii) is false. We work in a suitably saturated elementary extension N of M. Then, after naming parameters in N if necessary, there are a_{1}, b_{1}, c_{11} ∈ N, none of them algebraic over any other, such that c_{11} ∈ acl(a_{1}, b_{1}) via φ. Now, successively choose b_{2}, …, b_{n} ∈ N realizing tp(b_{1}/a_{1}) with b_{i} ∉ acl(a_{1}, b_{1}, …, b_{i−1}} for each 1 < i ≤ n. For i > 1 let σ_{i} ∈ Aut(N) fix a_{1} and map b_{1} to b_{i}, and let c_{1i} := σ_{i}(c_{11}). Note that c_{1i} ∈ acl(a_{1}, b_{i}). For each i = 2, …, n choose τ_{i} ∈ Aut(N) fixing b_{1}, …, b_{n}, and such that a_{i} := τ_{i}(a_{1}) ∉ acl(b_{1}, …, b_{n}, a_{1}, …, a_{i−1}). That this is possible follows by induction from the exchange property, as for each i, we have a_{1} ∉ acl(b_{1}, …, b_{n}, a_{2}, …, a_{i−1}). Lastly, put c_{ij} := τ_{i}(c_{1j}). It is easy to check inductively that all the c_{ij} are distinct, and c_{ij} ∈ acl(a_{i}b_{j}). It follows that acl(a_{1}, …, a_{n}, b_{1}, …, b_{n}) ≥ n^{2} for each n, uniformly via the formula φ. This behavior is realized in M by ω-saturation, from which we see easily that (iii) fails.

(ii) ⇒ (i). Assume (ii) holds. By compactness and ω-saturation of M, for each formula φ(x, ȳ) there are finitely many formulas ψ_{1}(x, z), …, ψ_{r}(x, z) such that if ā ∈ M and φ(b, ā) witnesses that b ∈ acl(ā), then for some i and j the formula ψ_{i}(b, a_{j}) witnesses that b ∈ acl(a_{j}). It is now easy to construct from the ψ_{i} a formula ψ that satisfies (i). □

Note that the proof of (iii) ⇒ (ii) above shows that if the growth rate of ϕ-closure is faster than linear, then it has at least quadratic polynomial growth.

We close this section with a result about graphs of S_{1}-rank 1 that is probably well-known—it is an immediate consequence of the Independence Theorem. It indicates that if algebraic closure is assumed to be trivial, then 1-dimensional asymptotic classes of graphs are highly constrained. This is not to say that such a class is uninteresting—see Example 3.4.

Proposition 4.6. Let Γ = (V Γ, E) be a countably infinite graph of S_{1}-rank 1, such that

a. for all A ⊂ V Γ, acl(A) = A, and

b. there is a 0-definable finite equivalence relation ≡ on V Γ that has no 0-

definable proper refinement. Let C_{1}, …, C_{k} be the ≡-classes. Then

i. each C_{i} is an infinite complete graph, an infinite null graph, or a copy of

the random graph, and

ii. for any distinct i, j ∈ {1, …, k}, either every vertex in C_{i} is adjacent to every vertex in C_{j}, or every vertex in C_{i} is not adjacent to every vertex in C_{j}, or, once edges within C_{i} and within C_{j} are deleted, the graph induced on C_{i} ∪ C_{j} is the random bipartite graph.

Furthermore, for any choice of data in (i) and (ii), there is at most one countably infinite graph satisfying the assumptions and realising the data which also is universal subject to the data and homogeneous once C_{1}, …, C_{k} are named by predicates. In particular, there are at most 3^{k} × 3^{\binom{k}{2}} such graphs up to isomorphism.

We cannot say there is a graph satisfying the assumptions and a given set of data, since for some sets of data the equivalence relation might not be definable.

To illustrate, there is no example with k = 2 and with C_{1} and C_{2} each isomorphic to the random graph, and with both edges and non-edges between C_{1} and C_{2}; such a graph would be isomorphic to the random graph, and the partition would not be definable. Before proving the proposition, we note

Corollary 4.7. Let Γ be a countably infinite graph of S_{1}-rank 1 such that there is no proper 0-definable finite equivalence relation on the vertex set and such that for every set A of vertices, acl(A) = A. Then Γ is isomorphic to the countably infinite complete graph or null graph, or to the random graph.

Proof of Proposition 4.6. Expanding the language, we may suppose each of the ≡-classes C_{1}, …, C_{k} is named by a unary predicate; this does not affect the assumptions on S_{1}-rank, algebraic closure, or finite equivalence relations. For each set of data as described in (i) and (ii) above (with the predicates), there is a universal homogeneous structure satisfying the conditions, obtained by amalgamation.

We now consider a set S of partial data, by which we mean a specification for each C_{i} whether or not C_{i} has an edge, and whether or not it has a non-edge, and for each distinct i and j, whether or not there is an edge between C_{i} and C_{j}, and whether or not there is a non-edge. We show that any structure M_{S} = (V Γ, E, C_{1}, …, C_{k}) satisfying such data and our other assumptions—S_{1}-rank 1, trivial algebraic closure, no 0-definable finite equivalence relation properly refining ≡—is universal subject to the data, and homogeneous when the C_{i} are named by predicates.

For a function f : {1, …, r} → {1, …, k}, a sequence ε̄ ∈ {−1, 1}^{r}, and an ℓ ∈ {1, …, k}, let σ_{f,ε̄,ℓ} be the sentence

∀u_{1}, …, u_{r} (⋀_{i≠j} u_{i} ≠ u_{j} ∧ ⋀_{i=1}^{r} C_{f(i)}u_{i} → ∃x (C_{ℓ}x ∧ ⋀_{i=1}^{r} E^{ε_{i}}(x, u_{i}))) ,

where E^{1}(x, y) denotes E(x, y), and E^{−1}(x, y) denotes ¬E(x, y). We say that σ_{f,ε̄,ℓ} is consistent with S if, for each i ∈ {1, …, r}, the following hold:

1. if f(i) = ℓ and ε_{i} = 1 then S specifies that C_{ℓ} has edges, and if f(i) = ℓ and ε_{i} = −1 then S specifies that C_{ℓ} has non-edges;

2. if f(i) ≠ ℓ and ε_{f(i)} = 1 then S specifies that there are edges between C_{f(i)} and C_{ℓ}, and if f(i) ≠ ℓ and ε_{f(i)} = −1 then S specifies that there are non-edges between C_{f(i)} and C_{ℓ}.

To prove that M_{S} is universal and homogeneous with respect to a set S of partial data, it is enough to show that if σ_{f,ε̄,ℓ} is consistent with S, then M_{S} satisfies σ_{f,ε̄,ℓ}. This is done by induction on r, and it clearly holds for r = 1. Now let a_{1}, …, a_{r} be distinct elements of M_{S} such that C_{f(i)}(a_{i}) holds for each i. Put A := {a_{1}, …, a_{r−1}} and B := {a_{r}}. Then by the assumption that algebraic closure is trivial, A and B are independent over ∅ (in the sense of non-forking in simple theories). Let φ(x) be the formula with parameters from A asserting that C_{ℓ}(x) ∧ ⋀_{i=1}^{r−1} E^{ε_{i}}(x, a_{i})), and let ψ(x) be the formula C_{ℓ}(x) ∧ E^{ε_{r}}(x, a_{r}). By induction hypothesis, φ is consistent and non-algebraic, and by the r = 1 case the same holds for ψ. Let a realize φ, and b realize ψ. Since a and b are in the same class C_{ℓ}, they realize the same strong type over ∅, so by Theorem 3.1 of [5], they realize the same Lascar strong type over ∅. Hence, by the Independence Theorem for Lascar strong types (Theorem 5.8 of [25]), there is an element c ∉ acl(A ∪ B) such that tp(c/A) = tp(a/A) and tp(c/B) = tp(b/B). Then c is a witness for ∃x(C_{ℓ}x ∧ ⋀_{i=1}^{r} E^{ε_{i}}(x, a_{i})), as required. □

5. Measurable structures

This section has its source in [6], where it is observed that the dimension and measure on definable subsets of finite fields naturally induces a dimension and measure on the definable subsets of a pseudofinite field. In this section we introduce in Definition 5.1 the concept of a measurable structure, an infinite structure whose definable sets come equipped with a dimension and measure satisfying certain natural axioms that are of course satisfied by pseudofinite fields. We investigate how measurability relates to other familiar model theoretic properties and obtain some preliminary structural results on measurable groups and fields.

For a structure M we denote by Def(M) the union, over all positive integers n, of the collection of non-empty subsets of M^{n} that are definable with parameters.

Definition 5.1. The structure M is measurable if there is a function h : Def(M) → ℕ × ℝ^{>0} satisfying the following conditions (where we write h(X) := (dim(X), meas(X))):

i. If X ∈ Def(M) is finite (and non-empty) then h(X) = (0, |X|); ii. For all X ∈ Def(M), D(X) ≤ dim(X), where D(X) is the D-rank of X; iii. For every formula φ(x̄, ȳ) there is finite set D_{φ} ⊂ ℕ × ℝ^{>0} so that

a. for all ā ∈ M^{m}, h(φ(M^{n}, ā)) ∈ D_{φ}.

b. for all (d, μ) ∈ D_{φ}, the set {ȳ ∈ M^{m} : h(φ(M^{n}, ȳ)) = (d, μ)} is 0-

definable; iv. Let X, Y ∈ Def(M) and f : X → Y be a definable surjection. As guaranteed by (iii), there is a positive integer r and (d_{1}, μ_{1}), …, (d_{r}, μ_{r}) ∈ ℕ×ℝ^{>0} so that if Y_{i} := {ȳ ∈ Y : h(f^{−1}(ȳ)) = (d_{i}, μ_{i})}, then Y = Y_{1} ∪ ⋯ ∪ Y_{r} is a partition of Y into non-empty disjoint definable sets. Let h(Y_{i}) = (e_{i}, ν_{i}) for i = 1, …, r, and let c := max{d_{1} + e_{1}, …, d_{r} + e_{r}}, where we suppose that this maximum is attained by the values d_{1} + e_{1}, …, d_{s} + e_{s}. Then h(X) = (c, μ_{1}ν_{1} + ⋯ + μ_{s}ν_{s}).

If h(X) = (d, μ) as in the preceding definition, we call d the dimension of X, μ the measure of X, and h the measuring function. We often write h_{i}(X), where i = 1, 2, for the projection of h(X) to the i^{th} coordinate. A measure μ on M is said to be normalized if M itself has measure 1.

It is easily checked that if M is measurable and M ≡ N then N is measurable. That is, if M is measurable then so is Th(M). This justifies saying that a complete theory T is measurable if it has a measurable model, equivalently all its models are measurable. Note also that Condition (ii) implies that Th(M) is supersimple of finite rank if M is measurable.

Remark 5.2. Mark Ryten and independently Richard Elwes have shown that Condition (ii) is redundant. Indeed, Conditions (i), (iii) and (iv) imply that if {X_{i} : i ∈ ω} is a collection of definable subsets of dimension n of a definable set X, and X_{i_{1}} ∩ … ∩ X_{i_{k}} = ∅ for all i_{1} < … < i_{k} < ω, then dim(X) ≥ n + 1. Hence, if D(X) = D(X_{i}) + 1, then dim(X) > dim(X_{i}), which yields (ii). A proof by induction on k is included in [14], but it also follows, for example, from Lemma 2.8 of [21]. This yields in particular that supersimplicity follows from (i), (iii), (iv).

From now on we assume this, so when verifying measurability we do not separately verify (ii).

We note several basic facts about measurable structures.

Proposition 5.3. Let M be measurable with measuring function h. Then: 1. If f : X → Y is a definable bijection, then h(X) = h(Y).

2. If X_{1}, …, X_{r} ∈ Def(M) are disjoint and h(X_{i}) = (d, μ_{i}) for each i, then h(X_{1} ∪ … ∪ X_{r}) = (d, μ_{1} + … + μ_{r}). Likewise, if X_{1}, …, X_{r} are definable then dim(X_{1} ∪ … ∪ X_{r}) = max{dim(X_{1}), …, dim(X_{r})}.

3. For Y_{1}, …, Y_{r} ∈ Def(M), we have dim(Y_{1} × … × Y_{r}) = dim(Y_{1}) + … + dim(Y_{r}) and μ(Y_{1} × ⋯ × Y_{r}) = μ(Y_{1}) × ⋯ × μ(Y_{r}). In particular, if μ is a normalized measure on M then M^{n} has measure 1 for each n < ω.

4. Let A ⊂ M and X ⊂ M^{n} be A-definable with h(X) = (t, ν). There is an Aut(M/A)-invariant finitely additive probability measure ρ on the collection of definable subsets of Y ⊂ X given by ρ(Y) = 0 if dim(Y) < t and ρ(Y) = meas(Y)/ν if dim(Y) = t.

5. Suppose that h(M) = (e, ν). Then there is a normalized measuring function h′ for M obtained from h by putting h′(X) = (d, \frac{λ}{ν^{d/e}}) for each definable X ⊂ M with h(X) = (d, λ).

6 If M is measurable via a function h, then h is determined by its restriction to the definable subsets of M, that is, 1-variable sets.

Proof. Statements (1)– (4) easily follow from conditions (i) and (iv). For (5), we first note that if we put h′(X) = (d, \frac{λ}{ν^{d/e}}) for each definable X ⊂ M^{n} with h(X) = (d, λ) and all n < ω, then it is a simple matter to check that we do obtain a normalized measure as required. The proof of (6) is inductive – for definable X ⊂ M^{n}, consider the projection to the first coordinate, and apply induction to the fibers. □

Ultraproducts of asymptotic classes are easily seen to be measurable.

Lemma 5.4. Let C be a 1-dimensional asymptotic class, and M an infinite ultraproduct of members of C. Then M is measurable of dimension 1.

Proof. For each formula φ(x̄, ȳ) and possible pair (d, μ) arising from Proposition 2.1, there is a corresponding formula φ_{d,μ}(ȳ). We use this formula to assign a dimension and measure to each set φ(M^{n}, ā) in the ultraproduct M. The axioms for measurability hold since the (counting) analogues of them hold in the members of C.

Remark 5.5. R. Elwes has developed a notion of N-dimensional asymptotic class (see [13]). He has shown that if C is an N-dimensional asymptotic class, then any ultraproduct is measurable of dimension N, under some measuring function. Suppose that L is a language with just a unary predicate P and C is a class of finite L-structures M for which |P (M)| = \sqrt{|M|}). Then under Elwes’ definition, C is a 2-dimensional asymptotic class, and so an ultraproduct M̂ of C has a measuring function satisfying dim(M̂) = 2. Note that M̂ is just a set with an infinite, coinfinite subset named by P, so naturally has D-rank 1. Moreover, it is evident that M̂ can be obtained as the ultraproduct of a 1-dimensional asymptotic class. The slightly curious clause (ii) in Definition 5.1—in which it is not required that dim(X) = D(X)—ensures that the proof of Lemma 5.4 remains valid.

We now investigate measurability for strongly minimal structures. Observe first that if (F, +, .) is an algebraically closed field, then F is not measurable. For example, in characteristic 0, the map f : F \ {0} → F \ {0} given by f(x) = x^{2} is surjective with all fibers of size two, which clearly contradicts condition (iv) in Definition 5.1. This is not accidental.

Recall that a strongly minimal structure M is unimodular [20] if, whenever U and V are definable sets of tuples from M and f_{i} : U → V, for i = 1, 2, are definable maps such that f_{i}^{−1}(a) contains a finite number k_{i} of elements for all a ∈ V, then k_{1} = k_{2}. It is immediate that every measurable strongly minimal set is unimodular. Thus, by the main theorem of [20], we obtain

Proposition 5.6. If M is measurable and strongly minimal then M is locally modular.

The converse is certainly false. Hrushovski provides examples of both a disintegrated strongly minimal set (a unary function with fibres of size 2) and a locally modular non-disintegrated strongly minimal set that are not unimodular, hence not measurable.

We now develop a criterion for measurability in the spirit of Definition 1.2 and Lemma 2.1 for 1-dimensional asymptotic classes. There is no crude criterion based on clauses (i)–(iii) of Definition 5.1 restricted to definable sets in one variable. Indeed, as noted above, the field of complex numbers is not measurable, but a one-variable version of measure is provided by cardinality. In the criterion below for measurability, we only assume a very special version of Definition 5.1 (iv), and clause (i) below is required only for a single variable x.

Proposition 5.7. Let M be a structure and h : Def(M) → ℕ × ℝ^{>0} be a function satisfying the following conditions (with the same notation as Definition 5.1, and with h(X) = (h_{1}(X), h_{2}(X))):

i. For each formula φ(x, ȳ) there are (n_{1}, μ_{1}), …, (n_{t}, μ_{t}) ∈ ℕ×ℝ^{>0} such that for each ā ∈ M^{m}, if φ(M, ā) ≠ ∅ then h(φ(M, ā)) ∈ {(n_{1}, μ_{1}), …, (n_{t}, μ_{t})}, and for each i = 1, …, t, the set {ȳ : h(φ(M, ȳ)) = (n_{i}, μ_{i})} is 0-definable in M.

ii. For each n ∈ ω and ā ∈ M^{n} we have h({ā}) = (0, 1).

iii. For all n ∈ ω and disjoint definable subsets X, Y ⊂ M^{n}, we have h_{2}(X ∪ Y) = h_{2}(X) + h_{2}(Y) if h_{1}(X) = h_{1}(Y) and h_{2}(X ∪ Y) = h_{2}(X) if h_{1}(Y) < h_{1}(X).

iv. For each n ∈ ω and i ∈ {1, …, n}, the following hold. Let X ⊂ M^{n} be definable, and let π : M^{n} → M be projection to the i^{th} coordinate. Suppose there is (d, μ) that for all a ∈ π(X), we have h(π^{−1}(a) ∩ X) = (d, μ). Then h_{1}(X) = h_{1}(π(X)) + d and h_{2}(X) = h_{2}(π(X)) × μ.

Then M is measurable, via the function h.

Proof. We first prove that clause (iv) of Definition 5.1 holds. For this we establish:

Claim. Let r < n be positive integers, S ⊂ M^{n} be definable over D ⊂ M, and π : M^{n} → M^{r} be a projection onto some set r of the coordinates of M^{n}. Suppose also that π(S) = Y_{1} ∪…∪Y_{k} is a partition into D-definable sets such that for each i and all y ∈ Y_{i}, the function h_{1} assumes the constant value d_{i} and h_{2} takes the constant value μ_{i} on the fibers π^{−1}(y). Let h(Y_{i}) = (e_{i}, ν_{i}) for each i ≤ k. If the maximum value of d_{i} + e_{i} is assumed for i = 1, …, t, then h(S) = (d_{1} + e_{1}, μ_{1}ν_{1} + … + μ_{t}ν_{t}).

Clause (iv) of Definition 5.1 follows almost immediately from the Claim. Given a definable function f : X → Y with X ⊂ M^{p} and Y ⊂ M^{q}, we apply the claim to R := {(x̄, f(x̄)) : x̄ ∈ X}, the graph of f, with π the projection onto the last q coordinates. Observe that if we apply the claim to the projection to the first s coordinates, dim(X) = dim(R). So we proceed to: Proof of the Claim. We focus on h_{2}; the argument for h_{1} is similar.

We first show, by (downward) induction on r < n, that for all D-definable S ⊂ M^{n} and projections π : M^{n} → M^{r} onto some set r of the coordinates of M^{n}, there are K < ω and finitely many pairs (d_{ℓ}, μ_{ℓ}) for ℓ ≤ K such that

a. for all b̄ ∈ M^{r} there is some ℓ ≤ K for which h(S ∩ π^{−1}(b̄)) = (d_{ℓ}, μ_{ℓ});

b. {b̄ ∈ M^{r} : h(S ∩ π^{−1}(b̄)) = (d_{ℓ}, μ_{ℓ})} is uniformly definable over D.

For r = n − 1, these assertions follow from the hypotheses (i) and (iv). For the induction step, we assume, for ease of notation, that the projection is onto the last r coordinates.

Let π′: M^{n} → M^{r+1} be projection onto the last r + 1 coordinates. By induction hypothesis, there are N < ω and pairs (e_{s}, ν_{s}) for s ≤ N such that for each (a, b̄) ∈ π′(S) there is some s ≤ N for which h(S ∩ π′^{−1}(a, b̄)) = (e_{s}, ν_{s}). For each s and b̄ ∈ π(S), let

T_{s}(b̄) := {a ∈ M : h(S ∩ π′^{−1}(a, b̄)) = (e_{s}, ν_{s})}.

Clearly, by the induction hypothesis, each set {(x, ȳ) : x ∈ T_{s}(ȳ)} is D-definable. It follows by hypothesis (i) that there are L = L(s) < ω and pairs (f_{ℓ}, ρ_{ℓ}) for ℓ ≤ L such that for all b̄ ∈ π(S) there is a value ℓ ≤ L for which h(T_{s}(b̄)) = (f_{ℓ}, ρ_{ℓ}) and moreover that for each ℓ ≤ L the set of all b̄ ∈ π(S) for which h(T_{s}(b̄)) = (f_{ℓ}, ρ_{ℓ}) is D-definable. Finally, for every s ≤ N and ℓ ≤ L, and every b̄ ∈ π(S), we complete the induction step by applying hypothesis (iv) to

{(c̄, a) ∈ M^{n−r} : (c̄, a, b̄) ∈ S ∧ h(S ∩ π′^{−1}(a, b̄)) = (e_{s}, ν_{s}) ∧ h(T_{s}(b̄)) = (f_{ℓ}, ρ_{ℓ})}.

The definability condition (b) follows easily from the above; the last details are left to the reader.

Now we turn to the claim proper. It is proved by induction on r. For r = 1, the claim follows from hypotheses (iii) and (iv). Turning to the induction step, it follows easily from the hypothesis (iii) that we may assume k = 1, and hence that h is constant on fibers of π. Let π_{1} : M^{r} → M denote projection onto the first coordinate, and π_{2} := π_{1} ∘ π. Statements (a) and (b) above allow us to suppose further that h is constant also on fibers of π_{2}. Choose b̄ ∈ π(S), and put b̄ = (a, b̄′) so a = π_{1}(b̄). Also put R := π(S).

By our assumption (iv),

(1)  h_{2}(S) = h_{2}(π_{2}(S)) × h_{2}(π_{2}^{−1}(a) ∩ S),

and by (iv) applied to R, we have

(2)  h_{2}(R) = h_{2}(π_{1}(R)) × h_{2}(R ∩ π_{1}^{−1}(a)).

Let S′ := π_{2}^{−1}(a) ∩ S and π_{r−1} : M^{r} → M^{r−1} denote projection onto the last r − 1 coordinates, and define π′ : M^{n} → M^{r−1} by π′ := π_{r−1} ∘ π. By (a), (b), and hypothesis (iii), we may assume further that h is constant on fibers of π′, and hence by induction hypothesis,

(3)  h_{2}(S′) = h_{2}(π′(S′)) × h_{2}(π′^{−1}(b̄′) ∩ S′).

Furthermore,

(4)  h_{2}(π′(S′)) = h_{2}(π_{1}^{−1}(a) ∩ R),

by induction applied to π_{r−1} ↾_{π(S′)} and hypothesis (ii).

Finally,

h_{2}(S) = h_{2}(π_{2}(S)) × h_{2}(S′)  (by (1) and the definition of R)
= h_{2}(π_{1}π(S)) × h_{2}(S′)
= h_{2}(π_{1}(R)) × h_{2}(S′)
= h_{2}(π_{1}(R)) × h_{2}(π′(S′)) × h_{2}(π′^{−1}(b̄′) ∩ S′)  (by (3))
= h_{2}(π_{1}(R)) × h_{2}(π_{1}^{−1}(a) ∩ R) × h_{2}(π′^{−1}(b̄′) ∩ S′)  (by (4))
= h_{2}(R) × h_{2}(π′^{−1}(b̄′) ∩ S′)  (by (2))
= h_{2}(R) × h_{2}(π^{−1}(b̄) ∩ S)  (as π′^{−1}(b̄′) ∩ π_{2}^{−1}(a) = π^{−1}(b)).

This yields the claim.

To complete the proof of the proposition, note that clause (i) of Definition 5.1 trivially follows from conditions (ii) and (iii) of the Proposition, and clause (iii) of the definition follows from (a) and (b) above. □

Proposition 5.8. Suppose M is strongly minimal, and that Th(M) has the definable multiplicity property and definable Skolem functions. Then Th(M) is measurable, and there is a measuring function h such that for all n and all definable subsets X ⊂ M^{n}, the function h_{1}(X) is the Morley rank of X and h_{2}(X) is the Morley degree of X.

In particular, by Proposition 5.6, such M must be locally modular.

Proof. We first verify that Morley rank and degree together satisfy clause (iv) in Definition 5.1. To this end, suppose that f : X → Y is a definable surjection between definable sets. We assume for all y ∈ Y that X_{y} := f^{−1}(y) has Morley degree d, and prove that X has Morley degree de, where e is the Morley degree of Y. The proof is by induction on d, over all f, X, and Y.

If d = 1 the conclusion is easily verified. So we suppose that d > 1. We assume that f, X, Y are definable over a set A. By the finite equivalence relation, for each y there is an Ay-definable equivalence relation E_{y} on X_{y} whose classes have the same rank as X_{y} and Morley degree 1. By compactness, we may suppose that E_{y} is uniformly definable in y. The existence of definable Skolem functions implies that there is an A-definable function g : Y → X with g(y) ∈ X_{y} for each y ∈ Y. Let

X′ := ⋃_{y∈Y} {x ∈ X : xE_{y}g(y)}.

By the d = 1 case, X′ has Morley degree e. Furthermore, by induction, X \ X′ has Morley degree (d − 1)e. Hence, X has Morley degree (d − 1)e + e = de, as required.

Finally, Morley rank is definable in all strongly minimal structures, and by assumption, Morley degree is definable. Thus, Definition 5.1 (iii) holds, and the result follows. □

Corollary 5.9. Let V be a vector space over a field F, regarded as a structure in the language of modules over F. Then V is measurable.

Proof. If F is a finite field, the conclusion is a consequence of Theorem 3.8 and Lemma 5.4. Now suppose that F is infinite. Then V is strongly minimal. In this case, Th(V) has quantifier elimination in the language specified above, and every non-trivial substructure of V —i.e., subspace of dimension greater than 0—is easily seen to be elementarily equivalent to V. It follows by Theorem 2.1 of [12] that if v_{0} ∈ V \ {0}, then Th(V, v_{0}) has definable Skolem functions. Proposition 5.8 hence implies that (V, v_{0}) is measurable. Since Morley degree is definable in vector spaces, it follows that V is measurable. □

We shall say that a many-sorted structure M is measurable if the restriction of M to any finite sub-collection of sorts is measurable in the sense of Definition 5.1.

Proposition 5.10. Let M be measurable. Then every structure obtained from M by the addition of any collection of sorts from M^{eq}, with all the induced structure, also is measurable.

Proof. It suffices to show that if M is measurable, n is a positive integer, and E is a 0-definable equivalence relation on M^{n}, then the structure M^{∗} is measurable, where M^{∗} is obtained by adjoining the single new sort M^{n}/E to M together with all the induced structure from M, a unary predicate P for M^{n}/E, and the natural map ρ: M^{n} → M^{n}/E.

To this end, let h be a measuring function on M. We must extend h to a measuring function h′ on M ∪ M^{n}/E. Let R ⊂ M^{k} × P^{ℓ} be a definable set and let

R^{∗} := {(x̄, ȳ_{1}, …, ȳ_{ℓ}) ∈ M^{k} × M^{nℓ} : (x̄, ȳ_{1}/E, …, ȳ_{ℓ}/E) ∈ R}.

Also, let f : M^{k+nℓ} → M^{k}×P^{ℓ} be the map (x̄, ȳ_{1}, …, ȳ_{ℓ}) ↦ (x̄, ȳ_{1}/E, …, ȳ_{ℓ}/E). As M is measurable, there is a partition R = R_{1} ∪ … ∪ R_{t} into M^{∗}-definable sets and pairs (d_{1}, μ_{1}), …, (d_{t}, μ_{t}) ∈ ℕ × ℝ^{>0} such that h(f^{−1}(ū)) = (d_{i}, μ_{i}) for each i ∈ {1, … t} and ū ∈ R_{i}. Let R_{i}^{∗} := f^{−1}(R_{i}) and note that each R_{i}^{∗} is definable in M. For each i ≤ t let h(R_{i}^{∗}) = (e_{i}, ν_{i}). We then define h′(R_{i}) = (e_{i} − d_{i}, ν_{i}/μ_{i}). It can be checked by Proposition 5.7 that h′ is a measuring function on M ∪ P. □

The next theorem shows, at least under the assumption acl = dcl, that the adjunction of a generic predicate as in [7] preserves measurability. We believe that the assumption acl = dcl is unnecessary, but the arguments become rather more intricate than those we present below. Hrushovski [23, Proposition 11.1], has proved an analogous result about the fixed point set of a generic automorphism of a strongly minimal set with the definable multiplicity property.

Theorem 5.11. Let T be a complete measurable theory over a language L with quantifier elimination, eliminating the quantifier ∃^{∞}, such that for all M ⊧ T and A ⊂ M, acl(A) = dcl(A). Let P be a unary predicate not in L, let L′ := L∪{P }, let S be a sort of T, and let T_{P,S} be the model companion of the theory of L′-structures satisfying T, with P interpreted by a subset of S. Let T′ be any completion of T_{P,S}. Then T′ is measurable.

Proof. It is convenient to suppose that L has an additional constant symbol ∞, and has been expanded slightly to ensure that all definable partial functions are given by terms, with introduced functions taking value ∞ if necessary.

Recall [7, 2.4] that the model companion T_{P,S} exists and is axiomatized by T together with sentences of the following form, where φ(x̄, z̄) is an L-formula, x̄ = (x_{1}, …, x_{m}), and I is any subset of {1, …, m}:

∀z̄([∃x̄φ(x̄, z̄) ∧ (x̄ ∩ acl_{T} (z̄) = ∅) ∧ ⋀_{i=1}^{m} S(x_{i})]

⟶ [∃x̄φ(x̄, z̄) ∧ ⋀_{i∈I}(x_{i} ∈ P) ∧ ⋀_{i∉I}(x_{i} ∉ P)]) .

Let M ⊧ T′, with reduct M_{L} to L. Since measurability is preserved under elementary equivalence, we assume that M is (sufficiently) saturated. By assumption, there are measure and dimension functions dim_{T} and μ_{T} on the collection of definable subsets of powers of the reduct M_{L}. We will define dimension and measure functions, dim and μ, for the collection of definable subsets of powers of M, prove this assignment is well-defined, and finally show they satisfy the hypotheses in Proposition 5.7.

Let p be a real number with 0 < p < 1. We shall assign a measure to M so that

μ ({x ∈ S : P (x)}) = pμ_{T} (S).

Let x̄ = (x_{1}, …, x_{m}), ȳ = (y_{1}, …, y_{n}), and z̄ = (z_{1}, …, z_{k}). By [7, Corollary 2.6], every L′-formula in the variables x̄ and ȳ—the variables ȳ are taken to be parameter variables—is equivalent modulo T′ to a finite disjunction of formulas φ(x̄, ȳ) of the form

(5)  ∃z̄ (ψ(x̄, ȳ, z̄) ∧ ⋀_{i=1}^{ℓ} P (t_{i}(x̄, ȳ, z̄)) ∧ ⋀_{i=1}^{ℓ′} ¬P (t′_{i}(x̄, ȳ, z̄))) ,

where ψ is a quantifier-free L-formula, t_{1}, …, t_{ℓ} and t′_{1}, …, t′_{ℓ′} all are L-terms, and c̄ ∈ acl_{T} (ā, b̄) for every (ā, b̄, c̄) satisfying ψ. The assumptions that acl = dcl in models of T, and that definable partial functions are given by terms, enable us to eliminate the existential quantifier in the cited result. Thus we assume further that every L′-formula is equivalent modulo T′ to a finite disjunction of formulas φ(x̄, ȳ) of the form

(6)  ψ(x̄, ȳ) ∧ ⋀_{i=1}^{ℓ} P (t_{i}(x̄, ȳ)) ∧ ⋀_{i=1}^{ℓ′} ¬P (t′_{i}(x̄, ȳ)),

where ψ is an L-formula, and t_{1}, … t_{ℓ}, t′_{1}, … t′_{ℓ′} all are L-terms.

For every L-formula ψ(x̄, ȳ) and term t(x̄, ȳ), and b̄ ∈ M^{n}, there are just finitely many c ∈ M such that dim_{T} (t^{−1}(c) ∩ ψ(M^{m}, b̄)) = dim_{T} (ψ(M^{m}, b̄). Hence all such c lie in dcl(b̄).

We shall call the formula φ(x̄, ȳ) as in (6) good if:

(i) ψ(x̄, ȳ) implies that t_{1}(x̄, ȳ), …, t_{ℓ}(x̄, ȳ), t′_{1}(x̄, ȳ), …, t′_{ℓ′}(x̄, ȳ) are all distinct, and that the terms t_{i}, t′_{i} only assume values in S;

(ii) for each b̄ ∈ M^{n} and each i, the t_{i}-fibers on φ(M^{m}, b̄) – that is, sets t_{i}^{−1}(c) ∩ φ(M^{m}, b̄) – have constant dimension of value less than dim(φ(M^{m}, b̄)), and likewise for t′_{i}.

For a good formula φ(x̄, ȳ) and b̄ ∈ M^{n}, we assign to the definable set φ(M^{m}, b̄) the measure μp^{ℓ}(1 − p)^{ℓ′}, where μ := μ_{T} (ψ(M^{m}, b̄)). Its dimension is defined to be dim_{T} (ψ(M^{m}, b̄)).

Every formula of the form (5) thus is easily seen to be equivalent to a finite disjunction of pairwise inconsistent formulas, each of which has the form

(7)  χ(x̄, ȳ) ∧ ⋀_{i=1}^{k} P (u_{i}(ȳ)) ∧ ⋀_{i=1}^{k′} ¬P (u′_{i}(ȳ)),

where χ is good. The u_{i} arise from the t_{i} in (6) which depend just on ȳ. For b̄ ∈ M^{n}, the measure and dimension of each such disjunct is defined to be either the same as for μ(χ(M^{m}, b̄)), or measure 0 and dimension 0, according to whether or not ⋀_{i=1}^{k} P (u_{i}(b̄)) ∧ ⋀_{i=1}^{k′} ¬P (u′_{i}(b̄)) holds. Thus, in considerations of measure we can essentially just work with disjunctions of good formulas (a slight but harmless oversimplification). This definition of dimension and measure is extended by specifying that the measure of a finite disjoint union of definable sets of the same dimension is the sum of their measures, and the dimension is the maximum of their dimensions.

We must show this assignment of measure and dimension is well-defined. We focus only on measure. To this end, suppose that the set X has two definitions X = X_{1} ∪ … ∪ X_{r} = Y_{1} ∪ … ∪ Y_{s} as disjoint unions of sets defined by formulas of the form (7). Since we may replace the each of the sets Y_{j} by the union of the sets X_{i} ∩ Y_{j} for i = 1, …, r, we may suppose that each of the X_{i} is the union of some of the Y_{j}, and thereby reduce to the case that r = 1, that is X = Y_{1} ∪ … ∪ Y_{s}. Thus, we may assume that X is defined by the good formula

ψ(x̄, b̄) ∧ ⋀_{i=1}^{ℓ} P (t_{i}(x̄, b̄)) ∧ ⋀_{i=1}^{ℓ′} ¬P (t′_{i}(x̄, b̄)),

and that Y_{i}, for i = 1, … s, is defined by the good formula

χ_{i}(x̄, c̄_{i}) ∧ ⋀_{j=1}^{k_{i}} P (u_{ij}(x̄, c̄_{i})) ∧ ⋀_{j=1}^{k′_{i}} ¬P (u′_{ij}(x̄, c̄_{i})).

We now assert that ψ(M^{m}, b̄) = ⋃_{i=1}^{s} χ_{i}(M^{m}, b̄_{i}). Indeed, the equality X = Y_{1} ∪ … ∪ Y_{s}, the axioms for T_{P,S}, and the definition of ‘good formula’, imply via compactness that these two sets can differ at most by a lower dimensional set, and we can modify the formulas to erase this difference. By a further decomposition, we may suppose that all the sets χ_{i}(M^{m}, b̄_{i}) are equal. Let Z = ψ(M^{m}, b̄), and so Z equals each χ_{i}(M^{m}, b̄_{i})).

Let i ∈ {1, …, s}. Arguing as in the last paragraph (again using the axioms of T_{P,S}), for each x̄ ∈ Z, we see that t_{j}(x̄, b̄) ∈ {u_{i1}(x̄, c̄_{i}), …, u_{i,k_{i}}(x̄, c̄_{i})} for j = 1, …, ℓ, and t′_{j}(x̄, b̄) ∈ {u′_{i1}(x̄, c̄_{i}), …, u′_{i,k′_{i}}(x̄, c̄_{i})} for j = 1, …, ℓ′; otherwise, Y_{i} ⊈ X. Thus, we may suppose additionally that for each x̄ ∈ Z and i = 1, …, s, we have t_{j}(x̄, b̄) = u_{ij}(x̄, c̄_{i}) for j = 1, …, ℓ, and t′_{j}(x̄, b̄) = u′_{ij}(x̄, c̄_{i}) for j = 1, …, ℓ′. (Some additional decomposition of X and the Y_{i} may be necessary here; it might happen, say, that for some x̄, t_{1}(x̄) = u_{i1}(x̄), and for other x̄, t_{1}(x̄) = u_{i2}(x̄).)

Hence, if we set

Y′_{i} := χ_{i}(x̄, c̄_{i}) ∧ ⋀_{j=1}^{ℓ} P (u_{ij}(x̄, c̄_{i})) ∧ ⋀_{j=1}^{ℓ′} ¬P (u′_{ij}(x̄, c̄_{i})),

then X = Y′_{1} = ⋯ = Y′_{s}, and Y′_{i} ⊇ Y_{i} for each i.

Let w_{1}(x̄), …, w_{N}(x̄) list the terms in {u_{i,ℓ+1}(x̄, c̄_{i}), …, u_{i,k_{i}}(x̄, c̄_{i}) : i = 1, …, s}, where we suppress the parameters for notational convenience. Since X does not properly contain Y_{1} ∪…∪Y_{s}, as we have argued above, genericity of P implies that s = 2^{N}, each i = 1, …, s is identified with a different function σ_{i}: {1, …, N} → {−1, +1}, and

Y_{i} := {x̄ ∈ X : ⋀_{{j:σ_{i}(j)=1}} P (w_{j}(x̄)) ∧ ⋀_{{j:σ_{i}(j)=−1}} ¬P (w_{j}(x̄))} .

If μ_{T} (ψ(M^{m}, b̄)) = ν, then by definition, μ(X) = νp^{ℓ}(1 − p)^{ℓ′}. Finally, calculating the measure of X via the decomposition given by the Y_{i}’s, we see that

μ(X) = μp^{ℓ}(1 − p)^{ℓ′} ∑_{j=1}^{N} \binom{N}{j}p^{j}(1 − p)^{N−j} = νp^{ℓ}(1 − p)^{ℓ′},

since ∑_{j=1}^{N} \binom{N}{j}p^{j}(1 − p)^{N−j} = 1.

Note that definability of dimension and measure for L′-formulas is easily seen to follow from how we assign dimension and measure to these formulas above, using that definability holds for T. We omit the details.

It remains to verify that this assignment of dimension and measure for T′ satisfies the conditions in Proposition 5.7. We shall focus on Condition (iv). Let π : M^{m} → M denote projection onto the first coordinate, and let R ⊂ M^{m} be definable. We may suppose R is defined by the good formula

ψ(x̄, b̄) ∧ ⋀_{i=1}^{ℓ} P (t_{i}(x̄, b̄)) ∧ ⋀_{i=1}^{ℓ′} ¬P (t′_{i}(x̄, b̄)),

and we now drop reference to the parameter b̄. Let R′ := ψ(M^{m}). Also, set S := π(R) and S′ := π(R′). For a ∈ S, let R_{a} := π^{−1}(a) ∩ R and R′_{a} := π^{−1}(a) ∩ R′ denote the fibers over a in R and R′, respectively. Definability of dimension and measure allows us to suppose, by refinement if necessary, that all the sets R_{a} for a ∈ S have the same dimension and measure, and likewise for the sets R′_{a} for a ∈ S′; likewise we may assume that the t_{i}|_{R_{a}} and t′_{i}|_{R_{a}} have fibers of constant dimension, and that this does not vary with a.

By quantifier elimination for T_{P,S}, we see that S can be defined by a formula χ(x_{1}) ∧ ⋀_{i=1}^{k} P (u_{i}(x_{1})) ∧ ⋀_{i=1}^{k′} ¬P (u′_{i}(x_{1})); infact, (it might be defined by a disjunction of such formulas, but we can handle each disjunct separately. We may assume, making further refinements if needed, that S′ := χ(M), that u_{1}, …, u_{k} occur among t_{1}, …, t_{ℓ}, and that u′_{1}, …, u′_{k} appear among t′_{1}, …, t′_{ℓ′}. For notational convenience, we assume that u_{i} = t_{i} for i = 1, …, k and u′_{i} = t′_{i} for i = 1, …, k′. It follows that for all a ∈ S, the fiber R_{a} can be defined by the good formula

(8)  ψ(x̄′) ∧ ⋀_{i=k+1}^{ℓ} P (t_{i}(x̄′)) ∧ ⋀_{i=k′+1}^{ℓ′} ¬P (t′_{i}(x̄′)),

where x̄′ := (a, x_{2}, …, x_{m}). Likewise, R′_{a} is defined by ψ(x̄′).

Since the reduct of M to L is measurable, dim_{T} (R′) = dim_{T} (R′_{a}) + dim_{T} (S′) for all a ∈ S′. As dim_{T} (R′) = dim(R), dim_{T} (S′) = dim(S), and dim_{T} (R′_{a}) = dim(R_{a}), we obtain dim(R) = dim(R_{a}) + dim(S), as required. Finally, let μ_{T} (R′) = ν. It follows that μ(R) = νp^{ℓ}(1−p)^{ℓ′}. Likewise, if μ_{T} (S′) = ρ. then μ(S) = ρp^{k}(1−p)^{k′}. By measurability of the L-reduct of M, for all a ∈ S′ the fiber R′_{a} has measure ν/ρ. From the good formula (8) which defines the fiber R_{a}, we see that μ(R_{a}) = (ν/ρ) p^{ℓ−k}(1 − p)^{ℓ′−k′}. It follows that μ(R) = μ(R_{a}) × μ(S), as required. □

We recall that a k-hypergraph is a structure (M, R) where R is a k-place relation on M, and

R(x_{1}, …, x_{k}) → ⋀_{i≠j} x_{i} ≠ x_{j} ∧ ⋀_{π∈S_{n}} R(x_{π(1)}, …, x_{π(k)}).

The (countable) universal homogeneous k-hypergraph can be regarded as the random k-hypergraph, based on edge probability p for any fixed p with 0 < p < 1. We now show that the universal homogeneous k-hypergraphs are all measurable of dimension 1 for all such p. We do now know if for k > 2 they are elementarily equivalent to ultraproducts of 1-dimensional asymptotic classes.

Proposition 5.12. Let (M, R) be the universal homogeneous k-hypergraph, and let p ∈ (0, 1). Then there is a measure on M such that M has dimension 1, and {(x_{1}, …, x_{k}) : R(x_{1}, …, x_{k})} has measure p.

Proof. By ω-categoricity and quantifier elimination, it suffices to specify the measure of complete types over finite sets, and show that this assignment satisfies Proposition 5.7.

Let ā = (a_{1}, …, a_{s}), and let q be a complete n-type over ā whose realizations are disjoint from ā. Let b̄ := (b_{1}, …, b_{n}) realize q. For each S ⊂ {1, …, s} with |S| ≤ k, let ā_{S} denotes the subtuple of ā with entries indexed by S and let α_{S} be the number of increasing subsequences i_{1} < … < i_{k−|S|} of (1, …, n) such that R(ā_{S}, b_{i_{1}}, …, b_{i_{k−|S|}}). Also, let β_{S} = \binom{n}{k−|S|} − α_{S}. For each m ≤ s let F_{m} denote the set of subsets of {1, …, s} of size at most m. The set of realizations of q has dimension n and measure

Π_{S∈F_{k−1}}p^{α_{S}}(1 − p)^{β_{S}}.

Such a measure extends naturally to a measure on all definable sets, and clearly the measure and dimension are definable.

We now verify that the set X of realizations of q satisfies the hypothesis (iv) of Proposition 5.7 with respect to projection π : M^{n} → M onto the first coordinate. Let α denote the number of increasing subtuples of āb_{1} with last entry b_{1} which satisfy the relation R, and let β := \binom{s}{k−1} − α. Then π(X) has measure p^{α}(1 − p)^{β}. We now calculate the measure of X′, the set of realizations of tp(b_{2} … b_{n}/āb_{1}). For each S ⊂ {1, …, s} of size at most k − 2, let α′_{S} be the number of subtuples b̄′ of b_{2} … b_{n} such that R(ā_{S}, b_{1}, b̄′) holds, and let α′′_{S} be the number of subtuples b̄′ of b_{2} … b_{n} such that R(ā_{S}, b̄′) holds. Clearly α′_{S} + α′′_{S} = α_{S}. For a (k − 1)-subset S of {1, …, n}, let α′′_{S} be the number of elements b′ from among b_{2}, …, b_{n} such that R(ā_{S}, b′). In all these cases put β′_{S} := \binom{n−1}{k−|S|−1}−α′_{S} and β′′_{S} := \binom{n−1}{k−|S|}−α′′_{S}. Then X′ has measure

Π_{S∈F_{k−2}}p^{α′_{S}}(1 − p)^{β′_{S}}p^{α′′_{S}}(1 − p)^{β′′_{S}}Π_{S⊂{1,...,s},|S|=k−1}p^{α′′_{S}}(1 − p)^{β′′_{S}}.

We must verify that meas(X′) × meas(π(X)) = meas(X), that is,

meas(X′) × p^{α}(1 − p)^{β} = Π_{S∈F_{k−1}}p^{α_{S}}(1 − p)^{β_{S}}.

Since α′_{S} + α′′_{S} = α_{S} and likewise β′_{S} + β′′_{S} = β_{S}, this reduces to showing that

Π_{S⊂{1,...,s},|S|=k−1}p^{α′′_{S}}(1 − p)^{β′′_{S}} × p^{α}(1 − p)^{β} = Π_{S⊂{1,...,s},|S|=k−1}p^{α_{S}}(1 − p)^{β_{S}}.

This follows directly from the definitions; on each side, the power of p is the number of subtuples of āb̄ with k − 1 elements from ā which satisfy R. □

Remark 5.13. 1. There is an alternative proof of Proposition 5.12. Start with a pure set M of size ℵ_{0}, and adjoin to M the sort consisting of ordered k-element subsets of M. The universal homogeneous k-hypergraph can be regarded as a generic predicate on S, so Theorem 5.11 can be applied.

2. M. Albert [1] considered finitely additive automorphism invariant probability measures on the definable subsets (in 1 variable) of the random graph. Such a measure is determined by its value on any complete 1-type. It was shown in [1] that any such measure on a complete 1-type p(x, ā) over ā depends only on the size of ā and the number of entries of ā which p asserts are adjacent to x. Since any measuring function on the random graph in our sense induces one in his sense, Albert’s result restricts possible measuring functions on the random graph.

Theorems 5.15 and 5.17 below the strength of the measurability assumption. Indeed, it is not known, just assuming supersimplicity, if every group of rank 1 is finite-by-abelian-by-finite, or if every group has an infinite abelian subgroup (c.f., Section 5.4 of [35]). First, we prove a lemma which may have further applications.

Lemma 5.14. Let G be a measurable group. Then some non-identity g ∈ G has infinite centralizer.

Proof. Suppose for a contradiction that each g ∈ G \ {1} has finite centralizer. For g ∈ G, let C_{g} be the conjugacy class of G, and let α_{g} : G → C_{g} be the definable surjection α_{g} : G → C_{g}, given by α_{g}(h) := h^{−1}gh. The fibres of α_{g} are all cosets of C_{G}(g), so have dimension 0 and measure |C_{G}(g)|. It follows by Definition 5.1 that dim(C_{g}) = dim(G) and meas(C_{g}) = 1/|C_{G}(g)|. As the conjugacy classes are uniformly definable, by dimension considerations there are finitely many of them, say C_{1}, …, C_{t}. Put μ_{i} := meas(C_{i}) for each i = 1 …, t.

Since centralizers have finite bounded size, the group G has finite exponent n. Let p_{1}, …, p_{r} be the primes dividing n.

Case 1. All the p_{i} are odd.

In this case, we define an equivalence relation ∼ on {C_{1}, …, C_{t}} by putting C_{i} ∼ C_{j} if there are g ∈ C_{i} and h ∈ C_{j} of the same order with h a power of g (i.e., they generate the same cyclic subgroup of G). Let C_{i_{1}}, …, C_{i_{s}} be a set of representatives of the ∼-classes, and for each j = 1, …, s let D_{j} be the union of the conjugacy classes ∼-equivalent to C_{i_{j}}. For j = 1, …, s and g_{j} ∈ C_{i_{j}}, let p_{1}^{a_{1,j}} ⋯ p_{r}^{a_{r,j}} be the order of g_{j}. By assumption each C_{G}(g_{j}) is finite, and we let p_{1}^{b_{1,j}} ⋯ p_{r}^{b_{r,j}} be its order. Finally, let p_{1}^{c_{1,j}} … p_{r}^{c_{r,j}} be the order of the group induced on ⟨g_{j}⟩ by its normalizer N_{G}(⟨g_{j}⟩) in G. Observe that the a_{i,j}, b_{i,j} and c_{i,j} do not depend on the choice of C_{i_{j}} in its ∼-class, or on g_{j} ∈ C_{i_{j}}. Also, all the a_{k,j}, b_{k,j}, and c_{k,j} are nonnegative.

If g and h generate the same cyclic group then they have the same centralizer. It follows that for each j = 1, …, s, all the conjugacy classes ∼-equivalent to C_{i_{j}} have measure 1/p_{1}^{b_{1,j}} … p_{r}^{b_{r,j}}. Furthermore, under the action of N_{G}(⟨g_{j}⟩) on ⟨g_{j}⟩, the generators of ⟨g_{j}⟩ fall into orbits of size p_{1}^{c_{1,j}} … p_{r}^{c_{r,j}}. As there are φ(p_{1}^{a_{1,j}} … p_{r}^{a_{r,j}}) many generators of ⟨g_{j}⟩, where φ denotes the Euler φ-function, the number of conjugacy classes ∼-equivalent to C_{i_{j}} is

\frac{φ(p_{1}^{a_{1,j}} … p_{r}^{a_{r,j}})}{p_{1}^{c_{1,j}} … p_{r}^{c_{r,j}}} .

Since each of these conjugacy classes has measure 1/p_{1}^{b_{1,j}} … p_{r}^{b_{r,j}}, the measure of D_{j} is

\frac{φ(p_{1}^{a_{1,j}} … p_{r}^{a_{r,j}})}{p_{1}^{c_{1,j}} … p_{r}^{c_{r,j}}p_{1}^{b_{1,j}} … p_{r}^{b_{r,j}}} .

For k = 1, …, r and j = 1, …, s, put d_{k,j} := b_{k,j} + c_{k,j}. Then, since the measure of G—which is 1—is the sum of the measures of the D_{j}, we have

1 = ∑_{j=1}^{s} \frac{φ(p_{1}^{a_{1,j}} … p_{r}^{a_{r,j}})}{p_{1}^{d_{1,j}} … p_{r}^{d_{r,j}}} .

For k = 1, …, r, let d_{k} := max{d_{k,1}, …, d_{k,s}}. Clearing denominators, from the last equation we obtain

p_{1}^{d_{1}} … p_{r}^{d_{r}} = Σ_{j=1}^{s}φ(p_{1}^{a_{1,j}} … p_{r}^{a_{r,j}})p_{1}^{d_{1}−d_{1,j}} … p_{r}^{d_{r}−d_{r,j}}.

Since each p_{1}, …, p_{r} all are odd, the left-hand side above is odd. As each φ(p_{1}^{a_{1,j}} … p_{r}^{a_{r,j}}) is even, the right-hand side is even, a contradiction that eliminates Case 1.

Case 2. Some p_{k} is even.

In this case, G has an involution g. Let the conjugacy class of g be C_{1}. For each h ∈ C_{1}, we have (gh)^{g} = hg = (gh)^{−1}. Hence, if S(g) := {x ∈ G : x^{g} = x^{−1} ∧ x ≠ 1} then dim(S(g)) = dim(C_{1}) = dim(G). Let k be the maximum size of the centralizer of a non-identity element of G. Then the uniformly definable family of sets {S(g) : g ∈ C_{1}} is (k + 2)-inconsistent. Indeed, if x ∈ S(g_{1}) ∩ … ∩ S(g_{k+2}), then the k + 1 distinct elements g_{i}g_{k+2}, for i = 1, …, k + 1, all centralize x, which is impossible. It follows that G must have D-rank at least dim(G) + 1, which is impossible. □

Theorem 5.15. Let G be a measurable group of dimension 1. Then G has an ∅-definable finite-by-abelian normal subgroup N of finite index in G.

Note that we cannot here obtain ‘abelian-by-finite’ as a conclusion. For an odd prime p, infinite extraspecial p-groups of exponent p are measurable of dimension 1 by Proposition 3.11 and Lemma 5.4, and are finite-by-abelian but not abelian-by-finite.

Proof. As G has dimension 1, every infinite definable subgroup of G has finite index in G. In particular, by Lemma 5.14, there is some g ∈ G \ {1} such that C_{G}(g) is infinite. As C_{G}(g) has finite index, the conjugacy class of g is finite.

The finite conjugacy classes of G have bounded size, as otherwise a simple compactness argument yields that G would have infinitely many infinite conjugacy classes, and so would have S_{1}-rank greater than 1. Consequently, the union of the finite conjugacy classses of G forms a non-trivial definable normal subgroup N of G. If N were finite, then it could be shown—see Proposition 5.10—that G/N would be a measurable group of S_{1}-rank 1 with no finite conjugacy classes, again contrary to Lemma 5.14 above. Hence N is infinite, and so |G : N| is finite. Furthermore, N is a BFC group, that is, a group with conjugacy classes of finite bounded size. By Theorem 3.1 of [29], we conclude that N′ is finite, and finally that G is finite-by-abelian-by-finite. □

Remark 5.16. Mark Ryten and Richard Elwes have extended the last result, and shown that any rank 1 supersimple group which is unimodular (as defined before Proposition 5.6) is finite-by-abelian-by-finite. The proof is similar.

Theorem 5.17. Let G be an ω-saturated infinite measurable group. Then G has an infinite abelian subgroup.

We cannot here expect an infinite definable abelian subgroup – consider again infinite extraspecial p-groups of exponent p.

Proof. Suppose the theorem is false. Let G be an infinite measurable group of minimal dimension such that G has no infinite abelian subgroup. We may assume additionally that G has finite exponent; for otherwise, by ω-saturation G has an element g of infinite order, and C_{G}(C_{G}(g)) is an abelian subgroup of G which contains ⟨g⟩, so is infinite. Furthermore, by the minimality hypothesis, every infinite definable subgroup of G has finite index.

Let N := {g ∈ G : g^{G} is finite}. As N is a definable subgroup, it is either finite or of finite index. We claim that N ≠ {1}. Indeed, by Lemma 5.14, there is some g ∈ G \ {1} such that C_{G}(g) is infinite. Then |G : C_{G}(g)| is finite, and so g ∈ N.

Next, suppose that N is infinite. Since N is definable, |G : N| is finite, so, replacing G by N if necessary, we may assume that N = G. Then |G : C_{G}(g)| is finite for all g ∈ G \ {1}. It is now easy to construct an infinite abelian subgroup of G: choose a sequence (y_{i} : i ∈ ω) from G, where y_{i} ∈ ⋂_{j<i} C_{G}(y_{j}) for each i, and take the subgroup generated by {y_{i} : i ∈ ω}. This again contradicts the hypothesis.

Finally, we consider the case that N is finite but non-trivial. If G contains an infinite subgroup H > N such that H/N abelian, then it is easily checked that the centralizer of every element of H has finite index in H. As in the last paragraph it follows that H contains an infinite abelian subgroup, contrary to hypothesis. Thus, invoking Proposition 5.10, we reduce to the situation that G/N is an infinite measurable group of the same dimension as G, with no infinite abelian subgroups and with all conjugacy classes infinite. This is impossible by the second paragraph, above. The proof is now complete. □

The final result of the paper provides some evidence that every measurable field may be pseudofinite.

Theorem 5.18. Let (F, +, .) be an infinite measurable field. Then:

i. F is quasifinite, that is, F has a unique extension of each finite degree; ii. F is perfect; iii. for every finite Galois extension K of F, the norm map N_{K/F} : K^{∗} → F^{∗}

is surjective.

Proof. Suppose F is measurable, and so has finite S_{1}-rank t. Assertions (ii) and (iii) hold for any supersimple field of finite S_{1}-rank: the statement (ii) is easy and is proved in [30], and (iii) is the main theorem of [31].

Statement (i) is proved almost exactly as in Scanlon’s Theorem 6.1, given in the Appendix below. In Theorem 6.1, it is assumed that the field admits a strong Euler characteristic rather than that it is measurable. Specifically, the assumption is that there is a partially ordered ring R and a map χ: Def(F) → R, from the collection of definable subsets of the cartesian powers of F to the set of non-negative elements of R, satisfying:

1. χ(X) = χ(Y) if X, Y are in definable bijection;

2. χ(X × Y) = χ(X)χ(Y);

3. χ(X ∪ Y) = χ(X) + χ(Y) if X ∩ Y = ∅;

4. if f: E → B is a definable surjection and c = χ(f^{−1}(b)) for every b ∈ B,

then χ(E) = c · χ(B). The Euler characteristic is nontrivial if 0 < 1 in R and the image of χ is not just {0}.

Each of these conditions hold for measure except for the additivity condition for disjoint unions, which is guaranteed to hold only if X and Y have the same dimension.

Lemma 6.3 is unchanged in our context, and Lemma 6.4 is not needed. In the proof of Lemma 6.5, from

F^{n} = I_{n} ∪ ∐_{{g:w̃(g)=n,g(n,1)=0}} Q_{g},

Scanlon obtains an expression for χ([I_{n}]). The latter depends on the additivity property, so requires that I_{n} and all the Q_{g} have the same dimension as F^{n}, namely nt. For this, it suffices to show inductively for all m that I_{m} has rank tm. If this is assumed for all m < n, then, arguing as in the fourth paragraph in the proof of Lemma 6.5, it follows for all g satisfying w̃(g) = n and g(n, 1) = 0 that Q_{g} has S_{1}-rank tn. If the dimension of I_{n} were less than tn, the end of the proof of Lemma 6.5 would yield 0 = \frac{1}{n}χ([I])^{n} + O(χ([I])^{n−1}), which is impossible.

Lemma 6.6 also adapts to the context of measure. Note, though, that in the last sentence, χ([S]) is equal to a summation over those s such that E_{s} has the same dimension as S – and this suffices for the argument. Our conclusion then follows from Lemmas 6.5 and 6.6, in the context of measure. □

Remark 5.19. It seems likely that Scanlon’s argument in the Appendix can be modified so that R is a semiring rather than a ring. In this case, in above proof one could directly quote Scanlon’s result, rather than adjust his proof. Define a semiring structure in the natural way on the pairs (d, μ). For addition, put (d_{1}, μ_{1})+(d_{2}, μ_{2}) = (d, μ), where d = Max {d_{1}, d_{2}}, and μ = μ_{1} +μ_{2} if d_{1} = d_{2}, and otherwise μ = μ_{i} if d = d_{i}. For multiplication, (d_{1}, μ_{1}) × (d_{2}, μ_{2}) = (d_{1} + d_{2}, μ_{1}μ_{2}). We have not checked this carefully.

6. Appendix due to Thomas Scanlon

This appendix contains the details of an assertion made in [26] to the effect that fields admitting a nontrivial strong ordered Euler characteristic are quasifinite.

The main theorem of this appendix is the following. Both the result and its presentation here are due to Scanlon.

Theorem 6.1. Any field admitting a nontrivial strong ordered Euler characteristic is quasifinite.

As the conclusion of Theorem 6.1 holds for finite fields, we may restrict attention to infinite fields. Throughout the rest of this note K denotes an infinite field given together with a nontrivial strong ordered Euler characteristic χ : Def(K) → R.

Lemma 6.2. K is perfect.

Proof. If K has characteristic zero, then there is nothing to prove. So we may assume that the characteristic of K is p > 0. The map x ↦ x^{p} on K is a definable bijection so χ([K]) = χ([K^{p}]). The inclusion K^{p} ↪ K shows that χ([K^{p}]) ≤ χ([K]) with equality only if K = K^{p}. Thus, K = K^{p}. That is, K is perfect as claimed. □

We now aim to show by a counting argument that for each positive integer n there is a unique extension of K of degree n. We need a simple combinatorial lemma.

Lemma 6.3. For a multi-index α ∈ ℤ_{+}^{ω} define w(α) := ∑_{n=0}^{∞} nα_{n}. Then for any natural number N we have ∑_{\{α:w(α)=N\}} ∏_{n=1}^{∞} \frac{1}{n^{αn} (α_{n}!)} = 1.

Proof.

∑_{N=0}^{∞}( ∑_{\{α:w(α)=N\}} ∏_{n=1}^{∞} \frac{1}{n^{α_{n}}(α_{n}!)})X^{N} = ∏_{n=1}^{∞}( ∑_{m=0}^{∞} \frac{1}{n^{m}(m!)}X^{nm})

= ∏_{n=1}^{∞} exp(\frac{X^{n}}{n})

= exp(∑_{n=1}^{∞} \frac{1}{n}X^{n})
= exp(log(\frac{1}{1 − X}))
= \frac{1}{1 − X}
= ∑_{N=0}^{∞} X^{N}

Equating the coefficients of X^{N} we obtain the statement of the lemma. □

Lemma 6.4. Let R′ := R ⊗ ℚ. There is a unique structure of a partially ordered ring on R′ for which ν : R → R′ is morphism of partially ordered ring. Moreover, R′ ≠ 0.

Proof. The positive elements in R′ are exactly those of the form x⊗r with x > 0 in R and r > 0 in ℚ. The rest of the proof is routine. □

We let χ̃ := ν ∘ χ : Def(K) → R′.

We define I_{n} := {(a_{0}, …, a_{n−1}) ∈ K^{n} : X^{n} + ∑_{i=0}^{n−1} a_{i}X^{i} is irreducible over K}.

Lemma 6.5. For any positive integer n we have χ̃([I_{n}]) = \frac{1}{n} χ̃([K])^{n}+O(χ̃([K])^{n−1}).

Proof. We prove the lemma by induction on n with the case of n = 1 being trivial as I_{1} = K.

For each n-tuple a = (a_{0}, …, a_{n−1}) ∈ K^{n}, let α(a) : ℤ_{+} → ω be defined by α(a)_{m} := the number of irreducible factors of X^{n} + ∑_{i=0}^{n−1} a_{i}X^{i} of degree m. Let β(a) : ℤ_{+}^{2} → ω be defined by β(a)(m, r) := the number of irreducible factors of X^{n} + ∑_{i=0}^{n−1} a_{i}X^{i} of degree m appearing with multiplicity exactly r.

For a given function f : ℤ_{+} → ω with w(f) = n, let P_{f} := {a ∈ K^{n} : α(a) = f}. Likewise, for a given g : ℤ_{+}^{2} → ω with w̃(g) := ∑_{m=1,r=1}^{∞} r · m · g(r, m) = n, let Q_{g} := {a ∈ K^{n} : β(a) = g}. We define u(g) := ∑_{m=1,r=1}^{∞} m · g(r, m).

Given g with w̃(g) = n, let ψ_{g} : ∏_{m,r} I_{m}^{g(m,r)} → K^{n} be the coefficient map associated to the composition of multiplication of polynomials with exponentiation of polynomials to the power r. Note that the image of ψ_{g} is Q_{g}. Moreover, ψ_{g} is ∏_{m,r} g(m, r)!-to-one over it image. Therefore, (∏_{m,r} g(m, r)!)χ̃([Q_{g}]) = ∏_{m,r} χ̃([I_{m}])^{g(m,r)} = ∏_{m,r} \frac{1}{m^{g(m,r)}} χ̃([K])^{u(g)} + O(χ̃([K])^{u(g)−1}.

We have K^{n} = I_{n} ∪^{·} ∐_{{g:w̃(g)=n,g(n,1)=0}} Q_{g}. Thus,

χ̃([I_{n}]) = χ̃([K])^{n} − ∑_{\{g:w̃(g)=n,g(n,1)=0\}}(∏_{m,r} \frac{1}{m^{g(m,r)}(g(m, r)!)})χ̃([K])^{u(g)} + O(χ̃([K])^{n−1})

= (1 − ∑_{\{f:w(f)=n,f(n)=0\}} ∏_{m} \frac{1}{m^{f(m)}(f(m)!)})χ̃([K])^{n} + O(χ̃([K])^{n−1})

= \frac{1}{n}χ̃([K])^{n} + O(χ̃([K])^{n−1})

as claimed. □

Lemma 6.6. Let L/K be an extension of degree n. Let S := {a ∈ K^{n} : X^{n} + ∑_{i=0}^{n−1} a_{i}X^{i} is the monic minimal polynomial of some b ∈ L}. Then χ̃([S]) ≥ \frac{1}{n} χ̃([K])^{n} + O(χ̃([K])^{n−1}).

Proof. Let B := {b ∈ L : K(c) ≠ L}. As the extension L/K is finite and separable, B = ⋃_{K≤M<L} M where the union runs over the finitely many proper subfields of L containing K. Each of these is a finite dimensional vector space over K of dimension strictly less than n. Thus, χ̃([L \ B]) = χ̃([K])^{n} + O(χ̃([K])^{n−1}).

For each 1 ≤ s ≤ n let E_{s} := {a ∈ L\B : a has exactly s conjugates in L over K}. Let f : (L \ B) → K^{n} be defined by f(a) = (b_{0}, …, b_{n−1}) where X^{n} + ∑_{i=0}^{n−1} b_{i}X^{i} is the monic minimal polynomial of a over K. Note that when restricted to E_{s}, the function f is s-to-one. Then S = ∐_{s=1}^{n} f(E_{s}). Thus, χ̃([S]) = ∑_{s=1}^{n} \frac{1}{s} χ̃([E_{s}]) ≥ ∑_{s=1}^{n} \frac{1}{n} χ̃([E_{s}]) = \frac{1}{n} χ̃([L \ B]) = \frac{1}{n} χ̃([K])^{n} + O(χ̃([K])^{n−1}) as claimed. □

Proof of Theorem 6.1. Combining the last two lemmata we see that there is a unique (Galois!) field extension of each degree. □

References

[1] M.H. Albert, ‘Measures on the random graph’, J. London Math. Soc. (2) 50 (1994), 417–429.

[2] T. Blossier, Ensembles minimaux localement modulaires, PhD thesis, Université Paris VII, 2001.

[3] B. Bollobás, A. Thomason, ‘Graphs which contain all small graphs’, Europ. J. Comb. 2 (1981), 13–15.

[4] B. Bollobás, Random Graphs, Academic Press, New York, 1985.

[5] S. Buechler, ‘Lascar strong types in some simple theories’, J. Symb. Logic 64 (1999), 817– 824.

[6] Z. Chatzidakis, L. van den Dries, A.J. Macintyre, ‘Definable sets over finite fields’, J. Reine Angew. Math. 427 (1992), 107–135.

[7] Z. Chatzidakis, A. Pillay, ‘Generic structures and simple theories’, Ann. Pure Appl. Logic 95 (1998), 71–92.

[8] G. Cherlin, L. Harrington, A.H. Lachlan, ‘ℵ_{0}-categorical, ℵ_{0}-stable structures’, Ann. Pure Appl. Logic 28 (1985), 103–135.

[9] G. Cherlin, E. Hrushovski, Finite structures with few types, Annals of Mathematics Studies No. 152, Princeton University Press, Princeton, 2003.

[10] A. Chowdhury, B. Hart, Z. Sokolović, ‘Affine covers of Lie geometries and the amalgamation property’, Proc. London Math. Soc. (3) 85 (2002), 513–563.

[11] K. Doerk, T, Hawkes, Finite soluble groups, de Gruyter, Berlin, 1992.

[12] L. van den Dries, ‘Algebraic theories with definable Skolem functions’, J. Symb. Logic 49 (1984), 625-629.

[13] R. Elwes, ‘Asymptotic classes of finite structures’, preprint.

[14] R. Elwes, H.D. Macpherson, ‘Measurable structures and asymptotic classes of finite structures’, in preparation.

[15] U. Felgner, ‘On ℵ_{0}-categorical extra-special p-groups’, Logique et Anal. (N.S.) 18 (1975), 407–428.

[16] C. Godsil, G. Royle, Algebraic graph theory, Springer, Berlin, 2001.

[17] R. L. Graham, J. H. Spencer, ‘A constructive solution to a tournament problem’, Canad. Math. Bull. 14 (1971), 45–48.

[18] D. Haskell, A. Pillay, and C. Steinhorn (Eds.), Model Theory, Algebra, and Geometry, Mathematical Sciences Research Institute Publications, v. 39, Cambridge University Press, Cambridge, 2000.

[19] W. Hodges, Model Theory, Cambridge University Press, Cambridge, 1993.

[20] E. Hrushovski, ‘Unimodular minimal structures’, J. London Math. Soc. (2) 46 (1992), 385– 396.

[21] E. Hrushovski, Y. Peterzil, A. Pillay, ‘Groups, measures, and the NIP’, preprint.

[22] E. Hrushovski, A. Pillay, ‘Definable subgroups of algebraic groups over finite fields’, J. Reine Angew. Math. 462 (1995), 69–91.

[23] E. Hrushovski, ‘Pseudofinite fields and related structures’, in Model theory and applications (Eds. L. Bélair, Z. Chatzidakis, P. D’Aquino, D.Marker, M. Otero, F. Point, A. Wilkie), Quaderni di Matematica, vol. 11, Caserta, 2005, 151–212.

[24] W.M. Kantor, M.W. Liebeck, H.D. Macpherson, ‘ℵ_{0}-categorical structures smoothly approximated by finite substructures’, Proc. London Math. Soc. (3) 59 (1989), 439–463.

[25] B. Kim, A. Pillay, ‘Simple theories’, Ann. Pure Appl. Logic 88 (1997), 149–164.

[26] J. Krajíček and T. Scanlon, Combinatorics with definable sets: Grothendieck rings and Euler characteristics, Bulletin of Symbolic Logic, Bull. Symb. Logic 6 (2000), 311-330.

[27] S. Lang, Algebra, Addison-Wesley, Menlo Park, 1984.

[28] I.D. Macdonald, ‘Some explicit bounds in groups with finite derived subgroups’, Proc. London Math. Soc. (3) 11 (1961), 23–56.

[29] B.H. Neumann, ‘Groups covered by permutable subsets’, J. London Math. Soc. 29 (1954), 236–248.

[30] A. Pillay, B. Poizat, ‘Corps et Chirurgie’, J. Symb. Logic 60 (1995), 528–533.

[31] A. Pillay, T. Scanlon, F.O. Wagner, ‘Supersimple fields and division rings’, Math. Research Letters 5 (1998), 473–483.

[32] H.N. Shapiro, Introduction to the theory of numbers, Wiley, New York, 1983.

[33] W. Szmielew, ‘Elementary properties of abelian groups’, Fund. Math. 41 (1955), 203–271.

[34] A. Thomason, ‘Random graphs, strongly regular graphs, and pseudo-random graphs’, in Surveys in Combinatorics 1987 (ed. C. Whitehead), London Math. Soc. Lecture Notes 123, Cambridge University Press, Cambridge, 1987, 173–195.

[35] F.O. Wagner, Simple theories, Kluwer, Dordrecht, 2000.

[36] J. Wiegold, ‘Groups with boundedly finite classes of conjugate elements’, Proc. Royal Soc. A 238 (1956), 389–401.

Department of Pure Mathematics, University of Leeds, Leeds LS2 9JT, England

  E-mail address: pmthdm@maths.leeds.ac.uk

Department of Mathematics, Vassar College, 124 Raymond Avenue Poughkeepsie, NY 12604 USA

  E-mail address: steinhorn@vassar.edu