This week, Henry Towsner concluded his portion of reading seminar of the Hrushovski paper, by discussing (a weaker, simplified version of) main model-theoretic theorem (Theorem 3.4 of Hrushovski), and described how this theorem implied the combinatorial application in Corollary 1.2 of Hrushovski. The presentation here differs slightly from that in Hrushovski’s paper, for instance by avoiding mention of the more general notions of S1 ideals and forking.

Here is a collection of resources so far on the Hrushovski paper:

— 1. Theorem 3.4 —

Here is a weakened version of Hrushovski’s Theorem 3.4:

Theorem 1 Let {M} be a countable model of a language extending the language of groups, with a universal extension {G}. Let {\mu} be a continuous, invariant Keisler measure that is also invariant under translations. Let {X} be a symmetric definable subset of {G} with {\mu(X) = 1} and {\mu(X \cdot X)} finite, and let {\tilde G} be the group generated by {X}. Let {q} be a wide type over {M} contained in {X}, and suppose that for every {a \in q(G)}, there exists {b \in q(G)} such that {tp(a/M \cup \{b\})} and {tp(b/M \cup \{a\})} are both wide.

Then the set {S := q^{-1} q q^{-1} q} is a normal subgroup of {\tilde G}.

Remark 1 The condition about {a} and {b} seems to be a statement that there exist plenty of pairs {(a,b)} in {q(G)} that are in “general position” somehow. In the case of abelian groups, it seems that this hypothesis not necessary. The hypothesis is for all {a \in q(G)}, but by homogeneity it suffices to verify it for a single {a} (since the action of the automorphism group of {G} is transitive on {q(G)}).

Remark 2 Interestingly, it seems that no doubling condition on {X} is needed to prove this theorem, but the doubling condition arises when one wants to put {S} to use.

Remark 3 As {q} is wide, {S} is wide also. If we also assume that every finite product {X^{\cdot n} = X \cdot \ldots \cdot X} has finite measure, this leads to the consequence that the index of {S} in {\tilde G} does not exceed {2^{\aleph_0}} in cardinality (i.e. has bounded index, see Lemma 1 of Notes 2). Indeed, if this were not the case, then one could find more than {2^{\aleph_0}} disjoint cosets {Sa_i} in {\tilde G}, and hence in some finite product {X^{\cdot n}}. By Section 4 of Notes 2, {S} is {\bigwedge}-definable, and so is the intersection of countably many definable sets {S_n}. For any distinct {i,j}, {Sa_i, Sa_j} are disjoint, thus by saturation we have {S_{n(i,j)} a_i \cap S_{n(i,j)} a_j} non-empty for some integer {n(i,j)}. By the Erdös-Rado theorem (an infinitary analogue of Ramsey’s theorem), we can then ass to a countable set of indices {i} in which the {n(i,j) = n} are constant, thus we have a countable set of disjoint translates {S_n a_i}, which live in some finite product {X^{\cdot n}}. But as {S} is wide, {S_n} has positive measure, while {X^{\cdot n}} has finite measure, leading to a contradiction.

Remark 4 The set {S} can also be defined in a more “characteristic” fashion as the smallest {\bigwedge}-definable subgroup of {\tilde G} of bounded index; we’ll return to this point in a later note (I think).

Remark 5 Here is one example of how the group {S} emerges. Start with a finite combinatorial model, in which {X} is a discrete interval {\{-N,\ldots,N\}} and the group is the integers; we normalise {X} to have measure {1}. Taking ultralimits, we end up with a non-standard discrete interval {X = \{-N,\ldots,N\}} in the non-standard integers, with {\mu} being the counting measure normalised to give {X} a measure of {1}. (This is not yet a saturated model, but yet us ignore this issue.) Note that the subsets {\{-N/k,\ldots,N/k\}} are definable for any standard natural number {k}. Their intersection {S := \bigcap_k \{-N/k,\ldots,N/k\}} is a wide subgroup; if {q} was a “generic” type in {S} then {q} would be wide, and {q^{-1} q q^{-1} q} would generate {S} (this is vaguely reminiscent of the “Bogulybov theorem” in additive combinatorics).

To apply Theorem 1, we need the following auxiliary lemma (a weakened version of Hrushovski Lemma 2.15):

Lemma 2 Let {B} be a definable set of positive measure. Then we can refine {B} to a wide type {q} such that for every {a \in q(G)}, there exists {b \in q(G)} such that {tp(a/M \cup \{b\})} and {tp(b/M \cup \{a\})} are both wide.

This lemma can be viewed as a more technical variant of Lemma 2 from Notes 2.

To prove this lemma we need a technical sublemma:

Lemma 3 Let {P} be a definable set of positive measure, and suppose that the product {P \times P} is covered by two definable sets {C, D} (these are sets of pairs, of course). Then one can refine {P} to a definable subset {P'} of positive measure, such that at least one of the following holds:

  • (i) For every {a \in P'}, the set {C_a := \{ b: (a,b) \in C \}} has positive measure; or
  • (ii) For every {b \in P'}, the set {D^b := \{ a: (a,b) \in D \}} has positive measure.

Proof: We can refine {C, D} to be contained in {P \times P}. At least one of {C, D} must have positive measure; let’s say that {\mu(C)=0}. We can find a definable set {Q_n} between {\{ a: \mu(C_a) > 1/n \}} and {\{ a: \mu(C_a) \geq 1/n \}}. If any of these {Q_n} has positive measure, then we can just take {P' := Q_n}, so we may assume instead that {\mu(Q_n)=0} for all {n}, which implies that {\mu(C) = 0} by Fubini’s theorem (which can be extended to Kiesler measures, at least in the weak form we need here), giving the desired contradiction. \Box

Now we prove Lemma 2. By starting with {B} and refining repeatedly using Lemma 3 (enumerating all the definable sets, {P} and pairs of definable sets {C,D}, so that each pair is revisited infinitely often) one can find a type {q} refining {B} with the property that whenever {P} is a definable set containing {q({\Bbb U})}, and {P \times P} is covered by two definable sets {C, D}, then either {C_a} has positive measure for all {a \in P}, or {D^b} has positive measure for all {b \in P}. In particular (setting {C=P \times P} and {D} empty) this implies that {q} is wide.

Now let {a \in q({\Bbb U})}, and define {q_a} to be the type {q}, refined using the complement of all the sets of the form {C_a} for definable {C} with {\mu(C_a)=0}, and the complement of the sets of the form {D_a} for definable {D} with {\mu(D^a)=0} (note the asymmetry here!). We claim that this collection of sentences is still finitely satisfiable. Indeed, if this were not the case, {q} would have to be covered by {C_a \cup D_a} for some definable {C, D} with {\mu(C_a)=\mu(D^a)=0}. Write {P := C_a \cup D_a}, then the set {\{ x: P = C_x \cup D_x \}} is definable and contains {a}, and thus contains {q}. If we set {P' := \{ x \in P: P = C_x \cup D_x \}}, we thus see that {P'} is a definable set containing {q} and {P' \times P' \subset C \cup D}, contradicting the construction of {q'}.

As {q_a} is finitely satisfiable, we may extend it to a type {q'_a} over {a}. Now let {b} be any realisation of {q'_a}. We claim that {tp(b/M \cup \{a\})} is wide. For if not, then {b} would be contained in a set {C_a} of measure zero for some definable {C}, but by construction {q_a({\Bbb U})} and hence {q'_a({\Bbb U})} is contained in the complement of {C_a}, a contradiction.

We similarly claim that {tp(a/M \cup \{b\})} is wide. For if not, then {a} is contained in a set {D^b} of measure zero for some definable {D}. since {b} and {a} have the same type over {M}, {D^a} has measure zero also, and so {q_a} is contained in the complement of {D_a} by construction. In particular, {b} lies outside {D_a}, which is inconsistent with {a} lying in {D^b}. This proves Lemma 2.

Remark 6 As I understand it, the argument simplifies in the stable case, when the wideness of {a} over {b} is equivalent to the wideness of {b} over {a}.

— 2. Corollary 1.2 —

Assuming Theorem 1, we now establish the following combinatorial consequence, which is (a slightly weaker version of) Corollary 1.2 of Hrushovski:

Corollary 4 Let {k,l,m} be positive integers. Then for {p} sufficiently close to {1}, the following statement is true: whenever {X_0} is a finite subset of a group {G} with the bounded quintipling property {|X_0 X X| \leq k |X_0|}, where {X := X_0^{-1} X_0}, and for a proportion at least {p} of the {l}-tuples {(a_1,\ldots,a_l) \in (X \cdot X)^l}, one has {|a_1^X \ldots a_l^X| \geq |X|/m} (recall that {a^X := \{ x^{-1}ax: x \in X \}}). Then there exists a subgroup {S} of {X \cdot X} such that {X_0} is contained in at most {k(m+1)} cosets of {S}.

We have weakened things a bit here by drawing the {a_i} from {X \cdot X} rather than {X} (and also weakening bounded tripling to bounded quintipling); this is in order to achieve some minor simplifications in the proof.

We now prove the corollary, by the usual “compactness and contradiction” method. If the corollary failed for some {k,l,m}, then one can find a sequence of groups {G} with subsets {X_0} of tripling uniformly bounded by {k}, such that the proportion of {l}-tuples {(a_1,\ldots,a_l)} in {(X \cdot X)^l} with {|a_1^X \ldots a_l^X| \geq |X|/m} approaches {1}, but such that there is no subgroup {S} of {X \cdot X} which can cover {X} by {k(m+1)} cosets.

Taking an ultralimit (and using counting measure normalised so that {X} has mass {1}), we obtain a subset {X_0} of a group {M} and a continuous, invariant, translation-invariant Keisler measure {\mu} so that {\mu(X) = 1}, {\mu(X_0 X X) \leq k \mu(X_0)}, and such that the set {Q := \{ (a_1,\ldots,a_l) \in (X \cdot X)^l: \mu( a_1^X \ldots a_l^X ) \geq \mu(X)/(m+0.5) \}} (say) has measure {\mu(X \cdot X)^l}. (Strictly speaking, one has to replace {\mu( a_1^X \ldots a_l^X ) \geq \mu(X)/(m+1)} by a definable predicate between {\mu( a_1^X \ldots a_l^X ) \geq \mu(X)/(m+1)} and {\mu( a_1^X \ldots a_l^X ) > \mu(X)/(m+1)}, but let’s ignore this technicality.) We then extend {M} to a universal model {G}.

The set {X_0} has positive measure (at least {1/k}, in fact), so by Lemma 2, we may refine it to a wide type {q} obeying the hypotheses of Theorem 1, so that the set {S := q^{-1} q q^{-1} q} is a group. Note that this set is contained in {X \cdot X}.

Since {S} contains the wide type {q}, it is itself wide. By Section 4 of Notes 2, {S} is {\bigwedge}-definable, and is thus the intersection of definable sets {S_n}, which have positive measure as {S} is wide; we can place this inside the definable set {X \cdot X}. As {Q} has full measure in {(X \cdot X)^l}, we see that {Q} intersects {S_n^l} for every {n}, by saturation, {Q} must also intersect {S^l}. In particular, there exists {a_1,\ldots,a_l} in {S} such that

\displaystyle \mu( a_1^X \ldots a_l^X ) \geq \mu(X)/(m+1).

On the other hand, as {S} is normal in {\tilde G}, the set {a_1^X \ldots a_l^X} lies in {S}. This implies that we cannot find more than {\mu(X_0 X X) (m+1) / \mu(X) \leq k(m+1)} disjoint translates {xS}, {x \in X_0}. As a consequence, {X_0} is covered by at most {k(m+1)} translates of {S}, and so {X^2} can be covered by {k^4 (m+1)^4} such translates, including {S} itself. In particular, {S} is both {\bigwedge}-definable and {\bigvee}-definable (it is the complement of all the other cosets in {X^2}). But any set {S} which is both {\bigwedge}-definable and {\bigvee}-definable has to be definable. (Proof: we can write {S} as the intersection of definable sets {S_n} and also as the union of definable sets {U_n}. By saturation, {U_n \backslash S_n} must be empty for at least one {n}, and the claim follows.)

To summarise, {S} is now a definable group which can cover {X_0} by at most {k(m+1)} cosets. This is a first-order statement and so descends back to the original finitary models, but this then contradicts the construction of such sets, and proves the Corollary.

Remark 7 The argument not only shows the existence of the set {S}, but shows that this set is “definable”, in the sense that there are a finite number of first-order expressions using {X} and normalised cardinality, one of which is guaranteed to generate {S} whenever the hypotheses of Corollary 4 are satisfied. Indeed, if this were not the case, one could construct a sequence of counterexamples for which no such recipe for constructing {S} would work for sufficiently late elements of this sequence, and then run the above argument to obtain a contradiction.