Model-theoretic Elekes-Szabó for stable and o-minimal hypergraphs
Abstract.
A theorem of Elekes and Szabó recognizes algebraic groups among certain complex algebraic varieties with maximal size intersections with finite grids. We establish a generalization to relations of any arity and dimension, definable in: 1) stable structures with distal expansions (includes algebraically and differentially closed fields of characteristic ); and 2) -minimal expansions of groups. Our methods provide explicit bounds on the power saving exponent in the non-group case. Ingredients of the proof include: a higher arity generalization of the abelian group configuration theorem in stable structures, along with a purely combinatorial variant characterizing Latin hypercubes that arise from abelian groups; and Zarankiewicz-style bounds for hypergraphs definable in distal structures.
2010 Mathematics Subject Classification:
03C45, 52C101. Introduction
1.1. History, and a special case of the main theorem
Erdős and Szemerédi [erdHos1983sums] observed the following sum-product phenomenon: there exists such that for any finite set ,
They conjectured that this holds with for an arbitrary , and by the work of Solymosi [MR2538014] and Konyagin and Shkredov [MR3488800] it is known to hold with for some sufficiently small . Elekes and Rónyai [elekes2000combinatorial] generalized this by showing that for any polynomial there exists such that for every finite set we have
unless is either additive or multiplicative, i.e. of the form or for some univariate polynomials respectively. The bound was improved to in [raz].
Elekes and Szabó [ES] established a conceptual generalization of this result explaining the exceptional role played by the additive and multiplicative forms: for any irreducible polynomial over depending on all of its coordinates and such that its set zero set has dimension , either there exists some such that has at most zeroes on all finite grids, or is in a coordinate-wise finite-to-finite correspondence with the graph of multiplication of an algebraic group (see Theorem (B) below for a more precise statement). In the special Elekes-Rónyai case above, taking to be the graph of the polynomial function , the resulting group is either the additive or the multiplicative group of the field. Several generalizations, refinements and variants of this influential result were obtained recently [MR3577370, ES4d, jing2019minimal, MR4181764, bukh2012sum, tao2015expanding, hrushovski2013pseudo], in particular for complex algebraic relations of higher dimension and arity by Bays and Breuillard [Bays].
In this paper we obtain a generalization of the Elekes-Szabó theorem to hypergraphs of any arity and dimension definable in stable structures admitting distal expansions (this class includes algebraically and differentially closed fields of characteristic and compact complex manifolds); as well as for arbitrary -minimal structures. Before explaining our general theorems, we state two very special corollaries.
Theorem (A).
(Corollary 6.21) Assume and is semi-algebraic, of description complexity (i.e. given by at most polynomial (in-)equalities, with all polynomials of degree at most , and ), such that the projection of to any coordinates is finite-to-one. Then exactly one of the following holds.
-
(1)
There exists a constant , depending only on and , such that: for any and finite with for we have
where if , and if .
-
(2)
There exist open sets , an open set containing , and analytic bijections with analytic inverses such that
for all .
Theorem (B).
(Corollary 5.51) Assume , and let be an irreducible algebraic variety so that for each , the projection of to any coordinates is generically finite. Then exactly one of the following holds.
-
(1)
There exist depending only on such that: for any and with for we have
where if , and if .
-
(2)
For one of , or an elliptic curve group, is in coordinate-wise correspondence (see Section 5.8) with
Remark 1.1.
Theorem (B) is similar to the codimension case of [Bays, Theorem 1.4], however our method provides an explicit bound on the exponent in Clause (1).
Remark 1.2.
Remark 1.3.
Note the important difference — Theorem (A) is local, i.e. we can only obtain a correspondence of to a subset of a group after restricting to some open subsets . This is unavoidable in an ordered structure since the high count in Theorem (A.2) might be the result of a local phenomenon in . E.g. when is the union of , for some , and another set for which the count is low.
1.2. The Elekes-Szabó principle
We now describe the general setting of our main results. We let be an arbitrary first-order structure, in the sense of model theory, i.e. a set equipped with some distinguished functions and relations. As usual, a subset of is definable if it is the set of tuples satisfying a formula (with parameters). Two key examples to keep in mind are (in which definable sets are exactly the constructible ones, i.e. boolean combinations of the zero-sets of polynomials, by Tarski’s quantifier elimination) and (in which definable sets are exactly the semialgebraic ones, by Tarski-Seidenberg quantifier elimination). We refer to [MR1924282] for an introduction to model theory and the details of the aforementioned quantifier elimination results.
From now on, we fix a structure , , definable sets , and a definable relation . We write if with . By a grid on we mean a set with and . By an -grid on we mean a grid with .
Definition 1.4.
For , we say that a relation is fiber-algebraic, of degree if for any we have
We say that is fiber-algebraic if it is fiber-algebraic of degree for some .
In other words, fiber algebraicity means that the projection of onto any coordinates is finite-to-one. For example, if is fiber-algebraic of degree , then for any we have . Conversely, let be given by , and let . Then . This indicates that the upper and lower bounds match for the graph of addition in an abelian group (up to a constant) — and the Elekes-Szabó principle suggests that in many situations this is the only possibility. Before making this precise, we introduce some notation.
1.2.1. Grids in general position.
From now on we will assume that is equipped with some notion of integer-valued dimension on definable sets, to be specified later. A good example to keep in mind is Zariski dimension on constructible subsets of , or the topological dimension on semialgebraic subsets of .
Definition 1.5.
-
(1)
Let be a definable set in , and let be a definable family of subsets of . For , we say that a set is in -general position if for every with .
-
(2)
Let , , be definable sets in . Let , where is a definable family of subsets of . For we say that a grid on is in -general position if each is in -general position.
For example, when is the field , a subset of is in a -general position if any variety of smaller dimension and bounded degree (determined by the formula defining ) can cut out only points from it (see the proof of Corollary 5.48). Also, if is any definable family of subsets of , then for any large enough , every is in -general position. On the other hand, let and let be the family of algebraic curves of degree less than . If , then any set with is not in -general position.
1.2.2. Generic correspondence with group multiplication.
We assume that is a sufficiently saturated structure, and let be a definable relation and a connected type-definable group in . Type-definability means that the underlying set of the group is given by the intersection of a small (but possibly infinite) collection of definable sets, and the multiplication and inverse operations are relatively definable. Such a group is connected if it contains no proper type-definable subgroup of small index (see e.g. [MR1924282, Chapter 7.5]). And is the structure obtained from by adding sorts for the quotients of definable sets by definable equivalence relations in (see e.g. [MR1924282, Chapter 1.3]). In the case when is the field , connected type-definable groups are essentially just the complex algebraic groups connected in the sense of Zariski topology (see Section 5.8 for a discussion and further references).
Definition 1.6.
We say that is in a generic correspondence with multiplication in if there exist a small set and elements such that:
-
(1)
;
-
(2)
are independent generics in over (i.e. each does not belong to any definable set of dimension smaller than definable over );
-
(3)
For each there is a generic element inter-algebraic with over (i.e. and , where is the model-theoretic algebraic closure), such that .
Remark 1.7.
There are several variants of “generic correspondence with a group” considered in the literature around the Elekes-Szabó theorem. The one that we use arises naturally at the level of generality we work with, and as we discuss in Sections 5.8 and 6.4 it easily specializes to the notions considered previously in several cases of interest (e.g. the algebraic coordinate-wise finite-to-finite correspondence in the case of constructible sets in Theorem (B), or coordinate-wise analytic bijections on a neighborhood in the case of semialgebraic sets in Theorem (A)).
1.2.3. The Elekes-Szabó principle
Let and be definable sets in a sufficiently saturated structure with .
Definition 1.8.
We say that satisfy the Elekes-Szabó principle if for any fiber-algebraic definable relation , one of the following holds:
-
(1)
admits power saving: there exist some and some definable families on such that: for any and any -grid in -general position, we have ;
-
(2)
there exists a type-definable subset of of full dimension that is in a generic correspondence with multiplication in some type-definable abelian group of dimension .
The following are the previously known cases of the Elekes-Szabó principle:
-
(1)
[ES] , , arbitrary (no explicit exponent in power saving; no abelianity of the algebraic group for );
-
(2)
[MR3577370] , , (explicit in power saving);
-
(3)
[ES4d] , , (explicit in power saving);
-
(4)
[MR4181764] , , is the graph of an -ary polynomial function for an arbitrary (i.e. this is a generalization of Elekes-Rónyai to an arbitrary number of variables);
-
(5)
[Bays] , and arbitrary, abelianity of the group for (they work with a more relaxed notion of general position and arbitrary codimension, however no bounds on );
-
(6)
[StrMinES] is any strongly minimal structure interpretable in a distal structure (see Section 2), , .
In the first five cases the dimension is the Zariski dimension, and in the sixth case the Morley rank.
1.3. Main theorem
We can now state the main result of this paper.
Theorem (C).
The Elekes-Szabó principle holds in the following two cases:
- (1)
-
(2)
(Theorem 6.4) is an -minimal structure expanding a group, with respect to the topological dimension. In this case, on a type-definable generic subset of , we get a definable coordinate-wise bijection of with the graph of multiplication of an abelian type-definable group (we stress that this is a priori unrelated to the underlying group that expands).
Moreover, the power saving bound is explicit in (2) (see the statement of Theorem 6.4), and is explicitly calculated from a given distal cell decomposition for in (1) (see Theorem 5.27).
Examples of structures satisfying the assumption of Theorem (C.1) include: algebraically closed fields of characteristic , differentially closed fields of characteristic with finitely many commuting derivations, compact complex manifolds. In particular, Theorem (B) follows from Theorem (C.1) with , combined with some basic model theory of algebraically closed fields (see Section 5.8). We refer to [pillay1996geometric] for a detailed treatment of stability, and to [tent2012course, Chapter 8] for a quick introduction. See Section 2 for a discussion of distality.
Examples of -minimal structures include real closed fields (in particular, Theorem (A) follows from Theorem (C.2) with combined with some basic -minimality, see Section 6.4), , for and ranging over all functions real-analytic on some neighborhood of , or the combination of both . We refer to [MR1633348] for a detailed treatment of -minimality, or to [MR3728313, Section 3] and reference there for a quick introduction.
Remark 1.9.
The assumption that is an -minimal expansion of a group in Theorem (C.2) can be relaxed to the more general assumption that is an -minimal structure with definable Skolem functions (see e.g. [dinis2022definable] for a detailed discussion of Skolem functions and related notions), but possibly with a weaker bound on the power saving exponent than the one stated in Theorem 6.4. Indeed, the in the -power saving stated in Theorem 6.4 depends on in the -ST property, and hence on , in Fact 2.15(2) — the proof of which uses that is an -minimal expansion of a group. However, Fact 2.15(2) is known to hold in an arbitrary -minimal structure with (at least) the weaker bound (see [DistCellDecompBounds, Theorem 4.1]). To carry out the rest of the arguments in the proof of Theorem 6.4 in Section 6 we only use the existence of definable Skolem functions. Thus any -minimal structure with definable Skolem functions satisfies the conclusion of Theorem 6.4 with if and if .
1.4. Outline of the paper
In this section we outline the structure of the paper, and highlight some of the key ingredients of the proof of the main theorem. The proofs of (1) and (2) in Theorem (C) have similar strategy at the general level, however there are considerable technical differences. In each of the cases, the proof consists of the following key ingredients.
-
(1)
Zarankiewicz-type bounds for distal relations (Section 2, used for both Theorem (C.1) and (C.2)).
- (2)
-
(3)
The dichotomy between an incidence configuration, in which case the bounds from (1) give power saving, and existence of a family of functions (or finite-to-finite correspondences) associated to closed under generic composition, in which case a correspondence of to an abelian group is obtained using (2). This is Section 5 for the stable case (C.1) and Section 6 for the -minimal case (C.2).
We provide some further details for each of these ingredients, and discuss some auxiliary results of independent interest.
1.4.1. Zarankiewicz-type bounds for distal relations (Section 2)
Distal structures constitute a subclass of purely unstable NIP structures [simon2013distal] that contains all -minimal structures, various expansions of the field , and many other valued fields and related structures [DistValFields] (we refer to the introduction of [distal] for a general discussion of distality in connection to combinatorics and references). Distality of a graph can be viewed as a strengthening of finiteness of its VC-dimension retaining stronger combinatorial properties of semialgebraic graphs. In particular, it is demonstrated in [chernikov2015externally, distal, chernikov2016cutting] that many of the results in semialgebraic incidence combinatorics generalize to relations definable in distal structures. In Section 2 we discuss distality, in particular proving the following generalized “Szemerédi-Trotter” theorem:
Theorem (D).
(Theorem 2.8) For every and there exists some satisfying the following.
Assume that admits a distal cell decomposition such that for all finite . Then, taking we have: for all and such that is -free,
In particular, if is a binary relation definable in a distal structure and is -free for some , then there is some such that: for all we have . The exponent strictly less that requires distality, and is strictly better than e.g. the optimal bound for the point-line incidence relation on the affine plane over a field of positive characteristic. In the proof of Theorem (C), we will see how this translates to the power saving exponent in the non-group case. More precisely, for our analysis of the higher arity relation , we introduce the so-called -Szemerédi-Trotter property, or -ST property (Definition 2.12), capturing an iterated variant of Theorem (D), and show in Proposition 2.14 that Theorem (D) implies that every binary relation definable in a distal structure satisfies the -ST property for some calculated in terms of its distal cell decomposition. We conclude Section 2 with a discussion of the explicit bounds on for the -ST property in several particular structures of interest needed to deduce the explicit bounds on the power saving in Theorems (A) and (B).
1.4.2. Reconstructing an abelian group from a family of bijections (Section 3)
Assume that is an abelian group, and consider the -ary relation given by . Then is easily seen to satisfy the following two properties, for any permutation of the variables of :
(P1) | |||
(P2) | |||
In Section 3 we show a converse, assuming :
Theorem (E).
(Theorem 3.21) Assume , and are sets, so that satisfies (P1) and (P2) for any permutation of the variables. Then there exists an abelian group and bijections such that for every we have
Moreover, if is definable and are type-definable in a sufficiently saturated structure , then we can take to be type-definable and the bijections relatively definable in .
On the one hand, this can be viewed as a purely combinatorial higher arity variant of the Abelian Group Configuration theorem (see below) in the case when the definable closure in is equal to the algebraic closure (e.g. when is -minimal). On the other hand, if , property (P1) is equivalent to saying that the relation is an -dimensional permutation on the set , or a Latin -hypercube, as studied by Linial and Luria in [linial2014upper, linial2016discrepancy] (where Latin -hypercube is just a Latin square). Thus the condition (P2) in Theorem (E) characterizes, for , those Latin -hypercubes that are given by the relation “” in an abelian group. We remark that for there is a known “quadrangle condition” due to Brandt characterizing those Latin squares that represent the multiplication table of a group, see e.g. [gowers2020partial, Proposition 1.4].
1.4.3. Reconstructing a group from an abelian -gon in stable structures (Section 4)
Here we consider a generalization of the group reconstruction method from a fiber-algebraic of degree to a fiber-algebraic of arbitrary degree, which moreover only satisfies (P2) generically, and restricting to definable in a stable structure.
Working in a stable theory, it is convenient to formulate this in the language of generic points. By an -gon over a set of parameters we mean a tuple such that any of its elements are (forking-) independent over , and any element in it is in the algebraic closure of the other ones and . We say that an -gon is abelian if, after any permutation of its elements, we have
Note that this condition corresponds to the definition of a -based stable theory, but localized to the elements of the -gon.
If is a type-definable abelian group, are independent generics in and , then is an abelian -gon (associated to ). In Section 4 we prove a converse:
Theorem (F).
(Theorem 4.6) Let be an abelian -gon, , in a sufficiently saturated stable structure . Then there is a type-definable (in ) connected abelian group and an abelian -gon associated to , such that after a base change each is inter-algebraic with .
It is not hard to see that a -gon is essentially equivalent to the usual abelian group configuration, so Theorem (F) is a higher arity generalization. After this work was completed, we have learned that independently Hrushovski obtained a similar (but incomparable) unpublished result [HrushovskiUnpubl, HruOber].
1.4.4. Elekes-Szabó principle in stable structures with distal expansions — proof of Theorem (C.1) (Section 5)
We introduce and study the notion of -dimension in Section 5.1, imitating the topological definition of dimension in -minimal structures, but localized at a given tuple of commuting definable global types. Assume we are given -pairs for , i.e. is an -definable set and is a complete stationary type on for each (see Definition 5.2). We say that a definable set is -generic, where refers to the tuple , if . Finally, we define the -dimension via if for some projection of onto components, is -generic. We show that -dimension enjoys definability and additivity properties crucial for our arguments that may fail for Morley rank in general -stable theories such as . However, if is a definable subset of finite Morley rank and degree one, taking to be the unique type on of Morley rank , we have that (this is used to deduce Theorem (B) from Theorem (C.1)).
In Section 5.2 we consider the notion of irreducibility and show that every fiber-algebraic relation is a union of finitely many absolutely -irreducible sets. In Section 5.3 we consider finite grids in general position with respect to -dimension and prove some preliminary power-saving bounds. In Section 5.4 we state a more informative version of Theorem (C.1) (Theorem 5.24 + Theorem 5.27 concerning the bound in power saving) and make some preliminary reductions. In particular, we may assume , and let be a generic tuple in . As is fiber-algebraic, is an -gon. We then establish the following key structural dichotomy.
Theorem (G).
(Theorem 5.35 and its proof) Assuming , one of the following is true:
-
(1)
For and we have .
-
(2)
, as a binary relation on , for and , is a “pseudo-plane”. By which we mean here that, ignoring a smaller dimensional () set of , every fiber has a zero-dimensional intersection for all outside a smaller dimensional set (more precisely, the -dimension of the set defined in terms of in Section 5.5 is ).
This notion of a “pseudo-plane” generalizes the usual definition requiring that any two “lines” in intersect on finitely many “points” in , viewing as the incidence relation.
In case (2) the relation satisfies the assumption on the intersection of its fibers in Definition 2.12, hence the incidence bound from Theorem (D) can be applied inductively to obtain power saving for (see Section 5.5). Thus we may assume that for any permutation of we have
i.e. the -gon is abelian. Assuming that , Theorem (F) can be applied to establish a generic correspondence with a type-definable abelian group (Section 5.6). The case of Theorem (C.1) is treated separately in Section 5.7 by reducing it to the case (similar to the approach in [MR3577370]).
In Section 5.8 we combine Theorem (C.1) with some standard model theory of algebraically closed fields to deduce Theorem (B) and its higher dimensional version.
1.4.5. Elekes-Szabó principle in -minimal structures — proof of Theorem (C.2) (Section 6)
Our proof of the -minimal case is overall similar to the stable case, but is independent from it. In Section 6.1 we formulate a more informative version of Theorem (C.2) with explicit bounds on power saving (Theorem 6.4) and reduce it to Theorem 6.9 — which is an appropriate analog of Theorem (G): (1) either is a “pseudo-plane”, or (2) it contains a subset of full dimension so that the property (P2) from Theorem (E) holds in a neighborhood of every point of . In Case (1), considered in Section 6.2, we show that satisfies the required power saving using Theorem (D) (or rather, its refinement for -minimal structures from Fact 2.15). In Case (2), we show in Section 6.3 that one can choose a generic tuple in and (type-definable) infinitesimal neighborhoods of so that the relation satisfies (P1) and (P2) from Theorem (E) — applying it we obtain a generic correspondence with a type-definable abelian group, concluding the proof of Theorem (C.2) for . The case is reduced to similarly to the stable case.
Finally, in Section 6.4 we obtain a Corollary of Theorem (C.2) that holds in an arbitrary -minimal structure, not necessarily a saturated one - replacing a type-definable group by a definable local group (Theorem 6.19). Combining this with the solution of the Hilbert’s 5th problem for local groups [goldbring2010hilbert] (in fact, only in the much easier abelian case, see Theorem 8.5 there), we can improve “local group” to a “Lie group” in the case when the underlying set of the -minimal structure is and deduce Theorem (A) and its higher dimensional analog (Theorem 6.20, see also Remark 6.22). We also observe that for semi-linear relations, in the non-group case we have -power saving for any (Remark 6.24).
1.5. Acknowledgements
We are very grateful to the referees for their detailed and insightful reports and many valuable suggestions on improving the paper. We thank Saugata Basu, Martin Bays, Emmanuel Breuillard, Jim Freitag, Rahim Moosa, Tom Scanlon, Pierre Simon, Chieu-Minh Tran and Frank Wagner for some helpful conversations. We thank Institut Henri Poincaré in Paris for its hospitality during the “Model theory, Combinatorics and valued fields” term in the Spring trimester of 2018. Chernikov was partially supported by the NSF CAREER grant DMS-1651321 and by a Simons Fellowship. He thanks Lior Pachter, Michael Kinyon, and Math Twitter for the motivation in the final effort of finishing this paper. Peterzil was partially supported by the Israel Science Foundation grant 290/19. Starchenko was partially supported by the NSF grant DMS-1800806. The results of this paper were announced in [breuillard2021model].
2. Zarankiewicz-type bounds for distal relations
We begin by recalling some of the notions and results about distality and generalized “incidence bounds” for distal relations from [chernikov2016cutting], and refer to that article for further details. The following definition captures a combinatorial “shadow” of the existence of a nice topological cell decomposition (as e.g. in -minimal theories or in the -adics).
Definition 2.1.
[chernikov2016cutting, Section 2] Let be infinite sets, and a binary relation.
-
(1)
Let . For , we say that crosses if and .
-
(2)
A set is -complete over if is not crossed by any with .
-
(3)
A family of subsets of is a cell decomposition for over if and every is -complete over .
-
(4)
A cell decomposition for is a map such that for each finite , is a cell decomposition for over .
-
(5)
A cell decomposition is distal if there exist and a relation such that for all finite , .
-
(6)
For , we say that a cell decomposition has exponent if there exists some such that for all finite sets .
Remark 2.2.
Note that if is a distal cell decomposition, then it has exponent for as in Definition 2.1(5).
Remark 2.3.
Assume that the binary relation admits a distal cell decomposition with for every finite . Then for every , the binary relation admits a distal cell decomposition with for all finite .
Proof.
Indeed, assume that is witnessing that is distal, i.e. for any finite we have
Fix , and let
Given a finite , we define as
Then , hence is a distal cell decomposition for and . ∎
Existence of “strong honest definitions” established in [chernikov2015externally] shows that every relation definable in a distal structure admits a distal cell decomposition (of some exponent).
Fact 2.4.
(see [chernikov2016cutting, Fact 2.9]) Assume that the relation is definable in a distal structure . Then admits a distal cell decomposition (of some exponent ). Moreover, in this case the relation in Definition 2.1(5) is also definable in .
The following definition abstracts from the notion of cuttings in incidence geometry (see the introduction of [chernikov2016cutting] for an extended discussion).
Definition 2.5.
Let be infinite sets, . We say that admits cuttings with exponent if there is some constant satisfying the following. For any with and any with there are some sets covering with and such that for each there are at most elements so that is crossed by .
In the case in Definition 2.5, an -cutting is equivalent to a distal cell decomposition (sets in the covering are not crossed at all). And for varying between and , -cutting allows to control the trade-off between the number of cells in a covering and the number of times each cell is allowed to be crossed.
Fact 2.6.
(Distal cutting lemma, [chernikov2016cutting, Theorem 3.2]) Assume admits a distal cell decomposition of exponent . Then admits cuttings with exponent and with the constant coefficient depending only on and the constant coefficient of (the latter is not stated there explicitly, but follows from the proof). Moreover, every set in this cutting is an intersection of at most two cells in .
Remark 2.7.
We stress that in the Definition 2.5 of an -cutting, some of the fibers might be equal to each other. This is stated correctly on page of the introduction of [chernikov2016cutting], but is ambiguous in [chernikov2016cutting, Definition 3.1] (the family there is allowed to have repeated sets, so it is a multi-set of sets) and in the statement of [chernikov2016cutting, Theorem 3.2] (again, the family there should be viewed as a family of sets with repetitions — this is how it is understood in the proof of Theorem 3.2 there).
The next theorem can be viewed as an abstract variant of the Szemerédi-Trotter theorem. It generalizes (and strengthens) the incidence bound due to Elekes and Szabó [ES, Theorem 9] to arbitrary graphs admitting a distal cell decomposition, and is crucial to obtain power saving in the non-group case of our main theorem. Our proof below closely follows the proof of [StrMinES, Theorem 2.6] (which in turn is a generalization of [fox2014semi, Theorem 3.2] and [pach1992repeated, Theorem 4]) making the dependence on explicit. We note that the fact that the bound in Theorem 2.8 is sub-linear in was first observed in a special case in [shefferincidence].
As usual, given we say that a bipartite graph is -free if it does not contain a copy of the complete bipartite graph with its parts of size and , respectively.
Theorem 2.8.
For every and there exists some satisfying the following.
Assume that admits a distal cell decomposition such that for all finite . Then, taking we have: for all and such that is -free,
Before giving its proof we recall a couple of weaker general bounds that will be used. First, a classical fact from [kovari1954problem] giving a bound on the number of edges in -free graphs without any additional assumptions (see e.g. [MR2078877, Chapter VI.2, Theorem 2.2] for the stated version):
Fact 2.9.
Assume is -free, for some and finite. Then .
Given a set and a family of subsets of , the shatter function of is defined as
where .
Second, the following bound for graphs of bounded VC-density is only stated in [fox2014semi] for -free graphs with (and with the sides of the bipartite graph exchanged), but the more general statement below, as well as the linear dependence of the bound on , follow from its proof.
Fact 2.10.
[fox2014semi, Theorem 2.1] For every and there is some constant such that the following holds.
Let be a bipartite graph such that the family of subsets of satisfies for all (where ). Then, for any so that is -free, we have
Remark 2.11.
If admits a distal cell decomposition with for all , then for we have for all .
Indeed, by Definition 2.1, given any finite and , for any (and the sets in give a covering of ), hence at most different subsets of are cut out by the fibers of .
Proof of Theorem 2.8.
Let so that is -free be given.
Let (note that as ), and consider the family of subsets of (some of the sets in it might be repeated). By assumption and Fact 2.6, there is a family of subsets of giving a -cutting for the family . That is, is covered by the union of the sets in , any of the sets is crossed by at most elements from , and for some .
Then there is a set containing at least points from . Let be a subset of size exactly .
Hence from now on we assume that . Let be the set of all points such that crosses . We know that
Again by Fact 2.9 we get
for some . Hence there is a point such that .
Since is -free, there are at most points in from (otherwise, since none of the sets crosses and contains , which is of size , we would have a copy of ). And we have as . Hence
for some . We remove and repeat the argument until (2.1) or (2.2) applies. This shows:
Note that
using and that the second term is non-negative for .
Taking — which only depends on — we thus have
for all . ∎
For our applications to hypergraphs, we will need to consider a certain iterated variant of the bound in Theorem 2.8.
Definition 2.12.
Let be a family of subsets of and . We say that satisfies the -Szemerédi-Trotter property, or -ST property, if for any function there exists a function so that: for every , and with , if for every there are at most elements with , then .
We say that a relation satisfies the -ST property if the family does.
Lemma 2.1.
Assume that is a family of subsets of and .
-
(1)
Assume that are some sets and are bijections. For , let , and let , a family of subsets of . Then satisfies the -ST property if and only if satisfies the -ST property.
-
(2)
Assume that for some we have , and let , . Assume that each satisfies the -ST property. Then also satisfies the -ST property.
Proof.
(1) is immediate from the definition. In (2), given , assume witnesses that satisfies the -ST property. Then witnesses that satisfies the -ST property. ∎
Lemma 2.13.
Assume that , with and satisfy:
-
for every , and finite , if is -free, then .
Then satisfies the -ST property with and .
Proof.
Given and finite sets satisfying the assumption of the -ST property, we consider the finite graph with the vertex set and the edge relation defined by for all . By the assumption of the -ST property, this graph has degree at most , so it is -colorable by a standard fact in graph theory. For each , let be the set of vertices corresponding to the th color. Then the sets give a partition of , and for each the restriction of to is -free.
For any fixed , applying the assumption on to , we have
Then we have
(2.3) |
For the first sum, applying Hölder’s inequality with , we have
for all (by definition of and as ).
For the second sum, we have
for all . For the third sum we have
for all . Substituting these bounds into (2.3), as we get
We note that the -ST property is non-trivial only if . Lemma 2.13 shows that if satisfies the condition in Lemma 2.13 with , then satisfies the -ST property for some . By Theorem 2.8 this condition on is satisfied for any relation admitting a distal cell decomposition, leading to the following.
Proposition 2.14.
-
(1)
Assume that and admits a distal cell decomposition such that for all finite . Then satisfies the -ST property with and depending only on .
-
(2)
In particular, if the binary relation admits a distal cell decomposition of exponent , then the family of fibers
satisfies the -ST property .
Proof.
(1) By assumption and Theorem 2.8 with , there exists some such that, taking , for all and with is -free we have
Then, by Lemma 2.13, satisfies the -ST property and .
(2) Combining (1) and Remark 2.3. ∎
The in Proposition 2.14 will correspond to the power saving in the main theorem. Stronger upper bounds on in Lemma 2.13 (than the ones given by Theorem 2.8) are known in some particular distal structures of interest and can be used to improve the bound on in Proposition 2.14, and hence in the main theorem. We summarize some of these results relevant for our applications.
Fact 2.15.
Let be an -minimal expansion of a group.
-
(1)
Let be a definable family of subsets of , i.e. for some and definable sets . The definable relation viewed as a binary relation on admits a distal cell decomposition with exponent by [chernikov2016cutting, Theorem 4.1]. Then Proposition 2.14(2) implies that satisfies the -ST property with . (See also [basu2017minimal] for an alternative approach.)
-
(2)
For general , every definable relation admits a distal cell decomposition with exponent by [DistCellDecompBounds] (this improves on the weaker bound in [barone2013some, Section 4] and generalizes the semialgebraic case in [chazelle1991singly]). As in (1), Proposition 2.14(2) implies that any definable family of subsets of satisfies the -ST property with .
In particular this implies the following bounds for semialgebraic and constructible sets of bounded description complexity:
Corollary 2.16.
-
(1)
If and is the family of semialgebraic subsets of of description complexity (i.e. every is defined by a Boolean combination of at most polynomial (in-)equalities with real coefficients, with all polynomials of degree at most ), then satisfies the -ST property with (noting that for a fixed , the family is definable in the -minimal structure and using Fact 2.15(2)).
-
(2)
If and is the family of constructible subsets of of description complexity (i.e. every is defined by a Boolean combination of at most polynomial equations with complex coefficients, with all polynomials of degree at most ), then satisfies the -ST property with (noting that for a fixed , every can be viewed as a constructible, and hence semialgebraic, subset of of description complexity , and using (1)).
We note that a stronger bound is known for algebraic sets over and , however in the proof of the main theorem over we require a bound for more general families of constructible sets:
Fact 2.17.
- (1)
-
(2)
If and is algebraic with each an algebraic variety of degree , it can be viewed as an algebraic subset of with all fibers algebraic varieties of fixed degree, which implies by (1) that satisfies the -ST property with . (This improves the bound in [ES, Theorem 9].)
Problem 2.18.
We expect that the same bound on as in Fact 2.17(2) should hold for an arbitrary constructible family over in Corollary 2.16(2), and the same bound on as in Fact 2.17(1) should hold for an arbitrary definable family in an -minimal structure in Fact 2.15(2). However, the polynomial method used to obtain these stronger bounds for high dimensions in the algebraic case does not immediately generalize to constructible sets, and is not available for general -minimal structures (see [basu2018zeroes]).
Fact 2.19.
Assume that and is a family of semilinear subsets of so that each is defined by a Boolean combination of linear equalities and inequalities (with real coefficients). Then by [basit2020zarankiewicz, Theorem (C)], for every the family satisfies the condition in Lemma 2.13 with (and some function depending on and ). It follows that satisfies the -ST property for every (which is the best possible bound up to ).
Fact 2.20.
It has been shown in [DistValFields] that every differentially closed field (with one or several commuting derivations) of characteristic admits a distal expansion. Hence by Fact 2.4, every definable relation admits a distal cell decomposition of some finite exponent , hence by Proposition 2.14(2) any definable family of subsets of in a differentially closed field of characteristic satisfies the -ST property for some .
Fact 2.21.
The theory of compact complex manifolds, or CCM, is the theory of the structure containing a separate sort for each compact complex variety, with each Zariski closed subset of the cartesian products of the sorts named by a predicate (see [moosa] for a survey). This is an -stable theory of finite Morley rank, and it is interpretable in the -minimal structure . Hence, by Fact 2.4 and Proposition 2.14(2), every definable family admits a distal cell decomposition of some finite exponent , and hence satisfies the -ST property for some .
We remark that in differentially closed fields it is not possible to bound in terms of alone. Indeed, the dp-rank of the formula “” is for all (since the field of constants is definable, and is an infinite dimensional vector space over it, see [chernikov2014valued, Remark 5.3]). This implies that the VC-density of a definable relation cannot be bounded independent of (see e.g. [kaplan2013additivity]), and since gives an upper bound on the VC-density (see Remark 2.11), it cannot be bounded either.
Problem 2.22.
Obtain explicit bounds on the distal cell decomposition and incidence counting for relations definable in DCF0 (e.g., are they bounded in terms of the Morley rank of the relation ?).
3. Reconstructing an abelian group from a family of bijections
In this and the following sections we provide two higher arity variants of the group configuration theorem of Zilber-Hrushovski (see e.g [pillay1996geometric, Chapter 5.4]). From a model-theoretic point of view, our result can be viewed as a construction of a type-definable abelian group in the non-trivial local locally modular case, i.e. local modularity is only assumed for the given relation, as opposed to the whole theory, based on a relation of arbitrary arity .
In this section, as a warm-up, we begin with a purely combinatorial abelian group configuration for the case of bijections as opposed to finite-to-finite correspondences. It illustrates some of the main ideas and is sufficient for the application in the -minimal case of the main theorem in Section 6.
In the next Section 4, we generalize the construction to allow finite-to-finite correspondences instead of bijections (model-theoretically, algebraic closure instead of the definable closure) in the stable case, which requires additional forking calculus arguments.
3.1. -relations or arity
Throughout this section, we fix some sets and a quaternary relation . We assume that satisfies the following two properties.
-
(P1)
If we fix any variables, then there is exactly one value for the 4th variable satisfying .
-
(P2)
If
then
and the same is true under any other partition of the variables into two groups each of size two.
Intuitively, the first condition says that induces a family of bijective functions between any two of its coordinates, and the second condition says that this family of bijections satisfies the “abelian group configuration” condition in a strong sense. Our goal is to show that under these assumption there exist an abelian group for which is in a coordinate-wise bijective correspondence with the relation defined by .
First, we can view the relation as a -parametric family of bijections as follows. Note that for every pair , the corresponding fiber is the graph of a function from to by (P1). Let be the set of all functions from to whose graph is a fiber of .
Similarly, let be the set of all functions from to whose graph is a fiber of (for some ). Note that all functions in and in are bijections, again by (P1).
Claim 3.1.
For every there is a unique with , and similarly for .
Proof.
We only check this for , the argument for is analogous. Let be fixed. Existence: let be arbitrary, then by (P1) there exists some with , hence the function corresponding to the fiber of at satisfies the requirement. Uniqueness follows from (P2) for the appropriate partition of the variables: if for some , then for all we have . ∎
Claim 3.2.
For every and in there exists a unique such that (which then satisfies for all ).
And similarly exchanging the roles of and .
Proof.
As are given, by (P1) there is a unique choice for the fourth coordinate of a tuple in determining the image of on . There is only one such by Claim 3.1 with respect to . ∎
For , we will denote by the unique as in Claim 3.2. Similarly, for , we will denote by the unique as in Claim 3.2.
Remark 3.3.
Note that and for all .
Claim 3.4.
Let , and for . Then , and .
Proof.
We first observe the following: given any and , if we take and , then . Indeed, let , , then . Similarly, let , , then . By the definition of we then have
Applying (P2) for the partition , this implies , as wanted.
Now fix an arbitrary and take the corresponding , varying the observation implies that the graph of is given by the fiber . Similarly, the graph of is given by the fiber for an arbitrary and the corresponding ; and follows. ∎
Claim 3.5.
For any we have , and similarly for .
Proof.
Let be arbitrary. We define , and , so we have . Let also , and , so we have .
We need to show that .
Claim 3.6.
Given an arbitrary element , for every pair we define
Then is an abelian group, with the identity element .
Proof.
Remark 3.7.
Next we establish a connection of these groups and the relation . We fix arbitrary , , and with . By Claim 3.1, let be unique with , and let be unique with . Then by Claim 3.2, and by Remark 3.7 we have isomorphic groups on and on . We will denote this common group by .
We consider the following bijections between each of and , using our identification of with both and and Claim 3.1:
-
•
let be the bijection that assigns to the unique with ;
-
•
let be the bijection that assigns to the unique with ;
-
•
let be the bijection that assigns to the unique with ;
-
•
let be the bijection that assigns to the unique with .
Claim 3.8.
For any and , is the unique function with .
Similarly, for any and , is the unique function with .
Proof.
Let be arbitrary, and let . Note that, from the definitions, , and , hence . The second claim is analogous. ∎
Proposition 3.9.
For any , if and only if (in ).
3.2. -relation of any arity for dcl
Now we extend the construction of an abelian group to relations of arbitrary arity . Assume that we are given , sets and a relation satisfying the following two conditions (corresponding to the conditions in Section 3.1 when ).
-
(P1)
For any permutation of the variables of we have:
-
(P2)
For any permutation of the variables of we have:
where , evaluates on the concatenated tuple , and similarly for .
We let be the set of all functions whose graph is given by the set of pairs satisfying for some .
Remark 3.10.
-
(1)
Every is a bijection, by (P1).
-
(2)
For every there exists a unique such that (existence by (P1), uniqueness by (P2)). We will denote it as .
Lemma 3.11.
For every and there exists some such that is the graph of .
Proof.
Choose any , let . Choose such that holds by (P1). Then defines the graph of by Remark 3.10(2). ∎
Lemma 3.12.
For any there exists some such that .
Proof.
Definition 3.13.
We fix arbitrary elements so that holds. Let be the function whose graph is given by , i.e. . We define by taking .
Lemma 3.14.
is an abelian group with the identity element .
Definition 3.15.
We define the map by for all , and the map by for all .
Note that both and are bijections by Remark 3.10.
Lemma 3.16.
For any and we have .
Proof.
Let . Note that , and , hence , so . ∎
Definition 3.17.
For any set , we define the map as follows: for , let be the function in whose graph is given by with for and for . We write for .
Remark 3.18.
For each , the map is a bijection (by (P2)).
Lemma 3.19.
Fix some and . Let . Then for any and we have .
Proof.
Without loss of generality we have and for some . Take any and . Then, from the definitions:
-
•
the graph of is given by , where ;
-
•
the graph of is given by ;
-
•
the graph of is given by .
Let be such that and let be such that . Then . On the other hand, the following also hold:
-
•
;
-
•
;
-
•
.
Applying (P2) with respect to the coordinates and the rest, this implies that holds, i.e. . Hence by Remark 3.10(2), as wanted.
∎
Proposition 3.20.
For any we have
Proof.
We are ready to prove the main theorem of the section.
Theorem 3.21.
Given , sets and satisfying (P1) and (P2), there exists an abelian group and bijections such that for every we have
Moreover, if we have first-order structures so that is -saturated, each is type-definable (respectively, definable) in over and for a relation definable in over , then given an arbitrary tuple , we can take to be type-definable (respectively, definable) and the bijections to be definable in , in both cases only using parameters from and , so that for all .
Proof.
Assume now that, for each , is type-definable in over , i.e. is the set of solutions in of some partial type over ; and that for some -definable relation . Then from (P1) and (P2) for , for any permutation of the variables of we have in :
By -saturation of , in each of these implications can be replaced by a finite conjunction of formulas in it. Hence, taking a finite conjunction over all permutations of the variables, we conclude that there exist some -definable sets so that satisfies (P2) and
-
(P1′)
For any permutation of the variables of , for any , there exists at most one (but possibly none) satisfying .
We proceed to type-definability of . Let (so in ) be as above (see Definition 3.13). We identify with , the domain of , via the bijection above mapping to (in an analogous manner we could identify the domain of with any of the type-definable sets ). Under this identification, the graph of addition in is given by
We have the following claim.
Claim 3.22.
-
•
For any and , if holds then defines the graph of (since satisfies (P2)).
-
•
For any , if coincides with the graph of some function , then using that satisfies (P1′) we have:
-
–
for any , is the unique element in satisfying ;
-
–
for any , is the unique element in satisfying .
-
–
Using Claim 3.22, we have
where is a definable relation in (with parameters in ) given by
This shows that is type-definable over . It remains to show definability of the bijections , where is identified with as above (i.e. to show that the graph of is given by some -definable relation intersected with ).
We have , hence we need to show that the relation
is of the form for some relation definable in . Using Claim 3.22, we can take
We have , hence the corresponding definable relation is just the graph of the equality.
Finally, given , maps to the function in with the graph given by . Hence, remembering that the identity of is , which corresponds to , and using Claim 3.22, the graph of is given by the intersection of with the definable relation
4. Reconstructing an abelian group from an abelian -gon
Let be a stable theory in a language and a monster model of . By “independence” we mean independence in the sense of forking, unless stated otherwise, and write to denote that does not fork over . We assume some familiarity with the properties of forking in stable theories (see e.g. [MR3888974] for a concise introduction to model-theoretic stability, and [pillay1996geometric] for a detailed treatment). We say that a subset of is small if .
4.1. Abelian -gons
For a small set , as usual by its -closure we mean the algebraic closure over , i.e. for a set its -closure is .
Definition 4.1.
111An analogous notion in the context of geometric theories was introduced in [berenstein2016geometric] under the name of an algebraic -gon, and it was also used in [chernikov2019n, Section 7].We say that a tuple is an -gon over a set if each type is not algebraic, any elements of the tuple are independent over , and every element is in the -closure of the rest. We refer to a -gon as a triangle.
Definition 4.2.
We say that an -gon over with is abelian if for any , taking , we have
Example 4.3.
Let be a small set and let be an abelian group type-definable over . Let be independent generic elements over , and let be such that . Then is an abelian -gon over associated to .
Indeed, by assumption we have . Also , hence , which together with implies . As the group is abelian, the same holds for any instead of .
Definition 4.4.
Given two tuples , and a small set we say that and are -equivalent over if for all . As usual if we omit it.
Remark 4.5.
Note that the condition “ are -equivalent” is stronger than “the tuples are inter-algebraic”, as it requires inter-algebraicity component-wise.
In this section we prove the following theorem.
Theorem 4.6.
Let be an abelian -gon, over some small set . Then there is a finite set with , a type-definable (in ) over connected (i.e. ) abelian group and an abelian -gon over associated to such that and are -equivalent over .
Remark 4.7.
After this work was completed, we have learned that independently Hrushovski obtained a similar (but incomparable) result [HrushovskiUnpubl, HruOber].
Remark 4.8.
In the case , Theorem 4.6 follows from the Abelian Group Configuration Theorem (see [bays2017model, Theorem C.2]).
In the rest of the section we prove Theorem 4.6, following the presentation of Hrushovski’s Group Configuration Theorem in [bays2018geometric, Theorem 6.1] with appropriate modifications.
First note that, adding to the language new constants naming the elements of , we may assume without loss of generality that in Theorem 4.6, and that all types over the empty set are stationary.
Given a tuple we will often modify it by applying the following two operations:
-
•
for a finite set with we expand the language by constants for the elements of , and refer to this as “base change to ”.
-
•
we replace with an -equivalent tuple (over ), and refer to this as “inter-algebraic replacing”.
It is not hard to see that these two operations transform an (abelian) -gon to an (abelian) -gon, and we will freely apply them to the -gon in the proof of Theorem 4.6.
Definition 4.9.
We say that a tuple is an expanded abelian -gon if is an abelian -gon, and .
We remark that the tuple might be infinite even if all of the tuples ’s are finite. Similarly, base change and inter-algebraic replacement transform an expanded abelian -gon to an expanded abelian -gon.
From now on, we fix an abelian -gon . We also fix such that (exists by the definition of abelianity).
Claim 4.10.
is a triangle and is an -gon.
Proof.
For , since and we have . Also . Thus the set is pairwise independent. We also have . From we obtain . Since we obtain . Similarly , thus is a triangle.
The proof that is an -gon is similar. ∎
4.2. Step 1. Obtaining a pair of interdefinable elements
After applying finitely many base changes and inter-algebraic replacements we may assume that and are interdefinable over , i.e. and
Our proof of Step 1 follows closely the proof of the corresponding step in the proof of [bays2018geometric, Theorem 6.1], but in order to keep track of the additional parameters we work with enhanced group configurations.
Definition 4.11.
An enhanced group configuration is a tuple
satisfying the following diagram.
That is,
-
•
is a triangle over ;
-
•
is a triangle over ;
-
•
is a triangle over ;
-
•
is a triangle;
-
•
for any non-collinear triple in , the set given by it and is independent over .
If we omit it from the diagram:
In order to complete Step 1 we first show a few lemmas.
Lemma 4.12.
Let be an enhanced group configuration. Let be the imaginary representing the finite set of all conjugates of over . Then is inter-algebraic with .
Proof.
It suffices to show that for all . Indeed, then , and as it satisfies the algebraic formula “”.
We have , so , so . Let , then , so . But , so . Then we also have since for each there is an automorphism of with and . ∎
Lemma 4.13.
Assume that is an enhanced group configuration. Then after a base change it is -equivalent to an enhanced group configuration such that . Moreover, and .
Proof.
Recall that by our assumption all types over the empty set are stationary.
Let . We have , hence . Then by stationarity we have . Let be such that . So is also an enhanced group configuration. Applying Lemma 4.12 to it, the set of conjugates of over is inter-algebraic with , and .
We add to the base, and take , , . Then is an enhanced group configuration satisfying the conclusion of the lemma. ∎
Lemma 4.14.
Let be an enhanced group configuration with . Then, applying finitely many base changes and inter-algebraic replacements, it can be transformed to a configuration
such that and are interdefinable over . (Notice that and remain unchanged.)
Proof.
Applying Lemma 4.13, after a base change and an inter-algebraic replacement we may assume .
Next observe that, since , the tuple is also an enhanced group configuration.
By Lemma 4.13, after a base change, it is -equivalent to a configuration with and . Thus after an inter-algebraic replacement we may assume that and .
Finally, observe that is an enhanced group configuration.
Applying the proof of Lemma 4.13 to it, after base change to an independent copy of , let , let be the set of conjugates of over , equivalently over since . So .
Now since and (since this was satisfied on the previous step), we have . But then for any a conjugate of over , and so . We take , and . Then , and also , and the tuple satisfies the conclusion of the lemma. ∎
We can now finish Step 1.
Let be an expanded abelian -gon. Let and
It is easy to check that is an enhanced group configuration.
Applying Lemma 4.14, after a base change it is -equivalent to an enhanced group configuration such that and are interdefinable over . Replacing with , respectively, and with we complete Step 1.
Reduction 1. From now on we assume that in the expanded abelian -gon we have that and are interdefinable over .
4.3. Step 2. Obtaining a group from an expanded abelian -gon.
As in Hrushovski’s Group Configuration Theorem, we will construct a group using germs of definable functions. We begin by recalling some definitions (see e.g. [bays2018geometric, Section 5.1]).
Let be a stationary type over a set . By a definable function on we mean a (partial) function definable over a set such that every element is in the domain of .
If and are two definable functions on , defined over sets and respectively, then we say that they have the same germ at , and write , if for all (equivalently, some) we have . We may omit and write if no confusion arises.
The germ of a definable function at is the equivalence class of under this equivalence relation, and we denote it by .
If and are stationary types over , we write if for some (any) representative of definable over and we have . We say that is invertible if there exists a germ and for some (any) representative definable over and we have . We denote by .
By a type-definable family of functions from to we mean an -definable family of functions and a stationary type over such that for any the function is a definable function on , and for any we have . We will denote such a family as , and the family of the corresponding germs as .
Let be stationary types over and a type-definable family of functions. This family is generically transitive if for any (equivalently, some) and . This family is canonical if for any we have .
We now return to our expanded abelian -gon .
Let for , and let .
Since and are interdefinable over and , there exists a formula such that
for some , and also
It follows that gives a type-definable family of invertible germs with .
Remark 4.15.
Let , and . By stationarity of types over we then have , and as has a unique solution this implies , so , and .
In particular is a generically transitive invertible family.
Consider the equivalence relation on the set of realizations of given by . By the definability of types it is relatively definable, i.e. it is an intersection of an -definable equivalence relation with . Assume with . We choose and let . By the choice of we have , hence and are inter-algebraic over . Since it follows that and are inter-algebraic over : as and implies , hence ; and similarly . Hence the -class of is finite. Replacing by , if needed, we will assume that the family is canonical.
We now consider the type-definable family of germs , . Again let be a relatively definable equivalence relation on defined as if and only if . Let be the type . We then have (by e.g. [MR2264318, Remark 3.3.1(1)]) a canonical family of germs such that for every there is unique with . We will denote this as . Clearly , and .
Lemma 4.16.
For any and we have and .
Proof.
It is sufficient to prove the lemma for some . We take from our abelian expanded -gon and let . Let .
Let and . We have an enhanced group configuration
In particular form a group configuration over , i.e. we have a group configuration
where any three distinct collinear points form a triangle over , and any three distinct non-collinear points form an independent set over .
It follows from the proof of the Group Configuration Theorem (e.g. see Step (II) in the proof of [bays2018geometric, Theorem 6.1]) that and .
We also have , hence , and as this implies , which together with implies . Hence and . ∎
This shows that the families of germs satisfy the assumptions of the Hrushovski-Weil theorem for bijections (see [bays2018geometric, Lemma 5.4]), applying which we obtain the following.
-
(a)
The family of germs is closed under generic composition and inverse, i.e. for any independent there exists with , and also there is with .
-
(b)
There is a type-definable connected group and a type-definable set with a relatively definable faithful transitive action of on that we will denote by , so that , and the action are defined over the empty set.
-
(c)
There is a definable embedding of into as its unique generic type, and a definable embedding of into as its unique generic type, such that the generic action of the family on agrees with that of on , i.e. for any and we have .
Reduction 2. Let be independent realizations of , and .
From now on we assume that is the generic type of a type-definable connected group , the group relatively definably acts faithfully and transitively on a type-definable set , the type is the generic type of , and generically the action of on agrees with the action of on , and , and the action are definable over the empty set.
4.4. Step 3. Finishing the proof
We fix an independent copy of , i.e. and .
We denote by the map given by . Note that is relatively definable over . Let
Note that by Claim 4.10 every tuple realizing is an -gon.
Notation 4.17.
For a tuple , and , we will denote by the tuple . For example, . We will typically omit the concatenation sign: e.g., for , and we denote by the tuple .
Also in the proof of the next proposition we let , , and continue using and to denote the corresponding -tuples.
Proposition 4.18.
For each there exists such that and .
We will choose such by reverse induction on . Before proving Proposition 4.18 we first establish the following lemma and its corollary that will provide the induction step.
Lemma 4.19.
For there exist , each realizing , such that
and .
Proof.
First we note that the condition can be relaxed to by stationarity of , since for and satisfying one of , , we have . Indeed, assume e.g. . We have and . By assumption
is an independent set, hence we obtain . Using we conclude . The other two cases are similar.
Let . Note that , hence all types over are stationary, and .
Then one verifies by basic forking calculus that
(4.1) |
is an enhanced group configuration over . Namely,
-
•
and are triangles over ;
-
•
and are triangles over ;
-
•
for any non-collinear triple in , the set given by it and is independent over .
In addition, and .
The triple is non-collinear, hence . Since
this implies . Since also , by stationarity of types over we have . Hence there exist , , such that the diagram
(4.2) |
is isomorphic over to the diagram (4.1). I.e., there is an automorphism of fixing (hence also ) and mapping (4.2) to (4.1).
It follows from the choice of the tuple , diagrams (4.1), (4.2) and their isomorphism over that and . Since we have . As , we have
Since all types over are stationary, this implies
hence there exists such that the diagram
(4.3) |
is isomorphic to the diagram (4.1) over .
A similar argument with the roles of the ’s and the ’s interchanged shows that , hence there exists such that the diagram
(4.4) |
is isomorphic to the diagram (4.1) over .
From the choice of and the isomorphisms of the diagrams we have
(4.5) |
We claim that . Indeed, as
we obtain , hence . As we have . Using we conclude
(4.6) |
As noted at the beginning of the proof, we have that , and we define as follows:
By (4.7), to conclude that in and finish the proof of the lemma it is sufficient to show that .
As , , and is an independent set, we have . Since (as is an -gon) we also have . It follows then that . Since, by Lemma 4.16, we have .
This concludes the proof of Lemma 4.19. ∎
Corollary 4.20.
For any , let with
Then there exist such that
and .
Proof.
It is sufficient to show that for any with , we have . Indeed, given any satisfying the conclusion of Lemma 4.19, we then have an automorphism of fixing with ; as the map is relatively definable over , it then follows that satisfy the requirements.
We have . As and each of is an -tuple from the corresponding -gon, we get . Also , as any realization of is an -gon, hence
As all types over the empty set are stationary, we conclude . ∎
We can now finish the proof of Proposition 4.18.
Proof of Proposition 4.18.
We start with . Applying Corollary 4.20 with , we obtain and with .
Applying Corollary 4.20 again with and we obtain and with .
Continuing this process with we obtain some
with . We take , which concludes the proof of the proposition. ∎
Proposition 4.21.
There exist such that , and .
Proof.
We choose with (possible by generic transitivity: as , hence by stationarity of types over ; and as , we can take to be the image of under the automorphism of sending to ). We also have ( and by the choice of , so ; as , we conclude ), hence by stationarity again.
Similarly , hence . By Lemma 4.16 we also have . By stationarity of this implies , so there exists some such that . Hence
equivalently
(4.8) |
In particular, .
We claim that . Since , and is an independent set, we have . Using we deduce . As , it implies that is an independent set. We have and . Using independence of we obtain . Since , we have that , hence is an independent set and . As we can conclude .
It also follows from (4.8) that
We let
To show that and finish the proof of the proposition it is sufficient to show that .
Since , (by Remark 4.15, as by the above we have and ) and , we obtain . Using we deduce , hence . It follows then that and, as , we obtain . ∎
Combining Propositions 4.21 and 4.18, we obtain some such that each is inter-algebraic with over and
Obviously each is also inter-algebraic over with .
Thus, after a base change to and inter-algebraically replacing with , with , and with for , and using that permuting the elements of an abelian -gon we still obtain an abelian -gon, we achieve the following.
Reduction 3. We may assume that realize the generic type of a connected group that is type-definable over the empty set, with .
To finish the proof of Theorem 4.6 it only remains to show that the group is abelian. We deduce it from the Abelian Group Configuration Theorem, more precisely [bays2017model, Lemma C.1].
Claim 4.22.
Let be a connected group type-definable over the empty set, and are generic elements of such that form an abelian -gon and . Then the group is abelian.
Proof.
Let . We have that are generics of over , and they form an abelian -gon over . Since is inter-algebraic over with , we have that form an abelian -gon over . Let . We have , hence
By [bays2017model, Lemma C.1], the group is abelian. ∎
5. Main theorem in the stable case
Throughout the section we work in a complete theory in a language . We fix an -saturated model of , and also choose a large saturated elementary extension of . We say that a subset of is small if . Given a definable set in , we will often view it as a definable subset of , and sometimes write explicitly to denote the set of tuples in realizing the formula defining .
5.1. On the notion of -dimension
We introduce a basic notion of dimension in an arbitrary theory imitating the topological definition of dimension in -minimal structures, but localized at a given tuple of commuting definable global types. We will see that it enjoys definability properties that may fail for Morley rank even in nice theories such as .
Definition 5.1.
If is a definable set in and is a family of subsets of , we say that is a definable family (over a set of parameters ) if there exists a definable set and a definable set (both defined over ) such that , where is the fiber of at .
Definition 5.2.
-
(1)
By a -pair we mean a pair where is an -definable set and is an -definable stationary type on .
-
(2)
Given , we say that is a -system if each is a -pair and the types commute, i.e. for all .
Example 5.3.
Assume is a stable theory, are arbitrary types over and are arbitrary definable sets. By local character we can choose a model with such that each is definable (and stationary) over and are definable over . The types automatically commute in a stable theory. Hence, naming the elements of by constants, we obtain a -system.
Assume now that is a -system. Given , we let be the projection map. For , we let . Given with , and , we write to denote the tuple with for and for . Given , and , we write to denote the fiber of above .
Example 5.4.
If is a definable family of subsets of and , then and are definable families of subsets of (over the same set of parameters).
Definition 5.5.
Let and a small subset of .
-
(1)
We say that is -generic in over if .
-
(2)
-
(a)
For we write if for some with the tuple is -generic (with respect to the corresponding -system ).
-
(b)
As usual, we define if and it is not true that .
-
(a)
-
(3)
If and , we write for some (equivalently, any) .
-
(4)
For a subset definable over , we define
note that this does not depend on the set such that is -definable.
-
(5)
As usual, for a definable subset we say that is a -generic subset of if (equivalently, is contained in )
If we will omit it.
Remark 5.6.
It follows from the definition that for a definable set , is the maximal such that the projection of onto some coordinates is -generic. As usual, for a definable and small we say that an element is generic in over if .
Remark 5.7.
It also follows that if is an arbitrary -saturated model and is the unique definable extension, for , then is a -system in , and for every definable subset in we have , where the latter is calculated in with respect to this -system.
Claim 5.8.
Let be a definable (over ) family of subsets of and . Then the family
is definable (over as well).
Proof.
Assume that for some definable and definable . Given , let , it suffices to show that is definable. As every is definable, for every , the type is also definable. In particular, there is a definable (over any set of parameters containing the parameters of and ) set such that for any , . Then is definable as
The following lemma shows that -dimension is “super-additive”.
Lemma 5.9.
Let be definable and . Assume that is such that for every we have . Then .
Proof.
Assume that is definable over a small set of parameters , and let . Then there is some such that
Let . As , there exist some so that . Then by assumption , that is for some with we have . Let , and let . Since the types are stationary and commuting, it follows that for . As , there exists some so that , hence . Thus , hence , and — which shows that , as required. ∎
5.2. Fiber-algebraic relations and -irreducibility
Definition 5.10.
Given a definable set and a small set of parameters so that is defined over , we say that is -irreducible over if there do not exist disjoint sets definable over with and .
We say that is absolutely -irreducible if it is irreducible over any small set such that is defined over .
Remark 5.11.
It follows from the definition of -dimension that a definable set is -irreducible over if and only if any two tuples generic in over have the same type over .
Lemma 5.12.
If is fiber-algebraic of degree , then the set
has cardinality at most .
Proof.
Assume towards a contradiction that are pairwise different types in this set. Then there exist some formulas with parameters in such that and for all . Let be the (finite) set of the parameters of and . For each , as , we have , which by definition of -dimension implies for at least one . By pigeonhole, there must exist some and some such that and for all . Now let be a tuple in satisfying . By the choice of , for each there exists some in such that holds. By the choice of the formulas , the elements are pairwise distinct, and — contradicting that is fiber-algebraic of degree . ∎
Corollary 5.13.
Every fiber-algebraic of degree is a union of at most absolutely -irreducible sets (which are then automatically fiber-algebraic, of degree ).
Proof.
Lemma 5.14.
If is -irreducible over a small set of parameters and , then for any and any tuple which is -generic in over (i.e. ), if is consistent then it implies a complete type over .
Proof.
Otherwise there exist two types such that and for both . Then there exist some formulas with parameters in such that , and . In particular, by assumption on ,
for both — contradicting irreducibility of over .∎
5.3. On general position
We recall the notion of general position from Definition 1.5, specialized to the case of -dimension.
Definition 5.15.
Let be a -pair, and let be a definable family of subsets of . For , we say that a set is in -general position if for every with we have .
We extend this notion to cartesian products of -pairs.
Definition 5.16.
For sets and an integer , by an -grid on we mean a set of the form with and for all .
Definition 5.17.
Let and , , be -pairs. Let be a definable system of subsets of , , i.e. where each is a definable family of subsets of . For , we say that a grid on is in -general position if each is in -general position.
We will need a couple of auxiliary lemmas bounding the size of the intersection of sets in a definable family with finite grids in terms of their -dimension.
Lemma 5.18.
Let , a -system, and a definable family of subsets of such that for every . Then there is a definable system of subsets such that: for any finite grid on in -general position and any we have .
Proof.
Assume that is a definable family of subsets with for all . For and , we let , note that still . Let , we claim that then satisfies the requirements.
Indeed, let be a finite grid on in -general position. Let be arbitrary. As with , by assumption we have for every . As , we have
hence , as required. ∎
Lemma 5.19.
Let and be a -system, and a definable family of subsets of . Assume that for some we have for every . Then there is a definable system of subsets of such that: for any and any -grid on in -general position, for every we have .
Proof.
Given and , we let be the smallest number in (if it exists) so that the bound holds (with respect to all possible -systems and definable families ). We will show that for all and .
For any and , the claim holds by Lemma 5.18 with . For any and , the claim trivially holds with (and ).
We fix and assume that the claim holds for all pairs with either or . Assume that for every . Given , let . Then is a definable family of subsets of by Claim 5.8. By assumption and Lemma 5.9 we have for every . Let
Both and (by Claim 5.8) are definable families of subsets of , all sets in have -dimension , and all sets in have -dimension . Applying the -induction hypothesis, let be a definable system of subsets of satisfying the conclusion of the lemma with respect to . Applying the -induction hypothesis, let be a definable system of subsets of satisfying the conclusion of the lemma with respect to . We let be a definable system of subsets of , with defined above and for .
Let now and be a finite grid on in -general position. Let be arbitrary. As , we have in particular that , and by the choice of , for every we have . And by the choice of , for every , we have . Combining, we get
This establishes a recursive bound on . Given , we can repeatedly apply this recurrence for , and using that for all we get that
for any . Using that for all and iterating this inequality for , it is not hard to see that for all . ∎
5.4. Main theorem: the statement and some reductions
From now on we will assume additionally that the theory is stable and eliminates imaginaries, i.e. (we refer to e.g. [tent2012course] for a general exposition of stability). As before, is an -saturated model of , is a monster model of , and we assume that is a -system in , with each non-algebraic. “Definable” means “definable with parameters in ”. As usual, if is a definable set, a family of subsets of is definable if there exist definable sets so that .
Remark 5.20.
Note that if is a fiber-algebraic relation of degree , then for any -grid we have
Definition 5.21.
Let be a definable family of subsets of .
-
(1)
Given a real , we say that admits -power saving if there exist definable families on , such that for and any , for any -grid on in -general position and any we have
-
(2)
We say that admits power saving222We are following the terminology in [Bays]. if it admits -power saving for some .
-
(3)
We say that a relation admits -)power saving if the family does.
-
(4)
We say that is special if it is fiber-algebraic and does not admit power-saving.
Lemma 5.1.
Assume are definable families of subsets of and is such that each satisfies -power saving. Assume that for every , for some . Then also satisfies -power saving.
Proof.
Assume each satisfies -power saving, i.e. there exist definable families on and functions so that letting , for every grid in -general position and every we have . Let , and . Then for every grid in -general position and every we have , as required. ∎
We recall Definition 1.6, specializing to -dimension.
Definition 5.22.
Let be a definable relation and a type-definable group in (over a small set of parameters ). We say that is in a -generic correspondence with (over ) if there exist elements such that:
-
(1)
;
-
(2)
are independent generics in over (in the usual sense of stable group theory);
-
(3)
for each there is a generic element realizing and inter-algebraic with over , such that .
Remark 5.23.
If is -irreducible over , then (3) holds for all satisfying (1) and (2), providing a definable generic finite-to-finite correspondence between and the graph of the -fold multiplication in .
The following is the main theorem of the section characterizing special fiber-algebraic relations in stable reducts of distal structures.
Theorem 5.24.
Assume that is an -saturated -structure, and is stable and admits a distal expansion. Assume that , is a -system with each non-algebraic and is a definable fiber-algebraic relation. Then at least one of the following holds.
-
(1)
admits power saving.
-
(2)
is in a -generic correspondence with an abelian group type-definable in over a set of parameters of cardinality .
The only property of distal structures actually used is that every definable binary relation in satisfies the -ST property (Definition 2.12) for some , by Proposition 2.14 and Fact 2.4. In fact, Theorem 5.24 follows from the following more precise version with the additional uniformity in families and explicit bounds on power saving.
Definition 5.25.
Let be a definable family of subsets .
-
(1)
We say that is a fiber-algebraic family if each is fiber-algebraic.
-
(2)
We say that is an absolutely -irreducible fiber-algebraic family if each is -irreducible and fiber-algebraic
Remark 5.26.
Let be a definable fiber-algebraic family. By saturation of there is such that every has degree . In this case we say that is of degree .
Theorem 5.27.
Assume that is an -saturated -structure and is stable. Assume that , is a -system with each non-algebraic, and let be a fiber-algebraic definable family, and fix .
-
•
If , assume that there exist and definable families of absolutely -irreducible sets so that for every we have for some . Assume also that for each , the family viewed as a definable family of subsets of satisfies the -ST property.
-
•
If , for each and as above, we additionally consider the definable family of subsets of , where
Assume moreover that there exist and definable families for so that for every we have for some . Assume also that for each , the family viewed as a definable family of subsets of satisfies the -ST property.
Then there is a definable subfamily such that the family admits -power saving, and for each the relation is in a -generic correspondence with an abelian group type-definable in over a set of parameters of cardinality .
To see that Theorem 5.24 follows from Theorem 5.27, assume that a definable relation is as in Theorem 5.24, and consider the definable family consisting of a single element . By Proposition 2.14 and Fact 2.4 every definable family of binary relations in satisfies the -ST property (Definition 2.12) for some . Moreover, by Corollary 5.13, if is definable and fiber-algebraic of degree , we have for some definable absolutely -irreducible sets . By distality, each satisfies the -ST-property for some . Hence, taking , and , the assumption of Theorem 5.27 is satisfied for . If , note that each is still fiber-algebraic of degree , hence each is fiber-algebraic, of degree by Lemma 5.44. By Corollary 5.13 again, for each we have for some definable absolutely -irreducible sets , each satisfying the -ST-property for some . Hence, taking , and , the assumption of Theorem 5.27 is satisfied for . In either case, let be as given by applying Theorem 5.27. If , then is in Case (1) of Theorem 5.24. Otherwise , and is in Case (2) of Theorem 5.24.
In the rest of the section we give a proof of Theorem 5.27 (which will also establish Theorem 5.24). In fact, first we will prove a special case of Theorem 5.27 for definable families of absolutely -irreducible sets and (Theorem 5.31), and then derive full Theorem 5.27 from it in Section 5.6 (for ) and Section 5.7 (for ). We begin with some auxiliary observations and reductions.
Assumption 1.
For the rest of Section 5, we assume that (even though some of the results below make sense for ), is -saturated, is a -system with each non-algebraic, and is a -definable. “Definable” will mean “definable with parameters in ”
Lemma 5.28.
If is fiber-algebraic then .
Proof.
Let , where is some finite set such that is -definable. The type is non-algebraic by Assumption 1, and has at most solutions. Hence necessarily
so . ∎
The following is straightforward by definition of fiber-algebraicity.
Lemma 5.29.
Let be a fiber-algebraic relation of degree and with . Let be the projection from onto . Let be a grid on . Then
Proposition 5.30.
Let be a definable family of fiber-algebraic subsets of . Let with . Assume that for every the projection onto is not -generic. Then admits -power saving.
Proof.
By Lemma 5.19 there exists a definable system of subsets of such that for any , for any -grid on in -general position, for any we have . Let be such that is of degree . Taking for , let . Then by Lemma 5.29, for any -grid on in -general position, for any we have , hence the family admits -power saving. ∎
The following is the main theorem for definable families of absolutely irreducible sets:
Theorem 5.31.
Assume that is an -saturated -structure and is stable. Assume that , is a -system with each non-algebraic, and let be a fiber-algebraic definable family of absolutely -irreducible subsets of . Assume that for some , for each , viewed as a definable family of subsets of satisfies the -ST property. Then there is a definable subfamily such that the family admits -power saving, and for each the relation is in a -generic correspondence with an abelian group type-definable in over a set of parameters of cardinality .
We fix a fiber-algebraic definable family of absolutely -irreducible subsets of .
Let be the set of all such that for some with for the projection of onto we have .
By Claim 5.8, the family is definable and it follows from Proposition 5.30 that the family admits -power saving. Hence replacing with , if needed, we will assume the following:
Assumption 2.
is a fiber-algebraic definable family of absolutely -irreducible subsets of . For any the projection of onto any coordinates is -generic. In particular, (by Lemma 5.28).
Proposition 5.32.
Let be a small set in , and let be a -generic in over (see Remark 5.6 for the definition). Then for any we have
Proof.
Since is absolutely -irreducible, it has unique -generic type over . By our assumption for any the projection of onto is -generic. Hence any realization of can be extended to a -generic of . ∎
Next we observe that the assumption that the projection of onto any coordinates is -generic in Proposition 5.32 was necessary, but could be replaced by the assumption that does not admit -power saving (this will not be used in the proof of the main theorem).
Proposition 5.33.
Assume that is absolutely -irreducible, (but no assumption on the projections of ), and does not admit -power saving. Let be a small set in and let be a generic in over . Then for any we have
Proof.
Let be a generic in over . Permuting the variables if necessary and using that the types commute, we may assume
We only consider the case , i.e. we need to show that
the other cases are analogous.
Assume this does not hold, then there is a relation definable over such that and .
Since is -irreducible over , the formula implies a complete type over by Lemma 5.14. Hence we have
so in particular
which implies
Then, by saturation of , there exists some -generic set definable over (given by a finite conjunction of formulas from ) such that
hence
Let and . Then and . Thus is covered by the union of and , each with -power saving by Proposition 5.30, which implies that admits -power-saving. ∎
Remark 5.34.
The assumption that has no -power saving is necessary in Proposition 5.33, and the assumption that the projection of onto any coordinates is -generic in necessary in Proposition 5.32. For example let and assume is the graph of a bijection from to some -definable set with . Then is clearly fiber algebraic, absolutely -irreducible, with . But for a generic , does not realize . Note that has -power saving. Indeed, let with . Then, given any and an -grid in -general position, as we must have , hence, by definition of , . Also note that is not -generic.
We can now state the key structural dichotomy at the core of Theorem 5.31:
Theorem 5.35.
Let be a definable family of absolutely -irreducible fiber-algebraic subsets of satisfying the Assumption 1 above. Assume the family , as a family of binary relations on
satisfies the -ST property for some .
Then there is a definable such that the family , admits -power-saving, and for every , for every tuple generic over there exists some tuple
of length at most such that
Remark 5.36.
Theorem 5.35 is trivial for with , as always holds with .
First we show how the above theorem, combined with the reconstruction of abelian groups from abelian -gons in Theorem 4.6, implies Theorem 5.31. Then we use theorem Theorem 5.31 to deduce Theorem 5.24 for (along with the bound in Theorem 5.27) in Section 5.6. The case of Theorem 5.24 requires a separate argument reducing to the case of Theorem 5.24 given in Section 5.7.
Proof of Theorem 5.31.
From the reductions described above, we assume that and satisfy Assumptions 1 and 2, and that for some , for each , viewed as a definable family of subsets of satisfies the -ST property.
It follows that for every permutation of , the family and the -system obtained from and by permuting the variables accordingly still satisfy the assumption of Theorem 5.35. Applying Theorem 5.35 to every permutation of , and taking (definable) to be the union of the corresponding ’s, we have that the family admits -power saving and for any , for every tuple generic in over , after any permutation of we have
Together with fiber-algebraicity of this implies that is an abelian -gon over .
Applying Theorem 4.6, we obtain that for any there exists a small set and a connected abelian group type-definable over and such that is in a -generic correspondence with over . (As stated, Theorem 4.6 only guarantees the existence of an appropriate set of parameters of size and in , however by -saturation of there exists a set in with the same type as , hence we obtain the required group applying an automorphism of sending to .) ∎
In the remainder of the section we prove Theorem 5.35.
5.5. Proof of Theorem 5.35
Let and . We view each as a binary relation .
We fix a formula such that for the formula defines , with the variables corresponding to and to .
We also fix such that is of degree .
Definition 5.37.
For and , let be the set
Claim 5.38.
The family is a definable family of subsets of .
Proof.
Claim 5.39.
For any and , we have that if and only if , if and only if .
Proof.
Let and . As is fiber-algebraic, we also have that the binary relation is fiber-algebraic, hence (by Lemma 5.28). The claim follows as, by definition of -dimension, for any . ∎
Claim 5.40.
For every and the set is fiber-algebraic, of degree .
Proof.
We fix and . Assume . Since is fiber-algebraic of degree (by fiber-algebraicity of ), the set of types with and is finite, of size (by Lemma 5.12); and for any we have if and only if belongs to one of these types (by definition of -dimension). Thus
Let list all types in . We then have , where . It is sufficient to show that each is fiber-algebraic of degree . Choose a realization of in . Obviously . As and , the set is fiber-algebraic of degree , hence the set is fiber-algebraic of degree as well. ∎
Definition 5.41.
Let be the set
Note that the family is definable by Claim 5.8.
Let . By Claim 5.8 the set is definable. We will show that the family admits -power saving for the required .
To show that the family admits -power saving, it suffices to show that both families and admit -power saving, where is the complement of in .
Since for any the set is not a -generic subset of , for the projection we have that is not a -generic subset of . Hence, by Proposition 5.30, the family admits -power saving.
Next we show that the family admits -power saving. By the definition of , for any and we have . By Lemma 5.19, there is a definable system of sets on such that for any -grid in -general position we have
for any and .
Applying Lemma 5.18 to the definable family
we obtain that there is a definable system of sets on such that for any -grid in -general position and any we have
Then is a definable system of sets on .
Let be an -grid on in -general position and . We need to estimate from above . Let and , then and . Let be viewed as a binary relation on , we have
so it suffices to obtain the desired upper bound on .
From the -general position assumption and the choice of we have: for any there are at most elements such that .
By assumption on the definable family of subsets of satisfies the -ST property, and let be as given by Definition 2.12 for . Then we have (independently of ), as required.
Thus the family admits -power saving.
We now fix .
By absolute irreducibility of and Remark 5.11 it is sufficient to show that there exists a tuple generic over and some tuple of length at most such that
We add to our language if needed and assume that .
By -saturation of , let be a tuple in which is -generic in , namely with (note that is -definable). Let be a model containing with .
Let be a -generic point in over , i.e. and .
Let be a tuple in with . Without loss of generality we assume that , namely . Note that such and can be chosen in by -saturation.
We now collect some properties of and .
Claim 5.42.
-
(1)
is generic in over .
-
(2)
and .
-
(3)
.
-
(4)
is generic in over .
Proof.
(1) We have, by our assumption above, that , hence in particular . Since we have (as using that the types commute). Since is fiber-algebraic and , we also have by Lemma 5.28.
(2) Since is generic in over by (1), by Proposition 5.32 we have .
(3) As and , we have .
(4) We have . Since and , we have (as by stationarity of non-forking over models), hence in particular . Also, since by (2), we have . Since is fiber-algebraic we also have , hence . ∎
Let and , both are definable types over by stability.
We choose canonical bases and of and , respectively; i.e. are tuples of length in , and for any automorphism of we have if and only if (pointwise); and if and only if .
Note that does not fork over and does not fork over .
Claim 5.43.
We have:
-
(a)
;
-
(b)
;
-
(c)
;
-
(d)
.
Proof.
(a) Assume not, then the orbit of under the automorphisms of fixing would be infinite. Hence we can choose a model containing with , and distinct types , each conjugate to under an automorphism of fixing .
Let . For each we choose such that . We have that , hence, by fiber-algebraicity, . But all are pairwise distinct types, a contradiction.
(b) Since , permuting variables if needed, we may assume that .
Assume (b) fails. Then we can find a model containing , and distinct types , each conjugate to under an automorphism of fixing . Let
in . For each we choose in such that
and get a contradiction as in (a).
(c) Since and does not fork over , we have , which by part (a) implies .
(d) Similar to (c). ∎
5.6. Proof of Theorem 5.27 for
Let be a definable family of subsets of satisfying the assumption of Theorem 5.27, and say is fiber-algebraic of degree . In particular, there exist and definable families of absolutely -irreducible subsets of , so that for every we have for some . Note that each is automatically fiber-algebraic, of degree . By assumption each satisfies the -ST property for some fixed , under any partition of the variables into two groups of size and .
For each , let the definable family be as given by Theorem 5.31 for . That is, for each the family admits -power saving, and for each the relation is in a -generic correspondence with an abelian group type-definable in over a set of parameters of cardinality . Consider the definable family
By Lemma 5.1, satisfies -power saving. On the other hand, from Definition 5.22, if , with , and at least one of the is in a -generic correspondence with a type-definable group, then is also in a -generic correspondence with the same group. Hence every element is in a -generic correspondence with a group type-definable over some .
5.7. Proof of Theorem 5.27 for ternary
In this subsection we reduce the remaining case of Theorem 5.27 to the case .
Let and a definable fiber-algebraic (say, of degree ) family of subsets of satisfy the assumption of Theorem 5.27 with some fixe . In particular, there exist and fiber-algebraic (of degree ) definable families of absolutely -irreducible subsets of , so that for every we have for some . By the same reduction as in Section 5.6, it suffices to establish the theorem separately for each , so we may assume from now on that additionally all sets in are absolutely -irreducible.
Consider the definable family of subsets of , where
Lemma 5.44.
The definable family of subsets of is fiber algebraic, of degree .
Proof.
We consider the case of fixing the first three coordinates of , all other cases are similar. Let , and be fixed. As is fiber algebraic of degree , there are at most elements such that ; and for each such , there are at most elements such that . Hence, by definition of , there are at most elements such that . ∎
Remark 5.45.
Note that with and is a -system with each non-algebraic.
The following lemma will be used to show that power saving for implies power saving for (this is a version of [StrMinES, Proposition 3.10] for families, which in turn is essentially [raz, Lemma 2.2]). We include a proof for completeness.
Lemma 5.46.
For any finite and , taking and we have
Proof.
Consider the (definable) set
and let . As usual, for arbitrary sets and , we denote by the fiber .
Note that and , which by the Cauchy-Schwarz inequality implies
For any tuple , the fiber has size at most by fiber algebraicity of . Hence , and so . ∎
Lemma 5.47.
Assume that and admits -power saving (with respect to the -system in Remark 5.45). Then admits -power saving for .
Proof.
By assumption there exist with definable families on and definable families on , and a function , such that for any and an -grid on in -general position we have .
We take , , , and .
Assume we are given and with in -general position. By the choice of it follows that the grid is in -general position, hence . By Lemma 5.46 this implies
Hence satisfies -power saving. ∎
We are ready to finish the proof of Theorem 5.27 (and hence of Theorem 5.24), the required bound on power saving follows from the proof.
Proof of Theorem 5.27 for .
By the reduction explained above we may assume that is a definable family of absolutely -irreducible sets and does not satisfy -power saving. Applying the case of Theorem 5.27 to the family (note that satisfies the assumption of Theorem 5.27 by the reduction above and since satisfies the assumption of Theorem 5.27), we find a definable subfamily such that the family admits -power saving, and for each the relation is in a -generic correspondence with an abelian group type-definable in over a set of parameters of cardinality .
Let be the set of all such that for some with for the projection of onto we have . By Claim 5.8, the family is definable and it follows from Proposition 5.30 that the family admits -power saving.
Consider the definable subfamily of . By Lemma 5.47, as , admits -power saving. On the other hand, if , then , hence there exists a small set and an abelian group type-definable over so that is in a -generic correspondence with .
This means that there exists a tuple so that , are independent generics over and a tuple so that each of the elements is -generic over and each of the pairs is inter-algebraic over .
By definition of there exists some such that and . We let and , and make the following observations.
-
(1)
(using that is abelian).
-
(2)
Each of the pairs is inter-algebraic over .
The pairs are inter-algebraic over by assumption. Note that and are inter-algebraic over as is fiber-algebraic, so it suffices to show that and are inter-algebraic over . By definition . Conversely, as , we have .
-
(3)
and are independent generics in over .
By assumption and is inter-algebraic with over , hence .
-
(4)
for all .
For : as and is inter-algebraic with over , we have , which by stationarity of implies .
For : as for and , it follows that and the tuple is generic in over (as by the choice of ). But then by the assumption on and Proposition 5.32 (can be applied by absolute irreducibility of and the choice of ).
It follows that is in a -generic correspondence with over , witnessed by the tuples and . ∎
5.8. Discussion and some applications
First we observe how Theorem 5.24, along with some standard facts from model theory of algebraically closed fields, implies a higher arity generalization of the Elekes-Szabó theorem for algebraic varieties over similar to [Bays]. Recall from [Bays] that a generically finite algebraic correspondence between irreducible varieties and over is a closed irreducible subvariety such that the projections and are generically finite and dominant (hence necessarily ). And assuming that and are irreducible algebraic varieties over , we say that and are in coordinate-wise correspondence if there is a generically finite algebraic correspondence such that for each , the closure of the projection is a generically finite algebraic correspondence between the closure of and the closure of .
Corollary 5.48.
Assume that , and and are irreducible algebraic varieties, with . Assume also that for each , the projection is dominant and generically finite. Let , . Then one of the following holds.
-
(1)
For every there exist and such that: for any and finite such that for every algebraic subsets of of dimension and degree , we have
for if , and if .
-
(2)
There exists a connected abelian complex algebraic group with such that is in a coordinate-wise correspondence with
The above Corollary 5.48 immediately follows from the following slightly more general statement:
Corollary 5.49.
Assume that , and are irreducible algebraic varieties with , and let be a definable family of subsets of , each of Morley degree . Assume also that for each , , the projection is Zariski dense and is generically finite to one. Then there is a definable family such that:
-
(1)
admits -power saving for if , and if .
-
(2)
For every there exists a connected abelian complex algebraic group with such that for some independent generics and generic we have that is inter-algebraic with for and inter-algebraic with .
It is not hard to see that Corollary 5.49 implies 5.48. Indeed, if is an irreducible variety then it has Morley degree one. Let be the family of all irreducible algebraic varieties contained in of degree , Morley rank and with all projections Zariski dense and generically finite to one. It is a definable family in by definability of Morley rank and irreducibility (see e.g. [freitag2017differential, Theorem A.7]), defined by a formula depending only on ; and . Applying Corollary 5.49 we can conclude depending on whether or .
Proof of Corollary 5.49.
Let , then and is an -saturated structure. We recall that is a strongly minimal structure, in particular it is -stable and has additive Morley rank coinciding with the Zariski dimension (see e.g. [MR1678602]).
For each , as is irreducible, i.e. has Morley degree , let be the unique type in with . By stability, types are definable, commute and are stationary after naming a countable elementary submodel of so that all of the ’s are defined over it.
Hence is a -system; and by the additivity of Morley rank we see that for any definable .
For any , since the projection of onto is Zariski dense and generically finite, we have .
Let be a definable set with . Since and have the same generic points, the item (2) is equivalent for and . Obviously -power saving for implies -power saving for , and we observe that -power saving for with implies -power saving for . Let . Then, as has Morley degree , , hence . Applying Lemma 5.19 to we obtain that has -power saving. Since , it follows that also has -power saving.
As by assumption every has generically finite projections, after removing a subset of smaller Morley rank we may assume that is fiber-algebraic. This can be done uniformly for the family by [freitag2017differential, Theorem A.7] (however, on this step we have to pass from a family of algebraic sets to a family of constructible sets, that is why we can only use bounds from Corollary 2.16(2) but not from Fact 2.17 in the following), hence we may assume that the family consists of fiber algebraic sets of fixed degree.
As , it follows that has a generically finite-to-one projection onto , hence, after possibly a coordinate-wise correspondence, we may assume that — again, uniformly for the whole family . By Corollary 2.16(2), every definable family of sets satisfies the -ST property. Applying Theorem 5.27 (we are using once more that irreducible components are uniformly definable in families in , see [freitag2017differential, Theorem A.7]) we find a definable subfamily with -power saving for the stated .
Every type-definable group in is actually definable (by -stability, see e.g. [MR1924282, Theorem 7.5.3]), and every group interpretable in an algebraically closed field is definably isomorphic to an algebraic group (see e.g. [MR1678602, Proposition 4.12 + Corollary 1.8]). Thus, for , there exists an abelian connected complex algebraic group , independent generic elements and such that and generic inter-algebraic with , such that . In particular, . And, by irreducibility of , hence uniqueness of the generic type, such ’s exist for any independent generics . As the model-theoretic algebraic closure coincides with the field-theoretic algebraic closure, by saturation of this gives the desired coordinate-wise correspondence. ∎
Remark 5.50.
Failure of power saving on arbitrary grids, not necessarily in a general position, does not guarantee coordinate-wise correspondence with an abelian group in Corollary 5.48. For example, let be the Heisenberg group of matrices over , viewed as a definable group in . For , consider the subset of given by
It is not hard to see that . For the definable fiber-algebraic relation on given by we have .
However, is not in a generic correspondence with an abelian group. Indeed, the sets are not in an -general position for any , with respect to the definable family of subsets of .
However, restricting further to the case for all , the general position requirement is satisfied automatically: for any definable set , if and only if is finite; and for every definably family of subsets of there exists some such that for any , if has cardinality greater than then it is infinite. Hence (using the classification of one-dimensional connected complex algebraic groups) we obtain the following simplified statement.
Corollary 5.51.
Assume , and let be an irreducible algebraic variety so that for each , the projection is generically finite. Then exactly one of the following holds.
-
(1)
There exist depending only on such that: for any and we have
for if , and if .
-
(2)
For one of , or an elliptic curve, is in a coordinate-wise correspondence with
Remark 5.52.
We expect that the two cases in Corollary 5.48 are not mutually exclusive (a potential example is suggested in [breuillard2021model, Remark 7.14]), however they are mutually exclusive in the -dimensional case in Corollary 5.51. The proof of this for is given in [StrMinES, Proposition 1.7], and the argument generalizes in a straightforward manner to an arbitrary .
We remark that the case of complex algebraic varieties corresponds to a rather special case of our general Theorem 5.24 which also applies e.g. to the theories of differentially closed fields or compact complex manifolds (see Facts 2.20 and 2.21). For example:
Remark 5.53.
Given definable strongly minimal sets and a fiber-algebraic in a differentially closed field of characteristic , we conclude that either has power saving (however, we do not have an explicit exponent here, see Problem 2.22), or that is in correspondence with one of the following strongly minimal differential-algebraic groups: the additive, multiplicative or elliptic curve groups over the field of constants of , or a Manin kernel of a simple abelian variety that does not descend to (i.e. the Kolchin closure of the torsion subgroup of ; we rely here on the Hrushovski-Sokolovic trichotomy theorem, see e.g. [MR3641651, Section 2.1]).
6. Main theorem in the -minimal case
6.1. Main theorem and some reductions
In this section we will assume that is an o-minimal, -saturated -structure expanding a group (or just with definable Skolem functions). We shall use several times the following basic property of o-minimal structures:
Fact 6.1.
[peterzil2019minimalist, Fact 2.1] Assume that and are small sets. For every definable open neighborhood of (defined over arbitrary parameters), there exists , -independent from over , and a -definable open containing . In particular, and .
For the rest of the section we assume that and for , we have -definable sets with for all (throughout the section, refers to the standard notion of dimension in -minimal structures). We also have an -definable set , with , and such that is fiber algebraic of degree , for some (see Definition 1.4).
Definition 6.2.
For , we say that satisfies -power saving if there are definable families , where each consists of subsets of of dimension smaller than , such that for every there exists a constant such that: for every and every -grid in -general position (i.e. for every and we have ) we have
It is easy to verify that if satisfy -power saving then so does . Before stating our main theorem in the -minimal case, we define:
Definition 6.3.
Given a finite tuple in an o-minimal structure , we let be the infinitesimal neighborhood of , namely the intersection of all -definable open neighborhoods of . It can be viewed as a partial type over , or we can identify it with the set of its realizations in an elementary extension of .
Theorem 6.4.
Under the above assumptions, one of the following holds.
-
(1)
The set has -power saving, for if , and if .
-
(2)
There exist (i) a tuple in generic in , (ii) a substructure of of cardinality (iii) a type-definable abelian group of dimension , defined over and (iv) -definable bijections , sending to , such that
for all .
We begin working towards a proof of Theorem 6.4.
Notation
-
(1)
For , we write for the set .
-
(2)
For and we write
We similarly write , for and .
Lemma 6.5.
The following are easy to verify:
-
(1)
For every , .
-
(2)
If is generic in then for every neighborhood of , and .
We will need to consider a certain local variant of the property (P2) from Section 3.2.
Definition 6.6.
Assume that .
-
•
We say that has the property near if for all and neighborhoods of respectively,
(6.1) and there are open neighborhoods in such that
(6.2) (namely, for every and , if then ).
-
•
We say that satisfies the -property near , for , if the above holds under the coordinate permutation of and , respectively.
-
•
We say that satisfies the -property near if it has the -property for all .
Remark 6.7.
Note that if satisfy (6.2), then also every and satisfy it. Note also that under the above assumptions, we have .
Definition 6.8.
-
•
Let be the set of all such that satisfies near .
-
•
Let be the set of all near which satisfies .
Clearly, and are -definable sets.
The main ingredient towards the proof of Theorem 6.4 is the following:
Theorem 6.9.
Assume that does not satisfy -power saving for as in Theorem 6.4(1). Then .
6.2. The proof of Theorem 6.9
The following is an analog of Lemma 5.19 in the -minimal setting.
Lemma 6.10.
Let be a definable family of subsets of , each fiber-algebraic of degree with . Then there exist definable families , , each consisting of subsets of of dimension smaller than , such that for every , if is an -grid in -general position then for every ,
In particular, each satisfies -power saving.
Proof.
For and we let
For , we similarly define
(1) For , we let
By our assumption on , . Let .
(2) For and , let
Then define Note that whenever , and therefore the set has dimension smaller than .
For , we continue in this way to define a family of subsets of as follows: for , , , we let
and let
Finally, for such that for , we let
and let
We provide some details on why the families satisfy the requirement.
Assume that and is an -grid which is in -general position, and fix .
Because there are at most elements , and for each such there are at most elements in which project to it. Indeed, this is true because is fiber-algebraic of degree , so for every tuple (and there are at most such tuples) there are elements such that .
So, altogether there are at most elements for which . On the other hand, there are at most elements . We now compute for how many we have .
By definition, , so now we consider two cases, and . In the first case, there are at most such , by general position, and as above, for each such there are at most tuples such that . Thus all together there are elements such that and . There are at most elements which are not in . Of course, there are at most pairs such that and , and we now want to compute how many project onto such . Repeating the same process along the other coordinates, we see that there are at most elements which project into each such , so all together there are at most tuples for which and . If we add it all we get at most elements in , which concludes the proof of the lemma. ∎
Corollary 6.11.
Assume that does not satisfy -power saving and that is a definable set with . Then also does not satisfy -power saving.
Proof.
Indeed, Lemma 6.10 (applied to the constant family) implies that itself satisfies -power saving, and since -power saving is preserved under union then it fails for . ∎
In order to prove Theorem 6.9, it is sufficient to prove the following:
Proposition 6.12.
Let be a definable set and assume that there exist such that . Then satisfies -power saving for as in Theorem 6.4(1).
Let us first see that indeed Proposition 6.12 quickly implies Theorem 6.9. Let be as in Theorem 6.4(1). Assuming that does not have -power saving, Proposition 6.12 with implies that . Also, if we take then clearly and therefore by the same proposition satisfies -power saving, and therefore does not satisfy -power saving. We can thus replace by and retain the original properties of together with the fact that has at every . Next we repeat the process with respect to every and eventually obtain a definable set of dimension such that satisfies at every point — establishing Theorem 6.9.
Proof of Proposition 6.12.
Let and be as in Proposition 6.12. It is sufficient to prove the proposition for (the case of arbitrary follows by permuting the coordinates accordingly). If then by Lemma 6.10 satisfies -power saving, hence -power saving. Thus we may assume that , and hence, by throwing away a set of smaller dimension, we may assume that is open in . It is then easy to verify that . Hence, without loss of generality, . We now assume that and therefore, by Lemma 6.10, has -power saving. Thus, in order to show that has -power saving, it is sufficient to prove that has -power saving, so we assume from now on that .
We let and .
Claim 6.13.
For every , the set
has dimension strictly smaller than . Moreover, the set is fiber algebraic in .
Proof.
We assume that relevant sets thus far (i.e. ) are defined over . Now, if (it is not hard to see that it cannot be bigger), then by -saturation of we may take generic in over , and then generic in over . Note that the fiber-algebraicity of implies that , and since it follows that is generic in both and over , so in particular, .
We claim that . Indeed, by our assumption,
Thus, there exists an open containing , such that , or, said differently, . By Fact 6.1, we may assume that the tuple is independent from the parameters defining over . Thus, without loss of generality, is definable over . The set is defined over and the set is defined over , and both contain . Since then . We can therefore find an open such that . Now, by the definition of , we have , and hence and therefore (since ), . This shows that , contradicting our assumption that .
To see that is fiber algebraic, assume towards contradiction that there exists a tuple for which there are infinitely many such that (the other coordinates are treated similarly). We can now pick such generic over and then pick generic over . Because it follows by the additivity of dimension that for any subtuple of we have . It follows that
Since holds, it follows that is infinite — contradicting the fiber-algebraicity of . ∎
We similarly have:
Claim 6.14.
For every , the set
has dimension strictly smaller than . Moreover, the set is fiber-algebraic in .
Lemma 6.15.
There exist definable families of subsets of , respectively, each containing only sets of dimension strictly smaller than , such that for every and every -grid in -general position, we have the following.
-
(1)
For all , if then .
-
(2)
For all , there are at most elements such that .
-
(3)
.
Proof.
We choose the definable families in as follows. Let
and . Clearly, each set in has dimension smaller than . Because is fiber algebraic of degree , it is easy to verify that (1) holds independently of the other families.
For the other families, we first recall that by Claim 6.13, for each , the set has dimension smaller than .
We now apply Lemma 6.10 to the family (note that from Lemma 6.10 is replaced here by ), and obtain definable families , each consisting of subsets of of dimension smaller than , such that for every and every -grid in -general position and every we have
Let and assume that is in -general position. It follows that for every there are at most elements such that . This proves (2).
We claim that the relation , viewed as a binary relation on , satisfies the -ST property. Indeed, for , let be an -minimal cell decomposition of , for some , we have . Then each (definable) cell is in a definable bijection with a definable subset of (namely, the projection on the appropriate coordinates is a homeomorphism), hence in a definable bijection with a definable subset of . For , let . Applying these definable bijections coordinate-wise, by Lemma 2.1(1) we may assume and apply Fact 2.15 to conclude that for each , satisfies the -ST property. But then, by Lemma 2.1(2), also satisfies the -ST property. Finally, given an -grid in -general position, we thus have by the -ST property that (2) implies (3).∎
6.3. Obtaining a nice -relation
By Theorem 6.9 we may assume that . Thus, in order to prove Theorem 6.4, we may replace by , and assume from now on that .
Using -minimal cell decomposition, we may partition into finitely many definable sets such that each is fiber-definable, namely for each tuple , there exists at most one
such that , and furthermore is a continuous function on its domain. We can do the same for all permutations of the variables. Since does not satisfy -power saving by assumption, one of these finitely many sets, of dimension , also does not satisfy -power saving.
Hence from now on we assume that is the graph of a continuous partial function from any of its variables to the remaining one.
By further partitioning and changing the sets up to definable bijections, we may assume that each is an open subset of . Fix in generic in , and let . Note that for each in a neighborhood of , the set is the graph of a homeomorphism between neighborhoods of and . We let (see Definition 6.3) and identify these partial types over with their sets of realizations in .
Lemma 6.16.
There exist -definable relatively open sets and , containing and , respectively, and a relatively open , containing , such that for every , .
In particular, for any and any we have
Proof.
Because the properties of and are first-order expressible over , it is sufficient to prove the existence of in any elementary extension of .
Because , there are definable, relatively open neighborhoods and of and , respectively, such that
By Fact 6.1, we may assume that are definable over such that is still generic in over . It follows that there exists a relatively open , containing , such that for every (so, and ), we have . As already noted, we now can find such and defined over .
Note that and , and . Let us see how the last clause follows: assume that , , and . We have , and
By the choice of , we thus have . ∎
Lemma 6.17.
The definable relation satisfies properties (P1) and (P2) from Section 3.2 with respect to the -type-definable sets , namely:
(P1) For any , there exists exactly one with , and this remains true under any coordinate permutation.
(P2) Let and . Then for every and ,
The same is true when is replaced by any with .
Proof.
By continuity of the function given by , for every tuple
there exists a unique such that . The same is true for any permutation of the variables. This shows (P1).
Property (P2) holds by Lemma 6.16 for the -coordinates. The same proof works for the other pairs . ∎
Let us see how Theorem 6.4 follows. Assume first that , and that does not have -power saving for . By Theorem 6.9 and the resulting Lemma 6.17 (see also the choice of the parameters before Lemma 6.16), there is generic in and a substructure of cardinality such that satisfies and of Theorem 3.21. Note that is a partial type over for , satisfies the relation, and is contained in . Thus, by the “moreover” clause of Theorem 3.21, there exists a type definable abelian group over and -definable bijections each sending to and satisfying:
for all . This is exactly the second clause of Theorem 6.4.
6.4. Discussion and some applications
We discuss some variants and corollaries of the main theorem. In particular, we will deduce a variant that holds in an arbitrary -minimal structure, i.e. without the saturation assumption on used in Theorem 6.4.
Definition 6.18.
(see [goldbring2010hilbert, Definition 2.1]) A local group is a tuple , where is a Hausdorff topological space, (the inversion map) and (the product map) are continuous functions, with and open subsets, such that , and for all :
-
(1)
;
-
(2)
if then and ;
-
(3)
if and , then
Our goal is to show that in Theorem 6.4 we can replace the type-definable group with a definable local group. Namely,
Corollary 6.19.
Let be an -saturated -minimal expansion of a group, , are -definable with , and is fiber algebraic. Then one of the following holds.
-
(1)
The set has -power saving, for if , and if .
-
(2)
There exist (i) a finite set and a structure (ii) a definable local abelian group with , defined over , (iii) definable relatively open , a definable open neighborhood of , and (iv) definable homeomorphisms , , such that for all ,
Proof.
We assume that (1) fails and apply Theorem 6.4 to obtain generic in , , a type-definable abelian group over , and bijections sending to , such that for all , and ,
By pulling back the group operations via, say, , we may assume that the domain of is . We denote this pull-back of the addition and the inverse operations by and , respectively. Let us see that and are continuous with respect to the induced topology on . Because is generic in , and is fiber algebraic, it follows from -minimality that the set defines a continuous function from any two of the coordinates to the third one, on the corresponding infinitesimal types .
The following is easy to verify: for , if and only if there exist and such that
By the above comments, can thus be obtained as a composition of continuous maps, thus it is continuous. We similarly show that is continuous.
Applying logical compactness, we may now replace the type-definable with an -definable , with partial continuous group operations, which make into a local group (we note that in general, any type-definable group is contained in a definable local group by logical compactness, except for the topological conditions). Similarly, we find , and as needed. ∎
Note that if is an o-minimal expansion of the field of reals and the ’s and are definable in , with not satisfying Clause (1) of Corollary 6.19, then taking a sufficiently saturated elementary extension , still does not satisfy Clause (1) in . Hence we may deduce that Clause (2) of Corollary 6.19 holds for in , possibly over additional parameters from . However, the definition of a local group is first-order in the parameters defining , and . Thus, by elementarity, we obtain that Clause (2) of Corollary 6.19 holds for , with and the functions definable in the original structure .
By Goldbring’s solution [goldbring2010hilbert] to the Hilbert’s 5th problem for local groups, if is a locally Euclidean local group (i.e. there is an open neighborhood of homeomorphic to an open subset of , for some ), then there is a neighborhood of such that is isomorphic, as a local group, to an open subset of an actual Lie group . Clearly, if the local group is abelian then the connected component of is also abelian. Combining these observations with Corollary 6.19 we conclude:
Corollary 6.20.
Let be an o-minimal expansion of the field of reals. Assume , are -definable with , and is fiber-algebraic. Then one of the following holds.
-
(1)
The set satisfies -power saving, for if , and if .
-
(2)
There exist definable relatively open sets , , an abelian Lie group of dimension and an open neighborhood of , and definable homeomorphisms , , such that for all
Finally, this takes a particularly explicit form when for all .
Corollary 6.21.
Let be an o-minimal expansion of the field of reals. Assume and is definable and fiber-algebraic. Then exactly one of the following holds.
-
(1)
There exists a constant , depending only on the formula defining (and not on its parameters), such that: for any finite with for we have
where if , and if .
-
(2)
There exist definable open sets , an open set containing , and homeomorphisms such that
for all .
Proof.
Corollary 6.20 can be applied to .
Assume we are in Clause (1). As the proof of Theorem 6.4 demonstrates, we can take any such that satisfies the -ST property (as a binary relation, under any partition of its variables into two and the rest) if ; and such that (as defined in Section 5.7) satisfies the -ST property if . Applying the stronger bound for definable subsets of from Fact 2.15(1), we get the desired -power saving. Note that in the -dimensional case, the general position requirement is satisfied automatically: for any definable set , if and only if is finite; and for every definable family of subsets of , by -minimality there exists some such that for any , if has cardinality greater than then it is infinite.
In Clause (2), we use that every connected -dimensional Lie group is isomorphic to either or , and in the latter case we can restrict to a neighborhood of and compose the ’s with a local isomorphism from to .
Finally, the two clauses are mutually exclusive as in Remark 5.52. ∎
Remark 6.22.
Remark 6.23.
If is semialgebraic (which corresponds to the case of Corollary 6.21), of description complexity (i.e. defined by at most polynomial (in-)equalities, with all polynomials of degree at most ), then in Clause (1) the constant depends only on and (as all ’s are defined by the instances of a single formula depending only on and ).