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:
- Henry Towsner’s notes (which most of Notes 2-4 have been based on);
- Alex Usvyatsov’s notes on the derivation of Corollary 1.2 (broadly parallel to the notes here);
- Lou van den Dries’ notes (covering most of what we have done so far, and also material on stable theories); and
- Anand Pillay’s sketch of a simplified proof of Theorem 1.1.
— 1. Theorem 3.4 —
Here is a weakened version of Hrushovski’s Theorem 3.4:
Theorem 1 Let be a countable model of a language extending the language of groups, with a universal extension . Let be a continuous, invariant Keisler measure that is also invariant under translations. Let be a symmetric definable subset of with and finite, and let be the group generated by . Let be a wide type over contained in , and suppose that for every , there exists such that and are both wide.
Then the set is a normal subgroup of .
Remark 1 The condition about and seems to be a statement that there exist plenty of pairs in that are in “general position” somehow. In the case of abelian groups, it seems that this hypothesis not necessary. The hypothesis is for all , but by homogeneity it suffices to verify it for a single (since the action of the automorphism group of is transitive on ).
Remark 2 Interestingly, it seems that no doubling condition on is needed to prove this theorem, but the doubling condition arises when one wants to put to use.
Remark 3 As is wide, is wide also. If we also assume that every finite product has finite measure, this leads to the consequence that the index of in does not exceed 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 disjoint cosets in , and hence in some finite product . By Section 4 of Notes 2, is -definable, and so is the intersection of countably many definable sets . For any distinct , are disjoint, thus by saturation we have non-empty for some integer . By the Erdös-Rado theorem (an infinitary analogue of Ramsey’s theorem), we can then ass to a countable set of indices in which the are constant, thus we have a countable set of disjoint translates , which live in some finite product . But as is wide, has positive measure, while has finite measure, leading to a contradiction.
Remark 4 The set can also be defined in a more “characteristic” fashion as the smallest -definable subgroup of 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 emerges. Start with a finite combinatorial model, in which is a discrete interval and the group is the integers; we normalise to have measure . Taking ultralimits, we end up with a non-standard discrete interval in the non-standard integers, with being the counting measure normalised to give a measure of . (This is not yet a saturated model, but yet us ignore this issue.) Note that the subsets are definable for any standard natural number . Their intersection is a wide subgroup; if was a “generic” type in then would be wide, and would generate (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):
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 be a definable set of positive measure, and suppose that the product is covered by two definable sets (these are sets of pairs, of course). Then one can refine to a definable subset of positive measure, such that at least one of the following holds:
- (i) For every , the set has positive measure; or
- (ii) For every , the set has positive measure.
Proof: We can refine to be contained in . At least one of must have positive measure; let’s say that . We can find a definable set between and . If any of these has positive measure, then we can just take , so we may assume instead that for all , which implies that by Fubini’s theorem (which can be extended to Kiesler measures, at least in the weak form we need here), giving the desired contradiction.
Now we prove Lemma 2. By starting with and refining repeatedly using Lemma 3 (enumerating all the definable sets, and pairs of definable sets , so that each pair is revisited infinitely often) one can find a type refining with the property that whenever is a definable set containing , and is covered by two definable sets , then either has positive measure for all , or has positive measure for all . In particular (setting and empty) this implies that is wide.
Now let , and define to be the type , refined using the complement of all the sets of the form for definable with , and the complement of the sets of the form for definable with (note the asymmetry here!). We claim that this collection of sentences is still finitely satisfiable. Indeed, if this were not the case, would have to be covered by for some definable with . Write , then the set is definable and contains , and thus contains . If we set , we thus see that is a definable set containing and , contradicting the construction of .
As is finitely satisfiable, we may extend it to a type over . Now let be any realisation of . We claim that is wide. For if not, then would be contained in a set of measure zero for some definable , but by construction and hence is contained in the complement of , a contradiction.
We similarly claim that is wide. For if not, then is contained in a set of measure zero for some definable . since and have the same type over , has measure zero also, and so is contained in the complement of by construction. In particular, lies outside , which is inconsistent with lying in . This proves Lemma 2.
Remark 6 As I understand it, the argument simplifies in the stable case, when the wideness of over is equivalent to the wideness of over .
— 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 be positive integers. Then for sufficiently close to , the following statement is true: whenever is a finite subset of a group with the bounded quintipling property , where , and for a proportion at least of the -tuples , one has (recall that ). Then there exists a subgroup of such that is contained in at most cosets of .
We have weakened things a bit here by drawing the from rather than (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 , then one can find a sequence of groups with subsets of tripling uniformly bounded by , such that the proportion of -tuples in with approaches , but such that there is no subgroup of which can cover by cosets.
Taking an ultralimit (and using counting measure normalised so that has mass ), we obtain a subset of a group and a continuous, invariant, translation-invariant Keisler measure so that , , and such that the set (say) has measure . (Strictly speaking, one has to replace by a definable predicate between and , but let’s ignore this technicality.) We then extend to a universal model .
Since contains the wide type , it is itself wide. By Section 4 of Notes 2, is -definable, and is thus the intersection of definable sets , which have positive measure as is wide; we can place this inside the definable set . As has full measure in , we see that intersects for every , by saturation, must also intersect . In particular, there exists in such that
On the other hand, as is normal in , the set lies in . This implies that we cannot find more than disjoint translates , . As a consequence, is covered by at most translates of , and so can be covered by such translates, including itself. In particular, is both -definable and -definable (it is the complement of all the other cosets in ). But any set which is both -definable and -definable has to be definable. (Proof: we can write as the intersection of definable sets and also as the union of definable sets . By saturation, must be empty for at least one , and the claim follows.)
To summarise, is now a definable group which can cover by at most 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 , but shows that this set is “definable”, in the sense that there are a finite number of first-order expressions using and normalised cardinality, one of which is guaranteed to generate 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 would work for sufficiently late elements of this sequence, and then run the above argument to obtain a contradiction.