Proof As each cell $\Delta \in \mathcal {T}(B)$ is not crossed by $\Phi (x;B)$ , its elements must all have the same $\Phi $ -types over B. Thus there is a function $f:\mathcal {T}(B)\to S^{\Phi }(B)$ sending each cell to the $\Phi $ -type over B of its elements. Each type in $S^{\Phi }(B)$ is consistent and definable by a formula, and thus must be realized in M, so there must be at least one cell of $\mathcal {T}(B)$ containing formulas of that type. Thus f is a surjection, and $ \left \lvert {\mathcal {T}(B)} \right \rvert \geq \left \lvert {S^{\Phi }(B)} \right \rvert $ .

Proof The definability requirements for a distal cell decomposition do not depend on the set of formulas $\Phi $ , so it suffices to show that $\mathcal {T}$ is an abstract cell decomposition for $\Phi $ , or that for a given B, each cell $\Delta \in \mathcal {T}(B)$ is not crossed by $\Phi (x;B)$ . As for any $\varphi \in \Phi $ , $b \in B$ , $\varphi (x;b)$ is a Boolean combination of formulas in $\Phi '(x;B)$ , and all of these have a fixed truth value on $\Delta $ , so does $\varphi (x;b)$ .

Proof By Proposition 2.7, for every distal cell decomposition $\mathcal {T}$ , $ \left \lvert {\mathcal {T}(B)} \right \rvert \geq \left \lvert {S^{\Phi }(B)} \right \rvert $ . Thus

$$ \begin{align*}\mathrm{vc}^*(\Phi)\leq \limsup_{n \to \infty}\frac{\log \pi^*_{\Phi}(n)}{\log n}\leq \limsup_{n \to \infty}\frac{\log \pi_{\mathcal{T}}(n)}{\log n}\end{align*} $$

so after taking the infimum over all $\mathcal {T}$ , the distal density is at least $\mathrm {vc}^*(\Phi )$ .

Proof Let $\mathcal {T}$ be a distal cell decomposition for $\Phi $ over $\mathcal {M}$ , consisting of a set $\Psi (x;y_1,\dots ,y_k)$ of formulas, and a formula $\theta _{\psi }$ for each $\psi \in \Psi $ (as in Definition 2.8). Then to verify that the same formulas define a distal cell decomposition for $\Phi $ over $\mathcal {M}'$ , we must simply check that for all finite $B \subset M^{\prime \left \lvert {y} \right \rvert }$ , the set of cells $\mathcal {T}(B)$ covers $M^{\prime \left \lvert {x} \right \rvert }$ , and that no cell of $\mathcal {T}(B)$ is crossed by $\Phi (x;B)$ .

It is enough to show that these facts can be described with first-order sentences. Fix some natural number n, and we will find a first-order sentence that shows that for all $B = \{b_1,\dots , b_n\}$ , the cells of $\mathcal {T}(B)$ cover the space and are not crossed. We can encode that the cells of $\mathcal {T}(B)$ cover $M^{\prime \left \lvert {x} \right \rvert }$ with the sentence

$$ \begin{align*} \forall y_1,\dots, y_n, \forall x, \bigwedge_{\psi \in \Psi, i_1,\dots,i_k \in \{1,\dots,n\}}\psi(x;y_{i_1},\dots,y_{i_k}) \wedge \bigwedge_{i = 1}^n \neg \theta_{\psi}(y_i;y_{i_1},\dots,y_{i_k}). \end{align*} $$

When interpreted over $\mathcal {M}'$ , this simply states that for any choice of n parameters $b_1,\dots , b_n$ and any $x_0 \in M^{\prime \left \lvert {x} \right \rvert }$ , there is some $\psi , i_1,\dots ,i_k$ such that $\psi (x;b_{i_1},\dots ,b_{i_k})$ defines a valid cell, which contains $x_0$ . Similarly, to show that the cell defined by $\psi (x;b_{i_1},\dots ,b_{i_k})$ , if included in the cell decomposition, is not crossed by $\Phi (x;B)$ , we can use the following sentence, showing that for all $B = \{b_1,\dots , b_n\}$ , if for some i and some $\varphi \in \Phi $ , $\phi (x;b_i)$ crosses $\psi (x;b_{i_1},\dots ,b_{i_k})$ , then $\psi (x;b_{i_1},\dots ,b_{i_k})$ is not a valid cell:

$$ \begin{align*} \forall y_1,\dots, y_n, \left(\bigvee_{\varphi \in \Phi, 1 \leq i \leq n} \exists x_1, x_2, \varphi(x_1;y_i) \wedge \neg \varphi(x_2;y_i) \wedge \psi(x_1;y_{i_1},\dots,y_{i_k}) \wedge \psi(x_2;y_{i_1},\dots,y_{i_k})\right) \\ \to \bigvee_{i = 1}^n \theta_{\psi}(y_i;y_{i_1},\dots,y_{i_k}). \end{align*} $$

Now it suffices to show that the shatter function $\pi _{\mathcal {T}}$ is the same in both models, as the distal exponent of $\mathcal {T}$ and distal density of $\Phi $ are defined in terms of these shatter functions.

To say that $\pi _{\mathcal {T}}(n) \leq m$ in $\mathcal {M}$ is to say that for all $b_1,\dots , b_n \in M^{ \left \lvert {y} \right \rvert }$ , there are at most m cells in $\mathcal {T}(B)$ . This is the disjunction of a finite number of cases, which we will index by $A_1,\dots ,A_m$ , where each $A_i \subset \Psi \times \{1,\dots ,n\}^k$ , as each tuple $t = (\psi _t, t_1,\dots ,t_n) \in \Psi \times \{1,\dots ,n\}^k$ corresponds to a potential cell $\Delta _s = \psi _t(x;b_{t_1},\dots ,b_{t_n})$ . Then in the case indexed by $A_1,\dots , A_m$ , there is a first-order sentence stating that for all $1 \leq i \leq n$ and $s,t \in A_i$ , the formulas $\Delta _s$ and $\Delta _t$ are equivalent, and for all tuples $t = (\psi , i_1,\dots ,i_n)$ not contained in any $A_i$ , t is not a valid cell, as implied by $\bigvee _{j =1}^n\theta _{\psi }(b_j;b_{i_1},\dots ,b_{i_n})$ . The disjunction of all these sentences states that there are at most m distinct cells in $\mathcal {T}(\{b_1,\dots ,b_n\})$ , and if $b_1,\dots ,b_n$ are replaced with universally quantified variables, we find a sentence that states that $\pi _{\mathcal {T}}(n)\leq m$ . Thus for all n, $\pi _{\mathcal {T}}(n)$ evaluates to the same number over any model of the theory of $\mathcal {M}$ .

Fact 2.16. The following are equivalent for any first-order structure $\mathcal {M}$ :

1. 1. $\mathcal {M}$ is distal.

2. 2. For every formula $\phi (x;y)$ , $\{\phi \}$ admits a distal cell decomposition.

3. 3. For every finite set of formulas $\Phi (x;y)$ , $\Phi $ admits a distal cell decomposition.

Proof The equivalence of (1) and (2) is by [Reference Chernikov and Simon12] (see [Reference Chernikov, Galvin and Starchenko11, Fact 2.9] for a discussion). Clearly (3) implies (2), so it suffices to show that (2) implies (3).

For a given $\Phi (x;y)$ , assume each $\phi \in \Phi $ admits a distal cell decomposition $\mathcal {T}_{\phi }$ . Then for finite $B\subseteq M^{ \left \lvert {y} \right \rvert }$ , we define $\mathcal {T}(B)$ to consist of all nonempty intersections $\bigcap _{\phi \in \Phi }\Delta _{\phi }$ , where each $\Delta _{\phi }$ is chosen from $\mathcal {T}_{\phi }(B)$ . These cells will cover $M^{ \left \lvert {x} \right \rvert }$ , as each $a \in M^{ \left \lvert {x} \right \rvert }$ belongs to some $\Delta _{\phi }$ for each $\phi $ , and thus belongs to their intersection. Any cell $\Delta = \bigcap _{\phi \in \Phi }\Delta _{\phi }$ will not be crossed by $\Phi (x;B)$ , as for each $\phi \in \Phi $ , as $\Delta \subset \Delta _{\phi }$ , and $\Delta _{\phi }$ is not crossed by $\phi (x;B)$ .

Now we check that this cell decomposition is uniformly definable. For each $\phi \in \Phi $ , let $\mathcal {T}_{\phi }$ consist of $\Psi _{\phi }$ and $\{\theta _{\psi }: \psi \in \Psi _{\phi }\}$ . Then $\mathcal {T}$ can be defined by the set of formulas $\Psi $ consisting of all conjunctions $\bigwedge _{\phi \in \Phi } \psi _{\phi }$ where $\psi _{\phi } \in \Psi _{\phi }$ for each $\phi $ . For a given $\Delta = \bigcap _{\phi \in \Phi }\Delta _{\phi }$ , we can let $\mathcal {I}(\Delta ) = \bigcup _{\phi \in \Phi } \mathcal {I}(\Delta _{\phi })$ .

Proof The case with $d=d_0$ follows directly from the assumptions, so we can proceed by induction. Assume the result for all finite sets of formulas with $ \left \lvert {x} \right \rvert =d-1 \geq d_0$ . Then we will build a distal cell decomposition for a $\Phi (x;y)$ with $ \left \lvert {x} \right \rvert =d$ . Where $x=(x_1,\dots ,x_d)$ , let $x'=(x_2,\dots ,x_d)$ . We start by fixing a distal cell decomposition $\mathcal {T}_1$ for the set of formulas $\Phi _1(x_1;x',y) := \{\phi (x_1;x',y):\phi (x;y) \in \Phi \}$ . Let the cells of $\mathcal {T}_1$ be defined by $\Psi _1(x_1;x^{\prime }_1,y_1,\dots , x^{\prime }_k, y_k)$ and a formula $\theta _{\psi }(x',y;x^{\prime }_1,y_1,\dots ,x^{\prime }_k,y_k)$ for each $\psi \in \Psi _1$ . For this construction, we will only use $\mathcal {T}_1$ to define $\Phi _1$ -types over sets of the form $\{a'\}\times B$ . Because each element of that set has the same first coordinate, we will abbreviate the formula $\psi (x_1;x^{\prime }_1,y_1,x^{\prime }_2,y_2,\dots ,x^{\prime }_1,y_k)$ as $\psi (x_1;x',y_1,y_2,\dots ,y_k)$ , assuming all the variables $x^{\prime }_i$ are equal. Similarly, we abbreviate $\theta _{\psi }(x',y;x^{\prime }_1,y_1,\dots ,x^{\prime }_k,y_k)$ as $\theta _{\psi }(x',y;y_1,\dots ,y_k)$ , setting each $x^{\prime }_i$ equal to $x'$ . We will also want to repartition the variables, setting $\theta _{\psi }*(x';y_1,\dots ,y_k,y) := \theta _{\psi }(x',y;y_1,\dots ,y_k)$ .

For each $\psi \in \Psi _1$ , let $\Phi _{\psi }(x';y_1,\dots ,y_k,y)$ be the set of formulas consisting of $\theta _{\psi }*$ and all formulas of the form $\forall x_1, \psi (x_1;x',y_1,\dots ,y_k) \to \square \phi (x_1,x';y)$ where $\phi \in \Phi $ , and $\square $ is either $\neg $ or nothing.

Then let $\mathcal {T}_{\psi }$ be a distal cell decomposition for $\Phi _{\psi }$ , consisting of $\Psi _{\psi }$ and a formula $\theta _{\psi '}$ for each $\psi ' \in \Psi _{\psi }$ . As before, we will assume some of the variables are equal, and write these formulas more succinctly, assuming that our set of parameters is of the form $\{(b_1,\dots ,b_k)\}\times B$ for some $b_1,\dots ,b_k \in M$ and finite $B \subseteq M^{ \left \lvert {y} \right \rvert }$ . This allows us to write each $\psi ' \in \Psi _{\psi }$ as $\psi '(x';y_1,\dots ,y_k,y_1^{\prime },\dots ,y_m^{\prime })$ , and write $\theta _{\psi '}$ as $\theta _{\psi '}(y;y_1,\dots ,y_k,y_1^{\prime },\dots ,y_m^{\prime })$ .

For each $\psi \in \Psi _1$ and $\psi ' \in \Psi _{\psi }$ , let $\psi \otimes \psi '(x;y_1,\dots ,y_k,y^{\prime }_1,\dots ,y_m^{\prime })$ be the formula

$$ \begin{align*} \psi'(x';y_1,\dots,y_k,y^{\prime}_1,\dots,y_m^{\prime})\wedge \psi(x_1;x',y_1,\dots,y_k). \end{align*} $$

(Intuitively, this defines a sort of cylindrical cell in $M^{ \left \lvert {x} \right \rvert }$ , where $x'$ is in a cell of one cell decomposition of $M^{ \left \lvert {x'} \right \rvert }$ , and $x_1$ is in a cell of a cell decomposition of M, defined using $x'$ as a parameter.) Let $\Psi (x;y_1,\dots ,y_k,y^{\prime }_1,\dots ,y_m^{\prime }) = \{\psi \otimes \psi ' : \psi \in \Psi _1, \psi ' \in \Psi _{\psi }\}$ . We will use $\Psi $ to define a distal cell decomposition $\mathcal {T}$ for $\Phi (x;y)$ .

To define $\mathcal {T}$ , it suffices to define $\theta _{\psi \otimes \psi '}$ for each $\psi \in \Psi _1, \psi ' \in \Psi _{\psi }$ . Define

$$ \begin{align*} \theta_{\psi \otimes \psi'}&(y;y_1,\dots,y_k,y^{\prime}_1,\dots,y^{\prime}_m) :=\\ &\theta_{\psi'}(y;y_1,\dots,y_k,y_1^{\prime},\dots,y_m^{\prime}) \wedge (\exists x', \psi'(x';y_1,\dots,y_k,y^{\prime}_1,\dots,y^{\prime}_m) \wedge \theta_{\psi}(x'; y_1,\dots,y_k,y)). \end{align*} $$

This means that if $\Delta $ is the cell $\psi \otimes \psi '(M^d;b_1,\dots ,b_k,b^{\prime }_1,\dots ,b_m^{\prime })$ , then

$$ \begin{align*} \mathcal{I}(\Delta) &:= \{b \in M^{ \left\lvert {y} \right\rvert } : \mathcal{M}\models \theta_{\psi \otimes \psi'}(b; b_1,\dots,b_k,b^{\prime}_1,\dots,b_m^{\prime})\}\\ &= \{b \in M^{ \left\lvert {y} \right\rvert } : \exists (a_1,a') \in \Delta, \mathcal{M}\models \theta_{\psi}(a',b;b_1,\dots,b_k)\}. \end{align*} $$

Thus for all $a'$ in the projection of $\Delta $ onto $M^{d-1}$ , the fiber $\{a_1 \in M: (a_1,a') \in \Delta \}$ is a cell of $\mathcal {T}_1(\{a'\}\times B)$ if and only if $B \cap \mathcal {I}(\Delta )=\emptyset $ .

Now we show that this definition of $\mathcal {T}$ gives a valid distal cell decomposition for $\Phi (x;y)$ . Fix a finite $B \subset M^{ \left \lvert {y} \right \rvert }$ and let $a \in M^d$ be given. Firstly, each element of $M^d$ is contained in a cell. If $a=(a_1,a')$ with $a_1 \in M, a' \in M^{d-1}$ , then $a_1$ is in some cell of $\mathcal {T}_1(\{a'\}\times B)$ , and that cell is defined by some $\psi (x_1;a',b_1,\dots ,b_k)$ , so for all $b \in B$ , $\mathcal {M} \models \neg \theta _{\psi }*(a';b_1,\dots ,b_k,b)$ . Therefore $a'$ is in some cell of $\mathcal {T}_{\psi }(\{(b_1,\dots ,b_k)\}\times B)$ on which $\mathcal {M} \models \neg \theta _{\psi }*(x';b_1,\dots ,b_k,b)$ . If that cell is defined by $\psi '(b_1,\dots ,b_k,b_1^{\prime },\dots ,b_m^{\prime })$ , then we can now define a cell containing a by $\psi \otimes \psi ' (x;b_1,\dots ,b_k,b_1^{\prime },\dots ,b_m^{\prime })$ .

Secondly, we show that each cell of $\mathcal {T}(B)$ is not crossed by $\Phi (x;B)$ . Fix a cell $\Delta \in \mathcal {T}(B)$ , and fix $\phi \in \Phi $ , $b \in B$ . We know that for each $a'$ in the projection of $\Delta $ onto $M^{d-1}$ , the fiber $\{a_1 \in M: (a_1,a') \in \Delta \}$ is a cell of $\mathcal {T}_1(\{a'\} \times B)$ , so that fiber is not crossed by $\phi (x;B)$ . We also guaranteed that if $\Delta $ is defined by the formula $\psi \otimes \psi '(x,b_1,\dots ,b_k,b_1^{\prime },\dots ,b_m^{\prime })$ , then the projection of $\Delta $ onto $M^{d-1}$ is a cell of $\mathcal {T}_{\psi }(B)$ , so it is not crossed by the formulas $\forall x_1, \psi (x_1; x',b_1,\dots ,b_k) \to \phi (x_1,x';b)$ and $\forall x_1, \psi (x_1; x',b_1,\dots ,b_k) \to \neg \phi (x_1,x';b)$ . If for some $(a_1,a')$ in $\Delta $ , $\mathcal {M}\models \phi (a_1,a';b)$ , then $\mathcal {M}\models \forall x_1, \psi (x_1; x',b_1,\dots ,b_k) \to \phi (x_1,x';b)$ for $x' = a'$ , and thus for all $x'$ in the projection of $\Delta $ , so $\mathcal {M}\models \psi (x;b)$ for all $x \in \Delta $ .

Finally we can count the number of cells of $\mathcal {T}(B)$ . For each $\psi \in \mathcal {T}_1$ , and each $b_1,\dots ,b_k$ , there are, by induction, $\mathcal {O}( \left \lvert {B} \right \rvert ^{k((d-1)-d_0)+r})$ cells in $\mathcal {T}'(\{(b_1,\dots ,b_k)\}\times B)$ , each inducing a cell of $\mathcal {T}(B)$ . Multiplying by the $ \left \lvert {B} \right \rvert ^k$ possible tuples $(b_1,\dots ,b_k) \in B^k$ and a finite number of formulas $\psi $ , we get the desired bound $\mathcal {O}( \left \lvert {B} \right \rvert ^{k(d-d_0)+r})$ .

Proof In any weakly o-minimal structure, if $\Phi (x;y)$ has $ \left \lvert {x} \right \rvert =1$ , then there exists a distal cell decomposition $\mathcal {T}$ with $ \left \lvert {\mathcal {T}(B)} \right \rvert =\mathcal {O}( \left \lvert {B} \right \rvert )$ with two parameters.

Indeed, by weak o-minimality, for any $\varphi (x;y) \in \Phi $ with $ \left \lvert {x} \right \rvert = 1$ , there is some number $N_{\varphi }$ such that the set $\varphi (M;b)$ is a union of at most $N_{\varphi }$ convex subsets for any $b \in M^{ \left \lvert {y} \right \rvert }$ . Let $N:=\max _{\varphi \in \Phi }N_{\varphi }$ . Then for each $\varphi (x;y) \in \Phi $ , we can define formulas $\varphi ^1(x;y),\dots ,\varphi ^N(x;y)$ by

$$ \begin{align*} &\varphi^n(x;y) :=\\ \exists x_1,&x_2,\dots,x_{n-1},y_1,\dots,y_{n-1}, \varphi(x;y)\wedge (x_1 \kern1.4pt{<}\kern1.4pt y_1 \kern1.4pt{<}\kern1.4pt x_2 \kern1.4pt{<}\kern1.4pt\dots \kern1.3pt{<}\kern1.3pt y_{n-1}<x) \wedge \bigwedge_{i=1}^{n-1} (\varphi(x_i;y)\wedge \neg \varphi(y_i;y)), \end{align*} $$

and then

$$ \begin{align*} \varphi(M;b)=\varphi^1(M;b)\cup \dots \cup \varphi^N(M;b) \end{align*} $$

for all b, each $\varphi ^i(M;b)$ is convex, and $\varphi ^i(M;b) < \varphi ^{i+1}(M;b)$ for each i, in the sense that for every $x_i \in \varphi ^i(M;b)$ and $x_{i+1} \in \varphi ^{i+1}(M;b)$ , $x_i < x_{i+1}$ .

Then for each $\varphi \in \Phi $ we can also define

$$ \begin{align*} \varphi^i_{\leq}(x;y):=\exists x_0(\varphi^i(x_0;y)\wedge x\leq x_0), \end{align*} $$

$$ \begin{align*} \varphi^i_<(x;y):=\forall x_0(\varphi^i(x_0;y)\to x< x_0). \end{align*} $$

Note that each $\varphi ^i_{\square }(M;b)$ for $\square \in \{<,\leq \}$ is closed downwards. Thus for any finite subset $B \subset M^{ \left \lvert {y} \right \rvert }$ , the family of sets $\mathcal {F}(B)=\{\varphi ^i_{\square }(M,b):b \in B,\varphi \in \Phi ,1\leq i \leq N, \square \in \{<,\leq \}\}$ is linearly ordered under inclusion. Thus the atoms in the Boolean algebra $\mathcal {B}$ generated by $\mathcal {F}(B)$ are of the form $X_1\setminus X_2$ where $X_1,X_2 \in \mathcal {F}(B)$ and $X_2$ is the unique maximal element of $\mathcal {F}(B)$ properly contained in $X_1$ , or $\mathcal {M}\setminus X_1$ where $X_1$ is the unique maximal element of $\mathcal {F}(B)$ . Thus only one atom of the Boolean algebra can be of the form $X_1 \setminus X_2$ for each $X_1$ , and thus the number of such atoms is at most $ \left \lvert {\mathcal {F}(B)} \right \rvert +1$ , which is $\mathcal {O}( \left \lvert {B} \right \rvert )$ .

Now we construct $\mathcal {T}$ . We let $\Psi $ consist of the formulas of the form $\psi (x;y_1,y_2):=\varphi ^i_{\square _1}(x;y_1)\wedge \neg \varphi ^j_{\square _2}(x;y_2)$ or $\psi (x;y):=\neg \varphi ^j_{\square _1}(x;y)$ with $1\leq i \leq N, \square \in \{<,\leq \}$ , and then for each potential cell $\Delta =\psi (M;b_1,b_2)$ , let $\mathcal {I}(\Delta )$ just consist of all $b \in M^{ \left \lvert {y} \right \rvert }$ such that $\Delta $ is crossed by $\varphi _0(M;b)$ for some $\varphi _0 \in \Phi $ . Then $\mathcal {T}(B)$ is exactly the set of atoms in the Boolean algebra generated by $\mathcal {F}(B)$ , so $ \left \lvert {\mathcal {T}(B)} \right \rvert =\mathcal {O}( \left \lvert {B} \right \rvert )$ . Each cell is not crossed by any set in $\mathcal {F}(B)$ , and thus not by any $\varphi (x;B)$ , or $\Phi (x;B)$ itself, so this is a valid distal cell decomposition, where every cell is defined using at most two parameters from B.

Thus we can use Theorem 3.1, setting $d_0=1$ , $r=1$ , and $k=2$ , to find that any family of formulas $\Phi (x;y)$ has a distal cell decomposition of exponent at most $2( \left \lvert {x} \right \rvert -1)+1=2 \left \lvert {x} \right \rvert -1$ .

If $\mathcal {M}$ is an o-minimal expansion of a group, we can instead set $d_0=2$ , then we can set $r=2$ , and by [Reference Chernikov, Galvin and Starchenko11, Theorem 4.1], for $\Phi (x;y)$ with $ \left \lvert {x} \right \rvert =2$ , $\Phi $ admits a distal cell decomposition of exponent $2$ . (In [Reference Chernikov, Galvin and Starchenko11], this is only proven for the case where $\mathcal {M}$ is an expansion of a field, but the proof only uses it for definable choice, which o-minimal expansions of groups also have.) Then for $ \left \lvert {x} \right \rvert \geq 2$ , $\Phi (x;y)$ admits a distal cell decomposition of exponent $2( \left \lvert {x} \right \rvert -2)+2=2 \left \lvert {x} \right \rvert -2$ .

Proof Throughout this proof, we will identify $\mathbb {Z}$ with the subgroup of G generated by the constant 1.

As G has quantifier elimination in this language, every $\varphi (x;y) \in \Phi $ is equivalent to a Boolean combination of atomic formulas. We will group the atomic formulas into two categories. The first is those of the form $f(x) \square g(y) + c$ , where $\square \in \{<,=,>\}$ , $(f,g)$ belongs to a finite set F of pairs of $\mathbb {Z}$ -linear functions of the form $\sum _{i = 1}^{ \left \lvert {x} \right \rvert } a_i x_i$ with $a_i \in \mathbb {Z}$ , and c belongs to a finite set $C \subseteq \mathbb {Z}$ . The second is atomic formulas of the form $k \mid (f(x) + g(y) + c)$ for $k \in \mathbb {N}$ , $(f,g) \in F$ , and $c \in C$ . Furthermore, we may assume that only one symbol of the form $k \mid $ is used. If K is the least common multiple of the finite collection of k such that $k \mid $ appears in one of these atomic formulas, then each $k \mid (f(x) + g(y)+ c)$ can be replaced with $K \mid (d \cdot f(x) + d \cdot g(y) + d \cdot c)$ , where $d \cdot \sum _{i = 1}^{ \left \lvert {x} \right \rvert }a_i x_i = \sum _{i = 1}^{ \left \lvert {x} \right \rvert }(d \cdot a_i) x_i$ and $dk = K$ . Note that all of these functions and constants are $\emptyset $ -definable.

Then, by Lemma 2.9, we may replace $\Phi (x;y)$ with the union of the following two sets of atomic formulas for appropriate choices of F and C:

• • Fix C to be a finite subset of $\mathbb {Z}$ , F a finite subset of pairs of $\mathbb {Z}$ -linear functions of the form $\sum _{i = 1}^{ \left \lvert {x} \right \rvert } a_i x_i$ , and $K \in \mathbb {N}$ .

• • Let $\Phi _0$ be the set of all $f(x)\square g(y)+ c$ with $(f,g)\in F,c \in C, \square \in \{<,=,>\}$ .

• • Let $\Phi _1$ be the set of all $K \mid (f(x)+g(y)+c)$ with $(f,g) \in F, c \in \{0,\dots ,K-1\}$ .

• • Let $\Phi = \Phi _0 \cup \Phi _1$ .

It is straightforward to see that the negation of any formula from $\Phi _0$ is equivalent to the disjunction of two formulas from $\Phi _0$ , and a negation of any formula $K | (f(x)+g(y)+c)$ from $\Phi _1$ is equivalent to $\bigvee _{0 \leq c' <K, c' \neq c} K|(f(x)+g(y)+c)$ , a disjunction of formulas from $\Phi _1$ .

To apply Lemma 4.3, it suffices to show that for any $\varphi \in \Phi $ and nonempty finite $B \subset M^{ \left \lvert {y} \right \rvert }$ , $\bigwedge _{b \in B} \varphi (x;b)$ is equivalent to $\varphi (x;b_0)$ for some $b_0 \in B$ or is not realizable. This holds for $\varphi \in \Phi _0$ for reasons discussed in the proof of 4.2. For $\varphi \in \Phi _1$ , we see that if there exist $b_1, b_2$ such that $g(b_1) \not \equiv g(b_2) \pmod {K}$ , then $\varphi (x;b_1) \wedge \varphi (x;b_2)$ implies $K|(f(x)+g(b_1)+c) \wedge K|(f(x)+g(b_2)+c)$ so $K|\left (g(b_1)-g(b_2)\right )$ , a contradiction. Thus this conjunction is not realizable. Otherwise, for any $b_0 \in B$ , and any other $b \in B$ , $g(b) \equiv g(b_0)\pmod {K}$ , so $\bigwedge _{b \in B}\varphi (x;b)$ is equivalent to $\varphi (x;b_0)$ .

Now Lemma 4.3 gives us a distal cell decomposition $\mathcal {T}$ for $\Phi $ , such that for all B, $ \left \lvert {T(B)} \right \rvert = \left \lvert {S^{\Phi }(B)} \right \rvert $ . The theory of $\mathbb {Z}$ in $\mathcal {L}_{\mathrm {Pres}}$ is quasi-o-minimal by [Reference Belegradek, Peterzil and Wagner7, Example 2], and the same argument will hold for G, because G has quantifier elimination in the same language. The same VC density results apply to quasi-o-minimal theories as to o-minimal theories (see [Reference Aschenbrenner, Dolich, Haskell, Macpherson and Starchenko2, Theorem 6.4]), so $ \left \lvert {S^{\Phi }(B)} \right \rvert \leq \mathcal {O}( \left \lvert {B} \right \rvert ^{ \left \lvert {x} \right \rvert })$ .

Fact 6.3 [Reference Leenknegt23], see also [Reference Bobkov8, Theorem 4.1.5]

Any definable subset of $\mathbb {Q}^k_p$ (in the language $\mathcal {L}_{\mathrm {aff}}$ ) decomposes into a finite disjoint union of k-cells.

Proof We trace the proof of the original cell decomposition result in [Reference Leenknegt23]. Lemmas 2.3 and 2.7 establish that finite unions of cells (in the case of finite residue field, equivalent to the “semi-additive sets” of Definition 2.6) are closed under intersections and projections respectively, and Lemma 2.5 (using Lemma 2.4) shows that all quantifier-free definable sets are semi-additive. It suffices to modify each of these four lemmas slightly. In all four lemmas, we modify the assumptions to require that all linear polynomials in the assumptions have constant term 0. In each construction, the polynomials in the results are linear combinations of the polynomials in the assumptions, and thus will also have constant term 0, allowing us to state the results in terms of k-cells over $\emptyset $ .

Proof If $a \in \mathrm {dcl}(\emptyset )$ , then $\{a\}$ is $\emptyset $ -definable, so it can be decomposed into $1$ -cells over $\emptyset $ . There can only be one cell in the decomposition, $\{a\}$ . All of its defining polynomials take in variables from the unique $0$ -cell, and thus consist only of their constant coefficient, which is 0. Thus the cell must be of the form $\{a\} = \{t \in D \times \mathbb {Q}_p | v(0) \square _1 v(t - 0) \square _2 v(0), t - 0 \in \lambda Q_{m,n}\}$ . The condition $v(0) \square _1 v(t) \square _2 v(0)$ will define one of the following sets: $\emptyset , \{0\}, \mathbb {Q}_p \setminus \{0\}, \mathbb {Q}_p$ , and the condition $t \in \lambda Q_{m,n}$ defines $\{0\}$ when $\lambda = 0$ , and otherwise, $\lambda Q_{m,n} \subseteq \mathbb {Q}_p \setminus \{0\}$ . Thus the whole cell is either $\{0\}$ or $\lambda Q_{m,n}$ which is infinite, so if it is a singleton $\{a\}$ , we must have $a = 0$ .

Proof We prove this by induction on k. The $k = 0$ case is trivial. The $(k + 1)$ -cell $\{(x, t)\ \in\ D\ \times\ \mathbb {Q}_p | v(a_1 (x)) \square _1 v(t - c(x)) \square _2 v(a_2(x)), t - c(x)\ \in\ \lambda Q_{m,n}\}$ is $\emptyset $ -definable if D is, $v(a_1 (x)) \square _1 v(t - c(x)) \square _2 v(a_2(x))$ is, and $t - c(x) \in \lambda Q_{m,n}$ is. We have that D is by the induction hypothesis. For the next condition, it suffices to observe that the defining polynomials are $\emptyset $ -definable functions if and only if they have constant coefficient 0, because scalar multiplication is $\emptyset $ -definable, but no constant other than 0 is. For the final condition, we see that if $\lambda = 0$ , then $t - c(x) \in \lambda Q_{m,n}$ is equivalent to $t - c(x) = 0$ , which is $\emptyset $ -definable, and if $\lambda \ne 0$ , then $t - c(x) \in \lambda Q_{m,n}$ is equivalent to $\lambda ^{-1}\cdot (t - c(x)) \in Q_{m,n}$ , which is $\emptyset $ -definable.

Lemma [Reference Bobkov8, Theorem 4.2.1]

Any $\mathcal {L}_{\mathrm {aff}}$ -formula (with parameters) $\phi (x;y)$ where x and y are finite tuples of variables is equivalent in the $\mathcal {L}_{\mathrm {aff}}$ -structure $\mathbb {Q}_p$ to a Boolean combination of formulas from a collection

$$ \begin{align*} \Phi_{\phi}=\{v(p_i(x)-c_i(y))<v(p_j(x)-c_j(y))\}_{i,j \in I}\cup \{p_i(x)-c_i(y) \in \lambda Q_{m,n}\}_{i\in I,\lambda \in \Lambda}, \end{align*} $$

where $I=\{1,\dots , \left \lvert {I} \right \rvert \}$ is a finite index set, each $p_i$ is a degree $\leq 1$ polynomial with constant term 0, each $c_i$ is a degree $\leq 1$ polynomial, and $\Lambda $ is a finite set of coset representatives of $Q_{m,n}$ for some $m,n \in \mathbb {N}$ .

Proof This follows from Lemma 7.2, together with Theorem 3.1.