COUNTING AND DIMENSIONS

EHUD HRUSHOVSKI^{1} AND FRANK WAGNER^{2}

Abstract. We prove a theorem comparing a well-behaved dimension notion to a second, more rudimentary dimension. Specialising to a non-standard counting measure, this generalizes a theorem of Larsen and Pink on an asymptotic upper bound for the intersection of a variety with a general finite subgroup of an algebraic group. As a second application we apply this to bad fields of positive characteristic, to give an asymptotic estimate for the number of 𝔽_{q}-rational points of a definable multiplicative subgroup similar to the Lang-Weil estimate for curves over finite fields.

Introduction

In [1] Larsen and Pink show that if H is a “sufficiently general” finite subgroup of a connected almost simple algebraic group G, then for any subvariety X of G

|H ∩ X| ≤ c · |H|^{dim(X)/dim(G)},

where the constant c depends only on the form of G and X, but not on H (in other words, G and X are allowed to vary in a constructible family). This theorem was recast (in somewhat greater generality) in model-theoretic form by the first author of the present paper, and rediscovered by the second author in the context of bad fields. In the general form it allows to give an upper bound, for suitable minimal structures with a well-behaved dimension d, of a rudimentary dimension δ (which may for instance be derived from counting measure in a quasi-finite subset) in terms of the original dimension d, typically giving Larsen-Pink like estimates for increasing families of finite subsets. We offer two proofs of the theorem: a more rapid one using types, and a more explicit construction using definable sets. The latter proof could in principle be used to get effective estimates on the constant c.

Date: February 23, 2006.

Work done during the semester on Model Theory and Applications to Algebra and Analysis at the Isaac Newton Institute Cambridge, whose hospitality is gratefully acknowledged.

1 Supported by Israel Science Foundation grant no. 244/03

2 Membre junior de l’Institut universitaire de France.

1. The Main theorem

Definition 1. Let 𝔐 be an uncountably saturated structure. A dimension theory on 𝔐 is an automorphism-invariant map d from the class of definable sets into ℕ, together with a formal element −∞, satisfying

(1) d(∅) = −∞ and d({x}) = 0 for any point x.

(2) d(X ∪ Y) = max{d(X), d(Y)}.

(3) Let f : X → Y be a definable map.

(a) If d(f^{−1}(y)) = n for all y ∈ Y, then d(X) = d(Y) + n, for all n ∈ ℕ ∪ {−∞}.

(b) {y ∈ Y : d(f^{−1}(y)) = n} is definable for all n ∈ ℕ∪{−∞}.

It follows that d(X × Y) = d(X) + d(Y), and d(X) = d(Y) if X and Y are definably isomorphic. By uncountable saturation, d(f^{−1}(y)) takes only finitely many values for y ∈ Y. Note that the trivial dimension d(X) = 0 for non-empty X is allowed.

Definition 2. For a partial type π let d(π) := min{d(X) : X ∈ π}; note that the minimum is necessarily attained. If p = tp(x/A), put d(x/A) := d(p).

For two partial types π, π′ over A let

π ⊗_{A} π′ := (π × π′) ∪ {¬X : X A-definable, d(X) < d(π) + d(π′)}.

Definition 3. Let 𝔐 be a structure with dimension d. A definable subset F ⊂ M^{3} is a correspondence on 𝔐 if the projection to the first two coordinates is surjective with 0-dimensional fibres. We put

\begin{aligned}F (X) & := \{y ∈ M :⊧ ∃(x, x′) ∈ X F (x, x′, y)\}, and \\ F^{−1}(y) & := \{(x, x′) ∈ M^{2} :⊧ F (x, x′, y)\}. \end{aligned}

If F is a set of correspondences, 𝔐 is F-minimal if for any A and partial 1-types π, π′ over A with 0 < d(π) ≤ d(π′) < d(M) and a partial type ρ over A extending π ⊗_{A} π′, there is F ∈ F with d(F (ρ)) > d(π′).

Roughly speaking, a structure is F-minimal if it is generated from any definable subset by repeated applications of the correspondences in F.

Lemma 1. The following are equivalent:

(1) 𝔐 is F-minimal.

(2) For any x, x′ ∈ M and parameters A with 0 < d(x/A) ≤ d(x′/A) < d(M) and d(xx′/A) = d(x/A) + d(x′/A) there is F ∈ F and y ∈ F (xx′) with d(F^{−1}(y) ∩ tp(xx′/A)) < d(x/A).

(3) For any A and A-definable X, X′ with 0 < d(X) ≤ d(X′) < d(M) and (x, x′) ∈ X × X′ there is A-definable W ⊆ X × X′ with (x, x′) ∈ W such that either d(W) < d(X × X′) or d(F^{−1}(y) ∩ W) < d(X) for some F ∈ F and y ∈ F (xx′).

Proof: Suppose 𝔐 is F-minimal, and consider x, x′, A as in (2). Put π = tp(x/A), π′ = tp(x′/A) and ρ := tp(xx′/A). Since d(xx′/A) = d(x/A)+d(x′/A) we have ρ ⊇ π⊗_{A}π′, so there is F ∈ F with d(F (ρ)) > d(π′). In particular there is y ∈ F (xx′) with d(y/A) > d(x′/A). Let k = d(F^{−1}(y) ∩ tp(xx′/A)), and choose A-definable W ∈ tp(xx′/A) with d(W) = d(xx′/A) and d(F^{−1}(y) ∩ W) = k, and A-definable Y ∈ tp(y/A) with d(F^{−1}(y′) ∩ W) = k for all y′ ∈ Y. Then

\begin{aligned}d(x/A) + d(x′/A) & = d(xx′/A) = d(W) ≥ d(F ∩ (W × Y)) \\ & = d(Y) + k ≥ d(y/A) + k > d(x′/A) + k \end{aligned}

(the first inequamlity holds, since the projection of F ∩ (W × Y) to W has fibres of dimension 0), whence d(x/A) > k = d(F^{−1}(y)∩tp(xx′/A)).

For the converse, consider partial types π, π′ and ρ over A as in the definition of F-minimality, and take xx′ ⊧ ρ. Since ρ ⊇ π ⊗_{A} π′ we have d(π) = d(x/A), d(π′) = d(x′/A), d(ρ) = d(xx′/A) and d(x/A) + d(x′/A) = d(xx′/A). By (2) there is F ∈ F and y ∈ F (xx′) with d(F^{−1}(y) ∩ tp(xx′/A)) < d(x/A). Choose A-definable W ∈ tp(xx′/A) with k = d(F^{−1}(y) ∩ tp(xx′/A)) = d(F^{−1}(y) ∩ W), and A-definable Y ∈ tp(y/A) with d(Y) = d(y/A) and d(F^{−1}(y′) ∩ W) = k for all y′ ∈ Y. Then

\begin{aligned}d(x/A) + d(x′/A) & = d(xx′/A) = d(ρ) ≤ d(F ∩ (W × Y)) \\ & = d(Y) + k = d(y/A) + k < d(y/A) + d(x/A) \end{aligned}

(for all uu′ ⊧ ρ there is v with uu′v ∈ F ∩ (W × Y), whence the first inequality), whence d(F (ρ)) ≥ d(y/A) > d(x′/A) = d(π′).

The equivalence (2) ⇔ (3) follows from the fact that for any partial type π there is X ∈ π with d(π) = d(X). □

Example 1. A field of finite Morley rank (possibly with additional structure) is {+, ×}-minimal.

Proof: Suppose 0 < RM(x/A) ≤ RM(x′/A) and x | ⌣_{A} x′. If both RM(x, x′/x + x′, A) ≥ RM(x/A) and RM(x, x′/xx′, A) ≥ RM(x/A), then x | ⌣_{A} x + x′ and x | ⌣_{A} xx′. Let x_{0}, x_{1} be independent realizations of stp(x/A, x′). Since x_{0} + x′ and x_{1} + x′ realize the same strong type over A, they realize the same non-forking extension to A, x_{0}, x_{1}; a strong automorphism over A, x_{0}, x_{1} maping x_{0} + x′ to x_{1} + x′ will map x_{0} − x_{1} + x′ to x′, whence x_{0} − x_{1} + x′ ⊧ stp(x′/A). As x′ | ⌣_{A} x_{0} − x_{1}, we get x_{0} − x_{1} ∈ stab^{+}(x′/A); similarly x_{0}x_{1}^{−1} ∈ stab^{×}(x′/A). As x_{0}, x_{1} are independent non-algebraic, both stabilizers are infinite; note that obviously stab^{+}(x′/A) is stab^{×}(x′/A)-invariant. However, in a field K of finite Morley rank the only definable additive subgroup A invariant under an infinite multiplicative subgroup is K itself (otherwise {c ∈ K : cA ≤ A} would define an infinite subring, and hence an infinite subfield, a contradiction). Thus stab^{+}(x′/A) = K, and RM(x′/A) = RM(K). □

Example 2. Let G be a simple algebraic group (or more generally, a simple group of finite Morley rank, possibly with additional structure). Let F be the collection of maps F_{c}(x, y) = cx^{−1}c^{−1}y, where c runs over a countable Zariski-dense subgroup Γ (respectively, subgroup Γ not contained in any proper definable subgroup of G). Then G is Fminimal.

Proof: In any group of finite Morley rank, d = RM is additive and definable. So consider A ⊇ Γ and x | ⌣_{A} x′ with 0 < RM(x/A) ≤ RM(x′/A), and suppose RM(x, x′/cx^{−1}c^{−1}x′, A) ≥ RM(x/A) for all c ∈ Γ. Then x | ⌣_{A} cx^{−1}c^{−1}x′, whence x^{−c^{−1}} | ⌣_{A} x^{−c^{−1}}x′ for all c ∈ Γ. So for any two independent realizations x_{0}, x_{1} of stp(x/A, x′) both x_{0}^{−c^{−1}}x′ and x_{1}^{−c^{−1}}x′ satisfy the unique non-forking extension of stp(x^{−c^{−1}}x′/A) to A, x_{0}, x_{1}, and (x_{0}x_{1}^{−1})^{c^{−1}}x′ ⊧ stp(x′/A). Since x_{0}, x_{1} | ⌣_{A} x′ this means that (x_{0}x_{1}^{−1})^{c^{−1}} ∈ stab(x′/A) for any two independent realisations x_{0}, x_{1} of stp(x/A), and any c ∈ Γ. So this stabilizer is an infinite definable subgroup, as is the intersection H of its Γ-conjugates. But then the normalizer of H contains Γ, whence G by our choice of Γ; since H is infinite and G is simple, we get H = G = stab(x′/A). Therefore tp(x′/A) is generic, and RM(x′/A) = RM(G). □

Definition 4. Let 𝔐 be any structure. A quasi-dimension on 𝔐 is a map δ from the class of definable sets into an ordered abelian group G, together with a formal element −∞, satisfying

(1) δ(∅) = −∞, and δ(X) > −∞ implies δ(X) ≥ 0.

(2) δ(X ∪ Y) = max{δ(X), δ(Y)}, and δ(X × Y) = δ(X) + δ(Y).

(3) For any definable X ⊆ M^{k} and projection π to some of the coordinates, if δ(π^{−1}(x̄)) ≤ g for all x̄ ∈ π(X), then δ(X) ≤ δ(π(X)) + g, for all g ∈ G ∪ {−∞}.

We can now state the main theorem.

Theorem 2. Let 𝔐 be an F-minimal structure, where F is a set of ∅-definable correspondences for some dimension d. Let δ be a quasidimension on 𝔐 such that

(0) d(X) = 0 implies δ(X) ≤ 0 for all definable X.

(4) For any F ∈ F and definable X ⊆ M^{2}, Y ⊆ M we have δ(F ∩(X ×Y)) ≥ δ(X), provided for all xx′ ∈ X there is y ∈ Y with F (xx′y).

Then d(M)δ(X) ≤ d(X)δ(M) for any definable set X ⊆ M.

Remark 1. (1) δ(F ∩ (X × Y)) ≤ δ(X) follows from axiom (3) and the fact that the fibres of the projection F ∩ (X × Y) → X have d-dimension zero, and hence δ-dimension zero.

(2) Requirement (4) holds in particular if F consists of definable functions, and δ is invariant under definable bijections.

The idea of the proof will be that given a set X, by F-minimality there is a sequence (F_{1}, …, F_{n}) of correspondences such that for Y_{1} = X and Y_{i+1} = F_{i}(X, Y_{i}), we get Y_{n} = 𝔐, and the kernels of the maps X × Y_{i} → F (X, Y_{i}) all have smaller dimension than X. By inductive hypothesis the kernels have small δ; since δ(M) is n δ(X) minus δ of the kernels, we get the desired upper bound for δ(X).

Proof: Clearly we may assume d(M) > 0. We use induction on d(X). For d(X) = 0 the assertion follows from condition (0). So suppose the assertion holds for dimension less than k, and d(X) = k. Put α = δ(M)/d(M) and suppose δ(X) ≥ α k.

Lemma 3. Let X, Y ⊆ M be B-definable with 0 < d(X) ≤ d(Y). Then there is a B-definable finite partition X × Y = W_{0} ∪ ⋯ ∪ W_{n}, correspondences F_{i} ∈ F and sets Z_{i} ⊆ F (W_{i}) for i = 1, …, n, such that

• d(W_{i}) = d(X) + d(Y) for i > 0, and d(W_{0}) < d(X) + d(Y).

• for all i > 0 we have d(Z_{i}) > d(Y), and d(F^{−1}(z) ∩ W_{i}) =

d(X) + d(Y) − d(Z_{i}) for all z ∈ Z_{i}.

Proof: For F ∈ F and B-definable W ⊆ X × Y put

\begin{aligned}W_{F} & := \{(x, y) ∈ W : ∃z ∈ F (xy) d(F^{−1}(z) ∩ W) < d(X)\}, and \\ Z_{F} & := \{z ∈ F (W_{F}) : d(F^{−1}(z) ∩ W) < d(X)\}. \end{aligned}

By Lemma 13 the B-definable sets

{V ⊂ X × Y : d(V) < d(X) + d(Y)} ∪ {W_{F} : F ∈ F, W B-definable}

cover X × Y. By compactness a finite subset covers X × Y; shrinking the sets if necessary, we may assume that the sets form a partition of X × Y. For i = d(X) − 1, d(X) − 2, …, 0 partition every Z_{F} involved into parts

Z_{F}^{i} := {z ∈ Z_{F} : d(F^{−1}(z) ∩ (W_{F} \ ⋃_{j>i} W_{F}^{j})) = i},

and put W_{F}^{i} = F^{−1}(Z_{F}^{i}) ∩ (W_{F} \ ⋃_{j>i} W_{F}^{j}). Let W_{0} be the union of those sets of dimension strictly less than d(X) + d(Y), and enumerate the others as W_{1}, …, W_{n} and Z_{1}, …, Z_{n}, respectively, with correspondences F_{1}, …, F_{n}. This satisfies the conditions. □

We inductively choose a tree of subsets of M with Y_{∅} := X and d(Y_{η′}) < d(Y_{η}) whenever η′ < η is a proper initial segment. Suppose we have found Y_{η}. If d(Y_{η}) = d(M) this branch stops. Otherwise put Y = Y_{η} in Lemma 3 and let Y_{ηi} := Z_{i} for i > 0. Put F_{ηi} := F_{i}, W_{ηi} := W_{i}, and n_{ηi} := n_{i} = d(X) + d(Y_{η}) − d(Y_{ηi}). As d(Y_{ηi}) > d(Y_{η}) for all η, the tree is finite. Let m be the maximal length of a branch, and put m_{η} = m − |η|, where 0 ≤ |η| ≤ m is the length of η.

Lemma 4. If W ⊂ X^{m_{ηi}} × Y_{ηi} with d(W) < d(X^{m_{ηi}} × Y_{ηi}), then d((id_{X^{mη−1}} × F_{ηi})^{−1}(W) ∩ (X^{m_{η}−1} × W_{ηi})) < d(X^{m_{η}} × Y_{η}).

Proof: Since the fibres have constant dimension n_{ηi}, we have

d((id_{X^{mη−1}} × F_{ηi})^{−1}(W) ∩ (X^{m_{η}−1} × W_{ηi})) = d(W) + n_{ηi}

< d(X^{m_{ηi}} × Y_{ηi}) + d(X) + d(Y_{η}) − d(Y_{ηi})

= d(X^{m_{η}} × Y_{η}). □

If d(Y_{η}) = d(M) put V_{m} = ∅, and if V_{η_{i}} has been defined for all i > 0 put

V_{η} := (X^{m_{η}−1} × W_{η0}) ∪ ⋃_{i>0}[(id_{X^{mη−1}} × F_{ηi})^{−1}(V_{ηi}) ∩ (X^{m_{η}−1} × W_{ηi})].

Then inductively d(V_{η}) < d(X^{m_{η}} ×Y_{η}). In particular d(V_{∅}) < d(X^{m+1}).

Lemma 5. If W ⊂ X^{n} with d(W) < n d(X), then δ(W) < n δ(X).

Proof: We use induction on n, the assertion being trivial for n = 0, 1. So assume it holds for n, and consider W ⊆ X^{n+1}. Let π be the projection of W to the first n coordinates, and put W_{i} = {x̄ ∈ π(W) : d(π^{−1}(x̄)) = i} for i ≤ k. Since d(W) < d(X^{n+1}), we have d(W_{k}) < d(X^{n}). So by inductive hypothesis

δ(π^{−1}(W_{k})) ≤ δ(W_{k}×X) = δ(W_{k})+δ(X) < δ(X^{n})+δ(X) = (n+1) δ(X).

On the other hand, for x̄ ∈ W_{i} with i < k we have

δ(π^{−1}(x̄)) ≤ α d(π^{−1}(x̄)) = α i

by our global inductive hypothesis. Hence by requirement (3)

δ(π^{−1}(W_{i})) ≤ δ(W_{i}) + α i ≤ δ(X^{n}) + α (k − 1) < (n + 1) δ(X)

since we assume δ(X) ≥ α k. Thus

δ(W) = max_{i≤k} δ(π^{−1}(W_{i})) < (n + 1) δ(X). □

It follows that δ(V_{∅}) < δ(X^{m+1}), and

(m + 1) δ(X) = δ(X^{m+1}) = δ((X^{m_{∅}} × Y_{∅}) \ V_{∅}).

For ȳ ∈ (X^{m_{ηi}} × Y_{ηi}) \ V_{ηi}

d((id_{X^{mη−1}} × F_{ηi})^{−1}(ȳ) ∩ [(X^{m_{η}−1} × W_{ηi}) \ V_{η}]) ≤ n_{ηi} < k,

so by inductive hypothesis

δ((id_{X^{mη−1}} × F_{ηi})^{−1}(ȳ) ∩ [(X^{m_{η}−1} × W_{ηi}) \ V_{η}]) ≤ α n_{ηi}.

Hence

\begin{aligned}δ((id_{X^{mη−1}} × F_{ηi}) & ∩ ([(X^{m_{η}−1} × W_{ηi}) \ V_{η}] × [(X^{m_{ηi}} × Y_{ηi}) \ V_{ηi}])) \\ & ≤ δ((X^{m_{ηi}} × Y_{ηi}) \ V_{ηi}) + α n_{ηi} \end{aligned}

by assumption (3), and

\begin{aligned}δ((id_{X^{mη−1}} × F_{ηi}) & ∩ ([(X^{m_{η}−1} × W_{ηi}) \ V_{η}] × [(X^{m_{ηi}} × Y_{ηi}) \ V_{ηi}])) \\ & ≥ δ((X^{m_{η}−1} × W_{ηi}) \ V_{η}]) \end{aligned}

by assumption (4). Since (X^{m_{η}} × Y_{η}) \ V_{η}) = ⋃_{i>0}(X^{m_{η}−1} × W_{ηi}) \ V_{η}),

\begin{aligned}δ((X^{m_{η}} × Y_{η}) \ V_{η}) & = max_{i>0} δ((X^{m_{η}−1} × W_{ηi}) \ V_{η}) \\ & ≤ max_{i>0} δ((X^{m_{ηi}} × Y_{ηi}) \ V_{ηi}) + α n_{ηi}. \end{aligned}

On the other hand, d(X) + d(Y_{η}) = d(Y_{ηi}) + n_{ηi} for all η and i > 0. Let η be the branch which corresponds always to the maximum of the δ-dimensions. Summing over the initial segments of η we obtain

(m + 1) δ(X) = δ((X^{m} × Y_{∅}) \ V_{∅}) ≤ δ(X^{m_{η}} × Y_{η}) + α ∑_{∅<η′≤η} n_{η′}

= m_{η} δ(X) + δ(Y_{η}) + α ∑_{∅<η′≤η} n_{η′}

≤ (m − |η|) δ(X) + δ(M) + α ∑_{∅<η′≤η} n_{η′},

whereas

(|η| + 1) d(X) = d(Y_{η}) + ∑_{∅<η′≤η} n_{η′} = d(M) + ∑_{∅<η′≤η} n_{η′}.

Therefore

(|η| + 1) δ(X) ≤ α (d(M) + ∑_{∅<η′≤η} n_{η′}) = α (|η| + 1) d(X),

and δ(X) ≤ α d(X). This proves the theorem. □

We shall now give a second, type-based proof for Theorem 2.

Proof: We use induction on d(X) =: k, the assertion following from condition (0) if k = 0. For partial types (π_{i} : i < m) and (π′_{j} : j < n) and rationals α_{i} and α′_{j} we put

∑_{i<m} α_{i} δ(π_{i}) ≤ ∑_{j<n} α′_{j} δ(π′_{j})

if for every choice of X′_{j} ∈ π′_{j} there are X_{i} ∈ π_{i} with ∑_{i<m} α_{i} δ(X_{i}) ≤ ∑ j < nα′_{j} δ(X′_{j}). Note that ≤ is transitive.

Claim. It is enough to prove the assertion for complete types.

Proof of Claim: Let X be an A-definable set, and 𝔛 the collection of A-definable X′ ⊆ X such that d(M)δ(X′) ≤ d(X′)δ(M). Then 𝔛 is closed under finite unions, so either d(M)δ(X) ≤ d(X)δ(M), or there is a type p ∈ S(A) completing the partial type {X \ X′ : X′ ∈ 𝔛}. By assumption d(M)δ(p) ≤ d(p)δ(M). So there are A-definable X_{1}, X_{2} ∈ p with d(M)δ(X_{1}) ≤ d(p)δ(M) and d(X_{2}) = d(p). But then X_{1}∩X_{2} ∈ 𝔛, a contradiction. □

So let p ∈ S_{1}(A) with d(p) = k. Clearly we may assume that d(M) δ(p) ≥ d(p) δ(M). For ease of notation we also assume that the value group G of δ is divisible.

Claim. If p′ ∈ S_{1}(A), there is q ∈ S_{2}(A) extending p ⊗_{A} p′ with δ(p) + δ(p′) ≤ δ(q).

Proof of Claim: Suppose not, and consider

𝔛 := {X ⊆ M^{2} A-definable : δ(p) + δ(p′) ≰ δ((p × p′) ∪ {X})}.

Then 𝔛 is closed under finite unions, and we can put ρ := (p × p′) ∪ {¬X : X ∈ 𝔛}, a consistent partial type. By assumption d(ρ) < d(p) + d(p′), as otherwise we could complete ρ to a type q with d(q) = d(p) + d(p′), whence q ⊇ p ⊗_{A} p′ and δ(p) + δ(p′) ≤ δ(q). Hence the projection to the second coordinate has fibres of dimension i < k. So there are A-definable sets X ∈ p, X′ ∈ p′ and X × X′ ⊃ Y ∈ ρ with d(X) = d(p), d(X′) = d(p′), d(Y) = d(ρ) and d(Y ∩ (X × {x′})) = i for all x′ ∈ X′. By inductive hypothesis d(M)δ(Y ∩ (X × {x′})) ≤ i δ(M) for all x′ ∈ X′, so by property (3)

δ(Y) ≤ δ(X′) + i δ(M)/d(M) ≤ δ(X′) + i δ(p)/d(p) ;

as one can choose Y depending on X′ we get

δ(ρ) ≤ δ(p′) + \frac{i}{k} δ(p) < δ(p′) + δ(p),

since δ(p) is bounded below by δ(M) d(p)/d(M), a contradiction to the definition of ρ. □

By F-minimality there is n < ω, a sequence p = p_{0}, p_{1}, …, p_{n} of complete types over A, a complete A-type q_{i} ⊇ p ⊗_{A} p_{i} with δ(p) + δ(p_{i}) ≤ δ(q_{i}) for i < n, and correspondences (F_{i} : i < n) in F, such that p_{i+1} is a completion of F_{i}(q_{i}) for all i < n with d(p_{i}) < d(p_{i+1}), and d(p_{n}) = d(M). For i < n put R_{i} := F_{i} ∩ (q_{i} × p_{i+1}), and choose A-definable sets X ∈ q_{i}, X′ ∈ p_{i+1} and Y ∈ R_{i} with d(X) = d(q_{i}) = d(p) + d(p_{i}), d(X′) = d(p_{i+1}), Y ⊆ X ×X′, and such that the fibres of the projection π of Y to the last coordinate have constant dimension j_{i} = d(π^{−1}(a)), where a ⊧ X′. Then

d(X′) + j_{i} = d(Y) = d(X) = d(p) + d(p_{i}) < d(p) + d(X′)

by axiom (3)(a). By inductive hypothesis δ(π^{−1}(a)) ≤ j_{i} δ(M)/d(M) for all a ∈ X′, whence δ(Y) ≤ δ(X′) + j_{i} δ(M)/d(M). Letting X′ converge to p_{i+1} and Y to R_{i}, we obtain δ(R_{i}) ≤ δ(p_{i+1}) + j_{i} δ(M)/d(M).

Since condition (4) implies δ(q_{i}) ≤ δ(F_{i} ∩ (q_{i} × p_{i+1})) = δ(R_{i}), we get

δ(p) + δ(p_{i}) ≤ δ(q_{i}) ≤ δ(R_{i}) ≤ δ(p_{i+1}) + j_{i} δ(M)/d(M).

Summing the inequalities for i < n, we obtain

(n + 1) δ(p) ≤ δ(p_{n}) + \frac{δ(M)}{d(M)} ∑_{i<n} j_{i} = δ(M) + \frac{δ(M)}{d(M)} ∑_{i<n} j_{i}.

On the other hand,

d(M) + ∑_{i<n} j_{i} = d(p_{n}) + ∑_{j<n}[d(p) + d(p_{i}) − d(p_{i+1})] = (n + 1) d(p),

whence

(n + 1) δ(p) ≤ \frac{δ(M)}{d(M)}[d(M) + ∑_{i<n} j_{i}] = \frac{δ(M)}{d(M)} (n + 1) d(p),

which proves the theorem. □

Remark 2. The above proof of Theorem 2 defined the relation δ(π) ≤ δ(π′) without actually defining the quantities δ(π). Perhaps for other applications an invariant δ(π) for types may be useful. We sketch now how this may be done.

Definition 4 requires δ to be a function into the non-negative elements of a linearly ordered group G that can be assumed divisible. In place of this, let us gain generality by taking G = (G, +, 0, <) to be a divisible linearly ordered commutative semi-group. This means that (1)–(2) below hold; we may as well assume (3); we assume cancellation only in the limited form (4), with respect to a distinguished element δ(M).

(1) (G, +, 0) is an additive semi-group, with every element uniquely divisible by any positive integer.

(2) < is a linear ordering, and x ≤ y implies x + z ≤ y + z.

(3) For any x ∈ G there is k < ω with 0 ≤ x ≤ k δ(M).

(4) x + δ(M) > x for any x.

It follows that x + \frac{1}{n} δ(M) > x for any x and integer n > 0.

These more general assumptions have the advantage that the semigroup G can be completed by means of Dedekind cuts. The assumptions continue to hold; in particular (4) does, since if U is a Dedekind cut invariant under adding δ(M), then by (3) it must include all of Γ, but Dedekind cuts are assumed bounded.

Now for any partial type π = ⋀_{i∈I} X_{i} we can define δ(π) = inf_{i∈I} δ(X_{i}). The earlier definition of the inequality is now a consequence. Whether the greater generality has any additional use, we do not know.

Corollary 6. Under the same hypotheses as Theorem 2, let X ⊂ M^{n} be definable. Then d(M) δ(X) ≤ d(X) δ(M).

Proof: We use induction on n, the assertion being Theorem 2 for n = 1. For X ⊆ M^{n+1} let π be the projection to the first n coordinates, and partition Y := π(X) into sets

Y_{i} := {x̄ ∈ Y : d(π^{−1}(x̄) ∩ X) = i}.

Let X_{i} := π^{−1}(Y_{i}) ∩ X, then (X_{i} : i ≤ d(M)) partitions X, and

d(X) = max_{i≤d(M)} d(X_{i}) = max_{i≤d(M)} d(Y_{i}) + i.

For every i ≤ d(M) and x̄ ∈ Y_{i} Theorem 2 yields δ(π^{−1}(x̄) ∩ X) ≤ α i, with α = δ(M)/d(M). By inductive hypothesis δ(Y_{i}) ≤ α d(Y_{i}), so

δ(X) = max_{i≤d(M)} δ(X_{i}) ≤ max_{i≤d(M)} δ(Y_{i}) + α i ≤ α max_{i≤d(M)} d(Y_{i}) + i = α d(X).

□

Remark 3. If 𝔐 is F-minimal, then 𝔐^{n} can be shown to be minimal with respect to the induced set of correspondences; this yields an alternative proof of Corollary 6.

2. An example that counts

Let (𝔐_{n} : n < ω) be a family of L-structures for some language L, and Γ_{n} finite subsets of M_{n}. For some ultrafilter on ω let ⟨𝔐, Γ⟩ be the ultraproduct of the structures ⟨𝔐_{n}, Γ_{n}⟩. The ultraproduct of the counting measures on the Γ_{n} yields a finitely additive measure μ on the definable subsets of Γ which takes values in some non-standard real closed field ℝ^{∗}. Note that ⟨𝔐, Γ, ℝ^{∗}, μ, log⟩ is ℵ_{0}-saturated (in fact, even ℵ_{1}-saturated).

Let I be the convex hull of ℤ in ℝ^{∗}, and π : ℝ^{∗} → ℝ^{∗}/I the natural (additive) quotient map. For a definable subset X of Γ define

δ(X) = π log μ(X),

and note that δ(X) = 0 if and only if log μ(X) ∈ I, that is μ(X) ∈ I, in other words μ_{n}(X_{n}) = O(1) in the factors, that is X is finite in the ultraproduct. For a definable subset Y of M we put δ(Y) := δ(Y ∩ Γ).

Lemma 7. Assume that 𝔐 has a dimension d such that d(X) = 0 implies X finite, and Γ is closed under the correspondences (i.e. for all xx′ ∈ Γ^{2} and y ∈ M such that F (xx′y) holds, y ∈ Γ as well). Then δ satisfies conditions (0)–(4) from Theorem 2.

Proof: (1) is obvious. For (2) note that

μ(X ∪ Y) ≤ μ(X) + μ(Y) ≤ 2 max{μ(X), μ(Y)},

whence log(μ(X ∪ Y)) ≤ log 2 + max{log μ(X), log μ(y)}. Since log 2 ∈ I, we get δ(X ∪ Y) ≤ max{δ(X), δ(Y)}; the other inequality follows from monotonicity.

We claim that for any definable map f : X → Y, if δ(f^{−1}(y)) ≤ α for all y ∈ Y, then there is r ∈ ℝ^{∗} with π(r) = α and log μ(f^{−1}(y)) ≤ r for all y ∈ Y. Indeed, pick any r_{0} ∈ ℝ^{∗} with π(r_{0}) = α. Put

Y_{n} := {y ∈ Y : log μ(f^{−1}(y)) ≤ r_{0} + n}.

Then Y_{n} ⊂ Y_{n+1} for all n < ω, and Y = ⋃_{n<ω} Y_{n}; by ℵ_{0}-saturation there is n_{0} with Y = Y_{n_{0}}. Then r := r_{0} + n_{0} will do.

This shows (3). Finally, (4) is clear, since the fibres of the projection of any F ∈ F to the first two coordinates must have d-dimension zero, hence be finite in the ultraproduct, and thus uniformly finite in the factors; they are non-empty by closedness of Γ under F. □

Unwinding the definitions, for this choice of δ (and suitable dimension d) the inequality d(M)δ(X) ≤ δ(M)d(X) becomes

|X_{n} ∩ Γ_{n}| ≤ O(|Γ_{n}|^{d(X)/d(M)}).

Possible choices for d include algebraic dimension, Morley rank, Shelah rank, Lascar rank, SU-rank or S_{1}-rank, whenever it is finite, additive and definable in the pure L-structure 𝔐.

Remark 4. Uniformity in parameters of the constant intervening in the O-notation follows automatically from compactness.

Remark 5. Note that for any definable map f : X → Y:

(1) If δ(f^{−1}(y) ≥ α for all y ∈ Y, then δ(Y) + α ≤ δ(X).

(2) If δ(f^{−1}(y) ≤ α for all y ∈ Y and f(X ∩ Γ) ⊆ Γ, then δ(X) ≤ δ(Y) + α.

In particular δ is invariant under definable bijections f preserving Γ (i.e. x ∈ Γ if and only if f(x) ∈ Γ).

3. An application

We shall now give the model-theoretic formulation of the theorem by Larsen and Pink alluded to in the introduction.

Theorem 8. [1] Let G_{n} be a simple algebraic group varying in an algebraic family and Γ_{n} a finite subgroup such that in the ultraproduct G the subgroup Γ is Zariski-dense. Then for any subvariety V of G

|V_{n} ∩ Γ_{n}| ≤ O(|Γ_{n}|^{dim(V)/dim(G)}).

Proof: Since G_{n} varies in an algebraic family, G is a simple algebraic group, and d = dim = RM is finite, additive and definable. Let F be the collection of maps F_{c}(x, y) = cx^{−1}c^{−1}y, where c runs over a countable Zariski-dense subgroup Γ_{0} of Γ. Clearly Γ is F-closed; moreover G is F-minimal by Example 2. Theorem 2 and Lemma 7 yield the result. □

Corollary 9. [1] In the setting of Theorem 8 consider a ∈ Γ with RM(C_{G}(a)) > 0, RM(a^{G}) > 0 and δ(G) > 0. Then Γ meets both C_{G}(a) and a^{G} in infinite sets.

Proof: Using the definable map x ↦ a^{x} and translation maps between C_{G}(a) and its cosets, we see that

RM(C_{G}(a)) + RM(a^{G}) = RM(G), and
δ(C_{G}(a)) + δ(a^{G}) = δ(G).

If α = δ(G)/RM(G), then δ(C_{G}(a)) ≤ α RM(C_{G}(a)) and δ(a^{G}) ≤ α RM(a^{G}) by Theorem 2 and Lemma 7, so equality must hold. □

4. Bad fields

A bad field [2] is a structure ⟨K, 0, 1, +, −, ·, T ⟩ of finite Morley rank, where T is a predicate for a distinguished infinite proper connected multiplicative subgroup (or even a non-algebraic connected subgroup of (K^{×})^{n} for some n, but these shall not be considered here). Such an object appears naturally when considering a faithful action of an abelian group M on an M-minimal abelian group A, the whole of finite Morley rank: We obtain that there is an algebraically closed field K such that A ≅ K^{+} and M ↪ K^{×}; one knows that the image of M generates K additively, but a priori it could be a proper subgroup. In particular, the possible existence of bad fields (and of bad groups) prevents us from proving an analogue of the Feit-Thompson theorem for simple groups of finite Morley rank, namely that they contain an involution (or, indeed, any torsion element at all).

In [3] the second author showed that under the assumption that there are infinitely many prime numbers of the form (p^{n}−1)/(p−1) (called p-Mersenne primes), there is no bad field of characteristic p > 0. In [4] he obtained an asymtotic estimate for the number of 𝔽_{q}-rational points of a multiplicative subgroup of rank 1; this shows the nonexistence of bad fields with RM(T) of rank 1 modulo a slightly weaker number-theoretic hypothesis. We can now obtain an analogous asymptotic estimate for multiplicative subgroups of arbitrary rank.

For two functions f and g on ℕ we put f ≍ g if there are positive constants c, c′ with cf(n) ≤ g(n) ≤ c′f(n) for all n ∈ ℕ.

Theorem 10. For any definable subset X of a bad field K of positive characteristic and any finite subfield 𝔽_{q} ≤ K we have |X ∩ 𝔽_{q}| ≤ O(q^{RM(X)/RM(K)}). In particular |T ∩ 𝔽_{p^{n}}| ≍ p^{n RM(T)/RM(K)}.

Proof: Let ⟨K, T ⟩ be a bad field of characteristic p > 0. We put 𝔐_{n} = ⟨K, T ⟩ for all n < ω, and Γ_{n} = 𝔽_{p^{n}}; our correspondences F will be addition and multiplication. Clearly Γ is closed under F, and K is F-minimal by Example 1. So Theorem 2 and Lemma 7 imply the first assertion.

By [3, Theorem 2] there is an ∅-definable partial function f : K → T with generic domain and an integer ℓ > 0 such that f(ta) = t^{ℓ}f(a) for all a ∈ dom(f) and all t ∈ T (in particular dom(f) is closed under multiplication by T). By connectivity T is ℓ-divisible, so all fibres have the same rank, namely RM(K) − RM(T). Hence the number of 𝔽_{q}- points on a fibre is bounded by O(q^{1−α}), where α = RM(T)/RM(K). Moreover, the complement of the domain has rank at most RM(K)−1, so its number of 𝔽_{q}-points is bounded by O(q^{1−1/RM(K)}). Since 𝔽_{q} is precisely the set of fixed points of the definable automorphism x ↦ x^{q}, it is closed under all 𝔽_{q}-definable functions. Hence the number of 𝔽_{q}- points of T is at least (q − O(q^{1−1/RM(K)}))/O(q^{1−α)} ≥ cq^{α} for some constant c. □

Definition 5. Let π be a set of prime numbers. For an integer n the π-part n_{π} is the biggest π-number (with all prime divisors in π) dividing n.

Corollary 11. Suppose ⟨K, T ⟩ is a bad field of characteristic p > 0, and let π be the set of prime orders of elements in T. Then

(p^{n} − 1)_{π} ≍ p^{α n},

with α = RM(T)/RM(K).

Proof: Since T is divisible, it is a direct sum of Prüfer groups. Hence if k is the subfield of K with p^{n} elements and q is a prime dividing |T ∩k^{×}|, then T contains all of the q-part of k^{×}. Thus |T ∩ k| = (p^{n} − 1)_{π}. □

Definition 6. Let 0 < α < 1. A set π of primes is (p, α)-balanced if ((p^{n} − 1)_{π}) ≍ p^{α n}. It is p-balanced if it is (p, α)-balanced for some α with 0 < α < 1.

Note that if π is (p, α)-balanced, then the complement of π is (p, 1−α)- balanced.

Corollary 12. If there is no p-balanced set, then there is no bad field of characteristic p.

Proof: This follows immediately from Corollary 11. □

References

[1] Michael J. Larsen and Richard Pink. Finite subgroups of algebraic groups. Preprint 1998.

[2] Bruno Poizat. Groupes Stables. Nur al-Mantiq wal-Marifah, Villeurbanne, 1987. Translated as: Stable Groups, AMS, 2002.

[3] Frank O. Wagner. Bad fields of positive characteristic. Bulletin of the London Mathematical Society, 35:499-502, 2003.

[4] Olivier Roche and Frank O. Wagner. Bad fields with a torus of rank 1. Proceedings of the Euro-conference on Model Theory and Applications, Ravello 2002, Quaderni di Matematika, Seconda Università di Napoli, Caserta, 2005.

Ehud Hrushovski, Einstein Institute of Mathematics, The Hebrew University of Jerusalem, Jerusalem 91904, Israel

E-mail address: ehud@math.huji.ac.il

Frank O. Wagner, Institut Camille Jordan, Université Claude Bernard (Lyon-1), 43 boulevard du 11 novembre 1918, 69622 Villeurbanne cédex, France

E-mail address: wagner@math.univ-lyon1.fr