# Topological properties of definable sets in ordered Abelian groups of burden
2

Alfred Dolich and John Goodrick  Dept. of Math and CS
Kingsborough Community College (CUNY)
2001 Oriental Blvd.
Brooklyn, NY 11235  Department of Mathematics
CUNY Graduate Center
365 5th Ave.
New York, NY 10016<EMAIL_ADDRESS>Departamento de Matemáticas
Universidad de los Andes
Carrera 1 No. 18A-12
Bogotá, COLOMBIA 111711<EMAIL_ADDRESS>
###### Abstract.

We obtain some new results on the topology of unary definable sets in
expansions of densely ordered Abelian groups of burden $2$. In the special
case in which the structure has dp-rank $2$, we show that the existence of an
infinite definable discrete set precludes the definability of a set which is
dense and codense in an interval, or of a set which is topologically like the
Cantor middle-third set (Theorem 2.9). If it has burden $2$ and both an
infinite discrete set $D$ and a dense-codense set $X$ are definable, then
translates of $X$ must witness the Independence Property (Theorem 2.26). In
the last section, an explicit example of an ordered Abelian group of burden
$2$ is given in which both an infinite discrete set and a dense-codense set
are definable.

The first author’s research was partially supported by PSC-CUNY Grant
#63392-00 51. The second author would like to thank the Universidad de los
Andes for granting him paid leave (Semestre de Trabajo Académico
Independiente) during which part of this research was carried out.

##  1\. Introduction

In this note we will study the topological properties of sets definable in
densely ordered Abelian groups satisfying an extra model-theoretic hypothesis
(having “burden 2”) which in some sense limits the combinatorial complexity of
combinations of instances of formulas (the precise definition will be recalled
below). Typical examples of such groups are the structures
$\mathcal{R}_{1}=\langle\R;<,+,\Q\rangle$, the additive group of real numbers
endowed with a unary predicate for the set of rationals, and
$\mathcal{R}_{2}=\langle\R;<,+,\Z\rangle$, the same group but with a predicate
for the integers. In fact, both of the structures $\mathcal{R}_{1}$ and
$\mathcal{R}_{2}$ are of _dp-rank 2_ , which is equivalent to having burden 2
and being NIP.111Note that it can be tricky to prove precise upper bounds on
the burden or the dp-rank of a structure. See [5] for a detailed calculation
of the dp-rank of the structures mentioned here.

Recall that in an expansion of a divisible ordered Abelian group (or “OAG”) of
dp-rank 1, no infinite discrete subset of the domain can be definable (see
[10]), nor can any dense and codense subset be definable (by a result of Simon
[20]). However, the examples $\mathcal{R}_{1}$ and $\mathcal{R}_{2}$ above
show that neither of these results hold for OAGs of dp-rank 2. One of the new
results of this article is that in an expansion of a divisible OAG of dp-rank
2, there cannot be _both_ a definable infinite discrete set and a definable
dense-codense set (see Theorem 2.9 below).

The goal of this article is to understand the topological properties of unary
definable sets in an expansion of a densely ordered OAG $\mathcal{R}=\langle
R;<,+,\ldots\rangle$ with burden at most $2$. Suppose that $X\subseteq R$ is
definable in such a structure. The case when $X$ is open may be considered the
“nicest” situation since the topological structure around any point in $X$ is
as simple as possible. An expansion of a densely ordered OAG in which every
infinite definable $X\subseteq R$ has interior is called a _viscerally ordered
structure_. In our previous work [8], we undertook an extensive analysis of
definable sets in a viscerally ordered structure, giving a cell decomposition
theorem and showing that topological dimension has many desirable properties,
justifying the intuition that this is the “tamest” possible case.

Suppose now that $\mathcal{R}$ is _not_ visceral and that furthermore
$\textup{Th}(\mathcal{R})$ has finite burden. Let $X\subseteq R$ be definable
with empty interior. Since infinite definable discrete sets in $\mathcal{R}$
cannot have accumulation points (see [5, Corollary 2.13]), it follows easily
that $X$ can be partitioned as $X=X_{0}\cup X_{1}\cup X_{2}$ with each $X_{i}$
definable so that:

  1. (1)

$X_{1}$ is either empty or dense and codense in an open definable set $U$ with
$X_{1}\subset U$;

  2. (2)

$X_{2}$ is either empty or discrete (and possibly finite); and

  3. (3)

$X_{3}$ is either empty or an infinite definable set which is nowhere dense
and has no isolated points.

In case (3), if $X_{3}$ is non-empty then the topological closure
$\overline{X}_{3}$ is what we call a _Cantor-like_ definable set, namely it is
a nonempty set which is closed, nowhere dense, and has no isolated points.

We conjecture that in an expansion of a divisible OAG of dp-rank $2$, if there
is an infinite definable set satisfying one of the three conditions above
(being discrete, being dense-codense in an interval, or being Cantor-like),
then there cannot be any other infinite definable set satisfying either of the
other two (giving a basic trichotomy). Though we cannot quite prove this, in
the next section we will show that the existence of an infinite definable
discrete set precludes the definability of either a dense-codense or an
infinite Cantor-like set (Theorem 2.9). In the case when $\mathcal{R}$ has
burden $2$ and is definably complete, there can never be a definable Cantor-
like set (Theorem 2.5 below). Finally, in any OAG with burden $2$, if there is
both an infinite discrete set $D$ definable in such a structure and also a
definable $X$ which is dense and codense in some interval, then the
Independence Property can be witnessed by translations of $X$ (Theorem 2.26).

After proving the above general results in Section 2, the final section
(Section 3) is devoted to the study of a concrete example of a divisible OAG
of burden 2 in which both an infinite discrete set and a dense codense set are
definable.

Note that the present work focuses on the topological properties of definable
sets. Given an expansion of a OAG of burden $2$ in which an infinite discrete
set $D$ is definable, it turns out that $D$ must have a very simple
“arithmetical” structure, similar to the subsets of definable in Presburger
arithmetic. For much more on this topic, see our previous article [5] or our
recent preprint [7], which can be seen as a companion to the present work.

###  1.1. Notation and basic definitions

Mostly we will follow standard notational conventions from model theory (as in
[21], for example). “Formulas” and “models” are as in first-order logic and
overlined variables ($\overline{x},\overline{a},\ldots$) denote finite tuples.
Unlike some authors, a plain variable such as $x$ (not $\overline{x}$) is
always a single variable, and we rarely work in $T^{eq}$. Also note that
“definable” for us always means “definable over some set of parameters.”

The abbreviation OAG stands for Ordered Abelian Group, which is a structure
$\langle G;+,<\rangle$ consisting of an Abelian group $\langle G;+\rangle$
endowed with a total ordering $<$ which is translation invariant ($x<y$
implies that $x+z<y+z$). Some OAGs are _discretely ordered_ and have a least
positive element (such as $\langle\Z;+,,\rangle$), but in the present article
all OAGs will be _densely ordered_. Note that if an OAG is _divisible_ – that
is, for every $x\in G$ and every positive integer $n$, there is a $y\in G$
such that $ny=x$ – then it is densely ordered, but there are examples of OAGs
of finite dp-rank which are densely ordered and not divisible. See, for
instance, [21] or [6] for more examples.

All topological properties of sets mentioned in this article (“open,” “dense,”
and so on) refer to the order topology generated by all open intervals.

At some points in Section 2 it will be useful to work in the Dedekind
completion $\overline{R}$ of an OAG $\mathcal{R}$, for which the following
notion from [14] will be useful.

######  Definition 1.1.

Suppose that $\mathcal{R}=\langle R;<,\ldots\rangle$ is a linearly ordered
structure and $\\{X_{\overline{a}}\,:\,\overline{a}\in Z\\}$ is a definable
family of subsets $X_{\overline{a}}$ of $R$, with $Z\subseteq R^{n}$ definable
over $\emptyset$ and $X_{\overline{a}}=\\{b\in
R\,:\,\mathcal{R}\models\varphi(b;\overline{a})\\}$ for some formula
$\varphi(x;\overline{y})$. Consider the relation $\sim$ on $n$-tuples from $Z$
such that $\overline{a}_{1}\sim\overline{a}_{2}$ if and only if

$\forall y_{1}\in X_{\overline{a}_{1}}\exists y_{2}\in
X_{\overline{a}_{2}}\left(y_{1}<y_{2}\right)\wedge\forall y_{2}\in
X_{\overline{a}_{2}}\exists y_{1}\in
X_{\overline{a}_{1}}\left(y_{2}<y_{1}\right).$

The relation $\sim$ is a definable equivalence relation on $Z$ which we
informally think of as expressing that
$\sup(X_{\overline{a}_{1}})=\sup(X_{\overline{a}_{2}})$ where the suprema are
calculated in the Dedekind completion $\overline{R}$ of $\mathcal{R}$, and
defined so that $\sup(\emptyset)=-\infty$ and $\sup(X_{\overline{a}})=+\infty$
when $X_{\overline{a}}$ is unbounded. Then $Z/\sim$, which is a sort in
$\mathcal{R}^{eq}$, is a called a _sort in $\overline{R}$._ We naturally
identify such a sort with a subset of the Dedekind completion $\overline{R}$
of $\mathcal{R}$ with the induced ordering.

Thinking of sorts in $\overline{R}$ as sorts in $\mathcal{R}^{eq}$, we can
also talk about definable subsets of sorts in $\overline{R}$, and of functions
to and from such sorts.

######  Definition 1.2.

If $\mathcal{R}=\langle R;<,+,\ldots,\rangle$ is an expansion of an OAG, then
$\mathcal{R}$ is _definably complete_ if for every nonempty definable subset
$X\subseteq R$ which has an upper bound, $\sup(X)\in R$.

The next observation ([15, Proposition 2.2]) will occasionally be useful.

######  Fact 1.3.

If $\mathcal{R}$ is an expansion of a densely ordered OAG which is definably
complete, then $\mathcal{R}$ is divisible.

The less commonly used definitions we need are those of _burden_ and _dp-
rank_. These notions originally go back to Shelah [19], but we will use the
versions as given by Adler [1]. We recall them briefly here. Below, “$T$”
always denotes some complete theory.

######  Definition 1.4.

An _ict-pattern of depth $\kappa$_ is a sequence
$\\{\varphi_{i}(\overline{x};\overline{y}_{i})\,:\,i<\kappa\\}$ of formulas
and a sequence $\\{\overline{a}_{i,j}\,:\,i<\kappa,j<\omega\\}$ of tuples from
some model $\mathcal{M}\models T$ such that for every function
$\eta\,:\,\kappa\rightarrow\omega$, the partial type

(1) $\\{\varphi_{i}(\overline{x};\overline{a}_{i,j})^{\textup{if
}j=\eta(i)}\,:\,i<\kappa,j<\omega\\}$

is consistent, where the exponent “$\textup{if }j=\eta(i)$” means that the
formula is negated if $j\neq\eta(i)$. If $p(\overline{x})$ is a partial type,
an ict-pattern as above is _in $p(\overline{x})$_ if every partial type as in
(1) is consistent with $p(\overline{x})$.

The partial type $p(\overline{x})$ has _dp-rank less than $\kappa$_ if there
is no ict-pattern of depth $\kappa$ in $p(\overline{x})$. If the least
$\kappa$ such that the dp-rank of $p(\overline{x})$ is less than $\kappa$ is a
successor cardinal, say $\kappa=\lambda^{+}$, then we say that the dp-rank of
$p(\overline{x})$ is $\lambda$.

The dp-rank of the theory $T$ is the dp-rank of the partial type $x=x$ (in a
single free variable $x$), and $T$ is _dp-minimal_ if its dp-rank is $1$.

######  Definition 1.5.

An _inp-pattern of depth $\kappa$_ is a sequence
$\\{\varphi_{i}(\overline{x};\overline{y}_{i})\,:\,i<\kappa\\}$ of formulas, a
sequence $\\{k_{i}\,:\,i<\kappa\\}$ of positive integers, and a sequence
$\\{\overline{a}_{i,j}\,:\,i<\kappa,j<\omega\\}$ of tuples from some model
$\mathcal{M}\models T$ such that:

$\bullet$ For each $i<\kappa$, the “$i$-th row”

$\\{\varphi_{i}(\overline{x};\overline{a}_{i,j})\,:\,j<\omega\\}$

is $k_{i}$-inconsistent; and

$\bullet$ For each function $\eta\,:\,\kappa\rightarrow\omega$, the partial
type

(2) $\\{\varphi_{i}(\overline{x};\overline{a}_{i,\eta(i)})\,:\,i<\kappa\\}$

is consistent.

If $p(\overline{x})$ is a partial type, an inp-pattern as above is _in
$p(\overline{x})$_ if every partial type as in (2) is consistent with
$p(\overline{x})$.

The partial type $p(\overline{x})$ has _burden less than $\kappa$_ if there is
no inp-pattern of depth $\kappa$ in $p(\overline{x})$. If the least $\kappa$
such that the burden of $p(\overline{x})$ is less than $\kappa$ is a successor
cardinal, say $\kappa=\lambda^{+}$, then we say that the burden of
$p(\overline{x})$ is $\lambda$.

The burden of the theory $T$ is the burden of the partial type $x=x$ (in a
single free variable $x$), and $T$ is _inp-minimal_ if its burden is $1$.

######  Fact 1.6.

(Adler, [1]) The dp-rank of a theory is less than some cardinal $\kappa$ if
and only if $T$ is NIP. In case $T$ is NIP, the dp-rank of $T$ is equal to the
burden of $T$. In particular, $T$ is dp-minimal if, and only if, $T$ is both
NIP and inp-minimal.

To mention some related work, fields of finite dp-rank have been recently
classified by Johnson, who also showed that any valued field with finite dp-
rank is Henselian [13]. Interesting examples of finite burden structures which
are not finite dp-rank include pseudo real-closed fields [16]. For more
background on these concepts and how they relate to NIP, see the introduction
to our companion article [7] or the survey [11].

##  2\. Topologoical properties of definable sets in burden-2 OAGs

In this section we will prove the general topological results for OAGs of
burden 2 mentioned in the introduction.

Throughout this section, we will work under the following assumptions, unless
otherwise stated:

  * •

$\mathcal{R}=\langle R;<,+,\ldots\rangle$ is an expansion of a densely-ordered
OAG with complete theory $T$;

  * •

$\mathcal{R}$ is sufficiently saturated (generally just $|T|^{+}$-saturated
will be enough);

  * •

The burden of $\mathcal{R}$ is at most $2$.

Note that in this section, we do not generally assume that $\mathcal{R}$ is
definably complete (unless we explicitly say so).

######  Lemma 2.1.

Suppose that $I\subseteq R$ is an interval such that $I$ has burden $1$. Then
if $X\subseteq I$ is definable and nowhere dense, then $X$ is finite.

###### Proof.

This is essentially the same result as Lemma 3.3(1) of [10], except that we
allow $I$ to be any interval instead of the whole universe $R$. The same proof
as in [10] goes through, working within $I$. ∎

######  Lemma 2.2.

If there is an infinite discrete set definable in $\mathcal{R}$ then there is
$\epsilon>0$ so that $(0,\epsilon)$ has burden $1$.

###### Proof.

Suppose to the contrary that $D\subseteq R$ is infinite, discrete, and
definable, and that for every $\epsilon>0$ in $R$ there is an inp-pattern of
depth $2$ consistent with $(0,\epsilon)$.

Now using $\omega$-saturation of $\mathcal{R}$ we can select an increasing
sequence of elements $\\{a_{i}\,:\,i\in\omega\\}\subseteq D$ and an
$\epsilon>0$ such that for every $i$ we have
$(a_{i}-2\epsilon,a_{i}+2\epsilon)\cap D=\\{a_{i}\\}$. We can now construct an
inp-pattern of depth $3$ by attaching translated copies of the inp-pattern
within $(0,\epsilon)$ onto each point of $a_{i}$ and adding a third row
consisting of pairwise disjoint intervals, leading to a contradiction.

More precisely, if $\varphi_{0}(x,\overline{b}_{0,j})$ and
$\varphi_{1}(x,\overline{b}_{1,j})$ witness an inp-pattern of depth $2$
consistent with $(0,\epsilon)$, then for each $\ell\in\\{0,1\\}$ let
$\varphi^{\prime}_{\ell}(x,\overline{b}_{\ell,j})$ be the formula expressing
“there is a unique point $a\in D$ such that $a<x<a+\epsilon$, and for this
unique point $a$, the formula $\varphi_{\ell}(x-a,\overline{b}_{\ell,j})$
holds.” These will be the first two rows of our inp-pattern, and the third row
will consist of the pairwise disjoint intervals
$I_{i}=(a_{i}-\epsilon,a_{i}+\epsilon)$. The inconsistency of each row is easy
to check, and if $c_{i,j}\in(0,\epsilon)$ satisfies the formula
$\varphi_{0}(x,\overline{b}_{0,i})\wedge\varphi_{1}(x,\overline{b}_{1,j})$,
then for any $k\in\omega$ the point $a_{k}+c_{i,j}$ satisfies
$\varphi^{\prime}_{0}(x,\overline{b}_{0,i})\wedge\varphi^{\prime}_{1}(x,\overline{b}_{1,j})$
and lies within the interval $I_{k}$. ∎

This lemma has an immediate and useful corollary:

######  Corollary 2.3.

If there is $X\subseteq R$ definable, infinite, and discrete then there is no
definable Cantor-like set in $\mathcal{R}$.

###### Proof.

By the previous Lemma, there is $\epsilon>0$ such that $(0,\epsilon)$ has
burden $1$. Suppose for contradiction that there is $Y$ definable and Cantor-
like. Translating $Y$ as necessary, we may assume that
$Y\cap(0,\epsilon)\neq\emptyset$; and intersecting $Y$ with a closed
subinterval of $(0,\epsilon)$, we may further assume that there is a Cantor-
like definable subset of $(0,\epsilon)$. This contradicts Lemma 2.1. ∎

Using the above Corollary, we can rule out the existence of any Cantor-like
definable set in the case when $\mathcal{R}$ additionally satisfies definable
completeness. First we prove a simple lemma. Recall that if $X$ is a subset of
an ordered structure, a _convex component_ of $X$ is a maximal subset of $X$
which is convex.

######  Lemma 2.4.

If $X$ is a Cantor-like subset of $R$, then $R\setminus X$ has infinitely many
convex components.

###### Proof.

Recall that Cantor-like sets are nonempty by definition, so we may pick some
$a\in X$. Given that $X$ has no isolated points, it is either the case that
(i) for every positive $\epsilon\in R$, the interval $(a-\epsilon,a)$ contains
a point of $X$, or (ii) for every positive $\epsilon\in R$, the interval
$(a,a+\epsilon)$ contains a point of $X$. Without loss of generality we assume
that (ii) occurs, and in case of (i) a similar proof will work.

Pick some $b_{0}>a$. Since $X$ is nowhere dense, there is some element $c_{0}$
of $R\setminus X$ contained in the interval $(a,b_{0})$. Given the assumption
(ii) above, the convex component $C_{0}$ of $c_{0}$ in $R\setminus X$ cannot
contain points arbitrarily close to $a$, an hence there is a point $b_{1}\in
R$ such that $a<b_{1}$ and $b_{1}$ is less than every element of $C_{1}$. Now
repeat the argument above to find $c_{1}\in R\setminus X$ contained in
$(a,b_{1})$, and continuing by induction we may find an infinite sequence of
elements $c_{1}>c_{2}>\ldots$ of $R\setminus X$ all in distinct convex
components.

∎

######  Theorem 2.5.

If $\mathcal{R}$ is a densely ordered, definably complete OAG with burden at
most $2$, then there is no definable Cantor-like set in $\mathcal{R}$.

###### Proof.

Assume otherwise, and let $X\subseteq R$ be a definable Cantor-like set. By
the previous lemma, $R\setminus X$ consists infinitely many convex components,
each of which is open (as $X$ is closed). By definable completeness, each
convex component of $R\setminus X$ is an interval; we call these the
_complementary intervals_. All but at most two complementary intervals are
bounded, and if $I=(a,b)$ is a bounded complementary interval, then we can use
the fact that $\mathcal{R}$ is divisible (Fact 1.3 above) to define its
midpoint $I_{m}=\frac{a+b}{2}$. The collection of all such midpoints $I_{m}$
is itself definable and comprises and infinite discrete set, yielding a
contradiction to Corollary 2.3. ∎

Now we will focus on the case when $\mathcal{R}$ has dp-rank 2 (which, recall,
is equivalent to NIP plus having burden $2$). In this case, we will show that
if $R$ is divisible and defines an infinite discrete set, then it cannot also
define a set which is dense and codense in some infinite interval.

To this end, we will use the _Shelah expansion_ $\mathcal{R}^{Sh}$ of the
structure $\mathcal{R}$. This concept, and the facts below, are due to Shelah
[18], but we will follow the notation and presentation of Simon [21].

######  Definition 2.6.

Suppose that $\mathcal{R}\prec\mathcal{U}$ and $\mathcal{U}$ is $|R|^{+}$
-saturated. The _Shelah expansion_ $\mathcal{R}^{Sh}$ of $\mathcal{R}$ is the
expansion of $\mathcal{R}$ with the following new predicates: for every
partitioned formula $\varphi(\overline{x};\overline{y})$ and every finite
tuple $\overline{b}\in U^{|\overline{y}|}$, define a predicate
$S_{\varphi(\overline{x};\overline{b})}(\overline{x})$ on $R^{|\overline{x}|}$
such that

$\mathcal{R}^{Sh}\models
S_{\varphi(\overline{x};\overline{b})}(\overline{a})\Leftrightarrow\mathcal{U}\models\varphi(\overline{a};\overline{b}).$

The subsets of $R^{n}$ defined by the new basic predicates
$S_{\varphi(\overline{x};\overline{b})}$ as above are called _externally
definable sets_. An important example for our purposes is that if $C\subseteq
R$ is convex, then using $|R|^{+}$-saturation we may find $a,b\in U$ such that
$(a,b)\cap R=C$, and thus $C$ is externally definable.

The next fact summarizes the important basic properties of Shelah expansions.

######  Fact 2.7.

([18], and see also [21]) Suppose that the complete theory of $\mathcal{R}$ is
NIP.

  1. (1)

The subsets of $R^{n}$ which are definable in the Shelah expansion
$\mathcal{R}^{Sh}$ are independent of the choice of the saturated extension
$\mathcal{U}$ in Definition 2.6, and hence we may talk about “the” Shelah
expansion.

  2. (2)

The structure $\mathcal{R}^{Sh}$ admits elimination of quantifiers.

  3. (3)

The structure $\mathcal{R}^{Sh}$ is NIP.

  4. (4)

If $X\subseteq R^{n}$ is type-definable in $\mathcal{R}$, then the dp-rank of
$X$ as calculated in $\mathcal{R}$ is equal to the dp-rank of $X$ as
calculated in $\mathcal{R}^{Sh}$.

###### Proof.

While complete proofs of (1), (2), and (3) can be found in [21], we take the
opportunity to explain how (4) follows from (2) and (3). Note that a fact
similar to (4) has been claimed by Onshuus and Usvyatsov (see [17]) but only
in the special case when the theory is dp-minimal.

Let $d_{1}$ be the dp-rank of $X$ as calculated in the original structure
$\mathcal{R}$, and let $d_{2}$ be the dp-rank of $X$ as calculated in the
Shelah expansion $\mathcal{R}^{Sh}$ (each of which exists since their theories
are NIP). On the one hand, if $\kappa$ is any cardinal and $d_{1}\geq\kappa$,
then there is an ict-pattern of depth $\kappa$ in $X$ with parameters from
some elementary extension of $\mathcal{R}$, and the same array of formulas is
an ict-pattern of depth $\kappa$ in the expanded language of
$\mathcal{R}^{Sh}$. Therefore $d_{1}\leq d_{2}$.

On the other hand, suppose that there is an ict-pattern

(3)
$\\{\varphi_{i}(\overline{x};\overline{a}_{i,j})\,:\,i<\kappa,\,j<\omega\\}$

of depth $\kappa$ consistent with $X$ in some elementary extension
$\mathcal{R}^{\prime}$ of $\mathcal{R}^{Sh}$. By quantifier elimination, we
may assume that

$\varphi_{i}(\overline{x};\overline{y})=S_{\psi_{i}(\overline{x};\overline{y};\overline{b}_{i})}(\overline{x};\overline{y})$

where $\overline{b}_{i}$ is a tuple of parameters from the $|R|^{+}$-saturated
model $\mathcal{U}\succ\mathcal{R}$ used to define $\mathcal{R}^{Sh}$.

Working in $\mathcal{R}^{Sh}$, for any $m,n\in\mathbb{N}$, any $m$-element
subset $\\{l_{1},\ldots,l_{m}\\}$ of $\kappa$, and any formula
$\theta(\overline{x})$ in $X$, there are parameters $\overline{c}_{i,j}\in R$
with $1\leq i\leq m$ and $1\leq j\leq n$ so that for any
$\eta:\\{1,\dots,m\\}\to\\{1,\dots,n\\}$ there is
$\overline{d}_{\eta}\in\theta(R)$ so that

$\mathcal{R}^{Sh}\models
S_{\psi_{l_{i}}(\overline{x};\overline{y};\overline{b}_{l_{i}})}(\overline{d}_{\eta};\overline{c}_{i,j})\text{
if and only if }\eta(i)=j.$

But then

$\mathcal{U}\models\psi_{l_{i}}(\overline{d}_{\eta},\overline{c}_{i,j},\overline{b}_{l_{i}})\text{
if and only if }\eta(i)=j.$

Thus by compactness, in $\mathcal{U}$ the formulas
$\psi_{i}(\overline{x},\overline{y},\overline{b}_{i})$ form an ict-pattern
with $\kappa$ rows consistent with $X$ and hence $d_{1}\geq d_{2}$.

∎

The next fact is a slight generalization of a theorem proved by Simon [20]
which we will need for what follows.

The fact below was proved by Simon [20] in the case when the entire structure
is a dp-minimal divisible OAG, but the same proof can be relativized to convex
definable subgroups $G$ to yield:

######  Fact 2.8.

If $G\subseteq R$ is a type-definable convex divisible subgroup of $R$,
$\textup{dp-rk}(G)=1$, and $X\subseteq G$ is infinite and definable, then $X$
has nonempty interior.

###### Proof.

Suppose that $G$ is as in the statement (type-definable, convex, divisible,
and with dp-rk $1$). By the comment just before Fact 2.7, the set $G$ is
externally definable. By Fact 2.7 (4), working in $\mathcal{R}^{Sh}$, the dp-
rank of $G$ is still $1$. Now consider the structure $\mathcal{G}$ whose
universe is the set $G$ and with the induced definable structure: that is, the
basic predicates in the language for $\mathcal{G}$ represent sets of the form
$G^{n}\cap Z$ where $Z\subseteq R^{n}$ is $\emptyset$-definable in the
language of $\mathcal{R}$. The fact that $\textup{dp-rk}(G)=1$ as calculated
in $\mathcal{R}^{Sh}$ implies that the theory of the structure $\mathcal{G}$
is dp-minimal. Also the set $X\subseteq G$ is definable in $\mathcal{G}$. Now
we can apply Theorem 3.6 of [20] to conclude that $X$ has nonempty interior,
as we wanted. ∎

Now we state our main result on divisible OAGs of dp-rank $2$.

######  Theorem 2.9.

If $\mathcal{R}$ is an expansion of a divisible ordered Abelian group of dp-
rank at most $2$ and there is an infinite definable discrete set in
$\mathcal{R}$ then there is no $X$ definable which is dense and codense in an
interval $I$ of $\mathcal{R}$ nor is there a definable Cantor-like set.

###### Proof.

Say $X\subseteq R$ is and $\mathcal{R}$-definable. By Corollary 2.3, we know
that $X$ is not Cantor-like. It only remains to consider the case when $X$ is
dense in some interval $I$.

First pick $\epsilon\in R$ as in the conclusion of Lemma 2.2 so that
$(-\epsilon,\epsilon)$ has dp-rank $1$. Now let $G$ be the subset of $R$
defined as

$G=\bigcap_{n\in\N}\left(-\frac{\epsilon}{n+1},\frac{\epsilon}{n+1}\right)$

and note that $G$ is a convex subgroup of $R$. By $\omega$-saturation, $G$ is
infinite. Also, $G$ is definable in $\mathcal{R}^{Sh}$, so by Fact 2.7, it has
dp-rank $1$ as calculated in the Shelah expansion.

Suppose that $X$ is dense and codense in $I$. Translating and truncating $I$
as necessary, we may assume that $I\subseteq G$. But then $X\cap I$ is an
infinite definable subset of $G$ which has empty interior, contradicting Fact
2.8.

∎

We have considerably more precise results if we also assume that $\mathcal{R}$
is definably complete.

######  Corollary 2.10.

Suppose that $\mathcal{R}$ is an expansion of a definably complete divisible
OAG of dp-rank at most $2$ in which an infinite discrete set is definable.
Then for any definable $X\subseteq R$, either $X$ is discrete or $X$ has
nonempty interior.

###### Proof.

Suppose that $X\subseteq R$ is definable and has empty interior. By Theorem
2.9, $X$ is nowhere dense. By Corollary 2.13 of [5], it follows that $X$ is
discrete. ∎

######  Corollary 2.11.

Suppose that $\mathcal{R}$ is a definably complete expansion of a divisible
ordered Abelian group with dp-rank at most $2$. If there is $X\subseteq R$
definable which is dense and codense in some interval then any model of
$T=\textup{Th}{(\mathcal{R})}$ has o-minimal open core.

###### Proof.

We claim that the theory of $\mathcal{R}$ has uniform finiteness: otherwise,
there would exist a formula $\varphi(x;\overline{y})$ such that for every
$n\in\N$, there are parameters $\overline{b}_{n}$ such that the set defined by
$\varphi(x;\overline{b}_{n})$ is finite and of size at least $n$. Note that
there is a first-order formula $\theta(\overline{y})$ which expresses the
property “the set defined by $\varphi(x;\overline{y})$ is topologically
discrete,” and since any finite set is discrete, $\theta(\overline{b}_{n})$
holds for each $n$. Thus every finite subset of

$\\{\exists^{\geq
m}x\,\,\varphi(x;\overline{y})\,:\,m\in\N\\}\cup\\{\theta(\overline{y})\\}$

is satisfiable by some tuple $\overline{b}_{n}$, and so by compactness and
$\omega$-saturation there is a tuple $\overline{b}$ such that
$\varphi(x;\overline{b})$ defines an infinite discrete set, contradicting
Theorem 2.9.

Therefore by [9, Theorem A], $\mathcal{R}$ has o-minimal open core. ∎

We note that Theorem 2.9 no longer holds once the dp-rank of $\mathcal{R}$
exceeds $2$: for example, in [5] we have shown that the structure
$\langle\R;+,<,\Q,\Z\rangle$ has dp-rank $3$.

For the remainder of this section, we return to the general situation when
$\mathcal{R}$ is only assumed to have burden $2$ (rather than dp-rank $2$).
Once again adapting arguments of Simon from [20] allows us to obtain
information on dense-codense definable sets in the case when there is also an
infinite definable discrete set.

We begin with a definition.

######  Definition 2.12.

Let $X\subseteq R$ be definable and $f:X\to\overline{R}$ be a definable
function from $X$ to some sort in the Dedekind completion $\overline{R}$ of
$\mathcal{R}$ (see Definition 1.1 above) with $f(x)>0$ for all $x\in X$. We
say that _$f$ is bounded away from $0$_ if whenever $I$ is an interval so that
$I\cap X$ is infinite there is $\epsilon>0$ and a subinterval $J\subseteq I$
with $J\cap X$ infinite so that $f(a)>\epsilon$ for all $a\in J$.

We say “functions on $X$ are bounded away from $0$” to mean that all definable
$f:X\to\overline{R}$ with $f$ positive on $X$ are bounded away from $0$.

######  Lemma 2.13.

If $X\subseteq R$ has burden $1$, then definable functions on $X$ are bounded
away from $0$.

###### Proof.

We will adapt the proof of [10, Lemma 3.19]. Suppose that definable functions
on $X$ are not bounded away from $0$, as witnessed by a definable function
$f\,:\,X\rightarrow\overline{R}$ and an interval $I$ such that:

(*) $I\cap X$ is infinite, and for any positive $\epsilon$ and every
subinterval $J$ with $X\cap J$ infinite, there is some $a\in X\cap J$ such
that $f(a)\leq\epsilon$.

By saturation, we may pick a sequence $\langle J_{i}\,:\,i\in\omega\rangle$ of
pairwise disjoint subintervals of $I$ such that for each $i$ the set
$J_{i}\cap X$ is infinite. The property (*) transfers to subintervals of $I$
so (*) is true, _mutatis mutandis_ , of each $J_{i}$ as well.

Pick $\epsilon_{0}>0$ in $R$ arbitrarily. By (*), we can pick an element
$a_{i,0}\in J_{i}$ for each $i$ such that for each $i$,

(4) $f(a_{i,0})<\epsilon_{0}.$

Now we pick positive elements $\epsilon_{j}$ and $a_{i,j}\in J_{i}$ for each
$j\in\omega$ by induction, as follows: suppose we have already selected
elements

$\epsilon_{0}>\epsilon_{1}>\ldots>\epsilon_{j}$

and elements $a_{i,j}\in J_{i}$ such that $f(a_{i,j})<\epsilon_{j}$. By
saturation, we can pick $\epsilon_{j+1}\in R$ such that for every
$i\in\omega$,

(5) $0<\epsilon_{j+1}<f(a_{i,j}).$

Finally, applying the property (*) again, for each $i\in\omega$ we can pick an
element $a_{i,j+1}\in J_{i}\cap X$ such that $f(a_{i,j+1})<\epsilon_{j+1}$.

Now we have elements $\langle a_{i,j}\,:\,(i,j)\in\omega\times\omega\rangle$
such that for every $(i,j)\in\omega\times\omega$,

$\epsilon_{j+1}<f(a_{i,j})<\epsilon_{j}.$

From this, we can construct an inp-pattern of depth $2$, as follows: in the
first row, we use formulas $\varphi_{0}(x;\overline{b}_{i})$ expressing the
fact that $x\in J_{i}\cap X$, and
$\\{\varphi_{0}(x;\overline{b}_{i})\,:\,i\in\omega\\}$ is $2$-inconsistent
since the $J_{i}$ are pairwise disjoint. In the second row, we use formulas
$\varphi_{1}(x;\epsilon_{j},\epsilon_{j+1})$ expressing the property that

$\epsilon_{j+1}<f(x)<\epsilon_{j}$

and again $\\{\varphi_{1}(x;\epsilon_{j},\epsilon_{j+1})\,:\,j\in\omega\\}$ is
$2$-inconsistent. Furthermore, for any $(i,j)\in\omega\times\omega$, the
formula

$\varphi_{0}(x;\overline{b}_{i})\wedge\varphi_{1}(x;\epsilon_{j},\epsilon_{j+1})$

is consistent since it is satisfied by $a_{i,j}$. Thus we have an inp-pattern
of depth $2$ in $X$, contradicting the assumption that $X$ has burden $1$.

∎

The next lemma generalizes a key fact from [10] about definable functions in
the dp-minimal case.

######  Lemma 2.14.

If there is an infinite discrete set definable in $\mathcal{R}$, then
functions on $R$ are bounded away from $0$.

###### Proof.

Suppose, to the contrary, that $f:R\rightarrow\overline{R}$ is definable,
$f(x)>0$ for every $x\in R$, and $f$ is not bounded away from $0$. Then there
is a nonempty interval $I$ such that for any $\epsilon>0$ and any subinterval
$J$ of $I$, there is $a\in J$ such that $f(a)\leq\epsilon$. Therefore, $f$ is
not bounded away from $0$ on any subinterval of $I$. By Lemma 2.13, any
subinterval of $I$ has burden $2$. By Lemma 2.2, there is some interval
$(0,\epsilon)$ of burden $1$, and shrinking $\epsilon$ as necessary, we may
assume that $\epsilon$ is less than the diameter of $I$. Since burden is
translation-invariant, we conclude that there is a subinterval of $I$ of
burden $1$, a contradiction.

∎

We record an immediate consequence of Lemma 2.14.

######  Corollary 2.15.

Suppose there is an infinite discrete set definable in $\mathcal{R}$. Suppose
that $I$ is an interval and $X\subseteq I$ is definable, dense, and codense in
$I$. Then functions on $X$ are bounded away from $0$.

###### Proof.

If $g\,:\,X\rightarrow\overline{R}$ is definable and has positive values, pick
any $a>0$ and extend $g$ to a definable function
$f\,:\,R\rightarrow\overline{R}$ by the rule that $f(x)=a$ when $x\notin X$.
Now apply the previous Lemma to conclude that $f$, and hence $g$, is bounded
away from $0$. ∎

######  Definition 2.16.

For a definable set $X$ we write $a\sim_{X,\delta}b$ or simply
$a\sim_{\delta}b$ for the equivalence relation on $R$ defined by

$\forall\,\epsilon\in(-\delta,\delta)\left[a+\epsilon\in X\Leftrightarrow
b+\epsilon\in X\right],$

and $a\sim_{X}b$ (or simply $a\sim b$) means that for some $\delta>0$, we have
$a\sim_{\delta}b$.

First we note the following easy but useful fact:

######  Lemma 2.17.

If $X$ is definable, $a,b\in R$, $a\sim_{X,\delta}b$, and $|\epsilon|<\delta$,
then $a+\epsilon\sim_{X,\delta-|\epsilon|}b+\epsilon$. In particular,
$a+\epsilon\sim_{X}b+\epsilon$.

######  Lemma 2.18.

Let $X$ be definable. Fix any $a\in X$ and let $\widetilde{X}=\\{b\in
X\,:\,b\sim_{X}a\\}$. Then $|\widetilde{X}/\sim_{\widetilde{X}}|=1$.

###### Proof.

Let $b\in\widetilde{X}$, and we will show that $b\sim_{\widetilde{X}}a$.
Choose $\delta>0$ such that $b\sim_{X,\delta}a$ and suppose that
$\epsilon\in(-\delta,\delta)$. By Lemma 2.17, we have
$b+\epsilon\sim_{X}a+\epsilon$, so in particular $b+\epsilon\sim_{X}a$ if and
only if $a+\epsilon\sim_{X}a$. In other words, $b+\epsilon\in\widetilde{X}$ if
and only if $a+\epsilon\in\widetilde{X}$, so $b\sim_{\widetilde{X},\delta}a$.
∎

Now we look for type-definable subgroups related to definable subsets of $R$.
The proof of the next lemma is similar to that of Theorem 3.6 from [20].

######  Lemma 2.19.

Suppose that:

  1. (1)

$X\subseteq R$ is definable;

  2. (2)

$I$ is an open interval such that $X\cap I$ is infinite;

  3. (3)

functions on $X\cap I$ are bounded away from $0$;

  4. (4)

$X\cap I$ is not discrete; and

  5. (5)

$|(X\cap I)/\sim|=1$.

Then for any $a\in X\cap I$, there is a nonzero type-definable convex subgroup
$C$ of $(R,+)$ such that $(X-a)\cap C$ is also a subgroup of $(R,+)$.

###### Proof.

Fix $a\in X\cap I$ and define $f:X\rightarrow\overline{R}$ to be the function

$f(x)=\sup\\{\delta\in R\,:\,x\sim_{\delta}a\\}.$

Note that $f(x)>0$ on $I$. Since functions on $X\cap I$ are bounded away from
zero, we may pick an $\epsilon>0$ and an open subinterval $J\subseteq I$ such
that $X\cap J$ is infinite and $f(x)>\epsilon$ for every $x\in J\cap X$.

######  Claim 2.20.

There is a positive element $\epsilon_{0}<\epsilon$ such that
$f(x)>\epsilon_{0}$ for every $x\in(a-\epsilon_{0},a+\epsilon_{0})$.

###### Proof.

First, we may assume that $f(a)>\epsilon$ (by replacing $\epsilon$ by a
positive element less than $f(a)$ if necessary). Pick some $b\in X\cap J$ and
some $\epsilon^{\prime}>0$ such that $a\sim_{\epsilon^{\prime}}b$,
$(b-\epsilon^{\prime},b+\epsilon^{\prime})\subseteq J$, and
$\epsilon^{\prime}\leq\epsilon$. Now pick a positive element
$\epsilon^{\prime\prime}$ such that
$2\epsilon^{\prime\prime}<\epsilon^{\prime}$ and let $z$ be an arbitrary
element of $(-\epsilon^{\prime\prime},\epsilon^{\prime\prime})$. Then we have

(6) $a+z\sim_{\epsilon^{\prime\prime}}b+z$

since $a\sim_{\epsilon^{\prime}}b$ and using Lemma 2.17. On the other hand,
since $b+z\in J$, we also have that $f(b+z)>\epsilon>\epsilon^{\prime\prime}$
(by our initial choice of the interval $J$), and so

(7) $b+z\sim_{\epsilon^{\prime}}a.$

By (6), (7), and transitivity, we conclude that
$a+z\sim_{\epsilon^{\prime\prime}}a$. Therefore, given that
$f(a)>\epsilon>\epsilon^{\prime\prime}$, it follows that for any
$a+z\in(a-\epsilon^{\prime\prime},a+\epsilon^{\prime\prime})$, we have
$f(a+z)\geq\epsilon^{\prime\prime}$. Then if
$0<\epsilon_{0}<\epsilon^{\prime\prime}$ and
$a+z\in(a-\epsilon_{0},a+\epsilon_{0})$, we have $f(a+z)>\epsilon_{0}$, as
desired. ∎

Pick $\epsilon_{0}$ as in the Claim above and small enough so that
$(a-\epsilon_{0},a+\epsilon_{0})\subseteq I$. Replace $I$ by the subinterval
$(a-\epsilon_{0},a+\epsilon_{0})$ and note that all the hypotheses of the
Lemma still hold (since (4) and (5) imply that $X\cap I$ has no isolated
points, hence $X\cap(a-\epsilon_{0},a+\epsilon_{0})$ is infinite, and the rest
are trivial).

Define

$C=\bigcap_{n\in\N}\\{x\in R:-\epsilon_{0}<nx<\epsilon_{0}\\}$

and note that $C$ is closed under addition by the triangle quality. Thus $C$
is a convex type-definable subgroup of $(R,+)$. Let $H=(X-a)\cap C$ and
suppose that $g,h\in H$. Then $g+h\in C$. Furthermore, since
$f(a+g)>\epsilon_{0}$ (by the conclusion of the Claim above), we have
$a+g\sim_{\epsilon_{0}}a$. Hence by Lemma 2.17 and the fact that
$|h|<\epsilon_{0}$, we obtain

$a+g+h\sim a+h.$

But $a+h\in X$ since $h\in X-a$, so $g+h\in X-a$. This shows that $H$ is
closed under addition. For closure under negation, if $g\in(X-a)\cap C$, then
it is immediate that $-g\in C$, while $a+g\sim_{\epsilon_{0}}a$ and
$|g|<\epsilon_{0}$ imply (using Lemma 2.17 again) that

$a+g-g\sim a-g$ $\Rightarrow a\sim a-g,$

and therefore $a-g\in X$, hence $-g\in X-a$.

∎

Finally we come to our generalization of Theorem 2.9 in the case when
$\mathcal{R}$ has burden $2$ instead of dp-rank $2$. The example in the
subsequent section demonstrates the necessity of the extra hypothesis that
$X/\sim$ is finite.

######  Theorem 2.21.

If $\mathcal{R}$ is a divisible OAG of burden $\leq 2$ in which an infinite
discrete set is definable, then there cannot be a definable set $X\subseteq R$
which is dense and codense in some nonempty interval and such that $X/\sim$ is
finite.

###### Proof.

Suppose towards a contradiction there is such a set $X$. Since $X/\sim$ is
finite, there is some $a\in X$ and some nonempty interval $I$ in which
$[a]_{\sim}$ is dense and codense. Let $Z=[a]_{\sim}\cap I$, and by Lemma
2.18, we have that $|Z/\sim_{Z}|=1$.

Since an infinite discrete set is definable in $\mathcal{R}$, by Corollary
2.15, functions on $Z$ are bounded away from zero. Fix any $a\in Z\cap I$, and
we may apply Lemma 2.19 to obtain a nonzero convex subgroup $C$ of $\langle
R;+\rangle$ such that $H:=C\cap(Z-a)$ is a subgroup. By our assumptions on
$Z$, $H$ is dense and codense in $C$. Pick any $g\in C\setminus H$.

######  Claim 2.22.

The set $\\{\frac{g}{n}\,:\,n\in\N\setminus\\{0\\}\\}$ contains
representatives of infinitely many cosets of $H$.

###### Proof.

On the one hand, if the image of $g$ in $R/H$ has infinite order, then for any
distinct $n,m\in\N\setminus\\{0\\}$, we have $mg-ng\notin H$, and hence
$\frac{g}{n}-\frac{g}{m}=\frac{mg-ng}{nm}\notin H$, so we are done. Otherwise,
let $k$ be the least positive natural number such that $kg\in H$, and note
that if $\textup{GCD}(k,m)=1$, then $mg\notin H$. Thus whenever $1\leq i<j$,

$\frac{g}{k^{j}}-\frac{g}{k^{i}}=\frac{(1-k^{j-i})g}{k^{j}},$

but $\textup{GCD}(1-k^{j-i},k)=1$, so this difference cannot be in $H$. ∎

By the Claim, the convex set $C$ intersects infinitely many cosets of the
group $H$. Now we can easily build a depth-2 inp-pattern within any interval
$J\subseteq C$, as follows: for the first row, let

(8) $\varphi_{0}(x;a_{i},b_{i}):=a_{0,i}<x<b_{0,i}$

(for $i<\omega$) be any family of formulas which define pairwise disjoint open
subintervals of $J$; and for the second row, let

(9) $\varphi_{1}(x;c_{j}):=x-c_{j}\in X$

with the parameters $\\{c_{j}\,:\,j\in\omega\\}$ chosen from $C$ which
represent distinct cosets of $H$ (which is possible by the Claim). Since $H$
is a dense and codense subgroup of $C$, every coset $c_{j}+H$ is also dense
and codense in $C$, and hence each pair
$\varphi_{0}(x;a_{i},b_{i})\wedge\varphi_{1}(x;c_{j})$ is consistent. Thus we
have an inp-pattern of depth $2$ in any subinterval $J$ of $C$, contradicting
Lemma 2.2 and finishing the proof. ∎

Thus we have established that for divisible $\mathcal{R}$ we can not
simultaneously have an infinite definable discrete set and a definable dense
codense set $X$ with $X/\sim$ finite. Next we consider the case in which
$X\subseteq R$ is definable and $X/\sim$ is infinite. First we need a
preliminary lemma:

######  Lemma 2.23.

If there is an infinite definable discrete set in $\mathcal{R}$, then there is
no definable $X\subseteq R$ such that $X$ divides over some elementary
submodel $\mathcal{R}_{0}$ of $\mathcal{R}$ and $0$ is an accumulation point
of $X$.

###### Proof.

Otherwise, say there is such a set $X=X_{\overline{a}}$ defined over
parameters $\overline{a}$. Pick any interval $I$ around $0$, and we will
construct an inp-pattern of depth $2$ in $I$ as follows: first, since
$X_{\overline{a}}$ divides, pick a set of $\mathcal{R}_{0}$-conjugates
$\\{X_{\overline{a}_{i}}\,:\,i\in\omega\\}$ of $X_{\overline{a}}$ which are
$k$-inconsistent for some $k$, and this will be the first row of the inp-
pattern. For the second row, we recursively construct a sequence of points

$b_{0}>c_{0}>b_{1}>c_{1}>\ldots>0$

as follows: first, let $b_{0}$ be any positive element of $I$. Since $0$ is an
accumulation point of $X$, it is also an accumulation point of each of its
conjugates $X_{\overline{a}_{i}}$, so by saturation we can pick $c_{0}>0$ so
that the interval $J_{0}:=(c_{0},b_{0})$ intersects each of the sets
$X_{\overline{a}_{i}}$. In general, once we have constructed $b_{i}$ and
$c_{i}$ for all $i\leq n$, we pick an arbitrary $b_{n+1}\in(0,c_{n})$, and
then as before the fact that $0$ is an accumulation point of each conjugate of
$X_{\overline{a}}$ allows us to pick $c_{n+1}\in(0,b_{n+1})$ so that
$J_{n+1}:=(c_{n+1},b_{n+1})$ intersects every $X_{\overline{a}_{i}}$.

Now the second row in our inp-pattern will consist of the formulas
$\varphi_{1}(x;b_{j},c_{j})$ asserting that $b_{j}<x<c_{j}$, which define
pairwise-disjoint intervals which each intersect every set
$X_{\overline{a}_{i}}$, as we wanted.

Since this inp-pattern can be constructed within any interval $I$ around $0$,
by Lemma 2.2 we have a contradiction. ∎

The next proposition is similar to the well-known fact that in an NIP theory,
global types which do not divide over a small submodel are invariant over said
submodel (see Chapter 5 of [21], or Proposition 2.1 of [12]). However, we
require a version of this which assumes only that the formula we are working
with is NIP.

######  Proposition 2.24.

Suppose $\varphi(\overline{x};\overline{y})$ is an NIP formula in a theory
$T$, $\mathcal{N}\prec\mathcal{M}$ are models of $T$ such that $\mathcal{M}$
is $|N|^{+}$\- saturated, and $p(\overline{x})$ is a complete
$\varphi(\overline{x};\overline{y})$-$M$-type222That is, a maximal consistent
collection of boolean combinations of instances
$\varphi(\overline{x};\overline{b})$ of $\varphi(\overline{x};\overline{y})$
with $\overline{b}$ from $M$. which does not divide over $N$. Then
$p(\overline{x})$ is $N$-invariant.

###### Proof.

The same proof as in [12] goes through. Namely, suppose that
$\overline{a}_{0},\overline{a}_{1}\in M$ and
$\textup{tp}(\overline{a}_{0}/N)=\textup{tp}(\overline{a}_{1}/N)$, and assume
towards a contradiction that
$\varphi(\overline{x};\overline{a}_{0})\wedge\neg\varphi(\overline{x};\overline{a}_{1})\in
p(\overline{x})$. As $N$ is a model, there is some $\overline{b}$ such that
both $\overline{a}_{0},\overline{b}$ and $\overline{a}_{1},\overline{b}$ can
be extended to infinite $N$-indiscernible sequences (see Facts 1.11 and 1.12
(ii) of [2]), and by saturation we may assume $\overline{b}\in M$. If
$\varphi(\overline{x};\overline{b})\in p$, then for the $N$-indiscernible
sequence $\\{\overline{a}^{\prime}_{i}:i\in\omega\\}$ extending
$\overline{a}_{1},\overline{b}$, we have
$\neg\varphi(\overline{x};\overline{a}^{\prime}_{0})\wedge\varphi(\overline{x};\overline{a}^{\prime}_{1})\in
p(\overline{x})$; and if to the contrary
$\neg\varphi(\overline{x};\overline{b})\in p$, then let
$\\{\overline{a}^{\prime}_{i}:i\in\omega\\}$ be the $N$-indiscernible sequence
extending $\overline{a}_{0},\overline{b}$, and we have
$\varphi(\overline{x};\overline{a}^{\prime}_{0})\wedge\neg\varphi(\overline{x};\overline{a}^{\prime}_{1})\in
p(\overline{x})$. In either case,

(10)
$\neg\left[\varphi(\overline{x};\overline{a}^{\prime}_{0})\leftrightarrow\varphi(\overline{x};\overline{a}^{\prime}_{1})\right]\in
p(\overline{x}).$

Since $p(\overline{x})$ does not divide over $N$, the partial type

$\\{\neg\left[\varphi(\overline{x};\overline{a}^{\prime}_{2i})\leftrightarrow\neg\varphi(\overline{x};\overline{a}^{\prime}_{2i+1})\right]\,:\,i<\omega\\}$

must be consistent. As any Boolean combination of NIP formulas is NIP,
$\neg\left[\varphi(\overline{x};\overline{y}_{1})\leftrightarrow\neg\varphi(\overline{x};\overline{y}_{2})\right]$
is NIP, but we have just shown that this formula has infinite alternation
rank, which is a contradiction. ∎

######  Proposition 2.25.

Suppose that there is an infinite discrete set definable in $\mathcal{R}$,
$X\subseteq R$ is definable, and the formula $\varphi(x;y)$ expressing that
$x\in X-y$ is NIP. Then $X/\sim$ is finite.

###### Proof.

Suppose that $X$ is definable over the $\omega$-saturated model
$\mathcal{R}_{0}$. Let $\mathcal{R}_{1}$ be an $|R_{0}|^{+}$-saturated
elementary extension of $\mathcal{R}_{0}$. If $X/\sim$ is infinite, then it
has unboundedly many equivalence classes (since $\sim$ is a definable
equivalence relation) and thus we can find $a,b\in X(R_{1})$ such that
$\textup{tp}(a/\mathcal{R}_{0})=\textup{tp}(b/\mathcal{R}_{0})$ and $a$ is not
in the same $\sim$-class as $b$. This means that for every $\epsilon>0$, there
is some $g\in(-\epsilon,\epsilon)$ such that

$\neg\left[a+g\in X\leftrightarrow b+g\in X\right],$

thus

$g\in(X-a)\Delta(X-b),$

and so $0$ is an accumulation point of the set $Z:=(X-a)\Delta(X-b)$. By Lemma
2.23, $Z$ does not divide over $R_{0}$. By $\omega$-saturation, $Z$ does not
fork over $R_{0}$ (see, for instance, Proposition 5.14 of [21]). Therefore $Z$
has an extension to a complete $\varphi(x;y)$-type $p(x)$ over $R_{1}$ which
does not fork over $R_{0}$. But the fact that $a\equiv_{R_{0}}b$ implies that
$Z$ is not $R_{0}$-invariant, and hence $p(x)$ cannot be $R_{0}$-invariant
either, so by Proposition 2.24, we conclude that $\varphi(x;y)$ cannot be NIP.

∎

Putting this all together, we obtain:

######  Theorem 2.26.

Suppose that $\mathcal{R}$ is a divisible OAG of burden $2$ in which an
infinite discrete set is definable and also there is a definable $X\subseteq
R$ which is dense and codense in some nonempty interval. Then the formula
$\varphi(x;y)$ expressing that $x\in X-y$ has the independence property.

###### Proof.

By Theorem 2.21, $X/\sim$ is infinite. Hence by Proposition 2.25, we conclude
that $\varphi(x;y)$ has the independence property. ∎

######  Question 2.27.

Are there divisible OAGs of burden $2$ (or dp-rank $2$) in which both a
Cantor-like set $C$ and a set $X$ which is dense and codense on an infinite
interval are definable?

##  3\. A theory with burden $2$ with both an infinite definable discrete set
and a dense-codense set

In this section, we construct an example of a complete theory $T$ with the
following properties:

  * •

$T$ expands the theory divisible ordered Abelian groups;

  * •

$T$ is definably complete;

  * •

$T$ has burden 2; and

  * •

if $\mathcal{M}\models T$ then there are both an infinite definable discrete
subset of $M$ and a definable dense and codense subset of $M$.

This establishes that the hypotheses of Theorem 2.26 can in fact be satisfied.
In order to accomplish this we need to develop some background facts that
slightly generalize some of the work in [3].

Recall that in [3] the authors show that given a theory $T$ in a language
$\mathcal{L}$ which eliminates $\exists^{\infty}$ and a distinguished unary
predicate $S$ from $\mathcal{L}$ if we expand $\mathcal{L}$ to
$\mathcal{L}(P)$ by adding a new unary predicate $P$ then the
$\mathcal{L}(P)$-theory

$T_{S}=T\cup\\{\forall x\left[P(x)\rightarrow S(x)\right]\\}$

has a model companion $T_{G}$ with multiple desirable properties.

Here we point out the the results from [3, section 2] all hold if we slightly
weaken the assumption that $T$ eliminates $\exists^{\infty}$ to the assumption
that $T$ eliminates $\exists^{\infty}$ relative to $S$.

######  Definition 3.1.

For a theory $T$ and a distinguished unary predicate $S$ we say that $T$
eliminates $\exists^{\infty}$ relative to $S$ if for any formula
$\varphi(x,\overline{y})$ so that $T\models\forall
x\left[\varphi(x,\overline{y})\rightarrow S(x)\right]$ there is
$n\in\mathbb{N}$ so that if $\mathcal{M}\models T$ and $\overline{a}\in
M^{|\overline{y}|}$ and $|\varphi(M,\overline{a})|>n$ then
$\varphi(M,\overline{a})$ is infinite.

We now provide the slight modifications to the result from [3, Section 2] that
we will need to construct and analyze our theory. All the proofs are mutatis
mutandis from those in the original paper of Chatzidakis and Pillay. We
include the specific analogous result from [3] with each statement. From now
on we assume that $T$ eliminates $\exists^{\infty}$ relative to $S$. We also
assume that $T$ eliminates quantifiers.

######  Definition 3.2.

[3, Definitions 2.1] Let $\mathcal{M}$ be a saturated model of $T$, $C$ a
small subset of $M$, $\overline{a}=(a_{1},\dots,a_{n})$ a tuple of elements of
$M$, and $\varphi(\overline{x})$ a formula defined with parameters in $C$.

  1. (1)

We define the algebraic dimension of $\overline{a}$ over $C$,
$\text{a-dim}(\overline{a}/C)$, to be the maximal length of a sequence $j(i)$
of positive integers $\leq n$ such that:

$a_{j(1)}\notin\textup{acl}(C),a_{j(i)}\notin\textup{acl}(C,a_{j(1)},\dots,a_{j(i-1)}).$

  2. (2)

We set

$\text{a-dim}(\varphi(\overline{x}))=\sup\\{\text{a-dim}(\overline{a}/C)|M\models\varphi(\overline{a})\\}.$

######  Fact 3.3.

[3, Lemma 2.2] Let $\mathcal{M}\models T$,
$\varphi(x_{1},\dots,x_{n},\overline{y})$ an $\mathcal{L}$-formula so that

$T\models\forall
x_{1},\dots,x_{n}(\varphi(\overline{x},\overline{y})\rightarrow\bigwedge_{1\leq
i\leq n}S(x_{i}))$

and $d$ an integer. Then the set
$\\{\overline{b}\;|\;\text{a-dim}(\varphi(\overline{x},\overline{b}))=d\\}$ is
definable.

######  Fact 3.4.

[3, Lemma 2.3] Let $\mathcal{M}$ be a saturated model of $T$ and
$\varphi(x_{1},\dots,x_{n},\overline{y})$ an $\mathcal{L}$-formula so that

$T\models\forall
x_{1},\dots,x_{n}(\varphi(\overline{x},\overline{y})\rightarrow\bigwedge_{1\leq
i\leq n}S(x_{i})).$

Then the set $\Sigma(\varphi)$ of tuples $\overline{b}$ so that there is
$\overline{a}\in M$ satisfying $\varphi(\overline{x},\overline{b})$ and
$\overline{a}\cap\textup{acl}(\overline{b})=\emptyset$ is definable.

######  Fact 3.5.

[3, Theorem 2.4] The theory $T_{S}$ has a model companion $T_{G}$, whose
axiomatization is obtained by expressing in a first order way the following
properties of a model $(M,P)$:

  1. (1)

$M\models T$.

  2. (2)

For every $\mathcal{L}$-formula $\varphi(x_{1},\dots,x_{n},\overline{z})$ so
that

$T\models\forall
x_{1},\dots,x_{n}(\varphi(\overline{x},\overline{z})\rightarrow\bigwedge_{1\leq
i\leq n}S(x_{i})),$

for every subset $I$ of $\\{1,\dots,n\\}$,

$\forall\overline{z}\left[\exists\overline{x}\varphi(\overline{x},\overline{z})\wedge(\overline{x}\cap\textup{acl}_{T}(\overline{z})=\emptyset)\wedge\bigwedge_{1\leq
i<j\leq n}x_{i}\not=x_{j}\right]$
$\rightarrow\left[\exists\overline{x}\varphi(\overline{x},\overline{z})\wedge\bigwedge_{i\in
I}(x_{i}\in P)\wedge\bigwedge_{i\notin I}(x_{i}\notin P)\right]$

where $\textup{acl}_{T}$ is the algebraic closure operator for $T$.

######  Fact 3.6.

[3, Proposition 2.5] Let $(\mathcal{M},P)$ and $(\mathcal{N},Q)$ be models of
$T_{G}$, and let $A$ be a common subset of $M$ and $N$. Then

$(\mathcal{M},P)\equiv_{A}(\mathcal{N},Q)\Leftrightarrow(\textup{acl}_{T}(A),P\cap\textup{acl}_{T}(A))\simeq_{A}(\textup{acl}_{T}(A),Q\cap\textup{acl}_{T}(A)).$

######  Fact 3.7.

[3, Corallaries 2.6]

  1. (1)

The completions of $T_{G}$ are obtained by describing
$P\cap\textup{acl}_{T}(\emptyset)$.

  2. (2)

If $\overline{a},\overline{b}$ are tuples from $\mathcal{M}\models T_{G}$ and
$A\subseteq M$, then $\textup{tp}(\overline{a}/A)=\textup{tp}(\overline{b}/A)$
if and only if there is an $A$-isomorphism of $\mathcal{L}(P)$ structures from
$\textup{acl}_{T}(A,\overline{a})$ to $\textup{acl}_{T}(A,\overline{b})$ which
carries $\overline{a}$ to $\overline{b}$.

  3. (3)

Let $a\in\mathcal{M}\models T_{G}$, $A\subseteq M$. Then $a$ is algebraic over
$A$ if and only if $a\in\textup{acl}_{T}(A)$. Thus algebraic closures in the
sense of $T$ and $T_{G}$ coincide.

  4. (4)

Modulo $T_{G}$, every formula $\varphi(\overline{x})$ is equivalent to a
disjunction of formulas of the form
$\exists\overline{y}\psi(\overline{x},\overline{y})$, where $\psi$ is
quantifier-free, and for every $(\overline{a},\overline{b})$ satisfying
$\psi$, $\overline{b}\in\textup{acl}_{T}(\overline{a})$.

Given this general background information we now proceed to analyze the
specific theory $T$ with which we plan to work.

Let $T$ be the theory of the structure $\langle\R;+,<,\mathbb{Z}\rangle$
formulated in the language
$\mathcal{L}=\\{+,<,0,1,\lfloor\;\rfloor,S,\lambda\\}_{\lambda\in\Q}$ where
$S$ is interpreted as the interval $(0,1)$, the $\lambda$ are simply
multiplication by $\lambda\in\Q$ and $\lfloor
x\rfloor=\max\\{y\in\mathbb{Z}:y\leq x\\}$. Note we do not include a separate
predicate for $\mathbb{Z}$ as the set of integers is defined by the quantifier
free formula $\lfloor x\rfloor=x$. Also notice that as $T$ is linearly ordered
$\textup{acl}=\textup{dcl}$ in models of $T$. By results from the appendix of
[15] the $\mathcal{L}$-theory $T$ eliminates quantifiers and is universally
axiomatizable. We record some additional facts about $T$ which we will use
repeatedly without further mention.

######  Fact 3.8.

  1. (1)

If $\mathcal{M}\models T$ and $f:M^{n}\to M$ is definable then $f$ is given
piecewise by terms; more precisely, if $f$ is definable with parameters
$\overline{c}$, then there are $\overline{c}$-definable sets
$X_{1},\dots,X_{k}$ partitioning $M^{n}$ and terms
$t_{1}(\overline{x},\overline{y}),\dots,t_{k}(\overline{x},\overline{y})$ so
that $f(\overline{x})=t_{i}(\overline{x},\overline{c})$ on $X_{i}$.

  2. (2)

$T$ has dp-rank 2.

  3. (3)

If $\mathcal{M}\models T$ and $X\subseteq M$ is definable then $X$ is either
discrete or has interior.

  4. (4)

If $\mathcal{M}\models T$ and $X\subseteq(0,1)$ is definable then $X$ is a
finite union of points and intervals, so $T$ eliminates $\exists^{\infty}$
relative to $S$ and the induced structure on $(0,1)$ is o-minimal.

  5. (5)

If $\mathcal{M}\models T$, $X\subseteq M$ is definable and discrete and
$f:M\to M$ is definable then $f[X]$ is discrete.

  6. (6)

If $\mathcal{M}\models T$, $U\subseteq M$ is an open interval and $f:U\to M$
is definable then there is an open subinterval $V\subseteq U$ so that $f$ is
equal to a linear function of the form $x\mapsto\lambda x+a$ on $V$.

###### Proof.

For (1), it is well known that this follows from the fact that $T$ is
universally axiomatizable and model complete. For completeness we outline a
proof. Fix $\mathcal{M}$ and $f$. Assume that $f$ is definable with parameters
$\overline{c}$. Let $\overline{a}\in M$. Consider the closure of
$\overline{a}\overline{c}$ under all terms,
$\langle\overline{a}\overline{c}\rangle$. As $T$ is universal
$\langle\overline{a}\overline{c}\rangle\models T$. As $T$ is model complete
$\langle\overline{a}\overline{c}\rangle\preceq\mathcal{M}$. In particular
$f(\overline{a})\in\langle\overline{a}\overline{c}\rangle$ so that
$f(\overline{a})=t(\overline{a},\overline{c})$ for some term $t$. The result
then follows by compactness.

See the note after the proof of Theorem 3.1 in [5] for (2). As $T$ is clearly
definably complete (3) follows from Corollary 2.10. (4) is a special case of
[5, Lemma 3.3(1)]. (5) follows from [5, Corollary 2.17]. (6) follows from [5,
Lemma 3.2(2)] and (1). ∎

As $T$ eliminates $\exists^{\infty}$ relative to $S$ we can form the theory
$T_{G}$. For convenience we fix a completion $T^{*}_{G}$ of $T_{G}$ by
specifying that if $\mathcal{M}\models T_{G}$ then
$P(M)\cap\textup{dcl}{(\emptyset)}=\emptyset$ (see Fact 3.7(1)).

######  Lemma 3.9.

$T_{G}^{*}$ has quantifier elimination and is definably complete.

###### Proof.

That $T^{*}_{G}$ has quantifier elimination follows from Fact 3.7 (4) together
with the facts that $\textup{acl}_{T}=\textup{dcl}_{T}$, definable functions
are given piecewise by terms (by Fact 3.8 (1)), and a use of compactness.

To establish that $T_{G}^{*}$ is definably complete we work in the structure
$\mathcal{R}=\langle\R;+,<,0,1,\lfloor\;\rfloor,S,\lambda\rangle_{\lambda\in\Q}$.
It suffices to show that there is
$G\subseteq\R\setminus\textup{dcl}(\emptyset)$ so that

$\langle\R;+,<,0,1,\lfloor\;\rfloor,S,G,\lambda\rangle_{\lambda\in\Q}$

is a model of $T_{G}^{*}$.

We construct $G\subseteq\R$ and its complement $\overline{G}=\R\setminus G$
simultaneously by induction. Let $\bm{c}=\left|\R\right|$.

By an instance of axiom (2) in Fact 3.5 we mean a triple
$C=(\varphi(\overline{x},\overline{y}),\overline{c},I)$ so that:

  1. (1)

$\varphi(x_{1},\dots,x_{n},\overline{y})$ is an $\mathcal{L}$-formula;

  2. (2)

$\overline{c}\in{}^{|\overline{y}|}$ and in some extension $\mathcal{M}$ of
$\mathcal{R}$ there is $\overline{a}\in M^{|\overline{x}|}$ satisfying
$\varphi(\overline{x},\overline{c})$ with
$\overline{a}\cap\textup{acl}{(\overline{c})}=\emptyset$ and all coordinates
of $\overline{a}$ distinct; and

  3. (3)

$I\subseteq\\{1,\dots,n\\}$.

We say for a set $G^{\prime}\subseteq\R$ a tuple
$\overline{a}\in{}^{|\overline{x}|}$ satisfies $C$ relative to $G^{\prime}$ if
$\mathcal{R}\models\varphi(\overline{a},\overline{c})$ and $a_{i}\in
G^{\prime}$ if and only if $i\in I$.

List all instances of axiom (2) as
$C_{\alpha}=(\varphi_{\alpha}(\overline{x},\overline{y}),\overline{c}_{\alpha},I_{\alpha})$
for $\alpha\in\bm{c}$.

We construct $G$ as $\bigcup_{\alpha\in\bm{c}}G_{\alpha}$ and
$\overline{G}=\bigcup_{a\in\bm{c}}\overline{G}_{\alpha}$ so that:

  1. (1)

$|G_{\alpha}|<\bm{c}$ and $|\overline{G}_{\alpha}|<\bm{c}$ for all
$\alpha<\bm{c}$;

  2. (2)

$G_{\alpha}\subseteq G_{\beta}$ and
$\overline{G}_{\alpha}\subseteq\overline{G}_{\beta}$ for $\alpha<\beta$;

  3. (3)

$G_{0}=\emptyset$ and $\overline{G}_{0}=\textup{dcl}(\emptyset)$;

  4. (4)

$G_{\alpha}\cap\overline{G}_{\alpha}=\emptyset$ for all $\alpha<\bm{c}$; and

  5. (5)

there is $\overline{c}_{\beta}\in G_{\alpha}\cup\overline{G}_{\alpha}$
satisfying condition $C_{\beta}$ relative to $G_{\alpha}$ for all
$\beta<\alpha$.

If we can construct such a $G$ then it is immediate that

$\langle\R;+,<,0,1,\lfloor\;\rfloor,S,G,\lambda\rangle_{\lambda\in\Q}\models
T_{G}^{*}.$

Constructing $G_{0}$ and $\overline{G}_{0}$ is immediate. Also if $\alpha$ is
a limit ordinal and we have constructed $G_{\beta}$ and $\overline{G}_{\beta}$
for all $\beta<\alpha$ then we simply let
$G_{\alpha}=\bigcup_{\beta<\alpha}G_{\alpha}$ and
$\overline{G}_{\alpha}=\bigcup_{\beta<\alpha}\overline{G}_{\beta}$.

Thus suppose we have a successor ordinal $\alpha+1$ and we have constructed
$G_{\beta}$ and $\overline{G}_{\beta}$ for all $\beta\leq\alpha$. We need to
extend the construction to satisfy
$C_{\alpha}=(\varphi_{\alpha}(\overline{x},\overline{y}),\overline{c}_{\alpha},I_{\alpha})$.
Let $X_{\alpha}\subseteq(0,1)^{n}$ be the subset of n defined by
$\varphi_{\alpha}(\overline{x},\overline{c}_{\alpha})$. By Fact 3.8 (2) the
structure induced by $\mathcal{R}$ on $(0,1)$ is o-minimal. Hence without loss
of generality we may assume that $X_{\alpha}$ is an o-minimal cell. After
potentially permuting the variables of the defining formula for $X_{\alpha}$
we may without loss of generality assume that

$X_{\alpha}=\\{(z_{1},\dots,z_{l},y_{1},\dots,y_{m}):\overline{z}\in U\text{
and }y_{i}=g_{i}(\overline{z})\text{ for all }1\leq i\leq m\\}$

where $U\subseteq{}^{l}$ is a definable open o-minimal cell and the $g_{i}$
are definable continuous functions on $U$ which are never equal on $U$. After
refining $U$ if necessary we may also assume that if
$a_{1},\dots,a_{l-1}\in\pi(U)$ (where $\pi$ is projection on the first $l-1$
coordinates) then $g_{i}:U_{(a_{1},\dots,a_{l-1})}\to\R$ is monotone for all
$1\leq i\leq m$ (where $U_{(a_{1},\dots,a_{l-1})}$ is the fiber in $U$ over
$(a_{1},\dots,a_{l-1})$). Furthermore we may also assume that for any $1\leq
i\leq m$ if for some $(a_{1},\dots,a_{l-1})\in\pi(U)$ the function
$g_{i}:U_{(a_{1},\dots,a_{l-1})}\to\R$ is increasing then the same is true for
all $(b_{1},\dots b_{l-1})\in\pi(U)$ and the same holds for “decreasing” or
“constant” in place of “increasing”.

To build $G_{\alpha+1}$ and $\overline{G}_{\alpha+1}$ it suffices to find
$a_{1},\dots,a_{l},b_{1},\dots,b_{m}\in X_{\alpha}$ so that $a_{i}\notin
G_{\beta}\cup\overline{G}_{\beta}$ and $b_{j}\notin
G_{\beta}\cup\overline{G}_{\beta}$ for all $1\leq i\leq l$, $1\leq j\leq m$,
and $\beta\leq\alpha$. We show this by induction on $l$, the dimension of $U$.
If $l=0$ then $U$ is a point, but then there can not be $\overline{a}$ in an
extension of $\mathcal{R}$ with $\overline{a}\in X_{\alpha}$ and
$\overline{a}\cap\textup{acl}(\overline{c})=\emptyset$. Hence there can be no
such instance of axiom (2). Thus we may assume that $l>0$ we have our result
for all values less that $l$. Suppose that for some function $g_{j}$ with
$1\leq j\leq m$ it is the case that $g_{j}:U_{(a_{1},\dots,a_{l-1})}\to\R$ is
constant (for simplicity suppose that this holds for the functions
$g_{1},\dots,g_{r}$ with $0\leq r\leq m$). Thus for $1\leq i\leq r$ the
function $g_{i}$ may be thought of as a function from $\pi(U)$ to . By
induction we may find $a_{1},\dots a_{l-1}\in\pi(U)$ so that $a_{i}\notin
G_{\beta}\cup\overline{G}_{\beta}$ for any $1\leq i\leq l-1$ and
$\beta\leq\alpha$ and also so that $g_{i}(a_{1},\dots,a_{l-1})\notin
G_{\beta}\cup\overline{G}_{\beta}$ for all $1\leq i\leq r$ and all
$\beta\leq\alpha$. If there are no constant functions $g_{i}$ then we can also
easily pick $a_{1},\dots,a_{l-1}\in\pi(U)$ so that no $a_{i}\in
G_{\beta}\cup\overline{G}_{\beta}$ for any $\beta\leq\alpha$. Each function
$g_{i}$ with $r<i$ is monotone increasing or decreasing on
$U_{(a_{1},\dots,a_{l-1})}$, in particular there are less than $\bm{c}$
elements $a_{l}$ of $U_{a_{1},\dots,a_{l-1}}$ so that
$g_{i}(a_{1},\dots,a_{l})\in G_{\beta}\cup\overline{G}_{\beta}$ for any
$\beta\leq\alpha$. Also that are less that $\bm{c}$ element $a_{l}$ of
$U_{(a_{1},\dots,a_{l-1})}$ so that $a_{l}\in
G_{\beta}\cup\overline{G}_{\beta}$ for some $\beta\leq\alpha$. Thus simply due
to cardinality considerations there must be $a_{l}\in
U_{(a_{1},\dots,a_{l-1})}$ so that $a_{l}\notin
G_{\beta}\cup\overline{G}_{\beta}$ for any $\beta\leq\alpha$ and
$g_{i}(a_{1}\dots,a_{l})\notin G_{\beta}\cup\overline{G}_{\beta}$ for all
$1\leq i\leq m$ and $\beta\leq\alpha$. Let $\overline{c}$ be the $n$-tuple
$(a_{1},\dots,a_{l},g_{1}(\overline{a}),\dots,g_{m}(\overline{a}))$. Set
$G_{\alpha+1}=G_{\alpha}\cup\\{c_{i}:i\in I_{\alpha}\\}$ and
$\overline{G}_{\alpha+1}=\overline{G}_{\alpha}\cup\\{c_{i}:i\in\\{1,\dots,n\\}\setminus
I_{\alpha}\\}$.

∎

Axiom scheme (2) for $T_{G}$ from Fact 3.5 implies that if $\mathcal{M}\models
T_{G}^{*}$ then $P(M)$ must be dense and codense in $(0,1)$. Thus to establish
that $T_{G}^{*}$ is our desired example we must show that $T_{G}^{*}$ is of
burden $2$. Ideally we would simply like to reference [4, Theorem 7.3] but as
$T$ does not satisfy exchange for algebraic closure it is not clear that this
result is applicable, so we provide an _ad hoc_ proof. We need some
preliminary lemmas and observations. The following is an immediate consquence
of the axiomatization for $T_{G}$ given in Fact 3.5.

######  Fact 3.10.

Let $\mathcal{M}\models T_{G}$ and let $U\subseteq M$ be an open interval.
Furthermore suppose that $f_{i}:U\to(0,1)$ for $1\leq i\leq n$ and
$g_{j}:U\to(0,1)$ for $1\leq j\leq m$ are definable functions which are
continuous, non-constant, and monotone. If there is $V\subseteq U$ an open
interval so that $f_{i}(x)\not=g_{j}(x)$ for all $x\in V$ and all $i,j$ then
there is $x\in V$ so that $f_{i}(x)\in P(M)$ for all $i$ and $g_{j}(x)\notin
P(M)$ for all $j$.

######  Lemma 3.11.

Let $\mathcal{M}\models T_{G}^{*}$ and $f:M\to(0,1)$ be definable. Then there
are only finitely many $a\in(0,1)$ so that $f^{-1}(a)$ has nonempty interior.

###### Proof.

Let

$X=\\{b\in M:f\text{ is constant in a neighborhood of }b\\}.$

Either $X$ is empty in which case we are done or it is a nonempty open set and
hence a union of open intervals by definable completeness. Also by definable
completeness if $I$ is any one of these intervals $f$ is constant on $I$. Let
$X_{0}$ be the set of midpoints of these intervals. $X_{0}$ is definable and
discrete. Thus $f[X_{0}]$ is discrete and as $f[X_{0}]\subseteq(0,1)$ it must
be finite. This establishes the lemma.

∎

######  Lemma 3.12.

Let $\mathcal{M}\models T_{G}^{*}$ and let $X\subseteq M$ be definable. $X$ is
a finite union of sets definable by formulas of the form:

$\psi(x)\wedge\bigwedge_{i\in I}P(t_{i}(x))\wedge\bigwedge_{j\in J}\neg
P(s_{j}(x))$

where $\psi(x)$ is an $\mathcal{L}$-formula possibly with parameters, $I$ and
$J$ are finite sets, and the $t_{i}$’s and $s_{j}$’s are terms possibly with
parameters so that:

  1. (1)

$\psi(M)$ is either discrete or open;

  2. (2)

if $\mathcal{M}\models\psi(a)$ then $t_{i_{1}}(a)\not=t_{i_{2}}(a)$ for
$i_{1}\not=i_{2}$, $s_{j_{1}}(a)\not=s_{j_{2}}(a)$ for $j_{2}\not=j_{2}$ and
$t_{i}(a)\not=s_{j}(a)$ for all $i,j$;

  3. (3)

if $\mathcal{M}\models\psi(a)$ then $t_{i}(a)\in(0,1)$ and $s_{j}(a)\in(0,1)$
for all $i,j$; and

  4. (4)

if $I$ is an open interval with $I\subseteq\psi(M)$ then no $t_{i}$ and no
$s_{j}$ is constant on $I$.

###### Proof.

By quantifier elimination for $T_{G}$ we reduce to the case where $X$ is
defined by a formula of the form:

$\psi_{0}(x)\wedge\bigwedge_{i\in I_{0}}P(t_{i}^{0}(x))\wedge\bigwedge_{j\in
J_{0}}\neg P(s^{0}_{j}(x))$

where $\psi_{0}$ is an $\mathcal{L}$-formula, $I_{0}$ and $J_{0}$ are finite
sets, and the $t^{0}_{i}$’s and $s^{0}_{j}$’s are terms. The proof is a
straightforward induction on $|I_{0}+J_{0}|$ and proceeds by repeatedly
partitioning the set defined by $\psi_{0}(x)$ into smaller
$\mathcal{L}$-definable subsets where (1) follows as any definable set in
$\mathcal{M}$ either is discrete or has interior, (2) is immediate, (3) is
immediate as $P(M)\subseteq(0,1)$, and (4) follows by Lemma 3.11 and the fact
that $T$ eliminates $\exists^{\infty}$ relative to $(0,1)$.

∎

######  Lemma 3.13.

If $\mathcal{M}\models T_{G}^{*}$ and $X\subseteq M$ is definable and discrete
then $X$ is definable in $\mathcal{M}\restriction\mathcal{L}$.

###### Proof.

Without loss of generality we may assume that $X$ is defined by a formula
$\varphi(x)$ of the form given in Lemma 3.12, say

$\varphi(x)=\psi(x)\wedge\bigwedge_{i\in I}P(t_{i}(x))\wedge\bigwedge_{j\in
J}\neg P(s_{j}(x)).$

If $\psi(M)$ has interior we can find an open interval $U\subseteq\psi(M)$ so
that each $t_{i}$ and $s_{j}$ is equal to a linear term of the form $\lambda
x+a$ on $U$. By assumption none of the $s_{i}$ and $t_{i}$ are equal on $U$
and none of them are constant. Thus by Fact 3.10 it must be the case that
$\varphi(M)$ is dense in $U$ and thus this case is impossible.

If $\psi(M)$ is discrete the image of $\psi(M)$ under any of the $t_{i}$ or
$s_{j}$ must be discrete. As these images are subsets of $(0,1)$ they must be
finite. It follows that $X$ is definable in
$\mathcal{M}\restriction\mathcal{L}$.

∎

Although we only need the following lemma in the specific case of models of
$T$ we provide a statement and proof in much greater generality.

######  Lemma 3.14.

Suppose that $\mathcal{N}$ is an expansion of a densely ordered group of
finite burden $n$. If $X\subseteq N$ is definable, infinite, and discrete,
then the burden of $X$ is less than or equal to $n-1$.

###### Proof.

Without loss of generality we assume that $\mathcal{N}$ is sufficiently
saturated. Suppose the result fails. Thus $X$ has burden $n$. Let the formulas
$\varphi_{i}(x,\overline{y})$ for $1\leq i\leq n$ and parameters
$\overline{a}_{i,j}$ for $1\leq i\leq n$ and $j\in\omega$ witness that $X$ has
burden $n$. Notice that we only need countably many elements from $X$ to
witness that the burden is $n$, thus by compactness we can find $\delta>0$ so
that

$X^{\prime}=\\{x\in X:(x-\delta,x+\delta)\cap X=\\{x\\}\\}$

also has burden $n$ witnessed by the same formulas and parameters.

We can find $0<\varepsilon_{j}^{0}<\varepsilon_{j}^{1}<\delta$ for
$j\in\omega$ so that $\varepsilon^{1}_{j}<\varepsilon^{0}_{j+1}$ for all
$j\in\omega$. Let $\varphi_{n+1}(x,y_{1}y_{2})$ be the formula

$\exists z\in X^{\prime}(z<x\wedge\forall w(w\in X^{\prime}\rightarrow w\leq
z\vee w>x)\wedge y_{1}<x-z<y_{2})$

and let $\varphi^{\prime}_{i}(x,\overline{y})$ for $1\leq i\leq n$ be the
formula

$\exists z(z\in X^{\prime}\wedge\forall w(w\in X^{\prime}\rightarrow w\leq
z\vee w>x)\wedge\varphi_{i}(x,\overline{y})).$

It now follows that the formulas
$\varphi^{\prime}_{1}(x,\overline{y})\dots\varphi^{\prime}_{n}(x,\overline{y})$
and $\varphi_{n+1}(x,y_{1}y_{2})$ with respective sequences of parameters
$\overline{a}_{1,j},\dots\overline{a}_{n,j}$ and
$\epsilon^{0}_{j},\epsilon^{1}_{j}$ witness that the theory of $\mathcal{N}$
has burden at least $n+1$, a contradiction. ∎

######  Proposition 3.15.

$T_{G}^{*}$ has burden $2$.

###### Proof.

Fix $\mathcal{M}$ a sufficiently saturated model of $T$ and suppose the result
fails. Let $\varphi_{k}(x,\overline{y})$ for $k\in\\{1,2,3\\}$ together with
mutually indiscernible parameters $\overline{a}_{k,l}$ with $k\in\\{1,2,3\\}$
and $l\in\R$ be an inp-pattern with three rows.

If any of the $\varphi_{k}(x,\overline{a}_{k,0})$, say $k=1$, defines a
discrete set $X$ then by Lemma 3.13 $X$ is definable in
$\mathcal{M}\restriction\mathcal{L}$. As $\mathcal{M}\restriction\mathcal{L}$
has dp-rank $2$, $X$ must have dp-rank $1$ in
$\mathcal{M}\restriction\mathcal{L}$ by Lemma 3.14. Now consider
$\varphi_{2}(M,\overline{a}_{2,0})\cap X$. This set is discrete and hence also
definable in $\mathcal{M}\restriction\mathcal{L}$, say by the
$\mathcal{L}$-formula $\theta_{2}(x,\overline{b}_{2,0})$. As
$\\{\overline{a}_{2,i}:i\in\R\\}$ is indiscernible over $\overline{a}_{1,0}$
we find $\\{\overline{b}_{2,i}:i\in\R\\}$ so that
$\theta_{2}(x,\overline{b}_{2,i})$ defines
$X\cap\varphi_{2}(x,\overline{a}_{2,i})$ for $i\in\R$. Similarly we find an
$\mathcal{L}$-formula $\theta_{3}(x,\overline{y})$ and parameters
$\\{\overline{b}_{3,i}:i\in\R\\}$ so that $\theta_{3}(x,\overline{b}_{3,i})$
defines $X\cap\varphi_{3}(x,\overline{a}_{3,i})$ for all $i\in\R$. Hence the
pair of formulas $\theta_{2}(x,\overline{y})$ and $\theta_{3}(x,\overline{y})$
with respective sequences of parameters $\\{\overline{b}_{2,i}:i\in\R\\}$ and
$\\{\overline{b}_{3,i}:i\in\R\\}$ witnesses that $X$ has burden $2$. But then
$X$ has dp-rank $2$, a contradiction.

Consider $\varphi_{1}(x,\overline{y})$. By [4, Lemma 7.1] we may assume that
this formula is of the form given by Lemma 3.12, say

$\varphi_{1}(x,\overline{y})=\psi_{1}(x,\overline{y})\wedge\bigwedge_{i\in
I}P(t_{i}(x,\overline{y}))\wedge\bigwedge_{j\in J}\neg
P(s_{j}(x,\overline{y}))$

with $\psi_{1}(M,\overline{a}_{1,0})$ open.

Suppose that $\\{\psi_{1}(x,\overline{a}_{1,l}):l\in\R\\}$ is consistent. Then
by compactness we may find an open interval $V=(c,d)$ so that $V$ is a subset
of $\psi_{1}(M,\overline{a}_{1,l})$ for all $l\in\R$. By shrinking $V$ further
we may also assume by Fact 3.8(6) that all the terms
$t_{i}(x,\overline{a}_{1,l})$ and $s_{j}(x,\overline{a}_{1,l})$ are given by
linear functions of the form $\lambda x+a$ on $V$. As
$\mathcal{M}\restriction\mathcal{L}$ is of dp-rank 2, by [21, Theorem 4.16] we
may find an open interval $W\subset\R$ so that $\\{\overline{a}_{1,j}:j\in
W\\}$ is indiscernible over $cd$ as a sequence in
$\mathcal{M}\restriction\mathcal{L}$. For notational convenience assume that
$W=\R$.

Fix $\kappa\in\omega$ such that
$\\{\varphi_{1}(x,\overline{a}_{1,l}):l\in\R\\}$ is $\kappa$-inconsistent. By
the assumptions on the formula $\varphi_{1}(x,\overline{y})$ from Lemma 3.12
all the terms are continuous, monotone, and non-constant on $V$ and we have
guaranteed that they are also all linear on $V$. But then by Fact 3.10 we can
only have $\kappa$-inconsistency of
$\\{\varphi_{1}(x,\overline{a}_{1,l}):l\in\R\\}$ if for some $i\in I$, some
$j\in J$, and some $l_{1},l_{2}\in\R$, we have that
$t_{i}(x,\overline{a}_{1,l_{1}})=s_{j}(x,\overline{a}_{1,l_{2}})$ densely
often in some subinterval of $V$. As these functions are linear over , it
follows that $t_{i}(x,\overline{a}_{1,l_{1}})=s_{j}(x,\overline{a}_{1,l_{2}})$
on all of $V$. Then by indiscernibility of $\overline{a}_{1,l}$ over $cd$ (as
an $\mathcal{M}\restriction\mathcal{L}$-sequence) it follows that
$t_{i}(x,\overline{a}_{1,0})=s_{j}(x,\overline{a}_{1,0})$ on $V$. But this
violates the properties of $\varphi_{1}$ guaranteed by Lemma 3.12.

Thus it must be the case that $\\{\psi_{1}(x,\overline{a}_{1,l}):l\in\R\\}$ is
inconsistent. But the same holds for
$\\{\psi_{k}(x,\overline{a}_{k,l}):l\in\R\\}$ for $k\in\\{2,3\\}$. Thus
$\psi_{k}(x,\overline{y})$ for $k\in\\{1,2,3\\}$ and $\overline{a}_{k,l}$ for
$k\in\\{1,2,3\\}$ and $l\in\R$ is an inp-pattern with three rows in
$\mathcal{M}\restriction\mathcal{L}$ which is impossible as
$\mathcal{M}\restriction\mathcal{L}$ has dp-rank $2$.

∎

This example demonstrates that the results in Section 2 of this paper are in
some sense sharp. In particular notice that as indicated in Theorem 2.26 the
formula $\tau(x,y):=x\in P-y$ has the independence property by the axioms for
$T_{G}$.

## References

  * [1] Hans Adler.  Strong theories, burden, and weight.  available on the author’s website, 2007.
  * [2] E. Casanovas, D. Lascar, A. Pillay, and M. Ziegler.  Galois groups of first order theories.  Journal of Mathematical Logic, 1(2):305–319, 2001.
  * [3] Zoé Chatzidakis and Anand Pillay.  Generic structures and simple theories.  Annals of Pure and Applied Logic, 95:71–92, 1998.
  * [4] Artem Chernikov.  Theories without the tree property of the second kind.  Annals of Pure and Applied Logic, 165(2):695–723, February 2014\.
  * [5] Alfred Dolich and John Goodrick.  Strong theories of ordered abelian groups.  Fundamenta Mathematicae, 236:269–296, 2017.
  * [6] Alfred Dolich and John Goodrick.  A characterization of strongly dependent ordered Abelian groups.  Revista Colombiana de Matemáticas, 52(2):139–159, 2018.
  * [7] Alfred Dolich and John Goodrick.  Discrete sets definable in strong expansions of ordered Abelian groups.  arXiv preprint 2208.06929, 2022.
  * [8] Alfred Dolich and John Goodrick.  Tame topology over definable uniform structures.  Notre Dame Journal of Formal Logic, 63(1):51–79, 2022.
  * [9] Alfred Dolich, Chris Miller, and Charles Steinhorn.  Structures having o-minimal open core.  Transactions of the American Mathematical Society, 362:1371–1411, 2010.
  * [10] John Goodrick.  A monotonicity theorem for dp-minimal densely ordered groups.  Journal of Symbolic Logic, 75(1):221–238, 2010.
  * [11] John Goodrick.  Definable sets in dp-minimal ordered abelian groups.  RIMS Kôkyûroku 2218 (proceedings of the RIMS Model Theory Workshop 2021), 2022.
  * [12] Ehud Hrushovski and Anand Pillay.  On NIP and invariant measures.  Jounral of the European Mathematical Society, 13(4):1005–1061, 2011\.
  * [13] Will Johnson.  Dp-finite fields VI: the dp-finite Shelah conjecture.  arXiv preprint 2005.13989, 2020.
  * [14] Dugald Macpherson, David Marker, and Charles Steinhorn.  Weakly o-minimal structures and real closed fields.  Transactions of the American Mathematical Society, 352(12):5435–5483, 2000.
  * [15] Chris Miller.  Expansions of dense linear orders with the intermediate value property.  The Journal of Symbolic Logic, 66:1783–1790, 2001.
  * [16] Samaria Montenegro.  Pseudo real closed fields, pseudo p-adically closed fields and NTP2.  Annals of Pure and Applied Logic, 168(1):191–232, 2017.
  * [17] Alf Onshuus and Alexander Usvyatsov.  On dp-minimality, strong dependence, and weight.  The Journal of Symbolic Logic, 76(3):737–758, September 2011.  available on second author’s website.
  * [18] Saharon Shelah.  Dependent first order theories, continued.  Israel Journal of Mathematics, 173(1):1–60, 2009.
  * [19] Saharon Shelah.  Strongly dependent theories.  Israel Journal of Mathematics, 204(1):1–83, 2014.
  * [20] Pierre Simon.  On dp-minimal ordered structures.  The Journal of Symbolic Logic, 76(2):448–460, June 2011.
  * [21] Pierre Simon.  A Guide to NIP Theories.  Cambridge University Press, 2015.


If $S_{i}\subseteq{\mathcal{W}}$ and $u\in{\mathcal{R}}$, for any arbitrary
$v_{i}$ we may take:

$\widehat{\Delta{\mathcal{G}}}^{\rm
gr}_{i}(S,u)=\begin{cases}\mathsf{err}^{\rm
indv}(u)\cdot\prod_{\begin{subarray}{c}v_{j}\in S\\\ \bar{W}_{ij}\neq
0\end{subarray}}(1-\mathsf{err}^{\rm indv}(v_{j}))&\quad\text{if
}\Psi_{i}({\mathcal{B}}\cup S,{\mathcal{R}}\cup\\{u\\})<0\\\
0&\quad\text{otherwise}\end{cases}$

If $u\in{\mathcal{B}}$, for any arbitrary $v_{i}$ we may take:

$\widehat{\Delta{\mathcal{G}}}^{\rm
gr}_{i}(S,u)=\begin{cases}\mathsf{err}^{\rm
indv}(u)\cdot\prod_{\begin{subarray}{c}v_{j}\in S\\\ \bar{W}_{ij}\neq
0\end{subarray}}(1-\mathsf{err}^{\rm indv}(v_{j}))&\quad\text{if
}\Psi_{i}({\mathcal{R}}\cup S,{\mathcal{B}}\cup\\{u\\})<0\\\
0&\quad\text{otherwise}\end{cases}$

and in both cases we have:

$\absolutevalue{\widehat{\Delta{\mathcal{G}}}_{i}^{\rm
gr}(S,u)-\Delta{\mathcal{G}}_{i}^{\rm
gr}(S,u)}\leq\exp\left(-\frac{(\Psi_{i}^{\mathcal{W}}(u)-\Delta\bar{W}_{i})^{2}}{4\sum_{v_{j}\in{\mathcal{W}}}\bar{W}_{ij}^{2}}\right)~{}.$

###### Proof.

Like previous lemma we have:

$\displaystyle\operatorname*{\mathbb{P}}^{\rm
gr}_{a\sim\Omega^{+}}\left(z(i,a)\leq
0\mid{\mathcal{T}}_{i}(S)\wedge{\mathcal{F}}(u)\right)$ $\displaystyle=$
$\displaystyle\operatorname*{\mathbb{P}}_{a\sim\Omega^{+}}\left(\sum_{\begin{subarray}{c}v_{j}\in{\mathcal{W}}\\\
v_{j}\notin S\cup\\{u\\}\end{subarray}}\bar{W}_{ij}\hat{y}^{\rm
indv}_{j}(a)+\sum_{v_{j}\in{\mathcal{R}}}\bar{W}_{ij}\hat{y}^{\rm
gr}_{j}(a)+\sum_{v_{j}\in{\mathcal{B}}}\bar{W}_{ij}\hat{y}^{\rm
gr}_{j}(a)+\sum_{v_{j}\in S}\bar{W}_{ij}-\bar{W}_{iu}\leq 0\right)$

If $u\in{\mathcal{R}}$ since we are conditioning on ${\mathcal{F}}(u)$ the
above probability is equal to:

$\displaystyle\operatorname*{\mathbb{P}}^{\rm
gr}_{a\sim\Omega^{+}}\left(z(i,a)\leq
0\mid{\mathcal{T}}_{i}(S)\wedge{\mathcal{F}}(u)\right)$
$\displaystyle=\Gamma_{i}^{+}({\mathcal{B}}\cup
S,{\mathcal{R}}\cup\\{u\\})~{}.$

Similarly

$\displaystyle\operatorname*{\mathbb{P}}^{\rm
gr}_{a\sim\Omega^{+}}\left(z(i,a)\geq
0\mid{\mathcal{T}}_{i}(S)\wedge{\mathcal{F}}(u)\right)$
$\displaystyle=\Gamma_{i}^{-}({\mathcal{B}}\cup
S,{\mathcal{R}}\cup\\{u\\})~{}.$

If $u\in{\mathcal{B}}$ we have

$\displaystyle\operatorname*{\mathbb{P}}^{\rm
gr}_{a\sim\Omega^{+}}\left(z(i,a)\leq
0\mid{\mathcal{T}}_{i}(S)\wedge{\mathcal{F}}(u)\right)$
$\displaystyle=\Gamma_{i}^{+}({\mathcal{R}}\cup
S,{\mathcal{B}}\cup\\{u\\})~{}.$

Similarly

$\displaystyle\operatorname*{\mathbb{P}}^{\rm
gr}_{a\sim\Omega^{+}}\left(z(i,a)\geq
0\mid{\mathcal{T}}_{i}(S)\wedge{\mathcal{F}}(u)\right)$
$\displaystyle=\Gamma_{i}^{-}({\mathcal{R}}\cup
S,{\mathcal{B}}\cup\\{u\\})~{}.$

Putting together, and employing lemma A.13 we get the premise.

∎

####  A.5.2 Case 2. monochromatic $S_{i}$

######  Lemma A.16.

Let ${\mathcal{C}}$ be either ${\mathcal{R}}$ or ${\mathcal{B}}$ and
${\bar{\mathcal{C}}}$ be the other color. Assume
$S_{i}\cap{\mathcal{C}}\neq\emptyset$ and
$S_{i}\cap{\bar{\mathcal{C}}}=\emptyset$. In this case, for any
$u\in{\mathcal{C}}$, we have $\forall i,\Delta{\mathcal{G}}^{\rm
gr}_{i}(S,u)=0$.

For $u\in{\bar{\mathcal{C}}}$ we may use the following estimation:

$\widehat{\Delta{\mathcal{G}}}_{i}^{\rm
gr}\left(S,u\right)=\begin{cases}\mathsf{err}({\bar{\mathcal{C}}})\prod_{v_{j}\in
S_{i}\cap{\mathcal{W}}}(1-\mathsf{err}^{\rm indv}(v_{j}))&\text{ if
}\quad\Psi_{i}({\mathcal{C}}\cup S,{\bar{\mathcal{C}}})<0\\\ 0&\text{
otherwise ~{}.}\end{cases}$

and for $u\in{\mathcal{W}}$ we may use the following estimation:

$\widehat{\Delta{\mathcal{G}}}_{i}^{\rm
gr}\left(S,u\right)=\begin{cases}\mathsf{err}(u)\mathsf{err}({\bar{\mathcal{C}}})\prod_{v_{j}\in
S_{i}\cap{\mathcal{W}}}(1-\mathsf{err}^{\rm indv}(v_{j}))&\text{ if
}\quad\Psi_{i}({\mathcal{C}}\cup S,{\bar{\mathcal{C}}}\cup\\{u\\})<0\\\
0&\text{ otherwise ~{}.}\end{cases}$

The above estimations satisfy:

$\absolutevalue{\widehat{\Delta{\mathcal{G}}}^{\rm
gr}_{i}(S,u)-\Delta{\mathcal{G}}^{\rm
gr}_{i}(S,u)}\leq\exp\left(-\frac{(\Psi_{i}^{\mathcal{W}}(u)-\Delta\bar{W}_{i})^{2}}{4\sum_{v_{j}\in{\mathcal{W}}}\bar{W}_{ij}^{2}}\right)~{}.$

###### Proof of lemma A.16.

Assume that $S_{i}$ intersects only with one color ${\mathcal{C}}$ and its
intersection with the other color ${\bar{\mathcal{C}}}$ is empty.

If $u\in{\mathcal{C}}$, then
$\operatorname*{\mathbb{P}}({\mathcal{T}}_{i}(S)\wedge{\mathcal{F}}(u))=0$.
Thus, $\forall i\ \Delta{\mathcal{G}}^{\rm gr}_{i}(S,u)=0$.

If $u\in{\bar{\mathcal{C}}}$:

We have that
$\operatorname*{\mathbb{P}}({\mathcal{T}}_{i}(S)\wedge{\mathcal{F}}(u))=\mathsf{err}({\bar{\mathcal{C}}})\cdot\prod_{v_{j}\in
S_{i}\cap{\mathcal{W}}}(1-\mathsf{err}^{\rm indv}(v_{j}))$ . Furthermore,

$\displaystyle\operatorname*{\mathbb{P}}^{\rm
gr}_{a\in\Omega^{+}}\left(z^{*}(i,a)\leq
0\mid{\mathcal{T}}_{i}(S)\wedge{\mathcal{F}}(u)\right)$
$\displaystyle=\operatorname*{\mathbb{P}}\left(\sum_{v_{j}\in{\mathcal{W}}\setminus
S_{i}}\bar{W}_{ij}\hat{y}^{\rm
indv}_{j}(a)+\bar{W}({\mathcal{C}})-\bar{W}({\bar{\mathcal{C}}})+\bar{W}(S\cap{\mathcal{W}})\leq
0\right)$ $\displaystyle=\Gamma_{i}^{+}\left({\mathcal{C}}\cup
S,{\bar{\mathcal{C}}}\right)~{}.$

Similarly,

$\displaystyle\operatorname*{\mathbb{P}}^{\rm
gr}_{a\in\Omega^{-}}\left(z^{*}(i,a)\geq
0\mid{\mathcal{T}}_{i}(S)\wedge{\mathcal{F}}(u)\right)=\Gamma_{i}^{-}\left({\mathcal{C}}\cup
S,{\bar{\mathcal{C}}}\right)~{}.$

Putting together and employing lemma A.13 we conclude the first part of the
premise.

If $u\in{\mathcal{W}}$: We have that
$\operatorname*{\mathbb{P}}({\mathcal{T}}_{i}(S)\wedge{\mathcal{F}}(u))=\mathsf{err}(u)\mathsf{err}({\bar{\mathcal{C}}})\cdot\prod_{v_{j}\in
S_{i}\cap{\mathcal{W}}}(1-\mathsf{err}^{\rm indv}(v_{j}))$. Furthermore,

$\displaystyle\operatorname*{\mathbb{P}}^{\rm
gr}_{a\in\Omega^{+}}\left(z^{*}(i,a)\leq
0\mid{\mathcal{T}}_{i}(S)\wedge{\mathcal{F}}(u)\right)$
$\displaystyle=\operatorname*{\mathbb{P}}\left(\sum_{v_{j}\in{\mathcal{W}}\setminus
S_{i}}\bar{W}_{ij}\hat{y}^{\rm
indv}_{j}(a)+\bar{W}_{i}({\mathcal{C}})-\bar{W}_{i}({\bar{\mathcal{C}}})+\bar{W}_{i}(S\cap{\mathcal{W}})-\bar{W}_{iu}\leq
0\right)$ $\displaystyle=\Gamma_{i}^{+}\left({\mathcal{C}}\cup
S,{\bar{\mathcal{C}}}\cup\\{u\\}\right)~{}.$

Similarly,

$\displaystyle\operatorname*{\mathbb{P}}^{\rm
gr}_{a\in\Omega^{-}}\left(z^{*}(i,a)\geq
0\mid{\mathcal{T}}_{i}(S)\wedge{\mathcal{F}}(u)\right)$
$\displaystyle=\Gamma_{i}^{-}\left({\mathcal{C}}\cup
S,{\bar{\mathcal{C}}}\cup\\{u\\}\right)~{}.$

Putting together and employing lemma A.13 we conclude the second part of the
premise. ∎

####  A.5.3 Case 3. bichromatic $S_{i}$

######  Lemma A.17.

If $S_{i}\cap{\mathcal{R}}\neq\emptyset$ and
$S_{i}\cap{\mathcal{B}}\neq\emptyset$, we have $\forall i\
\Delta{\mathcal{G}}^{\rm gr}_{i}(S,u)=0$.

###### Proof.

Note that $\operatorname*{\mathbb{P}}({\mathcal{T}}_{i}(S))=0$. Thus, we
conclude the premise. ∎

####  A.5.4 Missing material from section 4.2.2:
$\boldsymbol{{\mathcal{W}}}$-Ambiguous vertices.

Let’s first present the definition of ${\mathcal{W}}$-ambiguous vertices in
detail:

Consider the following partitioning of white vertices to low and high error
parts:

${\mathcal{W}}^{+}=\\{v_{j}\mid\mathsf{err}(v_{j})\leq 1/2\\}\ \ \&\
{\mathcal{W}}^{-}=\\{v_{j}\mid\mathsf{err}(v_{j})>1/2\\}$

with respect to this partition we define the following vectors:

${\mathcal{E}^{\mathcal{W}}}^{+}{=}\left(1-2\mathsf{err}(v_{j})\right)_{v_{j}\in{\mathcal{W}}^{+}}\
\ \&\
\quad{\mathcal{E}^{\mathcal{W}}}^{-}{=}\left(2\mathsf{err}(v_{j})-1\right)_{v_{j}\in{\mathcal{W}}^{-}}$
$\text{ and }\
\quad\quad\quad\quad{\bar{W}^{{\mathcal{W}}+}_{i}}=(\bar{W}_{ij})_{v_{j}\in{\mathcal{W}}^{+}}\
\ \&\quad\
{\bar{W}^{{\mathcal{W}}-}_{i}}=(\bar{W}_{ij})_{v_{j}\in{\mathcal{W}}^{-}}$

######  Definition A.18 ( ${\mathcal{W}}$-Ambiguous vertices ).

Let $\bar{W}^{\mathcal{W}}_{i}=(\bar{W}_{ij})_{v_{j}\in{\mathcal{W}}}$, and
$\absolutevalue{\cdot}_{2}$ be the $\ell_{2}$ norm and
$\langle\cdot,\cdot\rangle$ be dot product.

We call an agent $v_{i}\in V$, _${\mathcal{W}}$ -ambiguous_ if it satisfies

$\absolutevalue{\frac{\langle{\bar{W}^{{\mathcal{W}}+}_{i}},{\mathcal{E}^{\mathcal{W}}}^{+}\rangle}{\absolutevalue{\bar{W}_{i}^{\mathcal{W}}}_{2}}-\frac{\langle{\bar{W}^{{\mathcal{W}}-}_{i}},{\mathcal{E}^{\mathcal{W}}}^{-}\rangle}{\absolutevalue{\bar{W}_{i}^{\mathcal{W}}}_{2}}}\leq
4\sqrt{\log n}+\Delta\bar{W}_{i}~{},$

where
$\Delta\bar{W}_{i}=\absolutevalue{\sum_{v_{j}\in{\mathcal{R}}}\bar{W}_{ij}-\sum_{v_{j}\in{\mathcal{B}}}\bar{W}_{ij}}~{}.$
A _network_ is _nicely colored_ if no vertex is ${\mathcal{W}}$-ambiguous.

We now show that if a vertex is _not_ ambiguous w.r.t. ${\mathcal{W}}$ the
group gain associated to it can be estimated with high precision:

######  Lemma A.19.

Let $\widehat{\Delta{\mathcal{G}}_{i}}^{\rm gr}(S,u)$ be as defined in lemmas
A.14, A.16 and A.17. If a vertex is _non-ambiguous_ w.r.t ${\mathcal{W}}$ we
have:

$\absolutevalue{\Delta{\mathcal{G}}^{\rm
gr}_{i}(S,u)-\widehat{\Delta{\mathcal{G}}}^{\rm gr}_{i}(S,u)}\leq
o(n^{-1})~{}.$

###### Proof.

Note that from lemmas A.14, A.16 and A.17 we have that for any $v_{i}$:

$\absolutevalue{\Delta{\mathcal{G}}^{\rm
gr}_{i}(S,u)-\widehat{\Delta{\mathcal{G}}}^{\rm
gr}_{i}(S,u)}\leq\exp\left(-\frac{(\Psi_{i}^{\mathcal{W}}(u)-\Delta\bar{W}_{i})^{2}}{4\sum_{v_{j}\in{\mathcal{W}}}\bar{W}_{ij}^{2}}\right)~{}.$

Note that we have:

$\displaystyle\frac{(\Psi_{i}^{{\mathcal{W}}}(u)-\Delta\bar{W}_{i})^{2}}{\sum_{v_{j}\in{\mathcal{W}}}\bar{W}_{ij}^{2}}$
$\displaystyle=\left(\frac{\Psi_{i}^{{\mathcal{W}}}(u)-\Delta\bar{W}_{i}}{\absolutevalue{\bar{W}_{i}^{\mathcal{W}}}_{2}}\right)^{2}$
$\displaystyle=\left(\frac{\langle\bar{W}_{i}^{{\mathcal{W}}+},{\mathcal{E}}^{{\mathcal{W}}+}\rangle}{\absolutevalue{\bar{W}_{i}^{\mathcal{W}}}_{2}}-\frac{\langle\bar{W}_{i}^{{\mathcal{W}}-},{\mathcal{E}}^{{\mathcal{W}}-}\rangle}{\absolutevalue{\bar{W}_{i}^{\mathcal{W}}}_{2}}-\frac{2\mathsf{err}(u)\bar{W}_{iu}}{\absolutevalue{\bar{W}_{i}^{\mathcal{W}}}_{2}}-\frac{\Delta\bar{W}_{i}}{\absolutevalue{\bar{W}_{i}^{\mathcal{W}}}_{2}}\right)^{2}$
$\displaystyle\geq\left(\frac{\langle\bar{W}_{i}^{{\mathcal{W}}+},{\mathcal{E}}^{{\mathcal{W}}+}\rangle}{\absolutevalue{\bar{W}_{i}^{\mathcal{W}}}_{2}}-\frac{\langle\bar{W}_{i}^{{\mathcal{W}}-},{\mathcal{E}}^{{\mathcal{W}}-}\rangle}{\absolutevalue{\bar{W}_{i}^{\mathcal{W}}}_{2}}-\frac{\Delta\bar{W}_{i}}{\absolutevalue{\bar{W}_{i}^{\mathcal{W}}}_{2}}-2\right)^{2}$

Assuming that the vertex is not ambiguous w.r.t. whites we have:

$\absolutevalue{\frac{\langle{\bar{W}^{{\mathcal{W}}+}_{i}},{\mathcal{E}^{\mathcal{W}}}^{+}\rangle}{\absolutevalue{\bar{W}_{i}^{\mathcal{W}}}_{2}}-\frac{\langle{\bar{W}^{{\mathcal{W}}-}_{i}},{\mathcal{E}^{\mathcal{W}}}^{-}\rangle}{\absolutevalue{\bar{W}_{i}^{\mathcal{W}}}_{2}}}>4\sqrt{\log
n}+\Delta\bar{W}_{i}$

which implies

$\frac{(\Psi_{i}^{{\mathcal{W}}}(u)-\Delta\bar{W}_{i})^{2}}{\sum_{v_{j}\in{\mathcal{W}}}\bar{W}_{ij}^{2}}=\left(\frac{\Psi_{i}^{{\mathcal{W}}}(u)-\Delta\bar{W}_{i}}{\absolutevalue{\bar{W}_{i}^{\mathcal{W}}}_{2}}\right)^{2}\geq(3\sqrt{\log
n})^{2}\geq 5\log n$

From which we conclude that the error is bounded as:

$\exp\left(-\frac{(\Psi_{i}^{{\mathcal{W}}}(u)-\Delta\bar{W}_{i})^{2}}{\sum_{v_{j}\in{\mathcal{W}}}\bar{W}_{ij}^{2}}\right)\leq\exp(-5/4\log
n)=o(n^{-1})~{}.$

∎

####  A.5.5 Missing material from section 4.2.2: proof of the main theorems

###### Proof of theorem 4.8 and remark 3.12.

Note that the error of the greedy choice approximation is either generated
from approximation of $\sum_{i=1}^{n}\widehat{\Delta{\mathcal{G}}}^{\rm
gr}_{i}(S,u)$ or $\sum_{i=1}^{n}\widehat{\Delta{\mathcal{G}}}^{\rm
indv}_{i}(S,u)$. The error of $\widehat{\Delta{\mathcal{G}}}^{\rm
indv}_{i}(S,u)$ may be bounded similar to the independent case. To see the
bound the error of $\sum_{i=1}^{n}\widehat{\Delta{\mathcal{G}}}^{\rm
gr}_{i}(S,u)$ note that the error induced by all _non-ambiguous_ vertices is
$o(n\times n^{-1})=o(1)$. The error of each ambiguous vertex is at most one,
therefore, we conclude the result.

##### Approximation when having access $\widehat{{\mathcal{W}}}$.

Follows similarly as in lemma A.11 ∎

###  A.6 Concentration Bounds

######  Theorem A.20.

Let $X_{1},X_{2},\dots X_{k}$ be independent random variables in range
$[-1,1]$ with means $\mu_{1},\dots,\mu_{k}$ and let $w_{i}$s be weight
coefficients . Taking $\mu=\sum_{i=1}^{k}w_{i}\mu_{i}$. We have that for any
$\varepsilon>0$:

$\operatorname*{\mathbb{P}}\left(\sum_{i=1}^{k}w_{i}X_{i}\geq\mu+\varepsilon\right)\leq\exp\left({-\frac{\varepsilon^{2}}{4\sum_{i=1}^{k}w_{i}^{2}}}\right),~{}$

and

$\operatorname*{\mathbb{P}}\left(\sum_{i=1}^{k}w_{i}X_{i}\leq\mu-\varepsilon\right)\leq\exp\left({-\frac{\varepsilon^{2}}{4\sum_{i=1}^{k}w_{i}^{2}}}\right)~{}.$

##  Appendix B Additional experiments and details of set up

Our proposed problem and methods in general do not assume any prior knowledge
of the given datasets. Our algorithms are deterministic with no parameter to
tune. It has potential to be applied to any problems as long as the objective
function of the problems of interests related to our proposed objective
function. In the following, we include the parameter settings of the problems
in our experiments. These parameters are not tuned for our methods. We just
fix the parameters to make sure the problems are nontrivial enough. We use the
same parameters for all methods in our experiments.

We let $\absolutevalue{\Omega}=3$ and for initial opinion $\mathbf{\hat{y}}$,
we randomly generate for each agent $v_{i}$ a random vector
$(\hat{y}_{i}(a):a\in\Omega)$ with each entry sampled from Bernoulli
distribution with probability $p_{i}$ of $\hat{y}_{i}(a)=+1$ sampled uniformly
from $[0.3,0.9]$. For random graph generators, some of the key parameters are
fixed as follows:

  * •

Number of nodes: 128

  * •

Erdős-Rényi graph: Probability for edge creation $p=0.005$.

  * •

Barabási-Albert preferential attachment model: Number of edges to attach from
a new node to existing nodes $m=5$

  * •

Watts-Strogatz small-world graph: Each node is joined with its $k=5$ nearest
neighbors in a ring topology; The probability of rewiring each edge $p=0.25$

In practice, we found that the infinite FJ model with weight matrix converging
to $(I+L)^{-1}$ makes the problem less interesting than general case in
practice. The reason is that all entries of the matrix $(I+L)^{-1}$ are
positive and non-zero. With such weight matrix, we found even a random
selection algorithm can converge very fast. To avoid such simple cases, here
we apply a finite $t$-step FJ model. We fix $t=3$ to ensure the induced matrix
$\bar{W}$ is sparse enough.

Besides randomly generated graphs from tree classical models (ER, PA and WS),
we also test our algorithms on random generated matrix $\bar{W}$ directly,
denoted as RandomW. Each entry of $\bar{W}$ is independently sampled from a
uniform distribution on $[0,1]$. We let the sparsity of $\bar{W}$ to be around
$0.95$. Each row of $\bar{W}$ is normalized thus sum up to be $1$.

The statistics of real and synthetic datasets are summarized in table 2.
Experiment results are illustrated in fig. 3.

We let the set of faulty prediction be
$\mathcal{Z}^{f}\triangleq\mathbb{E}_{a\in\Omega}[\sum_{i=1}^{n}\mathbf{1}\mathcal{Z}(i,a)<0]$
, which serves as an upperbound on the egalitarian improvement. We define the
accuracy Acc as:

${\rm Acc}=\frac{\mathcal{G}^{({\rm egal})}(S)}{{\mathcal{Z}^{f}}}~{}.$

We calculate all expected values by taking averages over $a\in\Omega$.

Table 2: Table of statistics of datasets. Sparsity of $\bar{W}$ represents the percentage of zero entries in $\bar{W}$.  | size | sparsity of $\bar{W}$ | faulty prediction ${\mathcal{Z}^{f}}$
---|---|---|---
ER | 128 | 0.98 | 74.67
PA | 128 | 0.37 | 32.0
WS | 128 | 0.74 | 38.67
BIO | 297 | 0.45 | 55.33
CSPK | 39 | 0.75 | 14.67
FB | 620 | 0.75 | 161.33
WIKI | 890 | 0.66 | 238.67
RandomW | 128 | 0.95 | 37.67
|
---|---
|
|
Figure 3: More experimental results on different datasets.